GLoRa: A Benchmark to Evaluate the Ability to Learn Long-Range Dependencies in Graphs
Authors: Dongzhuoran Zhou
Evgeny Kharlamov
Egor V. Kostylev
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Learning
Graph Neural Networks
Synthetic Benchmarks
Long-Range Dependencies
Primary area: learning on graphs and other geometries & topologies

Abstract: Learning on graphs is one of the most active research topics in machine learning (ML). Among the key challenges in this field, effectively learning long-range dependencies in graphs has been particularly difficult. It has been observed that, in practice, the performance of many ML approaches, including various types of graph neural networks (GNNs), degrades significantly when the learning task involves long-range dependencies—that is, when the answer is determined by the presence of a certain path of significant length in the graph. This issue has been attributed to several phenomena, including over-smoothing, over-squashing, and vanishing gradient. A number of solutions have been proposed to mitigate these causes. However, evaluation of these solutions is currently challenging because existing benchmarks do not effectively test systems for their ability to learn tasks based on long-range dependencies in a transparent manner. In this paper, we introduce GLoRa, a synthetic benchmark that allows testing of systems for this ability in a systematic way. We then evaluate state-of-the-art systems using GLoRa and conclude that none of them can confidently claim to learn long-range dependencies well. We also observe that this weak performance cannot be attributed to any of the three causes, highlighting the need for further investigation.

Published as a conference paper at ICLR 2025
GLORA: A BENCHMARK TO EVALUATE THE ABILITY TO LEARN LONG-RANGE DEPENDENCIES IN GRAPHS
Dongzhuoran Zhou & Evgeny Kharlamov
Bosch Center for AI, Germany and University of Oslo, Norway [dongzhuoran.. zhou, evgeny. kharlamev) @de. bosch.com
Egor V. Kostylev University of Oslo, Norway egorkêifi. wwt.iiiii.ioonn.. no
ABSTRACT
Learning on graphs is one of the most active research topics in machine learning (ML). Among the key challenges in this field, effectively learning long- long-range dependencies in graphs has been particularly difficult. It has been observed that, in practice, the performance of many ML approaches, including various types of graph neural networks (GNNs), degrades significantly when the learning task involves long-range dependencies that is, when the answer is determined by the presence of a certain path of significant length in the graph. This issue has been attributed several phenomena, including over-smoothing over-squashing and vanishing gradient. A number of solutions have been proposed to mitigate these causes. However, evaluation of these solutions currently challenging because existing benchmarks do not effectively test systems for their ability to learn tasks based on long-range dependencies in transparent manner. this paper, we introduce GLoRa, synthetic benchmark that allows testing of systems for this ability in a systematic way. We then evaluate statc-of-the-an systems using GLoRa and conclude that none of them confidently claim to learn long-range dependencies well. We also observe that this weak performance cannot be attributed to any of the three causes, highlighting the need for further investigation.
INTRODUCTION
Graph structures are very common in many domains, including molecules in chemistry, social networks on the Web, and road networks traffic management. Thus, it is not surprising that learning on graphs is among the most active topics in the theory and practice of ML. However, standard ML approaches such as classic deep neural networks, are difficult to apply to graphs due to their non-trivial structure, and dedicated approaches have been developed for learning on graphs. The most prominent are based on the idea of Graph Neural Networks (GNNs) (Scarselli et al. (2008). where each layer updates the vector embedding of each node by aggregating the embeddings of the neighbours from the previous layer and combining the result with the previous embedding of the node itself. There are many GNN variants proposed in the literature, from basic GCNs (Kipt & Welling 2017) and GraphSAGE (Hamilton et al., (0177) to more advanced methods such as Drew-GCN (Gutteridge al. 2023) with Laplacian encoding (Kreuzer al. [02TT.
Many GNN- based systems have had great success in various tasks in learning on graphs. However, it also observed that the performance of such systems degrades dramatically when the task involves learning long-range dependencies- -tat is, when the ground-truth answer for a node in the graph (or, for graph-level tasks, for the full graph) depends on interaction of nodes with large graph distance between them (Aln & Yahav 202 1). However, this property is crucial for tasks in many applications, and essential interactions along several dozen of graph edges are not uncommon. For example, in the Web context, tasks such social influence prediction (Qiu et al. 2018), social representation learning (Liu et al.] 2022). and item recommendation (Fan et al. 2019) rely on the wide spread of information in social network and user-item graphs. In urban data mining, long-range dependencies are evident in

---

Published as a conference paper at ICLR 2025
air quality (Iskandaryan et al. 2023) and traffic flow prediction (Li & Zhu 2021 In internet safety and finance, the challenges of fake news detection (Han et al.) 2020) and mnti-y laundering (Weber et al. 2018) critical to detecting such dependencies in the corresponding graphs. Finally, in biochemistry, long-range dependencies emerge in protein-proted interaction (Jha et al. (202)) and drug side effects prediction (Bongini et al. 2022). where the properties are influenced by long chains of atoms in molecule graphs.
Numerous works address the long-range dependency learning issue by trying to identify its causes and suggesting methods to mitigate these causes. Most prominently, the long-range issue was attributed to three phenomena: wwer-smoothing (Li et al. 2018), which is an observation that in many GNN architectures the embeddings of all nodes converge to the same constant vector as the number of layers increases; over- squashin (Alon & Yahav 202T), concerning that the information from many nodes that are potentially relevant for the outcome of the target node has to be compressed into a fixed-size vector; and more classical vanishing gradient (Glorot & Bengio (010)) saying that, as the number of layers increases, the gradient magnitude of the loss usually decreases, thus slowing training down.
Several methods have been proposed to mitigate each of these phenomena. However, as a starting point for this paper, we observe that there are no methods that can with certainty verify whether an ML system is able to learn dependencies of given length. Indeed, such systems are often evaluated
on benchmarks based on real-life datasets (Dwivedi et al. 2023 Morris et al. 2020). whose properties not known and not controlled enough to give any guarantees. For example, even if an ML system performs relatively well on such a benchmark, we do not know whether the function to learn and the function the system really learned rely on long-range dependencies. There are also number of
dedicated synthetic benchmarks (Di Giovanni et al.) 2023) Bodnar et al.) [021]] Alon & Yahav 202T to evaluate the long-range performance of such systems. Unfortunately, as we will see in more detail
later on, these benchmarks are also not suitable for such guarantees, because they either allow simple functions that do not rely on long-range dependencies but perfectly fit the data examples, or, on the contrary, do not have fitting functions expressible in the GNN architectures.
The main contribution of this paper overcomes these shortcomings; in particular, we present a synthetic benchmark (more precisely, algorithm that generates a benchmark for every dependency length) and a method how to use this benchmark to identify, with certain guarantees, how long dependencies a graph learning system can learn. As our second contribution, we evaluate the state-of- the-art systems using our method, concluding that their dependency length limit is always very modest. As final contribution, we demonstrate, by means of dedicated experiments, that the degradation of performance with increasing length cannot be attributed to any of the three phenomena. Therefore, further investigation is required to identify the real cause of the long-range dependency learning issue and to develop new methods to mitigate this issue.
The rest of the paper is organised follows. In Section 2 first specify the typical graph ML tasks and formally introduce the long-range dependency issue, concentrating on a variant of formalisation that we call path-awars Then we discuss possible causes for this issue identified in the literature and proposed evaluation methods; thus, Sections and [244] give an overview of the most essential related work for this paper. Finally, we argue that these methods are not satisfactory, thus justifying the need for our benchmarks. We present our benchmark, which we call GLoRa (Graph Long- Range dependency benchmark), in Section 3 where we include detailed intuition and formal justifications that GLoRa benchmarks possess the desired formal properties. Then, in Section 4 we report the results of our experiments. The main experiment demonstrates that none of the state-ol-the-ee systems can learn dependencies beyond the very modest length 11. Secondary experiments demonstrate that this degradation cannot be attributed to any of the three phenomena. We conclude in Section [3] Secondary supporting materials for the claims of the paper are given in the appendices.
2 THE CHALLENGE OF LEARNING LONG-RANGE DEPENDENCIES
In this section, we first introduce typical graph ML tasks and graph neural networks as the standard approach to solving these tasks. We then formalise the long-range dependency learning issue, discuss its possible causes, and overview the existing benchmarks for this issue. Finally, we argue that these benchmarks are not satisfactory, thus justifying the need for our benchmark (presented in Section 3)
2

---

