Towards trustworthy and efficient machine learning on graph-structured data : theory and algorithms

Abstract

Graph-structured data underpins numerous scientific and industrial applications, from social networks and recommender systems to biological networks and knowledge graphs. Graph Neural Networks (GNNs) have emerged as powerful tools capable of effectively learning from such relational data. However, unlike traditional machine learning approaches, the performance and behavior of GNNs are inherently coupled with the underlying graph structure. This structural dependence introduces unique theoretical challenges and complicates practical implementations, especially as real-world graphs continue to grow in scale and complexity. This dissertation addresses these challenges through an in-depth theoretical analysis and novel algorithmic developments across multiple learning paradigms in graph-structured data. First, we establish theoretical foundations for GNNs on static graphs, systematically analyzing how structural properties affect essential learning aspects, including generalization and optimization. These insights guide the design of efficient, structurally-informed learning algorithms. Second, we extend this theoretical frame- work to dynamic graphs, developing robust, scalable models to effectively manage temporal evolution and structural shifts. We further introduce continual learning methods that enable GNNs to adapt continuously to streaming graph data while mitigating catastrophic forgetting. Lastly, we examine graph generation techniques, presenting a novel theoretical convergence analysis that clarifies the behavior of score-based generative methods. Collectively, this thesis offers significant theoretical insights and algorithmic innovations, providing a comprehensive framework for efficient, robust, and trustworthy graph learning. Our contributions lay crucial groundwork for future advancements in graph-based machine learning, benefiting real-time, safety-critical, and large-scale applications.