Network Embedding

论文地址：M-NMF Introduction Network Embedding的基本需求是保存网络机构和固有属性。而先前的方法主要保存了网络的围观结构（microscopic structure）如一阶相似度和二阶相似度（LINE，SDNE等）， 忽略了网络结构的介观社区结构（mesoscopic community structure）。针对这个问题，本文提出了一种模块化非负矩阵分解模型M-NMF，该模型将网络的社区结构融入network embedding中。利用节点表示和社区结构之间的一致关系（consensus relationship）， 联合优化基于非负矩阵分解的表示学习模型和基于模块化的社区发现模型， 这样就可以在节点表示中同时保存了微观网络结构和介观社区结构。 具体来说，对于微观结构（节点对相似性），本文使用矩阵分解来融合节点的一节相似性和二阶相似性；对于介观社区结构，通过模块度约束项来检测社区。因此，上面的两项可以通过节点的表示和基于辅助社区表示矩阵社区结构之间的一致关系来联合优化。同时，本文给出了乘法更新策略，保证了再推导参数的时候的正确性和收敛性。 M-NMF Model 对于一个无向图$G=(V,E)$, 图中有$n$个节点和$e$条边，用一个0,1二值邻接矩阵表示为$\mathbf{A}=[A_{i,j}] \in \mathbb{R}^{n \times n}$。 $\mathbf{U} \in \mathbb{R}^{n \times m}$ 为节点的表示矩阵，其中$m \leq n$，$m$是节点的嵌入维度。 建模社区结构 本文采用基于模块最大化的社区发现方法 Modularity， 给定一个邻接矩阵表示的网络$\mathbf{A}$，$\mathbf{A}$包含两个社区，根据Newman 2006b，模块度可以定义如下： $$ Q=\frac{1}{4 e} \sum_{i j}\left(A_{i j}-\frac{k_{i} k_{j}}{2 e}\right) h_{i} h_{j} $$ 其中，$k_i$表示节点$i$的度，如果$i$在第一个社区中，那么$h_i=1$,否则$h_i = -1$。 $k_ik_j$表示将所有边一分为二 参考模块度Q，那么节点$i$,$j$之间可能产生的边数。$\frac{k_{i} k_{j}}{2 e}$如果所有边随机放置，节点$i$,$j$之间的期望边数。定义一个模块度矩阵$\mathbf{B} \in \mathbb{R}^{n \times n}$，其中$B_{i,j}=A_{i,j}-\frac{k_{i} k_{j}}{2 e}$，那么$Q=\frac{1}{4 e} \mathbf{h}^{T} \mathbf{B h}$，其中$\mathbf{h}=[h_i] \in \mathbb{R}^n$，表示社区成员指标器。 如果将$Q$拓展到$k > 2$个社区，那么： $$ Q=\operatorname{tr}\left(\mathbf{H}^{T} \mathbf{B H}\right), \quad \text { s.t. } \quad \operatorname{tr}\left(\mathbf{H}^{T} \mathbf{H}\right)=n $$ 其中$tr()$表示矩阵的迹（主对角线元素和），$\mathbf{H}$是社区成员指标器，$\mathbf{H} \in \mathbb{R}^{n \times k}$，每行表示一个节点所属社区的one-hot编码。 ...

