Machine Learning with Graphs hw#1 @NCKU

本次作業為paper “Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach” 之實作，相較於耗費大量時間計算出一龐大網路中各節點實際的 Betweenness Centrality value，此研究目標在於利用深度學習技術，在encoder-decoder之框架下建構並訓練一個model，預測出各節點之間相對應的BC值大小，進而有效且快速地找出在龐大網路中BC值較高之重要節點。

此報告主要分為兩大部分，先是藉由此程式碼，在實作方法上做詳細的解說；而後再針對此實作計算出的結果做比較和分析。

根據上圖，細分為encoder/max pooling/decoder來建立model：

1.1 Encoder

encoder負責生成各點之feature，首先將input [deg(v), 1, 1] 經由fully-connected layer和ReLU轉成128維，之後的處理順序分別為：

1. Neighborhood Aggregation: GCN

為了省去直接計算兩點間最短距離之成本，這裡選擇使用Graph Convolutional來對圖做局部的aggregation操作，實作上直接套用torch_geometric中的GCNConv()

# prepare model
import torch
import torch.nn as nn
from torch_geometric.nn import MessagePassing
from torch_geometric.utils import add_self_loops, degree

class GCNConv(MessagePassing):
    def __init__(self, in_channels, out_channels):
        super(GCNConv, self).__init__(aggr='add')  
        self.lin = torch.nn.Linear(in_channels, out_channels)
    def forward(self, x, edge_index):
        edge_index, _ = add_self_loops(edge_index, num_nodes=x.size(0))
        x = self.lin(x)
        row, col = edge_index
        deg = degree(row, x.size(0), dtype=x.dtype)
        deg_inv_sqrt = deg.pow(-0.5)
        norm = deg_inv_sqrt[row] * deg_inv_sqrt[col]
        return self.propagate(edge_index, size=(x.size(0), x.size(0)), x=x, norm=norm)
    def message(self, x_j, norm):
        return norm.view(-1, 1) * x_j
    def update(self, aggr_out):
        return aggr_out

2. Combine: GRU

為了取得更佳的feature，我們需要對這層此node之neighborhood 的embedding 與此node自己上一層的embedding做Combine，而根據論文，這裡選用相較其他method而言，更具彈性的GRU來達成目標！

3. Layer Aggregation: max pooling

結束5次的Aggregation和Combine後，得到5個128維的feature，再從中以element-wise的方式，取出5個值中的最大值，得到一個128維的output。

        l = [x1[0],x2[0],x3[0],x4[0],x5[0]]
        l = torch.stack(l)
        x = torch.max(l, dim=0).values
        return x

1.2 Decoder

Decoder再負責將各點之feature轉成預測之BC value。而根據論文，這裡選擇ReLu作為我們的activation function。

        self.fc2 = nn.Linear(128, 64)
        self.relu2 = nn.LeakyReLU()
        self.fc3 = nn.Linear(64, 1)

最後得出

利用networkx之powerlaw_cluster_graph (n, m, p, seed=None) 生成n（在此model中設batch_size=16）個網路，其中參數之設置：

• n- num of nodes : random(150,200)
• m- num of random edges to add each new node: 4
• p- probability of adding a triangle after adding a random edge: 0.05

生成n個網路後，整理資料求出：

• deg_list：(|V| x 3) = [[deg(n0), 1, 1], [deg(n1), 1, 1], [deg(n2), 1, 1], …]
• edge_index：(2 x |E|) = [[S], [T]] { for all edge(s,v) in G | s∈S, t∈T }

利用networkx之betweenness_centrality(n) 算出各點實際的BC值，這裡特別要注意的是為了避免BC值太小（都趨近於0），model train不起來，因此算出之BC值得再做log處理，使彼此之差值變大，結果才可成功收斂。

• bc_value：(|V| x 1) = [bc(n0), bc(n1), bc(n2), …]

