Source-linked AI summary
Topology Adaptive Graph Convolutional Networks
Jian Du, Shanghang Zhang, Guanhang Wu, Jose M. F. Moura, Soummya Kar
TL;DR
Existing spectral graph CNNs approximate convolution to reduce computational complexity, while fixed-size CNN filters do not directly fit arbitrary graph topologies. TAGCN addresses this gap with topology-adaptive vertex-domain filters grounded in graph signal processing, and it reports better performance with lower computational complexity than existing methods.
Problem
Fixed-size CNN convolution does not directly apply to arbitrary graphs, while spectral graph CNNs require convolution approximations that can cause performance loss.
Method
TAGCN performs vertex-domain graph convolution using fixed-size learnable filters whose topologies adapt to local graph structure and whose operation is defined by adjacency-matrix polynomials.
Results
TAGCN consistently achieves superior performance across three graph-structured datasets compared with existing spectral and vertex-domain graph CNNs.
Takeaways & Limitations
TAGCN combines local feature extraction and weight sharing from classical CNNs with graph-signal-processing-consistent convolution, while supporting directed and undirected graphs.
Takeaways & Limitations
The analysis assumes a well-defined normalization of the adjacency matrix, and uses Jordan decomposition when the asymmetric adjacency matrix is rank deficient.
Abstract
from arXiv · showhide
Spectral graph convolutional neural networks (CNNs) require approximation to the convolution to alleviate the computational complexity, resulting in performance loss. This paper proposes the topology adaptive graph convolutional network (TAGCN), a novel graph convolutional network defined in the vertex domain. We provide a systematic way to design a set of fixed-size learnable filters to perform convolutions on graphs. The topologies of these filters are adaptive to the topology of the graph when they scan the graph to perform convolution. The TAGCN not only inherits the properties of convolutions in CNN for grid-structured data, but it is also consistent with convolution as defined in graph signal processing. Since no approximation to the convolution is needed, TAGCN exhibits better performance than existing spectral CNNs on a number of data sets and is also computationally simpler than other recent methods.
1 INTRODUCTION
TAGCN addresses the difficulty of applying fixed-size CNN filters to arbitrary graphs by defining topology-adaptive vertex-domain convolutions with learnable localized filters. It avoids convolutional approximation while retaining graph-signal-processing consistency and reports superior performance across three graph datasets.
- TAGCN applies fixed-size learnable filters whose local topologies adapt to the graph during convolution.The filters extract vertex features and correlations between vertices while operating on local receptive fields.
- TAGCN defines vertex-domain graph convolution as multiplication by polynomials of the graph adjacency matrix.This definition is consistent with convolution in graph signal processing and provides a theoretical foundation for the convolution step.
- TAGCN avoids spectral computation and approximation, using adjacency-matrix polynomials with maximum degree 2 rather than high-degree Laplacian polynomials.The cited comparison involves 25th-degree Chebyshev and 12th-degree Cayley polynomials.
- TAGCN uses general K-localized filters spanning size-1 through size-K receptive fields, replacing fixed square filters for grid-structured inputs.The design preserves local feature extraction and weight sharing associated with traditional CNNs.
- TAGCN’s multi-size filters avoid the information loss associated with deep single-size filtering and thereby improve representation capability and classification accuracy.Under a stated condition, single-size filters cause deep outputs to project along the adjacency matrix’s dominant-amplitude eigenvector.
- TAGCN consistently achieves superior performance on three commonly used graph-structured datasets compared with existing spectral and vertex-domain graph CNNs.
2 CONVOLUTION ON GRAPH
The paper defines graph convolution in the vertex domain using adjacency-based filters, extending local, weight-sharing convolution to arbitrary graph topologies. Its TAGCN filters adapt their local receptive fields to graph structure while retaining connections to traditional CNN and graph signal processing.
- Graph convolutional layer: Graph convolution is defined as a matrix-vector product using graph filters on vertex-indexed feature maps.The graph filter operates on the input features associated with all vertices, with a learnable bias and ReLU applied afterward.
- Graph convolutional layer: Graph filters are polynomials of the adjacency matrix, making the convolution consistent with graph signal processing.The graph shift is a local operation combining signal values from neighboring vertices, and polynomial adjacency filters extend conventional filtering to graph data.
- Filter design: TAGCN uses filters from size 1 through size K to extract features over increasingly localized graph receptive fields.The filter set comprises 1 × Cℓ, 2 × Cℓ, through K × Cℓ filters, with the resulting feature maps combined across filter sizes.
- Analysis of graph convolutional layers: Using only a size-k filter in deeper layers can project representations onto the adjacency eigenvector with the largest eigenvalue amplitude.The resulting linear approximation can cause information loss and lower classification accuracy; multiple filter sizes avoid this projection and improve representation capability.
- Filter design: Each graph-convolution neuron connects only to a local vertex-and-edge region whose topology adapts to the graph.The strength of path correlations is explicitly incorporated into the filter weights, and different graph vertices share filter parameters.
3 RELATION WITH OTHER EXISTING FORMULATIONS
TAGCN differs from spectral and simplified graph-convolution formulations by defining graph filters directly in the vertex domain, without spectral approximation. It also extends propagation through adaptive higher-order filters while avoiding the costly eigendecompositions used by spectral methods.
- Spectral-domain formulations: Spectral graph CNNs define convolution through Laplacian eigendecomposition and approximate spectrum-domain filtering with polynomial methods.ChebNet uses Chebyshev polynomials, while related methods use Cayley polynomials; symmetric adjacency is assumed for the Laplacian formulation.
- GCN and propagation methods: GCN simplifies the spectral formulation through a first-order approximation that produces a spectrum-independent propagation operator.Its derivation assumes K = 1, λmax = 2, and θ0 = θ1 = θ.
- TAGCN: TAGCN defines convolution as multiplication by polynomials of the graph adjacency matrix, directly implementing graph filters in the vertex domain.This definition follows graph signal processing and does not approximate the spectrum-domain convolution.
- Comparison with existing vertex-domain methods: GCN, ECC, and MoNet can be viewed as special cases of TAGCN because their propagation terms correspond to the k = 1 component of TAGCN filters.TAGCN additionally uses fixed-size filters adaptive to the input graph topology during convolution.
- Computational and representational differences: TAGCN avoids costly and numerically unstable eigendecompositions, while using farther-distance information without being a simple extension of GCN.The comparison also contrasts TAGCN's direct graph-filter construction with approximation-based spectral methods.
4 EXPERIMENTS
TAGCN is evaluated for semi-supervised vertex classification on three citation-graph datasets under standard comparison settings. It consistently outperforms recent graph CNN baselines, with filter-size ablations favoring K=2.
- Experimental settings: Experiments target semi-supervised vertex classification on the Cora, Citeseer, and Pubmed graph-structured datasets.Only a few vertices are labeled, and the remaining vertices are classified.
- Experimental settings: The citation graphs represent documents as vertices, citation links as undirected edges, and documents as sparse bag-of-words feature vectors.The adjacency matrix is constructed from document citation relationships and then normalized.
- Experimental settings: Results are averaged over 100 runs using the standard training, validation, and testing split followed in prior work.Five hundred labeled examples are used for hyperparameter optimization, with cross-entropy for classification evaluation.
- Quantitative evaluations: TAGCN outperforms DCNN, ChebNet, GCN, and MoNet on all three datasets by obvious margins in percentage classification accuracy.The comparison uses the same data statistics and closely follows standard experimental settings.
- Quantitative evaluations: K=2 filters consistently perform better than K=1, K=3, and K=4, while K=1 produces the worst classification accuracy.The ablation supports the analysis that a monomial filter provides a rough approximation.
- Quantitative evaluations: TAGCN retains a noticeable advantage over the A^2 comparison on Pubmed, Cora, and Citeseer.Reported accuracies for A^2 versus TAGCN are 79.1(80.8), 81.7(83.0), and 70.8(71.2), respectively.
5 CONCLUSIONS
TAGCN rearchitects CNNs for graph-structured data by adapting filters to graph topology while retaining local feature extraction and weight sharing. Its vertex-domain implementation is consistent with graph signal processing and offers a computationally efficient route to strong classification accuracy.
- Conclusions: TAGCN rearchitects the CNN architecture for graph-structured data with filters adaptive to graph topology during scanning.It retains local feature extraction and weight sharing from classical CNN convolutional layers.
- Conclusions: The vertex-domain TAGCN implementation is consistent with convolution in graph signal processing and unifies spectrum- and vertex-domain graph CNN perspectives.The paper connects its vertex-domain operation to the convolution theorem.
- Conclusions: These properties yield a noticeable classification-accuracy advantage on semi-supervised graph vertex-classification problems with low computational complexity.The conclusion states the performance and complexity consequence within this evaluation scope.
6 APPENDIX: SPECTRUM RESPONSE OF TAGCN
The appendix relates TAGCN's vertex-domain graph filtering to spectrum-domain multiplication through graph diagonalization. For a 1-D cyclic graph, this operation is consistent with classical signal-processing convolution.
- Spectrum response: When the adjacency matrix is diagonalizable, its eigenvalues and left and right eigenvectors define the graph spectral representation used in the derivation.The appendix assumes A = F^-1JF with J diagonal; the non-diagonalizable case uses generalized eigenvectors and block-diagonal J.
- Spectrum response: Graph filtering in the vertex domain becomes multiplication in the spectrum domain through the generalized convolution theorem.The graph Fourier transform maps vertex-domain features to the spectrum domain, where the graph filter acts multiplicatively.
- Spectrum response: For a 1-D cyclic graph, the graph convolution operator is consistent with convolution in classical signal processing.The cyclic topology is illustrated in Figure 3, and the appendix states this consistency explicitly.