論文標題：

DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks

論文地址：

https://arxiv.org/pdf/2010.03250.pdf

代碼鏈接：

https://github.com/AutoML-Research/DiffMG

摘要

圖數據的表示學習與圖神經網絡是當前重要且熱門的研究方向，不僅在學術界取得了很高的關注度（以圖表示學習的兩位國際領軍學者為例）：

▲ 圖1 Jure Leskovec的Google Scholar頁面

▲?圖2 Michael Bronstein的Google Scholar頁面

在工業界也有廣泛的應用（例如在阿里巴巴、Pinterest 等互聯網公司中應用的基于圖表示學習的大規模推薦算法 [1, 2]）。

在這篇文章中，我們提出了一種在異質圖（Heterogeneous Information Networks (HINs)）[3] 上進行表示學習的新方法。我們的方法受到了神經網絡架構搜索（Neural Architecture Search (NAS)）[4]?的啟發。NAS 旨在自動地搜索出適應于數據集與下游任務的神經網絡結構。對于 HINs，我們希望可以使圖神經網絡（Graph Neural Networks (GNNs)）[5] 自動地選擇利用異質圖中與下游任務相關的語義信息。

具體地，我們的方法自動地搜索一個與異質網絡和下游任務均匹配的“元圖”（Meta Graph）[6] 來決定 GNNs 如何沿著異質網絡中不同類型的邊傳播信息。我們設計了一個新穎且富有表達力的搜索空間（Search Space），這一搜索空間具有有向無環圖的形式（Directed Acyclic Graph (DAG)），以充分表示可能的“元圖”。

我們定義的搜索空間很大，為了高效地進行搜索，我們進一步提出了一個創新的可微搜索算法，使得搜索所需的時間與訓練一個單獨的 GNN 相當。我們在若干個真實的異質數據集上測評了我們的方法在節點分類（Node Classification）任務和推薦（Recommendation）任務中的表現，實驗結果表明，相比于已有的為異質圖設計的 GNNs，我們的方法可以在實現更好效果的同時保持高效率。

背景介紹

異質圖（HINs）廣泛地存在于真實世界的許多應用場景中，如互聯網數據挖掘、推薦系統、生物信息，以表示眾多個體間復雜的連接關系。相比于同質信息網絡，除了網絡的拓撲結構外，異質圖同時含有豐富的語義信息。這些語義信息包括節點與邊的類型等。例如，在一個電影推薦數據集中，節點可以分為電影、演員、導演等類型。這些附加的語義信息可以幫助下游任務，如何更好地利用它們是異質圖表示學習的一個重要挑戰。

▲ 圖3 異質圖示例

近年來，GNNs 在圖表示學習的許多任務上都取得了顯著的進展。然而，現有的方法在處理異質圖時仍有不足之處。例如，經典的 GCN 模型 [7] 認為所有鄰居節點是同質的，無法區分節點的不同類型，因此不能利用 HINs 中含有的語義信息。

一些專門為 HINs 設計的 GNNs，例如 HAN [8]、MAGNN [9]，依賴手工設計的規則“元路徑”（Meta Path）[10] 來選取從哪些鄰居節點收集信息。這類模型的主要限制在于，手工設計的規則需要領域的先驗知識，因此它們很難應用在來自新的、復雜的領域的數據集（例如，為各種各樣的化學粒子設計規則是極其困難的）。

另一個較新的方法 HGT [11] 借鑒了 Transformer 結構，對不同類型的節點和邊計算 attention，以避免手工設計規則。然而，HGT 的參數量大，訓練速度慢，這一問題在處理大規模的圖數據時會變得尤為明顯。

此外，即使 attention 可以對不同類型的鄰居節點賦予不同的權重，它仍然可能收集到與下游任務不相關的語義信息。例如，當我們想要預測學術網絡中作者的研究領域（CV、NLP 等）時，作者所在的機構/學校是無關的信息（噪聲），收集它們可能不利于下游的預測任務。綜上所述，如何使 GNNs 能自動地、高效地挖掘 HINs 中與下游任務相關的語義信息仍然沒有被很好地解決。

動機

我們的方法受到了神經網絡架構搜索（Neural Architecture Search（NAS））的啟發 [4]。NAS 旨在自動地搜索出適應于數據集與下游任務的神經網絡結構。在計算機視覺的許多任務中，NAS 發現的網絡結構已經取得了比手工設計的網絡更好的效果。早期的基于強化學習或進化算法的 NAS 工作，對每一個候選的網絡結構都要從頭訓練，然后驗證它的表現，這使得搜索過程非常耗時（可多達數千個 GPU 天）。

