用於多關係數據的圖神經網絡R-GCNs

　　

　　本文描述如何擴展圖神經網絡(GNNs)的最簡單公式，以編碼知識圖譜(KGs)等多關係數據的結構。

　　這篇文章包括4個主要部分:

　　1. 介紹了描述KGs特性的多關係數據的核心思想;

　　1. GNN體系結構中包含的標準組件摘要;

　　1. gnn最簡單公式的描述，稱為圖卷積網絡(GCNs);

　　1. 討論如何以關係圖卷積網絡(R-GCN)的形式擴展GCN層，對多關係數據進行編碼。

知識圖作為多關係數據

　　基本圖結構包括用於連接節點的無向，無類型和唯一邊。 例如，在哲學領域，我們可以定義兩個由「蘇格拉底」和「柏拉圖」實體表示的節點之間的連結。 在這種特定情況下，我們不提供關於這些哲學家之間關係的任何信息。。

　　另一方面，KG包括定向的，類型化的和用於連接節點的多個邊。 考慮我們正在運行的示例，從「蘇格拉底」到「柏拉圖」的連接可以用「影響」來標記。 在相反的方向上，可以建立從「柏拉圖」到「蘇格拉底」的另一種連接，可以用「影響者」來標記。

　　換句話說，KG是基於圖的結構，其節點表示真實世界的實體，而邊沿則定義了這些實體之間的多個關係。

圖神經網絡

　　GNN的主要組件包括(I)輸入層，(ii) GNN層，(iii)多層感知器(MLP)預測層。

　　在該體系結構中，GNN層是編碼局部圖結構的關鍵組件，用於更新節點表示。不同的GNN層使用不同類型的局部圖結構聚合。為了說明使用GNN行為，我們使用NumPy進行編碼，完成以下3個主要成分:

　　1. 表示節點的獨熱向量(無特徵)矩陣

　　1. 描述節點隱藏特徵的權值矩陣

　　1. 定義節點間無向邊的鄰接矩陣

　　### One-hot vector representation of nodes (5,5):
X = np.eye(5, 5)
n = X.shape[0]
np.random.shuffle(X)
print(X)

[[0. 0. 1. 0. 0.] # Node 1
[0. 1. 0. 0. 0.] # Node 2
[0. 0. 0. 0. 1.] ...
[1. 0. 0. 0. 0.]
[0. 0. 0. 1. 0.]] # Node 5
### Weight matrix (5,3)
# Dimension of the hidden features
h = 3
# Random initialization with Glorot and Bengio
W = np.random.uniform(-np.sqrt(1./h), np.sqrt(1./h),(n,h))
print(W)

[[-0.4294049 0.57624235 -0.3047382 ]
[-0.11941829 -0.12942953 0.19600584]
[ 0.5029172 0.3998854 -0.21561317]
[ 0.02834577 -0.06529497 -0.31225734]
[ 0.03973776 0.47800217 -0.04941563]]
### Adjacency matrix of an undirect Graph (5,5)
A = np.random.randint(2, size=(n, n))
# Include the self loop
np.fill_diagonal(A, 1)
# Symmetric adjacency matrix (undirected graph)
A_und = (A + A.T)
A_und[A_und > 1] = 1
print(A_und)

[[1 1 1 0 1] # Connections to Node 1
[1 1 1 1 1]
[1 1 1 1 0]
[0 1 1 1 1]
[1 1 0 1 1]]

　　考慮到這些因素，通過更新過程的所謂「消息傳遞框架」（message passing framework ,Gilmer ，2017）執行了「遞歸鄰域擴散」（ recursive neighborhood diffusion ,Dwivedi，2020）。 鄰居的特徵通過邊緣作為消息傳遞給目標節點。具體地說，所需的操作如下(請參閱NumPy代碼了解更多細節):

　　1. 涉及節點和權重矩陣（包括其隱藏特徵）的初始表示的線性變換（或投影）。

　　1. 鄰域擴散以更新節點的表示形式，匯總其鄰居的隱藏特徵。 針對每個節點並行計算此操作。

　　### Linear transformation
L_0 = X.dot(W)
print(L_0)

[[ 0.5029172 0.3998854 -0.21561317] # Node 1 (3rd row of W)
[-0.11941829 -0.12942953 0.19600584] # Node 2 (2nd row of W)
[ 0.03973776 0.47800217 -0.04941563] # Node 3 (5th row of W)
[-0.4294049 0.57624235 -0.3047382 ]
[ 0.02834577 -0.06529497 -0.31225734]] # Node 5 (4th row of W)
### GNN - Neighborhood diffusionND_GNN = A_und.dot(L_0)
print(ND_GNN)

