acceptodds
Under review as a conference paper at ICLR 2027

Graph Hierarchical Recurrence for Long-Range Generalization

Abstract

Graph Neural Networks and Graph Transformers have become central to graph learning, combining expressive representation learning with sample-efficient in- ductive biases. Yet they remain fundamentally limited when predictions depend on correlations between distant graph regions. We address this limitation with Graph Hierarchical Recurrence (GHR), a novel framework that jointly operates on the input graph and a pooled hierarchical abstraction. We also show that ex- isting models degrade more sharply under out-of-range generalization, where test instances require interactions across distances exceeding those observed during training. Despite its minimal design, GHR consistently strengthens every tested message-passing backbone, yielding robust performance on long-range dependen- cies and particularly pronounced gains in out-of-range regimes. Across a broad suite of long-range benchmarks, GHR achieves state-of-the-art or competitive re- sults on multiple tasks, establishing hierarchical recurrence as an effective mech- anism for extending graph models beyond their observed interaction range.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, long-range interactions, out-of-range generalization, hierarchical graph pooling, recurrent

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_PebHOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Graph Hierarchical Recurrence (GHR), a graph learning framework designed to improve out-of-range generalization in long-range tasks. GHR integrates recurrent computation with low-level and high-level message passing, where the high-level graph corresponds to the previous low-level graph pooled into a coarser graph, and the low-level graph for the next iteration is unpooled from the high-level one. The authors introduce in-range and out-of-range generalization and demonstrate that GHR outperforms flat-GNN baselines in long-range tasks.

Critical strengths
  1. The paper is well-written, enjoyable to read, and fits the chosen primary area.
  2. The idea of using hierarchical pooling and unpooling iteratively for the sake of reaching far-away nodes efficiently is interesting and novel. The experiments, results, and ablations are rigorous.
Critical weaknesses
  1. Even though the problem and the proposed solution are intriguing, I believe the experimental setup could be improved. To the best of my understanding, the RGG SSSP task uses a small synthetic dataset with a limited number of nodes (averaging 40 to 60). I think conducting a similar analysis on larger graphs would strengthen the paper's main claim, since the concept of "long-range interactions" is ill-defined in small graphs, such as the ones used in the paper.
  2. The recent SOTA method of Stable-ChebNet [1] is not included in the experiments. Please compare against this architecture specifically designed for long-range tasks.

[1] Hariri, Ali, et al. "Return of ChebNet: Understanding and Improving an Overlooked GNN on Long-Range Tasks." NeurIPS. 2025.

Questions for authors
  1. Have you analyzed the performance of GHR in both node-level and graph-level tasks in larger graph datasets?
  2. Have you compared against the most recent architectures specifically designed for long-range tasks, rather than simple GNN methods?
5 comments
AuthorsOpenReview ↗

Response to Reviewer PebH

We thank the reviewer for highlighting that the hierarchical pooling and unpooling between two scales iteratively with the aim of reaching distant nodes effectively is an interesting and novel idea. Moreover, we also thank the reviewer for highlighting that the ablations performed are rigorous.

In the following we address the reviewer’s weaknesses and answer the questions.

W1

[...] RGG SSSP task uses a small synthetic dataset with a limited number of nodes (averaging 40 to 60). [...]

We thank the reviewer for this comment, which helped us spot a clarity issue in how we presented our experimental setup. The experiment with graphs of 40–60 nodes on average is the one in the paragraph "Small-distance regime OOR generalization". Its goal is specifically to test whether under-reaching occurs in fixed-depth architectures and uses a small-distance regime.

The full ablation study in the main text, however, is run on RGGs with 300-350 nodes. Because edges in random geometric graphs only connect spatially close nodes, shortest-path distances are large relative to graph size: at this scale, we compute distances between nodes being up to 40 hops apart which is usually considered a long-range regime in the current literature like ECHO [1].

We acknowledge that the graphs’ sizes were only reported in App., which made it hard to distinguish the two regimes apart. In the revised version we:

  • report the graph sizes of the long-distance regime RGGs directly in the main text (Sec. 4);
  • rename the corresponding paragraph to “Ablation study on RGGs: long-distance regime", to make the distinction between the two settings explicit.

The changes are in Sec. 4.1 in lines 362-364.

W2

