Deep Learning: GNNs

Unlike images where there are a constant number of neighbours, graphs have no ordering of neighbours

One just needs to sum the number of connections at each node and should be able to obtain the highlighted correspondence. Since the question specifies that the answer contains the diagonal elements, node 1 has degree 4 (we count the self-connection as 2 to its total degree).

Let G be a graph of N vertices. Its Laplacian matrix is the NxN matrix L(G) = D(G) - A(G), where A(G) is the familiar (0, 1) adjacency matrix, and D(G) is the diagonal matrix of vertex degrees. 

Permutation invariance: If one permutes the nodes in a graph, we obtain an equivalent permutation in the rows and columns of the laplacian. Therefore, for graphs G_1, and G_2, where g_2 is a permutation of G_1, we have L(G_1) = P^T L(G_2) P, where P is the permutation matrix. Since P is orthonormal, the spectrum of L(G_1) is the same as L(G_2).

Isotropic: The reasoning here is similar. In this case we have a rotation matrix R. The spectrum of the laplacian is preserved as before since R is an orthonormal matrix.

[1] The evaluation complexity is linear with respect to the filter’s support size and the total number of edges. 

It is reasonable to assume sparse graphs since it is the case in most realistic scenarios (thus assuming sparse Laplacians). Therefore, we have |E| << N^2 where |E| is the number of edges, leading to linear complexity with respect to the input size N.

[1] Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. "Convolutional neural networks on graphs with fast localized spectral filtering." Advances in neural information processing systems 29 (2016): 3844-3852.

The mean operator fails in the cases 1) and 2). This is due to the fact that we have the same number of coloured nodes in each graph which makes it hard to distinguish between the two graphs after the mean operation

A max operator fails in all the cases. Let’s take case 3) as an example, whether the green or red value is larger than the other, we won’t be able to distinguish between them.