【NeurIPS 2019】17篇論文，詳解圖的機器學習趨勢

板橋胡同37號 2020-01-15

展開全文

本文來自德國Fraunhofer協會IAIS研究所的研究科學家Michael Galkin，他的研究課題主要是把知識圖結合到對話AI中。

必須承認，圖的機器學習（Machine Learning on Graphs）已經成為各大AI頂會的熱門話題，NeurIPS 當然也不會例外。

在NeurIPS 2019上，僅主會場就有 100多個與圖相關的論文；另外，至少有三個workshop的主題與圖有關：

Graph Representation Learning (大約有100多篇論文)；
Knowledge Representation & Reasoning Meets Machine Learning (KR2ML)(也有50篇吧)；
Conversational AI

我們希望在接下來的這篇文章里，能夠盡可能完整地討論基于圖的機器學習的研究趨勢，當然顯然不會包括所有。目錄如下：

Hyperbolic Graph Embeddings 雙曲圖嵌入
Logics & Knowledge Graph Embeddings 邏輯和知識圖嵌入
Markov Logic Networks Strike Back 馬爾科夫邏輯網絡卷土重來
Conversational AI & Graphs 對話 AI 和圖
Pre-training and Understanding Graph Neural Nets 圖神經網絡的預訓練和理解
Conclusions 結論

1、雙曲圖嵌入

傳統的嵌入算法都是在“平坦”的歐氏空間中學習嵌入向量，為了讓向量有更高的表示能力，就會選擇盡量高的維數（50維到200維），向量之間的距離也是根據歐氏幾何來計算。

相比之下，雙曲算法中用到的是龐加萊（Poincare）球面和雙曲空間。在嵌入向量的使用場景里，可以把龐加萊球面看作一個連續的樹結構，樹的根節點在球的中心，枝干和葉子更靠近球面一些（如上面的動圖）。

這樣一來，雙曲嵌入表征層級結構的能力就要比歐氏空間嵌入的能力高得多，同時需要的維數卻更少。

不過，雙曲網絡的訓練和優化依然是相當難的。NeurIPS2018中有幾篇論文對雙曲神經網絡的構建做了深入的理論分析，今年在NeurIPS2019上我們終于看到了雙曲幾何和圖結構結合的應用。

論文 1：Hyperbolic Graph Convolutional Neural Networks
雙曲圖卷積神經網絡
論文地址：https://papers./paper/8733-hyperbolic-graph-convolutional-neural-networks.pdf
開源地址：https://github.com/HazyResearch/hgcn

論文 2：Hyperbolic Graph Neural Networks
雙曲圖神經網絡
論文地址：https://papers./paper/9033-hyperbolic-graph-neural-networks.pdf
開源：https://github.com/facebookresearch/hgnn

論文 1 和論文 2 兩者的思想是相似的，都希望把雙曲空間的好處和圖神經網絡的表達能力結合起來，只不過具體的模型設計有所區別。前一篇論文主要研究了節點分類和連接預測任務，相比于歐氏空間中的方法大大降低了錯誤率，在Gromov雙曲性分數較低（圖和樹結構的相似度）的數據集上表現尤其好。后一篇論文關注的重點是圖分類任務。

論文 3：Multi-relational Poincaré Graph Embeddings
多關系龐加萊圖嵌入
論文地址：https://papers./paper/8696-multi-relational-poincare-graph-embeddings.pdf

論文 3 在它們的多關系龐加萊模型（MuRP）的知識圖嵌入中用上了雙曲幾何。直覺上，正確的三元組客體應該落在主體附近的某個超球面中，相關的這些決策邊界是由學習到的參數描繪的。作者用來優化模型的是黎曼幾何SGD（大量數學警告）。在兩個標準的評測數據集 WN18RR 和 FB15k-237 上，MuRP 的效果比對比模型更好，因為它“更具備雙曲幾何”而且也更適用于樹結構（如果能像上面的論文一樣計算一下Gromov雙曲性分數就更好了）。更有趣的是，MuRP只需要40維，得到的準確率就和歐氏空間模型用100維甚至200維向量的結果差不多！明顯可以看到，雙曲空間的模型可以節省空間維度和存儲容量，同時還不需要有任何精度的犧牲。