论文地址：BiNE Introduction Bipartite Network(二分网络):如下图所示： 二分网络将节点分为两种类型，其中 边存在于两种类型之间，例如users-items组成的推荐网络，相同类型节点间不会产生边。传统的Network Embedding将bipartite network视为同质网络（homogeneous network)， 也就是仅考虑直接联系的边。这样就存在一个问题，即在同一个类型中的节点，虽然没有直接的连接，但是也可能有间接的关系。比如两个用户同时连接到同一个商品，则这两个用户可能有有相同的购买偏好。 另一个问题， 如上两图所示， 图一可以看出，节点被访问的词数和考虑到的节点数呈现斜率为-1.582的幂律分布，但是基于随机游走的生成器相对于真实分布有所偏差， 文中分析原因在于基于随机游走的模型DeepWalk为每个节点生成相同长度的节点序列（walk_length）并且每个节点所需要的随机游走次数（walk per vertex)也是完全相同的，这样无法反应网络的特征以及异构性。 另外，对于Heterogeneous Network Embedding方法metapath2vec++, 此方法是次优的因为它将直接连接的节点与间接有关系的节点视为等价。 针对以上问题，BiNE为直接连接和间接关系分别设计了专用的目标函数，并且联合优化。 并且，所及游走的长度由该节点的重要程度决定，节点的重要程度通过HITS来衡量。 Model 如figure中的二分网络， 可以这样定义：$G=(U,V,E)$,和一个$|U| \times |V|$的$W=[w_{ij}]$为权重矩阵。输出d维embedding向量$U=[\overrightarrow{u_i}]$, $V=[\overrightarrow{v_i}]$，结构如下图所示： （取自作者的讲解ppt) Explicit Relations 同LINE一样， 基于直接连接的目标函数表示为： $$\mathrm{minimize} \quad O_1=-\sum_{e_{ij} \in E}w_{ij}\log \hat{P}(i,j)$$ Implicit Relations 构造随机游走序列 这是本文的创新点，分别为$U$和$U$构建语料库，即随机游走序列$D^U$和$D^V$。 首先给出两个同type节点相似度的定义： $$w^U_{ij}=\sum_{k \in V}w_{ik}w_{jk}$$ $$w^V_{ij}=\sum_{k \in U}w_{ki}w_{kj}$$ 其中$i$和$j$是为$U$或$V$中的同类节点，也就是说两个同类节点如果有共同目标顶点，那么他们的2介相似度不为0。 则$U$中的二阶权重矩阵$|U|\times|U|$维矩阵$W^U=[w^U_{ij}]$。$V$中同理。 其中$l=\max(H(v_i)\times \max T,\min T)$, $H(v_i)$为节点$v_i$的中心性，中心性由HITS衡量。$l$为节点$v$的random walk次数（the number of random walks）,有这个节点的重要程度（centrality/importance）决定。 $$D_{v_i}=\mathrm{BiasedRandomWalk}(W^R,v_i,p)$$ 表示其中一次随机游走的节点集合$p$表示停止概率。 通过上面的推导，可以对分别对$U$,$V$中的节点构早随机游走序列，以$U$为例，若$S\in D^U$表示 那么$S$就是$U$中的一个随机游走序列。 ...

