mlsanityData to 14 Oct 2026

Chordless Structure: A Pathway to Simple and Expressive GNNs

arXiv 2505.19188 ↗First posted 25 May 2025cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Researchers have proposed various methods of incorporating more structured information into the design of Graph Neural Networks (GNNs) to enhance their expressiveness. However, these methods are either computationally expensive or lacking in provable expressiveness. In this paper, we observe that the chords increase the complexity of the graph structure while contributing little useful information in many cases. In contrast, chordless structures are more efficient and effective for representing the graph. Therefore, when leveraging the information of cycles, we choose to omit the chords. Accordingly, we propose a Chordless Structure-based Graph Neural Network (CSGNN) and prove that its expressiveness is strictly more powerful than the k-hop GNN (KPGNN) with polynomial complexity. Experimental results on real-world datasets demonstrate that CSGNN outperforms existing GNNs across various graph tasks while incurring lower computational costs and achieving better performance than the GNNs of 3-WL expressiveness.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 38 of its 57 references that are in the map. First posted on arXiv 25 May 2025.

Builds on

38 of 57 references.

References · 38

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  7. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  9. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
  10. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  11. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  12. 2019Analyzing Learned Molecular Representations for Property Predictioncited by 375
26 more
  1. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  2. 2017Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphscited by 310
  3. 2020Self-supervised Graph Learning for Recommendationcited by 305
  4. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  5. 2020Can Graph Neural Networks Count Substructures?cited by 236
  6. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  7. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  8. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  9. 2023Graph Inductive Biases in Transformers without Message Passingcited by 153
  10. 2021Nested Graph Neural Networkscited by 137
  11. 2018DeepInf: Social Influence Prediction with Deep Learningcited by 128
  12. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  13. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  14. 2018GeniePath: Graph Neural Networks with Adaptive Receptive Pathscited by 66
  15. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  16. 2019k-hop Graph Neural Networkscited by 57
  17. 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
  18. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  19. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  20. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  21. 2021Cycle Representation Learning for Inductive Relation Predictioncited by 23
  22. 2022Geodesic Graph Neural Network for Efficient Graph Representation Learningcited by 19
  23. 2024Topology-Informed Graph Transformercited by 13
  24. 2024An end-to-end attention-based approach for learning on graphscited by 11
  25. 2023Cycle Invariant Positional Encoding for Graph Representation Learningcited by 8
  26. 2014An Efficient Algorithm for Enumerating Chordless Cycles and Chordless Pathscited by 1

Built on by

Not cited yet.