最後，用來比較兩兩node之間實際bc值的差值和predict之bc相對值的差值，採用論文的作法：randomly sample 5|V | source nodes and 5|V | target nodes來做比較之pair。

• pair_index：(2 x 5|V|) = [[shuffle(node_in_G5)], [shuffle(node_in_G5)]]

開始train！其中Optimizer、參數之設置皆參考於論文，training過程如下：

• learning rate: 0.0001
• batch size: 16
• iteration: 10000

最後之loss平均結果約落在：6000-7000上下

4.1 Read File

讀檔，將資料放進model得到結果

  f = readFile('y') #y for com_youtube,num for synthetic data
  f.get_deg_list() 
  f.get_edge_index()  
  f.get_bc_value()  
  
  outs = model(f.get_deg_list(),f.get_edge_index())

4.2 Top-N % accuracy

將經model運算得出的BC相對值以及實際計算得到BC值做排序，取出兩者前N%，再比較其相同node的數量作為一個準確度的判斷：

def takeSecond(elem):
    return elem[1]
    
def topN_accuracy(file,outs,n):
  predict_value,bc_value = [],[]
  for i,j in enumerate(outs.tolist()):
    predict_value.append([i,*j])
  bc_value = f.get_bc_value()
  bc_value.sort(key = takeSecond,reverse = True)
  predict_value.sort(key = takeSecond,reverse = True)
  p,t = [],[]
  for x in range(int(len(predict_value)*n/100)):
    p.append(predict_value[x][0])
    t.append(bc_value[x][0])
  return(len(set(t)&set(p)) / len(p))

4.3 Kendall tau

利用Kendall tau直接比較實際值/預測值間排序的相似程度：

import scipy.stats as stats
def kendall_tau(file,outs):
  predict_value,bc_value = [],[]
  for i,j in enumerate(outs.tolist()):
    predict_value.append(*j)
  for i in file.get_bc_value():
    bc_value.append(i[1])
  # print(predict_value)
  # print(bc_value)
  tau, _ = stats.kendalltau(predict_value, bc_value)
  return(tau)

利用30筆生成網路之data/ 真實網路youtube之data驗證此model：

根據結果可以發現此model之表現明顯在生成網路上是更勝於真實網路的，測試了30筆具5000個節點之不同的生成網路，標準差平均約0.017，top-10% rank以內的準確率普遍到達85%以上，Kendal tau係數平均也有0.63；相較於真實網路，top-10% rank以內的準確率平均只有約6成，Kendal tau係數也降到0.4。 然而會有這樣的結果，也可能是因為兩個網路的節點數相差太大（生成網路只有5000個node，然而youtube資料有10幾萬個），這部分也是有待討論。

training data: powerlaw_cluster_graph(n=random(150,200), m=4, p=0.05, seed=None)

針對n, m, p三組參數做實驗：

• n- 生成網路中的node數

根據結果可以發現training data中網路的node數對於較小的生成網路來說影響不大，而對於龐大的真實網路來說，準確率似乎有提升一點點。

• m- 生成網路中each node的基本邊數

根據結果可以發現training data中網路的邊數同樣對於較小的生成網路來說影響不大，但對於較龐大的真實網路來說，論文中實作的邊數4的確是最好的結果。

• p- 生成網路中新邊形成三角形的機率

根據結果同樣可以發現training data中三角形的數目越多，對於較小的生成網路來說影響不大，但對於較龐大的真實網路來說，雖然Top-10%以內的準確率看似沒有相差太多，但Kendal tau係數卻成了負相關，可見training data之網路選擇也不可過於群聚。

測試不同embedding dimension對於結果的影響：

根據結果可以發現，dim的調整對於較小的生成網路影響皆不大，而在youtube網路上，dim越低的確結果越差，然而dim越高，雖然Kendal tau係數變大了，但top-K之準確率卻相當的低。對於此現象，推測有可能是因為training data的網路較小，所以測試較龐大的網路時產生overfitting。