[Structural Deep Embedding for Hyper-Networks](https://arxiv.org/abs/1711.10146) 是在hyperedge(超邊是不可分解的)的基礎上保留object的一階和二階相似性，學習異質網絡表示。于與HEBE的差別在于，本文考慮了網絡high-oeder網絡結構和高度稀疏性。 傳統的基于clique expansion 和star expansion的方法，顯式或者隐式地分解網絡（如下圖所示）。也就說，分解後hyper edge節點地子集，依然可以構成一個新的超邊。對于同質網絡這個假設是合理地，因為同質網絡地超邊，大多數情況下都是根據潛在地相似性（共同地标簽等）建構的。
但是在異質網絡中要解決兩個問題：不可分解性和結構保留。對于不可分解性，作者設計了不可分解的tuplewise相似性函數。這個相似性函數定義在hyper edge的所有節點上，確定超邊的子集并沒有融合在網絡表示中，并且這個函數是非線性的。為了保留網絡結構，作者設計了一個 Auto encoder，通過重構節點的鄰居結構來學習節點表示，也就說有相似鄰居的節點将有相似的向量表示，每一種節點類型對應一個auto encoder。這兩部分在模型中，聯合優化來同時解決這兩個問題。模型架構圖如下：
####幾個定義 **1. Hyper Network：**一般形式為 G=(V,E) ，有T個類型的節點 V={Vt}Tt=1 ，網絡中的邊是超邊：即可以連接配接任意數量的節點： E={Ei=(v1,v2,vni)}(ni≥2) 。如果每個超邊隻連接配接兩個節點，那麼就退化為一般的network；如果 T≥2 ，那麼就是 heterogeneous hyper-network。 **2. First-Order Similarity:** 一階相似性衡量的是節點間的N-tuplewise相似性。對于節點 v1,v2,⋯,vN ，如果他們之間存在超邊，那麼這N個節點的一階相似性是1，但是這種相似性并不存在于這N個節點的子集上。 **3. Second-Order Similarity:** hyper-network上的二階相似性，衡量的是節點的鄰居結構之間的相似性。鄰居指的是： Ei∖vi,ifvi∈Ei 。 #### Loss Function 節點 vi 的向量表示是 Xi ，S表示 N-tuplewise的相似性函數。也就說 1. if (v1,v2,⋯,vN)∈E ，那麼 S(v1,v2,⋯,vN) 的值比較大（大于門檻值 l）。 2. if (v1,v2,⋯,vN)∉E ，那麼 S(v1,v2,⋯,vN) 的值比較小（小于門檻值s）。 本文考慮的是N=3的均勻長度的超邊。 scoring函數S不可以是線性的。如果是線性的那麼： S(v1,v2,⋯,vN)=∑iWiXi 。證明參考論文，基于門檻值l和s，舉個反例。 對于一階相似性，本文采用的是multilayer perceptron，分成兩個部分。第一部分是模型架構中的第二層，這是個全連接配接層而且激活函數是非線性的。輸入是三個節點 (vi,vj,vk) （他們屬于三個不同的節點類型a,b,c）的向量表示 (Xai,Xbj,Xck) 。作者把他們拼接起來，并且映射到統一的空間L。 Lijk=σ(W(2)a∗Xai+W(2)b∗Xbj+W(2)c∗Xck+b(2))
為了得到相似性，把它統一的空間中的表示 Lijk 映射到第三層的機率空間中： Sijk=S(Xai,Xbj,Xck)=σ(W(3)∗Lijk+b(3))
如果節點 (vi,vj,vk) 之間存在hyper edge，那麼 Rijk 的值為1，否則為0。損失函數（1）： L1=−(RijklogSijk+(1−Rijk)log(1−Sijk))
從上式可以看出，如果 Rijk 的值為1，則 Sijk 的值比較大；如果 Rijk 的值為0，則 Sijk 的值比較小。這也就保留了一階相似性。 **二階相似性**，跟[SDNE](http://dl.acm.org/citation.cfm?doid=2939672.2939753)的思想是很相似的，也是構造鄰接矩陣作為Auto encoder的輸入。鄰接矩陣 A=HHT−Dv 。矩陣 H 是 |V|×|E| 關聯矩陣，每個元素h(v,e)=1，如果節點v屬于超邊e，否則為0；矩陣 Dv 是對角矩陣，包含着節點的度 d(v)=∑e∈Eh(v,e) 。因而，鄰接矩陣的每一項代表着兩個節點的共同出現的次數。 Auto encoder包含編碼器和解碼器。編碼器是把輸入A非線性映射到X空間，解碼器是把X非線性的重構到原始的特征空間 A^ 。 Xi=σ(W(1)Ai+b(1))A^i=σ(W^(1)Xi+b^(1))
Auto Encoder的目的就是最小化輸入和輸出的重構錯誤。這就使得有相似鄰居結構的節點，向量表示相近，也就是保留了二階相似性 。鄰接矩陣往往是稀疏的，因而作者隻是處理非零項，通過sign函數。此外，每個節點類型對應着一個Auto encoder，因而損失函數是： L2=∑t||sign(Ati)⊙(Ati−A^ti)||2F
為了保留一階和二階相似性，論文聯合最小化目标函數： L=L1+αL2
在大多數現實世界的網絡中隻有正相關關系，是以這個算法收斂時，其中所有的元組關系都是相似的。為了解決這個問題，根據噪聲分布，為每條邊采樣多個負邊。整體算法如下：
在實驗方面，作者用了四個資料集：
- GPS：超邊是（user, location, activity）
- MovieLens：超邊是（user, movie, tag）
- drug：超邊是（user, drug, reac- tion）
- WordNet：超邊是（entity, relation, tail entity）