題目: Factorized Graph Representations for Semi-Supervised Learning from Sparse Data
簡介:
節點分類是圖數據管理中的一個重要問題。它通常由不同的標簽傳播方法來解決,這些方法從幾個有標簽的種子節點開始迭代地工作。對于具有類之間任意兼容性的圖,這些方法主要依賴于了解必須由領域專家或啟發式提供的兼容性矩陣。我們能否以一種有原則和可伸縮的方式,從一個稀疏標記的圖中直接估計正確的兼容性?我們肯定地回答了這個問題,并提出了一種稱為遠程兼容性評估的方法,這種方法甚至可以在標記極為稀疏的圖(例如,標記了10,000個節點中的1個)上工作,而這只是標記其余節點所需時間的一小部分。我們的方法首先創建多個因式圖表示(大小與圖無關),然后對這些更小的圖進行估計。我們將代數放大定義為利用算法更新方程的代數性質來放大稀疏信號的一般思想。我們證明了我們的估計器要比其他方法快幾個數量級,并且端到端的分類精度與使用標準兼容性相當。這使得它對于任何現有的標簽傳播方法都是一個廉價的預處理步驟,并且消除了當前對啟發式的依賴。
題目: DEEP LEARNING FOR SYMBOLIC MATHEMATICS
摘要: 神經網絡在解決統計或近似問題上比執行計算或處理符號數據更好。 在本文中,我們證明了它們在數學上更精細的任務上表現出令人驚訝的出色表現,例如符號積分和解決微分方程式。我們提出了一種表示數學問題的語法,以及生成可用于訓練序列到序列的大型數據集的方法。我們取得的結果優于Matlab或Mathematica等商業計算機代數系統。
節點分類是圖數據管理中的一個重要問題。它通常由不同的標簽傳播方法來解決,這些方法從幾個有標簽的種子節點開始迭代地工作。對于具有類之間任意兼容性的圖,這些方法主要依賴于了解必須由領域專家或啟發式提供的兼容性矩陣。我們能否以一種有原則和可伸縮的方式,從一個稀疏標記的圖中直接估計正確的兼容性?我們肯定地回答了這個問題,并提出了一種稱為遠程兼容性評估的方法,這種方法甚至可以在標記極為稀疏的圖(例如,標記了10,000個節點中的1個)上工作,而這只是標記其余節點所需時間的一小部分。我們的方法首先創建多個因式圖表示(大小與圖無關),然后對這些更小的圖草圖進行估計。我們將代數放大定義為利用算法更新方程的代數性質來放大稀疏信號的更一般的思想。我們證明了我們的估計器要比其他方法快幾個數量級,并且端到端的分類精度與使用真實標準兼容性相當。這使得它對于任何現有的標簽傳播方法都是一個廉價的預處理步驟,并且消除了當前對啟發式的依賴。
Node classification is an important problem in graph data management. It is commonly solved by various label propagation methods that work iteratively starting from a few labeled seed nodes. For graphs with arbitrary compatibilities between classes, these methods crucially depend on knowing the compatibility matrix that must be provided by either domain experts or heuristics. Can we instead directly estimate the correct compatibilities from a sparsely labeled graph in a principled and scalable way? We answer this question affirmatively and suggest a method called distant compatibility estimation that works even on extremely sparsely labeled graphs (e.g., 1 in 10,000 nodes is labeled) in a fraction of the time it later takes to label the remaining nodes. Our approach first creates multiple factorized graph representations (with size independent of the graph) and then performs estimation on these smaller graph sketches. We define algebraic amplification as the more general idea of leveraging algebraic properties of an algorithm's update equations to amplify sparse signals. We show that our estimator is by orders of magnitude faster than an alternative approach and that the end-to-end classification accuracy is comparable to using gold standard compatibilities. This makes it a cheap preprocessing step for any existing label propagation method and removes the current dependence on heuristics.
人工智能(AI)的成功應該在很大程度上歸功于豐富數據的可獲得性。然而,實際情況并非如此,行業中的開發人員常常面臨數據不足、不完整和孤立的情況。因此,聯邦學習被提議通過允許多方在不顯式共享數據的情況下協作構建機器學習模型,同時保護數據隱私,來緩解這種挑戰。然而,現有的聯邦學習算法主要集中在數據不需要顯式標記或者所有數據都有標記的情況下。然而在現實中,我們經常會遇到這樣的情況,標簽數據本身是昂貴的,沒有足夠的標簽數據供應。雖然這類問題通常通過半監督學習來解決,但據我們所知,聯邦半監督學習還沒有投入任何努力。在這項調查中,我們簡要地總結了目前流行的半監督算法,并對聯邦半監督學習做了簡要的展望,包括可能的方法、設置和挑戰。
題目: A Survey on Deep Geometry Learning: From a Representation Perspective
摘 要:
目前,研究人員已經在利用深度學習處理二維圖像方面取得了很大的成功。近年來,三維計算機視覺和幾何深度學習越來越受到人們的重視。針對不同的應用,提出了許多先進的三維造型技術。與二維圖像可以由像素的規則網格統一表示不同,三維圖形具有多種表示,如深度和多視圖圖像、基于體素的表示、基于點的表示、基于網格的表示、隱式的表面表示等。然而,不同應用程序的性能在很大程度上取決于所使用的表示,并且沒有一種惟一的表示可以適用于所有應用程序。因此,在本次調查中,我們從表象的角度回顧了三維幾何深度學習的最新發展,總結了不同表象在不同應用中的優缺點。我們也提出現有的數據集在這些表示和進一步討論未來的研究方向。
簡介: 主導圖神經網絡(GNN)完全依賴圖連接,已經存在幾個嚴重的性能問題,例如,過度平滑問題。此外,由于內存限制了節點之間的批處理,因此固定連接的特性會阻止圖形內的并行化,這對于大型數據輸入至關重要。在本文中,引入一種新的圖神經網絡,即GRAPH-BERT(基于圖的BERT),該網絡僅基于注意力機制而無需任何圖卷積或聚合算法。本文在局部上下文中使用采樣的無連接子圖訓練GRAPH-BERT。此外,如果有任何監督的標簽信息或某些面向應用的目標,則可以使用其他最新的輸出層對預訓練的GRAPH-BERT模型進行微調。我們已經在多個基準圖數據集上測試了GRAPH-BERT的有效性。在預訓練的GRAPH-BERT具有節點屬性重構和結構恢復任務的基礎上,我們進一步針對節點分類和圖聚類任務進一步調整GRAPH-BERT。
【導讀】近年來,隨著網絡數據量的不斷增加,挖掘圖形數據已成為計算機科學領域的熱門研究課題,在學術界和工業界都得到了廣泛的研究。 但是,大量的網絡數據為有效分析帶來了巨大的挑戰。 因此激發了圖表示的出現,該圖表示將圖映射到低維向量空間中,同時保持原始圖結構并支持圖推理。 圖的有效表示的研究具有深遠的理論意義和重要的現實意義,本教程將介紹圖表示/網絡嵌入的一些基本思想以及一些代表性模型。
關于圖或網絡的文獻有兩個名稱:圖表示和網絡嵌入。我們注意到圖和網絡都指的是同一種結構,盡管它們每個都有自己的術語,例如,圖和網絡的頂點和邊。挖掘圖/網絡的核心依賴于正確表示的圖/網絡,這使得圖/網絡上的表示學習成為學術界和工業界的基本研究問題。傳統表示法直接基于拓撲圖來表示圖,通常會導致許多問題,包括稀疏性,高計算復雜性等,從而激發了基于機器學習的方法的出現,這種方法探索了除矢量空間中的拓撲結構外還能夠捕獲額外信息的潛在表示。因此,對于圖來說,“良好”的潛在表示可以更加精確的表示圖形。但是,學習網絡表示面臨以下挑戰:高度非線性,結構保持,屬性保持,稀疏性。
深度學習在處理非線性方面的成功為我們提供了研究新方向,我們可以利用深度學習來提高圖形表示學習的性能,作者在教程中討論了將深度學習技術與圖表示學習相結合的一些最新進展,主要分為兩類方法:面向結構的深層方法和面向屬性的深層方法。
對于面向結構的方法:
對于面向屬性的方法:
本教程的第二部分就以上5種方法,通過對各個方法的模型介紹、算法介紹、對比分析等不同方面進行詳細介紹。
1、Structural Deep Network Embedding
network embedding,是為網絡中的節點學習出一個低維表示的方法。目的在于在低維中保持高度非線性的網絡結構特征,但現有方法多采用淺層網絡不足以挖掘高度非線性,或同時保留局部和全局結構特征。本文提出一種結構化深度網絡嵌入方法,叫SDNE該方法用半監督的深度模型來捕捉高度非線性結構,通過結合一階相似性(監督)和二階相似性(非監督)來保留局部和全局特征。
2、 Deep recursive network embedding with regular equivalence
網絡嵌入旨在保留嵌入空間中的頂點相似性。現有方法通常通過節點之間的連接或公共鄰域來定義相似性,即結構等效性。但是,位于網絡不同部分的頂點可能具有相似的角色或位置,即規則的等價關系,在網絡嵌入的文獻中基本上忽略了這一點。以遞歸的方式定義規則對等,即兩個規則對等的頂點具有也規則對等的網絡鄰居。因此,文章中提出了一種名為深度遞歸網絡嵌入(DRNE)的新方法來學習具有規則等價關系的網絡嵌入。更具體地說,我們提出了一種層歸一化LSTM,以遞歸的方式通過聚合鄰居的表示方法來表示每個節點。
3、Structural Deep Embedding for Hyper-Networks
是在hyperedge(超邊是不可分解的)的基礎上保留object的一階和二階相似性,學習異質網絡表示。于與HEBE的區別在于,本文考慮了網絡high-oeder網絡結構和高度稀疏性。 傳統的基于clique expansion 和star expansion的方法,顯式或者隱式地分解網絡。也就說,分解后hyper edge節點地子集,依然可以構成一個新的超邊。對于同質網絡這個假設是合理地,因為同質網絡地超邊,大多數情況下都是根據潛在地相似性(共同地標簽等)構建的。
4、 Deep variational network embedding in wasserstein space
大多數現有的嵌入方法將節點作為點向量嵌入到低維連續空間中。這樣,邊緣的形成是確定性的,并且僅由節點的位置確定。但是,現實世界網絡的形成和發展充滿不確定性,這使得這些方法不是最優的。為了解決該問題,在本文中提出了一種新穎的在Wasserstein空間中嵌入深度變分網絡(DVNE)。所提出的方法學習在Wasserstein空間中的高斯分布作為每個節點的潛在表示,它可以同時保留網絡結構并為節點的不確定性建模。具體來說,我們使用2-Wasserstein距離作為分布之間的相似性度量,它可以用線性計算成本很好地保留網絡中的傳遞性。此外,我們的方法通過深度變分模型隱含了均值和方差的數學相關性,可以通過均值矢量很好地捕獲節點的位置,而由方差可以很好地捕獲節點的不確定性。此外,本文方法通過保留網絡中的一階和二階鄰近性來捕獲局部和全局網絡結構。
5、 Learning embeddings of out-of-sample nodes in dynamic networks
迄今為止的網絡嵌入算法主要是為靜態網絡設計的,在學習之前,所有節點都是已知的。如何為樣本外節點(即學習后到達的節點)推斷嵌入仍然是一個懸而未決的問題。該問題對現有方法提出了很大的挑戰,因為推斷的嵌入應保留復雜的網絡屬性,例如高階鄰近度,與樣本內節點嵌入具有相似的特征(即具有同質空間),并且計算成本較低。為了克服這些挑戰,本文提出了一種深度轉換的高階拉普??拉斯高斯過程(DepthLGP)方法來推斷樣本外節點的嵌入。 DepthLGP結合了非參數概率建模和深度學習的優勢。特別是,本文設計了一個高階Laplacian高斯過程(hLGP)來對網絡屬性進行編碼,從而可以進行快速和可擴展的推理。為了進一步確保同質性,使用深度神經網絡來學習從hLGP的潛在狀態到節點嵌入的非線性轉換。 DepthLGP是通用的,因為它適用于任何網絡嵌入算法學習到的嵌入。
題目: Representation Learning on Graphs: Methods and Applications
摘要:
圖機器學習是一項重要且普遍存在的任務,其應用范圍從藥物設計到社交網絡中的友情推薦。這個領域的主要挑戰是找到一種表示或編碼圖形結構的方法,以便機器學習模型能夠輕松地利用它。傳統上,機器學習方法依賴于用戶定義的啟發法來提取對圖的結構信息進行編碼的特征(例如,度統計或內核函數)。然而,近年來,使用基于深度學習和非線性降維的技術,自動學習將圖結構編碼為低維嵌入的方法激增。在這里,我們提供了一個概念上的回顧,在這一領域的關鍵進展,圖表示學習,包括基于矩陣分解的方法,隨機漫步的算法和圖神經網絡。我們回顧了嵌入單個節點的方法以及嵌入整個(子)圖的方法。在此過程中,我們開發了一個統一的框架來描述這些最近的方法,并強調了一些重要的應用程序和未來工作的方向。
作者簡介:
William L. Hamilton是麥吉爾大學計算機科學的助理教授,也是加拿大魁北克Mila AI研究所的CIFAR AI主席。William L. Hamilton開發的機器學習模型可以對這個復雜的、相互聯系的世界進行推理。研究興趣集中在機器學習、網絡科學和自然語言處理的交叉領域,目前的重點是快速發展的圖表示學習和圖神經網絡。
Rex Ying是斯坦福大學計算機科學二年級的博士生,研究主要集中在開發應用于圖形結構數據的機器學習算法。曾致力于開發可擴展到網絡規模數據集的廣義圖卷積網絡,應用于推薦系統、異常檢測和生物學。
題目: Network Representation Learning: A Survey
摘要:
隨著信息技術的廣泛應用,信息網絡越來越受到人們的歡迎,它可以捕獲各種學科之間的復雜關系,如社交網絡、引用網絡、電信網絡和生物網絡。對這些網絡的分析揭示了社會生活的不同方面,如社會結構、信息傳播和交流模式。然而,在現實中,大規模的信息網絡往往使網絡分析任務計算昂貴或難以處理。網絡表示學習是近年來提出的一種新的學習范式,通過保留網絡拓撲結構、頂點內容和其它邊信息,將網絡頂點嵌入到低維向量空間中。這有助于在新的向量空間中方便地處理原始網絡,以便進行進一步的分析。在這項調查中,我們全面回顧了目前在數據挖掘和機器學習領域的網絡表示學習的文獻。我們提出了新的分類法來分類和總結最先進的網絡表示學習技術,根據潛在的學習機制、要保留的網絡信息、以及算法設計和方法。我們總結了用于驗證網絡表示學習的評估協議,包括已發布的基準數據集、評估方法和開源算法。我們還進行了實證研究,以比較代表性的算法對常見數據集的性能,并分析其計算復雜性。最后,我們提出有希望的研究方向,以促進未來的研究。
作者簡介:
Xingquan Zhu是佛羅里達大西洋大學計算機與電氣工程和計算機科學系的教授,在中國上海復旦大學獲得了計算機科學博士學位。曾在多家研究機構和大學工作過,包括微軟亞洲研究院(實習)、普渡大學、佛蒙特大學和悉尼科技大學。主要研究方向:數據挖掘、機器學習、多媒體系統、生物信息學。
論文題目: 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,英特爾實驗室的高級研究員。我在普渡大學計算機科學系獲得博士學位,在普渡大學獲得統計學和計算機科學碩士學位。研究方向是機器學習和數據挖掘,涵蓋了大規模圖挖掘、統計機器學習的理論和算法,以及它們在社會和信息網絡中的應用。