Source-linked AI summary
N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification
Sami Abu-El-Haija, Amol Kapoor, Bryan Perozzi, Joonseok Lee
TL;DR
Semi-supervised node classification must infer labels for most graph nodes from limited labeled data, while GCNs and random-walk embeddings capture complementary graph information. N-GCN combines GCNs operating at multiple random-walk scales and reports state-of-the-art results across the evaluated datasets and tasks.
Problem
Semi-supervised node classification infers labels for unlabeled nodes using graph structure, node features, and a small observed label subset.
Method
N-GCN jointly trains multiple GCNs on different powers of normalized adjacency and combines their outputs through a classification sub-network.
Results
N-GCN achieves state-of-the-art performance on all considered semi-supervised graph learning tasks.
Takeaways & Limitations
The model combines information from raw adjacency, multiple random-walk step sizes, and input features, while its attention can shift toward higher powers under perturbations.
Takeaways & Limitations
The analysis of GCNs learning random walks assumes identity activation and identity first-layer weights, conditions the paper states are not true in practice.
Abstract
from arXiv · showhide
Graph Convolutional Networks (GCNs) have shown significant improvements in semi-supervised learning on graph-structured data. Concurrently, unsupervised learning of graph embeddings has benefited from the information contained in random walks. In this paper, we propose a model: Network of GCNs (N-GCN), which marries these two lines of work. At its core, N-GCN trains multiple instances of GCNs over node pairs discovered at different distances in random walks, and learns a combination of the instance outputs which optimizes the classification objective. Our experiments show that our proposed N-GCN model improves state-of-the-art baselines on all of the challenging node classification tasks we consider: Cora, Citeseer, Pubmed, and PPI. In addition, our proposed method has other desirable properties, including generalization to recently proposed semi-supervised learning methods such as GraphSAGE, allowing us to propose N-SAGE, and resilience to adversarial input perturbations.
1 INTRODUCTION
The paper studies semi-supervised node classification when only a small subset of graph-node labels is observed. It introduces N-GCN, which combines GCN modules operating at multiple random-walk scales for classification.
- Background: Graph Convolutional Networks extend convolutional filters from regular spatial domains to irregular graph-structured data.This extension was motivated by the improvements of convolutional neural networks in computer vision.
- Problem: Semi-supervised graph learning recovers labels for unlabeled nodes from node features, graph structure, and a small labeled subset.Labels may be expensive to collect, whereas graph edges can be obtained explicitly or through pairwise similarities.
- Method: N-GCN feeds multiple GCN modules different powers of the normalized adjacency matrix, representing different random-walk step sizes and graph scales.The outputs are combined by a classification sub-network trained jointly with the GCN modules.
- Robustness: The classification sub-network can shift toward higher adjacency powers under input perturbations, widening the receptive field of the convolutional filters.The learned weights provide insight into how N-GCN combines information across graph scales.
- Results: N-GCN achieves state-of-the-art performance on the semi-supervised graph learning tasks considered in the paper.The introduction presents this result as evidence that explicit random walks enhance the model.
2 BACKGROUND
The background covers graph-based regularization, graph convolution, and node embeddings. These approaches differ in whether they model adjacency structure directly, diffuse features across graph edges, or represent random-walk co-occurrences.
- Semi-Supervised Node Classification: Traditional label propagation combines classification loss on labeled nodes with a graph-Laplacian regularizer encouraging connected nodes to have similar outputs.The coefficient λ controls the strength of the graph-based regularization term.
- Graph Convolutional Networks: A GCN layer multiplies node activations by normalized adjacency and trainable weights, then applies a nonlinearity.The first hidden activation is the feature matrix X, and the final softmax produces label scores for nodes.
- Graph Convolutional Networks: Left-multiplication by normalized adjacency averages features with direct neighbors, while successive GCN layers diffuse signals farther through the graph.This diffusion is performed through feature transformations and nonlinear activation functions.
- Graph Embeddings: Node embedding methods learn continuous vectors for graph nodes, while traditional approaches often optimize representations of the adjacency matrix.Eigenmaps is given as an example of the traditional formulation.
- Graph Embeddings: Random-walk embedding methods learn from co-occurrence statistics whose importance depends on node connectivity and distance in the walks.Their optimization target differs from traditional methods that represent the adjacency matrix directly.
3 OUR METHOD
N-GCN combines GCNs with random-walk information by applying multiple GCN instances to different powers of the normalized adjacency matrix. Their outputs are jointly combined and trained for semi-supervised node classification, targeting information across multiple graph scales.
- Motivation: GCNs and random-walk embeddings provide complementary graph information, but vanilla GCNs may struggle to model distant-node relationships directly.Vanilla GCN information flow passes through feature reduction and nonlinearities, limiting direct access to high powers of the normalized adjacency matrix.
- Network of GCNs: N-GCN feeds separate GCN instances with powers ˆA^0 through ˆA^(K−1), whose powers encode different random-walk step sizes.The identity power preserves input features, while higher powers represent progressively broader graph scales.
- Network of GCNs: The model concatenates outputs from the K GCNs and feeds them to a classification sub-network that learns a combination of multi-scale features.The combined features include normalized adjacency information, random-walk scales, and node features.
- Optimization: The fully-connected classifier is jointly trained with all GCN parameters using cross-entropy on known training labels.The classifier maps the concatenated representations to C output channels per node.
- Attention Classification Network: An alternative softmax-attention classifier learns a convex combination of GCN outputs and can add intermediate losses to make each GCN independently useful.The attention weights are produced by a softmax over one parameter per GCN.
Y ◦log N-GCN(X, ˆA)
The training objective uses labeled nodes to supervise N-GCN, while the framework also supports intermediate supervision and generalizes beyond vanilla GCNs. Its construction recovers existing models under special parameter choices.
- Objective: Intermediate supervision can be added to N-GCNa so that all GCN modules become independently useful.This supplements the loss applied at the overall N-GCN output.
- Implementation: The implementation applies every adjacency power to r GCN modules, although derivations simplify notation to one GCN per power.The implementation therefore contains r modules for each of the K adjacency powers.
- Generalization: The framework generalizes to arbitrary graph models, including GraphSAGE, yielding N-GCN and N-SAGE constructions.Algorithmic substitutions plug vanilla GCN or GraphSAGE modules into the shared network framework.
- Recovering Existing Models: Original GCN and SAGE are recovered with r = 1, K = 1, an identity classifier, and the specified adjacency update.Original DCNN can also be recovered with K > 1 after modifying the transition-matrix operation.
4 EXPERIMENTS
Experiments evaluate N-GCN and related models on citation and biological graphs, finding consistent gains over corresponding baselines and robustness to feature noise. Sensitivity analyses indicate that broader random-walk information contributes more than replication-based capacity increases, while deeper conventional models do not show the same benefit.
- Datasets and evaluation: Experiments cover Pubmed, Citeseer, Cora, and PPI, using citation-graph and biological-graph benchmarks with established data splits.Citation datasets use 20 training nodes per class, 500 validation nodes, and 1000 evaluation nodes; PPI uses 20 training, 2 validation, and 2 testing subgraphs.
- Node classification accuracy: N-GCN outperforms GCN and N-SAGE improves on SAGE for all datasets, with both proposed models achieving state-of-the-art results.Table 2 reports test performance from runs selected by highest validation accuracy; citation metrics are accuracy and PPI uses micro-averaged F1.
- Sensitivity analysis: Increasing random-walk length K and replication factor r improves performance, but larger K contributes more than larger r.Comparisons of K = 1, r > 1 against K > 1, r = 1 attribute the stronger result to random-walk information rather than increased capacity.
- Tolerance to feature noise: N-GCN and N-SAGE combine convolution and random walks, supporting performance across conditions with few or many training examples.The paper contrasts convolution-based methods that work well with few examples and unmodified random-walk methods that work well with more training data.
- Tolerance to feature noise: Under random feature removal, N-GCN, N-SAGE, and DCNN outperform convolutional methods including GCN and SAGE, with the performance gap widening as more features are removed.The authors suggest that nearby and distant neighbors can help recover removed features; experiments on Cora average 10 runs with matched seeds across models.
- Random-walk steps versus GCN depth: Unlike the proposed method, deeper GCN and SAGE models show no direct correspondence between depth and improved performance.The comparison uses deeper models to make their receptive fields comparable to those of the proposed models.
5 RELATED WORK
The related work situates N-GCN among graph convolution and random-walk approaches, contrasting its multi-scale GCN construction with polynomial, diffusion, and channel-based models.
- Graph convolution and polynomial methods: Defferrard et al. learn graph convolutions as K-degree Laplacian polynomials, whereas N-GCN uses powers of the normalized adjacency matrix.The K-th adjacency power represents random-walk transition probabilities, while the Laplacian is I − ˆA.
- Depth versus multi-scale structure: Deeper GCN and SAGE models do not consistently improve classification accuracy, unlike N-GCN and N-SAGE, which use shallower models across graph scales.The comparison suggests that widening the receptive field through multiple scales differs from simply increasing convolutional depth.
- Graph convolution and polynomial methods: N-GCN combines GCN outputs across adjacency powers, while related polynomial models learn linear combinations of transformed representations.The compared formulations differ in both the normalized operator and the function applied to each transformed input.
- Diffusion-based models: DCNN also retains powers of a transition matrix in separate channels before classification, but N-GCN applies adjacency propagation within every GCN layer.DCNN is a special case of N-GCN when its GCN module contains only one layer.
6 CONCLUSIONS AND FUTURE WORK
The paper presents N-GCN and N-SAGE as end-to-end meta-models that apply graph convolution models across random-walk scales. It reports learning information from near and distant neighbors and shifting weights toward higher powers under adversarial input perturbations.
- Conclusions and future work: N-GCN and N-SAGE run graph convolution models such as GCN and SAGE on multiple powers of the normalized adjacency matrix.Each instantiation operates at a different graph scale, and their outputs feed a classification sub-network.
- Conclusions and future work: The models are end-to-end trainable and directly learn information from both near and distant neighbors.
- Conclusions and future work: Under adversarial input perturbations, classification-subnetwork weights shift toward instances consuming higher adjacency powers.The paper identifies this weight redistribution as enabling the model to circumvent adversarial perturbations on the input.
- Future work: Future work extends the approach toward stochastic implementations and larger graph datasets.