Dissecting Long-range Dependency in Graph Implicit Models

Capturing long-range dependencies in an effective manner has been one of the key bottlenecks for advances in graph neural networks. Recently, graph implicit models (GIMs) have gained popularity as they provide a means to capture long-range dependency by solving for embeddings that are fixed-point solutions to `infinitely deeply stacked' graph neural networks, giving an effectively unbounded receptive field. Prior work shows examples where standard graph neural networks demonstrably fail to capture long-range dependencies, while graph implicit models succeed. Yet, graph implicit models do not necessarily outperform standard graph neural networks in real-world long-range benchmarks. In this paper, we theoretically disentangle this conundrum. We first analyze why linear GIMs can solve the simple $(1,L)$ chain task through an aligned learning-dynamics surrogate. We then establish a quantitative vanishing-influence bound: under contraction and sensitivity bounds uniform in graph size, GIMs cannot fit exact scores or maintain a fixed positive classification margin on the generalized $(L,L)$ chain-parity task for sufficiently large $L$. Motivated by this diagnosis, we propose , a GIM with per-node adaptive selection that retains intermediate representations while propagation continues. Benchmarking against implicit and standard graph models on synthetic chain-parity and four graph-property datasets shows that it achieves the best mean on three of the four graph datasets in our comparison. GLoRa and selection ablations provide further evidence for the proposed design.