GNN) GCN Layer Implementation

GCN는 Convolutional Aggregator를 사용하는 방식으로 위치는 다음과 같다.

해당 그래프가 있다면, 해당 그래프에서 GCN에서 필요한 정보는 다음과 같이 크게 3개가 될 수 있다. 

Adjancy matrix(A) , Degree Matrix (D) ,Feature Vector(X)

AX를 구할 때 다음과 같이 구할 수가 있게 되고, 여기서 발생되는 문제점들은 아래에서 소개해드리겠습니다. 

 

 

아래와 같은 그래프가 있다고 하였을 때, GCN을 적용해보고자 한다.

해당 테스크는 노드 분류를 하는 것이지만, 여기서는 GCN LAYER을 구현하는 것까지만 진행하고자 한다.

 

 

import numpy as np
from networkx.algorithms.community.modularity_max import greedy_modularity_communities
import networkx as nx
import matplotlib.pyplot as plt
g = nx.karate_club_graph()

g.number_of_nodes(), g.number_of_edges()
# 34,78

communities = greedy_modularity_communities(g)
colors = np.zeros(g.number_of_nodes())
for i, com in enumerate(communities):
    print(list(com))
    colors[list(com)] = i
n_classes = np.unique(colors).shape[0]
labels = np.eye(n_classes)[colors.astype(int)]
fig, ax = plt.subplots(figsize=(10,10))
pos = nx.spring_layout(g, k=5/np.sqrt(g.number_of_nodes()))
kwargs = {"cmap": 'gist_rainbow', "edge_color":'gray'}
nx.draw(
    g, pos, with_labels=False, 
    node_color=colors, 
    ax=ax, **kwargs)

 

 

 

 

 

일단 GCN을 하기 위해서는 node feature와 adjacency matrix가 필요하니 nxgraph를 이용해서 구하면 다음과 같다.

#Get the Adjacency Matrix (A) and Node Features Matrix (X) as numpy array
A = np.array(nx.attr_matrix(g)[0])
X = np.array(nx.attr_matrix(g)[1])
X = np.expand_dims(X,axis=1)

print('Shape of A: ', A.shape)
print('\nShape of X: ', X.shape)
print('\nAdjacency Matrix (A):\n', A)
print('\nNode Features Matrix (X):\n', X)

 

 

 

Adjacency matrix 및 node features matrix dot product은 인접 노드 기능의 합계를 나타냅니다.

이것을 여기서는 AX라고 합니다.

#Dot product Adjacency Matrix (A) and Node Features (X)
AX = np.dot(A,X)
print("Dot product of A and X (AX):\n", AX)

그 결과 AX는 인접 NODE FEATURES의 SUM를 나타내게 됩니다.

예를 들어 AX의 첫 번째 행은 노드 0에 연결된 노드 기능의 합계, 즉 노드 1, 2, 3에 해당합니다.

이것은 우리에게 propagation mechanism이 GCN에서 어떻게 일어나고 있는지와 노드 연결이 GCN에 의해 보이는 숨겨진 특징 표현에 어떻게 영향을 미치는지에 대한 아이디어를 줄 수 있다고 합니다. 

 

그러나 좀 더 생각해 보면 AX는 인접한 NODE FETURES을 요약하지만 NODE 자체는 고려하지 않는다는 것을 알 수 있을 것입니다.

그래서 이것을 해결하기 위해서 Self-Loops를 넣습니다. 

 

G_self_loops = g.copy()

self_loops = []
for i in range(g.number_of_nodes()):
    self_loops.append((i,i))
G_self_loops.add_edges_from(self_loops)

#Check the edges of G_self_loops after adding the self loops
print('Edges of G with self-loops:\n', G_self_loops.edges)

#Get the Adjacency Matrix (A) and Node Features Matrix (X) of added self-lopps graph
A_hat = np.array(nx.attr_matrix(G_self_loops)[0])
print('Adjacency Matrix of added self-loops G (A_hat):\n', A_hat)

#Calculate the dot product of A_hat and X (AX)
AX = np.dot(A_hat, X)
print('AX:\n', AX)

 

여기까지 보면 또하나의 문제는 scaling이 되어있지 않다는 것입니다. 

이러한 점은 수치 불안정성과 gradient에서 문제룰 줄 수 있기 때문에 처리가 필요합니다. 

 

GCN에서는 도 매트릭스(Degree Matrix, D)를 계산하고 AX를 사용한 D의 inverse의 dot product 연산을 수행하여 데이터를 정상화합니다.

 

#Get the Degree Matrix of the added self-loops graph
Deg_Mat = G_self_loops.degree()
print('Degree Matrix of added self-loops G (D): ', Deg_Mat)

#Convert the Degree Matrix to a N x N matrix where N is the number of nodes
D = np.diag([deg for (n,deg) in list(Deg_Mat)])
print('Degree Matrix of added self-loops G as numpy array (D):\n', D)

