论文笔记
最近的一些基于嵌入的方法可以通过采样负对齐对来在某种程度上产生对齐差异。在不同的甚至相互竞争的负抽样分布设计下，一些方法提倡正相关，这可能会导致假阴性样本错误地违反对齐一致性，而其他节点则支持负相关或均匀分布，这可能对学习有意义的嵌入贡献很小。本论文作者揭开了各种网络对齐方法背后的内在关系，以及这些相互竞争的抽样设计原则之间的内在关系。具体地说，在模型设计方面，我们从理论上揭示了一种特殊的图卷积网络模型与传统的基于一致性的对齐方法之间的密切联系。对于模型训练，我们量化了基于采样分布的网络对齐的嵌入学习的风险。提出了NEXTALIGN在对齐一致性和差异性之间达到了平衡。
基于对齐一致性的方法可能会导致局部邻域内的对齐的过度平滑问题，并且无法区分正确的对齐。嵌入的方法通过节点嵌入来推断节点对齐，可以在一定程度上合并对齐差异，并通过引入负对齐节点对来改善过平滑问题。通过负采样，学习到的节点嵌入可以潜在地使局部邻域内的对齐更加可分离（即对齐视差）。
过平滑问题：如果在GNN的运算输出的时候，得到了所有节点或者大部分节点的输出向量差不多，那么就认为出现了过平滑。过平滑出现的原因有：1.数据层面的问题，2.图卷积层堆叠的非常深，导致过平滑问题，3.图卷积核的问题
那么什么样的节点算是好的负采样的节点呢？
良好的负样本应该区分可能误导对齐的锚定链接和近节点对，同时不违反整体对齐的一致性。此外，这些负样本应该告知模型学习有意义的网络对齐嵌入。这些方法也有局限性：由于是单个网络的嵌入，基于正相关的抽样可能导致假的negative对齐对（即(c,f)作为anchor link (b,y)的负对齐对）这导致不正确的对齐违反对齐一致性。另一方面，利用先前定义的分布以及那些与正采样分布呈负相关的样本可能会对遥远或不同的节点对进行采样（也就是(e,h））可能并不会对学习有意义的embedding有多大的作用。
- model design：我们从理论上证明了由图卷积网络所推断出的对齐类似于基于FINAL一致性的对齐方法的半监督变体。这激发了一个特定的图卷积网络模型，可以保持对齐的一致性。
- model training：我们提供了一个引理，它表明通过期望损失和经验损失学习到的节点嵌入的内积之间的均方误差可以通过不同的抽样分布来量化。为了减少上述竞争设计相互兼容的误差，我们设计了一种新的对齐评分函数，为所提出的抽样策略铺平了道路。
\(n_1=|V_1|,n_2=|V_2|\)表示节点数\(X_1∈R^{d_0 \times n_1},X_2∈R^{d_0 \times n_2}\)。
\(\mathcal{L}_{1}=\left\{a \mid \exists x \in \mathcal{V}_{2}\right.\), s.t., \(\left.(a, x) \in \mathcal{L}\right\}\)表示网络1中的anchor节点
- 问题1：semi-supervised network alignment
- given：\(G_1= \left\{V_1,A_1,X_1\right\},G_2=\left\{V_1,A_2,X_2\right\}\)以及anchor links集合L。
- output：对齐矩阵S，其中\(S(a,x)\)表明节点a和x对齐的程度
对于没有节点特征的网络，使用one-hot embedding编码输入节点特征。我们可以通过将两个锚定节点合并为单个节点，将输入网络G1、G2集成到一个世界观网络G中。最终，G具有G1和G2中的非anchor nodes，以及独特的锚定节点作为G的节点。G1和G2中所有的边都在G中共存。通过在这个世界观网络G中学习节点嵌入，我们可以自然地在两个相应的锚点上共享唯一的嵌入。
对齐一致性（FINAL）
\(\min _{\mathrm{S}} \sum_{a, b, x, y}\left[\frac{\mathrm{S}(a, x)}{\sqrt{\left|\mathcal{N}_{1}(a)\right|\left|\mathcal{N}_{2}(x)\right|}}-\frac{\mathrm{S}(b, y)}{\sqrt{\left|\mathcal{N}_{1}(b)\right|\left|\mathcal{N}_{2}(y)\right|}}\right]^{2} \mathrm{~A}_{1}(a, b) \mathrm{A}_{2}(x, y)\)
其中\(N_1(a),N_2(x)\)表示节点a和节点x的邻居。\(A_1=A_1',A_2=A_2'\),当节点b和y是节点a和x的邻居时，公式1会导致\(S(a,x)和S(b,y)\)之间的小的不同。另一个角度解释公式1，给定一个anchor链接\((a,x)\)具有很高的\(S(a,x)\)，这将导致\(S(b,y)\)也很高，公式1自然地将所有相邻的节点对视为（𝑎，𝑥）的正对齐对.
公式1的解：
\(\mathrm{S}^{t}=\tilde{\mathrm{A}}_{1} \mathrm{~S}^{t-1} \tilde{\mathrm{A}}_{2}^{\prime}\)
其中\(\widetilde A_1,\widetilde A_2\)是\(A_1,A_2\)的对称标准化。
半监督模型中的anchor links可以被用作正则化，也就是：
\(\mathbf{S}^{t}=\alpha \tilde{\mathbf{A}}_{1} \mathbf{S}^{t-1} \tilde{\mathbf{A}}_{2}^{\prime}+(1-\alpha) \mathbf{L}\)
其中α控制的是对齐一致性的重要性。只有当\((a,x)\)是anchor links时\(L(a,x)=1\)，其他都为0
为了设计一个模型学习节点嵌入的同时遵循对齐一致性，我们首先证明了由一种特定的无参数消息传递方式的节点embeddings的对齐与半监督的FINAL方法是类似的。证明的关键思想是对等式(3)中使用的矩阵L进行rank-|L|分解和使用分解后的矩阵作为输入节点嵌入。直观上，通过将anchor nodes视为\(|L|\)维度的欧氏空间中的landmarks，这个消息传递可以解释为确定所有节点与anchor nodes相关的相对位置。随后，基于其捕获对齐一致性的能力，我们提出了该消息传递的参数化对应物在等式6中。我们将其命名为RelGCN层，然后用它来校准由等式 (5)计算出的节点的相对位置.最终的节点嵌入是通过在这些位置向量上应用一个线性层得到的。
在模型训练方面，实现权衡的关键思想是通过不同的抽样分布。它背后的直觉如下：给定一个anchor link \((a,x)∈L\)如果\((b,y)\)被采样为积极的对齐节点对，这将正向激励节点对\((b,y)\)和\((a,x)\)之间的一致性。相反，如果\((b,y)\)被选作负对齐节点对，它们之间的对齐差异是有利的。此外，为了保持同一网络中的局部邻近性，我们还对正上下文对和负上下文对进行了采样。为了设计这些抽样分布，我们首先量化了通过最小化预期损失和经验损失来学习的节点嵌入的内积之间的均方误差。在此基础上，为了在满足不同甚至相互竞争的设计原则的同时，更准确地对高概率节点对的内积进行估计，我们提出了一种新的对齐方法 反映节点嵌入的多个方面的评分功能。
模型设计
假设节点a,x的对齐是由\(S(a,x)=a'x\)计算的，随后我们有：
\(\begin{aligned}\left(\mathbf{a}^{t}\right)^{\prime} \mathbf{x}^{t} &=\mathrm{S}^{t}(a, x)=\tilde{\mathrm{A}}_{1}(a,:) \mathrm{S}^{t-1} \tilde{\mathrm{A}}_{2}(:, x) \\ &=\sum_{b \in \mathcal{N}_{1}(a)} \sum_{y \in \mathcal{N}_{2}(x)} \frac{\left(\mathbf{b}^{t-1}\right)^{\prime} \mathbf{y}^{t-1}}{\sqrt{\left|\mathcal{N}_{1}(a)\right|\left|\mathcal{N}_{1}(b)\right|\left|\mathcal{N}_{2}(x)\right|\left|\mathcal{N}_{2}(y)\right|}} \\ &=\sum_{b \in \mathcal{N}_{1}(a)} \frac{\left(\mathbf{b}^{t-1}\right)^{\prime}}{\sqrt{\left|\mathcal{N}_{1}(a)\right|\left|\mathcal{N}_{1}(b)\right|}} \sum_{y \in \mathcal{N}_{2}(x)} \frac{\mathbf{y}^{t-1}}{\sqrt{\left|\mathcal{N}_{2}(x)\right|\left|\mathcal{N}_{2}(y)\right|}} \end{aligned}\)
其中\(b^{t-1}\)表示节点b的第\((t-1)\)层的节点嵌入。可以看见，第t层的计算对齐矩阵\(S^t(a,x)\)相当于通过应用不带参数的普通GCN来更新节点嵌入。
\(\mathbf{a}^{t}=\sum_{b \in \mathcal{N}_{1}(a)} \frac{\mathbf{b}^{t-1}}{\sqrt{\left|\mathcal{N}_{1}(a)\right|\left|\mathcal{N}_{1}(b)\right|}}, \mathbf{x}^{t}=\sum_{y \in \mathcal{N}_{2}(x)} \frac{\mathbf{y}^{t-1}}{\sqrt{\left|\mathcal{N}_{2}(x)\right|\left|\mathcal{N}_{2}(y)\right|}}\)
与一般的GCN模型不同的是，这里并没有使用带有自环的邻域。由于GCN面临的过平滑的问题，对齐可能也会造成过平滑的问题。在锚定链接可用的半监督设置中，我们设计了以下没有参数的消息传递：
\(\begin{aligned} \mathbf{u}^{t} &=\sqrt{\alpha} \sum_{b \in \mathcal{N}_{1}(u)} \frac{\mathbf{b}^{t-1}}{\sqrt{\left|\mathcal{N}_{1}(u)\right|\left|\mathcal{N}_{1}(b)\right|}}+\sqrt{1-\alpha} \mathbf{u}^{t-1} \\ \mathbf{v}^{t} &=\sqrt{\alpha} \sum_{y \in \mathcal{N}_{2}(v)} \frac{\mathbf{y}^{t-1}}{\sqrt{\left|\mathcal{N}_{2}(v)\right|\left|\mathcal{N}_{2}(y)\right|}}+\sqrt{1-\alpha} \mathbf{v}^{t-1} \\ \mathbf{a}^{t}=\mathbf{x}^{t} &=\sqrt{\alpha} \sum_{b \in \mathcal{N}_{1}(a)} \frac{\mathbf{b}^{t-1}}{\sqrt{\left|\mathcal{N}_{1}(a)\right|\left|\mathcal{N}_{1}(b)\right|}}+\sqrt{1-\alpha} \mathbf{x}^{t-1} \\ &+\sqrt{\alpha} \sum_{y \in \mathcal{N}_{2}(x)} \frac{\mathbf{y}^{t-1}}{\sqrt{\left|\mathcal{N}_{2}(x)\right|\left|\mathcal{N}_{2}(y)\right|}} \end{aligned}\)
其中节点u和节点v是非铆钉节点，节点a和节点x是铆钉节点。
lemma 1：假设初始的非铆钉节点嵌入是\(u^0=v^0=0\)并且铆钉节点是\(a^0=x^0=e_i∈R^{|L|}\)其中\((a,x)\)是第i个anchor link，\(e_i(i)=1 \ and \ e_i(j)=0 j≠i\)。然后更新公式(5)一次，对齐计算与公式(3)一样直到额外的网络内部接近度和可能的缩放项。
证明：给定\(|L|=L\)个铆钉节点，我们可以对L进行L维没有误差的矩阵分解为\(L=L'_1L_2\)。由于\(L(a,x)=1 \ if\ (a,x)∈L\)，我们有\(L_1(:,a)=a^0=e_i,L_2(:,x)=x^0=e_i\)。对于非铆钉节点，我们有\(L_1(:u)=u^0=0,L_2(:,v)=v^0=0\)，在初始化嵌入矩阵为\(L_1,L_2\)之后，对齐由使用等式(5)更新的嵌入之间的内积计算 .