-
Notifications
You must be signed in to change notification settings - Fork 23
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
- Loading branch information
1 parent
f6eb88a
commit 9eb57cf
Showing
1 changed file
with
20 additions
and
63 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -1,83 +1,40 @@ | ||
# Exphormers: Sparse Transformers for Graphs | ||
**Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces** | ||
|
||
<p align="center"> | ||
<img src="/images/graph_mamba_icon.jpeg" width="200" height="200" /> | ||
</p> | ||
|
||
[![arXiv](https://img.shields.io/badge/arXiv-2303.06147-b31b1b.svg)](https://arxiv.org/abs/2303.06147) | ||
[![PWC](https://img.shields.io/endpoint.svg?url=https://paperswithcode.com/badge/exphormer-sparse-transformers-for-graphs/graph-classification-on-cifar10-100k)](https://paperswithcode.com/sota/graph-classification-on-cifar10-100k?p=exphormer-sparse-transformers-for-graphs) | ||
[![PWC](https://img.shields.io/endpoint.svg?url=https://paperswithcode.com/badge/exphormer-sparse-transformers-for-graphs/node-classification-on-coco-sp)](https://paperswithcode.com/sota/node-classification-on-coco-sp?p=exphormer-sparse-transformers-for-graphs) | ||
[![PWC](https://img.shields.io/endpoint.svg?url=https://paperswithcode.com/badge/exphormer-sparse-transformers-for-graphs/graph-classification-on-malnet-tiny)](https://paperswithcode.com/sota/graph-classification-on-malnet-tiny?p=exphormer-sparse-transformers-for-graphs) | ||
[![PWC](https://img.shields.io/endpoint.svg?url=https://paperswithcode.com/badge/exphormer-sparse-transformers-for-graphs/graph-classification-on-mnist)](https://paperswithcode.com/sota/graph-classification-on-mnist?p=exphormer-sparse-transformers-for-graphs) | ||
[![PWC](https://img.shields.io/endpoint.svg?url=https://paperswithcode.com/badge/exphormer-sparse-transformers-for-graphs/node-classification-on-pascalvoc-sp-1)](https://paperswithcode.com/sota/node-classification-on-pascalvoc-sp-1?p=exphormer-sparse-transformers-for-graphs) | ||
[![PWC](https://img.shields.io/endpoint.svg?url=https://paperswithcode.com/badge/exphormer-sparse-transformers-for-graphs/link-prediction-on-pcqm-contact)](https://paperswithcode.com/sota/link-prediction-on-pcqm-contact?p=exphormer-sparse-transformers-for-graphs) | ||
Attention mechanisms have been widely used to capture long-range dependencies among nodes in Graph Transformers. Bottlenecked by the quadratic computational cost, attention mechanisms fail to scale in large graphs. Recent improvements in computational efficiency are mainly achieved by attention sparsification with random or heuristic-based graph subsampling, which falls short in data-dependent context reasoning. State space models (SSMs), such as Mamba, have gained prominence for their effectiveness and efficiency in modeling long-range dependencies in sequential data. However, adapting SSMs to non-sequential graph data presents a notable challenge. | ||
|
||
|
||
|
||
![Exphormer-viz](./Exphormers.png) | ||
|
||
|
||
In this work we introduce new sparse transformers for graph data, and use them in the [GraphGPS](https://github.com/rampasek/GraphGPS) framework. Our sparse transformers outperform BigBird and Performer in all cases we tried, which have been mainly designed for the natural language processing context; in many cases, we even get better results than full (dense attention) transformers. Our sparse transformer has three components: actual edges, expander graphs, and universal connectors or virtual nodes. We combine these components into a single sparse attention mechanism. | ||
In this work, we introduce Graph-Mamba, the first attempt to enhance long-range context modeling in graph networks by integrating a Mamba block with the input-dependent node selection mechanism. Specifically, we formulate graph-centric node prioritization and permutation strategies to enhance context-aware reasoning, leading to a substantial improvement in predictive performance. Extensive experiments on ten benchmark datasets demonstrate that Graph-Mamba outperforms state-of-the-art methods in long-range graph prediction tasks, with a fraction of the computational cost in both FLOPs and GPU memory consumption. | ||
|
||
|
||
### Python environment setup with Conda | ||
|
||
```bash | ||
conda create -n exphormer python=3.9 | ||
conda activate exphormer | ||
|
||
conda install pytorch=1.10 torchvision torchaudio -c pytorch -c nvidia | ||
conda install pyg=2.0.4 -c pyg -c conda-forge | ||
|
||
# RDKit is required for OGB-LSC PCQM4Mv2 and datasets derived from it. | ||
conda install openbabel fsspec rdkit -c conda-forge | ||
|
||
pip install torchmetrics | ||
pip install performer-pytorch | ||
pip install ogb | ||
pip install tensorboardX | ||
pip install wandb | ||
|
||
conda create --name graph-mamba --file requirements_conda.txt | ||
conda activate graph-mamba | ||
conda clean --all | ||
``` | ||
To troubleshoot Mamba installation, please refer to https://github.com/state-spaces/mamba. | ||
|
||
|
||
### Running Exphormer | ||
### Running Graph-Mamba | ||
```bash | ||
conda activate exphormer | ||
|
||
# Running Exphormer for LRGB Datasets | ||
python main.py --cfg configs/Exphormer_LRGB/peptides-struct-EX.yaml wandb.use False | ||
conda activate graph-mamba | ||
|
||
# Running Exphormer for Cifar10 | ||
python main.py --cfg configs/Exphormer/cifar10.yaml wandb.use False | ||
# Running Graph-Mamba for Peptides-func dataset | ||
python main.py --cfg configs/GPS/peptides-func-GPS.yaml wandb.use False | ||
``` | ||
You can also set your wandb settings and use wandb. | ||
|
||
### Guide on configs files | ||
|
||
Most of the configs are shared with [GraphGPS](https://github.com/rampasek/GraphGPS) code. You can change the following parameters in the config files for different parameters and variants of the Exphormer: | ||
Most of the configs are shared with [GraphGPS](https://github.com/rampasek/GraphGPS) and [Exphormer](https://github.com/hamed1375/Exphormer) code. You can change the following parameters in the config files for different parameters and variants of Graph-Mamba: | ||
``` | ||
prep: | ||
exp: True # Set True for using expander graphs, set False otherwise. | ||
# Alternatively you can set use_exp_edges to False. | ||
# In this case expander graphs will be calculated but not used in the Exphormer. | ||
exp_deg: 5 # Set the degree of the expander graph. | ||
# Please note that if you set this to d, the algorithm will use d permutations | ||
# or d Hamiltonian cycles, so the actual degree of the expander graph will be 2d | ||
exp_algorithm: 'Random-d' # Options are ['Random-d', 'Random-d2', 'Hamiltonian]. | ||
# Default value is 'Random-d' | ||
add_edge_index: True # Set True if you want to add real edges beside expander edges | ||
num_virt_node: 1 # Set 0 for not using virtual nodes | ||
# otherwise set the number of virtual nodes you want to use. | ||
``` | ||
|
||
## Citation | ||
|
||
Our work can be cited using the following bibtex: | ||
```bibtex | ||
@inproceedings{shirzad2023exphormer, | ||
title={Exphormer: Sparse transformers for graphs}, | ||
author={Shirzad, Hamed and Velingker, Ameya and Venkatachalam, Balaji and Sutherland, Danica J and Sinop, Ali Kemal}, | ||
booktitle={International Conference on Machine Learning}, | ||
eprinttype={arXiv}, eprint={2303.06147}, | ||
year={2023} | ||
} | ||
gt: | ||
layer_type: CustomGatedGCN+Mamba_Hybrid_Degree_Noise | ||
# CustomGatedGCN+Mamba_Hybrid_Degree_Noise_Bucket - For large graph datasets that use the bucketing technique | ||
# Refer to graphgps/layer/gps_layer.py for NUM_BUCKETS | ||
# CustomGatedGCN+Mamba_Hybrid_Noise - For permutation-only Graph-Mamba | ||
# CustomGatedGCN+Mamba - For baseline Mamba without Graph-Mamba adaptations | ||
``` |