论文笔记：图嵌入（非深度）

Question

Graph Factorization

损失函数：最小二乘 + L2 正则化

相似度：邻接矩阵

GraRep

损失函数：最小二乘

相似度：行标准化邻接矩阵 的k次方

HOPE

损失函数：最小二乘

相似度：

• Katz Index
• Rooted Page Rank
• 共同邻居
• Adamic-Adar 得分

LINE

损失函数：sigmoid 交叉熵

一阶不带负采样

二阶带负采样

相似度：

• 标准化邻接矩阵
• 对于非常稀疏的图：
• 对于权重差距过大的图：对每条边采样，概率与权重正相关，变成无权图

BINE

损失函数：sigmoid 交叉熵

一阶不带负采样

二阶带负采样（引入上下文矩阵）

相似度：

• 一阶：标准化邻接矩阵
• 二阶：相当于共现矩阵

Algorithm 1: WalkGenerator(W, R, maxT, minT, p)
-----------------------------------------------
Input: weight matrix of the bipartite network W,
       vertex set R (can be U or V ),
       maximal walks per vertex maxT, 
       minimal walks per vertex minT, 
       walk stopping probability p
Output: a set of vertex sequences D^R
1 Calculate vertices’ centrality: H = CentralityMeasure(W);
2 Calculate W^R w.r.t. Equation (4);
3 foreach vertex vi ∈ R do
4     l = max(H(vi) × maxT, minT);
5     for i = 0 to l do
6         D[v[i]] = BiasedRamdomWalk(W^R, v[i], p);
7         Add D[v[i]] into D^R;
8 return D^R;

node2vec

（随机游走 + word2vec）

损失函数：sigmoid 交叉熵带负采样

相似度：相当于共现矩阵

LearnFeatures(Graph G = (V, E, W), Dimensions d, Walks per node r, Walk length l, Context size k, Return p, In-out q)
π = PreprocessModifiedWeights(G, p, q)
G' = (V, E, π)
Initialize walks to Empty
for iter = 1 to r do
    for all nodes u ∈ V do
        walk = node2vecWalk(G', u, l)
        Append walk to walks
f = StochasticGradientDescent(k, d, walks)
return f

node2vecWalk(Graph G' = (V, E, π), Start node u, Length l)
Inititalize walk to [u]
for walk_iter = 1 to l do
    curr = walk[−1]
    Vcurr = GetNeighbors(curr, G')
    s = AliasSample(Vcurr, π)
    Append s to walk
return walk

DeepWalk

（随机游走 + word2vec）

损失函数：sigmoid 交叉熵带负采样

相似度：相当于共现矩阵

Algorithm 1 DeepWalk(G, w, d, γ, t)
-----------------------------------
Input: graph G(V, E)
    window size w
    embedding size d
    walks per vertex γ
    walk length t
Output: matrix of vertex representations Φ ∈ R^{|V|×d}
1: Initialization: Sample Φ from U[|V|×d]
2: Build a binary Tree T from V
3: for i = 0 to γ do
4:     O = Shuffle(V)
5:     for each vi ∈ O do
6:         W[v[i]] = RandomWalk(G, v[i], t)
7:         SkipGram(Φ, W[v[i]], w)
8:     end for
9: end for

pte

文本异构网络的节点：单词、文档、类别，边：单词-单词、单词-文档、单词-类别。处理为一个同构图，两个二分图。

损失函数：sigmoid 交叉熵带负采样

相似度：共现矩阵或成员关系矩阵

walklet

（随机游走 + word2vec）

损失函数：sigmoid 交叉熵带负采样

相似度：相当于共现矩阵