在科學研究中，從方法論上來講，都應“先見森林，再見樹木”。當前，人工智能學術研究方興未艾，技術迅猛發展，可謂萬木爭榮，日新月異。對于AI從業者來說，在廣袤的知識森林中，系統梳理脈絡，才能更好地把握趨勢。為此，我們精選國內外優秀的綜述文章，開辟“綜述專欄”，敬請關注。來源：知乎—努力努力再努力q

地址：//zhuanlan.zhihu.com/p/435040892

**聲明：**本文譯自教授Michael Bronstein在Medium上發布的博客。歡迎大家評論、批評指正翻譯中存在的任何問題。現代機器學習往往忽視了微分幾何和代數拓撲的相關知識，在本篇文章中，我會向讀者們展示如何以這兩個領域的相關知識為有力工具去重新解釋圖神經網絡以及圖神經網絡模型的一些共同困境。對稱性，無論我們考慮它的廣泛或者狹隘定義，它都是人類長久以來用于試圖理解和創造秩序、優美和完美的一種理念。Hermann Wey [1] 的這種富有詩意的描述強調了對稱性在科學研究中的基石作用。Felix Klein 在1872年的“Erlangen Programme”[2] 通過利用對稱性來描述了幾何學的特征，這不僅僅是數學上的突破，統一了幾何學領域而且還進一步導致了現代物理理論的發展，這些理論完全可以追溯到對稱的第一原理[3]。在幾何深度學習的發展中，類似的原理也出現在了機器學習中，幾何深度學習是通過組不變性和等方差性推導出大多數流行神經網絡架構的一般藍圖[4]。

圖神經網絡可以被視為幾何深度學習藍圖的一個特例，其構建組成是具有對稱群的域（在這種情況下特指具有置換群的圖）、域上的信號（節點特征）和此類信號的群-等變函數（消息傳遞）。幾何深度學習藍圖可以應用于不同的領域，例如結構化網格、非結構化網格或圖[5]。然而，雖然前兩者有明確的連續型模擬對象（結構化網格可以被認為是歐幾里德或更普遍的齊次空間如球體的離散化，而非結構化網格是二維流形的常見離散化），但對于圖卻沒有明確的的連續模擬對象[6]。這種不公平有點令人不安，并驅動我們仔細研究用于圖學習的連續模型。

Grid （結構化網格）、Mesh （非結構化網格）和圖是幾何深度學習藍圖中處理的領域的示例。然而，雖然前兩者具有連續類比（例如，結構化網格可以被視為歐幾里得空間的離散化，而非結構化網格是二維流形或曲面的常見離散化），但沒有針對圖的此類直接連續類比。

圖神經擴散----

圖神經網絡 (GNNs) 通過在圖上執行某種形式的消息傳遞來學習，特征在點與點之間依靠邊進行傳播。這種機制與圖上的擴散過程有關，可以用偏微分方程 (PDE) 的形式表示，稱為“擴散方程”。在最近的一篇論文 [7] 中，我們展示了這種具有非線性可學習擴散函數的 PDE 的離散化（稱為“圖神經擴散”或 GRAND）概括了一大類 GNN 架構，例如圖注意力網絡（GAT) [8]。PDE 思維方式提供了多種優勢，例如可以利用具有保證穩定性和收斂特性的高效數值求解器（例如隱式、多步、自適應和多重網格方案）。這些求解器中的一些在流行的 GNN 架構領域中沒有直接的類比，可能有望帶來新的有趣的圖神經網絡設計。由于我們考慮的擴散 PDE 可以被視為某些相關能量的梯度流 [9]，因此此類架構可能至少比典型架構更易于理解。同時，雖然 GRAND 模型在傳統 GNN 的層位置提供連續時間，但方程的空間部分仍然是離散的并且依賴于輸入圖。重要的是，在這個擴散模型中，域（圖）是固定的，并且在其上定義的一些屬性（特征）會演變。微分幾何中常用的一個概念是幾何流，它演化域本身的屬性 [10]。這個想法在 1990 年代被我的博士導師 Ron Kimmel 和他的合著者在圖像處理領域采納 [11]。他們將圖像建模為嵌入在聯合位置和顏色空間中的流形，并通過最小化嵌入的諧波能量的偏微分方程對其進行演化 [12]。這種稱為貝爾特拉米流的 PDE 具有各向同性非歐氏擴散的形式，并產生邊緣保留的圖像去噪。我們將此范式應用于“Beltrami 神經擴散”（BLEND）框架 [13] 中的圖形。圖的節點現在以位置和特征坐標為特征，兩者都是進化的，兩者都決定了擴散特性。在這種心態下，圖本身變成了一個輔助角色：它可以從位置坐標生成（例如作為 k 最近鄰圖）并在整個進化過程中重新連接。下圖說明了這個同步進化過程：

