【導讀】Graph Neural Network（GNN）由于具有分析圖結構數據的能力而受到了廣泛的關注。本文對Graph Neural Network進行了簡要介紹。它涵蓋了一些圖論，以便于理解圖和分析圖時遇到的問題。然后介紹了不同形式的Graph神經網絡及其原理。它還涵蓋了GNN可以做什么以及GNN的一些應用。
圖論
首先，我們需要知道什么是圖。圖是一種由兩個部分組成的數據結構：頂點和edge。它用作分析目標和實體之間成對關系的數學結構。通常，將圖定義為G =（V，E），其中V是一組節點，E是它們之間的邊。
圖通常由鄰接矩陣A表示。如果圖具有N個節點，則A的維數為（N x N）。人們有時會提供另一個特征矩陣來描述圖中的節點。如果每個節點都有F個特征，則特征矩陣X的維數為（N x F）。
為什么圖難以分析？
首先，在歐幾里得空間中不存在圖，這意味著它無法用我們熟悉的任何坐標系表示。與其他類型的數據（例如波，圖像或時間序列信號）相比，這使得圖數據的解釋更加困難（“文本”也可以視為時間序列），可以輕松地將其映射為2-D或3-D歐幾里德空間。
其次，圖沒有固定的形式。為什么？看下面的例子。圖（A）和圖（B）具有完全不同的結構和外觀。但是，當我們將其轉換為鄰接矩陣表示形式時，兩個圖具有相同的鄰接矩陣（如果不考慮邊的權重）。那么我們應該考慮這兩個圖是相同還是不同？
最后，一般來說，圖很難直觀地顯示出來以供人類解釋。我不是在談論像上面的例子這樣的小圖。我說的是涉及數百或數千個節點的巨型圖。它的維數很高，節點密集地分組在一起，甚至使人難以理解圖。因此，為該任務訓練機器是具有挑戰性的。以下示例顯示了對集成電路中邏輯門進行建模的圖。
Example of a giant graph: circuit netlist. Figure from J. Baehr et. al. “Machine Learning and Structural Characteristics of Reverse Engineering”
為什么要使用圖？
人們選擇使用圖的原因可以歸納為以下幾點：
- 圖提供了一種更好的方式來處理諸如關系和交互之類的抽象概念。它們還提供了直觀的視覺方式來思考這些概念。圖也構成了在社會環境中分析關系的自然基礎。
- 圖可以通過將問題簡化為更簡單的表示形式來解決更復雜的問題，或者從不同的角度將問題轉換為表示形式。
- 圖論和概念用于研究和建模社交網絡，欺詐模式，功耗模式，病毒性以及在社交媒體中的影響力。社交網絡分析（SNA）可能是圖論在數據科學中最著名的應用。
傳統圖分析方法
傳統方法主要基于算法，例如：
- 搜索算法，例如BFS，DFS
- 最短路徑算法，例如Dijkstra算法，最近鄰居
- 生成樹算法，例如Prim算法
- 聚類方法，例如高度連接的組件，k均值 這種算法的局限性在于，在應用該算法之前，我們需要以一定的置信度獲得圖的先驗知識。換句話說，它對我們研究圖本身沒有任何意義。最重要的是，沒有辦法執行圖級別分類。
圖神經網絡
所謂的圖神經網絡是一種可以直接應用于圖的神經網絡。它為節點級別，邊緣級別和圖級別的預測任務提供了一種方便的方法。
文獻中主要有三種類型的圖神經網絡：
- 遞歸圖神經網絡
- 空間卷積網絡
- 譜卷積網絡
GNN的直覺是，節點自然是由其鄰居和連接定義的。為了理解這一點，我們可以簡單地想象一下，如果刪除節點周圍的鄰居和連接，則該節點將丟失其所有信息。因此，節點的鄰居和與鄰居的連接定義了節點的概念。
考慮到這一點，我們然后給每個節點一個狀態（x）來表示其概念。我們可以使用節點狀態（x）產生輸出（o），即有關概念的決策。節點的最終狀態（x_n）通常稱為“節點嵌入”。所有GNN的任務是通過查看其相鄰節點上的信息來確定每個節點的“節點嵌入”。 我們將從圖神經網絡，循環圖神經網絡或RecGNN的經典版本開始。
遞歸圖神經網絡
正如原始GNN論文中介紹的那樣，RecGNN是基于Banach不動點定理的假設而構建的。Banach不動點定理指出：（X，d）是一個完整的度量空間，而（T：X→X）是一個壓縮映射。然后，T具有唯一的不動點（x ?），對于任何x∈X，n→∞的序列T_n（x）收斂到（x ?）。這意味著，如果我申請的映射T上X為?倍，X ^ K在幾乎等于x ^（K-1），即：
RecGNN定義了一個參數化函數f_w：
其中L_N，l_co，x_ne，l_ne 表示當前節點的特征[n]，節點的邊緣[n]，相鄰節點的狀態，與相鄰節點的功能。（在原始論文中，作者將節點特征稱為節點標簽。這可能會造成一些混亂。）
An illustration of node state update based on the information in its neighbors. Figure from “The Graph Neural Network Model” 最終，在經過k次迭代之后，最終的節點狀態將用于生成輸出，以決定每個節點。輸出函數定義為：
空間卷積網絡
空間卷積網絡的直覺類似于著名的CNN，后者主導著圖像分類和分割任務的文獻。要了解圖像上的CNN，您可以查看這篇文章，其中詳細說明了CNN。
簡而言之，在圖像上進行卷積的想法是對中心像素周圍的相鄰像素求和，該像素由參數化大小和可學習權重的濾波器指定。空間卷積網絡通過將相鄰節點的特征聚合到中心節點中采用了相同的思想。
Left: Convolution on a regular graph such as an image. Right: Convolution on the arbitrary graph structure. Figure from “A Comprehensive Survey on Graph Neural Networks”
譜卷積網絡
與其他類型的GNN相比，這種類型的圖卷積網絡具有非常強大的數學基礎。譜卷積網絡建立在圖信號處理理論的基礎上。并通過簡化和逼近圖卷積。 通過Chebyshev多項式逼近 （Hammond et al。2011），圖卷積可以簡化為以下形式：
進一步簡化后，GCN論文提出了一種2層神經網絡結構，可以用以下等式描述：
其中A_head是原始圖鄰接矩陣A的預處理拉普拉斯算子。（有關數學的詳細信息，請參見GCN論文。將需要大量的精力來進行充分說明。）
如果您有一些機器學習經驗，則此公式看起來非常熟悉。這不過是常用的兩個完全連接的層結構。但是在這種情況下，它確實可以用作圖卷積。我將在下面說明為什么它可以執行圖卷積。
Example of a graph with a feature assigned to each node. Figured by author
讓我們考慮一下，我們有一個包含4個節點的簡單圖。如上圖所示，為這些節點中的每個節點分配了一個特征矩陣。圖鄰接矩陣和特征矩陣很容易得出，如下所示：
Example of the adjacency matrix and feature matrix. Figure by author
注意，鄰接矩陣的對角線故意更改為“ 1”，以為每個節點添加一個自環。當我們執行特征聚合時，這將包括每個節點本身的特征。 然后，我們執行A x X（為簡單起見，我們先忽略A的拉普拉斯算子和權重矩陣W。）
Example of graph convolution by matrix multiplication. Figure by author
矩陣乘法的結果顯示在最右邊的矩陣中。讓我們以第一個節點的結果功能為例。不難發現結果是[節點1]的所有特征之和，包括[節點1]本身的特征，并且[節點4]中的特征不包括在內，因為它不是[節點1]的鄰居。。在數學上，僅當存在邊時，圖的鄰接矩陣才具有值“ 1”，否則具有“ 0”。這使得矩陣乘法成為連接到參考節點的節點的特征之和。 因此，頻譜卷積網絡和空間卷積網絡盡管是在不同的基礎上開始的，但是它們共享相同的傳播規則。 當前可用的所有卷積圖神經網絡共享相同的格式。他們都嘗試學習通過該消息傳遞過程傳遞節點信息并更新節點狀態的功能。 任何圖神經網絡可被表達為與消息傳遞神經網絡（J. Gilmer et al. , 2017）的消息傳遞功能，節點更新功能和讀出功能。
GNN可以做什么？
GNN解決的問題可以大致分為三類：
- 節點分類
- 鏈接預測
- 圖分類 在節點分類中，任務是預測圖中每個節點的節點嵌入。通常以半監督的方式訓練此類問題，其中僅對部分圖進行標記。節點分類的典型應用包括引文網絡，Reddit帖子，Youtube視頻和Facebook朋友關系。 在鏈接預測中，任務是了解圖中實體之間的關系，并預測兩個實體之間是否存在連接。例如，推薦系統可被視為鏈接預測問題，其中模型被賦予一組用戶對不同產品的評論，任務是預測用戶的偏好并調整推薦系統以根據用戶推送更多相關感興趣的產品。 在圖分類中，任務是將整個圖分類為不同的類別。它類似于圖像分類，但是目標變為圖域。有許多工業問題可以應用圖分類，例如在化學，生物醫學，物理學中，模型被賦予分子結構并被要求將目標分類為有意義的類別。它加快了對原子，分子或任何其他結構化數據類型的分析。
一些實際的應用
在了解了GNN可以執行哪種類型的分析之后，您一定想知道我可以對圖進行哪些實際應用。好了，本節將為您提供有關GNN實際應用的更多見解。
自然語言處理中的GNN
GNN被廣泛使用在自然語言處理（NLP）中。實際上，這也是GNN最初開始的地方。如果您中的某些人具有NLP經驗，則必須考慮到文本應該是一種序列或時間數據，則可以由RNN或LTSM最好地描述。然而，GNN則從完全不同的角度解決了這個問題。GNN利用單詞或文檔的內部關系來預測類別。例如，引文網絡嘗試根據論文引文關系和其他論文中引用的詞來預測網絡中每篇論文的標簽。它也可以通過查看句子的不同部分而不是像RNN或LTSM中那樣的純粹序列來構建語法模型。
計算機視覺中的GNN
許多基于CNN的方法已經在圖像中的目標檢測中達到了最新的性能，但是我們還不知道目標之間的關系。GNN在CV中的一種成功應用是使用圖來建模基于CNN的檢測器檢測到的物體之間的關系。從圖像中檢測到目標后，將它們輸入到GNN推理中以進行關系預測。GNN推斷的結果是生成的圖，該圖對不同目標之間的關系進行建模。
Scene Graph Generation. Figure from D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in Proc. of CVPR, 2017
CV中另一個有趣的應用是根據圖描述生成圖像。這可以解釋為幾乎與上述應用相反。圖像生成的傳統方式是使用GAN或自動編碼器生成文本到圖像。從圖到圖像的生成不是使用文本來描述圖像，而是提供了有關圖像語義結構的更多信息。
Image generated from scene graphs. Figure from J. Johnson, A. Gupta, and L. Fei-Fei, “Image generation from scene graphs,” in Proc. of CVPR, 2018 我想分享的最有趣的應用是零樣本學習（ZSL）。您可以找到這篇文章，以全面了解ZSL。總之，ZSL是想學給定的一類分類NO（目標類別的）訓練樣本。這是非常具有挑戰性的，因為如果沒有給出訓練樣本，我們需要讓模型在邏輯上“思考”以識別目標。例如，如果給了我們三張圖像（如下圖所示），并告訴我們在其中找到“ okapi”。我們以前可能沒有看過“okapi”。但是，如果我們還得到信息，“okapi”是一種有四只腿，斑馬紋皮膚的鹿面動物，那么我們就不難確定哪個是“okapii”。典型的方法是通過將檢測到的特征轉換為文本來模擬這種“思考過程”。但是，文本編碼彼此獨立。很難對文本描述之間的關系進行建模。換句話說，圖表示很好地模擬了這些關系。
Figure from X. Wang, Y. Ye, and A. Gupta, “Zero-shot recognition via semantic embeddings and knowledge graphs,” in CVPR 2018
其他領域的GNN
GNN的更多實際應用包括人類行為檢測，交通控制，分子結構研究，推薦系統，程序驗證，邏輯推理，社會影響預測以及對抗攻擊。下面顯示了對社交網絡中人際關系建模的圖表。GNN可用于將人們分為不同的社區群體。
結論
我們在本文中介紹了一些圖論，并強調了分析圖的重要性。人們總是將機器學習算法視為“ 黑匣子 ”。大多數機器學習算法僅從訓練數據的特征中學習，但沒有實際的邏輯可以執行。使用形，我們也許能夠將一些“邏輯”傳遞給機器，并使其更自然地“思考”。
GNN仍然是一個相對較新的領域，值得更多的研究關注。它是分析圖數據的強大工具。但是，它不僅限于圖中的問題。它可以很容易地推廣到任何可以通過圖建模的研究中。圖建模是分析問題的自然方法。
參考鏈接：
付費5元查看完整內容
相關內容
題目： Continuous Graph Neural Networks
摘要：
本文建立了圖神經網絡與傳統動力系統之間的聯系。我們提出了持續圖神經網絡(CGNN)，它將現有的圖神經網絡與離散動力學進行了一般化，因為它們可以被視為一種特定的離散化方案。關鍵思想是如何表征節點表示的連續動力學，即關于時間的節點表示的導數。受現有的基于擴散的圖方法(如社交網絡上的PageRank和流行模型)的啟發，我們將導數定義為當前節點表示、鄰節點表示和節點初始值的組合。我們提出并分析了兩種可能的動態圖，包括節點表示的每個維度(又名特征通道)各自改變或相互作用的理論證明。所提出的連續圖神經網絡在過度平滑方面具有很強的魯棒性，因此允許我們構建更深層次的網絡，進而能夠捕獲節點之間的長期依賴關系。在節點分類任務上的實驗結果證明了我們提出的方法在和基線對比的有效性。
介紹
圖神經網絡(GNNs)由于其在節點分類等多種應用中的簡單性和有效性而受到越來越多的關注;、鏈接預測、化學性質預測、自然語言理解。GNN的基本思想是設計多個圖傳播層，通過聚合鄰近節點的節點表示和節點本身的表示，迭代地更新每個節點表示。在實踐中，對于大多數任務，幾層(兩層或三層)通常就足夠了，更多的層可能導致較差的性能。
改進GNNs的一個關鍵途徑是能夠建立更深層次的網絡，以了解數據和輸出標簽之間更復雜的關系。GCN傳播層平滑了節點表示，即圖中相鄰的節點變得更加相似。當我們堆疊越來越多的層時，這會導致過度平滑，這意味著節點表示收斂到相同的值，從而導致性能下降。因此，重要的是緩解節點過平滑效應，即節點表示收斂到相同的值。
此外，對于提高我們對GNN的理論理解，使我們能夠從圖結構中描述我們可以學到的信號，這是至關重要的。最近關于理解GCN的工作(Oono和Suzuki, 2020)認為GCN是由離散層定義的離散動力系統。此外，Chen等人(2018)證明了使用離散層并不是構建神經網絡的唯一視角。他們指出，帶有剩余連接的離散層可以看作是連續ODE的離散化。他們表明，這種方法具有更高的記憶效率，并且能夠更平滑地建模隱藏層的動態。
我們利用基于擴散方法的連續視角提出了一種新的傳播方案，我們使用來自常微分方程(即連續動力系統)的工具進行分析。事實上，我們能夠解釋我們的模型學習了什么表示，以及為什么它不會遭受在GNNs中常見的過度平滑問題。允許我們建立更深層次的網絡，也就是說我們的模型在時間價值上運行良好。恢復過平滑的關鍵因素是在連續設置中使用了最初在PageRank中提出的原始分布。直觀上，重新開始分布有助于不忘記鄰接矩陣的低冪次信息，從而使模型收斂到有意義的平穩分布。
本文的主要貢獻是:
- 基于PageRank和擴散方法，提出了兩個連續遞增模型容量的ODEs;
- 我們從理論上分析了我們的層學習的表示，并表明當t → ∞我們的方法接近一個穩定的不動點，它捕獲圖結構和原始的節點特征。因為我們在t→∞時是穩定的，我們的網絡可以有無限多個“層”，并且能夠學習遠程依賴關系;
- 我們證明了我們的模型的記憶是高效的，并且對t的選擇是具有魯棒性的。除此之外，我們進一步證明了在節點分類任務上，我們的模型能夠比許多現有的最先進的方法表現更好。
付費5元查看完整內容
主題： Graph Neural Networks with Composite Kernels
摘要： 近年來，對圖結構化數據的學習引起了越來越多人的興趣。諸如圖卷積網絡（GCN）之類的框架已經證明了它們在各種任務中捕獲結構信息并獲得良好性能的能力。在這些框架中，節點聚合方案通常用于捕獲結構信息：節點的特征向量是通過聚集其相鄰節點的特征來遞歸計算的。但是，大多數聚合方案都將圖中的所有連接均等化，而忽略了節點特征的相似性。本文從內核權重的角度重新解釋了節點聚合，并提出了一個框架來考慮特征相似性。我們表明歸一化的鄰接矩陣等效于Kerin空間中基于鄰居的內核矩陣。然后，我們提出功能聚集作為基于原始鄰居的內核和可學習的內核的組成，以在特征空間中編碼特征相似性。我們進一步展示了如何將所提出的方法擴展到圖注意力網絡（GAT）。實驗結果表明，在一些實際應用中，我們提出的框架具有更好的性能。
付費5元查看完整內容
1、Approximation Ratios of Graph Neural Networks for Combinatorial Problems
作者：Ryoma Sato， Makoto Yamada， Hisashi Kashima;
摘要：本文從理論的角度研究了圖神經網絡(GNNs)在學習組合問題近似算法中的作用。為此，我們首先建立了一個新的GNN類，它可以嚴格地解決比現有GNN更廣泛的問題。然后，我們彌合了GNN理論和分布式局部算法理論之間的差距，從理論上證明了最強大的GNN可以學習最小支配集問題的近似算法和具有一些近似比的最小頂點覆蓋問題比率，并且沒有GNN可以執行比這些比率更好。本文首次闡明了組合問題中GNN的近似比。此外，我們還證明了在每個節點特征上添加著色或弱著色可以提高這些近似比。這表明預處理和特征工程在理論上增強了模型的能力。
網址：//www.zhuanzhi.ai/paper/9cad40c81920dfd71fa91e4ddf778616
2、D-VAE: A Variational Autoencoder for Directed Acyclic Graphs
作者：Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, Yixin Chen;
摘要：圖結構數據在現實世界中是豐富的。在不同的圖類型中，有向無環圖(DAG)是機器學習研究人員特別感興趣的，因為許多機器學習模型都是通過DAG上的計算來實現的，包括神經網絡和貝葉斯網絡。本文研究了DAG的深度生成模型，提出了一種新的DAG變分自編碼器(D-VAE)。為了將DAG編碼到潛在空間中，我們利用了圖神經網絡。我們提出了一個異步消息傳遞方案，它允許在DAG上編碼計算，而不是使用現有的同步消息傳遞方案來編碼局部圖結構。通過神經結構搜索和貝葉斯網絡結構學習兩項任務驗證了該方法的有效性。實驗表明，該模型不僅生成了新穎有效的DAG，還可以生成平滑的潛在空間，有助于通過貝葉斯優化搜索具有更好性能的DAG。
網址：
3、End to end learning and optimization on graphs
作者：Bryan Wilder, Eric Ewing, Bistra Dilkina, Milind Tambe;
摘要：在實際應用中，圖的學習和優化問題常常結合在一起。例如，我們的目標可能是對圖進行集群，以便檢測有意義的社區(或者解決其他常見的圖優化問題，如facility location、maxcut等)。然而，圖或相關屬性往往只是部分觀察到，引入了一些學習問題，如鏈接預測，必須在優化之前解決。我們提出了一種方法，將用于常見圖優化問題的可微代理集成到用于鏈接預測等任務的機器學習模型的訓練中。這允許模型特別關注下游任務，它的預測將用于該任務。實驗結果表明，我們的端到端系統在實例優化任務上的性能優于將現有的鏈路預測方法與專家設計的圖優化算法相結合的方法。
網址：
4、Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
作者：Simon S. Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, Keyulu Xu;
摘要：雖然圖內核(graph kernel，GK)易于訓練并享有可證明的理論保證，但其實際性能受其表達能力的限制，因為內核函數往往依賴于圖的手工組合特性。與圖內核相比，圖神經網絡通常具有更好的實用性能，因為圖神經網絡使用多層結構和非線性激活函數來提取圖的高階信息作為特征。然而，由于訓練過程中存在大量的超參數，且訓練過程具有非凸性，使得GNN的訓練更加困難。GNN的理論保障也沒有得到很好的理解。此外，GNN的表達能力隨參數的數量而變化，在計算資源有限的情況下，很難充分利用GNN的表達能力。本文提出了一類新的圖內核，即圖神經切線核(GNTKs)，它對應于通過梯度下降訓練的無限寬的多層GNN。GNTK充分發揮了GNN的表現力，繼承了GK的優勢。從理論上講，我們展示了GNTK可以在圖上學習一類平滑函數。根據經驗，我們在圖分類數據集上測試GNTK并展示它們實現了強大的性能。
網址：
5、HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
作者：Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, Partha Talukdar;
摘要：在許多真實世界的網絡數據集中，如co-authorship、co-citation、email communication等，關系是復雜的，并且超越了成對關聯。超圖（Hypergraph）提供了一個靈活而自然的建模工具來建模這種復雜的關系。在許多現實世界網絡中，這種復雜關系的明顯存在，自然會激發使用Hypergraph學習的問題。一種流行的學習范式是基于超圖的半監督學習(SSL)，其目標是將標簽分配給超圖中最初未標記的頂點。由于圖卷積網絡(GCN)對基于圖的SSL是有效的，我們提出了HyperGCN，這是一種在超圖上訓練用于SSL的GCN的新方法。我們通過對真實世界超圖的詳細實驗證明HyperGCN的有效性，并分析它何時比最先進的baseline更有效。
網址：
6、Social-BiGAT: Multimodal Trajectory Forecasting using Bicycle-GAN and Graph Attention Networks
作者：Vineet Kosaraju, Amir Sadeghian, Roberto Martín-Martín, Ian Reid, S. Hamid Rezatofighi, Silvio Savarese;
摘要：從自動駕駛汽車和社交機器人的控制到安全監控，預測場景中多個交互主體的未來軌跡已成為許多不同應用領域中一個日益重要的問題。這個問題由于人類之間的社會互動以及他們與場景的身體互動而變得更加復雜。雖然現有的文獻探索了其中的一些線索，但它們主要忽略了每個人未來軌跡的多模態性質。在本文中，我們提出了一個基于圖的生成式對抗網絡Social-BiGAT，它通過更好地建模場景中行人的社交互來生成真實的多模態軌跡預測。我們的方法是基于一個圖注意力網絡(GAT)學習可靠的特征表示(編碼場景中人類之間的社會交互)，以及一個反方向訓練的循環編解碼器體系結構(根據特征預測人類的路徑)。我們明確地解釋了預測問題的多模態性質，通過在每個場景與其潛在噪聲向量之間形成一個可逆的變換，就像在Bicycle-GAN中一樣。我們表明了，與現有軌跡預測基準的幾個baseline的比較中，我們的框架達到了最先進的性能。
網址：
7、Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching
作者：Hongteng Xu, Dixin Luo, Lawrence Carin;
摘要：我們提出了一種可擴展的Gromov-Wasserstein learning (S-GWL) 方法，并建立了一種新的、理論支持的大規模圖分析范式。該方法基于Gromov-Wasserstein discrepancy，是圖上的偽度量。給定兩個圖，與它們的Gromov-Wasserstein discrepancy相關聯的最優傳輸提供了節點之間的對應關系，從而實現了圖的匹配。當其中一個圖具有獨立但自連接的節點時（即，一個斷開連接的圖），最優傳輸表明了其他圖的聚類結構，實現了圖的劃分。利用這一概念，通過學習多觀測圖的Gromov-Wasserstein barycenter圖，將該方法推廣到多圖的劃分與匹配; barycenter圖起到斷開圖的作用，因為它是學習的，所以聚類也是如此。該方法將遞歸K分割機制與正則化近似梯度算法相結合，對于具有V個節點和E條邊的圖，其時間復雜度為O(K(E+V) logk V)。據我們所知，我們的方法是第一次嘗試使Gromov-Wasserstein discrepancy適用于大規模的圖分析，并將圖的劃分和匹配統一到同一個框架中。它優于最先進的圖劃分和匹配方法，實現了精度和效率之間的平衡。
網址：
8、Universal Invariant and Equivariant Graph Neural Networks
作者：Nicolas Keriven, Gabriel Peyré;
摘要：圖神經網絡(GNN)有多種形式，但應該始終是不變的(輸入圖節點的排列不會影響輸出)或等變的(輸入的排列置換輸出)。本文考慮一類特殊的不變和等變網絡，證明了它的一些新的普適性定理。更確切地說，我們考慮具有單個隱藏層的網絡，它是通過應用等變線性算子、點態非線性算子和不變或等變線性算子形成的信道求和而得到的。最近，Maron et al. (2019b)指出，通過允許網絡內部的高階張量化，可以獲得通用不變的GNN。作為第一個貢獻，我們提出了這個結果的另一種證明，它依賴于實值函數代數的Stone-Weierstrass定理。我們的主要貢獻是將這一結果推廣到等變情況，這種情況出現在許多實際應用中，但從理論角度進行的研究較少。證明依賴于一個新的具有獨立意義的廣義等變函數代數Stone-Weierstrass定理。最后，與以往許多考慮固定節點數的設置不同，我們的結果表明，由一組參數定義的GNN可以很好地近似于在不同大小的圖上定義的函數。
網址：
付費5元查看完整內容
題目： Graph Neural Networks:A Review of Methods and Applications
簡介： 許多學習任務需要處理圖形數據，該圖形數據包含元素之間的關系信息。對物理系統進行建模，學習分子指紋，預測蛋白質界面以及對疾病進行分類，都需要從圖輸入中學習模型。在諸如從文本和圖像之類的非結構數據中學習的其他領域中，對提取結構的推理，例如句子的依存關系樹和圖像的場景圖，是一個重要的研究課題，它也需要圖推理模型。圖神經網絡（GNN）是連接器模型，可通過在圖的節點之間傳遞消息來捕獲圖的依賴性。與標準神經網絡不同，圖神經網絡保留一種狀態，該狀態可以表示來自其鄰域的任意深度的信息。盡管已經發現難以訓練原始圖神經網絡來固定點，但是網絡體系結構，優化技術和并行計算的最新進展已使他們能夠成功學習。近年來，基于圖卷積網絡（GCN）和門控圖神經網絡（GGNN）的系統已經在上述許多任務上展示了突破性的性能。在本綜述中，我們對現有的圖神經網絡模型進行了詳細的回顧，對應用程序進行了系統分類，并提出了四個未解決的問題，供以后研究。
作者簡介： 周杰，教授,清華大學自動化系黨委書記，教授，博士生導師。
付費5元查看完整內容
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191