我們還有一個雙曲知識圖嵌入比賽，獲獎方法名為 RotationH，論文見 https://grlearning./papers/101.pdf，其實和上面的雙曲圖卷積神經網絡論文的作者是同一個人。這個模型使用了雙曲空間的旋轉（思路上和RotatE https:///abs/1902.10197 模型相似，不過RotatE是復數空間的模型），也使用了可學習的曲率。RotationH 在WN18RR上刷新了最好成績，而且在低維的設定下也有很好的表現，比如，32維的RotationH就能得到和500維RotatE差不多的表現。

如果你碰巧在大學學習了sinh（雙曲正弦）、龐加萊球面、洛倫茲雙曲面之類的高等幾何知識但是從來都不知道在哪能用上的話，你的機會來了，做雙曲幾何+圖神經網絡吧。

2、邏輯和知識圖嵌入

如果你平時就有關注arXiv或者AI會議論文的話，你肯定已經發現，每年都會有一些越來越復雜的知識圖嵌入模型，每次都會把最佳表現的記錄刷新那么一點點。

那么，知識圖的表達能力有沒有理論上限呢，或者有沒有人研究過模型本身能對哪些建模、對哪些不能建模呢？看到這篇文章的你可太幸運了，下面這些答案送給你。

交換群：弱雞；阿貝爾群：大佬

論文4：Group Representation Theory for Knowledge Graph Embedding
鏈接：https://grlearning./papers/15.pdf

論文 4 從群論的角度來研究KG嵌入。結果表明，在復空間中可以對阿貝爾群進行建模，且證明了RotatE（在復空間中進行旋轉）可以表示任何有限阿貝爾群。

有沒有被“群論”、“阿貝爾群”這些數學名詞嚇到？不過沒關系，這篇文章里有對相關的群論知識做簡要介紹。

不過這個工作在如何將這個工作拓展到1-N或N-N的關系上，還有很大的gap。作者提出一個假設，即或許我們可以用四元數域H來代替復數空間C……

論文5：Quaternion Knowledge Graph Embeddings
鏈接：https://papers./paper/8541-quaternion-knowledge-graph-embeddings.pdf

……在這次NeurIPS' 19上，這個問題被 Zhang et al. 解決了。他們提出了QuatE，一個四元數KG嵌入模型。

什么是四元數？這個需要說清楚。簡單來說，復數有一個實部，一個虛部，例如a+ib；而四元數，有三個虛部，例如 a+ib+jc+kd。相比復數會多出兩個自由度，且在計算上更為穩定。

QuatE將關系建模為4維空間（hypercomplex space）上的旋轉，從而將complEx 和 RotatE統一起來。在RotatE中，你有一個旋轉平面；而在QuatE中，你會有兩個。此外，對稱、反對稱和逆的功能都保留了下來。與RotatE相比，QuatE在 FB15k-237上訓練所需的自由參數減少了 80%。

我上面并沒有從群的角度來分析這篇文章，不過若感興趣，你可以嘗試去讀原文：

四元數域的旋轉

論文 6：Quantum Embedding of Knowledge for Reasoning
鏈接：https://papers./paper/8797-quantum-embedding-of-knowledge-for-reasoning.pdf

論文 6 提出了 Embed2Reason（E2R）的模型，這是一種受量子邏輯啟發的量子KG嵌入方法。該方法可以嵌入類（概念）、關系和實例。

不要激動，這里面沒有量子計算。量子邏輯理論（QL）最初是由伯克霍夫和馮諾依曼于1936年提出，用于描述亞原子過程。E2R的作者把它借用過來保存KG的邏輯結構。

在QL中（因此也是E2R中），所有一元、二元以及復合謂詞實際上都是某些復雜向量空間的子空間，因此，實體及其按某種關系的組合都落在了特定的子空間內。本來，分布定律a AND（b OR c）=（a AND b）OR（a AND c）在QL中是不起作用的。但作者用了一個巧妙的技巧繞開了這個問題。

