Graph Neural Networks with Low-rank Learnable Local Filters

Xiuyuan Cheng, Zichen Miao, Qiang Qiu

Abstract

Geometric variations like rotation, scaling, and viewpoint changes pose a significant challenge to visual understanding. One common solution is to directly model certain intrinsic structures, e.g., using landmarks. However, it then becomes non-trivial to build effective deep models, especially when the underlying non-Euclidean grid is irregular and coarse. Recent deep models using graph convolutions provide an appropriate framework to handle such non-Euclidean data, but many of them, particularly those based on global graph Laplacians, lack expressiveness to capture local features required for representation of signals lying on the non-Euclidean grid. The current paper introduces a new type of graph convolution with learnable low-rank local filters, which is provably more expressive than previous spectral graph convolution methods. The model also provides a unified framework for both spectral and spatial graph convolutions. To improve model robustness, regularization by local graph Laplacians is introduced. The representation stability against input graph data perturbation is theoretically proved, making use of the graph filter locality and the local graph regularization. Experiments on spherical mesh data, real-world facial expression recognition/skeleton-based action recognition data, and data with simulated graph noise show the empirical advantage of the proposed model.

Introduction

Deep learning has revolutionized the processing of Euclidean data, such as images. However, many computer vision tasks involve non-Euclidean structures, such as facial landmarks or human skeletons, which are often irregular and coarse. Existing Graph Neural Networks (GNNs) face a trade-off: spectral methods (e.g., GCN, ChebNet) are theoretically grounded but often lack the expressiveness to capture fine-grained local features due to their reliance on global graph Laplacians. Conversely, spatial methods (e.g., GAT) offer flexibility but often lack rigorous theoretical stability guarantees.

The proposed L3Net (Low-rank Learnable Local Filters) aims to bridge this gap by providing a model as expressive as locally-connected networks but with a significantly smaller parameter footprint, while maintaining theoretical guarantees for stability against noise.

Methods: The L3Net Layer

The core of L3Net is a novel graph convolution layer that defines the filter $M$ using a low-rank decomposition: $$M(u', u; c', c) = \sum_{k=1}^{K} a_k(c', c) B_k(u', u)$$ Here, $B_k$ represents $K$ learnable basis filters supported on local neighborhoods (e.g., 1st or 2nd order neighbors), and $a_k$ are learnable coefficients that combine these bases across input ($c$) and output ($c'$) channels.

L3Net architecture overview showing the low-rank filter decomposition and target applications in facial and skeletal analysis.

Unified Framework and Regularization

L3Net serves as a generalization of several popular models; by varying $K$ and the neighborhood order, it can recover ChebNet, GCN, GAT, or EdgeNet. To handle "graph noise" (e.g., missing landmarks), the authors introduce Local Laplacian Regularization based on the local Dirichlet graph Laplacian. This penalty encourages filter smoothness relative to local geometry, enhancing robustness.

Experiments and Datasets

The model was evaluated on several benchmarks:

  • Spherical Data: Sphere MNIST and Sphere ModelNet-40.
  • Facial Expression Recognition (FER): Extended Cohn-Kanade (CK+) and FER13 datasets using 15 facial landmarks.
  • Action Recognition: NTU-RGB+D and Kinetics-Motion, treating skeletal joints as graph nodes.
Example of a facial landmark graph used for expression recognition.

Key Results

  • Superior Expressiveness: L3Net achieved 95.37% accuracy on the CK+ dataset, outperforming ChebNet (93.22%) and GAT (91.62%) with a comparable parameter count.
  • Action Recognition Performance: On the NTU-RGB+D "cross-view" task, L3Net reached 91.52%, surpassing the ST-GCN baseline (88.30%).
  • Robustness to Noise: In noisy MNIST experiments ($7 \times 7$ grids), L3Net with regularization maintained significantly higher accuracy under heavy Gaussian noise compared to GCN and MPNN.
  • Efficiency: Testing time remains practical; for instance, 13.02ms on CK+, which is nearly identical to ChebNet (12.56ms).

Conclusion

L3Net introduces a powerful and efficient approach to graph convolutions by breaking the global symmetry constraints of traditional spectral GNNs. By allowing for "neighborhood-specialized" filters through a low-rank decomposition, it captures local features essential for tasks like facial and skeletal analysis. The inclusion of local Laplacian regularization further ensures stability, making it a robust choice for real-world irregular data.

Summary updated

Abstract

Geometric variations like rotation, scaling, and viewpoint changes pose a significant challenge to visual understanding. One common solution is to directly model certain intrinsic structures, e.g., using landmarks. However, it then becomes non-trivial to build effective deep models, especially when the underlying non-Euclidean grid is irregular and coarse. Recent deep models using graph convolutions provide an appropriate framework to handle such non-Euclidean data, but many of them, particularly those based on global graph Laplacians, lack expressiveness to capture local features required for representation of signals lying on the non-Euclidean grid. The current paper introduces a new type of graph convolution with learnable low-rank local filters, which is provably more expressive than previous spectral graph convolution methods. The model also provides a unified framework for both spectral and spatial graph convolutions. To improve model robustness, regularization by local graph Laplacians is introduced. The representation stability against input graph data perturbation is theoretically proved, making use of the graph filter locality and the local graph regularization. Experiments on spherical mesh data, real-world facial expression recognition/skeleton-based action recognition data, and data with simulated graph noise show the empirical advantage of the proposed model.
BibTeX
@inproceedings{cheng2021graph,
  author = {Xiuyuan Cheng and Zichen Miao and Qiang Qiu},
  title = {{Graph Neural Networks with Low-rank Learnable Local Filters}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=9xNLKXyDZ-},
}
Figure