論文題目：Modeling Relational Data with Graph Convolutional Networks
論文來源：ESWC 2018
論文連結：https://arxiv.org/abs/1703.06103
代碼連結：https://github.com/tkipf/relational-gcn
關鍵詞：知識圖譜，GCN，基函數分解，塊對角分解
文章目錄
- 1 引言
- 2 神經關系模組化
-
- 2.1 Relational Graph Convolutional Networks
- 2.2 Regularization
- 3 實體分類
- 4 連結預測
- 5 實驗
提出關系圖卷積網絡(R-GCNs)，用于兩個知識庫的補全任務：連結預測、實體分類(恢複丢失的實體屬性)。
1 引言
知識圖譜中存儲了大量的知識，可用于問答系統、資訊檢索等下遊任務。但是許多知識圖譜都是不完備的，例如DBPedia、Wikidata、Yago，有許多資訊的缺失，這會影響其在下遊任務中的應用。預測知識庫中缺失的資訊是統計關系學習(SRL)的主要研究内容。
考慮兩個基本的SRL任務：連結預測(恢複缺失的三元組)、實體分類(為實體配置設定類型或類别屬性)。
許多缺失的資訊都是隐含在通過鄰居結構編碼的圖中。作者從這一思想出發，設計了一個編碼器，編碼關系網絡中的實體，并應用于這兩個任務中。
實體分類模型：對圖上的每個節點使用softmax分類器，R-GCN得到的節點表示作為分類器的輸入。這個模型以及R-GCN的參數都是通過優化交叉熵損失學習得到的。
連結預測模型：可視為由一個encoder和一個decoder組成的自編碼器。
1）encoder：R-GCN為實體生成隐層的特征表示；
2）decoder：張量的分解模型，利用encoder生成的表示預測邊的label。
按理說decoder可以使用任何一種形式的分解/打分函數，作者使用了最簡單并最有效的分解方法：DistMult。
貢獻
（1）第一個将GCN用于模組化關系型資料的工作，尤其是針對連結預測和實體分類任務。
（2）在R-GCN中使用了參數共享和稀疏限制，應用于有大量關系的多個圖。
（3）實驗證明，以DistMult為例，使用一個在關系圖中執行多步資訊傳播的encoder模型來豐富矩陣分解的模型，可以顯著提高其性能。
2 神經關系模組化
定義有向的且有标簽的多個圖為 G = ( V , E , R ) G=(\mathcal{V}, \mathcal{E}, \mathcal{R}) G=(V,E,R)，節點為 v i ∈ V v_i\in \mathcal{V} vi∈V，有标簽的邊為 ( v i , r , v j ) ∈ E , r ∈ R (v_i,r,v_j)\in \mathcal{E}, r\in \mathcal{R} (vi,r,vj)∈E,r∈R。
2.1 Relational Graph Convolutional Networks
模型的動機是使用圖中局部的鄰居資訊，将GCN擴充到大規模的關系型資料中。可以了解成是一個簡單可微的消息傳遞架構：
其中 M i \mathcal{M}_i Mi表示節點 v i v_i vi的傳入消息集合，通常為入度的邊緣集。 g m ( ⋅ , ⋅ ) g_m(\cdot, \cdot) gm(⋅,⋅)可以是類似神經網絡的函數，也可以是簡單的線性轉換。
這種方式可以有效地聚合編碼局部鄰域結構的特征，并且在圖分類和基于圖的半監督學習等任務中表現出了很好的效果。
受上述架構的啟發，作者定義了如下的消息傳播模型：
其中 N i r \mathcal{N}^r_i Nir表示與節點 i i i有 r r r類型連邊的鄰居節點。 c i , r c_{i,r} ci,r是針對特定問題的歸一化常數，可以學習得到也可以預先設定（例如 c i , r = ∣ N i r ∣ c_{i,r}=|\mathcal{N}^r_i| ci,r=∣Nir∣）。
使用 W h j Wh_j Whj這種線性的轉換形式的優點：（1）不需要儲存中間過程的基于邊的表示資訊，節省了存儲空間；（2）可進行向量化的運算。
和正規的GCN不同的是，作者引入的是relation-specific的轉換，依賴于邊的類型以及邊的方向。為了保證第 l l l層的節點表示資訊可以傳遞給第 l + 1 l+1 l+1層的節點，作者為每個節點都添加了一個特殊類型的關系——自連接配接。
式（2）對所有節點進行并行計算，就可以實作神經網絡層的更新，堆疊多層可以捕獲多步之間的關系依賴。将這個圖編碼模型就是R-GCN。圖1描述了使用R-GCN模型對圖中一個節點的更新過程。
2.2 Regularization
式（2）應用于多關系型資料面臨的主要問題就是：随着圖中關系數量的增長，參數的數量迅速增長。這很容易導緻過拟合。
有兩種方法可以解決參數量過大的問題：
- 在權重矩陣間共享參數
- 在權重矩陣中進行稀疏限制
針對這兩種政策，作者引入了兩種方法，用于R-GCN層權重的正則化：基函數分解(basis-decomposition) 和 塊對角分解(block-diagonal-decomposition)。
（1）基函數分解
W r ( l ) W^{(l)}_r Wr(l)定義為基變換 V b ( l ) ∈ R d ( l + 1 ) × d ( l ) V^{(l)}_b\in \mathbb{R}^{d^{(l+1)}\times d^{(l)}} Vb(l)∈Rd(l+1)×d(l)的線性組合， a r b ( l ) a^{(l)}_{rb} arb(l)是系數，隻有系數依賴于關系 r r r。
（2）塊對角分解
W r ( l ) W^{(l)}_r Wr(l)求得後是塊對角矩陣：
塊對角分解就是(DistMult)解碼器中使用的對角稀疏限制的推廣。
基函數分解是實作不同關系類型間權重共享的一種形式；塊分解可看成是對每種關系的權重矩陣的稀疏限制。
塊分解的結構認為潛在的特征可以被分成多組變量，組内的聯系比組間的更加緊密。
對于高度多關系類型的資料（例如 知識庫），這兩種分解的方式都減少了參數。
R-GCN模型的流程如下：像式（2）定義的那樣，堆疊 L L L層，目前層的輸出為下一層的輸入。若沒有給定節點的特征，則為每個節點賦予唯一的one-hot向量，作為第一層的輸入。對于塊分解，通過一層線性變換将one-hot向量映射成稠密的表示。
本文隻考慮節點無特征的方法，當然GCN類型的方法可以結合預定義的特征向量。
3 實體分類
堆疊多層R-GCN層，最後一層的輸出後再過一個softmax函數。忽略未标注的節點，對所有已标注的節點最小化如下的交叉熵損失：
其中 Y \mathcal{Y} Y是有标簽的節點集合， h i k ( L ) h^{(L)}_{ik} hik(L)是第 i i i個已标注的節點在第 k k k個位置的輸出， t i k t_{ik} tik表示對應的ground truth标簽。如圖1b所示。
4 連結預測
知識庫由有向的有标簽的圖 G = ( V , E , R ) G=(\mathcal{V}, \mathcal{E}, \mathcal{R}) G=(V,E,R)組成。通常邊的集合不是完全給定的，隻給定了不完整的邊集合 E ^ \mathcal{\hat{E}} E^。連結預測的目标就是給定可能的邊 ( s , r , o ) (s, r, o) (s,r,o)，計算打分函數 f ( s , r , o ) f(s, r, o) f(s,r,o)，判斷邊屬于$ \mathcal{E}$的可能性。
為了解決這一問題，引入如圖1 c所示的自編碼器模型，由實體編碼器和打分函數(decoder)組成。
編碼器将每個實體 v i v_i vi映射成實值向量 e i ∈ R d e_i\in \mathbb{R^d} ei∈Rd。
解碼器根據編碼器得到的節點表示資訊，重構圖中的邊。具體而言，解碼器使用打分函數為三元組 ( s u b j e c t , r e l a t i o n , o b j e c t ) (subject, relation, object) (subject,relation,object)打分，判斷這個三元組對應的邊在圖中是否存在。現有的連結預測的方法幾乎都采用了這種方式。
本文的方法和先前方法的主要差別在于對編碼器的依賴。先前的方法大多對每個節點 v i v_i vi使用單一的、實值的向量 e i e_i ei，直接在訓練過程中優化。本文的方法是使用帶有 e i = h i ( L ) e_i=h^{(L)}_i ei=hi(L)的R-GCN編碼器計算表示。
實驗中，使用DistMult分解作為打分函數。其中，每個關系 r r r都和一個對角矩陣 R r ∈ R d × d R_r\in \mathbb{R^{d\times d}} Rr∈Rd×d相關聯，對三元組 ( s , r , o ) (s, r, o) (s,r,o)的評分計算如下：
訓練時使用負采樣技術，随機替換正樣本的subject或object，生成 w w w個負樣本。使用交叉熵損失，讓模型對正樣本的打分值比負樣本高：
其中， T \mathcal{T} T是正樣本和負樣本的三元組集合， l l l是logistic sigmoid函數， y y y是正負樣本的訓示函數。
5 實驗
資料集：
實驗任務：連結預測、實體分類
實驗結果：
（1）實體分類
（2）連結預測