[[ 0.45158244 0.68316307 -0.3812803 ] # Updated Node 1
[ 0.02217754 1.25940542 -0.6860185 ]
[-0.00616823 1.3247004 -0.37376116]
[-0.48073966 0.85952002 -0.47040533]
[-0.01756022 0.78140325 -0.63660287]]
### Test on the aggregation
assert(ND_GNN[0,0] == L_0[0,0] + L_0[1,0] + L_0[2,0] + L_0[4,0])

　　觀察鄰域擴散的結果，您可以注意到節點1的更新表示

　　[0.5029172 0.3998854 -0.21561317] # Node 1

　　為表示節點1 (self-loop)、節點2、節點3、節點4的向量之和。這些節點根據前面定義的鄰接矩陣連接到節點1。

　　[ 0.5029172 0.3998854 -0.21561317] # Node 1[-0.11941829 -0.12942953 0.19600584] # Node 2[ 0.03973776 0.47800217 -0.04941563] # Node 3[ 0.02834577 -0.06529497 -0.31225734] # Node 5

　　本節中描述的代碼可以在數學上形式化如下:

　　通用更新功能（hi ^（l + 1）），用於將鄰居（hj ^ l）的隱藏特徵聚合到中心節點（h_i ^ l）的隱藏特徵

圖卷積網絡(GCNs)

　　在被稱為普通圖卷積網絡(GCNs)的GNNs的公式中，節點更新是通過「對鄰域特徵進行各向同性平均運算」來執行的(isotropic averaging operation over the neighborhood features ，Dwivedi，2020)。換句話說，相鄰節點同樣有助於更新中心節點的表示。更準確地說，在普通GCNs(Vanilla GCNs)的具體情況下，執行了各向同性平均計算。這個計算需要一個由每個節點的度表示的新元素，該度由其連接邊的數量組成。

　　### Degree vector (degree for each node)
D = A_und.sum(axis=1)
print(D)

[4 5 4 4 4] # Degree of Node 1
### Reciprocal of the degree (diagonal matrix)
D_rec = np.diag(np.reciprocal(D.astype(np.float32)))
print(D_rec)

[[0.25 0. 0. 0. 0. ] # Reciprocal value of Node 1 degree
[0. 0.2 0. 0. 0. ]
[0. 0. 0.25 0. 0. ]
[0. 0. 0. 0.25 0. ]
[0. 0. 0. 0. 0.25]]
### GCN - Isotropic average computation
ND_GCN = D_rec.dot(ND_GNN)
print(ND_GCN)

[[ 0.11289561 0.17079077 -0.09532007] # Updated Node 1 (with deg)
[ 0.00443551 0.25188109 -0.1372037 ]
[-0.00154206 0.3311751 -0.09344029]
[-0.12018491 0.21488001 -0.11760133]
[-0.00439005 0.19535081 -0.15915072]]
### Test on the isotropic average computation:
assert(ND_GCN[0,0] == ND_GNN[0,0] * D_rec[0,0])

　　度向量的每個元素代表i節點的度值。 實際上，向量的第一個元素等於4，因為鄰接矩陣顯示4個節點連接到節點1。然後計算度數的倒數，以實現連接到節點的邊的平均貢獻。 最後，根據GCN公式進行各向同性平均計算。 使用節點1度執行平均計算的節點1的更新表示等於：

　　[ 0.11289561 0.17079077 -0.09532007]

　　通過將以下向量（表示節點1的聚合表示）乘以其度數的倒數（0.25），可以得到此向量：

　　[ 0.45158244 0.68316307 -0.3812803 ]

　　本節中描述的代碼可以通過數學形式化如下：

　　描述GCN層執行的各向同性平均聚合的函數。 U是投影步長的結果，deg是中心節點的度數。 N是其鄰居數

關係圖卷積網絡（Relational-GCN）

　　前面的示例描述了GCN在無向和無類型圖上的行為。如前所述，更新過程基於以下步驟（在以下說明中，為簡單起見，不考慮節點度）。

　　通過將（i）單熱點特徵矩陣與（ii）權重矩陣相乘，可以實現投影步驟（或線性變換）。

　　（i）2D矩陣（n，n），用於定義表示節點的獨熱向量。

　　（ii）定義隱藏特徵的2D矩陣（n，h）。當前矩陣僅編碼一種類型的關係。

　　將鄰接矩陣(i)與投影步驟產生的矩陣(ii)相乘，即可實現一個聚合步驟。

　　（i）2D對稱矩陣（n，n），描述無向和無類型的邊。

　　（ii）投影步驟產生的2D矩陣（n，h）。

