Unifying Graph Convolutional Neural Networks and Label Propagation

Abstract

Label Propagation (LPA) and Graph Convolutional Neural Networks (GCN) are both message passing algorithms on graphs. Both solve the task of node classification but LPA propagates node label information across the edges of the graph, while GCN propagates and transforms node feature information. However, while conceptually similar, theoretical relation between LPA and GCN has not yet been investigated. Here we study the relationship between LPA and GCN in terms of two aspects: (1) feature/label smoothing where we analyze how the feature/label of one node is spread over its neighbors; And, (2) feature/label influence of how much the initial feature/label of one node influences the final feature/label of another node. Based on our theoretical analysis, we propose an end-to-end model that unifies GCN and LPA for node classification. In our unified model, edge weights are learnable, and the LPA serves as regularization to assist the GCN in learning proper edge weights that lead to improved classification performance. Our model can also be seen as learning attention weights based on node labels, which is more task-oriented than existing feature-based attention models. In a number of experiments on real-world graphs, our model shows superiority over state-of-the-art GCN-based methods in terms of node classification accuracy.

References in corpus (10)

• Cooperative Game Theory Approaches for Network Partitioning
• Inductive Representation Learning on Large Graphs
• Understanding Black-box Predictions via Influence Functions
• Pitfalls of Graph Neural Network Evaluation
• Learning to Propagate Labels: Transductive Propagation Network for Few-shot Learning
• GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs
• Attention-based Graph Neural Network for Semi-supervised Learning
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• GMNN: Graph Markov Neural Networks
• An Iterative Locally Linear Embedding Algorithm

Cited by in corpus (31)

• Graph Neural Networks: A Review of Methods and Applications
• Combining Label Propagation and Simple Models Out-performs Graph Neural Networks
• Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
• Alleviating Structural Distribution Shift in Graph Anomaly Detection
• Topology-Imbalance Learning for Semi-Supervised Node Classification
• Bag of Tricks for Node Classification with Graph Neural Networks
• Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training
• Semi-supervised Superpixel-based Multi-Feature Graph Learning for Hyperspectral Image Data
• SAC: Accelerating and Structuring Self-Attention via Sparse Adaptive Connection
• Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information
• Graph Meta Learning via Local Subgraphs
• Robust Node Classification on Graphs: Jointly from Bayesian Label Transition and Topology-based Label Propagation
• Learning Tree Structures from Leaves For Particle Decay Reconstruction
• PPGN: Physics-Preserved Graph Networks for Real-Time Fault Location in Distribution Systems with Limited Observation and Labels
• NodeNet: A Graph Regularised Neural Network for Node Classification
• Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification
• Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classification
• Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods
• Self-Enhanced GNN: Improving Graph Neural Networks Using Model Outputs
• Extract the Knowledge of Graph Neural Networks and Go Beyond it: An Effective Knowledge Distillation Framework
• Label-GCN: An Effective Method for Adding Label Propagation to Graph Convolutional Networks
• SNoRe: Scalable Unsupervised Learning of Symbolic Node Representations
• Relational Message Passing for Knowledge Graph Completion
• $p$-Laplacian Based Graph Neural Networks
• Implicit SVD for Graph Representation Learning
• A Graph Convolutional Network Composition Framework for Semi-supervised Classification
• Structure-Aware Label Smoothing for Graph Neural Networks
• Multi-task Self-distillation for Graph-based Semi-Supervised Learning
• Cyclic Label Propagation for Graph Semi-supervised Learning
• Gradient scarcity with Bilevel Optimization for Graph Learning
• FeatureNorm: L2 Feature Normalization for Dynamic Graph Embedding