Topic 20: Graph Neural Networks (GNNs) - Exercises¶

These exercises cover manual calculation, implementation, and conceptual understanding of GNNs.

In [1]:

import random

import matplotlib.pyplot as plt
import numpy as np

%load_ext autoreload
%autoreload 2

SEED = 42
random.seed(SEED)
rng = np.random.default_rng(SEED)

plt.rcParams["figure.dpi"] = 90

import random import matplotlib.pyplot as plt import numpy as np %load_ext autoreload %autoreload 2 SEED = 42 random.seed(SEED) rng = np.random.default_rng(SEED) plt.rcParams["figure.dpi"] = 90

Exercise 1: Hand Calculation of Normalized Laplacian¶

Consider a small 4-node graph with the following adjacency matrix:

A = [[0, 1, 1, 0],
     [1, 0, 1, 1],
     [1, 1, 0, 0],
     [0, 1, 0, 0]]

Task:

1. Compute the degree matrix $D$.
2. Compute the unnormalized Laplacian $L = D - A$.
3. Compute the symmetric normalized Laplacian $L_{sym} = I - D^{-1/2} A D^{-1/2}$.
4. Verify the smallest eigenvalue of $L$ is 0 using NumPy.

In [2]:

# Your code here

A = np.array([[0, 1, 1, 0],
              [1, 0, 1, 1],
              [1, 1, 0, 0],
              [0, 1, 0, 0]])

# 1. Compute D
# 2. Compute L
# 3. Compute L_sym
# 4. Check eigenvalues

# Your code here A = np.array([[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 0], [0, 1, 0, 0]]) # 1. Compute D # 2. Compute L # 3. Compute L_sym # 4. Check eigenvalues

Solution (Exercise 1)¶

In [3]:

D = np.diag(np.sum(A, axis=1))
print("D:\n", D)

L = D - A
print("L:\n", L)

D_inv_sqrt = np.diag(1.0 / np.sqrt(np.diag(D)))
L_sym = np.eye(4) - D_inv_sqrt @ A @ D_inv_sqrt
print("L_sym:\n", L_sym)

eigenvalues = np.linalg.eigvals(L)
print("Eigenvalues of L:", np.sort(eigenvalues))

# Deterministic checks against hand-computed values
assert np.array_equal(np.diag(D), [2, 3, 2, 1])
assert np.allclose(np.diag(L_sym), 1.0, atol=1e-12)
assert np.isclose(L_sym[0, 1], -1.0 / np.sqrt(2 * 3), atol=1e-12)
assert np.allclose(np.min(eigenvalues), 0, atol=1e-7)

D = np.diag(np.sum(A, axis=1)) print("D:\n", D) L = D - A print("L:\n", L) D_inv_sqrt = np.diag(1.0 / np.sqrt(np.diag(D))) L_sym = np.eye(4) - D_inv_sqrt @ A @ D_inv_sqrt print("L_sym:\n", L_sym) eigenvalues = np.linalg.eigvals(L) print("Eigenvalues of L:", np.sort(eigenvalues)) # Deterministic checks against hand-computed values assert np.array_equal(np.diag(D), [2, 3, 2, 1]) assert np.allclose(np.diag(L_sym), 1.0, atol=1e-12) assert np.isclose(L_sym[0, 1], -1.0 / np.sqrt(2 * 3), atol=1e-12) assert np.allclose(np.min(eigenvalues), 0, atol=1e-7)

D:
 [[2 0 0 0]
 [0 3 0 0]
 [0 0 2 0]
 [0 0 0 1]]
L:
 [[ 2 -1 -1  0]
 [-1  3 -1 -1]
 [-1 -1  2  0]
 [ 0 -1  0  1]]
L_sym:
 [[ 1.         -0.40824829 -0.5         0.        ]
 [-0.40824829  1.         -0.40824829 -0.57735027]
 [-0.5        -0.40824829  1.          0.        ]
 [ 0.         -0.57735027  0.          1.        ]]
Eigenvalues of L: [1.15057372e-16 1.00000000e+00 3.00000000e+00 4.00000000e+00]

Exercise 2: Implementing Message Passing¶

In the MPNN framework, the node update is defined as: $h_i^{(l+1)} = U_l(h_i^{(l)}, \sum_{j \in \mathcal{N}(i)} M_l(h_i^{(l)}, h_j^{(l)}))$

