API reference

Reading graphs

Reading graph files (read_graph_from_file) and one-time start-up (warm_up).

orbitsi.utils.read_graph_from_file(filepath, build_index=True)

Read a graph file into a NetworkX graph.

The file is parsed in C++ straight into arrays (see Graph file format). The result is an orbitsi.arraygraph.ArrayGraph: a networkx.Graph whose node and adjacency dictionaries are built only when first used.

Parameters:

• filepath (str or os.PathLike) – Path to the graph file.

• build_index (bool, default True) – Also build the graph’s integer index (orbitsi.graphindex.GraphIndex), its neighbour-label frequencies and the C++ core’s copy (orbitsi.core.data_graph()), so that their cost is paid here and not by the first pattern searched; also runs warm_up() once per process.

Returns:

networkx.Graph – The undirected graph, with each node’s label in its 'label' attribute.

Raises:

ValueError – If a v or e line has a missing or non-integer field, or an integer outside 64 bits.

orbitsi.utils.warm_up()

Pay one-time library start-up costs now.

Runs filtering, ordering and counting once on a tiny graph with both backends, so that one-time start-up (NumPy’s first sort sets up its SIMD dispatch, about 50 ms; the first calls of other array routines and of the C++ extensions) is paid at load, not by the first pattern. Does nothing after its first call in a process.

class orbitsi.arraygraph.ArrayGraph(*args, backend=None, **kwargs)

Bases: Graph

A networkx.Graph read into arrays, whose NetworkX dictionaries are built on first use.

orbitsi.utils.read_graph_from_file() returns one. Until its node or adjacency dictionaries are first read, GraphIndex and the C++ core use its arrays directly; number_of_nodes() and len() also work without them. Any other NetworkX use (iterating nodes or edges, copy(), subgraph(), mutation, NetworkX algorithms) builds them, in the order NetworkX would have built them from the same file, and the object then becomes a plain networkx.Graph. Pickling and deep copies keep it unbuilt.

Parameters:

• incoming_graph_data (optional) – As for networkx.Graph; used only when arrays is None, in which case the result is a plain networkx.Graph.

• arrays (tuple of numpy.ndarray, optional) – (node_ids, labels, has_label, offsets, nbors) as returned by _orbitsi_core.read_graph: node IDs in node order, each node’s label and whether it has one, and the adjacency in CSR form over node positions (the neighbours of node i are nbors[offsets[i]:offsets[i + 1]]).

• **attr – Graph attributes, as for networkx.Graph.

number_of_nodes()

The number of nodes, without building the NetworkX dictionaries.

Search

class orbitsi.search.OrbitSIEngine(data_graph, orbit_counter_class, graphlet_size=4, order_method='auto', arc_consistency=False, contraction=True, backend='cpp', edge_thinning=True, tail=True, published=False)

Bases: object

OrbitSI’s subgraph isomorphism search over one data graph.

Filtering is LDF and NLF, then one orbit filter on the candidate-induced subgraph (FilterEngine); then a matching order (OrderEngine) and a backtracking search (SearchEngine). count() runs the same pipeline in C++ (orbitsi.core) by default.

Parameters:

• data_graph (networkx.Graph) – The data graph, with node labels in the 'label' attribute.

• orbit_counter_class (type) – EVOKEOrbitCounter or ORCAOrbitCounter.

• graphlet_size ({4, 5}, default 4) – Graphlet size of the orbit filter (ORCA supports 4 only).

• order_method ({'auto', 'core'}, default 'auto') – ‘auto’ is OrbitSI’s orbit-strength order; ‘core’ puts the pattern’s 2-core first.

• arc_consistency (bool, default False) – Add arc consistency before and after the orbit filter (not in OrbitSI as published).

• contraction (bool, default True) – Repeat NLF inside the candidate subgraph before the orbit filter (not in OrbitSI as published).

• backend ({'cpp', 'python'}, default 'cpp') – Implementation of count(); ‘cpp’ applies only with EVOKE, otherwise the count runs in Python. run() always runs in Python.

• edge_thinning (bool, default True) – Count orbits only on the candidate subgraph’s edges that some pattern edge can map onto (not in OrbitSI as published).

• tail (bool, default True) – Count the last pattern vertices together instead of searching them (not in OrbitSI as published).

• published (bool, default False) – OrbitSI’s algorithm as published: overrides order_method (‘auto’) and turns off arc_consistency, contraction, edge_thinning and tail. The candidates, the order and the count are the published algorithm’s; the implementation is the current one.

