In [1]:
import matplotlib.pyplot as plt
import networkx as nx  
import numpy as np
In [2]:
G=nx.Graph()
G.add_nodes_from(['John','Mary','Sara','Helen','Tim','Jim','John'])
G.add_edges_from([('Mary','Sara'),('Sara','Helen'),('Helen','Jim'),('Helen','Tim'),
                  ('Jim','Tim'),('Jim','John'),('Tim','John'),
                  ('Mary','Maria'),('Mike','Mel'),('Mel','Mary'),
                  ('Mike','Mary'),('Maria','Mel'),('Mike','Maria'),('Mel','Maya'),
])
nx.draw(G,node_color='lightblue',node_size=1000,with_labels=True)   
plt.show()
In [3]:
from networkx import to_numpy_matrix
A = to_numpy_matrix(G)
I = np.eye(G.number_of_nodes())
#Add Self-Loops
A_hat = A + I
D_hat = np.array(np.sum(A_hat, axis=0))[0]
D_hat_srt=np.power(D_hat,-1/2)
D_hat = np.matrix(np.diag(D_hat))
D_hat_srt = np.matrix(np.diag(D_hat_srt))
print(D_hat_srt) #should be a diagonal matrix with d[i,i]=1/sqrt(degree_i) [mind the self-loops]
[[0.57735027 0.         0.         0.         0.         0.
  0.         0.         0.         0.        ]
 [0.         0.4472136  0.         0.         0.         0.
  0.         0.         0.         0.        ]
 [0.         0.         0.57735027 0.         0.         0.
  0.         0.         0.         0.        ]
 [0.         0.         0.         0.5        0.         0.
  0.         0.         0.         0.        ]
 [0.         0.         0.         0.         0.5        0.
  0.         0.         0.         0.        ]
 [0.         0.         0.         0.         0.         0.5
  0.         0.         0.         0.        ]
 [0.         0.         0.         0.         0.         0.
  0.5        0.         0.         0.        ]
 [0.         0.         0.         0.         0.         0.
  0.         0.5        0.         0.        ]
 [0.         0.         0.         0.         0.         0.
  0.         0.         0.4472136  0.        ]
 [0.         0.         0.         0.         0.         0.
  0.         0.         0.         0.70710678]]
In [4]:
print("Node list: ",G.nodes())
print("Original adjacency matrix:\n",A)
print("Modified adjacency matrix with self loops:\n",A_hat)
Node list:  ['John', 'Mary', 'Sara', 'Helen', 'Tim', 'Jim', 'Maria', 'Mike', 'Mel', 'Maya']
Original adjacency matrix:
 [[0. 0. 0. 0. 1. 1. 0. 0. 0. 0.]
 [0. 0. 1. 0. 0. 0. 1. 1. 1. 0.]
 [0. 1. 0. 1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 0. 1. 1. 0. 0. 0. 0.]
 [1. 0. 0. 1. 0. 1. 0. 0. 0. 0.]
 [1. 0. 0. 1. 1. 0. 0. 0. 0. 0.]
 [0. 1. 0. 0. 0. 0. 0. 1. 1. 0.]
 [0. 1. 0. 0. 0. 0. 1. 0. 1. 0.]
 [0. 1. 0. 0. 0. 0. 1. 1. 0. 1.]
 [0. 0. 0. 0. 0. 0. 0. 0. 1. 0.]]
Modified adjacency matrix with self loops:
 [[1. 0. 0. 0. 1. 1. 0. 0. 0. 0.]
 [0. 1. 1. 0. 0. 0. 1. 1. 1. 0.]
 [0. 1. 1. 1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 1. 1. 1. 0. 0. 0. 0.]
 [1. 0. 0. 1. 1. 1. 0. 0. 0. 0.]
 [1. 0. 0. 1. 1. 1. 0. 0. 0. 0.]
 [0. 1. 0. 0. 0. 0. 1. 1. 1. 0.]
 [0. 1. 0. 0. 0. 0. 1. 1. 1. 0.]
 [0. 1. 0. 0. 0. 0. 1. 1. 1. 1.]
 [0. 0. 0. 0. 0. 0. 0. 0. 1. 1.]]
