hyper graph是一種廣義上的圖，它的邊可以連接配接任意數量的定點。[維基百科](https://zh.wikipedia.org/wiki/%E8%B6%85%E5%9B%BE)。超圖是一個集合組 H=<X,E> , X是一個有限集合，該集合的元素稱為節點或頂點；E是X的非空子集的集合，成為超邊（hyper edge）或連接配接。是以，E是 P(X)∖{ϕ} 的一個子集，其中 P(X) 是X的一個幂集。圖的邊有一對節點，而超邊是節點的任意集合，因而可以有任意數量的節點。每個超邊連接配接節點數目相同的超圖，是k-均勻超圖。如下圖所示（[維基百科](https://zh.wikipedia.org/wiki/%E8%B6%85%E5%9B%BE)）：
HEBE（Large-Scale Embedding Learning in Heterogeneous Event Data）
對于隻包含單種interaction的網絡，一般都是在局部采集上下文(比如在文本中的，滑動視窗内的詞視為上下文)，然後通過預測上下文來建構目标函數。
對于一個包含多種節點和邊類型的網絡，現有的方法PTE等，将所有object之間同時存在的interaction分解為幾個分散的pairwise的interaction（比如論文網絡，分解為論文-作者，論文-期刊/會議等），然後用傳統的single-typed網絡embedding方法求解。這種分解會丢失很多重要的資訊，舉個例子: A在期刊V上發表了論文 P1 , B在期刊V上發表了論文 P2 ，但是A-B之間并沒有合作關系（ A−P1−V−P2−B ）。
HEBE 主要做的就是把跟一個事件相關的節點都關聯到一個hyper edge中，以此來保留網絡更多的資訊。
如下圖所示：
例1 DBLP資料隻有一種event ：
例2 Yelp資料有兩種event ：
幾個基本定義
1. Information Network： 給定一個有T類objects的集合 X={Xt}Tt=1 （ 其中 Xt 是所有 tth 類的object的集合），資訊網絡就是 G=(X,E) ， E 是連接配接兩個object的邊。如果 T≥2 ， 那麼是異質(heterogeneous)網絡；如果T=1，那麼是同質（homogeneous）網絡。
2. 事件(event)： Qi 可以表示為 <Vi,wi> <script type="math/tex" id="MathJax-Element-14"> </script>，其中 wi 是事件 Qi 的權重； Vi={Vti}Tt=1 ，并且 Vti⊆Xt 表示的是屬于t類型的object的集合。
3. 超邊： Hi 刻畫事件Q_i$，它把與事件的所有相關objects看作一個整體。
4. Subevent：子事件就是從每個object類型中均勻地采樣出一個object組成地事件。現實的場景中，一個事件中的不同object類型對應的object數目 |Vti|≥1 （比如：一篇論文對應多個作者，多個term，卻隻對應一個venue）。對于一個事件 Qi={Vi,wi},Vi={a1,a2,a3}∪{t1,t2,t3}∪{v1} 。那麼我們以1/（2*3）的機率可以得到子樣本 Qi,s=a2,t2,v1 ，相應的子樣本的權重為 wi/(2×3) 。這也就造成了，不同的event有相同的Subevent。
模型建構
事件(event)的相似性：在event相關的所有object中，選出一個作為target，然後用剩餘的objects作為上下文C預測這個object。并且，作者将target的候選集，定義在與target同類型的幾點上，比如target是u， u∈X1 并且 u∉C ，條件機率定義為：
P(u|C)=exp(S(u,C))∑v∈X1exp(S(v,C))
S是一個scoring function， 表示u/v與上下文C的相似度。假設上下文是 C={c1,c2,⋯,cT} ，并且對象u的向量表示為 w⃗ u∈Rd ，那麼S函數可以表示為：
S(u,C)=<w⃗ u,1T−1∑t=2Tw⃗ ct>
為了保留object之間的相似性，最小化 P(u|C) 和經驗分布 Pˆ(u|C)= 之間的KL距離（假設：目标object類型為t，對應的上下文為 Ct ， Pt 是 Ct 的采樣空間 Pt={Ci,t}Ni=1 ）：
L=−∑Tt=1γt∑Ct∈PtλCtKL(Pˆ(⋅|C),P(⋅|C))
其中\gamma_t 為t類型的重要性參數，本文設定為 γ1=γ2=⋯=γT ； λCt 表示上下文 Ct 的重要性：
λCt=∑Ni=1wiI{Ct=Vi∖ui,t}
其中， Pi,t 是 Pt 在 Vi 上的子集。 I{⋅} 是一個二進制訓示函數。因而， λCt 可以直覺的解釋為：以 Ct 作為自己的超邊權重數量。
基于 λCt 上式可以化簡為：
L=−∑Tt=1∑Ct∈PtλCtKL(Pˆ(⋅|C),P(⋅|C))=−∑Tt=1∑Ct∈Pt∑Ni=1wiI{Ct=Vi∖ui,t}⋅∑Nj=1Pˆ(uj,t|Ct)logPˆ(uj,t|Ct)P(uj,t|Ct)=−Cˆ+∑Tt=1∑Ni=1wilogP(ui,t|Vi∖ui,t)
其中 Cˆ 是一個常數，經驗分布的計算為：
Pˆ(ui,t|Ct)=wi∑Nj=1wjI{Ct=Vj∖uj,t}
對于多事件（event）類型的網絡，目标函數可以寫為：
L=∑Kk=1Lk
優化（Noise Pairwise Ranking）
直接優化目标函數 L 計算量比較大，每次計算條件機率 P(u|Ct) 都要周遊多有的屬于t類型的object。noise contrastive estimation (NCE)和 negative sampling（NEG）都是把這個問題作為分類問題來解決的。但是負采樣的方法，受超參數 k （負樣本的數量）的影響，為了規避這個問題，本文提出了Noise Pairewise Ranking（NPR）的方法。相對比而言，NCE和NEG是判别模型，NPR是生成模型。
通過化簡，條件機率可以表示為：
P(u|C)=11+∑v≠uexp(S(v,C)−S(u,C))
然而，作者并沒有直接優化上式，而是用一小部分的噪音樣本 X1∖u ，單個的節點可以表示為： vn 。優化的機率是：
P(u>vn|C)=σ(−S(vn,C)+S(u,C))
直覺解釋，給定上下文C，最大化觀測到目标節點u而不是負樣本 vn 的機率。特别是，很容易驗證 P(u|C)>∏vn≠uP(u>vn|C)
得到的節點對排序結果 P(u>vn|C) 與Bayies Pairwise Ranking（BPR）是很相似的。但是，BPR的負樣本來自于從隐士回報，NPR是基于條件機率的soft max定義近似推到出來的，而且負樣本來自于噪音分布。因而，條件機率近似為：
P(u|C)∝Evn∼P(n)logP(u>vn|C)
在實驗中作者采用的是異步梯度下降的方法。為了避免實驗結果陷于局部最優（在計算scoring函數時，每個類型的object做了平均，這就導緻object數量少的類型對應的object權重大，反之則權重小），作者根據節點類型調整步長： βt=αtη ， αt=|Xt|maxTt′=1{|Xt′|} 是梯度系數。實驗結果證明HEBE是适用于大規模網絡的，實驗資料中 DBLP有1,938,912篇論文。
參考：
HEBE：Large-scale embedding learning in heterogeneous event data
Embedding learning with events in heterogeneous information networks