GLoRa: A Benchmark to Evaluate the Ability to Learn Long-Range Dependencies in Graphs

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.
2. Unrigorous proof of Theorem 1
3. 80% in Figure 2 is a bit arbitrary of a threshold, but this isn't a huge issue.
4. Algorithm block is a bit hard to understand, but Figure 1 is clear at least.

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

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.

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.

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

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

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

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