KDD Cup 全稱為國際知識發(fā)現(xiàn)和數(shù)據(jù)挖掘競賽，自1997年開始，由 ACM 協(xié)會 SIGKDD 分會每年舉辦一次，目前是全球數(shù)據(jù)挖掘領(lǐng)域最有影響力的賽事，其所設(shè)比賽題目具有相當高的實際意義和商業(yè)價值。多年來，該賽事每年都吸引著眾多世界頂級的 AI 研究機構(gòu)與企業(yè)的參與，并且催生了大量的經(jīng)典比賽和經(jīng)典算法。

今年，KDD Cup 2021 首次與斯坦福大學圖神經(jīng)網(wǎng)絡(luò)權(quán)威 Jure Leskovec 教授領(lǐng)導 Open Graph Benchmark（OGB）團隊合作，聯(lián)合舉辦第一屆 OGB Large-Scale Challenge，共有500余個來自全球各地的隊伍參賽。大賽于本周剛剛結(jié)束，由微軟亞洲研究院的研究員和大連理工大學等高校的實習生組成的團隊在圖預(yù)測賽道摘得桂冠（官方競賽結(jié)果網(wǎng)頁鏈接：https://ogb.stanford.edu/kddcup2021/results/）。

圖1：微軟亞洲研究院的研究員和實習生組成的團隊在 OGB-LSC 圖預(yù)測賽道摘得桂冠，團隊成員包括：應(yīng)承軒（大連理工大學）、楊明奇（大連理工大學）、羅勝杰（北京大學）、蔡天樂（普林斯頓大學）、柯國霖（微軟亞洲研究院）、賀笛（微軟亞洲研究院）、鄭書新（微軟亞洲研究院）、吳承霖（廈門大學）、王宇新（大連理工大學）、申彥明（大連理工大學）

針對圖預(yù)測任務(wù)，大賽給出的賽題為“根據(jù)給定的 2D 分子化學結(jié)構(gòu)圖預(yù)測分子性質(zhì)”。由于近年來人工智能在生物醫(yī)學、材料發(fā)現(xiàn)等領(lǐng)域的探索持續(xù)受到關(guān)注，因此該賽道競爭激烈異常，“高手”云集。只有主動求變，才能在眾多高手中脫穎而出。為此，微軟亞洲研究院的研究員們通過借鑒 Transformer 模型的思路，提出了可應(yīng)用于圖結(jié)構(gòu)數(shù)據(jù)的 Graphormer 模型，展現(xiàn)了跨領(lǐng)域研究的創(chuàng)新成果，并希望借此為各個領(lǐng)域的技術(shù)變革帶來一些啟發(fā)。團隊現(xiàn)已將論文和代碼公開發(fā)表在 arXiv 和 GitHub 上。

論文鏈接:

https://arxiv.org/abs/2106.05234

代碼鏈接:

https://github.com/microsoft/Graphormer

[[407249]]

將Transformer應(yīng)用于圖數(shù)據(jù)，核心在于如何正確編碼“圖結(jié)構(gòu)”

為了得到更精確的分子性質(zhì)，計算化學家們常使用基于量子力學力場的密度泛函理論 DFT （Density Functional Theory）預(yù)測，然而該方法非常耗時。若直接使用圖神經(jīng)網(wǎng)絡(luò) GNN 模型，輸入分子的 2D 結(jié)構(gòu)，則可以快速而準確地預(yù)測分子性質(zhì)，并且在幾秒鐘內(nèi)就能夠完成。因此，目前圖預(yù)測領(lǐng)域的主流算法主要是圖神經(jīng)網(wǎng)絡(luò)（GNN）模型及其變種，比如圖卷積網(wǎng)絡(luò)（Graph Convolutional Net）、圖注意力網(wǎng)絡(luò)（Graph Attention Net）、圖同構(gòu)網(wǎng)絡(luò)（Graph isomorphic Net）等。

但是，這些圖神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)相對簡單，表達能力有限，且經(jīng)常會出現(xiàn)過度平滑（Over-Smoothing）的問題，即無法通過堆深網(wǎng)絡(luò)而增加 GNN 的表達能力。為此，微軟亞洲研究院的研究員們轉(zhuǎn)變思路，希望可以在圖預(yù)測學習任務(wù)中從圖表達能力著手，來提升圖預(yù)測性能。

