# OrbitSI using NetworkX for Python
[](LICENSE)
[](https://doi.org/10.1109/ICKG63256.2024.00052)
[](https://www.python.org/)
[](https://en.cppreference.com/w/cpp/compiler_support)
[](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`, and builds the search pipeline using `networkx`.
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.
---
## Wiki
- [Introduction](https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/wikis/home)
- [Subgraph Isomorphism](https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/wikis/Subgraph-Isomorphism-Search)
- [Orbit Counting](https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/wikis/Orbit-Counting)
---
## Installation
### Install from PyPi:
```bash
pip install orbitsi
```
### Install from source
1. Clone the repository:
```bash
git clone https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx.git
cd orbitsi-nx
```
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]
```
###### **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`)
###### **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`)
* `--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 orca --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`
---
## 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://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/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://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/blob/main/LICENSE) file for details.
Raw data
{
"_id": null,
"home_page": null,
"name": "orbitsi",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.8",
"maintainer_email": null,
"keywords": "graphlets, orbits, subgraph isomorphism, EVOKE, ORCA",
"author": null,
"author_email": "Syed Ibtisam Tauhidi <stauhidi01@qub.ac.uk>",
"download_url": null,
"platform": null,
"description": "# OrbitSI using NetworkX for Python\n\n[](LICENSE)\n[](https://doi.org/10.1109/ICKG63256.2024.00052)\n[](https://www.python.org/)\n[](https://en.cppreference.com/w/cpp/compiler_support)\n[](https://pypi.org/project/orbitsi/)\n\n**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.\n\nOrbitSI 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 \u2014 **EVOKE** and **ORCA** \u2014 via optimised C++ bindings using `pybind11`, and builds the search pipeline using `networkx`.\n\nThe 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.\n\n---\n\n## Wiki\n\n- [Introduction](https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/wikis/home)\n- [Subgraph Isomorphism](https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/wikis/Subgraph-Isomorphism-Search)\n- [Orbit Counting](https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/wikis/Orbit-Counting)\n\n---\n\n## Installation\n\n### Install from PyPi:\n\n```bash\npip install orbitsi\n```\n\n### Install from source\n\n1. Clone the repository:\n\n```bash\ngit clone https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx.git\ncd orbitsi-nx\n```\n\n2. Build and install:\n\n```bash\npip install .\n```\n\n> Requires Python 3.8+, NumPy, NetworkX, and a C++17 compiler (e.g., g++ or clang++).\n\n---\n\n## Command-Line Interface (CLI) Usage\n\nOnce installed, the `orbitsi` CLI tool allows you to perform:\n\n1. **Subgraph Isomorphism Search**\n2. **Node Orbit Counting**\n\nTo confirm installation:\n\n```bash\norbitsi --help\n```\n\n---\n\n### Subgraph Isomorphism Search\n\nFind 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>.\n\n###### **Command:**\n\n```bash\norbitsi search --data <path_to_data_graph> --pattern <path_to_pattern_graph> [--orbit-counter evoke|orca] [--graphlet-size 4|5]\n```\n\n###### **Arguments:**\n\n* `--data`: Path to the data graph file (required)\n* `--pattern`: Path to the pattern/query graph file (required)\n* `--orbit-counter`: Orbit counting backend, either `evoke` (default) or `orca`\n* `--graphlet-size`: Graphlet size to use for orbit counting (`4` or `5`, default: `4`)\n\n###### **Example:**\n\n```bash\norbitsi search --data datasets/data_graph/HPRD.graph --pattern datasets/query_graph/query1.graph --orbit-counter evoke --graphlet-size 4\n```\n\n### Orbit Counting for a Graph\n\nCompute node orbit vectors for a given graph using either the EVOKE or ORCA backend.\n\n###### **Command:**\n\n```bash\norbitsi count-orbits --graph <path_to_graph> [--orbit-counter evoke|orca] [--graphlet-size 4|5] [--induced]\n```\n\n###### **Arguments:**\n\n* `--graph`: Path to the graph file (required)\n* `--orbit-counter`: Orbit counting backend, either `evoke` (default) or `orca`\n* `--graphlet-size`: Size of graphlets to consider (`4` or `5`)\n* `--induced`: Flag to compute **induced** orbit counts (optional; default is non-induced)\n\n###### **Example:**\n\n```bash\norbitsi count-orbits --graph datasets/data_graph/HPRD.graph --orbit-counter orca --graphlet-size 5 --induced\n```\n\n---\n\n### Graph File Format\n\nAll graphs should be in `.graph` format:\n\n```\nt N M\nv 0 1 2\nv 1 2 1\n...\ne 0 1\ne 1 2\n...\n```\n\n* `t N M`: number of nodes `N` and edges `M`\n* `v ID Label Degree`: vertex ID, label (label is required), degree (optional)\n* `e u v`: edge between vertex `u` and `v`\n---\n\n## Testing\n\nA complete suite of unit and integration tests is provided in the [`tests/`](tests/) directory. This includes:\n\n* Benchmark-based validation for subgraph isomorphism\n* Cross-validation of orbit counting with external tools\n\nTo get started, see [`tests/README.md`](https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/blob/main/tests/README.md) for detailed setup and usage instructions.\n\n---\n\n## Citation\n\nIf you use **OrbitSI** for **subgraph isomorphism search**, please cite:\n\n> 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)\n\nIf you only use the orbit counting modules (`ORCAOrbitCounter`, `EVOKEOrbitCounter`), cite:\n\n- **`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\u2013455. [https://doi.org/10.1145/3336191.3371773](https://doi.org/10.1145/3336191.3371773)\n\n- **`ORCA`**: Toma\u017e Ho\u010devar and Janez Dem\u0161ar. \"A combinatorial approach to graphlet counting.\" *Bioinformatics*, 30(4): 559\u2013565, 2014. [https://doi.org/10.1093/bioinformatics/btt717](https://doi.org/10.1093/bioinformatics/btt717)\n\n---\n\n# Acknowledgement\n\nThis work was supported by:\n\n- [Kelvin Living Lab](https://blogs.qub.ac.uk/dipsa/the-kelvin-living-lab/) \\[grant number EP/Z531054/1\\]\n- 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/).\n\n---\n## License\n\nThis project is licensed under the Apache License 2.0.\n\nSee the [LICENSE](https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/blob/main/LICENSE) file for details.\n",
"bugtrack_url": null,
"license": "Apache-2.0",
"summary": "OrbitSI: An Orbit-based Algorithm for the Subgraph Isomorphism Search Problem",
"version": "0.1.2",
"project_urls": {
"Documentation": "https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx/-/wikis/home",
"Homepage": "https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx",
"Source": "https://hpdc-gitlab.eeecs.qub.ac.uk/sitauhidi/orbitsi-nx"
},
"split_keywords": [
"graphlets",
" orbits",
" subgraph isomorphism",
" evoke",
" orca"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "ddbd013a66d06016ba7a79e87445b9ca84796e862d7c67196bf2263e6e38783c",
"md5": "290e39718d123ab4859193ca2f00c33a",
"sha256": "3752155d568acbf3d0fd4793bca78a8a6795e02702386050317ed93e03082f4c"
},
"downloads": -1,
"filename": "orbitsi-0.1.2-cp310-cp310-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"has_sig": false,
"md5_digest": "290e39718d123ab4859193ca2f00c33a",
"packagetype": "bdist_wheel",
"python_version": "cp310",
"requires_python": ">=3.8",
"size": 255035,
"upload_time": "2025-07-31T08:16:26",
"upload_time_iso_8601": "2025-07-31T08:16:26.971606Z",
"url": "https://files.pythonhosted.org/packages/dd/bd/013a66d06016ba7a79e87445b9ca84796e862d7c67196bf2263e6e38783c/orbitsi-0.1.2-cp310-cp310-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "423d84db9f07d0daa78cf157a31616e5638335a84005404c4e2ed16d6673ee5d",
"md5": "90b71f96172acaadfc31d1e1b2d18316",
"sha256": "f6d0f9aebc638a57cb949a67091d6443fded1559950efb26845d4ab001651a6a"
},
"downloads": -1,
"filename": "orbitsi-0.1.2-cp311-cp311-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"has_sig": false,
"md5_digest": "90b71f96172acaadfc31d1e1b2d18316",
"packagetype": "bdist_wheel",
"python_version": "cp311",
"requires_python": ">=3.8",
"size": 258149,
"upload_time": "2025-07-31T08:16:28",
"upload_time_iso_8601": "2025-07-31T08:16:28.480378Z",
"url": "https://files.pythonhosted.org/packages/42/3d/84db9f07d0daa78cf157a31616e5638335a84005404c4e2ed16d6673ee5d/orbitsi-0.1.2-cp311-cp311-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "8b141f090930b5aba858be90f218b11c8f40ba4684daf4954b77b73a6e45b17f",
"md5": "274d2f0174fd91f7522e633df1dc00e8",
"sha256": "49b767244357cf2fabcd91bb37bc456d4519213fae5a6ab90c36fcc815393f59"
},
"downloads": -1,
"filename": "orbitsi-0.1.2-cp312-cp312-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"has_sig": false,
"md5_digest": "274d2f0174fd91f7522e633df1dc00e8",
"packagetype": "bdist_wheel",
"python_version": "cp312",
"requires_python": ">=3.8",
"size": 261330,
"upload_time": "2025-07-31T08:16:29",
"upload_time_iso_8601": "2025-07-31T08:16:29.809279Z",
"url": "https://files.pythonhosted.org/packages/8b/14/1f090930b5aba858be90f218b11c8f40ba4684daf4954b77b73a6e45b17f/orbitsi-0.1.2-cp312-cp312-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "857dbc64c452a46627901ab7cd4db4832c014acd7888d4cfc9e4d7cb33d44196",
"md5": "2a2f8f4286cc2c1959d624a30f71b1ac",
"sha256": "1a334c0a5e88c2cd27ffb6f5ead5c80fa23b3331fbb8a07aa4d017da9e5c417d"
},
"downloads": -1,
"filename": "orbitsi-0.1.2-cp313-cp313-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"has_sig": false,
"md5_digest": "2a2f8f4286cc2c1959d624a30f71b1ac",
"packagetype": "bdist_wheel",
"python_version": "cp313",
"requires_python": ">=3.8",
"size": 261487,
"upload_time": "2025-07-31T08:16:31",
"upload_time_iso_8601": "2025-07-31T08:16:31.324688Z",
"url": "https://files.pythonhosted.org/packages/85/7d/bc64c452a46627901ab7cd4db4832c014acd7888d4cfc9e4d7cb33d44196/orbitsi-0.1.2-cp313-cp313-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "f935a7100d2040f2f9cf019c0c3314d0080e9aad3c71e27b601f4250655da5ea",
"md5": "a44e4b1f2f66d27087a0833a23da088b",
"sha256": "f07c7f6f52087c4b3e040b45e3114736a75b6c570b4284858b8aa5ebc9dcdd16"
},
"downloads": -1,
"filename": "orbitsi-0.1.2-cp314-cp314-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"has_sig": false,
"md5_digest": "a44e4b1f2f66d27087a0833a23da088b",
"packagetype": "bdist_wheel",
"python_version": "cp314",
"requires_python": ">=3.8",
"size": 261632,
"upload_time": "2025-07-31T08:16:32",
"upload_time_iso_8601": "2025-07-31T08:16:32.842131Z",
"url": "https://files.pythonhosted.org/packages/f9/35/a7100d2040f2f9cf019c0c3314d0080e9aad3c71e27b601f4250655da5ea/orbitsi-0.1.2-cp314-cp314-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "8b8e887d34e86abde03fc3ef8ae02517ed89b4ab8e87b1675e6a45b2992f55ff",
"md5": "4af9fb5f4ad89af1b6f994a80e75bac2",
"sha256": "b522ee131754b8932fafcd8f6c3bdb54fe539bb0768f95321439e71cad28d441"
},
"downloads": -1,
"filename": "orbitsi-0.1.2-cp314-cp314t-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"has_sig": false,
"md5_digest": "4af9fb5f4ad89af1b6f994a80e75bac2",
"packagetype": "bdist_wheel",
"python_version": "cp314",
"requires_python": ">=3.8",
"size": 261868,
"upload_time": "2025-07-31T08:16:34",
"upload_time_iso_8601": "2025-07-31T08:16:34.175332Z",
"url": "https://files.pythonhosted.org/packages/8b/8e/887d34e86abde03fc3ef8ae02517ed89b4ab8e87b1675e6a45b2992f55ff/orbitsi-0.1.2-cp314-cp314t-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "5fa9a5a033a3480fb90b0cf2001ef8c417d8ab52f9e8d7e1665894c2e6489aac",
"md5": "e0e8bebbe40ad03bdae4b104214be5eb",
"sha256": "ab23102587ac1dc3a1e2800268f412c94dd1f600eddb886a93ed7339fa15463e"
},
"downloads": -1,
"filename": "orbitsi-0.1.2-cp38-cp38-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"has_sig": false,
"md5_digest": "e0e8bebbe40ad03bdae4b104214be5eb",
"packagetype": "bdist_wheel",
"python_version": "cp38",
"requires_python": ">=3.8",
"size": 253960,
"upload_time": "2025-07-31T08:16:36",
"upload_time_iso_8601": "2025-07-31T08:16:36.318569Z",
"url": "https://files.pythonhosted.org/packages/5f/a9/a5a033a3480fb90b0cf2001ef8c417d8ab52f9e8d7e1665894c2e6489aac/orbitsi-0.1.2-cp38-cp38-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "750c46a07481a093878ecd36ec0bc7c81d961957aed2eac8ac27630be973d664",
"md5": "b8f6180fd0070e414615c98e45fce722",
"sha256": "7ef91aba452d06832c156c82bef443840a0de1436be66e7ec6b68a1522427c5a"
},
"downloads": -1,
"filename": "orbitsi-0.1.2-cp39-cp39-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"has_sig": false,
"md5_digest": "b8f6180fd0070e414615c98e45fce722",
"packagetype": "bdist_wheel",
"python_version": "cp39",
"requires_python": ">=3.8",
"size": 255024,
"upload_time": "2025-07-31T08:16:38",
"upload_time_iso_8601": "2025-07-31T08:16:38.041763Z",
"url": "https://files.pythonhosted.org/packages/75/0c/46a07481a093878ecd36ec0bc7c81d961957aed2eac8ac27630be973d664/orbitsi-0.1.2-cp39-cp39-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-07-31 08:16:26",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "orbitsi"
}
JSON