论文地址：HTNE Introduction 本文出发点在于捕获动态网络中节点和边的变化来在embedding中保持网络结构，举个简单的例子来说，如Fig. 1所示，是一个共同作者网络图。数字标注的节点是author，方框内是co-authored paper. 可以看到图中每个节点每条边加入网络中的时间是不同的。根据图中的信息，可以分析出例如前期1和2，3合作较紧密，后期转为了6,7。 并且(b)中所示，同一条边可能多次出现，这就比传统的单条边拥有更多语义信息。 另外，最近也有方法对动态网络的embedding做了研究，比如[29][30]的方法。但是他们的目的是将时间线分段为固定时间窗来对动态建模，但是这些方法依然没有考虑动态过程也就是网络随时序动态变化的信息。 因此，本文提出了基于霍克斯过程（Hawkes process）的时序网络表示学习方法，该方法是由序列事件驱动的（也就是序列的变化） 如Fig .1(b)所示 (b)图为节点1的邻域生成序列。霍克斯过程的思路是说历史上发生的事情对未来的概率密度函数有影响，只是随着时间流逝这种影响会逐渐减弱（Decay）。本文提出用霍克斯过程来捕获时间序列（也就是邻域生成序列）的激励效应。 尤其是历史事件对当前事件的影响。 通过把成对的向量映射到基本速率和历史影响，从而把低维向量被输入Hawkes过程。 另外历史邻居当前邻居的影响，不同节点是不同的，所以本文使用attention model来学习历史邻居对当前邻居影响的量化表示。 值得注意的是，本文目标是优化邻域生成序列的极大似然估计即条件强度函数（conditional intensity function）来邻域生成序列的到达率，而不是条件概率函数 Model Definition 本文通过跟踪节点邻域的形成来捕获网络的形成过程。 Definition 1 : 时序网络 $G=(V,E,A)$, $A$ 是事件集， 边$(x,y) \in E$ 被表示为按时间顺序的时间序列，例如， $\mathbf{a}_{x,y}={a_1\to{a_2}\to{…}}\subset\mathcal{A}$, $a_i$ 表示时间$t_i$时刻的一个事件。 因此，网络中节点的相邻邻居可以根据与邻居的交互事件的时序被组织为序列，表示邻域形成过程。 Definition 2 : 对于给定节点$x$,邻域表示为$N(x)={y_i|i=1,2…}$.$x$的目标邻居到达事件可以表示为${x:(y_1,t_1)\to(y_2,t_2)\to…\to(y_n,t_n)}$,即邻域形成序列。每个元组表示在时间戳$t_i$时，$x$与$y_i$建立边。 Hawkes Process 点过程（Point Process）通过假设t时刻前的历史事件可以影响当前事件的发生，来对离散序列事件建模。 对于一个给定的节点$x \in V$, 在$x$的邻域生成序列中，到达目标邻居$y$的条件强度函数（或者可以说是$x$与$y$有边的可能性强度）可以表示为： $$ \tilde{\lambda}_{y|x}(t)=\mu_{x,y}+\sum_{t_h<t}{\alpha_{h,y}\kappa(t-t_{h})}$$ 其中，$\mu_{x,y}$表示构建一条连接节点$x$和$y$的基本率(base rate)，$h$是t时刻前的历史目标节点，$\alpha_{h,y}$表示一个$t_h$时刻的历史目标节点$h$（该节点是$x$的邻居）对当前邻居$y$的影响强度。$\sum_{t_h<t}$表示遍历t时刻前$x$的所有邻居。$\kappa(t-t_{h})$表示随时间的衰减，可以表示成指数函数： $$\kappa(t-t_h)=\exp(-\delta_s(t-t_h))$$ 其中，减少率 $\delta$是一个源依赖参数，对于每一个源节点（每个序列的根），历史邻居对当前邻居形成的影响强度是不同的。具体来说，如果$\kappa$越大，说明$t_h$时刻的邻居对当前邻居的影响越大，即 $-\delta_s(t-t_h)$越大, $\delta_s(t-t_h)$越小，因为$t$是当前时刻的邻居，所以当$t_h$越接近当前邻居时刻时，$\kappa$越大，这就说明了里当前时刻之前越近的邻居，对当前时刻邻居的影响越大。 综上所述，$\kappa$的具体意义是随时间衰减的影响，其中$\delta_s$参数表示对于不同的源节点，影响是不同的。 如果$\tilde{\lambda}_{y|x}(t)$ 越大，说明x和y有边的可能性也越大。 直观的来看，基本率（base rate）$\mu_{x,y}$揭示了节点x和节点y之间的连接可能性。为了简洁，本文使用了**负平方欧式距离（negative squared Euclidean）**来反映表示向量间的相似度: $\mu_{x,y}=f(\mathbf{e}_x,\mathbf{e}_y)=-||\mathbf{e}_x-\mathbf{e}_y||^2$。同样的，在计算历史邻居$h$对当前邻居$y$的影响时，也采用这个方法，即： $\alpha_{h,y}=f(\mathbf{e}_h,\mathbf{e}_y)=-||\mathbf{e}_h-\mathbf{e}_y||^2$。 因为条件强度函数必须为正，所以使用如下公式: $\lambda_{y|x}(t)=\exp(\tilde\lambda_{y|x}(t))$。$exp()$对原函数进行了归一化，所以问题就转化为了given $x$, maximize likelihood: $p(y|x)$. 这就与传统的NE方法差不多了。。。 ...