The recent SOTA method of Stable-ChebNet [1] is not included in the experiments. [...]

We thank the reviewer for the suggestion. In the original submission, we restricted our comparisons to the models reported in the respective benchmarks, which already span a variety of architectural families. We agree that Stable-ChebNet is a relevant baseline for long-range tasks, and we have added it to our experiments, using the official implementation and the configurations reported by the authors.

Below are MAE results on ECHO-Synth (mean ±\pm std over 3 runs, lower is better) compared to GHR results, which are added to the revised manuscript:

ModelSSSPECCDIAM
Stable-ChebNet [1]0.239±0.0120.239\pm0.0123.666±0.0863.666\pm0.0861.149±0.0771.149\pm0.077
GHR-GINE (Ours)0.035±0.0040.035\pm0.0043.456±0.0413.456\pm0.0410.749±0.0230.749\pm0.023

Experiments on ECHO-Chem are currently running. We will report them here if they complete before the end of the discussion period. Otherwise they will be included in the final version of the paper.

The changes in the revised version are in Sec. 1, line 54-57 and in Tab. 1.

Q1

We thank the reviewer for the suggestion that complements the existing results. In order to analyze GHR performance on a Large Graph dataset we additionally evaluated GHR-GCN on City-Networks [2], a transductive node-level benchmark on real road networks with over 10^5 nodes per graph.

Following the manuscript methodology, we evaluated using GCN as backbone since it is in the original paper, allowing for a direct comparison. Due to the short times of the rebuttal, one more backbone and the rest of the cities will be included in the final version.

Accuracy is averaged across three independent seeds, hyper-parameters are fixed across the two cities: Hidden dimension = 64, T_H = 2 T_L = 8, graclus rounds = 4

ModelParisShanghai
GHR-GCN (Ours)57.6±0.557.6\pm0.570.2±1.470.2\pm1.4
GCN, 16 layers (Liang et al., 2026)53.2±0.353.2\pm0.362.1±0.262.1\pm0.2
Exphormer, best model in (Liang et al., 2026)55.1±0.855.1\pm0.870.2±0.470.2\pm0.4

In order to report training cost and needed resources on such large networks we additionally report full-graph training steps time and peak memory cost on GPU, showing how our framework, thanks to its linear complexity, adapts well to expensive datasets:

City# fine nodes# coarse nodesPeak VRAMms/step
Paris114,127114{,}12712,14412{,}1442.402.40 GB109.9109.9
Shanghai183,917183{,}91722,49022{,}4903.703.70 GB159.8159.8

This additional experiment is referenced in the main text of the revised version in section 4.2 (lines 421-423) with all the results being added to the App. C.6.

Q2

We appreciate the reviewer’s interest in how we compare with recent long-range architectures. Our main benchmarks include both architectures designed specifically for long-range propagation and graph transformers. On ECHO (Table 1) we compare with rewiring (DRew), dynamical-system approaches (A-DGN, PH-DGN, SWAN and now Stable-ChebNet) and graph transformers (GPS, GRIT). On LRIM (Tab. 3) we compare with three different variants of GPS and with a virtual-node model.

Both ECHO and LRIM benchmarks were published at ICLR 2026, so their baselines show recent long-range architectures.

AuthorsOpenReview ↗

Response to Reviewer PebH (References)

References

[1] Miglior et al., “Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation”. ICLR (2026)

[2] Liang et al., “Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement”. ICLR (2026)

[3] Mathys et al., “LRIM: a Physics-Based Benchmark for Provably Evaluating Long-Range Capabilities in Graph Learning”. ICLR (2026)

Reviewer_PebHOpenReview ↗

Response to rebuttal by authors

Thank you for the rebuttal. Please report the pending results if they become available before the discussion period ends. I keep my score as is.

Reviewer_v3x6OpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work studies long range generalization in graphs. They define out-of-range distribution shifts, where test distances are larger than training distances. I believe this may take inspiration from other studies in length generalization from other kinds of data, which would be nice to see stated in the paper. Existing models have a hard time adapting to this. The work proposes a hybrid architecture where iterative computation (which is adaptive) combines with message passing on the coarsened graph (which can also adapt to different train/test sizes). This serves as an addition to already existing message passing backbone architectures.

Critical strengths

