一区二区三区日韩精品-日韩经典一区二区三区-五月激情综合丁香婷婷-欧美精品中文字幕专区

分享

從圖嵌入到圖分類——圖網(wǎng)絡(luò)入門綜述

 Tomsp360lib 2019-05-19
導(dǎo)語

現(xiàn)實(shí)世界中的大量問題都可以抽象成圖模型(Graph Model),也就是節(jié)點(diǎn)和連邊的集合。從知識圖譜到概率圖模型,從蛋白質(zhì)相互作用網(wǎng)絡(luò)到社交網(wǎng)絡(luò),從基本的邏輯線路到巨大的Internet,圖與網(wǎng)絡(luò)無處不在。然而傳統(tǒng)的機(jī)器學(xué)習(xí)方法很難處理圖網(wǎng)絡(luò)信息,這種缺陷大大限制了深度學(xué)習(xí)的應(yīng)用領(lǐng)域。于是人們提出了圖網(wǎng)絡(luò)(Graph Network),一種基于圖結(jié)構(gòu)的廣義人工神經(jīng)網(wǎng)絡(luò),它可以直接對真實(shí)問題進(jìn)行建模,又可以利用自動(dòng)微分技術(shù)進(jìn)行學(xué)習(xí),甚至有望將多個(gè)傳統(tǒng)人工智能領(lǐng)域進(jìn)行融合。

編譯:集智俱樂部翻譯組

來源:medium

原題:How to get started with machine learning on Graphs

目錄

一、 什么是圖數(shù)據(jù)?

二、 為什么要在圖數(shù)據(jù)上使用機(jī)器學(xué)習(xí)?(Graph ML

    1.機(jī)器學(xué)習(xí)能自動(dòng)化人類可以輕易實(shí)現(xiàn)但難以向計(jì)算機(jī)描述的任務(wù)。

     2. ML 可以以人類無法企及的規(guī)模來轉(zhuǎn)換信息。

三、 什么是 Graph ML?

    1.使用 Graph ML 會(huì)遇到什么樣的挑戰(zhàn)?

    2.GraphML系統(tǒng)在實(shí)際運(yùn)行中是怎樣的?

四、 讓我們在圖上開始機(jī)器學(xué)習(xí)吧!

    1.你想要執(zhí)行什么類型的任務(wù)?

    2.基本過程

    3.通用 Graph ML 方法

五、 節(jié)點(diǎn)嵌入 Node embeddings

    1.隨機(jī)游走

    2.node2Vec

    3.node2vec擴(kuò)展

    4.使用隨機(jī)游走的協(xié)同過濾

六、 圖卷積網(wǎng)絡(luò)

    1.對圖網(wǎng)絡(luò)的擴(kuò)展

七、 鏈接預(yù)測

    1.節(jié)點(diǎn)嵌入和隨機(jī)游走

    2.具有圖特征的深度學(xué)習(xí)

    3.神經(jīng)張量網(wǎng)絡(luò)

    4.強(qiáng)化學(xué)習(xí)

八、 節(jié)點(diǎn),邊和整個(gè)圖的評分和分類

    1.節(jié)點(diǎn)嵌入和隨機(jī)游走

    2.圖網(wǎng)絡(luò)

    3. 注意力序列

    4.基于分塊或節(jié)點(diǎn)屬性的傳統(tǒng)深度學(xué)習(xí)

    5.節(jié)點(diǎn)屬性在搜索引擎上的技術(shù)

附:參考文獻(xiàn)

作者在倫敦Connected Data上的演講之后,與很多擁有圖數(shù)據(jù),想要開始機(jī)器學(xué)習(xí)但不知道怎樣開始的研究團(tuán)隊(duì)進(jìn)行了交流。在這篇文章里,作者以通俗易懂的方式展示了他們在圖上進(jìn)行機(jī)器學(xué)習(xí)的方法技巧,并提供了相關(guān)的資料。

注:

作者 David Mack 是 Octavian.ai 的創(chuàng)始人。

Octavian.ai 是一家開源公司,致力于機(jī)器問答系統(tǒng)和圖上深度學(xué)習(xí)。

這是他們的開源項(xiàng)目列表:

https://github.com/Octavian-ai

一、 什么是圖數(shù)據(jù)?

通過與這些希望獲得機(jī)器學(xué)習(xí)領(lǐng)域協(xié)助的團(tuán)隊(duì)交流我們得知,圖數(shù)據(jù)真是無處不在 —— 從疾病診斷,遺傳學(xué)研究還有健康管理,到銀行和工程,圖都是一種解決困難問題的強(qiáng)有力的分析模式。

簡單來說,一張圖就是節(jié)點(diǎn)(比如人)和他們之間關(guān)系(比如 Fatima 是 Jacob 的朋友)的集合。這些節(jié)點(diǎn)通常具有自己的屬性(比如 Fatima 23歲)。

     圖1 數(shù)據(jù)庫中以圖形式的儲(chǔ)存數(shù)據(jù)。如圖所示,這個(gè)例子在數(shù)據(jù)庫里通常是這樣存儲(chǔ)的。一個(gè)最主流的圖數(shù)據(jù)庫是Neo4j,用他們自己的話說“ 這是一個(gè)處于世界領(lǐng)先地位的圖數(shù)據(jù)庫,因?yàn)樗哂斜镜氐膱D存儲(chǔ)和圖處理能力。

如圖所示,這個(gè)例子在數(shù)據(jù)庫里通常是這樣存儲(chǔ)的。一個(gè)最出名的圖數(shù)據(jù)庫是Neo4j,用他們自己的話說“ 這是一個(gè)處于世界領(lǐng)先地位的圖數(shù)據(jù)庫,因?yàn)樗哂斜镜氐膱D存儲(chǔ)和圖處理能力。

