Adaptive Universal Generalized PageRank Graph Neural Network

Abstract

In many important graph data processing applications the acquired information includes both node features and observations of the graph topology. Graph neural networks (GNNs) are designed to exploit both sources of evidence but they do not optimally trade-off their utility and integrate them in a manner that is also universal. Here, universality refers to independence on homophily or heterophily graph assumptions. We address these issues by introducing a new Generalized PageRank (GPR) GNN architecture that adaptively learns the GPR weights so as to jointly optimize node feature and topological information extraction, regardless of the extent to which the node labels are homophilic or heterophilic. Learned GPR weights automatically adjust to the node label pattern, irrelevant on the type of initialization, and thereby guarantee excellent learning performance for label patterns that are usually hard to handle. Furthermore, they allow one to avoid feature over-smoothing, a process which renders feature information nondiscriminative, without requiring the network to be shallow. Our accompanying theoretical analysis of the GPR-GNN method is facilitated by novel synthetic benchmark datasets generated by the so-called contextual stochastic block model. We also compare the performance of our GNN architecture with that of several state-of-the-art GNNs on the problem of node-classification, using well-known benchmark homophilic and heterophilic datasets. The results demonstrate that GPR-GNN offers significant performance improvement compared to existing techniques on both synthetic and benchmark data.

arXiv commentICLR 2021

References in corpus (20)

• Adam: A Method for Stochastic Optimization
• Community detection in graphs
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Neural Message Passing for Quantum Chemistry
• Link Prediction in Complex Networks: A Survey
• Fast Graph Representation Learning with PyTorch Geometric
• Simplifying Graph Convolutional Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• Pitfalls of Graph Neural Network Evaluation
• Scaling Graph Neural Networks with Approximate PageRank
• PairNorm: Tackling Oversmoothing in GNNs
• Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs
• Watch Your Step: Learning Node Embeddings via Graph Attention
• Geom-GCN: Geometric Graph Convolutional Networks
• Residual Correlation in Graph Neural Network Regression
• Block Models and Personalized PageRank
• Adaptive Diffusions for Scalable Learning over Graphs
• Contextual Stochastic Block Models
• Heat kernel based community detection
• Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection

Cited by in corpus (5)

• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders
• How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications
• LineMVGNN: Anti-Money Laundering with Line-Graph-Assisted Multi-View Graph Neural Networks
• Clarify Confused Nodes via Separated Learning