Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily

Asela Hevapathige, Asiri Wijesinghe, Ahad N. Zehmakan · 2025

Read Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily by Asela Hevapathige, Asiri Wijesinghe, Ahad N. Zehmakan (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-2511-06608.txt.

Introduction

Asela Hevapathige, Asiri Wijesinghe, and Ahad Zehmakan let each node in a graph choose how far its information should travel. Graph neural networks classify nodes by pooling neighbor features, but fixed pooling depth hurts when some neighborhoods mix labels heavily and others do not. Homophilic areas want shallow reach, heterophilic areas want care, and one depth cannot serve both.

Theory ties local structure and label patterns to how class information survives each round of pooling, showing the best depth varies by node. Their adaptive architecture picks a depth per node from those grounded measures. One unified model then handles both friendly and hostile neighborhoods, lifting standard backbones across varied benchmarks.

Catalog record

CREATORAsela Hevapathige, Asiri Wijesinghe, Ahad N. Zehmakan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-06608

Browse the full library · About the Tower of Babel

Full text

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

Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily Asela Hevapathige, Asiri Wijesinghe, Ahad N. Zehmakan Abstract Graph Neural Networks (GNNs) have achieved significant success in addressing node classification tasks. However, the effectiveness of traditional GNNs degrades on heterophilic graphs, where connected nodes often belong to different labels or properties. While recent work has introduced mechanisms to improve GNN performance under heterophily, certain key limitations still exist. Most existing models apply a fixed aggregation depth across all nodes, overlooking the fact that nodes may require different propagation depths based on their local homophily levels and neighborhood structures. Moreover, many methods are tailored to either homophilic or heterophilic settings, lacking the flexibility to generalize across both regimes. To address these challenges, we develop a theoretical framework that links local structural and label characteristics to information propagation dynamics at the node level. Our analysis shows that optimal aggregation depth varies across nodes and is critical for preserving class-discriminative information. Guided by this insight, we propose a novel adaptive-depth GNN architecture that dynamically selects node-specific aggregation depths using theoretically grounded metrics. Our method seamlessly adapts to both homophilic and heterophilic patterns within a unified model. Extensive experiments demonstrate that our approach consistently enhances the performance of standard GNN backbones across diverse benchmarks. Introduction Graph Neural Networks (GNNs) have achieved remarkable success in various graph-based downstream tasks across diverse domains, including social network analysis ( 31 ; 5 ) , bioinformatics ( 59 ; 57 ) , and anomaly detection ( 25 ; 4 ) . Particularly, GNNs have demonstrated strong performance in node classification tasks due to their ability to integrate structural characteristics and node feature information into meaningful representations ( 43 ; 24 ) . However, many mainstream GNNs are built upon the homophily assumption, where connected nodes tend to share similar labels or characteristics ( 36 ; 66 ) . While this assumption has proven effective for many real-world networks, such as citation networks and knowledge graphs ( 56 ) , it significantly limits GNNs’ performance on heterophilic graphs, where connected nodes often have different labels or properties ( 61 ) . Such heterophilic patterns are common in many real-world scenarios, including social networks and web graphs ( 37 ; 64 ; 38 ) . To address this limitation, researchers have begun exploring specialized heterophily-aware GNN architectures that explicitly account for the dissimilarity between connected nodes and develop alternative message-passing strategies ( 64 ; 60 ; 34 ; 65 ; 47 ) . Nonetheless, certain limitations still exist. First, categorizing graphs as homophilic or heterophilic based on simple neighborhood label ratios oversimplifies the complex nature of information propagation in graphs. Real-world graphs are intricate structural entities with different regions or nodes exhibiting varying levels of homophily. Different nodes have varying sensitivity to information aggregation, depending on their structural context, features, and neighbor label composition. A more nuanced understanding of this phenomenon is required to design GNN architectures that accommodate these differences. Second, methods specifically designed for heterophilic graphs often lack the flexibility to effectively handle both homophilic and heterophilic contexts within the same architecture, limiting their applicability and generalizability across diverse graph types. We aim to address these limitations through a fundamental observation: optimal information propagation strategies are inherently different across nodes within the same graph. The uniform nature of information aggregation in current GNNs (i.e., fixed layer depth applied to all nodes) limits node classification performance, as different nodes have varying information aggregation needs based on their local neighbourhood properties, including degree distribution, label homophily ratio, and feature similarity patterns within their close neighbourhoods. This motivates us to theoretically connect structural and label characteristics to information propagation dynamics at the node level, gaining a more nuanced understanding of node-specific aggregation needs beyond global graph homophily characteristics. Building on these theoretical insights, we derive node-specific metrics that quantify individual node aggregation requirements without being constrained by global graph homophily measures. We then utilize these insights to develop dynamic GNN architectures that adaptively determine aggregation depth for each node, improving their ability to handle node-specific information propagation needs. The main contributions of our work are summarized as follows: • Theoretical Foundation : We establish theoretical connections between structural and label characteristics and information propagation dynamics, deriving node-specific metrics that quantify optimal aggregation depth requirements in GNNs. • Novel Adaptive Depth Architecture : We propose a novel GNN architecture that dynamically adjusts aggregation depth for individual nodes based on their specific information propagation needs, with two distinct variants to accommodate different computational requirements. • Unified Homophilic/Heterophilic Handling : Our architecture provides a single framework that seamlessly accommodates both homophilic and heterophilic graph patterns without requiring separate architectures or preprocessing steps. • Empirical Validation : We provide comprehensive experiments demonstrating that our adaptive depth architecture consistently improves node classification performance of mainstream GNN backbones across diverse graph structures and homophily levels. Related Work Heterophily-Aware GNNs While traditional GNNs assume homophily, such an inductive bias is believed to result in performance degradation in less homophilic graphs ( 32 ) . Geom-GCN ( 37 ) is one of the early works that identified this performance bottleneck. Since then, there has been a plethora of works targeting enhancing GNN performance in heterophilic graphs. Some works propose filtering neighbours to improve aggregation performance on heterophilic graphs by excluding or deprioritising dissimilar nodes ( 7 ; 34 ; 63 ; 18 ) . Furthermore, some works have shown that incorporating higher-order neighbourhoods could alleviate this issue, as it enables the aggregation process to access more homophilic information ( 66 ; 49 ; 50 ; 30 ; 58 ; 28 ) . There have been some works introducing structural constraints such as neighbour ordering ( 42 ) and selective aggregation mechanisms ( 21 ; 20 ; 48 ) to enable more discriminative node representations by controlling how information flows between nodes of different classes. While the aforementioned works have focused on improving GNN architecture, some studies have taken an alternative path by rewiring the input graph to increase homophily ( 17 ; 29 ; 6 ; 9 ) . Recent theoretical findings have shown that heterophily does not always negatively impact node classification. 35 first demonstrated this, showing that moderate levels of heterophily are more detrimental to GNNs than conditions of extreme heterophily. Further, 47 elaborated that class separability in node classification using GNNs depends on both neighborhood distribution distances and node degrees, establishing that the impact of heterophily is nuanced rather than uniformly negative. Our work is fundamentally different from the above. We present a granular node-level theoretical framework that decomposes GNN aggregation based on neighbourhood label composition, demonstrating how the classification quality of individual nodes scales across multiple layers. Our work shows that nodes with varying neighborhood compositions benefit from different propagation depths, resulting in an adaptive architecture. Depth-Adaptive GNNs There have been few works exploring the impact of adaptive depth in GNNs. 53 employed reinforcement learning to design a flexible GNN architecture that adaptively searches for optimal parameters of components, including GNN depth, aggregation functions, and pooling operations for graph classification. ADMP-GNN ( 1 ) introduced a depth allocation policy for GNNs using centrality heuristics to cluster structurally similar nodes and assign optimal

Read the complete text