Source-linked AI summary
Unifying Graph Convolutional Neural Networks and Label Propagation
Hongwei Wang, Jure Leskovec
TL;DR
The paper addresses the uninvestigated theoretical relationship between LPA and GCN in graph-based node classification. It analyzes their smoothing and influence properties, then proposes an end-to-end unified model with learnable edge weights and LPA regularization. Experiments on five datasets show that GCN-LPA outperforms state-of-the-art baselines in classification accuracy.
Problem
The theoretical relationship between LPA and GCN, and how to combine them for more accurate graph node classification, had not been investigated.
Method
The paper analyzes feature/label smoothing and influence, then jointly learns GCN transformations and edge weights with LPA serving as a regularizer.
Results
Experiments on five datasets show that GCN-LPA outperforms state-of-the-art baselines in node-classification accuracy.
Takeaways & Limitations
GCN-LPA provides a unified approach that learns edge weights using node-label information and improves node-classification performance.
Takeaways & Limitations
The reported experimental setting follows GCN and is transductive, although the method can be generalized to inductive learning using a GraphSAGE-like implementation.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper investigates the theoretical relationship between LPA and GCN and uses that analysis to develop a unified node-classification model. Experiments on five datasets show improved classification accuracy over state-of-the-art methods.
- Background: LPA propagates and aggregates node labels, whereas GCN propagates and transforms node features across graph edges.Both methods address node classification but operate on opposite sides of the node-to-label mapping.
- Theoretical relationship: The paper analyzes GCN and LPA through feature/label smoothing and feature/label influence.The analysis examines neighbor averaging and how one node’s initial feature or label affects another node’s output.
- Unified model: The analysis motivates GCN-LPA, a unified model that makes edge weights trainable and uses LPA to regularize GCN learning.The LPA component assists GCN in learning edge weights that support separation between node classes.
- Unified model: GCN-LPA can learn edge attention weights from node-label information rather than node-feature similarity.This provides a more task-oriented attention mechanism than the feature-based attention models described by the authors.
- Experiments: Experiments on five datasets indicate that the unified model outperforms state-of-the-art methods in node-classification accuracy.The experiments also indicate that combining GCN and LPA learns more informative edge weights and improves performance.
2. Unifying GCN and LPA
GCN and LPA are parallel graph message-passing methods that propagate features and labels, respectively. The paper establishes theoretical links through smoothing and influence, then uses them to build GCN-LPA with learnable edge weights and end-to-end LPA regularization.
- Node classification uses graph edges as additional information, with LPA propagating labels and GCN propagating and transforming node features.
- Smoothing: GCN and LPA are theoretically related because both smooth node information across graph edges.Under identity activation and transformations, GCN representations become weighted neighbor averages, paralleling LPA label propagation.
- Smoothing: Feature smoothing guarantees bounded label-smoothing error when the latent feature-to-label mapping is differentiable and L-Lipschitz.The bound depends on the feature reconstruction error and higher-order terms; learnable edge weights can directly improve feature smoothing.
- Influence: After k iterations or layers, LPA label influence equals, in expectation, cumulative normalized GCN feature influence under ReLU activations.This relationship motivates combining label-based and feature-based propagation in one model.
- Unified model: GCN-LPA jointly learns edge weights and GCN parameters, using LPA prediction loss as regularization to guide edge-weight learning.The learned weights emphasize paths and potential edges connecting nodes with the same labels, transferring label-space information to feature-space GCN learning.
- Empirical analysis: On five datasets, GCN-LPA outperforms state-of-the-art methods in classification accuracy, while weighted intra-class edges improve embeddings and robustness to noisy edges.In the karate club experiment, increasing intra-class edge weights produced linearly separable embeddings and preserved cluster separation after adding noisy inter-class edges.
3. Connection to Existing Work
The paper relates its learnable edge-weight approach to adaptive LPA, graph attention, and LLE, while distinguishing its label-supervised use of graph structure.
- Locally Linear Embedding: LLE learns edge weights from local linear dependencies for unsupervised dimensionality reduction, while this work transfers edge importance across spaces in a semi-supervised, high-order setting.The comparison emphasizes that LLE relies on local proximity only.
- Adaptive LPA: Adaptive LPA variants learn edge weights from node features, but use those features to construct graph structure rather than directly predict labels.The paper instead treats LPA itself as regularization.
- Graph attention: Graph attention methods learn edge weights from node features, whereas this work learns attention weights based on node labels for a more task-oriented objective.The cited attention mechanisms compute weights from transformed features of edge endpoints.
4. Experiments
Experiments evaluate GCN-LPA on five citation and coauthor networks against feature-based, structure-based, and GNN baselines. Results report classification accuracy, sensitivity to LPA settings, labeled-node dependence, and training-time overhead.
- Datasets: Experiments use five datasets spanning citation and coauthor networks, with documents or authors as nodes and task-specific features and class labels.The citation datasets are Cora, Citeseer, and Pubmed; the coauthor datasets are Coauthor-CS and Coauthor-Phy.
- Baselines: The comparison includes feature-only MLP and LR, structure-only LPA, and GNN-based methods using both node features and graph structure.Baselines also include GCN, GAT, JK-Net, and GraphSAGE.
- Experimental setting: The experiments use a transductive 6:2:2 train-validation-test split, train for 200 epochs, and report mean accuracy with 95% confidence intervals over three runs.All node features and the full graph are available, while labels are known for only part of the nodes.
- Classification results: GCN-LPA surpasses state-of-the-art GCN/GNN baselines in node-classification accuracy, while JK-Net performs strongly on Cora but inconsistently elsewhere.Using only node features or only graph structure is described as causing information loss.
- Sensitivity analysis: Classification accuracy initially improves with more LPA iterations but declines when noisy nodes enter propagation, while λ values from 1 to 5 are easier to train than λ = 0.The λ result supports using LPA loss as regularization during joint learning.
- Ablation and efficiency: GCN-LPA performance worsens as the LPA labeled-node ratio decreases, and it requires only 9.2% extra training time on average compared with GCN.The runtime comparison uses random graphs ranging from 1,000 to 1,000,000 nodes.
5. Conclusion and Future Work
The paper unifies GCN and LPA through a model that jointly learns transformation matrices and edge weights, with LPA assisting GCN as a regularizer. Experiments support improved accuracy and time efficiency, while future work targets inductive settings and other aggregation functions.
- GCN-LPA learns transformation matrices and edge weights simultaneously, with an LPA regularizer assisting GCN.
- Experiments on five datasets show that GCN-LPA outperforms state-of-the-art baselines and is highly time-efficient with respect to graph size.
- Future work includes evaluating inductive settings without test-node access during training and extending the model to other aggregation functions.
A. Proof of Theorem 1
The proof normalizes edge weights and uses a first-order Taylor expansion to analyze the approximation of a node’s output from neighboring information. Inequality arguments then bound the resulting approximation error.
- Normalized edge weights are defined as ã_ij = a_ij/d_ii, and their sum over a node’s neighbors equals 1.
- A first-order Taylor expansion with Peano’s remainder is applied at x_i under the assumption that M is differentiable.
- The approximation is bounded using the Cauchy–Schwarz inequality and the L-Lipschitz property.
B. Proof of Theorem 2
The proof characterizes feature and label influence through weighted paths and random walks. It accounts for LPA’s repeated resetting of labeled nodes and restricts relevant paths according to labeling status.
- Feature influence sums weighted paths of a fixed length, whereas label influence sums paths of length at most k because labeled nodes reset after each LPA iteration.
- The product of normalized edge weights represents the probability of a path, so summing these products gives the probability that a random walk reaches a target node after k steps.
- For label influence, paths are restricted to unlabeled nodes except for the endpoint, reflecting that labeled nodes retain constant initial labels during propagation.
- The proof combines the feature- and label-influence lemmas to establish the stated theorem under an assumption about independent labeling status.
C. Proof of Theorem 3
The proof isolates contributions to a label dimension in LPA by tracing them to nodes with the corresponding initial label. This yields a path-based expression for label influence.
- Different label dimensions do not interact during LPA, so a label dimension receives contributions only from nodes with the matching initial label.
- The argument therefore expresses the relevant output label component through label influence accumulated from nodes sharing that initial label.
- The contribution from matching-label nodes is weighted by the label-influence quantity I_l(v_a, v_b; k).
D. Proof of Theorem 4
The proof bounds the Hessian of D(x) by 2I, using assumptions about representation dimensionality and the spectrum of a Markov matrix. It also connects GCN aggregation to a gradient-descent step whose size may be too large to guarantee decrease.
- Assumptions: The proof assumes scalar node representations, while noting that the conclusion generalizes to multidimensional representations by decomposing D(x) into one-dimensional cases.The proof continues using bold notation for node representations despite treating them as scalars.
- Proof strategy: The proof begins by introducing lemmas for the gradient and Hessian of the quadratic function D(x), then uses them to establish Theorem 4.The Hessian lemma states that ∇2D(x) ⪯ 2I.
- Proof strategy: GCN aggregation is equivalent to one gradient-descent step with step size one, but this step size does not guarantee that D(h(k)) ≤ D(x(k)).The proof attributes the lack of guarantee to the possibility that the step size is too large to reduce D.
- Hessian bound: The resulting matrix relation is 2I − ∇2D(x) positive semidefinite, equivalently ∇2D(x) ⪯ 2I.The proof identifies 2I − ∇2D(x) with I + D−1A before applying the Markov-matrix spectrum.
- Hessian bound: Because D−1A is a Markov matrix with eigenvalues in [-1, 1], I + D−1A has eigenvalues in [0, 2] and is positive semidefinite.This spectral argument establishes the required matrix property for the Hessian bound.
E. More Visualization Results on Karate Club Network
The karate-club visualization compares GCN and GCN-LPA representations across one to four layers under a fixed two-dimensional experimental setup.
- Visualization setup: Figure 7 visualizes GCN and GCN-LPA on the karate club network with the number of layers varied from 1 to 4.The layer sweep examines how learned representations evolve.
- Visualization setup: The experiment uses one-hot identity vectors as initial node features and sets both hidden-layer and output dimensions to 2.These choices define the representation dimensions shown in the visualization.
- Visualization setup: Transformation matrices are uniformly initialized in [-1, 1], and sigmoid is used as the nonlinear activation function.These settings are held as part of the visualization configuration.
F. Hyper-parameter Settings
The hyper-parameter section specifies how GCN-LPA components and search procedures are configured across datasets, with detailed settings reported in Table 4.
- Model configuration: GCN-LPA uses the same dimension for all hidden layers, while its GCN layer count and LPA iteration count can differ.GCN and LPA are implemented as independent modules.
- Search procedure: Hyper-parameters are selected by grid search on Cora and by one-at-a-time fine-tuning on the other datasets.For non-Cora datasets, one hyper-parameter is varied at a time to test for further improvement.
- Configuration reference: Table 4 lists the detailed hyper-parameter settings used for all datasets.The table is the section’s reference for dataset-specific configuration values.