PaperlayerView exact revision on arXiv

Source-linked AI summary

Semi-Supervised Classification with Graph Convolutional Networks

Thomas N. Kipf, Max Welling

arXiv:1609.02907v4cs.LGstat.ML

TL;DR

Node classification in graphs is challenging when labels are available for only a small subset of nodes. This paper introduces a scalable graph convolutional network based on a first-order spectral approximation, and finds it outperforms several recent methods while remaining computationally efficient.

  • Problem

    The paper addresses semi-supervised node classification in graphs when labels are available for only a small subset of nodes.

  • Method

    The model uses a graph convolutional network with an efficient layer-wise propagation rule motivated by a first-order approximation of spectral graph convolutions, combining graph structure and node features.

  • Results

    The GCN outperforms several recently proposed methods by a significant margin while remaining computationally efficient on network datasets.

  • Takeaways & Limitations

    The approach can encode graph structure and node features in a way useful for semi-supervised classification.

  • Takeaways & Limitations

    The framework does not naturally support edge features and is limited to undirected graphs, although a graph transformation handled both in one dataset.

Abstract

from arXiv · show

We present a scalable approach for semi-supervised learning on graph-structured data that is based on an efficient variant of convolutional neural networks which operate directly on graphs. We motivate the choice of our convolutional architecture via a localized first-order approximation of spectral graph convolutions. Our model scales linearly in the number of graph edges and learns hidden layer representations that encode both local graph structure and features of nodes. In a number of experiments on citation networks and on a knowledge graph dataset we demonstrate that our approach outperforms related methods by a significant margin.

1 INTRODUCTION

The paper addresses semi-supervised node classification with few labeled nodes by encoding graph structure directly in a neural network, avoiding explicit graph regularization. It introduces a simple propagation rule motivated by first-order spectral graph convolution approximations and applies it to fast, scalable classification.

  • Problem setting: Semi-supervised node classification propagates label information through graph structure when only a small subset of nodes is labeled.The setup applies to graphs such as citation networks, where nodes may represent documents.
  • Problem setting: Explicit graph regularization assumes connected nodes are likely to share labels, but graph edges may encode information beyond node similarity.This limitation can restrict the modeling capacity of graph-based methods.
  • Approach: The model encodes graph structure through f(X, A) and trains on labeled nodes, allowing supervised gradients to shape representations of both labeled and unlabeled nodes.Conditioning the neural network on the adjacency matrix avoids explicit graph-based regularization in the loss.
  • Contributions: The paper introduces a layer-wise propagation rule for graph neural networks motivated by a first-order approximation of spectral graph convolutions.The rule is described as simple and well-behaved.
  • Contributions: The proposed graph-based neural network supports fast and scalable semi-supervised classification of graph nodes, with experiments conducted across multiple datasets.The introduction presents scalability and experimental validation as central contributions.

2 FAST APPROXIMATE CONVOLUTIONS ON GRAPHS

The GCN propagation rule is motivated as a first-order, localized approximation to spectral graph convolutions. Chebyshev polynomial filters establish edge-linear computation, while further simplifications yield a renormalized layer suitable for deep, feature-based graph networks.

  • Spectral motivation: Spectral graph convolution is computationally expensive because multiplying by the eigenvector matrix costs O(N^2), and Laplacian eigendecomposition may also be prohibitive.
  • Localized spectral filters: Truncated Chebyshev expansions produce K-localized filters that depend only on nodes within K steps and have evaluation complexity O(|E|).
  • First-order approximation: Restricting the convolution to K = 1 gives a Laplacian-linear filter, and stacking layers recovers richer filters while successive operations reach k-hop neighborhoods.
  • Renormalization: Repeated application of IN + D−1 2 AD−1 2 can cause exploding or vanishing gradients because its eigenvalues lie in [0, 2], motivating renormalization with self-loops.
  • Feature-wise filtering: For C input channels and F feature maps, the renormalized filtering operation costs O(|E|FC) using sparse–dense matrix multiplication.