#Find the inverse of Degree Matrix (D)
D_inv = np.linalg.inv(D)
print('Inverse of D:\n', D_inv)

#Dot product of D and AX for normalization
DAX = np.dot(D_inv,AX)
print('DAX:\n', DAX)

아래 그림 처럼 정규화가 된 것을 알 수 있습니다. 

AX의 같은 값이어도 DAX는 달라지는 경우가 있는데, 이런 경우에는 node에 degree에 따라 달라지며,

노드의 degree가 낮을수록 노드가 특정 그룹 또는 클러스터에 속해 있는 강도가 높아진다는 의미가 될 수 있다고 합니다.

from scipy.linalg import fractional_matrix_power
#Symmetrically-normalization
D_half_norm = fractional_matrix_power(D, -0.5)
DADX = D_half_norm.dot(A_hat).dot(D_half_norm).dot(X)
print('DADX:\n', DADX)

 

여기까지가 feature handling이고 다음이 nn과 결합하는 부분입니다

Adding Weights and Activation Function

 

위에서 있는 feature handling 하는 부분과 nn weight를 곱하는 것을 하게 되면 다음과 같이 됩니다.

여기서 shape은 항상 (node features, hidden_size) 형태로 되게 됩니다.

배치 사이즈까지 있다면, (batch_size, node_features, hidden_size)가 될 것입니다. 

np.random.seed(77777)
n_h = 4 #number of neurons in the hidden layer
n_y = 2 #number of neurons in the output layer
W0 = np.random.randn(X.shape[1],n_h) * 0.01
W1 = np.random.randn(n_h,n_y) * 0.01

#Implement ReLu as activation function
def relu(x):
    return np.maximum(0,x)

#Build GCN layer
#In this function, we implement numpy to simplify
def gcn(A,H,W):
    I = np.identity(A.shape[0]) #create Identity Matrix of A
    A_hat = A + I #add self-loop to A
    D = np.diag(np.sum(A_hat, axis=0)) #create Degree Matrix of A
    D_half_norm = fractional_matrix_power(D, -0.5) #calculate D to the power of -0.5
    eq = D_half_norm.dot(A_hat).dot(D_half_norm).dot(H).dot(W)
    return relu(eq)
    
#Do forward propagation
H1 = gcn(A,X,W0)
H2 = gcn(A,H1,W1)
print('Features Representation from GCN output:\n', H2)

 

 

def plot_features(H2):
    #Plot the features representation
    x = H2[:,0]
    y = H2[:,1]

    size = 1000

    plt.scatter(x,y,size)
    plt.xlim([np.min(x)*0.9, np.max(x)*1.1])
    plt.ylim([-1, 1])
    plt.xlabel('Feature Representation Dimension 0')
    plt.ylabel('Feature Representation Dimension 1')
    plt.title('Feature Representation')

    for i,row in enumerate(H2):
        str = "{}".format(i)
        plt.annotate(str, (row[0],row[1]),fontsize=18, fontweight='bold')

    plt.show()


plot_features(H2)

중간에 network에서 일부로 2차원을 만들고 맵핑을 해보면, 다음과 같이 나올 것이고, 학습이 된다면, 특정 그룹들끼리 묶이는 현상이 발생할 것으로 예상됩니다.

 

 

Pytorch-geometric Implementation

간단하게 pytorch-geometric에서는 위의 데이터를 사용하면 다음과 같이 구현이 된다. 

import torch
import community as community_louvain
from torch_geometric.data import InMemoryDataset, Data

x = torch.eye(g.number_of_nodes(), dtype=torch.float)

adj = nx.to_scipy_sparse_matrix(g).tocoo()
row = torch.from_numpy(adj.row.astype(np.int64)).to(torch.long)
col = torch.from_numpy(adj.col.astype(np.int64)).to(torch.long)
edge_index = torch.stack([row, col], dim=0)

# Compute communities.
partition = community_louvain.best_partition(g)
y = torch.tensor([partition[i] for i in range(g.number_of_nodes())])

# Select a single training node for each community
# (we just use the first one).
train_mask = torch.zeros(y.size(0), dtype=torch.bool)
for i in range(int(y.max()) + 1):
    train_mask[(y == i).nonzero(as_tuple=False)[0]] = True
data = Data(x=x, edge_index=edge_index, y=y, train_mask=train_mask)

from torch_geometric.nn import GCNConv

LAYER= GCNConv(data.num_features, 2)
embedding = LAYER(data.x, data.edge_index)
embedding_np = embedding.detach().numpy()
plot_features(embedding_np)

 

content	url
gcn example	https://github.com/imayachita/Explore_GCN/blob/master/Building_GCN.ipynb
gcn introduction	https://www.topbots.com/graph-convolutional-networks/