Notes

None of the options changes the embeddings found or their number.

run(pattern_graph)

List every embedding of a pattern.

Parameters:

pattern_graph (networkx.Graph) – The pattern, with node labels in the 'label' attribute.

Returns:

list of dict – One {pattern node: data node} dict per embedding.

count(pattern_graph)

Count the embeddings of a pattern without materialising them.

Parameters:

pattern_graph (networkx.Graph) – The pattern, with node labels in the 'label' attribute.

Returns:

int

class orbitsi.search.FilterEngine(data_graph, pattern_graph, orbit_counter_class, graphlet_size=4, arc_consistency=False, contraction=True, edge_thinning=True)

Bases: object

OrbitSI’s filter: the candidate data vertices of each pattern vertex.

LDF (label and degree), then NLF (neighbour-label frequencies, on the full data graph), then one orbit pass: the subgraph of the data graph induced by every remaining candidate is orbit-counted, and a candidate v of pattern vertex u survives if each of v’s non-induced orbit counts there is at least u’s in the pattern. Orbits that every pattern vertex has 0 of are neither compared nor, where the counter can skip them, counted.

The data graph is processed as integer arrays (orbitsi.graphindex.GraphIndex, built once per graph and cached). The candidates of all pattern vertices are held together in two flat arrays, so LDF, NLF and the orbit comparison each take a fixed number of array operations, whatever the pattern’s size. The candidate subgraph is built in CSR form and handed to the orbit counter directly when it provides count_csr.

Parameters:

• data_graph (networkx.Graph) – The data graph and the pattern, with node labels in the 'label' attribute.

• pattern_graph (networkx.Graph) – The data graph and the pattern, with node labels in the 'label' attribute.

• orbit_counter_class (type) – EVOKEOrbitCounter or ORCAOrbitCounter.

• graphlet_size ({4, 5}, default 4) – Graphlet size of the orbit pass.

• arc_consistency (bool, default False) – Run arc consistency after NLF (so the orbit-counted subgraph is induced by its survivors) and again after the orbit pass: v stays a candidate of u only if, for every pattern neighbour u’ of u, some data neighbour of v is a candidate of u’, repeated until nothing changes. Not in OrbitSI as published.

• contraction (bool, default True) – Before the orbit pass, repeat NLF with neighbours counted inside the candidate subgraph, while that shrinks it by at least 5% a round, so the orbits are counted on a smaller subgraph. Not in OrbitSI as published.

• edge_thinning (bool, default True) – Keep in the orbit-counted subgraph only the edges some pattern edge can map onto. Not in OrbitSI as published.

run()

Run the whole filter.

Returns:

• pattern_orbits (dict) – {pattern node: orbit vector}.

• candidate_sets (dict) – {pattern node: candidate data node IDs}, in data-graph node order.

• subgraph (orbitsi.graphindex.CandidateSubgraph or None) – The candidate-induced subgraph the orbits were counted on.

• If some pattern vertex has no candidate left, returns ({}, {}, None).

ldf_filter()

LDF alone: {pattern node: candidates}, or {} if some pattern vertex has none.

nlf_filter(candidate_sets)

NLF on the full data graph, applied to candidate_sets; {} if some set empties.

arc_consistency_filter(candidate_sets)

Arc consistency to a fixpoint, applied to candidate_sets; {} if some set empties.

orbit_filter(candidate_sets)

The orbit pass on the subgraph induced by candidate_sets.

Returns:

• candidate_sets (dict) – The survivors, or {} if some set empties.

• subgraph (orbitsi.graphindex.CandidateSubgraph or None) – The subgraph the orbits were counted on.

orbit_filter_full(candidate_sets)

The orbit pass with orbits counted on the whole data graph instead (not used by run()).

printCandidateSets(candidate_sets)

Print each pattern vertex’s candidates.

class orbitsi.search.OrderEngine(pattern_graph, pattern_orbits=None, method='auto', candidate_sets=None)

Bases: object

Matching order for the search.

Parameters:

• pattern_graph (networkx.Graph) – The pattern.

• pattern_orbits (dict, optional) – {pattern node: orbit vector}; needed by the ‘orbit’ method.