3 SEMI-SUPERVISED NODE CLASSIFICATION

This section formulates semi-supervised node classification with a two-layer GCN that conditions propagation on node features and graph structure. It specifies normalized adjacency preprocessing, labeled-node cross-entropy training, and edge-linear computational and memory costs.

  • Model formulation: The GCN conditions semi-supervised node classification on both node features X and the graph adjacency matrix A.This relaxes assumptions typically made in graph-based semi-supervised learning.
  • Model formulation: The two-layer model operates on a symmetric binary or weighted adjacency matrix and precomputes normalized adjacency ˆA = ˜D−1.The supplied passage introduces ˆA = ˜D−1 2 ˜A ˜D−1 2 across consecutive passages, though the displayed expression is truncated.
  • Optimization: O(|E|) memory is required for sparse adjacency storage, making full-batch gradient descent viable when datasets fit in memory.Dropout introduces stochasticity, while mini-batch memory-efficient extensions are left for future work.
  • Implementation: O(|E|CHF) computational complexity is achieved for evaluating Eq. 9 using sparse-dense matrix multiplications in TensorFlow.The stated complexity is linear in the number of graph edges.

4 RELATED WORK

Related work spans graph-based semi-supervised methods, graph-embedding approaches, and neural networks operating directly on graphs. The paper positions its method as a scalable simplification of spectral graph convolutions for transductive node classification on larger networks.

  • Graph-based semi-supervised learning: Graph-based semi-supervised methods largely use explicit graph Laplacian regularization or graph embeddings.Examples of Laplacian-based methods include label propagation, manifold regularization, and deep semi-supervised embedding.
  • Graph-based semi-supervised learning: DeepWalk, LINE, and node2vec learn graph embeddings using skip-gram-inspired neighborhood prediction with random-walk or breadth-first-search schemes.These approaches use multi-step pipelines, as indicated by the supplied passage.
  • Neural networks on graphs: Earlier graph neural networks used recurrent propagation with contraction maps applied repeatedly until node representations reached stable fixed points.Later work alleviated this restriction by introducing modern recurrent-neural-network training practices.
  • Neural networks on graphs: A related node-classification model reported O(N^2) complexity, while another converted local graph neighborhoods into sequences requiring a preprocessing node ordering.These design choices limit application scale or impose an ordering requirement.
  • Spectral graph convolutions: The method builds on spectral graph convolutions and fast localized convolutions, simplifying those frameworks for transductive node classification on significantly larger networks.The cited spectral-convolution lineage includes Bruna et al. (2014) and Defferrard et al. (2016).

5 EXPERIMENTS

The experiments evaluate GCNs on citation networks, a knowledge-graph-derived entity-classification dataset, random graphs, and graph-propagation models. The setup uses sparse node features, limited labels, standardized dataset splits, and comparisons with established semi-supervised and graph-embedding baselines.

  • Experimental scope: Experiments cover semi-supervised document classification, knowledge-graph entity classification, graph-propagation evaluation, and random-graph runtime analysis.The random-graph experiments measure training time per epoch across graph sizes.
  • Citation networks: Citation-network experiments use Citeseer, Cora, and Pubmed, representing documents as nodes with citation links as undirected edges and sparse bag-of-words features.Training uses 20 labels per class while retaining all feature vectors.
  • Knowledge graph: NELL is a bipartite knowledge-graph dataset whose entity nodes have sparse feature vectors and whose relations are represented using separate relation nodes.The preprocessing follows Yang et al. (2016), with unique one-hot representations added to extend NELL’s features.
  • Evaluation setup: Unless otherwise noted, models are two-layer GCNs evaluated on 1,000 labeled test examples using Yang et al. (2016) dataset splits and a 500-example validation set.Hyperparameters include dropout, first-layer L2 regularization, and the number of hidden units; deeper models with up to 10 layers are evaluated in Appendix B.
  • Baselines: Baselines include LP, SemiEmb, ManiReg, DeepWalk, ICA with local and relational logistic regression, and the best-performing Planetoid variant.TSVM is omitted because it does not scale to the large number of classes in one dataset.