作者在論文中還介紹了如何使用QL對來自描述邏輯（DL）的術語（例如包含、否定和量詞）進行建模！

實驗結果非常有趣：在FB15K上，E2R產生的Hits @ 1高達96.4％（因此H@10也能達到）；不過在WN18上效果不佳。

事實證明，E2R會將正確的事實排在首位或排在top10以下，這就是為什么在所有實驗中H @ 1等于H @ 10的原因。

補充一點，作者使用LUBM作為演繹推理的基準，該演繹推理包含了具有類及其層次結構的本體。實際上，這也是我關注的焦點之一，因為標準基準數據集FB15K（-237）和WN18（RR）僅包含實例和關系，而沒有任何類歸因。顯然，大型知識圖譜具有數千種類型，處理該信息可以潛在地改善鏈接預測和推理性能。我還是很高興看到有越來越多的方法（如E2R）提倡將符號信息包含在嵌入中。

論文 7：Logical Expressiveness of Graph Neural Networks
鏈接：https://grlearning./papers/92.pdf

讓我們繼續來考察圖神經網絡的邏輯表達。

論文 7 中對哪些GNN架構能夠捕獲哪個邏輯級別進行了大量的研究。目前為止，這個研究還僅限于一階邏輯的兩變量片段FOC_2，因為FOC_2連接到用于檢查圖同構的Weisfeiler-Lehman（WL）測試上。

作者證明，聚合組合神經網絡（AC-GNN）的表達方式對應于描述邏輯ALCQ，它是FOC_2的子集。

作者還進一步證明，如果我們添加一個獨處成分，將GNN轉換為聚合組合讀出GNN（ACR-GNN），則FOC_2中的每個公式都可以由ACR-GNN分類器捕獲。

這個工作怎么說呢？簡直是不能再棒了！

論文 8：Embedding Symbolic Knowledge into Deep Networks
鏈接：https://papers./paper/8676-embedding-symbolic-knowledge-into-deep-networks.pdf

論文 8 提出了模型LENSR，這是一個具有語義正則化的邏輯嵌入網絡，它可以通過圖卷積網（GCN）將邏輯規則嵌入到d-DNNF（決策確定性否定范式）當中。

在這篇文章中，作者專注于命題邏輯（與上述論文中更具表現力的描述邏輯相反），并且表明將AND和OR的兩個正則化組件添加到損失函數就足夠了，而不用嵌入此類規則。

這個框架可以應用在視覺關系預測任務中，當給定一張圖片，你需要去預測兩個objects之間的正確關系。在這篇文章中，Top-5的精確性直接將原有84.3#的SOTA提升到92.77%。

Source: Xie et al

3、馬爾科夫邏輯網絡卷土重來

馬爾科夫邏輯網絡（Markov Logic Network）的目標是把一階邏輯規則和概率圖模型結合起來。然而，直接使用馬爾科夫邏輯網絡不僅有拓展性問題，推理過程的計算復雜度也過高。

近幾年來，用神經網絡改進馬爾科夫邏輯網絡的做法越來越多，今年我們能看到很多有潛力的網絡架構，它們把符號規則和概率模型結合到了一起。

論文9：Probabilistic Logic Neural Networks for Reasoning
鏈接：https://papers./paper/8987-probabilistic-logic-neural-networks-for-reasoning.pdf

論文 9 提出了 pLogicNet，這個模型是用來做知識圖推理的，而且知識圖嵌入和邏輯規則相結合。模型通過變差EM算法訓練（實際上，這幾年用EM做訓練&模型優化的論文也有增加的趨勢，這事可以之后單獨開一篇文章細說）。