研究員們看到，Transformer 模型具有很強的模型表達能力，沒有其他圖神經(jīng)網(wǎng)絡(luò)所存在的上述弱點。微軟亞洲研究院機器學習組對 Transformer 模型結(jié)構(gòu)有著深刻的理解，近幾年在頂級國際學術(shù)會議如 ICML、NeurIPS、ICLR 上發(fā)表了許多關(guān)于如何改進 Transformer 的論文，基于這些對模型本質(zhì)的認識，研究員們相信 Transformer 的不少優(yōu)勢在圖數(shù)據(jù)上也可以發(fā)揮巨大的作用。

經(jīng)典的 Transformer 模型是處理序列類型數(shù)據(jù)的，如自然語言、語音等等，那么如何讓這個模型處理圖類型數(shù)據(jù)呢？研究員們認為最重要的是讓 Transformer 學會編碼圖的結(jié)構(gòu)信息。Transformer 的核心在于其自注意力機制，通過在計算中輸入不同位置語義信息的相關(guān)性，可以捕捉到信息之間的關(guān)系，并且可基于這些關(guān)系得到對整個輸入完整的表達（representation）。然而，自注意力機制無法捕捉到結(jié)構(gòu)信息。對于自然語言序列而言，輸入序列的結(jié)構(gòu)信息可以簡單認為是詞與詞的相對順序，以及每個詞在句子中的位置。對于圖數(shù)據(jù)而言，這種結(jié)構(gòu)信息更加復雜、多元，例如在圖上的每個節(jié)點都有不同數(shù)量的鄰居節(jié)點，兩個節(jié)點之間可以有多種路徑，每個邊上都可能包含重要的信息。如何在圖數(shù)據(jù)中成功應(yīng)用 Transformer 的核心優(yōu)勢，最關(guān)鍵的難題是要確保模型可以正確利用這些圖結(jié)構(gòu)信息。

[[407250]]

圖結(jié)構(gòu)數(shù)據(jù)上的Transformer變種Graphormer

為了把 Transformer 模型強大的表達能力引入圖結(jié)構(gòu)數(shù)據(jù)中，研究員們提出了 Graphormer 模型。Graphormer 模型引入了三種結(jié)構(gòu)編碼，以幫助 Transformer 模型捕捉圖的結(jié)構(gòu)信息。這些結(jié)構(gòu)編碼讓 Graphormer 模型的自注意力層可以成功捕捉到更“重要”的節(jié)點或節(jié)點對，從而令后續(xù)的注意力權(quán)重分配更準確。

圖2：Graphormer 模型的三種結(jié)構(gòu)編碼

第一種編碼，Centrality Encoding（中心性編碼）。Centrality（中心性）是描述圖中節(jié)點重要性的一個關(guān)鍵衡量指標。圖的中心性有多種衡量方法，例如一個節(jié)點的“度”（degree）越大，代表這個節(jié)點與其他節(jié)點相連接的邊越多，那么往往這樣的節(jié)點就會更重要，如在疾病傳播路線中的超級傳播者，或社交網(wǎng)絡(luò)上的大V、明星等。Centrality 還可以使用其他方法進行度量，如 Closeness、Betweenness、Page Rank 等。在 Graphormer 中，研究員們采用了最簡單的度信息作為中心性編碼，為模型引入節(jié)點重要性的信息。

第二種編碼，Spatial Encoding（空間編碼）。實際上圖結(jié)構(gòu)信息不僅包含了每個節(jié)點上的重要性，也包含了節(jié)點之間的重要性。例如：鄰居節(jié)點或距離相近的節(jié)點之間往往相關(guān)性比距離較遠的節(jié)點相關(guān)性高。因此，研究員們?yōu)?Graphormer 設(shè)計了空間編碼：給定一個合理的距離度量 ϕ(v_i, v_j), 根據(jù)兩個節(jié)點(v_i, v_j)之間的距離，為其分配相應(yīng)的編碼向量。距離度量 ϕ(⋅) 的選擇多種多樣，對于一般性的圖數(shù)據(jù)可以選擇無權(quán)或帶權(quán)的最短路徑，而對于特別的圖數(shù)據(jù)則可以有針對性的選擇距離度量，例如物流節(jié)點之間的最大流量，化學分子 3D 結(jié)構(gòu)中原子之間的歐氏距離等等。為了不失一般性，Graphormer 在實驗中采取了無權(quán)的最短路徑作為空間編碼的距離度量。

