Normalised Adjacency Matrix

Build the symmetrically normalised adjacency matrix with self loops, the matrix that a graph convolutional network (GCN) multiplies by at every layer.

A is the adjacency matrix of an undirected graph: A[i, j] = 1 when there is an edge between nodes i and j. Two changes make it usable for message passing:

1. Add self loops, A_hat = A + I, so that a node keeps its own features when it averages over its neighbours.
2. Normalise by degree. High-degree nodes would otherwise sum many messages and blow up the scale. With D the diagonal matrix of row sums of A_hat:

A_norm = D^(-1/2) @ A_hat @ D^(-1/2)

So entry (i, j) is A_hat[i, j] / sqrt(d_i * d_j).

Function signature

def normalize_adjacency(A):

Example

Input

A = np.array([[0, 1, 0],
              [1, 0, 1],
              [0, 1, 0]])        # a path 0 - 1 - 2
normalize_adjacency(A)

Output

array([[0.5       , 0.40824829, 0.        ],
       [0.40824829, 0.33333333, 0.40824829],
       [0.        , 0.40824829, 0.5       ]])

Reasoning

With self loops, nodes 0 and 2 have degree 2 and node 1 has degree 3. The diagonal entries are 1 / 2 and 1 / 3. The edge between nodes 0 and 1 gets 1 / sqrt(2 * 3) = 0.408. Nodes 0 and 2 are not connected, so that entry stays 0.

Constraints and notes

• A is a square, symmetric 0/1 matrix with zeros on the diagonal.
• The result is symmetric.
• Do not build D^(-1/2) as a dense matrix if you can avoid it. Scaling rows and columns by a vector is enough.