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

AI summary

Overview

Research area: Graph machine learning — specifically Graph Neural Networks (GNNs) for semi-supervised node classification, and the problem of varying homophily (whether connected nodes share labels) across a graph.

Technical level: Advanced. The paper builds a formal theoretical framework (contextual stochastic block model, signal/noise variance decomposition, multi-layer aggregation analysis) before deriving its architecture.

Scope: The paper derives a node-level theory of how neighbourhood label composition affects information propagation depth in GNNs, and uses it to build AD-GNN, an adaptive-depth architecture that assigns each node its own number of aggregation layers.

What This Paper Is About

Most GNNs apply the same number of aggregation layers to every node, which assumes all nodes need the same amount of neighbourhood information. This paper shows theoretically that the optimal propagation depth depends on each node's local mix of same-label and opposite-label neighbours and its degree, and that a single fixed depth is therefore wrong for many nodes. The authors use that theory to build an architecture that gives each node a node-specific depth within one unified model that works on both homophilic and heterophilic graphs.

Key Contributions

1. A node-level theoretical framework. The authors decompose GNN aggregation by neighbour label, define a signal preservation factor α_v = (1 + d_v⁺ − d_v⁻)/(d_v + 1) for node v, and derive closed-form expressions for signal variance, noise variance, and node-specific classification quality Q_v = α_v²(d_v + 1)Δ²/σ²_intra, then extend this to an n-layer setting.

2. The AD-GNN architecture and two variants. A depth allocation mechanism assigns each node a stopping depth using a depth benefit metric ε_v^n = (α_v² · (d_v + 1))^n and a learnable, monotonically increasing threshold τ_θ(t) = λ + (1 − λ)·θ(t). A second variant, AD-GNN_fast, replaces the learned neighbour-similarity function with a static degree-based approximation p_uv = (d_u × d_v) / max_(i,j)∈E (d_i × d_j).

3. A unified homophilic/heterophilic model. No separate architectures or preprocessing are required for the two regimes; the same depth-allocation rule handles both, and the mechanism is defined as a wrapper that can be added to existing backbones (GCN, GAT, GraphSAGE, MixHop, GATv2, DirGNN).

4. Extensive empirical validation. Experiments on 11 datasets covering homophilic and heterophilic settings, plus a case study, an oversmoothing study, a hyperparameter sensitivity study, and a scalability study on ogbn-arxiv.

Main Findings

• Optimal depth is node-dependent, not graph-level. Theorem 1 shows that after one aggregation the expected representation is 𝔼[h_v | y_v] = ((1 + d_v⁺)/(d_v + 1))μ^{y_v} + (d_v⁻/(d_v + 1))μ^{1−y_v}, with signal variance α_v²Δ² and noise variance σ²_intra/(d_v + 1). Because α_v varies per node, so does the benefit of aggregating.

• Strong homophily: aggregation almost always helps. When d_v⁺ ≫ d_v⁻, α_v ≈ 1 and Q_v ∝ d_v, so higher-degree nodes benefit more, and according to the authors' reading of Corollary 1 aggregation is beneficial regardless of degree.

• Strong heterophily is not inherently bad, but is degree-sensitive. When d_v⁻ ≫ d_v⁺, α_v moves from 0 at low degree toward −1 at high degree; quality is poor at low degree (signal cancellation, Q_v ≈ 0) but scales like Q_v ∝ d_v at high degree.

• Balanced neighbourhoods are the worst case. When d_v⁺ ≈ d_v⁻, α_v ≈ 1/(d_v + 1), and the cancellation gets worse as degree grows (α_v → 0), so high-degree nodes with balanced neighbour labels are hardest to classify.

• Depth compounds the effect. Theorem 2 gives multi-layer signal variance α_v^{2n}Δ², noise variance σ²_intra/(d_v + 1)^n, and quality Q_v^n = α_v^{2n}(d_v + 1)^n Δ²/σ²_intra. If |α_v| < 1, degradation compounds exponentially with depth, while noise reduction compounds favourably.

