Answers.Body: <p>Actually, the given pipeline was used in the old days of Graph Neural Networks.</p>
  <p>Canonical paper on the subject is <a href="https://arxiv.org/abs/1606.09375" rel="nofollow noreferrer">Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering</a>.</p>
  <p>You start from arbitrary <strong>graph with adjacency</strong> matrix <span class="math-container">$A_{ij}$</span> (let us assume that graph is undirected), such that:
  <span class="math-container">$$
  A_{ij} = 
  \begin{cases}
  1 &amp; \text{if there and edge between vertices $i$ and $j$} \\
  0 &amp; \text{otherwise}
  \end{cases}
  $$</span></p>
  <p>Then one constructs <strong>graph Laplacian</strong>:
  <span class="math-container">$$
  L = D-A
  $$</span>
  <span class="math-container">$D$</span> is the degree matrix (number of edges entering the given vertex). There are also different normalizations in the literature, like <span class="math-container">$I - D^{-1/2} A D^{-1/2}$</span> is called <strong>normalized Laplacian</strong>.</p>
  <p>This matrix has several properties:</p>
  <ul>
  <li>It is symmetric</li>
  <li>Non-negative definite</li>
  </ul>
  <p>From the first statement it follows, that the matrix can be diagonalized due to the <a href="https://en.wikipedia.org/wiki/Spectral_theorem" rel="nofollow noreferrer">Spectral theorem</a>,</p>
  <p>Therefore, it makes sense to perform the eigendecomposition of this operator. And the eigenvectors form the <a href="https://en.wikipedia.org/wiki/Graph_Fourier_transform" rel="nofollow noreferrer">graph Fourier basis</a>.</p>
  <p>Note, that in the special case, when the graph is a regular square grid, graph Laplacian just the discrete Laplace operator:
  <span class="math-container">$$
  \begin{pmatrix}
  0 &amp; -1 &amp; 0 \\
  -1 &amp; 4 &amp; -1 \\
  0 &amp; -1 &amp; 0 \\
  \end{pmatrix}
  \qquad 
  (\text{for 2d case})
  $$</span>
  And the Fourier basis consists of plane waves:
  <span class="math-container">$$
  \sim e^{i (k_i i + k_j j)} 
  $$</span></p>
  <p>The next important fact is the <a href="https://en.wikipedia.org/wiki/Convolution_theorem" rel="nofollow noreferrer">Convolution theorem</a> that states that convolution of two signals can be done as inverse Fourier transform of the dot product of their Fourier transforms:
  <span class="math-container">$$
  f * g = \mathcal{F}^{-1} [\mathcal{F}[f] \cdot \mathcal{F}[g]]
  $$</span></p>
  <p>These operations correspond to steps <strong>3</strong> and <strong>4</strong> in the pipeline in the OP.</p>
  <p>I am not aware of the simple geometrical intuition in this setting. But in the following research, full eigendecomposition was truncated to Chebyshev polynomials, and then up to the first term in the decomposition, which gave rise to <a href="https://tkipf.github.io/graph-convolutional-networks/" rel="nofollow noreferrer">Graph Convolutional Networks</a> by T.Kipf.</p>
  <p>They allow for more intuitive and visual interpretation. Given adjacency matrix <span class="math-container">$A$</span>, input feature map on the graph <span class="math-container">$H^{(l)}$</span> one defines the output of the layer to be:
  <span class="math-container">$$
  f(H^{(l)}, A) = \sigma(\tilde{D}^{-1/2} A \tilde{D}^{-1/2} H^{(l)} W^{(l)})
  $$</span>
  <span class="math-container">$\tilde{D}$</span> is the graph Laplacian for adjacency matrix with self-loops (arrows <span class="math-container">$i \rightarrow i$</span>).  <span class="math-container">$W^{(l)}$</span> is the matrix of learnable parameters.</p>
  <p>In essence, one transforms the feature vectors <span class="math-container">$ H^{(l)}$</span> by a pointwise linear transformation, and aggregates the information from the neighborhood with some coefficients. Equivalently the function above can be rewritten as;</p>
  <p><span class="math-container">$$H_{i}^{l+1}=\eta\left(\frac{1}{\hat{d}_{i}} \sum_{j \in N_{i}} \hat{\boldsymbol{A}}_{i j}{W}^{l} H_{j}^{l}\right)$$</span></p>
  <p>From the formula above one can see, that graph convolution is the summation of the features in the neighborhood vertices which are transformed by the weight matrix <span class="math-container">${W}^{l}$</span> and division by the normalizing constant.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-28T20:58:55.990Z
