Answers.Body: <p>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.</p>
  <p>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, <span class="math-container">$x_i$</span>, is then updated as a function of itself and its neighbors. (I've left off time indices for readability...)</p>
  <p>For instance:
  <span class="math-container">$$ x_i := Update(x_i, \sum_{x_j\in N(x_i)} Message(x_i,x_j, e_{ij})) $$</span></p>
  <p>where <span class="math-container">$N(x_i)$</span> is the set of vectors associated with nodes neighboring <span class="math-container">$x_i$</span> and <span class="math-container">$Update$</span> and <span class="math-container">$Message$</span> are arbitrary parameterized functions.</p>
  <p>In the case where <span class="math-container">$Message(x_i, x_j, e_{ij}) = e_{ij} x_j$</span> and <span class="math-container">$e_{ij}$</span> is a scalar, and <span class="math-container">$Update(a,b) = b$</span>, this becomes the following:</p>
  <p><span class="math-container">$$ x_{i} := \sum_{x_j\in N(x_i)} e_{ij} x_j $$</span></p>
  <p>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.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-10T09:27:51.300Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-09T04:40:53.397Z
Answers.LastActivityDate: 2021-03-09T23:00:56.127Z
Answers.LastEditDate: 2021-03-09T23:00:56.127Z
Answers.UserDisplayName: JacKeown
Body: <p>In lecture 4 of <a href="https://gnn.seas.upenn.edu/" rel="nofollow noreferrer">this course</a>, the instructor argues that GNNs are generalizations of CNNs, and that one can recover CNNs from GNNs.</p>
  <p>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).</p>
  <p><a href="https://i.sstatic.net/sGOlQ.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/sGOlQ.jpg" alt="enter image description here" /></a></p>
  <p>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.</p>
  <p>EDIT: I found part of the answer <a href="https://gnn.seas.upenn.edu/time-images-and-graphs/" rel="nofollow noreferrer">here</a>. 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</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-24T12:11:35.200Z
Comments.Text: Recently, we had [a very similar question](https://ai.stackexchange.com/q/24891/2444), but with no answer, so I will not close any of the two for now.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-28T19:50:42.880Z
Comments.Text: @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.
Comments.UserDisplayName: Swakshar Deb
Tags: <neural-networks><convolutional-neural-networks><comparison><graph-neural-networks>
Title: Are Graph Neural Networks generalizations of Convolutional Neural Networks?
UserDisplayName: An Ignorant Wanderer
ThreadText: # Are Graph Neural Networks generalizations of Convolutional Neural Networks?
  
  (Asked by: username_0 on 2020-12-24)
  
  In lecture 4 of [this course](https://gnn.seas.upenn.edu/), 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](https://i.sstatic.net/sGOlQ.jpg)](https://i.sstatic.net/sGOlQ.jpg)
  
  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](https://gnn.seas.upenn.edu/time-images-and-graphs/). 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
  
  **Tags:** neural-networks, convolutional-neural-networks, comparison, graph-neural-networks
  
  > **Comments:**
  > **username_1**: Recently, we had [a very similar question](https://ai.stackexchange.com/q/24891/2444), but with no answer, so I will not close any of the two for now.  
  > **username_2**: @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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2021-03-09. Score: 2
  
  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.)
  
  > **Comments:**
  > **username_1**: 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.  
  
  ---
  
  