Task: Implement a simple message passing step where:

• Message function $M_l(h_i, h_j) = h_j$ (just pass neighbor's features).
• Aggregation is SUM.
• Update function $U_l(h_i, m_i) = h_i + m_i$.

Verify that this is equivalent to $H^{(l+1)} = (A + I) H^{(l)}$ in matrix form.

In [4]:

# Node features
H = np.array([[1.0, 2.0], 
              [3.0, 4.0], 
              [5.0, 6.0], 
              [7.0, 8.0]])

def simple_message_passing(H, A):
    # Your code here (implement node-by-node or vectorized)
    pass

# Node features H = np.array([[1.0, 2.0], [3.0, 4.0], [5.0, 6.0], [7.0, 8.0]]) def simple_message_passing(H, A): # Your code here (implement node-by-node or vectorized) pass

Solution (Exercise 2)¶

In [5]:

def simple_message_passing(H, A):
    N = H.shape[0]
    H_new = np.zeros_like(H)
    for i in range(N):
        # Aggregate messages from neighbors
        m_i = np.zeros(H.shape[1])
        for j in range(N):
            if A[i, j] == 1:
                m_i += H[j]
        # Update node
        H_new[i] = H[i] + m_i
    return H_new

H_mp = simple_message_passing(H, A)
H_matrix = (A + np.eye(4)) @ H

print("MPNN loop output:\n", H_mp)
print("Matrix output:\n", H_matrix)
assert np.allclose(H_mp, H_matrix)

# Deterministic check against hand-computed values, e.g. node 0 keeps [1, 2] and
# aggregates neighbors 1 and 2: [1, 2] + [3, 4] + [5, 6] = [9, 12]
H_expected = np.array([[9.0, 12.0],
                       [16.0, 20.0],
                       [9.0, 12.0],
                       [10.0, 12.0]])
assert np.allclose(H_mp, H_expected, atol=1e-12)

def simple_message_passing(H, A): N = H.shape[0] H_new = np.zeros_like(H) for i in range(N): # Aggregate messages from neighbors m_i = np.zeros(H.shape[1]) for j in range(N): if A[i, j] == 1: m_i += H[j] # Update node H_new[i] = H[i] + m_i return H_new H_mp = simple_message_passing(H, A) H_matrix = (A + np.eye(4)) @ H print("MPNN loop output:\n", H_mp) print("Matrix output:\n", H_matrix) assert np.allclose(H_mp, H_matrix) # Deterministic check against hand-computed values, e.g. node 0 keeps [1, 2] and # aggregates neighbors 1 and 2: [1, 2] + [3, 4] + [5, 6] = [9, 12] H_expected = np.array([[9.0, 12.0], [16.0, 20.0], [9.0, 12.0], [10.0, 12.0]]) assert np.allclose(H_mp, H_expected, atol=1e-12)

MPNN loop output:
 [[ 9. 12.]
 [16. 20.]
 [ 9. 12.]
 [10. 12.]]
Matrix output:
 [[ 9. 12.]
 [16. 20.]
 [ 9. 12.]
 [10. 12.]]

Exercise 3: Conceptual Analysis¶

Questions:

1. Why is the standard GCN considered a special case of the MPNN framework? What are its message and update functions?
2. Explain physically (or intuitively) why over-smoothing occurs when stacking many GCN layers.

Solution (Exercise 3)¶

Answer 1: GCN is an MPNN where:

• The message function is $M(h_i, h_j) = \frac{1}{\sqrt{d_i d_j}} W h_j$. It passes a transformed and degree-normalized version of the neighbor's feature.
• The aggregation is SUM.
• The update function is $U(h_i, m_i) = \sigma(m_i + \frac{1}{d_i} W h_i)$ (incorporating the self-loop via $\tilde{A}$).

Answer 2: The normalized adjacency matrix $\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ acts as a transition probability matrix (related to random walks on the graph). Multiplying node features by this matrix repeatedly is analogous to applying a low-pass filter or running a Markov chain until it reaches its stationary distribution. Because high-frequency signals (differences between neighbors) are smoothed out at each layer, after many layers, all nodes within a connected component converge to similar representations proportional to their degree, losing their discriminative features.