GCN Normalized Adjacency Build

Problem

Build the propagation matrix used by graph convolutional networks: D~^-1/2 (A + I) D~^-1/2.

Add self-loops to the undirected graph, let D~ be the resulting degrees, and normalize each entry (A + I)[i][j] by 1 / sqrt(D~[i] * D~[j]). edges is a list of [u, v] pairs. Return the n by n matrix.

Hint

Self-loops make isolated nodes propagate their own features.

Test cases

case 1

in: [3,[[0,1],[1,2]]]

expected: [[0.5,0.4082482904638631,0],[0.4082482904638631,0.3333333333333333,0.4082482904638631],[0,0.4082482904638631,0.5]]

case 2

in: [2,[[0,1]]]

expected: [[0.5,0.5],[0.5,0.5]]

case 3

in: [1,[]]

expected: [[1]]

Starter codePython

import math
def gcn_normalized_adjacency(n, edges):
    # Your code here
    pass

3 test cases · run your code against them in the editor