Graph Convolution with Low-rank Learnable Local Filters

Xiuyuan Cheng, Zichen Miao, Qiang Qiu

Introduction

Geometric variations such as rotation, scaling, and viewpoint changes pose significant challenges to visual understanding in deep learning. A common solution to handle these variations is to model intrinsic structures directly using landmarks—such as key points on a human face or joints in a skeleton.

Facial landmarks form an irregular, non-Euclidean grid that standard CNNs struggle to process.

However, these landmarks form irregular, coarse, and non-Euclidean grids. While standard Convolutional Neural Networks (CNNs) excel on regular Euclidean data like image pixels, they cannot natively handle these irregular structures. This paper introduces L3Net, a novel Graph Neural Network (GNN) architecture designed to bridge the gap between spectral and spatial graph convolutions, offering a more expressive and robust way to process such data.

The Limitations of Existing GNNs

To process landmark data, researchers typically turn to GNNs. Yet, existing approaches have notable flaws:

  1. Spectral GNNs (e.g., GCN, ChebNet): These rely on global graph Laplacians. As a result, they tend to be "too smooth" and lack the expressiveness needed to capture distinct, localized features.
  2. Spatial GNNs (e.g., GAT): These operate directly on local neighborhoods but often rely on heuristics, lacking a solid theoretical foundation regarding their stability and representational power.

The core challenge is designing a model expressive enough to learn specialized local patterns while remaining robust to "graph noise," such as missing or inaccurately detected landmarks.

Introducing L3Net: Methods and Architecture

To address these limitations, the authors propose L3Net, centered around a new type of graph convolution layer.

1. Low-Rank Local Filters

Instead of applying a single global filter across the entire graph, L3Net decomposes the linear mapping at each node into a sum of $K$ learnable local bases ($B_k$) multiplied by learnable coefficients ($a_k$).

L3Net decomposes the linear mapping into a low-rank sum of learnable local bases and coefficients.

By keeping $K$ small (low-rank), the model remains computationally efficient while allowing filters to specialize for different local neighborhoods. Mathematically, L3Net acts as a unifying "super-framework" that encompasses ChebNet, GAT, and EdgeNet as special cases.

2. Local Graph Regularization

To prevent overfitting on irregular grids, L3Net introduces a penalty based on the local Dirichlet graph Laplacian. This regularization encourages the learnable filters to respect the local geometry of the graph. It functions as a "stability knob": high regularization forces the model to behave like a stable spectral filter, while low regularization allows for high-capacity spatial learning.

3. Breaking Symmetry for Theoretical Expressiveness

A key insight of the paper is that spectral GNNs are limited by their symmetry; because they rely on the global Laplacian, they struggle with directional signals. L3Net breaks this symmetry locally, allowing it to learn directional context (e.g., "which way is up" on a graph). The authors prove that L3Net is strictly more expressive than spectral GNNs, demonstrating on a "ring graph" that L3Net can distinguish between "upwind" and "downwind" signals, whereas permutation-equivariant spectral GNNs cannot.

Key Results and Performance

L3Net was evaluated across diverse benchmarks, including synthetic tasks, 3D spherical meshes, Facial Expression Recognition (FER), and skeleton-based action recognition.

  • Unmatched Expressiveness: On the synthetic "upwind/downwind" classification task, L3Net achieved ~100% accuracy, while baselines like ChebNet and GCN were stuck at ~50% (equivalent to random guessing).
  • Facial Expression Recognition: On the CK+ dataset (using 15 facial landmarks), L3Net reached 95.37% accuracy, outperforming ChebNet (93.22%) and GAT (91.62%) with a comparable parameter count.
  • Action Recognition: On the NTU-RGB+D cross-view task (using body skeletons), L3Net achieved 91.52%, significantly outperforming the baseline ST-GCN (88.30%).
  • Robustness to Noise: In simulated experiments with 7x7 MNIST grids, the regularized L3Net proved significantly more resilient to Gaussian noise and missing nodes than its non-regularized counterparts.

Limitations and Future Directions

While highly effective, L3Net has a few limitations. Its computational complexity includes an $npK$ term (where $n$ is nodes and $p$ is patch size), which is efficient for landmark-scale graphs (dozens to hundreds of nodes) but may become a bottleneck for massive graphs with millions of nodes.

Additionally, the current analysis assumes a relatively stable graph topology across samples. Extending the framework to handle dynamically changing underlying graphs and incorporating edge-specific features (like the distance or angle between joints) represent promising avenues for future work.

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.,...
BibTeX
@inproceedings{cheng2021graph,
  author = {Xiuyuan Cheng and Zichen Miao and Qiang Qiu},
  title = {{Graph Convolution with Low-rank Learnable Local Filters}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=9xNLKXyDZ-},
}
Figure