題目: Graph Neural Networks: A Review of Methods and Applications
摘要: 許多學習任務都需要處理包含元素間豐富關系信息的圖形數據。建模物理系統、學習分子指紋、預測蛋白質界面和疾病分類需要一個模型從圖形輸入中學習。在文本、圖像等非結構化數據的學習等領域,對句子的依存樹、圖像的場景圖等提取的結構進行推理是一個重要的研究課題,同時也需要建立圖形推理模型。圖神經網絡(GNNs)是通過圖節點之間的信息傳遞來獲取圖的依賴性的連接模型。與標準神經網絡不同,圖神經網絡保留了一種狀態,這種狀態可以以任意深度表示來自其鄰域的信息。雖然原始GNNs已經被發現很難訓練到固定的點,但是最近在網絡結構、優化技術和并行計算方面的進展已經使它能夠成功地學習。近年來,基于圖形卷積網絡(GCN)、圖形注意網絡(GAT)、門控圖形神經網絡(GGNN)等圖形神經網絡變體的系統在上述許多任務上都表現出了突破性的性能。在這項調查中,我們提供了一個詳細的檢討現有的圖形神經網絡模型,系統分類的應用,并提出了四個開放的問題,為今后的研究。
作者簡介: Jie Zhou,CS的研究生,從事系統研究,主要研究計算機安全。他畢業于廈門大學,在羅切斯特大學獲得碩士學位及博士學位。
Zhiyuan Liu,清華大學計算機系NLP實驗室副教授。
題目: Continuous Graph Neural Networks
摘要:
本文建立了圖神經網絡與傳統動力系統之間的聯系。我們提出了持續圖神經網絡(CGNN),它將現有的圖神經網絡與離散動力學進行了一般化,因為它們可以被視為一種特定的離散化方案。關鍵思想是如何表征節點表示的連續動力學,即關于時間的節點表示的導數。受現有的基于擴散的圖方法(如社交網絡上的PageRank和流行模型)的啟發,我們將導數定義為當前節點表示、鄰節點表示和節點初始值的組合。我們提出并分析了兩種可能的動態圖,包括節點表示的每個維度(又名特征通道)各自改變或相互作用的理論證明。所提出的連續圖神經網絡在過度平滑方面具有很強的魯棒性,因此允許我們構建更深層次的網絡,進而能夠捕獲節點之間的長期依賴關系。在節點分類任務上的實驗結果證明了我們提出的方法在和基線對比的有效性。
介紹
圖神經網絡(GNNs)由于其在節點分類等多種應用中的簡單性和有效性而受到越來越多的關注;、鏈接預測、化學性質預測、自然語言理解。GNN的基本思想是設計多個圖傳播層,通過聚合鄰近節點的節點表示和節點本身的表示,迭代地更新每個節點表示。在實踐中,對于大多數任務,幾層(兩層或三層)通常就足夠了,更多的層可能導致較差的性能。
改進GNNs的一個關鍵途徑是能夠建立更深層次的網絡,以了解數據和輸出標簽之間更復雜的關系。GCN傳播層平滑了節點表示,即圖中相鄰的節點變得更加相似。當我們堆疊越來越多的層時,這會導致過度平滑,這意味著節點表示收斂到相同的值,從而導致性能下降。因此,重要的是緩解節點過平滑效應,即節點表示收斂到相同的值。
此外,對于提高我們對GNN的理論理解,使我們能夠從圖結構中描述我們可以學到的信號,這是至關重要的。最近關于理解GCN的工作(Oono和Suzuki, 2020)認為GCN是由離散層定義的離散動力系統。此外,Chen等人(2018)證明了使用離散層并不是構建神經網絡的唯一視角。他們指出,帶有剩余連接的離散層可以看作是連續ODE的離散化。他們表明,這種方法具有更高的記憶效率,并且能夠更平滑地建模隱藏層的動態。
我們利用基于擴散方法的連續視角提出了一種新的傳播方案,我們使用來自常微分方程(即連續動力系統)的工具進行分析。事實上,我們能夠解釋我們的模型學習了什么表示,以及為什么它不會遭受在GNNs中常見的過度平滑問題。允許我們建立更深層次的網絡,也就是說我們的模型在時間價值上運行良好。恢復過平滑的關鍵因素是在連續設置中使用了最初在PageRank中提出的原始分布。直觀上,重新開始分布有助于不忘記鄰接矩陣的低冪次信息,從而使模型收斂到有意義的平穩分布。
本文的主要貢獻是:
題目: Introduction to Graph Neural Networks
簡介:
在復雜的實際應用中,圖是有用的數據結構,例如對物理系統進行建模,學習分子指紋,控制交通網絡以及在社交網絡中推薦朋友。但是,這些任務需要處理包含元素之間的豐富關系信息且無法通過傳統深度學習模型(例如卷積神經網絡(CNN)或遞歸神經網絡(RNN))妥善處理的非歐氏圖數據。圖中的節點通常包含有用的特征信息,這些信息在大多數無監督的表示學習方法(例如,網絡嵌入方法)中無法很好地解決。提出了圖神經網絡(GNN)來結合特征信息和圖結構,以通過特征傳播和聚集學習更好的圖表示。由于其令人信服的性能和高解釋性,GNN最近已成為一種廣泛應用的圖形分析工具。本書全面介紹了圖神經網絡的基本概念,模型和應用。首先介紹了香草GNN模型。然后介紹了vanil la模型的幾種變體,例如圖卷積網絡,圖遞歸網絡,圖注意力網絡,圖殘差網絡和一些通用框架。還包括不同圖類型的變體和高級訓練方法。對于GNN的應用,該書將min分為結構,非結構和其他場景,然后介紹了解決這些任務的幾種典型模型。最后,最后幾章提供了GNN的開放資源以及一些未來方向的展望。
深度學習在許多領域都取得了可喜的進展,例如計算機視覺和自然語言處理。這些任務中的數據通常以歐幾里得表示。但是,許多學習任務需要處理包含元素之間豐富的關系信息的非歐氏圖數據,例如建模物理系統,學習分子指紋,預測蛋白質界面等。圖神經網絡(GNN)是基于深度學習的方法,在圖域上運行。由于其令人信服的性能和高解釋性,GNN最近已成為一種廣泛應用的圖形分析方法。本書全面介紹了圖神經網絡的基本概念,模型和應用。它從數學模型和神經網絡的基礎開始。在第一章中,它對GNN的基本概念進行了介紹,目的是為讀者提供一個概覽。然后介紹了GNN的不同變體:圖卷積網絡,圖遞歸網絡,圖注意力網絡,圖殘差網絡和一些通用框架。這些最差的結果是將通用的深度學習技術轉化為圖形,例如卷積神經網絡,遞歸神經網絡,注意力機制和跳過連接。此外,這本書介紹了GNN在結構場景(物理,化學,知識圖譜),非結構場景(圖像,文本)和其他場景(生成模型,組合優化)中的不同應用。最后,這本書列出了相關的數據集,開源平臺和GNN的實現。本書組織如下。在第1章中進行了概述之后,在第2章中介紹了數學和圖論的一些基本知識。在第3章中介紹了神經網絡的基礎,然后在第4章中簡要介紹了香草GNN。四種類型的模型分別在第5、6、7和8章中介紹。在第9章和第10章中介紹了不同圖類型和高級訓練方法的其他變體。然后在第11章中提出了幾種通用的GNN框架。第12、13和14章介紹了GNN在結構場景,非結構場景和其他場景中的應用。最后,我們在第15章提供了一些開放資源,并在第16章總結了這本書。
題目: Representation Learning on Graphs: Methods and Applications
摘要:
圖機器學習是一項重要且普遍存在的任務,其應用范圍從藥物設計到社交網絡中的友情推薦。這個領域的主要挑戰是找到一種表示或編碼圖形結構的方法,以便機器學習模型能夠輕松地利用它。傳統上,機器學習方法依賴于用戶定義的啟發法來提取對圖的結構信息進行編碼的特征(例如,度統計或內核函數)。然而,近年來,使用基于深度學習和非線性降維的技術,自動學習將圖結構編碼為低維嵌入的方法激增。在這里,我們提供了一個概念上的回顧,在這一領域的關鍵進展,圖表示學習,包括基于矩陣分解的方法,隨機漫步的算法和圖神經網絡。我們回顧了嵌入單個節點的方法以及嵌入整個(子)圖的方法。在此過程中,我們開發了一個統一的框架來描述這些最近的方法,并強調了一些重要的應用程序和未來工作的方向。
作者簡介:
William L. Hamilton是麥吉爾大學計算機科學的助理教授,也是加拿大魁北克Mila AI研究所的CIFAR AI主席。William L. Hamilton開發的機器學習模型可以對這個復雜的、相互聯系的世界進行推理。研究興趣集中在機器學習、網絡科學和自然語言處理的交叉領域,目前的重點是快速發展的圖表示學習和圖神經網絡。
Rex Ying是斯坦福大學計算機科學二年級的博士生,研究主要集中在開發應用于圖形結構數據的機器學習算法。曾致力于開發可擴展到網絡規模數據集的廣義圖卷積網絡,應用于推薦系統、異常檢測和生物學。
題目: A Survey on Network Embedding
摘要: 網絡嵌入將網絡中的節點分配給低維表示,有效地保持了網絡結構。近年來,這一新興的網絡分析范式取得了很大的進展。本文首先對網絡嵌入方法進行了分類,然后回顧了網絡嵌入方法的發展現狀,并指出了其未來的研究方向。我們首先總結了網絡嵌入的動機。討論了經典的圖嵌入算法及其與網絡嵌入的關系。隨后,我們對大量的網絡嵌入方法進行了系統的綜述,包括結構和屬性保持的網絡嵌入方法、帶邊信息的網絡嵌入方法和先進的信息保持的網絡嵌入方法。此外,還綜述了幾種網絡嵌入的評價方法和一些有用的在線資源,包括網絡數據集和軟件。最后,我們討論了利用這些網絡嵌入方法構建有效系統的框架,并指出了一些潛在的未來方向。
作者簡介: Peng Cui,清華大學計算機科學與技術系媒體與網絡實驗室副教授。
Jian Pei,現任加拿大大數據科學研究主席(Tier 1)和西蒙弗雷澤大學(Simon Fraser University)計算科學學院教授。他還是統計與精算科學系、科學院和健康科學院的副院士。他是數據科學、大數據、數據挖掘和數據庫系統等領域的知名首席研究員。他的專長是為新的數據密集型應用開發高效的數據分析技術。他被公認為計算機械協會(ACM)的研究員,他為數據挖掘的基礎、方法和應用做出貢獻,并作為電氣與電子工程師協會(IEEE)的研究員,為他的數據挖掘和知識發現做出貢獻。
題目: Graph Summarization Methods and Applications: A Survey
摘要:
雖然計算資源的進步使處理大量數據成為可能,但人類識別這些數據模式的能力并沒有相應提高。因此,壓縮和簡化數據的高效計算方法對于提取可操作的見解變得至關重要。特別是,雖然對數據摘要技術進行了廣泛的研究,但直到最近才開始流行對相互關聯的數據或圖進行匯總。這項調查是一個結構化的,全面的概述了最先進的方法,以總結圖形數據。我們首先討論了圖形摘要背后的動機和挑戰。然后,我們根據作為輸入的圖形類型對摘要方法進行分類,并根據核心方法進一步組織每個類別。最后,我們討論了總結在真實世界圖上的應用,并通過描述該領域的一些開放問題進行了總結。
作者簡介:
Yike Liu是密西根大學物理系五年級的博士生,也是計算機科學與工程系的一名碩士研究生。我是葉杰平教授的顧問。主要研究方向是深度學習和強化學習,尤其是在交通數據上的應用。在此之前,從事過基于圖形的機器學習和數據挖掘,特別是圖形總結和圖形聚類,在這些工作中,開發了圖形挖掘算法,幫助更好地理解底層的圖形組織并理解它。
Tara Safavi是密西根大學博士研究生,研究重點是知識表示及其在以人為中心的任務中的使用、評估和解釋,還對更廣泛的AI+社會問題感興趣,比如隱私、偏見和環境可持續性。研究目前得到了美國國家科學基金會(NSF)研究生獎學金和谷歌女性科技創造者獎學金的支持。
題目: A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications 摘要: 圖形是一種重要的數據表示形式,它出現在現實世界的各種場景中。有效的圖形分析可以讓用戶更深入地了解數據背后的內容,從而有利于節點分類、節點推薦、鏈路預測等許多有用的應用。然而,大多數圖形分析方法都存在計算量大、空間開銷大的問題。圖嵌入是解決圖分析問題的有效途徑。它將圖形數據轉換為一個低維空間,其中圖形結構信息和圖形屬性被最大程度地保留。在這項調查中,我們對圖嵌入的文獻進行了全面的回顧。本文首先介紹了圖嵌入的形式化定義及相關概念。之后,我們提出了兩個分類的圖形嵌入,對應于什么挑戰存在于不同的圖形嵌入問題設置,以及現有的工作如何解決這些挑戰,在他們的解決方案。最后,我們總結了圖形嵌入在計算效率、問題設置、技術和應用場景等方面的應用,并提出了四個有前途的研究方向。
作者簡介: Hongyun Cai,經驗豐富的研究人員,有在研究行業工作的經驗。精通計算機科學,C++,數據庫,Java和機器學習。昆士蘭大學計算機科學專業研究生,哲學博士。
Vincent W. Zheng,新加坡先進數字科學中心(ADSC)的研究科學家,也是伊利諾伊大學香檳分校協調科學實驗室的研究附屬機構。他目前領導著ADSC的大型社交項目。該項目旨在利用目前在我們的數字社會(即社交媒體)中普遍存在的巨大“人類傳感器”,并實現對此類數據的社會分析,從而建立一個以人為中心的網絡系統。他還對圖形表示學習、深度學習、自然語言處理、移動計算等領域感興趣,并在社交挖掘、文本挖掘、實際位置和活動識別、用戶分析、移動推薦、增強現實等方面有應用。
Kevin Chen-Chuan Chang是伊利諾伊大學香檳分校計算機科學教授,他領導了數據搜索、集成和挖掘的前沿數據實驗室。他在國立臺灣大學獲得理學學士學位,在斯坦福大學獲得電機工程博士學位。他的研究涉及大規模信息訪問,用于搜索、挖掘和跨結構化和非結構化大數據的集成,目前的重點是“以實體為中心”的Web搜索/挖掘和社交媒體分析。他在VLDB 2000年和2013年獲得了兩項最佳論文獎,2002年獲得了NSF職業獎,2003年獲得了NCSA院士獎,2004年和2005年獲得了IBM院士獎,2008年獲得了創業領導力學院院士獎,并在2001年、2004年、2005年、2006年、2010年和2011年獲得了伊利諾伊大學不完整的優秀教師名單。他熱衷于將研究成果帶到現實世界中,并與學生共同創辦了伊利諾伊大學(University of Illinois)的初創公司Cazoodle,致力于在網絡上深化垂直的“數據感知”搜索。
題目: Graph Neural Networks:A Review of Methods and Applications
簡介: 許多學習任務需要處理圖形數據,該圖形數據包含元素之間的關系信息。對物理系統進行建模,學習分子指紋,預測蛋白質界面以及對疾病進行分類,都需要從圖輸入中學習模型。在諸如從文本和圖像之類的非結構數據中學習的其他領域中,對提取結構的推理,例如句子的依存關系樹和圖像的場景圖,是一個重要的研究課題,它也需要圖推理模型。圖神經網絡(GNN)是連接器模型,可通過在圖的節點之間傳遞消息來捕獲圖的依賴性。與標準神經網絡不同,圖神經網絡保留一種狀態,該狀態可以表示來自其鄰域的任意深度的信息。盡管已經發現難以訓練原始圖神經網絡來固定點,但是網絡體系結構,優化技術和并行計算的最新進展已使他們能夠成功學習。近年來,基于圖卷積網絡(GCN)和門控圖神經網絡(GGNN)的系統已經在上述許多任務上展示了突破性的性能。在本綜述中,我們對現有的圖神經網絡模型進行了詳細的回顧,對應用程序進行了系統分類,并提出了四個未解決的問題,供以后研究。
作者簡介: 周杰,教授,清華大學自動化系黨委書記,教授,博士生導師。
論文題目: A Structural Graph Representation Learning Framework
論文摘要: 許多基于圖的機器學習任務的成功在很大程度上取決于從圖數據中學習到的適當表示。大多數工作都集中在于學習保留鄰近性的節點嵌入,而不是保留節點之間結構相似性的基于結構的嵌入。這些方法無法捕獲對基于結構的應用程序(如web日志中的visitor stitching)至關重要的高階結構依賴和連接模式。在這項工作中,我們闡述了高階網絡表示學習,并提出了一個稱為HONE的通用框架,用于通過節點鄰域中的子圖模式(network motifs, graphlet orbits/positions)從網絡中學習這種結構性節點嵌入。HONE引入了一種通用的diffusion機制和一種節省空間的方法,該方法避免了使用k-step線性算子來顯式構造k-step motif-based矩陣。此外,HONE被證明是快速和有效的,最壞情況下的時間復雜度幾乎是線性的。實驗結果表明,該算法能有效地處理大量的網絡日志數據,包括鏈接預測和visitor stitching。
作者簡介:
Ryan A. Rossi,目前在Adobe Research工作,研究領域是機器學習;涉及社會和物理現象中的大型復雜關系(網絡/圖形)數據的理論、算法和應用。在普渡大學獲得了計算機科學博士和碩士學位。
Nesreen K. Ahmed,英特爾實驗室的高級研究員。我在普渡大學計算機科學系獲得博士學位,在普渡大學獲得統計學和計算機科學碩士學位。研究方向是機器學習和數據挖掘,涵蓋了大規模圖挖掘、統計機器學習的理論和算法,以及它們在社會和信息網絡中的應用。
Lots of learning tasks require dealing with graph data which contains rich relation information among elements. Modeling physics system, learning molecular fingerprints, predicting protein interface, and classifying diseases require that a model learns from graph inputs. In other domains such as learning from non-structural data like texts and images, reasoning on extracted structures, like the dependency tree of sentences and the scene graph of images, is an important research topic which also needs graph reasoning models. Graph neural networks (GNNs) are connectionist models that capture the dependence of graphs via message passing between the nodes of graphs. Unlike standard neural networks, graph neural networks retain a state that can represent information from its neighborhood with arbitrary depth. Although the primitive GNNs have been found difficult to train for a fixed point, recent advances in network architectures, optimization techniques, and parallel computation have enabled successful learning with them. In recent years, systems based on graph convolutional network (GCN) and gated graph neural network (GGNN) have demonstrated ground-breaking performance on many tasks mentioned above. In this survey, we provide a detailed review over existing graph neural network models, systematically categorize the applications, and propose four open problems for future research.