线图变换能提升图神经网络区分复杂图结构的能力
Theoretical Insights into Line Graph Transformation on Graph Learning
- 通过线图变换将原图边映射为节点，简化复杂图结构
- 实验表明变换后对CFI图和强正则图的区分准确率显著提升
- 适合研究图神经网络表达能力与图同构测试的学者
线图变换在图论中广泛研究，其中线图的每个节点对应原图的一条边。这一变换启发了一系列应用于线图的图神经网络（GNN），在多种图表示学习任务中表现有效。然而，关于线图变换如何影响GNN模型表达能力的理论研究仍有限。本研究聚焦于两类对魏斯费勒-莱曼（WL）测试具有挑战性的图：Cai-Fürer-Immerman（CFI）图和强正则图，证明线图变换可排除这些难分辨的图属性，从而帮助WL测试区分它们。我们通过一系列实验，在不同图结构类型上对比了原始图与线图变换后图的图同构测试精度与效率，验证了理论发现。
原文摘要 · Abstract (English)
Line graph transformation has been widely studied in graph theory, where each node in a line graph corresponds to an edge in the original graph. This has inspired a series of graph neural networks (GNNs) applied to transformed line graphs, which have proven effective in various graph representation learning tasks. However, there is limited theoretical study on how line graph transformation affects the expressivity of GNN models. In this study, we focus on two types of graphs known to be challenging to the Weisfeiler-Leman (WL) tests: Cai-Fürer-Immerman (CFI) graphs and strongly regular graphs, and show that applying line graph transformation helps exclude these challenging graph properties, thus potentially assist WL tests in distinguishing these graphs. We empirically validate our findings by conducting a series of experiments that compare the accuracy and efficiency of graph isomorphism tests and GNNs on both line-transformed and original graphs across these graph structure types.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。