Learning on Graphs with Long-Range Dependencies: Methods and Applications

Graph Neural Networks (GNNs) have become a central framework for learning on relational data such as molecules, biological systems, and social networks. Despite their success, standard message-passing architectures struggle to capture long-range dependencies. As information propagates through multiple layers, structural bottlenecks in the graph lead to phenomena such as oversquashing and oversmoothing, which severely limit the ability of GNNs to model interactions between distant nodes.

This thesis studies graph learning from the perspective of information propagation and develops methods to improve long-range reasoning in graph neural architectures. First, we propose a principled graph rewiring framework that introduces latent nodes acting as global mediators, enabling more efficient communication between distant regions of the graph and alleviating structural bottlenecks. We demonstrate that this approach improves the modeling of long-range interactions in protein structure learning tasks.

Second, we introduce a generative framework for modeling full-atom protein conformations using latent diffusion on graph embeddings. Protein structures are encoded using a Chebyshev spectral graph network, and a diffusion model is trained in a learned latent space to generate diverse conformational states that are subsequently decoded into full atomic coordinates.

Finally, we revisit Chebyshev spectral graph networks from a dynamical systems perspective and analyze the stability of high-order polynomial filtering. We introduce architectural modifications that enforce stable information propagation while preserving spectral expressivity, leading to strong performance on long-range graph benchmarks.

Together, these contributions advance the understanding and design of graph neural architectures capable of modeling long-range dependencies in complex relational systems.