近期的 one-shot NAS 方法使用參數共享（parameter sharing）[12]，即所有候選的網絡結構共享一個更大的超網絡的參數。這樣，搜索問題就轉化為了如何訓練一個超網絡及如何從超網絡中得到理想的子模型，從而大大縮短了搜索時間。NAS 的這些進展吸引了我們的注意，并促使我們思考，能否基于這一框架提出一種方法來解決異質圖表示學習的問題？

這樣的延伸遠不是容易的，因為不同領域的數據和任務有不同的性質，對應的網絡結構也有各自的特點。一個首要的問題是：如何設計一個能表示 HINs 中包含的語義信息的搜索空間？我們借鑒了傳統的數據挖掘方法在對 HINs 中節點的相似性進行建模時提出的兩個概念，即“元路徑”（Meta Path）[10] 和“元圖”（Meta Graph）[6]。

這兩個概念是由節點類型和邊類型組成的復合關系，以表示 HINs 中的語義信息。例如，圖 4(a) 是一個 meta path，表示兩部電影有共同的導演，而圖 4(b) 是一個 meta graph，表示兩部電影不僅有共同的導演，還有相同的演員。

▲ 圖4 “元路徑”與“元圖”

Meta Path 這一概念已經被一些相關工作采用（如 HAN [8] 與 MAGNN [9] 就采用手工設計 meta paths 的方式利用語義信息）。然而，相比于 Meta Path，Meta Graph 通過靈活地結合多個路徑，可以更好地表示細粒度的語義信息。因此，我們希望把 Meta Graph 和 GNN 的消息傳播（message passing）框架結合在一起，并設計一個搜索空間來表示可能的 meta graphs。

搜索空間

我們將搜索空間定義為一個有向無環圖（DAG）。這個 DAG 中的每個節點表示? GNN 在 message passing 過程中的一個中間狀態。在第 個狀態時，異質圖中節點的表示向量為 。 表示輸入的初始特征。DAG 中的每條邊從一個舊的狀態 出發指向一個新的狀態 k，表示將 沿著異質網絡中某種類型的邊（候選的邊類型的集合為 ）傳播一次，得到的傳播后的表示向量以相加的方式參與構成 。

以一個學術網絡為例，我們在圖中展示了一個狀態數為 2 的搜索空間以及這個搜索空間中的一個實例。在這一例子中，從 到 ，以及從 到 ，異質網絡中的信息都由文章類型的節點傳播至作者，然而，這兩次信息傳播的效果是不同的，因為 中的文章類型的節點已經收集了會議類型的節點的信息。

▲ 圖5 搜索空間

為了使搜索空間更加靈活，我們在候選的可供信息傳播的邊類型的集合中還加入了Identity （即 不進行信息傳播）和 Zero （即 不參與構成 ）。進一步地，我們注意到，對于某些信息傳播步驟，只有特定的邊類型需要被包含在候選集合中。

對于圖中的例子，當我們預測作者的研究領域時（即節點分類），只有作者的表示會參與到下游任務中，因此 中只需包含由文章指向作者，以及從機構指向作者這兩種邊類型。這樣的限制可以幫助我們提前過濾掉搜索空間中不必要的選擇。然而，對于含有豐富語義信息的異質網絡，搜索空間仍然非常大，因此需要我們設計一個高效的搜索算法。

搜索算法

我們采用 one-shot 的思路，在搜索時引入額外的“結構參數” （區別于 GNN 自身的參數 ）來表示候選的各個邊類型的重要程度。在 one-shot NAS 的框架下，搜索問題轉化為一個 Bi-level 優化問題，實踐中通常采取交替更新 和 的做法。然而，直接訓練經過 加權混合后的超網絡有兩個潛在的問題。一是訓練超網絡不夠高效，因為我們需要對每個候選的邊類型都計算一次信息傳播操作，然后再把它們加權相加。二是優化超網絡的過程與最后測試時的實驗設置不一致。

測試時我們只從超網絡中導出一個最好的子模型（基于優化后的 ）從頭訓練，但優化超網絡時不同的子模型可能會互相關聯，導致 無法很好地反映每個子模型單獨訓練時的好壞。因此，我們提出了一個基于貪心策略的搜索算法，每輪迭代只從候選的信息傳播操作中挑選一個參與計算，這樣一方面提高了搜索效率，同時也使得優化后的超網絡能更好地反映子模型的表現。算法的詳細推導請參看原論文。

