Are Graph Neural Networks generalizations of Convolutional Neural Networks?

Question

In lecture 4 of this course, the instructor argues that GNNs are generalizations of CNNs, and that one can recover CNNs from GNNs.

He presents the following diagram (on the right) and mentions that it represents both a CNN and a GNN. In particular, he mentions that if we particularize the graph shift operator (i.e the matrix S, which in the case of a GNN could represent the adjacency matrix or the Laplacian) to represent a directed line graph, then we obtain a time convolutional filter (which I hadn't heard of before watching this, but now I know that all it does is shift the graph signal in the direction of the arrows at each time step).

That part I understand. What I don’t understand is how we can obtain 2D CNNs (the ones that we would for example apply to images) from GNNs. I was wondering if someone could explain.

EDIT: I found part of the answer here. However, it seems that the image convolution as defined is a bit different from what I’m used to. It seems like the convolution considers pixels only to the left and above of the “current” pixel whereas I’m used to convolutions considering both left, right, above, and below

Answer 1

Excuse my lack of rigor. Although I believe this could be rigorously proven for certain definitions of GNN, the term is still too loose for me to honestly claim one way or another on this. Hopefully the following thoughts will be helpful anyway.

I prefer the term Message Passing Networks as a generalization of many things people like to call GNN. In a generic Message Passing Network, every node has an associated vector. Each node's vector, $x_i$, is then updated as a function of itself and its neighbors. (I've left off time indices for readability...)

For instance: $$ x_i := Update(x_i, \sum_{x_j\in N(x_i)} Message(x_i,x_j, e_{ij})) $$

where $N(x_i)$ is the set of vectors associated with nodes neighboring $x_i$ and $Update$ and $Message$ are arbitrary parameterized functions.

In the case where $Message(x_i, x_j, e_{ij}) = e_{ij} x_j$ and $e_{ij}$ is a scalar, and $Update(a,b) = b$, this becomes the following:

$$ x_{i} := \sum_{x_j\in N(x_i)} e_{ij} x_j $$

This means that each node becomes a weighted sum of its neighbors and this is precisely convolution (given that you have a stride of 1 ... and that you have padding ... and that the graph is a grid where all upward edges are equal, all leftward edges are equal, all rightward edges are equal and all downward edges are equal.)