Source-linked AI summary
Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning
Qimai Li, Zhichao Han, Xiao-Ming Wu
TL;DR
The paper clarifies why GCNs work and identifies their limits in semi-supervised learning with few labels. It proposes co-training and self-training approaches that substantially improve GCN performance while avoiding additional validation labels.
Problem
GCN mechanisms remain unclear, while shallow GCNs struggle with few labels and require additional labeled data for validation and model selection.
Method
The paper interprets GCN graph convolution as Laplacian smoothing and proposes co-training with random walks plus self-training to expand supervision.
Results
At 1% labeling, the methods improve over GCN-V by 23% on Cora and 28% on CiteSeer, and over GCN+V by 12% and 7%, respectively.
Takeaways & Limitations
GCNs can perform substantially better with very few labels when combined with co-training and self-training, without requiring additional labeled validation data.
Takeaways & Limitations
Shallow GCNs cannot sufficiently propagate label information across the graph when only a few labels are available.
Abstract
from arXiv · showhide
Many interesting problems in machine learning are being revisited with new deep learning tools. For graph-based semisupervised learning, a recent important development is graph convolutional networks (GCNs), which nicely integrate local vertex features and graph topology in the convolutional layers. Although the GCN model compares favorably with other state-of-the-art methods, its mechanisms are not clear and it still requires a considerable amount of labeled data for validation and model selection. In this paper, we develop deeper insights into the GCN model and address its fundamental limits. First, we show that the graph convolution of the GCN model is actually a special form of Laplacian smoothing, which is the key reason why GCNs work, but it also brings potential concerns of over-smoothing with many convolutional layers. Second, to overcome the limits of the GCN model with shallow architectures, we propose both co-training and self-training approaches to train GCNs. Our approaches significantly improve GCNs in learning with very few labels, and exempt them from requiring additional labels for validation. Extensive experiments on benchmarks have verified our theory and proposals.
1 Introduction
The paper explains why GCNs work for semi-supervised learning and identifies their limits with few labels and deeper architectures. It proposes co-training and self-training approaches to improve label efficiency and address localized propagation.
- Motivation: Semi-supervised learning uses abundant unlabeled data alongside typically small labeled datasets to reduce labeling demands.Leveraging unlabeled data can significantly improve accuracy when structural and feature information is used properly.
- Motivation: GCNs extend convolutional neural networks to graph-structured data and naturally integrate vertex features with graph topology.The paper builds on the simplified GCN model proposed for semi-supervised classification.
- GCN insights: GCN graph convolution is a special form of Laplacian smoothing that mixes each vertex’s features with those of nearby neighbors.This makes features within the same cluster more similar, easing classification, but can cause over-smoothing.
- GCN limitations: Deeper GCNs risk over-smoothing and become more difficult to train, while shallow GCNs require additional validation labels and struggle to propagate labels globally when supervision is scarce.The two-layer GCN’s localized convolution causes performance to drop quickly as training size shrinks, even with 500 additional validation labels.
- Proposed solutions: The paper proposes co-training GCNs with random-walk models and self-training GCNs to complement global topology exploration and overcome localized propagation.Combining the two approaches is reported to substantially improve GCNs for semi-supervised learning.
2 Preliminaries and Related Works
This section defines graph notation and semi-supervised classification on graphs, then reviews graph-based learning and graph convolutional networks. It presents GCNs as a simplified, spectrum-free spectral model that combines graph structure with vertex features for semi-supervised prediction.
- Graph notation: Graphs are represented as undirected G = (V, E) with nonnegative adjacency matrix A and degree matrix D.The graph has vertex set V with |V| = n, and D is diagonal with vertex degrees.
- Problem setting: Semi-supervised graph classification predicts labels for unlabeled vertices Vu given features X and labels for vertices Vl.Each vertex feature xi is c-dimensional, and the graph is represented by G = (V, E, X).
- Graph-based learning: Graph-based semi-supervised methods exploit graph or manifold structure to learn with very few labels, often using the assumption that nearby vertices share labels.Representative approaches include min-cuts and randomized min-cuts.
- Graph convolutional networks: GCNNs comprise spatial models that aggregate neighborhood information and spectral models that define convolution in the graph spectral domain.Spectral filtering can be approximated with Chebyshev polynomials, producing a spectrum-free ChebNet that avoids explicitly computing Laplacian eigenvectors.
- Graph convolutional networks: GCNs simplify ChebNet by setting K = 1, approximating λmax of Lsym by 2, and applying a normalization trick to the convolution matrix.The resulting propagation rule transforms activations H(l) using normalized graph connectivity, trainable weights Θ(l), and an activation function σ.
- GCN semi-supervised classification: In semi-supervised classification, a two-layer GCN applies a softmax classifier and trains its weights with cross-entropy over labeled examples.The model mixes features of unlabeled vertices with nearby labeled vertices and propagates them through multiple layers.
3 Analysis
The analysis identifies GCN graph convolution as symmetric Laplacian smoothing, explaining its strong performance by making connected vertices’ features more similar. It also shows that deeper GCNs face over-smoothing and training limits, while shallow models struggle to propagate labels and depend on validation data for model selection.
- Graph convolution: A one-layer GCN substantially outperformed a one-layer FCN on Cora with 20 labels per class, showing that graph convolution drives the performance gain.The only architectural difference is the graph convolution matrix applied to the feature matrix.
- Laplacian smoothing: GCN graph convolution is a special form of Laplacian smoothing that averages each vertex’s features with those of itself and its neighbors.With self-loops and symmetric normalization, the operation is exactly symmetric Laplacian smoothing, which makes features within densely connected clusters more similar.
- Over-smoothing: Repeated smoothing can cause over-smoothing: features within each connected component converge to the same values, harming classification accuracy.For symmetric Laplacian smoothing, the limiting values are proportional to the square root of vertex degree; self-loops ensure no bipartite component remains.
- Architecture limits: A shallow GCN cannot sufficiently propagate label information across the graph because graph convolution is localized and only combines adjacent neighbors’ features.Deeper GCNs can improve propagation, but many layers are difficult to train and may mix features from different clusters until they become indistinguishable.
- Validation dependence: Training a GCN without an additional validation set causes a significant performance drop because validation accuracy is used for early stopping and model selection.Without validation, performance drops much more sharply than with validation.
4 Solutions
The proposed solutions expand GCN training labels through co-training with global random-walk information, self-training from confident GCN predictions, or their Union and Intersection combinations. These methods optimize on the expanded label set without additional validation data and address GCN limitations with few labels or disconnected graph components.
- Co-Training: Co-training combines a GCN with a random-walk model to exploit global graph structure and add confident vertices to the training set.The random walk complements the GCN’s localized filtering, which performs unsatisfactorily with few labeled data.
- Co-Training: ParWalks computes absorption probabilities from P = (L + αΛ)−1 and uses the t most confident vertices for each class to expand GCN training.These probabilities represent how likely pairs of vertices are to belong to the same class and capture global graph structure.
- Self-Training: Self-training repeatedly adds each class’s most confident GCN predictions to the label set and continues training from the pretrained GCN.This provides additional training examples and complements random-walk propagation when graphs contain isolated small components.
- Combining Co-Training and Self-Training: Union adds confident labels identified by either the random walk or GCN, whereas Intersection adds labels selected confidently by both methods.The combined methods aim to improve label diversity, classifier robustness, or label accuracy.
- Training Without Validation: All proposed methods train on the expanded label set without additional validation data, provided it contains enough correct labels.A proposed lower-bound estimate for labels is η = |V_l| from (d̂)^τ ∗ η ≈ n, where τ is the GCN layer count and d̂ the graph’s average degree.
5 Experiments
Experiments on citation-network benchmarks verify the proposed Co-Training, Self-Training, Union, and Intersection methods. The methods generally outperform GCN baselines, especially with very few labels, while parameter and runtime analyses support practical use.
- Experimental setup: The study evaluates Co-Training, Self-Training, Union, and Intersection against GCN variants and several state-of-the-art semi-supervised learning methods.GCN baselines include GCN+V, GCN-V, and Cheby; other baselines include LP, Planetoid, DeepWalk, ManiReg, and SemiEmb.
- Experimental setup: Experiments use the CiteSeer, Cora, and PubMed citation networks, representing documents with binary bag-of-words features and citation links with binary adjacency matrices.These are commonly used citation-network benchmarks.
- Results: Co-Training performs best on PubMed with strong manifold structure, Self-Training performs worst there but does well on CiteSeer, and Union often performs best while Intersection benefits from larger training sets.Intersection filters out many labels, whereas Co-Training leverages graph structure and Self-Training does not.
- Results: With small training sizes, the proposed methods substantially outperform GCN baselines, improving over GCN-V by 23% and 28% and over GCN+V by 12% and 7% at 1% labeling on Cora and CiteSeer.At 0.05% labeling on PubMed, they improve over GCN-V and GCN+V by 37% and 18%, respectively.
- Influence of the Parameters: Using 3η newly added labels performs similarly to using 2η or 4η, balancing noise from too many labels against insufficient data for training a good GCN classifier.The lower bound η is estimated from (d̂)^τ*η ≈ n.
- Computational Cost: Co-Training’s random-walk overhead is negligible on Cora and CiteSeer and takes less than 0.38 seconds on PubMed, while Self-Training has runtime comparable to a GCN.Self-Training converges quickly because it builds on a pre-trained GCN.
6 Conclusions
The paper advances understanding of GCNs for semi-supervised classification by identifying their mechanisms and limitations and deriving solutions to overcome them. It also proposes future work on deep-compatible convolutional filters and advanced deep learning technology.
- 6 Conclusions: The paper contributes to understanding the GCN model and its application in semi-supervised classification.This contribution targets the model itself and its use in semi-supervised classification.
- 6 Conclusions: The analysis reveals the GCN model’s mechanisms and limitations while motivating solutions that overcome its limits.The conclusions connect theoretical analysis to proposed remedies.
- 6 Conclusions: Future work will develop convolutional filters compatible with deep architectures and exploit advanced deep learning technology.The passage identifies both directions as planned extensions.