GAMMA: Gated Multi-hop Message Passing for Homophily-Agnostic Node Representation in GNNs

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.

1. Novelty and distinction from GPR-GNN:

GPR-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.

2. Comparison with CO-GNN and computational efficiency:

we have benchmarked against $\\text{CO-GNN } (\\ast,\\ast)$, the best-performing configuration reported in their paper, and the results show GAMMA's superior performance.

As 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.

CO-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.

3. "Node-Specific" Terminology:

The 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. Thank you for pointing out this potential for confusion. We will revise the manuscript to more clearly state that.

4. Theoretical analysis:

Appendix 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.

5. Large-scale evaluation:
   To 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.

Notably, 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.

Responses to questions:

• 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.

• 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.

• 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.

• 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.

We thank the reviewer for their continued engagement and valuable feedback.

Regarding the performance concerns on large-scale datasets, while GAMMA does not achieve state-of-the-art results on all benchmarks, it performs either first or second place in 6 out of 7 of newly added datasets. Further, we would like to add that looking at the broader literature, this reflects a common characteristic across heterophilic GNN methods [1, 2, 3, 4, 5], where no single architecture achieves universal dominance. For instance, LRGNN [1] underperforms on 4 of 9 small datasets despite its theoretical and methodological contributions. Similarly, H2GCN [2] and Neural Sheaf Diffusion [3] show variable performance across benchmarks while making significant architectural improvements.

GAMMA's core contribution lies in its computational efficiency, which enables full-batch training of heterophilic GNNs on commodity hardware, addressing an important efficiency bottleneck and a practical constraint that has limited accessibility to these methods. As reviewer "hXHc" noted, the computational feasibility of expensive GNNs on standard GPUs is a concern. Most state-of-the-art methods, including H2GCN and CO-GNN mentioned by the reviewer, encounter out-of-memory errors even on medium-sized datasets when using typical desktop GPUs (e.g., NVIDIA RTX A2000, GeForce RTX 3050 and RTX 2000 Ada Generation), which is why they were initially excluded from our commodity hardware experiments.

To address scalability concerns raised by reviewers, we upgraded our evaluation to an A100 80GB GPU, a server-grade, non-commodity setup allowing all baseline methods to complete full-batch training without memory constraints. In this enhanced environment, GAMMA achieves comparable accuracy while maintaining its efficiency advantages. Critically, GAMMA averages 7.57× faster execution time and consumes 24.18× less memory than competing methods across these newly added datasets, approaching the efficiency of simple GCNs while handling heterophily effectively.

This efficiency enables practical deployment scenarios that existing methods cannot support. GAMMA reduces the computational gap between heterophilic GNNs and simple architectures like GCN, making heterophilic graph learning accessible to users with limited computational resources.

[1] Liang et al., "Predicting global label relationship matrix for graph neural networks under heterophily," NeurIPS 2023

[2] Zhu et al., "Beyond homophily in graph neural networks: Current limitations and effective designs," NeurIPS 2020

[3] Bodnar et al., "Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns," NeurIPS 2022

[4] Yang et al., "Diverse message passing for attribute with heterophily," NeurIPS 2021

[5] Li et al., "Finding global homophily in graph neural networks when meeting heterophily," ICML 2022

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.

• Evaluation on Large-Scale Graphs:

The 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:

As 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.

For 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.

Our 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:

Feature 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.

Complex 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.

However, 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.

Together, 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.

• Accuracy-to-Efficiency Trade-off Figure:

This 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.

• Discussion of Limitations:

Indeed, 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.

While 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.

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.

Regarding 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.

Below, we address the questions in detail.

1. Clarification of the GAMMA Mechanism

Thank 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).

• 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:

The 1-hop embedding is calculated as $H^{(1)} = AH$. The 2-hop embedding is then $H^{(2)} = A(H^{(1)}) = A(AH)$. The 3-hop embedding follows as $H^{(3)} = A(H^{(2)}) = A(A(AH)) = A^3H$.

This 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.

• 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.

For 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.

So, 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.

• 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.

2. Computational Cost and Data-Driven Iterations

• 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:

Lightweight 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.

Memory 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).

• 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).

• 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.

3. Performance on Homophilic Datasets

This 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.

The 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.

We appreciate the reviewer’s constructive feedback. Below we address each concern with comprehensive experiments and analysis.

1. Scalability on Large‑Scale Datasets
   The 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.

The 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.

2. Feasibility of Training Large‑Scale Heterophilic Graphs on Commodity GPUs
   Our 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:

• 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.

• 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.

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.

3. Novelty and Technical Contributions

While 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.

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.

Gated Multi‑hop Message Passing: Our new design is the dynamic, node‑specific, and iterative gating mechanism, fundamentally different from existing approaches:

• 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.

• 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.

• 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.

Additionally, 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.

Thank you for the extensive empirical verification. Based on the authors' extensive responses, I will increase my score. In the revision, I believe it is critical to address the points raised by myself and other reviewers about scalability and novelty. For scalability, the authors have shown important findings, describing that many models are not feasible to train on commodity GPUs (e.g., NVIDIA A2000) even for smaller sized datasets (Roman-Empire, Amazon Ratings). If GAMMA can run on these smaller GPUs on the larger datasets like ogbn-products, that is an even bigger win. Even on larger GPUs, many of the state of the art models time out and GAMMA remains competitive with the remaining models. For novelty, GAMMA does seem very similar to GPR-GNN, but these ablations have demonstrated the difference lying in the adaptive node specific weights. I believe this distinction is key to highlight in the revision.