Published as a conference paper at ICLR 2025
2.1 LEARNING ON GRAPHS
As customary in the context of graph ML, we formalise a graph as a triple &V.E, A), where V is a finite of nodes, & C V is set of edges, which are pairs of nodes, and A V R is the node embedding, which is an assignment of real-valued vectors of some dimension v. E N to the nodes.
Note here that we assume edges to be directed; undirected graphs, which are sometimes adopted in graph learning, can be represented in this formalisation by assuming that & is symmetric-ttht is, such that (V1, 02) E & implies (U2, u1) &. As we will see later, our benchmark has a version for both the directed and undirected settings, and our experiments show that each considered existing system performs similarly across these versions; however, the directed version has conceptual advantage, which ensures stronger guarantees (see Section 4.2). Note also that only nodes in our graphs have embeddings; this is just for brevity, and all our ideas apply to graphs with edge embeddings.
The most common MI. task on graphs is (supervised) node classification, where system needs to learn, using training examples, a function that assigns a class (called a label in this context) from a finite set to each graph node. Binary classification is particular case when there are only two classes, True and False. Another common task is node regression, where the function assigns a numeric value instead of a class. Both classification and regression may be transductive, when all relevant nodes (for all training, validation, and testing) belong to the same graph, fully known for training. The more general is the inductive setting, where each example may have its own graph (with the same node embedding dimension). Tasks very close in essence to the inductive tasks are graph classification and regression, where a value is assigned to the entire graph. our presentation, we concentrate on inductive binary node classification, but all our ideas transfer directly to the other settings.
2.2 GRAPH NEURAL NETWORKS
In principle, we can use many ML approaches to graph learning. However, usual methods, such as deep neural networks, have limited applicability in setting, because graphs may be of arbitrary size (e.g.. a model trained on small graphs should be applicable to arbitrarily bigger graphs); moreover, a graph learning model is expected to be agnostic to graph representation- be invariant over reshuffling of nodes and edges in the model's input. Thus, a standard neural architecture for graph learning is paessing- graph neural networks (GNNs); in general form, a GNN A with L layers for classifying nodes with embedding dimension n to classes C' is a triple
is, the answer should
((Ager)eet)...
(eomb:Jee(1......) Class)
where each aggregation function Agg, maps multiset of vectors of size n4-1 to such vector, each combination function Comb; maps two vectors of size 7ig-1 to a vector of size nhg, and classification function Class maps a vector of size nı to a class in C: here, n2 = n and each ny is the dimension of layer f. The aggregation, combination. and classification functions of GNN usually depend on learnable parameters of the model, while I, and each n4, f. E (1....; or among the hyperparameters. Given an input graph G = (V, A) with dimension n, GNN N computes, for each E ,,I...,,,,, the f-th embedding Vi of each v E V as
....,..) I.). are fixed in advance
Vz Comb Agge (1(
(())))),
where [t-1 ()) is the multiset constructor, each vo is A(v). and each (u) is the neighbourhood {u E V vu, E E) of a node e in G; then, the final classification of each is Class(VL))
A GNN example is graph convolutional networks (GCNs) (Kipf & Welling 2017) instantiating
as
Σ (O)(E) VIN(o) IN(
Wau-1
V1 =
where a is a non-linearity activation function, such as ReLU or sigmoid, and each W. is a learnable matrix of parameters (of dimension n& x nı-1)); the final dimension n is 1, and Class(v) just thresholds VL.
1); it may also be assumed that, for binary classification,
Many other variants of GNN are suggested in the literature (GINs (xu al. 2019). Graph- SAGE (Hamilton et al. 2017). GATs (Velickovic et al., 2018). etc.). Moreover, there are a number of proposals known GNN architecture, but apply modification of the input graph G rather
3

---

