We can generalize the representation of convolutional filters beyond the chain graph by using arbitrary adjacency matrices $$A$$ or Laplacians. We can define a generalized polynomial filter as:

$$Q_h = \alpha_0I + \alpha_1A + \alpha_2A^2 + \dots + \alpha_KA^K$$

When we multiply this filter by a matrix of node features $$\mathbf{X} \in \mathbb{R}^{|V| \times m}$$, we get:

$$Q_h\mathbf{X} = \alpha_0I\mathbf{X} + \alpha_1A\mathbf{X} + \alpha_2A^2\mathbf{X} + \dots + \alpha_KA^K\mathbf{X}$$

where $$(Q_h\mathbf{X})[u]$$ at a given node $$u$$ corresponds to a feature vector $$\in \mathbb{R}^m$$ that aggregates information from the node's $$K$$-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 \times N}$$ is a matrix representation of the convolution operator by a filter function $$h$$ and **f** = $$\mathbf{[f(t_0),f(t_1),...,f(t_{N-1})]}^\top$$ is a vector representation of the function $$f$$.

Carleton College

Google

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

The Laplacian matrix $$L_c$$ for a chain graph can be represented by the equation: $$L_c = I - A_c$$ where $$I$$ is the identity matrix and $$A_c$$ is the adjacency matrix of the chain graph.

Laplacian Matrix of a Chain Graph

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

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:

Fourier Transform of the Convolution Operation

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 }]$$

Learn Before

Related

Learn After