Introducing Graph Alignment Python Library (GALib): GALib is a lightweight, user-friendly, and highly versatile Python library for diverse unrestricted graph alignment algorithms, which calls for finding a matching between the nodes of one graph and those of another graph, in a way that they correspond to each other by some fitness measure. With GALib, you can effortlessly align graphs and leverage its extensive range of functionalities.
We have developed GALib, an open-source library for network alignment, using Python and PyTorch. To facilitate the integration of representative models and enable third-party developers to extend it according to their specific requirements, we abstract this framework into two main components: Encoder and Decoder. The Encoder takes the structural information of two graphs as input, with the option to include label information, and outputs the similarity matrices of the two graphs. The Decoder processes the obtained similarity matrices to derive the final alignment matrix. The Decoder is followed by a search module for alignment tasks. To facilitate the extension to other downstream tasks such as multimodal alignment and graph representation learning, we extract the search module from the Decoder component, allowing third-party developers to modify it as needed. The output of the search module is the final evaluation metric results (Hits@k, MRR, and MNC).
We integrate eleven representative network-alignment as Encoder and deocder. Their papers and the original codes are given in the following table.
| Encoder | Paper | Publish |
|---|---|---|
| Isorank | Global alignment of multiple protein interaction networks with application to functional orthology detection | PNAS'2008 |
| NSD | Network Similarity Decomposition (NSD): A Fast and Scalable Approach to Network Alignment | IEEE'2012 |
| Big-Align | BIG-ALIGN: Fast Bipartite Graph Alignment | IEEE'2013 |
| FINAL | FINAL: Fast Attributed Network Alignment | KDD '2016 |
| Regal | REGAL: Representation Learning-based Graph Alignment | CIKM '2018 |
| LREA | Low Rank Spectral Network Alignment | WWW '2018 |
| GWL | Gromov-Wasserstein Learning for Graph Matching and Node Embedding | arXiv'2019 |
| CΟΝΕ | CONE-Align: Consistent Network Alignment with Proximity-Preserving Node Embedding | CIKM '2020 |
| Grampa | Spectral graph matching and regularized quadratic relaxations: algorithm and theory | ICML'2020 |
| Grasp | GRASP: Graph Alignment Through Spectral Signatures | APWeb-WAIM'2021 |
| B-Grasp | GRASP: Scalable Graph Alignment by Spectral Corresponding Functions | TKDD'2023 |
| Decoder | Paper | Publish |
| RefiNA | Refining Network Alignment to Improve Matched Neighborhood Consistency | SDM'2021 |
| CAPER | CAPER: Coarsen, Align, Project, Refine - A General Multilevel Framework for Network Alignment | arXiv'2022 |
| Greed-Match | - | - |
| Sinkhorn | From Alignment to Assignment: Frustratingly Simple Unsupervised Entity Alignment | EMNLP'2021 |
We have standardized the format of the experimental data, and more information about the datasets can be accessed at CAPER.
| Name | Nodes | Edges | Description |
|---|---|---|---|
| Arenas | 1,133 | 5,451 | communication network |
| Hamsterster | 2,426 | 16,613 | social network |
| 4,039 | 88,234 | social network | |
| Magna | 1,004 | 8,323 | protein-protein interaction |
This section provides instructions on obtaining a copy of the library, as well as guidance on installing and running it on your local machine for development and testing purposes. Additionally, it offers an overview of the package structure of the source code.
src/
├── GALib/
│ ├── encoder/: package of the implementations for existing representative network alignment approaches
│ ├── decoder/: package of the implementations for refining simiarlity matrix approaches
│ ├── matcher/: package of the implementations for the search utils of framework, search module, and their interaction
│ ├── input/: package of the components for datasets process
│ ├── utils/: package of the components for this framework
- Python(3.7)
- numpy(1.20.3)
- scipy(1.7.3)
- networkx(1.11)
- pickle
- scikit-learn(0.24)
- sacred(0.8.2)
- theano (1.0.5)
- pymanopt(0.2.5)
- pandas(1.1.3)
- Run an implemented model
chmod u+x run.sh
./run.sh- Modify and run a script as follows (examples are in
run/):
python main.py \
--true_align data/arenas/arenas_edges-mapping-permutation.txt \
--combined_graph data/arenas/arenas_combined_edges.txt \
--embmethod xnetMF \
--alignmethod CONE \
--refinemethod RefiNA - If you want to adjust the architecture of the model yourself, or set the parameters of each part of Encoder or Decoder, you can do so on the 'main.py' as follows (take CONE as Encoder and RefiNA as Decoder, search by greed_match):
fromencoder.CONE.CONEimportCONEfromdecoder.RefiNA.RefiNAimportRefiNAencoder=CONE(adjA, adjB, dim=64,window=10,negative=1.0,niter_init=10,reg_init=1.0, \
lr=1.0,bsz=10,nepoch=5,embsim="euclidean",numtop=10,reg_align=0.05,niter_align=10)
alignment_matrix=encoder.align()
decoder=RefiNA(alignment_matrix, adjA, adjB, token_match=1, n_update=1, iter=100)
alignment_matrix=decoder.refine_align()
score, _=refina_utils.score_alignment_matrix(alignment_matrix, topk=1, true_alignments=true_align)The Codebase is built upon the following work -
We appreciate them and many other related works for their open-source contributions.