abstract
现有的网络对齐的方法可以分为两类：(1) 基于一致性优化的方法，通常明确地假设对齐在跨网络的邻域拓扑和属性方面是一致的；(2) 基于网络嵌入的方法，学习低维节点嵌入向量来推断对齐。本文中，通过分析两种方法中具有代表性的方法，我们证明了：（1）基于一致性优化的方法本质上是来自锚定链接的特定随机游走传播，可能限制太大；（2）基于嵌入的方法不再明确地假设对齐一致性，而是不可避免地存在空间视差问题。为了克服这两个限制，我们将这些方法连接起来，并提出了一个新的网络对齐算法家族，BRIGHT处理普通网络和属性网络。具体来说，它通过构造一个带重启(RWR)的随机游走空间，其基是锚节点的一个热编码向量，然后是一个共享的线性层。
许多现有的网络对齐方法往往是基于对齐一致性原则，并作为一个优化问题来表述。这些方法的一个基本假设是，要对齐的节点的邻域拓扑和/或属性在不同网络中是一致的。传统上，网络对齐可以被描述为一个图的对齐问题，它将一个网络视为另一个网络的有噪声的排列。这类方法的目标函数是最小化\(\left\|\mathbf{A}_{1}-\mathbf{P A}_{2} \mathbf{P}^{T}\right\|_{F}^{2}\)，其中\(A_1\)和\(A_2\)是两个网络的邻接矩阵，P是节点的置换矩阵。然而由于网络的异质性，一致性假设可能会被违反。
谷歌学者网络中的边缘可以描述共同作者关系，这引入了这两个网络之间的另一种类型的异质性（即关系的不同语义）。
基于网络嵌入的方法旨在学习按序的节点嵌入向量来推测节点对齐，嵌入方法可以被总结为：(1) 通过节点的嵌入来保存每个网络的拓扑信息；(2) 使得anchor nodes的嵌入尽可能的接近。然而网络嵌入方法不可避免地会引入嵌入空间的不同问题。
本文作者首先分析了一些具有代表性的两种类的方法，包含（1）基于一致性优化的方法，（2）网络嵌入方法。具体地说，我们展示了基于拓扑/属性一致性假设的基于一致性优化的方法可以认为是在不同的网络中同时从锚定节点进行随机游走。然而，在两个网络中具有完全相同步数的随机游动传播可能会导致限制性太大，无法捕获它们之间的结构不一致性/差异（限制性传播限制）。另一方面，通过分解基于嵌入的方法的典型目标函数，我们揭示了他们的损失函数本质上是基于一致性优化方法的目标函数的上界。这个上界引入的误差可以累积，最终导致空间视差问题。
为了解决上述问题，我们提出了一种新的网络对齐算法家族BRIGHT，包含BRIGHT-U针对普通网络，以及BRIGHT-A针对属性网络。其关键思想是利用训练锚链作为基础/地标，通过重启随机行走构建一定的统一空间（RWR）。关于锚定节点的RWR分数被用作相应维度上的初始节点嵌入的值。然后，我们使用一个共享的线性层来学习RWR分数在不同维度上的重要性。这样，所提出的方法就具有处理限制性传播限制的灵活性和解决空间视差问题的能力。对于特征网络，我们进一步利用一个GCN网络来充分利用属性信息。
本文的主要贡献：
（1）定理分析。据我们所知，我们是第一个揭示了基于一致性优化的方法和基于嵌入的方法的一些基本局限性，并旨在连接它们。
（2）新模型。
（3）实验结果。我们在不同的场景下对5个数据集进行了广泛的实验，证明了所提模型的有效性。
问题定义
本文参数如下：
问题1：半监督的有属性的网络对齐。
给定两个特征网络\(G_1=\left\{A_1,X_1\right\}\)以及\(G_2=\left\{A_2,X_2\right\}\)，以及一个anchor node对的集合L。
输出：一个\(n_2 \times n_1\)对齐矩阵S，其中\(S(x,a)\)表示在网络G1中的节点a以及在网络G2中的节点x的对齐度。
备注。如果我们没有X1和X2，这将成为半监督的纯网络对齐问题。如果我们没有L，这将成为无监督的属性网络对齐问题 .
分析
1. 基于一致性优化的方法
对于基于一致性约束优化的方法，锚定节点连接集合L是否以先验对齐矩阵H的形式进行编码，其中锚定节点对应的连接是1否则是0.对于一般的网络对齐任务，拓扑一致性是一个基本的假设，假设a和b是\(G_1\)网络中的邻居，x和y是\(G_2\)网络中的邻居。如果a和x对齐，那么b与y有很大的可能性是对齐的。进一步，最终的对齐矩阵S应该与最初的对齐矩阵一致。基于一致性优化的方法[23,34]的目标函数可以表述为：
其中\(d_2(x),d_1(a),d_2(y),d_1(b)\)分别是节点x，a，y，b的度，α是参数。该目标方程有一个近似的解：
其中\(s,h\)是向量化的S和H，\(W=A_1⊙A_2\)是Kronecker product。它等同于下列的等式：
考虑任意一个节点对\((b,y)\)，其中b是\(G_1\)中的一个节点，y是\(G_2\)中的一个节点。假设\((b,y)\)对应于s中的第i项，我们可以打破每个锚定链路的先前对齐向量h：
如果\(h(j)=0\)，求和中对应项的值为0，这将会被忽略。如果\(h(j)=0\)那么\(\alpha^{t} \hat{\mathbf{W}}^{t}(i, j)\)来分析。因为\(\hat{\mathbf{W}}=\mathrm{D}_{\mathrm{W}}^{-\frac{1}{2}} \mathrm{WD}_{\mathrm{W}}^{-\frac{1}{2}}\)并且\(\mathbf{W}=\mathbf{A}_{1} \otimes \mathbf{A}_{2}\)，\(\hat{\mathbf{W}}^{t}(i, j) \mathbb{1}(\mathbf{h}(j))\)表示由h(j)=1表示的锚定链路精确地移动t步，它将到达节点对(b，y)，它用s(i)表示。因此，节点对(b，y)将从锚定链路h(j)=1中获得一个分数s(i)，其衰减速率为α。最后，来自所有锚定链接的分数将被加在一起。
从以上分析中我们知道，基于一致性优化的方法是锚定链路的随机游动传播，如图3所示。归属网络对齐任务的方法依赖于 在选择下一步的方向时，利用节点/边属性的一致性，对不可行的选择进行修剪，这是普通方法的一个广义版本。从等式开始（4），我们可以看到：
该方程要求，仅当一个锚定链路的两个锚定节点（例如，h(i）)以完全相同的步长\(\hat{\mathbf{W}}^{t}(i, j) \mathbb{1}(\mathbf{h}(j))\)到达给定的节点对(b、y）时，给定的节点对（b、y）可以收到一个分数。即使是一个小的扰动（例如，删除一个节点/边）也可以使节点对（b，y）从这个锚定链接获得一个零分数。
所有锚链接的分数权重等量设置为1，并简单地加在一起。如果某个锚定链路对对齐任务有负面影响，那么这些方法就无法剔除这样的锚链路。
2. 基于embedding的方法
对于基于embedding的方法，我们证明他们可以被看做是一致性优化方法的一种简化与方程(1)。具体来说，我们证明了一致性约束优化方法直接地优化了网络之间的节点相似性。相比之下，基于embedding的方法将其放松为对于节点对\(\left\{(y,x),(x,a),(a,b)\right\}\)。为了分析空间视差问题，我们从分析基于嵌入的方法的损失函数开始。这些方法的损失函数一般可以写成如下：
其中\(O_1^{in},O_2^{in}\)分别是网络\(G_1,G_2\)内部的损失函数，\(O^{cross}\)是网络之间的损失函数。考虑每个阳性样本都有一个阴性样本，\(O_1^{in}\)可以被重写为：
其中\(d(.,.)\)是在嵌入空间中的两个节点的距离或不相似度函数，这可以是欧氏距离或者负余弦相似度。\((a,b)\)表示一个正的节点对，在他们之间有一条边或者在一个固定长度的随机游走中进行采样。\((a,c)\)是负采样节点样本。\(O^{cross}\)可以被重写为：
其中l1和l2是对应的训练的anchor node对。
为了更好的阐述我们的分析，我们简单对齐设置为以下场景：(1) G1和G2是同构的k正则图(正则图的意思就是每个节点的度是k)；(2) \(d(.,.)\)是距离矩阵；(3) 矩阵S被\(e^{-d(.,.)}\)计算；(4) positive node pairs (a,b)以及(x,y)之间有边相连接。
由于基于一致性优化的方法是锚链路的随机游走传播，因此我们也从锚链路进行分析。令\((a,x)\)是\(G_1\)和\(G_2\)之间的边，\((a,b)\)是G1内的边，(x,y)是G2内的边。然后，对应的等式(1)中的条目\((a,x)\)来最小化目标方程为：
其中K是K正则图中的度。在理想情况下，\(d(y,b)\)是一个平凡解。考虑到基于嵌入的方法的损失函数，\(O_1\)最小化d(a,b)，O2优化d(x,y)。此处我们暂时舍弃负采样样本d(a,c)，后面会加上。\(O^{cross}\)实际上最小化了d(a,x)，所以，在损失函数O中的条目(a,b,x,y)就会变为：
这是优化了d(b，y)的上界，因为
正如我们所看到的，基于嵌入的方法对节点对(b、y)的d(b、a)、d(a、x)、d、x、y)进行了优化。然而，等式（8）直接优化了d(b，y)。假设(a,b)和(x,y)是在G1和G2中的不完全等价节点，d(b,a)>0,d(x,y)>0，在理想状态下，当基于嵌入的方法收敛时，d(x,a)=0存在一个非常小的正数ϵ，它满足以下条件\(ε<min\left\{d(b,a),d(x,y)\right\}\)。在这种情况下，有一个任意的\(δ∈[0,2ε]\)，d(b,y)会收敛到δ。这意味着即使损失函数在理想情况下收敛，d(b，y)也不一定是0，这意味着即使损失函数在理想情况下收敛，d(b，y)也不一定是0。现在，让我们考虑负抽样项d(a，c)。这一项旨在使未链接到a的其他节点的嵌入远离节点a的嵌入，从而导致即使d(y，b)≠0，也小到足以区分右n的情况 ode对（如图4中的(b，y)）来自错误的对（如图4中的(y，c1)。然而，小的δ误差会随着来自锚链接的随机游动的长度而累积(例如，图4中不正确对齐的对(z2，c1))，特别是当锚链接在t中是稀疏的时候 这导致了一个严重的空间差距问题。如果(a，b)以固定长度的随机游动抽样，而不是直接连接，误差会变得更大。在证明了基于嵌入的方法本质上是基于一致性优化的方法的宽松版本之后，我们提出了一个关于空间视差问题的命题：
proposition 1：一种基于嵌入的网络对齐方法必须满足以下必要而非充分条件。给定两个同构图G1和G2以及它们之间的一些锚定链接L，对于G1和G2之间应该对齐的任何节点对(a，x)，a和x与模型的输出中的d(a，x)=0有相同的嵌入。
命题1的正确性很简单。网络对齐的目标是使应该对齐的节点对之间的距离等于0。换句话说，从锚点l开始 在训练过程中，当前基于嵌入的方法中不允许任何d(a，x)的小δ。然而，这并不是证明网络对齐的正确性的充分条件 存在具有无意义节点嵌入的ial解（例如，所有节点都为0）。这样，网络对齐模型就需要能够学习具有信息性的节点嵌入。
方法
overview
为了同时解决限制性传播限制和空间差异问题，提出的BRIGHT模型努力满足以下要求：
要求1：它应该解除在两个网络中具有完全相同的随机游动步骤的限制，并调整组合锚定链路的权重的方法。
要求2：应建立一个统一的嵌入空间，以满足命题1中的条件。
BRIGHT架构如上图所示，BRIGHT的关键思想是将锚定链接作为对齐任务中的地标。相应地，这些锚链的单热向量形成了一些空间的基，捕捉经过了RWR后的接近。原始嵌入的每一维度被RWR分数计算，这与anchor links相关而不是本地邻居结构相关。初始嵌入表示整个网络中所有节点的相对位置。在共享模块之后，所提出的方法满足提案1中的条件，我们将在第4.2小节中展示。对于要求1，RWR中的重启过程通过在两个网络中进行单独的RWRs来缓解了精确的t步长限制，而在亮-u中共享的线性层可以重新调整分数的权值 m个不同的锚定链接以进行组合。
BRIGHT-U
对于普通网络对齐，只给出了A1、A2和锚定链路集L。首先，我们的目标是避免限制性的传播限制。同时，我们希望为两个网络建立一个统一的嵌入空间，以解决空间视差问题。关键的直觉是，锚定链路L的集合为两个网络中的所有节点提供了地标。基于锚定链路的相对位置可以为所有节点形成一个统一的空间，无论它们属于哪个网络。根据第3节的分析，以往基于一致性优化的方法是以完全相同的步骤从锚链中随机游走。因此，我们使用重新启动的随机游走来测量节点和锚定链接之间的相对位置。两个网络中单独的rwr有助于避免相同的步长限制，为随机游走过程带来更大的灵活性，比最短路径等其他距离测量更鲁棒 距离给定一个anchor link l∈L（我们使用l1和l2来表示在G1和G2中的相同的l），RWR分数向量\(r_{l_1}\)是\(n_1 \times 1\)可以被计算为：
其中\(W_1 = (D^{-1}A_1)^T\)是\(A_1\)的行归一化矩阵，β是重启概率，\(e_{l_1}\)是独热向量其中\(e_{l_1}(l_1)=1\),所有其他条目均为0。最终的\(r_{l_1}\)可以被解决为：
这里我们给出一个直观的解释为什么这个过程满足命题1的条件。给定两个同构图\(G_1,G_2\)以及\((a,x)\)作为一个ground-truth对齐节点对，节点a与锚定链路l1的相对位置是\(r_{l_2}(x)\)。在等式12中，条目\(\left(\mathbf{I}-(1-\beta) \hat{\mathbf{W}}_{1}\right)^{-1}\)和公式(2)中的\((\mathbf{I}-\alpha \hat{\mathbf{W}})^{-1}\)它表示从锚点链接到节点的所有规范化路径。因为（a，x）是两个同构图中的一个ground truth对齐的节点对，而（l1，l2）是锚链接（也是一个ground truth对齐的节点对）。从l1到a的路径和从l2到x的路径都一样。结果，\(r_{l_1}(a)=r_{l_2}(x)\)，它满足命题1中的条件。在得到G1和G2的所有RWR向量后，我们构建了两个大小为n1|的×|L|和大小为n2×|L|的R2。随后，我们归一化R1和R2与每一行相关为\(\hat{\mathbf{W}}_{\mathbf{R}_{1}} \in \mathbb{R}^{n_{1} \times|\mathcal{L}|}\)和\(\hat{\mathbf{W}}_{\mathbf{R}_{2}} \in \mathbb{R}^{n_{2} \times|\mathcal{L}|}\)其在每个位置的值表示节点与锚链路的相对位置。
为了解决在基于一致性优化的方法中，简单地添加来自不同锚点链接的分数和同等权重的局限性，BRIGHT-U使用一个共享的线性层来保持调整来自不同锚定链接的得分权重，在训练过程中保持G1和G2的节点嵌入在相同的嵌入空间中：
\(\mathbf{E}_{1}=\mathbf{E}_{1}^{R W R}=\operatorname{LINEAR}\left(\hat{\mathbf{W}}_{\mathbf{R}_{1}}\right)\)
其中\(\mathrm{E}_{1}^{R W R} \in \mathbb{R}^{n_{1} \times k}\)表示G1最终的嵌入矩阵，k是一个固定的维度。通过利用RWR和一个共享的线性层，BRIGHT-U成功的利用统一空间中两个网络的节点嵌入，放松限制性的传播限制。
3. BRIGHT-A
对于属性网络对齐任务，如图5所示，我们添加了一个共享的两层图卷积网络(GCN)模块来捕获属性信息。GCN嵌入矩阵\(X_1^2\)，\(X_1^2\)会与\(E_1^{RWR}\),\(E_2^{RWR}\)结合，并通过一个共享的线性组合层，得到最终的嵌入矩阵E1和E2。G1的第一层和第二层为：
其中，\(\hat{\mathrm{A}}_{1}=\mathrm{D}_{1}^{-\frac{1}{2}} \mathrm{~A}_{1} \mathrm{D}_{1}^{-\frac{1}{2}}\)，σ是激活函数，W1和W2是GCN的第一层和第二层的参数矩阵。随后，来自\(E_1^{RWR}\)的\(X_1^2\)以及RWR嵌入矩阵会被结合馈入到一个组合层中：
\(\mathbf{E}_{1}=\operatorname{COMBINE}\left(\left[\mathbf{E}_{1}^{R W R} \| \mathbf{X}_{1}^{2}\right]\right)\)
最终的嵌入矩阵e1和e2仍然在一个统一的嵌入空间中，因为训练过程中涉及的所有模块对于g1和g2具有相同的参数共享。
4. BRIGHT模型训练
在优化模型时，我们使用了起源于实体链接社区的边际排名损失。有E1,E2我们有：
其中L是anchor link集合，γ是边缘参数，\(i∈{1,2}\)区分两个网络l1和l2是G1和G2中对应的锚链路l的锚节点，\(U_{l_i}\)是节点li负采样集对，\(u∈U_{l_i}\)是在\(G_{3-i}\)对于在\(G_i\)的\(l_i\)负采样对。例如，如果i=1，这证明\(U_{l_i}\)是来自G2的负采样节点对样本。我们使用L1范数作为d（（·，·））—节点嵌入的距离。特别地，我们的负抽样策略是排序然后选择。为了提高负采样质量和对齐性能，我们在G2中的节点嵌入最接近锚节点l1的G1嵌入为Ul1。如果n2太大的话，可以采用双级负抽样策略。我们首先随机抽取固定数量的负节点，然后使用相同的排序后选择策略进行第二级负抽样。BRIGHT的最终损失函数为：J=J1+J2
BRIGHT收敛之后，我们计算在对齐矩阵S中的\(S(x,a)\)如下：
\(\mathrm{S}(x, a)=e^{-d(x, a)}\)
其中d(x,a)是L1范数距离，G1中的a与G2中的x的距离。