A preliminary exploration of graph, graph embedding(DeepWalk) and Graph Convolutional Networks(GCN)

17 min readAug 7, 2020

Machine learning 在結構化、影像、文字等類型的資料有許多發展外，以圖學(Graph)為基礎的社群網路資料(如 FB等社群網站互相follow的關係、電子信箱信件往來關係、論文間互相cite...等) 也是目前正在興起的一個方向，在推薦系統或用戶屬性分類以及文章引用建議等有不少用途。

graph data 樣本間往往都存在著相關性，這違反了傳統 ML的 i.i.d.假設，使得演算法無法有效的利用此特徵來做預測。
最近讀了一些些相關的文章和教學，用這篇文章來稍為記錄一下。

Outline:
1. graph
2. networkX
3. DeepWalk
4. Graph Convolutional Network
5. GCN on Cora dataset

Graph

社群網路分析基本上是運用圖論(Graph theory)去從連結中研究關係與架構。Graph 是由"節點"(node or vertex) 和"邊" (edge)所組成，用 V 來代表node，E 代表 edge，一張 graph 的資料可以寫成 G = (V,E)，用以下方式表示:

graph 的架構經常使用 adjacency matrix 表示，並用degree 表示每一個node 有多少個node跟他相連。以上面舉的例子來說:

而每個node 可能會有自己的一些feature 和 label(可能是預測目標)，edge 也可能有不同權重(關連性的強度)，沒有的話就當作equal weight.

NetworkX

networkx 是一款 Python 的package，用於創造、操作網絡。官網有基本操作的教學: https://networkx.github.io/documentation/stable/tutorial.html

用networkx 來建立上面的範例圖:

import networkx as nxG = nx.Graph() #initialize一張空圖
G.add_edges_from([(1,2),(1,3),(1,4),(2,3),(3,4)])
nx.draw(G,with_labels=True)print('number of nodes:',G.number_of_nodes())
print('number of edges: ',G.number_of_edges())

使用 .add_node 和 .add_edge 新增 node 和edge:

使用 set_node_attributes 來給定 node 的label 或 feature

## 隨機給每個 node A 或 B 兩種 label 
import randomcat = ['A','B']
node_cat_mapping = {
node:random.sample(cat,1)[0] for node in list(G.nodes)
}
node_cat_mapping>>{1: 'B', 2: 'A', 3: 'B', 4: 'A', 5: 'A', 6: 'A'}## set node attribute by set_node_attributes
nx.set_node_attributes(G, node_cat_mapping, 'label')
G.nodes[1]>>{'label': 'B'}
## we use different color to represent node label in graph. 
cat_color_mapping = {'A':'green','B':'yellow'}node_color_list = [cat_color_mapping[ G.nodes[node]['label'] ] for node in list(G.nodes) ]node_color_list
>>['yellow', 'green', 'yellow', 'green', 'green']
## draw the graph
nx.draw(G,with_labels=True,node_color=node_color_list)

DeepWalk

paper: https://arxiv.org/abs/1403.6652

一張graph 可能僅有一部分的node 有 label ，針對沒有label的node我們可能會想做一些像是 classification / anomaly detection 等等的事，而一般ML 模型是無法直接吃 graph 架構的。

Deepwalk是一種 graph embedding 的方法，它將graph 的拓樸架構映射到歐式空間，使每個 node轉換成一個低維度的向量表示。兩點在graph裡連結關係較強者在歐式空間中距離也會較接近。

embedding 的做法是利用word2vec ，在語音助理那篇裡有稍微介紹到。但要套用skip-gram or CBOW 必須要有corpus呀，我只有graph又沒有sentences要怎麼做呢？

deepwalk的貢獻就是在graph的每個 node 上隨機遊走，將走過的路徑視為一句sentence，然後再透過word2vec得到 embeded function。

Random Walk:

其實想想也蠻直觀的，node間的連結關係的確有點像單詞間前後文的關係。

演算法如下：每個node為出發點各走 gamma 次長度為 t 的路徑，把路徑收集起來當作語料庫來訓練word2vec，即可得到embedding

DeepWalk 實做

