【KDD2020】多层次图卷积网络的跨平台锚链预测，Multi-level Graph Convolutional Networks for Cross-platform Anchor Link Prediction

题目： Multi-level Graph Convolutional Networks for Cross-platform Anchor Link Prediction

摘要：

在社交网络分析中，跨平台账户匹配扮演着重要的角色，并且有利于很多应用。然而，现有的方法要么严重依赖高质量的用户生成内容(包括用户信息文件)，要么仅关注网络拓扑结构就存在数据不足的问题，这给研究者带来了模型选择的两难困境。为了解决这个问题，我们提出了一个新的框架，在局部网络结构和超图结构上统一考虑多层次的图卷积。该方法克服了现有工作中数据不足的问题，且不需要依赖用户的人口统计信息。此外，为了使该方法能够处理大规模社交网络，我们提出了一种两阶段空间协调机制，以在基于网络划分的并行训练和跨不同社交网络的账户匹配中对齐嵌入空间。在两个大规模的现实社会网络上进行了广泛的实验。实验结果表明，该方法的性能优于现有模型。

介绍： 如今，大多数人都参与了不止一个在线社交网络(OSN)，如Facebook、Twitter、微博、Linkedin。通常情况下，用户为了不同的目的在不同的OSNs上注册，不同的OSNs显示了不同的观点和人的不同方面。例如，一个用户在Facebook上链接的是他们的朋友，但是使用Linkedin链接的是他/她的同事，感兴趣的公司和寻找工作机会。虽然不同的OSNs表现出不同的特性和功能，但在不同的社交平台上，个人用户帐户的重叠现象一直存在。然而，出于隐私方面的考虑或缺乏动机，在大多数社交网络中，属于同一个人的多个账户的信息并没有明确给出。

在数据挖掘研究领域中，将来自不同社交网络的同一个人的账号匹配问题定义为账号映射、社交网络去匿名化或社交锚链预测。帐户匹配在不同社交平台在社会网络分析中起着基础和重要的角色,因为它有助于提高许多下游应用程序,如在线个性化服务,链接预测,推荐系统,生物蛋白质对齐老化相关复合物,和犯罪行为检测。尽管人们对这一具有挑战性的课题给予了很大的关注，但仍有很大的改进空间。以往的研究提出利用可用的辅助信息，如自生成的用户资料、每日生成的内容和其他人口统计特征(如用户名、头像、位置、性别、帖子、博客、评论等)来解决这一问题。然而，随着公众隐私和信息权利意识的提高，这些信息越来越难以获得和获取。

近年来，随着网络嵌入(Network Embedding, NE)技术的发展，与此问题相关的研究重点已经转移到挖掘网络结构信息上，因为有人认为社会网络结构数据在正确性和完整性方面更加可靠。然而，仅仅关注网络结构本身的建模，使得几乎所有现有的方法都存在数据不足的问题，特别是在小规模网络和冷启动设置(即网络新用户)。因此，在实际的场景中，它一直是从业者所面临的两难问题急需解决办法。

基于此，我们提出利用并整合从原始网络中提取的超图信息来进行数据增强。在本文的其余部分，我们分别使用简单图和超图来表示原始网络和从原始网络中提取的超图。与简单图相比，超图允许有一条边。同时连接两个以上的节点。这意味着图中节点之间的非成对关系可以很容易地组织并表示为超边。此外，超图具有鲁棒性和灵活性，能够适应各种各样的社交网络，无论给定的社交网络是纯社交网络还是具有各种属性和链接的异构社交网络。

更具体地说，我们提出了一种新的多层图卷积网络的嵌入框架，即MGCN，来共同学习不同粒度的网络顶点的嵌入。简单图GCN，超图GCN)。社交网络的简单图结构信息揭示了用户之间的关系(如友谊、关注者)，而超图则根据其在社交网络中的具体定义具有不同的语义意义。例如，基于N-hop邻居的超图(用户的N-hop邻居通过同一个超边连接)在一定程度上表示朋友圈。基于中心的超图表示不同的社会层次(具有相似中心性值的用户可能具有相同的社会地位)。因此，通过定义各种超图并将其嵌入到网络嵌入学习中，将有助于学习更好的用户表示。为了支持这一点，我们提出的MGCN框架是灵活的，可以包含各种超图定义，它可以将任何超图作为向量表示，使模型结构对各种超图定义不变性。

通过扩展GCN来开发和集成超图背后的基本原理是，超图提供了一个更灵活的网络表示，与本地网络拓扑上的单个图GCNs相比，它可以包含更多更丰富的信息。我们发现，在大多数情况下，GCN层的最优数量总是被设置为2，因为添加更多的层不能显著提高的性能。因此，GCNs只能捕获网络中某个节点周围的本地信息。这一现象也使得单一的GCN存在矛盾，因此在账户匹配任务上表现的一般，因为任务的关键是探索更多更深的信息来进行预测。从直观上看，在从原始网络中提取的超图上定义GCNs将补充现有基于GCN嵌入模型的局限性。

然而，这仍然是一项具有挑战性的任务，因为社交网络是大规模的，有数百万个节点和数十亿个边。传统的集中训练方法由于计算量大，无法适应这样大的网络。为了使MGCN适应于大规模社交网络，提高其可扩展性和效率，我们提出了一种新的训练方法，该方法首先将大规模社交网络分割成簇，然后以完全分散的方式学习网络嵌入。为了对齐不同簇的学习嵌入空间，我们提出了一种新的两相空间协调机制。在第一阶段，我们对齐从同一网络内的每个簇中学习到的嵌入空间。除了不同子网之间的排列在同一网络,推导空间和解对齐两个不同网络通过少量的观测锚节点,这使得我们的MGCN框架实现更精确的锚点链接比最先进的模型和预测效率高在大型社交网络。

本文的主要贡献总结如下:

• 我们提出了一个新的框架，用于预测跨不同社交网络的锚链接这一具有挑战性的任务。该方法同时考虑了局部和超图级的图卷积来学习网络嵌入，能够为任务捕获更广泛、更丰富的网络信息。

• 为了使所提出的框架能够适应大规模的社交网络，我们提出了一系列的处理方法，包括网络分割和空间调和来处理分布式的训练过程。

• 对大规模真实数据集进行了广泛的评估，实验结果证明了提出的MGCN模型相对于最新模型的优越性。