为您推荐:
精华内容
最热下载
问答
  • 这里定义的同质异质网络是指行骗者更可能连接着其他行骗者。合法人更可能连接其他合法人。 令l为网络中合法结点的比例,f为网络中欺诈结点的比例,2lf就是一条边连接两个不同标签的结点的期望可能性,这些边叫做...
    1. 当标签x的结点更大程度上连接其他标签x的结点的时候,这个网络是同质的。非同质的网络是异质的。
    2. 这里定义的同质异质网络是指行骗者更可能连接着其他行骗者。合法人更可能连接其他合法人。
    3. 令l为网络中合法结点的比例,f为网络中欺诈结点的比例,2lf就是一条边连接两个不同标签的结点的期望可能性,这些边叫做cross-labeled edges.如果已知的cross-labeled edges的比例r小于期望的2lf,这个网络就是同质的。
    4. 其他衡量同质性的因素还包括dyadicity和heterophilicity.结点分享一个共同的特性比性质随机分散在网络中的可能性更大。这就是dyadicity的影响。对于标签仅仅取两个值的网络,1(Fraud)0(Legitimate),n1(n0)是fraudulent(legitimate)的节点数,N=n0+n1.定义三种dyads:(1-1),(1-0)和(0-0),表示两个终端结点的联系标签(Fraud-Fraud),(Fraud-legitimate),(Legitamate-legitimate),每种的数量是m11,m10,m00,M=m11+m10+m00.如果结点随机连接其他的结点而无关于标签,那么m11和m10的期望值相同.
    5. m11 = (n1 2)p =n1(n1-1)p/2    m10 = (n1 1)(n0 1)p=n1(N-n1)p
    6. p = 2M/(N(N-1))是关联度,代表两个结点连接的可能性。如果p=1,网络中所有结点都相互连接.
    7. Dyadicity and heterophilicity然后被这样定义:D=m11/m11, H=m10/m10, 如果D>1则网络是Dyadicity的,表示fraudulent的结点相比随机连接彼此连接更紧密。如果H<1,一个网络是heterophobic的(与heterophilic相反),意味着fraud结点与legitimate结点有更少的连接相比随机的情况。
    8. 如果一个网络是dyadic and heterophobic,他表现同质性。一个网络是anti-dyadic and heterophilic,是相反的同质性。
    展开全文
    qq_32146369 2019-04-09 10:16:11
  • 3.9MB weixin_38617602 2021-06-18 04:55:48
  • 350KB weixin_38606019 2020-05-27 19:35:51
  • 275KB weixin_38696458 2021-06-09 20:30:43
  • 1.46MB weixin_39841365 2019-07-22 18:19:24
  • 文章目录摘要引言问题定义3 HetGNN3.1 采样异构邻居3.2二级目录三级目录 【注】本篇文章与HAN于同年...虽然在同质(或异构)图嵌入、属性图嵌入以及图神经网络等方面已经做了大量的研究,但很少有研究能够有效地结合考


    论文题目: Heterogeneous Graph Neural Network
    论文来源:KDD 2019
    代码链接:

    关键词:HIN, GNN, Graph Embedding

    【注】本篇文章与HAN于同年先后提出,可结合看。
    相关文章解读

    摘要

    异构图中的表示学习旨在为每个节点追求有意义的向量表示,为链接预测、个性化推荐、节点分类等下游应用提供便利。然而,这项任务具有挑战性,不仅因为需要合并由多种类型的节点和边组成的异构结构(图)信息,而且还因为需要考虑异构属性或内容(e.д。,文本或图像)与每个节点关联。虽然在同质(或异构)图嵌入、属性图嵌入以及图神经网络等方面已经做了大量的研究,但很少有研究能够有效地结合考虑每个节点的异构结构(图)信息和异构内容信息。本文提出一种异构图神经网络模型HetGNN来解决这一问题。具体来说,我们首先引入带重启策略的随机游走 ,对每个节点的强相关异构邻居进行固定大小的采样,并根据节点类型将它们分组。其次,我们设计了一个包含两个模块的神经网络结构来聚合采样的邻近节点的特征信息。第一个模块对异构内容的“深度”特征交互进行编码,生成面向每个节点的内容嵌入。第二个模块对不同相邻组(类型)的内容(属性)嵌入进行聚合,并考虑不同组(类型)的影响进行组合,得到最终节点嵌入。最后,我们利用一个图上下文丢失和一个小批量梯度下降过程以端到端方式训练模型。在多个数据集上进行的大量实验表明,HetGNN在各种图挖掘任务中,即链路预测、推荐、节点分类聚类和归纳节点分类聚类,都能优于最先进的基线。

    1 引言

    异构图(HetG)包含丰富的多类型节点之间具有结构关系(边)的信息,以及与每个节点相关联的非结构化内容。
    传统上,各种各样的HetG任务都依赖于来自于手工特征工程任务的特征向量。这需要对HetG的不同统计数据或特性进行规范和计算,作为下游机器学习或分析任务的特征向量。然而,这可能是非常有限的,不能推广。最近,出现了一种表示学习方法,可以自动完成特征工程任务,从而促进大量下游的机器学习或分析任务。从同构图[6,20,29]开始,图表示学习已经扩展到异构图[1,4]、属性图[15,34]以及特定图[22,28]。例如,“浅”模型e.д。, DeepWalk[20],最初开发的目的是向SkipGram模型[19]提供一组图上的短随机漫步,以近似这些漫步中的节点共生概率,获得节点嵌入。接下来是语义感知方法,e.д。提出了metapath2vec[4],以解决异构图中的节点和关系异构问题。此外,content-aware方法e.д。, ASNE[15],利用“潜在”特征和属性来学习节点嵌入图。
    这些方法直接学习节点的“潜在”嵌入,但在获取丰富的邻域信息方面有局限性。图神经网络(GNNs) 利用深度神经网络对相邻节点的特征信息进行聚合,使得聚合后的嵌入更加强大。此外,GNNs可以很自然地应用于推理性任务,包括训练期间不存在的节点。GCN、GraphSage、GAT分别采用卷积算子、LSTM架构和自注意机制对相邻节点的特征信息进行聚合。GNN的发展和应用主要集中在同构图上。目前最先进的gnn还没有很好地解决HetG所面临的以下挑战,我们在本文中解决了这些问题。

    • HetG中的许多节点可能不能连接到所有类型的邻居。另外,每个节点的相邻节点数量也不相同。 例如,在图1(a)中,任何author节点都没有直接连接到venue节点。同时,在图1(b)中,节点a有5个直接邻居,而节点c只有2个。现有的gnn大多只聚合直接相邻节点(firstorder)的特征信息,而特征的传播过程可能会削弱较远相邻节点的影响。此外,“hub”节点的嵌入生成受到弱相关邻居(“噪声”邻居)的影响,而“冷启动”节点的嵌入由于邻居信息有限而不能充分表示。因此,挑战1是:如何对HetG中每个节点的嵌入生成具有强相关性的异构邻居进行采样,如图1(b)中的C1所示。
    • HetG中的节点可以承载非结构化异构内容,例如属性、文本或图像。此外,与不同类型的节点相关联的内容可以是不同的。因此,如何为HetG中带有异质内容信息的不同节点设计节点内容信息的encoder
    • (C3)不同类型的邻居对HetG中的节点嵌入有不同的贡献。例如,在图1(a)的学术图中,作者和论文的邻域应该对作者节点的嵌入有更大的影响,因为地点节点包含不同的主题,因此具有更普遍的嵌入。目前大多数gnn主要关注同构图,不考虑节点类型的影响。因此,挑战3是:如何考虑不同节点类型的影响,聚合异构邻居的特征信息,
      在这里插入图片描述
      为了解决这些挑战,我们提出了HetGNN,一种异构图神经网络模型,用于HetG中的表示学习。
    • 首先设计了一个带重启的随机游走策略,为HetG中的每个节点采样固定数量的强关联的异质邻居
    • 接着设计了两个模块组成的异质GNN,聚合采样邻居的特征信息。
      第一个模块使用了RNN编码节点异质内容信息间深度的特征交互信息,得到每个节点的内容(content)嵌入。
      第二个模块使用另一个RNN,聚合不同类别的邻居节点的嵌入,并且运用了注意力机制,为不同类型的异质邻居节点分配不同的注意力,得到最终的节点嵌入。
    • 最后使用基于图上下文的损失函数loss,运用mini-batch梯度下降法训练模型。
      总而言之,我们工作的主要贡献是:
    • 定义了同时涉及图结构的异质性节点内容异质性的异质图表示学习问题。
    • 提出HetGNN模型,用于HetG上的表示学习,实现了同时捕获异质的结构和节点内容,并且适用于直推式任务(transductive tasks)和归纳式任务(inductive tasks)。表1对比了HetGNN和其他模型。
    • 多个图数据挖掘任务实现state-of-the-art
      在这里插入图片描述

    2 问题定义

    在本节中,我们介绍了将在本文中使用的与内容相关的异构图的概念,然后正式定义异构图表示学习的问题。

    2.1 内容相关的HetG (Content-associated Heterogeneous Graphs)

    C-HetG定义为 G = ( V , E , O V , R E ) G = ( V , E , O_V , R_E ) G=(V,E,OV,RE) G = ( V , E , O V , R E ) G = ( V , E , O_V , R_E ) G=(V,E,OV,RE)
    分别代表节点类型集合边类型集。每个节点都有异质的内容信息,比如属性、文本、图片。

    2.2 异质图表示学习

    给定C-HetG G = ( V , E , O V , R E ) G = ( V , E , O_V , R_E ) G=(V,E,OV,RE)和节点内容集 C CC,目标就是学习到参数为 Θ Θ Θ的函数 F Θ F_Θ FΘ ,该函数可为每个节点学习到d维的嵌入,以用于多种下游任务。并且该模型能够编码异质的图结构信息以及节点中异质的无结构的内容信息

    3 HetGNN

    在本节中,我们正式介绍HetGNN来解决第1节中描述的三个挑战。HetGNN包括四个部分:(1)对异构邻居进行抽样;(2)对节点异构内容进行编码;(3)聚合异构邻居;(4)制定目标,设计模型训练流程。图2说明了HetGNN的框架。
    在这里插入图片描述

    3.1 采样异构邻居

    大多数图神经网络(GNNs)的核心思想是从一个节点的直接(一阶)邻居(如GraphSAGE[7]或GAT[31])聚集特征信息。然而,直接将这些方法应用于异构图可能会引发几个问题:

    • 它们不能直接从不同类型的邻居中获取特征信息。例如,在图1(a)中,作者没有直接与当地作者和场地邻居建立联系,这可能导致代表性不足。
    • 他们被不同数量的邻居削弱了。一些作者写了很多论文,而一些只有很少的论文在学术图表。有些条目被许多用户审阅,而有些条目在审阅图表中只收到很少的反馈。“中心”节点的嵌入可能会被弱关联的邻居破坏,“冷启动”节点的嵌入可能无法充分表示
    • 它们不适合聚合具有不同内容特性的异构邻居。异构邻居可能需要不同的特征转换来处理不同的特征类型和维度。

    针对这些问题,为了解决挑战C1,我们设计了一种基于带重启的随机漫步(RWR)异构邻居采样策略。它包含两个连续的步骤:

    • 步骤1 使用RWR采样固定长度的路径
      从节点v出发进行随机游走,以迭代的方式每一步走向当前节点的邻居节点,或者以p的概率返回到起始节点,迭代直到采样到了固定数量的节点为止,生成的序列记为 R W R ( v ) RWR(v) RWR(v) 。同时保证 R W R ( v ) RWR(v) RWR(v) 中每种类型的节点都有,也就是采样到了所有类型的节点。
    • 步骤2 将这些采样到的邻居节点按类型进行分类
      针对每种节点类型t,根据其在 R W R ( v ) RWR(v) RWR(v)中出现的频次,选取top k t k_t kt
      ​个节点,将这些邻居节点就是和节点v vv强相关的类型为t tt的邻居节点。

    该策略能够避免上述问题,因为:

    • 为每个节点都采样到了所有类型的邻居节点;
    • 每个节点采样到的邻居节点数是固定的,并且从中选择出了频次最高的邻居节点,也就是和该节点强相关的邻居节点。
    • 将相同类型的邻居分组,以便应用type-based aggregation

    其次,我们设计了一个异构图神经网络结构,该结构包含两个模块,用于聚合每个节点的异构邻居采样特征信息

    3.2 编码异质的内容信息

    4 实验

    实验目的

    回答4个问题:

    • HetGNN和state-of-the-art baseline相比,在链接预测、个性化推荐、节点分类和聚类任务上效果如何?
    • HetGNN在inductive图挖掘任务上,例如inductive节点分类和聚类,和state-of-the-art baseline相比效果如何?
    • 节点的异质内容信息编码和异质邻居聚合是如何影响模型性能的?
    • 不同的超参数,如嵌入向量的维度、采样的邻居数目是如何影响模型性能的?

    数据集

    使用了两种HetG,学术图和评论图。
    在这里插入图片描述
    对比方法
    metapath2vec(MP2V, 异质图), ASNE(属性图), SHNE(属性图),GraphSAGE(GSAGE), GAT

    实验结果

    (1)链接预测
    在这里插入图片描述
    (2)推荐实验结果
    在这里插入图片描述

    (3)节点分类和聚类
    在这里插入图片描述

    (4)inductive的节点分类和聚类
    在这里插入图片描述
    (5)消融实验
    在这里插入图片描述
    (6)超参数设置对模型效果的影响
    在这里插入图片描述

    5 相关工作

    相关研究包括:(1)异构图挖掘;(2)图表示学习;(3)图形神经网络。
    异构图挖掘。在过去的十年中,许多工作致力于挖掘异构图(HetG)用于不同的应用,如关系推理[2,25,33,35],个性化推荐[10,23],分类[36]等。例如,孙等人[25]利用基于元路径的方法来提取拓扑特征和预测学术图中的引用关系。陈等人[2]设计了一个基于HetG的匿名论文作者排名模型。张等[36]在HetG中提出了一种用于集体分类的深度卷积分类模型。
    图表示学习。图表示学习[3]已经成为过去几年中最流行的数据挖掘主题之一。基于图结构的模型[4,6,20,29]被提出来学习矢量化的节点嵌入,其可以进一步被用于各种图挖掘任务的研究。例如,受word2vec [19]的启发,Perozzi等人[20]开发了创新的DeepWalk,它在图中引入了节点上下文概念(类似于单词上下文),并将图中的一组随机行走(类似于“句子”)馈送给SkipGram,以获得节点嵌入。后来,为了解决图结构的异构性,董等人[4]引入了元路径引导行走,并提出了用于HetG中表示学习的元路径2vec。此外,属性图嵌入模型[14,15,34]已经被提出来利用图结构和节点属性来学习节点嵌入。除了这些方法,已经提出了许多其他方法[1,18,21,28,32],例如通过矩阵分解学习节点嵌入的NetMF [21]和使用对立正则化自动编码器学习节点嵌入的NetRA [32],等等。
    图形神经网络。最近,随着深度学习的出现,图形神经网络(GNNs) [5,7,12,16,24,31]得到了很多关注。与以前的图形嵌入模型不同,GNNs背后的关键思想是通过神经网络聚集来自节点本地邻居的特征信息。例如,GraphSAGE [7]使用神经网络,例如д。,LSTM,聚集邻居的特征信息。此外,GAT [31]采用自我注意机制来衡量不同邻居的影响,并结合他们的影响来获得节点嵌入。此外,一些任务相关的方法。用于恶意账户检测的GEM [16]已经被提出来为特定任务获得更好的节点嵌入。

    6 结论

    本文介绍了异构图表示学习问题,并提出了一种异构图神经网络模型HetGNN来解决这个问题。HetGNN联合考虑了节点异构内容编码、基于类型的邻居聚合和异构类型组合。在训练阶段,使用图上下文loss和mini-batch梯度下降过程来学习模型参数。对各种图挖掘任务(即链接预测、推荐、节点分类和聚类以及归纳节点分类和聚类)的大量实验表明,HetGNN可以优于现有的方法。

    展开全文
    qq_36291847 2021-04-15 11:03:30
  • 315KB weixin_39841365 2019-08-16 10:35:51
  • 1.08MB weixin_39840515 2019-07-22 23:02:11
  • 286KB weixin_38621624 2021-06-10 09:36:41
  • 1.09MB weixin_39841856 2019-07-22 21:26:51
  • 476KB weixin_38705014 2021-03-05 20:27:47
  • 1020KB weixin_38639471 2021-06-10 13:06:47
  • 360KB weixin_38725734 2021-06-09 19:43:36
  • 本文主要是大佬梳理了2019年各大顶会上关于异质图神经网络的论文,包括算法研究及应用研究.同时,作者也整理了相关大牛老师/论文/资料/数据集供大家学习. 1.介绍 ​ 图神经网络是近年来图数据挖掘领域的热门研究...

    转载 纪厚业

    本文主要是大佬梳理了2019年各大顶会上关于异质图神经网络的论文,包括算法研究及应用研究.同时,作者也整理了相关大牛老师/论文/资料/数据集供大家学习.

    目录

    1.介绍

    2.模型

    2.1 19WWW  HAN-Heterogeneous Graph Attention Network

    2.2 19KDD HetGNN-Heterogeneous Graph Neural Network

    2.3 19NeurIPS GTN-Graph Transformer Networks

    3 应用

    3.1 19EMNLP HGAT-Heterogeneous Graph Attention Networks for Semi-supervised Short Text Classification

    3.2 19KDD MEIRec-Metapath-guided Heterogeneous Graph Neural Network for Intent Recommendation

    3.3 19CIKM GAS-Spam Review Detection with Graph Convolutional Networks

    4 总结

    5 相关信息(导师/资料/论文/数据)

    5.1 国内外相关大牛老师:

    5.2 相关资料/论文整理:

    5.3 相关数据集整理:

    6.其他相关



    1.介绍

    ​ 图神经网络是近年来图数据挖掘领域的热门研究方向之一,尤其以Graph Convolutional Network,Graph Attention Network为代表的图神经网络已经引起了学术界与工业界的广泛关注.然而,目前的图神经网络主要针对同质图(节点类型和边类型单一)设计.同质图中只有一种类型的节点和边(例如,只有朋友关系的社交网络),网络结构较为简单.因此,同质图神经网络通常只需要聚合单一类型的邻居来更新节点的表示即可(例如,通过在朋友关系下的邻居来更新节点表示). 但真实世界中的图大部分都可以被自然地建模为异质图(多种类型的节点和边,如下图所示,IMDB数据中包含三种类型的节点Actor、Movie和Director,两种类型的边Actor-Moive和Movie-Director). 多种类型的节点和丰富的语义信息给异质图神经网络设计带来了巨大挑战.

     与同质图不同,异质图通常需要需要考虑不同关系下邻居信息的差异. 因此,异质图神经网络通常采用层次聚合的方式: (1) 节点级别(下图(a)). 针对节点,找到其在某种关系下的邻居并聚合邻居信息来得到节点在某种关系下的表示. (2) 语义级别(下图(b)). 对多种关系(不同的边类型/元路径)下的节点表示进行融合,得到一个较为全面的节点表示. 元路径是一种节点间的连接模式,如上图中的Movie-Actor-Movie和Movie-Director-Moive.注意,不同类型的边关系(如Movie-Actor)可以认为是长度为1的元路径.

    接下来的章节,我们首先梳理了几种异质图神经网络的架构设计,然后介绍了异质图神经网络在的实际应用(NLP/推荐/恶意评论检测). 最后,附上了异质图分析的相关导师/论文/资料/数据集.

    2.模型

    2.1 19WWW  HAN-Heterogeneous Graph Attention Network

    本文由北京邮电大学联合清华大学和西弗吉尼亚大学发表在WWW2019上. 本文首次提出了基于注意力机制的异质图神经网络Heterogeneous Graph Attention Network(HAN),可以广泛地应用于异质图分析。作者也开源了相关的代码和数据 https://github.com/Jhy1993/HAN.

    HAN也遵循经典的异质图神经网络架构(节点级别聚合与语义级别聚合).为了更好的实现层次聚合函数,HAN利用语义级别注意力和节点级别注意力来同时学习元路径与节点邻居的重要性, 并通过相应地聚合操作得到最终的节点表示.这是一个很自然的想法,因为节点邻居的重要性或者是元路径的重要性肯定是有所差异的.如果能捕获这种差异性应该能带来一定的提升. 模型整体架构如下图所示:

    2.2 19KDD HetGNN-Heterogeneous Graph Neural Network

    本文与上篇Heterogeneous Graph Attention Network名字仅有一字之差,发表时间也仅仅相差3个月. Heterogeneous Graph Neural Network(HetGNN)也遵循异质图神经网络的层次聚合方式,只是聚合器的设计略有不同. 数据集和代码见https://github.com/chuxuzhang/KDD2019_HetGNN 模型整体框架如下如所示:

    与HAN不同, 本文的HetGNN没有考虑节点级别的注意力,而是用了LSTM作为聚合器来聚合某种关系下的节点邻居并更新节点表示. 这里的邻居选择也有所不同:通过random walk with restart来选择固定数量的邻居.

    2.3 19NeurIPS GTN-Graph Transformer Networks

    本文所提出的Graph Transformer Networks也遵循异质图神经网络的层次聚合.但是本文的重点并不在于聚合器的设计,而是解决异质图分析中的另个一重要问题:如何选取合适元路径? 异质图分析的很多文章都需要预先指定元路径(包括上述两篇文章), 但是这需要很强的先验知识.元路径选的好不好会极大的影响模型的效果.GTN可以自动的逐步生成对任务有用的元路径,省去了人工指定带来的偏差. 数据集和代码见 https://github.com/seongjunyun/Graph_Transformer_Networks 整个模型架构见下图:

    3 应用

    3.1 19EMNLP HGAT-Heterogeneous Graph Attention Networks for Semi-supervised Short Text Classification

    本文由北京邮电大学联合南洋理工大学发表在EMNLP2019, 是异质图神经网络在NLP中的应用. 数据集和代码见http://www.shichuan.org/dataset/HGAT.7z 针对短文本分类的稀疏/歧义和标签稀缺问题,通过将其建模为异质图来解决数据稀疏和歧义带来的挑战. 下图是作者在AG-News数据上建立的异质图.

    同时,本文提出了一种异质图注意力HGAT来学习短文本的表示并进行分类. HGAT也遵循异质图神经网络的层次聚合,并且利用层次注意力机制来实现更好的信息聚合.模型架构见:

    3.2 19KDD MEIRec-Metapath-guided Heterogeneous Graph Neural Network for Intent Recommendation

    本文由北京邮电大学联合阿里巴巴发表在KDD2019, 是异质图神经网络在推荐中的应用.针对淘宝业务的实际需求,本文将Intent Recommendation场景建模为一个大规模异质图,并提出了一种基于异质图神经网络的推荐算法MEIRec. 作者也给出了一个Intent Recommendation的例子,见下图

    本文所提出的MEIRec的核心思想是:设计一个异质图神经网络来学习user和query的表示。这里的异质图神经网络也遵循经典的层次聚合方式.下图展示了MEIRec的整个算法框架。

    可以看出,作者选择了QIU和IQU两条元路径来学习User的表示, 选择了QIU和IUQ来学习Query的表示. 这里将异质图神经网络应用于推荐时比较自然的: 淘宝的实际业务场景是天然的异质图,多条元路径可以更好地对节点进行描述.

    3.3 19CIKM GAS-Spam Review Detection with Graph Convolutional Networks

    本文由阿里巴巴发表在CIKM2019上,是异质图神经网络在垃圾评论中的应用.本文也获得了CIKM的最佳应用论文奖.

    作者将闲鱼上的恶意评论建模为一个大规模异质图(如下图所示),提出了一种GCN-based Anti-Spam (GAS)模型,可以实现高效准确的垃圾评论检测. 由于这里的图数据实际上只有User-Item之间的一种关系,GAS模型并没有遵循异质图神经网络经典的层次聚合, 只选取了一种元路径(User-Item)在节点层面来聚合邻居信息.

    4 总结

    图神经网络已经成为深度学习领域的热门研究方向之一.作为真实生活中广泛存在的异质图,其相应的异质图神经网络具有更高的实际研究价值. 下面通过一个表格来对比本文所整理所有算法.

    5 相关信息(导师/资料/论文/数据)

    5.1 国内外相关大牛老师:

    • Philip S. Yu(俞士纶), UIC教授兼清华数据科学研究院院长, ACM和IEEE院士,异质图分析倡导者,名列全球计算机科学领域高引作者前十的华人.主页 https://www.cs.uic.edu/~psyu/
    • Jiawei Han(韩家炜), UIUC教授,IEEE和ACM院士.曾担任KDD、SDM和ICDM等国际知名会议的程序委员会主席.个人主页 https://hanj.cs.illinois.edu
    • 石川老师, 北京邮电大学教授,智能通信软件与多媒体北京市重点实验室副主任,在Springer出版异质图分析方向第一部英文专著.个人主页http://www.shichuan.org/ShiChuan_ch.html
    • Yizhou Sun(孙怡舟), UCLA助理教授,发表异质图分析经典论文PashSim作者, 出版关于异质图分析专著Mining Heterogeneous Information Networks: Principles and Methodologies. 个人主页http://www.ccs.neu.edu/home/yzsun/Publications.htm
    • Yangqiu Song(宋阳秋), HKUST助理教授, WeChat-HKUST联合实验室副主任,其关于异质图分析的论文HinDroid获得了ACM SIGKDD 2017 Best Student Paper Award(Applied Data Science Track).个人主页 http://www.cse.ust.hk/~yqsong/
    • Yanfang Ye(叶艳芳), 凯斯西储大学副教授,曾任科摩多安全首席科学家,其关于异质图分析的论文HinDroid获得了ACM SIGKDD 2017 Best Student Paper Award(Applied Data Science Track).个人主页 https://cse.nd.edu/seminars/cse-seminar-series-fanny-ye

    5.2 相关资料/论文整理:

    Jhy1993/Representation-Learning-on-Heterogeneous-Graph​github.com

    5.3 相关数据集整理:

    https://github.com/Jhy1993/Datasets-for-Heterogeneous-Graph​github.com

    其他平台 我是如何寻找数据集的,一些个人私藏

    • Google 数据集

      • 谷歌为数据集专门开发的搜索系统,20年初就已经覆盖2500万的数据集。界面也非常简洁,输入关键词即可返回相对应的数据集描述,如下。

      • 链接:https://datasetsearch.research.google.com/

    • Huggingface数据集

      • NLP界网红抱抱脸家的数据集,主要是自然语言处理方面的数据。支持使用python直接调取,譬如squad_dataset = load_datasets("squad")。

      • 链接1:https://github.com/huggingface/datasets

      • 链接2:https://huggingface.co/datasets

    • Kaggle 数据集

      • Kaggle大家再熟悉不过了,比赛平台自然少不了数据啦。

      • 链接:https://www.kaggle.com/datasets

    • Paper With Code 数据集

      • 4075个机器学习相关数据集,相比于其他平台的优势是会将数据集和相应领域的paper和benchmark对应在一起。

      • 链接:https://www.paperswithcode.com/datasets

    • Reddit 数据集

      • Reddit是国外热门论坛,在dataset板块,可以搜索数据集。相比于其他平台不同的是,可以与其他人针对数据集一起讨论。

      • 链接:https://www.reddit.com/r/datasets/

    • CLUE 数据集

      • 虽然上述平台也会涵盖中文的数据集,但是可能并不全面。CLUE组织专门针对中文NLP数据搭建了一个平台,同时开源了许多中文大规模数据和预训练模型,点赞!!

      • 链接:https://www.cluebenchmarks.com/dataSet_search.html

    • 其他

      • https://www.datasetlist.com/

      • https://github.com/awesomedata/awesome-public-datasets

      • https://tinyletter.com/data-is-plural

      • https://jupyter-tutorial.readthedocs.io/en/latest/data/index.html

      • https://www.openml.org/search?type=data

      • https://github.com/InsaneLife/ChineseNLPCorpus

    6.其他相关

    1)EMNLP2019: 基于层次多图卷积网络的实体类型分类

    • EMNLP2019: Fine-Grained Entity Typing via Hierarchical Multi Graph Convolutional Networks

    • 论文链接: https://www.aclweb.org/anthology/D19-1502/

    • 代码: https://github.com/SIGKDD/HMGCN

    • 解读: 公众号机器学习研究组

    展开全文
    lj2048 2020-05-01 16:59:02
  • 3.43MB weixin_38750003 2021-06-10 12:52:32
  • 2.41MB weixin_38592847 2021-05-31 02:24:14
  • 101KB weixin_38722329 2021-05-20 13:08:50
  • 430KB weixin_38611459 2021-05-20 12:08:26
  • 1.27MB weixin_38743481 2019-09-20 21:31:03
  • 746KB weixin_38743481 2019-09-20 10:55:27
  • 论文题目:Heterogeneous Network Representation Learning: Survey, Benchmark, Evaluation, and Beyond 论文来源:arXiv 2020.04.01 论文链接:https://arxiv.org/abs/2004.00216 ...关键词:异质...

    论文题目:Heterogeneous Network Representation Learning: Survey, Benchmark, Evaluation, and Beyond

    论文来源:arXiv 2020.04.01

    论文链接:https://arxiv.org/abs/2004.00216

    代码链接:https://github.com/yangji9181/HNE

    关键词:异质网嵌入,综述,benchmark


    异质网的嵌入学习方法(HNE)已经被广泛应用,但还没有一篇详细的综述。

    本文的贡献如下:

    (1)本文提出了一个统一的范式,对各种现有的HNE算法的优点进行系统的分类和分析

    (2)本文还从不同来源创建了4个具有不同属性的基线数据集,包括规模、结构、属性/标签可用性等,以更全面地评估HNE算法。

    (3)重构并修正了10个HNE流行算法接口的实现。并在多个任务和不同的实验设置下对其进行了全方位的比较。



    1 Generic Paradigm


    1.1 问题定义

    (1)网络嵌入(Network embedding)

    给定图 G = { V , E } G={\{V, E}\} G={V,E} V V V是节点集合, E E E是边集合。网络嵌入就是一个将节点映射成低维向量表示的函数: Φ : V → R ∣ V ∣ × d \Phi : V\rightarrow \mathbb{R}^{|V|\times d} Φ:VRV×d d d d远小于 ∣ V ∣ |V| V。映射函数 Φ \Phi Φ定义了每个节点的隐层表示,表示中含有从边集 E E E中捕获到的图的结构信息。

    在多数情况下,网络相似性(network proximity)是需要捕获的主要拓扑信息。例如,DeepWalk就捕获到了基于随机游走的节点相似性。随后有各种工作对DeepWalk进行了改进和扩展,这不属于本文的范围,DeepWalk是应用于同质图的,本文关注的是异质图的表示学习。

    (2)异质网(Heterogeneous network)

    异质网 H = { V , E , ϕ , ψ } H={\{V, E, \phi, \psi}\} H={V,E,ϕ,ψ}有多种类型的节点和边。 H H H中,每个节点 v i v_i vi都对应一种节点类型 ϕ ( v i ) \phi(v_i) ϕ(vi),每个边 e i j e_{ij} eij都对应一种边类型 ψ ( e i j ) \psi(e_{ij}) ψ(eij)。边的类型自动定义了其两端节点的类型。

    (3)元路径(Meta-path)

    元路径是定义在network schema上的由不同类型的节点和边组成的序列。

    每个元路径都从特定的语义角度捕获到了其两端节点的相似性。使用不同的元路径就可以使得模型计算到多模多类型的节点相似性和关系,有助于学习到更丰富的节点表示。

    (4)异质网嵌入(Heterogeneous network embedding)

    给定一个异质图 H H H,异质网嵌入就是一组映射函数: { Φ k : V k → R ∣ V k ∣ × d } k = 1 K {\{\Phi_k: V_k\rightarrow \mathbb{R}^{|V_k|\times d}\}}^K_{k=1} {Φk:VkRVk×d}k=1K。其中 K K K是节点类型的数量, ∀ v i ∈ V k , ϕ ( v i ) = k \forall v_i \in V_k, \phi(v_i)=k viVk,ϕ(vi)=k。映射函数 Φ k \Phi_k Φk定义了类型为 k k k的所有节点的隐层表示,捕获到了 E E E中关于异质边的网络拓扑信息。


    1.2 提出的范式

    HNE一个最重要的原则就是趋同性。在网络嵌入中,趋同性可以解释成“在网络中相近的节点应该有相似的嵌入表示”。

    事实上,我们进一步发现了同质性原理和在网络上广泛使用的平滑实施技术之间的内在联系,提出了一个通用的数学范式,涵盖了大多数现有的和可能的许多未来的HNE算法。

    作者引入如下的目标函数

    其中, e u = Φ ( u ) , e v = Φ ( v ) e_u=\Phi(u), e_v=\Phi(v) eu=Φ(u),ev=Φ(v)是需要学习得到的节点嵌入向量。 w u v w_{uv} wuv是权重, d ( ⋅ , ⋅ ) d(\cdot, \cdot) d(,)是计算嵌入向量间距离的函数, J R \mathcal{J}_R JR是附加的目标函数(例如正则化),在不同的HNE算法中,对这三项的定义不同。


    2 算法分类


    我们使用一个统一的分类方法,将现有的HNE算法基于它们的目标分为3类,并且解释它们都符合式(1)的范式

    2.1 Proximity-Preserving 方法

    网络嵌入的一个基本目标就是捕获到网络的拓扑信息保留不同类型节点间的相似度可以实现这一目标。HNE中相似度保留(proximity preserving)方法可分成两类:(1)受DeepWalk启发的基于随机游走的方法(2)受LINE启发的基于一阶/二阶相似度的方法


    2.1.1 基于随机游走的方法

    (1)metapath2vec

    metapath2vec使用了由元路径指导的随机游走得到的节点组成的路径,考虑到异质的语义信息,来建模节点的上下文。给定元路径 M \mathcal{M} M在第 i i i步的转移概率定义为

    其中, N l ( v ) = { u ∣ ψ ( u , v ) = l } \mathcal{N}_l(v)={\{u|\psi(u, v)=l}\} Nl(v)={uψ(u,v)=l}为通过类型为 l l l的边和节点 v v v相连接的邻居节点。假定 P = { P 1 , . . . , P M } \mathcal{P}={\{\mathcal{P}_1,..., \mathcal{P}_M}\} P={P1,...,PM}是随机游走生成的一组序列。则metapath2vec的目标函数为:

    其中, C ( v ) \mathcal{C}(v) C(v) v v v P \mathcal{P} P中的上下文。例如,若 P 1 = v 1 v 2 v 3 v 4 v 5 . . . \mathcal{P}_1=v_1v_2v_3v_4v_5... P1=v1v2v3v4v5...,上下文窗口大小为2,则 { v 1 , v 2 , v 4 , v 5 } ⊆ C ( v 3 ) {\{v_1, v_2, v_4, v_5}\}\subseteq \mathcal{C}(v_3) {v1,v2,v4,v5}C(v3)。令 w u v w_{uv} wuv记为在 P \mathcal{P} P u ∈ C ( v ) u\in \mathcal{C}(v) uC(v)出现的次数,将式(3)重写为如下的形式:

    分母需要对所有节点进行计算求和,计算量很大。在实际的计算中,通常使用负采样进行近似


    (2)HIN2Vec

    HIN2Vec是考虑节点 u , v u,v u,v间存在元路径 M \mathcal{M} M的可能性

    其中, 1 \mathbf{1} 1是全1的向量, ⊙ \odot 是Hadamard乘积, f 01 f_{01} f01是正则化函数。 e u = W X T u , e v = W X T v , e M = f 01 ( W R T m ) e_u=W^T_Xu, e_v=W^T_Xv, e_{\mathcal{M}}=f_{01}(W^T_Rm) eu=WXTu,ev=WXTv,eM=f01(WRTm)可视为 u , v , M u, v, \mathcal{M} u,v,M的嵌入表示。令 A M = d i a g ( e M 1 , . . . , e M d ) \mathbf{A}_{\mathcal{M}}=diag(e_{\mathcal{M}1},..., e_{\mathcal{M}d}) AM=diag(eM1,...,eMd),有:

    其中, σ \sigma σ是sigmoid函数,于是有:

    HIN2Vec忽略节点/边的类型,使用同质的随机游走生成了多个正的三元组样本 ( u , v , M ) (u, v, \mathcal{M}) (u,v,M)。对于每个正样本,将 u u u随机替换成 u ′ u^{'} u,生成多个负样本。目标函数为:

    这其实就是对如下目标函数的负采样近似值:

    其中 w u v M w^{\mathcal{M}}_{uv} wuvM是在元路径为 M \mathcal{M} M的前提下,节点 u , v u, v u,v间的路径实例数。


    (3)SHINE

    SHINE在metapath2vec的基础上记性了改进,考虑到了附加的节点信息。一些类型的节点可能有附加的文本信息(定义为 x v x_v xv)。它提出了基于GRU的深层编码函数 f E N C f_{ENC} fENC。若 v v v有文本信息,则 e v = f E N C ( x v ) e_v=f_{ENC}(x_v) ev=fENC(xv);否则, e v e_v ev就表示可训练的节点嵌入。

    SHINE的目标函数和metapath2vec一样,它还可以通过利用特定领域的深层编码器,直接扩展到其他类型的节点信息,例如类别属性值、图像等。


    其他的基于随机游走的方法总结到了表1中。MRWNN将内容先验整合到了DeepWalk嵌入中;HHNE将metapath2vec扩展到了双曲空间;GHE提出了一种半监督的元路径加权技术;MNE在多视图网络中对每个视图分别进行随机游走;JUST提出Jump/Stay随机游走,不依赖于预先定义的元路径。


    2.1.2 基于一阶/二阶相似度的方法

    (1)PTE

    PTE提出将异质网分解为多个二部图,每个都描述了一种类型的边。它的目标函数是对所有二部图的对数似然的和:

    其中, T E \mathcal{T}_E TE是边类型的集合; w u v l w^l_{uv} wuvl是节点对 ( u , v ) (u, v) (u,v)间类型为 l l l的边所对应的权重(若 u , v u, v u,v间没有类型为 l l l的连边,则该值为0); w u v = ∑ l w u v l w_{uv}=\sum_l w^l_{uv} wuv=lwuvl是节点 u , v u, v u,v间边的权重之和。


    (2)AspEm

    AspEm假定每个异质图都有多个角度(aspects),将每个角度定义成network schema的一个子图。AspEm还提出了一个不兼容的度量,以为嵌入学习选取合适的角度。给定一个角度 a a a,目标函数为:

    其中, T E a \mathcal{T}_E^a TEa是角度 a a a下的边集合; Z l = ∑ u , v w u v l Z_l=\sum_{u, v}w^l_{uv} Zl=u,vwuvl是为了规范化的参数; e u , a e_{u, a} eu,a是节点 u u u在特定角度下的嵌入表示。


    (3)HEER

    HEER是PTE的扩展,它考虑到了typed closeness。类型为 l l l边有嵌入表示 μ l \mu_l μl。目标函数为:

    其中, g u v g_{uv} guv是边 ( u , v ) (u, v) (u,v)的嵌入表示; P l ( u , v ) = { ( u ′ , v ) ∣ ψ ( u ′ , v ) = l } ∪ { ( u , v ′ ) ∣ ψ ( u , v ′ ) = l } P_l(u, v)={\{(u^{'}, v)| \psi(u^{'}, v)=l}\} \cup { \{(u, v^{'})| \psi(u, v^{'})=l}\} Pl(u,v)={(u,v)ψ(u,v)=l}{(u,v)ψ(u,v)=l}。HEER原文中的 g u v g_{uv} guv基于Hadamard乘积针对有向边和无向边有不同的定义。本文为了总结的简化,我们假定 g u v = e u ⋅ e v g_{uv}=e_u\cdot e_v guv=euev。令 A l = d i a g ( μ l 1 , . . . , μ l d ) A_l=diag(\mu_{l1},..., \mu_{ld}) Al=diag(μl1,...,μld),则有 μ l T g u v = e u T A l e v \mu^T_lg_{uv}=e^T_uA_le_v μlTguv=euTAlev和目标函数:


    其他的基于一阶/二阶相似度的方法总结到了表1中。HNE模型中引入了一个节点的类型感知的内容编码器(node type-aware content encoder);CMF在分解得到的二部图中进行了联合的矩阵分解;HEBE考虑到了每个元路径,保留了相似性信息;Phine面向半监督的训练,结合了额外的正则化;MVE提出基于attention的框架,考虑到了同一节点的多个视角。


    还有一些研究采取了其他形式的目标函数描述一阶/二阶相似性。例如,SHINE受SDNE的启发,使用自动编码器的重构损失作为目标函数;DRL提出在每一步学习一种类型的边,并使用深度强化学习的方法选择下一步的边类型;HINSE基于不同元路径的邻接矩阵,采用谱嵌入的方法;HeGAN使用关系类型感知的判别器,提出对抗学习的框架。


    基于上述讨论,大多数proximity-preserving方法可以定义为

    其中, w u v w_{uv} wuv是针对特定元路径 M \mathcal{M} M或者是针对类型为 l l l的边的,可表示为 w u v M w^{\mathcal{M}}_{uv} wuvM w u v l w^l_{uv} wuvl J R 0 \mathcal{J}_{R0} JR0是针对特定算法的正则化函数(表1中有总结); s ( u , v ) s(u, v) s(u,v)是节点 u , v u, v u,v间的相似度度量函数。

    在大多数情况下,可以将 s ( u , v ) s(u, v) s(u,v)写成 f ( e u ) T f ( e v ) f(e_u)^Tf(e_v) f(eu)Tf(ev)。例如metapath2vec、PTE f ( e u ) = e u f(e_u)=e_u f(eu)=euHIN2Vec f ( e u ) = A M e u f(e_u)=\sqrt{A_{\mathcal{M}}e_u} f(eu)=AMeu HEER f ( e u ) = A l e u f(e_u)=\sqrt{A_{\mathcal{l}}e_u} f(eu)=Aleu 。在这些方法中,目标函数可形式化为

    第二步得出是因为 ∣ ∣ x − y ∣ ∣ 2 = ( x − y ) T ( x − y ) = ∣ ∣ x ∣ ∣ 2 + ∣ ∣ y ∣ ∣ 2 − 2 x T y ||x-y||^2=(x-y)^T(x-y)=||x||^2+||y||^2-2x^Ty xy2=(xy)T(xy)=x2+y22xTy。因此,我们的目标等价于

    其中, J R 1 \mathcal{J}_{R1} JR1 J R 2 \mathcal{J}_{R2} JR2是两个正则化函数。没有 J R 1 \mathcal{J}_{R1} JR1时,让 ∣ ∣ f ( e v ) ∣ ∣ → 0 ||f(e_v)||\rightarrow 0 f(ev)0可以最小化 d ( e u , e v ) d(e_u, e_v) d(eu,ev);没有 J R 2 \mathcal{J}_{R2} JR2时,让 e v ≡ c , ( ∀ v ∈ V ) e_v\equiv c, (\forall v\in V) evc,(vV)可以最小化 d ( e u , e v ) d(e_u, e_v) d(eu,ev)

    式(1)中的 J R \mathcal{J}_R JR − J R 0 , − J R 1 , J R 2 -\mathcal{J}_{R_0}, -\mathcal{J}_{R_1}, \mathcal{J}_{R_2} JR0,JR1,JR2的和。表1中总结了 w u v , d ( e u , e v ) , J R 0 w_{uv}, d(e_u, e_v), \mathcal{J}_{R0} wuv,d(eu,ev),JR0的不同选择。


    2.2 Message-Passing 方法

    网络中的每个节点都可能有属性信息,表示为 x u x_u xu消息传递(Message-passing)的方法目的就是通过聚合来自节点 u u u的邻居的信息以及节点 u u u自身的属性信息 x u x_u xu学习得到节点嵌入表示 e u e_u eu。近些年的研究中,GNN被广泛用于消息的聚合和传递过程。

    (1)R-GCN

    R-GCN有 K K K层卷积,初始的节点表示 h u ( 0 ) h^{(0)}_u hu(0)是节点的特征 x u x_u xu在第 k k k层卷积,每个节点向量表示是通过聚合邻居节点的信息得到的

    和传统的GCNs不同,R-GCN考虑到了边的异质性为每种类型的边都学习到了一个矩阵 W W W。在消息传递时,同一类型的边的邻居先被聚合并归一化。第 K K K层的输出 e v = h v ( K ) e_v=h^{(K)}_v ev=hv(K)就是节点嵌入。

    无监督的实验设置中,消息传递方法使用链接预测作为下游任务,最大化异质网中出现边的似然,来对GNNs进行训练。R-GCN使用负采样交叉熵损失,对如下的目标函数进行近似:

    其中 w u v l = 1 ( u , v ) ∈ E 1 w^l_{uv}=\mathbf{1}_{(u,v)\in E_1} wuvl=1(u,v)E1


    (2)HAN

    HAN没有直接使用一阶邻居,而是使用元路径来建模更高阶的相似性。给定一个元路径 M \mathcal{M} M,节点 u u u的表示是从基于该元路径的邻居聚合的,邻居节点为: N M ( u ) = { u } ∪ { v ∣ v 通 过 元 路 径 M 和 u 相 连 } \mathcal{N}_{\mathcal{M}}(u)={\{u}\}\cup {\{v| v通过元路径\mathcal{M}和u相连}\} NM(u)={u}{vvMu}。HAN提出注意力机制为不同的邻居学习到不同的权重:

    其中, a M a_{\mathcal{M}} aM是元路径 M \mathcal{M} M下节点级别的注意力向量; x u ′ = M ϕ ( u ) x u x^{'}_u=M_{\phi(u)}x_u xu=Mϕ(u)xu是节点 u u u映射后的特征向量; ∣ ∣ || 表示连接操作。

    给定特定元路径下的嵌入 h u M h^{\mathcal{M}}_u huM,HAN使用语义级别的注意力为不同的元路径分配不同的权重:

    其中 q q q是语义级别的注意力向量。

    最近,有学者提出HGDI来提升基于HAN的无监督训练效果;HGT的提出实现了对动态图进行时间编码以及在大规模数据上进行mini-batch的采样

    因为HAN是为半监督的节点分类问题设计的,当需要在无监督的情况下学习节点嵌入时(就像许多的proximity-preserving方法),我们通常采用链接预测任务的损失函数,例如R-GCNGraphSAGE


    (3)HetGNN

    HetGNN假定每个节点都和不同的特征相关联,例如类别、文本、图像。它首先将每个节点的内容信息编码成向量 h u s h^s_u hus,然后使用节点的类型感知(node type-aware)的聚合函数从邻居节点收集信息:

    其中 N R W R ( v ) \mathcal{N}_{RWR}(v) NRWR(v)是使用带重启的随机游走得到的节点 v v v的邻居。HetGNN对不同类型的邻居节点使用注意力机制,以得到最终的嵌入,和HAN的思想一致:

    HetGNN的损失函数和PTE的一样


    还有一些其他的message-passing方法。例如HEP从邻居 N o ( u ) \mathcal{N}_o(u) No(u)(例如 节点类型感知的邻居)进行聚合得到 u u u的表示,应用于电商平台的用户对齐;GATNE从邻居 N l ( u ) \mathcal{N}_l(u) Nl(u)(例如 边类型感知的邻居)进行聚合得到 u u u的表示,应用于transductive和inductive的网络嵌入学习。

    上述的message-passing方法也可以写成式(4)的形式,其中 s ( u , v ) s(u, v) s(u,v)是关于 e u , e v e_u, e_v eu,ev的函数。唯一的不同之处在于,这里的 e u e_u eu是使用GNNs从 x v x_v xv聚合得到的。若我们仍将 J R \mathcal{J}_R JR写成式(1)中 − J R 0 , − J R 1 , J R 2 -\mathcal{J}_{R_0}, -\mathcal{J}_{R_1}, \mathcal{J}_{R_2} JR0,JR1,JR2的和,则可以得到如式(5)所示的相同的 J R 1 , J R 2 \mathcal{J}_{R_1}, \mathcal{J}_{R_2} JR1,JR2

    在这组算法中,只有HEP使用了额外的重构损失 J R 0 = ∑ v ∣ ∣ e v − h v ∣ ∣ 2 \mathcal{J}_{R_0}=\sum_v ||e_v-h_v||^2 JR0=vevhv2其他所有的算法中都有 J R 0 = 0 \mathcal{J}_{R_0}=0 JR0=0。我们将 w u v , d ( e u , e v ) w_{uv}, d(e_u, e_v) wuv,d(eu,ev)和聚合函数的不同选择,总结在了表2中。


    2.3 Relation-Learning 方法

    异质网中的每个边都可以看成一个三元组 ( u , l , v ) (u, l, v) (u,l,v),其中 u , v u, v u,v是节点, l ∈ T E l\in \mathcal{T}_E lTE是边的类型(例如 KG中的实体和关系)。

    relation-learning方法的目标是学习到一个打分函数 s l ( u , v ) s_l(u, v) sl(u,v),对任意一个三元组进行评估,衡量这个三元组可接受性。这一思想广泛用于KB的嵌入学习。已经有了KB嵌入学习算法的综述,我们在这里只考虑最流行的方法并且突出它们和HNE的关联。

    (1)TransE

    TransE假定若存在三元组 ( u , l , v ) (u, l , v) (u,l,v),则有这样的嵌入变换: e u + e l = e v e_u + e_l = e_v eu+el=ev。因此TransE的打分函数就定义为: s l ( u , v ) = − ∣ ∣ e u + e l − e v ∣ ∣ p , p = 1 或 2 s_l(u, v)=-||e_u+e_l-e_v||_p, p=1或2 sl(u,v)=eu+elevp,p=12。目标函数就是最小化一个margin-based ranking loss

    其中, T T T是正的三元组样本集合, T ( u , l , v ) ′ T^{'}_{(u, l, v)} T(u,l,v)是将 u u u v v v随机替换得到的负的三元组样本集合:

    TransE是使用"a translational distance"来定义打分函数的最具代表性的模型。它的扩展TransH, TransR, RHINE等。


    (2)DistMult

    和translational distance的模型不同,DistMult使用了基于相似性的打分函数。每个关系都用一个对角矩阵 A l = d i a g ( e l 1 , . . . , e l d ) A_l=diag(e_{l1},...,e_{ld}) Al=diag(el1,...,eld)表示, s l ( u , v ) s_l(u,v) sl(u,v)使用双线性函数定义:

    注意,对于任意的 u , v u, v u,v,都有 s l ( u , v ) = s l ( v , u ) s_l(u,v)=s_l(v,u) sl(u,v)=sl(v,u)。因此DistMult主要用于对称的关系数据。

    除了DistMult,RESCAL也是用双线性的打分函数,但是不将 A l A_l Al限制为对角阵


    (3)ConvE

    ConvE不使用简单的距离或相似性函数,而是提出了深层的神经模型为三元组打分。分值由在2D的嵌入上的卷积决定

    其中, E u , E r E_u, E_r Eu,Er分别表示节点嵌入和关系嵌入的2D矩阵," ∗ * "是卷积操作。

    其他使用深度神经网络作为打分函数的模型包括:NTN,CACL,SACN,NKGE等。


    所有上述提到的基于relation-learning的嵌入算法都采用了式(6)的margin-based ranking loss,再加上一些正则项,作为损失函数:

    有学者提出基于margin的损失和如下的负采样损失有着相似的形式:

    使用负采样损失重写式(7),就可以近似成最大化如下的式子:

    • 对于translational distance模型 s l ( u , v ) s_l(u, v) sl(u,v)是通过距离描述的,等价于:

    此例中,可将 J R \mathcal{J}_R JR写成 − J R 0 + J R 1 -\mathcal{J}_{R_0}+\mathcal{J}_{R_1} JR0+JR1

    • 对于neural triplet scores s l ( u , v ) s_l(u, v) sl(u,v)的形式比内积或者距离更加复杂。在这些情况下,因为距离和相似度可以看成相反的度量,我们将 d ( e u , e v ) d(e_u, e_v) d(eu,ev)定义成 C − s l ( u , v ) C-s_l(u, v) Csl(u,v),其中 C C C s l ( ⋅ , ⋅ ) s_{l}(\cdot, \cdot) sl(,)的上界,是一个常数。则损失函数和式(8)就相似了,仍有 J R = − J R 0 + J R 1 \mathcal{J}_R=-\mathcal{J}_{R_0}+\mathcal{J}_{R_1} JR=JR0+JR1

    我们将 w u v l , d ( e u , e v ) , J R 0 w^l_{uv}, d(e_u, e_v), \mathcal{J}_{R_0} wuvl,d(eu,ev),JR0的不同选择总结到了表3中。注意,对于relation-learning方法, d ( ⋅ , ⋅ ) d(\cdot, \cdot) d(,)也许不是一个距离的度量。例如在许多translational distance模型中, d ( e u , e v ) ≠ d ( e v , e u ) d(e_u, e_v)\neq d(e_v, e_u) d(eu,ev)=d(ev,eu)。这是因为 ( u , l , v ) (u, l, v) (u,l,v) ( v , l , u ) (v, l ,u) (v,l,u)通常表达了不同的语义。


    3 Benchmark


    3.1 数据集的准备

    我们整理并公开了4个来源于不同领域的真实的异质网数据集,旨在为现有的和未来的HNE算法建立一个benchmark。


    (1)DBLP

    我们从DBLP构建了一个含有authors, paper, venues, phrases的网络。Phrases是使用流行的AutoPhrase算法,从论文文本抽取的,并且专家对其进行了进一步的筛选过滤。

    我们对所有的论文文本进行了word2vec的计算,生成了300维的paper和phrase的特征。author和venue的特征是通过聚合它们对应的的paper特征得到的。我们还采用爬虫技术,将一小部分author手动标记成来自4个研究领域的12个研究小组。


    (2)Yelp

    我们从Yelp构建了由businesses,users,locations,reviews构成的网络。节点没有特征,但是大部分的businesses都有16类中的一类或多类的标签


    (3)Freebase

    从Freebase构建了由books,films,music,sports,people,locations,organizations,businesses组成的网络。节点没有特征,但大部分的books都属于8类中的一类


    (4)PubMed

    从PunMed构建了由genes,diseases,chemicals,species组成的网络。所有的节点都是通过AutoPhrase抽取得到的,由AutoNER打标签,然后由专家进行进一步的过滤。

    我们在PubMed所有的papers上进行了word2vec的计算,为所有类型的节点生成了200维的单词嵌入。还将一小部分的diseases分成了8类,每个disease只有一个标签


    3.2 结构分析

    这4个数据集统计为表4图3所示。

    作者还对这些异质网的属性进行了分析,有度分布(图4)、聚合系数(图5)、频繁元路径的数量(图6)。根据度分布进行节点采样,度分布可以显著影响HNE算法的性能。聚类系数对使用潜在的社区结构的HNE算法带来影响。由于许多HNE算法依赖于元路径,元路径的skewer distribution可能偏向于使用较少元路径的算法。

    对于这4个数据集,我们关注到的属性是不一样的。例如,Yelp中有更多紧密的链接和更多的标签;Freebase和PubMed中的节点有鲜明的长尾度分布;DBLP和Yelp中特定类型的节点连接地较好(例如 DBLP中的phrase,Yelp中的businesses),形成了更多的星型结构(star-shaped)的子图;type-wise的聚类系数和元路径分布在DBLP中偏斜最严重,在PubMed中最均衡。

    这4个数据集为各种HNE算法的鲁棒性和通用性提供了一个全面的基准。(4.2节中有介绍)


    3.3 设置,任务和度量

    对所有数据集设置成无监督无属性的HNE,主要对10种算法进行比较,目的是保留异质网中不同类型的边。

    (1)对于为属性网和半监督的HNE特别设计的message-passing算法,在相应的设置下对它们进行了额外的实验。在DBLP和PubMed数据集上进行了带属性的HNE的评估,在Yelp和Freebase上进行了半监督HNE的评估。在节点分类链接预测两个任务上测试学习得到的网络嵌入表示。将所有算法得到的嵌入维度设为50,在所有数据集上使用标准的5折交叉验证对超参数进行微调。

    (2)对于标准的无属性无监督的HNE算法,随机隐藏20%的边,使用剩余80%的边训练所有的HNE算法。

    • 对于节点分类任务,基于使用80%有标注的节点训练学习得到的嵌入,训练一个分离的线性SVM(LinearSVC),以预测剩余的20%的节点标签。重复5次这一过程对所有的得分取平均,得到macro-F1和micro-F1

    • 对于链接预测任务,使用Hadamard函数重构节点对的特征向量,在80%的链接数据集上训练一个二分类的LinearSVC,在剩余的20%的数据集上进行评估。同样的,重复5次这一过程,得到AUC(ROC曲线下的面积)和MRR(mean reciprocal rank)两个度量。AUC是分类问题的标准度量,我们将链接预测视为了二分类问题。MRR是排序问题的标准度量,我们将链接预测视为了链接检索问题。对所有的节点对进行计算,这个计算量太大了,所以通常使用两跳(two-hop)的邻居作为所有节点的候选

    (3)对于带属性的HNE,节点特征用于HNE算法的训练过程。对于半监督的HNE,只使用特定数量的节点标签(默认是80%)。


    4 实验评估


    4.1 Algorithms and Modifications

    我们修改了10个流行的HNE算法以在我们准备的数据集上进行有效的实验评估。我们选择的算法和进行的修改如下:


    (1)metapath2vec

    原始的实现版本包含大量的hard-coded的特定数据的设置,例如节点类型和元路径。并且优化是不稳定的和受限的,因为它仅仅检测了基于元路径的一种类型的上下文。作者重新实现了该方法。

    首先,进行随机游走,基于采样的实例数目学习到不同元路径的权重。然后使用统一的损失函数训练模型,损失函数是对所有元路径的损失进行加权求和得到的。

    随机游走和基于元路径的嵌入优化都是通过多线程并行实现的。


    (2)PTE

    原先的方法是将有标签的文本作为输入,只能用于有三种特定类别节点(word, document, label)和三种特定类别边(word-word, document-word, label-word)的文本网络。作者将原始版本进行了修正,使得模型能直接用于有任意类型的节点和边的异质网。


    (3)HIN2Vec

    作者去除掉了不必要的数据预处理代码,对原始的版本进行了修改,使得程序先进行随机游走,然后对模型进行训练,最终只输出节点的嵌入表示


    (4)AspEm

    作者去除了原始版本中hard-coded特定数据的设置,编写了script将自动选择aspects的不同组成部分相连接,并实现了不兼容性的最小化。还同时连接了基于不同aspects的嵌入的学习、配对、拼接。


    (5)HEER

    作者去除了原始版本中hard-coded特定数据的设置,跳过了knockout步骤并理顺了图建立的过程,实现了数据预处理的简化


    (6)R-GCN

    现有的DGL的实现版本由于在图卷积过程需要将整张图输入到内存中,只能扩展到有上千个节点的异质网。为了使得R-GCN能扩展到大规模的数据,作者采用了固定大小的节点和边的采样,像GraphSage一样,用于batch-wise训练。


    (7)HAN

    HAN的原始实现版本包含了大量hard-coded特定数据的设置,例如节点类型和元路径,并且和R-GCN一样不能扩展到大规模的数据集。作者在R-GCN实现的基础上重新实现了HAN算法

    具体来说,我们首先根据所选的节点类型,基于adjacency lists自动构建元路径。然后在batch-wise的训练过程中为seed nodes采样邻居。


    (8)TransE

    修改了OpenKE的实现,使得模型只输出节点的嵌入表示


    (9)DistMult

    作者去除了原始版本中hard-coded特定数据的设置,和原始版本相比极大地简化了数据预处理


    (10)ConvE

    同DistMult。


    作者公开了提出的4个数据集,以及上述所有方法的实现代码,组成了开源的易使用的HNE benchmark。

    https://github.com/yangji9181/HNE


    4.2 Performance Benchmarks

    在我们整理的4个数据集上,对上述的10个流行的state-of-the-art的HNE算法进行了实验对比。实验情景有:无监督无属性的HNE带属性的HNE半监督的HNE

    表5展示了无监督无属性的HNE节点分类链接预测任务上的对比结果。

    表5中可以看出:


    (1)proximity-perserving算法无监督无属性的HNE设置下,通常在两个任务中都有较好的表现。这也就解释了为什么proximity-perserving算法是应用最广泛的HNE。

    在proximity-perserving方法中,HIN2VecHEER在链接预测任务中表现出了很好的效果,但是在节点分类问题上表现欠佳(尤其是在DBLP和Freebase数据集上)。实际上这两个方法的目标主要是对边的表示进行建模(HIN2Vec中的 A M A_{\mathcal{M}} AM,HEER中的 A l A_l Al),所以更适用于链接预测任务


    (2)在无监督无属性的HNE设置下,message-passing方法表现不好,尤其是在节点分类任务中。正如我们前面所讨论过的,message-passing方法集成了节点属性、链接结构和训练标签。当节点属性和标签都没有的时候,我们使用随机的向量表示作为节点特征,并且使用链接预测的损失,这极大地限制了R-GCN和HAN的表现能力。后面将关注着两个算法在有属性的和半监督的HNE设置下的表现。

    HANYelp数据集上的链接预测结果甚至不可得。这是因为HAN只能预测同类型的两节点间的连边(例如 business-business),但是Yelp中所有的连边连接的都是不同类型的节点(例如 business-user)。


    (3)Relation-learning方法在Freebase和PubMed数据集上,两个任务的表现更好,尤其在链接预测任务中表现更好。在表4图3中我们可以观察到这两个数据集,尤其是Freebase数据集,有更多种类型的边。Relation-learning方法主要是为KG的嵌入学习设计的(例如 Freebase),可以更好地捕获到不同种类的有向连接的语义信息


    数据集的角度:


    (1)所有的方法在Yelp和Freebase的节点分类任务上都有较低的F1值,尤其是Yelp。这是因为这两个数据集都有大量的节点标签,Yelp中是16个,Freebase是8个。

    而且,和其他的数据集不同的是,Yelp中的节点可以有多个标签,这使得分类任务更具挑战。


    (2)图4中可以看出Freebase的度分布更加偏斜。这就会导致在Freebase上进行边的采样或者随机游走时,度数较小的节点被采样的频率越低,它们的表示就不能准确地学习到。

    这一发现就能解释为什么链接预测在Freebase上的度量结果普遍比DBLP和Yelp上的低。


    (3)从图3-6可以看出,网络属性在Freebase和PubMed上更加均衡(尤其是在PubMed上)。对于所有算法,这使得节点分类和链接预测任务更加困难,同样使得不同算法间的效果差异变小。


    为了提供不同HNE算法深层次的性能比较,我们进一步对实验参数进行了控制

    图7中展示了在PubMed数据集上进行节点分类链接预测的结果。可以看出,不同的嵌入维度和link removal率可以对大多数算法的结果产生显著影响。这再次说明了建立包括数据集和评估协议在内的标准基准对系统HNE算法评估的重要性。

    PubMed数据集上,大于50维度的嵌入会损害大多数算法的表现性能,尤其是在节点分类任务上。这可能是由于在有限的数据维度和标签情况下产生了过拟合。有意思的是,随机去除掉连边并没有对链接预测任务的效果产生有害的影响,并且没有对节点分类的预测结果带来必然的损害。

    这意味着节点的类别连接的结构可能并不总是强相关联的,甚至连接的一部分已经为节点分类提供了最大程度的有用信息。


    针对目前将节点属性和标签整合到R-GCN、HAN等嵌入学习中的HNE算法评价,我们还通过在节点属性中加入随机高斯噪声掩蔽(mask)不同数量的训练标签进行了控制实验。

    图8展示了在PubMed数据集上的结果。从中可以看出,所有子图中的得分都比表5中的高,这表示了R-GCN和HAN在整合节点属性和标签方面的有效性

    将方差更大的随机噪声添加到节点属性时节点分类的性能显著下降,但是链接预测的性能受的影响很小。当可获得的训练标签更多时,所有算法都在节点分类任务上得到了显著的提升,但是链接预测任务几乎不受影响

    这一发现有一次证实了这两个任务有着不同的天然特性节点类别可以从节点内容和连接结构等多个信号中推断得出,而链接只和其他链接有关联性


    5 Future

    文本对多个现有的HNE算法进行了分类,并提供了benchmark数据集和baseline方法,以易于这一方向后续工作的开展。接下来简单讨论一下当前HNE的局限性值得探索的几个方向

    (1)Beyond homophily(趋同性)

    正如式(1)所示,当前的HNE算法利用了网络的趋同性。最近的针对同质图的研究结合了位置(positional)和结构(structural)的嵌入,未来可以探索如何将这样的设计和范式推广到HNE中。

    特别地,在异质图中,相对位置节点的结构角色使用不同的meta-paths或meta-graphs进行度量,这就可以利用更丰富的信息。但是,这样的考虑同样引入了有关计算难度的挑战。


    (2)Beyond accuracy

    大多数现有的HNE方法只是关注于算法在下游任务的准确率。未来应该进一步研究HNE的高效性(efficiency)和可扩展性(scalability),时间适应性(用于动态网络),鲁棒性(面向对抗攻击),可解释性不确定性(uncertainty),公平性(fairness)。


    (3)Beyond node embedding

    已经有同质图上针对图级别的和子图级别嵌入算法的相关研究,但是很难在异质图上应用。尽管HIN2Vec研究了元路径的嵌入,以提升节点的嵌入表示。但是直接应用异质网的上下文图级别和子图级别的嵌入学习还有待进一步研究。


    (4)Revisiting KB embedding

    KB嵌入HNE主要区别在于节点和连边类型的数量。直接将KB的嵌入学习方法用于异质网的话,没有考虑到有丰富语义信息的元路径,直接将HNE应用到KB也是不现实的,因为KB元路径的数量是指数级别的。

    未来可以研究这两组方法和这两种类型数据的交互

    例如,如何将异质图中的元路径思想与KB中的embedding transformation相结合,以为HNE提供更多的语义感知的转换操作(semantic-aware transformation)?

    如何为KB的嵌入学习设计基于截断的随机游走方法(truncated random walk),以学习到包含高阶关系信息的嵌入表示?


    (5)Modeling heterogeneous contexts

    异质网的嵌入学习主要是对不同类型的节点和边进行建模。然而,如今的网络中可能包含丰富的内容信息,这些信息为节点、边和子网络提供了上下文信息。

    因此,如何通过多模态的内容结构的集成来对多方面(multi-facet)环境下的异构信息交互进行建模,是一个具有挑战性但值得研究的方向。


    (6)Understanding the limitation

    虽然HNE(以及其他的基于神经网络的表示学习模型)在多个领域中都有着很好的表现,但是我们还需要理解它的一些潜在的局限性

    例如,在什么情况下流行的HNE算法比传统的网络挖掘方法(例如 path counting, 子图匹配, 非神经的或线性的模型)表现更好?如何联合两种类型的方法的优点

    此外,已经有一些针对同质网神经网络背后数学机制的深入研究(例如 smoothingm, 低通滤波器, invariant and equivariant变换)。本工作对现有的HNE模型进行了统一整理,也有助于促进对HNE的能力和局限性的进一步理论研究。

    展开全文
    byn12345 2020-04-07 14:44:15
  • 1.06MB weixin_38743968 2019-09-20 20:58:23
  • 1.73MB weixin_38743481 2019-09-20 18:47:28
  • 919KB weixin_38743968 2019-09-08 16:42:34
  • 519KB weixin_38729607 2020-05-16 01:06:27
  • 571KB weixin_38743602 2019-09-07 06:54:20
  • 352KB weixin_38711333 2021-04-28 23:40:49
  • 601KB weixin_38686080 2021-05-15 05:12:08
  • 1.08MB weixin_38599712 2021-04-28 23:21:45
  • Eastmount 2021-07-19 20:16:21

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 856
精华内容 342
关键字:

同质论异质论