Geometric Deep Learning: Impact of Graph Structure on Graph Neural Networks

Deep learning techniques have led to major improvements in fields like natural language processing, computer vision, and other Euclidean data domains, yet in many domains data are irregular, requiring graphs or manifolds to be explicitly modeled. Such applications include social networks, sensor feeds, logistics, supply chains, chemistry, neuroscience, and other biological systems. The extension of deep learning to these nonEuclidean data is an area of research now called Geometric Deep Learning (GDL). This thesis focuses on a subfield of GDL, graph neural networks (GNNs) that learn on graph signals using neural networks. We explore the impact of the data graph structure on the performance of graph neural networks using real and synthetic data for two graph learning tasks: node and graph classification. 

We start with the formalization of GNNs, and consider two flavors of approaches: spectral approach typified by graph convolutional networks (GCNs) and spatial approach typified by topology adaptive graph convolutional networks (TAGCNs). In general, TAGCN requires fewer number of layers than GCN, with moderate degrees of the polynomial filters. 

For node classification, not many layers are needed to achieve optimal performance. Unlike graph classification, graph signal is necessary and important. For some real datasets, classifying using a simple estimator on the graph signals can outperform GNNs. For synthetic datasets, Erdos-Rényi and preferential attachment models have similar test accuracy curves for both GCN and TAGCN with respect to the number of layers and the degree of the polynomial filters. For smallworld model, TAGCN’s filters play an important role in achieving the optimal accuracy and accelerating the effect of over-smoothing. 

We also study the training convergence for node classification. We show theoretically that training loss converges to a global minimum for linearized TAGCN. Despite the non-convex objectives, training loss for 1-degree H-layer TAGCN, i.e., with degree 1 polynomial filter and H layers, is guaranteed to converge to global minimum at an exponential rate, faster with higher number of layers. With K-degree TAGCN, convergence is accelerated with higher degree K of the polynomial filters. We experimentally validate our theory and show training convergence holds true for both linearized and nonlinearized TAGCN. 

For graph classification, graph structure plays a more important role than the graph signal. GNNs can often classify graphs using just the graph structures of the different classes if they are distinct enough. For real datasets, we relate simple network metrics and signal statistics to the performance of these models. We show for some datasets, classifiers on number of edges or number of nodes can lead to better or similar performance as graph neural networks. For other datasets, signal statistics can perform well. Based on these observations, we were able to apply simple modifications to GCN and TAGCN to improve their performance (sumpool and degree-aware TAGCN). For synthetic datasets, Erd˝os-Rényi and preferential attachment models again have similar test accuracy curves for both GCN and TAGCN. For smallworld model, more than 1 layer is needed to achieve good performance if the edge rewiring probability is distinct for different classes. 

We apply the architecture of TAGCN to a COVID-19 case study. We introduce a novel approach for molecular property prediction by combining two existing GNN methods. Our model (D-MPNN+TAGCN) consistently outperforms the state-of-the-art baseline on five coronavirus datasets.