[CS224W] NetworkX , pytorch geometric Tutorial

 

 

1️⃣  NetworkX Tutorial 

---

 

🔹 NetworkX

 

https://networkx.org/

NetworkX — NetworkX documentation

 

•  Software for complex networks 

•  정형, 비정형 데이터를 네트워크에 입력할 수 있다. 

•  다양한 유형의 네트워크를 생성할 수 있다. 

•  analyze network structure, build network models, design new network algorithms, draw networks, and much more

 

 

🌠 library import 

 

import networkx as nx 

 

 

🔹 NetworkX graph types 

 

•  4가지 그래프 유형 

 

Class (불러올때)	Type	Self-loop allowed	Parallel edges (Multiple edges) allowed
Graph	undirected 양방향	Yes	No
DiGraph	directed 단방향	Yes	No
MultiGraph	undirected	Yes	Yes
MultiDiGraph	directed	Yes	Yes

 

 

 

🔹 Graph

 

•  networkX 는 양방향, 단방향 그래프와 같은 다양한 유형의 그래프를 저장하는데 다양한 클래스를 제공한다. Multigraph 를 생성하는 클래스도 지원한다. 

 

# 양방향 undirected 그래프 생성 
G = nx.Graph() 
print(G.is_directed()) 

# 단방향 directed 그래프 생성 
H = nx.DiGraph() 
print(H.is_directed()) 

# 그래프에 속성 추가하기 
G.graph['Name'] = 'bar' 

print(G.graph)

 

 

 

🔹 Node 

 

•  NetworkX 에서는 그래프에 노드를 쉽게 추가시킬 수 있다 : add_node, add_nodes_from 

 

•  add_node : 속성을 가진 한 개의 노드 추가 

 

# 하나의 (속성을 가진) 노드 추가

G.add_node(0, features = 5, label = 0)  # 인덱스위치, 속성 (feature, label)

# node 0 의 속성 출력하기 

node_0_attr = G.nodes[0] 
print('node 0 has the attributes {}'.format(node_0_attr))

 

 

•  add_nodes_from : 속성을 가진 여러개의 노드를 추가

 

# ⭐ 속성을 가진 여러개의 노드를 추가하기 

G.add_nodes_from([
    (1,{'feature' : 1, 'label' : 1}), 
    (2, {'feature' : 2, 'label' : 2})
]) # node, 사전형태로 저장 

# ⭐ 모든 노드+속성을 출력해보자 : .nodes 로 접근 

for node in G.nodes(data=True) : 
  print(node)  # data=True 옵션을 주면 노드의 속성을 반환한다. 

# ⭐ 노드의 개수를 출력해보자 : .number_of_nodes()

num_nodes = G.number_of_nodes() 
print('G has {} nodes'.format(num_nodes))

 

 

🔹 Edge

 

•  NetworkX 에서는 그래프에 엣지를 쉽게 추가시킬 수 있다

 

•  add_edge : 속성을 가진 한 개의 엣지 추가 

 

# 0.5의 가중치를 가진 엣지 하나를 추가 

G.add_edge(0, 1, weight = 0.5)  

# (0,1) 엣지, 즉 노드 0과 노드1을 연결시켜주는 엣지의 속성 출력하기 

edge_0_1_attr = G.edges[(0,1)] 
print('Edge (0,1) attributes {}'.format(edge_0_1_attr))

 

•  add_edges_from : 속성을 가진 여러개의 엣지를 추가

 

# ⭐ 가중치를 가진 엣지 여러개를 추가 

G.add_edges_from([
    (1,2, {'weight' : 0.3}), 
    (2,0,{'weight' : 0.1})
])

# ⭐ 그래프에 존재하는 모든 엣지를 출력해보기 

for edge in G.edges() : 
  print(edge) 

# ⭐ 엣지의 개수 출력해보기 
num_edges = G.number_of_edges() 

print('G 는 {}개의 엣지를 가진다'.format(num_edges))

 

 

 

🔹 시각화 

 

