Neural Subgraph Learning (NSL) is a general library that implements various tasks related to learning of subgraph relations.
It is able to perform 2 tasks:
- Neural subgraph matching.
- Frequent subgraph mining.
The library implements the algorithm NeuroMatch.
Given a query graph Q anchored at node q, and a target graph T anchored at node v, predict if there exists an isomorphism mapping a subgraph of T to Q, such that the isomorphism maps v to q. The framework maps the query and target into an embedding space, and either uses MLP/Neural tensor network + cross entropy loss or order embedding + max margin loss to obtain a prediction score and make the binary prediction of subgraph relationship based on a threshold of the score.
See paper and website for detailed explanation of the algorithm.
- Train the encoder:
python3 -m subgraph_matching.train --node_anchored. Note that a trained order embedding model checkpoint is provided inckpt/model.pt. - Optionally, analyze the trained encoder via
python3 -m subgraph_matching.test --node_anchored, or by running the "Analyze Embeddings" notebook inanalyze/
By default, the encoder is trained with on-the-fly generated synthetic data (--dataset=syn-balanced). The dataset argument can be used to change to a real-world dataset (e.g. --dataset=enzymes), or an imbalanced class version of a dataset (e.g. --dataset=syn-imbalanced). It is recommended to train on a balanced dataset.
The module python3 -m subgraph_matching.alignment.py [--query_path=...] [--target_path=...] provides a utility to obtain all pairs of corresponding matching scores, given a pickle file of the query and target graphs in networkx format. Run the module without these arguments for an example using random graphs.
If exact isomorphism mapping is desired, a conflict resolution algorithm can be applied on the
alignment matrix (the output of alignment.py).
Such algorithms are available in recent works. For example: Deep Graph Matching
Consensus and Convolutional Set Matching for Graph
Similarity.
Both synthetic data (common/combined_syn.py) and real-world data (common/data.py) can be used to train the model.
One can also train with synthetic data, and transfer the learned model to make inference on real
data (see subgraph_matching/test.py).
The neural_matching folder contains an encoder that uses GNN to map the query and target into the
embedding space and make subgraph predictions.
Available configurations can be found in subgraph_matching/config.py.
This package also contains an implementation of SPMiner, a graph neural network based framework to extract frequent subgraph patterns from an input graph dataset.
Running the pipeline consists of training the encoder on synthetic data, then running the decoder on the dataset from which to mine patterns.
Full configuration options can be found in subgraph_matching/config.py and subgraph_mining/config.py.
To run SPMiner to identify common subgraph pattern, the prerequisite is to have a checkpoint of
trained subgraph matching model (obtained by training the GNN encoder).
The config argument args.model_path (subgraph_matching/config.py) specifies the location of the
saved checkpoint, and is shared for both the subgraph_matching and subgraph_mining models.
python3 -m subgraph_mining.decoder --dataset=enzymes --node_anchored
Full configuration options can be found in decoder/config.py. SPMiner also shares the
configurations of NeuroMatch subgraph_matching/config.py since it's used as a subroutine.
- Analyze the order embeddings after training the encoder:
python3 -m analyze.analyze_embeddings --node_anchored - Count the frequencies of patterns generated by the decoder:
python3 -m analyze.count_patterns --dataset=enzymes --out_path=results/counts.json --node_anchored - Analyze the raw output from counting:
python3 -m analyze.analyze_pattern_counts --counts_path=results/
The library uses PyTorch and PyTorch Geometric to implement message passing graph neural networks (GNN). It also uses DeepSNAP, which facilitates easy use of graph algorithms (such as subgraph operation and matching operation) to be performed during training for every iteration, thanks to its synchronization between an internal graph object (such as a NetworkX object) and the Pytorch Geometric Data object.
Detailed library requirements can be found in requirements.txt