mlsanityData to 7 Oct 2026

Permutation-Invariant Graph Partitioning:How Graph Neural Networks Capture Structural Interactions?

arXiv 2312.08671 ↗First posted 14 Dec 2023cs.LG cs.AIcited by 2

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) have paved the way for being a cornerstone in graph-related learning tasks. Yet, the ability of GNNs to capture structural interactions within graphs remains under-explored. In this work, we address this gap by drawing on the insight that permutation invariant graph partitioning enables a powerful way of exploring structural interactions. We establish theoretical connections between permutation invariant graph partitioning and graph isomorphism, and then propose Graph Partitioning Neural Networks (GPNNs), a novel architecture that efficiently enhances the expressive power of GNNs in learning structural interactions. We analyze how partitioning schemes and structural interactions contribute to GNN expressivity and their trade-offs with complexity. Empirically, we demonstrate that GPNNs outperform existing GNN models in capturing structural interactions across diverse graph benchmark tasks.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 41 of its 61 references that are in the map. First posted on arXiv 14 Dec 2023.

Builds on

41 of 61 references.

References · 41

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  9. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  10. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  11. 2020Benchmarking Graph Neural Networkscited by 672
  12. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
29 more
  1. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 442
  2. 2019Provably Powerful Graph Networkscited by 385
  3. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  4. 2020Can Graph Neural Networks Count Substructures?cited by 235
  5. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  6. 2021Identity-aware Graph Neural Networkscited by 197
  7. 2021Equivariant Subgraph Aggregation Networkscited by 154
  8. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  9. 2019On the Universality of Invariant Networkscited by 151
  10. 2021Nested Graph Neural Networkscited by 136
  11. 2020Directional Graph Networkscited by 132
  12. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  13. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  14. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  15. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  16. 2021Topological Graph Neural Networkscited by 86
  17. 2021Reconstruction for Powerful Graph Representationscited by 65
  18. 2019k-hop Graph Neural Networkscited by 57
  19. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  20. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  21. 2021Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Trackingcited by 47
  22. 2023A Survey on Privacy in Graph Neural Networks: Attacks, Preservation, and Applicationscited by 22
  23. 2022A Practical, Progressively-Expressive GNNcited by 20
  24. 2018Graph Partition Neural Networks for Semi-Supervised Classificationcited by 17
  25. 2023Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding (Technical Report)cited by 9
  26. 2020Graph Partitioning and Graph Neural Network based Hierarchical Graph Matching for Graph Similarity Computationcited by 8
  27. 2021Large-Scale Network Embedding in Apache Sparkcited by 6
  28. 2023Union Subgraph Neural Networkscited by 6
  29. 2019On neighbourhood degree sequences of complex networkscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 0; 2026: 1.

2 papers.

  1. 2024Molecular Graph Representation Learning via Structural Similarity Informationcited by 0
  2. 2026Feature Transformation Enhanced Jacobi Polynomial Graph Filtering for Graph Anomaly Detectioncited by 0