•  nx.draw( 그래프, with_labels = True ) 

 

nx.draw(G, with_labels = True) # 노드의 레이블도 표시하기

 

 

🔹 Degree, neighbor 

 

•  Degree : 차수, 연결된 엣지의 개수 → G.degree[n] 

•  neighbor : 이웃노드 → G.neighbors() 

 

node_id = 1 

# node 1 의 차수(연결된 엣지의 개수) 확인 : G.degree[n]
print('node {} 는 {} 차수 (degree)를 가지고 있다'.format(node_id, G.degree[node_id]))

# node 1 의 이웃 노드 출력하기 : G.neighbors() 
for neighbor in G.neighbors(node_id) :
  print('node {} 는 node {} 를 이웃노드로 가지고 있다.'.format(node_id, neighbor))

 

 

🔹 Other functions 

 

•  networkX 는 유용한 다양한 메서드들을 제공한다. 

•  예) PageRank 

 

num_nodes = 4 

# 새로운 path 를 만들고 단방향 그래프로 바꾸기 

G = nx.DiGraph(nx.path_graph(num_nodes)) 
nx.draw(G, with_labels = True) 

# PageRank 가져오기 

pr = nx.pagerank(G, alpha = 0.8) 
pr

 

 

 

 

※ PageRank : 구글 검색 엔진의 기반 알고리즘으로, 하이퍼링크를 이용해 웹페이지 중요도를 측정하는 알고리즘이다. 모든 그래프에서 노드의 중요도 측정에 사용하는 용도로 쓰인다. 

 

 

 

 

 

 

 

 

2️⃣  Pytorch Geometric Tutorial 

---

 

🔹 Pytorch Geometric 

 

↪  simple graph-structured 예제 :  Zachary's karate club network

 

 

↪  가라테 운동 동아리에 가입된 34명 멤버들 사이의 social network 관계망 

 

↪ 문제정의 : 멤버 간의 상호작용 (A와 B가 사이가 안좋아져서 2개로 club 이 나뉘어짐) 을 일으키는 커뮤니티를 발견하는 것에 초점 

 

 

🔹  데이터셋 가져오기 

 

# 데이터셋 가져오기 

from torch_geometric.datasets import KarateClub  

dataset = KarateClub() 
print(f'Dataset : {dataset} :')  
print('------------------') 
print(f'그래프 개수 : {len(dataset)}') 
print(f'피처의 개수 : {dataset.num_features}') 
print(f'클래스의 개수 : {dataset.num_classes}')

 

 

↪ 가라테 동아리 데이터셋의 속성을 살펴보자면, 이 데이터셋의 경우 하나의 그래프로 구서오디어 있으며, 각 노드는 동아리의 각 구성원 (34명) 을 묘사하기 위해여 34 차원의 feature vector 로 표현된다. 또한 그래프는 각 노드가 속한 커뮤니티 단체를 표현하기 위해 4개의 클래스를 가지고 있다. 

 

 

🔹  그래프 특징들 살펴보기 

 

# 그래프 살펴보기 

data = dataset[0]  # 첫번째 그래프 객체 가져오기 

print(data) 
print('--------------------------------------------------') 

print(f'노드의 개수 : {data.num_nodes}') 
print(f'엣지의 개수 : {data.num_edges}') 
print(f'평균 노드 차수 : {(2*data.num_edges)/data.num_nodes : .2f}') 
print(f'훈련 노드 수 : {data.train_mask.sum()}')  
print(f'훈련 노드 레이블의 비율 : {int(data.train_mask.sum())/data.num_nodes : .2f}') 
print(f'고립 노드를 포함하는지 여부 : {data.has_isolated_nodes()}') 
print(f'self loop 를 포함하는지 여부 : {data.has_self_loops()}') 
print(f'양방향 그래프인지 여부 : {data.is_undirected()}')

 

 

•  Edge list 방식으로 엣지 정보를 표현 

 

data.edge_index.T

 

 

 

•  데이터 구조 

# data 

print(data)

 

