Answers.Body: <p>Yes, a CNN can be formalized as a specific kind of GNN where nodes are connected together in a 2D lattice structure and the outer edge is padded with zeros. Down-sampling techniques or pooling layers are an additional operation which remove edge nodes or low activation nodes. Convolutional layers act in the same manner as GNN weights by comparing each node with it's neighbors.</p>
  <p>Yes, GNNs are generalized architectures of CNNs. A CNN is derivable by treating the image as a lattice graph and augmenting pooling and/or down-sampling layers. <code>N</code> <code>w x w</code> convolutional kernels has a node with feature of length <code>N</code> interacting with a <code>w</code>-hop neighborhood. Any node of distance <code>w</code> is considered adjacent.</p>
  <p>I am an expert on convolutional networks and not graph neural networks. Maybe these two articles would also be helpful.
  <a href="https://towardsdatascience.com/understanding-graph-convolutional-networks-for-node-classification-a2bfdb7aba7b?gi=4c06cb6c8e30" rel="nofollow noreferrer">https://towardsdatascience.com/understanding-graph-convolutional-networks-for-node-classification-a2bfdb7aba7b?gi=4c06cb6c8e30</a></p>
  <p><a href="https://medium.com/@rmwkwok/gnn-notes-series-explain-graph-convolutional-networks-gcn-with-knowledge-in-cnn-b827be1c872b" rel="nofollow noreferrer">https://medium.com/@rmwkwok/gnn-notes-series-explain-graph-convolutional-networks-gcn-with-knowledge-in-cnn-b827be1c872b</a></p>
  <p>My goal in writing this was to provide a more novice accessible answer than the  others on this post.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-05T22:47:09.833Z
Answers.Text: Nice answer. Voted
Answers.UserDisplayName: Zollikofen4
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-06T18:19:30.983Z
Answers.LastActivityDate: 2023-07-07T17:01:53.297Z
Answers.LastEditDate: 2023-07-07T17:01:53.297Z
Answers.UserDisplayName: Ryan
Answers.Body: <h2>Spectral Graph Convolution</h2>
  <p>We use the <a href="https://en.wikipedia.org/wiki/Convolution_theorem" rel="nofollow noreferrer">Convolution Theorem</a> to define convolution for graphs. The Convolution Theorem states that the Fourier transform of the convolution of two functions is the pointwise product of their Fourier transforms:</p>
  <p><span class="math-container">$$\mathcal{F}(w*h) = \mathcal{F}(w) \odot \mathcal{F}(h) \tag{1}\label{1} $$</span>
  <span class="math-container">$$ w * h = \mathcal{F}^{-1}(\mathcal{F}(w)\odot\mathcal{F}(h))  \tag{2}\label{2}$$</span>
  Here <span class="math-container">$w$</span> is the filter in spatial domain(time domain) and <span class="math-container">$h$</span> is the signal in spatial domain(time domain). For images this signal <span class="math-container">$h$</span> is a <span class="math-container">$2D$</span> matrix and for other cases this <span class="math-container">$h$</span> can be a <span class="math-container">$1D$</span> signal.</p>
  <p>Assume we have <span class="math-container">$n$</span> number of node in a graph. In graph fourier transform the eigenvalues carry the notion of frequency. <span class="math-container">$\Lambda$</span> is the <span class="math-container">$ n \times n$</span> egenvalue matrix and it is a diagonal matrix. We can write equation 2 as:</p>
  <p><span class="math-container">$$w * h = \phi(\phi^{T}w \odot \phi^{T}h) = \phi\hat{w}(\Lambda)\phi^{T}h \tag{3}$$</span></p>
  <p>Here <span class="math-container">$\phi$</span> is the eigenvector matrix of graph Laplacian <span class="math-container">$\in R^{n \times n}$</span>,
  <span class="math-container">$\hat{w}(\Lambda)$</span> is the filter in spectral domain(frequency domain) <span class="math-container">$\in R^{n \times n}$</span> a diagonal matrix, <span class="math-container">$h$</span> is the <span class="math-container">$1D$</span> graph signal <span class="math-container">$\in R^{n}$</span> in spatial domain and w is the filter in spatial domain <span class="math-container">$\in R^{n}$</span>.</p>
  <h3>Vanilla Spectral GCN</h3>
  <p>We define the spatial convolutional layer such that given layer <span class="math-container">$h^{l}$</span> , the activation of the next layer is:</p>
  <p><span class="math-container">$$h^{l+1}=\sigma(w^l*h^l)  \tag{4}\label{4},$$</span></p>
  <p>where <span class="math-container">$\sigma$</span> represents a nonlinear activation and <span class="math-container">$w^l$</span> is a spatial filter and <span class="math-container">$h$</span> is the graph signal.</p>
  <p>We can perform the above equation in terms of spectral graph convolution operation as:</p>
  <p><span class="math-container">$$h^{l+1}=\sigma(\hat{w}^l*\hat{h}^l)  \tag{5}\label{5},$$</span></p>
  <p>where <span class="math-container">$\hat{w}$</span> is the same filter but in the spectral domain(frequency domain). In case of vanilla GCN this equation yeild to:</p>
  <p><span class="math-container">$$ h^{l+1} = \sigma(\phi\hat{w}^{l}(\Lambda)\phi^{T}h)  \tag{6}\label{6}$$</span></p>
  <p>Now, we will learn the <span class="math-container">$\hat{w}$</span> using backpropagation.</p>
  <p>This vanilla GCN has several limitations, like larger time complexity and this does not guarantee localization in the spatial domain that we get from CNN's filter.</p>
  <p>In next works, such as SplineGCNs, <a href="https://arxiv.org/pdf/1606.09375.pdf" rel="nofollow noreferrer">ChebNet</a>, <a href="https://arxiv.org/pdf/1609.02907.pdf" rel="nofollow noreferrer">Klipf and Welling's GCN</a>, and many other works address those issues, and try to solve them.</p>
  <p>Note that we can think of ChebNet and Klipf and Welling's GCN as a message-passing system, but, in the background, they are computing spectral convolution and also they use some standard assumption that's why we do not need any eigenvector and we implement them in the spatial domain, but still they are spectral convolution.</p>
  <p>There is also another branch in graph convolution called spatial graph convolution. I only talked about the spectral graph convolution.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T23:01:49.593Z
