本文介紹的是ICLR2020入選論文《INDUCTIVE MATRIX COMPLETION BASED ON GRAPH NEURAL NETWORKS》（基於圖神經網絡的歸納矩陣補全）。文章來自華盛頓大學聖路易斯分校博士、Facebook AI 研究院研究科學家張牧涵。

文 | 張牧涵

編 | 叢末

下載鏈接：
https://openreview.net/pdf?id=ByxxgCEYDS

代碼地址：
https://github.com/muhanzhang/IGMC

1 摘要

矩陣補全(Matrix Completion)被廣泛應用於推薦系統中。傳統的矩陣分解(Matrix Factorization)方法為轉導推理模型(Transductive Model)，所學習到的embedding不能推廣到訓練集中未出現過的用戶(user)和商品(item)。而 Inductive Matrix Completion (IMC) 模型使用內容信息(content)來補全矩陣，缺點是對內容的質量要求很高，且在內容質量不好的情況下會導致遠低於矩陣分解的性能。

本文提出一種新的Inductive Graph-based Matrix Completion (IGMC) 模型，在保持歸納推理(inductive reasoning)的同時，完全不藉助任何內容信息。能不藉助內容信息達成歸納推理的秘訣就在於子圖結構。IGMC為每一個(user, item) pair提取一個包含子圖(enclosing subgraph)，並用圖神經網絡(graph neural network)訓練一個由子圖結構映射到用戶對商品評分(rating)的回歸模型。

IGMC在多個數據集上取得了最先進的性能；它不僅能夠適用於沒在訓練集中出現的用戶和商品，更可以遷移(transfer)到新數據上。我們使用一個在MovieLens上訓練的IGMC模型去預測豆瓣電影評分，取得了非常好的性能，甚至好於許多專門在豆瓣數據上訓練的模型。

2 動機

只要我們把每個user或item看成一個節點(node)，每個rating看成一個邊(edge)，則矩陣補全可以看成是在二分圖(bipartite graph)上的鏈路預測(link prediction)問題。不同於傳統鏈路預測只關注預測存在性(link existence)，這裡我們要預測鏈路的值(link value)，也就是用戶對商品的評分。

首先，我們定義包含子圖(enclosing subgraph)。對一個(user, item) pair，它們的h階包含子圖是由該user、 item，所有該user、 item的h-hop內鄰接節點（包含h-hop），以及所有這些節點之間的邊組成的圖。這樣的一個包含子圖內存在大量對於預測評分有用的信息。舉例來說，即使只用一階包含子圖，我們也可以獲得比如用戶平均評分、商品平均評分、商品累計評價次數，以及大量的基於路徑(path)等的結構信息。參加圖一。

一個簡單的基於路徑的結構特徵如下，假如我們想知道用戶u0對於商品v0的評分，我們可以看有多少和u0品味相似的用戶u1對v0打了高分；而品味相似可以用是否這個u1和u0曾經都給某個其它的商品v1打過高分。總結下來，這樣的一個路徑特徵即為：

我們可以通過查有多少這樣的路徑來估算u0是否會給v0高分。而且，所有這樣的路徑都被包含在一階包含子圖(1-hop enclosing subgraph)中。

我們相信類似這樣的結構特徵數不勝數。因此，與其手動定義大量這樣的啟發式特徵(heuristics)，不如直接將一階包含子圖輸入給一個圖神經網絡，用圖神經網絡強大的圖特徵學習能力來自動學習更通用的、更有表達能力的特徵。我們使用圖神經網絡訓練一個由包含子圖映射到評分的回歸模型，實驗證明，這種新的方法可以精確地預測評分。

3 方法

提取每個包含子圖後，我們首先要對其中的節點進行標註(node labeling)。目的是為了區分子圖中節點的不同角色。比如我們要區分目標節點(target user/item)和背景節點 (context nodes)。目標節點標示出我們到底要預測子圖中哪一對(user, item)之間的評分。同時，我們可以區分不同階的鄰居節點，比如一階鄰居(1-hop neighbors)和二階鄰居(2-hop neighbors)對目標節點的貢獻程度並不相同。