论文地址:GraphGAN Introduction GAN是CV上非常火的方法，作者将其引入Network Embedding领域。为了达到这个目的，首先，作者将当前的NE model分成了两类，分别是生成模型(generative model)和判别模型(discriminative model)。简单来说，生成模型。 所谓生成模型，就是对于每个节点$v_c$，都存在一个潜在的真实连接分布$p_{true}(v|v_c)$, 这个分布反映了由条件生成样本的概率，因此，生成式模型的目的就是求网络中边的极大似然。比较经典的方法有DeepWalk，是通过随机游走来获得center node的上下文，然后最大化上下文节点的似然。Node2vec拓展了DeepWalk,提出了biased随机游走，使得模型在为给定节点生成上下文节点时具有更多的灵活性。 所谓判别模型，目的是学习一个分类器来直接预测边是否存在。将两个节点视为输入特征，然后输出预测的两个节点之间有边的概率，即$p(edge|(v_i,v_j))$,常见的方法有SDNE，PPNE。 于是，本文结合生成对抗网络(GAN),提出了GraphGAN来同一生成和判别器。其中生成器$G(v|v_c)$试图拟合真实的连接概率分布$p_{true}(v|v_c)$,生成最可能和$v_c$有链接的点。判别器$D(v,v_c)$尝试区分强连接节点对和若连接节点对，然后计算$v$和$v_c$存在边的可能性。简单来说，就是把生成器生成的可能与$v_c$有边的节点放入判别器计算两者有边的概率。 除此之外GAN框架下，然而生成器的连接分布是通过softmax实现的，但是传统的softmax无法适配生成器，原因如下: (1).传统的softmax对网络中的所有节点一视同仁，缺乏对网络结构相似度信息的考虑。 (2).计算成本太高。 因此，论文中提出了新的生成器实现方法 Graph Softmax。并且证明GS具有归一化（normalization）、网络结构感知（graph structure awareness）和高计算效率（computational efficiency）的性质。相应的，文中也提出了基于随机游走(random walk)的生成器策略。 Model 这里挑特别的来说。$\mathcal{N}(v_c)$表示和$v_c$直接相连的节点集。我们把给定节点$v_c$与任意节点$v \in \mathcal{V}$的真实连接分布表示为$p_{true}(v|v_c)$。这么看$\mathcal{N}(v_c)$可以看做从$p_{true}(v|v_c)$中采样的集合。文章的目的是学习两个模型: Generator $G(v|v_c;\theta_G)$ 生成器，尝试拟合真实连接分布$p_{true}(v|v_c)$，并且从节点集$\mathcal{V}$中生成最有可能和$v_c$相连的节点。 Discriminator $D(v,v_c;\theta_G)$ 判别器，目的是判断已对接点$(v,v_c)$的连接性。$D(v,v_c;\theta_G)$输出$v$和$v_c$有边的概率。 生成器$G$尝试完美拟合$p_{true}(v|v_c)$，并且生成和$v_c$真实邻居高度相似的节点来欺骗判别器。相反，判别器尝试发现输入的顶点是真实的节点对或者有生成器生成出的样本。这是一个极大极小游戏，目标函数$V(G,D)$: $$\min_{\theta_G} \max_{\theta_D} V(G,D)=\sum_{c=1}^V (\mathbb{E}_{v \sim p_{true}(\cdot|v_c)}[\log D(v,v_c;\theta_D)]+\mathbb{E}_{v \sim G(\cdot|v_c;\theta_G)}[\log(1-D(v,v_c;\theta_D))])$$ 上面这个公式是本文最关键的公式，以我的分析就是：在给定$\theta_D$的情况下，对其最小化。先来分析$\max_{\theta_D}V(G,D)$,即给定$\theta_G$,使原式最大。当给定$\theta_G$时，通过改变$\theta_D$,使$\mathbb{E}_{v \sim p_{true}(\cdot|v_c)}[\log D(v,v_c;\theta_D)]$达到最大（是判别器D拟合真实分布），同时使$\mathbb{E}_{v \sim G(\cdot|v_c;\theta_G)}[\log(1-D(v,v_c;\theta_D))]$最大，即尽可能减小选定节点$v_c$与判别器中生成的$v_c$邻居节点与$v_c$连接的可能性。然后在给定$\theta_D$的情况下，通过改变生成器$\theta_G$继续生成节点，使得$\mathbb{E}_{v \sim G(\cdot|v_c;\theta_G)}[\log(1-D(v,v_c;\theta_D))]$尽可能小，即上一步的判别器尽可能把当前生成器生成的节点认为是邻居。 之后再更新判别器,以此类推。这样$G$和$D$各自提高性能，最终$G$生成的分布和真实连接分布无法区分，这样达到最好的效果。整体过程如下图所示: Discriminator Optimization 对于判别器来说是个简单的sigmoid函数，来计算两个输入节点的表示向量: $$D(v,v_c;\theta_D)=\frac{1}{1+\exp(-d^\top_v d_{v_c})}$$ 其中，$d_v$,$d_{v_c}$是两个输入节点关于判别器$D$的表示向量，$\theta_D$是所有节点表示向量的结合。注意到上面的公式只涉及$v$和$v_c$, 我们只需要更新$d_v$,$d_{v_c}$，通过梯度下降的方法可以实现： Generator Optimization 对于生成器来说，目标是最小化判别器将生成的样本判断为负样本的对数似然（概率）。换句话说，生成器会调整自己的连接分布（通过调整生成的所有节点的向量表示$\theta_G$）来提升对生成样本的判别分数。由于$v$的采样时离散的，所以使用policy gradient来计算$V(G,D)$关于$\theta_G$的梯度： 为了理解上述公式，注意到$\nabla_{\theta_G}V(G,D)$是一个由$\log(1-D(v,v_c;\theta_D))$加权的梯度$\nabla_{\theta_G}\log G(v|v_c;\theta_G)$的求和，直观上说，这意味着有高概率是负样本的节点会将生成器G“拉着”远离自己（因为我们在$\theta_G$上执行梯度下降)。 Graph Softmax graph softmax的核心思想是定义一种新的计算连接性概率的方式，满足以下性质: ...