論文的重點是，用一個馬爾科夫邏輯網絡定義知識圖中的三元組上的聯合分布（當然了，這種做法要對未觀察到的三元組做一些限制，因為枚舉出所有實體和關系上的所有三元組是做不到的），并給邏輯規則設定一個權重；你可以再自己選擇一個預訓練知識圖嵌入（可以選TransE或者ComplEx，實際上隨便選一個都行）。在推理步驟中只能怪，模型會根據規則和知識圖嵌入找到缺失的三元組，然后在學習步驟中，規則的權重會根據已見到的、已推理的三元組進行更新。pLogicNet 在標準的連接預測測試中展現出了強有力的表現。我很好奇如果你在模型里選用了 GNN 之類的很厲害的知識圖嵌入會發生什么。

論文 10：Neural Markov Logic Networks
鏈接：https://kr2ml./2019/papers/KR2ML_2019_paper_18.pdf

論文 10 介紹了一個神經馬爾科夫邏輯網絡的超類，它不需要顯式的一階邏輯規則，但它帶有一個神經勢能函數，可以在向量空間中編碼固有的規則。作者還用最大最小熵方法來優化模型，這招很聰明（但是很少見到有人用）。但缺點就是拓展性不好，作者只在很小的數據集上做了實驗，然后他表示后續研究要解決的一大挑戰就是拓展性問題。

論文11：Can Graph Neural Networks Help Logic Reasoning?
鏈接：https://kr2ml./2019/papers/KR2ML_2019_paper_22.pdf

最后，論文 11 研究了GNN和馬爾科夫邏輯網絡在邏輯推理、概率推理方面的表現孰強孰弱。作者們的分析表明，原始的GNN嵌入就有能力編碼知識圖中的隱含信息，但是無法建模謂詞之間的依賴關系，也就是無法處理馬爾科夫邏輯網絡的后向參數化。為了解決這個問題，作者們設計了ExpressGNN架構，其中有額外的幾層可調節的嵌入，作用是對知識圖中的實體做層次化的編碼。

4、對話 AI 和圖

好了，硬核的機器學習算法講得差不多了，下面我們看點輕松的，比如NLP應用。和NeurIPS正會一起開的workshop里有很多有趣的對話AI+圖的論文。

論文12：Multi-domain Dialogue State Tracking as Dynamic Knowledge Graph Enhanced Question Answering
鏈接：http:///workshops/neurips19-Conversational-AI/Papers/51.pdf

這篇論文提出了一個通過問答追蹤對話進度（Dialogue State Tracking via Question Answering (DSTQA)）的模型，用來在MultiWOZ環境中實現任務導向的對話系統，更具體地，就是通過對話幫助用戶完成某個任務，任務一共分為5個大類、30個模版和超過4500個值。它基于的是問答（Question Answering ）這個大的框架，系統問的每個問題都要先有一個預設模版和一組預設的值，用戶通過回答問題確認或者更改模版中的預設值。

有個相關的假說提出，同一段對話中的多個模版、多組值之間并不是完全獨立的，比如，你剛剛訂好五星級酒店的房間，然后你緊接著問附近有什么餐館，那很有可能你想找的餐館也是中高檔的。論文中設計的整個架構流程很繁瑣，我們就只講講他們的核心創新點吧：

首先，作者們把對話狀態建模為一個根據對話內容逐漸擴充的動態知識圖。圖中的節點由大類、模版和值構成，建立節點之間關系的過程也利用了上面那個假說，就是因為不同的模版之間有一些值可以是相同的、部分重疊或者是有關聯的。
其次，用一個圖注意力網絡（Graph Attention Net）學習為圖中的節點分配權重，網絡的輸出也會被送入一個門機制，用來決定要在問題文本中表現出圖的多大的一部分。
作者們也使用了角色嵌入，這樣模型可以由系統的話語和用戶的話語共同訓練
最后，作者們同時使用了CharCNN和ELMO嵌入來做對話文本內容的編碼

DSTQA 在 MultiWOZ 2.0 和 MultiWOZ 2.0 上都刷新了最好成績，在 WOZ 2.0 上也和當前的最好方法不相上下。根據作者們的誤差分析，主要的丟分點來自于真實值的標注有一些不準確的 —— 大規模眾包數據集中就是經常會發生這種情況，沒什么辦法，攤手

