1.创新点
- 首先这篇文章只通过网络的结构化信息来对齐网络，与以往专注于成对学习和保持拓扑一致假设的方法不同，提出的CrossMNA考虑了至少包含两种类型的多网络场景 具有不同网络结构的网络。
- 提出来三种节点嵌入向量，inter-vector（network alignment，这反映了不同网络中锚节点的共同特征，并在已知的锚节点之间共享），intra-vector（downstream tasks，它保留了所选网络中一个节点的特定结构特征，并通过network vector和intra-vector的组合生成。），network vector（挖掘网络的语义信息）
2. Intro问题的提出
- 首先，大多数现有的工作仅仅考虑两个网络场景或者在多个网络中成对的进行表示学习。但是在真实世界中，一个网络通常是与多个网络关联的。因此，成对的学习方法很可能会忽略一些在多个社交网络中的有价值的信息。
- 其次，许多先前的研究认为网络拓扑一致的，也就是在不同社交网络中同一个用户的节点结构应该是一致的，但是由于不同网络之间的不同语义信息，节点的网络结构很可能是非常不一致的。
- 先前的工作大多严重依赖特征属性，但是特征信息通常是不完整的或者是不可信的，没有价值的，所以基于属性的方法在实际情况下是不可用的。
语义多样性
网络语义的多样性导致了每个网络中同一节点的交互行为的不同，从而影响了节点匹配的准确性。此外，网络越多，问题就越复杂。因此，如何减轻不同的网络语义对节点匹配的影响是一个很大的挑战。
数据不平衡
（1）每个网络的大小可能会有很大的差异，包括每个网络中的节点或边的数量
（2）每对网络之间的锚定链路的数量可能是不相等的。
模型容量
3. 模型CROSSMNA
在本文中所有的网络都被认为是无向边的，且边是没有权重的。
参数定义：
| 参数 | 定义 |
|---|---|
| \(G=((G^1,G^2,...,G^N),(A^{(1,2)},A^{(1,3)},...,A^{(N-1,N)}))\) | 表示一系列对齐的网络 |
| \(G^i\) | 表示在集合中的第i个网络 |
| \(N\) | 相关网络的数目 |
| \(A^{(i,j)},i,j∈{1,2,...,N}\) | 在网络\(G^i\)和\(G^j\)之间的anchor links |
| \(G^i={V^i,E^i}\) | \(V^i\)表示节点集，\(E^i\)表示用户集 |
| \((v_k^i,v_k^j)∈A^{(i,j)}\) | anchor links |
| \(\vec {u}\) | inter-vector |
| \(\vec v\) | intra-vector |
| \(\vec r\) | network vector |
所选网络中的锚节点由于其网络语义意义，既可以表现出与其节点相似的结构特征，也可以表现出独特的连接关系。具有相同语义信息的网络之间的anchor nodes具有结构一致性。
inter-vector \(\vec u\) 保留anchor nodes的共同特征，这个向量是很难学习的，因为在未知的anchor nodes之间没有直接的联系，所以只能通过间接方法计算。
intra-vector \(\vec v\) 直接可以通过网络嵌入的方式来提取节点的结构特征。由于语义，这类向量既包含了对应物之间的向量，也包含了它的所选网络中的特定局部连接，因此，除非我们能够剥离网络语义的影响，否则它不能应用于节点匹配。
network vector \(\vec r\) 提取的是\(G^k\)的特有特征，反映了不同网络之间的全局的不同。
\(v_i^k=u_i+r^k\),因此，我们可以通过训练基于组合的内部向量来间接细化锚节点的间向量。
考虑上面的图中的情况，\(v_1\)是anchor nodes，它能够反映网络之间的共有特性，这就是inter-vector所应该反应的。
所以有下面的公式： \[ \vec {v_1^1}= \vec {u_1}+ \vec {r^1} \\ \vec {v_1^2} = \vec {u_1} + \vec {r^2} \] 一方面，通过联合训练intra-vectors，共享的\(\vec {u_1}\)可以存储两个网络之间的互补信息；另一方面，\(\vec {r^1},\vec {r^2}\)可以反映出两个网络由于\(\vec {u_1}\)中公共信息传递而导致的两个网络之间的全局差异。
考虑\(G^3\)网络中的\(v_4\)，它的intra-vector可以被写为：\(\vec {v_4^3}=\vec {u_4}+\vec {r^3}\)。通过学习\(G^3\)的结构信息，\(v_4^3\)能够包含一些与\(v_1^1\)或者\(v_1^2\)相似的特征，例如\(v_4\)也与\(v_2\)还有\(v_3\)相互关联。\(\vec {r^3}\)能够保留\(G^3\)的特有的语义特征，因此通过剥离\(\vec {r^3}\)的影响，\(\vec {u_4}=\vec {v_4^3}- \vec {r^3}\)，那么这时候\(\vec {u_4}\)和\(\vec {u_1}\)的相似性应该很高，我们就能推测出\(v_4\)和\(v_1\)是同一个用户。
inter-vector和intra-vector是不一样的，在不同的向量空间中。因此，作者提出一个转移矩阵W来对齐他们： \[ \vec {v_i^k}=W \vec {u_i}+\vec {r^k},\vec {u_i}∈U^{d_1},\vec {v_i^k}∈R^{d_2} \] 学习的参数就包括：\(W,\vec {u_i},\vec {r^k}\)
考虑的相关的网络越多，节点的匹配的准确率越高。所以，CROSSMNA需要联合训练所有的相关的网络，总的目标方程为： \[ J=\sum_{k}J^k \] 其中\(J^k\)表示的是每个网络的目标函数，旨在保留在网络\(G^k\)中的每个节点的结构信息。对于在网络\(G^k\)中连接的边\((v_i^k,v_j^k)\)，我们定义条件概率\(v_i^k\)导出\(v_j^k\)的条件概率为：
所以最终的目标函数被定义为：（也就是有边相连接的都得求个和，\(\vec {u_k}\)是对于所有的网络都不变的，\(\vec {r^k}\)是对于每个网络都不一样的）通过联合优化，已知的锚节点将尽可能发挥作用，通过共享的向量u传递结构信息，使该向量包含共同的 锚定节点之间的一致性。通过条件概率公式，每个锚节点的intra-vector可以在不同的网络中保留不同的结构特征，这使得网络向量\(\vec {r^k}\)可以提取出其自身全局结构的特定特征。
对于每个未知的anchor nodes \(\vec {v_i^k}\)，尽管我们不能直接的与其对应的节点进行关联，它的基于组合的intra-vector可以保留一些与其他网络中相似的特征。经过剥离\(\vec {r^k}\)之后，其inter-vector \(\vec {u_i}\)将会与其对应的节点表示成一样的。这样就可以做节点匹配。
为了加速训练的过程，采用负采样的形式来估计目标方程为：
这个公式是用的word2vec中的负采样的思想来实现的，推导如下：
其中\(P(v)αd_v^{3/4}\)，\(d_v\)是节点v的度。所以最终的目标函数表示为：
以往的方法在成对学习方案下，很容易出现数据不平衡的问题，但是作者提出来的CrossMNA能够弥补这个问题，因为联合训练所有网络，并通过共享的节点间向量在已知锚节点之间传输互补信息，这可以缓解数据不平衡问题的影响。
经过训练，为每个节点得到两种类型的嵌入向量：intra-vector反映所选网络中一个节点的结构信息，适用于网络内分析任务，而inter-vector来解释不同网络中锚节点的共性，可以有效地应用于多网络对齐任务。
找到节点对齐的一种简单方法是计算节点间向量之间的所有相似性对，这是非常耗时的。然而，在实践中，我们通常只需要找到每个节点的软对齐通过返回其他网络中最有可能的top-α节点。因此，在[10]之后，我们使用k-d树数据结构，在匹配过程中加速相似度搜索[4]。我们 这里使用余弦相似度来定义向量空间中两个节点的距离。用余弦相似度来计算两个节点的距离。
在训练过程中，inter-vector负责在anchor nodes之间传递结构信息。因此
kd树
根据KNN每次要预测一个点时，都需要计算数据集中每个点到这个点的距离，然后选出距离最近的k个点进行投票，当数据集很大时，这个计算成本很高。为了避免每次都重新计算一遍距离，算法会把距离信息保存在一棵树中。这样在计算之前从树里查询距离信息，尽量避免重新计算，其基本原理是，如果A和B距离很远，B和C距离很远，那么A和C距离也很远。有了这个信息，可以在合适的时候跳过距离远的点。这样优化后算法的复杂度可能降低为\(O(DNlog(N))\)。
kd树是二叉树的一种，是对k维空间的一种分割，不断地用垂直于坐标轴的超平面将k维空间切分，形成k维超距形区域，kd树的每一个节点对应于一个k维超矩形区域。
kd树的构造方式：
- 选取\(x^{(i)}\)为坐标轴，以训练集中的所有数据x坐标的中位数作为切分点，将超矩形区域切割成为两个子区域。将该切分点作为根节点，由根节点生出深度为1的左右节点，左节点对应x坐标小于切分点，右节点对应x坐标大于切分点。
- 对深度为j的节点，选择\(x^{(l)}\)为切分坐标轴，\(l=j(mod \ k)+1\)，以该节点区域中训练数据\(x^{(l)}\)坐标的中位数作为切分点，将区域分为两个子区域，且生成深度为j+1的左右子节点。左节点对应\(x^{(l)}\)坐标小于切分点，右节点对应\(x^{(l)}\)坐标大于切分点。
- 重复2，直到两个子区域没有数据为止。
kd树实现k近邻搜索：（寻找p点的最近的k个点）
根据p的坐标和kd树的节点向下进行搜索（如果树的节点是以\(x^{(l)}\)来切分的，那么如果p的\(x^{(l)}\)）坐标小于c，则走左子节点，否则走右子节点。
到达叶子节点时，将其标记为已访问。如果S中不足k个点，则将该节点加入到S中；如果S不为空且当前节点与p点的距离小于S中最长的距离，则用当前节点替换S中离p最远的点
如果当前节点不是根节点，则执行(a)，否则算法结束
回退到当前节点的父节点，此时的节点为当前节点。将当前节点标记为已访问，执行(b),(c)；如果当前节点已经被访问过，再次执行(a)
如果此时S中不足k个点，则将当前节点加入到S中；如果S中已有k个点，且当前节点与p点的距离小于S中最长距离，则用当前节点替换S中距离最远的点。
计算p点和当前节点切分线的距离。如果该距离大于等于S中距离p最远的距离并且S中已有k个点，执行3；如果该距离小于S中距离最远的距离或S中没有k个点，从当前节点的另一子节点开始执行1；如果当前节点没有另一子节点，执行3。