They very clearly state the problem they are tackling and illustrate it with an example. They make the architecture adaptative to different ranges at test time.

Critical weaknesses

I wonder if some of the gains come from being able to access a larger part of the graph more quickly at inference, for which there are other architectures that would do the same thing (say, L2G-Net, from ICML 2026). The solution to the problem is a bit cumbersome and combines two different kinds of steps, to which I wonder if they are both required and why.

Questions for authors

Does recurrent computation restrict either training or expressivity in any way? Does coarsening input noise to the learning process? Why are the two parts necessary?

6 comments
AuthorsOpenReview ↗

Response to Reviewer v3x6

We thank the reviewer for the comment and for highlighting the adaptive nature of our framework, especially at test time when additional iterations might be needed to achieve accurate predictions on previously unseen ranges.

### Response to weaknesses and questions

I wonder if some of the gains come from being able to access a larger part of the graph more quickly at inference, for which there are other architectures that would do the same thing (say, L2G-Net, from ICML 2026).

We agree with the reviewer's intuition, as we believe that some of the improvements in the standard long-range benchmarks come from the ability to access larger or more distant portions of the graph at each forward step. We also wish to highlight that since the coarsening in GHR can be any partition of the nodes (Section 2), it could in principle also use partitions produced by spectral methods, such as hard assignments from MinCutPool or the small-cut partitions computed by L2G-Net.

We were not aware of the latter work at the time of submission since it is a concurrent work, but we are happy to discuss it in the revised version of the paper.

Specifically we adapt the revised paper in Lines 54-65.

The solution to the problem is a bit cumbersome and combines two different kinds of steps [...]

While GHR combines two types of updates operating at different graph scales, each of its components remains relatively simple. Every update consists of a standard message-passing layer with a residual connection, and the coarse state is incorporated into the fine-level update through a simple addition. Compared to a recurrent MPNN, GHR only introduces a coarsening operation computed once per graph and an additional second message-passing layer operating on the coarse graph. To further illustrate the simplicity of the proposed scheme, we will use the additional space available in the revised version to move Figure 6, which illustrates the iterative pooling-unpooling scheme, from the appendix to the main text (now figure 3 of the revised manuscript).

[...] to which I wonder if they are both required and why. [...] Why are the two parts necessary?

We thank the reviewer for these questions. Figure 5 (now Fig. 6 in the revised text) shows that hierarchy alone is not sufficient for OOR generalization: the hierarchical but non-recurrent model (DeepGHR) does not generalize beyond the training range.

Recurrence instead improves predictions in the OOR regime, and moreover it allows the model to be unrolled for additional iterations at test time. However when unrolled, we observe in Figure 5 that the recurrent non-hierarchical models lose accuracy on in-range: RecurrentGIN degrades the most and RecurrentGIN + GR although degrading less in-range, improves only marginally out-of-range. GHR performs best, staying stable and accurate in range while having the lowest error in the OOR regime. These results indicate that both components are needed for strong performance both in range and out of range regimes.

Does recurrent computation restrict either training or expressivity in any way? Does coarsening input noise to the learning process?

Weight sharing restricts the model to apply the same update for every step. This restriction is also the inductive bias that allows the update to be applied beyond training range, although it can be relaxed if needed through a step-conditioned MP (as in Appendix A.4). The hierarchy does not restrict the model since by setting the coarse projection to zero, GHR reduces to a flat recurrent MPNN (Section 3.1). Regarding noise, in Appendix D.1 we also study suboptimal coarsenings which bring performance back towards that of the flat model. Since GHR is a framework in which the coarsening is a choice (Section 2), it can be adapted to the task to limit such effects, as we show with block partitions on LRIM lattices.

Dear Reviewer,

as the rebuttal discussion period is approaching its end, we would like to kindly follow up on our responses.

We would appreciate hearing whether our responses have addressed your concerns or if there are any remaining points you would like us to clarify. We would be happy to discuss them further and hope you might reconsider your score in light of the new evidence.

Best regards, the authors

I appreciate the authors' detailed answers, particularly in bringing up the method's diagram to improve clarity. Would the authors be willing to develop the intuition that "believe that some of the improvements in the standard long-range benchmarks come from the ability to access larger or more distant portions of the graph at each forward step" in the main text, at least e.g. in the conclusions? Moreover, I said in the summary that I would like to see some connection to length generalization in non-GNN literature, and I forgot to repeat it in the questions. With both these things in the manuscript, I will raise my score accordingly.