▲ 圖6 搜索算法

實驗結果

我們在節點分類任務和推薦任務上對我們的方法進行了測試，實驗結果表明我們的方法可以取得比現有的為 HINs 設計的 GNNs 更好的效果。

▲ 圖7 實驗結果

我們比較了我們的搜索算法與其他搜索方法的搜索效率，結果表明我們的搜索算法顯著地縮短了搜索時間，使得搜索耗時與從頭訓練一個單獨的 GNN 模型相當。當我們從頭訓練搜索得到的模型時，其達到最好的驗證集表現所需的時間比最好的基準方法 HGT 短得多，相比于最簡單的結構 GCN，其大幅提高了表現且只需要很少的額外時間完成訓練。這樣的結果表明我們的方法可以很好地應用于大規模的異質圖。

▲ 圖8 搜索效率比較

▲?圖9 搜索出的“元圖”

未來工作

最后，我們結合本組的相關研究簡單談一下未來工作。

自動化圖神經網絡近兩年成為一個比較重要且熱門的方向，本文主要探索了異質圖上的元圖搜索，這是異質圖上的核心任務之一。后續的改進方向之一，就是將元圖搜索和圖神經網絡的聚合算子搜索相結合。本組之前的工作，針對同質網絡，提出了可微圖神經網絡架構搜索?[13]，未來可以考慮將兩者融合在一起，尋求在異質圖上更為強大的圖神經網絡架構。

從知識圖譜中挖掘邏輯規則是引領人工智能從感知走向認知的一個重要方向，區別于異質圖的元路徑和元圖，圖譜中的邏輯強調關系層面的復合推理，比如工作于+位于，有大概率推導出居住于的關系，由于關系種類的多樣性，這種模式更難被挖掘。后續的改進方向之一，就是基于元圖搜索的想法，結合圖譜上遞歸結構搜索 [14]，在知識圖譜中搜索邏輯模式，學習更高階的知識，提升知識圖譜對知識的表達能力。

合作機會

清華大學電子工程系博士后（水木學者計劃）；第四范式實習生、研究員（需博士學位）。

有意者請垂詢：qyaoaa@tsinghua.edu.cn

參考文獻

[1]?Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba. KDD, 2018.

[2]?Graph Convolutional Neural Networks for Web-Scale Recommender Systems. KDD, 2018.

[3]?Heterogeneous Network Representation Learning: A Unified Framework with Survey and Benchmark. TKDE, 2020.

[4]?Neural Architecture Search: A Survey. JMLR, 2019.

[5]?Graph neural networks: A review of methods and applications. AI Open, 2020.

[6]?Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks. KDD, 2017.

[7]?Semi-Supervised Classification with Graph Convolutional Networks. ICLR, 2017.

[8]?Heterogeneous Graph Attention Network. WebConf, 2019.

[9]?MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding. WebConf, 2020.

[10]?PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks. VLDB, 2011.

[11]?Heterogeneous Graph Transformer. WebConf, 2020.

[12]?Understanding and Simplifying One-Shot Architecture Search. ICML, 2018.

[13]?Search to aggregate neighborhood for graph neural network. ICDE, 2021.

[14]?Interstellar: Searching Recurrent Architecture for Knowledge Graph Embedding. NeurIPS, 2020.

特別鳴謝

感謝 TCCI 天橋腦科學研究院對于 PaperWeekly 的支持。TCCI 關注大腦探知、大腦功能和大腦健康。

更多閱讀

#投 稿?通 道#

?讓你的文字被更多人看到?

如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學術熱點剖析、科研心得或競賽經驗講解等。我們的目的只有一個，讓知識真正流動起來。

📝?稿件基本要求：

? 文章確系個人原創作品，未曾在公開渠道發表，如為其他平臺已發表或待發表的文章，請明確標注?

? 稿件建議以?markdown?格式撰寫，文中配圖以附件形式發送，要求圖片清晰，無版權問題

? PaperWeekly 尊重原作者署名權，并將為每篇被采納的原創首發稿件，提供業內具有競爭力稿酬，具體依據文章閱讀量和文章質量階梯制結算

📬?投稿通道：

? 投稿郵箱：hr@paperweekly.site?

? 來稿請備注即時聯系方式（微信），以便我們在稿件選用的第一時間聯系作者

? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿

△長按添加PaperWeekly小編

🔍

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

·

總結

以上是生活随笔為你收集整理的KDD 2021 | 异质图神经网络的可微元图搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。