OrbitSI using NetworkX for Python

OrbitSI is a NetworkX-based Python package that efficiently solves the subgraph isomorphism enumeration problem, i.e., finding all subgraphs in a large data graph G_d that are isomorphic to a pattern/query graph G_p. It also supports fast vertex orbit counting, which summarises the local structural roles of vertices within a network.

OrbitSI combines orbit-based filtering and ordering to prune and order candidate node mappings, significantly reducing the search space during subgraph matching. It integrates two state-of-the-art orbit counting engines — EVOKE and ORCA — via optimised C++ bindings using pybind11. Graphs are networkx graphs; the filter, the matching order and the counting search also run in a C++ core (the default for counting), and graph files are read in C++ straight into arrays.

The package includes a command-line interface (CLI), usable library, and testing utilities. It is installable via pip, tested on synthetic and real-world benchmark datasets, and fully open source under the Apache 2.0 license.

Documentation

The documentation is at sitauhidi.github.io/OrbitSI: installation, Python and command-line usage, the graph file format, how the algorithm works, and the API reference. It is built from docs/ with Sphinx.

Installation

Install from PyPi:

pip install orbitsi

Install from source

1. Clone the repository:

git clone https://github.com/sitauhidi/OrbitSI.git
cd OrbitSI

2. Build and install:

pip install .

Requires Python 3.8+, NumPy, NetworkX, and a C++17 compiler (e.g., g++ or clang++).

Command-Line Interface (CLI) Usage

Once installed, the orbitsi CLI tool allows you to perform:

1. Subgraph Isomorphism Search
2. Node Orbit Counting

To confirm installation:

orbitsi --help

Subgraph Isomorphism Search

Find all subgraphs in a large graph G_d that are isomorphic to a smaller query/pattern graph G_p.

Command:

orbitsi search --data <path_to_data_graph> --pattern <path_to_pattern_graph> [--orbit-counter evoke|orca] [--graphlet-size 4|5] [--order auto|core] [--arc-consistency] [--no-contraction] [--no-edge-thinning] [--no-tail] [--published] [--backend cpp|python] [--count-only]

Arguments:

• --data: Path to the data graph file (required)
• --pattern: Path to the pattern/query graph file (required)
• --orbit-counter: Orbit counting backend, either evoke (default) or orca
• --graphlet-size: Graphlet size to use for orbit counting (4 or 5, default: 4; orca supports 4 only)
• --order: Matching order, auto (OrbitSI's orbit-strength order, default) or core (2-core first, then most already-matched neighbours, then fewest candidates)
• --arc-consistency: Also run arc consistency (a candidate of u needs, for every pattern neighbour u', a data neighbour among u''s candidates; repeated to a fixpoint) after NLF and after the orbit filter. Off by default, as in OrbitSI as published
• --no-contraction: Leave out the NLF rounds on the candidate subgraph before the orbit filter (repeated while the subgraph shrinks by at least 5%, so orbits are counted on a smaller graph)
• --no-edge-thinning: Count orbits on every edge of the candidate subgraph, not only on the edges some pattern edge can map onto
• --no-tail: Search the last pattern vertices one by one instead of counting them together
• --published: OrbitSI's algorithm as published: the orbit-strength order, no arc consistency, and none of contraction, edge thinning or tail counting (overrides --order, --arc-consistency and the three options above). Candidates, order and count are those of the published algorithm; the implementation is the current one
• --backend: Implementation of --count-only, cpp (default) or python. cpp applies only with --orbit-counter evoke; with orca the count runs in Python. Listing the embeddings always runs in Python
• --count-only: Print only the number of matches, counted without storing them (much faster and lighter when there are many)

Contraction, edge thinning and tail counting are on by default; none of them changes the matches found.

Example:

orbitsi search --data datasets/data_graph/HPRD.graph --pattern datasets/query_graph/query1.graph --orbit-counter evoke --graphlet-size 4

Orbit Counting for a Graph

Compute node orbit vectors for a given graph using either the EVOKE or ORCA backend.

Command:

orbitsi count-orbits --graph <path_to_graph> [--orbit-counter evoke|orca] [--graphlet-size 4|5] [--induced]

Arguments:

• --graph: Path to the graph file (required)
• --orbit-counter: Orbit counting backend, either evoke (default) or orca
• --graphlet-size: Size of graphlets to consider (4 or 5; orca supports 4 only)
• --induced: Flag to compute induced orbit counts (optional; default is non-induced)

Example:

orbitsi count-orbits --graph datasets/data_graph/HPRD.graph --orbit-counter evoke --graphlet-size 5 --induced

Graph File Format

All graphs should be in .graph format:

t N M
v 0 1 2
v 1 2 1
...
e 0 1
e 1 2
...

• t N M: number of nodes N and edges M
• v ID Label Degree: vertex ID, label (label is required), degree (optional)
• e u v: edge between vertex u and v

Vertex IDs and labels are integers within 64 bits; IDs need not be 0..N-1 or in order. Only the first fields of v and e lines are read, and every other line (including t) is ignored. Repeated edges and self-loops are kept once; a repeated v line updates the label. A vertex that appears only in edges has no label. Graphs are undirected.

Python API

from orbitsi.utils import read_graph_from_file
from orbitsi.orbit import EVOKEOrbitCounter
from orbitsi.search import OrbitSIEngine

G = read_graph_from_file("datasets/data_graph/HPRD.graph")
P = read_graph_from_file("datasets/query_graph/query_dense_16_1.graph")

engine = OrbitSIEngine(G, EVOKEOrbitCounter, graphlet_size=4)
engine.count(P)   # number of embeddings (C++ core)
engine.run(P)     # list of embeddings, as {pattern node: data node} dicts (Python)

OrbitSIEngine takes the same options as the CLI (order_method, arc_consistency, contraction, edge_thinning, tail, published, backend). orbitsi.core.run(G, P, ..., limit=N) enumerates the embeddings one at a time in C++ and stops after N of them; its result also has the candidates, the matching order and per-stage times.

read_graph_from_file returns a networkx.Graph (an orbitsi.arraygraph.ArrayGraph). The file is parsed in C++ straight into arrays, which the filter and the C++ core use directly. The graph's NetworkX node and adjacency dictionaries are built only when first used (for example by the Python backend, G.copy() or G.subgraph()); the graph then becomes a plain networkx.Graph. The node and neighbour order is the order NetworkX would build from the file. By default the reader also builds the indexes the search needs (build_index=True), so their cost is paid at load and not by the first pattern.

Testing

A complete suite of unit and integration tests is provided in the tests/ directory. This includes:

• Benchmark-based validation for subgraph isomorphism
• Cross-validation of orbit counting with external tools

To get started, see tests/README.md for detailed setup and usage instructions.

Citation

If you use OrbitSI for subgraph isomorphism search, please cite:

Tauhidi, Syed Ibtisam, Arindam Karmakar, Thai Son Mai, and Hans Vandierendonck. "OrbitSI: An Orbit-based Algorithm for the Subgraph Isomorphism Search Problem." In 2024 IEEE International Conference on Knowledge Graph (ICKG), pp. 360-369. IEEE, 2024. https://doi.org/10.1109/ICKG63256.2024.00052

If you only use the orbit counting modules (ORCAOrbitCounter, EVOKEOrbitCounter), cite:

• EVOKE: Noujan Pashanasangi and C. Seshadhri. "Efficiently counting vertex orbits of all 5-vertex subgraphs, by EVOKE.", WSDM 2020: Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 447–455. https://doi.org/10.1145/3336191.3371773

• ORCA: Tomaž Hočevar and Janez Demšar. "A combinatorial approach to graphlet counting." Bioinformatics, 30(4): 559–565, 2014. https://doi.org/10.1093/bioinformatics/btt717

Acknowledgement

This work was supported by:

• Kelvin Living Lab [grant number EP/Z531054/1]
• Ministry of Education, Government of India through the collaboration between Queen's University Belfast and Tezpur University.

License

This project is licensed under the Apache License 2.0.

See the LICENSE file for details.