When I asked about why the two parts are necessary, I didn't mean empirically (as this shows in the figure), but more as a further discussion on why that is the case. As the authors mention in the other reviewer's rebuttal, existing theoretical tools on depth generalization are limited, and it is beneficial to raise discussions based on empirical evidence on what exactly is missing. My two cents are on the combination of iterative computation for length generalization, and longer reaching at each forward step. So I would like for this to take up a larger part in the manuscript, if space allows.

Reviewer_R6yiOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes GHR, combining recurrent message passing on the original graph with a coarsened graph to improve long-range information propagation. The authors further investigate out-of-range (OOR) generalization and report strong results across several benchmarks.

Critical strengths
  1. Combining recurrence and hierarchical propagation is a promising approach to long-range graph learning.
  2. The framework supports multiple GNN backbones and achieves competitive performance across several benchmarks.
Critical weaknesses
  1. Limited methodological novelty. GHR primarily combines established graph coarsening with recurrent message passing. The contribution appears largely to be an engineering-oriented integration of existing techniques, with empirical results demonstrating their effectiveness, rather than introducing a fundamentally new mechanism for long-range graph learning.
  2. Insufficient theoretical justification for OOR generalization. The proposed hierarchy mainly addresses under-reaching by shortening propagation paths, which can also be alleviated by sufficiently deep or iterative GNNs. Although the paper explains how coarsening extends the effective receptive field, it does not establish why this mechanism, together with nested recurrence, should improve generalization to distances unseen during training. A larger receptive field does not necessarily imply better OOR extrapolation.
  3. The necessity of hierarchical recurrence remains unclear. Figure 5 already shows that flat recurrent GNNs can achieve OOR generalization and can extend their propagation depth through test-time unrolling. It remains unclear whether GHR's improvements arise from the proposed nested recurrence or simply from the shorter propagation paths introduced by coarsening.
  4. Missing comparisons with efficient long-range propagation methods. The paper does not compare GHR with implicit or decoupled propagation approaches such as LazyGNN and APPNP, which can capture long-range dependencies without stacking many trainable GNN layers. These approaches provide relevant alternatives for efficient long-range learning, and their absence limits the evidence that hierarchical recurrence is necessary or more effective.
  5. Limited hierarchical and pooling baselines. The evaluation lacks comparisons with learned pooling approaches (e.g., DiffPool and MinCutPool), existing hierarchical GNNs (e.g., Graph U-Net), and simpler recurrent GNNs equipped with virtual nodes. Task-adapted comparisons with these alternatives would help determine whether GHR offers benefits beyond established hierarchical information propagation mechanisms.
  6. On LRIM-16-hard, LogMSE degrades substantially from −4.701 with 2×2 block pooling to −3.630 with Graclus, which is worse than the reported plain GatedGCN baseline (−3.844). Random partitioning (−3.669) also performs comparably to Graclus. Furthermore, pooling operators and cluster aggregation strategies are selected separately for different benchmarks, raising concerns about the robustness and generality of the proposed framework.
Questions for authors

please refer to weakness.

5 comments
AuthorsOpenReview ↗

Response to Reviewer R6yi (Weaknesses 1-2)

We thank the reviewer for acknowledging that combining recurrence and hierarchical propagation is a promising approach to long-range graph learning. In the following we address the reviewer’s concerns.

W1

Limited methodological novelty [...]

We thank the Reviewer for this thoughtful point and we would like to clarify the nature of our contribution, which we believe goes beyond a straightforward combination of existing techniques. Indeed, this distinction was also recognized by Reviewer PebH, who notes that "The idea of using hierarchical pooling and unpooling iteratively for the sake of reaching far-away nodes efficiently is interesting and novel".

