Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Node ClassificationGraph LearningSimilar Papers 제목 키워드 기반
Full-Spectrum Graph Neural Networks: Expressive and Scalable
It is well established that spectral graph neural networks (GNNs) can universally approximate node signals; however, their expressive power remains bounded by the 1-dimensional Weisfeiler-Lehman test, which is mirrored i…
Graph LearningAuto-HeG: Automated Graph Neural Network on Heterophilic Graphs
Graph neural architecture search (NAS) has gained popularity in automatically designing powerful graph neural networks (GNNs) with relieving human efforts. However, existing graph NAS methods mainly work under the homoph…
Graph LearningGraph Neural NetworkNeural Architecture SearchRedesigning graph filter-based GNNs to relax the homophily assumption
Graph neural networks (GNNs) have become a workhorse approach for learning from data defined over irregular domains, typically by implicitly assuming that the data structure is represented by a homophilic graph. However,…
Inductive BiasEdge Directionality Improves Learning on Heterophilic Graphs
Graph Neural Networks (GNNs) have become the de-facto standard tool for modeling relational data. However, while many real-world graphs are directed, the majority of today's GNN models discard this information altogether…
Graph Neural NetworkNode ClassificationNode Classification on Non-Homophilic (Heterophilic) GraphsHeroFilter: Adaptive Spectral Graph Filter for Varying Heterophilic Relations
Graph heterophily, where connected nodes have different labels, has attracted significant interest recently. Most existing works adopt a simplified approach - using low-pass filters for homophilic graphs and high-pass fi…
Natural Questions