你可以在 Neo4j 數(shù)據(jù)庫中使用 Cypher 查詢數(shù)據(jù),這是一種類似于SQL的圖查詢語言。在之前的演示示例中,我們可以這樣獲取一個(gè) Fatima 朋友的列表:

MATCH (n1)-[:IS_FRIEND_OF]-(n2)WHERE n1.name = 'Fatima'RETURN n2.name

圖是描述數(shù)據(jù)的一種極具靈活性的強(qiáng)大方式。傳統(tǒng)的關(guān)系型數(shù)據(jù)庫很難用固定模式存儲(chǔ)不同實(shí)體之間的聯(lián)系,然而這些聯(lián)系是現(xiàn)實(shí)世界中普遍且至關(guān)重要的一部分。在圖數(shù)據(jù)庫中,這些聯(lián)系是非常易于存儲(chǔ)和查詢的。此外,通常很多事物之間的聯(lián)系(例如家庭成員之間的關(guān)系)構(gòu)成分析問題的關(guān)鍵,使用圖數(shù)據(jù)庫使得問題分析變得很簡單。

備注:關(guān)系(relationship)和邊(edge)在這篇文章里是可以相互替換的。Neo4j 語境下使用前者,圖論語境下用后者。

二、 為什么要在圖數(shù)據(jù)上

使用機(jī)器學(xué)習(xí)?(Graph ML)

首先,為什么使用機(jī)器學(xué)習(xí)? 關(guān)于這個(gè)問題,Benedict Evans 寫了一篇很好的文章 “Ways to think about machine Learning” ,覆蓋了企業(yè)思考和開始機(jī)器學(xué)習(xí)的方式。

論文地址:
https://www./benedictevans/2018/06/22/ways-to-think-about-machine-learning-8nefy

這里總結(jié)來自 Ben 對于圖機(jī)器學(xué)習(xí)(Graph ML) 兩種有用的觀點(diǎn):

  • 機(jī)器學(xué)習(xí)能自動(dòng)化人類可以輕易實(shí)現(xiàn)但難以向計(jì)算機(jī)描述的任務(wù)。

真實(shí)世界的數(shù)據(jù)是充滿干擾且多層次的。比如像”描述圖中的人物“此類任務(wù)對于人類來說很簡單,但是很難抽象為離散的算法。

我們可以用深度學(xué)習(xí)把大量的數(shù)據(jù)轉(zhuǎn)換為執(zhí)行特定任務(wù)的高效功能。

這在圖上也是成立的——得益于開放式的關(guān)系結(jié)構(gòu),它們與圖像或向量有非常大的不同。我們可以在 Graph ML 上建立適用于通用模式的方法。

  • ML 可以以人類無法企及的規(guī)模來轉(zhuǎn)換信息。

另一方面,對于計(jì)算機(jī)來說,它們可以準(zhǔn)確執(zhí)行我們的指令(雖然偶爾也會(huì)出現(xiàn)錯(cuò)誤)。

這意味著它們可以完全地運(yùn)行指令,并且沒有任何額外操作。需要它們運(yùn)行多久,它們就會(huì)持續(xù)多久。

因此,計(jì)算機(jī)可以處理非常大規(guī)模的數(shù)據(jù)(換做人類需要很多時(shí)間或注意力)。這讓新的分析應(yīng)用成為可能,例如從數(shù)十億的web數(shù)據(jù)里找出欺詐的特征。

三、 什么是 Graph ML?

這可以簡單地定義為 ”在圖數(shù)據(jù)上應(yīng)用機(jī)器學(xué)習(xí)(applying machine learning to graph data)“。我們特地這樣通俗地解釋,是因?yàn)樵谶@篇文章里,我們將聚焦于神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)本身,即便如此,我也會(huì)盡可能地包含其他補(bǔ)充的鏈接。

我不想去寫傳統(tǒng)的圖分析,包括一些廣為人知的算法,如 PageRank,Clique Indentification, Shortest Path 等。這些強(qiáng)大且能夠作為第一選擇的算法已經(jīng)在公開的資料中有了大量的參考。

使用 Graph ML 

會(huì)遇到什么樣的挑戰(zhàn)?

然而在這個(gè)令人激動(dòng)又充滿希望的領(lǐng)域里,Graph ML 還是一項(xiàng)非常年輕的技術(shù)。

主流機(jī)器學(xué)習(xí)的討論更多的是在可應(yīng)用性(例如使用ResNet進(jìn)行遷移學(xué)習(xí)來分類圖像,或者在文本中使用BERT預(yù)測),還有對開發(fā)者的易用性上(例如 TensorFlow, PyTorch, FastAI)。這并不是簡單而通用的技術(shù),即便如此也沒有任何流行的ML庫支持圖數(shù)據(jù)。

同樣的,像 Neo4j 這樣的圖數(shù)據(jù)庫自己也沒有支持在數(shù)據(jù)上運(yùn)行ML的方法。(盡管 Neo4j 已經(jīng)在嘗試使它成為可能)

在深度學(xué)習(xí)庫中不支持圖的其中一個(gè)原因是圖具有過于靈活的的數(shù)據(jù)結(jié)構(gòu)(例如任何節(jié)點(diǎn)與其他節(jié)點(diǎn)有任意多的連接)并不契合主流深度學(xué)習(xí)庫和 GPU 架構(gòu)中使用的固定大小圖和固定尺寸張量。

更簡單來說,用矩陣來描述并操作一個(gè)稀疏圖是非常困難的。不是不可能,但絕對比使用向量,文本還有圖像要難得多。

盡管如此,Graph ML 的趨勢依然無法阻擋。我個(gè)人預(yù)測,這將成為我們在很多產(chǎn)業(yè)中分析數(shù)據(jù)的一個(gè)主流的基本方式。