這裡我使用 karate_club_graph 數據集，Zachary’s Karate Club是一個描述大學空手道俱樂部成員社交關係的網路，由Wayne W. Zachary在論文 “An Information Flow Model for Conflict and Fission in Small Groups” 中提出，是一個常用的社交網路範例。這個俱樂部共包含34名成員，會長 John A 和教官 Mr. Hi (化名)之間因是否調漲價錢而產生衝突導致這個俱樂部一分為二，一半的成員跟著 Mr. Hi 成立了新的俱樂部，另一半成員要麼找了新的教練，要麼放棄空手道。

先來看一下數據集的樣子

稍為看一下degree 的資訊:

可以看到大部分的人都只有連接5個人以內，有兩個人的degree特別高，大概就是管理員和教官吧。

接著開始deepwalk的部分，這裡我是參考了這篇文章，我把他的code稍微修改整理一下。

來稍微看一下幾條random walk的路徑:

for i in range(10):
    print(corpus[i])

可以看到前30條路徑皆為由0出發隨機走50步

接著把每個node 丟進train 好的 word2vec model 取得 embedding 並加入node attribute:

# set node attribute
nx.set_node_attributes(G, node_embedding_dic, 'embedding')G.nodes[0]>>{'club': 'Mr. Hi', 'embedding': array([-0.655476 ,  0.7207127], dtype=float32)}

可以看到node除了原本就有的 'club' 外多了embedding的attribute。接著把他畫出來看看:

可以看到光用graph的架構資訊 (沒有用到任何node 的feature) 並只embedding 到2維空間就能用一個線性分類器把兩個類別給分的不錯了!

Graph Convolutional Networks

在CNN中convolution 能夠有效的提取 image 特徵同時又避免了過大的參數量而有許多表現很好的知名網路架構。然而CNN的 convolution 無法直接應用到圖學上，因此衍伸出了GCN。

對CNN熟的人大概都知道 convolution layer的運算就是把像素中鄰近的點給做 weighted sum，而GCN的概念其實也類似，它把與該node 有連結的node的feature給做weight sum。

找出每個node 鄰近的node 就是透過 adjacency matrix ，先定義幾個符號:

N: total node count
A: adjacency matrix(NxN)
X: node feature matrix (假設每個node 用 f 個 feature，那麼X為 NxF)
W: 權重矩陣 (假設第一層有 hidden_size個節點，那麼W為 F x hidden_size)

直接用例子來看，我延續前一篇的範例，並假設每個node 各有一個 2 維度的特徵:

hidden_size = 10
A = np.matrix([[0,1,1,1],
               [1,0,1,0],
               [1,1,0,1],
               [1,0,1,0]])
X = np.matrix([[1,1],[2,2],[3,3],[4,4]]) #隨便假設每個node的feature
W = np.matrix(np.random.normal(loc=0,scale=1,size=(2, hidden_size)))#隨機給權重print('adjacency matrix size:',A.shape)
print('feature matrix size:',X.shape)
print('first layer weight matrix:',W.shape)>> adjacency matrix size: (4, 4) 
>> feature matrix size: (4, 2) 
>> weight matrix: (2, 10)

那我們想要的是把node相鄰的點給做weighted sum 因此計算 A*X 便可得到

A*X
>>matrix([[9., 9.],         
          [4., 4.],         
          [7., 7.],         
          [4., 4.]])

手乘一次就會知道第一列的9 = 0*1+1*2+1*3+1*4，也就是和node ‘1’ 相臨的另外3個點的 feature 相加。因此呢，如果我們算的是A*X*W 就是有相鄰的這幾個node 的feature 做 weighted sum!

然而這邊有兩個問題:

沒用到自己的特徵
每個node 的degree不相同，在訓練的時候不公平，沒什麼人連接到的node可能gradient很小沒辦法訓練到，反之可能梯度爆炸

因此做些調整: 把graph每個node 都加上自我連接，也就是 adjacency matrix 加上 identity matrix ，然後利用degree matrix 的反矩陣來對不同degree的node做標準化。

所以就變成:

A_hat = A+np.eye(4)
D_hat = np.array(np.sum(A_hat, axis=1)).reshape(-1) #考慮自迴圈
D_hat = np.matrix(np.diag(D_hat))