論文 13：Neural Assistant: Joint Action Prediction, Response Generation, and Latent Knowledge Reasoning
鏈接：http:///workshops/neurips19-Conversational-AI/Papers/32.pdf

論文13 介紹了一個神經網絡助理模型，這個對話系統架構不僅能考慮到對話歷史，也能利用到知識庫中的事實信息。系統架構可以看作是Transformer架構的拓展，它會編碼對話歷史中的文本；知識庫中的內容是簡單的單詞三元組比如（餐館A，價格，便宜）（沒有 Wikidata 那種花哨的知識圖模式），這些三元組也會被Transformer編碼。最后，解碼器會同時處理歷史文本編碼和知識圖編碼，用來生成輸出語句，以及決定是否要進行下一步動作。

之前的論文中有很多人在所有的知識庫三元組上計算softmax（只要知識庫稍微大一點，這種做法就非常低效），這篇論文就沒這么做，他們根據知識庫中的實體是否在真實值回答中出現的情況做弱監督學習。他們的架構在 MultiWOZ 設置下比原本的Transformer架構得到更好的表現，預測動作以及實體出現的F1分數超過90%。不過，他們的進一步分析顯示出，知識庫中的條目超過一萬條之后準確率就會開始快速下降。所以，嗯，如果你有心思把整個Wikidata的70億條三元組都搬過來的話，目前還是不行的。

論文 14：A Comprehensive Exploration on WikiSQL with Table-Aware Word Contextualization
鏈接：https://kr2ml./2019/papers/KR2ML_2019_paper_8.pdf

當你設計面向任務的系統的時候，往往有很多內容是無法長期留在內存里的，你需要把它們存在外部存儲中，然后需要的時候去檢索。如果是圖數據，你可以用SPARQL或者Cypher建立圖數據庫來操作；或者用經典的SQL數據庫也行。對于后一種情況，最近出現了很多新任務（https:///@mgalkin/knowledge-graphs-nlp-emnlp-2019-part-i-e4e69fd7957c），其中WikiSQL 是第一批引起了學術研究人員興趣的。

如今，只經過了不到兩年的時間，我們就已經可以說這個數據集已經基本被解決了，基于神經網絡的方法也獲得了超過人類的表現。這篇論文中提出了語義解析模型 SQLova ，它通過BERT編碼問題和表頭、用基于注意力的編碼器生成SQL查詢（比如 SELECT 命令、WHERE 條件、聚合函數等等）、然后還能對生成的查詢語句進行排序和評價。

作者們在論文中指出，不使用語義解析、只使用BERT的暴力編碼的話，效果要差得多，所以語言模型還是不能亂用。模型的測試準確率達到了90%（順便說一句，還有一個叫 X-SQL 的模型拿到了接近92%的準確率，https:///pdf/1908.08113.pdf），而人類的準確率只有88%；根據錯誤分析來看，系統表現的最大瓶頸基本就是數據標注錯誤了（和上面那個MulitWOZ的例子類似）。

除此之外我還有幾篇NLP相關的論文想推薦給大家：

Relational Graph Representation Learning for Open-Domain Question Answering

用于開放領域問答的關系圖表征學習
https://grlearning./papers/123.pdf
這篇論文提出了一個帶有注意力的關系GNN，能夠解決基于普通文本的以及把WebQuestionsSP外掛數據集作為知識圖的問答任務。

Populating Web Scale Knowledge Graphs using Distantly Supervised Relation Extraction and Validation

通過遠距離有監督關系提取和驗證，制作大規模網絡知識圖
https://kr2ml./2019/papers/KR2ML_2019_paper_11.pdf
這篇論文解決了如何同時提取文本中的關系并立即通過預訓練的知識圖嵌入對候選的知識圖做實事檢查。這個方法可以拓展到包含百萬級三元組的知識圖上（比如 Common Crawl — DBpedia 語料庫有超過六百萬個三元組）

Incorporating rules into end-to-end dialog systems