Published as a conference paper at ICLR 2025
than to G itself:; the most prominent such idea is to rewire G by adding and removing nodes and edges
according to some (often quite sophisticated) rule (Gutteridge et al. [023] Abboud et al. [022] Alon
& Yahav [021 Gasteiger et al., 2019b] Topping et al. 2022; Karbadkar et al. [2023). An extreme of
this idea is graph transformers (Dwivedi & Bresson, 2020; Kreuzer et al. 2021 Rampásek et al.
2022p. where edge is added between each two nodes, and an attention mechanism employed to
learn nontrivial dependencies. As we will see in the next section, several rewiring-based methods have been proposed to mitigate difficulties with learning long-range dependencies. Another idea to deal with long-range dependencies is realised by implicit GNNs (Gu et al., 2020; [iu et al., 2021 Chen et al., 2022), where the number of layers not predefined but the same transformation is applied many times until (approximate) convergence. We omit the details of these systems here, because in this benchmark paper we largely treat graph learning systems as a black-box.
Intuitively, node classification functions may be characterised by how long the dependencies they rely on tree-that is, how far the target node (i.e., the node to classify) may be from the nodes that this node needs to interact with to decide its classification. It has been observed many times in practice that the quality of learning node classification functions using standard graph learning methods (e.g.. GCNs) degrades dramatically when the function to learn relies long dependencies (Gutteridge
et al. 2023 Di Giovanni et al. 2023). As we will discuss in Section [2.]] this issue has been attributed to several causes, and number of methods
proposed mitigate this issue. However, we first
note that, to the best of our knowledge, the long-range dependencies are not yet formalised in the
context of graph learning, and only informal explanations have been suggested (Alon & Yahav] [00T]] Dwivedi et al. 2022). Since this issue is central to our paper, we next give such a formalisation.
In the following, let, as usual, simple path p from node v' to a node a graph (V, &, A) be sequence ub....: Vd of distinct nodes in V such that Uo = v', 22 = v, and (u3-1, 2x) E E for every i with 1 & d. Let then Gr(k,m], for every k, m with 0 < k S m < d, be the graph obtained from G by duplicating the part of p between 2k and Um Um-thatt that is, the graph with nodes V U (1/ ..... "' I; edges & LUE E", where E' contains an edge (u² u²) for each (u', E E,
V of length d in
such that each u² with h E (1, is oy. if th is 1, for some j with &s S j S m, and v² otherwise; and embedding X' extending A with ((u))) = Mez) for each j with k S j m.
Definition 1 A node classification function f for the node embedding dimension relies on (path- aware) dependency of length d if there is a graph G = (V,E,) A) with dimension n, a node u E V, a simple path p Uo. ... vd-1, v, and vectors a; F A(vs) in IR,, for each with 0 << i < d, such that
for each with 0 < <i< d, f(G, v) + f(G,, v) where the graph G. = (V,E,>) x*) is the same G except that X² (vx)) a, (i.e., in particular, X" (vv) = Mvv) for every v' A vz);
for each J, m with 0 s S m < d, V)
for Gpthmm) = -(V", ,',
the same as Gplkmm) except that X² (1)) aj:
for each i, K J. m with 0 i < d and k S j S d f(G,u) # f(G pk.,m) G (V", E" (²) the same Gplk.m) except that X (w:) = a, and X (x5) aj-
_u) for
This definition essentially says that there should be a node, u, in a graph with long enough path, p, leading to e that is really important for the classification of e: it should be possible to distort the embedding of any node in p to change the classification of o; moreover, a combination of p with duplicate of its part where an embedding of a node is distorted should not lead to the change of classification, while distorting both the path and the duplicate should.
We argue that such requirements for witnessing path reflect the intuition of what long-range dependency is. The examples of the real-life tasks in the introduction also essentially rely on these requirements. However, we agree that there may be other, inequivalent, formalisations of this intuition (e.g., one may waive the existence of a path to v, asking only for a node with some properties not too close to e); we add 'path-aware' to the notion to emphasise our choice.
2.3 POSSIBLE CAUSES FOR THE RANGE DEPENDENCY ISSUE
Since learning long-range dependencies is crucial in graph learning, there is a line of research that has focused on identifying and mitigating the causes of performance degradation with increasing dependency length. In particular, this issue is currently linked to three phenomena: over-smoothing (Li
4

---

Published as a conference paper at ICLR 2025
et al., 2018). over-squashing (Alon & Yahav 2021), and vanishing gradient (Glorot & Bengio 2010 Bengio et al. 1994). The graph learning community has developed several methods to mitigate these causes, which we discuss next.
Over-smoothing (Li ct al. 2018) causes the node embeddings to converge to the same vector as the number of GNN layers increases. This may hamper the effectiveness of many GNNs, especially GCNs, when many layers are needed, for example, to capture long-range dependencies. Methods to
mitigate over-smoothing include PairNorm (Zhao & Akoglu 2020), ResGCN and DenseGCN (Li
et al. 2019), Jet (uu et al. 2018), DropEdge (Rong el al.
2020), GPRGNN (Chien et al. 202 l).
DAGNN (Luu al. 2020). GCNII (Chen et al. 2020). IGNN (Gu et al. 2020 EIGNN (Liu et al.
2021 GIND (Chen et al. 2022). and G² (Rusch et al. 2023).
Over-squashing (Alon Yahav 202T refers the bottleneck of graph learning formalisms, including
GNNs, where information from many nodes condense into fixed-size vector of one node. In dense graphs, the number of paths to a target node may be exponential in the number of the GNN's layers.
Therefore, over-squashing can limit learning long-range dependencies in such graphs. Methods to
alleviate over-squashing include several variants of DRew (Gutteridge et al. (002). SP-GCN (Abboud
et al. 2022), FOSR (Karhadkar et al.) 2023), SRDF (Topping et al.) 2022). FA-GCN Alln &
Yahav 2021 p. DIGL (Gasteiger et 2011bb. Mixhop-GGe (Abu-El-Haija et al. 2019). ).. and graph
transformers, such as SAN (Kreuzer et al. 202T and GraphGPS (Rampásek et al. 2022)
Vanishing gradient (Glorot & Bengio 2010) is a common phenomenon in deep neural networks, including GNNs. As the number of layers increases, the gradient of the loss often decreases, slowing or even stopping the training. Well-known techniques to mitigate this in usual neural networks, such as
BatchNNrrm (loffe & Szegedy (0155), ResNet (He et al. 2015), and LSTM (Graves) 2012), have been
adapted for GNNs in systems G² (Rusch et al. (2023) Gradient-Guided Dynamic Rewiring (Jaiswal
al. 2022), , and Residual GANs (Lukovnikov & Fischer 2021).
2.4 EXISTING BENCHMARKS AND THEIR LIMITATIONS
Evaluation of the abilities of GNN-based methods to address the long-range dependency issue (e.g.. by mitigating the three phenomena) usually employs benchmarks based on real-world and synthetic datasets. We next discuss these benchmarks and argue that they are ill-suited for this purpose.
Many real-world benchmarks, such as Cora and Citeseer (Yang et al. 2016), Cornell and Texas (Pei al., 2020), and TUDataset (Morris et al., 2020) were not initially designed for long-range de- pendency studies. Others, such as OGB (Hu et al. (2020) and LRGB (Dwivedi et al. (022), were introduced specifically to assess the ability to mitigate the three phenomena. However, many of them have already been argued to lack significantly long-range dependencies (Dwivedi et al. 2022 Tönshoff al., 2023). Moreover, we observe that real-life benchmarks do not suit well for the purpose in general, because we do not have enough control over their functions to learn. In particular, we have no means to ensure that a function that perfectly fits all the examples actually relies on a dependency of a particular length; in fact, cannot even ensure that all the labels are justified by some properties of the inputs rather than being just noise. Thus, such benchmarks are only useful to conclude that one system is better than another on this particular benchmark, but not claim with confidence that a specific approach can learn a dependency of a specific length. So, to give such guarantees, we have employ synthetic benchmarks.
Several synthetic benchmarks designed for long-range dependency evaluation have also been pro- posed. They include Teig-biig (Alon & Yahav 2021). h-Proximity (Abboud al., (022). Graph Transfer and Ring Transfer (Di Giovanni et al., 2023 Gutteridge et al.) 2023), Synthetic Chains (Gu al. 2202), Color-Connecctvitty (Rampásek
Wolf 2021), Conditional Recall, and Tree Max (Lukovnikov & Fischer 202I). The common principle in their design is that they label nodes in rather simple graphs using a known function that relies on dependency of a specific length. However, we argue that this is not enough: we also need to ensure that there is no other classification function that fits all the generated examples, but does not rely on long-enough dependency; moreover, we also need to guarantee that there exists such a Long-range function that is in principle expressible in the tested graph learning architecture- -that is, that there exists an instance of the architecture (e.g..
GCN) that realises, in uniform way, this function (see) Barceló et al. (2020) and Grohe (2023) for the details of such expressibility and related notions (Xu et al.] 2019 Morris et al., 2019] Grohe (203)). Unfortunately, none of the synthetic benchmarks mentioned above satisfyy these two properties. For
5

---

Published as a conference paper at ICLR 2025
T
Figure 1: Positive (left) and negative (right) GLoRa examples for d == 6: green (i.e., source), blue (normal), and orange (hole) nodes have embeddings of form [1, -1. [-, 1], and [-, 0), respectively; T marks the target node; the red-arrows chain is the long-range dependency path
example, in the Synthetic Chains benchmark (Gu et al. 2020), the graph in each example is directed chain, where the tail node is labelled True or False depending on whether the start node has or 0 as the first element of its initial embedding vector. These examples indeed generated by means of function that relies on a long dependency (in particular, of the length of the longest chain). However, it is possible perfectly solve this benchmark by a (learned) function that ignores the distance and path information, and only checks whether there somewhere in the graph there is node without incoming edges with or 0 as the first element. More detailed justification for this and other synthetic benchmarks are in Appendix D The main contribution of this paper is benchmark generator GL.RRa, which produces benchmarks satisfying the two crucial properties.
BENCHMARK GENERATOR GLORA
In this section, we present the main contribution of this paper: an algorithm GLoRa that generates benchmarks (i.e., sets of training, possibly validation, and test examples), which can be systematically used check the ability of system to learn functions relying on dependencies of specified length. In particular, our benchmark generated for length d ensures the following properties.
(P1) All node classification functions fitting the training examples rely on dependency of length with arbitrarily high precision and probability.
(P2) There exists such function that expressible by all GNN-based graph learning approaches aware of (including GCNs).
(P3) The benchmark is fair-thal is, all examples come from the same distribution.
Before we start with intuition, we note that our benchmarks have two versions: one with directed and one with undirected graphs. However, in the following presentation we concentrate on the directed version, while the generalisation to undirected graphs is straightforward.
3.1 INTUITION
Our benchmark for the dependency of length d uses graphs with dimension 2 and relies on the following intended binary classification function, which clearly relies on the dependency of length d.
(F) The target node is classified as True if and only if there is a path of length to d from node with embedding of the form [1, - (which we call the source node) the target node such that all nodes along the path, except the source, have embeddings [-, 1]; here, represents any number different from 1.
A naive benchmark for this function would use the following examples: a positive example will have chain of length d or slightly less the graph, starting from a source node with embedding [1, -). ending at the target node, and such that all nodes along the chain except the source have embedding [-. 1]: turn, each negative example the same, except that one intermediate node has [-, 0) instead of [- (in what follows, call node with [-.0] embedding hole).
This approach, however, would not lead to a benchmark that satisfies property (PI). Indeed, it would be possible to perfectly fit all these examples by learning much simpler function, which does not depend on any significantly long-range dependency; for instance, one such function classifies the target node True if and only if there is node anywhere in the graph, except the target node, with embedding [-, (i.c., where both elements are not l). Thus, the model that learned this 'shallow' alternative can perfectly classify all the examples of this benchmark.

---

Published as a conference paper at ICLR 2025
Algorithm 1 GLoRa Benchmark Example Generation
Input: Length 2 3. label Ans {True, False)
Output: Graph-node pair (G, 1) labelled Ans
1: Let D [-12, 2 [3, 13]
Part Create the main chain 8/
2: Let G = (V,,, A) with kn 2 1//12//......................... dl.....d)).
v== [v8 --- v0 J. E {(1g (1) iE .......ool
M(rg)=== = (L. ( with 86 ~(D). A(v)) (1 with = U(D) for each (I....,ka)
3: if Ans = False then
4: Set "xx0))= = (a)), 0) with bg ~ U(f1....... ko 1})
1* Part B: Add alternative chains %/
5: Let P~ (P((5..... 10))
6:
for p to do
7:
Let Let U(f12/3 (2112/3-d// d]. ...,, d}) and mp, ue ~ U(f,,..., ...,, hp 11) assuming my I np
8:
Let ~ U(fu," EV m, = 1ky (my - -1)/k + 1/2[{)
9:
Let ~ U(fo)' EV ny 1ky (mp + 11/kp + 1/2
Add fresh op ..... up to V and (v', "²") (vp up )) ). ..... (0p 10 oop ")))) (ub" "d"" "o") Eo
10:
letting X(e)) = (o 1) with 2 U(D) for each E (
11:
Set (( = (0 0) with hp ~ U((mp....,mp)
1a Part C: Add additional holes */
12: Let R ~ U((2,3) 3)) and V = V/ (rgg "
13: if Ana True then
14: Set Rl == R 1 and V V" (0g l (L...., 1))
15: ror 1 to do
16: Set A(o5) = (af. 0) with of ~ U(V)
17:
return (G, v0
To ensure (PI), while preserving (P2), GLoRa adds to the chain-like graphs as in the naive approach alternative paths with holes (i.e., [] embeddings) from the source to the target; this is illustrated in Figure T The embeddings on these extra chains also ensure that the number of holes cannot be used as distinguishing property between positive and negative examples; same should hold for more complex properties, such as the number of holes on paths between a [1, --ssuuce node and the target node. As we will see formally in Theorem [ such an approach ensures that any GNN-based function fitting (a sufficient number of) such examples rely on a dependency of length d. So, we can use GLoRa for length to check if system can learn functions with dependency of length (c.g.. d = 6 in Figure []. Moreover, we can use a sequence of the benchmarks with increasing d to identify the limit of system that is, the maximal length for which it can learn the dependencies.
3.2 GENERATOR ALGORITIM AND GUARANTEES
The pseudocode that generates GLoRa example is given in Algorithm I Since each benchmark is parameterised by length d, this number is one of the inputs of the algorithm. The second input, Ans, ranges over classes True and False-that is, specifies whether the example is positive or negative. It is assumed that GLoRa for given depth d contains a sufficiently large balanced number of examples generated by this algorithm in its training, validation (possibly), and test sets. Note that the algorithm has a large degree of randomness, and the notation X ~ U(S) means that X is sampled, uniformly at random and independently of other samplings, from a set S. The algorithm consists of three parts.
In Part A (lines 2-4), the algorithm generates the main chain, which either has no holes, if the example positive, or one hole (i.e., a [- 0] embeeded node), otherwise. The chain length is not predetermined, but sampled randomly from (rounded) 2/3 of d to d, so that the exact length cannot be used by systems in learning. The main chain starts in source node of with embedding [1, []. while all other nodes have embeddings [-, 1] or [- 0] (i.e., the hole); these nodes include the target node *o
In Part B (lines 5-11), the algorithm adds several (5 to 10) alternative chains with the ends the previously generated chains (main or additional). The construction ensures (lines 7-9) that there are loops and the length of the path from the source to the target corresponding each additional
7

---

Published as a conference paper at ICLR 2025
chain is within the same bounds the main chain. Each additional chain has hole, that only the path along the main chain determines the example is positive or negative. Note, however, that a model does not know which nodes belong to the main chain, so it has to explore all of them.
Finally, in Part C (lines 12-17), the algorithm adds several holes so that each individual path from the source to the target does not have a predetermined number of holes. It also ensures that positive examples remain positive (i.e., that the main chain has no holes), and that the distribution of the number of holes in the positive and negative examples is the same.
We next argue that GLoRa possesses properties (PI)-(3).. Property (P1) is the most sophisticated and is ensured by the following theorem (proved in Appendix C). We use several new notions. First, we introduce an approximate version of Definition ! node classification function ff relying on dependency of length d with precision 5 > 0 is the same as in Definition
I except that X in each item is required to match X, aj, and a, (when relevant) only with precision ò (under the maximum norm), while the difference between each a; and X(v)) should have the gap at least 36 ttha is, we require, for example, ||X (w:) ailloc S ô instead of X (v.) = a, for each and |a, - X(xx)ll>o 2 36 instead of a; + M(e.). Then, a set of examples for node classification requires learning dependencies of length d with precision 5 > 0 if each function that fits all these examples relies on such a dependency.
Let d E N be length. Then, for every 8 > O and P (0, there exists number K such that a set of K examples, half generated by GLoRa(d, True) and half by GLoRa(d, False), requires learning dependencies of length d with precision d with probability at least P.
Theorem
Moving on to property (P2) we note that the results of Barceló et al. (2020) imply that GCNs can express our intended function (F). We also observe that virtually all other known GNN-based classification approaches are more expressive than GCNs, which implies (P2). Finally, property (P3)
is automatic since the same (probabilistic) algorithm is used for generating all examples.
In the passing, we note that our algorithm can be easily adapted to undirected graphs.
4 EMPIRICAL STUDIES
In this section, we report our results on the evaluation of existing systems' ability to learn long- range dependencies. We begin with the setup of our main experiment, which is based on GLoRa benchmarks. We then present our results, demonstrating that, although some systems perform better than others, none can effectively learn dependencies of significantly long length. Finally, we show that this rather weak performance cannot be attributed to any of the three phenomena.
4.1 MAIN EXPERIMENT SETUP AND RESULTS
If a system for learning binary node classification claims that it can learn dependencies of length d, then it should show (nearly) perfect testing accuracy on benchmark generated using GLoRa example generator for length d. So, we can find the length limit of a system by running it on such benchmarks with increasing values of d until the accuracy drops from nearly I values close to 0.5.
For our experiment, we generated 5000 positive and 5000 negative examples using Algorithm I for each d E (3, .3,.... 15), and split each half with the ratio 10:10:10 to training, validation, and test sets.
Having these GLoRa benchmarks at hand, we evaluated state-of of-the-art systems from four categories:
1. vanilla GNN-based systems (i.e., not designed to deal with long-range dependencies):
GCN (Kipf & Welling 2017). GAT (Velickovic et al., 2018), GraphSAGE (Hamilton et al..
2017). GatedGCN (Bresson & Laurent 2017). GGNN (Li et al. 2016). SGC (Wu et al. 2019 and GIN (Xu et al. 2019);
2. GNN-based systems targeting over-smoothing: GCNII Chen et al. 2020), PairNorm ZZhao & Akoglu, 2020). DropEdge (Rong et al.] 2020), GPRGNN (Chien et al. 202 l). DAGNN (Liu et al. 2020). APPNP (Gasteiger et al. 2019a), ResGCN and DenseGCN (Li ett al.) 2019), as well as their variants ResGatedGCN, DenseGatedGCN, ResGAT, and
DenseGAT with explanaaly names, JKNet (Xu et al. 2018), IGNN (Gu et al. 2020).
EIGNN (Liu et al. 2021), GIND (Cen et al. 2022). and G² (Rusch et al. 2023)
8

---

Published as a conference paper at ICLR 2025
3. GNN-based systems targeting over-squashing (and vanishing gradient): DDDew-GCM for
y/ E {1. ) and Dreww Brew-GCN+LapPE (Gutteridge et al. 2023). SP-GCN (Abboud et al.
2022). FA-GCN (Alon & Yahav 2021). DIGL (Gasteiger al. (2019b), MixHop- GCN (Abu
El-Haija et al. 2019). SDRF (Topping et al.
2022), and FOSR (Karhadkar et al. 2023);
4. transformer- based systems Vaswani et al. 2017):
GraphTransformer (Dwivedi & Bresson
2020). SAN (Kreuzer et al. 2021). and GraphGPPS (Rampásek et al. 2022). where the last
uses either RWSE LapPE positional encoding.
We run each system on each benchmark five times, training for maximum of 300 epochs until convergence, validating hyperparameters, and computing the average testing accuracy over the five runs. For the GNN-based systems, we set the number of layers as d-22, which is always enough to express (F). Further details on the experiment setting are given in Appendix
1.0
0.9
0.7
0.6
0.5
10
12
14
GCN
GraphSAGE
GIN
In Figure 2 we present test accuracy results for the best five systems in each of the first three categories; detailed results for the other systems, including the transformer-based ones, which perform badly even for very short d, are given in Appendix [ Since our benchmark is noise-free, accuracy 1.0 is reasonable target. Moreover, since this is a binary classification task, random guessing has accuracy 0.5. So, curacy below 0.8 is an indication that the model has not effectively learned any function that fits the examples that is, cannot learn dependen- cies of the given length.
GatedGCN
(a) Vanilla GNN-based systems
1.0
neguracc
0.8
0.7
0.6
0.5
2
10
12.
14
16
d
DenseGCN
DenseCatedCCN
ResCatedGCN
(h) Systems targeting over-smonthing
In the figure, we can observe that most systems experience performance drop before d reaches 9, showing their inability to learn dependencies of significant length. We also see that some systems can Iearn longer dependencies little better; however, even their performance poor after d = 11. Notably, the best performance is achieved by systems that use gated edges that is, GatedGCN, and its variants DenseGatedGGNN and ReeSGatteGNNNSuugeeee may be starting point for GNNs that can truly learn range dependencies.
Recurney
0.8
0.7
0.6
10
12
14
16
Drew
<Drew-GGN
SP.GN
DDeww-GCN + LapPE
MixHop-GCN
that this feature
(c) Systems targeting over-squashing
Figure 2: Test accuracy of based systems on
In summary, while some systems perform better than others, none can reliably claim to be able learn dependencies much longer than of quite modest length 11. We also note that, as we report in Appendix E. the performance of all the systems in the undirected setting is very similar.
GLoRa benchmarks for increasing d (lines rep- resent mean accuracy over multiple runs, shaded areas indicate the standard deviation)
4.2 OVER- -VER-SMOOTHING, OVER-SQUASHING VANISHING GRADIENT ARE NOT THE REASON
Finally, we argue that, rather surprisingly, none of the three phenomena owoo-smootiing over- squashing, vanishing gradient- is the reason for the dropping performance in the main experi- ment. In this section, we focus on the best-performing systems in the three categories (GatedGCN, DenseGatedGGN, and IDrew-GNN) but the same arguments apply the other systems.
We first argue that smootshg not a reason for the performance drop in all three systems. To justify claim, considered the largest d for which the accuracy for all systems and

---

Published as a conference paper at ICLR 2025
5000
5000
5000
15-layer
4000
15-layer 6-layer
15-layer
oount
5000
8 8-bayer
count
5000
Soun
3000
8 layyer
2000
2000
2000
1000
-3.0
-0.5
0.0
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
last layer output value
last layer output value
last. layer output valiee
(a) GatedGCN
(b) DenseGatedGCN
(c) IDrew-GCN
Figure 3: Histograms of the last-layer values for the best-performing systems
n.9 on5
0.00
0.19
gradieu whess
grdiem ralies
wsd
gradiont values
0.00
(0y
spedis
-3
10.0
1.0
opecits
-0.0
130
spochs
200
200
(a) GatedGCN
(b) DenseGatedGCN
(c) IDrew- GCN
Figure 4: First layer weight gradients across max 300 epochs for best-performing systems
the smallest d for which the accuracy is close to 0.5: 6 and 13. For each case, we extracted the numeric value of the (I-dimensional) last (i.e., 8 and 15) layer embedding of the target node for each of the examples and plotted their histograms in Figure 3 As expected, when accuracy is good, the last-layer embeddings are clearly separated, while when accuracy is poor, they are more mixed together. However, even in the latter case they still do not converge-ther is, have rather significant standard deviation. In other words, we do not observe ovor-smoothing in any of the three cases.
We next argue that over-squashing is also not the reason for degradation for the systems. In fact, this guaranteed by the construction of GLoRa examples. Indeed, since each example has P additional chains, which is at most 10 (line 5 in Algorithm 1.. there is small (and independent of d) bound on the number of paths leading to the target node. Therefore, over-squashing. which concerns the compression of the information from many (exponential number of) paths to single vector, is not relevant here. Note that directedness of the graphs crucial for this argument: in undirected graphs, single chain to the target node would induce exponential (in d) number of paths leading to this node, and so making such a claim would not be possible.
We finally argue that gradient vanishing is also not the reason for the performance degradation of the three systems. This phenomenon is primarily caused by the fact that the chain rule in backpropagation results in exponentially smaller gradients in previous layers, making training difficult when there many of them. We plotted, in Figure 4 the distribution of the first layer gradients across multiple epochs for the three systems. As we can see, the gradients remain stable throughout training, with magnitudes well above zero, indicating no vanishing. As we report in Appendix [F] the systems have similar behaviour on other layers. This suggests that gradient vanishing not the reason for their inability to learn dependencies for the corresponding d. As a side comment, we note that the standard techniques against gradient vanishing, such as Adam W, weight initialisation, gradient clipping, ReLU activation, and batch normalisation are all employed during training for all the systems.
5 CONCLUSION AND FUTURE WORK
The main contribution of this paper is GLoRa, a generator of synthetic benchmarks that allows us to evaluate graph-learning systems in terms their ability to learn long-range dependencies. Using GLoRa, we have demonstrated that none of the state-of-the-art systems can learn dependencies longer than a very modest length of 1.. We have also shown that this degradation cannot be attributed to the over-smoo squa-squ,,,,ng, vanishing gradient. This opens up two directions for future research: to identify the real causes of this degradation and to develop methods to overcome it.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
The work was partially supported by EU Projects Graph Massivizer (GA 101093202), Dome 4.0 (GA 953163), enRichMyData (GA 101070284), and SMARTY (GA 101140087), and the Research Council of Norway through its Centres of Excellence scheme, Integreat- -Nowwegian Centre for knowledge-drie driven machine learning, project 332645.
REFERENCES
Ralph Abboud, Radoslav Dimitrov, and Ismail ilkan Ceylan. Shortest path networks for graph property prediction. Learning on Graphs Conference (LoG), 2022.
Sami Abu- -l--aaa Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional ar- chitectures via sparsified neighborhood mixing. In International Conference on Machine Learning (ICML), pp. 21-29, 2019.
Uri Alon and Eran Yahav. On the bottleneck of Graph Neural Networks and its practical implications. In International Conference on Learning Representations (ICLR), 2021.
Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva.
The logical expressiveness of Graph Neural Networks. In International Conference on Learning Representations (ICLR), 2020.
Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Transactions on Neural Networks, 5(2):157-166, 1994.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Liò, Guido F. Montúfar, and Michael M. Bronstein. Weisfeiler and Lehman go cellular: CW networks. Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 2625-2640, 2021.
Pietro Bongini, Franco Scarselli, Monica Bianchini, Giovanna Maria Dimitri, Niccolo Pancino, and Pictro Lio. Modular multi-source prediction of drug side-effects with DruGNN. IEEE/ACM Transactions Computational Biology and Bioinformatics, 20(2):121111220, 2022.
Xavier Bresson and Thomas Laurent. Residual gated Graph ConvNets. CoRR, arXiv:1711.07555 [cs.LG], 2017.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep Graph Convolutional Networks. In International Conference on Machine Learning (ICML), pp. 1725- 1735, 2020.
Qi Chen, Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Oppimization-induced graph implicit nonlinear diffusion. In International Conference on Machine Learning (ICML), pp. 3648-3661, 2022.
Eli Chien, Jianhao Peng. Pan Li, and Olgica Milenkovie. Adaptive universal generalized PageRank Graph Neural Network. In International Conference on Learning Representations (ICLR), 2021.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise. Pictro Lio, and Michael M. Bronstein. On over-squashing in message passing neural networks: The impact width, depth, and topology. In International Conference Machine Learning (ICML), pp. 7865-7885, 2023.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks graphs. CoRR, arXiv:2012.09699 [cs.LG]] 2020.
Vijay Prakash Dwivedi, Ladislav Rampásek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking Graph Neural Networks. Journal of Machine Learning Research, 24(43):1 2023.
11

---

Published as a conference paper at ICLR 2025
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Yihong Eric Zhao, Jiliang Tang, and Dawei Yin. Graph Neural Networks for social recommendation. In The World Wide Web Conference (WWW), pP- 417-426, 2019.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph Neural Networks meet personalized PageRank. In International Conference on Learning Representations (ICLR), 2019a.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 13333- 13345, 2019b.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In International Conference Artificial Intelligence and Statistics (AISTATS), pp- 249-256,20 2010.
Alex Graves.
Supervised Sequence Labelling with Recurrent Neural Networks, volume 385 of Studies in Computational Intelligence. Springer, 2012.
Martin Grohe. The descriptive complexity of Graph Neural Networks. Symposium on Logic in Computer Science (IJCS), pp. 1-14, 2023.
Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui Implicit graph neural networks. Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 11984-11995, 2020.
Benjamin Gutteridge, Xiaowen Dong, Michael M. Bronstein, and Francesco Di Giovanni. Drew: Dynamically rewired message passing with delay. In International Conference on Machine Learning (ICML), pp. 12252-12267, 2023.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Annual Conference on Neural Information Processing Systems (NIPS), pp. 1024-1034, 2017.
Yi Han, Shanika Karunasekera, and Christopher Leckie Graph Neural Networks with continual learning for fake news detection from social media. CoRR, arXiv:2007.033. 60 [cs.SI], 2020.
Kaiming He, Xiangyu Zhang, Shaoging Ren, and Jian Sun. Deep residual learning for image recognition. CoRR, 1riiv.1512.03338 [cs.LG] 2015.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. International Conference on Muchine Learning (ICML), pp- 448-456 2015.
Ditsuhi Iskandaryan, Francisco Ramos, and Sergio Trilles Graph Neural Network for air quality prediction: A case study in Madrid. IEEE Access, 11:2729-2743 2742, 2023.
Ajay Jaiswal, Peihao Wang, Tianlong Chen, Justin F. Rousseau, Ying Ding, and Zhangyang Wang. Old can be gold: Better gradient flow can make vanilla-GCNs great again. In Annual Conference on Neural Information Processing Systems (NeuriPS), 2022.
Kanchan Jha, Sriparna Saha, and Hiteshi Singh. Prediction of protein interaction using Graph Neural Networks. Scientific Reports, 12(1).8360, 2022.
Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montúfar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In International Conference on Learning Representations (ICLR), 2023.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
12

---

Published as a conference paper at ICLR 2025
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In Annual Conference on Neural Information Processing Systems (NeurIPS), pp- 11618-21629, 2021.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. DeepGCNs: Can GCNs go deep as CNNs? In International Conference on Computer Vision (ICCV), pp. 9267-9276, 2019.
Mengzhang Li and Zhanxing Zhu. Spatial-temporal fusion Graph Neural Networks for traffic flow forecasting, In AAAI Conference on Artificial Intelligence (AAAI), volume 35, pp. 4189-4196, 2021.
Qimai Li. Zhichao Han, and Xiao-Ming Wu. Deeper insights into Graph Convolutional Networks for semi-supervised learning. AAAI Conference on Artificial Intelligence (AAAI), pp. 3538-3545, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated Graph Sequence Neural Networks. International Conference on Learning Representations (ICIRR, 2016.
Hai Liu, Chao Zheng, Duantengchuan Li, Zhaoli Zhang, Ke Lin, Xiaoxuan Shen, Neal N. Xiong, and Jiazhang Wang. Multi-perspective social recommendation method with graph representation learning. Neurocomputingg 468:469 481, 2022.
Juncheng Liu, Kenji Kawaguchi, Bryan Hooi, Yiwei Wang, and Xiaokui Xiao. EIGNN: Efficient depth graph neural networks. In Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 18762-18773, 2021.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper Graph Neural Networks. In International Conference on Knowledge Discovery Data Mining (SIGKDD), 2020.
Denis Lukovnikov and Asja Fischer. Improving breadth-wise backpropagation in Graph Neural Networks helps learning long-range dependencies. In International Conference on Machine Learning (ICML), pp. 7180-7191, 2021.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order Graph Neural Networks. In AAAI Conference on Artificial Intelligence (AAAI), pp.
2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. CoRR, arXiv:2007.08663 [cs.LG], 2020.
Hongbin Pei, Bingzhe Wei, Kevin
Chang, Yu Lei, and Bo Yang. Geom-GCN: Geometric Graph Convolutional Networks. In International Conference on Learning Representations (ICLR), 2020.
Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. DeepInf: Social influence prediction with deep learning. In International Conference on Knowledge Discovery & Data Mining (ICKDDM), pp. 21 10-2119, 2018.
Ladislav Rampášek and Guy Wolf. Hierarchical Graph Neural Nets can capture long-range interac- tions. In International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1-6, 2021.
I Ladislav Rampásek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. In Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. DropEdge: Towards deep Graph Convolutional Networks on node classification. In International Conference on Learning Repre- sentations (ICLR), 2020.
T. Konstantin Rusch, Benjamin Paul Chamberlain, Michael W. Mahoney, Michael M. Bronstein, and Siddhartha Mishra. Gradient gating for deep multi-rate learning on graphs. In International Conference Learning Representations (ICLR), 2023.
13

---

Published as a conference paper at ICLR 2025
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network model. JEEE Transactions on Neural Networks, 20(1):61-800 2008.
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe. Where did the gap go? Reassessing the long-range graph benchmark. Transactions Machine Learning Research, 2023.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations (ICLR), 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Annual Conference on Neural Information Processing Systems (NIPS), pp. 19998-0088 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liō, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations (ICLR), 2018.
Mark Weber, Jie Chen, Toyotaro Suzumura, Aldo Pareja, Tengfei Ma, Hiroki Kanezashi, Tim Kaler, Charles Leiserson, and Tao B. Schardl. Scalable graph learning for anti-money laundering: first look. CoRR, arXiv:1812.0000 [cs:SI], 2018.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing Graph Convolutional Networks. In International Conference on Machine Learning (ICML), pp. 6861-6871, 2019.
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 (ICML). pp. 5453-5462, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations (ICLR), 2019.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learming (ICML), pp. 40-48, 2016.
Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling oversmoothing in GNNs. In International Conference on Learning Representations (ICLR), 2020.
14

---

Published as a conference paper at ICLR 2025
A
MAIN EXPERIMENT DETAILS
In this appendix, we give additional details of the settings of the main experiment in Section
A.1 STATISTICS OF THE BENCHMARK USED IN THE EXPERIMENT
Table 1 presents excerpt of the benchmark statistics. We created benchmarks for every E (3....,15), but, for readability, give the statistics only for those at intervals of that is, for depths of 5, 10, and 15.
Length d
Examples
Total Nodes
Average Nodes in Graph
Mean In-Degree
Total Edges
Average Edges Graph
Average
$
10000
19334
259154
26
10
10000
336606
33
2
401698
40
10000
497528
2
562624
56
Table Statistics of the synthetic benchmark generated by GLoRa with varying length d, where each column entry gives the number of the elements in the set of the column name; here 'Average S - ' stands for the average path length from the source node the target node, while other column names self-explanatory
A.2 BENCHMARK LICENSES
Our benchmark generator source code is available at attt://gtthloccco//oooooo/oozzzu under the MIT License.
A.3 SOURCE CODES FOR EVALUATED SYSTEMS
For the vanilla GNN-based systems (i.e., not designed to deal with long-range dependencies), GCN, GAT, GraPhSAGE. GGNN, SGC, and GIN, we used the implementations included into library PyTorch Geometric (see http://ituub..oo//ggteeeeee geemmtrrhgeomttrie)) The implementation of GatedGCN was taken from the repository of GraphGPS (Rampásek et al. 2022).
For the GNN-based systems targeting over-smoothing, used the PyTorch Geometric implementa- tions for GCNII, PairNorm, DropEdge, APPNP, JKNet, ResGCN, and DenseGCN, as well as the variants ResGatedGCN, DenseGatedGCN, ResGAT, and DenseGAT of the last two. The imple- mentations of GPRGNN, DAGNN, IGNN, EIGNN, GIND, and G2 were obtained from the original repositories reported in the corresponding papers.
For the GNN-based systems targeting over-squashing, the implementations of -Drew-GCN with SP-GCN, DIGL, and MixHop-GCN were taken from the repository of Drew (Gutteridge 123revisiiingggnn curvature Lastly, the FA-GCN architecture was re-implemented in in-house
E (1, 0c
et al. 2023), while SDRF and FOSR were taken from
For all transformer-based systems-thh that is, TraphTransformer, SAN, and GraphGPS with RWSE and LapPE-Wc used the implementations available the GraphGPS repository (Rampásek et al. 2022).
The overview of these sources is given in Table
A.4 COMPUTING ENVIRONMENT
All experiments were conducted in shared computing cluster environment utilizing various CPU and GPU architectures, including NViiaa V100 (16GB/32GB) and NVidia A100 (40GB/80GB) Each system allocated resource budget of 1 GPU, CPUs, and up to 32GB of system RAM.
15

---

Published as a conference paper at ICLR 2025
Category
Baseline
URLs
GCN, GAT; GraphSAGB
http://ghhubbboom//pyscccccoooop geometric
vanilla GNNs
GIN, GGNN, SGC
GatedGCN
GCNIL, PairNorm, DropEdge
ResGON, APPNP, ResGatedGCN
DenseGCN, JKtet, DenseGAT
ResGAT, DenseGatedGGN
GPRGNN
targeting over-smogthing
DAGNN
IGNN
https://ethub.
HIGNN
GIND
htt.:///wwnn/echciiiici httpss//gtthuu.ccmm//
G
DDeew-GCN, 1Drew-GCN
SP-GCN
DIGL
https//gtthu..com/
targeting over-squashing
MixHop-GCN
SDRF
http://gtttaaocommmmmeeuul////tu gon-curvatury
FOSR
FA-GCN
htpps//ggtabbbcmm//ooogzuuuuuuuu
GraphTransfommer
transformer--aaed
SAN
GraphGPS with RWSE and LapPE
Table 2: URLs for Baseline Model Source Codes
A.5 HYPERPARAMETER SETTINGS
The essential parameters and hyperparameters are as follows.
All experiments are trained for 300 epochs until convergence, with results averaged over 5 runs.
All experiments use batch sizes of 32.
All results use the AdamW optimiser with momentum 31 0.9, base learning rate search space [0.005, 0.01, 0.05], and weight decay space [0, 5e-6, 5e-4].
All experiments use batch normalisation with le-5, momentum=0.9.
For the GNN-based systems, the number of layers was set to d + 2, where is the depth of the benchmark (which, not surprisingly, was shown be best number of layers in all cases in additional experiments).
For MixHop-GCN, hyperparameter P is set of integer adjacency powers. The search space for is [3. 5, 7).
DIGL and GraphGPS configured to use GatedGCN the base model, as it delivers the best performance among MPNNs.
For DIGL, we employ PPR diffusion with a with search space [0.1, 0.2, 0.5, 0.9] and apply threshold sparsification with average degree dayg with search space [1, 2, 3, 5J.
GAT head search space is [1, 4, 8).
JKNet has three options of connection, i.e., concatenation, max, and Istm, which is also taken as a hyperparameter.
For GPRGNN, we the random walk path length K 10, and search for the best PPR within space a E [0.1, 0.2, 0.5, 0.9).
For GPS and SAN, layer number search space is [5...., 14).
B ADDITIONAL RESULTS OF THE MAIN EXPERIMENT
In this appendix, we report the results of the main experiment that are not included in the main body of the paper. In F show the testing accuracy GLoRa benchmarks with increasing d
16

---

Published as a conference paper at ICLR 2025
1.0
1.0
0.9
0.9
80ouracy
0.8
0.8
0.7
0.7
0.6
0.5
0.3
2
6
8
10
12
14
16
2
4
8
10
12
14
16
d
GAT
GGNN
ResGAT - G?
aорuracy
accuracy
0.8
0.8
0.7
0.7
0.6
0.6
0.5
0.5
12
14
10
12
16
DenseGAT
DropEdge APPNP
DAGNN
GPRGNN
GIND
EIGNN
PairNorm
JKNct
IGNN
1.0
1.0
0.9
0.9
accuracy
eccuracy
0.8
0.8
0.7
0.7
0.6
0.6
0.5
0.5
2
12
11
4
10
12
16
FOSR
TransTransf
GraphGPS with
RA-GCN
SAN
GraphGPS LapPE
Figure 5: Test accuracy of non-top-5 based systems GLoRa benchmarks for increasing (lines represent mean accuracy over multiple runs, shaded areas indicate the standard deviation)
for systems outside the top 5 in vanilla GNNs, GNNs targeting over-smoothing, GNNs targeting over-squashing, and all transformer-basse they are GAT and GGNN; for the GNNs targeting over-smoothing they are ResGAT, G2, DenseGAT, DropEdge, DAGNN, PairNorm, APPNP, GPRGNN, GIND, EIGNN, JKNet, and IGNN; and for the GNNs targeting over-squashing systems they are DIGL. SDRF, FOSR, and FA-GCN, For transformer- based methods, consider Graph Transformer, SAN, and GraphGPS.
methods. Specifically, for vanilla GNN-based systems
C PROOF SKETCH OF THEOREM
In this appendix, we give proof sketch of our theorem.
Theorem Let d E be a length. Then, for every > 0 and P E (0,1) there exists number K such that of K examples, half generated by GLoRa(d, True) and half by GLoRa(d, False), requires learning dependencies of length with precision ō with probability at least P.
Proof sketch. First, observe that, for the given d, there is only finite number of pairs V. & of sets of nodes and edges that can be the first two components of a graph generated by GLoRa algorithm with parameter d. Moreover, each of these pairs has non-zero probability of being generated. Moreover, D is bounded and the values are sampled from this set by the agorithm uniformly. So, for the given 5 and P, there is number K such that K generated examples include, with required probability, an appropriate number of examples that support the claim that is, such thar the approximated version of Definition I holds. Indeed, only need to ensure that the graph structures of each
17

---

Published as a conference paper at ICLR 2025
Desitive-negative pair agree with the required structure and between the two examples in the pair, and that their embeddings are within everywhere, except the designated differences.
D NON-SUITABILITY OF EXISTING SYNTHETIC BENCHMARKS
In this appendix, we provide a summary of existing synthetic benchmarks, each with its unique graph structures and target functions. Then explain why each of the existing synthetic benchmarks are not suitable for the purpose of checking whether a system is able to learn long-range dependencies.
Summary of existing synthetic benchmarks is follows:
Synthetic Chains (Gu et al. 2020). The graph structure in this benchmark is directed chain. The task is to classify nodes directed chain of length l. For simplicity, binary classification is used, with two types of chains. The class of each node is determined by the 1/0 encoding in the first dimension of the starting node's 100-dimensional feature vector. The training set includes randomly sampled nodes from these chains. The target function is that the node is true if and only if the starting node, which has no incoming edges, has a value of I in its first dimension.
Graph Transfer, Ring Transfer (Di Giovanni et al.. 2023 Gutteridge et al., 2023). The graph structures in these benchmarks are ring, crossed-ring. and clique-path, Ring graphs are cycles of size n. In each ring, there exist pairs of nodes that are placed at a distance of | from each other. One of these node pairs is chosen. One node in the pair has its class information encoded used to classify the other node. The target function is that there exists a node with a one-hot encoding node embedding in the graph. The class of the node at distance of [ from this node is the same as the one-hot encoded class. A similar setting applies in crossed-ring and clique-path.
one-hot vector (5 classes total) in its embedding, which is
Trie-Neigs (Alon & Yahav, 2021). The graph structure in this benchmark is directed binary tree, where the root and leaves have some additional 1- --hop neighbours pointing them. The target function is that the class of the root node is the class of the leaf node, which has the same number of 1-hop neighbors pointing to it as the root node. Here, the 1-hop neighbours do not include the nodes on the original binary tree.
h-Proximity (Abboud et al. 2022). The graph structure in the benchmark is defined as follows: (i) consecutive level nodes are pairwise fully connected, (ii) nodes within the same level are pairwise disconnected. Each node is either red, blue, or uncoloured. The target function states that the graph is positive if all red nodes in this graph have at most 2 blue nodes within their h-hop neighborhood.
(Rampášek & Wolf, 2021). The graph structure in the benchmark consists of 2D square grids. Each node is either red or blue. Red nodes are sampled by random walks starting from two random nodes until half the nodes red; the remaining nodes are colored blue. The target function states that the graph is positive if there is single connected island of red nodes, and negative if there are two disjoint islands of red nodes.
Conditional Recall (Lukovnikov & Fischer, 2021): The graph structure in Conditional Recall is a directed chain. The nodes in the chain are encoded as letters (both uppercase and lowercase) and digits. The target function is as follows: (i) if there is a digit in the sequence, the first digit corresponds to the class label of the chain; (ii) otherwise, if there is uppercase letter, the first uppercase letter is the class label; (iii) if neither digits nor uppercase letters are present, the class is given by the first character in the sequence.
Tree-Max (Lukovnikov & Fischer, 2021). The graph structure in Tree-Max is directed binary tree. The nodes in the tree are encoded digits. The target function is that the label of the node is the largest value of all the descendants of a node and the node itself.
The reason why each of the existing synthetic benchmarks are not suitable for the purpose of checking whether a system is able to learn long-range dependencies are as follows:
Synthetic Chains. Intuitively, to solve this benchmark, it is possible for the learned function to ignore the distance and path information, making global readouts like Virtual Nodes
18

---

Published as a conference paper at ICLR 2025
1.0
accuracy
0.8
0.8
0.7
0.7
0.6
0.6
0.5
0.5
8
12
14
10
16
GCN
GraphSAGE
GIN
GCNI DenseGCN
ResGCN ResGatedGCN
SGC
GaledGCN
DenseGatedGGN
1.0
accuracy
0.9
0.8
0.7
0.6
0.5
12
14
DDrew Drew GCN
SP.GCN
LDrew-GGN+LappE
GCNN
Figure 6: Test accuracy of best five systems in each category of vanilla GNN-based systems, systems targeting over-smoothing and systems targeting over-squashing on undirected GLoRa benchmarks for increasing (lines represent mean accuracy multiple runs, shaded areas indicate the standard deviation)
sufficient. In particular, such function does not rely on long-range dependency, because it does not satisfy the requirement that any intermediate node on justifying path can be dropped.
Graph Transfer and Ring Transfer. This benchmark has similar properties as Synthetic Chains and hence also can be perfectly fitted with similar function that does not rely on long-range dependency. Moreover, the design of these benchmarks allows only for five different examples (one for each class of the used multi-class classification), which makes the benchmarks limited use, because these five examples may be memorised by the system during training.
Neie-beggho.rs. Same the previous two cases, this benchmark can be perfectly fitted with a function that does not rely on long-range dependency, which is based on the same principle.
h- I-Porxxiity. In this case, the possible function that does not rely on long-range dependency is the one that does not rely on the embeddings of the nodes on the paths between any red node and the target node (thus not satisfying Definition Tp.
Calour-Conneetivityy On the contrary to the previous cases, this benchmark indeed requires learning function relying on long-range dependency. However, has an opposite issue: all the GNN-based systems amount of randomly generated training examples.
aware of cannot express any function that fits sufficient
Conditional Recall, Tree-Max. The graphs in these benchmarks have limited size, so is also possible solve each of them by using function that does not depend on long-range dependency.
E UNDIRECTED GRAPH EXPERIMENT RESULTS
In this section, we present the test results for all the based systems discussed Section on the undirected version of GLoRa. The results reported in Figures 6 and
19

---

Published as a conference paper at ICLR 2025
1.0
1.0
80curacy
0.9
0.9
0.8
0.8
0.7
0.7
0.6
0.5
0.3
2
6
8
10
12
14
16
2
4
8
10
12
14
16
d
GAT
GGNN
ResGAT - G?
0.9
аосuracy
accuracy
0.8
0.8
0.7
0.7
0.6
0.6
0.5
0.5
12
14
10
12
16
DenseGAT
DropEdge APPNP
DAGNN
GPRGNN
GIND
EIGNN
PairNorm
JKNct
IGNN
1.0
1.0
accuracy
0.9
accuracy
0.9
0.8
0.8
0.7
0.7
0.6
0.6
0.5
0.5
2
12
11
4
10
12
16
TransTrantf
GraphGPS with GraphGPS LapPE
RA-GCN
Figure 7: Test accuracy of non-top-5 based systems undirected GLoRa benchmarks for increasing d (lines represent mean accuracy over multiple runs, shaded areas indicate the standard deviation)
F GRADIENT VISUALIZATION OF THE DEEP LAYERS
In this section, we present the gradient distributions of the second and third layers for the best- performing systems. As shown Figure 8, the gradients both the second and third layers remain sufficiently large, indicating that the models do not suffer from vanishing gradient problems. This stability of gradients across deeper layers suggests that the degradation performance not due to gradient vanishing, but likely other factors.
20

---

Published as a conference paper at ICLR 2025
010
goddew veloze
2.00
-005
specla
grdden valocs
-000
opochs
godicu values
are
15g
opochs
(a) GatedGCN
(b) DenseGatedGCN
(c) IDrew-GCN
ALD udd
0L1 0015
0L10 025
grallonn values
gradion vahees
gtadion vahes
puth
100
opeices
2015
100
apeches
DUtS
100
opochs
200
200
300
(d) GatedGCN
(c) DenseGatedGCN
(f) Drew-GGNN
Figure 8: Gradient weights of the second (a, b. c) and third layer (d, e, f) across 300 epochs for the best-performing systems
21


Reviews:
[{"review_id": "t0k8fUZbZE", "reviewer": "Reviewer_jY5f", "summary": "The paper presents an algorithm for generating a synthetic dataset for every dependency length and demonstrates how to use this benchmark to identify, with certain guarantees, the maximum dependency length that a graph learning system can learn. Additionally, the paper illustrates the application of the benchmark in the experiment section.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method is novel, and the paper is well-written. The methodology is easy to follow, and the experiment section is well-structured and clearly presented. Through dedicated experiments, the authors show that, in nearly all cases, the performance degradation with increasing dependency length cannot be attributed to any of the three phenomena: over-smoothing, over-squashing, or vanishing gradients. This finding opens up two directions for future research: identifying the true causes of this degradation and developing methods to address it.", "weaknesses": "Overall, the paper is good; however, some improvements are needed in figure presentation. For example, the position of subgraph titles should be consistent across Figures 2, 3, and 4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hDrSo8m7Eb", "reviewer": "Reviewer_Je5y", "summary": "This paper introduces GLoRa, a synthetic benchmark designed to evaluate the ability of graph neural networks (GNNs) to capture long-range dependencies. By generating controlled graph examples with enforceable dependency lengths, GLoRa addresses a key gap in current GNN benchmarks. The authors provide theoretical guarantees for GLoRa, showing that models must capture dependencies of exact lengths to perform well. The paper also presents an empirical evaluation of several GNN architectures (including vanilla, over-smoothing-mitigated, over-squashing-mitigated, and Transformer-based GNNs) on GLoRa, revealing that none of the models perform well beyond modest dependency lengths.", "questions": "1. Could you clarify why Transformer-based models perform poorly on GLoRa, even at small dependency lengths? Have alternative positional encodings or adaptations been considered?\n2. How does GLoRa handle variations in the number of “holes” within paths, and would testing different numbers of interruptions provide further insight into model performance?\n3. Are there plans to test models that perform well on GLoRa against real-world benchmarks requiring long-range dependencies to validate GLoRa’s practical transferability?\n4. How do various types of implicit GNNs perform on the proposed benchmark?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Novelty in Benchmark Design**: GLoRa provides a synthetic benchmark with strict, enforceable dependency-length requirements, filling an important gap in current graph benchmarks.\n- **Theoretical Guarantees**: The benchmark’s theoretical properties, including enforceable dependency lengths, are rigorously proven, making GLoRa a well-grounded tool for long-range dependency evaluation.\n- **Clarity and Structure**: The paper is well-structured, with clear explanations of the benchmark construction process and theoretical foundations.", "weaknesses": "1. **Disconnection Between Theory and Experiment**: The experiments do not fully validate the theoretical properties of GLoRa, such as the enforceable dependency lengths. Testing trained models across a range of dependency lengths or with varied “holes” in paths might provide empirical support for the benchmark’s theoretical claims.\n   \n2. **Unexpected Performance of Transformer-Based Models**: Transformer-based GNNs perform poorly on GLoRa, even for small dependency lengths (e.g., \\(d = 3\\)). This contradicts their generally strong performance on other tasks, raising questions about whether GLoRa aligns with their strengths or if implementation details (like positional encodings) limit performance. Further exploration of encoding options or discussing the potential limitations of Transformers on GLoRa would clarify this discrepancy.\n   \n3. **Limited Testing of Transferability and Practical Relevance**: GLoRa’s relevance to real-world tasks remains untested, as there are no experiments that transfer GLoRa-trained models to practical benchmarks requiring long-range dependencies. Testing transferability on benchmarks like social networks or molecular graphs would substantiate GLoRa’s practical utility.\n\n4. **Missing Important Evaluations for Implicit GNNs**: While the paper tests many GNN models, most of these GNNs do not claim to capture long-distance dependency. Various types of implicit GNNs have been demonstrated to capture long-distance dependency better, but the paper misses this important category of models. A more comprehensive evaluation on implicit GNNs will be helpful.\n\nWhile GLoRa is a theoretically grounded and novel benchmark for evaluating long-range dependencies in GNNs, the experimental design could be strengthened to better align with its theoretical properties and validate practical relevance. Specifically, testing models across varying dependency lengths, addressing the Transformer performance anomaly, and exploring GLoRa’s transferability to real-world tasks would greatly enhance the impact of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KunUGc7mPA", "reviewer": "Reviewer_VTpd", "summary": "In this work, the authors propose GLoRa, a benchmark generator for long-range dependency tasks on graphs. The authors overcome the limitations of existing work by precisely stating a definition for long-range dependencies and designing a benchmark that guarantees that models cannot solve the generated tasks unless they respect the long-range dependencies in a given graph. An empirical study on a variety of GNN and transformer baselines concludes that no architecture can perform well on the GLoRA tasks for dependencies longer than depth 10. Further, the authors find that neither over-squashing, over-smoothing or vanishing gradients are the cause for this poor performance.", "questions": "- **Q1**: The experimental setting is not fully clear to me. In L412 the authors state that they “generated 1000 positive and 1000 negative examples by Algorithm 1 for each $d \\in \\{3, \\dots, 15\\}$”. Does that mean that models are trained on $2000 \\cdot 0.8 = 1600$ training samples for each depth $d$ or do you construct a joint training set of size $2000 \\cdot 0.8 \\cdot 13 = 20,800$ training samples and merely evaluate the test accuracy separately for each depth $d$?\n- **Q2**: The authors state in L465-466: “Finally and not surprisingly, all types of graph transformers cannot learn even very short dependencies”. Can the authors provide a more detailed insight into why this result is unsurprising? The GPS model, for example, uses a local message-passing module that should at the very least match the performance of the vanilla GatedGCN. I find that this warrants further analysis. One possible reason could be the possibly low amount of data seen during training; see related **Q1**.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- **S1**: The authors give a clear definition of long-range dependency which is often lacking in prior work.\n- **S2**: The authors benchmark a variety of baselines, from simple GNNs to more involved approaches, as well as transformers.\n- **S3**: The finding that neither over-smoothing, over-squashing or vanishing gradients are the causes for the poor performance at long range is very interesting and deserves more attention in future research.\n- **S4**: The authors have identified a surprisingly simple problem setting that a variety of GNN architectures fail to solve. These findings could lead to interesting follow-up work which aims to understand why the models fail and how these limitation can be overcome.", "weaknesses": "- **W1**: The authors argue for the need of a synthetic benchmark where long-range dependencies can be guaranteed. The authors argue that such guarantees are not given in real-world benchmarks. While I generally agree with the fact that in real-world benchmarks there may be shortcuts or simpler functions that avoid long-range dependencies but still correctly predict the labels, I am concerned that the present work proposes a benchmark for a problem they cannot identify in the real-world. In particular, the authors argue in the introduction that long-range dependencies are crucial in many applications (recommendation systems, traffic prediction, fake news detection). However, if long-range dependencies are crucial in these applications I would argue that it would be more sensible to derive benchmarks from real-world data in these domains. Further, if the authors are concerned that in real-world data one cannot verify whether long-range dependencies are truly needed to solve a task, I conclude that the authors also cannot guarantee that their proposed notion of long-range dependencies (Definition 1) is actually useful in real-world applications. Hence, I ask the authors to justify the relevance of long-range dependencies in real-world problems or to argue otherwise how progress on GLoRA contributes to solving real-world problems in graph learning.\n- **W2**: The theoretical contributions are formally imprecise and no full proof is given for Theorem 1 (only a proof sketch). First, the authors should clearly state in L385 that Theorem 1 is only supported by a proof sketch. The authors say “proof” in the main paper but “proof sketch” in the appendix. Second, let me expand on what I mean with formally imprecise. The statement of Theorem 1 says “[For every probability $\\mathcal{P}$] there exists a number $K$ such that a set $S$ of $K$ samples […] requires learning dependencies of length $d$ with probability at least $\\mathcal{P}$.” It is not formally clear what it means for a set of samples to require learning dependencies of some length. I could guess that the authors mean that a model cannot separate the set into positive and negative samples unless the model finds the corresponding path of length $d$. However, the statement in its current form is not formally precise. The authors should either formally state their theorem and prove it, or replace the theorem with an informal argument supported by the proof sketch. If the authors decide to formally state their theorem they should carefully define what they mean with the statement above. It is perfectly fine to give an informal (but intuitive) version of the Theorem in the main text and precisely formalize the theorem statement and proof in the appendix. In this case, I recommend to state the theorem in the main text as \"Theorem 1 (informal)\" and then write something like \"For a precise theorem statement and formal proof, see Appendix ...\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x3sniSIr5U", "reviewer": "Reviewer_PPjm", "summary": "This work introduces a new synthetic benchmark, GLoRa, to measure the ability for graph machine learning methods to learn long-range dependencies. For different depths of dependencies and difficulty levels, GLoRa can make synthetic tasks that do not have simple shortcuts that other long-range benchmarks suffer from. Experiments are conducted across many different GNN architectures from different families. It is argued that oversmoothing, oversquashing, and vanishing gradients are not the issues with learning these long-range dependencies.", "questions": "1. Figure 3 does not rule out the case of this type of oversmoothing: at the last layer of a GNN, it may be the case that most nodes in one graph have the same embedding. But, this embedding can be different across different graphs that you run a forward pass on.\n2. Why do the Transformers fail, and why do you say this is \"not surprising\"?\n3. Some important details, like how number of layers is chosen, is hidden in Appendix.\n4. What is the way forward for making GNNs that solve GLoRa?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. Good criticism of existing benchmarks. Many of them can be solved in a graph independent way, or long-range-dependency independent way.\n2. Interesting that over-squashing is not a problem in directed GLoRa by design (number of paths constant and small).\n3. Experiments on many types of representative GNNs from different families.\n4. In my opinion, good synthetic data experiments were very much needed for this exact question (long-range dependences in graph learning). Doing this well can be quite helpful.", "weaknesses": "1. For the definition of path-aware dependencies, isn't it easy to satisfy this for node classification functions on complete graphs, even though the connections are very short. In particular, there is no requirement in this definition for non-existence of paths.\n2. Unrigorous proof of Theorem 1\n3. 80% in Figure 2 is a bit arbitrary of a threshold, but this isn't a huge issue.\n4. Algorithm block is a bit hard to understand, but Figure 1 is clear at least.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)