让图神经网络更懂异质图,通过方向性和表达力提升分类效果
Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs
- 设计可表达高阶交互的GNN,分别处理流入流出边
- 在5个异质图数据集上优于现有方法,罗马帝国图上达最新水平
- 方向性有效依赖图结构,人工加方向未必有帮助
在异质图中,相邻节点常属于不同类别,传统图神经网络因依赖局部同质邻居而表现不佳。已有研究指出,建模边的方向性可提升有效同质性并改善分类性能。同时,多项式表达力强的GNN在捕捉特征间高阶交互方面展现潜力。本文研究边方向性与表达性消息传递在异质图节点分类中的联合效应,提出两种架构:(1) 多项式表达的GAT基线(Poly);(2) 方向感知变体(Dir-Poly),分别聚合入边和出边。两者均能学习输入特征上的置换等变高次多项式,且无额外时间复杂度。在五个基准异质图数据集上的实验表明,Poly模型持续优于现有基线,而Dir-Poly在具有固有方向性的图(如罗马帝国图)上进一步提升,达到当前最优结果。有趣的是,在无向图中引入人工方向性并不总有效,说明方向性消息传递的效果具有上下文依赖性。研究揭示了边方向性与表达性特征建模在异质图学习中的互补作用。
原文摘要 · Abstract (English)
In heterophilic graphs, where neighboring nodes often belong to different classes, conventional Graph Neural Networks (GNNs) struggle due to their reliance on local homophilous neighborhoods. Prior studies suggest that modeling edge directionality in such graphs can increase effective homophily and improve classification performance. Simultaneously, recent work on polynomially expressive GNNs shows promise in capturing higher-order interactions among features. In this work, we study the combined effect of edge directionality and expressive message passing on node classification in heterophilic graphs. Specifically, we propose two architectures: (1) a polynomially expressive GAT baseline (Poly), and (2) a direction-aware variant (Dir-Poly) that separately aggregates incoming and outgoing edges. Both models are designed to learn permutation-equivariant high-degree polynomials over input features, while remaining scalable with no added time complexity. Experiments on five benchmark heterophilic datasets show that our Poly model consistently outperforms existing baselines, and that Dir-Poly offers additional gains on graphs with inherent directionality (e.g., Roman Empire), achieving state-of-the-art results. Interestingly, on undirected graphs, introducing artificial directionality does not always help, suggesting that the benefit of directional message passing is context-dependent. Our findings highlight the complementary roles of edge direction and expressive feature modeling in heterophilic graph learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。