A Unified Deep Learning Formalism For Processing Graph Signals

Myriam Bontonou, Carlos Eduardo Rosar Kós Lassance, Jean-Charles Vialatte, Vincent GriponarXiv 2019 · arXiv

Introduction

Deep learning has achieved remarkable success in processing Euclidean data, such as images (2D grids) and audio (1D sequences), primarily through Convolutional Neural Networks (CNNs). However, a vast amount of real-world data is non-Euclidean, naturally represented as graphs. This includes social networks, sensor grids, and the functional connectivity of the human brain.

To address this, the field of Graph Signal Processing (GSP) has seen a proliferation of Graph Neural Network (GNN) architectures. While effective, this rapid development has led to a "notational fog," where each new model introduces its own mathematical formalism. This lack of a common language makes it difficult to compare models, identify underlying similarities, or understand the specific mechanisms driving performance. This paper introduces a unified mathematical framework that brings diverse GNN architectures under a single, universal equation.

The Unified Formalism: $g(\mathbf{X}) = \mathbf{\Theta S X}$

The authors propose that any linear layer in a graph-based network can be expressed through the interaction of three fundamental components:

  1. $\mathbf{X}$ (The Input): The signal supported on the graph, typically represented as features at each node.
  2. $\mathbf{\Theta}$ (The Parameters): A tensor containing the unique learnable weights of the model.
  3. $\mathbf{S}$ (The Allocation Tensor): The "secret sauce" of the framework. This tensor defines the parameter sharing scheme, dictating how weights are distributed across the graph's edges and vertices based on the underlying topology (such as adjacency or Laplacian matrices).

By separating the learnable weights ($\mathbf{\Theta}$) from the structural parameter-sharing scheme ($\mathbf{S}$), the framework provides a "Rosetta Stone" for the GNN landscape.

Mapping Architectures to the Framework

The power of this formalism lies in its ability to reconstruct established architectures simply by redefining the allocation tensor $\mathbf{S}$:

  • Fully Connected (FC) Layers: $\mathbf{S}$ is configured to allow every input to connect to every output with a unique weight, representing a lack of structural constraints.
  • Standard CNNs: $\mathbf{S}$ is structured as a Toeplitz matrix, enforcing the local, translation-invariant filters characteristic of Euclidean convolutions.
  • Spectral Filtering (ChebNet & GCN): $\mathbf{S}$ is derived from the graph Laplacian or normalized adjacency matrix. For instance, a Graph Convolutional Network (GCN) is revealed as a first-order approximation of ChebNet, utilizing a simplified version of the $\mathbf{S}$ tensor.
  • Graph Attention Networks (GAT): $\mathbf{S}$ becomes dynamic and data-dependent, containing attention coefficients calculated from the input features rather than relying solely on static topology.
  • Topology Adaptive GCN (TAGCN): The allocation tensor incorporates higher powers of the adjacency matrix, enabling the model to aggregate information from nodes multiple hops away.

Key Insights: Separation of Concerns

This unified approach yields several critical insights into the nature of deep learning on graphs:

1. Weight Sharing as Topology

The framework demonstrates that "parameter sharing"—the mechanism that grants CNNs their efficiency—is mathematically equivalent to encoding the graph's structure into the $\mathbf{S}$ tensor. This suggests that the primary innovation in most GNN research is not the learning process itself, but the design of the allocation tensor.

2. CNNs as a Subset of GNNs

The formalism elegantly shows that standard 1D or 2D convolutions are merely special cases of graph signals. In this view, a standard image is a graph with a grid topology, and the CNN's $\mathbf{S}$ tensor is specifically structured to enforce translation invariance across that grid.

3. Comparative Clarity

By placing disparate models like GCN, ChebNet, and GAT into the same equation, researchers can clearly see which "knobs" are being turned. It becomes obvious, for example, how TAGCN extends GCN by simply increasing the complexity of the $\mathbf{S}$ tensor to include multi-hop neighborhoods.

Limitations and Future Directions

While the framework provides significant theoretical clarity, it currently focuses on the linear portions of neural layers. While non-linearities (like ReLU) are acknowledged, they are not yet integrated into the core unified equation. Additionally, while the tensor $\mathbf{S}$ is mathematically elegant, the paper does not extensively address the computational or memory overhead required to represent $\mathbf{S}$ for massive, real-world graphs (though $\mathbf{S}$ is typically sparse in practice).

Looking forward, this formalism opens the door to "Neural Architecture Search" for graphs. By experimenting with novel structures for the allocation tensor $\mathbf{S}$, researchers may be able to discover entirely new types of graph layers optimized for specific topological properties.

Summary updated

BibTeX
@misc{bontonou2019unified,
  author = {Myriam Bontonou and Carlos Eduardo Rosar Kós Lassance and Jean-Charles Vialatte and Vincent Gripon},
  title = {{A Unified Deep Learning Formalism For Processing Graph Signals}},
  year = {2019},
  eprint = {1905.00496},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.00496},
}
Figure