論文筆記整理：葉群，浙江大學計算機學院，知識圖譜、NLP方向。

---

會議：WSDM 2019

鏈接：https://dl.acm.org/citation.cfm?id=3290961

Motivation

基于spring-electrical的模型在網絡可視化中取得了非常成功的應用，一個優秀的網絡可視化算法意味著越相似的節點在空間中歐式距離越相近。本文將spring-electrical模型應用在了鏈接預測問題上，前提是假設節點之間的歐氏距離和節點之間存在link的概率成正相關。性能評估上，模型與baseline的對比顯示了其性能的優越，尤其是在node embedding維度很低的時候。

Problem Statement

????? 知識圖譜由于種種原因，其中很多節點之間存在缺失的邊。鏈接預測算法指的是，給定網絡節點和網絡結構等信息，去預測尚未存在邊的節點之間存在鏈接的概率。實驗中，給定網絡G=<V,E>，我們隨機掩蓋一定比例的邊（如10%），并采樣一部分負例作為測試集，然后將剩下90%的邊和所有節點作為訓練集。

評估指標采用AUC值：

Baseline

介紹三種常用的baseline

1. Local similarity indices

分析節點周圍的局部結構，作為節點之間存在鏈接的概率（以下式子中δ表示節點的相鄰一跳節點）。

• Common neighbours：以兩節點公共鄰居的個數來衡量存在鏈接的概率

• Adamic-Adar index：common neighbours的一種加權的改進

• Preferential Attachment index：以節點現有的度來衡量節點之間存在鏈接的概率（非常na?ve的assumption）

2. Matrix factorization

矩陣分解的方式將網絡的鄰接矩陣作為輸入，分解成兩個低秩的矩陣。低秩矩陣的行或列可以作為節點的latent feature，將兩節點的latent feature做點積，即可得到兩節點之間存在鏈接的概率。

• Truncate SVD

• Non-negative matrix factorization（NMF）

3. Neural embedding

一些工作嘗試用神經網絡來學習graph embedding，比如經典的DeepWalk和node2vec算法，都是受word2vec的啟發。基本思想是將圖中的節點當做單詞，在圖中隨機游走得到一系列節點當作一個句子，然后利用word2vec的目標函數來做訓練。訓練完成后，將節點的embedding做點積，即得到節點之間存在鏈接的概率。

Model

Spring-electrical中的spring指的是彈簧，electrical指的是電荷，其基本思想是將一張圖當做一個機械系統，將圖中的節點比作電荷，將邊比作彈簧。所有的電荷均為同性電荷，相互之間存在斥力；彈簧力表現為引力。基于這樣的假設，當這個力學系統達到平衡之后，不存在邊相連的節點將會由于斥力，在空間距離上分布較遠。

對庫倫定律進行修改，引入超參p，電荷之間的斥力公式為：

對虎克定律進行修改，彈簧的引力公式為：

通過利用力是能量的負梯度這個性質，可以將一個力學系統轉換成能量系統，力的平衡對應系統能量的最小值。所以，目標函數為求解系統能量的極小值，即：

???? 上式的求解存在兩個問題：1）計算復雜度過大；2）容易收斂到局部極小值。本文采用了一種叫做ScalableForce Directed Placement（SFDP）的優化方法進行求解，較好的解決了這兩個問題。

Case Study

????? 在實際的數據集上進行評估之前，本文先在由球體的三角剖分得到的圖上進行了casestudy。鏈接預測的結果如下圖所示，可以看到SFDP方法取得了很好的效果，同時注意到SFDP方法在向量維度極小的情況（d=2,3）下，依舊取得非常好的效果。

除此之外，實驗將d=3的向量進行了可視化（如下圖），比較了不同模型可視化的差異。可以看到，SFDP方法很好的保留了球體的原始形狀，SVD向量分布在3條坐標軸上，node2vec則是一個錐形。造成這種差異的原因是，SFDP采用了歐式距離作為損失函數，而SVD和node2vec則是基于點積。基于歐式距離的損失函數會使不相似的節點在空間上盡可能遠，而點積則會使不相似節點盡可能垂直。

Experiment

實驗在以下幾個公開數據集上做了評估：PowerGrid: 美國的電力供應網絡；Euroroad: 歐洲道路交通網絡；Airport: 美國航空機場網絡；Facebook:????? Facebook社交網絡；Reactome: 蛋白質的相互作用網絡；Ca-HepTh:arXiv上的作者合作關系網絡。

實驗結果如下圖所示，SFDP在多數數據集上的表現都達到最優，同時在向量維度d=2,3時就可以得到非常好的實驗效果。

下表是得到最佳結果時embedding維度的比較，SFDP方法在d=2,3維度時的結果就可以媲美其他模型100維甚至500維的效果，embedding效率極高。

下表給出了SFDP模型與localsimilarity indices方法的效果比較：

另外實驗還在二分網絡和有向圖數據集上進行評估，并對SFDP做了相應的修改。

Conclusion

??????????? 本文將網絡可視化中的spring-electrical模型應用在了鏈接預測問題上，在數據集評估上取得了十分優越的結果，尤其是在低維空間展現了非常好的效果。Embedding維度效率的提升可以解決向量嵌入在現實應用中的一些問題，如向量維度過高時最近鄰搜索的計算復雜度過高。后續工作可以聚焦在如何為latent feature model選擇更優的距離度量以及向量維度效率更深入的分析。

?

---

OpenKG

開放知識圖譜（簡稱 OpenKG）旨在促進中文知識圖譜數據的開放與互聯，促進知識圖譜和語義技術的普及和廣泛應用。

點擊閱讀原文，進入 OpenKG 博客。

總結

以上是生活随笔為你收集整理的论文浅尝 | 一种嵌入效率极高的 node embedding 方式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。