在端到端對話系統中集成規則
http:///workshops/neurips19-Conversational-AI/Papers/43.pdf
作者們研究了如何把規則集成到端到端的對話系統以及上下文中，目的是讓生成的文本更多樣化，比如，如果用戶已經要求查詢某個數據了，系統就不會重新和用戶打招呼、重新讓用戶選任務模版。其中表現最好的一種配置會把對話上下文和規則編碼到一起。他們的方法通用性很好，可以和各種生成回答的網絡架構共同使用。

5、圖神經網絡的預訓練和理解

在這一節，我會介紹一些從更通用的角度研究GNN的論文，包括一些研究GNN模型的可解釋性的論文。

論文 15：Pre-training Graph Neural Networks
鏈接：https:///abs/1905.12265

這篇論文挺火的，這是提出并解釋預訓練圖神經網絡框架的首批論文之一。我們都很熟悉預訓練語言模型了，就是先在海量文本上預訓練一個語言模型，然后在某個具體任務上做精細調節。從思路上來說，預訓練圖神經網絡和預訓練語言模型很像，問題重點在于這種做法在圖上能不能行得通。簡單的答案就是：可以！不過使用它的時候還是要小心謹慎。

對于用預訓練模型在節點級別（比如節點分類）和圖級別（比如圖分類）捕捉結構和領域知識，作者們都在論文中提出了有價值的見解，那就是，對于在節點級別學習結構屬性來說，內容預測任務的重點是在負采樣的幫助下根據嵌入預測一個節點周邊的節點（仿佛很像word2vec的訓練對不對），其中通過掩蔽的方式，隨機遮住一些節點/邊的屬性，然后讓網絡預測它們。

作者們也說明了為什么聚合-合并-讀出的GNN結構（Aggregate-Combine-Readout GNN）的網絡更適合這類任務，是因為它們支持用一個置換不變的池化函數獲取一個圖的全部表征。實驗表明，只使用圖級別的有監督預訓練時，向下游任務遷移會造成表現下降，所以需要同時結合節點級別和圖級別的表征。把特征這樣組合之后能在40種不同的預測任務中帶來6%到11%的ROC-AUC提升。

所以，這代表圖上的遷移學習時代已經正式來到我們面前了嗎？會有更多優秀的研究人員為預訓練GNN模型編寫優秀的庫，讓大家都可以更方便地使用預訓練GNN嗎？

論文 16：Graph Transformer Networks
鏈接：https://papers./paper/9367-graph-transformer-networks.pdf

這篇論文為異質圖設計了圖Transformer（Graph Transformer）架構。異質圖是指，圖中含有多種類型的節點和邊。圖Transformer網絡（GTN）中通過1x1卷積來獲取元路徑（邊組成的鏈）的表征。接著，他們思路的關鍵在于，在此基礎上再生成一系列任意長度的新的元路徑（元-元路徑？），長度可以由Transformer層的數量指定，這些元路徑理論上可以為下游任務編碼更多有有價值的信號。作者們的實驗中，GTN憑借和圖注意力網絡（Graph Attention Nets）相近的參數數量刷新了節點任務分類的最好成績。

論文 17：GNNExplainer: Generating Explanations for Graph Neural Networks
鏈接：https://papers./paper/9123-gnnexplainer-generating-explanations-for-graph-neural-networks.pdf

這里要介紹的最后一篇論文瞄準的是“圖神經網絡的可解釋性”這個重要任務，論文中提出了用來解釋圖神經網絡的輸出的GNN Explainer，這是一個模型無關的框架，它能為任意任務上的、任意一個基于圖的模型的預測結果做出解釋。比如說，你在用圖注意力網絡做節點分類/圖分類任務，然后你想看看你的問題的可解釋的結果，那你直接用GNN Explainer就好了。

他們的設計思路是，GNN Explainer會讓模型預測和結合圖、節點特征形成的子圖結構之間的共同信息最大化（當然了，生成子圖的過程需要一些優化技巧，畢竟檢測所有可能的子圖是辦不到的）。這個框架給出的解釋的形式是，它會返回一個帶有最重要的通路和特征的子圖，這就很容易被人類解讀了。論文里有一些很清晰的示例圖（如下方）。很棒的論文，鼓掌！