Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs

Arman Gupta, Govind Waghmare, Gaurav Oberoi, Nitish Srivastava · 2025

Read Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs by Arman Gupta, Govind Waghmare, Gaurav Oberoi, Nitish Srivastava (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00772.txt.

Introduction

Arman Gupta, with three co-authors, studies graph neural networks on heterophilic graphs. In such graphs, neighbors often belong to different classes. Standard networks rely on neighbors that resemble each other. They thus struggle when that resemblance fails. The team asks if edge direction and richer features can help.

They propose two architectures for node classification. Poly learns high-degree combinations of input features. Dir-Poly also splits incoming edges from outgoing edges. Both models stay scalable with no added time cost. Tests use five heterophilic benchmark datasets. Poly beats existing baselines across the board. Dir-Poly adds gains on graphs with true direction. On undirected graphs, fake direction does not always help.

Catalog record

CREATORArman Gupta, Govind Waghmare, Gaurav Oberoi, Nitish Srivastava
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-00772

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs Arman Gupta, Govind Waghmare, Gaurav Oberoi, Nitish Srivastava Abstract . 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. 1. Introduction GNNs have become the de facto approach for learning over graph-structured data, achieving remarkable success in domains ranging from social network analysis and recommendation systems to molecular property prediction and fraud detection ( Wu et al. 2019 ) . However, the majority of GNN architectures ( Kipf and Welling 2016 ; Veličković et al. 2018 ; Hamilton et al. 2017 ) assume that the input graphs are undirected and homophilic, that is, neighboring nodes tend to belong to the same class or share similar attributes. This assumption underpins the core message-passing mechanism of many GNNs, where information is aggregated from local neighbors to infer node properties. Yet, many real-world graphs such as citation networks, web graphs, and interaction graphs, are inherently directed and heterophilic. In heterophilic graphs, connected nodes frequently belong to different classes, violating the inductive bias of classical GNNs ( Zhu et al. 2020 ) . Moreover, transforming directed graphs into undirected ones, often done during preprocessing (e.g., in libraries like PyTorch Geometric 1 1 1 https://github.com/pyg-team/pytorch_geometric/blob/master/torch_geometric/datasets/heterophilous_graph_dataset.py##L119 ), may lead to information loss, especially in heterophilic settings. Recent studies ( Rossi et al. 2023 ) have shown that preserving edge directionality can increase the effective homophily of a graph and substantially improve GNN performance on node classification tasks in such settings. At the same time, another critical limitation of most existing GNN architectures is their limited expressive power. Traditional GNNs like GCN ( Kipf and Welling 2016 ) , GraphSAGE ( Hamilton et al. 2017 ) , or GAT ( Veličković et al. 2018 ) rely on simple, linear aggregation functions (e.g., sum, mean, and max) which cannot capture high-order, nonlinear feature interactions among nodes. This expressivity bottleneck has prompted the development of more flexible aggregation functions such as principled neighborhood aggregation (PNA) ( Corso et al. 2020 ) by combining multiple simple aggregation functions, each associated with a learnable weight but the practical capacity of PNA is still limited by simply combining multiple simple aggregation functions. Recent literature have introduced higher-order polynomially expressive models such as tGNN ( Hua et al. 2022 ) and Polynormer ( Deng et al. 2024 ) , which aim to represent richer feature transformations by learning high-degree polynomial functions while preserving permutation equivariance. However, these models either suffer from limited polynomial expressivity ( Hua et al. 2022 ) or incur high computational costs ( Liao et al. 2024 ) , making them less practical for large-scale or complex graph tasks. Although both edge directionality and polynomial expressiveness have independently been shown to improve performance in specific contexts, their combined effect on heterophilic node classification remains largely unexplored. In this work, we bridge this gap by empirically studying the synergistic impact of edge directionality and expressive message passing on heterophilic graphs. Specifically, we design two architectures: • Poly , a GAT-based model augmented with a permutation-equivariant polynomially expressive message passing scheme. Inspired by the local attention mechanism in Polynormer ( Deng et al. 2024 ) , Poly explicitly captures high-degree interactions by recursively composing local attention and linear layers with multiplicative gating, and • Dir-Poly , which additionally accounts for edge direction by performing separate aggregations over incoming and outgoing edges. Both models are scalable and do not incur additional time complexity compared to standard GATs. We evaluate these architectures on five benchmark heterophilic datasets: Roman Empire, Amazon Ratings, Minesweeper, Tolokers, and Questions. Our results show that Poly consistently outperforms all existing baselines, while Dir-Poly achieves further gains on inherently directed graphs like Roman Empire. However, enforcing artificial directionality on undirected graphs offers limited benefit, indicating that direction-aware message passing is context-dependent. Overall, our results show that directional message passing and high-degree polynomial aggregation are complementary, and combining them effectively models complex interactions in heterophilic graphs. 2. Related Work Graph Neural Networks (GNNs) have emerged as core models for learning from graph-structured data. Early frameworks such as GCN ( Kipf and Welling 2016 ) , GAT ( Veličković et al. 2018 ) , and GraphSAGE ( Hamilton et al. 2017 ) established neighborhood aggregation as the fundamental paradigm, typically using permutation-invariant functions like sum or mean. While effective on homophilic graphs, where neighboring nodes often share labels, these models degrade in performance on heterophilic graphs due to their implicit homophily assumptions. GNNs for Heterophily. To address this, recent models such as H2GCN ( Zhu et al. 2020 ) , GPR-GNN ( Chien et al. 2020 ) , and GGCN ( Yan et al. 2022 ) introduce mechanisms to disentangle structural proximity from label similarity, either by decoupling feature propagation or adopting flexible message-passing schemes. More recently, Dir-GNN ( Rossi et al. 2023 ) demonstrated that explicitly modeling edge directionality improves performance on heterophilic datasets by distinguishing between incoming and outgoing flows, an insight especially relevant for real-world directed graphs like citation or interaction networks. Directionality in GNNs. Although several earlier GNNs ( Gilmer et al. 2017 ; Scarselli et al. 2009 ; Li et al. 2017 ) nominally support directed graphs, many implementations symmetrize edges or only partially utilize directional information (e.g., GatedGCN ( Li et al. 2017 ) aggregates solely from out-neighbors). Spectral methods like DGCN ( Tong et al. 2020b ) , DiGCN ( Tong et al. 2020a ) , and MagNet ( Zhang et al. 2021 ) incorporate directional operators, but often share weights across directions and suffer from limited scalability due to computationally expensive spectral decompositions. Dir-GNN ( Rossi et al. 2023 ) overcomes these limitations via spatial aggregation paths that preserve direction-specific semantics, showing notable gains on heterophilic tasks. Expressive Aggregation Functions. Parallel to directionality, another line of work enhances GNN expressivity through advanced aggregation. PNA ( Corso et al. 2020 ) improves flexibility using multiple aggregators and degree-scalers. Polynormer ( Deng et al. 2024 ) further introduces polynomially expressive attention to model high-order interactions while preserving permutation equivariance. Tensor-based approaches ( Hua et al. 2022 ) similarly aim to capture higher-order structures,

Read the complete text