Learning latent graph structures for graph neural networks

Abstract

Graphs are powerful tools for modeling complex relationships between entities, making them essential in various domains, such as social networks, citation networks, molecular graphs, and road networks. In recent years, Graph Neural Networks (GNNs) have gained significant attention for learning on graphs. However, existing GNNs are very limited in effectively learning various latent graph structures, which are not immediately apparent but very important for graph learning, such as graph clusters. Consequently, there is a pressing need to design novel approaches that enable GNNs to capture diverse latent structures in graph learning.

To this end, this dissertation aims to design novel methodologies that can integrate latent structures into graph neural networks to bolster their learning performance. In particular, the focus is on three types of latent graph structures: graph clusters, implicit sparsity and latent structure from the Third Law of Geography. With our investigation on these structures and method designs, we can obtain more insights on both graph structures and graph learning, and further improve the performance of graph neural networks and their real-world applications.

First, we highlight the importance of graph clusters in graph learning, and identify the benefits of incorporating graph clusters into graph attention which lacks cluster information. To incorporate graph clusters into graph attention, we proposed Differentiable Clustering for Graph Attention (DCAT), which enhances graph attention by learning cluster-aware attention scores. In DCAT, graph clusters are learned through a differentiable objective based on a relaxed form of modularity maximization. Thus the objective can be optimized together with the semi-supervised loss in an end-to-end manner. Our analysis indicates that DCAT can allocate higher attention scores to nodes within the same cluster, allowing them to have a higher influence on node representation learning.

Second, we investigate the latent sparsity phenomenon in real-world graphs, where a large portion of edges connect irrelevant nodes, potentially degrading GNN performance. To address this issue, we propose a novel graph selective attention mechanism,which employs various forms of learnable node-node dissimilarity to learn the latent sparsity. With selective attention, each node can effectively filter out irrelevant edges and selectively attend to its most irrelevant neighbors. We further build the graph selective attention network (SAT) based on it, and conduct theoretical analysis on its expressiveness.

Third, we investigate a latent structure in road networks according to the Third Law of Geography, which has not been explored in previous literature. This law suggests a latent structure which goes beyond the spatial relationships of geospatial entities according to their geographic configurations. To learn from the latent structure, we propose a novel graph contrastive learning method, with geographic configuration aware graph augmentation and spectral negative sampling.

Our proposed approaches have been evaluated against a number of state-of-the-art baselines across various real-world tasks. The results demonstrate our methods can perform robustly, showcasing learning latent graph structures is indeed an effective way to advance graph neural networks. The methodologies proposed in this thesis inaugurate new directions that can further strengthen graph representation learning for various real-world tasks.