论文地址: Enhanced Network Embeddings via Exploiting Edge Labels Introduction 这是DeepWalk团队的一篇论文，目的是捕获网络中的边信息。传统的NE方法通常把节点简单关系当做（0,1）二值，然而边中所包含的丰富的语义信息。本文尝试做Network Embedding的同时保留网络结构和节点关系信息。举个例子来说，真实社交网络中，一个用户可能和他的同事，家人有关系，但是已有的NE方法不能同事捕获好友关系（有边连接），以及边的类型。 具体来说，本分的方法分为无监督部分和监督部分。其中无监督部分预测节点邻域， 监督部分预测边标签。所以本文模型是个半监督NE模型。 Problem Definition 假定Network Graph $G=(V,E)$是无向图。$L=(l_1,l_2,…,l_{|V|})$是边的类型集。一个含有边类型的Graph可以被重新定义为$G=(V,E_L,E_U,Y_L)$,其中$E_L$是由label的边集，$E_U$是没有label的边集，$E_L \cup E_U =E$。$Y_L$表示$E_L$中边的关系类型集合。论文中假定一条边可以有多重关系，所以对于边$E_i$的label集$Y_L(i) \in Y_L$, $Y_L(i)$可能包含很多类型 所以$Y_L(i) \subseteq L$。目的还是一样，学习一个映射函数$\Phi \to \mathbb{R}^{|V| \times d}$, 其中$d \ll |V|$。 Method 首先定义损失函数: $$\mathcal{L}=(1-\lambda)\mathcal{L}_s+\lambda\mathcal{L}_r$$ 其中$\mathcal{L}_s$表示预测节点邻域的损失。$\mathcal{L}_r$表示预测边label的损失。$\lambda$是两种损失的权重。 Structural Loss 第一部分是最小化无监督网络结构损失，对于一个给定的节点$v$, 要最大化这个节点和它邻域可能性。其中，节点的邻域不一定要一定和该节点有边相连。文章先给出了结构损失的目标函数： $$\mathcal{L}_s=-\sum_{u \in C(v)} \log Pr(u|v)$$ 这个函数其实就是给定$v$,最大化$v$的邻域的极大似然。其中$Pr(u|v)$是一个softmax函数： $$Pr(u|v)=\frac{\exp(\Phi(u) \cdot \Phi’(v))}{\sum_{u’ \in V} \exp(\Phi(u’) \cdot \Phi’(v))}$$ 这其实和DeepWalk一样，一个节点$v$有两个表示向量，$\Phi(v)$和$\Phi’(v)$分别表示该节点作为中心节点和上下文节点的表示。由于计算复杂度较高，所以采用负采样的策略。 剩下的问题就是如何构建节点$v$的邻域$C(v)$。一种直接的方式就是从邻接矩阵中选取他的邻居。然后由于现实网络的稀疏性，一个节点只有很少的邻居。为了缓解网络稀疏性的问题， 本文采取了类似于DeepWalk的randomwalk策略。 最终可以得到节点$v$的邻域： $$C(v)={v_{i-w},…,v_{i-1}} \cup {v_{i+1},…,v_{i+w}}$$ Relational Loss 由于label是为了预测边的，所以需要把每条边表示出来，所以对于边$e=(u,v) \in E$,可以用一下方法来表示这条边: $$\Phi(e)=g(\Phi(u),\Phi(v))$$ 其中，$g$是一个映射函数用来把两个节点的表示向量转化为他们之间边的表示向量，本文使用了简单的连接操作，即把两个向量直接拼接： $$\Phi(e)=\Phi(u) \oplus \Phi(v)$$ 这样我们就获得了edge embedding。直接将它输入前馈神经网络，前馈神经网络第$k$层的定义为: $$h^{(k)}=f(W^{(k)}h^{(k-1)}+b^{(k)})$$ 其中 $h^{(0)}=\Phi(e)$，$f$是除最后一层外采用relu激活函数，最后一层采用sigmoid函数激活,最后一层输出为$\hat{y_i}$。最后最小化二元交叉熵损失函数： ...

