歡迎光臨
每天分享高質量文章

KDD 18論文解讀 | 斯坦福大學提出全新網絡嵌入方法 — GraphWave

在碎片化閱讀充斥眼球的時代,越來越少的人會去關註每篇論文背後的探索和思考。

在這個欄目里,你會快速 get 每篇精選論文的亮點和痛點,時刻緊跟 AI 前沿成果。


點擊本文底部的「閱讀原文」即刻加入社區,查看更多最新論文推薦。

這是 PaperDaily 的第 100 篇文章

本期推薦的論文筆記來自 PaperWeekly 社區用戶 @xuehansheng本文是斯坦福大學發表於 KDD ’18 的工作,論文提出了一種通過利用熱小波擴散樣式、通過低維嵌入來表示每個節點的網絡鄰域的方法——GraphWave。 


GraphWave 不是在手工選擇的特征上進行訓練,而是以無人監督的方式學習這些嵌入。文章在數學上證明具有相似網絡鄰域的節點將具有類似的 GraphWave 嵌入,即使這些節點可能駐留在網絡的非常不同的部分中。

如果你對本文工作感興趣,點擊底部閱讀原文即可查看原論文。

關於作者:薛寒生,澳大利亞國立大學博士生,研究方向為人工智慧與計算生物學。

■ 論文 | Learning Structural Node Embeddings via Diffusion Wavelets

■ 鏈接 | https://www.paperweekly.site/papers/2204

■ 原始碼 | https://github.com/snap-stanford/graphwave


論文動機


駐留在圖的不同部分中的節點可能在其本地網絡拓撲中具有類似的結構角色。然而學習節點的結構表示是一項具有挑戰性的無監督學習任務,其通常涉及為每個節點人工指定和定製拓撲特征。 


GraphWave 是一種可擴展的無監督方法,用於基於網絡中的結構相似性來學習節點嵌入。 GraphWave 通過將小波視為概率分佈,並使用經驗特征函式表徵分佈來開發光譜圖小波的新用途。 


GraphWave 提供理論保證,具有相似本地網絡鄰域的節點將具有類似的 GraphWave 嵌入,即使這些節點可能駐留在網絡的非常不同的部分中。 GraphWave 與邊數成線性比例,不需要任何人工定製節點的拓撲特征。

GraphWave 模型介紹

GraphWave 基於以該節點為中心的譜圖小波的擴散,學習每個節點的結構嵌入。直觀地,每個節點在圖上傳播能量單位,並基於網絡對該探測的響應來表徵其相鄰拓撲。


GraphWave 使用一種新穎的方法將小波視為圖上的概率分佈。通過這種方式,結構信息包含在擴散如何通過網絡傳播而不是傳播的位置。為了提供矢量值特征,然後可以將其用作任何機器學習演算法的輸入,GraphWave 使用經驗特征函式嵌入這些小波分佈。


在上圖中,節點 a 和 b 具有相似的區域性結構角色,即使它們在圖中很遠。雖然 a 和 b 的原始光譜圖小波簽名/繫數 Ψ 可能非常不同,但 GraphWave 將它們視為概率分佈,因此可以自動瞭解繫數分佈確實相似。Graphwave 利用這些新見解,基於以節點 a/b 為中心的譜圖小波的擴散,學習節點 a/b 的結構嵌入。


GraphWave Algorithm 


實驗結果


Barbell Graph 


在這個例子中,文章考慮一個杠鈴圖,它由兩個由長鏈連接的密集團組成。 我們將 GraphWave 應用於杠鈴圖並繪製學習結構簽名的 2D PCA。 


從下圖中可以看出,該圖具有 8 個不同類別的結構等效節點,如顏色(左)所示。 結構簽名的 2D PCA 投影(右)包含與杠鈴圖中的節點相同數量的點。 這是因為相同的簽名具有相同的投影,導致重疊點。



GraphWave 正確地學習了結構等效節點的相同表示,為 GraphWave 的理論保證提供了經驗證據。這可以通過圖中的結構等效節點(相同顏色的節點)在 PCA 圖中具有相同的投影來看出。


特別是,GraphWave 正確地將 clique 節點(紫色)組合在一起。GraphWave 還正確區分連接杠鈴圖中兩個密集團的節點。它以類似梯度的樣式表示那些捕獲這些節點的結構角色譜的節點(右)。 


A Cycle Graph with Attached House Shapes 在這個例子中,文中考慮一個圖形,其中“房屋”形狀沿迴圈圖定期放置。和以前一樣,我們使用 GraphWave 來學習圖中節點的結構簽名,然後使用有關結構角色的地面實況信息來評估 GraphWave 的性能。


圖形在下圖(左)中可視化,同時還有 GraphWave 結構簽名的 2D PCA 投影(中間)。我們觀察到結構等效節點的表示重疊,GraphWave 完美地恢復了 6 種不同的節點型別。



可以看到小波繫數分佈的最終特征函式(右)。在該圖中,不同形狀的特征函式捕獲不同的結構角色。我們註意到這些曲線所攜帶的藍色,淺綠色和紅色節點的作用之間的視覺接近度,以及它們與核心深綠色和紫色節點的明顯差異。

總結

文中提出了一種全新的 NE 方法 GraphWave,該方法使用譜圖小波為每個節點生成結構嵌入,我們通過將小波視為分佈並評估結果特征函式來實現。為網絡嵌入提供了全新的思路。

本文由 AI 學術社區 PaperWeekly 精選推薦,社區目前已改寫自然語言處理、計算機視覺、人工智慧、機器學習、資料挖掘和信息檢索等研究方向,點擊閱讀原文即刻加入社區!


點擊以下標題查看更多論文解讀: 


#投 稿 通 道#

 讓你的論文被更多人看到 


如何才能讓更多的優質內容以更短路徑到達讀者群體,縮短讀者尋找優質內容的成本呢? 答案就是:你不認識的人。


總有一些你不認識的人,知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁,促使不同背景、不同方向的學者和學術靈感相互碰撞,迸發出更多的可能性。 


PaperWeekly 鼓勵高校實驗室或個人,在我們的平臺上分享各類優質內容,可以是最新論文解讀,也可以是學習心得技術乾貨。我們的目的只有一個,讓知識真正流動起來。

來稿標準:

• 稿件確系個人原創作品,來稿需註明作者個人信息(姓名+學校/工作單位+學歷/職位+研究方向) 

• 如果文章並非首發,請在投稿時提醒並附上所有已發佈鏈接 

• PaperWeekly 預設每篇文章都是首發,均會添加“原創”標誌


? 投稿郵箱:

• 投稿郵箱:hr@paperweekly.site 

• 所有文章配圖,請單獨在附件中發送 

• 請留下即時聯繫方式(微信或手機),以便我們在編輯發佈時和作者溝通



?


現在,在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關註」訂閱我們的專欄吧

關於PaperWeekly


PaperWeekly 是一個推薦、解讀、討論、報道人工智慧前沿論文成果的學術平臺。如果你研究或從事 AI 領域,歡迎在公眾號後臺點擊「交流群」,小助手將把你帶入 PaperWeekly 的交流群里。

▽ 點擊 | 閱讀原文 | 下載論文 & 原始碼

赞(0)

分享創造快樂