• Large gains on heterophilic benchmarks. With GCN as backbone, Texas moves from 60.00 ± 6.45 to 92.30 ± 4.52, Cornell from 55.14 ± 8.46 to 88.51 ± 4.87, Wisconsin from 61.60 ± 7.00 to 93.88 ± 3.03, and Film from 30.26 ± 0.79 to 42.54 ± 1.15.

• Gains on homophilic benchmarks as well, though smaller. GCN on Citeseer goes from 76.68 ± 1.64 to 79.14 ± 1.00, Pubmed from 86.74 ± 0.47 to 88.39 ± 0.32, Photo from 89.30 ± 0.82 to 94.10 ± 0.31, Cora-ML from 87.07 ± 1.21 to 87.32 ± 1.25, and DBLP from 83.93 ± 0.34 to 84.14 ± 0.44.

• The method also lifts heterophily-aware backbones. AD-MixHop reaches 90.21 ± 3.59 on Cornell versus 73.51 ± 6.34 for MixHop, and AD-DirGNN reaches 91.70 ± 2.60 on Cornell versus 76.51 ± 6.14 for DirGNN, indicating the mechanism captures information those models miss.

• The fast variant is competitive. AD-GCN_fast matches AD-GCN closely and sometimes exceeds it, for example 94.38 ± 2.86 versus 93.88 ± 3.03 on Wisconsin and 90.23 ± 0.42 versus 90.09 ± 0.58 for AD-MixHop_fast on Pubmed.

• Case study confirms the theory. On synthetic stochastic block model graphs, performance stays stable at both extremes of homophily but declines in mixed-homophily settings, consistent with Corollary 3. Excluding low-degree nodes (degrees 1–2) from aggregation improved performance under strong heterophily, while preventing aggregation for high-degree nodes caused a decline.

• Oversmoothing is mitigated. On Citeseer and Texas, tested at layer depths 1, 2, 4, 8, 16, 32, and 64, traditional GNNs degrade rapidly with depth while AD-GNN variants maintain consistent performance.

• Optimal λ depends on degree distribution. Homophilic datasets (Citeseer, Pubmed, DBLP) perform best at λ = 0. Chameleon also prefers λ = 0 because most of its nodes have moderate to high degree, whereas Texas and Film, whose nodes mostly have degrees 1–2, benefit from λ > 0.

• Scalability costs are modest. On ogbn-arxiv with hidden size 128, AD-GCN_fast at depth 4 uses 55.5K parameters versus 55.5K for GCN, takes 286.40 ms per epoch versus 277.13 ms, and reaches 70.18% versus 69.53%. At depth 8, AD-GCN_fast uses 122.5K parameters versus 122.5K, 580.15 ms versus 564.73 ms, and 70.42% versus 68.39%. AD-GCN itself uses 88.5K parameters at depth 4 (405.85 ms, 70.32%) and 155.6K at depth 8 (655.52 ms, 70.63%). The paper states the runtime increase for AD-GCN_fast is around 5%.

• Complexity. AD-GNN totals O(|E| × d + t_max × (|E| + |V|)), while AD-GNN_fast reduces to O(t_max × (|E| + |V|)) and requires no regularization term.

Methodology in Plain English

The authors start with a simple question: if you average a node's features with its neighbours' features, how much does that help or hurt that specific node? To answer it analytically, they set up a standard two-class synthetic model where each class has a prototype feature vector, and every node's features are that prototype plus Gaussian noise. They then split a node's neighbours into same-label and opposite-label groups and work out what the averaged representation looks like in expectation.

The punchline is a single number per node, α_v, which measures how much of the original class signal survives the averaging. If a node has many same-label neighbours, α_v is near 1 and averaging is good. If it has many opposite-label neighbours and few neighbours overall, the signals cancel. If it has roughly equal numbers of each, cancellation is severe, and getting more neighbours makes it worse rather than better. Raising α_v to the power 2n shows what happens when you stack layers: good signal stays good, bad signal degrades exponentially.