The Reviewer is correct that our framework combines pooling and recurrence methods, for which we do not claim originality. However, we argue that the novelty lies in how these components are integrated in a non-trivial architecture specifically designed to enable effective long-range information propagation and generalization. Specifically,

  1. Methodological contribution. Our architecture integrates pooling and unpooling in a non-trivial way. More in detail, our architecture’s peculiarity is to integrate an iterative pooling-unpooling scheme across different graph scales, where the coarse state enters the fine-level stream only via addition, in a nested recurrent scheme as shown in Fig. 6 and 7. As a result, both coarse and fine updates can be iterated to any depth, unlike any other hierarchical approach to the best of our knowledge. We acknowledge, however, that these architectural details were not sufficiently clear in the original submission. To address this, we have decided to move Fig. 6 from the appendix to the main text (Now Fig. 3 of the revised manuscript).
  2. The effectiveness of this solution. Our extensive experimental validation demonstrates that GHR achieves results that neither pooling nor recurrence achieves independently, as shown in Fig. 5 (now Fig. 6 in the revised manuscript).

Finally, beyond our methodological contribution, we want to highlight that we also make a conceptual contribution by introducing the distinction between in-range and out-of-range generalization and providing an evaluation framework across interaction ranges. Through this framework, we demonstrate that out-of-range generalization is a widespread challenge across commonly used graph learning models, which cannot be explained solely by under-reaching, as shown in Fig. 4 (now Fig. 5 in the revised manuscript).

W2

Insufficient theoretical justification for OOR generalization [...]

Providing a formal characterization remains particularly challenging, as the gap between current machine learning theory and practice hinders the development of a theoretical framework that adequately captures the empirical phenomena highlighted in our work. Indeed, existing theoretical tools in graph learning primarily focus on expressivity and complexity measures, which are insufficient to characterize the behavior of overparameterized models, even in settings considerably simpler than those addressed in our paper [1].

In light of these restrictions, the main goal of our paper is to highlight how the problem of long-range interactions in graph learning is more nuanced than commonly recognized in the existing literature and to propose practical solutions to address it. We believe that our empirical findings and evaluation protocol are valuable in their own right, lay the foundation for future theoretical investigations, and justify timely dissemination to the graph learning community.

Although the paper explains how coarsening extends the effective receptive field, [...]. A larger receptive field does not necessarily imply better OOR extrapolation.

We agree with the reviewer and would like to clarify that we do not claim that a larger receptive field necessarily leads to better OOR extrapolation. Rather, we use the size of the receptive field to distinguish poor OOR generalization from under-reaching. Indeed, the sufficiently deep and iterative GNNs suggested by the reviewer are already evaluated in our paper, where we show that increasing depth can alleviate under-reaching but does not necessarily improve OOR generalization. More in detail:

  • In Fig. 4 (Fig. 5 in the revised), fixed-depth models whose receptive field covers all test distances lose accuracy just beyond the training range.
  • In Tab. 2 Graph Transformers with global attention degrade out-of-range on every task.
  • In Fig. 5 (Fig. 6 in the revised) the predictions of deep models with 30 layers fail between 22 and 30 hops and flat recurrent models unrolled to 42 steps either lose accuracy in range or improve only marginally.
AuthorsOpenReview ↗

Response to Reviewer R6yi (Weaknesses 3-4-5)

W3

The necessity of hierarchical recurrence remains unclear. [...]

As the reviewer highlights, Fig. 5 (now Fig. 6 in the revised text) shows that recurrence can improve OOR generalization to some extent and can benefit from test-time unrolling, as stated in Section 4.1. While we agree that weight sharing is an important component to enable out-of-range generalization, we believe that it is not sufficient for strong OOR performance. The ablations are designed to isolate this effect. In particular, we highlight the following:

  • Hierarchy without recurrence. The ablation shows how DeepGHR, which uses the same coarse graph and number of operations of GHR without weight-sharing, fails to generalize out-of-range. Shorter paths therefore do not improve OOR generalization by themselves.
  • Recurrence without hierarchy. Beyond their under-reaching boundary (30 iterations), recurrent GINs fail to generalize and their error grows linearly with distance. Even within the OOR region where they do not suffer from under-reaching, they remain less accurate than GHR.
  • Recurrence with test-time unrolling. Unrolling improves the OOR performance of recurrent GINs, but their error still grows with distance. While unrolled GHR error does not increase beyond 30 hops. Unrolling also has a clear cost in range for flat models: RecurrentGIN loses more than an order of magnitude in in-range accuracy, RecurrentGIN+GR loses about half an order of magnitude but improves less out of range. Unrolled GHR retains the best performance.