我們採用了一個簡單的做法，對目標用戶(target user)，我們標註為0，對目標商品(target item)，我們標註為1；對i-hop的背景用戶我們標註為2i，對i-hop的背景商品我們標註為2i+1。之後，我們將這些標註轉化為one-hot encoding vector，作為每個節點的初始特徵輸入給圖神經網絡。

在圖神經網絡(GNN)中，我們採用relational graph convolutional operator (R-GCN)作為卷積層，因為R-GCN可以從邊類型中學習。

其中，代表節點在第層的特徵向量，和為可學習的參數，代表rating(一般從中選擇，代表與節點以類型邊相連的鄰居節點。

多層卷積後，我們將每一層結果相連得到每個節點的最終表示：

最後，我們取目標用戶和目標商品的相連的表示作為這個包含子圖的最終表示：

並訓練一個兩層神經網絡(MLP)從子圖表示回歸到目標評分(rating)。

4 實驗結果

我們僅使用一階包含子圖訓練IGMC。首先，在Table 2中我們展示了在Flixster, Douban和YahooMusic上的RMSE性能。我們的IGMC模型取得了state-of-the-art性能，超過了近期的其他基於圖神經網絡的模型。

在Table 3中我們展示IGMC在ML-100K 和 ML-1M上的性能。在ML-100K上，IGMC取得了最好的性能，和之前領先的一種轉導模型GC-MC性能相同。但是注意，GC-MC使用了額外的內容(content)特徵，而IGMC完全依靠子圖結構。GC-MC在不使用content的情況下RMSE為0.910。在ML-1M上，IGMC仍落後於其他一些轉導推理的方法。我們接下來深入研究這一問題。

對於ML-1M數據集，我們分別將訓練矩陣稀疏為0.2, 0.1, 0.05, 0.01和0.001倍。Figure 2比較了GC-MC和IGMC在不同稀疏程度下的性能對比。我們發現，雖然IGMC在sparsity=1時落後於GC-MC，但是此後IGMC在不同sparsity下都優於GC-MC，而且矩陣越稀疏，性能優勢越明顯。我們猜測，基於子圖特徵學習的IGMC對稀疏矩陣更魯棒；而基於矩陣分解等的轉導模型需要矩陣較為緻密(dense)才能有好的性能。這也暗示了IGMC在數據稀疏的推薦系統中的潛力。

最後，我們測試IGMC的遷移學習性能。我們直接將ML-100K上訓練的IGMC模型用於預測Flixster, Douban和YahooMusic。出人意料，遷移的IGMC模型取得了極強的性能，甚至好於一些專門在這三個數據集上訓練的模型。這說明，不同推薦任務共享了大量相同的子圖模式。

為驗證這點，我們可視化了一些真實的包含子圖，見Figure 3。可以發現，高評分和低評分對應的包含子圖確實有着明顯的不同；且不同數據集之間共享許多相似的子圖模式。

5 總結

本文提出了一種通過子圖特徵進行歸納推理(inductive reasoning)的矩陣補全模型，IGMC。

通過本文我們證明了僅從一階包含子圖學習圖特徵即可在許多數據集上達到領先的性能，這似乎暗示更高階的連接關係並沒有特別多的額外價值。

此外，我們也證明了不藉助於內容(content)的inductive matrix completion (IMC)方法是同樣可行的且大大超越了傳統的藉助內容的IMC方法。IGMC的許多特性，比如遷移性、稀疏魯棒性等都暗示了它的強大潛力。我們希望IGMC能為矩陣補全和推薦系統領域帶來新的想法和啟發。

另外，藉助子圖特徵的鏈路預測方法已經獲得了巨大的成功，參見我們的另一篇文章「Link Prediction Based on Graph Neural Networks」：

http://papers.nips.cc/paper/7763-link-prediction-based-on-graph-neural-networks.pdf

ICLR 2020 系列論文解讀

0、ICLR 2020 會議動態報道

疫情嚴重，ICLR2020 將舉辦虛擬會議，非洲首次 AI 國際頂會就此泡湯

疫情影響，ICLR 突然改為線上模式，2020年將成為頂會變革之年嗎？