Official Review · ICLR 2025

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. - **Novelty in Benchmark Design**: GLoRa provides a synthetic benchmark with strict, enforceable dependency-length requirements, filling an important gap in current graph benchmarks. - **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. - **Clarity and Structure**: The paper is well-structured, with clear explanations of the benchmark construction process and theoretical foundations. 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 alig