圖神經網絡(GNNs)成功地從大多數類型的網絡數據學習表示,但在大型圖的情況下受到限制。挑戰出現在學習架構的設計本身,因為大多數GNN是由圖的一些矩陣表示(例如,鄰接矩陣)參數化的,當網絡很大時,這可能很難獲得。此外,在許多GNN架構中,圖操作是通過譜域中的卷積操作來定義的。在這種情況下,另一個障礙是圖譜的獲得,這需要代價高昂的矩陣特征分解。
然而,從共享結構屬性的意義上來說,大型圖通常可以被識別為彼此相似。因此,我們可以預期,處理這些圖上支持的數據應該會產生類似的結果,這將減輕大尺寸的挑戰,因為我們可以為小圖設計GNN,并將它們轉移到更大的圖上。在這篇論文中,我將這種直覺形式化,并表明當這些圖屬于同一個“族”時,這種圖的可移植性是可能的,其中每個族由不同的圖元標識。
graphon是一個函數W(x,y),它描述了一類具有相似形狀的隨機圖。我們可以將參數(x,y)看作是一對節點的標簽,以及圖元值W(x,y)作為x和y之間一條邊的概率的標簽。這產生了一個從圖元采樣的圖的概念,或者,等價地,一個隨著采樣圖中節點數量增長的極限的概念。從一個graphon上采樣的圖形幾乎肯定在極限上具有相同的屬性,例如同態密度,這在實踐中意味著,graphon識別的網絡家族在某種意義上是相似的,某些“motifs”的密度是保持不變的。這激發了對圖上的信息處理的研究,作為在大型圖上進行信息處理的一種方法。
信號處理理論的核心部分是一個移位的概念,它引入了一類具有傅立葉變換(FT)特征的光譜表示的線性濾波器。本文表明,graphon誘導了一個線性算子,可用于定義移位,從而定義graphon濾波器和graphon FT。基于圖序列和相關圖信號的收斂性質,可以證明對于這些序列,圖FT收斂到graphon FT,圖濾波器的輸出收斂到具有相同系數的graphon濾波器的輸出。這些定理表明,對于屬于某些族的圖,圖傅里葉分析和圖濾波器設計具有明確的限制。反過來,這些事實使具有大量節點的圖上的圖信息處理成為可能,因為為極限圖設計的信息處理管道可以應用于有限圖。
我們通過組合具有點非線性的graphon濾波器組來進一步定義graphon神經網絡(WNNs)。WNNs是理想的極限,在實際中并不存在,但它們是理解GNNs基本性質的有用工具。特別是,graphon濾波器的采樣和收斂結果可以很容易地擴展到WNNs,從而表明當圖收斂到graphon時,GNN收斂到WNNs。如果兩個GNN可以任意接近同一個WNN,那么通過一個簡單的三角形不等式參數,它們也可以任意接近彼此。這個結果證實了我們的直覺,即GNN可以在相似的圖之間轉移。一個GNN可以在中等規模的圖上訓練,并在一個可轉移性誤差主要為最小圖的大小的倒數的大尺度圖上執行。有趣的是,這種誤差隨著卷積濾波器光譜響應的可變性而增加,揭示了從圖濾波器繼承來的可轉移性和光譜鑒別性之間的權衡。在實踐中,由于非線性,這種權衡在GNN中很少出現,它能夠將數據的光譜成分分散到特征值譜的不同部分,在那里它們可以被區分。這解釋了為什么GNN比圖過濾器更可轉移。
在許多現代應用中取得顯著成功的最主要的技術之一是深度學習。對圖像識別、語音處理和文本理解中的海量數據分析的癡迷,促使深度神經網絡在不同研究領域的不同學習任務中取得了顯著進展。深度學習技術聯盟產生了強大的卷積神經網絡和新興的圖神經網絡。圖神經網絡(Graph neural networks),簡稱GNNs,是一種輸入包含內部結構關系的深度神經網絡。圖神經網絡(GNNs)的主流找到了圖的充分數值表示,這對統計或機器學習模型的預測性能至關重要。圖表示學習在現實世界中有許多應用,如藥物再利用、蛋白質分類、流行病傳播控制和社會網絡分析等。在過去五年中,GNN的快速發展過程中,發現了一些設計缺陷,如過度平滑、易受擾動、缺乏表現力和缺乏可解釋性。同時,對該研究領域的持續熱情為解決更復雜的問題積累了經驗,如大小可變圖壓縮和時變圖動態捕獲。
//ses.library.usyd.edu.au/handle/2123/28617
**這篇論文的目標是闡明一些關于數學的概述問題。**其中,圖壓縮的置換不變設計支持流形學習,魯棒的圖平滑依賴于凸優化原理,高效的動態圖表示學習借鑒了信號處理和矩陣分解的隨機冪方法。作者認為,深度學習技術的有效性不應該僅僅取決于在特定數據集上的性能,對黑盒模型的修改應該在皮膚層之下進行,并比超參數調整付出更多的努力。深度神經網絡的可靠性期待著在嚴格的數學支持下設計模型,以便有一天“計算機科學”成為真正的科學。
深度學習重塑了人工智能的研究和應用。現代深度學習模型主要是為規則結構的數據設計的,如序列和圖像。這些模型是為將這些規則結構的數據作為輸入(例如分類、回歸)、作為輸出(例如生成)或作為結構先驗(例如神經架構設計)的任務而建立的。然而,并非所有形式的數據都是規則結構的。一個值得注意的例子是圖結構數據,這是一種通用而強大的數據結構,它以簡潔的形式表示實體及其關系。雖然圖結構數據在自然和社會科學中無處不在,但它是離散的和非i.i.d的。大自然給現代深度學習模型帶來了獨特的挑戰。本文旨在通過促進深度學習模型將圖作為輸入、輸出和先驗,以圖結構數據為深度學習賦能。我在這三個方向的研究為深度學習的研究開辟了新的前沿:(1)基于深度學習的圖學習。開發了具有表現力的有效深度學習方法,可以將圖作為輸入,促進了圖的學習和理解。(2)基于深度學習的圖生成。用深度學習模型規范了圖的生成過程,促進了圖的發現和設計。(3)圖作為深度學習的先驗。發現圖結構可以作為神經架構和機器學習任務的強大先驗,為深度學習的設計和理解打開了一個新的方向。討論了上述技術的廣泛應用,包括推薦系統、藥物發現、神經架構設計和缺失數據填補。
//stacks.stanford.edu/file/druid:mz469rn9516/PhD_thesis_final_Jiaxuan-augmented.pdf
1.1 動機
在大數據時代,深度學習已經成為從數據中挖掘價值的主要工具。例如,深度學習為人臉識別(使用圖像數據)、機器翻譯(使用文本數據)和語音識別(使用音頻數據)等關鍵應用程序提供了強大的功能。與傳統的機器學習技術相比,深度學習代表了一種基于大規模數據集的自動化學習模式。此外,深度學習得益于指數級增長的計算資源和網絡規模的數據收集。由于這些原因,深度學習在研究和行業中得到了廣泛的普及。
現代深度學習模型主要是為文本和圖像等規則結構數據設計的。例如,遞歸神經網絡(rnn)[38,88]和變壓器[228]設計用于具有確定性排序的序列數據,卷積神經網絡(CNNs)[84,120]設計用于網格類數據。數據規律性的假設不僅導致了專門的高性能深度學習架構,而且簡化了深度學習管道的軟硬件實現,這有助于深度學習的成功。
然而,并不是所有形式的數據都是規則結構的。在本文中,我們特別關注圖結構數據。圖是一種通用的、功能強大的數據結構,它以簡潔的形式表示實體及其關系。圖結構數據在自然科學和社會科學中無處不在。例如,一個分子可以表示為一個圖,其中原子是節點,化學鍵是邊,一個社交網絡可以表示為一個圖,其中成員是節點,他們的友誼關系是邊。盡管圖結構數據無處不在,但它給深度學習模型帶來了獨特的挑戰,總結如下:
復雜的拓撲結構。圖中的節點可以任意地相互連接;因此,深度學習模型必須適應輸入數據的形狀/結構。此外,所有可能圖的空間是巨大的,因為有 個具有n個節點的可能簡單圖;因此,將圖映射到有意義的低維嵌入是極具挑戰性的。
Non-i.i.d。大自然。由于給定節點的語義意義取決于它與整個圖的連通性,因此我們不能將不同的節點視為i.i.d.分布的。因此,深度學習中廣泛采用的標準隨機梯度下降優化方法不能直接作用于圖(對于圖級任務,可以直接使用隨機梯度下降法。在這里,整個圖被視為單個數據點,通常假設為i.i.d)。
排列不變的性質。圖是一個無序的數據對象,它要求所有的深度學習算子對節點的排序不變量。
在本文中,我們的目標是用圖結構數據增強深度學習。我們的愿景是為圖形結構數據構建一個表達性強、使用方便的深度學習框架。我們希望這樣一個框架可以將深度學習在規則結構化數據上的成功轉化為圖結構數據,圖結構數據代表了更通用、更靈活的數據格式。同時,我們將展示一個成功的圖的深度學習框架,進而推動深度學習研究的總體進展。為了實現這些目標,我們建議賦予深度學習框架以能力,使其能夠將圖作為輸入、輸出和先驗。圖1.1總結了三個研究方向。
圖形作為輸入。我們開發了富有表現力和有效的深度學習方法,可以將圖形作為輸入,促進圖形的學習和理解。
作為輸出的圖形。我們使用深度學習模型闡明圖的生成過程,這促進了圖的發現和設計。
3.圖作為先驗。我們發現圖結構可以作為神經結構和機器學習任務的強大先驗,這為深度學習的設計和理解開辟了一個新的方向。
如何對不同設置下的序列數據建模是一個跨許多領域的重要機器學習問題,包括對時間序列數據、自然語言文本和事件流的預測。不同字段中的順序數據通常具有不同的特征。例如,自然語言文本可以被視為一個離散變量的序列,而傳感器網絡信號可以被視為一個連續向量空間中的多變量序列。為了在各種各樣的現實世界領域中開發成功的神經網絡模型,我們需要根據數據和問題的性質定制架構和算法。本文設計了新穎高效的神經網絡解決方案,用于序列建模和應用。具體來說,這些貢獻可以分為四部分。
第一部分重點研究了多變量序列數據中變量之間的相關性,如多傳感器的時間序列,并提出了新的算法,即深度可分圖卷積網絡(DSGC)(第二章)[60]和分解遞歸神經網絡(FRNN)(第三章)[63],以利用相關模式,提高預測精度。
第二部分側重于將人類先驗知識用于時序數據依賴模式的時間建模。具體地說,我們提出了一種新的方法,命名為長期和短期時間序列網絡(LSTNet)(第4章)[59],它被證明是特別有效的捕獲各種周期模式在不同的應用。
第三部分著重于序列分類任務中Transformers 的高效算法。具體來說,通過識別常用的Transformer架構中的計算冗余,并提出一種新的替代方案,即漏斗Transformers (第5章)[27],我們實現了更好的計算與精度之間的權衡。
第四部分側重于事件之間時間關系的建模/預測,其中的主要挑戰是從稀疏標記的數據中有效學習。我們通過結合高級數據增強、半監督學習和人類先驗知識的引入來應對這一挑戰(第6章)。因此,我們大大提高了這項任務的最先進性能。
深度神經網絡已經徹底改變了電力系統中的許多機器學習任務,從模式識別到信號處理。這些任務中的數據通常以歐幾里得域表示。然而,在電力系統中有越來越多的應用,其中的數據收集自非歐幾里得域,并表示為具有高維特征和節點間相互依賴的圖結構數據。圖結構數據的復雜性給現有的歐幾里得域深度神經網絡帶來了重大挑戰。近年來,在電力系統圖結構數據的深度神經網絡擴展方面出現了許多研究。本文對電力系統中的圖神經網絡(GNNs)進行了綜述。總結了幾種經典的GNNs結構范式 (圖卷積網絡、圖遞歸神經網絡、圖注意力網絡、圖生成網絡、時空圖卷積網絡以及混合形式的GNNs),并詳細綜述了其在電力系統故障診斷、功率預測、能流計算和數據生成等方面的關鍵應用。此外,還討論了GNN在電力系統中應用的主要問題和一些研究趨勢。
近年來,人們對學習圖結構數據表示的興趣大增。基于標記數據的可用性,圖表示學習方法一般分為三大類。第一種是網絡嵌入(如淺層圖嵌入或圖自動編碼器),它側重于學習關系結構的無監督表示。第二種是圖正則化神經網絡,它利用圖來增加半監督學習的正則化目標的神經網絡損失。第三種是圖神經網絡,目的是學習具有任意結構的離散拓撲上的可微函數。然而,盡管這些領域很受歡迎,但在統一這三種范式方面的工作卻少得驚人。在這里,我們的目標是彌合圖神經網絡、網絡嵌入和圖正則化模型之間的差距。我們提出了圖結構數據表示學習方法的一個綜合分類,旨在統一幾個不同的工作主體。具體來說,我們提出了一個圖編碼解碼器模型(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上找到。
本備忘單是機器學習手冊的濃縮版,包含了許多關于機器學習的經典方程和圖表,旨在幫助您快速回憶起機器學習中的知識和思想。
這個備忘單有兩個顯著的優點:
清晰的符號。數學公式使用了許多令人困惑的符號。例如,X可以是一個集合,一個隨機變量,或者一個矩陣。這是非常混亂的,使讀者很難理解數學公式的意義。本備忘單試圖規范符號的使用,所有符號都有明確的預先定義,請參見小節。
更少的思維跳躍。在許多機器學習的書籍中,作者省略了數學證明過程中的一些中間步驟,這可能會節省一些空間,但是會給讀者理解這個公式帶來困難,讀者會在中間迷失。