Answers.Text: You may also explain or at least link to some other external resource that motivates your claim "it makes sense to perform the eigendecomposition of this operator" (i.e. the normalized Laplacian). In other words, why if a matrix is symmetric and non-negative semi-definitive, then we can find the eigendecomposition? What also does "graph Fourier basis" mean? Why do we care about this basis? And why does the eigenvectors of the normalised Laplacian form this basis?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-28T21:00:46.077Z
Answers.Text: You don't need to explain this completely in your answer, but it may be a good idea to link to an external resource that explains this for people not familiar with these concepts. Finally, to make this a better answer, I would also explain the relationship between your diagram and the last sentence. For people that are more or less familiar with GNNs, that last sentence makes sense, but it may not be clear how it is related to the diagram.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-29T05:06:55.107Z
Answers.Text: @nbro yeah, thanks. I've added links and made some fixes
Answers.UserDisplayName: spiridon_the_sun_rotator
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-09T15:02:37.903Z
Answers.Text: Thank you very much @spiridon_the_sun_rotator! This is very clear and aligns with what I have learned since making this post. Apologies for not responding sooner, but have just logged back on.
Answers.UserDisplayName: Rocky the Owl
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-28T19:47:40.010Z
Answers.LastActivityDate: 2021-11-29T05:06:23.013Z
Answers.LastEditDate: 2021-11-29T05:06:23.013Z
Answers.UserDisplayName: spiridon_the_sun_rotator
Body: <p>I was reading the following article on Towards Data Science (<a href="https://towardsdatascience.com/graph-convolutional-networks-for-geometric-deep-learning-1faf17dee008" rel="nofollow noreferrer">here</a>) and it says the following, regarding the calculation of convolutional layers:</p>
  <blockquote>
  <p>So the overall steps are:</p>
  <ol>
  <li>Transform the graph into the spectral domain using eigendecomposition</li>
  <li>Apply eigendecomposition to the specified kernel</li>
  <li>Multiply the spectral graph and spectral kernel (like vanilla convolutions)</li>
  <li>Return results in the original spatial domain (analogous to inverse GFT)</li>
  </ol>
  </blockquote>
  <p><strong>Question:</strong> How can we visualize the convolutional layer working for a graph neural network?</p>
  <p>For example, for a CNN we can imagine the following (source: Stanford CS231n YouTube lectures, Lecture 5: Convolutional Neural Networks (<a href="https://www.youtube.com/watch?v=bNb2fEVKeEo&amp;list=PLC1qU-LWwrF64f4QKQT-Vg5Wr4qEE1Zxk&amp;index=5" rel="nofollow noreferrer">here</a>)). What is the analogous image for a graph convolutional filter?</p>
  <p><a href="https://i.sstatic.net/9noug.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/9noug.jpg" alt="CNN filter sliding across image" /></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-18T14:15:11.730Z