Answers.Text: Ok, there are some terms here that I think you should define (in order to be fully clear). First, what do you mean by "graph signal"? What do you mean by "spectral" or "spectral domain"? Maybe you could link to [this answer](https://dsp.stackexchange.com/q/56272/40095) (written by me, btw) if you think it's correct and useful. Another thing that is unclear is how do you get from equation 4 to equation 5, and what is $\Lambda$.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T23:16:15.353Z
Answers.Text: Finally, to clarify, although in the past I actually came across all these concepts and now I recall them, you're essentially saying that, by performing a multiplication between $w$ and $h$ (e.g. in the spectral domain), we are performing actually a convolution in the spatial domain, because of the Convolution Theorem. I suggest that you edit this answer, which seems good, to emphasize this after you have shown equation 5. Another thing that you could clarify is: what is the dimensionality of $\hat{w}$ and what is the $\phi$ and $\Lambda$ actually defined.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T23:18:12.123Z
Answers.Text: Another thing that you should try to clarify is how what you have said relates to the actual convolution in the CNN. I know this may seem obvious, but you could try to make 
  a mapping between the two, in terms of symbols involved. Maybe you could also point to a resource that talks about the convolution in the spatial domain. If you clarify all these points (I know they are many, but I think it would be nice to have a complete answer), I will surely upvote this answer, as it seems consistent with my knowledge (which I now recall, given that you mentioned the convolution theorem).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-05T22:48:02.067Z
Answers.Text: @SwaksharDeb I like your answer. I voted for you. You had a -1, now it's 0 :)
Answers.UserDisplayName: Zollikofen4
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T20:58:19.020Z
Answers.LastActivityDate: 2020-12-29T08:22:24.777Z
Answers.LastEditDate: 2020-12-29T08:22:24.777Z
Answers.UserDisplayName: Swakshar Deb
Body: <p>Convolution Neural Network (CNNs) operate over strict grid-like structures (<span class="math-container">$M \times N \times C$</span> images), whereas Graph Neural Networks (GNNs) can operate over all-flexible graphs, with an undefined number of neighbors and edges.</p>
  <p>On the face of it, GNNs appear to be neural architectures that can subsume CNNs. Are GNNs really generalized architectures that can operate arbitrary functions over arbitrary graph structures?</p>
  <p>An obvious follow-up - <strong>How can we derive a CNN out of a GNN</strong>?</p>
  <p>Since non-spectral GNNs are based on message-passing that employ <em>permutation-invariant</em> functions, is it possible to derive a CNN from a base-architecture of GNN?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-28T19:56:19.060Z
Comments.Text: @nbro, GNNs is the same as CNN except that CNN only works in euclidean space( I mean grid). GNN also extracts features via convolution operation on a graph just like CNN.
Comments.UserDisplayName: Swakshar Deb
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-28T20:05:34.783Z
Comments.Text: @SwaksharDeb I would like to see a _complete_ **proof** that shows that the "graph convolution" (if we really can call it like that) is a generalization of the convolution used in CNNs. If I remember correctly, in GNNs, there's no concept of shifting a kernel, but you only have an aggregation step for each node (or edge), as far as I recall, and you do this for every node (or edge). These message passing operations have some similarities with CNN's convolution, i.e. they may do some kind of dot product, but I don't think that's sufficient to say that they are equivalent.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-28T20:11:50.863Z
Comments.Text: It's been a while I had to deal with GNNs, even when I had written the comments above, so I don't really remember the details. Right now, I remember that there are different variants of these message passing algorithms used in GNNs. Some of them work also on edges and not just nodes. So, I see it as a non-trivial task to fully show some kind of equivalence between the operations and CNN's convolution, if possible, but I don't exclude the possibility. Anyway, this is what this and the other duplicate question are asking people to show. If you know the complete answer, feel free to write it.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-28T20:15:14.927Z
Comments.Text: @nbro, your aforementioned argument is correct I am not saying it is wrong, just think it like this, in case of spectral graph convolution we transform the filter from the time domain to frequency domain and perform the convolution on frequency domain. This is the same convolution operation except that we are doing it in frequency domain in case of spectral graph convolution
Comments.UserDisplayName: Swakshar Deb
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-28T21:41:42.160Z
Comments.Text: Why do you think that GNNs generalize CNNs? Where did you read this?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-29T19:38:41.570Z
Comments.Text: GNNs generalize in the sense that they can learn arbitrary functions over graphs of any size/shape, and that CNNs perform a more specific convolution operation over fixed dimension grid-like structures.
Comments.UserDisplayName: Kris
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-29T20:04:00.230Z
Comments.Text: As far as I remember, the "convolution" performed by GNNs is not really the same as the convolution/cross-correlation performed by CNNs. I am not even sure why they called it convolution: as you say, it's a messaging passing algorithm, and I am not sure what the relationship between this message passing algorithm and the convolution is. Can you provide a link to a reliable source (e.g. a research paper) that talks about "GNNs being able to learn arbitrary functions over graphs" and how this relates to CNNs and the convolution?
Comments.UserDisplayName: nbro
Tags: <deep-learning><convolutional-neural-networks><comparison><geometric-deep-learning><graph-neural-networks>
Title: How can we derive a Convolution Neural Network from a more generic Graph Neural Network?
UserDisplayName: Kris
ThreadText: # How can we derive a Convolution Neural Network from a more generic Graph Neural Network?
  
  (Asked by: username_0 on 2020-11-28)
  
  Convolution Neural Network (CNNs) operate over strict grid-like structures ($M \times N \times C$ images), whereas Graph Neural Networks (GNNs) can operate over all-flexible graphs, with an undefined number of neighbors and edges.
  
  On the face of it, GNNs appear to be neural architectures that can subsume CNNs. Are GNNs really generalized architectures that can operate arbitrary functions over arbitrary graph structures?
  
  An obvious follow-up - **How can we derive a CNN out of a GNN**?
  
  Since non-spectral GNNs are based on message-passing that employ *permutation-invariant* functions, is it possible to derive a CNN from a base-architecture of GNN?
  
  **Tags:** deep-learning, convolutional-neural-networks, comparison, geometric-deep-learning, graph-neural-networks
  > **Comments:**
  > **username_2**: Why do you think that GNNs generalize CNNs? Where did you read this?  
  > **username_0**: GNNs generalize in the sense that they can learn arbitrary functions over graphs of any size/shape, and that CNNs perform a more specific convolution operation over fixed dimension grid-like structures.  
  > **username_2**: As far as I remember, the "convolution" performed by GNNs is not really the same as the convolution/cross-correlation performed by CNNs. I am not even sure why they called it convolution: as you say, it's a messaging passing algorithm, and I am not sure what the relationship between this message passing algorithm and the convolution is. Can you provide a link to a reliable source (e.g. a research paper) that talks about "GNNs being able to learn arbitrary functions over graphs" and how this relates to CNNs and the convolution?  
  > **username_1**: @nbro, GNNs is the same as CNN except that CNN only works in euclidean space( I mean grid). GNN also extracts features via convolution operation on a graph just like CNN.  
  > **username_2**: @SwaksharDeb I would like to see a _complete_ **proof** that shows that the "graph convolution" (if we really can call it like that) is a generalization of the convolution used in CNNs. If I remember correctly, in GNNs, there's no concept of shifting a kernel, but you only have an aggregation step for each node (or edge), as far as I recall, and you do this for every node (or edge). These message passing operations have some similarities with CNN's convolution, i.e. they may do some kind of dot product, but I don't think that's sufficient to say that they are equivalent.  
  > **username_2**: It's been a while I had to deal with GNNs, even when I had written the comments above, so I don't really remember the details. Right now, I remember that there are different variants of these message passing algorithms used in GNNs. Some of them work also on edges and not just nodes. So, I see it as a non-trivial task to fully show some kind of equivalence between the operations and CNN's convolution, if possible, but I don't exclude the possibility. Anyway, this is what this and the other duplicate question are asking people to show. If you know the complete answer, feel free to write it.  
  > **username_1**: @nbro, your aforementioned argument is correct I am not saying it is wrong, just think it like this, in case of spectral graph convolution we transform the filter from the time domain to frequency domain and perform the convolution on frequency domain. This is the same convolution operation except that we are doing it in frequency domain in case of spectral graph convolution  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2023-07-06. Score: 1
  
  Yes, a CNN can be formalized as a specific kind of GNN where nodes are connected together in a 2D lattice structure and the outer edge is padded with zeros. Down-sampling techniques or pooling layers are an additional operation which remove edge nodes or low activation nodes. Convolutional layers act in the same manner as GNN weights by comparing each node with it's neighbors.
  
  Yes, GNNs are generalized architectures of CNNs. A CNN is derivable by treating the image as a lattice graph and augmenting pooling and/or down-sampling layers. `N` `w x w` convolutional kernels has a node with feature of length `N` interacting with a `w`-hop neighborhood. Any node of distance `w` is considered adjacent.
  
  I am an expert on convolutional networks and not graph neural networks. Maybe these two articles would also be helpful.
  <https://towardsdatascience.com/understanding-graph-convolutional-networks-for-node-classification-a2bfdb7aba7b?gi=4c06cb6c8e30>
  
  <https://medium.com/@rmwkwok/gnn-notes-series-explain-graph-convolutional-networks-gcn-with-knowledge-in-cnn-b827be1c872b>
  
  My goal in writing this was to provide a more novice accessible answer than the others on this post.
  
  > **Comments:**
  > **username_4**: Nice answer. Voted  
  
  ---
  
  ### Answer by username_1 on 2020-12-28. Score: 0
  
  ## Spectral Graph Convolution
  
  We use the [Convolution Theorem](https://en.wikipedia.org/wiki/Convolution_theorem) to define convolution for graphs. The Convolution Theorem states that the Fourier transform of the convolution of two functions is the pointwise product of their Fourier transforms:
  
  $$\mathcal{F}(w\*h) = \mathcal{F}(w) \odot \mathcal{F}(h) \tag{1}\label{1} $$
  $$ w \* h = \mathcal{F}^{-1}(\mathcal{F}(w)\odot\mathcal{F}(h)) \tag{2}\label{2}$$
  Here $w$ is the filter in spatial domain(time domain) and $h$ is the signal in spatial domain(time domain). For images this signal $h$ is a $2D$ matrix and for other cases this $h$ can be a $1D$ signal.
  
  Assume we have $n$ number of node in a graph. In graph fourier transform the eigenvalues carry the notion of frequency. $\Lambda$ is the $ n \times n$ egenvalue matrix and it is a diagonal matrix. We can write equation 2 as:
  
  $$w \* h = \phi(\phi^{T}w \odot \phi^{T}h) = \phi\hat{w}(\Lambda)\phi^{T}h \tag{3}$$
  
  Here $\phi$ is the eigenvector matrix of graph Laplacian $\in R^{n \times n}$,
  $\hat{w}(\Lambda)$ is the filter in spectral domain(frequency domain) $\in R^{n \times n}$ a diagonal matrix, $h$ is the $1D$ graph signal $\in R^{n}$ in spatial domain and w is the filter in spatial domain $\in R^{n}$.
  
  ### Vanilla Spectral GCN
  
  We define the spatial convolutional layer such that given layer $h^{l}$ , the activation of the next layer is:
  
  $$h^{l+1}=\sigma(w^l\*h^l) \tag{4}\label{4},$$
  
  where $\sigma$ represents a nonlinear activation and $w^l$ is a spatial filter and $h$ is the graph signal.
  
  We can perform the above equation in terms of spectral graph convolution operation as:
  
  $$h^{l+1}=\sigma(\hat{w}^l\*\hat{h}^l) \tag{5}\label{5},$$
  
  where $\hat{w}$ is the same filter but in the spectral domain(frequency domain). In case of vanilla GCN this equation yeild to:
  
  $$ h^{l+1} = \sigma(\phi\hat{w}^{l}(\Lambda)\phi^{T}h) \tag{6}\label{6}$$
  
  Now, we will learn the $\hat{w}$ using backpropagation.
  
  This vanilla GCN has several limitations, like larger time complexity and this does not guarantee localization in the spatial domain that we get from CNN's filter.
  
  In next works, such as SplineGCNs, [ChebNet](https://arxiv.org/pdf/1606.09375.pdf), [Klipf and Welling's GCN](https://arxiv.org/pdf/1609.02907.pdf), and many other works address those issues, and try to solve them.
  
  Note that we can think of ChebNet and Klipf and Welling's GCN as a message-passing system, but, in the background, they are computing spectral convolution and also they use some standard assumption that's why we do not need any eigenvector and we implement them in the spatial domain, but still they are spectral convolution.
  
  There is also another branch in graph convolution called spatial graph convolution. I only talked about the spectral graph convolution.
  
  > **Comments:**
  > **username_2**: Ok, there are some terms here that I think you should define (in order to be fully clear). First, what do you mean by "graph signal"? What do you mean by "spectral" or "spectral domain"? Maybe you could link to [this answer](https://dsp.stackexchange.com/q/56272/40095) (written by me, btw) if you think it's correct and useful. Another thing that is unclear is how do you get from equation 4 to equation 5, and what is $\Lambda$.  
  > **username_2**: Finally, to clarify, although in the past I actually came across all these concepts and now I recall them, you're essentially saying that, by performing a multiplication between $w$ and $h$ (e.g. in the spectral domain), we are performing actually a convolution in the spatial domain, because of the Convolution Theorem. I suggest that you edit this answer, which seems good, to emphasize this after you have shown equation 5. Another thing that you could clarify is: what is the dimensionality of $\hat{w}$ and what is the $\phi$ and $\Lambda$ actually defined.  
  > **username_2**: Another thing that you should try to clarify is how what you have said relates to the actual convolution in the CNN. I know this may seem obvious, but you could try to make  a mapping between the two, in terms of symbols involved. Maybe you could also point to a resource that talks about the convolution in the spatial domain. If you clarify all these points (I know they are many, but I think it would be nice to have a complete answer), I will surely upvote this answer, as it seems consistent with my knowledge (which I now recall, given that you mentioned the convolution theorem).  
  > **username_4**: @SwaksharDeb I like your answer. I voted for you. You had a -1, now it's 0 :)  
  
  ---
  
  