论文地址：SDNE Introduction 这是一篇比较早的Network Embedding论文， 较早将深度模型应用到NE任务。 首先，本文提出了当前网络表示学习中遇到的三个问题： （1）. 高度非线性 （2）. 尽可能保持网络结构 （3）. 现实网络的高度稀疏性 SDNE的主要目标就是保持网络结构的一阶相似性和二阶相似性。 一阶相似性就是网络中边相连的节点对之间具有的相似性。 二阶相似性就是在一个Graph中，拥有共同邻居但是不直接向相连的两个节点具有的相似性。 其中，一阶相似性主要反映了网络的局部特征。 二阶相似性反映了网络的全局特征。 Model 本文的模型主要如下图所示： 这张图看上去有点复杂，实则原理非常简单。 模型分为无监督部分和有监督部分，无监督部分是一个深度自编码器 用来捕获二阶相似度（保留全局结构），监督部分是一个拉普拉斯特征映射捕获一阶相似度（局部结构）。呃呃呃，Emmmmm ,不知道是我理解有问题还是其他原因，文章里说的和我理解的不太一样 /(ㄒoㄒ)/~~。 然后介绍一下具体的模型结构： 深度自编码器的编码部分： $$y_i^{(k)}=\sigma{(W^{(k)}y_i^{(k-1)}+b^{(k)})}, k=2,…,K$$ 假设第$k$层是 节点$v$的表示向量（仅考虑全局信息），那么从第$k$层开始解码，最终得到$\hat{x_i}$, 所以自编码器的误差就是输入节点$v$的邻接向量的重构误差。所以，二阶相似度损失函数定义为: $$\mathcal{L}=\sum_{i=1}^n{||\hat{x_i}-x_i||^2_2}$$ 值得注意的是，由于网络的稀疏性，邻接矩阵中的0元素远多于非0元素，使用邻接矩阵作为输入的话要处理很多0，这样就做了太多无用功了。为了解决这个问题，对损失函数做了改进如下： $$\mathcal{L_{2nd}}=\sum_{i=1}^n||(\hat{x_i}-x_i)\odot{b_i}||^2_2=||\hat{X}-X\odot{B}||^2_F$$ 其中$\odot$是哈马达乘积，表示对应元素相乘。$b_i={b_{i,j}}^n_{j=1}$， 邻接矩阵中的0对应$b=1$, 非0元素的$b>1$,这样的目的是对于有边连接的节点增加惩罚。可以理解为对有边连接的节点赋予更高权重。 以上我们获得了二阶相似度的损失函数。在介绍一阶相似度之前，我们先来看看拉普拉斯映射（Laplacian Eigenmap） 其实LE也是一种经典的NRL方法，主要目的也是降维。其目标函数如下所示: $$\sum_{i,j} W_{ij}||y_i-y_j||^2$$ LE是通过构建相似关系图来重构局部特征结构,如果放在网络结构中来说,如果节点$v_i$和$v_j$很接近（有边），那么他们在embedding space中的距离也应该相应接近。$y_i$和$y_j$就表示他们在特征空间中的表示。因此，本文定义了保持一阶相似度的目标函数： $$\mathcal{L_{1st}}=\sum_{i,j=1}^n{s_{i,j}||y_i^{(K)}-y_j^{(K)}||^2_2}=\sum_{i.j=1}^n{s_{i,j}||y_i-y_j||^2_2}$$ 具体来说，$K$就是自编码器第$K$层的输出，即编码结果，需要保持一条边的两个节点在嵌入空间中的表示相对接近。 最终 结合一阶相似度和二阶相似度，本文给出了SDNE的目标函数： $$\mathcal{L_{mix}}=\mathcal{L_{2nd}+\alpha{\mathcal{L_{1st}}}}+\nu{\mathcal{L_{reg}}} =||(\hat{X}-X)\odot{B}||^2_F+\alpha{\sum_{i.j=1}^n{s_{i,j}||y_i-y_j||^2_2}}+\nu{\mathcal{L_{reg}}}$$ 其中，为了防止过拟合，添加了$\mathcal L2$-norm单元$\mathcal{L_{reg}}$来防止过拟合: $$\mathcal{L_{reg}}=\frac{1}{2}\sum_{k=1}^k({||W^{(k)}||^2_F+||\hat{W}^{k}||_F^2})$$ Optimization 使用SGD来优化$\mathcal{L_{mix}}$。具体算法如下：

