Topology adaptive graph convolutional networks

Jian Du, Shanghang Zhang, Guanhang Wu, José M. F. Moura, Soummya KararXiv 2017 · arXiv

Abstract

Topology Adaptive Graph Convolutional Networks (TAGCN) represent a significant advancement in graph-based deep learning. By defining convolution directly in the vertex domain through polynomials of the adjacency matrix, TAGCN bypasses the limitations of spectral approximations and the information loss inherent in first-order methods like GCN. The architecture utilizes a set of learnable, multi-scale filters that adapt to the local graph topology. This design prevents "over-smoothing"—the tendency of deep graph networks to collapse data onto the principal eigenvector—and achieves state-of-the-art accuracy on standard citation network benchmarks.

Introduction

Standard Convolutional Neural Networks (CNNs) excel at processing grid-structured data such as images. However, extending these techniques to graphs—where nodes have varying degrees and irregular local structures—presents a challenge. Previous research generally followed two paths: spectral methods, which operate in the Laplacian frequency domain but are computationally intensive, and vertex methods, which propagate features locally. Popular vertex methods like the Graph Convolutional Network (GCN) often rely on first-order approximations. The authors of TAGCN argue that as these models increase in depth, they suffer from "information collapse," where local details are blurred into coarse, global features.

Methodology

TAGCN unifies spectral and vertex approaches by defining filters as polynomials of the normalized adjacency matrix ($A$).

Multi-Scale Polynomial Filters

Unlike GCN, which uses a fixed 1-hop neighborhood, TAGCN employs filters of degree $K$, allowing the model to aggregate information from up to $K$ hops away. Inspired by "Inception" modules in computer vision, TAGCN applies multiple filters of varying sizes (from 1 to $K$ hops) simultaneously. The final output is a weighted combination of these diverse receptive fields.

Visualization of multi-scale filters in TAGCN, showing different receptive fields (red and purple) mapped to output features.

Vertex Domain Advantages

Because TAGCN is defined using the adjacency matrix rather than the Laplacian spectrum, it avoids expensive eigendecompositions. This formulation also enables the model to handle directed graphs naturally, a significant advantage over many spectral-based GCN variants.

Theoretical Insights

A key contribution of the paper is the analysis of why deep GCNs often fail. The authors provide a mathematical proof (Theorem 1) demonstrating that repeatedly applying a single-size first-order filter causes the network's output to project onto the graph's principal eigenvector. This "over-smoothing" removes the local variance necessary for classification.

A directed cycle graph used to analyze the convergence properties and information preservation of graph filters.

TAGCN’s multi-scale filters act as a buffer against this collapse by maintaining a variety of frequency responses, ensuring that local topological details are preserved even in deeper architectures.

Experimental Results

The model was evaluated on three benchmark citation networks: Cora, Citeseer, and Pubmed. In these tasks, nodes represent documents and edges represent citations, with the goal of semi-supervised node classification.

Dataset GCN GAT TAGCN
Pubmed 79.0% 79.0% 81.1%
Cora 81.5% 83.0% 83.3%
Citeseer 70.3% 72.5% 71.4%

TAGCN consistently outperformed or matched state-of-the-art models. The performance gain was most notable on Pubmed, the largest dataset. Ablation studies indicated that a filter size of $K=2$ typically offers the optimal trade-off between accuracy and computational cost.

Conclusion

TAGCN introduces a robust, topology-adaptive framework for graph convolutions. By leveraging multi-scale polynomial filters, it avoids the pitfalls of spectral approximations and the over-smoothing issues of first-order methods. While future work is needed to explore its performance on graph-level classification and massive dense graphs, TAGCN provides a powerful and computationally efficient tool for processing complex relational data.

Summary updated

BibTeX
@misc{du2017topology,
  author = {Jian Du and Shanghang Zhang and Guanhang Wu and José M. F. Moura and Soummya Kar},
  title = {{Topology adaptive graph convolutional networks}},
  year = {2017},
  eprint = {1710.10370},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.10370},
}
Figure