通過帶重新布線的 Beltrami 流對 Cora 圖的位置和特征分量的演變（顏色代表特征向量）。動畫：James Rowbottom。注：原文中有個非常漂亮的GIF動圖，由于尺寸過大超出知乎限制，請有心的同學們前往原文查看。如有解決方案也煩請告知，不勝感激。最近的工作格外關注圖神經網絡的表達能力問題。消息傳遞 GNNs 等效于 Weisfeiler-Lehman 圖同構測試 [14-16]，這是一種嘗試通過迭代顏色細化來確定兩個圖在結構上是否等效（“同構”）的經典方法。這個檢驗是必要但不充分的條件：事實上，Weisfeler-Lehman 可能認為一些非同構圖是等價的。下圖說明了傳遞 GNN 的消息“看到”了什么：兩個突出顯示的節點看起來無法區分，盡管圖顯然具有不同的結構：

Weisfeiler-Lehman 檢驗無法區分的兩個非同構圖的示例。圖改編自Sato [18]。

位置編碼----

解決此問題的常見方法是通過為節點分配一些表示圖中節點的角色或“位置”的附加特征來“著色”節點。在 Transformers [17]（它是在完整圖 [4] 上運行的注意力 GNN 的特例）中普及，位置編碼方法已成為增加圖神經網絡表達能力的常用方法。

位置編碼為圖的節點分配額外的特征，允許消息傳遞獲得比 Weisfeiler-Lehman 測試更高的表達能力。然而，在位置編碼的多種可能選擇中，沒有“規范”的。圖改編自Sato[18]。也許最直接的方法是賦予每個節點一個隨機特征[18]；然而，雖然更具表現力，但這種方法的泛化能力較差（因為不可能在兩個圖中重現隨機特征）。圖拉普拉斯算子 [19] 的特征向量提供了圖的鄰域保留嵌入，并已成功用作位置編碼。最后，我們在與 Giorgos Bouritsas 和 Fabrizio Frasca [20] 的論文中表明，圖的子結構計數可以用作位置或“結構”編碼的一種形式，可以證明它比基本的 Weisfeiler-Lehman 測試更強大。然而，對于位置編碼有多種選擇，如何選擇一個沒有明確的方法，也沒有明確的答案在哪種情況下哪種方法更有效。我相信像 BLEND 這樣的幾何流可以根據這個問題來解釋：通過非歐式擴散演化圖的位置坐標，位置編碼適用于下游任務。因此，答案是“視情況而定”：最佳位置編碼是手頭數據和任務的函數。

高階消息傳遞----

表達性的另一種選擇是停止從節點和邊的角度考慮圖。圖是被稱為細胞復合體的對象的例子，細胞復合體是代數拓撲領域的主要研究對象之一。在這個術語中，節點是 0-cells，邊是 1-cells。不必止步于此：我們可以構建如下圖所示的 2 個單元格（面），這使得我們之前示例中的兩個圖完全可區分：

在最近與 Cristian Bodnar 和 Fabrizio Frasca [21-22] 合著的兩篇論文中，我們表明有可能構建一種“提升變換”，用這種高階單元來增強圖，在其上可以執行更復雜的形式 的分層消息傳遞。這個方案可以證明比 Weisfeiler-Lehman 測試更具表現力，并且在計算化學中顯示出有希望的結果，其中許多分子表現出更好地建模為細胞復合物而不是圖形的結構。GNNs 的另一個常見困境是“過度擠壓”現象，或者由于輸入圖的某些結構特征（“瓶頸”）而導致消息傳遞無法有效傳播信息[23]。過度擠壓通常發生在體積呈指數增長的圖中，例如小世界網絡 [24] 以及依賴于遠程信息的問題。換句話說，GNN 在其上運行的輸入圖并不總是對消息傳遞友好。

“小世界”圖中快速增長的鄰居數量通常是 GNN 中觀察到的過度擠壓現象的根源。

過度擠壓、瓶頸和圖重繪----

