How OrbitSI works

OrbitSI finds the embeddings of a pattern \(G_p\) in a data graph \(G_d\): injective maps of the pattern’s vertices to data vertices with the same labels, such that every pattern edge maps to a data edge. It runs in three stages: filtering, ordering and search.

Filtering

Filtering gives each pattern vertex \(u\) a set of candidates \(C(u)\), the data vertices it may map to. No embedding uses a vertex outside them, so the search only has to look among them. If some set empties, the pattern has no embedding and the search is skipped.

LDF

\(v\) is a candidate of \(u\) only if it has \(u\)’s label and at least its degree.

NLF

For every label, \(v\) must have at least as many neighbours with that label as \(u\) has.

Orbit filter

The subgraph of \(G_d\) induced by every remaining candidate is orbit-counted (graphlets of 4 or 5 vertices), and \(v\) stays a candidate of \(u\) only if each of its non-induced orbit counts is at least \(u\)’s in the pattern. An embedding maps every graphlet around \(u\) to a distinct one around \(v\) inside that subgraph, so no candidate an embedding uses is removed. Orbits no pattern vertex has are not compared and, where the counter can skip them, not counted.

Three refinements are on by default. None was in OrbitSI as published, and none changes the result:

Contraction (contraction)

Before the orbit filter, NLF is repeated with neighbours counted inside the candidate subgraph, while that shrinks the subgraph by at least 5% a round. The orbits are then counted on a smaller graph.

Edge thinning (edge_thinning)

The orbit-counted subgraph keeps only the edges some pattern edge can map onto (one end a candidate of \(u\), the other of a pattern neighbour of \(u\)). An embedding uses no other edge, so the counts that matter are unchanged, while the counting is cheaper.

Tail counting (tail)

See Search below.

Arc consistency (arc_consistency) is off by default. When on, it runs after NLF and again after the orbit filter: \(v\) stays a candidate of \(u\) only if, for every pattern neighbour \(u'\), some neighbour of \(v\) is a candidate of \(u'\), repeated until nothing changes.

Ordering

The search matches the pattern’s vertices in a fixed order.

auto (OrbitSI’s order)

Start at the vertex with the largest orbit strength (the sum of its squared orbit counts), then repeatedly take the vertex with the most already-ordered neighbours, ties by orbit strength.

core

The pattern’s 2-core before the trees hanging off it. Start at the vertex with the fewest candidates per pattern neighbour, then repeatedly take the vertex with the most already-ordered neighbours, ties by fewest candidates.

Search

The search is a depth-first backtracking search over the candidate sets. A candidate-space index, filled in as the search reaches it, holds, 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 tried for \(u\) are the intersection of those sets over its already-matched neighbours, so each is adjacent to all of them and only injectivity remains to check.

When counting, the last pattern vertex is counted rather than visited: every unused local candidate completes one embedding. With tail counting, the last few vertices of the order are counted together when they are mutually non-adjacent and their candidate sets pairwise disjoint: their images then number the product of each one’s unused local candidates.

Implementations

OrbitSIEngine.count() runs the whole pipeline in C++ (orbitsi.core) when the orbit counter is EVOKE, which is the default. Listing the embeddings (run()) and backend='python' use the Python implementation (FilterEngine, OrderEngine, SearchEngine), whose filter works on NumPy arrays. Both give the same candidates, orders and counts; the tests compare them.

published=True (--published) runs OrbitSI’s algorithm as published: the orbit-strength order, no arc consistency, and no contraction, edge thinning or tail counting. Its candidates, order and count are the published algorithm’s; the implementation is the current one.

Orbit counting

A graphlet is a small connected graph, and an orbit is a class of its vertices that some automorphism maps onto each other. A vertex’s orbit counts give, for each orbit, the number of graphlets in which the vertex has that role: 15 orbits over graphlets of 2 to 4 vertices, 73 up to 5 vertices. Counts are induced (the graphlet’s vertices induce exactly that graphlet) or non-induced (the graphlet’s edges are present, possibly with more). The filter uses non-induced counts, which an embedding never decreases. EVOKE counts non-induced orbits of up to 5 vertices; ORCA induced ones of up to 4. OrbitMatrixConverter converts between the two exactly.