这篇文章提出了一个UAGA（Unsupervised Adversarial Graph Alignment）架构以完全无监督的方式学习不同图的两个嵌入空间之间的交叉图对齐。该框架学习每个图的嵌入空间，然后尝试通过对抗性训练对齐这两个空间，然后进行细化过程。我们进一步将我们的UAGA方法扩展到增量UAGA(iUAGA)，该方法基于伪锚定链接迭代地显示未观察到的用户链接。这可以用来进一步提高嵌入质量和对齐精度。
文章只使用两个图的结构信息，首先，利用无监督图嵌入方法分别学习源图和目标图的单个特征表示。接下来，它利用对抗性的训练来学习a 从源嵌入空间到目标嵌入空间的线性映射，然后进行细化过程，从得到的共享嵌入空间中得到伪节点对应 并使用来自[17]的封闭形式的解决程序解决方案对映射进行微调。最后，我们将UAGA方法扩展到增量UAGA(iUAGA)，以提高嵌入质量和对齐 性能迭代。
hub问题，即在高维嵌入空间中，一定数量的节点成为许多其他节点的枢纽和最近邻，如果不解决，将使 通过最近的搜索进行的对齐更加困难和不准确。
- 定义一：(Graph Alignment Problem)给定两个社交网络\(G_s=(V_s,E_s)\)以及\(G_t=(V_t,E_t)\)，没有先验的anchor links，目的就是要找到隐藏的对齐的节点。
在本文中，使用deepwalk来学习源网络和目标网络的graph embedding，定义为\(Z_s,Z_t∈R^{|V| \times d}\)。
按照流程图，首先用无监督学习的方法学习图的特征表示，然后我们利用领域对抗性训练来学习W的初始代理。接下来，我们利用学习到的W来选择伪锚点链接来进行映射细化。最后，我们利用细化的映射W将所有源节点映射到目标潜在特征空间。我们通过改变空间的度量来提高比图对齐的性能，这将导致在数据密集的区域中分布更多的这些节点。
在本文中，我们提出学习一个映射，不需要任何形式的跨域监督之间，这样两个不同的嵌入空间可以很好地对齐。
令\(Z_s= \left\{ z_s^1,...,z_s^n\right\}\)以及\(Z_t= \left\{ z_t^1,...,z_t^m\right\}\)为源网络和目标网络的嵌入空间。如果我们知道跨网络的节点对齐（比方说\(z_s^i,z_t^i\)是对齐的），我们能够学习到一个线性映射\(W∈R^{d \times d}\)：
d是嵌入向量的维度，X和Y是两个对齐的矩阵，\(X,Y∈R^{d \times k}\)，是由源网络和目标网络中找到的k个结点形成的。在测试阶段，任意源网络的embedding \(z_s^i\)的转换可以被定义为：\(arg \max_{z_t^j∈Z_t}cos(Wz_s^i,z_t^j)\)，注意，如果我们有地面-真节点对应，方程（2）可以直接用作监督学习的损失部分。
所提出的UAGA框架包括两个步骤：学习W的初始代理的领域对抗性训练，然后是利用最佳匹配节点来创建的细化过程 应用方程（2）的伪锚点链接。
A. domain-adversarial training
在这一步中，我们的目标是要使得映射后的\(Z_s,Z_t\)难以区分。（用的是GAN的方法）首先我们定义一个判别器，它旨在区分从\(WZ_s={W_{z^1_s}、W^{z^2_s}、..，W_{z^n_s}}\)和\(Z_t\)中随机采样的元素。映射W可以看作是生成器，通过使嵌入特征WZs和Zt变得无法区分，来防止鉴别器做出准确的预测。因此，域对抗训练过程是一个双人博弈，其中第一个玩家是训练区分源域和目标域，第二个玩家是同时被训练来混淆鉴别器的生成器。
给定映射W，鉴别器由\(\theta_D\)通过最小化以下目标函数进行优化：
前一项表示的含义是：嵌入\(z_s^i\)来自源嵌入空间，给定鉴别器，映射W的目的是通过最小化以下目标函数来欺骗鉴别器精确预测嵌入的原始域的能力：
为了训练我们的模型，我们遵循标准的生成对抗网(GANs)[30]训练程序，它交替地和迭代地优化鉴别器θD和映射W，使其分别最小化LD和LW。
B. the hubness problem and refinement procedure
域对抗训练步骤学习一个匹配全局源和目标嵌入空间的映射函数W，而不考虑数据分布背后的复杂的多模结构。换句话说，在我们的无监督场景中，两组节点之间的细粒度的点到点约束（即没有两条边共享一个共同的端点）没有被明确地强制执行。
为了解决上述挑战，我们提出了一个细化过程，使细粒度的点对点与生成的伪锚定链路的图对齐。细化的优点 我们可以从两个方面得出结论。首先，通过引入额外的监督(伪锚链，我们在领域对抗训练步骤中规避了潜在的模式崩溃问题(这在传统gan中是一个臭名昭著的问题) )，以适用于点对点的对齐。第二，在选择伪锚链接时，我们在确定了相互关系中所谓的hub问题（即点倾向于高维空间中许多点的最近邻）[31] 通过引入一个交叉图相似度缩放(CGSS)方案。
我们使用在之前的领域对抗性训练步骤中学习到的W作为初始代理，随后构建许多伪造的anchor links，为了获得高质量的伪造的anchor links，我们只保留在\(Z_s和Z_t\)中相互是最邻近的邻居的结点。然而，最近邻通常是不对称的：\(z_t\)是\(z_s\)的k最邻不代表\(z_s\)是\(z_t\)的k近邻。在嵌入特征空间中，这将导致一种不利于基于最近邻规则对齐节点嵌入的现象：嵌入空间中的一些节点，我们称之为枢纽，ar e更有可能是许多其他节点的最近邻居，但其他节点（称为反集线器）并不是任何节点的最近邻居。
我们使用CGSS来缓解所谓的hubness问题，我们考虑一个二部邻域图，其中给定锚链的每个节点都连接到另一个图中的K个最近邻。在二部图中，与映射的源节点嵌入关联\(Wz_s\)的邻域被表示为\(N_T(Wz_s)\)。\(N_T(Wz_s)\)所有的K个元素是来自源网络的结点。源嵌入z与目标邻域的平均相似度表示为：（每个节点都连接到目标网络的k个最近邻，就是说在原网络中i和j是k近邻的话，那么在目标网络中他们也是k近邻的话那么就被保留为伪造的anchor links）
cos表示cos相似度，同理可以定义目标embedding到其源网络邻居的平均相似度。我们使用有效的最近邻算法[32]来计算所有的源节点和目标节点的嵌入。形式上，我们利用这些相似性来定义一个跨域相似性度量CGSS（.，.）在映射的源嵌入和目标嵌入之间，
CGSS方案的动机是直观的：它增加了与孤立节点嵌入相关的相似性，而减少了位于密集区域的嵌入的相似性。换句话说，我 T鼓励选择位于低密度区域的节点作为伪锚定链接。形式上，映射W通过方法进一步细化：我们应用方程（2） 或链接来细化W。（度越大的结点对于对齐的影响干扰越大）
C. orthography constraints
在我们的工作中，我们额外提出了一个简单的更新步骤，使映射矩阵W在训练进行时保持接近一个正交矩阵。正交约束的优势如下：（1）分别保留源特征嵌入和目标特征嵌入的个体特征和质量；（2）随着训练的进行，稳定了学习过程；（3）保持点积以及它们的L2距离。具体来说，我们的模型将通过使用以下更新策略进行迭代和交替更新
利用正交约束，方程（2）可以归结为普罗克鲁斯问题，就是一个矩阵的逼近问题，它的解就是\(YX^T\)的奇异值分解值：
为了进一步有效地利用伪锚定链接来学习更准确的映射，我们进一步提出了一个增量的UAGA(iUAGA)程序，它逐步选择一组伪锚定链接，然后利用它们通过使用方程（2）来细化映射W。如果满足以下两个条件，我们选择一个伪锚定链路。首先，我们要求跨域相似度（即方程（5））应该超过阈值参数，我们设为 在实验中分别是0.7或0.75。第二个要求是根据CGSS，嵌入特征对是相互最近的邻居。我们假设，除非它们是相互的最近邻，否则成对的关系是不可靠的。这两个要求减少了伪锚定链路的数量，但提高了其精度和最终的对齐性能。伪造的铆钉节点表示为\(\left\{\widehat T=(v_s,v_t)|v_s∈V_s,v_t∈V_t\right\}\)。
另一个问题就是一些存在的边可能因为没有显式的建立或者没有爬取到而并不能观察到，为了解决这个问题，在此基础上，我们的方法提出了通过伪标记许多可靠的锚定链路来逐步弥补交叉图监督的不足，这有助于显示了未被观察到的边缘（图内伪用户链接）。理由是，如果两个节点在一个图中不连接，但它们的对应节点（根据伪锚点链接）在另一个图中链接，那么在中间加一条边是可行的 在现在的图中，
通过利用伪标记的用户链接，我们可以进一步提高图的嵌入质量和最终的对齐性能。它背后的原因是扩展的图可以提供 更丰富的结构信息，可用于图形的嵌入和映射。
形式上给定两个图\(G_s,G_t\)，具有伪造的锚定节点\(\widehat T\)，\(G_s\)的扩展图\(\widehat G_s\)可以被表示为：
算法流程如下：
整个算法的流程就是：首先得到两个图的各自的node embedding，然后进行GAN的参数更新，得到一个对齐矩阵W。然后获取一个伪造的anchor links集合（如果互为k临近的话那么就是符合要求的），随后细化映射W。随后按照公式7扩展源网络和目标网络，最后重置Gs,Gt和T。最后使用公式5来对齐网络。