Graphs, which abstract complex systems of relations and interactions, can model transportation networks, trading networks, epidemic networks, the World Wide Web, and more. Graph Neural Networks (GNNs), aiming to adaptively integrate both feature and structure knowledge on networks, have emerged as a popular graph representation learning technique. The key component in GNNs is the non-parameterized message-passing operator, which updates node representation via aggregating neighbor node messages. Message-passing operators generally follow the algorithm alignment design principle, where the operator should align with the task principle or the corresponding graph algorithms, e.g., Common Neighbor for friend recommendation, PageRank for web Search, and Dijkstra algorithm for finding the shortest path. Despite the initial success achieved by GNNs, most of them are end-to-end trained and evaluated on one single dataset. Consequently, an architectural overfitting phenomenon can be found where GNNs generally cannot perform well across graphs with various properties, as they are specifically designed to beat existing methods on the limited benchmark dataset. Such obstacle makes it difficult for practitioners to determine which models will generalize effectively to unseen datasets. Thereby, a new but necessary requirement for graph representation learning is to be expressive enough to capture diverse properties and adapt across different graphs. To achieve this ultimate goal, I first endeavor to elucidate all the underlying network patterns across diverse graphs with a properly designed random network model. Theoretical analysis is further conducted to principally characterize the relationship between different network patterns. Secondly, I conduct analysis on GNN's inner mechanism about which network patterns GNNs can capture and which not. With the help of the random network model, I can identify the inevitable but largely ignored limitation of GNNs. Finally, I develop Graph Foundation Models~(GFMs) to address the incapability of GNNs. GFMs comprehensively consider the training data diversity, expressive architecture design, and suitable training objective, which moderates the over-reliance on the algorithm alignment and captures diverse network patterns on different graphs.
Read
