One-sentence Summary

Researchers from the University of Amsterdam and CIFAR propose a graph convolutional network (GCN) for semi-supervised learning that uses a localized first-order approximation of spectral convolutions to scale linearly with the number of edges and to encode local graph structure and node features, achieving significant improvements over previous methods on citation networks and a knowledge graph dataset.

Key Contributions

• A scalable graph convolutional network (GCN) for semi-supervised node classification is introduced, using a localized first-order approximation of spectral graph convolutions that scales linearly in the number of graph edges.
• The model employs a single weight matrix per layer and symmetric normalization of the adjacency matrix, handling varying node degrees and integrating local graph structure and node features without a predefined node ordering.
• Experiments on citation networks and a knowledge graph dataset demonstrate that the GCN outperforms several recent methods by a significant margin while being computationally efficient.

Introduction

The authors address semi-supervised node classification on graphs, such as labeling documents in citation networks when only a small fraction of nodes have labels. Prior methods often rely on explicit graph Laplacian regularization that assumes connected nodes share the same label, which limits modeling power because real edges can encode more varied relationships. Graph embedding approaches like DeepWalk require multi-step pipelines, and earlier graph neural networks suffer from scalability issues, including degree-specific weight matrices or quadratic complexity. The authors introduce a graph convolutional network (GCN) that directly conditions on the adjacency matrix to learn node representations without explicit regularization. Their key contribution is a simple, layer-wise propagation rule motivated by a first-order approximation of spectral graph convolutions, enabling fast and scalable semi-supervised classification that achieves state-of-the-art accuracy and efficiency.

Dataset

The authors experiment with three types of datasets: citation networks, a knowledge graph dataset, and synthetic random graphs. Dataset statistics are summarized in Table 1.

• Citation networks (Citeseer, Cora, Pubmed)

• Source: Standard citation graph benchmarks where nodes are documents, edges are undirected citation links.

• Features: Each document is described by a sparse bag-of-words feature vector.

• Graph construction: A binary, symmetric adjacency matrix is built from the citation links.

• Training setup: For semi-supervised node classification, only 20 labeled nodes per class are used for training, while all feature vectors of all nodes are available.

• NELL

• Source: Extracted from the NELL knowledge graph, following the preprocessing of Yang et al. (2016).

• Composition: A bipartite graph with 55,864 relation nodes and 9,891 entity nodes. For each entity pair (e1, r, e2), separate relation nodes r1 and r2 are created, resulting in connections (e1, r1) and (e2, r2).

• Features: Entity nodes have sparse feature vectors; relation nodes receive a unique one-hot representation, giving every node a 61,278-dimensional sparse feature vector.

• Graph construction: A binary, symmetric adjacency matrix where A_ij = 1 if any edge exists between nodes i and j.

• Training setup: The extreme semi-supervised case: only one labeled example per class is used for training.

• Random graphs

• Source: Simulated datasets for measuring training time per epoch.

• Composition: For a graph with N nodes, 2N edges are added uniformly at random.

• Features: The identity matrix I_N is used as the feature matrix X, treating each node as a unique one-hot vector (featureless approach).

• Labels: A dummy label Y_i = 1 is assigned to every node.

• Usage: These graphs are used solely to evaluate computational efficiency, not for classification accuracy.

For all real datasets, the resulting adjacency matrices and node feature matrices serve as input to the graph neural network. The limited training labels (20 per class for citation networks, 1 per class for NELL) are used to learn node representations, while the remaining unlabeled nodes form the test set.

Method

The authors leverage spectral graph convolutions to build a neural network model capable of efficient information propagation on graphs. They define spectral convolutions as the multiplication of a signal with a filter parameterized in the Fourier domain. Since evaluating this directly is computationally expensive, the authors approximate the filter using a truncated expansion of Chebyshev polynomials. This results in a localized convolution that depends only on nodes within a maximum of $K$K steps, reducing the complexity to be linear in the number of edges.

To build a deep neural network, the authors simplify this formulation by limiting the layer-wise convolution operation to $K=1$K=1, creating a layer-wise linear model. By further approximating the largest eigenvalue $\lambda_{\max} \approx 2$λmax​≈2 and constraining the number of parameters to prevent overfitting, the filtering operation simplifies significantly. To address numerical instabilities and exploding or vanishing gradients in deep networks, they introduce a renormalization trick. The generalized filtering operation for a signal with multiple input channels and feature maps is defined as: $Z = \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} X \Theta$Z=D~−21​A~D~−21​XΘ where $\tilde{A} = A + I_N$A~=A+IN​ represents the adjacency matrix with added self-connections, $\tilde{D}$D~ is the corresponding degree matrix, and $\Theta$Θ is the matrix of filter parameters.

