{ "id": "epjfpnaa2j", "slug": "graph-isomorphism-network", "title": "Graph isomorphism network", "updated": "2026-09-30", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_computation" }, { "id": "technology.computing.ai.neural_deep", "label": "Neural networks and deep learning", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.neural_deep" }, { "id": "technology.computing.ai.nn_architectures", "label": "Neural network architectures", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.nn_architectures" }, { "id": "technology.computing.ai.nn_architectures.graph_networks", "label": "Graph neural network architectures", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.nn_architectures.graph_networks" } ], "geo": [ { "id": "geo.nongeo.t2001.technology.computing.ai.neural_deep", "label": "Non-geographic · 2001 to 2020: Neural networks and deep learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.neural_deep", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t2001", "label": "Non-geographic · 2001 to 2020", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001" }, { "id": "geo.nongeo.t2001.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology" }, { "id": "geo.nongeo.t2001.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing" }, { "id": "geo.nongeo.t2001.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai" }, { "id": "geo.nongeo.t2001.technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.ml_computation" }, { "id": "geo.nongeo.t2001.technology.computing.ai.neural_deep", "label": "Neural networks and deep learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.neural_deep" } ] } ], "excerpt": "A graph isomorphism network (GIN) is a graph neural network architecture that updates each node by summing neighbor features through an MLP, matching the 1-WL isomorphism test's power.", "snippet": "A graph isomorphism network (GIN) is a graph neural network architecture that updates each node by summing neighbor features through an MLP, matching the 1-WL isomorphism test's power.", "node": "technology.computing.ai.nn_architectures.graph_networks", "markdown": "# Graph isomorphism network\n\nA graph isomorphism network (GIN) is a neural network architecture for machine learning on graphs that updates each node's representation by summing its neighbors' features and passing the result through a multilayer perceptron (MLP). It was designed so that its ability to distinguish non-isomorphic graphs matches that of the 1-dimensional Weisfeiler–Lehman (1-WL) graph isomorphism test, the theoretical ceiling for message-passing graph neural networks (GNNs).[1](https://doi.org/10.48550/arxiv.1810.00826) Node embeddings produced by a GIN can be used directly for node classification and link prediction, and a graph-level readout produces graph embeddings for graph classification.[1](https://doi.org/10.48550/arxiv.1810.00826)\n\n| Key fact | Detail |\n|---|---|\n| Defining property | Under injective aggregation and readout, GIN is as powerful as the 1-WL test in distinguishing non-isomorphic graphs[1](https://doi.org/10.48550/arxiv.1810.00826) |\n| Update rule | \\( h_{v}^{(k)} = \\mathrm{MLP}^{(k)}\\left((1+\\epsilon^{(k)}) \\cdot h_{v}^{(k-1)} + \\sum_{u \\in \\mathcal{N}(v)} h_{u}^{(k-1)}\\right) \\)[1](https://doi.org/10.48550/arxiv.1810.00826) |\n| Key aggregation choice | Sum over neighbor multisets, which is injective; mean and max aggregation are not[1](https://doi.org/10.48550/arxiv.1810.00826) |\n| Original benchmarks | 9 graph classification datasets; GIN-0 reached 92.4±2.5% on REDDIT-BINARY and 89.4±5.6% on MUTAG[1](https://doi.org/10.48550/arxiv.1810.00826) |\n| Named variants | GIN-0 and GIN-ε (learnable ε); GINE with edge features; virtual-node GIN used on OGB molecular datasets[1](https://doi.org/10.48550/arxiv.1810.00826) • [2](https://www.dgl.ai/dgl_docs/_modules/dgl/nn/pytorch/conv/gineconv.html) • [3](https://proceedings.neurips.cc/paper_files/paper/2019/file/fb60d411a5c5b72b2e7d3527cfc84fd0-Paper.pdf) |\n| Ceiling | Cannot distinguish any graph pair that the 1-WL test cannot[4](https://doi.org/10.1609/aaai.v33i01.33014602) |\n\n## How it works\n\nGIN belongs to the message-passing family, in which an AGGREGATE operator maps the multiset of neighbor representations to a single vector and an UPDATE operator combines it with the node's own representation.[5](https://perso.isep.fr/pconde/Publi-2022-mathematics.pdf) Its update equation is\n\n\\[ h_{v}^{(k)} = \\mathrm{MLP}^{(k)}\\left(\\left(1+\\epsilon^{(k)}\\right) \\cdot h_{v}^{(k-1)} + \\sum_{u \\in \\mathcal{N}(v)} h_{u}^{(k-1)}\\right), \\]\n\nwhere \\( \\epsilon^{(k)} \\) adjusts the weight of the central node's own previous embedding relative to the neighbor sum.[1](https://doi.org/10.48550/arxiv.1810.00826) Two variants were defined: GIN-ε, which learns \\( \\epsilon \\) by gradient descent, and GIN-0, which fixes \\( \\epsilon \\) to 0 and is slightly less powerful in principle.[1](https://doi.org/10.48550/arxiv.1810.00826)\n\nThe theoretical core is injectivity. Sum aggregation is injective on multisets: Corollary 6 of the original paper states that \\( h(c,X) = (1+\\epsilon) \\cdot f(c) + \\sum_{x \\in X} f(x) \\) is unique for each pair \\( (c,X) \\) for infinitely many choices of \\( \\epsilon \\), including all [irrational numbers](https://www.edgepedia.org/irrational-number), so distinct neighbor multisets never collapse to the same value.[1](https://doi.org/10.48550/arxiv.1810.00826) Mean and max aggregation discard information about how many times a feature repeats, so they cannot be injective. The MLP after the sum supplies the injective mapping that a single linear layer, as in GCN, cannot represent, whereas an MLP with at least one hidden layer is a universal approximator.[6](https://alessioborgi.github.io/blog/gnn/gin/)\n\nThe Weisfeiler–Lehman test (iterative graph test distinguishing non-identical graphs) is the yardstick because of two matching results. The GIN paper proves that any aggregation-based GNN is at most as powerful as the WL test, and (Theorem 3) that a GNN whose neighbor aggregation and graph-level readout are injective is as powerful as the WL test.[1](https://doi.org/10.48550/arxiv.1810.00826) Christopher Morris and colleagues independently showed, for a broad class of GNN architectures and all parameter choices, that GNNs cannot be more powerful than the 1-WL test, and that with the right parameter initialization they have the same expressiveness as the 1-WL algorithm, completing the equivalence.[4](https://doi.org/10.1609/aaai.v33i01.33014602) [The 1](https://www.edgepedia.org/the-1)-WL test succeeds on almost all pairs of non-isomorphic graphs, which is why matching it is a meaningful target.[7](https://proceedings.neurips.cc/paper_files/paper/2019/file/71ee911dd06428a96c143a0b135041a4-Paper.pdf)\n\n## How it is done\n\nA practical GIN classifier stacks several GIN layers and applies a graph-level readout that concatenates the READOUT of node embeddings across all iterations,\n\n\\[ h_{G} = \\mathrm{CONCAT}\\left(\\mathrm{READOUT}\\left(\\{h_{v}^{(k)} \\mid v \\in G\\}\\right) \\mid k = 0, 1, \\ldots, K\\right), \\]\n\nan architecture the authors describe as similar to Jumping Knowledge Networks, so information from all depths contributes to the graph embedding.[1](https://doi.org/10.48550/arxiv.1810.00826) In the original experiments, training used 10-fold cross-validation with LIB-SVM, 5 GNN layers, 2-layer MLPs, batch normalization on every hidden layer, and Adam with an initial learning rate of 0.01 decayed by 0.5 every 50 epochs; on the Reddit datasets a single one-dimensional vector served as the node feature.[1](https://doi.org/10.48550/arxiv.1810.00826) Both PyTorch Geometric and DGL provide ready implementations of the operator.[8](https://pytorch-geometric.readthedocs.io/en/stable/generated/torch_geometric.nn.conv.GINConv.html) • [2](https://www.dgl.ai/dgl_docs/_modules/dgl/nn/pytorch/conv/gineconv.html)\n\n## Origin\n\nGIN was reported by Keyulu Xu and colleagues in \"How Powerful are Graph Neural Networks?\", posted to arXiv in 2018 and published at ICLR 2019.[1](https://doi.org/10.48550/arxiv.1810.00826) The paper built on earlier message-passing architectures it analyzed directly: it identifies its mean–1-layer and max–1-layer ablations with GCN and [GraphSAGE](https://www.edgepedia.org/graphsage) respectively, up to minor architecture modifications, and notes that both fail the injectivity conditions of Theorem 3.[1](https://doi.org/10.48550/arxiv.1810.00826) The equivalence result was obtained independently by Christopher Morris and colleagues in \"Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks\" (AAAI 2019), the same paper that proposed k-dimensional GNNs.[4](https://doi.org/10.1609/aaai.v33i01.33014602) A third related line is the k-order invariant graph network of Haggai Maron and colleagues in \"Provably Powerful Graph Networks\" (arXiv, 2019).[9](https://doi.org/10.48550/arxiv.1905.11136)\n\n## Variants\n\n**GIN-0 and GIN-ε** differ only in whether \\( \\epsilon \\) is fixed at 0 or learned. GIN-0 slightly but consistently outperforms GIN-ε in test accuracy while both fit training data equally well, which the authors attribute to GIN-0's simplicity.[1](https://doi.org/10.48550/arxiv.1810.00826)\n\n**GINE** is the Graph Isomorphism Network with edge features, introduced in \"Strategies for Pre-training Graph Neural Networks\". Its update is\n\n\\[ h_{i}^{(l+1)} = f_{\\Theta}\\left((1+\\epsilon) \\cdot h_{i}^{l} + \\sum_{j \\in \\mathcal{N}(i)} \\mathrm{ReLU}\\left(h_{j}^{l} + e_{j,i}^{l}\\right)\\right), \\]\n\nwhere \\( e_{j,i}^{l} \\) is the edge feature; DGL's implementation defaults \\( \\epsilon \\) to 0 and makes it learnable only if requested.[2](https://www.dgl.ai/dgl_docs/_modules/dgl/nn/pytorch/conv/gineconv.html)\n\n**Virtual-node GIN** adds a virtual node connected to all nodes and is the GIN configuration benchmarked on [Open Graph Benchmark](https://www.edgepedia.org/open-graph-benchmark) molecular datasets.[3](https://proceedings.neurips.cc/paper_files/paper/2019/file/fb60d411a5c5b72b2e7d3527cfc84fd0-Paper.pdf) Edge-aware Weisfeiler–Lehman extensions modify the GIN update by adding a term over pairs of neighbors connected by an edge; when no such edges exist (no triangles), the extra term is zero and the model reduces to GIN.[10](https://arxiv.org/html/2206.02059v3)\n\n## Applications\n\nThe original evaluation covered 9 graph classification benchmarks: 4 bioinformatics datasets (MUTAG, PTC, NCI1, PROTEINS) and 5 social network datasets (COLLAB, IMDB-BINARY, IMDB-MULTI, REDDIT-BINARY, REDDIT-MULTI5K). GINs, especially GIN-0, outperformed or matched less powerful GNN variants on all 9 datasets, achieving state-of-the-art performance at the time, including 92.4±2.5% on REDDIT-BINARY and 89.4±5.6% on MUTAG.[1](https://doi.org/10.48550/arxiv.1810.00826)\n\nOn the Open Graph Benchmark, the best GIN with a virtual node reaches 77.07±1.49% test ROC-AUC on ogbg-molhiv versus GCN's best 76.06±0.97%, and 27.03±0.23% test AP on ogbg-molpcba versus GCN's 24.24±0.34%.[3](https://proceedings.neurips.cc/paper_files/paper/2019/file/fb60d411a5c5b72b2e7d3527cfc84fd0-Paper.pdf) Main application areas are molecule property prediction, social network analysis, and graph classification generally.[1](https://doi.org/10.48550/arxiv.1810.00826) • [3](https://proceedings.neurips.cc/paper_files/paper/2019/file/fb60d411a5c5b72b2e7d3527cfc84fd0-Paper.pdf)\n\n## Limitations and alternatives\n\nGIN's expressiveness ceiling is the 1-WL test, and it inherits that test's shortcomings. Although 1-WL-constrained message-passing architectures can distinguish many graphs beyond their degree sequences, they fail on particular non-isomorphic graph families, such as some regular graphs, which receive indistinguishable colorings.[11](https://dl.acm.org/doi/10.1145/3770855.3818116) Higher-order models go beyond it: k-GNNs, based on the k-dimensional WL algorithm, perform message passing between subgraph structures rather than individual nodes and are strictly more powerful than GNNs; hierarchical k-GNNs combining representations at different granularities consistently outperformed traditional GNNs in their experiments.[4](https://doi.org/10.1609/aaai.v33i01.33014602) Maron and colleagues' k-order invariant graph networks distinguish graphs as well as the k-WL tests, which are provably stronger than 1-WL for \\( k > 2 \\), and they prove the existence of a network separating any pair distinguishable by 3-WL.[9](https://doi.org/10.48550/arxiv.1905.11136) Even second-order models have gaps: 2-IGNs cannot distinguish non-isomorphic regular graphs with the same degree.[12](https://export.arxiv.org/pdf/1905.12560v2.pdf)\n\nAmong 1-WL-class alternatives, GCN (degree-normalized sum with a linear update), GAT (attention-weighted sum), and GraphSAGE (mean or max-pool) all sit below 1-WL power, while GIN's sum aggregation with an MLP update reaches it. The original paper's ablations show that replacing MLPs with 1-layer perceptrons or sum with mean or max-pooling produces models confused by simple graphs, though mean-aggregator models like GCN still perform well for node classification.[1](https://doi.org/10.48550/arxiv.1810.00826)\n\nTwo caveats qualify these comparisons. Expressiveness is a statement about worst-case distinguishing power, not about accuracy: a less expressive model can still win on a given dataset. And GIN-family models remain standard baselines rather than obsolete ones: a 2024 graph-transformer paper trains GINE for 45 epochs as its comparison model against a fine-tuned (2,1)-graph transformer,[13](https://raw.githubusercontent.com/mlresearch/v235/main/assets/muller24c/muller24c.pdf) and a 2025 paper argues that classic GNN architectures remain strong baselines for graph-level tasks.[14](https://arxiv.org/html/2502.09263v3) Published comparisons do not settle current OGB leaderboard standings for GIN-family models or detailed head-to-head results against graph transformers beyond GINE's use as a baseline.\n\n## References\n\n1. [Xu, Keyulu and colleagues (2018). How Powerful are Graph Neural Networks?. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1810.00826)\n2. [dgl.nn.pytorch.conv.gineconv, DGL 2.5 documentation](https://www.dgl.ai/dgl_docs/_modules/dgl/nn/pytorch/conv/gineconv.html)\n3. [Open Graph Benchmark: Datasets for Machine Learning on Graphs (Hu et al., NeurIPS 2020)](https://proceedings.neurips.cc/paper_files/paper/2019/file/fb60d411a5c5b72b2e7d3527cfc84fd0-Paper.pdf)\n4. [Morris, Christopher and colleagues (2019). Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. AAAI Publications (The Association for the Advancement of Artificial Intelligence (AAAI)).](https://doi.org/10.1609/aaai.v33i01.33014602)\n5. [Mathematical Expressiveness of Graph Neural Networks](https://perso.isep.fr/pconde/Publi-2022-mathematics.pdf)\n6. [GIN: Graph Isomorphism Network, The Most Expressive GNN](https://alessioborgi.github.io/blog/gnn/gin/)\n7. [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://proceedings.neurips.cc/paper_files/paper/2019/file/71ee911dd06428a96c143a0b135041a4-Paper.pdf)\n8. [torch_geometric.nn.conv.GINConv, PyTorch Geometric documentation](https://pytorch-geometric.readthedocs.io/en/stable/generated/torch_geometric.nn.conv.GINConv.html)\n9. [Maron, Haggai and colleagues (2019). Provably Powerful Graph Networks. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1905.11136)\n10. [Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm](https://arxiv.org/html/2206.02059v3)\n11. [Invariant-Stratified Propagation for Expressive Graph Neural Networks (KDD 2025)](https://dl.acm.org/doi/10.1145/3770855.3818116)\n12. [2-Invariant Graph Networks fail to distinguish regular graphs](https://export.arxiv.org/pdf/1905.12560v2.pdf)\n13. [Aligning Transformers with Weisfeiler–Leman (ICML 2024, PMLR v235)](https://raw.githubusercontent.com/mlresearch/v235/main/assets/muller24c/muller24c.pdf)\n14. [Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence](https://arxiv.org/html/2502.09263v3)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Machine learning and neural computation › Neural networks and deep learning › Neural network architectures › Graph neural network architectures*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/graph-isomorphism-network", "markdown_url": "https://www.edgepedia.org/graph-isomorphism-network.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Graph isomorphism network\", Edgepedia (EdgeChat), https://www.edgepedia.org/graph-isomorphism-network. Edgepedia Community License 1.0.", "credit_md": "\"[Graph isomorphism network](https://www.edgepedia.org/graph-isomorphism-network)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/graph-isomorphism-network](https://www.edgepedia.org/graph-isomorphism-network). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Graph isomorphism network\", Edgepedia (EdgeChat), https://www.edgepedia.org/graph-isomorphism-network. Edgepedia Community License 1.0.", "speakable": "A graph isomorphism network is a graph neural network architecture that updates each node by summing neighbor features through an MLP, matching the 1-WL isomorphism test's power." }