In the following table we report aggregate MAE in the IR region in Fig. 5 (now Fig. 6) for the three unrolled models, highlighting the strong loss in performance in the absence of hierarchy.

GHR (unrolled)RecurrentGINRecurrentGIN (unrolled)RecurrentGIN+GR (unrolled)
IR MAE0.0520.0520.0670.0670.8990.8990.3390.339

Only their combination obtains the lowest error across the entire range of target distances.

Using the additional page, we adapt the clarification discussed in this answer, extending the discussion provided in Fig. 5 with the IR MAE results for the unrolled models.

Specifically: we adapted line 375-410 of the revised manuscript.

W4

Missing comparisons with efficient long-range propagation methods.

We have performed additional experiments to evaluate APPNP [2]. We report the ECHO-Synth benchmark with APPNP in the table in answer W5: APPNP was evaluated with the architecture of the original paper, setting the number of steps to K = 40. Training hyper parameters were selected by grid search, under the training protocol of ECHO [3]. This model propagation computes a linear average of node predictions, which cannot represent minima and the maxima over paths required by these targets. LazyGNN [4] belongs to the same family of linear propagation and both were designed for transductive large-scale tasks. Finally, we note that GHR also captures long-range dependencies without stacking trainable layers, since its depth comes from a single layer iterated.

W5

Limited hierarchical and pooling baselines.

Following the Reviewer suggestion, we also evaluated DiffPool, MinCutPools and Graph U-Net on ECHO-Synth. DiffPool and MinCutPool were designed for graph-level tasks, and we adapted them to node-level prediction by unpooling through their assignment matrix with a skip connection. We report the ECHO-Synth benchmark results.

ModelSSSPECCDIAM
APPNP5.629±0.0325.629\pm0.0326.111±0.0206.111\pm0.0205.069±0.0555.069\pm0.055
DiffPool4.93±0.454.93\pm0.454.90±0.684.90\pm0.684.30±0.174.30\pm0.17
Graph U-Net4.74±0.484.74\pm0.484.98±0.334.98\pm0.332.07±0.232.07\pm0.23
MinCutPool5.02±0.095.02\pm0.095.04±0.565.04\pm0.564.54±1.134.54\pm1.13
GHR-GINE (Ours)0.035±0.0040.035\pm0.0043.456±0.0413.456\pm0.0410.749±0.0230.749\pm0.023

As expected for architecture not designed for tasks requiring precise propagation over many hops, these models do not match long-range baselines. A comparison with a virtual nodes model is already in LRIM benchmark (Tab. 3) where GHR improves over it in all settings.

The results are added to the revised manuscript in Tab. 7 in App. C.3

Experiments on ECHO-Chem, computationally more expensive, are running, and we will add them during the discussion period if they complete in time, or in the final version.

AuthorsOpenReview ↗

Response to Reviewer R6yi (Weakness 6 and Refs)

W6

On LRIM-16-hard, LogMSE degrades [...]

We would like to clarify that graclus on LRIM in Tab. 13 is an ablation of coarsening, run with the hyperparameters selected for 2×22 \times 2 block pooling, without any tuning. Its controlled comparison is the same model without the coarse stream, which graclus improves from −2.294-2.294 to −3.630-3.630. The 16-layer GatedGCN is a separately tuned feedforward model that shares only the MP operator with GHR. Nevertheless, to address the reviewer's concern, we tuned GHR with graclus, which achieves a LogMSE of −4.019±0.073−4.019 \pm 0.073, improving over GatedGCN (−3.844-3.844).

Random partitioning [...]

As discussed in App. D.1, LRIM depends on global aggregates which explains why random partitioning helps there. Nonetheless, by comparing to the same model without the coarse stream, every coarsening improves, even a random partition, highlighting the benefit of the hierarchy.


References

[1] Yehudai et al., “From Local Structures to Size Generalization in Graph Neural Networks”. ICML (2021)

[2] Gasteiger at al., “Predict Then Propagate: Graph Neural Networks Meet Personalized Pagerank”. ICLR (2019)

[3] Miglior et al., “Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation”. ICLR (2026)

[4] Xue et al., “LazyGNN: Large-Scale Graph Neural Networks via Lazy Propagation”. ICML (2023)

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.