  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.