根據經驗，觀察到將輸入圖與計算圖解耦并允許在不同的圖上傳遞消息有助于緩解問題；這種技術通常被稱為“圖重繪”。公平地說，許多流行的 GNNs 架構都實現了某種形式的圖重新布線，可以采用鄰域采樣（最初在 GraphSAGE 中提出以應對可擴展性 [25]）或多跳過濾器 [26] 的形式。上面討論的拓撲消息傳遞也可以看作是一種重新布線的形式，從而可以通過高階單元“捷徑”地在遠距離節點之間傳輸信息。Alon 和 Yahav [23] 表明，即使像使用全連接圖這樣簡單的方法也可能有助于改善圖機器學習問題中的過度擠壓。Klicpera 和合著者熱情地宣稱“擴散改進了圖學習”，提出了 GNNs（稱為“DIGL”）的通用預處理步驟，包括通過擴散過程對圖的連通性進行去噪 [27]。總體而言，盡管進行了重要的實證研究，但過度擠壓現象一直難以捉摸且理解不足。在最近的一篇論文 [28] 中，我們表明導致過度擠壓的瓶頸可歸因于圖的局部幾何特性。具體來說，通過定義 Ricci 曲率的圖類比，我們可以證明負彎曲的邊是罪魁禍首。這種解釋導致了類似于“反向 Ricci 流”的圖形重新布線程序，該程序通過外科手術去除了有問題的邊，并生成了一個更適合消息傳遞的圖形，同時在結構上與輸入的圖形相似。

使用基于擴散的方法（DIGL，中）和基于曲率的方法（Ricci，右）重新連接康奈爾圖（左）的示例。基于曲率的方法更顯著地減少了瓶頸，同時更忠實于原始圖結構。這些例子表明微分幾何和代數拓撲為圖機器學習中的重要和具有挑戰性的問題帶來了新的視角。在本系列的后續文章中，我將更詳細地展示如何使用這些領域的工具來解決圖神經網絡的上述問題。第二部分將討論代數拓撲如何提高 GNN 的表達能力。第三部分將處理幾何擴散偏微分方程。第四部分將展示過度擠壓現象如何與圖曲率相關，并提供一種受 Ricci 流啟發的圖形重新布線的幾何方法。

[1] H. Weyl, Symmetry (1952), Princeton University Press. [2]F. Klein, Vergleichende Betrachtungen über neuere geometrische Forschungen (1872). [3] J. Schwichtenberg, Physics from symmetry (2018), Springer. [4] M. M. Bronstein, J. Bruna, T. Cohen, and P. Veli?kovi?, Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges (2021); see an accompanying post and the project website. [5] In the above GDL proto-book, we call these the “5G” of Geometric Deep Learning. [6] Geometric graphs naturally arise as discrete models of objects living in a continuous space. A prominent example is molecules, modeled as graphs where every node represents an atom with 3D spatial coordinates. On the other hand, it is possible to embed general graphs into a continuous space, thus (approximately) realising their connectivity using the metric structure of some space. [7] B. Chamberlain, J. Rowbottom et al., GRAND: Graph Neural Diffusion (2021) ICML. [8] P. Veli?kovi? et al., Graph Attention Networks (2018) ICLR.[9] A gradient flow can be seen as a continuous analogy of gradient descent in variational problems. It arises from the optimality conditions (known in the calculus of variations as Euler-Lagrange equations) of a functional. [10] Geometric flows are gradient flows of functionals defined on manifolds. Perhaps the most famous of them is the Ricci flow, used by Grigori Perelman in the proof of the century-old Poincaré conjecture. Ricci flow evolves the Riemannian metric of the manifold and is structurally similar to the diffusion equation (hence often, with gross simplification, presented as “diffusion of the metric”). [11] N. Sochen et al., A general framework for low-level vision (1998) IEEE Trans. Image Processing 7(3):310–318 used a geometric flow minimising the embedding energy of a manifold as a model for image denoising. The resulting PDE is a linear non-euclidean diffusion equation ? = Δx (here Δ is the Laplace-Beltrami operator of the image represented as an embedded manifold), as opposed to the nonlinear diffusion ? = div(a(x)?x) used earlier by P. Perona and J. Malik, Scale-space and edge detection using anisotropic diffusion (1990) PAMI 12(7):629–639. [12] Beltrami flow minimises a functional known in string theory as the Polyakov action. In the Euclidean case, it reduces to the classical Dirichlet energy.

【導讀】ICLR 2020大會共收到近2600篇投稿，相比ICLR 2019的1580篇論文投稿，今年增幅約為62.5%, 競爭尤其激烈。 圖神經網絡（GNN）相關的論文依然很火爆，為此，專知小編提前為大家篩選了五篇Open代碼的GNN相關論文供參考和學習！后續小編還會整理ICLR 2020的相關論文和最新信息，盡請期待。

1、Unsupervised Learning of Graph Hierarchical Abstractions with Differentiable Coarsening and Optimal Transport