论文地址： metapath2vec Introduction 真实网络中通常包含多种类型的节点和关系，这些节点和关系共同组成了异质信息网络（Heterogeneous Information Network），传统的NE方法如DeepWalk, Line , node2vec更多关注与同质网络从而忽略了网络的异质性。针对这个问题，这篇文章提出了metapath2vec基于meta-path的随机游走来构建节点的异质邻域，采用异质Skip-gram模型来学习节点的representation。 另外，在负采样时也考虑异质性，从而进一步提出了metapath2vec++。如下： Definition Definition 1: 异质网络： $G = (V,E,T)$，其中每个节点和边分别对应一个映射 $\phi(v) : V \rightarrow T_{V}$ 和$\varphi(e) : E \rightarrow T_{E}$。 其中$T_V$和$T_E$分别表示节点的类型集合以及关系的类型集合。且$\left|T_{V}\right|+\left|T_{E}\right|>2$。 Definition 2: 异质网络表示学习 为网络中的节点学习一个$d$维的表示 $\mathrm{X} \in \mathbb{R}^{|V| \times d}$，$d \ll|V|$。节点的向量表示可以捕获节点间结构和语义关系。 Model metapath2vec Skip-Gram模型是给定一个节点，预测向下文节点的概率。metapath2vec的目的是考虑多种类型节点和多种类型关系的情况下，最大化网络概率。为了将异质信息融入skip-gram模型中，首先提出异质skip-gram。 Heterogeneous Skip-Gram 对于节点类型$|T_V| > 1$的网络$G$， 给定一个节点$v$，需要最大化属于类型$t \in T_V$的异质上下文节点的概率： $$ \arg \max_{\theta} \sum_{v \in V} \sum_{t \in T_{V}} \sum_{c_{t} \in N_{t}(v)} \log p\left(c_{t} | v ; \theta\right) $$ 其中，$N_t(v)$表示$v$属于第$t$个类型的邻居节点。 $p\left(c_{t} | v ; \theta\right)$ 表示给定节点$v$，它的$t$类型邻域概率： $p\left(c_{t} | v ; \theta\right)=\frac{e^{X_{c_{t}} \cdot X_{v}}}{\sum_{u \in V} e^{X_{u} \cdot X_{v}}}$，是一个softmax函数，$X_v$是节点$v$的表示。由于softmax函数的分母每一次都要遍历所有节点，所以采用负采样改进$\log p(\cdot)$ 如下： $$ \log \sigma\left(X_{c_{t}} \cdot X_{v}\right)+\sum_{m=1}^{M} \mathbb{E}_{u^{m} \sim P(u)}\left[\log \sigma\left(-X_{u^{m}} \cdot X_{v}\right)\right] $$ 其中 $\sigma(x)=\frac{1}{1+e^{-x}}$。 ...