再提及一點(diǎn),就像其他任何機(jī)器學(xué)習(xí)技術(shù),大多數(shù) Graph ML 都需要大量的訓(xùn)練數(shù)據(jù)。

Graph ML系統(tǒng)

在實(shí)際運(yùn)行中是怎樣的?

雖然這個(gè)問題的答案會(huì)隨著任務(wù)和數(shù)據(jù)集的變化而變化,但它有助于概括出你,這個(gè)敏銳的冒險(xiǎn)家,將會(huì)遇到的問題。

絕大多數(shù)時(shí)候,這系統(tǒng)需要你自己來寫代碼完成 —— 因?yàn)楦呒壍?Graph ML 工具還不存在。你可能會(huì)想要用 Python, 還有機(jī)器學(xué)習(xí)庫 像TensorFlow 或者 PyTorch 來實(shí)現(xiàn)。根據(jù)你的數(shù)據(jù)規(guī)模,你可以在單機(jī)上實(shí)現(xiàn)訓(xùn)練模型,也可以使用分布式系統(tǒng)。(有趣的是,很多圖訓(xùn)練過程可以很好地在分布式系統(tǒng)上工作)。

     圖2 訓(xùn)練模型

你很可能需要先從存儲(chǔ)在 CSV 文件和在 Neo4j 這樣的數(shù)據(jù)庫,或者其他格式的圖數(shù)據(jù)庫中提取你的數(shù)據(jù)。

然后你需要把數(shù)據(jù)提供給機(jī)器學(xué)習(xí)庫。在我當(dāng)前的工作中(涉及到百萬的小圖(small graphs)),我把每一張圖都預(yù)先編譯成了 TFRecord,特征向量存儲(chǔ)了節(jié)點(diǎn),聯(lián)系,還有相鄰矩陣信息。所有節(jié)點(diǎn)的屬性與文本被標(biāo)記成了一個(gè)字典的格式。

這只在小圖上起作用,如果圖很大,你需要用某種方案把圖分為較小的訓(xùn)練樣本(你可以分批訓(xùn)練,或者按照 節(jié)點(diǎn)-邊-節(jié)點(diǎn) 三個(gè)一組的形式訓(xùn)練)。

建議:一些情況下數(shù)據(jù)在導(dǎo)入機(jī)器學(xué)習(xí)庫之前進(jìn)行表格化(tabularize )。Node2Vec 就是一個(gè)很好的例子,它的每一個(gè)節(jié)點(diǎn)都被隨機(jī)游走(Random Walk)轉(zhuǎn)換成向量,然后這些向量再以列表的形式傳入機(jī)器學(xué)習(xí)模型。

一旦在數(shù)據(jù)傳入之后,真正的模型和訓(xùn)練工作就開始了。這是一個(gè)復(fù)雜的變化過程。

最終,模型會(huì)被用在某些地方。一些情況下,一個(gè)模型計(jì)算完成后的新節(jié)點(diǎn)/邊/圖信息會(huì)存儲(chǔ)在外部數(shù)據(jù)庫里。

另外一部分的模型會(huì)被部署在線上的產(chǎn)品中。在這種情形下,從圖數(shù)據(jù)建立的模型系統(tǒng)需要更好的性能(可以是從圖數(shù)據(jù)庫中導(dǎo)入數(shù)據(jù)),然后這個(gè)預(yù)測模型最終會(huì)被用戶或下一代系統(tǒng)所利用(例如 Alexa 和用戶的問答系統(tǒng))。

四、 讓我們在圖上開始機(jī)器學(xué)習(xí)吧!

讓我們先看一下一些可以用來在圖上執(zhí)行機(jī)器學(xué)習(xí)的建議吧。

我將在這里大概列舉一系列方法,指出它們其中的一些缺點(diǎn)和優(yōu)點(diǎn),然后給出完整的鏈接。因?yàn)槠@里省略了一些細(xì)節(jié)。盡管這是一個(gè)年輕的領(lǐng)域,研究人員還是想出了一系列令人眼花繚亂豐富的方法處理Graph ML。即便我想在本文中詳盡介紹,遺憾的是也沒有辦法完全列出主要的部分。

如果你想要在這篇文章中幫助我完善列表,請聯(lián)系我。

你想要執(zhí)行什么類型的任務(wù)?

對于 Graph ML有各種各樣的開始和執(zhí)行過程的方式。因此,通過考慮你的任務(wù)目的來縮小開始的范圍和方式是很有幫助的。

如同任何機(jī)器學(xué)習(xí)系統(tǒng)一樣,縮小和明確你要實(shí)現(xiàn)的目標(biāo),將對你的試驗(yàn)成功和試驗(yàn)過程有極大的幫助。通過提出一個(gè)最小的、明確的目標(biāo),你的模型和需要數(shù)據(jù)集就會(huì)減小到易于處理的程度。

最后一點(diǎn),圖數(shù)據(jù)庫是特別有吸引力的,它鼓勵(lì)我們朝著宏偉的“萬能”目標(biāo)前進(jìn):因?yàn)閳D數(shù)據(jù)庫幾乎可以代表任何東西,所以這對試圖建立通用的智能的工作者很有誘惑力的。警告:)

我們將要闡述的任務(wù)類型:

  1. 預(yù)測兩個(gè)節(jié)點(diǎn)之間的關(guān)系是否存在

  2. 預(yù)測和分類節(jié)點(diǎn),邊,還有整張圖

本文旨在作為你自己研究的初級參考。與任何數(shù)據(jù)科學(xué)一樣,使用方法也需要適應(yīng)你個(gè)人所處的環(huán)境。由于許多Graph ML尚處于早期研究階段,因此你應(yīng)該在找到一個(gè)有效的方法之前嘗試多種方法。

