近年來,人們對學習圖結構數據表示的興趣大增。基于標記數據的可用性,圖表示學習方法一般分為三大類。第一種是網絡嵌入(如淺層圖嵌入或圖自動編碼器),它側重于學習關系結構的無監督表示。第二種是圖正則化神經網絡,它利用圖來增加半監督學習的正則化目標的神經網絡損失。第三種是圖神經網絡,目的是學習具有任意結構的離散拓撲上的可微函數。然而,盡管這些領域很受歡迎,但在統一這三種范式方面的工作卻少得驚人。在這里,我們的目標是彌合圖神經網絡、網絡嵌入和圖正則化模型之間的差距。我們提出了圖結構數據表示學習方法的一個綜合分類,旨在統一幾個不同的工作主體。具體來說,我們提出了一個圖編碼解碼器模型(GRAPHEDM),它將目前流行的圖半監督學習算法(如GraphSage、Graph Convolutional Networks、Graph Attention Networks)和圖表示的非監督學習(如DeepWalk、node2vec等)歸納為一個統一的方法。為了說明這種方法的一般性,我們將30多個現有方法放入這個框架中。我們相信,這種統一的觀點既為理解這些方法背后的直覺提供了堅實的基礎,也使該領域的未來研究成為可能。
概述
學習復雜結構化數據的表示是一項具有挑戰性的任務。在過去的十年中,針對特定類型的結構化數據開發了許多成功的模型,包括定義在離散歐幾里德域上的數據。例如,序列數據,如文本或視頻,可以通過遞歸神經網絡建模,它可以捕捉序列信息,產生高效的表示,如機器翻譯和語音識別任務。還有卷積神經網絡(convolutional neural networks, CNNs),它根據移位不變性等結構先驗參數化神經網絡,在圖像分類或語音識別等模式識別任務中取得了前所未有的表現。這些主要的成功僅限于具有簡單關系結構的特定類型的數據(例如,順序數據或遵循規則模式的數據)。
在許多設置中,數據幾乎不是規則的: 通常會出現復雜的關系結構,從該結構中提取信息是理解對象之間如何交互的關鍵。圖是一種通用的數據結構,它可以表示復雜的關系數據(由節點和邊組成),并出現在多個領域,如社交網絡、計算化學[41]、生物學[105]、推薦系統[64]、半監督學習[39]等。對于圖結構的數據來說,將CNNs泛化為圖并非易事,定義具有強結構先驗的網絡是一項挑戰,因為結構可以是任意的,并且可以在不同的圖甚至同一圖中的不同節點之間發生顯著變化。特別是,像卷積這樣的操作不能直接應用于不規則的圖域。例如,在圖像中,每個像素具有相同的鄰域結構,允許在圖像中的多個位置應用相同的過濾器權重。然而,在圖中,我們不能定義節點的順序,因為每個節點可能具有不同的鄰域結構(圖1)。此外,歐幾里德卷積強烈依賴于幾何先驗(如移位不變性),這些先驗不能推廣到非歐幾里德域(如平移可能甚至不能在非歐幾里德域上定義)。
這些挑戰導致了幾何深度學習(GDL)研究的發展,旨在將深度學習技術應用于非歐幾里德數據。特別是,考慮到圖在現實世界應用中的廣泛流行,人們對將機器學習方法應用于圖結構數據的興趣激增。其中,圖表示學習(GRL)方法旨在學習圖結構數據的低維連續向量表示,也稱為嵌入。
廣義上講,GRL可以分為兩類學習問題,非監督GRL和監督(或半監督)GRL。第一個系列的目標是學習保持輸入圖結構的低維歐幾里德表示。第二系列也學習低維歐幾里德表示,但為一個特定的下游預測任務,如節點或圖分類。與非監督設置不同,在非監督設置中輸入通常是圖結構,監督設置中的輸入通常由圖上定義的不同信號組成,通常稱為節點特征。此外,底層的離散圖域可以是固定的,這是直推學習設置(例如,預測一個大型社交網絡中的用戶屬性),但也可以在歸納性學習設置中發生變化(例如,預測分子屬性,其中每個分子都是一個圖)。最后,請注意,雖然大多數有監督和無監督的方法學習歐幾里德向量空間中的表示,最近有興趣的非歐幾里德表示學習,其目的是學習非歐幾里德嵌入空間,如雙曲空間或球面空間。這項工作的主要動機是使用一個連續的嵌入空間,它類似于它試圖嵌入的輸入數據的底層離散結構(例如,雙曲空間是樹的連續版本[99])。
鑒于圖表示學習領域的發展速度令人印象深刻,我們認為在一個統一的、可理解的框架中總結和描述所有方法是很重要的。本次綜述的目的是為圖結構數據的表示學習方法提供一個統一的視圖,以便更好地理解在深度學習模型中利用圖結構的不同方法。
目前已有大量的圖表示學習綜述。首先,有一些研究覆蓋了淺層網絡嵌入和自動編碼技術,我們參考[18,24,46,51,122]這些方法的詳細概述。其次,Bronstein等人的[15]也給出了非歐幾里德數據(如圖或流形)的深度學習模型的廣泛概述。第三,最近的一些研究[8,116,124,126]涵蓋了將深度學習應用到圖數據的方法,包括圖數據神經網絡。這些調查大多集中在圖形表示學習的一個特定子領域,而沒有在每個子領域之間建立聯系。
在這項工作中,我們擴展了Hamilton等人提出的編碼-解碼器框架,并介紹了一個通用的框架,圖編碼解碼器模型(GRAPHEDM),它允許我們將現有的工作分為四大類: (i)淺嵌入方法,(ii)自動編碼方法,(iii) 圖正則化方法,和(iv) 圖神經網絡(GNNs)。此外,我們還介紹了一個圖卷積框架(GCF),專門用于描述基于卷積的GNN,該框架在廣泛的應用中實現了最先進的性能。這使我們能夠分析和比較各種GNN,從在Graph Fourier域中操作的方法到將self-attention作為鄰域聚合函數的方法[111]。我們希望這種近期工作的統一形式將幫助讀者深入了解圖的各種學習方法,從而推斷出相似性、差異性,并指出潛在的擴展和限制。盡管如此,我們對前幾次綜述的貢獻有三個方面
我們介紹了一個通用的框架,即GRAPHEDM,來描述一系列廣泛的有監督和無監督的方法,這些方法對圖形結構數據進行操作,即淺層嵌入方法、圖形正則化方法、圖形自動編碼方法和圖形神經網絡。
我們的綜述是第一次嘗試從同一角度統一和查看這些不同的工作線,我們提供了一個通用分類(圖3)來理解這些方法之間的差異和相似之處。特別是,這種分類封裝了30多個現有的GRL方法。在一個全面的分類中描述這些方法,可以讓我們了解這些方法究竟有何不同。
我們為GRL發布了一個開源庫,其中包括最先進的GRL方法和重要的圖形應用程序,包括節點分類和鏈接預測。我們的實現可以在//github.com/google/gcnn-survey-paper上找到。
現實網絡由多種相互作用、不斷進化的實體組成,而現有的研究大多將其簡單地描述為特定的靜態網絡,而沒有考慮動態網絡的演化趨勢。近年來,動態網絡的特性跟蹤研究取得了重大進展,利用網絡中實體和鏈接的變化來設計網絡嵌入技術。與被廣泛提出的靜態網絡嵌入方法相比,動態網絡嵌入努力將節點編碼為低維密集表示,有效地保持了網絡結構和時間動態,有利于處理各種下游機器學習任務。本文對動態網絡嵌入問題進行了系統的研究,重點介紹了動態網絡嵌入的基本概念,首次對現有的動態網絡嵌入技術進行了分類,包括基于矩陣分解的、基于躍格的、基于自動編碼器的、基于神經網絡的等嵌入方法。此外,我們仔細總結了常用的數據集和各種各樣的后續任務,動態網絡嵌入可以受益。在此基礎上,提出了動態嵌入模型、大規模動態網絡、異構動態網絡、動態屬性網絡、面向任務的動態網絡嵌入以及更多的嵌入空間等現有算法面臨的挑戰,并提出了未來可能的研究方向。
【導讀】深度學習革新了很多應用,但是背后的理論作用機制一直沒有得到統一的解釋。最近來自谷歌大腦和斯坦福的學者共同撰寫了深度學習統計力學的綜述論文《Statistical Mechanics of Deep Learning》,共30頁pdf,從物理學視角闡述了深度學習與各種物理和數學主題之間的聯系。
最近,深度神經網絡在機器學習領域取得了驚人的成功,這對它們成功背后的理論原理提出了深刻的疑問。例如,這樣的深度網絡可以計算什么?我們如何訓練他們?信息是如何通過它們傳播的?為什么他們可以泛化?我們如何教他們想象?我們回顧了最近的工作,其中物理分析方法植根于統計力學已經開始提供這些問題的概念上的見解。這些見解產生了深度學習與各種物理和數學主題之間的聯系,包括隨機景觀、旋轉玻璃、干擾、動態相變、混沌、黎曼幾何、隨機矩陣理論、自由概率和非平衡統計力學。事實上,統計力學和機器學習領域長期以來一直享有強耦合交互作用的豐富歷史,而統計力學和深度學習交叉領域的最新進展表明,這些交互作用只會進一步深化。
概述
具有多層隱含層(1)的深度神經網絡在許多領域都取得了顯著的成功,包括機器視覺(2)、語音識別(3)、自然語言處理(4)、強化學習(5),甚至在神經科學(6、7)、心理學(8、9)和教育(10)中對動物和人類自身的建模。然而,用于獲得成功的深度神經網絡的方法仍然是一門高度熟練的藝術,充滿了許多啟發,而不是一門精確的科學。這為理論科學提出了令人興奮的挑戰和機會,以創建一個成熟的深度神經網絡理論,該理論強大到足以指導在深度學習中廣泛的工程設計選擇。雖然我們目前離這樣成熟的理論還有很長的距離,但是最近在統計力學和深度學習交叉領域出現的一批研究已經開始為深度網絡的學習和計算提供理論上的見解,有時還會提出新的和改進的方法來推動這些理論的深入學習。
在這里,我們回顧了建立在統計力學和機器學習相互作用的悠久而豐富的歷史基礎上的這一工作體系(11-15)。有趣的是,正如我們下面所討論的,這些工作在統計力學和深度學習之間建立了許多新的橋梁。在本介紹的其余部分中,我們將為機器學習的兩個主要分支提供框架。第一個是監督學習,它涉及到從例子中學習輸入-輸出映射的過程。第二種是無監督學習,它涉及到學習和挖掘數據中隱藏的結構模式的過程。有了這兩個框架,我們將在1.3節中介紹本綜述中討論的幾個深度學習的基本理論問題,以及它們與與統計力學相關的各種主題的聯系。
【導讀】近年來,隨著網絡數據量的不斷增加,挖掘圖形數據已成為計算機科學領域的熱門研究課題,在學術界和工業界都得到了廣泛的研究。但是,大量的網絡數據為有效分析帶來了巨大的挑戰。因此激發了圖表示的出現,該圖表示將圖映射到低維向量空間中,同時保持原始圖結構并支持圖推理。圖的有效表示的研究具有深遠的理論意義和重要的現實意義,本教程將介紹圖表示/網絡嵌入的一些基本思想以及一些代表性模型。
關于圖或網絡的文獻有兩個名稱:圖表示和網絡嵌入。我們注意到圖和網絡都指的是同一種結構,盡管它們每個都有自己的術語,例如,圖和網絡的頂點和邊。挖掘圖/網絡的核心依賴于正確表示的圖/網絡,這使得圖/網絡上的表示學習成為學術界和工業界的基本研究問題。傳統表示法直接基于拓撲圖來表示圖,通常會導致許多問題,包括稀疏性,高計算復雜性等,從而激發了基于機器學習的方法的出現,這種方法探索了除矢量空間中的拓撲結構外還能夠捕獲額外信息的潛在表示。因此,對于圖來說,“良好”的潛在表示可以更加精確的表示圖形。但是,學習網絡表示面臨以下挑戰:高度非線性,結構保持,屬性保持,稀疏性。
深度學習在處理非線性方面的成功為我們提供了研究新方向,我們可以利用深度學習來提高圖形表示學習的性能,作者在教程中討論了將深度學習技術與圖表示學習相結合的一些最新進展,主要分為兩類方法:面向結構的深層方法和面向屬性的深層方法。
對于面向結構的方法:
結構性深層網絡嵌入(SDNE),專注于保持高階鄰近度。
深度遞歸網絡嵌入(DRNE),其重點是維護全局結構。
深度超網絡嵌入(DHNE),其重點是保留超結構。
對于面向屬性的方法:
專注于不確定性屬性的深度變異網絡嵌入(DVNE)。
深度轉換的基于高階Laplacian高斯過程(DepthLGP)的網絡嵌入,重點是動態屬性。
本教程的第二部分就以上5種方法,通過對各個方法的模型介紹、算法介紹、對比分析等不同方面進行詳細介紹。
1、Structural Deep Network Embedding
network embedding,是為網絡中的節點學習出一個低維表示的方法。目的在于在低維中保持高度非線性的網絡結構特征,但現有方法多采用淺層網絡不足以挖掘高度非線性,或同時保留局部和全局結構特征。本文提出一種結構化深度網絡嵌入方法,叫SDNE該方法用半監督的深度模型來捕捉高度非線性結構,通過結合一階相似性(監督)和二階相似性(非監督)來保留局部和全局特征。
2、 Deep recursive network embedding with regular equivalence
網絡嵌入旨在保留嵌入空間中的頂點相似性。現有方法通常通過節點之間的連接或公共鄰域來定義相似性,即結構等效性。但是,位于網絡不同部分的頂點可能具有相似的角色或位置,即規則的等價關系,在網絡嵌入的文獻中基本上忽略了這一點。以遞歸的方式定義規則對等,即兩個規則對等的頂點具有也規則對等的網絡鄰居。因此,文章中提出了一種名為深度遞歸網絡嵌入(DRNE)的新方法來學習具有規則等價關系的網絡嵌入。更具體地說,我們提出了一種層歸一化LSTM,以遞歸的方式通過聚合鄰居的表示方法來表示每個節點。
3、Structural Deep Embedding for Hyper-Networks
是在hyperedge(超邊是不可分解的)的基礎上保留object的一階和二階相似性,學習異質網絡表示。于與HEBE的區別在于,本文考慮了網絡high-oeder網絡結構和高度稀疏性。
傳統的基于clique expansion 和star expansion的方法,顯式或者隱式地分解網絡。也就說,分解后hyper edge節點地子集,依然可以構成一個新的超邊。對于同質網絡這個假設是合理地,因為同質網絡地超邊,大多數情況下都是根據潛在地相似性(共同地標簽等)構建的。
4、** Deep variational network embedding in wasserstein space**
大多數現有的嵌入方法將節點作為點向量嵌入到低維連續空間中。這樣,邊緣的形成是確定性的,并且僅由節點的位置確定。但是,現實世界網絡的形成和發展充滿不確定性,這使得這些方法不是最優的。為了解決該問題,在本文中提出了一種新穎的在Wasserstein空間中嵌入深度變分網絡(DVNE)。所提出的方法學習在Wasserstein空間中的高斯分布作為每個節點的潛在表示,它可以同時保留網絡結構并為節點的不確定性建模。具體來說,我們使用2-Wasserstein距離作為分布之間的相似性度量,它可以用線性計算成本很好地保留網絡中的傳遞性。此外,我們的方法通過深度變分模型隱含了均值和方差的數學相關性,可以通過均值矢量很好地捕獲節點的位置,而由方差可以很好地捕獲節點的不確定性。此外,本文方法通過保留網絡中的一階和二階鄰近性來捕獲局部和全局網絡結構。
5、Learning embeddings of out-of-sample nodes in dynamic networks
迄今為止的網絡嵌入算法主要是為靜態網絡設計的,在學習之前,所有節點都是已知的。如何為樣本外節點(即學習后到達的節點)推斷嵌入仍然是一個懸而未決的問題。該問題對現有方法提出了很大的挑戰,因為推斷的嵌入應保留復雜的網絡屬性,例如高階鄰近度,與樣本內節點嵌入具有相似的特征(即具有同質空間),并且計算成本較低。為了克服這些挑戰,本文提出了一種深度轉換的高階拉普拉斯高斯過程(DepthLGP)方法來推斷樣本外節點的嵌入。DepthLGP結合了非參數概率建模和深度學習的優勢。特別是,本文設計了一個高階Laplacian高斯過程(hLGP)來對網絡屬性進行編碼,從而可以進行快速和可擴展的推理。為了進一步確保同質性,使用深度神經網絡來學習從hLGP的潛在狀態到節點嵌入的非線性轉換。DepthLGP是通用的,因為它適用于任何網絡嵌入算法學習到的嵌入。
簡介: 在許多將數據表示為圖形的領域中,學習圖形之間的相似性度量標準被認為是一個關鍵問題,它可以進一步促進各種學習任務,例如分類,聚類和相似性搜索。 最近,人們對深度圖相似性學習越來越感興趣,其中的主要思想是學習一種深度學習模型,該模型將輸入圖映射到目標空間,以使目標空間中的距離近似于輸入空間中的結構距離。 在這里,我們提供對深度圖相似性學習的現有文獻的全面回顧。 我們為方法和應用提出了系統的分類法。 最后,我們討論該問題的挑戰和未來方向。
在特征空間上學習足夠的相似性度量可以顯著確定機器學習方法的性能。從數據自動學習此類度量是相似性學習的主要目的。相似度/度量學習是指學習一種功能以測量對象之間的距離或相似度,這是許多機器學習問題(例如分類,聚類,排名等)中的關鍵步驟。例如,在k最近鄰(kNN)中分類[25],需要一個度量來測量數據點之間的距離并識別最近的鄰居;在許多聚類算法中,數據點之間的相似性度量用于確定聚類。盡管有一些通用度量標準(例如歐幾里得距離)可用于獲取表示為矢量的對象之間的相似性度量,但是這些度量標準通常無法捕獲正在研究的數據的特定特征,尤其是對于結構化數據。因此,找到或學習一種度量以測量特定任務中涉及的數據點的相似性至關重要。
報告簡介: 圖形領域的機器學習是一項重要而普遍的任務,其應用范圍從藥物設計到社交網絡中的友情推薦。該領域的主要挑戰是找到一種表示或編碼圖形結構的方法,以便機器學習模型可以很方便地利用它。 報告中介紹了深度學習的技術,自動學習將圖形結構編碼為低維嵌入。以及表示學習的關鍵進展,包括圖形卷積網絡及其表示能力,探討了它在Web級推薦系統、醫療保健、知識表示和推理方面的應用。
嘉賓介紹: 領域的大牛Jure Leskovec,是斯坦福大學計算機學院的副教授,也是圖表示學習方法 node2vec 和 GraphSAGE 作者之一。研究重點是對大型社會和信息網絡進行挖掘和建模,它們的演化,信息的傳播以及對它們的影響。 Jure Leskovec主頁