Towards Graph Foundation Models: Enhancing Expressiveness and Generalization in Graph Learning

Message passing neural networks (MPNNs) are the leading architecture for deep learning on graph-structured data, mainly due to their simplicity and scalability. Nevertheless, they suffer from a set of limitations, including poor generalization to out-of-distribution data and limited expressive power. In this thesis, we show how the set of subgraphs of the original graph can help mitigate this diverse set of problems. 

We start by leveraging the stability of subgraph densities in graphon random graph models to learn representations that are approximately invariant to distribution shifts in the graph sizes from train to test data. More precisely, we provide a causal model that formally describes a class
of graph classification tasks where training and test graphs have different sizes, and test data is not available in training. Then, we introduce a graph representation method leveraging subgraph densities that is invariant to the distribution shifts of our causal model. Unlike existing invariant representations, our proposed approach can generalize to out-of-distribution data even when all training graphs have the same size (single environment).

Then, we focus on the expressive power limitation of MPNNs, which were shown to be at most as expressive as the Weisfeiler-Lehman (WL) graph isomorphism test, and, therefore, fail to distinguish simple non-isomorphic graphs. In our work, we demonstrate that deconstructing a graph into a set of subgraphs increases the expressive power of existing MPNNs. Our main observation is that while two graphs may not be distinguishable by an MPNN, they often contain distinguishable subgraphs. Thus, we propose to represent each graph as a set of subgraphs derived by some predefined generation policy, and to process the set using an architecture that is equivariant to permutations of both subgraphs and nodes therein.


To address the increased computational complexity in subgraph-based architectures, arising from performing message passing on numerous subgraphs, we propose to learn to select a small subset of the large set of possible subgraphs in a data-driven fashion. We first motivate the problem by proving that there are families of WL-indistinguishable graphs for which there exist efficient subgraph selection policies: small subsets of subgraphs that can already identify all the graphs within the family. We then propose a new approach that learns how to select subgraphs in an iterative manner. We prove that, unlike popular random policies and prior work addressing the same problem, our architecture is able to learn the efficient policies mentioned above.

Finally, this thesis explores the emerging concept of Graph Foundation Models (GFMs). While existing work outlines the potential of GFMs, a fully general graph foundation model remains unrealized. As a foundational step toward this goal, we propose holographic node representations, a framework that enables task-agnostic pretraining and seamless adaptation to node-, link-, and higher-order tasks. Holographic node representations utilize an expansion map to generate expressive embeddings and a reduction map to reintroduce task-specific symmetries, achieving state-of-the-art results and demonstrating robust transferability across tasks.