|
IterOrbit
Subgraph isomorphism with iterative graphlet-orbit filtering
|
IterOrbit is a subgraph isomorphism engine: given a small pattern graph and a large data graph, both vertex-labelled and undirected, it finds or counts the embeddings of the pattern in the data graph. It extends OrbitSI's graphlet-orbit filter by iterating it: the candidates that survive a round induce a smaller data graph, and the filters are evaluated again on that graph, until nothing more is removed.
The executable is called iterorbit.
make.pytest, for the tests.The orbit-counting library Escape/EVOKE is included in extern/Escape.
The build uses -march=native, so run the binary on the kind of machine it was built on. make clean removes the whole build directory.
One graph per file, as text:
Only the v lines (vertex ID and label) and e lines (one per undirected edge) are read. Vertex IDs are 0 .. n-1.
Typical runs:
./build/iterorbit without arguments prints this list.
Filtering:
| Option | Meaning |
|---|---|
--graphlet-size <3\|4\|5> | Graphlet size for orbit counting (default 4). |
--iterate <N> | Maximum number of filtering rounds, I_max (default 1). 0 iterates until a round removes no candidate. |
--use-full-graph | Count orbits on the whole data graph instead of the candidate-induced subgraph. One round only; cannot be combined with --iterate. |
--filter-only | Stop after filtering and print candidate statistics. |
--no-arc-consistency | Run the semi-join once per round instead of to a fixpoint. |
--disable-semi-join | Skip the semi-join stage. |
--no-orbit-filter | Skip the orbit stage in every round; the data graph is still contracted. |
--single-induction | Induce the data graph once per round (before the orbit stage) instead of twice (also after it). |
--orbit-throttle, --orbit-throttle-threshold <f> | Skip the orbit stage in rounds where the candidate sets have barely shrunk since it last ran (off by default). |
Ordering and search:
| Option | Meaning |
|---|---|
--induced | Induced subgraph isomorphism (default: non-induced). |
--count-only | Count the embeddings without storing them. Cannot be combined with --verbose. |
--max-embeddings <N> | Enumerate the embeddings one by one and stop after N of them (no symmetry breaking or last-level counting). Cannot be combined with --count-only. |
--cbj | Conflict-directed backjumping. |
--order-mode <core\|orbit\|core-orbit> | Matching order (default core); see include/OrderEngine.h. |
--order <u,u,...> | Use this matching order (a permutation of the pattern's vertex IDs). |
--no-edge-orbit-filter | Do not prune the candidate-space index by per-edge triangle counts. |
--no-symmetry | With --count-only: count every embedding one by one instead of one per class of pattern automorphisms. |
--search-stats | Print the matching order and per-depth search-tree statistics. |
--verbose | Print every embedding and per-stage filtering statistics. |
The options that switch a component off exist for ablation; none of them changes the result.
The run prints its configuration, then one line per phase and the result:
If filtering empties a candidate set, the pattern has no embedding: the run reports Matches found: 0 without searching. A count that exceeds 64 bits is reported as INT64_MAX, with a warning.
| Paper | Code |
|---|---|
| Candidate sets, filter operators, Algorithm 1 (IterOrbitFilter) | include/FilterEngine.h, src/FilterEngine.cpp |
| Graphlet orbit counts | include/OrbitCounter.h, src/OrbitCounter.cpp, extern/Escape |
| Candidate-induced subgraph | AppGraph::createSubgraph in src/AppGraph.cpp |
| Ordering strategy | include/OrderEngine.h, src/OrderEngine.cpp |
| Enumeration, edge-orbit index filter | include/SearchEngine.h, src/SearchEngine.cpp |
| Counting with symmetry breaking | include/Symmetry.h, src/Symmetry.cpp |
| Command line, phase timers | src/main.cpp |
The headers document each component's interface. src/OrbitCounter.cpp reimplements several Escape routines; each says which routine it replaces and what differs.
The headers and file summaries are written for Doxygen. With Doxygen installed, run
in this directory (Doxyfile holds the configuration).
test/test_orbitsi.py runs every pattern in test/query_graph against test/data_graph/HPRD.graph and compares the number of embeddings with test/expected_output.res.
The configuration is set through environment variables: GRAPHLET_SIZE, ITERATE, USE_FULL_GRAPH, CBJ, COUNT_ONLY, ARC_CONSISTENCY (0 for --no-arc-consistency), ORDER_MODE, EXTRA_FLAGS (any other options) and ORBITSI_BIN (the binary to test, default build/iterorbit).
test/orbit_equivalence.cpp checks the reimplemented orbit-counting routines against Escape's originals on subgraphs of a given graph; its header comment gives the build line and usage.
analysis/ holds every number, table and figure of the paper, and the exploratory analyses behind it:
analysis/data/: the experiments' results as CSV files (MANIFEST.csv lists each file and its source).analysis/analysis.ipynb: the notebook that computes everything from those CSVs, one section per figure, table or subsection, with its outputs. analysis/analysis.py is the same code as a script; the notebook is generated from it.analysis/build_data.py: rebuilds analysis/data/ from the experiments' logs (not part of this repository).slurm/: the SLURM scripts that run IterOrbit's experiments and write those logs (see slurm/README.md).baseline/: the patches the paper's comparison applied to the baselines' upstream sources (subgraphmatching-mccreesh and -filteronly for SubgraphMatchingSurvey eb3ab43, whose own candidate printing is left as upstream has it; gup-timed for GuP fbaf103), each applied with patch -p1 to a copy of the checkout. 1.9.8