這也是一篇滿分的工作。是由常年戰斗在圖領域的大佬 Pablo Barceló 團隊貢獻的。圖神經網絡（GNN）區分圖節點的能力最近已經通過用于檢查圖同構性的 Weisfeiler-Lehman（WL）測試進行了表征。但是，這種表征并不能解決哪些布爾節點分類器可以由 GNN 來表示 （即，將圖中的節點分類為真或假的函數）的問題。這篇文章專注于研究布爾分類器來解決上述問題。首先研究的是流行的GNNs（文中稱為 AC-GNNs）開始，在該類 GNN 中僅根據鄰居的特征，在連續的層中更新圖中每個節點的特征。實驗表明，這類 GNN 太弱而無法捕獲所有 FOC2（一種一階邏輯研究） 分類器，并提供了 AC-GNNs 可以捕獲的 FOC2 分類器最大子類的語法表征。然后，研究人員研究了，需要在 AC-GNNs 中添加什么來實現捕獲所有的 FOC2 分類器，實驗表明，添加 readout 就可以了。不僅可以更新節點的鄰居，還可以更新全局屬性向量。文章稱這類 GNNs 為 ACR-GNNs。
付費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元查看完整內容
圖神經網絡(GNNs)最近被成功地用于節點和圖的分類任務中，但GNNs對鄰近節點屬性之間的依賴關系建模，而不是對觀察到的節點標簽之間的依賴關系建模。在這項工作中，我們考慮了在監督和半監督設置中使用GNNs進行歸納節點分類的任務，其目標是合并標簽依賴項。因為當前的GNN不是通用的。為了提高現有GNN的表達能力，我們提出了一種通用的集體學習方法。我們的框架結合了集體分類和自監督學習的思想，并使用蒙特卡羅方法來采樣嵌入圖的歸納學習。我們評估了5個真實網絡數據集的性能，并證明了在各種最先進的GNN中，節點分類精度的一致性和顯著提高。
付費5元查看完整內容
在多標簽文本分類(MLTC)中，一個樣本可以屬于多個類。可以看出，在大多數MLTC任務中，標簽之間存在依賴關系或相互關系。現有的方法往往忽略了標簽之間的關系。本文提出了一種基于圖的注意力網絡模型來捕獲標簽間的注意依賴結構。圖注意力網絡使用一個特征矩陣和一個相關矩陣來捕獲和探索標簽之間的關鍵依賴關系，并為任務生成分類器。將生成的分類器應用于文本特征提取網絡(BiLSTM)獲得的句子特征向量，實現端到端訓練。注意力允許系統為每個標簽分配不同的權值給相鄰節點，從而允許系統隱式地學習標簽之間的依賴關系。在5個實際的MLTC數據集上驗證了模型的結果。與以往的先進模型相比，該模型具有相似或更好的性能。
付費5元查看完整內容
Graph Neural Networks (GNNs) have recently been used for node and graph classification tasks with great success, but GNNs model dependencies among the attributes of nearby neighboring nodes rather than dependencies among observed node labels. In this work, we consider the task of inductive node classification using GNNs in supervised and semi-supervised settings, with the goal of incorporating label dependencies. Because current GNNs are not universal (i.e., most-expressive) graph representations, we propose a general collective learning approach to increase the representation power of any existing GNN. Our framework combines ideas from collective classification with self-supervised learning, and uses a Monte Carlo approach to sampling embeddings for inductive learning across graphs. We evaluate performance on five real-world network datasets and demonstrate consistent, significant improvement in node classification accuracy, for a variety of state-of-the-art GNNs.
圖神經網絡
·
圖神經網絡是解決各種圖學習問題的有效的機器學習模型。盡管它們取得了經驗上的成功，但是GNNs的理論局限性最近已經被揭示出來。因此，人們提出了許多GNN模型來克服這些限制。在這次調查中，我們全面概述了GNNs的表達能力和可證明的強大的GNNs變體。
付費5元查看完整內容
題目： What Can Neural Networks Reason About?
摘 要:
神經網絡已經成功地完成了許多推理任務。從經驗上看，這些任務需要專門的網絡結構，例如，圖神經網絡(GNNs)在許多這樣的任務中表現良好，但較少結構的網絡會失敗。從理論上講，盡管網絡結構具有相同的表達能力，但人們對網絡結構為什么以及何時比其他網絡結構更能泛化的理解是有限的。本文通過研究網絡的計算結構與相關推理過程的算法結構之間的一致性，建立了一個描述網絡能很好學習哪些推理任務的框架。我們正式定義了這種算法對齊，并推導出一個隨更好的對齊而減小的樣本復雜度界。該框架為流行推理模型的經驗成功提供了一個解釋，并指出了它們的局限性。例如，我們通過一個強大的算法范例——動態規劃(DP)的鏡頭，將看似不同的推理任務，如直覺物理、可視化問題回答和最短路徑統一起來。我們證明了GNN與DP是一致的，因此可以解決這些問題。在一些推理任務中，我們的理論得到了實證結果的支持。
付費5元查看完整內容
簡介：
馬爾可夫邏輯網絡（MLN）將邏輯規則和概率圖形模型完美地結合在一起，可用于解決許多知識圖問題。但是，MLN的推理需要大量的計算，這使得MLN的工業規模應用非常困難。 近年來，圖神經網絡（GNN）已經成為解決大規模圖問題的有效工具。 盡管如此，GNN并未將先前的邏輯規則明確納入模型，并且可能需要許多帶有標簽的示例來完成目標任務。 在本文中，我們探索了MLN和GNN的組合，并使用圖神經網絡進行MLN的變異推理。 我們提出了一個名為ExpressGNN的GNN變體，該變體在表示能力和模型的簡單性之間取得了很好的平衡。 我們在幾個基準數據集上進行的廣泛實驗表明，ExpressGNN可以帶來有效而高效的概率邏輯推理。
付費5元查看完整內容
題目： Logical Expressiveness of Graph Neural Networks
摘要：
圖神經網絡(Graph Neural Networks, GNNs)是近年來在分子分類、知識圖譜補全等結構化數據處理領域中流行起來的一類機器學習體系結構。最近關于GNNs表達能力的研究已經建立了它們對圖中節點進行分類的能力與用于檢查圖同構的WeisfeilerLehman (WL)測試之間的緊密聯系。具體來說，這兩篇論文的作者分別觀察到，WL測試產生的節點分類總是細化了任何GNN產生的分類，而且有GNN可以重現WL測試。這些結果表明，GNNs在節點分類方面與WL測試一樣強大。然而，這并不意味著GNNs可以表達任何通過WL測試改進的分類器。我們的工作旨在回答以下問題:什么是可以用GNNs捕獲的節點分類器?在本文中，我們從邏輯的角度來看待這個問題，將其限制在FOC2中可表達的屬性上，即具有計數能力的一階邏輯的兩變量片段進行研究。
作者：
Pablo Barceló是智利天主教大學工程學院和數學學院數學與計算工程研究所所長，研究領域為數據庫理論、計算機科學中的邏輯、自動機理論。
付費5元查看完整內容
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191