The Impact of Global Structural Information in Graph Neural Networks Applications

Abstract

Graph Neural Networks (GNNs) rely on the graph structure to define an aggregation strategy where each node updates its representation by combining information from its neighbours. A known limitation of GNNs is that, as the number of layers increases, information gets smoothed and squashed and node embeddings become indistinguishable, negatively affecting performance. Therefore, practical GNN models employ few layers and only leverage the graph structure in terms of limited, small neighbourhoods around each node. Inevitably, practical GNNs do not capture information depending on the global structure of the graph. While there have been several works studying the limitations and expressivity of GNNs, the question of whether practical applications on graph structured data require global structural knowledge or not, remains unanswered. In this work, we empirically address this question by giving access to global information to several GNN models, and observing the impact it has on downstream performance. Our results show that global information can in fact provide significant benefits for common graph-related tasks. We further identify a novel regularization strategy that leads to an average accuracy improvement of more than 5% on all considered tasks.

References in corpus (27)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Graph Convolutional Neural Networks for Web-Scale Recommender Systems
• Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)
• Representation Learning on Graphs with Jumping Knowledge Networks
• Hierarchical Graph Representation Learning with Differentiable Pooling
• Random walks and diffusion on networks
• Predict then Propagate: Graph Neural Networks meet Personalized PageRank
• Self-Attention Graph Pooling
• Scaling Graph Neural Networks with Approximate PageRank
• Revisiting Semi-Supervised Learning with Graph Embeddings
• GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs
• Towards Sparse Hierarchical Graph Classifiers
• Diffusion Improves Graph Learning
• Anonymous Walk Embeddings
• Personalized PageRank Estimation and Search: A Bidirectional Approach
• Geom-GCN: Geometric Graph Convolutional Networks
• On the Bottleneck of Graph Neural Networks and its Practical Implications
• N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification
• Attention Models in Graphs: A Survey
• Graph U-Nets
• What graph neural networks cannot learn: depth vs width
• Efficient Algorithms for Personalized PageRank
• Approximation Ratios of Graph Neural Networks for Combinatorial Problems
• Graph Laplacian Regularized Graph Convolutional Networks for Semi-supervised Learning