Graph Embedding Techniques

Edge Reconstruction Based Optimization

• Maximizing Edge Reconstruction Probability
• Minimizing Distance-Based Loss
• Minimizing Margin-Based Ranking Loss

Maximizing Edge Reconstruction Probability

意思是好的 embedding 方法是可以在 input graph 中重建出原本的 edge（？）

First-order Proximity

• ---> 跟 之間的 first-order proximity，可以藉由 joint probability 計算出來
• 用微觀一點的角度來看，就是要最大化任兩點連接的機率
  • 

objective function

但因為最佳化的目標是所有節點，所以要把它們都加總起來

Second-order Proximity

有 first-order proximity，當然也有 second-order proximity

• 任兩節點的 second-order proximity，可以藉由當 在 start node 的情況下， 為 end node 的機率來計算（conditional probability）
  • 

objective function

其中 所代表的是在 graph 隨機抽樣出來的路徑集合，並不是所有的路徑都會被考慮進去

Minimizing Distance-Based Loss

First-order Proximity

node proximity 有兩種方法可以計算出，一種是使用 first-order proximity，另一藉由觀察邊計算出 empirical probability。

• node embedding 的方式可以使用 first-order proximity 的公式來計算
  • 
• empirical probability 可以藉由觀察邊來計算
  • 
  • 是 edge 的權重

objective function

裡面提到使用 KL divergence 當作距離函數來計算 和 之間的差異，並且省略當中的常數項。
但我找到的 KL divergence 的公式都跟上面的不太像。但是在這篇文章中有到稍微類似的公式...

Second-order Proximity

node proximity 的計算方式

• second-order proximity 可以就由計算當 出現的情況下， 出現的條件機率
  • 
• empirical probability
  • 
  • 指的是 out degree

objective function