Unitary Convolutions for Learning on Graphs and Groups

Lukas Fesser, Bobak T. Kiani, Melanie Weber

TL;DR

This paper introduces "unitary graph convolutions" as a novel approach to improve the stability and performance of Graph Neural Networks (GNNs). By enforcing unitarity in the convolution operations, the authors demonstrate a theoretical solution to the "over-smoothing" problem in deep GNNs and achieve competitive results on various benchmark datasets.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) have become a powerful tool for learning from graph-structured data, finding applications in fields like chemistry, drug discovery, and particle physics. However, a significant challenge with current GNN architectures, particularly as they become deeper, is their instability. This instability often manifests as "over-smoothing," where node representations converge too quickly, losing their distinctiveness and hindering the learning of long-range dependencies. While existing methods like skip connections and graph rewiring offer partial solutions, the authors seek a more principled architectural approach with theoretical guarantees.

Methods

The core contribution of this paper is the introduction of unitary graph convolutions. Instead of standard linear transformations in GNN layers, the authors propose replacing them with operations that preserve the norm of the data (isometry) and are invertible. This is achieved by leveraging concepts from group theory and linear algebra, specifically by parameterizing operations within the Lie algebra of unitary groups and applying the exponential map.

Two main variants are proposed:

  • Separable Unitary Convolution (UniConv): This approach adjusts standard message passing by treating linear transformations over nodes and features separately, enforcing unitarity.
  • Lie Orthogonal/Unitary Convolution (Lie UniConv): This method parameterizes operations directly in the Lie algebra, ensuring full unitarity.

The theoretical analysis shows that these unitary convolutions provably avoid over-smoothing and enhance stability, preventing gradients from vanishing or exploding.

Datasets

The paper evaluates its proposed methods on several datasets:

  • LRGB (Long Range Graph Benchmark): This includes the Peptides (function and structure classification), COCO, and PascalVOC datasets.
  • TU Datasets: ENZYMES, IMDB-BINARY, MUTAG, and PROTEINS.
  • Heterophilous Graph Datasets: Roman-empire, Amazon-ratings, Minesweeper, Tolokers, and Questions.
  • Toy Model: A ring graph of 100 nodes used to specifically test the learning of long-range dependencies.
  • Dihedral Group Dn: A task designed to learn distances between group elements.

Key Insights and Ideas

  • Unitarity as a Solution to Over-smoothing: The paper provides a strong theoretical argument and empirical evidence that enforcing unitarity in GNN layers directly combats over-smoothing by preserving the norm of node representations.
  • Enhanced Stability in Deep Networks: Unitary operations naturally lead to more stable training dynamics, allowing for deeper architectures without the typical gradient issues.
  • Principled Approach to Inductive Bias: By encoding symmetries through unitary transformations, the authors offer a more principled way to inject geometric inductive biases into GNNs.
  • Generalizability to Other Groups: The framework is extended beyond permutations (graphs) to general group convolutions, suggesting broader applicability.

Key Results

  • Competitive Performance: Unitary GCNs achieve competitive performance on LRGB and TU datasets, often outperforming standard GNNs and matching state-of-the-art models. For instance, on the TU datasets, Unitary GCN outperforms other message-passing GNNs by up to 18%.
  • Overcoming Over-smoothing: Experiments on a toy ring graph demonstrate that while conventional GNNs fail to learn long-range dependencies due to over-smoothing, unitary GCNs successfully learn the task, even with many layers.
  • Stability with Depth: Figure 4 shows that Unitary GCNs maintain performance with an increasing number of layers, unlike other message-passing architectures that collapse to trivial accuracy.
  • Robustness: The paper theoretically shows that unitary transformations provide robustness guarantees against adversarial perturbations.

Limitations and Future Work

  • Computational Overhead: Maintaining unitarity can introduce computational overhead, particularly when using approximations of the exponential map or diagonalizations in Fourier bases.
  • Complex Numbers and Initialization: Working with complex numbers and ensuring proper initialization for unitary layers requires different techniques.
  • Problem Dependency: Unitarity might not be appropriate for all tasks, especially those where the target function is not inherently invertible or isometric.
  • Future Directions: The authors suggest exploring extensions to more advanced graph methods (e.g., incorporating edge features), hybrid models combining unitary and non-unitary layers, and improving the efficiency of parameterizations. They also highlight the potential for unitary matrices to provide adversarial robustness guarantees, which warrants further practical investigation.

Summary updated

BibTeX
@inproceedings{fesser2024unitary,
  author = {Lukas Fesser and Bobak T. Kiani and Melanie Weber},
  title = {{Unitary Convolutions for Learning on Graphs and Groups}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=lG1VEQJvUH},
}
Figure