B0558
Title: Analyzing graph neural network architectures through the neural tangent kernel
Authors: Mahalakshmi Sabanayagam - Technical University of Munich (Germany)
Pascal Esser - Technical University of Munich (Germany)
Debarghya Ghoshdastidar - Technical University of Munich (Germany) [presenting]
Abstract: The fundamental principle of graph neural networks (GNNs) is to exploit the structural information of the data by aggregating the neighbouring nodes using a "graph convolution" in conjunction with a suitable choice for the network architecture, such as depth and activation functions. Therefore, understanding the influence of each design choice on the network performance is crucial. Convolutions based on graph Laplacian have emerged as the dominant choice with the symmetric normalization of the adjacency matrix being the most widely adopted one. However, some empirical studies show that row normalization outperforms it in node classification, but this has no theoretical explanation. Similarly, the performance of linear GNN on par with ReLU is observed empirically but lacks rigorous theoretical backing. The influence of different aspects of the GNN architecture is analyzed using the graph neural tangent kernel in a semi-supervised node classification setting. Under the population degree corrected stochastic block model, it is proven that: (i) linear networks capture the class information as well as ReLU networks; (ii) row normalization preserves the underlying class structure better than other convolutions; (iii) performance degrades with network depth due to over-smoothing, but the loss in class information is the slowest in row normalization; (iv) skip connections retain the class information even at infinite depth, thereby eliminating over-smoothing.