6 RESULTS

Section 6 evaluates classification accuracy, training time, propagation-model variants, and per-epoch efficiency across citation networks and simulated random graphs. Results use controlled dataset splits, repeated runs, and GPU/CPU timing comparisons against Planetoid where applicable.

  • Classification accuracy: Table 2 reports classification accuracy in percent, with ICA averaged over 100 random node orderings and other baselines taken from Yang et al. (2016).Planetoid* denotes the best respective-dataset model among the variants reported in the Planetoid paper.
  • Training-time comparison: The study reports wall-clock training time until convergence for GCN and Planetoid on the same hardware, including GCN validation-error evaluation.Both models use the same dataset splits, while GCN accuracy is averaged over 100 random weight initializations.
  • Random splits: GCN performance is also evaluated on 10 random dataset splits matching the original split size, reporting test-set mean accuracy and standard error in percent.This analysis is labeled GCN (rand. splits).
  • Per-epoch efficiency: Per-epoch training time is measured for 100 epochs on simulated random graphs, comparing GPU and CPU-only TensorFlow implementations.Each epoch includes the forward pass, cross-entropy calculation, and backward pass.

7 DISCUSSION

The method outperforms related approaches, while its renormalized propagation model improves efficiency and predictive performance over alternative graph-convolution models. The discussion identifies memory, graph-type, edge-feature, and locality limitations with possible remedies.

  • Discussion: The method outperforms recent related methods by a significant margin in semi-supervised node classification experiments.Graph-Laplacian methods may be limited by assuming edges encode mere node similarity, while skip-gram methods use a difficult-to-optimize multi-step pipeline.
  • Discussion: The renormalized propagation model offers improved efficiency and predictive performance compared with naïve first-order and higher-order Chebyshev-polynomial models.Its efficiency involves fewer parameters and operations, including multiplication or addition.
  • Memory requirement: Full-batch training requires memory that grows linearly with dataset size, but CPU training remains viable for graphs that exceed GPU memory.Mini-batch stochastic gradient descent can alleviate memory demands, although batch generation must account for the Kth-order neighborhood required by a K-layer GCN.
  • Directed edges and edge features: The framework does not naturally support edge features and is limited to undirected graphs, but NELL shows directed edges and edge features can be represented indirectly.The representation converts the directed graph into an undirected bipartite graph with additional nodes representing original edges.
  • Limiting assumptions: The approximations assume locality and equal importance for self-connections and neighboring edges, motivating a learnable trade-off parameter λ.Locality means dependence on the Kth-order neighborhood for a GCN with K layers.

8 CONCLUSION · A RELATION TO WEISFEILER-LEHMAN ALGORITHM

The paper introduces GCNs for semi-supervised graph classification, using efficient propagation based on first-order spectral convolution approximations to encode graph structure and node features. It also interprets GCN propagation as a differentiable, parameterized generalization of the 1-dim Weisfeiler-Lehman algorithm.

  • 8 CONCLUSION: The proposed GCN addresses semi-supervised classification on graph-structured data with an efficient layer-wise propagation rule.The rule is based on a first-order approximation of spectral convolutions on graphs.
  • 8 CONCLUSION: Experiments on network datasets suggest that GCN representations encode both graph structure and node features for semi-supervised classification.The conclusion states that the model outperforms several recently proposed methods, although the supplied passage truncates the comparison.
  • A RELATION TO WEISFEILER-LEHMAN ALGORITHM: The 1-dim Weisfeiler-Lehman algorithm assigns node labels from graph structure and optionally discrete initial node labels.It provides a framework for unique node-label assignment given a graph and initial coloring.
  • A RELATION TO WEISFEILER-LEHMAN ALGORITHM: WL-1 iteratively updates each node’s coloring by hashing the colors of its neighboring nodes.The algorithm takes an initial node coloring as input and produces a final node coloring.
  • A RELATION TO WEISFEILER-LEHMAN ALGORITHM: The WL-1 hash function can be replaced by a differentiable neural-network-like function with trainable parameters.Node representations become layer activations, combined using normalized edges, weight matrices, and differentiable nonlinearities.
  • A RELATION TO WEISFEILER-LEHMAN ALGORITHM: Using degree-based normalization recovers the GCN propagation rule in vector form.The passage identifies this rule with Eq. 2 of the GCN model.
  • A RELATION TO WEISFEILER-LEHMAN ALGORITHM: The GCN is, loosely speaking, a differentiable and parameterized generalization of the 1-dim Weisfeiler-Lehman algorithm on graphs.This interpretation connects the neural propagation mechanism to iterative WL-1 neighborhood aggregation.

