Unifying Graph Convolutional Neural Networks and Label Propagation

By Hongwei Wang, Jure Leskovec. 2020

198 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Qian Huang
2. Enyan Dai
3. Shikun Feng
4. Hui Zhong
5. Yu Sun
6. Wenjin Wang
7. Zhengjie Huang
8. Suhang Wang

In Computational Theory and Mathematics

1. Suhang Wang
2. Austin R. Benson
3. Ser-Nam Lim

Citations in the corpus

• Masked Label Prediction: Unified Massage Passing Model for Semi-Supervised Classification (2020, methodology): “, 2019] using GNN predict soft labels and then propagate them, and GCNLPA [Wang and Leskovec, 2019] uses LPA to regularize their GNN model.”
• Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information (2020, background): “• Debias-e : Similar to the ALFR-e, we also add the deepwalk embeddings • FCGE [4]: FCGE is proposed to learn fair node embeddings in ALFR and ALFR-e are trained with features of all the users V , labels of V 𝐿 , and the sensitive attributes of V 𝑆 is on contrary with our setting that V 𝐿 V 𝑆 Th”
• Combining Label Propagation and Simple Models Out-performs Graph Neural Networks (2020, methodology): “Recent research connects GNNs to label propagation (Wang & Leskovec, 2020; Jia & Benson, 2020) as well as Markov Random fields (Qu et al., 2019; Gao et al., 2019), and some techniques use ad hoc incorporation of label information in the features (Shi et al., 2020).”