Struggling to understand GCNNs (Graph Convolutional Neural Networks)

Question

Although I've worked with CNN's for over a year, I am struggling to understand how GCNNs work paper on their simplification. I've read several papers, and I find myself out of my depth when they talk about Chebyshev polynomials or Fourier spaces.

The descriptions talk about using an adjacency matrix as input, and perhaps my primary confusion is how I can supply such a matrix to a convolutional neural network (if that is what is in fact what is done). I can't just convolve over the matrix as if it were an image because spatial similarity in the matrix (i.e. rows/cols that are near to each other) doesn't signify actual closeness between nodes in the graph. The question is therefore, how does an adjacency matrix, fit into the framework of CNNs which uses the spatial filters, and the logistic operations (non-linear regressions) in the layered stack/graph.

As this GCNN is less mature than CNNs, which have more explanatory material, some further explanation material as to how these methods differ would be helpful. Are there simple situations in which the usage of GCNN can be used to derive results specific to this method/framework?

Answer 1

The name "Graph Convolutional Neural Network" is a bit misleading, as no "traditional" convolutions (like in the context of CNNs) take place at all. You are correct that it doesn't really make sense to perform convolutions on the adjacency matrix of a graph. The thing that GCNNs have in common with CNNs is that there is a concept of a "local neighbourhood" which is exploited.

In CNNs, this neighbourhood consists of the surrounding pixels of each pixel. A linear transformation (discrete convolution) is applied to the pixels in the neighbourhood, before being passed through a nonlinearity.

In GCNNs, however, the neighbourhood for each node is given by the set of other nodes that share edges with the node. The representations of each node are averaged with the representations of the nodes in their neighbourhoods before having a linear transformation applied and subsequent nonlinearity. The method for performing the local averaging can be done using some matrix arithmetical tricks with the adjacency matrix, which is perhaps what you got confused about.

In the simplified version, they remove the nonlinearity step which vastly simplifies the computation of the hidden representations and the linear transformation step.