基本過程

在開始構(gòu)建一個(gè) Graph ML 系統(tǒng)(可能需要對基礎(chǔ)設(shè)施進(jìn)行大量投資)之前,重要的是要考慮簡單的方法是否已經(jīng)足夠達(dá)成目,這能為你節(jié)約下很多不必要的工作。

這里有一些簡化問題的方法:

  • 你可以把你的數(shù)據(jù)列表化(tabularize)么(你能看到節(jié)點(diǎn)列表么?你可以在 節(jié)點(diǎn)-邊-節(jié)點(diǎn) 的三元組模式下工作么?)然后在此之上應(yīng)用傳統(tǒng)的機(jī)器學(xué)習(xí)過程(例如線性回歸,前饋網(wǎng)絡(luò))?

  • 你能把數(shù)據(jù)集過濾成更小的部分么?(例如移除現(xiàn)有的節(jié)點(diǎn))

  • 你可以把這個(gè)圖聚類成子圖,并把它們合成一個(gè)表么?

  • 你是否可以使用傳統(tǒng)機(jī)器學(xué)習(xí)擴(kuò)展的的圖度量指標(biāo)(如 PageRank)?(例如對計(jì)算節(jié)點(diǎn)的屬性應(yīng)用線性回歸來對節(jié)點(diǎn)進(jìn)行分類)

在下面可以適用的部分中,我會(huì)回顧其中的一些方法。

通用 Graph ML 方法

一些 Graph ML 的方法通用性強(qiáng)。我已經(jīng)在這里包含了它們?nèi)康慕榻B。在下面的章節(jié)中,我將參考此部分并著重解釋一些應(yīng)用在特定任務(wù)的過程。

再一次重申,我們不可能在一篇文章中涉及所有Graph MLD的內(nèi)容,我們能做的最好的就是給你建議,以便你繼續(xù)深入。

你可以自由跳過這個(gè)章節(jié),并在開始解決你感興趣的任務(wù)的時(shí)候回頭再看。

節(jié)點(diǎn)層

五、 節(jié)點(diǎn)嵌入 

Node embeddings

節(jié)點(diǎn)嵌入是 graph ML 早期的一種開發(fā)方式,它的流行是因?yàn)楹唵?,穩(wěn)定,且易于計(jì)算。

簡單來說,節(jié)點(diǎn)嵌入就是輪流計(jì)算圖中的每一個(gè)節(jié)點(diǎn)的向量。向量可以計(jì)算出有用的屬性,例如任意兩個(gè)節(jié)點(diǎn)嵌入的內(nèi)積可以表示它們是否來自于同一個(gè)社群。

通過這種方式,節(jié)點(diǎn)嵌入將圖形數(shù)據(jù)簡化為更易于管理的東西:向量。

節(jié)點(diǎn)層經(jīng)常和很多圖結(jié)構(gòu)合并在一起計(jì)算(稍后會(huì)詳細(xì)介紹)。

權(quán)衡之下必然會(huì)放棄一些信息。一個(gè)固定長度的向量很少能代表一個(gè)節(jié)點(diǎn)周圍的所有圖結(jié)構(gòu)。它可以包含也可以不包含節(jié)點(diǎn)和關(guān)系屬性。

然而,只有少量具有創(chuàng)新性的節(jié)點(diǎn)層可以被其他 Graph ML 過程復(fù)用。在這樣的設(shè)置下,節(jié)點(diǎn)層成為一種節(jié)點(diǎn)屬性,并被用作其他技術(shù)的催化劑,即使它并沒有像生成層一樣嵌入到圖結(jié)構(gòu)中。

接下來我將重點(diǎn)介紹一些主要的嵌入過程。有關(guān)于圖嵌入技術(shù)的調(diào)查和它們之間的比較,請查閱這兩篇論文。

論文題目:

A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications

論文地址:

https:///pdf/1709.07604.pdf

論文題目:

Graph Embedding Techniques, Applications, and Performance: A Survey

論文地址:

https:///pdf/1705.02801.pdf

隨機(jī)游走

     圖3 隨機(jī)游走圖分析技術(shù)圖示

隨機(jī)游走是一種非常強(qiáng)大且簡單的圖分析技術(shù),和數(shù)論有很長一段淵源。

一次隨機(jī)游走從圖中的一個(gè)節(jié)點(diǎn)開始,隨機(jī)地選擇一個(gè)邊,并穿過它。然后重復(fù)這一過程,直到提供路徑足夠地長。

隨機(jī)游走的聰明之處在于它將一個(gè)多維度的不規(guī)則事物(圖)轉(zhuǎn)化為一個(gè)簡單的矩陣(每個(gè)路徑由節(jié)點(diǎn)組成的固定長度的路徑列表)。

在足夠大的規(guī)模下,從理論上可以從隨機(jī)游走中重建出基本的圖結(jié)構(gòu)。隨機(jī)游走發(fā)揮了機(jī)器學(xué)習(xí)的巨大優(yōu)勢:從大量數(shù)據(jù)中學(xué)習(xí)。

有很多方法可以利用隨機(jī)游走來計(jì)算節(jié)點(diǎn)嵌入。下面我將重點(diǎn)介紹一些主要的方法。

node2Vec

論文題目:

node2vec scalable feature learning for networks

論文地址:

https:///abs/1607.00653

node2vec 是一種流行且相當(dāng)普遍的使用隨機(jī)游走的嵌入方法。

