Metadata-Version: 2.4
Name: orbitsi
Version: 0.2.0
Summary: OrbitSI: An Orbit-based Algorithm for the Subgraph Isomorphism Search Problem
Author-email: Syed Ibtisam Tauhidi <stauhidi01@qub.ac.uk>
License: Apache-2.0
Project-URL: Homepage, https://github.com/sitauhidi/OrbitSI
Project-URL: Documentation, https://sitauhidi.github.io/OrbitSI/
Project-URL: Source, https://github.com/sitauhidi/OrbitSI
Keywords: graphlets,orbits,subgraph isomorphism,EVOKE,ORCA
Classifier: Programming Language :: Python :: 3
Classifier: License :: OSI Approved :: Apache Software License
Classifier: Operating System :: OS Independent
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: networkx
Requires-Dist: numpy
Requires-Dist: pybind11
Dynamic: license-file

# OrbitSI using NetworkX for Python

[![License: Apache 2.0](https://img.shields.io/badge/License-Apache_2.0-blue.svg)](LICENSE)
[![DOI](https://zenodo.org/badge/DOI/10.1109/ICKG63256.2024.00052.svg)](https://doi.org/10.1109/ICKG63256.2024.00052)
[![Python Version](https://img.shields.io/badge/python-3.8%2B-blue.svg)](https://www.python.org/)
[![C++](https://img.shields.io/badge/C%2B%2B-17%2B-brightgreen.svg)](https://en.cppreference.com/w/cpp/compiler_support)
[![PyPI version](https://img.shields.io/pypi/v/orbitsi.svg)](https://pypi.org/project/orbitsi/)

**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 <em>G</em><sub>d</sub> that are isomorphic to a pattern/query graph <em>G</em><sub>p</sub>. 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](https://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/`](docs/) with Sphinx.

---

## Installation

### Install from PyPi:

```bash
pip install orbitsi
```

### Install from source

1. Clone the repository:

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

2. Build and install:

```bash
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:

```bash
orbitsi --help
```

---

### Subgraph Isomorphism Search

Find all subgraphs in a large graph <em>G</em><sub>d</sub> that are isomorphic to a smaller query/pattern graph <em>G</em><sub>p</sub>.

###### **Command:**

```bash
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:**

```bash
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:**

```bash
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:**

```bash
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

```python
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/`](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`](https://github.com/sitauhidi/OrbitSI/blob/main/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](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](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](https://doi.org/10.1093/bioinformatics/btt717)

---

# Acknowledgement

This work was supported by:

- [Kelvin Living Lab](https://blogs.qub.ac.uk/dipsa/the-kelvin-living-lab/) \[grant number EP/Z531054/1\]
- Ministry of Education, Government of India through the collaboration between [Queen's University Belfast](https://www.qub.ac.uk/) and [Tezpur University](https://www.tezu.ernet.in/).

---
## License

This project is licensed under the Apache License 2.0.

See the [LICENSE](https://github.com/sitauhidi/OrbitSI/blob/main/LICENSE) file for details.
