Source-linked AI summary
CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters
Ron Levie, Federico Monti, Xavier Bresson, Michael M. Bronstein
TL;DR
Graph convolutional networks need efficient spectral filters that can focus on relevant frequency bands without sacrificing spatial locality. CayleyNets use complex rational Cayley polynomials to provide such filters, and experiments report superior performance to other spectral CNNs across several graph-learning tasks.
Problem
Chebyshev filters struggle to specialize in narrow frequency bands while retaining localized computation, motivating filters that combine O(r) neighbor exchanges with narrow-band specialization.
Method
CayleyNets use complex rational Cayley filters that avoid explicit eigendecomposition, remain spatially localized, and specialize in narrow spectral bands.
Results
Experiments on MNIST, CORA, and MovieLens report superior performance over other spectral CNN methods across spectral image classification, community detection, vertex classification, and matrix completion.
Takeaways & Limitations
CayleyNets provide a flexible spectral graph CNN construction that preserves locality while focusing on frequency bands important to graph-learning tasks.
Takeaways & Limitations
Chebyshev filters can require high order for narrow bands and then produce unwanted non-local filters; early spectral CNNs also incur O(n^2) Fourier-transform costs.
Abstract
from arXiv · showhide
The rise of graph-structured data such as social networks, regulatory networks, citation graphs, and functional brain networks, in combination with resounding success of deep learning in various applications, has brought the interest in generalizing deep learning models to non-Euclidean domains. In this paper, we introduce a new spectral domain convolutional architecture for deep learning on graphs. The core ingredient of our model is a new class of parametric rational complex functions (Cayley polynomials) allowing to efficiently compute spectral filters on graphs that specialize on frequency bands of interest. Our model generates rich spectral filters that are localized in space, scales linearly with the size of the input data for sparsely-connected graphs, and can handle different constructions of Laplacian operators. Extensive experimental results show the superior performance of our approach, in comparison to other spectral domain convolutional architectures, on spectral image classification, community detection, vertex classification and matrix completion tasks.
1 Introduction
Graph learning extends deep neural networks to non-Euclidean data, where the absence of vector-space structure makes convolution difficult. CayleyNets address this setting with filters that retain localization and linear complexity while specializing in relevant frequency bands.
- Graph learning targets data such as social, regulatory, brain, and manifold-structured networks.
- Graph CNNs face the lack of vector-space structure and shift-invariance underlying classical convolution.
- Spectral graph CNNs use Laplacian eigenvectors as Fourier-like atoms and define learnable filters through spectral multipliers.
- Cayley polynomials provide filters with localization, linear complexity in the number of edges, and specialization to narrow frequency bands.
2 Spectral techniques for deep learning on graphs
Spectral graph convolutions represent filtering through the graph Laplacian spectrum, but early formulations incur costly transforms and poor transferability. Chebyshev filters improve efficiency and locality, yet struggle with narrow spectral bands, motivating filters that combine local computation with frequency specialization.
- A graph Laplacian admits an eigendecomposition whose eigenvectors act as Fourier atoms and whose eigenvalues represent frequencies.
- Spectral convolution applies learnable frequency-domain multipliers to graph signals and uses graph coarsening for pooling.
- Spectral convolutional layers can require O(n^2) Fourier-transform multiplications because general graphs lack FFT-like algorithms.
- Basis-dependent spectral coefficients prevent a spectral CNN learned on one graph from transferring to another graph.
- 2.3 ChebNet: Chebyshev filters avoid explicit eigendecomposition, use O(rn) operations on sparse graphs, and guarantee r-hop spatial localization.
- 2.3 ChebNet: Narrow-band Chebyshev filters require high order and consequently produce unwanted non-local filters, especially around clustered eigenvalues.
- 2.3 ChebNet: The resulting design requirement is a filter class combining O(r) neighbor exchanges with specialization in narrow frequency bands.
3 Cayley filters
Cayley filters use complex rational functions of a scaled Laplacian to represent flexible spectral responses, specialize in frequency bands, and remain spatially localized with efficient sparse-graph computation.
- Cayley polynomial construction: Cayley polynomials are real-valued spectral filters with one real coefficient, r complex coefficients, and a trainable spectral zoom parameter h.They apply rational functions of the Laplacian without explicit eigendecomposition.
- Analytic properties: Cayley filters can represent any spectral filter by interpolating its spectral values with a trigonometric polynomial.Their trigonometric representation is real-valued and conjugate-even.
- Analytic properties: Complex coefficients provide an overcomplete Fourier expansion on the lower half-circle, yielding more same-order spectral filters without increasing computational complexity.Real coefficients reduce the construction to cosine or sine polynomials, while complex coefficients combine both forms.
- Spectral zoom: The spectral zoom h maps different portions of the Laplacian spectrum into better-separated regions, enabling filters specialized to different frequency bands.Larger h improves spacing among lower frequencies, while smaller h improves spacing among higher frequencies.
- Numerical properties: The filter’s sequential linear-system recursion is stable because C(h∆) is unitary, whose condition number is 1.The recursion computes C^j(h∆)f for j = 1, . . . , r.
- Numerical properties: For sparse Laplacians, approximate Cayley filtering takes O(rKn) operations, while smaller h can also accelerate convergence under the stated assumptions.The approximation uses Jacobi iterations, and its convergence behavior is closer to the regular-graph case in most real-life situations.
- Localization: Although Cayley filters have whole-graph rational support, their responses decay exponentially around a vertex and therefore remain well localized.Theorem 4 gives exponential L2 decay for a Cayley filter of order r.
- Cayley vs Chebyshev: Cayley filters address narrow-band limitations of Chebyshev filters by zooming into relevant spectral bands before approximating them with trigonometric polynomials.This is especially useful when community information is concentrated among small Laplacian eigenvalues.
4 Results
Experiments across synthetic community detection, MNIST, CORA, and matrix completion evaluate CayleyNet against ChebNet and other graph CNNs. CayleyNet benefits from spectral zooming, often achieving strong accuracy with lower filter orders while approximate inversion preserves linear scaling.
- Community detection: CayleyNet significantly outperforms ChebNet on the synthetic 15-community task for smaller filter orders, with improvement as large as 80%.Learned filters exploit low-frequency bands containing community information.
- Complexity: Approximate inversion guarantees O(n) complexity, and one Jacobi iteration can outperform ChebNet for low-order filters on community detection.The complexity experiment varied graph size, filter order, and Jacobi iterations.
- MNIST: CayleyNet with 11 Jacobi iterations matches ChebNet's near-perfect MNIST accuracy using order r = 12 rather than r = 25.The comparison used two spectral convolutional layers with pooling and graph coarsening.
- Citation network: On standard CORA, the lighter CayleyNet outperforms DCNN, GCN, and MoNet, while GAT remains superior.Results average performance over 50 runs under the standard semi-supervised split.
- Citation network: On extended CORA, the best CayleyNets consistently outperform the best ChebNets with fewer parameters, and CayleyNet outperforms other spectral CNN methods.Complex-coefficient CayleyNet with order r has the same parameter count as ChebNet with order 2r.
- Recommender system: On matrix completion, the Chebyshev-order-8 sRGCNN outperforms all competing methods, while Cayley-polynomial order 4 with 15 Jacobi iterations requires 0.165 +/- 0.00332 sec at test time.The comparison uses equal-parameter sRGCNN variants.
5 Conclusion
The paper concludes that CayleyNet combines efficient, localized spectral filtering with narrow-band specialization. Across MNIST, CORA, and MovieLens, it reports strong performance and superiority over other spectral CNN methods.
- 5 Conclusion: CayleyNet uses complex rational filters that are spatially localized, represent smooth spectral transfer functions, and scale linearly with input dimension.Its key design property is specializing in narrow frequency bands with few filter parameters while preserving spatial locality.
- 5 Conclusion: Experiments on MNIST, CORA, and MovieLens show good performance against varied approaches and superior performance against other spectral CNN methods.
A Proof of Proposition 1
The proof analyzes Jacobi-based approximations to the Cayley-filter recursion. It bounds approximation behavior using the iteration count, graph-dependent convergence properties, and normalization choices.
- Jacobi approximation: The proof begins from the classical Jacobi approximation of Ax = b with zero initialization, where the error after k iterations is represented through J^k x.
- Jacobi approximation: The Cayley recursion approximates y_j = C(h∆)˜y_{j−1} by a finite-iteration approximation ˜y^(K).
- Error bounds: The convergence analysis uses the Cayley operator's unitary property together with norm bounds and the triangle inequality.
- Error bounds: The proof also treats general and unnormalized Laplacian settings through spectral-radius bounds and graph-regularity assumptions.For regular graphs, D = dI; the spectral radius of the Laplacian is bounded using degree information.
- Error bounds: For normalized Laplacians of regular graphs, the Jacobi iteration matrix has spectral radius κ = h/√(h^2+1), yielding bounds of the form e_j ≤ jκ^(K+1).The corresponding normalization factor is M_j = j.
B Proof of Theorem 4
The theorem proof establishes locality of the approximate Cayley filtering procedure by tracking how Jacobi iterations expand signal support across graph neighborhoods.
- B Proof of Theorem 4: Because each Jacobi iteration expands a vertex-supported signal by one hop, K iterations across an order-r filter remain supported within the r(K + 1)-hop neighborhood.The proof denotes this radius by l = r(K + 1).
C Computational Complexity
Figure 6 compares the computational complexity of CayleyNey and ChebNet for the community detection problem.
- Figure 6 compares the computational complexity of CayleyNey and ChebNet.The passage identifies the two architectures being compared.
- The comparison is conducted on a community detection problem.The passage specifies the evaluation task.
- The figure evaluates computational complexity rather than reporting a task-performance result.The passage frames Figure 6 specifically as a complexity comparison.
D Back propagation
The paper develops back propagation for Cayley filters with complex coefficients by realifying the coefficient space, enabling ordinary real-space differentiation and the usual chain rule.
- D Back propagation: Cayley-filter optimization minimizes the loss with respect to all coefficients of all filters in the network.The authors emphasize that the choice of inner product does not change the minimizing set.
- D Back propagation: Realification replaces the complex coefficient space with a real space using the real part of the complex inner product.This treats complex coefficients through their real and imaginary components.
- D Back propagation: Under the standard complex dot product, the loss is generally not differentiable, whereas realification makes the relevant functions differentiable in the real setting.The paper contrasts complex analyticity with richer real differentiability after identifying C with R2.
- D Back propagation: The coefficient space is represented as R2r because h and c0 are real while the remaining coefficients are complex.The resulting real vector space supports differentiation with respect to c and h.
- D Back propagation: Back propagation then follows the usual chain rule in the realificated space R2r.The gradient is taken with respect to the signal using the usual real dot product.
- D Back propagation: The derivative with respect to the spectral zoom h is obtained by differentiating gc,h(λ) and transferring the result to gc,h(∆) through functional calculus.The transfer uses that ∆ is a bounded normal operator.