mlsanityData to 7 Oct 2026

Going Deeper into Permutation-Sensitive Graph Neural Networks

arXiv 2205.14368 ↗First posted 28 May 2022cs.LG cs.DM stat.MLcited by 15

Not on the map. Why?

Abstract (arXiv)

The invariance to permutations of the adjacency matrix, i.e., graph isomorphism, is an overarching requirement for Graph Neural Networks (GNNs). Conventionally, this prerequisite can be satisfied by the invariant operations over node permutations when aggregating messages. However, such an invariant manner may ignore the relationships among neighboring nodes, thereby hindering the expressivity of GNNs. In this work, we devise an efficient permutation-sensitive aggregation mechanism via permutation groups, capturing pairwise correlations between neighboring nodes. We prove that our approach is strictly more powerful than the 2-dimensional Weisfeiler-Lehman (2-WL) graph isomorphism test and not less powerful than the 3-WL test. Moreover, we prove that our approach achieves the linear sampling complexity. Comprehensive experiments on multiple synthetic and real-world datasets demonstrate the superiority of our model.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 49 of its 83 references that are in the map. First posted on arXiv 28 May 2022.

Builds on

49 of 83 references.

References · 49

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  4. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  5. 2017Inductive Representation Learning on Large Graphscited by 6,284
  6. 2018How Powerful are Graph Neural Networks?cited by 4,355
  7. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,016
  8. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  9. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  10. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  11. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
  12. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
37 more
  1. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  2. 2020Benchmarking Graph Neural Networkscited by 672
  3. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  4. 2019Provably Powerful Graph Networkscited by 385
  5. 2017Residual Gated Graph ConvNetscited by 341
  6. 2018Invariant and Equivariant Graph Networkscited by 339
  7. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  8. 2019Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networkscited by 241
  9. 2020Can Graph Neural Networks Count Substructures?cited by 235
  10. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  11. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  12. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  13. 2021Identity-aware Graph Neural Networkscited by 197
  14. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  15. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  16. 2020Random Features Strengthen Graph Neural Networkscited by 184
  17. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  18. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  19. 2021Equivariant Subgraph Aggregation Networkscited by 154
  20. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  21. 2019On the Universality of Invariant Networkscited by 151
  22. 2019Relational Pooling for Graph Representationscited by 150
  23. 2021Nested Graph Neural Networkscited by 136
  24. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  25. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  26. 2018Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputscited by 96
  27. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  28. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  29. 2020Wasserstein Embedding for Graph Learningcited by 56
  30. 2018Covariant Compositional Networks For Learning Graphscited by 54
  31. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  32. 2019Coloring graph neural networks for node disambiguationcited by 49
  33. 2021Autobahn: Automorphism-based Graph Neural Netscited by 39
  34. 2020Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Resultscited by 19
  35. 2017On the expressive power of query languages for matricescited by 14
  36. 2018On the expressive power of linear algebra on graphscited by 14
  37. 2016A General Framework for Estimating Graphlet Statistics via Random Walkcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 7; 2024: 5; 2025: 0; 2026: 2.

15 papers.

Sort:

By area:

  1. 2023Continual Learning on Dynamic Graphs via Parameter Isolationcited by 35
  2. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  3. 2022Test-Time Training for Graph Neural Networkscited by 17
  4. 2023From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networkscited by 17
  5. 2024Towards Dynamic Message Passing on Graphscited by 11
  6. 2023Xtal2DoS: Attention-based Crystal to Sequence Learning for Density of States Predictioncited by 4
  7. 2024A Scalable and Effective Alternative to Graph Transformerscited by 4
  8. 2024Scalable Graph Compressed Convolutionscited by 2
  9. 2024Long-context Protein Language Modeling Using Bidirectional Mamba with Shared Projection Layerscited by 1
  10. 2023Introducing Expertise Logic into Graph Representation Learning from A Causal Perspectivecited by 0
  11. 2023Invariant Layers for Graphs with Nodes of Different Typescited by 0
  12. 2023Concept Prerequisite Relation Prediction by Using Permutation-Equivariant Directed Graph Neural Networkscited by 0
3 more
  1. 2024Simplicity within biological complexitycited by 0
  2. 2026Aligning Molecular Graph Explanations with Chemical Identity via InChIfied Invariantscited by 0
  3. 2026GraphK: Variable-Size Graph Generation with Efficient Edge Constructioncited by 0