• method ({'auto', 'orbit', 'degree', 'core'}, default 'auto') – ‘auto’ is OrbitSI’s order: ‘orbit’ if pattern_orbits is given, else ‘degree’. ‘orbit’ starts at the vertex with the largest orbit strength (sum of squared orbit counts), then repeatedly takes the vertex with the most already-ordered neighbours, ties by orbit strength. ‘degree’ is the same with degree in place of orbit strength. ‘core’ orders the 2-core’s vertices before the trees hanging off it: it starts at the vertex with the fewest candidates per pattern neighbour, then repeatedly takes the vertex with the most already-ordered neighbours, ties by fewest candidates.

• candidate_sets (dict, optional) – {pattern node: candidates}; needed by the ‘core’ method.

compute_score(node)

A pattern vertex’s strength: its orbit strength with the ‘orbit’ method, else its degree.

run()

Compute the order.

Returns:

• order (list) – The pattern nodes in matching order.

• pivot (dict) – {pattern node: an earlier neighbour in the order}, None for a node without one.

class orbitsi.search.SearchEngine(data_graph, pattern_graph, candidate_sets, order, pivot=None, tail=True)

Bases: object

Backtracking search for the embeddings of a pattern over filtered candidate sets.

Local candidates come from a candidate-space index, filled in as the search reaches it: for every pattern edge (u’, u) with u’ earlier in the order, and every candidate v’ of u’, the candidates of u adjacent to v’. The candidates of u at a search node are the intersection of those sets over u’s already-matched (backward) neighbours, so every candidate tried is adjacent to all of them; only injectivity remains to be checked. A pattern vertex with no backward neighbour (the first vertex of each connected component) takes its whole candidate set.

Parameters:

• data_graph (graph) – The graph searched: the candidate subgraph returned by FilterEngine.run() (any graph with NetworkX’s adj works).

• pattern_graph (networkx.Graph) – The pattern.

• candidate_sets (dict) – {pattern node: candidate data nodes}.

• order (list) – The pattern nodes in matching order.

• pivot (dict, optional) – Accepted for compatibility; not needed.

• tail (bool, default True) – Let count() count the last vertices of the order together instead of searching them, if they are mutually non-adjacent and their candidate sets pairwise disjoint (the longest such run at the end, up to TAIL_MAX; the order is not changed). Once the others are mapped, every neighbour of a tail vertex is mapped, and since no two tail vertices can take the same data vertex, their images number the product, over tail vertices, of each one’s unused local candidates. Not in OrbitSI as published.

run(return_all=True)

List the embeddings.

Parameters:

return_all (bool, default True) – If False, stop at the first embedding.

Returns:

list of dict – One {pattern node: data node} dict per embedding.

count()

Count the embeddings without materialising them.

Returns:

int

C++ pipeline

OrbitSI’s count pipeline in C++ (the _orbitsi_core extension): the filter of orbitsi.search.FilterEngine, the matching orders of OrderEngine and the counting of SearchEngine.count, with the same semantics (the tests compare them). OrbitSIEngine.count() goes through it by default.

data_graph(G) builds the extension’s copy of a data graph once (cached with its GraphIndex; read_graph_from_file builds it at load); run(G, P, …) filters, orders and counts one pattern.

orbitsi.core.data_graph(G)

The C++ core’s copy of data graph G, built on first use and cached with its GraphIndex.

Parameters:

G (networkx.Graph) – The data graph, with node labels in the 'label' attribute.

Returns:

_orbitsi_core.DataGraph

orbitsi.core.run(G, P, graphlet_size=4, order_method='auto', arc_consistency=False, contraction=True, edge_thinning=True, tail=True, stop='count', limit=0)

Filter, order and count (or enumerate) the embeddings of pattern P in G, in C++.

Parameters:

• G (networkx.Graph) – The data and pattern graphs, with node labels in the 'label' attribute.

• P (networkx.Graph) – The data and pattern graphs, with node labels in the 'label' attribute.

• graphlet_size ({4, 5}, default 4) – Graphlet size of the orbit filter (counted by EVOKE).

• order_method ({'auto', 'core'}, default 'auto') – Matching order: OrbitSI’s orbit-strength order, or 2-core first (see orbitsi.search.OrderEngine).

• arc_consistency (bool, default False) – Run arc consistency after NLF and after the orbit filter.

• contraction (bool, default True) – Repeat NLF inside the candidate subgraph before the orbit filter.

• edge_thinning (bool, default True) – Count orbits only on the candidate subgraph’s edges that some pattern edge can map onto.

