GAMMA: Gated Multi-hop Message Passing for Homophily-Agnostic Node Representation in GNNs
Authors: Amir Ghazizadeh Ahsaei
Rickard Ewetz
Hao Zheng
Venue: NeurIPS 2025 poster ()
Keywords: GNNs
Semi-supervised Learning
Message Passing
Heterophlic GNNs
Primary area: deep_learning
TL;DR: A Multi-hop Message Passing method for Homophily-Agnostic Node Representation in GNNs.

Abstract: The success of Graph Neural Networks (GNNs) leverages the homophily principle, where connected nodes share similar features and labels. However, this assumption breaks down in heterophilic graphs, where same-class nodes are often distributed across distant neighborhoods rather than immediate connections. Recent attempts expand the receptive field through multi-hop aggregation schemes that explicitly preserve intermediate representations from each hop distance. While effective at capturing heterophilic patterns, these methods require separate weight matrices per hop and feature concatenation, causing parameters to scale linearly with hop count. This leads to high computational complexity and GPU memory consumption. We propose Gated Multi-hop Message Passing (GAMMA), where nodes assess how relevant the aggregated information is from their k-hop neighbors. This assessment occurs through multiple refinement steps where the node compares each hop's embedding with its current representation, allowing it to focus on the most informative hops. During the forward pass, GAMMA finds the optimal mix of multi-hop information local to each node using a single feature vector without needing separate representations for each hop, thereby maintaining dimensionality comparable to single hop GNNs. In addition, we propose a weight sharing scheme that leverages a unified transformation for aggregated features from multiple hops so the global heterophilic patterns specific to each hop are learned during training. As such, GAMMA captures both global (per-hop) and local (per-node) heterophily patterns without high computation and memory overhead. Experiments show GAMMA matches or exceeds state-of-the-art heterophilic GNN accuracy, achieving up to $\approx20\times$ faster inference. Our code is publicly available at \url{https://github.com/amir-ghz/GAMMA}.

GAMMA: Gated Multi-hop Message Passing for Homophily-AAnostic Node Representation in GNNs
Amir Ghazizadeh' Rickard Ewetz²
Hao Zheng'
1 Department of Electrical and Computer Engineering, University Central Florida, Orlando, FL, USA DDeparment of Electrical and Computer Engineering, University of Florida, Gainesville, FL, USA
{amir.g, hao. (ro.zhen))@uce edu, rewetz@ufl.edu
Abstract
The success of Graph Neural Networks (GNNs) leverages the homophily prin- ciple, where connected nodes share similar features and labels. However, this assumption breaks down in heterophilic graphs, where same-class nodes are often distributed across distant neighborhoods rather than immediate connections. Re- cent attempts expand the receptive field through multi-hop aggregation schemes that explicitly preserve intermediate representations from each hop distance. While effective at capturing heterophilic patterns, these methods require separate weight matrices per hop and feature concatenation, causing parameters scale linearly with hop count. This leads to high computational complexity and GPU memory consumption. We propose Gated Multi-hop Message Passing (GAMMA), where nodes assess how relevant the aggregated information is from their k-hop neigh- bors. This assessment occurs through multiple refinement steps where the node compares each hop's embedding with its current representation, allowing it to focus on the most informative hops. During the forward pass, GAMMA finds the optimal mix of multi-hop information local to each node using single feature vector without needing separate representations for each hop, thereby maintaining dimensionality comparable to single hop GNNs. In addition, propose weight sharing scheme that leverages a unified transformation for aggregated features from multiple hops the global heterophilic patterns specific each hop are learned during training. As such, GAMMA captures both global (per-hop) and local (per-node) heterophily patterns without high computation and memory overhead. Experiments show GAMMA matches or exceeds state-of-the-ar heterophilic GNN accuracy, achieving up 20x faster inference. Our code is publicly available https: //g::///iiti github. com/ amir- /gz//GMMM
Introduction
Graph Neural Networks (GNNs) [4
have become the standard model for learning graph- structured data across domains such as social and molecular networks (9 [6]. Their core strength lies in message passing K3), which iteratively aggregates features from local neighborhoods to capture structural information. However, most standard GNNs implicitly rely on the homophily assumption, where connected nodes are likely to share similar labels features, limiting their effectiveness on heterophilic graphs, where connected nodes frequently belong to different classes 39).
10 34
agnostic to feature similarity of aggregated Such GNNs function as low-pass filters, smoothing representations across neighbor- hoods 25 which enhances class signals in homophilic graphs but obscures them in heterophilic ones. This fundamental limitation has motivated significant research into heterophill-speccfie GNN architectures (39]
Conventional GNNs, such GCN 114 and GAT 34
nodes 22
40
Existing approaches to heterophilic graph learning broadly fall into several categories. Some works aim to capture global heterophily by enabling nodes to aggregate information from potentially
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