將這些隨機(jī)游走轉(zhuǎn)化為計(jì)算嵌入的方法有一種智能的優(yōu)化方式。首先為每個(gè)節(jié)點(diǎn)分配一個(gè)隨機(jī)層,(例如長度為N的高斯向量)。然后對于每對源相鄰節(jié)點(diǎn),我們希望通過調(diào)整這些層來最大化它們的點(diǎn)積。同時(shí)最后,我們最小化隨機(jī)節(jié)點(diǎn)對的點(diǎn)積。這樣做的效果是我們學(xué)習(xí)了一組嵌入,這些嵌入傾向于在相同的遍歷過程中高點(diǎn)積的節(jié)點(diǎn)。例如在相同的 社群/結(jié)構(gòu)中。

     圖4  由node2vec生成的LesMisérables可視化外觀網(wǎng)絡(luò),其標(biāo)簽顏色表示了同質(zhì)性(頂部)和結(jié)構(gòu)等價(jià)性(底部)。

你要知道關(guān)于node2vec 的最后一點(diǎn)是,它是由參數(shù)決定隨機(jī)游走的形式的。通過 ”In-out“ 超參數(shù),你可以優(yōu)先考慮遍歷是否集中在小的局部區(qū)域(例如這些節(jié)點(diǎn)是否在同一個(gè)小邊中?)或者這些游走是否在圖中廣范移動(dòng)(例如這些節(jié)點(diǎn)是否處于統(tǒng)一類型的結(jié)構(gòu)中?)。

node2vec 擴(kuò)展

node2vec 的優(yōu)勢在于它的簡單,但這也是它最大的弱點(diǎn)。標(biāo)準(zhǔn)算法并不包含節(jié)點(diǎn)屬性或邊屬性以及其他需要的信息。

但是,擴(kuò)展 node2vec 使它包含更多的信息非常簡單,只需更改損失函數(shù),比如:

  • 嘗試不同的學(xué)習(xí)函數(shù)替代兩個(gè)節(jié)點(diǎn)層之間的點(diǎn)積

  • 不僅使用節(jié)點(diǎn)層,也需要包含它們的屬性

更多了解請查閱大量引用 node2vec 的論文。

使用隨機(jī)游走的協(xié)同過濾

Collaborative filtering)

一個(gè)使用隨機(jī)游走來解決協(xié)同過濾的簡單例子是輸入用戶對產(chǎn)品的評論,預(yù)測用戶會(huì)喜歡其他哪些產(chǎn)品。

這大體上遵循了與 node2vec 相同的方案,盡管已經(jīng)進(jìn)一步簡化。你可以在本文中找到完整的實(shí)現(xiàn)和解釋。

六、 圖卷積網(wǎng)絡(luò)

圖網(wǎng)絡(luò)是 Graph ML 的一個(gè)豐富而重要的領(lǐng)域,其基本前提是在圖結(jié)構(gòu)中嵌入神經(jīng)網(wǎng)絡(luò):

     圖5 

通常,這涉及存儲(chǔ)每個(gè)節(jié)點(diǎn)的狀態(tài),并使用鄰接矩陣將這些狀態(tài)傳播到節(jié)點(diǎn)的近鄰節(jié)點(diǎn)。

一篇很好的綜述文章是 DeepMind 的 “Relational inductive biases, deep learning, and Graph networks” ,它既記錄了這一子領(lǐng)域的歷史,也提出了一種統(tǒng)一的方法來比較圖網(wǎng)絡(luò)和一般神經(jīng)網(wǎng)絡(luò)的不同。

論文地址:

https:///abs/1806.01261

在上面的文章中,圖網(wǎng)絡(luò)被認(rèn)為是用于在節(jié)點(diǎn),邊和整個(gè)圖上傳播狀態(tài)和聚合狀態(tài)的函數(shù)集合。這樣,來自于許多不同理論的架構(gòu)都是可比較的。下面是從函數(shù)中提取的步驟:

     圖6 GN模塊塊中的更新。藍(lán)色表示正在更新的元素,黑色表示更新中涉及的其他元素(請注意,藍(lán)色元素更新前的值也在更新中使用)。有關(guān)符號的詳細(xì)信息,請參見原論文的公式1。      

一個(gè)圖網(wǎng)絡(luò)可能包括很多輸出:

  • 節(jié)點(diǎn)狀態(tài)

  • 邊狀態(tài)

  • 整個(gè)圖狀態(tài)

這些可以像嵌入層一樣使用,如分類,評分和預(yù)測。

圖網(wǎng)絡(luò)是非常通用的強(qiáng)大技術(shù),它們已經(jīng)被用來分析很多東西,從自然語言,3D場景到生物學(xué)。我們最近的研究表明,它們可以實(shí)現(xiàn)許多傳統(tǒng)的圖算法。

