Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns

Abstract

Graph neural networks (GNNs) have achieved tremendous success on multiple graph-based learning tasks by fusing network structure and node features. Modern GNN models are built upon iterative aggregation of neighbor's/proximity features by message passing. Its prediction performance has been shown to be strongly bounded by assortative mixing in the graph, a key property wherein nodes with similar attributes mix/connect with each other. We observe that real world networks exhibit heterogeneous or diverse mixing patterns and the conventional global measurement of assortativity, such as global assortativity coefficient, may not be a representative statistic in quantifying this mixing. We adopt a generalized concept, node-level assortativity, one that is based at the node level to better represent the diverse patterns and accurately quantify the learnability of GNNs. We find that the prediction performance of a wide range of GNN models is highly correlated with the node level assortativity. To break this limit, in this work, we focus on transforming the input graph into a computation graph which contains both proximity and structural information as distinct type of edges. The resulted multi-relational graph has an enhanced level of assortativity and, more importantly, preserves rich information from the original graph. We then propose to run GNNs on this computation graph and show that adaptively choosing between structure and proximity leads to improved performance under diverse mixing. Empirically, we show the benefits of adopting our transformation framework for semi-supervised node classification task on a variety of real world graph learning benchmarks.

published in KDD 2021; 11 pages;

Cited by in corpus (11)

• Attention-based graph neural networks: a survey
• UniG-Encoder: A Universal Feature Encoder for Graph and Hypergraph Node Classification
• Graph Neural Networks with Diverse Spectral Filtering
• GCNH: A Simple Method For Representation Learning On Heterophilous Graphs
• ES-GNN: Generalizing Graph Neural Networks Beyond Homophily with Edge Splitting
• Spatial Heterophily Aware Graph Neural Networks
• Graph Representation Learning Beyond Node and Homophily
• Neighborhood Homophily-based Graph Convolutional Network
• A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions
• Clarify Confused Nodes via Separated Learning
• When Heterophily Meets Heterogeneity: Challenges and a New Large-Scale Graph Benchmark