可以看到當你degree越高(鄰居越多)，D 反矩陣對應的系數就會越小。
而標準化的方式直接取反矩陣算是一種算術平均:

但其實 GCN 幾乎都是用幾何平均的方式來標準化:

最後再取個activation function 就變成:

(Hi代表第i 層的hidden layer 輸出，H0則為node feature 也就是上面的X)

GCN 到這邊看似直觀好理解，但其實背後有扎實的數學理論支持著，詳細可以看李宏毅老師的助教課了解一下。

Example on Karate Club dataset

這邊延用前一篇介紹的 Karate club 資料集來實做看看上面手刻的GCN

一樣先load 資料:

計算 A_hat 和 D_hat 以及初始化權重W，因為node其實沒有 feature 所以第一層的X 直接帶單位矩陣

https://gist.github.com/henry16lin/e09c10a8efe69c917f7fbf655f221ca7#file-karaph_gcn_1-py

然後就是計算GCN layer 並把softmax前的embedding拿來畫圖看看:

到目前為止在完全沒有用到node feature 也沒有訓練直接使用隨機初始化的權重透過 GCN 出來的embedding 似乎就有點能分開的樣子!

接著我們找一組比較複雜一點的資料集來實際訓練GCN試試~

GCN on Cora dataset

要訓練類神經網路我們需要深度學習框架，這邊使用 pytorch geometric 簡稱pyG 是一個基於pytorch 建例來處理圖學相關資料的深度學習框架，使用過pytorch 基本上要操作pyG應該是可以無縫使用。

Cora dataset

cora dataset 是由機器學習論文所組成的，node 一共有七種論文類別:

Case_Based
Genetic_Algorithms
Neural_Networks
Probabilistic_Methods
Reinforcement_Learning
Rule_Learning
Theory

每一篇論文至少引用了數據集裡面另外一篇論文或者被另外一篇論文所引用，共有2708篇有label 的papers，而每篇paper 共有1433個feature，表示該篇paper是否有包含某個特殊的專有名詞(皆為0/1)

cora 數據集在pyG裡有內建先把他load起來

from torch_geometric.datasets import Planetoiddataset = Planetoid(root='/tmp/Cora', name='Cora')

我們先把它轉成networkX 把graph 畫出來看看:

然後看一些graph的基本資訊:

#some informationprint(dataset[0])
print('is directed:',dataset_x.is_directed())
print('num of nodes:',dataset_x.number_of_nodes())
print('num of edges:',dataset_x.number_of_edges())
print('num of classes:',len(set(y_np)))
print('degree distribution:')degree_sequence = [d for n, d in dataset_x.degree()]
plt.hist(degree_sequence,bins='auto')
plt.show()
print('average degree:',np.mean(degree_sequence))
>> Data(edge_index=[2, 10556], test_mask=[2708], train_mask=[2708],val_mask=[2708], x=[2708, 1433], y=[2708]) 
>> is directed: False 
>> num of nodes: 2708 
>> num of edges: 5278 
>> num of classes: 7 
>> average degree: 3.8980797636632203

其中上面的 train/val/test mask 是有幫我們切分好的 true/false list

然後來建立GCN 的layer:

可以看到完全和pytorch 一樣，只是引入了 pyG 的 layer!

最後開始訓練!

我們來看看GCN 把 cora data embedding 成什麼樣子來進行分類:
(使用t-SNE 降到2維呈現)

可以看到把training set 分得很不錯，而test 似乎有點overfitting的現象，不過我覺得training set 的資料量這麼少(140筆)，應該也不容易了吧?!

順帶一提，基於好奇我用前一篇的 deepwalk 做一次cora dataset 把graph embedding到100維，然後將原本的node feature (1433維)給合併起來變成1533維的feature 並丟到XGBoost 跑跑看，最後得到 test acc~58%，所以GCN應該還是蠻有用的!

GCN 後來也有很多變型，如 GAT(透過attention 學習edge間的比重) 以及 cluster-GCN(解決graph太大時或layer較深時的計算問題)，這些在pytorch geometric裡都有提供可以直接使用!