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

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

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

針對(duì)圖預(yù)測(cè)任務(wù)，大賽給出的賽題為“根據(jù)給定的 2D 分子化學(xué)結(jié)構(gòu)圖預(yù)測(cè)分子性質(zhì)”。由于近年來人工智能在生物醫(yī)學(xué)、材料發(fā)現(xiàn)等領(lǐng)域的探索持續(xù)受到關(guān)注，因此該賽道競(jìng)爭(zhēng)激烈異常，“高手”云集。只有主動(dòng)求變，才能在眾多高手中脫穎而出。為此，微軟亞洲研究院的研究員們通過借鑒 Transformer 模型的思路，提出了可應(yīng)用于圖結(jié)構(gòu)數(shù)據(jù)的 Graphormer 模型，展現(xiàn)了跨領(lǐng)域研究的創(chuàng)新成果，并希望借此為各個(gè)領(lǐng)域的技術(shù)變革帶來一些啟發(fā)。團(tuán)隊(duì)現(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ì)，計(jì)算化學(xué)家們常使用基于量子力學(xué)力場(chǎng)的密度泛函理論 DFT （Density Functional Theory）預(yù)測(cè)，然而該方法非常耗時(shí)。若直接使用圖神經(jīng)網(wǎng)絡(luò) GNN 模型，輸入分子的 2D 結(jié)構(gòu)，則可以快速而準(zhǔn)確地預(yù)測(cè)分子性質(zhì)，并且在幾秒鐘內(nèi)就能夠完成。因此，目前圖預(yù)測(cè)領(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)相對(duì)簡(jiǎn)單，表達(dá)能力有限，且經(jīng)常會(huì)出現(xiàn)過度平滑（Over-Smoothing）的問題，即無法通過堆深網(wǎng)絡(luò)而增加 GNN 的表達(dá)能力。為此，微軟亞洲研究院的研究員們轉(zhuǎn)變思路，希望可以在圖預(yù)測(cè)學(xué)習(xí)任務(wù)中從圖表達(dá)能力著手，來提升圖預(yù)測(cè)性能。

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

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

[[407250]]

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

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

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

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

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

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

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

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

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

[[407251]]

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

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

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

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

論文鏈接:

https://arxiv.org/abs/2106.05234

代碼鏈接:

https://github.com/microsoft/Graphormer