3
$\begingroup$

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).

enter image description here

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

$\endgroup$
2
  • 1
    $\begingroup$ Recently, we had a very similar question, but with no answer, so I will not close any of the two for now. $\endgroup$
    – nbro
    Dec 24 '20 at 12:11
  • $\begingroup$ @An IgnorantWanderer, you said that you don't understand how can we get 2D CNN form GNNs. GNN is more generalize from than CNN where CNN only work for grid like structure. If you take the inverse fourier transform of our spectral filter this is the same filter you use in CNN in spatial domain. Make sure the filter is smooth in spectral domain otherwise it will not gurante localization that we get in CNN. $\endgroup$ Dec 28 '20 at 19:50
2
$\begingroup$

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.)

$\endgroup$
1
  • $\begingroup$ It may be worth mentioning that these "message passing" algorithms or view already existed in the context of graphical models. Maybe you can comment on their similarities (e.g. what are the similarities between these GNNs algorithms and belief propagation?), in case you are familiar with the MP algorithms in those contexts. $\endgroup$
    – nbro
    Mar 10 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.