促進(jìn)了解圖網(wǎng)絡(luò)及其功能的一些參考:

  • Thomas Kipf 的 “How powerful are Graph Convolutional Networks” 說明了一個(gè)未經(jīng)訓(xùn)練的網(wǎng)絡(luò)怎么通過單獨(dú)的結(jié)構(gòu)執(zhí)行分析。

  • GraphSAGE 是大型圖歸納表示學(xué)習(xí)(inductive representation learning)的一個(gè)框架。

  • Deep Learning for Network Biology 對應(yīng)用于生物問題的 Graph ML 技術(shù)進(jìn)行了概述。

    七、 對圖網(wǎng)絡(luò)的擴(kuò)展

    在我們的MacGraph研究項(xiàng)目中,我們一直在嘗試對圖網(wǎng)絡(luò)進(jìn)行一些擴(kuò)展。雖然我們?nèi)栽诟倪M(jìn)這些方法,但它們已經(jīng)展現(xiàn)出很大的希望,值得長期研究。

    我們正在嘗試學(xué)習(xí)不同的推理算法,從圖中提取和轉(zhuǎn)換數(shù)據(jù)。為此,我們在上述網(wǎng)絡(luò)中添加了一系列組件,使其類似于基于圖的圖靈機(jī)器:

    • 每個(gè)節(jié)點(diǎn)上的 GRU 單元使得每個(gè)節(jié)點(diǎn)在多次迭代中更好地保持狀態(tài)。

    • 節(jié)點(diǎn)從基于注意力機(jī)制的全局控制單元讀寫數(shù)據(jù)。

    • 一個(gè)控制單元(本質(zhì)上是一個(gè) LSTM 單元),它把當(dāng)前任務(wù)作為輸入,并向網(wǎng)絡(luò)的其余部分輸出一系列控制信號,指導(dǎo)它們的下一步行動(dòng)——這是基于Macnet體系結(jié)構(gòu)。

    • 節(jié)點(diǎn)和邊列表從注意力導(dǎo)向的控制單元讀取。

    • 供上述組件讀寫的工作狀態(tài)存儲(chǔ)器。

      八、 鏈接預(yù)測

      預(yù)測兩個(gè)節(jié)點(diǎn)之間

      是否存在關(guān)系

      這是一項(xiàng)通常且非常簡單的任務(wù),基本表示為:

      節(jié)點(diǎn)A與節(jié)點(diǎn)B有關(guān)系的概率p(a,r,b)是多少?

      例如知識圖補(bǔ)全(例如,如果米開朗基羅是托斯卡納出生的畫家,他是意大利人嗎?),預(yù)測蛋白質(zhì)相互作用。這兩種方法都可以用來預(yù)測新的未知事物(例如哪些藥物可能有效?)以及改進(jìn)現(xiàn)有不完善的數(shù)據(jù)(例如,此任務(wù)屬于哪個(gè)項(xiàng)目?).

      關(guān)于許多方法的更多信息,可以在前面的“通用 Graph ML 方法”一節(jié)中找到。

      節(jié)點(diǎn)嵌入和隨機(jī)游走

      節(jié)點(diǎn)嵌入(通常使用隨機(jī)游走生成)經(jīng)常用于鏈接預(yù)測。

      嵌入層通常是這樣生成的:圖中鄰近的節(jié)點(diǎn)具有相似的嵌入的張量。然后就能比較距離(例如點(diǎn)積或歐幾里得距離)來預(yù)測存在連接的可能性。有些方法,比如 node2vec,實(shí)際上是直接訓(xùn)練嵌入層的存/無(presence/absence)鏈接樣本。

      圖網(wǎng)絡(luò)可用于生成鏈接預(yù)測的嵌入節(jié)點(diǎn)。在這種情況下,需要將鏈接預(yù)測能力納入到網(wǎng)絡(luò)的損失函數(shù)中。

      具有圖特征的深度學(xué)習(xí)

      這意味著對圖數(shù)據(jù)進(jìn)行序列化,然后在其上運(yùn)行傳統(tǒng)的前饋網(wǎng)絡(luò)。

      例如,每個(gè)節(jié)點(diǎn)可以由其屬性表示(串聯(lián)形成張量)。每個(gè)訓(xùn)練示例都有兩個(gè)節(jié)點(diǎn)和關(guān)系類型作為特征,存在的邊則作為標(biāo)簽。記住要平衡已標(biāo)注的類數(shù)量。

      當(dāng)許多圖結(jié)構(gòu)反映在屬性中時(shí)(例如,街道圖和每個(gè)節(jié)點(diǎn)都有其 GPS 位置),這種簡單的方法可以很好地工作。

      神經(jīng)張量網(wǎng)絡(luò)

           圖7 神經(jīng)張量網(wǎng)絡(luò)

      斯坦福大學(xué)的這種有趣的方法基本上將圖形記憶成張量和矩陣?!拔覀兊哪P蛢?yōu)于以前的模型,可以對 WordNet 和Freebase 中未公開的關(guān)系進(jìn)行分類,準(zhǔn)確率分別為86.2%和90.0%?!?/span>

       強(qiáng)化學(xué)習(xí)

      強(qiáng)化學(xué)習(xí)也可用于鏈接預(yù)測。在這種方法中,網(wǎng)絡(luò)學(xué)習(xí)從圖中提取一系列事實(shí),并結(jié)合這些事實(shí)生成鏈接預(yù)測。

      這種方法的一個(gè)例子是“Multi-hop knowledge graph reasoning with reward shaping”,在這種推理中,網(wǎng)絡(luò)學(xué)習(xí)遍歷圖并使用該信息生成鏈接預(yù)測。

      九、 節(jié)點(diǎn),邊和整個(gè)圖的

      評分和分類

      另一個(gè)常見的任務(wù)是嘗試對圖的一部分進(jìn)行分類或評分。例如,試圖找出與某個(gè)基因相關(guān)的蛋白質(zhì)。或者嘗試根據(jù)他們的交友小組把學(xué)生聚集到他們的學(xué)校。    

      分類意味著輸出潛在標(biāo)簽之間的概率分布,評分意味著輸出一個(gè)可用于與其他標(biāo)簽進(jìn)行比較的權(quán)重。兩者在概念上相似,分類涉及更多維度。

      通常的任務(wù)是定義以下函數(shù)之一,其中 Output 是一組可能的類別分布或一組可能的輸出分?jǐn)?shù):

      f(n:Node) → r ∈ Output

      g(e:Edge) → r ∈ Output

      h(g:Graph) → r ∈ Output

      執(zhí)行此操作的大多數(shù)方法有兩個(gè)步驟:

      1. 對圖執(zhí)行一些計(jì)算,也許是將其節(jié)點(diǎn)和邊的多個(gè)元素組合成存儲(chǔ)在節(jié)點(diǎn)、邊 和/或 整個(gè)圖中的狀態(tài)中。

      2. 提取、聚合并將狀態(tài)轉(zhuǎn)換為所需的輸出。

      步驟1可以使用許多不同的方法來執(zhí)行,我將在下面列出。

      步驟2通常使用前饋神經(jīng)網(wǎng)絡(luò)(FFN)來執(zhí)行。提取和聚合可以使用手工建立的函數(shù)(例如,讀取特定節(jié)點(diǎn)、將特定邊求和)或?qū)W習(xí)的函數(shù)(例如,注意力機(jī)制提取、聚合卷積)。

      這兩個(gè)步驟的選擇都是數(shù)據(jù)科學(xué)和實(shí)驗(yàn)的問題,還沒有出現(xiàn)任何明確的“一刀切”的解決方案。

      關(guān)于其中許多方法的更多信息,可以在前面的“通用 Graph ML 方法”一節(jié)中找到。

      節(jié)點(diǎn)嵌入和隨機(jī)游走

      節(jié)點(diǎn)嵌入為分類和評分提供了豐富的節(jié)點(diǎn)狀態(tài)。

      當(dāng)使用嵌入時(shí),通常這些檢測的節(jié)點(diǎn)通過一個(gè)小的 FFN 網(wǎng)絡(luò)來得到期望的輸出。根據(jù)用例的不同,節(jié)點(diǎn)的屬性也可以包含在FFN的輸入中。

      如果節(jié)點(diǎn)嵌入是使用隨機(jī)游走創(chuàng)建的(例如,使用node2vec),則它們將包含可能與正在執(zhí)行的分類或評分相關(guān)的原始結(jié)構(gòu)信息(例如,節(jié)點(diǎn)所在的邊或其所屬的上一層結(jié)構(gòu))(例如,聚類處于不同圖的子邊)。

      圖網(wǎng)絡(luò)

      圖網(wǎng)絡(luò)是一種將神經(jīng)網(wǎng)絡(luò)嵌入到圖中的通用方法。圖網(wǎng)絡(luò)可以計(jì)算節(jié)點(diǎn)、邊和圖的狀態(tài)(根據(jù)應(yīng)用的場景可以省略其中的一些狀態(tài))。然后可以轉(zhuǎn)換這些狀態(tài)以產(chǎn)生最終輸出。例如,圖狀態(tài)可以通過一個(gè) FFN 來創(chuàng)建一個(gè)完整的圖分類。

      在圖網(wǎng)絡(luò)的論文中有許多不同的例子,請參見導(dǎo)論部分了解它們的概述。

      注意力序列

      一個(gè)有趣的方法是在論文“使用結(jié)構(gòu)化注意力進(jìn)行圖分類”中得來的。在這項(xiàng)工作中,我們使用注意力從圖中反復(fù)讀取節(jié)點(diǎn).

      論文地址:

      http:///pubs/KDD18-graph-attention-model.pdf


           圖8 基于注意力的圖分類,由一個(gè)初始點(diǎn) v*和一個(gè)預(yù)算值 T = 3 點(diǎn)用于圖分類的選擇注意力是用于導(dǎo)航到圖中信息更加充分的部分。

      網(wǎng)絡(luò)的中心是一個(gè) LSTM 單元,它控制從哪個(gè)節(jié)點(diǎn)讀取數(shù)據(jù),將注意力讀取到的數(shù)據(jù)合并到其內(nèi)部的狀態(tài),然后輸出對圖分類的預(yù)測。

      這類似于用于機(jī)器推理的綜合注意力網(wǎng)絡(luò)中的方法(盡管不在圖數(shù)據(jù)上),其中一個(gè)中心 RNN 單元引導(dǎo)注意力讀取和讀取數(shù)據(jù)的合成。

      *論文鏈接https://cs./people/dorarad/mac/blog.html

      基于分塊或節(jié)點(diǎn)屬性的

      傳統(tǒng)深度學(xué)習(xí)

      將問題簡化為一個(gè)對照數(shù)據(jù)集,可以找到許多更好的研究方法(例如前饋和卷積神經(jīng)網(wǎng)絡(luò))。

      一種方法是將每個(gè)節(jié)點(diǎn)及其屬性視為一個(gè)訓(xùn)練樣本。這可能涉及手工創(chuàng)建你認(rèn)為將有助于 分類/評分 的附加屬性。

      創(chuàng)建圖的另一種方法是提取固定大小的分塊。在這個(gè)模型中,一個(gè)節(jié)點(diǎn)、它的邊以及它的近鄰節(jié)點(diǎn)被提取到一個(gè)固定大小的表中。固定大小意味著邊和節(jié)點(diǎn)有最大數(shù)量的存儲(chǔ)限制,如果表中存在多出邊和節(jié)點(diǎn),則必須隨機(jī)抽樣。此外,如果節(jié)點(diǎn)和邊少于固定表可以存儲(chǔ)的數(shù)量,則需要用指定的空值填充。最后,必須選擇如何選擇分塊-一個(gè)簡單的模型是從每個(gè)節(jié)點(diǎn)或邊提取一個(gè)分塊。

      表格化丟棄了隱藏在網(wǎng)絡(luò)信息中的價(jià)值,但簡化了工程和模型研究。

      節(jié)點(diǎn)屬性在搜索引擎上的技術(shù)

      最后,也有一些非機(jī)器學(xué)習(xí)方法值得思考。如果在某種鏈接、內(nèi)容或文本的基礎(chǔ)上對節(jié)點(diǎn)進(jìn)行評分,可能會(huì)對搜索引擎/文檔檢索效果提升有效。

      這包括簡單的模糊文本匹配,到 PageRank,短語和語義匹配。

      這是一個(gè)非常成熟的計(jì)算機(jī)科學(xué)領(lǐng)域。更多提示,請查閱維基百科的信息檢索文章。

      附錄

      在本文中,我引用了很多資源,為了方便起見,都在此列出。此外,我還添加了其他前面未列出的有趣項(xiàng)目。

      Surveys of the field

      • A good survey of the different structural approaches to graph machine learning (I’d recommend starting with this one):Graph Neural Networks: A Review of Methods and Applications

        • https:///pdf/1812.08434v1.pdf

      • A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications

        • https:///pdf/1709.07604.pdf

      • Graph Embedding Techniques, Applications, and Performance: A Survey

        • https:///pdf/1705.02801.pdf

      • A Survey on Network Embedding

        • https:///abs/1711.08752

      • Attention Models in Graphs: A Survey

        • https:///abs/1807.07984

      • Deep Learning for Network Biology

        • http://snap./deepnetbio-ismb/slides/deepnetbio-part2-gcn.pdf

      • Representation Learning on Graphs: Methods and Applications

        • https://cs./people/jure/pubs/graphrepresentation-ieee17.pdf

      • Network Representation Learning: A Survey

        • https:///abs/1801.05852

      • Graph Summarization Methods and Applications: A Survey

        • https:///abs/1612.04883

      • Must-read papers on knowledge representation learning (KRL) / knowledge embedding (KE)

        • https://github.com/thunlp/KRLPapers

      Random walks / embeddings

      • node2Vec

        • https:///pdf/1607.00653.pdf

      • Review prediction with Neo4j and TensorFlow

        • https:///octavian-ai/review-prediction-with-neo4j-and-tensorflow-1cd33996632a

      • Knowledge graph embedding: a survey of approaches and applications

        • https:///octavian-ai/review-prediction-with-neo4j-and-tensorflow-1cd33996632a

      • A novel embedding model for knowledge base completion based on CNN

        • https:///octavian-ai/review-prediction-with-neo4j-and-tensorflow-1cd33996632a

      • GEMSEC: Graph embedding with self clustering

        • https:///pdf/1802.03997.pdf

      Graph Networks

      • Relational inductive biases

        • https:///abs/1806.01261

      • Graph convolutional networks

        • https:///abs/1806.01261

      • GraphSAGE

        • https:///abs/1806.01261

      • Smart Reply: Automated Response Suggestion for Email

        • https://static./media/research.google.com/en//pubs/archive/45189.pdf

      • 3D graph Neural Networks for RGBD Semantic Segmentation

        • http://www.cs./~rjliao/papers/iccv_2017_3DGNN.pdf

        Knowledge graphs

        • DeepPath: A Reinforcement Learning Method for Knowledge graph Reasoning

          • https://www.cs./~william/papers/DeepPath.pdf

        • Multi-hop knowledge graph reasoning with reward shaping

          • https://www.cs./~william/papers/DeepPath.pdf

        • Neural Tensor Networks

          • https://nlp./pubs/SocherChenManningNg_NIPS2013.pdf

        • MacGraph?—?Iterative reasoning on knowledge graphs

          • https://nlp./pubs/SocherChenManningNg_NIPS2013.pdf

        • KBGAN: Adversarial Learning for Knowledge graph Embeddings

          • https:///pdf/1711.04071.pdf

        Miscellaneous

        • Compositional Attention Networks for Machine Reasoning

          • https://cs./people/dorarad/mac/blog.html

        • graph classification using Structural Attention

          • https://cs./people/dorarad/mac/blog.html

        • GAMEnet: graph augmented memory networks for recommending medication combination

          • https:///pdf/1809.01852.pdf

        • Modeling Relational Data with raph Convolutional Networks

          • https:///pdf/1703.06103.pdf

        • Answering questions using knowledge graphs and sequence translation

          • https:///octavian-ai/answering-english-questions-using-knowledge-graphs-and-sequence-translation-2acbaa35a21d

        翻譯:王舒凡

        審校:陳曦

        編輯:王怡藺

        原文地址:

        https:///octavian-ai/how-to-get-started-with-machine-learning-on-graphs-7f0795c83763

          本站是提供個(gè)人知識管理的網(wǎng)絡(luò)存儲(chǔ)空間,所有內(nèi)容均由用戶發(fā)布,不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息,謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請點(diǎn)擊一鍵舉報(bào)。
          轉(zhuǎn)藏 分享 獻(xiàn)花(0

          0條評論

          發(fā)表

          請遵守用戶 評論公約

          類似文章 更多

          亚洲一区二区三区福利视频| 91日韩在线观看你懂的| 日韩国产传媒在线精品| 亚洲专区一区中文字幕| 欧美日韩精品一区免费| 99精品人妻少妇一区二区人人妻| 亚洲精品中文字幕熟女| 日本一二三区不卡免费| 麻豆视频传媒入口在线看| 亚洲中文字幕在线视频频道| 午夜福利网午夜福利网| 精品国产91亚洲一区二区三区| 亚洲天堂男人在线观看| 亚洲性生活一区二区三区| 国产三级视频不卡在线观看| 精品国自产拍天天青青草原| 午夜视频成人在线观看| 白白操白白在线免费观看| 国产精品免费福利在线| 欧美一区二区三区不卡高清视 | 亚洲视频一级二级三级| 久草国产精品一区二区| 欧美日本道一区二区三区| 久久亚洲精品中文字幕| 国产亚洲视频香蕉一区| 国产在线观看不卡一区二区| 国产日韩欧美国产欧美日韩| 国产av熟女一区二区三区四区 | 色哟哟哟在线观看视频| 麻豆看片麻豆免费视频| 亚洲综合伊人五月天中文| 亚洲伦理中文字幕在线观看| 欧美人与动牲交a精品| 三级高清有码在线观看| 国产成人亚洲欧美二区综| 在线观看视频日韩成人| 精品少妇一区二区视频| 成人你懂的在线免费视频| 老司机精品一区二区三区| 国产精品日韩精品一区| 亚洲欧美日韩在线中文字幕|