paper-with-me

홈 › Papers

Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs

2025-08-31 · Arman Gupta, Govind Waghmare, Gaurav Oberoi, Nitish Srivastava arxiv

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.

📄 PDF Abstract BibTeX arXiv:2509.00772

Code (0)

등록된 구현이 없습니다.

Tasks

Node ClassificationGraph Learning

Similar Papers 제목 키워드 기반

Full-Spectrum Graph Neural Networks: Expressive and Scalable

2026-05-07 · Xiaohan Wang, Deyu Bo, Longlong Li, Kelin Xia arxiv

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 Learning

Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs

2023-02-23 · Xin Zheng, Miao Zhang, Chunyang Chen, Qin Zhang 외

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 Search

Redesigning graph filter-based GNNs to relax the homophily assumption

2024-09-13 · Samuel Rey, Madeline Navarro, Victor M. Tenorio, Santiago Segarra 외

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 Bias

Edge Directionality Improves Learning on Heterophilic Graphs

2023-05-17 · Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca 외

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) Graphs

HeroFilter: Adaptive Spectral Graph Filter for Varying Heterophilic Relations

2025-10-13 · Shuaicheng Zhang, Haohui Wang, Junhong Lin, Xiaojie Guo 외 arxiv

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