原名 : Structural Deep Embedding for Hyper-Networks

1. Introduction

這篇論文介紹了一種處理具有 hyperedge 的網路結構的方法.

1.1 Hyperedge

一般的網路結構, 我們的edge都是二元的, 即使有多元的(即需要多個node的參與), 也是將其分解為多個edge. 作者的初衷是認為, 這種 hyperedge是不可分解的. 因此提出了這個方案.

hyperedge網路還有一個難以處理的地方, 有很多node之間的關係並不是通過直接聯繫的, 而是通過鄰接的鄰接, 或者是鄰接的鄰接的..., 現在的網路模型還無法發現這種結構的關係.

1.2 Heterogeneous

真實世界的網路往往還具有異質性(Heterogeneous). 這種特性表現為, network的節點不止是embedding不一樣, 並且在類型上具有本質的區別. 例如在人際網路中, 老師和學生屬於完全不同的類型的節點.

1.3 本文貢獻

1.3.1 DHNE

提出了一個DHNE網路模型去embedding indecomposable hyper-network embedding.

並且演算法複雜度是 O(n)

1.3.2 Indecomposibility

提供了一種處理局部和全局的非分解性結構信息的方法.

1.3.3 Experiments

在真實世界網路上進行了實驗, 效果不錯.

2. Notations and Definitions

2.1 Hyper-network

相比於普通的 graph network, 這裡的網路定義多了兩個東西,

第一個是node 的type, 這個是為了支持異質網路特性.

第二個是擁有 node 的 set 作為參數的邊, 這個是為了支持 hyperedge.

然後, 每個node V 擁有一個embedding X.

當 T=1 時, 也就是node的種類只有一種時, 網路從異質網路退化為普通網路.

2.2 The first-order proximity

一階接近, 是一種近似度標準, 說的是n個node之間的相似度, 只看這兩個n就可以.

比如說, 我們看n個人的性格像不像, 這裡的方法是通過分析這n個人來進行計算.

2.3 The second-order Proximity

二階接近, 是一種近似度標準, 說的是n個node之間的相似度, 將n個node的各個node的鄰接點當作計算相似度的參數.

看n個人性格像不像也可以通過他們的朋友來得知, 人以類聚物以群分嘛.

2.4 圖示

其中的圈就是 hyperedge.

3. Deep Hyper-Network Embedding

3.1 一圖勝千言

只看這個圖的話,

  • 模型先通過自編碼器把不同類型的 node, 轉化為向量.

3.2 Loss function

3.2.1 Property 1

loss function 應該具有的一點特性是, 具有同一個 hyperedge 的 nodes 之間的相似度應該高, 反之應該低. 公式為:

3.2.2 Theorem 1

若 mathcal{S}(X_1,X_2,...,X_n) 是一個線性函數, 那麼 mathcal{S}(X_1,X_2,...,X_n) 是無法滿足 Property1 的.

論文中給出了證明, 有興趣的看論文.

因此論文提出了下面這個非線性變換的函數, 這個函數的目的是把被一個hyperedge連接的nodes合三為一, 映射到一個 common latent space L.

本論文使用的 hyperedge 最大是三元關係

接下來利用這個新的space中的向量去計算三個nodes之間的相似度.

3.2.3 Loss function

這個模型從兩個思路來設計 loss function,

3.2.3.1. first-order proximity

第一個是, 同一個 hyperedge 下的 nodes 之間的 first-order proximity 應該是很大的, 反之, 不屬於同一個 hyperedge 的 nodes 的 first-order proximity 應該是很小的.

為了滿足這個條件, 設計了如下的一個函數.

可以看出, 這個函數本質和 邏輯回歸的損失函數很像, 很好理解.

其中的 R_{ijk} 是一個 1函數, 即, 如果, node ijk 屬於一個 hyperedge, 則等於1; 反之為0.

3.2.3.2. Second-order proximity

  • 鄰接矩陣A第二個是, second-order proximity, 處理思想和上面一樣, 由於這個是 hyperedge 網路, 所以在定義和處理上有一些複雜.首先在上面的模型圖中, 一開始就有個 A , 這裡的 A 其實就是點和點之間的鄰接矩陣.A 是一個矩陣, 其中, A=HH^T-D H 也是一個矩陣, H_{ij} 代表的是第i個node, 是否被 edge j 包含在內. 因此, 矩陣中全是0/1值. 那麼,

    HH^T 就是一個將點和點之間的互連信息全部匯總的矩陣, 其中 (HH^T)_{ij} , 指的是, 第

    i個node和第j個node之間的連接數. D是一個對角矩陣, 對角線上是每個node的度值.那麼 A_{i} 這一行就是說, 第i個node與所有node的連接信息.
  • autoencoder模型通過對 A 中的每一行進行autoencoder來獲得node的向量.

autoencoder的意義是, 使得擁有相似鄰居的節點的embedding相近.這樣就提供了 Second-order proximity 所需要的信息.autoencoder的重建誤差函數是 :

  • 多個autoencoder並且, 模型對不同類型的node之間進行了區分. 另 A_i^j node i 與代表 type 為 j 的所有node的相關信息.不過這裡我很不解的是, 如果這樣設定的話, 豈不是只能表示同種node之間的相關關係.
  • Second-order proximity這樣就提供了Second-order proximity的損失函數所需要的信息.

3.2.3.3. Loss function

最後的損失函數是:

3.2.4 小結

這裡模型的設置感覺是非常經典的, 非常巧妙的

  • 利用損失函數去表達將向量應該具有的信息加入到模型中, 即關於屬性1的假設.
  • 利用autoencoder 去加入二階信息.

4. Optimization

省略

5. Experiment

這裡採用的是網路重建任務和link 預測任務, 基於四個數據集去評價向量的優劣.

5.1 四個數據集

只關心最後一個, 即wordnet的數據集, 這裡將邊視作一個node, 構建了 <辭彙-關係-辭彙> 這樣三元關係的 hyper-netwoek.

5.2 評價用任務

網路重建任務是利用訓練好的向量去預測原來網路之中的關係, 將關係加入到網路中.

效果如下:

link 預測任務是對於新的網路中的link的預測.

效果如下:


推薦閱讀：
相关文章