Deep Learning: GNNs

Which of the following are NOT valid graph categories?

• Static (Known is another valid category)

• Fixed

• Varied

• Unknown

Consider a graph G, is there a fixed ordering of neighbours?

• No

• Yes

Answer explanation

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

Consider the Graph in the figure below.

What would be the diagonal elements of its degree matrix?

• 4-3-2-3-3-1

• 4-2-3-3-3-1

• 4-3-3-1-2-1

• 4-3-3-3-3-1

Answer explanation

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).

Choose the correct multiple answers.

Graph Laplacian is:

• Permutation Invariant

• Isotropic

• Shift invariant

• Anisotropic

Answer explanation

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.

In ChebNet under the assumptions of sparse Laplacians, the complexity of learnable parameters is:

• O(n)

• O(n^2)

• O(1)

• O(n log n)

Answer explanation

[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.

In which of the following cases, does a mean function aggregator NOT fail (colours represent different feature values):

• 1

• 2

• 3

• They all fail :(

Answer explanation

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

In which of the following cases, does a max function aggregator NOT fail (colours represent different feature values)

• 1

• 2

• 3

• They all fail :(

Answer explanation

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.