3
$\begingroup$

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?

$\endgroup$
7
  • 2
    $\begingroup$ Why do you think that GNNs generalize CNNs? Where did you read this? $\endgroup$ – nbro Nov 28 '20 at 21:41
  • $\begingroup$ 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. $\endgroup$ – Kris Nov 29 '20 at 19:38
  • $\begingroup$ 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? $\endgroup$ – nbro Nov 29 '20 at 20:04
  • $\begingroup$ @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. $\endgroup$ – Swakshar Deb Dec 28 '20 at 19:56
  • $\begingroup$ @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. $\endgroup$ – nbro Dec 28 '20 at 20:05
-1
$\begingroup$

Spectral Graph Convolution

We use the 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, Klipf and Welling's GCN, 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.

$\endgroup$
4
  • $\begingroup$ 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 (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$. $\endgroup$ – nbro Dec 28 '20 at 23:01
  • $\begingroup$ 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. $\endgroup$ – nbro Dec 28 '20 at 23:16
  • $\begingroup$ 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). $\endgroup$ – nbro Dec 28 '20 at 23:18
  • $\begingroup$ Thanks, I will edit it tomorrow morning. $\endgroup$ – Swakshar Deb Dec 28 '20 at 23:21

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.