摘要：層次抽象是解決各種學科中大規模圖數據問題的一種方法。Coarsening就是這樣一種方法:它生成一個金字塔形的圖，其中下一層圖是上一層圖的結構總結。科學計算歷史悠久，許多Coarsening策略是基于數學驅動的啟發式算法發展起來的。近年來，人們對通過可微參數化設計可學習的層次方法的研究又有了新的興趣。這些方法與下游任務配對以進行監督學習。在這項工作中，我們提出了一種無監督的方法，稱為OTCoarsening，使用最優transport。OTCoarsening矩陣和transport成本矩陣都是參數化的，這樣就可以學習最優coarsening策略并針對給定的一組圖進行裁剪。結果表明，與監督方法相比，該方法能生成有意義的coarse圖，且具有較好的分類性能。

網址： //www.zhuanzhi.ai/paper/88cab6f00b90d041a7c39

代碼：

2、Fractional Graph Convolutional Networks (FGCN) for Semi-Supervised Learning

摘要：由于在許多應用程序(從社交網絡到區塊鏈到電網)中的高實用性，對非歐幾里德對象(如圖和流形)的深入學習繼續獲得越來越多的興趣。目前大多數可用的技術都是基于這樣的思想，即在spectral域中使用適當選擇的非線性可訓練濾波器進行卷積運算，然后使用有限階多項式逼近濾波器。然而，這種多項式逼近方法往往對圖結構的變化不具有魯棒性，而且主要用于捕獲全局圖拓撲。在本文中,我們提出一種新的Fractional Generalized Graph Convolutional Networks (FGCN)方法，該方法將L'evy Fights投射到圖上的隨機游走中，因此,可以更準確地解釋內在圖拓撲和大幅度提高分類性能,尤其是對異構圖形。

網址：

代碼：

3、Transfer Active Learning For Graph Neural Networks

摘要：圖神經網絡在節點分類等多種圖數據預測任務中已被證明是非常有效的。一般來說，訓練這些網絡需要大量的標記數據。然而，在現實中，在大型圖數據中獲取大量標記數據的成本可能非常高。本文研究了圖神經網絡的主動學習（active learning）問題。，即如何有效地標記圖上的節點來訓練圖神經網絡。我們將該問題描述為一個連續的決策過程，該過程對信息節點進行了連續的標記，并訓練了一個策略網絡來最大化圖神經網絡在特定任務中的性能。此外，我們還研究了如何學習一個通用的策略，用多個訓練圖在圖上標記節點，然后將學習到的策略遷移到不可見的圖上。在單一圖和多重訓練圖(遷移學習設置)的實驗結果證明了我們提出的方法在許多競爭性baseline上的有效性。

網址：

代碼：

4、Chordal-GCN: Exploiting sparsity in training large-scale graph convolutional networks

摘要：盡管圖卷積網絡(GCNs)在眾多應用中取得了令人矚目的成功，但大規模稀疏網絡的訓練仍然具有挑戰性。當前的算法需要大量的內存空間來存儲GCN輸出以及所有的中間嵌入。此外，這些算法大多涉及隨機抽樣或鄰接矩陣的近似，這可能會很不幸地丟失重要的結構信息。在這篇論文中，我們建議使用Chordal-GCN來進行半監督節點分類。該模型利用了精確的圖結構(即不需要采樣或近似)，而與原來的GCN相比，需要有限的內存資源。此外，它還利用了圖的稀疏模式和集群結構。該模型首先將一個大規模的稀疏網絡分解成幾個小的稠密子圖(稱為cliques)，然后構造一個clique樹。通過遍歷樹，GCN訓練是按clique進行的，并通過樹層次結構利用clique之間的連接。此外，我們在大規模數據集上實現了Chordal-GCN，并展示了優越的性能。

網址：

代碼：

5、Graph Neural Networks for Soft Semi-Supervised Learning on Hypergraphs

摘要：基于圖的半監督學習(SSL)將標簽分配給圖中最初未標記的頂點。圖神經網絡(GNNs)，特別是圖卷積網絡(GCNs)，啟發了當前基于圖的SSL問題的最新模型。GCN本質上假定目標標簽是數值或類別變量。然而，在許多實際應用中，如coauthorship網絡、推薦網絡等，頂點標簽可以很自然地用概率分布或直方圖來表示。此外，真實世界的網絡數據集具有復雜的關系，超出了兩兩關聯的范疇。這些關系可以通過超圖自然而靈活地建模。在本文中，我們探討了基于圖的直方圖SSL的GNN。受現實網絡中復雜關系(超越兩兩關系)的啟發，我們提出了一種新的有向超圖方法。我們的工作基于現有的graph-based SSL 直方圖，源自optimal transportation理論。本文的一個重要貢獻是在算法穩定性的框架下建立了單層GNN的泛化誤差邊界。我們還通過對真實數據的詳細實驗，證明了我們提出的方法的有效性。我們已經提供了代碼。

網址：

代碼：