Having established this efficient propagation model, the authors apply it to semi-supervised node classification. The model conditions on both the node feature data $X$X and the underlying graph structure $A$A, which is particularly powerful when the adjacency matrix contains relational information not present in the features alone. The overall multi-layer Graph Convolutional Network (GCN) architecture for this task is presented. As shown in the figure below:

For a concrete implementation, the authors consider a two-layer GCN. After a pre-processing step to calculate the normalized adjacency matrix $\hat{A} = \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$A^=D~−21​A~D~−21​, the forward model takes the form: $Z = f(X, A) = \operatorname{softmax} \left( \hat{A} \operatorname{ReLU} \left( \hat{A} X W^{(0)} \right) W^{(1)} \right)$Z=f(X,A)=softmax(A^ReLU(A^XW(0))W(1)) Here, $W^{(0)}$W(0) and $W^{(1)}$W(1) represent the input-to-hidden and hidden-to-output weight matrices, respectively. The softmax activation is applied row-wise. For semi-supervised multiclass classification, the model is trained by evaluating the cross-entropy error over all labeled examples: $\mathcal{L} = - \sum_{l \in \mathcal{Y}_L} \sum_{f=1}^{F} Y_{lf} \ln Z_{lf}$L=−∑l∈YL​​∑f=1F​Ylf​lnZlf​ where $\mathcal{Y}_L$YL​ denotes the set of labeled node indices. The network weights are optimized using batch gradient descent on the full dataset, with stochasticity introduced via dropout to prevent overfitting. The implementation utilizes sparse-dense matrix multiplications, ensuring the computational complexity remains linear with respect to the number of graph edges.

Experiment

The evaluation spans semi-supervised node classification on citation networks and a knowledge graph, comparing a two-layer graph convolutional network against methods such as label propagation, DeepWalk, ICA, and Planetoid. The experiments validate that incorporating feature propagation across graph neighborhoods substantially improves accuracy over approaches relying solely on label aggregation or graph-Laplacian regularization. An ablation of propagation models confirms that the proposed renormalization trick yields both higher predictive performance and computational efficiency. Additional runtime measurements on random graphs demonstrate linear scalability with the number of edges, highlighting the model's practical applicability to large graphs.

The table summarizes four datasets used for semi-supervised node classification. The three citation networks—Citeseer, Cora, and Pubmed—vary in size from 2,708 to 19,717 nodes and from 500 to 3,703 features, with label rates between 0.003 and 0.052. The NELL knowledge graph is substantially larger, containing 65,755 nodes and 266,144 edges across 210 classes, with an extremely low label rate of 0.001 that reflects only a single labeled example per class. Among the citation networks, Cora has the highest label rate (0.052) and Pubmed the lowest (0.003), despite Pubmed being the largest with nearly 20,000 nodes. NELL uses only one labeled instance per class, resulting in a label rate of 0.001, making it a much larger and more sparsely supervised dataset than the citation networks.

The proposed GCN model achieves the highest classification accuracy across all four datasets, exceeding prior methods by notable margins. It is substantially faster than Planetoid on Citeseer, Cora, and NELL, while providing a modest accuracy gain on Pubmed at a slightly higher training time. The results demonstrate that propagating feature information from neighbors in every layer yields both state-of-the-art predictive performance and favorable wall-clock efficiency. GCN attains the top accuracy on all datasets: 70.3% on Citeseer, 81.5% on Cora, 79.0% on Pubmed, and 66.0% on NELL, surpassing both label-propagation methods and skip-gram baselines. On Citeseer and Cora, GCN trains in 7 and 4 seconds respectively, compared to Planetoid's 26 and 13 seconds, while also delivering higher accuracy; on NELL, it reaches 66.0% accuracy in 48 seconds versus Planetoid's 61.9% in 185 seconds.

Across the three citation network datasets, the renormalization trick propagation model consistently achieves the highest classification accuracy, outperforming both higher-order Chebyshev filters and the first-order model. Eliminating graph-based propagation by using only input features causes a severe accuracy drop, particularly on Citeseer and Cora. The renormalization trick thus provides both superior predictive performance and efficient parameterization. The renormalization trick yields the top accuracy on all datasets (70.3% on Citeseer, 81.5% on Cora, 79.0% on Pubmed), surpassing Chebyshev filters, first-order models, and single-parameter variants. A plain multi-layer perceptron that ignores graph structure achieves only 46.5% on Citeseer and 55.1% on Cora, demonstrating the critical benefit of neighborhood feature propagation.

The evaluation uses semi-supervised node classification on three citation networks and the NELL knowledge graph to assess overall performance against baselines and compare propagation models. The proposed GCN with renormalization trick achieves state-of-the-art accuracy on all datasets, combining high predictive performance with efficient training. Ablation shows that this propagation method consistently outperforms alternatives, and removing graph-based feature propagation drastically reduces accuracy, confirming the model's effectiveness and the critical role of graph structure.