↪  속성과 shape 에 대한 정보를 확인해볼 수 있다. 

 

1. edge_index : graph connectivity 그래프 연결성에 대한 정보를 가지고 있다.

 

2. x : node features 노드 피처에 대한 정보를 가지고 있다. (34,34) 표기를 통해, 34개의 노드 각각이 34 차원의 feature vector 로 이루어져 있음을 파악할 수 있다. 

 

3. y : node labels 여기선 값이 34 이므로 각 노드가 특정한 하나의 클래스에 할당되었음을 알 수 있다. 

 

4. train_mask : 각 노드가 어떤 커뮤니티에 속해있는지 설명하는 속성으로, 여기서 우리가 알고있는 ground-truth label 은 4개 노드 뿐이며 (이전 출력 코드 참고) 나머지는 inference 를 통해 맞춰야 한다. 

 

 

 

 

🔹  Edge Index , Viz

 

•  edge_index 를 출력해보자 

 

 

↪  [ source node , destination node ] 형식으로 구성되어 있음 : COO format (coordinate format) 이라고도 부른다. 

 

↪ 시각화는 networkx 라이브러리 포맷으로 진행한다. 

 

from torch_geometric.utils import to_networkx

G = to_networkx(data, to_undirected = True) 
visualize(G, color = data.y)

 

 

 

 

 

 

🔹  그래프 신경망 구축 Graph convolutional network 

 

•  GCN layer : GCNConv 

 

•  GNN 의 output 형태는 ? 

 

↪  각 node 는 feature vector Xi 형태로 표현되며, 이를 input 형태로 넣으면 output 은 embedding 으로 도출되는데, embedding 은 downstream task 에 맞게 표현된 노드 벡터를 의미한다. 학습된 임베딩으로 각 노드 feature 가 맵핑되면, 그러한 임베딩을 통하여 node 단위, edge 단위, graph 단위의 regression 혹은 classification 문제들을 수행할 수 있게 된다. 

 

👉 여기서는 각 노드를 개별 커뮤니티 클래스에 분류하는 Node classification 문제를 다뤄볼 것이다. (learn embedding) 

 

 

class GCN(torch.nn.Module) : 

  def __init__(self) : 
    super().__init__() 
    torch.manual_seed(1234) 
    self.conv1 = GCNConv(dataset.num_features, 4) 
    self.conv2 = GCNConv(4,4) 
    self.conv3 = GCNConv(4,2) 
    
    # 3개의 graph convolutional layer 를 쌓음 
    
    
    # 분류기
    self.classifier = Linear(2, dataset.num_classes) 

  def forward(self, x, edge_index) : 
    h = self.conv1(x, edge_index) 
    h = h.tanh() 
    h = self.conv2(h, edge_index) 
    h = h.tanh() 
    h = self.conv3(h, edge_index) 
    h = h.tanh() 

    out = self.classifier(h) 

    return out, h 

model = GCN() 
print(model)

 

•  GCN 에서 각 layer 는 1-hop neighborbood 즉, 바로 연결된 이웃 노드로부터 정보를 수집하여 임베딩을 진행하고 3개의 layer 를 합칠 땐 각 노드의 3-hop neighborgood 로부터 정보를 수집한다. 

 

•  GCNConv layer 는 노드 feature 의 차원을 34 에서 2로 감소시킨다. 또한 각 layer 는 하이퍼볼릭 탄젠트 활성화 함수 tanh 를 통해 비선형성을 높인다. 

 

•  마지막의 classifier 에 해당하는 linear 층은 노드를 4개의 클래스 중에 하나로 할당하기 위한 분류를 수행하기 위해 선형 변환을 진행하도록 한다. 

 

 

🔹  가중치 학습 이전 모습 시각화 

 

%matplotlib inline
import torch
import networkx as nx
import matplotlib.pyplot as plt