paper Introduction 在现实世界的社交网络中，一个顶点在与不同的邻居顶点交互时可能表现出不同的方面 (aspect)，这是很直观的。例如，研究人员通常与各种合作伙伴就不同的研究主题进行合作（如下图所示），社交媒体用户与分享不同兴趣的各种朋友联系，一个网页出于不同目的链接到多个其它网页。然而，现有的大多数 NE 方法只为每个顶点安排一个 single embedding 向量，并产生以下两个问题： 这些方法在与不同邻居交互时，无法灵活转换不同的aspect 在这些模型中，一个顶点倾向于迫使它的所有邻居之间的 embedding彼此靠近，但事实上并非一直如此。例如下图中，左侧用户和右侧用户共享较少的共同兴趣，但是由于他们都链接到中间用户，因此被认为彼此接近。因此，这使得顶点 embedding 没有区分性。 为了解决上述问题，本文提出了一个 CANE框架，用于精确建模顶点之间的关系。更具体而言，论文在信息网络上应用 CANE。信息网络的每个顶点还包含丰富的外部信息，例如文本、标签 、或者其它元数据。在这种场景下，上下文的重要性对 network embedding 更为关键。在不失一般性的情况下，论文在基于文本的信息网络中实现了 CANE，但是 CANE可以很容易地扩展到其它类型的信息网络。 在传统的 network embedding模型中，每个顶点都表达为一个静态的 embedding 向量，即 context-free embedding 。相反，CANE 根据与当前顶点交互的不同邻居，从而将动态的 embedding分配给当前顶点，称为 context-aware embedding。以一个顶点$u$为例：当与不同的邻居交互时， 的 context-free embedding保持不变；而当面对不同的邻居时， $u$的 context-aware embedding是动态的。 当顶点$u$与它的邻居顶点$v$交互时，它们彼此相关的 context embedding 分别来自它们的文本信息。对于每个顶点，可以轻松地使用神经模型neural model ，例如卷积神经网络和循环神经网络来构建 context-free embedding 和 text-based embedding 。为了实现 context-aware text-based embedding，论文引入了 selective attention 方案，并在这些神经模型中建立了 和 之间的互注意力 mutual attention 。mutual attention 预期引导神经模型强调那些被相邻顶点 focus 的单词，并最终获得 context-aware embedding。每个顶点的 context-free embedding 和 context-aware embedding 都可以通过使用现有的 network embedding 方法学到（如 DeepWalk，LINE，node2vec）并拼接起来。 ...