剔除图中冗余边，用无弦结构提升GNN表达力与效率
Chordless Structure: A Pathway to Simple and Expressive GNNs
- 通过移除环中的弦边，构建更简洁高效的图神经网络
- 理论证明其表达力强于传统k跳GNN，且计算复杂度为多项式
- 实测在多个任务上超越现有模型，兼具高性能与低开销
研究发现，图中弦边虽增加结构复杂度，但在多数情况下贡献有限。相比之下，无弦结构更高效且更具表达力。为此，本文提出基于无弦结构的图神经网络（CSGNN），并证明其表达力严格强于多项式复杂度的k跳GNN（KPGNN）。在真实数据集上的实验表明，CSGNN在各类图任务中表现优于现有GNN模型，计算开销更低，性能超过3-WL表达力的GNN。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。