　　為了擴展GCN層以編碼KG結構，我們需要將我們的數據表示為有向圖和多類型圖。更新/聚合過程與上一個類似，但是組成部分稍微複雜一些。下面提供了有關執行步驟的詳細信息。

　　通過將（i）獨熱點特徵矩陣與（ii）權重張量相乘，可以實現投影步驟。

　　（i）定義節點初始特徵的2D矩陣（n，n）。

　　（ii）描述節點隱藏特徵的3D張量（r，n，h）。該張量能夠通過堆疊大小為（n，h）的r批矩陣來編碼不同的關係。每個批都編碼單個類型的關係。

　　投影步驟將不再是矩陣的簡單乘法，而是批次矩陣乘法，其中（i）與（ii）的每一批相乘。

　　聚合步驟，是通過將（i）（有向）鄰接張量乘以（ii）由投影步驟得出的張量而實現的。

　　（i）描述有向和r型邊的3D張量（r，n，n）。該張量由r批鄰接矩陣（n，n）組成。每個鄰接矩陣根據特定類型的關係描述節點之間的邊。而且，與無向圖的鄰接矩陣相比，這些鄰接矩陣中的每一個都不對稱，因為它編碼特定的邊緣方向。

　　（ii）由上述投影步驟產生的3D張量（r，n，h）。

　　就像投影步驟一樣，聚合階段包括一個批處理矩陣乘法。每批（i）乘以每批（ii）。此匯總定義了每個批次的GCN轉換。在該過程的最後，必須將批次加在一起（R-GCN），以獲得根據不同關係類型併入鄰域聚合的節點表示。

　　以下代碼示例顯示了R-GCN層的行為，該行為編碼具有兩種類型的邊（或關係）的有向和多類型圖或KG。

　　### Recall: One-hot vector representation of nodes (n,n)
print(X)
[[0. 0. 1. 0. 0.] # Node 1
[0. 1. 0. 0. 0.] ...
[0. 0. 0. 0. 1.]
[1. 0. 0. 0. 0.]
[0. 0. 0. 1. 0.]]
### Number of relation types (r)
num_rels = 2
### Weight matrix of relation number 1 (n,n)
## Initialization according to Glorot and Bengio (2010))
W_rel1 = np.random.uniform(-np.sqrt(1./h),np.sqrt(1./h),(n,h))
print(W_rel1)

[[-0.46378913 -0.09109707 0.52872529]
[ 0.03829597 0.22156061 -0.2130242 ]
[ 0.21535272 0.38639244 -0.55623279]
[ 0.28884178 0.56448816 0.28655701]
[-0.25352144 0.334031 -0.45815514]]
### Weight matrix of relation number 2 (n,h)
## Random initialization with uniform distribution
W_rel2 = np.random.uniform(1/100, 0.5, (n,h))
print(W_rel2)

[[0.22946783 0.4552118 0.15387093]
[0.15100992 0.073714 0.01948981]
[0.34262941 0.11369778 0.14011786]
[0.25087085 0.03614765 0.29131763]
[0.081897 0.29875971 0.3528816 ]]
### Tensor including both weight matrices (r,n,h)
W_rels = np.concatenate((W_rel1, W_rel2))
W_rels = np.reshape(W_rels,(num_rels, n, h))
print(W_rels)

[[[-0.46378913 -0.09109707 0.52872529]
[ 0.03829597 0.22156061 -0.2130242 ]
[ 0.21535272 0.38639244 -0.55623279]
[ 0.28884178 0.56448816 0.28655701]
[-0.25352144 0.334031 -0.45815514]]
[[ 0.22946783 0.4552118 0.15387093]
[ 0.15100992 0.073714 0.01948981]
[ 0.34262941 0.11369778 0.14011786]
[ 0.25087085 0.03614765 0.29131763]
[ 0.081897 0.29875971 0.3528816 ]]]

### Linear trasformationwith batch matrix multiplication (r,n,h)
L_0_rels = np.matmul(X, W_rels)
print(L_0_rels)

[[[ 0.21535272 0.38639244 -0.55623279] # Node 1 (3rd row of W_rel1)
[ 0.03829597 0.22156061 -0.2130242 ]
[-0.25352144 0.334031 -0.45815514]
[-0.46378913 -0.09109707 0.52872529]
[ 0.28884178 0.56448816 0.28655701]]
[[ 0.34262941 0.11369778 0.14011786] # Node 1 (3rd row of W_rel2)
[ 0.15100992 0.073714 0.01948981]
[ 0.081897 0.29875971 0.3528816 ]
[ 0.22946783 0.4552118 0.15387093]
[ 0.25087085 0.03614765 0.29131763]]]
### Adjacency matrix of relation number 1 (n,n)
A_rel1 = np.random.randint(2, size=(n, n))
np.fill_diagonal(A, 0) # No self_loop
print(A_rel1)

