关注上海本地生活

上海精神

谷歌 AI 图表示学习最新成果:解决重叠区域描述难题

2019-07-07 16:44 作者: 来源: 本站 浏览: 130 次 字号:

摘要: 雷锋网 AI 科技评论按,表示实体之间关系的关系数据在网络(如在线社交网络)和物理世界(如蛋白质交互网络)中随处可见。这些数据可以表示为一个带有节点(如用户、蛋白质)和连接它们的边(如社交网络中的朋友关系、蛋白质之间的相互作用)的图。 不久前,谷歌 ...

雷锋网 AI 科技评论按,表示实体之间关系的关系数据在网络(如在线社交网络)和物理世界(如蛋白质交互网络)中随处可见。这些数据可以表示为一个带有节点(如用户、蛋白质)和连接它们的边(如社交网络中的朋友关系、蛋白质之间的相互作用)的图。

不久前,谷歌 AI 发布了一篇博文,介绍了他们在图 embedding 上面的两篇论文成果。其中,其中一篇论文解决了如何更好地描述具有重叠区域的网络,第二篇论文解决了图 embedding 中超参数调整的基本问题。雷锋网 AI 科技评论将他们的博文编译如下。

考虑到图的广泛流行,图分析在机器学习中起着基础性的作用,在集群、关系预测、隐私和其他方面都有应用。要将机器学习方法应用于图(例如,预测新的友谊,或发现未知的蛋白质相互作用),需要学习一种可用于 ML 算法的图形表示。

然而,图本质上是由离散部分(如节点和边)组成的组合结构,而许多常见的 ML 方法(如神经网络)更倾向于连续结构,特别是向量表示。矢量表示在神经网络中特别重要,因为它们可以直接用作输入层。为了解决在 ML 中使用离散图表示困难的问题,图嵌入方法为图学习一个连续的向量空间,将图中的每个节点或边分配给向量空间中的特定位置。在这一领域,一种流行的方法是基于随机移走的表示学习,正如在 DeepWalk 中引入的一样。

左图:代表社交网络的著名 Karate 图表。右图:使用 DeepWalk 在图中连续嵌入节点的空间。

在这里,我们展示了最近两篇关于图 embedding 的论文的结果:The web conference 2019 会议论文「Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts」和 Neurips’ 2018 论文「Watch Your Step: Learning Node Embeddings via Graph Attention」。第一篇文章介绍了一种新颖的技术来学习每个节点的多个嵌入,从而能够更好地描述具有重叠区域的网络。第二个问题解决了图嵌入中超参数调整的基本问题,使人们可以轻松地部署图嵌入方法。我们也很高兴地宣布,我们已经在 Google Research Github 图嵌入库中发布了这两篇论文的代码。

学习节点表示,捕获多个社交背景

在几乎所有情况下,标准图嵌入方法的关键假设是必须为每个节点学习单个嵌入。因此,嵌入方法的作用可以认为是识别在图的几何图形中,表征每个节点的单个角色或位置。然而,最近的研究发现,真实社区中的节点属于多个重叠的区域,扮演着多个角色。想想你的社交网络,在那里你既参与到你的家庭社区中,又参与到你的工作社区中。这引发了以下问题:是否有可能开发将节点嵌入多个向量中,表示它们参与重叠的区域的方法?

在我们的 The web conference 2019 论文中,我们开发了 Splitter,这是一种无监督的嵌入方法,允许图中的节点具有多个嵌入,以便更好地表示它们在多个社区中的参与。我们的方法是基于最近在基于 ego-network 分析的重叠聚类中的创新,特别是使用了人物图概念。该方法获取一个图 G,并创建一个新的图 P(称为角色图),其中 G 中的每个节点都由一系列称为角色节点的副本表示。节点的每个角色表示它所属的本地社区中节点的实例。对于图中的每个节点 U,我们分析节点的 ego-network(即连接节点与其邻居的图,在本例中是 A、B、C、D),以发现节点所属的本地社区。例如,在下图中,节点 U 属于两个社区:集群 1(与 A 和 B 一起,表示 U 的家人)和集群 2(与 C 和 D 一起,表示 U 的同事)。

节点 U 的 ego-net

然后,我们使用这些信息将节点 U「分割」为两个角色 U1(家庭角色)和 U2(工作角色)。这将两个社区分离开来,使它们不再重叠。

ego-splitting 将两个角色中的 U 节点分离

该技术已被用于改善图形嵌入方法中的最新结果。这种改进的关键原因是该方法能够消除社交网络和其他现实世界的图中高度重叠的社区的歧义。我们进一步通过对作者所属的重叠研究群体(如机器学习和数据挖掘)的合作关系图的深入分析来验证这一结果。

左上角:具有高度重叠社区的典型图。右上角:使用 node2vec 在左侧 embedding 图的传统方法。左下角:上图中的角色图。右下角:角色图的拆分器 embedding。

通过图注意力自动调整超参数

图 embedding 方法在各种基于 ML 的应用程序上表现出了突出的性能,但它们有许多必须手动设置的超参数。例如,在学习 embedding 时,附近的节点比远处的节点更重要吗?即使专家可以微调这些超参数,但他们必须对每个图单独进行调整。为了避免这种手工操作,在第二篇论文中,我们提出了一种自动学习最优超参数的方法。

具体来说,许多图 embedding 方法,如 DeepWalk 等,都采用随机移走来探索给定节点周围的上下文(即直接邻居、邻居的邻居等)。这样的随机移走可以有许多超参数,允许调整图的局部搜索,从而调节 embedding 到附近节点的注意力。不同的图可能会呈现不同的最佳注意力模式,因此会呈现不同的最佳超参数(见下图,其中我们展示了两种不同的注意力分布)。

我们的新方法自动进行超参数调整,注意你的步骤,使用注意力模型来学习不同图的上下文分布。上面显示的是两个关于中心节点(黄色)和上下文分布(红色渐变)的示例,由模型学习得来。左边的图显示了一个更分散的注意力模型,而右边的分布显示了一个集中在直接邻居上的模型。

这项工作属于日益壮大的 AutoML 家族,我们希望减轻优化超参数的负担,这是实际机器学习中的一个常见问题。许多 AutoML 方法都使用神经结构搜索。本文给出了一个变量,我们使用 embedding 中超参数与图论矩阵公式之间的数学关系。「Auto」部分对应于通过反向传播学习图的超参数。

我们相信,我们的贡献将进一步推进图 embedding 的研究现状。我们学习多节点 embedding 的方法在丰富和深入研究的重叠社区检测领域中起到了一定的作用。我们相信后一种图 embedding 方法将为今后的研究带来丰硕的成果。这一领域的一个开放性问题是使用多种 embedding 方法进行分类。此外,我们在学习超参数方面的贡献将减少昂贵的手动调优工作,促进图 embedding 的研究。我们希望这些论文和代码的发布将有助于推动这些研究。