The theoretical study of Message Passing Neural Networks (MPNN) focuses on increasing expressive power and overcoming over-squashing

Convergence of Invariant Graph Network. In this part, we investigate the convergence of one powerful GNN, Invariant Graph Network (IGN) over graphs sampled from graphons. We first prove the stability of linear layers for general k-IGN (of order k) based on a novel interpretation of linear equivariant layers. Building upon this result, we prove the convergence of k-IGN under the model of \cite{ruiz2020graphon}, where we access the edge weight but the convergence error is measured for graphon inputs. Under the more natural (and more challenging) setting of \cite{keriven2020convergence} where one can only access 0-1 adjacency matrix sampled according to edge probability, we first show a negative result that the convergence of any IGN is not possible. We then obtain the convergence of a subset of IGNs, denoted as IGN-small, after the edge probability estimation. We show that IGN-small still contains functions rich enough to approximate spectral GNNs arbitrarily well. Lastly, we perform experiments on various graphon models to verify our statements.

The Connection between MPNN and Graph Transformer. In this part, we study the connection between local GNN (MPNN) and global GNN (Graph Transformer). Graph Transformer (GT) recently has emerged as a new paradigm of graph learning algorithms, outperforming the previously popular Message Passing Neural Network (MPNN) on multiple benchmarks. Previous work \cite{kim2022pure} shows that with proper position embedding, GT can approximate MPNN arbitrarily well, implying that GT is at least as powerful as MPNN. In this paper, we study the inverse connection and show that MPNN with virtual node (VN), a commonly used heuristic with little theoretical understanding, is powerful enough to arbitrarily approximate the self-attention layer of GT.

In particular, we first show that if we consider one type of linear transformer, the so-called Performer/Linear Transformer, then MPNN + VN with only $O(1)$ depth and $O(1)$ width can approximate a self-attention layer in Performer/Linear Transformer. Next, via a connection between MPNN + VN and DeepSets, we prove the MPNN + VN with $O(n^d)$ width and $O(1)$ depth can approximate the self-attention layer arbitrarily well, where d is the input feature dimension. Lastly, under some assumptions, we provide an explicit construction of MPNN + VN with $O(1)$ width and $O(n)$ depth approximating the self-attention layer in GT arbitrarily well.

Graph coarsening with neural networks. In this part, we study the fundamental problem of reducing graph size/resolution while preserving its spectral property. We first propose a framework for measuring the quality of coarsening algorithm and show that depending on the goal, we need to carefully choose the Laplace operator on the coarse graph and associated projection/lift operators. Motivated by the observation that the current choice of edge weight for the coarse graph may be sub-optimal, we parametrize the weight assignment map with GNN and train it to improve the coarsening quality in an unsupervised way. Through extensive experiments on both synthetic and real networks, we demonstrate that our method significantly improves common graph coarsening methods under various metrics, reduction ratios, graph sizes, and graph types. It generalizes to graphs of larger size (25x of training graphs), is adaptive to different losses (differentiable and non-differentiable), and scales to much larger graphs than previous work.

Recently there has been an increasing number of learning problems arising in complex data domains, like graph-structured data, such as social networks and knowledge graphs. Various machine learning approaches have been developed to handle different kinds of data like PointNet for point clouds and graph neural networks for graph-structured data. At the same time, to tame the complexity in data, geometry and topology form natural platforms. In particular, computational geometry and the emerging field of topological data analysis (TDA) have been effective at capturing hidden structure and shape features from data, as well as providing efficient algorithms for them. In this thesis, we aim to integrate geometric ideas and topological concepts with machine learning pipelines to further augment their power and performance.

In the first part of the thesis, we show how topological ideas, in particular, the so-called persistent homology, can help with analyzing graph-structured data. Persistent homology provides a flexible and versatile way to summarize complex shapes (including graphs) by a simple multiscale summary. In the first line of work, we designed an effective metric learning approach for persistence-based summaries of graphs, and showed how this improved graph classification tasks. In the second line, we show how topological summaries can be used to further improve graph neural networks' performance.

In the second part, we investigate how geometric algorithmic ideas can be combined with neural networks (NNs) to tackle hard optimization problems in geometric setting. In recent years, NNs have shown promise in helping solve combinatorial optimization problems. However, such approaches often tend to be ad hoc. Instead of solving problems in a completely data-driven manner using NNs, we propose to design mixed algorithmic-NN frameworks, where NNs are used as components within an algorithmic framework. In particular, this allows us to leverage elegant algorithmic ideas for problems in geometric setting to develop learning-based frameworks solving optimization problems efficiently in practice, but also with theoretical guarantees. We demonstrate our proposed mixed algorithmic-NN frameworks over two problems: Maximum-independent set (and several other graph problems) for intersection graphs in Euclidean setting, and computing (rectilinear) Minimum Steiner Tree for points in Euclidean setting.