Leveraging global information for machine learning on graphs

Abstract

Representing data as a graph is becoming increasingly widespread across a myriad of domains such as biochemistry, social networks, traffic networks, autonomous driving and weather prediction. Its popularity derives from its flexible formulation and inherent ability to model interactions. However, this rich representation presents unique challenges when modeling the data, which requires a trade-off between capturing as much information about the graph as possible while remaining computationally tractable. After several decades filled with varied approaches such as embedding methods and graph kernels, the focus has shifted to the development of deep learning methods that can operate on graphs. These methods, termed graph neural networks (GNNs), use neighborhood aggregation to update the representation of each node. Although GNNs have enjoyed strong empirical success, recent work has uncovered some of their limitations, such as the inability to transmit information over long distances in the graph and limitations on their ability to distinguish non-isomorphic graphs. These limitations are directly related to the design paradigm of graph neural networks, which models local structural information in the graph via neighborhood aggregation. While this paradigm encodes relevant and critical information, it is an open question of how to best counteract the limitations that are a result of it. This thesis explores the role that global information can play in generating meaningful graph representations that do not suffer from the problems associated with neighborhood aggregation. We do not seek to replace the powerful neighborhood aggregation methods of the current day, but rather to investigate how global information can complement or provide an alternative view of the local information in the graph. The first contribution of this thesis introduces a novel way of representing a graph as a high-dimensional curve, termed a filtration curve. Filtration curves are an efficient method for generating a global representation of a graph by capturing information at multiple scales, and can be completely parameter-free. The curve-based representation comes with additional benefits, such as a straightforward way to create a vector representation of the graph, enabling it to be used with standard machine learning algorithms. In addi- tion to its efficiency and ease of use, we find that our simplest form of filtration curves already achieves empirical performance that is competitive with the much more complex, highly parameterized state-of-the-art competitor methods, establishing the value of global representations of graphs. The second contribution investigates how combining global and location information can improve graph representations. We introduce the Structure-Aware Transformer, which combines local structural information from message passing GNNs with global information from a transformer architecture, and is the first graph transformer to integrate a transformer and an arbitrary GNN into a single block. We do so by introducing a new structure- aware self-attention calculation, which filters nodes based on the similarity between their subgraphs rooted at the nodes of interest, enabling a more robust comparison on the basis of structural and attribute similarity. Furthermore, we abstract this formulation and provide a generic framework that can be tailored to the domain of interest. Our graph transformer achieves state-of-the-art performance on several benchmark datasets and outperforms the global-only and local-only equivalents of the architecture, highlighting the potential of combining these two views of a graph. Finally, the third contribution is an empirical analysis of the current procedure for evaluating graph generative models, which relies on global graph summary statistics and the maximum mean discrepancy (MMD). We discover some issues with the current procedure adopted by the community, which in the worst case leads to spurious results, and propose a modified workflow to avoid these cases. We conclude this thesis by providing an outlook for future work that combines global and local information in graph representations. As more and more new domains begin to represent their data as graphs, the paradigms for how to learn meaningful representations of graphs may shift or require novel approaches. From this perspective, we anticipate that the proposed methods of incorporating global information into graph representations will prove useful in current and future applications of graph learning.