第三種編碼，Edge Encoding（邊信息編碼）。對于很多的圖任務(wù)，連邊上的信息有非常重要的作用，例如連邊上的距離、流量等等。然而為處理序列數(shù)據(jù)而設(shè)計的 Transformer 模型并不具備捕捉連邊上的信息的能力，因為序列數(shù)據(jù)中并不存在“連邊”的概念。因此，研究員們設(shè)計了邊信息編碼，將連邊上的信息作為權(quán)重偏置（Bias）引入注意力機制中。具體來說，在計算兩個節(jié)點之間的相關(guān)性時，研究員們對這兩個節(jié)點最短路徑上的連邊特征進行加權(quán)求和作為注意力偏置，其中權(quán)重是可學習的。

與此同時，研究員們還從理論角度證明了當前流行的 GNN 網(wǎng)絡(luò)如 GCN、GIN、GraphSage 等，都是 Graphormer 的特例：在為 Graphormer 設(shè)定特殊的參數(shù)時，這些 GNN 中的操作可以被 Graphormer 所覆蓋。例如，當兩個節(jié)點為鄰居節(jié)點時，將空間編碼設(shè)為0，或?qū)⒖臻g編碼設(shè)為-∞，并且令 W_Q=W_K=0, W_V=I，則自注意力層即成為 GCN、GraphSage 等網(wǎng)絡(luò)中的 MEAN Aggregation 操作。因此，Graphormer 能夠取得比 GNN 模型更好的效果也是理所應(yīng)當?shù)摹?/p>

此外，研究員們還在多個主流圖預(yù)測任務(wù)排行榜上驗證了 Graphormer 的效果。例如，OGB 數(shù)據(jù)集中的 ogbg-molhiv 任務(wù)（預(yù)測是否被 HIV 病毒感染），ogbg-molpcba 任務(wù)（預(yù)測分子的64種性質(zhì)）以及 Benchmarking-GNN 數(shù)據(jù)集中的 ZINC 任務(wù)（對真實世界中存在的分子的受限溶解度 Constrained Solubility 進行預(yù)測）。Graphormer 均取得了優(yōu)異的成績，具體測試結(jié)果如下圖：

圖3：Graphormer 模型在 ogbg-molhiv、 ogbg-molpcba 和 ZINC 數(shù)據(jù)集上的測試結(jié)果

[[407251]]

不止于分子性質(zhì)預(yù)測

近年來，微軟亞洲研究院一直在探索如何利用 AI 的技術(shù)手段與不同基礎(chǔ)科學領(lǐng)域進行跨界研究合作，如生物學、環(huán)境科學、物理學等等，并產(chǎn)生了大量的創(chuàng)新研究成果。

Graphormer 在設(shè)計之初并非只針對分子性質(zhì)預(yù)測場景，其采用的三種編碼具有通用性，可以應(yīng)用于更廣泛的圖數(shù)據(jù)場景中，例如，社交網(wǎng)絡(luò)的推薦和廣告、知識圖譜、自動駕駛的雷達點云數(shù)據(jù)、對交通物流運輸?shù)鹊臅r空預(yù)測和優(yōu)化、程序理解和生成等等，還包括分子性質(zhì)預(yù)測所涉及的行業(yè)，比如藥物發(fā)掘、材料發(fā)現(xiàn)、分子動力學模擬、蛋白質(zhì)結(jié)構(gòu)預(yù)測等等。研究員們表示，下一步將在更多的任務(wù)中探索 Graphormer 模型的潛能。相信未來，各個科學領(lǐng)域與 AI 的密切結(jié)合將為領(lǐng)域的發(fā)展帶來更為非常廣闊的空間。

歡迎大家使用 Graphormer 模型，為模型的提升提出寶貴建議，與我們共同推進相關(guān)領(lǐng)域的技術(shù)進展。

論文鏈接:

https://arxiv.org/abs/2106.05234

代碼鏈接:

https://github.com/microsoft/Graphormer