similar nodes graph-wide. For example, one strategy requires pre-copuutation to estimate structural
similarities, as explored by methods like SimP-GCN [[3 and Geom-GCN (29]. Other approaches
utilize learned affinity matrices to dynamically capture global heterophily patterns, exemplified by
models such as NL.GNNN (20] and CPGNN (1I. Alternatively, some methods incorporate higher- order neighborhoods, seeking same-class nodes from long range dependencies [ 29]. For example, H2GCN [40] emphasizes the aggregation of 2-hop neighbors while MixHop [I] concatenates features of nodes upto k-hops so each node is represented using its multi-hop features as its intermediate representation. Unfortunately, incorporating higher-order features requires compute and memory intensive operations that not GPU friendly.
Despite these efforts, developing GNNs that are both effective and scalable across the diverse landscape of heterophilic graphs remains a significant challenge. Most importantly, computation efficiency has been largely an afterthought in heterophilic GNN design. Our analysis reveals that state-of-the-art heterophilic GNNs like H2GCN 440 can consume over 6x more GPU memory than vanilla GCN with 33x increase in execution time, a prohibitive cost for many real-world applications.
Moreover, real-world graphs rarely exhibit purely homophilic heterophilic structures. Instead, they display mixed homophily-heterophhe patters, where optimal feature aggregation varies across different nodes and hops 23 For instance, fraud detection graphs are largely heterophilic. where fraudulent users often connect to legitimate ones, yet include homophilic clusters of coordinated fraudulent activities [6. Similarly. protein- protiinn--ieinnnii interaction networks, though generally heterophilic, contain homophilic subclusters of functionally related proteins [1]] Thus, GNNs must adopt message passing schemes capable of modeling global heterophily while exploiting localized homophily.
To address these challenges, we propose Gated Multi-hop Message Passing (GAMMA), a novel GNN architecture for heterophilic graphs that balances accuracy with computational efficiency. Our contributions are summarized as follows:
Comprehensive computational analysis: We provide the first systematic analysis of com- putational requirements and performance bottlenecks across 13 state-of-the-art heterophilic GNN architectures, revealing critical efficiency gaps in current designs.
Adaptive node-specific message passing: We introduce lightweight iterative gating mechanism that enables each node to dynamically assess the relevance of aggregated information from its k-hop neighbors, capturing nodc-specific local heterophily patterns on the fly.
Efficient weight sharing scheme: We propose parameter-efffcieett approach using learn- able scaling vectors that leverages a unified transformation for features from multiple hops, capturing global heterophilic patterns specific to each hop during training while significantly reducing memory requirements by up to 12 times compared to the state of the art.
State-of-the-art performance with efficiency: Extensive experiments demonstrate that GAMMA matches or exceeds state-of-the heterophilic GNN accuracy while achieving up 20x faster inference and substantially lower memory consumption on commodity GPUs.
By capturing both global (per-hop) and local (per-node) heterophily patterns without high computa- tional overhead, GAMMA makes heterophilic graph learning practical for real-world applications on commodity hardware.
2 Heterophilic Graph Characteristics and Performance Analysis
Our investigation reveals two critical aspects of heterophilic graph learning: the complex, non-uniform heterophily distributions across node neighborhoods and the significant computational overhead of current heterophilic GNN designs.
Heterophily is not a monolithic property. Most existing GNNs assume uniform heterophily patterns across all nodes, but our analysis reveals that real-world heterophilic graphs exhibit complex, node-specific patterns that vary significantly across hop distances. The node homophily ratio is the proportion of a node's 's neighbors that share the same class label as the node itself [30].
Fig. demonstrates two distinct manifestations of this heterogeneity. First, we observe dataset-level heterophily evolution: different datasets exhibit fundamentally different patterns of how homophily changes with hop distance. The Cornell dataset shows non-monotoni,, oscillating pattern, where 1 hhhop neighborhoods exhibit severe heterophily (79.8% of nodes having homophily ratios < 0.05).

---

which increases substantially at 2-hops (mean of 0.456), but then decreases again at 3-hops (mean of 0.266). In contrast, the Tolokers dataset displays a progressively increasing homophily trend with distance (0.634 - 0.654 + 0.660 for 1-, 2-, and 3-hops respectively), suggesting that same-class nodes become more accessible at greater distances.
However, the more critical insight lies in the node-level heterophily diversity. Within the same dataset and hop distance, individual nodes ex- hibit dramatically different homophily patterns, For instance, in Cornell's 2-hop neighborhoods, while 44.8% of nodes concentrate around high homophily (0.72), others span the entire spec- trum from 0.02 to 1.0. This variance indicates that Node i might experience a heterophily tra- jectory of [high, low, medium] across 1-2-3 hops, while Node in the same graph follows an en- tirely different pattern such as [low, high, low]. Unlike global parameters that assume all nodes benefit equally from information at a specific hop distance, this node-specific heterophily requires adaptive mechanisms that allow each node to identify which hop distances contain the most relevant class information for its individual prediction task.
Figure 1: Node homophily density across 3-hop distances cornell and tolokers.
These observations reveal that heterophily is neither a monolithic graph-level property nor a uniform node-level characteristic. Instead, it manifests as multi-facede phenomenon with both global struc- tural patterns (varying across datasets) and highly individualized local neighborhood configurations (varying across nodes within the same graph), necessitating architectures that can adapt to both levels of heterogeneity simultaneously.
GPU efficiency analysis. Current heterophilic GNN architectures face significant performance challenges on commodity hardware. While efficient GPU execution relies on dense matrix multi- plications, heterophilic multi-hop GNNs often require recursive sparse-dense operations, feature concatenation [1, and intermediate storage (40) that substantially increase computational overhead. From memory perspective, high usage arises from concatenating features across multiple hops and caching intermediate embeddings. For instance, BernNet's Kthhorder filter requires K separate sparse-dent multiplications, each a distinct pass over the edge list with its own kernel overhead and intermediate storage.
From a compute standpoint, many low-level operations are executed as dozens of small, memory- bound kernels. This overhead becomes dominant on large graphs, even when the asymptotic com- plexity aligns with a simple GCN. For example, in M2M2GCN (18), each edge triggers small MLP and a segmented softmax over c-dimensional vector. These operations cannot be cast as one large matrix-matrix multiply, so they incur per-edge kernel launches and intermediate result synchronization, further increasing runtime and reducing GPU efficiency.
To quantify these costs, we benchmarked 13 representative GNN variants- each configured with the same hidden dimension and number of layers on the Flickr dataset using an NVIDIA RTX A2000 GPU.
As illustrated in Fig. H2GCN, con- sumes over 6x more GPU memory than vanilla GCN and incurs 33x increase in combined forward and backward time. Moreover, memory footprint does not al- ways predict execution time. BernNet uses roughly one-third the memory of GAT yet runs slower, owing to its intricate graph operations (e.g., K th-order filter caleula- tion) and frequent GPU memory transac- tions. These results underscore a funda- mental trade-off between expressive power and computational efficiency. These find- ings underscore the need for architectures that combine heterophilic modeling capac- ity with practical computational efficiency.
Forward Pass
Backward Pass
Mumory Usage
H2GCN
M2MGNN
$5.2
1187
173.7
MixHop
GАТΙ
185
41.5
BemNett
GAT
10.1
25.0
GCN2
1.3
20.7
23.0
767.0
GONJK
16.0
CPRGNN
3.3
15.4
18.0 ma
507.2 HD
APPNP
GCN
4.8
30.7
15.2
326.3
SGC
8.8
10
100
1.0 Memory Usage
Computation Time Log Scale
Figure 2: memory and runtime analysis across different GNN models for Flickr dataset.
3

---

3 Preliminaries
Let G = (V, be an undirected graph with n = [V] nodes and m = |E] edges. Each node v E V has an associated feature vector x,, E R and we denote the node feature matrix as E Ruxdh, The graph structure is represented by an adjacency matrix A E R=x*, where A. > 0f (i E E, and Asy = otherwise. We primarily consider binary adjacency matrices (A E {0, 1 .......ddy
though our formulation generalizes to weighted graphs. Let D diag(d1, d2,.............. ..., d,) denote the degree matrix of G. where d; = Σ== Aij is the degree of node i. The normalized adjacency matrix with self-loops
defined as À D (A++)L, node classification, only subset of nodes Vz. C V have known labels yr E 21, C),, where C denotes the number of classes. The goal is to predict labels for all unlabeled nodes in V \ Vz.
where I, the n n identity matrix. In semi-supervised
Message Passing and Multi-hop Propagation. GNNs operate on the principle of message passing, where each node iteratively aggregates information from its neighborhood. The neighborhood N(v) of node v is defined as the set of nodes adjacent to e in G, i.c..N()) = {u E V (v, E E}}.
The standard message passing framework be formalized as follows. At each layer I, node updates its representation by aggregating information from its immediate neighbors:
h UPDATE (n. (n!-"), AGGREGATE (nn!-V:uEND))) : (eE(())))))
(1)
where h Rd4 the representation of node at layer I, with h X.. The functions AGGREGATE and UPDATE are typically parameterized by learnable weights and vary across different GNN architectures. matrix form, many GNN layers can be expressed as:
- ( = (AH AAH"-DW(-))
(2)
where H E Raxd is the matrix of node representations at layer / (with H = X), W(-1) e Rd 1xd is learnable weight matrix, is non-linear activation function, and P R= is propagation matrix derived from the graph structure. A is the normalized adjacency matrix A.
The standard message passing paradigm focuses on immediate neighbors (1-hop connectivity), but mopti-hop information is critical in heterophilic settings. We define the p-hop neighborhood of a node v as:
(P = {u E V dist(r, u) pp}
(3)
where dist(v, u) is the length of the shortest path between nodes e and u. By convention, (V {v) (the node itself).
The p-hop connectivity in a graph can be represented by the p-th power of the adjacency matrix, AP. For an unweighted graph, the entry (AP)s counts the number of distinct walks of length p from node i to node j. In particular, (A));; > 0 if and only if there exists at least one walk of length p between i and j. If (AP) Pig > then (")), meaning node is reachable from node via walk of length most p. We adopt the convention that A I,, representing oof-cconectiooss
4 GAMMA: Gated Multi-hop Message Passing
We now introduce the Gated Multi-hop Message Passing (GAMMA) mechanism. GAMMA explicitly addresses a fundamental yet unresolved limitation in current multi-hop GNNs: the inability to adaptively modulate the non non-uniform heterophilic patterns specific to each node when aggregating neighborhood features from multiple hops.
Following prior work I 40), to leverage multi-hop neighborhoods, features from higher powers of the adjacency matrix are explicitly computed. For feature matrix X, the p-hop propagated features can be expressed as A where each row (APX); aggregates information from all nodes exactly p hops away from node i. A multi-hop aggregation scheme formulates node representations by concatenating features processed independently for each hop distance:
(A"XW())
Zeoncat
(4)
p=D

---

bp Inttialized
6 AA
Spuesh
Softmari(
1 hop
hop
hop
ON
$ OH
Class
2 00
Class
Titerations
Class
[a] Input Graph
[b] Vector Space Example
[c] Gated Multi-hop hop Message Passing
Figure 3: Gated Multi-hop Message Passing
where W(P) E IR Xdw is a hop-specific weight matrix, and K the maximum hop distance considered. (Note: The resulting dimension of Zeoneat will be N (K + 1)doa each APX ( is N dout.)
We aim avoid pitfalls associated with naive feature concatenation I 40 37 due to several key concerns. Primarily, feature concatenation can lead to parameter inefficiency and higher risk of overfitting by drastically expanding the feature dimensionality fed into subsequent layers, demanding more data and computational resources than potentially necessary. Secondly, it often introduces significant information redundancy, as concatenated features from different hops might related, forcing the model to expand capacity on disentangling correlated signals rather than learning novel patterns. Crucially, by naively concatenating feature vectors from multiple hops, the complex task of distinguishing interactions and relative contributions among is entirely offloaded downstream general-purper purpose layers (like an MLP). This may be less effective than employing more sophisticated. adaptive fusion mechanisms that explicitly model and exploit these relationships carlier and more directly, ultimately aiming for robust representation learning process.
To overcome these limitations, we adopt inspiration from the observation that Capsule Networks [3 dynamically link spatially local features to global object representations. Specifically, we treat each p-hop aggregation constituent part of the full node embedding. Then, we measure how well each part's embedding aligns (via dot product) with the node's evolving feature (i.e., final representation), thereby adaptively integrating only those hops whose local aggregated features agree with the overall representation.
Formally, let ( from multi-hop propagation, AP. These embeddings first normalized via La-normalization mitigate scale discrepancies among hops:
p-= denote normalized hww.shoecieeeeeeee specific embeddings for node i at hop p. each derived
p= p=0...,,
(5)
These normalized embeddings are then stacked into a unified tensor representation, U, E ((++))x
facilitate subsequent iterative gating computations.
The core of GAMMA is an iterative gating procedure, driven by a of gating logits b, E RRK+ initialized to zero. Each iteration refines these logits, which encode the node's confidence in each hop's contribution its final representation. Specifically, iteration t, we compute a which is the hop-wise gating coefficient for node i through a softmax operation:
cxp(b
a: (t)
softmax (D(²)
0
(6)
Exz exp()
These gating coefficients determine how hop-specific embeddings combined into intermediate representation (*)
8
(8)
(4)
(7)
5

---

To maintain meaningful vector magnitudes and preserve directional information, we employ the squash function
32 to transform sy (1) into a normalized representation v (
|s (
1+ 13
The key improvement that enables distinguishing features from different hops, is the iterative update of gating logits based on the concept of agreement, quantified as the inner product between each hop-specific embedding and the evolving node representation:
(1+1) 6.
H (p)
Intuitively, hops whose embeddings consistently align with the emerging consensus (as represented by ((t) experience increased gating logits and thus higher gating coefficients, reinforcing their influence. Conversely, hops providing contradictory or noisy signals are progressively suppressed. This is illustrated in Fig. b), where the aggregated embedding from the second hop has the strongest
agreement with the target node i (Figure a)). Consequently, the dot product H(()) vv") yields
higher value, which increases the corresponding gating logit (1++1) for the next iteration, thereby intensifying the influence of the second hop's 's features in the final representation.
After R routing iterations, we finalize the node representation: H, = (R) + b, where b E RRd an optional learnable bias. The number of routing iterations is a hyperparameter, with 2 or 3 iterations typically sufficient practice (see Appendix [A].
It is crucial to distinguish between hop-specific feature aggregation and node-specific gating. The initial multi-hop propagation (H (ArXW)) generates hop-specific embeddings that aggregate features globally from all nodes at distance However, the gating mechanism operates node-
specifically: each node i independently computes its routing coefficients ai,p based the
(t)
agreement between its evolving representation v.()) and each hop's embedding H!!") These coef- ficients are unique to each node and recomputed during every forward pass (including inference on unseen graphs), enabling adaptive, castance-driven weighting of multi-hop information without gradient updates. This distinguishes GAMMA from methods like GPR-GNN S where coefficients learned once globally and applied uniformly all nodes.
From a practical computational viewpoint, GAMMA offers substantial benefits over concatenation- based multi-hop methods. Since GAMMA dynamically selects and aggregates hop-specific informa- tion without explicitly expanding the feature space, it significantly reduces memory consumption and computational overhead. Furthermore, by maintaining single shared projection matrix across hops, GAMMA leverages efficient sparse-dense matrix multiplications, substantially improving training scalability and inference efficiency. Moreover, During inference on unseen graph, the routing loop re- computsss the gating coefficients a, from scratch, enabling GAMMA to re-calibrate hop importance for heterophily patterns specific to each node's 's local neighborhood without any gradient updates.
Empirically, the adaptive nature of the GAMMA routing mechanism provides unparalleled flexibility, allowing each node to selectively amplify structurally informative signals from distinct hop distances, based on the nuanced local context. This flexibility not only enhances performance on highly heterophilic datasets but also robustly generalizes across diverse graph structures, significantly outperforming existing multi-hop approaches, demonstrated extensively in our experimental results. For more details about GAMMA and the algorithm pseudocode, refer to Appendix and Algorithm!I
Weight Sharing Across Hops
The iterative gating mechanism in GAMMA compares hop-wise messages with an inner product. Such a comparison is reliable only if all hop embeddings reside in a common and coherent feature space. Using independent, learnable projection matrices for each hop, done in some multi-hop hop architectures M. would map features to potentially unrelated latent spaces, rendering their direct comparison via inner products ill-defined and potentially undermining the gating process.
To address this, GAMMA employs a shared linear transformation for all hop distances. Initial node features X are first projected into common dimennsnnio space using single weight

---

matrix W E Rd Xdu, This projected representation, Hpooj
X W, then serves as the basis for
generating representations for all considered hop distances:
(8) where A = I, (the identity matrix, representing the node's own projected features), and H()) denotes the unscaled features aggregated from the p-hop neighborhood. By utilizing a single W, we ensure that all H(P) are expressed in the same coordinate system, making their subsequent normalization and dot-product- based comparisons in the gating mechanism.
A proj
p= 0. K,
This weight-sharing strategy reduces the number of learnable parameters compared to models that use separate matrices W(r) for each hop. Instead of (K + 1) din x deat parameters for transformations, GAMMA uses only di X dout- This reduction lessens the risk of overfitting, especially in semi- supervised settings with limited labeled data, and contributes to tighter generalization bounds. Also, fewer parameters naturally lead to lower memory requirements for storing the model. Furthermore, computations involving single shared matrix can be more optimized.
While a single shared projection W ensures a consistent feature space, might be too restrictive, lacking the flexibility to emphasize or de-emphasize certain feature dimensions differently for messages originating from various hop distances. To re-introduce a degree hop-specific adaptability without fracturing the shared geometric space, GAMMA incorporates learnable channel-wise scaling factors 7/p E Rd for each hop p. After obtaining the propagated features (z) using the shared projection, each is modulated as follows:
H
(P) scaled
H
Tp.
0, K,
(9)
where @ denotes element-wist wise multiplication. These scaled representations H (P) normalized to produce H for the gating procedure.
scaled are then L2-
This scaling mechanism allows the model to learn the global importance of different feature channels at differ- ent hop distances. For instance, certain features might be highly informative when sourced from 1-hop neighbors but less so from 3-hop neighbors, or vice-versa. The seal- ing factors 7, enable GAMMA to adapt to such patterns. Importantly, since scaling merely stretches or shrinks ex- isting feature dimensions, preserves the integrity of the common coordinate system, ensuring that the inner prod- uets used in the routing stage remain meaningful. The parameter overhead for these scaling factors is minimal, adding only (K + 1) x dout parameters, which is negli- gible compared to using full hop-specific transformation matrices.
hop
hop
Weight Scating
Figure& 4: weight sharing.
However, it is crucial to distinguish the global and local heterophilic patterns in a graph. At the global level, each hop's features are scaled by the learnable channel-wise factors 7/- which adjust the overall importance of information from hop p across the entire graph. In contrast, local adaptation to non-uniform heterophilic patterns relies the coefficients ai.p (softmax over logits b) are not fixed but recomputed iteratively during each forward pass. These logits are updated based on the dot-prod agreement between node i's current embedding and the normalized messages from each hop, yielding per-instance, activation-driven weights. By differentiating global scaling from mode-specific gating. GAMMA can both prioritize broadly informative hop distances and adapt on-the-fly to unseen local heterophily patterns, without relying on static, learned weights for node-sper specciie preferences.
GAMMA' dynamic gating, where each node i,
6 Evaluation
Configuration and setup. We evaluate GAMMA on the semi supisvupe node classification task across a diverse set of benchmark datasets, encompassing both homophilic and heterophilic graphs, with detailed results presented in Table [] Our experiments demonstrate that GAMMA achieves competitive performance across these varied graph structures, showcasing its adaptability. All models were implemented in Python using PyTorch Geometric [7]. Experiments were conducted on
7

---

desktop machine equipped with an NVIDIA RTX A2000 GPU (12GB VRAM) 27 CUDA 12.8
facilitated GPU acceleration and NVIDIA Nsight Compute CLI 28 was employed for profiling and computational performance evaluations such as memory consumptions and runtime.
Baselines. Too benchmark GAMMA, we compare it against a comprehensive suite of baselines representing key strategies in graph representation learning, especially for heterophilic contexts. This selection includes Standard GNNs and Foundational Models (MLP (12). GCN (14). GAT [34]. SGC (36). which serve to ground performance and highlight the challenges heterophily poses to conventional
sessage-passing paradigms. We also incorporate Spectral Graph Filters (GCN- 4. GPRGNN []) BernNet [T],, chosen for their design leveraging graph signal processing to capture the mixed -feeuunny signals often characteristic of heterophilic structures. Furthermore, Methods Utilizing High-Order Neighbors (MixHop (1. H2GCN [40), GCN-JK [37], GAT-JK (37)) are included, as they aim to discover informative, potentially distant, same-class nodes by expanding the receptive field beyond immediate, possibly misleading, connections. Finally, Discriminative Message Passing Techniques (M2MGNN (18) represent approaches that enable more selective and nuanced aggregation from diverse or signed neighborhood information, crucial when local context is not uniformly homophilous. This diverse selection provides robust testbed for evaluating GAMMA's adaptability and effectiveness across the spectrum of graph structures.
Training recipe. For a fair and rigorous comparison of both predictive accuracy and computational demands, all models, including baselines, were configured with consistent architecture: two GNN layers and a fixed hidden dimension size of 32. Hyperparameters for each model were optimized via grid search over learning rates in {0.05, 0.01, 0.002) and dropout rates E {0.0, 0.5). Across all datasets and splits, models were trained for a fixed 500 epochs. We report the test accuracy achieved using the hyperparameter configuration that yielded the highest performance on a held-out validation set for each dataset and model combination.
For robust evaluation, we adhere to standardized data splitting procedures. Specifically, for the heterophilic benchmark datasets, we utilize the 10 fixed train/validationneess splits B1. These splits allocate 50% of nodes for training, 25% for validation, and 25% for testing, reflecting common practice of using a substantial training set for non- -omoophiilluu graph learning evaluations [40] 29]
19 38
For the homophilic datasets, we also employ 10 distinct random splits, following the setup in with 48% of nodes for training, 32% for validation, and 20% for testing. Each model is trained once per split, and we report the mean test performance metrics along with their standard deviations across these 10 splits, consistent with the evaluation methodology in (3T].
Table 1: Node classification accuracy (%) on homophilic and heterophilic benchmarks.
Homophilic Graphs
Heterophilic Graphs
Ciccess
PalMMed
Tosa
Wiscomin
Acsux
Squinel
Chancloon
Coesell
Nodes
2,708
3,327
19.717
183 309
251 499
7,600
5,201
2.277
183
lidges
5,429
4,732
64,318
30,019
217,073
36, 101101
250
Hom,
0.74
0.80
0.11
0,21
0.32
0.22
0.23
0,30
MLP Lb:
76.64 = 1.85
75:00 + 1.48
86, 1::01000 0.50
90.26 4 3.58
64.71
+ 2.31
35
0.87
92.16 +: 1.16
49.75 +
77
5.16
GCN
87.27
1.24
76.00 6 1.13
87.35 0.57
10.25
6 3.21
10.40
=: 6.07
27.38
0.98
25.13
4: 1.25
20.35 2
47.50
7.88
SGC 53
36,91
11.87
03.25:2 2 4.80
76.19
0
54.21 1 4.88
44.01
2: 4.81
26.14:1
3.20
23.66 2: 1.63
26.43 2:
48.36
6.47
OCN 11 13
51.56 = 2.24
74.15 1.81
85. 86
0.47
76.32 1: 8,80
$1.95
2: 3.45
08.18--
1.34
31.86
1: 1.58
40.61 4:
65.26
7.56
GCN JK 13]
S1.10
1.10
09:61
2 1.64
86.04 1 0.63
28.4
1 6.34
42.16
1 6.52
25.54
0.90
22.56
1: 1.12
29.17 1 10300
50.00 8.57
GAT 19
34,33
1.05
11.74 1 1.95
83,55 0.57
41.58 1 5.24
46.07
1 8:00
26.68
0.82
21.07
1: 1.25
36.55
1 2.50
50.53
8.55
HEGCN (0]
57.77
0.55
75.95
1.24
50 01:01-11
01 36
58.38 3.47
55.85 2 6:10
35:30
1.06
35.36
1.39
50.09 11 1.43
18.10 6.97
GAT [4]
85.34
= 0.58
13. 19:11
1.79
87.15
0.54
13.05 1 5.79
14.12.1633
26.36
1.11
25.02
1: 1.35
$1.87 3 2.70
46.05
8.45
Michfop 0
65.50
1.00
11.90-1
1.81
50 00
0.55
$1.21 + 0.6
85.00 5:00
32.70
1.25
31.61 1 4.447
52.
51
01 2.25
76.47
4.71
BernNer [T]
55.331
1.20
76.42
3: 1.57
80.84 1: 0.52
79.47 1 3.00
$1.57 2: 4.31
33.78
1.72
33.43
1: 1.43
40.14
2:
73.56
7.58
GPRGNN 5
.5.772
0.88
75.20:11
1 1.69
88.
0.49
61.5 1 8.66
78.24
11 3:00
35.62
0.02
25.29
1: 1.25
34.03
21
2.34
02.37
5.77
MZMGNN
[8]
53.65
1.58
70.70
2.47
88.
02 0.06
S1.47
1 4.77
87.00
3 2.00
33.50
1.14
33.89
1 4.01
58.
11
11
3.14
76.54
4.52
GAMMA
87.42
3 1.00
75.29
8 1.67
89
02
0.43
87.37
8 3.08
86.27
31 21
35.50
1.29
36
20
1.01
51.16
3. 2
08
3:42
Note: Values are colored according their ranking: best in green, second-best in bluc. and third-bost in red.
Performance on Homophilic Benchmarks. On standard homophilic benchmarks, GAMMA demonstrates consistently strong and competitive performance, validating its robustness even when the homophily assumption largely holds. As shown in Table [ on PubMed, GAMMA achieves the best accuracy among all compared methods with 89.62 + 0.43%. For Cora, GAMMA obtains 87.42 + 1.01%, performing comparably to GPRGNN (87.72 + 0.8%% and H2GCN (87.75 + 0.88%). These results indicate that GAMMA's adaptive multi-hop gating mechanism does not impede its ability to leverage strong homophilous signals, maintaining high efficacy on datasets where traditional GNNs typically excel.
Performance on Heterophilic Benchmarks. GAMMA showcases its strength and adaptability on the more challenging heterophilic datasets. Across the six heterophilic benchmarks, GAMMA consistently ranks among the top-performing models, outperforming many specialized heterophilic
8

---

GNNs and standard GNNs, which often struggle in these settings. Specifically, GAMMA achieves the best performance on three of the six heterophilic datasets. On Texas, it surpasses H2GCN and M2MGNN. On the Actor dataset, GAMMA leads with 35.59 + 1. 1.29%. ahead of MLP and H2GCN and on Cornell, GAMMA again achieves the top accuracy of 78.68 + 3.42%, outperforming H2GCN and MLP. On the remaining heterophilic datasets, GAMMA also demonstrates robust and highly competitive results. For Wisconsin GAMMA appears as the second-best closely following M2MGNN (87.06 + 2.00%) and outperforming several other specialized methods like H2GCN and MixHop.
These strong performances across datasets with varying low homophily ratios (from 0.11 1 for Texas to 0.30 for Coreell.. The results suggest that GAMMA's node-specific adaptive gating of multi-hop in- formation is particularly beneficial for navigating the complex neighborhood structures characteristic of heterophilic graphs, allowing it to match or exceed the performance of methods that rely on fixed higher-order aggregations (MixHop) or more complex titerophily-specifn designs (BernNet and M2MGNN). The competitive results on both homophilic and heterophilic graphs strongly support GAMMA's design as a homophily-aggostic GNN.
To address scalability concerns and demon- strate GAMMA's effectiveness on larger graphs, we evaluate our method on seven large heterophilic benchmarks. Table 2 Notably, many toite-of-thhaaae art methods encounter Out- Of-Memory (OOM) errors even on an NVIDIA A100 GPU with 80GB VRAM, particularly on ogbn-prooe products (2.4M nodes, 61M edges), due to architectural choices such as feature concatenation (H2GCN, MixHop. JK-Nets) or complex per-edge operations (M2MGNN) that create prohibitively large intermediate tensors. GAMMA addresses these limitations through its weight-sharing strategy and dynamic gating mechanism, enabling it to scale effectively while maintaining competitive accuracy. GAMMA achieves state-of-the-ary or highly competitive performance on 6 out 7 large-scale datasets, demonstrating that efficient architectural design does not compromise effectiveness. Across the complete benchmark suite of 16 datasets spanning both small and large-scale graphs, GAMMA achieves the best overall performance with an average rank of 2.06, compared to H2GCN (3.71) and MixHop (3.87), confirming its effectiveness and scalability for heterophilic graph learning.
Performance on Larger Heterophilic Benchmarks.
presents results on datasets ranging from tens of thousands to millions of nodes.
Table 2: Node classification accuracy (%) on large heterophilic benchmarks. OOM indicates Out-Of- Memory errors.
egbn-arxiv
roman-empire
ogbn-products
minesweeper
amazzo-ratings
amizon-photos
tolokers
Nodes # Edges
169.343
22,662 32,927
2,449.029
10,000
24,492
7,650
11,758
1,166,243
61,859,140
39.402
186, 100
238,162
519,000
MLP
65.37
0.58
43,20 0.01
79.45
38.35 0.22
18.73
1.80
0.300
GCN
[4
61.91 + 0.26
51.16 :: 0.28
71.31 = 0.16
80.31 = 0.21
12.12 0.29
52.14
1 1.50
78. 76
0.17
SGC
63.47 1 0.16
61.20 0.65
0OM
80.05
0.033
41.61
0.72
57.97
0.52
78.56
0.19
GCN-11
61.96=. - 0.12
61.9 0.38
61.08 = 0.18
82.80 = 0.35
17.20 0.35
91.10
0.25
79.80 20.00:200 0.30
GCN JK S7
70.19 1 0.11
62.18 1. 0.91
69.46 1: 0.33
85.15 1 0.42
0.37 48.77
95.28
0.05
81.23
0.26
GAT-JK
OOM
H2GGN 40
00M
75.89 1: 0.55
0OM
83.11 1: 0.65
42.90 0.38
54.95 0.38
79.39 0.42
GAT 34
70:01 + 0.00
74.50 + 0.45
00M
81.52 +: 0.26
48.80 0.61
96.56 0.15
78.63
0.06
MixHop 0
70.27
$2,20 0.31
0OM
84.58 0.45
50.98
0.30
96.34
81.03
BernNet
[
63.15 : 0.13
66,27
+: 0.35
00M
80.00 - 0.07
40.90 2: 0.09
62.34 +: 7.02
78. 16 0.00
GPRGNN
87.66 0.07
60.60 0.40
73.26 4 0.65
80.36 + 0.19
43.44 4- 0.13
79.54 0.39
78.36 0.10
M2MGNN [8]
72.52 4: 0.10
80.81
de 0.70
0OM
85.83 = 0.25
50.57
0.29
95.73
0.25
80. 00.66- 0:47
GAMMA
71.81 4: 0.19
81.37
0.25
72:61 # 0.04
87.58 0.2.55
49.07 +: 0.65
96.22 0.13
82 59 +:
Note: Values are colored according to their ranking: best in green, second best in blue, and third best in red.
Computational efficiency. Beyond predictive accuracy, the practical utility of a GNN model heavily depends on its computational efficiency, encompassing both execution latency and memory footprint. We benchmarked GAMMA against various basclines. measuring forward pass time, backward pass time, and total GPU memory usage on the Flickr dataset. The results, shown on the right-hand side of Fig. 5 underscore GAMMA's efficiency profile. GAMMA operates with total execution time (backward + forward pass) of 23.17 ms and memory footprint of 480.60 MB. This latency is competitive with the simplest architectures such as GCN, which records 15.24 ms, and GPRGNN at 18.75 ms. Critically, GAMMA demonstrates substantial speedups over several complex models: it runs approximately 20x faster than H2GCN, over 7.4x faster than M2MGNN, and nearly 5x faster than MixHop. In terms of memory, GAMMA's 180.60 MB usage is significantly efficient, consuming approximately 12.1 x less memory than M2MGNN, over x less than GATJK, and about 4. less than H2GCN (1993.90 MB).
9

---

Publied
Pornard Fisss
Forward
GAMNA Beckward
Baconard Pass
Fameryy Usage Humrer
Flidr
Forward
GAMMA forward
GANHA Bachoourd
Backnurd Nass
Menory Usage
CAMMA Meroary
Bember
67.3
cat PM
R20C4
145.1
M29GAN
18.
23.
M24NN
172.7.04
Nishop
83
15.8
17.3
NiHoop
11.5
133 oe
CAT-JK
122
16:1 64
155
CAT-JK
16.3
1033
GPMCNN
16:2
13370
100
BerNec:
L6.3
2001
14.3
5086
GAT
1/6
113
16:386
GAT
16.1
15:01|
H2GCN
15.7
160
1814 PM
GCN-1
18:0
107,5:0
GAMMA
113
223
GCNJK
18:00
25.7
502.390 PM
GCK-1
113
15:5
GAMMA
3.9
17.3
23.2
4604-0
GONJKK
1.1
64
105,00
GPRCNN
23
15.1
20.8
547.3
GCN
17
23
$7. Mg
GCN
45
10.30
15:2
200
1.0
10.0
300
Comcutation Time (Log Scale]
Nemory Usage
Compotation Time- Liww-oog Log Scale
Hersony Userge
Figure 5: GAMMA efficiency comparison across various GNNs on Flickr and PubMed datasets.
GAMMA's computational efficiency, despite its capacity for adaptive multi-hop information pro- cessing, stems from several core architectural decisions. Firstly, the shared linear transformation applied once to input features (X ensures parameter efficiency for the primary feature projection, as discussed in Section 5 Subsequent multi-hop hhop propagations (A (X (XW)) operate on these already transformed, fixed-dimension features. This is a key distinction from models like MixHop, which larger feature
concatenates outputs from different powers of the adjacency matrix, leading dimension for subsequent layers and higher parameter counts as distinct transformations were applied per hop. Secondly, GAMMA avoids explicit feature concatenation for integrating multi-hop information. Many multi-hop architectures, such as H2GCN (which concatenates features from 1-hop and 2-hop paths, and across iterations) and MixHop, expand the feature dimensionality before which in turn requires larger memory transactions. This increase in output feature dimension directly results in larger intermediate tensors and more expensive matrix operations. In contrast, GAMMA's gating mechanism computes a weighted sum of hop-specific embeddings and merges them into unified output vector, each preserving the target output feature dimension, thus avoiding heavy memory and computational requirements.
The lightweight iterative gating mechanism further contributes GAMMA'S efficiency. Each iteration of the gating mechanism involves GPU friendly and highly parallel operations like softmax, weise products, and sums primarily on tensors of shape [#Nodes, #hops]. with low number of iterations (empirically to 3). These operations are computationally less demanding than, for example, the per-edge multi-layer perceptron and segmented softmax operations within M2MGNN's layers, or the per-edge attention coefficient calculations in GAT and its variants. While GAMMA computes embeddings from multiple hops using standard message passing, the subsequent aggregation via gating is more efficient than learning complex, global filter coefficients for each feature as in some spectral methods like BernNet, which involves K propagation steps for its polynomial filters, or handling large feature dimensions. Consequently, GAMMA offers compelling balance between accuracy across diverse graphs and the practical computational efficiency required for real-world heterophilic datasets.
7 Conclusion
In this paper, we introduced GAMMA, a homophily-agnostic GNN architecture that effectively handles the non-uniform heterophilic patterns prevalent in real-world graphs. By employing lightweight iterative gating mechanism and an efficient weight-sharing scheme, GAMMA adaptively leverages multi-hop neighborhood information based node-specific structural patterns. Our experiments across diverse benchmarks demonstrate that GAMMA matches or exceeds state-of-the- art accuracy while achieving up to 20x faster inference and substantially lower memory consumption, making heterophilic graph learning practical on commodity hardware. Despite these advances, limitations remain for future exploration. GAMMA's current fixed routing iteration count may be suboptimal for nodes with varying neighborhood complexities, and extremely large graphs the gating mechanism. Additionally, while our dot-product
may require further optimizations agreement measure works well in practice, more sophisticated routing strategies might better capture particularly complex heterophilic relationships. Nevertheless, GAMMA challenges the assumption that handling heterophily necessitates complex architectures, providing practical solution that balances adaptability, performance, and computational efficiency for diverse graph learning tasks.
Acknowledgements
This work was partially supported by DARPA under Cooperative Agreement FA8750-23-2-0577 the U.S. Department of Energy under grant DF-SC0022428, and the U.S. National Science Foundation under CAREER Award CCF-2441973.
10

---

References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyun- yan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architcctures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR. 2019.
[2] Arash Ashari, Shirish Tatikonda, Matthias Boehm, Berthold Reinwald, Keith Camphell, John Keenleyside, and Sadayappan. On optimizing machine learning workloads via kernel fusion. ACM SIGPLAN Notices, 50(8):173-182, 2015.
[3] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-free oow-rreueency information graph convolutional networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 3950-3957, 2021.
[4] Ming Chen, Zhewei Wei, Zengfeng Huang. Bolin Ding, and Yaliang Li. Simple and deep graph convolu- tional networks. In International conference on machine learning, pages 1725-1735. PMLR, 2020.
[5] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint ar0iv: 07990, 2020.
[6] Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng. Hao Peng. and Philip S Yu. Enhancing graph neu- ral network-based fraud detectors against camouflaged fraudsters. In Proceedings of the 29th ACM international conference on information & knowledge management, pages 315-324, 2020.
[7] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In arXiv preprint arXiv:1903.02444 024428 2019. doi: 10.48550/arXiv.1000 19t..ii.......222.....
[8] Ben Finkelshtein, Xingyue Huang, Michael Bronstein, and Ismail Ilkan Ceylan. Cooperative graph neural networks. arXiv preprint 11Xiv22310001267, 2023.
[9] Chen Gao, Yu Zheng, Nian Li, Yinfeng Li, Yingrong Qin, Jinghua Piao, Yuhan Quan. Jianxin Chang. Depeng Jin, Xiangnan He, et al. A survey of graph neural networks for recommender systems: Challenges, methods, and directions. ACM Transactions on Recommender Systems, 1(1):1-51, 2023.
[10] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[11] Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 14:14999-14 2021.
[12] Yang Hu, Нaoxuan You, Zhecan Wang. Zhicheng Wang. Erjin Zhou, and Yue Gao. Graph-mlp: Node classification without message passing in graph. arXiv preprint arXiv:2106.0405), 2021.
[13] Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM international conference on web search and data mining, pages 146-155. 2021.
[14] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609.02907 2016.
[15] Ronny Krashinsky, Olivier Giroux, Stephen Jones, Nick Stam, and Sridhar Ramaswamy, Nvidia ampere architecture de-te.th. NVIDIA Technical Blog. May 2020. URL URL blog/nvidisg ampere- wwwhitectureeec..o. in- / Accessed: 3025-10-22
wwwpeeoooer..iiiiiiieeeeee nvidia. com/
[16] Rui Li, Xin Yuan, Mohsen Radfar, Peter Marendy, Wei Ni, Terrence O' O'Brien, and Pablo Casillas- Espinosa. Graph signal processing, graph neural network and graph learning on biological data: a systematic review. IEEE Reviews in Biomedical Engineering, 16:109 100,-115,5000 2021.
[17] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning, pages 13242-13256 PMLR, 2022.
[18] Langzhang Liang, Sunwoo Kim, Kijung Shin, Zenglin Xu, Shirui Pan, and Yuan Qi. Sign is not a remedy: Multiset-to-mullee message passing for learning on heterophilic graphs. arXiv preprint 2405524005 2024.
[19] Derek Lim, Felix Hohne, Xiuyu Li. Sijia Linda Huang. Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non non- homophilous graphs: New benchmarks and strong simple methods. Advances in neural information processing systems, 34:20887- 20902, 2021.
11

---

[20] Meng Liu,, Zhengyang Wang. and Shuiwang Ji. Non-local graph neural networks. IEEE transactions on pattern amalysis and machine intelligence, 44(12):00770100276, 2021.
[21] Renming Liu and Arjun Krishnan. Open biomedical network benchmark: A python toolkit for benchmark- ing datasets with biomedical networks. In Proceedings of the 18th Machine Learning in Computational Biology meeting, pages 23-59, 2024.
[22] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wor Wen Chang. and Doina Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35:1362-1333 13752117..222 2022.
[23] Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. Demystifying structural disparity in graph neural networks: Can one size fit all? Advances in neural information processing systems, 16:37013-37065 2023.
[24] Xinxin Mei and Xiaowen Chu. Dissecting gpu memory hicrarchy through microhenchmarking. IEFE Transactions on Parallel and Distributed Systems, 28( (8())722866 2016.
[25] Hoang Nt and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters, arXiv preprint 09550, 2019.
[26] NVIDIA Corporation. Nvidia a100 tensor core gpu architecture. Technical report, NVIDIA Cor- poration, 2020. URL https::/immaaee mvidia. com/aem. dam/ /en-z:/Soluiions/teee center/
aawaaaa-aarr----ccttttatee whiteppper.... pdf Architecture Whitepaper.
[27] NVIDIA Corporation. NVIDIA R7X A2000 12 GB Datasheet, May 2022.
URL https
7/www. www...viiia.co wwwp///oneeee//t/mmmnn--e/eeeeea 2ttp://mmeem////////ii/ooeooaoe Swtp://oootoon///ooooooooooo //tp://wwwwaaaaccccc/c//////////
ietiiiaatin/rttte /tt//ttx---/ a2000/
avidia-rtz- htw.::/ee222000---aataataaaa----
Published May 2022; accessed May 2025.
[28] NVIDIA Corporation. NVIDIA Nsight Compute CLI (122025.2) User Guide, 2025. URL https://doca
hvidia.com waapl/aa.coomnssggccoooppouuu/ee h/tp:////e///sstttaaaooooooa/eee html Version 2025.2 2,5.2.00 accessed May
2025.
[29] Hongbin Pei. Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287. 2020.
[30] Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Characterizing graph datasets for node classification: Homophily-heteraphii dichotomy and beyond. Advances in Neural Information Processing Systems, 36:523-548, 2023.
[31] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint arXiv:2302. 1640, 2023.
[32] Sara Sabour, Nicholas Frosst, and Geoffrey Hinton. Dynamic routing between capsules. Advances in neural information processing systems, 30, 2017.
[33] Petar Veličković. Message passing all the way up. arXiv preprint arXiv:2202. / 2022.
[34] Petar Velickovie, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, Yoshua Bengio, Graph attention networks. stat, (550(20):00488555 2017.
[35] Samuel Williams, Andrew Waterman, and David Patterson. Roofline: insightful visual performance model for multicore architectures. Communications of the ACM, 52(4))65-76, 2009.
[36] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. Pmir, 2019.
[37] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pages 5453 5462. PMLR, 2018.
[38] Yujun Yan, Milad Hashemi, Kevin Swersky. Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), pages 1287-1292. IEEE, 2022.
[39] Xin Zheng, Yi Wang, Yixin Liu, Ming Li, Miao Zhang, Di Jin Philip S Yu, and Shirui Pan. Graph neural networks for graphs with heterophily: A survey, arXiv preprint arXiv:2202.00 07082, 2022.
12

---

[40] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances neural information processing systems, 33:7793-7804, 2020.
[41] Jiong Zhu, Ryan A Rossi, Anup Rao. Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference on artificial intelligence. volume 35, pages 11168-11 11176, 2021.
13

---

Appendix
A
Ablation Study on Number of Routing Iterations in the Gating Mechanism
15
B Impact of Dynamic Gating Mechanism Through Empirical Study
16
C
GAMMA Pseudocode and Implementation Details
16
Related Work
Supplementary Theoretical Analysis
20
E.1
Preliminaries and Notation
E.2
Detailed Convergence Analysis
E.3
Information-Theordde Optimality
29
E.4
Functional Expressivity
E.5
Universal Approximation
F
On the Hardware Efficiency of GAMMA
36
F.
The Memory Wall in GPU-Accelerated Graph Learning
37
F.2
Architectural Inefficiencies in Multi-Hop Heterophilic GNNs
38
F3
GAMMA's Architectural Co-Design for Hardware Efficiency
39
F.4
Theoretical Memory Bandwidth Bounds
F.5
Empirical Validation and Architectural Insights
14

---

Iteration
10
Cora
+1.31
87.09
+101
87.
+1.01
+118
04
+1m
+1
+1.00
80
CiteSeer
75.16
74.74
75,01
75.02
74,93
74.99
75,05
74,96
75.05
75,05
10
70
PubMed
89.09
89.20
09.09
40.25
+1.34
+127
+0.32
+1.20
+122
+2.33
+0.66
+0.36
5
10
-60
Chameleon
48.82
48
.89
47.79
46,80
46.64
10:44
+7
Accuracy (%)
50
Cornell
77-11
79.47
79.21
78 42
79.47
70
78.16
78.95
80.00
75.79
20100
40
Wisconsin
53.53
+1.0
+155
+1.0
20.20
+131
+327
+1.5
10
Texas
57.09
82.37
+641
-117
84.21
$3.95
.2
81.58
+1
20
Squirrel
33.79
34,27
34.97
34.15
34.37
34.18
33.55
34,38
33.17
33:45
-10
Actor
-1.04
34.83 -1.90
34.84
-156
34.88
-084
35.48
35.66 -1
+1
+0.0
+491
+1
Accuracy
Figure 6: Iterative gating mechanism performance with different number of iterations
A Ablation Study on Number of Routing Ittrationn in the Gating Mechanism
To understand the impact of the iterative refinement process within the GAMMA layer, we conduct an ablation study on the number of iterations (R in Algorithm|] [ line 10). This parameter controls how many times each node refines its assessment of the relevance of aggregated information from its k-hop neighbors by updating the gating logits b based on the agreement between hop-specific embeddings and the evolving node representation v. We vary number of iterations from to 10 and report the mean accuracy and standard deviation over 10 splits for each dataset. The detailed results of this study are presented in Fig. [ allowing us to observe how the performance of GAMMA changes as nodes are given more steps to dynamically determine the optimal mix of multi-hop information.
On the homophilic datasets (Cora, CiteSeer, and PubMed), the performance of GAMMA demonstrates a general trend of either peaking or stabilizing with a relatively small number of routing iterations. For instance, on Cora, accuracy improves from 87.02 at iteration to a peak of 87.13 at 5 iterations, after which it sees marginal decline. PubMed also shows robustness, with performance quickly reaching near-optimal levels (e.g., 89.20 at 2 iterations and 89.21 at 10 iterations), indicating that a few iterations are sufficient establish effective routing coefficients. CiteSeer exhibits slight fluctuations but generally performs well across different iteration counts, achieving 75.16 at 1 iteration and 75.05 10 iterations. This suggests that for graphs where homophily is prevalent, the initial agreement scores are often strong, and the iterative process rapidly converges to an effective combination of hop information, primarily leveraging local neighborhood signals. While additional iterations do not significantly degrade performance, they offer diminishing returns, implying that the model quickly identifies the most relevant, often nearby, hops.
In contrast, the behavior on heterophilic datasets is more varied, underscoring the diverse nature of information distribution in such graphs. Some heterophilic datasets like Chameleon and Wisconsin achieve their peak performance with very few iterations (Chameleon: 48.82 at 2 iterations; Wisconsin: 86.67 at iterations), with performance tending decrease with more iterations. This pattern suggests that for these specific graphs, the initial routing based on agreement quickly identifies the most discriminative hop information, and further iterations might risk incorporating noisy or less relevant signals from more distant or dissimilar neighborhoods. However, other heterophilic datasets such as Actor and Cornell benefit from a greater number of iterations. Actor's 's accuracy gradually increases, peaking at 36.09 with 7 iterations, while Coreell peaks at 80.78 79 with 6 iterations. This
15

---

indicates that for these graphs, the iterative refinement process is crucial for dynamically adjusting the weights of different k-hop neighborhoods. allowing the model to progressively focus on more informative, potentially non-obvious, hop distances that are critical for capturing heterophilic patterns. The optimal number of iterations thus appears to be dataset-dependent, reflecting the unique structural characteristics and the complexity of heterophily within each graph.
B Impact of Dynamic Gating Mechanism Through Empirical Study
To demonstrate the contribution of GAMMA's node-specific dynamic gating mechanism, we conduct an ablation study comparing two configurations: (1) Without Gating: uniform hop weights for all nodes (i.e., Oi,p equal across all hops p for each node i), while retaining the learnable channel- wise scaling factors Yyp that operate globally, and (2) With Gating: GAMMA's full iterative gating mechanism that adaptively computes node-specific hop coefficients 0t based on agreement scores.
Table presents results six heterophilic datasets aggregating information from different hop combinations. The results demonstrate that dynamic gating consistently outperforms uniform hop weighting across all datasets, with improvements ranging from 2-8% depending on the dataset. These gains stem from GAMMA's ability to adaptively capture node-specific multi-hop homophily patterns.
Table 3: Ablation study: Impact of gating mechanism node classification accuracy (%).
Cornell
Texas
Wisconsin
Chameleon
Actor
Squirrd
Hop Config:
Wlo
With
Wio
With
Wio
With
4
Wlo
With
Wil
With
W/o
With
4
1:2 hop
15.31
78.88
+3.37
83.25
87.37
+4.12
81.40
86.27
+4.87
44.79
51.16
+6.37
30.72
35.59
+4.7
28.33
36.20
+7.87
1:3 hop
73.51
77.01
+3.00
82.57
86.47
+3.00
79.02
$4.12
+5.10
42.29
$1.14
+8.85
30.29
36.06
+5.77
29.28
35.43
+6.15
1-4 hop
75.99
79.21
+3.22
81.86
86.21
+4.35
80006
$4.71
+4.65
42.40
50.87
+8.47
27.25
34.90
+7.65
27.42
35.52
+8.10
Note: "Wlo"= without dynamic gating (uniform hop weights with global scaling %, "With" = GAMMA's full dynamic gating. A shows improvement from adding dynamic galing.
Why Dynamic Gating Matters. As demonstrated in Section 2 heterophily varies both across nodes and hop distances. For instance, in the Chameleon dataset, we observe dramatically different multi-hop homophily patterns across nodes. Chameleon exhibits only 20.7% pattern consistency, meaning just 20.7% of nodes share similar multi-hop homophily trajectories, while most show diverse, complex patterns. This explains why Chameleon sees the largest performance gains (6-7%) from dynamic gating. In contrast, Cornell displays 65.3% pattern dominance, where the majority of nodes share similar multi-hop homophily, resulting in smaller but still meaningful improvements (2-3%).
Unlike methods with global coefficients (e.g., GPR-GNN), GAMMA's dynamic gating operates at both training and inference time. During inference, the routing loop recomputes gating coefficients Oi.p from scratch for each node, enabling GAMMA to adapt to unseen heterophily patterns in the local neighborhood without any gradient updates This architectural design separates global pattern learning (via 7 learned during training) from local pattern identification (via dynamic at.p computed during each forward pass).
C GAMMA Pseudocode and Implementation Details
Algorithm Explanation and GPU-Efficient Computation. Algorithm 1 provides a concise overview of the forward pass in GAMMA layer. In Lines 1-4, perform a single shared linear transformation on the imput X and then apply K-hop propagations via standard sparse-dense matrix multiplication (spmm), which is highly optimized for modern GPUs. Unlike multi-hop meth- ods relying on explicit feature concatenation, GAMMA keeps each hop representation ((P) in the same output dimension dant and scales it channel-wise in Lines 6-7. This uniform dimensionality avoids blowing up tensor shapes in memory and reduces the number of large intermediate operations typically seen in concatenation-base
schemes (e.g.. MixHop).
Within each node's local routing loop (Lines 10-17), the dot products in Line 12 act similarity measure between node's evolving summary vector v, and each normalized hop embedding H!!) These dot products are very lightweight on a GPU, as they operate on small vectors with shape [dam] and then update a softmax distribution of size K+1. Importantly, these per-node operations can be mapped to GPU kernels that rely on fully on-chip memory, climinating large-scale memory
16

---

Algorithm 1 GAMMA Layer Forward Pass
Require: Node features X R adjacency matrix A R powers K, routing iterations R. scaling YK, weight matrix W ddur, bias b E Rdon Rexdd
parameters Yo..... Yk,
Ensure: Node representations
I: H + XW
> Shared lincar transformation D O-hop representation is the node's 's own features
2: H <- H
3: forp= to K do
4: H + ()
> p-hop propagation via sparse-dense matmul
5: for 0 K do
6:
((P) H の T
Apply hop-specific scaling Node-wise L2 normalization
7:
H(() < normalize H())
8: for each i do
b, < RK-1
Initialize gating logits
10:
for = R do
11:
a, + softmax b.)
D Compute gating coefficients
12:
Epn Ct.p H.!))
Weighted of hop representations Apply "squash" for normalization
13:
V. (s.
14:
for p- t do
15:
bi. big H.
Logit update via dot product (agreement)
16:
V1 bb
Optional bias for final representation b Output node representations
17:
return V = (vihiev
transactions. By contrast, concatenation-base methods generate large expanded embeddings (often dimension +1) dow), which can lead to memory- bound kernels and slower performance.
Note that in Lines 1-7, first apply the shared linear transformation H XW, then iteratively compute p-hop embeddings by multiplying from right to left:
(P)) ( + H(P) = AP (XW).
(10)
This step-by-step approach avoids explicitly forming A at once and reduces repeated large-scale multiplications. After channel-wise scaling and normalization (Lines 6-7), each node's per-hop features remain in dimension drar, rather than expanding to (K + dout in feature concatenation.
Within the routing loop (Lines 10-16), the dot products in Line 12 act as a localized "agreement" between node's 's evolving representation and each hop's 's normalized embedding. These computations are inexpensive on GPUs, as each node handles only small diuediinnio vectors. Crucially, by maintaining a single vector per node and updating logits b, in place, we avoid memory-bounn concatenations. Consequently, relevant hop data remain on-chip, allowing the algorithm to leverage GPU-friendly sparse-dense kernels efficiently. This design leads to less overhead and lower peak memory usage, as observed empirically Section 6
D Related Work
The foundational success of early Graph Neural Networks (GNNs), such as Graph Convolutional Net- works (GCN) 14 and Graph Attention Networks (GAT) (34), has been predominantly demonstrated on homophilic graphs, where connected nodes tend to share similar features and labels. Their inherent message-passing mechanisms act as low-pass filters, effectively smoothing representations within local neighborhoods, which is beneficial under homophily 25 However, this very property leads to suboptimal performance on heterophilic graphs, where adjacent nodes often belong to different classes [40] 39]. This discrepancy has catalyzed significant body of research focused on developing GNNs tailored for, or robust to, hetcrophily. These approaches can be broadly categorized.
Standard GNNs and Foundational Models. Beyond GCN and GAT, other foundational models highlight the challenges of heterophily. Simplified Graph Convolutions (SGC) [36] streamline GCN by removing non-linearities and collapsing multiple layers into a single linear transformation. While exceptionally efficient due to its pre-computation of K-hop features, SGC's aggressive smoothing makes it highly susceptible to performance degradation on heterophilic graphs where dissimilar neighbors are prevalent. Interestingly, Multilayer Perceptrons (MLP) 12]. which entirely disregard
17

---

graph structure and operate solely on node features, sometimes surprisingly outperform standard GNNs on highly heterophilic datasets (see Table 1). This phenomenon underscores the detrimental effect of inappropriate message passing in heterophilic settings, where aggregating from misleading local connections can be worse than ignoring them altogether. While these models offer high computational efficiency, their inherent homophily bias or complete disregard for structure makes them ill-suited for effectively leveraging the complex relational information in heterophilic graphs.
Extending Receptive Fields: Multi-hop and Jumping Knowledge Architectures. Recognizing that informative similar-class nodes in heterophilic graphs might reside beyond immediate neigh- borhoods, several methods explicitly incorporate multi-hop information. MixHop ① enables GNN layers to learn from linear combinations of feature representations from neighbors at various hop distances (k=0,1,2.....) ) by repeatedly multiplying features with powers of the (normalized) adjacency matrix and concatenating their transformed versions. This allows the model to directly access infor- mation from different neighborhood ranges. While MixHop demonstrates the utility of multi-hop features for heterophily. it relies on feature concatenation. This strategy leads to linear increase in feature dimensionality and parameters with the number of hops considered, significantly increasing computational and memory costs, shown in our analysis (Figure 2). Furthermore, the mixing of hop information in MixHop is typically global, not adapted per node, limiting its ability to capture node-specific heterophily patterns.
Jumping Knowledge Networks (JK-Nets) 37 applicable to models like GCN-JK and GAT-JK, offer more flexible approach to leverage multi-scale information. JK-Nets aggregate representations from all previous layers (effectively different neighborhood radii) for each node at the final layer, using mechanisms like concatenation, max-pooling, or LSTM-attention to combine them. This allows nodes to adaptively select the relevant neighborhood range. However, the selection mechanism in JK-Nets is primarily focused on the depth of the GNN, and it allows differential influence of k-hop information. The combination strategy, while adaptive, might still mix features from different semantic spaces if distinct transformations used per layer before aggregation, potentially leading to information redundancy or dilution.
specifically targets heterophily by incorporating three key design principles: (i) sepa- rating the representation of the ego-node from its aggregated neighbors to prevent feature dilution, (ii) explicitly including 2-hop neighbors to reach potentially more similar nodes, and (iii) com- bining intermediate representations from different layers to preserve a spectrum of neighborhood information. H2GCN's 's strength lies in its tailored design for heterophily. showing strong empirical results. However, its architecture is somewhat manually crafted with a fixed inclusion of specific hop distances (I (I-hop and 2-hop). and the concatenation of features from these hops and across layers leads to substantial increases in memory usage and computational load. Our analysis (Figure 2 in the main paper) shows H2GCN consuming over 6x more GPU memory and incurring 33x increase in execution time compared to vanilla GCN, making it computationally prohibitive for many real-world applications.
H2GCN 40
These methods underscore the importance of higher-order neighborhoods for heterophily. However, they often involve either fixed schemes for incorporating multi-hop data strategies that can significantly increase model parameters and computational demands.
Spectral Approaches and Graph Filtering. Another line of work draws inspiration from graph signal processing, designing spectral filters to capture varying frequencies of graph signals, which is pertinent for heterophily where both high and low-frequency information can be crucial. GPR-GN 5 learns a set of weights for a linear combination of propagated feature matrices, where each matrix corresponds to a different power of generalized propagation matrix (c.g., normalized adjacency matrix). This allows the model to learn an optimal polynomial filter for the task and graph at hand. While GPR-GNN adaptively learns the filter coefficients, these coefficients are global for the entire graph, meaning the spectral response is not tailored to individual nodes or local structures. This global learning can limit its effectiveness on graphs exhibiting diverse local homophily/heterophily patterns.
BernNet [ employs Bernstein polynomial filters, which offer a more stable way to approximate desired spectral filters. By adjusting the coefficients of the Bernstein basis polynomials, BernNet can shape the filter response to capture complex patterns. Similar to GPR-GNN, BernNet learns global filter coefficients. Its K-th order filter necessitates K separate sparse-dense multiplications,
18

---

each incurring its own kernel overhead and intermediate storage, making it computationally intensive despite its expressive power (Figure 2).
GCNII [4] addresses the oversmoothing problem in deep GCNs by incorporating an initial residual connection and identity mapping in each layer. This allows GCNII build deeper models that can potentially capture longer-range dependencies without performance degradation. While GCNII improves information propagation in deep GNNs, its core message passing still relies on the standard GCN aggregation, which is primarily homophily-oriented and doesn't It specifically address heterophilic aggregation challenges beyond enabling greater depth. Overall, Spectral methods provide a principled way to combine multi-hop information. However, their reliance on globally learned filters often means they may not offer the fine- ane-grained, node-level adaptivity required for graphs patterns.
graphs with
diverse local homophily/heterophhi
Addressing Heterophily via Signed or Adaptive Message Aggregation. Some approaches aim to differentiate how messages from neighbors are aggregated, sometimes allowing for "negative" influences or class-aware aggregation. The concept of Signed Message Passing (SMP) B3 38 allows
GNNs to assign negative weights message passing, enabling the model to distinguish between features from same-class and different-class neighbors. This allows the model to attract similar neighbors and repel dissimilar ones. However, Liang et al. [88 identified that naive SMP can suffer from undesirable multi-hop effects (e.g., when combining individually appropriate one-hop propagation matrices) and vulnerability to oversmoothing in multi-class settings as mean embeddings of different classes converge exponentially.
M2M-GNN Pialtiieetto-Muuliise GNN) [8] was proposed to overcome these limitations. replaces the standard muultiset-t-ellmenn aggregation with multiset-to-muule approach. An attention mechanism assigns neighbors into different "chunks" (ideally corresponding to different classes), and then class-specific information is pooled from these chunks. This helps maintain the segregation of information from potentially different classes. While M2M-GNN effectively segregates information, it typically uses fixed combination strategy (e.g., concatenation) for the resulting chunk vectors, which may not optimally integrate the segregated information. Moreover, M2M-GNN can be computationally intensive due to its per-edge MLP and segmented softmax operations, which cannot be cast as one large -mtrix multiply, leading to numerous small kernel launches and frequent intermediate result synchronization (Figure 2).
tackles heterophily by first estimating initial class probabilities for each node. It then propagates these "soft labels" or priors across the graph, weighted by a trainable compatibility matrix that encodes the likelihood of different classes being adjacent. This allows message passing to be guided by estimated class relationships. CPGNN offers a novel way to incorporate class semantics into propagation. However, its propagation relies on these estimated class compatibilitees which are learned globally, and the message passing itself is synchronous, potentially missing finer- mner-grained local differences in how nodes should value their neighbors from different hop distances.
CPGNN Protot-Pr Graph Neural Network)
Further, CO-GNN (Cooperative Graph Neural Networks) represents a recent approach to node- specific message passing through cooperative learning framework. CO-GNN employs dual networks, an action network that generates node-specific aggregation weights and an environment network that provides context, enabling each node to learn individualized message passing strategies. While this design achieves node-specific adaptation, it comes at substantial computational cost. The dual-network architecture requires separate linear transformations and graph convolutions for both networks at each layer, effectively doubling the computational load. Our profiling shows CO-GNN incurs 4.4x backward pass overhead compared to GCN (forward: 1.820 ms, backward: 13.431 ms on Cora).
Redefining Neighborhoods and Global Methods. A distinct set of approaches rethinks the notion of "ncighbor" or allows for global information exchange, moving beyond fixed topological neigh- borhoods. Geom-GCN (29 aggregates information from nodes in continuous space, constructing neighborhoods based on structural similarity (e.g., nodes with similar local graph structures posi- tions in latent space) rather than direct edge connections. This allows aggregation from distant but structurally similar nodes.
GloGNN 17 and its variants take more direct global approach. They might learn a dense affinity matrix or use attention mechanisms that allow each node to potentially aggregate information from
19

---

all other nodes in the graph, irrespective of direct connections. This enables the model to capture very long-range dependencies and global patterns.
While these methods can be powerful, especially Geom-GCN and GloGNN, they often come with significant computational costs (e.g., computing pairwise similarities or attention over all nodes with O(n²) complexity) and high memory requirements, making them challenging to scale to large graphs. They also risk incorporating noise by connecting nodes that are globally related but contextually irrelevant for a specific prediction.
Positioning of GAMMA. The existing landscape of GNNs for heterophily reveals a critical trade-off: methods that are highly adaptive or capture global context are often computationally demanding. while more efficient methods may lack the necessary node-specific adaptivity in how they leverage multi-hop information. Many multi-hop GNNs use fixed schemes, globally learned weights for hop combination, or feature concatenation strategies that escalate computational and memory demands. GAMMA designed bridge this gap. explicitly computes multi-hop representations but employs a lightweight, iterative gating mechanism at each node to dynamically assess and combine information from these different hop distances. Crucially, by using a shared linear transformation and learnable scaling vectors for features from different hops, followed by gating process that outputs fixed- dimension embedding. GAMMA A avoids the parameter explosion and high memory footprint associated with concatenating multi-hop features transformed by distinct weight matrices. This allows GAMMA to capture both global (per-hop learned scaling) and local (per-node adaptive gating) heterophily patterns efficiintly, offering compelling balance of expressive power, adaptability, and computational performance, as demonstrated in our experiments (Figure 5).
E Supplementary Theoretical Analysis
We establish convergence guarantees, information-theoree optimality, functional expressivity, and universal approximation properties for GAMMA. Throughout this section, let G = (V, E) denote graph with n = [V] nodes, normalized adjacency matrix A E R"**, and node features X E Raxds where d denotes the input feature dimension.
E.1 Preliminaries and Notation
We begin by establishing the notation used throughout the theoretical analysis. Let K 2 0 denote the maximum hop distance considered by GAMMA, where p-hop neighborhood for p {0, I...., K} refers to nodes at distance exactly p from a given node in the graph. By convention, the 0-hop neighborhood of node is the node itself. The choice of K determines the receptive field of the network, with larger K allowing information propagation from more distant nodes.
For node E V, we denote by H(") (A'XW), E Rdo the p-hop aggregated features, where:
A E RR*x represents the p-th power of the normalized adjacency matrix, capturing p-hop connectivity
W Rdu is the shared projection matrix that transforms input features to dout- dimensional hidden space
The subscript extracts the i-th row, giving the representation specific to node
After this projection and propagation, hop-specific channel-wise scaling factors Tp E Rh are applied element-wise
To ensure scale-invariance and enable meaningful comparison across hops, we normalize these embeddings. Let (2) -H(") / denote the no-noazlliedd embeddings, where || ||a is the Euclidean norm. This normalization ensures ||Er((]] || = for all hops p. making dot products between different hop embeddings interpretable cosine similarities.
The routing mechanism operates iteratively over f 0, 1, hyperparameter controlling the number of refinement steps. At iteration each node i maintains routing logits ( RRK,, which are (K + -iddiennsi vectors storing one logit value per hop
iterations, where R a
(0) 0, corresponding to uniform initial gating. The logits distance. These logits are initialized to b
20

---

are converted to gating coefficients via the softmax function:
exp(6 1. Ex exp(b
(II)
where Cip E [0, 1] represents the weight assigned to hop p at iteration for node i, and == a ip = ensures the coefficients form a valid probability distribution. We denote by
ΣK
(a..0 "Kk)" E gk+1 the vector of all gating coefficients at iteration t, written com-
pactly as a; softmax ).
The aggregated representation before the squashing nonlinearity is computed as weighted combina- tion:
K
19 H ERC
$/
(12)
P=0
This represents a convex combination of the normalized hop embeddings, where the weights determined by the current gating coefficients. The squashing function, inspired by capsule networks, then normalizes this aggregated representation while preserving its direction:
||s
10
(4)
(+)
(13)
||
1
The squashing function maps vectors to a bounded region: when ||s ( - 0, we have ||v O. and when ||s ( -> oc, we have ||v (0)
This ensures ||v!"|| E [o, 1] for all
The routing update rule refines the logits based on agreement scores between each hop embedding and the current aggregated representation:
(1+1)
(1) + H(P) v
(14)
(!) denotes the inner product. This update increases the logit for hop p when its embedding aligns well with the current aggregated representation, creating a feedback loop that iteratively refines the gating distribution.
where (
Definition (Gram Matrix and Agreement Scores). For node i, define the Gram matrix G, (((+1))(K+)) with entries
(G (H! (!
(15)
where P.q E (0.1....,KY K}. This matrix encodes the pairwise similarities between all hop em- beddings for node i. Since it can be written G; U.U, where U, = (.. xk++))x is the matrix whose semidefinite. This means all its eigenvalues are non non-negative: 0 I >ı I >2 S.... S AK+1, where we order eigenvalues in increasing order. Since each normalized embedding has unit norm, the diagonal
the normalized hop embeddings, the Gram matrix is positive
entries satisfy (G+)pp = ! = 1, and by the trace formula. -K-1 2x = tr(G.) ( = K Combined with the operator norm bound ||G.]| < K + 1, we have AK+1 K + 1. However, since (G E [-1, 1] (as cosine similarities), tighter bounds apply: AK+1 S when the embeddings identical, and X1 0 by positive semidefiniteness. We denote μ4; X1 2 0 as the minimum eigenvalue and L; = Ax+1 S K + as the maximum eigenvalue. When μ4 > 0, the Gram matrix is strictly positive definite, meaning the hop embeddings are linearly independent (up the dimension d
E.2 Detailed Convergence Analysis
We now analyze the convergence properties of the routing mechanism, establishing that it converges unique fixed point with exponential rate. The analysis proceeds through several lemmas building toward the main convergence theorem.
21

---

Lemma (Properties of the Free Energy Functional). Define the free energy functional for node as function of the gating distribution a and the aggregated representation
K
K B
Fi(a, = -
H
+
Op log Op
(16)
P=
P=0
where AK+1 lies the (K + 1--dimensional probability simplex defined
Ak=I-lEERK aa==1,0 0.ror all p}
(17)
P=
and v E Rha with ||v]| S (bounded representation). The parameter
is an implicit inverse
temperature parameter arising from the softmax. The first term Ep Op ( (H v) encourages alignment between the weighted hop embeddings and the target representation, while the second term? Ep=o Op log Opp is the negative entropy, which regularizes the distribution to prevent overly concentrated weights. Then:
1. For fixed v, F((.,) is strictly convex on Ak+1 with unique minimizer
a'(v) ((v) exp(3G,v)
(18)
(P) v)) ) the partition function ensuring normalization, and we use the notation [exp(u)]p exp( up) to denote element-wise exponential of a vector u.
where Z(v) Ex=o (
2. The gradient with respect to a (in the tangent space of AK+1. accounting for the constraint Ep Op = 1) satisfies
( vv
log di +
1
vaF((o,)==
+ A1
(19)
(K)
log oK +1
for some Lagrange multiplier X E R enforcing the constraint En ap = 1, where
=
11,1...., 1)T RR the all-ones vector.
3. The Hessian (restricted to the tangent space of Ak+1) satisfies
V Fi v) - (dag((a)=+>
(20)
where diag(a)-1 diag(1/ lag........................ 1/a,)) is diagonal matrix with entries 1/a, the diagonal. The notation > means the matrix is positive definite, establishing strict convexity.
Proof. For part (1), we minimize Fi v) subject to the constraint Σn Og 1 (and implicitly ap 2 0) via the method of Lagrange multipliers. The Lagrangian is:
K Σ
C(a,
a
v)
Σ ap log ap A
Eap-11
(21)
3 P=0
p=0
where À is the Lagrange multiplier associated with the equality constraint.
Setting ac 0 for each p (0.,,...,KK Bay
0 dap
1 ap (H) v) a log + rap - v) [10g + +1) =
+))+)(100))
(22)
where we used
d [ar log x log +1 de
22

---

Solving for Opi
(log ap + + = (HI v) B
1
(23)
log 0p = ((H v) B3 3 - exp (P) v) 31 - -11 =I)= - 9Aー1
(24)
ap
.v))
(25)
The constant e - is determined by the normalization constraint Σ Op = 1:
K
Σ
Op = e -
exp(B(H)) v)) =1
(26)
p=0
p=0
Therefore:
8A-1
ΣØ= exp(3(H, v)) = Z(v)
(27)
where we define the partition function Z(v) = Σx= exp exp( v)). Substituting back:
exp(3(H, v)) Z(v)
exp(5((H))) v))
(28)
Σ cxp( (H v))
which is precisely the softmax function with temperature 8-1 For part (2), the gradient of F; with respect is computed component wise::
0F: = - (p)
1
B (log up + 1)
(29)
Oop
Incorporating the constraint via the Lagrange multiplier À gives the form in the lemma statement.
For part (3), we compute the Hessian of the entropy term H (a) convention). The second derivative is:
E, ap log ap (noting the sign
8 (1)
2
(log Otp 6pg
(30)
0a,00g dog
Okp
where 6yy is the Kronecker delta (equals 1 = q, and otherwise). Therefore: {²H(a)= = ddag(1 ddagg(/oo.- 1/ak)
(31)
The first term in F,, namely
E, ap (H (p) v). is linear a, so its Hessian is zero. Thus:
Fr diag(1 1/00.-................ 1/ak) = diag(a))
(32)
Since Op > 0 for all p in the interior of AK+1 and B 0, all diagonal entries are positive, making the Hessian positive definite: V2 Fi > 0. This establishes strict convexity of Fi(., v) on the interior of the simplex.
Lemma 2 (Monotonicity via KL Divergence). Define the potential function a a (t)T (0TTT a.
R. which measures the expected squared norm of the aggregated representation (before squashing) at iteration I. This potential is quadratic form in the gating coefficients. Then for the routing update described in the preliminaries:
T (1+1)
(()
Dxi (( +
(1) A0 Aa
(t
10)
pG 20
(33)
P.g
where Aot Cipp o denotes the change in the gating coefficient for hop from iteration
1)+1)
t to t + 1, and D (x]l() = E, an log(lo///////ooo 3p) denotes the Kullback-Leibler divergence between two probability distributions a and B on the simplex. The KL. divergence is always non-negative, with (xl(ax) (xx] if and only i = B. The second term non-negative because G, positive semidefinite. Therefore, the potential is monotonically increasing across routing iterations.
23

---

Proof. We expand the potential difference $ (1+1)
- by substituting the definitions. Recall that:
K K
T (((11) = o G
(1+1)
(1-1)
ΣΣ
Lp
((+1)
dig
(1+1)
(Gi)ps
(34)
p= 0
9 oz
(B)T
G:a!
(1)
ΣE
2.p 1,9 (Gi)
(1) (1)
(35)
p=0==0
Expanding the potential difference:
(++1)
aip dig 1
(++1) (++1)
(G))
-
Eagpar (G.)
(36)
P-9
Substitute (1+1)_ (t)
aip a + D to express new coefficients in terms of old coefficients plus their
(1)
change:
(++1) 111)= Σ
Eap + Da (a (G))
Ealoa (Gi)pa
(1)
(37)
P-O
Expanding the product:
0 1.
i.g
(2)
+ oip
A
10
(1) + Ao
+ Do (0) (0) (Gi)pg
Aa!!!
(38)
P-
Σ p.q
aip iig (G:)pg
(39)
The terms Ep, 2 ;. (G:) pq cancel, leaving:
(1) (4)
1 (1-1)
(0)
Eaa Aa
(t) + a. A
( + Aa (G)))))))))))))))))
(40)
P.O
Using the symmetry of the Gram matrix (Gi)pg = (Gi)gp (since it represents inner products), the (t) Ao. (1) (G:)pg are equal (by swapping indices p <> q in
terms Ep. iip
(t) (c)
A i.q
(Gi)pg and Σ p.g
0i
the latter sum):
$ (1+1)
$ (t)
2
iip
(1) Do (Gi)pg +
(1) Aane Aaia (Gi)pg
(41)
Aa(t)
(t)
Σ
aig
(Gi)pg
Σ
Aa ( (Go)p
(42)
p
P.q
Now we interpret the term Eg Rig9
(t)
(Gi)
By the definition of the Gram matrix:
aa (oll Σ
2 H H
A
Σ
af H (
(AA
((0)
(43)
(4) (o) is the aggregated representation before squashing. where s: (1) = En aig
The squashed representation v is related to 5 by:
2
(44)
||5
where (4)
2 2 1+ [ 1|2
E (0,1) is a scalar. This shows v is proportional to the unit vector in the
direction of s Therefore:
|s
(H (/9) = -1ss ( 1 /1s(0111 (I)
(o)
(())
(45)
(
24

---

However, for the proof, the key quantity is the agreement score xp = (HH) v!?), which appears in the routing update. From the routing update rule:
DiP
(1+1)
Dip sp
(46)
where 8p = (
(()) is the agreement score.
The routing update gives the new gating coefficients via softmax:
exp(biip (1) + 88)
(++1)
softmax(b ) E, exp(b (1) + )1 pp
(47)
We now analyze the first term in the expansion using KL divergence. The KL divergence between the new and old distributions is:
(1+1)
(xt(a(tt)la
Σ
a
(1+1)
App
log
i.p
(t)
(48)
0 ipp
p
Σ
(++1)
log
(++1)
log (1) atp
(49)
1.p
From the softmax formulas:
(++1) log 1. k.p + sp - -log (((11)
= (1)
(50)
log a Di
(1) (t)
log (t))
(51)
where =0=== E, exp(b!!t) and z(+1) E, (xp (1) ) are the partition functions.
Subtracting:
. log
(1) (++1) - log a s(1) loog 2 loog 2
(52)
Substituting into the KL divergence:
(aa Σ
(++1) - log ((+1)) + log 2
(53)
A. p
Σ
Oip
(1+1) (t)
5p log (1+1) + log (1)
(54)
p
where we used Ep
((+1) iip
Now we apply Jensen's 's inequality to bound log (t++1) - log Z(1), Since the exponential function is convex:
z(++)) Σ exp(bl) + +(()) Σ (0) exp(s!") exxp(!)))xp((!())
(55)
exp(b
(
Z(0) exp(s 2(+)) Σ a exp(s(")
(56)
By Jensen's 's inequality (since exp is convex and Σ, (1) =1);
a
E 2 exp
exp(o!))
(57)
Therefore:
z(+1) > 7(1) exp Σ [a(l s
(58)
25

---

Taking logarithms:
log (((+1) log 2
Σ
(59)
Substituting back into the KL divergence expression:
DKL(a (++1)
(a. 2
Σ
up p
(++1)
(1)
Σ
(1)
(60)
Σ
i.
(t+1)
0 1
(1)
Da
(61)
Combining with the earlier expansion of 2 ([+1)
1 (1) and noting that G, is positive semidefinite 1.9 (G:) 20, we obtain:
(hence the quadratic form Ep.q Aa Aa,
(c)
(++) D z (a (+ a (2) 20
(62)
This establishes monotonicity of the potential function.
L
Theorem 1 (Exponential Convergence to Unique Fixed Point). Assume the Gram matrix G3 is strictly positive definite with minimum eigenvalue μ4 >> O and maximun eigenvalue L,. This assumption holds when the normalized hop embeddings {f AK 1p=0 span a subspace of dimension K + (or equivalently, when these K + 1 vectors are linearly independent). Initialize the routing logits to corresponding uniform initial gating coefficients a. 1/(K for all p. Then:
b
(0)
1. The routing converges exponentially unique fixed point b R+ with rate:
1/2
11 2L;
b
b
(63)
where || 1l2 denotes the Euclidean norm. The convergence rate depends the condi- tion number = Li/ps of the Gram matrix: smaller condition numbers lead to faster convergence.
2. The converged gating coefficients satisfy:
G FG
(64)
where (1,1,..., E KK1+ the all-ones vector. This gives an explicit formula for the equilibrium distribution in terms of the Gram matrix.
3. The convergence satisfies the
(PL) condition:
[IVE: p -.(())
(65)
for all in a neighborhood of where (a) denotes the gradient of the potential function. The PL condition is a weaker condition than strong convexity but is sufficient to guarantee exponential convergence for gradient- based methods.
Proof. Part 1: Existence and Uniqueness of Fixed Point.
From Lemma the potential function (t) a (t)T G,a iterations. We now establish that it is also bounded above.
(1) is monotonically increasing across
Since | (p) = for all E 10.,,...,KK (by normalization) and a; lies on the probability
simplex (so E, o 1), we can bound:
(t)
$ = a;
(0)
(1) G.a;
(t)
Σ
aipa H.
(0)
(66)
p.g
Σ
i.n
(9) (g)
=
H
(67)
26

---

By the triangle inequality and the fact that
Ep
(1) cip
Σ
S
Σ
= Σ iip 1=1
(68)
Therefore D < 1 for all By the monotone convergence theorem, since 1 is monotonically increasing and bounded above, the limit lim;->oc (1) D E [0. 1] exists.
At a fixed point, the routing coefficients no longer change: a: (1+1) (9) which implies Aa?" (2) From Lemma at a fixed point:
0.
(1(+1) o. (a (1+2) la (1a
(4) (1) Ea Daii (G.)pg =0
(69)
P-1
Since both terms are non-negative, each must be zero. In particular:
DKL (a. (
(++1) a(t a
(0)
(70)
To characterize the fixed point, we consider the optimization problem that the routing implicitly solves:
a' arg max aEAg
P;(a) = arg max a GiG aEAxı1
(71)
This is quadratic program over the probability simplex. To solve it, we form the Lagrangian:
[(a, A) a" - 1)
(72)
where À E R is the Lagrange multiplier enforcing the constraint Σp ap 1. The first-order optimality condition (KKT condition) is:
ac 2G 01
(73)
Since G; strictly positive definite (14: > by assumption), is invertible. Therefore:
G
(74)
The constraint aTa = determines the Lagrange multiplier:
1Ta A 1G =1
(75)
2
1GG
Substituting back:
G G
a'
(76)
FG
To verify this is the unique global maximum, note that the objective a G, strictly convex on the compact convex set AK+1 (since the Hessian 2G, > 0). A strictly convex function compact convex set has unique maximizer, establishing uniqueness a"
Part 2: Convergence Rate via Polyak-Lojasiewiez.
To analyze the convergence rate, work with the negative potential L(a) a (note the sign flip, converting maximization to minimization). The gradient in the tangent space of AK+1 is approximately (ignoring the constraint for the moment):
v((a) a2
(77)
To account for the constraint E, Op = 1, we project this gradient onto the tangent space of the simplex. The tangent space at consists of vectors satisfying 1T (zero sum). The projected gradient is:
C(a) = a + 2(a G,a)
(78)
(1"a)
27

---

However, for the analysis, it suffices to work with the unprojected gradient and use the Polyak- Lojasiewiez (PL) condition, which is weaker than strong convexity.
The Pl. condition states that for all a in a neighborhood of the optimum:
V 2 -
(79)
To establish this, first compute:
- - (o')
(80)
Expanding x² + +aaaaa)) a²):
(a (aa'' a²)
(81)
Using the first-order condition G, 2" 1 and the fact that 1 1"( - a²) = (both are on the
2
simplex), the middle term vanishes:
Xa - 1T 1" -a))=
Ga')" a²)=
(82)
2
Therefore:
((a) -(a") -(a a G a')
(83)
By the eigenvalue bounds on G; (with #4 S X < I, for all eigenvalues X):
- - aa- a') 2 -Lila - x1
(84)
For the gradient norm:
[VL(a) = - aG a
(85)
Using a o² + (ax x²)) and the first-order condition:
G + Gi(a- - a²) 1 --1
X" Gila G -a"
(86)
For vectors on the simplex tangent space (where 1s (a-a"") = 0), the constant vector 1 is orthogonal the difference. Therefore:
[VC()) 4||G.(a a²)13 4willa a al
(87)
Combining the two inequalities:
4p4 (- [VL(a)] 2 4uslla- a² a²112
(88)
L,
This establishes the PI. condition with constant 2/1/ T. For an iterative update scheme with effective step size n, the PL condition implies:
((a L(a") (1 - (1- "u..//)))(((( - L(ax))
(89)
Taking 7) 1/2 (a typical choice in routing algorithms):
((a - L(a") (1 (1- 14 ) (C(a(()) L(a"))
)
(90)
Converting back to the potential Φ; -L:
Φ (00 <
1
Hi
( (0)))
(91)
L
28

---

Using the relation between the potential and the distance to optimum (from the eigenvalue inequality):
||a! xx a= -
:
H4 Li
( -0!
(92)
H4
Taking square roots:
:
(0)
(1 (1-
1/2
|1a00) ax
(93)
pi
2L,
Since 0 and Φ; < 1, have & (+) softmax (b( and the Lipschitz property of softmax imply a similar bound on |lb(t) bb
1. Also, for the routing logits, the relationship
completing the proof of part (1).
E.3 Information-Thhereee Optimality
We now establish that the routing mechanism approximately maximizes the mutual information between the aggregated node representation and its label. Mutual information T(X; Y) quantifies the amount of information obtained about random variable Y by observing random variable X, and symmetric: [(;; Y) XX).
Theorem 2 (Mutual Information Maximization). For node E V, let Ip(t) = I(H : denote the
mutual information between the p-hop representation H())) E IRd and the node label ye (0, 13 (for binary classification; the result extends to multi-class). Assume:
Features H yy follow multivariate Gaussian distributions N( Ep) with class- (p)
conditional means po (p) (p) Ba and common covariance Ep E Rdaaxduu This pi
assumption is reasonable due to the central limit theorem: hop embeddings are averages over many neighbors, hence approximately Gaussian.
2. Neighborhood sizes satisfy [W(()) 2 denotes the set of nodes at distance exactly p from node i. This ensures sufficient averaging for concentration bounds.
Colog dona for some constant C O, where N No (i)
3. Class priors are balanced: P(y, 0) is not essential; the result generalizes to imbalanced classes with minor modifications.
P(y = 1) 1 This simplifies the analysis but
Then the converged gating coefficients af approximately maximize the weighted mutual information:
K
a RJ arg max aEAR+1
apIpli)
(94)
p=0
with approximation error O(ylog dona! which vanishes neighborhood sizes grow.
Proof. Step 1: Gaussian Mutual Information.
Under the Gaussian assumption, the mutual information between H(P)) and y can be expressed via differential entropies:
((H (n) = H(H{")) ((H(")) (b))
(95)
where ((H(")) = f p(h) log p(h)dh is the differential entropy of the marginal distribution, and H (H (y:) the conditional entropy.
For the conditional entropy, using the halanced class prior assumption:
H(H 19 (..) = Σ P(u. c) (( c) Σ ( = cc)
(96)
c=0
c=0
29

---

For Gaussian random vector H. l/- = cc (N. Ep), the differential entropy is:
1 (P) yi c) dout (TTe) 2 log del (2p)
H(H
(97)
where det(Ep) is the determinant of the covariance matrix.
Since the entropy is the same for both classes (common covariance):
(P) (B4) H H
dout log (2Te) + log det det(Ep) Ep)
1
(98)
2
The marginal distribution is mixture of Gaussians:
(p) 1 N(: (p) Ep) + 2 Nh:
p(h) 2
, Ep)
(99)
For well-separated means Mo and u1d), the entropy of this mixture can be approximated. When the separation (|14()) |1 is large relative to the covariance, the two Gaussian components have little overlap, and the entropy approximately:
H(H
(0) dout log(2 log det(Ep) + 8 (ug uP
p (())
(100)
The approximation comes from second-order Taylor expansion of the mixture entropy around the limit of widely separated components. Subtracting the conditional entropy:
1p(1) = (( (2) :8:) =
5 ( - μ (() " (m4))) (م)
(p) pi
(101)
E
where || =V>>, is is the squared Mahalanobis distance, which measures distance in units normalized by the covariance.
This shows that mutual information is proportional to the squared distance between class centroids in the metric induced by the covariance.
Step 2:
Connection to Agreement Scores.
For node with true label y; {0, 1), the normalized hop embedding after aggregation over its p-hop neighborhood concentrates around the class centroid:
H
R
+
6p
(102)
M
where Ep E ddd noise with covariance (aa (/////((P)) (i)) 1, arising from averaging over [W(()) neighbors. The variance decreases as 1/I (i) by standard concentration results.
The dot product (agreement score) between this normalized embedding and the aggregated represen- tation V. E, ag H.H is:
(p)
H
vz)
He
Σ
Oig
O([ee])
(103)
||
uee (g)
Oig
+
O([Ee()
(104)
||
When the routing converges, v, aligns with the true class centroid direction. Hops where the class centroids well-separated (large || (p) 11 (((")) []) provide stronger class-discriminative signals,
yielding larger agreement scores when v; points toward the correct class.
Step 3: Quantitative Relationship.
30

---

Under the isotropy assumption that Σp = I (spherical Gaussian, common simplification), the Mahalanobis distance reduces to the Euclidean distance:
(1)
S l
(p) - -14 (p)
(105)
The agreement score for node i with label y/s satisfies:
Mec
v.) cos(Op)
(106)
(p) pell
where = Elv:ly: = cj is the expected aggregated centroid for class and Op is the angle between the hop embedding and the aggregated representation.
For hops where (0 and 1 are well-separated, the class-conditional agreement scores differ significantly. Specifically, the difference in agreement between the two classes is:
P)) vi)lu:
(H va) y 1] l1
(107)
Therefore, maximizing the weighted sum of agreement scores E, ap ( v.) (which the routing does via Theorem T is approximately equivalent to maximizing the weighted mutual information Ep (plp(i).
Step Concentration Bound.
To formalize the approximation error, we use Hoeffding's 's inequality. For (W(z) (t) = np neighbors hop p. each contributing independently to the aggregation:
vv) E(H vi)i c) s 2 exp (- -mnpe² npp
(H
P
(108)
22
This follows because the inner product can be viewed as of dour terms, each bounded. For 22dcau log(2/0)/n, where ó E (0,1) is a failure
Mp 2 C' C'log doat with C > 2, choosing
probability:
IP (11 v.) - vill
2dou l2g(2/8)
S 8
(109)
np
With high probability (at least - (K 1)6 by union bound over all K + hops):
K
2dou log(2/8)
2dou log(2/0 (2/6)
Otp
pp)
Σ
o ((())) (P) viYl
Opp
sv
(110)
Rp
minp np
p=0
Since the routing from Theorem maximizes the empirical agreement Σ, ( (p) v.), and this differs from the expected agreement (which is proportional to mutual information by Steps 1-3) by at most ( log doun/ mp), the converged a approximately maximizes the weighted mutual information E, (1) up to this concentration error.
E.4 Functional Expressivity
We now establish that GAMMA's function class contains the function class of concatenation- -base multi-hop GNNs, showing that GAMMA least as expressive.
Theorem 3 (Expressivity Hierarchy). Let Fooman denote the function class of multi-hop concatenation
GNNs that use hop-specific weight matrices (W(p) E Rdd.dd Ip= to independently transform features from each hop before concatenating them. Let FGAMMA denote GAMMA'S 's function class with
shared projection W E & dos, channel-wise scaling factors {Tp E Redss j pp and adaptive gating the routing mechanism. Then:
Feoncut C FGAMMA
(111)
Moreover, for any e and any function I E Feomcas there exists a function g E FGAMMA such that Il glloo <. any compact domain, where ||- lloo denotes the supremun norm.
31

---

Proof. We construct an explicit simulation of concatenation based architectures using GAMMA.
Consider concatenation--assel architecture that produces node representations by:
f(x. (IW(' (0)
W (x)
(112)
where:
H (P) = (A"X); E Rd is the p-hop propagated feature for node (before any projection)
W(r) Rdax is the hop-specific transformation matrix
The concatenation [.....:) produces a vector in 12 (K))dd
① R(K+1)daa RC is a downstream network (c.g., MLP with classification head)
producing C-dimensional output (c.g., class logits)
To simulate this with GAMMA, we construct the following:
Step 1: Dimension Expansion. Set the hidden dimension to d'ot = (K + 1)dout. which is (K + 1) times larger than the original concatenation dimension per hop.
Step 2: Disable Routing. Initialize routing to uniform distribution: ai,p 1/(K + 1) for all
p {0. .O..... K]. and set the number of routing iterations to O. This prevents any adaptive refinement, making the gating static and uniform across all hops.
Step 3: Partition Feature Space via Scaling Factors. Configure the channel-wise scaling factors
Yp E If to partition the expanded feature space into (K + 1) non-overlapping blocks, one per hop:
Yp 10...,,, O, Wp.1, ....,........................... Wppddur O, 0,...,0l E (R++)))
(113)
pdou
dea entries
(K-p)dan
where the entries Wp. for j E {1,.... d encode the entries of the j-th column of W Specifi- cally, if W(P) E RRda Xdui is the original hop-specific matrix, we set the shared projection W to be an identity (or simple linear embedding), and use 7/ to apply the transformation post-prou post-proaagatio.
More precisely, setting W = Ia,, (identity matrix, assuming d = d'un or with appropriate padding), the p-hop embedding becomes:
H (P) (APXW): (APX);
(114)
Applying the scaling factor 7, element-wise isolates the transformation to a specific block of the feature space.
Step 4: Aggregation with Uniform Weights. The aggregated representation (before squashing, which we can effectively disable by setting appropriate parameters) becomes:
Oip (Yp 3 (!)))
(115)
p=0
K (7p 2 H!))
(116)
H.
(117)
K+1
where the notation [....... now represents the blocked structure induced by the scaling factors. The factor of 1/(K + comes from the uniform gating.
Step 5: Adjust Output Layer. Apply an output transformation कp p'=KK' + 1) to compensate for the averaging factor 1/(K + 1). This gives:
g(X, v'(v.) = (K+1)
W
H (0)
w(0HH(13)) = H(W"H ,..., ((O)
K+1
(118)
32

---

This exactly matches f(X, A);. establishing that f can be represented by GAMMA, hence f E FGAMMA-
For the approximation statement: Any function in Feemcal can be written as composition of the multi-hop feature extraction (linear maps) and the downstream network Φ (nonlinearities), By the universal approximation theorem for neural networks, & can approximate any continuous function to arbitrary precision given sufficient capacity. The construction above shows that GAMMA can exactly represent the concatenated multi-hop features. Therefore, by approximating & with a sufficiently large network (increasing the capacity of the final layers in GAMMA), we can approximate any F Foncat to within error.
E.5 Universal Approximation
Finally, we establish that GAMMA universally approximate any continuous function on graphs, with explicit bounds on the required architecture size.
Theorem (Universal Approximation with Explicit Rates). Let C. Ruxda x gg be a compact set of graph instances (node features and adjacency matrices) with diameter D under some norm || I|. Let f :K + RaxC be a Lipschitz continuous function mapping graph instances to node-wise outputs (e.g., node classifications) with Lipschitz constant L.. meaning:
(x, (",,,, A2)1e A1) - (X2, A2)ll
(119)
for all (X1, A1), (X2, A2) E K. Then for any there exists a GAMMA network J with parameters:
= O(log n)) hops (maximum hop distance)
(120)
= (log(D/))
routing iterations (refinement steps)
(121)
1b
dow =0
(1
dn/2
hidden dimension (feature space size)
(122)
such that (X)eX [If(X, (X,A)) < i.e, uniformly approximates f K. to within error
Proof. We decompose the total approximation error into four independent sources, each contributing at most e/4, which sum to give total error less than
Error Source 1: Polynomial Approximation of f"
By Jackson's 's theorem (a classical result in approximation theory), any Ly-Lsshhittz function on a du dimensional domain with diameter D can be approximated by polynomials. Specifically, there exists a polynomial Pm of total degree at most m such that:
LjD m2/dm
Epoly (m) sup
[I Pm (X. C3 (X.A)EK
(123)
where C3 > 0 is a universal constant depending only on the dimension. This bound captures the curse of dimensionality: the required polynomial degree grows exponentially with dimension to achieve the same approximation error.
To ensure Epoly (m) c/4:
D CJ 2/d
DC
4CCLL
dn/2
2/dm
m
(124)
Error Source 2: Representing Polynomials via Multi-hop Aggregations.
A polynomial Pm, (X,A) of total degree in the entries of X and A can be written as:
Pm Ax) = Σ CB.7
(125)
kt
181+
Sm
K.E
33

---

where 3 = (Btz) and (rike) are multi-indices and [3| = Eig Biy denotes the total degree in X.
Each monomial involving A" (the p-th power of the adjacency matrix) can be expressed via the p-hop propagation in GAMMA. The key observation is that (ArX)iy involves products of entries of A and X, capturing p-hop paths.
Since |||]| & 1 (the operator norm of the normalized adjacency matrix is bounded by 1), powers beyond K decay:
K
|||
< 1
(126)
However, if A has spectral radius slightly less than I, say ((A) = 1- - å for small (which holds for many normalized adjacency matrices on connected graphs), then:
|| S (1 - 5)k e
(127)
For 5 1/n (a typical spectral gap), taking K (logg) ensures || contributions from hops p > K negligible.
O(1/n), making
More precisely, for polynomial with coefficients {ap}. the error from truncating at hop K is:
Ehop (K)
A
l0p |0p|||71||X1]
ap 6). (128)
p=
p=
p=
For coefficients decaying as |apl S Ce (typical for smooth functions), the tail sum is:
8
C (k]+)) 5) 1 - e1-e-1(1-10
8) 51 lapl(1 SC Σ e p P(1-55p
(129)
p=K+1
p=K+1
For K
/ we obtain (K) S e/4.
Error Source 3: Analytic Function Approximation (Softmax and Squashing).
The softmax function <b), = exp(tp)/ Eg exp(by) and the squashing function are real analytic (infinitely differentiable with convergent Taylor series). For bounded inputs, their Taylor expansions converge uniformly on compact sets.
For softmax with inputs bounded by B (i.e. |//l I B), the truncation error of the Taylor expansion up to order M is:
C.BM+1
o(b)
Σ
ba
I
c (K+1)B
(130)
a
(M + 1)!
jalSM
where Co is constant depending on the dimension K 11 In GAMMA, routing logits iteration satisfy:
1-1
Σ
H (
Σ
(131)
since [ || = (normalized) and
||
1 <
(squashing bounds the norm). After R iterations,
B = R.
To achieve error e/4 from the softmax approximation:
C. M++
(k++)) < E 4 (M + 1)!
(132)
Taking logarithms:
(M 1) R log((M + 1)!) + (K + 1)R < log
-log C₂
(133)
34

---

Using Stirling's approximation lM! = M log M -::
(M + log R (M + log M + (M 1) (K 1)R s log 4
-log Co
(134)
Rearranging:
R
+ +1 (K 1)R S log 4
(M 1) log
log Co
(135)
M +
For practical choices of R (small, say R < 5) and K = O n), solving for M yields:
M O + (K + 1)R log(1 (e)(1))) O(log log(1/e))
(136)
Since K O n) and R small constant independent of n, M remains polynomial log and log(1/e).
Similarly, the squashing function >(r) r22/(1+ +1+++ analytic for 0. Its Taylor series around r r=0 is:
7(r) - +
(11
(137)
For S 1 (which holds since [I after normalization), the series converges rapidly. Truncating at order O(log(1/e)) terms gives error at most e/8.
Total analytic approximation enror: Eanatric S e/44.
Error Source 4: Routing Convergence.
From Theorem I after R. routing iterations, the representation within distance:
vill S
L
Mi
R/2
vill
(138)
2
Since ||v (0) = || < (bounded by squashing). the initial distance satisfies ||v (0)
v <
(triangle inequality). The diameter of K. in terms of node representations is most D by definition.
To ensure Frouting I c/4:
Li
Hi
1/2
C 2D <
(139)
14
2T,
4
Taking logarithms:
Hi
log
S log
(140)
2
2L,
8D /DT/T./
Using log(1 - x) se -r for small x::
R.
pi
I log
(141)
2
2L,
8D L./m/
Solving for R:
4h. P:
8D 8D TT//u
4h;
D
1
log T, log 8
R
log
log
(142)
14
c
2
For bounded condition number K; well-conditioned), this simplifies to:
Li/M = O(1) (which holds when hop embeddings are
R = 0 1og D
(143)
Hidden Dimension Requirement.
35

---

To represent all monomials in the polynomial Pm up to degree m, the hidden dimension must be sufficient to capture all (Aa+T)) possible monomials. By standard combinatorial estimates:
dm + m (dm
(din + m) (oldi + m)
(144)
m
m!!
m
For m = (() and assuming din < (large degree regime):
(0(())))))
da/2
dam = 0m =0
(145)
Total Error.
Combining all four error sources:
|I - ls I Epply + Enap + Esmalytic +
Ereating
-
=
(146)
4
4
This establishes the universal approximation result with explicit parameter dependencies.
Remark 1. The parameter scalings in Theorem eexhibit the curse of dimensionality through dooe 0e/22, which is inherent approximating arbitrary Lipschitz functions high dimensions and cannot be avoided by any architecture. However, the number of hops K = (logn) grows only logarithmically with the graph size n, and the routing iterations logarithmically with the desired accuracy making GAMMA practically efficient. In typical GNN applications where dig is moderate (tens to hundreds), and we only require approximation accuracy 0.01 (reasonable for classification tasks with finite precision), these requirements remain manageable on standard hardware.
(llogLL/e) grow
F
On the Hardware Efficiency of GAMMA
Modern GPU architectures are designed to maximize throughput for dense matrix operations, yet Graph Neural Networks present unique computational challenges that systematically underutilize available hardware resources. The fundamental tension arises from the mismatch between the spatial locality assumptions inherent in GPU memory hierarchies and the irregular memory access patterns induced by graph-structured data. In this section, we provide rigorous analysis of GAMMA's hardware efficiency, demonstrating how its architectural choices, particularly weight sharing, dynamic routing with fixed dimensionality, and the strategic climination of feature concatenation, translate to measurable improvements in memory bandwidth utilization, cache hicrarchy exploitation, and sustained computational throughput. We ground our analysis in the memory subsystem design of contemporary datacenter GPUs and establish theoretical bounds on the performance of multi-hop heterophilic architectures, contrasting GAMMA's design with representative approaches such as MixHop 1 and H2GCN 40).
Notation. Throughout this section, employ the following notation to facilitate clarity and precision in our hardware efficiency analysis.
Graph and Architecture Parameters: Let N E N denote the number of nodes in the input graph, K represent the maximum hop distance considered in multi-hop aggregation (so the total number of hops is K + 1, including the O-hop self- seff-connection, din E N denote the input feature dimension, drat E N denote the output feature dimension, and represent generic feature dimension when din daut-
Graph Data Structures: We denote the adjacency matrix as A E NNN. where entry Ai represents the connection weight from node node (we use A denote the k-hop adjacency matrix, with A I being the identity matrix), the input node feature matrix as X E Nxd,, where row X, contains the features for node i, and weight matrices as (Ak) E du Xdw for hop-specific transformations (MixHop, H2GCN) or W E Rda x for the shared transformation in GAMMA.
Hardware Specifications: For a representative GPU (NVIDIA A 100 80GB), we denote NsM 108 as the number of Streaming Multiprocessors, CL2 40 MB as the capacity of the shared L2 cache,
36

---

Bmem = 2,039 GB/s as the memory bandwidth from HBM2e to the GPU, RSM = 63.536 as the number 32-bit registers per SM, and Peak 19.5 TFLOPS as the peak floating-pone point throughput for FP32 operations.
Performance Metrics: Let 7 (measured in FLOPs/byte) denote the computational intensity of an operation (ratio of floating- operations to bytes transferred from main memory). P denote achievable performance (measured in FLOPS), Lidge denote the ridge point operational intensity (the threshold where compute and memory bandwidth constraints balance), _ = 4 bytes represent the storage requirement for single FP32 element, and p denote the bandwidth efficiency ratio comparing GAMMA to concatenation- based architectures.
Memory and Latency Metrics: We M with various subscripts to denote memory footprints (measured in bytes): Mesnca for concatenation-base architectures, Mixed for fixed-dimensionality architectures, Momting for GAMMA's routing state, and MaAMMA for GAMMA's total memory consumption. For latencies (measured in cycles unless otherwise specified), we denote TDRAM R 400 cycles as DRAM access latency, 7L2 200 cycles as L2 cache access latency, and Taunch as the CPU-side kernel launch latency (typically 5-20 microseconds).
Data Movement Metrics: Let D with various subscripts denote data movement (measured in bytes); Duin for the theoretical minimum data movement, D Deoncut for concatenation- based architectures, DGAMMA for GAMMA's data movement, unffused for unfused kernel data traffic, and Dissed for fused kernel data traffic. We denote Bused as the bandwidth consumed by a layer, Ber as the effective bandwidth under cache behavior, and Beache as the effective bandwidth when serving from cache.
Execution Time Metrics: Let Mayer denote the execution time for a single layer, with various subscripts denote total execution times: Toerheed for accumulated kernel launch overhead, T Tistal overhend for overhead across training. Trouiing for routing computation time, TGAMMa for GAMMA's total execution time, TissHop for MixHop's execution time, and TH2GCN for H2GCN's execution time.
Training Parameters: Let of training epochs, and B E N denote the number of batches per epoch.
denote the number of layers in the model, E E N denote the number
Tieer E N to denote the number of routing iterations, t to index routing iterations where E 1,......, Tier 1). H₁ E R x to denote embeddings at hop k. H₃ Nxda to denote normalized hop embeddings, z(") E R. to denote node i's routing state at iteration t, has R. denote the normalized embedding for node i at hop k, dij E R to denote the agreement score between node i's routing state and hop k at iteration t, and w
Routing Mechanism Parameters: For GAMMA's routing,
E [0, 1] denote the normalized routing weight for node and hop k iteration (where (E)
2k= ik 1).
Additional Parameters: We denote μ [0, 1] as the cache miss rate, W 32 as the warp size (number of threads executing in lockstep). >> O as a small constant to prevent division by zero in normalization, "fusion as the fusion efficiency factor, Pioual as the total parameter count, S, the size of intermediate tensor i, Rops as the number of operations in a sequence, and + as the concatenation operator along the feature dimension.
F.1
The Memory Wall in GPU-Accelerated Graph Learning
To understand GAMMA's efficiency gains, we must first examine the fundamental bottleneck in modern GPU computing: the memory hierarchy and its implications for data movement. Consider representative datacenter GPU such as the NVIDIA A100 80GB, which features NsM = 108 Streaming Multiprocessors, a shared L2 cache of capacity CL2 = 40 MB, and memory bandwidth Bmem 2.039 GB/s from HBM2e memory [26]. Each SM contains register file of RSM 65,536 32-bit registers and shares access to the unified L2 cache, which serves as the coherence point for all device memory transactions [[5]. The critical observation is that despite the GPU's peak meating-point throughput of Fpesk = 19.5 TFLOPS for standard FP32 operations, the achievable performance for many deep learning workloads is constrained not by computational capacity but by memory bandwidth, the rate at which data can traverse the memory hierarchy from DRAM through cache to compute units.
The Roofline Model 351 provides the theoretical framework for understanding this constraint. For an operation with computational intensity (measured in FLOPs per byte transferred from main
37

---

memory), the achievable performance P is fundamentally bounded by:
P min (F (Fpeak, Beem T).
(147)
The ridge point, where compute and memory bandwidth constraints intersect, occurs at operational intensity:
peek
19.5 10
Iddgo
Bmem 2.039 x 1012 R 9.6 FLOPs/byte.
(148)
Operations with < Fridge are memory-bound, meaning performance is fundamentally limited by data movement rather than arithmetic throughput. Unfortunately, the sparse-dense matrix multiplications and neighborhood aggregations central to GNN computation cxhibit low operational intensity, placing them squarely in this regime. The situation is further exacerbated by the irregular memory access patterns inherent in graph structures, which violate the spatial and temporal locality assumptions that modern cache hierarchies are designed to exploit. When neighbor indices are scattered throughout memory, cache lines (typically 128 bytes) are incompletely utilized, and hardware prefetchers, which predict future memory accesses based on observed patterns, fail provide timely data delivery. This architectural mismatch between algorithm and hardware is the fundamental source of inefficiency in naive GNN implementations.
F.2
Architectural Inefficiencies in Multi-Hop Heterophilic GNNs
Multi-hop heterophilic architectures attempt to capture long-range dependencies by aggregating information across multiple hop distances. However, the implementation strategies employed by architectures such as MixHop [ and H2GCN 40) introduce systematic inefficiencies that fun- damentally limit their scalability. These inefficiencies manifest multiple levels of the memory hierarchy and arise from design decisions that, while algorithmically motivated, have profound negative consequences for hardware utilization.
F.2.1 The Hidden Cost of Feature Concatenation
MixHop computes multi-hop representations as:
K
ZixxHop
A k=
(A*xW())),
(149)
where Q denotes concatenation along the feature dimension, A E NNN represents the adjacency matrix, X E xx contains input features, and W E 12d, are hop-specific weight matrices. For K + 1 hops, each producing embeddings of dimension dout. the concatenated representation has dimension (K + 1)dea- This design choice, while straightforward algorithmically, introduces a cascade of inefficiencies throughout the memory hierarchy that severely impact both memory consumption and computational throughput.
The memory footprint grows linearly with the number of hops. Let B bytes represent the storage requirement for single FP32 element. The total memory required for intermediate hop representations and the final concatenated output
Meoncal ON
demi + (N(K + 1)doa 3N (ou + 2).
(150)
In contrast, fixed-dimensionality architecture that maintains d throughout requires only Mixed NN yielding a memory expansion factor of 2K + 2. For typical configurations with K = 2, this represents sixfold increase in memory consumption. The ramifications extend beyond mere capacity: when the working set size exceeds the L2 cache capacity CL2. intermediate results must be evicted DRAM, triggering expensive round-trips with latencies of TDRAM 400 cycles, compared to TL2 R 200 cycles for L2 cache access [24]. Consider graph with N nodes where K = 2 and d d. The concatenated features require memory:
M ( N, K, d) = 3N(K + 1)d = 33Nd,
(151)
which must within C1 to avoid DRAM traffic. For the 1100 with C122 = 40 MB, this constrains Nd < 3.33 x 10S, a threshold easily exceeded by real-world graphs.
38

---

More critically, concatenation forces the materialization of intermediate results in global memory, violating temporal locality and preventing kernel fusion opportunities. Modern deep learning frame- works achieve high performance through kernel fusion 2 where consecutive operations are merged into a single GPU kernel to eliminate intermediate memory transactions. A fused kernel can maintain data in registers (latency R 1 cycle) shared memory (latency = 30 cycles) throughout a sequence of operations, whereas unfused operations must write to and read from global memory between each step. Concatenation creates hard data dependency that prevents fusion of downstream operations, as the concatenated tensor must be fully materialized before subsequent layers can proceed. Each concatenation incurs data movement of (K 1) bytes, consuming memory bandwidth that could otherwise be allocated to computation. For a graph with N nodes, this bandwidth consumption is:
(K + dou
Bused
(152)
Bayer
where daaer represents the layer execution time. When Bused approaches Bmems the architecture becomes bandwidth-limited, with compute units stalled waiting for data.
F,2.2 Parameter Proliferation and Memory System Implications
Beyond concatenation, MixHop and H2GCN employ separate weight matrices W E Rdo Iddaxdan for each hop k {0, (0, K}. introducing total parameter count of:
Protal (K don-
(153)
While parameter count itself is often not limiting factor for modern GPUs, the computational implications are significant. Each hop requires a separate matrix multiplication kernel launch, incurring (K + 1) kernel launch overheads. The CPU-side kernel launch latency, denoted Flaunch- is typically in the range of 5-20 microseconds depending on API calls and driver state (28). For K + hops, the accumulated overhead is:
Toverhead (K + Taunch-
(154)
While this overhead may appear negligible for individual layers, it compounds across layers and training iterations. For a model with layers trained over E epochs with batches per epoch, the total overhead accumulates to:
ovtabboear overhead
L.
E- B (K + 1) Taunch.
(155)
More insidiously, separate weight matrices residing at distinct memory addresses disrupt the operation of hardware prefetchers. Modern GPUs employ sophisticated prefetching logic that detects sequential or strided access patterns and preemptively loads data into cache before explicit requests. When weight matrices are scattered throughout memory, access patterns appear random from the prefetcher's perspective, leading to cache misses and memory stalls. The effective memory bandwidth Ber under poor prefetching related to the cache miss rate fs by:
Bat
Buem (1 (1
p)) Beache -
(156)
where Beache < Bmem represents the effective bandwidth when serving from cache. High miss rates significantly degrade Ban, throttling computational throughput.
F.3 GAMMA's Architectural Co-Design for Hardware Efficiency
GAMMA addresses these systemic inefficiencies through principled algorithmic and architectural co-design. The architecture's ' efficiency stems from three core design principles: weight sharing with unified transformation to maximize parameter reuse, dynamic routing with fixed dimensionality to preserve cache locality, and elimination of explicit concatenation to enable kernel fusion.
F.3.1 Weight Sharing: Memory Reuse and Cache Coherence
GAMMA employs single shared weight matrix W E Rdaxdu to transform input features exactly
once:
H proj
XW.
(157)
39

---

All subsequent molti-hop propagations operate on these projected features:
H A A proj. k E (0, .., K)
(158)
where A I represents the identity. This seemingly minor architectural decision has profound implications for hardware efficiency. The parameter count reduces to:
PGamma = din
(159)
representing a reduction factor of (K + 1) compared to architectures with per-hop weights. More eritically, the single matrix multiplication kernel launch eliminates (K + 1) launches, reducing overhead to Thanch regardless of K.
The architectural advantages extend deeper into the memory subsystem. By repeatedly accessing the same weight matrix across hops, GAMMA maximizes cache reuse. Once W is loaded into 1.2 cache, subsequent accesses are served with latency 722 rather than TDRAM- The cache hit rate for weight matrix accesses approaches unity, as the matrix remains resident throughout the multi-hop computation. Furthermore, the single, contiguous memory allocation enables hardware prefetchers to establish clear access patterns, preloading cache lines ahead of computation. The operational intensity for the shared transformation phase is:
2N dou
Trnnsoorm (Nidin + din + do
(160)
where the numerator counts FLOPs (each element requires a dot product of length din) and the denominator accounts for bytes transferred (input features, weights, output features). For typical dimensions where N " da dour. this simplifies to:
2dindou
Transforrm Rd
(161)
(din + doa)) )
For dun dout d, we obtain Iransform R d/(23), which grows linearly with feature dimension. For moderate d 2 64, this operational intensity approaches exceeds Indges transitioning the computation from memory-bound to compute-boule bound regime where GPU arithmetic units are fully utilized.
F33.2 Fixed Fixes-DDimessinaality Dynamic Routing: Preserving the Working Set
GAMMA's dynamic routing mechanism computes adaptive combinations of multi-hop embeddings while maintaining fixed output dimensionality. Given hop-specific embeddings (Hx 1K where H₂ E N NNNxda the routing mechanism computes normalized embeddings:
HA
H
k 10, (,.,,,,K),, K),
(162)
H 2 +
where normalization operates row-wise and prevents division by zero. The iterative routing process computes agreement scores between each node's current representation z, and candidate hops:
ike = (z," hw)):
(163)
followed by softmax normalization:
exp(a!") Σe= expla!")
Wik
(8)
(164)
K
and weighted aggregation:
K
(t+1) z
wik
hag-
(165)
k=
The critical architectural insight is that all intermediate representations z maintain constant dimen- sion dou throughout routing iterations. The memory footprint for routing state is:
Mooning
-N (K 2),
(166)
40

---

accounting for K + +1 hop embeddings plus the current routing state. This contrasts sharply with concatenation- based approaches where memory grows as (2K + d For graphs where Muuting < C1.,, the entire routing computation can proceed with all data resident in 1.2 cache, eliminating DRAM traffic. The routing iterations involve primarily element-wise operations (dot products, exponentials, multiplications) on vectors of length K + 1, which exhibit high arithmetic intensity and minimal memory traffic. Each routing iteration requires approximately:
Touting Taot + Tsoftmax + nggrregat
(167)
where each component scales as (N with small constants. The softmax over K + 1 elements per node is efficiently parallelized across thread blocks, with each warp handling multiple nodes simultancously. Critically, the fixed dimensionality enables the entire routing loop to be fused into a single GPU kernel, maintaining all state in fast memory (shared memory registers) throughout iterations. This fusion eliminates (T - kernel launches for routing iterations and prevents intermediate memory transactions.
F.3.3 Kernel Fusion and Memory Traffic Reduction
The elimination of explicit concatenation enables aggressive kernel fusion throughout GAMMA's forward and backward passes. Consider the sequence of operations in a single layer: initial trans- formation, multi-hop propagation, normalization, and routing. In concatenation based architectures, each operation requires separate kernel launches with intermediate results materialized in global memory. The memory traffic for this sequence is:
D Dunfused
S (reads; + writes:),
(168)
where S; represents the size of intermediate tensor i and each operation i requires reading its inputs and writing its outputs. In a fused kernel, intermediate values remain in fast memory, reducing traffic to:
D Diused = Sippt + Soutput
(169)
representing only the initial inputs and final outputs. The traffic reduction factor is:
Yusion
Dunfused
-==1
S (reads; + writes:)
(170)
Dissed
Simput + Soutpat
For typical deep learning operations with multiple intermediate tensors, Musion ranges from 2 to 10, directly translating speedup when memory-bound. GAMMA's architecture maximizes fu- sion opportunities by maintaining fixed tensor dimensions and eliminating operations that force materialization.
Furthermore, the normalized dot-product agreement mechanism in Eq. (163) exhibits excellent vectorization properties. Modern GPUs execute operations in warps of W 32 threads that execute in lockstep (SIMD fashion). Dot products over vectors of length dout can be efficiently parallelized using warp-level reduction primitives, achieving near-peak throughput. The absence of conditional branches or data-dependent control flow ensures full warp utilization without divergence penalties. When threads within a warp execute different code paths (divergence). all paths must be serialized, degrading throughput by up to W-lold. GAMMA's routing mechanism, being purely data mata-parallel with uniform control flow, avoids this pathology entirely.
F,4 Theoretical Memory Bandwidth Bounds
We now establish formal bounds on the memory bandwidth requirements for multi-hop GNN architectures and demonstrate that GAMMA operates near the theoretical minimum. Consider multi-hop GNN layer processing a graph with N' nodes, K + hops, input dimension din, and output dimension dout- The fundamental operations are: (1) feature transformation, (2) multi-hop propagation, and (3) aggregation. The minimum data movement, assuming perfect cache behavior and no recomputation,
Dmin = 3 dnn + diadout + N Nouu).
(171)
representing reading input features, reading weights, and writing output features. Any architecture must satisfy D > Dmin-
41

---

For concatenation-basee architectures, the actual data movement includes reading imput features, reading (K + 1) weight matrices, writing (K + 1) intermediate hop results, reading these for concatenation, and writing the concatenated result:
D Dooncat ((Vdm + (K + 1)dma
+ (K + 1)N dout + +K 1)
(172)
+ (K + 1)Ndoa...
Simplifying:
Demcan B(Ndin + (K + 1)dindow + 3(K 1)Ndmm).
(173)
For GAMMA with weight sharing and fixed dimensionality, the data movement is:
DAAMA = (N + din + (K + 1) + _Nooo):
(174)
accounting for reading inputs, reading the single weight matrix, writing and reading hop embeddings (routing operates in-place on normalized copies), and writing the final output. The bandwidth efficiency ratio is:
DGAMMA
Nd + don + (K + N
P
Deoncat
Nd + (K + 1)di + 3(K + 1)
(175)
In the regime where N >> dins doat (typical for large graphs), the weight matrix terms become negligible:
di + (K + 2)
2
(176)
dm + 3(K + 1)dam
For din dout and K 2:
5d
p
0.5,
(177)
10d
demonstrating that GAMMA achieves approximately 2x reduction in memory bandwidth consump- tion compared to concatenation-bat approaches. This bandwidth efficiency directly translates to runtime improvement in the memory- -oound regime, execution time is inversely proportional to effective bandwidth utilization.
Empirical Validation and Architectural Insights
The theoretical efficiency gains manifest in measured performance on real hardware. Our experiments
on the Flickr dataset (N = 89,250 nodes) demonstrate that GAMMA achieves total execution time (forward plus backward pass) of TGAMMA 23.17 ms with memory footprint MGAMMA 480.60
MB. In contrast, MixHop requires MixHop 115.68 ms (5.0x slower) with MMixHop = 1,965.30 MB (4.1x larger), and H2GCN requires TH2GCN 463.89 ms (20.0x slower) with MH2GGN 1,993.90 MB (4.1x x larger). These measurements validate our theoretical analysis: the 4-5x memory reduction aligns with predictions from Eq. (175). and the runtime improvements reflect both reduced memory traffic and kernel launch overhead elimination.
The architectural implications extend beyond raw performance metrics. GAMMA's design phi- losophy, prioritizing algorithmic choices that align with hardware execution models, represents departure from the prevailing trend of increasing architectural complexity to capture graph het- erophily. Rather than expanding feature dimensions or introducing intricate attention mechanisms, GAMMA achieves adaptivity through a lightweight routing process that maps efficiently onto GPU execution units. The normalized dot-product agreement computation vectorizes naturally, the softmax operation parallelizes across nodes, and the weighted aggregation fuses with downstream opera- tions. This hardware-algorithm co-design demonstrates that sophisticated functionality need not sacrifice efficiency; indeed, by respecting the constraints of the memory hierarchy and the parallelism model GPUs, GAMMA achieves both greater expressiveness and superior performance relative to architectural approaches that ignore these fundamental constraints.
The lesson for future GNN architecture design clear: algorithmic innovation must pursued in concert with hardware considerations. Choices that appear benign from purely mathematical perspective, concatenation, separate weight matrices, expanding dimensionality, carry hidden costs that accumulate throughout the memory hierarchy. By contrast, designs that maintain fixed working
42

---

set sizes, maximize parameter reuse, enable kernel fusion, and exploit vectorization opportunities achieve superior efficiency without compromising model capacity. GAMMA exemplifies this princi- ple, demonstrating that careful architectural co-design enables heterophilic graph learning at scale on commodity hardware.
43

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). ). general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the paper's ' main contributions:
(1) gated multi-ho hop message passing mechanism that adaptively leverages nulti-hop neighborhood information based on node-specific heterophilic patterns, (2) a weight sharing scheme that reduces memory overhead while preserving global heterophilic information, and (3) experimental results showing GAMMA matches or exceeds SOTA heterophilic GNN accuracy while achieving up to 20x faster inference. These claims are supported by the empirical results in Section and the theoretical analysis in Sections 3-4. Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals not attained by the paper.
44

---

2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper briefly discusses limitations in the conclusion section: GAMMA's current fixed routing iteration count may be suboptimal for nodes with varying neighborhood complexities, and extremely large graphs may require further optimizations to the gating mechanism. Additionally, while our dot-produce agreement measure works well in practice, more sophisticated routing strategies might better capture particularly complex heterophilic relationships. While not in dedicated section, the paper acknowledges key technical limitations related to routing iterations, scalability to extremely large graphs, and potential for more sophisticated agreement measures.
Justification;
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [NA]
Justification: This paper focuses the empirical effectiveness of the GAMMA approach for node classification heterophilic graphs rather than developing theoretical guarantees. The work emphasizes practical performance, computational efficiency, and experimental validation across diverse benchmark datasets, without relying on theoretical proofs as part of its core contributions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
45

---

The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper provides comprchensive information for reproducing the main experimental results. Section describes the GAMMA architecture in detail, with complete pseudocode provided in Algorithm in the Appendix. The experimental setup is thoroughly documented in Section 5, including implementation details (PyTorrc Geometric, NVIDIA RTX A2000 GPU, CUDA 12.8), model architecture specifications (two GNN layers with hidden dimension size of 32), hyperparameter optimization process (grid search over learning rates in 0.05, 0.01, 0.002 and dropout rates in 0.0, 0.5), training protocol (500 epochs), and evaluation methodology (10 splits with specified ratios). All datasets are clearly listed with their properties in Table 1, and baseline models are properly referenced.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
46

---

Answer: [Yes]
Justification: The code implementing GAMMA and scripts to reproduce all experimental results will be made publicly available and provided to the conference. All datasets used in our experiments are standard benchmark datasets (Cora, CiteSeer, PubMed, Texas, Wisconsin, Actor, Squirrel, Chameleon, Cornell) that are publicly available through the PyTorch Geometric library, which is properly cited in the paper. The implementation is based on the detailed algorithm description in Section and the complete pscudocode in Algorithm 1, with all experimental settings documented in Section 5.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips //nips.cc/ppp https/ccccccblcguuuueeeeeeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper provides comprehensive experimental details in Section 5. It specifies the architecture configuration (two GNN layers with hidden dimension size of 32), hyperparameter optimization process (grid search over learning rates in 0.05, 0.01, 0.002 and dropout rates 0.0, 0.5), training protocol (500 epochs), and model selection criteria (best validation performance). Data splitting procedures are clearly described for both heterophilic datasets and homophilic datasets. Implementation framework (Py Torch Geometric) and hardware specifications (NVIDIA RTX A2000 GPU with CUDA 12.8) are also documented, providing sufficient detail to understand and contextualize the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The paper reports standard deviations as error bars for all classification accuracy results in Table 1, calculated across 10 different data splits for each datasct. The
47

---

methodology for obtaining these statistics is clearly described in Section (Evaluation). The evaluation methodology follows established practices the field and is properly cited in the evaluation section. This approach captures variability across different data splits, providing a reliable measure of model robustness.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If eгror bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper provides detailed information on compute resources in Section 5. specifies that experiments
conducted "a desktop machine equipped with an NVIDIA RTX A2000 GPU (12GB VRAM)" using "CUDA 12.8" for GPU acceleration. The paper also presents comprehensive resource utilization metrics in Figure comparing memory consumption and execution time across all models. For GAMMA specifically, it reports "a total execution time (backward forward pass) of 23.17 ms and memory footprint of 480.60 MB." The performance benchmarks are detailed for all 13 baseline models, providing a clear picture the relative computational requirements for reproducing the experiments. Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research in this paper conforms with the NeurlPS Code of Ethics. The work uses public benchmark datasets with proper attribution, presents transparent and
48

---

statistically sound evaluations, and focuses on improving computational efficiency of graph neural networks without raising ethical concerns. The algorithms and models proposed do not pose risks related to privacy, bias, or potential misuse. The research aims to make graph neural networks more computationally efficient and effective on heterophilic graphs, which aligns with ethical considerations regarding responsible resource usage in machine learning research.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The paper does not explicitly discuss socictal impacts. This work is primarily
foundational machine learning research focused improving computational efficiency and effectiveness of graph neural networks for heterophilic graphs. While not discussed in the paper, potential positive impacts include reduced computational resource requirements (benefiting researchers with limited resources and reducing energy consumption) and en- abling more effective modeling in areas like fraud detection networks. The research does not present direct negative societal impacts as it focuses on algorithmic improvements rather than specific applications, though with any ML advancement, applications built with these methods should be evaluated for potential biases or misuse in specific downstream contexts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
49

---

Justification: The paper presents an algorithm for graph neural networks that poses no particular risk for misuse. The research uses standard benchmark datasets that are already publicly available and does not involve high-risk technologies such as language models, image generators, or scraped datasets. The proposed method an algorithmic advancement focused on efficiency and effectiveness of graph neural networks for heterophilic graphs, without introducing technologies that would require specific safeguards against misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [No]
While the paper properly credits creators by citing the original papers for datasets (Cora, CiteSeer, PubMed, etc.) and software tools (Py (PyTorch Geometric, CUDA), it does not explicitly mention the specific licenses (MIT, Apache, etc.) under which these assets are available. The paper appropriately references all baseline models through citations to their original papers, but does not include license information for any of these resources. Although these standard academic benchmarks and publicly available frameworks commonly used the research community, explicitly stating their licenses would improve completeness and transparency.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsssippppetteeeeeeeoe thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The paper introduces new GNN architecture (GAMMA) which is thoroughly documented within the paper itself. Section 4 provides detailed description of the GAMMA method, Section 5 gives implementation details, and the Appendix includes comprehensive
50

---

pseudocode in Algorithm I that outlines the full forward pass process. This documentation is sufficient for implementing the method. Additionally, mentioned in previous responses, code implementing GAMMA will be made available and provided to the conference with appropriate documentation facilitate reproducibility and usage by other researchers.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research with human subjects. The research focuses developing and evaluating graph neural network algorithms standard benchmark datasets. All experiments were computational nature, testing the proposed GAMMA approach against baseline methods on publicly available graph datasets, without any human participant involvement.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
This research does not involve human subjects. The paper presents algorithmic research on graph neural networks with experiments conducted exclusively on standard benchmark datasets. No human participants were involved any aspect of the study, so IRB approval was not required or applicable.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
51

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
This research does not involve LLMs as any component of the methodology. The paper focuses entirely on graph neural networks for heterophilic graphs, specifically introducing the GAMMA method that employs gating mechanism for multi-hop mes- sage passing, No language models were used in developing the approach or conducting experiments.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve L.MMs as any important, original, or non-standard components.
Please refer to our LLM policy http:////eurrips.cc//aaeeerrrree for what should or should not be described.
52


Reviews:
[{"review_id": "1Zdx0dZJau", "reviewer": "Reviewer_hXHc", "summary": "The paper demonstrates through comprehensive empirical analysis that state of the art GNNs are not computationally efficient in memory and runtime. To address these limitations authors propose GAMMA that leverages multihop gated message passing and weight sharing across hops to reduce both memory and runtime. GAMMA is show to match or exceed state of the art GNNs on homophilous and heterophilous benchmarks.", "questions": "1. How does GAMMA perform on larger datasets in comparison to state of the art GNNs?\n2. Are state of the art GNNs feasible to train on larger datasets given a reasonable budget of compute, time, and memory?\n3. How are GAMMAs designs (gated multihop message passing and shared weight across hops) related and different to designs proposed in the literature?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n1. The problem is well-motivated and a fair and rigorous comparison of memory/runtime requirements for state of the art GNNs is a gap in the literature as far as I'm aware. Often times, this is an overlooked aspect in GNN design.\n2. The two designs are intuitive. It is clear how they address and mitigate the memory/runtime issues of state of the art GNNs\n3. The paper is clear and well written. \n\n**Weaknesses**\n1. My main weakness is the evaluation. The paper does a good job setting up the problem and also demonstrating the runtime and memory requirements across many state of the art GNNs, but only evaluates on relatively small datasets (table 1). Texas, Cornell, and Wisconsin each range in 100s of nodes with some dataset construction issues (e.g. only one node per class). Squirrel and Chameleon have been identified as having issues as well with many duplicate nodes, leading to test set leakage [1]. There have been many proposed heterophilous datasets since these original smaller ones [1, 2]. Since memory and runtime are the main motivation, I think it would be good to include (i) GAMMAs performance on these larger datasets and also (ii) comparisons to state of the art GNNs on these larger datasets since the large datasets are where these factors play the most important role. These would address questions I have about if GAMMA's performance remains matched with state of the art for larger datasets. I would also be very interested to see a fair and rigorous comparison of the feasibility of training large scale GNNs. is it the case that expensive GNNs like H2GCN is infeasible to train with even a moderate amount of compute, memory, and runtime? If so, I think these would make the contributions stronger. \n2. I was also wondering how novel the designs are (multihop gating and weight sharing across hops)? It seems that these have been used in the literature each individually and comparing your specific designs to others that are similar would be helpful to appreciate the contributions. \n\n[1] Platanov et al., A critical look at the evaluation of GNNs under heterophily: Are we really making progress?\n[2] Lim et al., Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods", "was_revised": true, "final_justification": "My initial concerns about scalability and novelty are mostly resolved. On the scalability front, the authors did an excellent job in the rebuttal with positive results for their method and also important findings about the feasibility of other popular methods. This is also an overlooked component in GNN papers. On the novelty front, I don't think the designs are highly novel and I still think they are quite close to existing models in the literature, most notably GPR-GNN, but the authors have argued that there are key differences in their approach and have demonstrated that GAMMA's performance is higher than GPR-GNN across a range of benchmarks. I have thus increased my score from 3 to 4.", "rebuttal": "We appreciate the reviewer’s constructive feedback. Below we address each concern with comprehensive experiments and analysis.\n\n1. **Scalability on Large‑Scale Datasets**  \nThe reviewer’s primary concern is that our evaluation is limited to smaller datasets, questioning whether GAMMA’s performance holds on larger graphs where memory and runtime are paramount. To address this, we have benchmarked GAMMA and a comprehensive set of baselines on seven large‑scale heterophilic graphs.\n\n$$\n\\\\begin{array}{l|ccccccc}\n\\\\hline\n& \\\\text{ogbn-arxiv} & \\\\text{roman-empire} & \\\\text{ogbn-products} & \\\\text{minesweeper} & \\\\text{amazon-ratings} & \\\\text{amazon-photos} & \\\\text{tolokers} \\\\\\\\\n\\\\hline\n\\\\text{MLP}   & 47.34 \\\\pm 0.09 & 65.37 \\\\pm 0.58 & 43.20 \\\\pm 0.01 & 79.48 \\\\pm 0.21 & 38.35 \\\\pm 0.20 & 48.73 \\\\pm 1.80 & 78.16 \\\\pm 0.00 \\\\\\\\\n\\\\text{GCN}   & 64.91 \\\\pm 0.26 & 54.16 \\\\pm 0.28 & \\\\mathbf{71.31 \\\\pm 0.16} & 80.31 \\\\pm 0.24 & 42.12 \\\\pm 0.29 & 52.14 \\\\pm 1.50 & 78.76 \\\\pm 0.17 \\\\\\\\\n\\\\text{SGC}   & 63.47 \\\\pm 0.16 & 61.20 \\\\pm 0.65 & \\\\text{OOM} & 80.05 \\\\pm 0.03 & 41.61 \\\\pm 0.72 & 57.97 \\\\pm 0.52 & 78.56 \\\\pm 0.19 \\\\\\\\\n\\\\text{GCN2}  & 61.96 \\\\pm 0.42 & 64.96 \\\\pm 0.38 & 61.08 \\\\pm 0.18 & 82.80 \\\\pm 0.35 & 47.20 \\\\pm 0.55 & 94.10 \\\\pm 0.25 & 79.80 \\\\pm 0.30 \\\\\\\\\n\\\\text{GCNJK} & 70.19 \\\\pm 0.11 & 62.18 \\\\pm 0.91 & 69.46 \\\\pm 0.33 & 85.15 \\\\pm 0.42 & 48.77 \\\\pm 0.37 & 95.28 \\\\pm 0.05 & \\\\mathbf{81.23 \\\\pm 0.26} \\\\\\\\\n\\\\text{GATJK} & \\\\mathbf{70.75 \\\\pm 0.19} & 70.00 \\\\pm 0.70 & \\\\text{OOM} & \\\\mathbf{85.65 \\\\pm 0.34} & \\\\mathbf{50.84 \\\\pm 0.52} & 95.71 \\\\pm 0.11 & \\\\mathbf{81.31 \\\\pm 0.48} \\\\\\\\\n\\\\text{H2GCN} & \\\\text{OOM} & 75.89 \\\\pm 0.55 & \\\\text{OOM} & 83.31 \\\\pm 0.65 & 42.90 \\\\pm 0.38 & 84.95 \\\\pm 0.38 & 79.39 \\\\pm 0.42 \\\\\\\\\n\\\\text{GAT}   & 70.01 \\\\pm 0.09 & 74.50 \\\\pm 0.45 & \\\\text{OOM} & 81.52 \\\\pm 0.26 & 48.89 \\\\pm 0.61 & 95.56 \\\\pm 0.15 & 78.63 \\\\pm 0.06 \\\\\\\\\n\\\\text{MixHop}& 70.27 \\\\pm 0.14 & \\\\mathbf{82.20 \\\\pm 0.31} & \\\\text{OOM} & 84.88 \\\\pm 0.45 & \\\\mathbf{50.98 \\\\pm 0.30} & \\\\mathbf{96.34 \\\\pm 0.30} & 81.03 \\\\pm 0.70 \\\\\\\\\n\\\\text{BernNet}& 63.15 \\\\pm 0.13 & 66.27 \\\\pm 0.35 & \\\\text{OOM} & 80.00 \\\\pm 0.07 & 40.90 \\\\pm 0.09 & 62.34 \\\\pm 7.02 & 78.16 \\\\pm 0.00 \\\\\\\\\n\\\\text{GPRGNN}& 67.66 \\\\pm 0.07 & 69.60 \\\\pm 0.40 & \\\\mathbf{73.26 \\\\pm 0.65} & 80.36 \\\\pm 0.19 & 43.44 \\\\pm 0.13 & 79.54 \\\\pm 0.39 & 78.36 \\\\pm 0.10 \\\\\\\\\n\\\\text{M2MGNN}& \\\\mathbf{72.52 \\\\pm 0.10} & \\\\mathbf{80.81 \\\\pm 0.70} & \\\\text{OOM} & \\\\mathbf{85.83 \\\\pm 0.25} & \\\\mathbf{50.57 \\\\pm 0.29} & \\\\mathbf{95.73 \\\\pm 0.25} & 80.66 \\\\pm 0.47 \\\\\\\\\n\\\\text{GAMMA} & \\\\mathbf{71.81 \\\\pm 0.19} & \\\\mathbf{81.37 \\\\pm 0.25} & \\\\mathbf{72.61 \\\\pm 0.04} & \\\\mathbf{87.58 \\\\pm 0.25} & 49.07 \\\\pm 0.65 & \\\\mathbf{96.28 \\\\pm 0.11} & \\\\mathbf{82.59 \\\\pm 0.41} \\\\\\\\\n\\\\hline\n\\\\end{array}\n$$\n\nThe table demonstrates GAMMA's consistently high performance on large-scale heterophilic graphs, achieving state-of-the-art comparable results and often the best or second-best accuracy across 5 out of 7 datasets, showcasing its effectiveness at scale. The models were trained for 500 epochs across 5 random splits, using a 60/20/20 train/validation/test split, with all models utilizing the same learning rate, dropout, and weight decay, and their baseline GNN implementations without additional architectural enhancement or residual connections. As shown, many state-of-the-art models encountered Out-Of-Memory (OOM) errors, particularly on larger datasets like ogbn-products, due to architectural choices such as explicit concatenation of feature representations (e.g., H2GCN, JK-Nets) or complex per-edge operations (e.g., M2MGNN) that lead to a significant increase in feature dimensionality or large intermediate tensors. GAMMA addresses these issues through weight sharing to maintain a coherent feature space, dynamic gating for selective and efficient hop information propagation, and streamlined message passing that discards redundant information, enabling it to scale effectively.\n\n2. **Feasibility of Training Large‑Scale Heterophilic Graphs on Commodity GPUs**  \nOur primary goal was to enable full‑batch training for heterophilic graphs, designing for efficiency from the start, rather than treating it as an afterthought. Unfortunately, with commodity GPUs like the NVIDIA A2000 (12 GB VRAM), many state‑of‑the‑art models fail even on medium‑scale datasets like *roman‑empire* (22.7 K nodes, 32.9 K edges). For fair comparison on larger datasets, we employed an NVIDIA A100 with 80 GB memory to enable full‑batch training for prior work as well. However, even with this substantial memory, resource‑hungry models still encounter Out‑Of‑Memory (OOM) errors on large‑scale datasets like *ogbn‑products* (2.4 M nodes, 61 M edges). The OOM failures for such models stem directly from their architectural choices: \n\n• Concatenation‑based models (H2GCN, MixHop, GCN/GAT‑JK): These explicitly concatenate feature representations from different hops or layers. H2GCN’s final representation size explodes to \\\\((2^{k+1}-1) \\\\times \\\\text{hidden\\\\_channels}\\\\), MixHop expands channel dimensions at each layer (\\\\(\\\\text{hidden\\\\_channels} \\\\times 3\\\\)), and JK‑Nets concatenate outputs from all layers. This linear or exponential growth in feature dimensionality is fundamentally unscalable.  \n\n• Complex Propagation/Aggregation (BernNet, M2MGNN): BernNet’s K‑th order filter requires K distinct propagation steps, storing all intermediate results. M2MGNN performs complex per‑edge operations (MLP and segmented softmax), creating large intermediate tensors prohibitive on graphs with millions of edges. \n\n**GAMMA’s Solution:** Our method addresses these issues through: (1) weight sharing that maintains a single coherent feature space rather than expanding dimensions, (2) dynamic gating that selectively propagates only informative hop information, eliminating the need for feature concatenation, and (3) efficient message passing that discards redundant information while preserving essential multi‑hop patterns.\n\n3. **Novelty and Technical Contributions**  \n\nWhile concepts like “gating” and “weight sharing” exist individually, GAMMA’s novelty lies in their unique synthesis and specific design for heterophilic graphs. We provide detailed positioning in Appendix A.3 submitted in the supplementary material.  \n\n**Weight Sharing Across Hops:** Our approach differs fundamentally from simple parameter reduction. By applying a single shared linear projection \\\\(W\\\\) before propagation, we ensure all hop‑specific embeddings \\\\(H^{(p)}\\\\) reside in a coherent, shared geometric space, a critical prerequisite for our gating mechanism’s dot‑product agreement measure. Architectures using independent hop‑specific weights \\\\(W^{(p)}\\\\) map features to potentially unrelated latent spaces, making direct comparisons ill‑defined. Our lightweight, learnable scaling vectors \\\\(\\\\gamma_p\\\\) reintroduce hop‑specific adaptability without fracturing this shared space.  \n\n**Gated Multi‑hop Message Passing:** Our new design is the dynamic, node‑specific, and iterative gating mechanism, fundamentally different from existing approaches:  \n\n• Comparison with Spectral Methods (GPRGNN, BernNet): These learn global polynomial filter coefficients applied uniformly across the graph. GAMMA’s gating coefficients \\\\(\\\\alpha_{i,p}\\\\) are computed per‑node and activation‑driven, recalculated in each forward pass to adapt to specific local structures around each node. \n \n• Comparison with JK‑Nets (GCNJK, GATJK): JK‑Nets aggregate representations from different layers at the network’s end using mechanisms like max or concatenation. GAMMA’s gating iteratively refines hop contributions based on agreement within the message‑passing layer itself, enabling more nuanced information fusion.  \n\n• Comparison with GAT: GAT computes attention over a node’s 1‑hop neighborhood to weigh individual neighbors. GAMMA operates at a higher abstraction level, weighing aggregated messages from entire hop‑distances rather than individual neighbors.\n\nAdditionally, the theoretical analysis in Appendix A.4 (provided in the supplementary material) further demonstrates how this design enables adaptive information propagation while maintaining computational efficiency."}, {"review_id": "OqsebG3FkX", "reviewer": "Reviewer_QbS7", "summary": "The authors propose a new architecture for multi-hop aggregation graph learning. Previous work captured heterophilic patterns in graphs by concatenating $p$-hop neighborhoods but this approach often suffers from high memory requirements. The authors instead propose a gated multi-hop message passing mechanism (GAMMA) which essentially involves computing a weighted sum of hop embeddings (gating coefficient dictate the weights in the sum), thereby avoiding concatenation. Additionally, there is an iterative update for the gating coefficient that happens each forward pass of GAMMA. GAMMA is evaluated against a variety of standard message passing NNs and k-hop message passing NNs and shows competitive classification accuracy with greater efficiency (in terms of memory and inference time)", "questions": "1. How are the hop-specific embeddings generated? Is the GAMMA layer something that comes after standard multi-hop message passing layer? Is it that if I have a node $v$ and its $p$-hop neighbors $\\mathcal{N}^p$ with some computed embeddings, there is some gating coefficient $s_i^{(t)}$ learned per $p$-hop neighborhood and then the new node feature is generated by taking a weighted sum over the $p$-hop neighbors with the gating coefficients as the weights? I guess the gating coefficient is based on by the set of gating logits $b_i$ but are these gating logics learned? I think there is a good summary of GAMMA's gating mechanism in lines 381-384 that maybe should have been moved to the earlier section where GAMMA is introduced. \n2. Is there any additional computation cost during training time due to the $R$ routing iterations for the GAMMA gating mechanism? Can the number of iterations can be controlled in some data-drive way (see [1] where they control the number of iterations through another learnable MLP module)? \n3. It seems that the performance for GAMMA suffers a bit on homophilic datasets (which makes sense because the focus of GAMMA is for heterophilic benchmarks) but is there a way to see how the performance of GAMMA changes as the level of homophily in the datasets change? \n\n[1] \"Towards scale-invariant graph-related problem solving by iterative homogeneous gnns\"", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- Strong experimental baseline comparisons and the tables regarding computation efficiency are convincing. GNNs often suffer from long training times (especially on large graphs) since a forward pass depends on the number of nodes/edges in the input graph. This is probably even more of a problem with multi-hop GNNs so the efficiency of GAMMA (I think due to the fact that they avoid the computational cost associated with concatenation of multi-hop node features) as compared to previous multi-hop techniques seems significant. \n\n**Weaknesses** \n- Explanation of GAMMA is a bit unclear, I have some questions below that hopefully the authors can clarify. \n- Minor typo: in table 1, I think GCN shows the best accuracy for CiteSeer and should be highlighted in green.", "was_revised": true, "final_justification": "The authors addressed my initial questions. I think GAMMA shows convincing performance gains in terms of efficiency (especially the faster inference as compared to current SoTA models). However, as mentioned by Reviewer DJEL, it seems that GAMMA's improvements on heterophilic datasets (especially large scale datasets) still leave something to be desired. When balancing these two points, I would like to keep my original score of 4.", "rebuttal": "We sincerely thank the reviewer for the positive assessment of our work, particularly for recognizing the significance of GAMMA's efficiency and the strength of our experimental comparisons. We also appreciate the meticulous review and thoughtful questions, which will help us improve the paper's clarity.\n\nRegarding the minor typo in Table 1, indeed GCN shows the best accuracy for CiteSeer and should be highlighted in green. Thank you for catching this; we will make this correct.\n\nBelow, we address the questions in detail.\n\n1. Clarification of the GAMMA Mechanism\n\nThank you for these detailed questions; they highlight areas where we can be clearer in our explanation. The GAMMA layer is a self-contained module that integrates multi-hop propagation and adaptive gating. To break down the process step-by-step and for a more formal description, we also refer to the pseudocode in Algorithm 1 (Appendix A.2 provided in the supplementary material).\n\n- How are the hop-specific embeddings generated? The hop-specific embeddings $H^{(p)}$ are generated using a standard multi-hop aggregation process. First, all node features $X$ are projected into a common embedding space via a shared linear transformation, $H = XW$. From there, we generate the features for each hop distance by iteratively applying the graph propagation operator (the normalized adjacency matrix $A$). For instance, the process is as follows:\n\nThe 1-hop embedding is calculated as $H^{(1)} = AH$.\nThe 2-hop embedding is then $H^{(2)} = A(H^{(1)}) = A(AH)$.\nThe 3-hop embedding follows as $H^{(3)} = A(H^{(2)}) = A(A(AH)) = A^3H$.\n\nThis iterative propagation, formally expressed as $H^{(p)} = A H^{(p-1)}$, is used to aggregate information from higher-order neighborhoods. It is conceptually similar to aggregation strategies used in other multi-hop models like MixHop or H2GCN, which also leverage powers of the adjacency matrix. GAMMA integrates this standard propagation step before applying its novel gating mechanism.\n\n- How are the gating coefficients generated and are the logits learned? As mentioned by the reviewer, it is correct that the final node feature is a weighted sum of the hop embeddings. However, a key distinction is that the gating coefficients $\\alpha_{i,p}$ are not learned parameters in the traditional sense. They are dynamically computed for each node $i$ during every forward pass through an iterative refinement process.\n\nFor each node $i$, we initialize a vector of gating logits $b_i$ to all zeros. In the first iteration, passing these zero logits through a softmax function results in uniform coefficients $\\alpha_{i,p} = 1/(K+1)$, ensuring all hops are treated equally at the start. Next, in each routing iteration $t$, we compute a temporary node representation $v_i^{(t)}$ by taking a weighted sum of the hop embeddings using the current coefficients and applying a squash normalization function. We then measure the agreement between this representation and each hop's embedding via a dot product: $H_{i}^{(p)} \\cdot v_{i}^{(t)}$. This agreement score directly updates the logits: $b_{i,p}^{(t+1)} = b_{i,p}^{(t)} + \\text{agreement}$. If a hop's embedding aligns well with the node's evolving representation, its corresponding logit increases, which in turn increases its influence in the next iteration. After $R$ iterations, the final representation $v_i^{(R)}$ is used as the output of the GAMMA layer.\n\nSo, to summarize, the gating logits are not learned via backpropagation; they are iteratively refined on-the-fly based on feature agreement during the forward pass. This allows each node to adapt its information aggregation strategy based on its specific local neighborhood structure.\n\n- Organization Suggestion: Thank you for this suggestion. We agree that the summary in lines 381-384 provides a very clear overview of the global vs. local adaptation mechanism. We will revise the manuscript to move this explanation to an earlier point in Section 4 to improve the clarity and flow of the introduction to GAMMA.\n\n\n2. Computational Cost and Data-Driven Iterations\n\n- The $R$ routing iterations do introduce an additional computational step. However, this overhead is minimal and the design is highly efficient for two key reasons:\n\nLightweight Operations: The operations inside the routing loop (dot products, softmax, weighted sums) are performed on small, fixed-size tensors ($d_{out}$-dimensional vectors). These are highly parallelizable and computationally cheap compared to the main graph convolution operations.\n\nMemory Efficiency: Crucially, GAMMA avoids feature concatenation. Unlike models like H2GCN or MixHop that expand feature dimensionality to $(K+1) \\times d_{out}$ , GAMMA maintains a single output vector of dimension $d_{out}$. This prevents the creation of large intermediate tensors, which is a primary cause of high memory usage and long latency in GNNs due to irregular memory access patterns. This design choice is why GAMMA achieves significant speedups (up to 20x) and memory savings (up to 12x).\n\n- Data-Driven Control of Iterations: In our current framework, the number of iterations $R$ is a fixed hyperparameter. Our ablation study in Appendix A.1 shows that performance is robust and typically optimal with a small, fixed $R$ (e.g., 2-4 iterations). \n\n- Introducing a learnable module to control: $R$ in a data-driven way is a potential direction for future research. It could offer finer-grained control at the cost of increased model complexity. \n\n3. Performance on Homophilic Datasets\n\nThis is an important point about the model's generalizability. Our goal with GAMMA was to create a homophily-agnostic model, not one that is purely specialized for heterophily. The experimental results in Table 1 show that GAMMA performs very competitively on homophilic benchmarks. It achieves the best accuracy on PubMed ($89.62\\%$) and is on par with the top performers on Cora ($87.42\\%$). This demonstrates that the adaptive gating mechanism is not detrimental when strong homophilic signals are present. In such cases, the routing mechanism simply learns to assign the highest weights to the 0-hop (self-features) and 1-hop embeddings, effectively recovering the behavior of a standard GNN.\n\nThe performance across the spectrum of datasets in Table 1 illustrates how GAMMA's performance changes with the level of homophily. While many standard GNNs see a sharp performance drop when moving from homophilic graphs (e.g., Cora, ratio 0.81) to heterophilic ones (e.g., Texas, ratio 0.11), GAMMA maintains strong and often state-of-the-art results across the board. This robustness is a key strength of its adaptive design, allowing it to excel regardless of the underlying graph structure."}, {"review_id": "lnDuLIEOyS", "reviewer": "Reviewer_1qWb", "summary": "The paper introduces gated multi-hop message passing (GAMMA) as a method for efficient node classification on heterophilic graphs. Compared to existing methods, GAMMA provides a 20x improvement in inference speed and achieves comparable performance to the state-of-the-art. The efficiency of this method comes from a novel gating mechanism which avoids the need for feature concatenation, and the introduction of a weight sharing scheme.", "questions": "Could you include some evaluation of GAMMA on larger scale graphs or at least some discussion of why this not included?\n\nIs the absence of evaluation on larger scale graphs due to any limitations in scaling up GAMMA?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n-\tThe paper introduces GAMMA to tackle the known and relevant problem of GNN performance and efficiency on heterophilic graphs and provides convincing evidence that GAMMA can address these issues.\n-\tGAMMA is well motivated and explained intuitively through the use of figures.\n-\tThe paper is very clear and well written.\n\n**Weaknesses:**\n\n-\tThe evaluation of GAMMA is limited to small scale graphs. Evaluation on larger scale heterophilic graphs like the ones discussed in Lime et al. 2021 or Platonov 2023 would provide stronger support for the applicability of this method in realistic settings.\n-\tThe conclusion briefly mentions limitations for \"extremely large graphs\". Further discussion of this and other limitations would improve the paper and make its scope clearer.\n-\tA figure showing both classification accuracy and computation time would be welcome to make clear, for example, that while GCN-JK has a comparable computation time to GAMMA, it has significantly lower accuracy across the selected datasets. A figure highlighting the compute to accuracy trade-off would prevent the reader from having to go back and forth from Table 1 to Figure 5.\n\n\nLim, D., Hohne, F. M., Li, X., Huang, S. L., Gupta, V., Bhalerao, O. P., & Lim, S.-N. (2021). Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In Advances in Neural Information Processing Systems. https://openreview.net/forum?id=DfGu8WwT0d\n\nPlatonov, O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova, L. (2023). A critical look at the evaluation of GNNs under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations. https://openreview.net/forum?id=tJbbQfw-5wv", "was_revised": true, "final_justification": "The authors have addressed my concerns about evaluation on larger scale graphs, and I am happy that the authors will incorporate the suggestions of this review in the revised paper. I maintain my score and recommendation that this paper be accepted.", "rebuttal": "We are grateful for your assessment of our work, and your constructive suggestions for improving the paper. We are especially pleased that you found GAMMA to be well-motivated and the paper to be clear and well-written.\n\n- Evaluation on Large-Scale Graphs:\n\nThe reviewer raised a critical point regarding the evaluation being limited to smaller graphs. Demonstrating scalability on larger benchmarks is crucial for validating GAMMA's applicability in realistic settings. To address this, we have benchmarked GAMMA against all of the baselines on seven larger heterophilic graphs, including those from the families of benchmarks mentioned by the reviewer:\n\n$$\n\\\\begin{array}{l|ccccccc}\n\\\\hline\n& \\\\text{ogbn-arxiv} & \\\\text{roman-empire} & \\\\text{ogbn-products} & \\\\text{minesweeper} & \\\\text{amazon-ratings} & \\\\text{amazon-photos} & \\\\text{tolokers} \\\\\\\\\n\\\\hline\n\\\\text{MLP}   & 47.34 \\\\pm 0.09 & 65.37 \\\\pm 0.58 & 43.20 \\\\pm 0.01 & 79.48 \\\\pm 0.21 & 38.35 \\\\pm 0.20 & 48.73 \\\\pm 1.80 & 78.16 \\\\pm 0.00 \\\\\\\\\n\\\\text{GCN}   & 64.91 \\\\pm 0.26 & 54.16 \\\\pm 0.28 & \\\\mathbf{71.31 \\\\pm 0.16} & 80.31 \\\\pm 0.24 & 42.12 \\\\pm 0.29 & 52.14 \\\\pm 1.50 & 78.76 \\\\pm 0.17 \\\\\\\\\n\\\\text{SGC}   & 63.47 \\\\pm 0.16 & 61.20 \\\\pm 0.65 & \\\\text{OOM} & 80.05 \\\\pm 0.03 & 41.61 \\\\pm 0.72 & 57.97 \\\\pm 0.52 & 78.56 \\\\pm 0.19 \\\\\\\\\n\\\\text{GCN2}  & 61.96 \\\\pm 0.42 & 64.96 \\\\pm 0.38 & 61.08 \\\\pm 0.18 & 82.80 \\\\pm 0.35 & 47.20 \\\\pm 0.55 & 94.10 \\\\pm 0.25 & 79.80 \\\\pm 0.30 \\\\\\\\\n\\\\text{GCNJK} & 70.19 \\\\pm 0.11 & 62.18 \\\\pm 0.91 & 69.46 \\\\pm 0.33 & 85.15 \\\\pm 0.42 & 48.77 \\\\pm 0.37 & 95.28 \\\\pm 0.05 & \\\\mathbf{81.23 \\\\pm 0.26} \\\\\\\\\n\\\\text{GATJK} & \\\\mathbf{70.75 \\\\pm 0.19} & 70.00 \\\\pm 0.70 & \\\\text{OOM} & \\\\mathbf{85.65 \\\\pm 0.34} & \\\\mathbf{50.84 \\\\pm 0.52} & 95.71 \\\\pm 0.11 & \\\\mathbf{81.31 \\\\pm 0.48} \\\\\\\\\n\\\\text{H2GCN} & \\\\text{OOM} & 75.89 \\\\pm 0.55 & \\\\text{OOM} & 83.31 \\\\pm 0.65 & 42.90 \\\\pm 0.38 & 84.95 \\\\pm 0.38 & 79.39 \\\\pm 0.42 \\\\\\\\\n\\\\text{GAT}   & 70.01 \\\\pm 0.09 & 74.50 \\\\pm 0.45 & \\\\text{OOM} & 81.52 \\\\pm 0.26 & 48.89 \\\\pm 0.61 & 95.56 \\\\pm 0.15 & 78.63 \\\\pm 0.06 \\\\\\\\\n\\\\text{MixHop}& 70.27 \\\\pm 0.14 & \\\\mathbf{82.20 \\\\pm 0.31} & \\\\text{OOM} & 84.88 \\\\pm 0.45 & \\\\mathbf{50.98 \\\\pm 0.30} & \\\\mathbf{96.34 \\\\pm 0.30} & 81.03 \\\\pm 0.70 \\\\\\\\\n\\\\text{BernNet}& 63.15 \\\\pm 0.13 & 66.27 \\\\pm 0.35 & \\\\text{OOM} & 80.00 \\\\pm 0.07 & 40.90 \\\\pm 0.09 & 62.34 \\\\pm 7.02 & 78.16 \\\\pm 0.00 \\\\\\\\\n\\\\text{GPRGNN}& 67.66 \\\\pm 0.07 & 69.60 \\\\pm 0.40 & \\\\mathbf{73.26 \\\\pm 0.65} & 80.36 \\\\pm 0.19 & 43.44 \\\\pm 0.13 & 79.54 \\\\pm 0.39 & 78.36 \\\\pm 0.10 \\\\\\\\\n\\\\text{M2MGNN}& \\\\mathbf{72.52 \\\\pm 0.10} & \\\\mathbf{80.81 \\\\pm 0.70} & \\\\text{OOM} & \\\\mathbf{85.83 \\\\pm 0.25} & \\\\mathbf{50.57 \\\\pm 0.29} & \\\\mathbf{95.73 \\\\pm 0.25} & 80.66 \\\\pm 0.47 \\\\\\\\\n\\\\text{GAMMA} & \\\\mathbf{71.81 \\\\pm 0.19} & \\\\mathbf{81.37 \\\\pm 0.25} & \\\\mathbf{72.61 \\\\pm 0.04} & \\\\mathbf{87.58 \\\\pm 0.25} & 49.07 \\\\pm 0.65 & \\\\mathbf{96.28 \\\\pm 0.11} & \\\\mathbf{82.59 \\\\pm 0.41} \\\\\\\\\n\\\\hline\n\\\\end{array}\n$$\n\n\nAs the new results demonstrate, GAMMA's performance is not only maintained but excels at a larger scale. It achieves state-of-the-art or second-best accuracy on 5 of the 7 datasets.\n\nFor a fair and rigorous comparison, all models were trained for 500 epochs across 5 random splits, using a 60/20/20 train/validation/test split. A consistent learning rate, dropout, and weight decay were used for all models, which were implemented in their baseline forms without extra architectural enhancements like residual connections.\n\nOur primary goal with GAMMA was to design an architecture that makes full-batch training on heterophilic graphs feasible and efficient, even on commodity hardware. However, our analysis confirmed that many state-of-the-art models (H2GCN, MixHop or M2MGNN) fail on even medium-scale graphs (e.g., roman-empire) when using a typical commodity GPU like the NVIDIA A2000 (12 GB VRAM). To provide a fair comparison, we utilized a more powerful NVIDIA A100 with 80 GB of memory. Even with this substantial resource, many models still encountered Out-Of-Memory (OOM) errors, particularly on large datasets like ogbn-products. These failures are a direct consequence of specific architectural choices common in heterophily-focused GNNs:\n\nFeature Concatenation Bottleneck: Models like H2GCN, MixHop, and Jumping Knowledge Networks (JK-Nets) explicitly concatenate feature representations from different hops or layers. This strategy causes the feature dimensionality to grow linearly or even exponentially, leading to massive intermediate tensors that are fundamentally unscalable for large graphs.\n\nComplex Aggregation Overhead: Other models suffer from computationally intensive operations. For example, BernNet's K-th order filter requires K distinct propagation steps, storing all intermediate results in memory. Further, M2MGNN performs complex per-edge operations, including a small MLP and a segmented softmax, which cannot be efficiently batched and become prohibitive on graphs with millions of edges.\n\nHowever, GAMMA's architectural design directly addresses these scalability challenges by employing a single, shared projection matrix. It ensures all hop embeddings reside in a coherent, fixed-dimension feature space. This entirely avoids the feature dimensionality explosion that exists in concatenation-based models. Further, the iterative gating mechanism adaptively computes a compact representation by selectively weighting hop information, rather than stacking it. This selective fusion process eliminates the need for concatenation, drastically reducing memory footprint.\n\nTogether, these elements create a streamlined framework that discards redundant information on-the-fly while preserving essential multi-hop patterns. This combination of parameter efficiency and an adaptive, non-expansive aggregation mechanism is what enables GAMMA to scale effectively where other methods fail.\n\n\n- Accuracy-to-Efficiency Trade-off Figure:\n\nThis is an excellent suggestion for improving the paper's clarity. Visualizing the accuracy-to-efficiency trade-off directly would indeed prevent readers from having to cross-reference Table 1 and Figure 5. In the revised manuscript, we will add a 2D scatter plot where the x-axis represents computation time (or memory) and the y-axis represents accuracy. \n\n- Discussion of Limitations:\n\nIndeed, a more detailed discussion of limitations strengthens the paper and clarifies its scope. We will expand the limitations paragraph in the conclusion to be more comprehensive.\n\nWhile GAMMA scales well, for web-scale graphs with billions of edges, the one-time pre-computation of multi-hop adjacencies ($A^k$) could become a bottleneck if not handled with sparse matrix formats. We will discuss this and mention potential mitigation strategies like on-the-fly neighborhood sampling. Further, the fixed number of routing iterations (R) is a hyperparameter that might be suboptimal for graphs with highly varied neighborhood complexities. We will explicitly state this trade-off and reference potential future work on adaptive iteration counts."}, {"review_id": "Z583vr5Jw5", "reviewer": "Reviewer_DJEL", "summary": "GAMMA proposes an efficient GNN architecture for learning in heterophilic or mixed-homophily graphs. It avoids traditional multi-hop concatenation by using an iterative routing-style gating mechanism that adaptively weights multi-hop embeddings per node, while sharing a single projection matrix to reduce overhead. The paper performs detailed computational profiling and demonstrates significant accuracy and efficiency gains on benchmark datasets.", "questions": "-\tHow does the routing mechanism converge, and is it stable across diverse graph types? It’ll be helpful to provide analysis on routing convergence behavior and its effect on representation learning.\n-\tIs weight sharing across hops always beneficial — could this limit expressiveness for disjoint hop information?\n-\tHow sensitive is GAMMA to graph noise or perturbations (e.g., edge rewiring)?\n-\tCan GAMMA adapt to temporal or attributed dynamic graphs?\n\nI'm open to increase the score if the questions and the weaknesses are reasonably addressed.", "limitations": "yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strength: \n-\tThe idea of iterative soft-attention routing over hops seems novel and well-motivated.\n-\tInteresting analysis on the efficiency of current heterophily methods ,and the results show the proposed message passing scheme is time- and memory-efficient.\n-\tSome analysis are intuitive and elegant,e.g., the capsule network analogy and gating mechanism.\n-\tSome empirical gains (i.e., runtime and memory profiling of 13 baselines) are significant, e.g., up to 20× faster inference while matching or exceeding state-of-the-art accuracy on some datasets.\n\n## Weakness:\n-\tOne major concern is the novelty is incremental: The proposed message passing scheme is quite similar to the one proposed in GPR-GNN. I don’t see any clear distinction. Also, GPR-GNN allows having negative coefficients for combining hop-specific embeddings $\\mathbf{H}$, while the proposed scheme does not have that flexibility.\n-\tIn line 66, the authors mention \"Adaptive node-specific message passing\". However, the proposed scheme is not node-specific but rather hop-specific. This is confusing.\n-\tA similar line of work, which actually formulates node-specific message passing [1], is not discussed and included as a baseline.\n-\tWhile routing is claimed to be efficient, no direct ablation on routing steps (e.g., 1 vs 3) is presented. It will be helpful to include ablation study on routing iterations and gating stability.\n\n-\tTheoretical analysis of convergence, expressivity, or generalization are missing.\n-\tPerformance shown mostly on small to mid-scale datasets (e.g., Cornell, Tolokers); unclear how it scales to large graphs. It will be interesting to see how the proposed method perform on the heterophilic datasets introduced in [2]. Also, it would be interesting to study the proposed method with large scale OGB datasets.\n\n## References:\n\n[1] Finkelshtein et al. Cooperative Graph Neural Networks. ICML 2024.\n\n[2] Platonov et al. A Critical Look at the Evaluation of GNNs Under Heterophily : Are We Really Making Progress? ICLR 2023.", "was_revised": true, "final_justification": "I appreciate the authors' engagement in the rebuttal. I think the evaluation of both performance and efficiency in the submitted version can be better set up.", "rebuttal": "We thank the reviewer for the detailed and constructive feedback. The comments have been invaluable in improving both the quality and clarity of our manuscript.\n\n1. Novelty and distinction from GPR-GNN:\n\nGPR-GNN learns a *global* polynomial filter, one coefficient vector applied identically to every node, capturing only dataset-level structure. GAMMA's global scaling vectors $\\gamma_{p}$ are unconstrained and can become negative during training, allowing the model to subtract or amplify features at the hop level. However, the key distinction from GPR-GNN is architectural: GPR-GNN applies its coefficients (which can be negative) uniformly across all nodes, while GAMMA combines negative-capable global scaling with positive node-specific routing coefficients $α_{i,p}$ (from softmax). This dual-level design provides both global feature manipulation and local adaptive weighting.\n\n2. Comparison with CO-GNN and computational efficiency:\n \nwe have benchmarked against $\\\\text{CO-GNN } (\\\\ast,\\\\ast)$, the best-performing configuration reported in their paper, and the results show GAMMA's superior performance. \n$$\n\\\\begin{array}{l|ccccccccc}\n\\\\hline\n& \\\\text{Cora} & \\\\text{CiteSeer} & \\\\text{PubMed} & \\\\text{Texas} & \\\\text{Wisconsin} & \\\\text{Actor} & \\\\text{Squirrel} & \\\\text{Chameleon} & \\\\text{Cornell} \\\\\\\\\n\\\\hline\n\\\\text{CO-GNN } (\\\\ast,\\\\ast) & 87.48 \\\\pm 0.71 & 76.26 \\\\pm 1.32 & 88.44 \\\\pm 0.35 & 79.03 \\\\pm 2.47 & 71.95 \\\\pm 3.28 & 32.03 \\\\pm 2.68 & 31.20 \\\\pm 3.85 & 58.28 \\\\pm 1.62 & 75.03 \\\\pm 2.26 \\\\\\\\\n\\\\hline\n\\\\text{GAMMA} & 87.42 \\\\pm 1.01 & 75.49 \\\\pm 1.67 & 89.62 \\\\pm 0.43 & 87.37 \\\\pm 3.68 & 86.27 \\\\pm 4.21 & 35.59 \\\\pm 1.29 & 36.20 \\\\pm 1.01 & 51.16 \\\\pm 2.22 & 78.68 \\\\pm 3.42 \\\\\\\\\n\\\\hline\n\\\\end{array}\n$$\n\nAs shown in the table, GAMMA achieves higher accuracy on challenging heterophilic datasets. This superior performance is achieved while adhering to our primary design philosophy: prioritizing computational efficiency for heterophilic graphs. In contrast, CO-GNN introduces significant overhead due to its dual-network design, requiring separate action and environment networks and doubling the number of linear transformations and graph convolutions per layer.\n\nCO-GNN incurs a 4.4x backward pass overhead compared to a standard GCN, with a forward pass time of 1.820 ms and a backward pass of 13.431 ms, ranking 12th out of 15 models on Cora (these profilings will be added to the manuscript). GAMMA’s streamlined architecture avoids these costs, delivering state-of-the-art accuracy with up to 12x lower memory usage and faster inference than leading alternatives.\n\n3. \"Node-Specific\" Terminology:\n\nThe distinction between \"node-specific\" and \"hop-specific\" is best understood by separating the feature aggregation process from the gating mechanism. This is illustrated in Algorithm 1 in the supplementary material (Appendix A.2). Hop-specific refers to the initial, global aggregation of features. For each node and its neighbors at hop distance $p$, we generate an embedding $H^{(p)}$ by gathering information from all nodes at that distance. However, node-specific refers to our gating mechanism. After the hop-specific embeddings are generated, each node $i$ individually computes its own set of routing coefficients, $\\alpha_{i,p}$. These coefficients are unique to each node because they are determined by an \"agreement\" score calculated between the node's own evolving representation and the messages it receives from each hop.\nThank you for pointing out this potential for confusion. We will revise the manuscript to more clearly state that.\n\n4. Theoretical analysis:\n \nAppendix A.4 proves convergence to a unique fixed point, demonstrates that GAMMA’s function class strictly contains concatenation-based methods, and shows adaptive routing maximizes mutual information between embeddings and labels.\n\n5. Large-scale evaluation:  \nTo address scalability, we have benchmarked GAMMA on seven large-scale heterophilic graphs. The results in the provided table below show that GAMMA achieves state-of-the-art or second-best accuracy on 5 of the 7 datasets.\n\n$$\n\\\\begin{array}{l|ccccccc}\n\\\\hline\n& \\\\text{ogbn-arxiv} & \\\\text{roman-empire} & \\\\text{ogbn-products} & \\\\text{minesweeper} & \\\\text{amazon-ratings} & \\\\text{amazon-photos} & \\\\text{tolokers} \\\\\\\\\n\\\\hline\n\\\\text{MLP}   & 47.34 \\\\pm 0.09 & 65.37 \\\\pm 0.58 & 43.20 \\\\pm 0.01 & 79.48 \\\\pm 0.21 & 38.35 \\\\pm 0.20 & 48.73 \\\\pm 1.80 & 78.16 \\\\pm 0.00 \\\\\\\\\n\\\\text{GCN}   & 64.91 \\\\pm 0.26 & 54.16 \\\\pm 0.28 & \\\\mathbf{71.31 \\\\pm 0.16} & 80.31 \\\\pm 0.24 & 42.12 \\\\pm 0.29 & 52.14 \\\\pm 1.50 & 78.76 \\\\pm 0.17 \\\\\\\\\n\\\\text{SGC}   & 63.47 \\\\pm 0.16 & 61.20 \\\\pm 0.65 & \\\\text{OOM} & 80.05 \\\\pm 0.03 & 41.61 \\\\pm 0.72 & 57.97 \\\\pm 0.52 & 78.56 \\\\pm 0.19 \\\\\\\\\n\\\\text{GCN2}  & 61.96 \\\\pm 0.42 & 64.96 \\\\pm 0.38 & 61.08 \\\\pm 0.18 & 82.80 \\\\pm 0.35 & 47.20 \\\\pm 0.55 & 94.10 \\\\pm 0.25 & 79.80 \\\\pm 0.30 \\\\\\\\\n\\\\text{GCNJK} & 70.19 \\\\pm 0.11 & 62.18 \\\\pm 0.91 & 69.46 \\\\pm 0.33 & 85.15 \\\\pm 0.42 & 48.77 \\\\pm 0.37 & 95.28 \\\\pm 0.05 & \\\\mathbf{81.23 \\\\pm 0.26} \\\\\\\\\n\\\\text{GATJK} & \\\\mathbf{70.75 \\\\pm 0.19} & 70.00 \\\\pm 0.70 & \\\\text{OOM} & \\\\mathbf{85.65 \\\\pm 0.34} & \\\\mathbf{50.84 \\\\pm 0.52} & 95.71 \\\\pm 0.11 & \\\\mathbf{81.31 \\\\pm 0.48} \\\\\\\\\n\\\\text{H2GCN} & \\\\text{OOM} & 75.89 \\\\pm 0.55 & \\\\text{OOM} & 83.31 \\\\pm 0.65 & 42.90 \\\\pm 0.38 & 84.95 \\\\pm 0.38 & 79.39 \\\\pm 0.42 \\\\\\\\\n\\\\text{GAT}   & 70.01 \\\\pm 0.09 & 74.50 \\\\pm 0.45 & \\\\text{OOM} & 81.52 \\\\pm 0.26 & 48.89 \\\\pm 0.61 & 95.56 \\\\pm 0.15 & 78.63 \\\\pm 0.06 \\\\\\\\\n\\\\text{MixHop}& 70.27 \\\\pm 0.14 & \\\\mathbf{82.20 \\\\pm 0.31} & \\\\text{OOM} & 84.88 \\\\pm 0.45 & \\\\mathbf{50.98 \\\\pm 0.30} & \\\\mathbf{96.34 \\\\pm 0.30} & 81.03 \\\\pm 0.70 \\\\\\\\\n\\\\text{BernNet}& 63.15 \\\\pm 0.13 & 66.27 \\\\pm 0.35 & \\\\text{OOM} & 80.00 \\\\pm 0.07 & 40.90 \\\\pm 0.09 & 62.34 \\\\pm 7.02 & 78.16 \\\\pm 0.00 \\\\\\\\\n\\\\text{GPRGNN}& 67.66 \\\\pm 0.07 & 69.60 \\\\pm 0.40 & \\\\mathbf{73.26 \\\\pm 0.65} & 80.36 \\\\pm 0.19 & 43.44 \\\\pm 0.13 & 79.54 \\\\pm 0.39 & 78.36 \\\\pm 0.10 \\\\\\\\\n\\\\text{M2MGNN}& \\\\mathbf{72.52 \\\\pm 0.10} & \\\\mathbf{80.81 \\\\pm 0.70} & \\\\text{OOM} & \\\\mathbf{85.83 \\\\pm 0.25} & \\\\mathbf{50.57 \\\\pm 0.29} & \\\\mathbf{95.73 \\\\pm 0.25} & 80.66 \\\\pm 0.47 \\\\\\\\\n\\\\text{GAMMA} & \\\\mathbf{71.81 \\\\pm 0.19} & \\\\mathbf{81.37 \\\\pm 0.25} & \\\\mathbf{72.61 \\\\pm 0.04} & \\\\mathbf{87.58 \\\\pm 0.25} & 49.07 \\\\pm 0.65 & \\\\mathbf{96.28 \\\\pm 0.11} & \\\\mathbf{82.59 \\\\pm 0.41} \\\\\\\\\n\\\\hline\n\\\\end{array}\n$$\n\nNotably, many SOTA models encounter Out-Of-Memory (OOM) errors on larger graphs (on the same setup, NVIDIA A100 - 80 GB) like ogbn-products. GAMMA's design, which avoids feature concatenation and uses an efficient gating mechanism, enables it to scale effectively.\n\nResponses to questions:\n\n- Convergence and stability: The convergence and stability of the routing mechanism are supported by both theoretical guarantees and empirical results. Theorem 1 (Appendix A.4.2) formally proves that the iterative routing update rule converges to a unique fixed point that optimally balances agreement between hop-specific embeddings and their weighted combination, with an entropy term preventing degenerate solutions. Empirically, our ablation study (Appendix A.1) demonstrates stability across datasets: performance consistently peaks within 2 to 6 iterations. For example, on heterophilic datasets (Cornell, Actor), performance peaks at 6 and 7 iterations, while on homophilic datasets (Cora, PubMed), it stabilizes after just 2-5 iterations. This shows the mechanism quickly finds a stable, effective weighting of hop information across diverse graph structures without extensive tuning.\n\n- Weight sharing and expressiveness: While using a shared weight matrix $W$ across hops improves parameter efficiency, it does not reduce GAMMA’s expressive power. Appendix A.5.1 shows that GAMMA’s function class $F_{GAMMA}$ strictly contains that of concatenation-based models (H2GCN or MixHop). This greater expressiveness comes from a dual-level adaptation: global hop-specific scaling vectors $\\gamma_{p}$ let the model learn the importance of feature channels at each hop, while node-specific gating coefficients $\\alpha_{i,p}$ enable dynamic routing based on each node’s local structure. This combination of shared geometric space with both global and local adaptive weighting allows GAMMA to represent any function a concatenation-based model can—and more, as shown in the proof.\n\n- Robustness to noise: GAMMA is inherently robust to noise and structural perturbations due to its adaptive gating mechanism. This resilience stems from agreement-based routing: if a spurious edge introduces noise into a hop embedding $H_{i}^{(p)}$, its low dot-product agreement with the node’s evolving representation $v_{i}^{(t)}$ prevents the routing logit $b_{i,p}$ from increasing, so the softmax assigns it a low coefficient $\\alpha_{i,p}$, effectively filtering out the noise. The multi-hop design adds redundancy; if a node’s 1-hop neighborhood is noisy, the routing can up-weight information from its more stable 0-hop or 2-hop representations. GAMMA’s strong results on inherently noisy real-world datasets further support this robustness.\n\n- Adaptation to dynamic graphs: GAMMA is a potential candidate for extension to temporal or dynamic graphs. Its parameter efficiency means fewer updates are needed as the graph evolves. The lightweight routing mechanism is computationally inexpensive, enabling frequent and efficient re-computation of node-specific gating coefficients $\\alpha_{i,p}$ with each graph change, allowing fast adaptation to local structural modifications without retraining the entire model. While the current version is for static graphs, extending GAMMA to dynamic settings is a promising direction. This could involve making the routing mechanism time-aware, such as incorporating a temporal decay factor into the routing logits or making the global scaling vectors $\\gamma_{p}$ time-dependent to capture evolving global patterns."}]

Author rebuttal:

Meta-review: This paper proposes a gated multi-hop message passing framework that adaptively integrates information across different hop distances, enabling expressive representations without increasing dimensionality beyond that of single-hop GNNs. It is shown experimentally to combine competitive accuracy (matching or exceeding SOTA heterophilic GNNs) with significantly improved inference speed.

During the rebuttal, the authors provided additional scalability experiments, stronger comparisons, and clarifications on novelty. While the framework does not consistently outperform the state of the art on all datasets (especially on large benchmarks), its aggregate performance is strong, and the efficiency improvements (in terms of inference speed / memory usage) make it a meaningful contribution. The contribution can be strengthened by more explicitly clarifying its novelty and positioning within the broader GNN literature in the revised manuscript. Overall, the paper constitutes a solid and practical contribution to GNN design.
Decision: Accept (poster)