Because α_v depends on neighbour labels that are unknown at test time, the method estimates them. In the main variant it trains a small learnable function that takes two adjacent nodes' embeddings and predicts the probability they share a label, supervised by a regularizer on edges between training nodes. In the fast variant it skips learning entirely and uses the product of the two nodes' degrees as a same-label proxy, based on the observation that high-degree nodes tend to connect to other high-degree nodes.

With estimated α_v, the method computes a depth benefit score for every node and compares it against a learnable threshold curve. Nodes whose score clears the threshold at layer t get to aggregate at that layer; other nodes freeze their representation at whatever depth they stopped. Nodes that stop early never re-enter at deeper layers because the threshold is monotonically increasing. The whole thing is differentiable, so similarity estimates and depth allocation are trained end-to-end alongside the underlying GNN. Evaluation uses a 60/20/20 train/validation/test split with mean and standard deviation of accuracy over 10 random initializations, with Squirrel and Chameleon using the filtered splits from Platonov et al. (2023).

Why This Matters

Impact on research. The paper reframes heterophily from a graph-level property into a node-level one. Instead of asking whether a dataset is homophilic or heterophilic, it asks which nodes in a graph benefit from propagation and by how much. This gives a principled alternative to the prevailing practice of picking one depth for an entire graph, and it offers an explanatory framework for the counterintuitive result (previously reported by Ma et al. 2022 and Wang et al. 2024b) that moderate heterophily can be worse than extreme heterophily. The depth-allocation mechanism is defined generically as a wrapper, so it is orthogonal to backbone design and can be combined with existing heterophily-aware architectures.

Real-world applications.

• Fraud and anomaly detection in transaction or social networks, where connections frequently cross label boundaries and degree varies widely.
• Recommendation and social network analysis, where user-item or user-user graphs are heterophilic and node popularity (degree) follows a heavy-tailed distribution.
• Bioinformatics, such as protein interaction or molecule graphs, where functional neighbours may not share labels.
• Web and citation classification, where regional homophily varies within a single crawl.

Industry relevance. The cost profile matters here. AD-GNN_fast matches GCN's parameter count at both depth 4 and depth 8 in the ogbn-arxiv study and adds roughly 5% runtime, while improving accuracy. Since the mechanism progressively filters edges, the paper notes it can also reduce backbone GNN cost by operating on smaller edge sets at deeper layers. That combination of low overhead and a drop-in wrapper is what makes it practical for large production graphs, rather than only for small academic benchmarks.

Future Directions

• Extending beyond binary classification. The theory is developed for two classes; the paper states in the Appendix that its insights should hold in the multi-class setting, but a full multi-class derivation is left open.
• Accounting for oversmoothing and feature correlation. Remark 1 acknowledges that the main analysis assumes simplified behaviour and that real GNNs deviate; the extended analysis addressing these effects is placed in the Appendix rather than the main results.
• Choosing λ automatically. The sensitivity study shows that the best λ depends on the dataset's degree distribution (0 for DBLP, Pubmed, Citeseer, Chameleon; greater than 0 for Texas and Film), which currently requires dataset-specific tuning rather than being learned.
• Improving the fast variant's similarity proxy. The degree-product heuristic used in AD-GNN_fast is a static approximation motivated by degree assortativity; a cheap learned proxy or a hybrid could close the remaining gap to the full variant.

Target Audience

Researchers and graduate students working on graph representation learning and message passing, particularly those interested in heterophily, over-smoothing, and adaptive computation. It will also suit practitioners building GNNs on large, structurally diverse graphs who need a low-overhead way to improve an existing backbone. Readers should be comfortable with GCN-style aggregation, stochastic block models, and variance-based generalization arguments; the theoretical sections and Appendix are not written for a beginner audience.

Authors’ 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.