[[0 1 1 1 1] # Connections to Node 1 with Rel 1
[1 1 0 0 1] # Connections to Node 2 with Rel 1
[1 0 0 1 0]
[0 0 1 1 1]
[1 1 0 1 0]]
### Adjacency matrix of relation number 2 (n,n)
A_rel2 = np.random.randint(3,size=(n,n))
np.fill_diagonal(A_rel2, 0) # No self loop
A_rel2[A_rel2>1] = 0

[[0 0 0 1 0] # Connections to Node 1 with Rel 2
[1 0 0 0 0] # Connections to Node 2 with Rel 2
[1 0 0 1 1]
[0 0 0 0 0]
[0 1 0 0 0]]
### Tensor including both adjacency matrices (r,n,n)
A_rels = np.concatenate((A_rel1, A_rel2))
A_rels = np.reshape(A_rels, (num_rels, n, n))
print(A_rels)

[[[0 1 1 1 1] # Connections to Node 1 with Rel 1
[1 1 0 0 1]
[1 0 0 1 0]
[0 0 1 1 1]
[1 1 0 1 0]]
[[0 0 0 1 0] # Connections to Node 2 with Rel 2
[1 0 0 0 0]
[1 0 0 1 1]
[0 0 0 0 0]
[0 1 0 0 0]]]
### (GCN) Neighborhood diffusion for each typed edge (r,n,h)
ND_GCN = np.matmul(A_rels, L_0_rels)
print(ND_GCN)

[[[-0.39017282 1.0289827 0.14410296] # Updated Node 1 with Rel 1
[ 0.54249047 1.17244121 -0.48269997]
[-0.24843641 0.29529538 -0.0275075 ]
[-0.42846879 0.80742209 0.35712716]
[-0.21014043 0.51685598 -0.2405317 ]]
[[ 0.22946783 0.4552118 0.15387093] # Updated Node 1 with Rel 2
[ 0.34262941 0.11369778 0.14011786]
[ 0.82296809 0.60505722 0.58530642]
[ 0. 0. 0. ]
[ 0.15100992 0.073714 0.01948981]]]
### (R-GCN) Aggregation of GCN (n,h)
RGCN = np.sum(ND_GCN, axis=0)
print(RGCN)

[[-0.16070499 1.48419449 0.29797389] Updated Node 1(Rel 1 + Rel 2)
[ 0.88511988 1.28613899 -0.34258211]
[ 0.57453168 0.9003526 0.55779892]
[-0.42846879 0.80742209 0.35712716]
[-0.05913052 0.59056998 -0.22104189]]
### Test of the aggregation
assert(RGCN[0,0] == L_0_rels[0,1,0] + L_0_rels[0,2,0] + L_0_rels[0,3,0] + L_0_rels[0,4,0] + L_0_rels[1,3,0])

　　你可以從這個例子中注意到，鄰域擴散(GCN)的結果是一個大小為(r, n,h)的3D張量，而不是一個大小為(n,h)的2D矩陣。原因是，對於每種類型的關係，鄰居擴散都是以一種單獨的方式進行的。R-GCN層對GCN所實現的每種關係類型的節點表示進行聚合。為了闡明這個方面，考慮節點1的聚合表示

　　[-0.16070499 1.48419449 0.29797389]

　　這個向量是由節點1的更新表示與關係1相加得到的

　　[-0.39017282 1.0289827 0.14410296]

　　與關係2的節點1的更新表示

　　[ 0.22946783 0.4552118 0.15387093]

　　本節中描述的代碼可以在數學上形式化如下:

　　描述R-GCN層執行的各向同性聚合的功能。 與先前的功能相比，此聚合包括進一步的求和運算，該運算包括節點i和j之間的不同類型的邊緣（E_ij）。 為了簡單起見，省略了節點的度數

總結

　　R-GCN代表了強大的圖神經體系結構，可對諸如KG之類的多關係數據進行編碼。 在以後的文章中，我將向您展示如何利用這種編碼能力在KG中執行特定任務，包括節點分類和連結預測。

　　如果要直接運行和測試代碼，可以在此處下載可用的筆記本：

　　githubgiuseppefutia/notebooks/blob/main/rgcn.ipynb

　　以下研究論文提供了有關R-GCN架構的更多詳細信息：

　　arxiv/1703.06103

　　作者：Giuseppe Futia

　　deephub翻譯組