圖表示學習進展：理解大規模數據的形狀
01
在處理數據時，理解複雜數據集之間的差異和相似性是一個有趣的挑戰。形式化這個問題的一種方法是將每個數據集視為一個圖，圖是一種表示數據項之間相互關係的數學模型。圖被廣泛用於建模對象之間的關係——互聯網圖連接了相互引用的頁面，社交圖將朋友聯繫在一起，而分子圖連接了相互結合的原子。
圖是離散的對象，可以建模許多不同類型數據之間的關係，包括 Web 頁面(左圖)、社會關係(中間的圖)或分子(右圖)。
一旦有了多個圖的集合，通常就需要預測每個圖的某些屬性(例如，每個圖一個標籤)。例如，考慮從結構預測蛋白質功能的任務：這裡的每個數據集都是一個蛋白質，而預測任務是最終的結構是否對酶進行編碼。因為我們想要一個模型來計算預測，所以我們需要一種表示法來讓我們在不同的蛋白質結構中實現泛化。理想情況下，人們會想要一種不需要代價很高的標籤就能將圖表示為向量的方法。隨著圖的增大，這個問題變得更加困難——在分子的例子中，人們擁有一些關於它們屬性的知識，然而，面對更大、更複雜的數據集時，推理就會變得越來越困難。
在本帖里,我們將重點介紹圖表示學習領域的一些最新進展」 Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs 」(發表在 WWW’20)，這篇發表文章改善了我們早期研究的可伸縮性,「DDGK: Learning Graph Representations for Deep Divergence Graph Kernels」(發表在 WWW’19)。SLaQ 引入了一種縮放計算的方法，以近似於某類圖統計數據，從而允許快速有效地描述大型圖。我們也很高興地宣布，我們已經在Google Research GitHub圖嵌入庫中發布了這兩篇論文的程式碼。
02
圖相似性的完全無監督學習
在我們2019年的論文中，我們證明了在不需要領域知識和監督的情況下學習圖相似性的表示是可能的。我們提出了深度發散圖核(deep divergence graph kernels, DDGK)，這是一種無監督的方法，用於學習對圖的相似性進行編碼的表示。與以前的工作不同，我們的無監督方法能夠做到共同學習節點表示、圖表示和基於注意力的圖對齊。
這是通過 DDGK 學習到的潛在表達的 t-SNE 可視化來比較蛋白質。藍色的點表示編碼酶的蛋白質，紅色的點表示不編碼酶的蛋白質。我們可以看到，編碼與蛋白質的結構屬性相關(無論它是否編碼酶)，即使在訓練中沒有提供這種背景。(注意，這是表示的投影，因此絕對軸上的值沒有意義。)
使用 DDGK 編碼和對齊不同數據集之間的成對距離。顏色表示潛在空間中的距離，相似度的範圍從 0(相同)到 1.0(非常不同)。我們看到，可以將表示聚類來將類似的數據集分組在一起——例如，數據集 nci1 和 ptc 都是化合物的數據集。
03
譜描述符的快速準確近似
圖的譜是一種強大的表示，它對圖的屬性進行編碼，包括圖節點和聚類資訊之間的連接模式。譜已被證明可以傳遞關於不同對象屬性的豐富資訊，例如鼓聲、三維形狀、圖和一般的高維數據。譜圖描述符的應用包括自動系統、動態圖中的異常檢測和化學分子表徵。
目前，基於學習的系統(如 DDGK)既不能伸縮到大型圖，也不能伸縮到大型圖集合。或者，我們可以使用沒有學習成分的譜資訊來獲得更理想的尺度特性。然而，計算大型圖的譜描述符在計算上是禁止的。我們最近的一篇論文通過提出 SLaQ 來解決這個問題，SLaQ 是一種近似於一系列圖描述符的方法。我們的方法使用隨機逼近演算法來計算譜函數的軌跡，這使我們能夠研究幾個著名的譜圖特徵，如馮諾依曼圖熵、Estrada 指數、圖能量和 NetLSD。
例如，我們使用 SLaQ 來監視Wikipedia圖結構中的異常變化。SLaQ 允許我們從諸如大量頁面重命名之類的瑣碎更改中辨別出頁面圖結構中的有意義的改變。我們的實驗表明，平均而言，近似精度提高了兩個數量級。
左:著名的空手道圖形代表了兩個武術俱樂部的社會互動。右邊:原始圖的譜描述符(NetLSD、VNGE 和 Estrada 指數)用藍色表示，去掉邊的圖用紅色表示。
04
結論
圖的無監督表示學習是一個重要的問題，而且我們相信我們在這裡強調的方法是這一領域一大令人興奮的進展! 具體來說，SLaQ 允許我們為大量數據集計算原則表示， DDGK 引入了一種自動學習數據集之間對齊的機制。我們希望我們的貢獻將有助於推動大型數據集的分析，並將有助於理解時變圖數據集的變化，如在 推薦系統中使用的那些。
致謝
我們感謝 Marina Munkhoeva, Rami Al-Rfou 和 Dustin Zelle 對這些工作的貢獻。有關 圖挖掘團隊(部分 演算法和優化組)的更多資訊，請訪問我們的頁面。