Comments.Text: Note that there are several graph neural networks and, from what I remember when I was studying them, they can be quite different, so it may not be possible to give an explanation that applies to all GNNs. Moreover, it seems to me that now you changed the question to ask for a diagram that illustrates how the convolutional layer for some _specific_ GNN works. If that's the case, you may also want to change the title to reflect that.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-19T01:32:28.440Z
Comments.Text: Thanks @nbro, I'll make the updates in the morning. Do you have any links to resources you used when you were studying the topic?
Comments.UserDisplayName: Rocky the Owl
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-19T23:53:45.310Z
Comments.Text: I didn't study geometric deep learning or graph neural networks thoroughly. I had read a few papers and articles online, so my knowledge of the topic is not very solid, so I don't really have one resource that I would recommend. Back then (i.e. about 2-3 years ago), there weren't many good resources on this topic. Maybe [this answer](https://ai.stackexchange.com/q/22627/2444) is useful. [Don't forget to upvote the question and answer there if you find them useful ;)](https://ai.stackexchange.com/help/someone-answers). In any case, it seems to me you're already aware of this book.
Comments.UserDisplayName: nbro
Tags: <geometric-deep-learning><graph-neural-networks><convolutional-layers>
Title: How do convolutional layers of basic Graph Convolutional Networks work?
UserDisplayName: Rocky the Owl
ThreadText: # How do convolutional layers of basic Graph Convolutional Networks work?
  
  (Asked by: username_0 on 2021-09-08)
  
  I was reading the following article on Towards Data Science ([here](https://towardsdatascience.com/graph-convolutional-networks-for-geometric-deep-learning-1faf17dee008)) and it says the following, regarding the calculation of convolutional layers:
  
  > So the overall steps are:
  >
  > 1. Transform the graph into the spectral domain using eigendecomposition
  > 2. Apply eigendecomposition to the specified kernel
  > 3. Multiply the spectral graph and spectral kernel (like vanilla convolutions)
  > 4. Return results in the original spatial domain (analogous to inverse GFT)
  
  **Question:** How can we visualize the convolutional layer working for a graph neural network?
  
  For example, for a CNN we can imagine the following (source: Stanford CS231n YouTube lectures, Lecture 5: Convolutional Neural Networks ([here](https://www.youtube.com/watch?v=bNb2fEVKeEo&list=PLC1qU-LWwrF64f4QKQT-Vg5Wr4qEE1Zxk&index=5))). What is the analogous image for a graph convolutional filter?
  
  [![CNN filter sliding across image](https://i.sstatic.net/9noug.jpg)](https://i.sstatic.net/9noug.jpg)
  
  **Tags:** geometric-deep-learning, graph-neural-networks, convolutional-layers
  
  > **Comments:**
  > **username_1**: Note that there are several graph neural networks and, from what I remember when I was studying them, they can be quite different, so it may not be possible to give an explanation that applies to all GNNs. Moreover, it seems to me that now you changed the question to ask for a diagram that illustrates how the convolutional layer for some _specific_ GNN works. If that's the case, you may also want to change the title to reflect that.  
  > **username_0**: Thanks @username_1, I'll make the updates in the morning. Do you have any links to resources you used when you were studying the topic?  
  > **username_1**: I didn't study geometric deep learning or graph neural networks thoroughly. I had read a few papers and articles online, so my knowledge of the topic is not very solid, so I don't really have one resource that I would recommend. Back then (i.e. about 2-3 years ago), there weren't many good resources on this topic. Maybe [this answer](https://ai.stackexchange.com/q/22627/2444) is useful. [Don't forget to upvote the question and answer there if you find them useful ;)](https://ai.stackexchange.com/help/someone-answers). In any case, it seems to me you're already aware of this book.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-11-28. Score: 1 | Accepted answer
  
  Actually, the given pipeline was used in the old days of Graph Neural Networks.
  
  Canonical paper on the subject is [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://arxiv.org/abs/1606.09375).
  
  You start from arbitrary **graph with adjacency** matrix $A\_{ij}$ (let us assume that graph is undirected), such that:
  $$
  A\_{ij} =
  \begin{cases}
  1 & \text{if there and edge between vertices $i$ and $j$} \\
  0 & \text{otherwise}
  \end{cases}
  $$
  
  Then one constructs **graph Laplacian**:
  $$
  L = D-A
  $$
  $D$ is the degree matrix (number of edges entering the given vertex). There are also different normalizations in the literature, like $I - D^{-1/2} A D^{-1/2}$ is called **normalized Laplacian**.
  
  This matrix has several properties:
  
  * It is symmetric
  * Non-negative definite
  
  From the first statement it follows, that the matrix can be diagonalized due to the [Spectral theorem](https://en.wikipedia.org/wiki/Spectral_theorem),
  
  Therefore, it makes sense to perform the eigendecomposition of this operator. And the eigenvectors form the [graph Fourier basis](https://en.wikipedia.org/wiki/Graph_Fourier_transform).
  
  Note, that in the special case, when the graph is a regular square grid, graph Laplacian just the discrete Laplace operator:
  $$
  \begin{pmatrix}
  0 & -1 & 0 \\
  -1 & 4 & -1 \\
  0 & -1 & 0 \\
  \end{pmatrix}
  \qquad
  (\text{for 2d case})
  $$
  And the Fourier basis consists of plane waves:
  $$
  \sim e^{i (k\_i i + k\_j j)}
  $$
  
  The next important fact is the [Convolution theorem](https://en.wikipedia.org/wiki/Convolution_theorem) that states that convolution of two signals can be done as inverse Fourier transform of the dot product of their Fourier transforms:
  $$
  f \* g = \mathcal{F}^{-1} [\mathcal{F}[f] \cdot \mathcal{F}[g]]
  $$
  
  These operations correspond to steps **3** and **4** in the pipeline in the OP.
  
  I am not aware of the simple geometrical intuition in this setting. But in the following research, full eigendecomposition was truncated to Chebyshev polynomials, and then up to the first term in the decomposition, which gave rise to [Graph Convolutional Networks](https://tkipf.github.io/graph-convolutional-networks/) by T.Kipf.
  
  They allow for more intuitive and visual interpretation. Given adjacency matrix $A$, input feature map on the graph $H^{(l)}$ one defines the output of the layer to be:
  $$
  f(H^{(l)}, A) = \sigma(\tilde{D}^{-1/2} A \tilde{D}^{-1/2} H^{(l)} W^{(l)})
  $$
  $\tilde{D}$ is the graph Laplacian for adjacency matrix with self-loops (arrows $i \rightarrow i$). $W^{(l)}$ is the matrix of learnable parameters.
  
  In essence, one transforms the feature vectors $ H^{(l)}$ by a pointwise linear transformation, and aggregates the information from the neighborhood with some coefficients. Equivalently the function above can be rewritten as;
  
  $$H\_{i}^{l+1}=\eta\left(\frac{1}{\hat{d}\_{i}} \sum\_{j \in N\_{i}} \hat{\boldsymbol{A}}\_{i j}{W}^{l} H\_{j}^{l}\right)$$
  
  From the formula above one can see, that graph convolution is the summation of the features in the neighborhood vertices which are transformed by the weight matrix ${W}^{l}$ and division by the normalizing constant.
  
  > **Comments:**
  > **username_1**: You may also explain or at least link to some other external resource that motivates your claim "it makes sense to perform the eigendecomposition of this operator" (i.e. the normalized Laplacian). In other words, why if a matrix is symmetric and non-negative semi-definitive, then we can find the eigendecomposition? What also does "graph Fourier basis" mean? Why do we care about this basis? And why does the eigenvectors of the normalised Laplacian form this basis?  
  > **username_1**: You don't need to explain this completely in your answer, but it may be a good idea to link to an external resource that explains this for people not familiar with these concepts. Finally, to make this a better answer, I would also explain the relationship between your diagram and the last sentence. For people that are more or less familiar with GNNs, that last sentence makes sense, but it may not be clear how it is related to the diagram.  
  > **username_2**: @username_1 yeah, thanks. I've added links and made some fixes  
  > **username_0**: Thank you very much @username_2! This is very clear and aligns with what I have learned since making this post. Apologies for not responding sooner, but have just logged back on.  
  
  ---
  
  