A.1 NODE EMBEDDINGS WITH RANDOM WEIGHTS

An untrained GCN with random weights can extract useful node features through local graph structure, even without node features or training. On Zachary’s karate club network, its embeddings are comparable to those from the more expensive unsupervised method DeepWalk.

  • Method: An untrained GCN with random weights can serve as a powerful feature extractor for graph nodes, by analogy with the Weisfeiler-Lehman algorithm.The example uses a 3-layer GCN model.
  • Implementation: The model uses randomly initialized weight matrices, with ˆA, X, and Z defined as in Section 3.1.Self-connections are implicitly assumed to have been added to every node.
  • Experiment: The experiment applies the model to Zachary’s karate club network, containing 34 nodes and 154 undirected, unweighted edges assigned to four modularity-based classes.The graph’s node labels come from modularity-based clustering.
  • Implementation: Using X = I_N with randomly ordered nodes, the model has hidden dimensionality 4 and a two-dimensional output for visualization.The featureless input uses the N by N identity matrix, where N is the number of nodes.
  • Result: The untrained GCN’s node embeddings are comparable to DeepWalk embeddings, despite DeepWalk using a more expensive unsupervised training procedure.The embeddings are the outputs Z of the untrained 3-layer GCN applied to the karate club network.

A.2 SEMI-SUPERVISED NODE EMBEDDINGS

A GCN trained with one labeled node per class uses graph structure to learn node embeddings that linearly separate communities in the karate club network.

  • A.2 SEMI-SUPERVISED NODE EMBEDDINGS: The embeddings become useful for classification by incorporating graph structure and features extracted from that structure at later layers.This behavior is illustrated on the karate club network.
  • A.2 SEMI-SUPERVISED NODE EMBEDDINGS: The model is trained semi-supervised with one labeled example per class, totaling four labeled nodes.Training runs for 300 iterations with Adam, a 0.01 learning rate, and cross-entropy loss.
  • A.2 SEMI-SUPERVISED NODE EMBEDDINGS: The model succeeds in linearly separating communities using minimal supervision and graph structure alone.Figure 4 shows the evolution of node embeddings over training iterations.

B EXPERIMENTS ON MODEL DEPTH

The experiments examine how GCN depth affects classification on Cora, Citeseer, and Pubmed using 5-fold cross-validation, comparing standard models with residual connections. Best performance occurs at 2–3 layers, while deeper standard models become difficult to train and may overfit.

  • Experimental setup: The study evaluates model depth on Cora, Citeseer, and Pubmed using 5-fold cross-validation with all labels.The comparison includes standard GCNs and models with residual connections between hidden layers.
  • Depth findings: Best results are obtained with 2- or 3-layer models across the considered datasets.
  • Depth findings: Beyond 7 layers, standard models without residual connections can become difficult to train as each node’s effective context expands with depth.The effective context grows through the node’s Kth-order neighborhood for a K-layer model.
  • Depth findings: Increasing model depth can also cause overfitting because the number of parameters increases.
Loading 1609.02907v4…