In [5]:
#PLAY WITH TWO FEATURES (PAO, AEK)
#John, Tim = PAO
#Mel, Maya  = AEK
X=np.matrix([
    [1,0],
    [0,0], 
    [0,0],
    [0,0],
    [1,0],
    [0,0], 
    [0,0],
    [0,0],
    [0,1], 
    [0,1]]
)
print(X)
[[1 0]
 [0 0]
 [0 0]
 [0 0]
 [1 0]
 [0 0]
 [0 0]
 [0 0]
 [0 1]
 [0 1]]
In [6]:
colors=["gray" for i in range(X.shape[0])]
colors=['green' if X[i,0]>X[i,1] else colors[i] for i in range(X.shape[0])]
colors=['yellow' if X[i,0]<X[i,1] else colors[i] for i in range(X.shape[0])]
#nx.draw(G,node_color=colors,node_size=1000,with_labels=True)   
#plt.show()

pos = nx.spring_layout(G)
nx.draw_networkx(G,node_color=colors,pos=pos,node_size=1000,with_labels=True)
In [7]:
#try one iteration
AX=A*X

print("A*X=\n",AX)
colors=["gray" for i in range(AX.shape[0])]
colors=['green' if AX[i,0]>AX[i,1] else colors[i] for i in range(AX.shape[0])]
colors=['yellow' if AX[i,0]<AX[i,1] else colors[i] for i in range(AX.shape[0])]

nx.draw_networkx(G,node_color=colors,pos=pos,node_size=1000,with_labels=True)
plt.show()
A*X=
 [[1. 0.]
 [0. 1.]
 [0. 0.]
 [1. 0.]
 [1. 0.]
 [2. 0.]
 [0. 1.]
 [0. 1.]
 [0. 1.]
 [0. 1.]]
In [8]:
#NOW LET'S TRY A GCN

NUM_NODES=G.number_of_nodes()
np.random.seed(125) #this seems to work

NUM_NODES_HIDDEN_LAYER = 5 
NUM_OUTPUT_FEATURES = 2 #just for fun

#For the nodes, assume no known features since we want to learn from the topology, not from made-up features in this example
#Thus, we use the identity matrix for input, resulting in passing the random weights of the input layer to the activation function
INPUT = I

#Initialize random weights on all three layers
W_1 = np.random.normal(
    loc=0, scale=1, size=(INPUT.shape[1], NUM_NODES_HIDDEN_LAYER))
W_2 = np.random.normal(
    loc=0,scale=1, size=(W_1.shape[1], NUM_NODES_HIDDEN_LAYER))
W_3 = np.random.normal(
    loc=0,scale=1, size=(W_2.shape[1], NUM_OUTPUT_FEATURES))

def ReLU(X):
   return np.maximum(0,X)

def gcn_layer(A_hat, D_hat_srt, X, W):
    return ReLU(D_hat_srt * A_hat * D_hat_srt * X * W)


H_1 = gcn_layer(A_hat, D_hat_srt, INPUT, W_1)
H_2 = gcn_layer(A_hat, D_hat_srt, H_1, W_2)
H_3 = gcn_layer(A_hat, D_hat_srt, H_2, W_3)

output = H_3

print(output)
[[4.15832628e+00 2.98931141e-01]
 [2.60366701e+00 7.21513265e-02]
 [3.88216170e+00 2.18718666e-01]
 [5.18247914e+00 3.53681940e-01]
 [4.98100596e+00 3.57721344e-01]
 [4.98100596e+00 3.57721344e-01]
 [1.58147959e+00 4.33567972e-03]
 [1.58147959e+00 4.33567972e-03]
 [1.53638104e+00 9.15061537e-03]
 [5.66658813e-01 4.46915266e-03]]
In [9]:
figure = plt.figure(figsize=(8, 8))
ax = figure.add_subplot(111)
feat_x=np.array([feat[0,0] for feat in output])
feat_y=np.array([feat[0,1] for feat in output])
ax.scatter(feat_x, feat_y)
for i, txt in enumerate(G):
    ax.annotate(txt, (feat_x[i]+.002, feat_y[i]+.002),size=14)