# Visualization function for NX graph or PyTorch tensor
def visualize(h, color, epoch=None, loss=None, accuracy=None):
    plt.figure(figsize=(7,7))
    plt.xticks([])
    plt.yticks([])

    if torch.is_tensor(h):
        h = h.detach().cpu().numpy()
        plt.scatter(h[:, 0], h[:, 1], s=140, c=color, cmap="Set2")
        if epoch is not None and loss is not None and accuracy['train'] is not None and accuracy['val'] is not None:
            plt.xlabel((f'Epoch: {epoch}, Loss: {loss.item():.4f} \n'
                       f'Training Accuracy: {accuracy["train"]*100:.2f}% \n'
                       f' Validation Accuracy: {accuracy["val"]*100:.2f}%'),
                       fontsize=16)
    else:
    	# 📌
        nx.draw_networkx(G, pos=nx.spring_layout(G, seed=42), with_labels=False,
                         node_color=color, cmap="Set2")
    plt.show()

 

 

↪ nx.spring_layout : Fruchterman-Reingold force-directed 알고리즘을 사용하여 노드를 배치 

 

👀  네트워크에서는 개별 노드에 좌표값이 없기 때문에 어디에 그려야 하는지 애매하다. 노드의 수가 많다면 더욱이 해당 네트워크의 특징을 잘 보여지도록 시각화 해야 하기 때문에, 복잡한 네트워크에서 각 노드의 좌표를 잘 배치하여 시각화 하는 방법이 다양한 알고리즘으로 나오고 있다.

 

 

 

 

model = GCN()

_, h = model(data.x, data.edge_index)
print(f'Embedding shape: {list(h.shape)}')

visualize(h, color=data.y)

 

 

👀   가중치 training 이전에 (초기화된 상태에서도) 같은 색(커뮤니티)의 노드들은 이미 임베딩 공간에서 밀접하게 위치하고 있음을 파악할 수 있는데, 이는 GNN 이 비슷한 노드 임베딩은 input 그래프에서 가까운 위치에 존재한다는 inductive bias 를 초래함을 알 수 있다. 

 

↪ Inductive Bias 란 : 주어지지 않은 입력의 출력을 예측하는 것으로 일반화 성능을 높이기 위해 만약의 상황에 대한 추가적인 가정에 해당한다. 보지 못한 데이터에 대해서도 귀납적 추론이 가능해지도록 하는 알고리즘이 가지고 있는 가정의 집합이라 볼 수 있다. CNN 의 경우에는 Locality Translation invariance (어떤 사물이 들어있는 이미지를 제공해줄 때 사물의 위치가 바뀌어도 해당 사물을 인식 가능하다) 에 대한 Relation Inductive Bias 를 갖는데 각 entity 간의 관계가 서로 가까운 비슷한 요소들이 모여있다는 뜻이다. 

 

 

✔ 참고 : https://re-code-cord.tistory.com/entry/Inductive-Bias%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%BC%EA%B9%8C

Inductive Bias란 무엇일까?

 

 

 

🔹  훈련 

 

•  loss 가 1.43 에서 0.02 까지 감소했다. 

 

model = GCN()  
criterion = torch.nn.CrossEntropyLoss()  # loss 
optimizer = torch.optim.Adam(model.parameters(), lr = 0.01) # optimizer 

def train(data) : 
  optimizer.zero_grad() # gradients 초기화 
  out, h = model(data.x, data.edge_index) # forward 
  loss = criterion(out[data.train_mask], data.y[data.train_mask]) # loss 계산 (훈련 노드) 
  loss.backward() # 역전파 
  optimizer.step() # 파라미터 업데이트 
  return loss, h 

for epoch in range(401) : 
  loss, h = train(data) 
  if epoch % 10 == 0 : 
    print(loss)

 

※ predicted label : out 

※ ground-truth label : data.y 

 

 

•  노드 임베딩이 훈련 시간에 따라 evolve 하는 과정 시각화 

 

 

 

 

 

👉 3-layer GCN 모델이 비슷한 클래스의 노드들을 유사한 위치에 배치하며 임베딩을 바꾸어 가며 학습을 진행하는 것을 확인해볼 수 있다.