• tail (bool, default True) – Count the last pattern vertices together instead of searching them.

• stop ({'count', 'order', 'filter'}, default 'count') – Stop after filtering or ordering instead of searching.

• limit (int, default 0) – If positive, enumerate the embeddings one at a time (no tail or last-level counting) and stop after limit of them.

Returns:

dict – status (‘ok’, or ‘refuted’ if filtering leaves some pattern vertex without candidates); count (int: the number of embeddings, at most limit if one is set); limit_reached (bool); candidates ({pattern node: [data node IDs]}, empty when refuted); order (pattern nodes in matching order); orbit_subgraph (vertices and edges of the subgraph the orbits were counted on); times (milliseconds per stage).

orbitsi.core.count(G, P, **kwargs)

The number of embeddings of pattern P in data graph G (keyword arguments as run()).

Orbit counting

class orbitsi.orbit.EVOKEOrbitCounter(G, size=4)

Bases: object

Vertex orbit counts of a graph by EVOKE (graphlets of 4 or 5 vertices).

Parameters:

• G (networkx.Graph) – The graph; self-loops are ignored.

• size ({4, 5}, default 4) – Graphlet size: 15 orbits for 4, 73 for 5.

property converter

The OrbitMatrixConverter for induced counts, loaded on first use.

count_orbits()

Count the non-induced orbits: {node: list of counts}, also kept in self.counts.

get_orbits(induced=False)

The orbit counts, one row per node in sorted node order.

Parameters:

induced (bool, default False) – Induced counts instead of non-induced ones (EVOKE’s own).

Returns:

numpy.ndarray – An n x 15 (size 4) or n x 73 (size 5) int64 array.

static count_csr(offsets, nbors, size=4, orbits=None)

Non-induced orbit counts of a graph in CSR form.

Parameters:

• offsets (array_like of int) – The graph over vertices 0..n-1: the neighbours of vertex i are nbors[offsets[i]:offsets[i + 1]].

• nbors (array_like of int) – The graph over vertices 0..n-1: the neighbours of vertex i are nbors[offsets[i]:offsets[i + 1]].

• size ({4, 5}, default 4) – Graphlet size.

• orbits (iterable of int, optional) – The orbits needed (None: all). At size 4, routines counting none of them are skipped, and the orbits only they count are left at 0.

Returns:

numpy.ndarray – An n x 15 or n x 73 int64 array.

class orbitsi.orbit.ORCAOrbitCounter(G, size=4)

Bases: object

Vertex orbit counts of a graph by ORCA (graphlets of 4 vertices only).

Parameters:

• G (networkx.Graph) – The graph; self-loops are ignored.

• size ({4}, default 4) – Graphlet size (15 orbits).

count_orbits()

Count the induced orbits: {node: list of counts}, also kept in self.counts.

get_orbits(induced=False)

The orbit counts, one row per node in sorted node order.

Parameters:

induced (bool, default False) – Induced counts (ORCA’s own) instead of non-induced ones.

Returns:

numpy.ndarray – An n x 15 int64 array.

static count_csr(offsets, nbors, size=4, orbits=None)

Non-induced orbit counts of a graph in CSR form.

Parameters:

• offsets (array_like of int) – The graph over vertices 0..n-1: the neighbours of vertex i are nbors[offsets[i]:offsets[i + 1]].

• nbors (array_like of int) – The graph over vertices 0..n-1: the neighbours of vertex i are nbors[offsets[i]:offsets[i + 1]].

• size ({4}, default 4) – Graphlet size.

• orbits (iterable of int, optional) – Accepted for EVOKEOrbitCounter.count_csr()’s interface; all orbits are counted.

Returns:

numpy.ndarray – An n x 15 int64 array.

class orbitsi.orbit.orbit_converter.OrbitMatrixConverter

Bases: object

Converts vertex orbit counts between induced and non-induced.

Orbits are grouped by graphlet size: orbit 0 (an edge) is the same either way; orbits 1-3, 4-14 and 15-72 are related by the matrices for 3-, 4- and 5-vertex graphlets (non-induced = M @ induced). Each M is unit upper-triangular with integer entries, so its inverse is an integer matrix too, and both directions are exact in int64.

noninduced_to_induced(noninduced_matrix)

Convert non-induced orbit counts (one row per vertex) to induced counts.

induced_to_noninduced(induced_matrix)

Convert induced orbit counts (one row per vertex) to non-induced counts.