Chordless Structure: A Pathway to Simple and Expressive GNNs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909622430859264 |
|---|---|
| author | Pan, Hongxu Hu, Shuxian Zhou, Mo Wang, Zhibin Gu, Rong Tian, Chen Yang, Kun Zhong, Sheng |
| author_facet | Pan, Hongxu Hu, Shuxian Zhou, Mo Wang, Zhibin Gu, Rong Tian, Chen Yang, Kun Zhong, Sheng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_19188 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Chordless Structure: A Pathway to Simple and Expressive GNNs Pan, Hongxu Hu, Shuxian Zhou, Mo Wang, Zhibin Gu, Rong Tian, Chen Yang, Kun Zhong, Sheng Machine Learning 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. |
| title | Chordless Structure: A Pathway to Simple and Expressive GNNs |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.19188 |