We can generalize representing different properties of time-varying signals beyond the chain graph by considering arbitrary adjacency matrices and Laplacians.

$Q_h = \alpha_0I + \alpha_1A + \alpha_2A^2 + ... + \alpha_nA^N$

Therefore, when we multiply a matrix of node features **X** $\in \mathbb{R}^{|v|*m}$, then we get 

$Q_hX = \alpha_0IX + \alpha_1AX + \alpha_2A^2X + ... + \alpha_nA^NX$

where $Q_hX[u]$ at a given node $u$ corresponds to a vector $\in \mathbb{R}^m$ that contains information in the node's $N$-hop neighborhood.

Representing convolutional filters on general graphs

We can represent a convolution by a filter $h$ as matrix multiplication on the vector **f**:

$(f \star h)(t) = \sum_{\tau=0}^{N-1} f(\tau)h(\tau - t)$

= $Q_hf$

where $Q_h \in \mathbb{R}^{N*N}$  is a matrix representation of the convolution operator by a filter function $h$ and **f** = $\mathbf{[f(t_0),f(t_2),...,f(t_{N-1}]}^\top$ is a vector representation of the function $f$

Carleton College

The Laplacian $L_c$ for a chain graph can be represented by:

$L_c = I − A_c$

Laplacian for a Chain Graph

In order to generalize the notion of a convolution to graphs, we first must define
what we wish to generalize and provide some brief background details. We can define the general continuous convolution operation * shown below, let f and h be two functions.


 The General Continuous Convolution Operation

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

Representing convolutions with matrix multiplications

We can represent the difference operator by multiplication by the Laplacian:

$(L_cf)[t] = f[t] − f[(t + 1)_{mod N }]$

Representing difference on discrete time-varying signals

We can represent time shifts as multiplications by the adjacency matrix:

$(A_cf)[t]=f[(t+1)_{mod N}]$

Representing time shifts on discrete time-varying signals

One critical aspect of the convolution operation is that it can be computed by
an element-wise product of the Fourier transforms of the two functions:

Learn Before

Related

Learn After