精华内容
下载资源
问答
  • 异质网络将复杂系统中的信息抽象成不同类型的节点和链接关系,不同于同质网络,基于异质网络的社区发现能够挖掘出更加精确的社区结构。异质网络的社区发现通过对异质网络中的多维结构、多模信息、语义信息、链接关系...
  • 医学研究中常用的统计方法通常假定患者来自一个同质人群。 但是,大量异质性的存在和重要性已被广泛记录。 众所周知,常见和复杂的人类疾病通常具有异质的疾病病因,通常涉及多种遗传和环境因素的相互作用,导致潜在...
  • 异质Agent间的知识迁移强化学习,刘博,程玉虎,针对现有知识迁移方法仅适用于同质强化学习Agent的问题,提出一种能够在具有不同状态动作空间的异质Agent间迁移知识的Q学习算法。算�
  • 针对异质无线传感网络的覆盖性能测试评估困难的问题,提出了一种基于目标...实验结果表明,改进后的算法(ICFA)对于异/同质网络覆盖性能的评估均适用,且与基于网格的贪婪算法相比,具有算法复杂度低和本地化的优点。
  • 动态网络的社区发现是目前复杂网络分析领域的重要研究内容,然而现有动态网络社区发现方法主要针对同质网络,当网络包含多种异质信息时,现有方法不再适用。针对这个问题,提出了一种基于联合矩阵分解的动态异质网络...
  • 文章目录摘要引言问题定义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,OV,RE)G = ( V , E , O_V , R_E )G=(V,E,OV,RE)G = ( V , E , O_V , R_E )
    分别代表节点类型集合边类型集。每个节点都有异质的内容信息,比如属性、文本、图片。

    2.2 异质图表示学习

    给定C-HetG G=(V,E,OV,RE)G = ( V , E , O_V , R_E )和节点内容集 C CC,目标就是学习到参数为ΘΘ的函数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的概率返回到起始节点,迭代直到采样到了固定数量的节点为止,生成的序列记为RWR(v)RWR(v) 。同时保证RWR(v)RWR(v) 中每种类型的节点都有,也就是采样到了所有类型的节点。
    • 步骤2 将这些采样到的邻居节点按类型进行分类
      针对每种节点类型t,根据其在RWR(v)RWR(v)中出现的频次,选取top ktk_t
      ​个节点,将这些邻居节点就是和节点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可以优于现有的方法。

    展开全文
  • 结果表明,企业家团队绩效改善的路径中没有单一的变量构成,团队价值观的同质性,团队性别的异质性和自主学习都有助于改善任务绩效和创新绩效创业团队。 此外,不同领导风格和其他变量的结合有利于提高创业团队的...
  • 摘要:目的对来自多传感器的同质异质遥感图像进行自动配准。方法对传统的相关系数相 似性量度进行深入分析,通过对其推广,提出一种也适用于异质遥感图像相似性度量的基于联合概 率的方法,并通过具体的图像进行...
  • A Survey of Heterogeneous Information Networks Analysis and Applications (软件学报 2015) 虽然这篇论文早在2015发表的,...信息网络、异质/同质网络、网络模式的定义 元路径、受限元路径(带约束条件)、加权.

    A Survey of Heterogeneous Information Networks Analysis and Applications (软件学报 2015)

    虽然这篇论文早在2015发表的,但是里面的一些基础知识,包括一些定义,对以后写异质信息网络相关的论文会有用到。

    关键词:异质信息网络;元路径;网络表示学习;图神经网络

    最新进展和前沿成果元图:加权元路径、元图、属性异质网络等

    1.异质网络基础知识

    信息网络、异质/同质网络、网络模式 的定义

    元路径、受限元路径(带约束条件)、加权元路径、元结构/元图

    多关系网络、二分网络、星型网络、多中心网络、属性网络、无模式网络

    未考虑路径实例间链接上的属性语义差异诱发较大的语义差异

    元路径只能表示两对象间的简单关系,而元结构/元图可以融合多条元路径,方便地表达复杂语义

    基于元路径的数据挖掘

    相似性度量(基于特征和基于链接):计算余弦相似性或者欧几里得距离等

    推荐 链接预测 元路径选择

    异质网络的表示学习

    问题 :稀疏性及其不断增长的规模

    解决:将网络节点映射到低维向量空间中,用低维稠密向量来表示网络中的任意节点,即信息网络的表示学习。

    代表性模型:DeepWalk,将随机游走和skip-gram模型结合来学习网络节点表示

    浅层模型:基于随机游走

    深层模型:基于自动编码器、基于生成对抗网络、基于强化学习、基于图神经网络

    浅层和深层模型比较

    应用

    未来发展方向

    面向多模态数据的异质网络构建与分析方法

    面向复杂网络数据的异质网络分析方法

    面向深度计算的异质网络表示学习

     

     

    展开全文
  • 在此基础上引入非极端偏好决策成员主观接受程度来说明非极端偏好决策成员对个体极端偏好同质群体集和异质群体集影响力的接受程度,进而构建多阶段大群体应急决策风险偏好演化模型.最后通过案例及数据仿真结果的对比...
  • 运用行为金融理论和博弈,研究了机构投资者和潜在投资者同、异质预期对IPO抑价的影响,并针对有意和无意抑价进行比较分析.研究表明:当机构投资者和发行人以期望效用最大...
  • 然后,建立了双同质群体的多智能体仿真模型,并将仿真结果与复制动态分析和单同质群体进行了对比;最后,从策略更新时间、网络结构、学习机制三方面提出了双群体的异质演化机制。仿真结果表明,不同演化博弈机制下的...
  • 提取学习者多维特征分量,通过模糊C均值算法以学习风格、知识水平、学习目标和兴趣爱好为主要特征进行同质聚类,根据活跃度和性别特征进行异质聚类以实现混合性质分组。该算法将异质同质分组相结合,既保证了学习...
  • 研究结果表明, 在个体从众性同质的情况下, 存在使网络舆论同步的阈值, 当个体从众性较大时, 网络群体事件舆论趋于同步; 当从众性较小时, 群体态度演化成具有明显社团结构的多个舆论方向. 个体从众性异质时, ...
  • 作为量子搜索算法研究的一个基本工具,量子行走是一个重要研究课题。同时,击中时是衡量量子行走到达某一目标顶点速度的...针对同质开放量子行走、异质开放量子行走和嵌套开放量子行走,分别给出四种击中时具体计算。
  • 然而这些同质,静态的网络往往难以充分地描述社区中的知识资源要素及变化.为解决异质性表达问题,本文针对大众协同创新社区中知识的增长和消退机制,构建了一种超网络动态演化模型.同时,应用该模型的拓扑特性指标对...
  • 建立了基于面向对象Petri网逻辑模型并形式化定义了Chaku-Chaku规则,通过仿真方法确认生产线稳态后系统的空间及物理层面特征,采用数值分析方法分析了同质员工与异质员工两种情况下生产系统的特性,确定了员工在生产...
  • 对第二定律的挑战可追溯到统计异质性,该异质性超出了玻耳兹曼,吉布斯,托尔曼和冯·诺依曼在其H定理中所作的同质性和不可区分性的假设。 表催化作用超出了这些假设。 因此,H-定理不适用于它,第二定律被绕过而不...
  • 然而,虽然对同质网络的分类研究已有几十年的历史,但对异质网络的分类却一直没有深入的研究。 本文研究了共享同一主题的异构网络数据的传递分类问题。只有给定网络中的一些对象被标记,我们的目标是预测剩余对象的...

    异构信息网络中的图正则化平移分类

    摘要

    异构信息网络是由多种类型的对象和链接组成的网络。近年来,人们认识到强类型异构信息网络在现实世界中普遍存在。有时,标签信息可用于某些对象。从这些标记和未标记的数据中学习,通过归纳分类可以很好地提取隐藏网络结构的知识。然而,虽然对同质网络的分类研究已有几十年的历史,但对异质网络的分类却一直没有深入的研究。

    本文研究了共享同一主题的异构网络数据的传递分类问题。只有给定网络中的一些对象被标记,我们的目标是预测剩余对象的所有类型的标签。提出了一种新的基于图的正则化框架GNetMine,用于对具有任意网络模式和任意对象/链接类型的信息网络中的链接结构进行建模。具体地说,我们通过分别保持对应于每种类型链接的每个关系图的一致性来明确地尊重类型差异。然后引入有效的计算格式来求解相应的优化问题。在DBLP数据集上的实验结果表明,与现有的最新方法相比,该算法显著提高了分类精度。

    1.引言

    信息网络是由大量相互连接的数据对象组成的,在现实生活中无处不在。例如从书目数据中提取的合著者网络和论文引用网络,以及通过万维网中的超链接互连的网页网络。从如此庞大的网络数据集中提取知识最近引起了极大的兴趣[11][15][16][19]。有时,标签信息可用于某些数据对象。从标记和未标记数据中学习通常称为半监督学习[22][21][3],其目的是基于已知信息对未标记数据进行分类。分类有助于发现信息网络中隐藏的结构,深入了解每个对象所扮演的不同角色。事实上,像研究社区发现、欺诈检测和产品推荐这样的应用程序都可以看作是一个分类问题[11][15]。一般来说,分类可以分为两类:(1)归纳分类[10][11][22][21][19]:为给定的未标记数据预测标签;(2)归纳分类[9][15][12][18][3]:在整个数据空间中构造决策函数。在本文中,我们重点研究了网络数据中的一种常见情况:传递分类

    目前对网络数据的归纳分类研究[9][10][11][15]主要集中在同质信息网络,即由单一类型对象组成的网络,如上所述。但在现实生活中,可能存在多种类型的对象,形成异构的信息网络。除了合著者网络和引文网络之外,书目数据自然地在论文、作者、会议、术语等之间形成一个网络。人们已经认识到,异构信息网络是普遍存在的,其中任何两种类型的对象之间都可能发生互联联系。

    例1。书目信息网。书目信息网络通常包含四种类型的数据对象:论文、作者、地点(会议和期刊)和术语论文作者是通过“作者”与“作者”的关系联系在一起的。论文地点之间通过“发表在”与“发表”的关系联系在一起。论文术语之间是通过“包含”与“包含”的关系联系起来的。

    作为对同质网络数据分类的自然推广,我们考虑了将异构网络数据分类为多个类的问题,每个类由共享一个共同主题的多类型数据组成。例如,书目信息网络中的研究社区不仅包含作者,还包含属于同一研究领域的论文、地点和术语。其他例子包括电影、导演、演员和关键词属于同一类型的电影网络,以及卖家、客户、物品和标签属于同一购物类别的电子商务网络。

    分类的一般问题在文献中已有很好的研究。然而,由于数据的以下特点,强类型异构信息网络的转换分类更具挑战性:

    1. 网络结构的复杂性。在处理异构信息网络中的多类型网络结构时,一种常见的解决方案是将其转化为同质网络,并应用传统的分类方法[11][15]。然而,这种简单的转换有几个缺点。例如,假设我们想把论文分为不同的研究领域。现有的方法很可能从整个书目网络中提取一个引用网络。然后一些有价值的鉴别信息可能会丢失(例如论文作者和论文发表地点)。利用整个网络的另一个解决方案是忽略对象和链接之间的类型差异。然而,不同类型的对象自然具有不同的数据分布,不同类型的链接具有不同的语义,因此平等地对待它们可能是次优的。人们已经认识到[8][16]在挖掘异构信息网络时,应该考虑链接和对象之间的类型差异,以便产生更有意义的结果。
    2. 缺乏特色。传统的分类方法通常从数据的局部特征或属性中学习。然而,对于所有类型的网络数据,都没有自然的特征表示。如果我们将链接信息转换为特征,那么随着对象数量的增加,我们可能会生成非常高维的稀疏数据。此外,即使我们对异构信息网络中的某些对象进行了特征表示,但不同类型对象的特征在不同的空间中是不可比较的。这也是支持向量机、朴素贝叶斯和logistic回归等传统的基于特征的方法难以应用于异构信息网络的另一个原因。
    3. 缺少标签。许多分类方法需要合理数量的训练实例。然而,在许多实际应用中,标签是昂贵的。在一个异构的信息网络中,我们甚至不可能拥有所有类型的对象的完全标记子集来进行训练。某些类型的对象的标签信息很容易获取,而某些其他类型的对象的标签则不容易获取。因此,一个灵活的transductive分类器应该允许标签在不同类型的对象之间传播。

    在本文中,我们提出了一种新的基于图的正则化框架来解决这三个难题,该框架仅基于任何类型对象的标签信息和链接结构,就可以同时对具有任意网络拓扑结构和对象/链接类型数的所有非属性、纯网络数据进行分类。通过保持每一类链接对应的关系图上的一致性,我们明确地考虑了链接和对象的类型差异,从而比传统的基于图的同构网络上的直推分类更有效地编码了类型信息。

    本文其余部分的结构如下。在第二节中,我们简要回顾了现有的关于网络数据分类和基于图的学习的工作。在第三节中,我们正式定义了异构信息网络的传递分类问题。我们的基于图的正则化框架(用GNetMine表示)在第4节中介绍。第五节给出了实验结果。最后,我们在第6节中总结这项工作。

    2.相关工作

    我们总结了表1中的各种归纳分类方法,其中一个维度表示数据是否具有特征/属性,另一个维度表示不同类型的网络结构:从非网络数据到异构网络数据。我们提出的方法适用于异构、非属性的纯网络数据,这是最一般的情况,需要最少的信息量。

    近年来,网络数据分类受到了广泛的关注。中心思想是从网络结构和局部属性(如果有的话)推断类标签。在对网页或文档进行分类时,可以使用Naıve Bayes[4]、logistic回归[9]、图正则化[20]等方法将局部文本特征和链接信息结合起来。所有这些方法都假设网络是齐次的。关系依赖网络[12]通过为每个感兴趣的变量建立条件模型来学习依赖结构时,尊重关系数据之间的类型差异,但仍然像其他关系学习方法一样依赖于局部特征。此外,统计关系学习通常需要一个完全标记的数据集进行训练,这在实际应用中可能很难获得。

    Macskassy等人[10]提出了一种仅针对网络数据的关系邻居分类器。通过按邻域的大多数类对对象进行迭代分类,与更复杂的模型(包括概率关系模型[6][17]、关系概率树[13]和关系贝叶斯分类器[14])相比,该方法的性能非常好。Macskassy等人[11]进一步强调,同质性对于他们的方法在网络分类中的良好表现非常重要。

    近年来,人们对挖掘异构信息网络的兴趣激增[7][2][8][1]。NetClus[16]使用排序聚类互增强方法生成由多类型对象组成的聚类。然而,聚类不能有效地利用已有的先验知识。Yin等人[19]探索了用于异构web对象分类的社会标记图。它们在标签web对象之间构造一个二部图来提高分类性能。然而,他们无法区分不同类型的链接。而且他们的方法局限于标签和web数据之间的特定网络模式,因此不能应用于任意的链接结构

    同时,基于图的学习在翻译分类中得到了长期的普及。大多数方法都是基于局部特征在标记和未标记的实例上构造一个相似图来编码实例之间的相似性。然后,他们设计一个学习者来保持数据几何结构的平滑性和一致性。Zhu等人[22]用一个高斯随机场模型来描述这个问题。Zhou等人[21]提出让每个点迭代地将其标签信息传播给邻居,以确保局部和全局的一致性。当局部特征在信息网络中不可用时,基于图的方法有时可以利用固有的网络结构来扮演亲和图的角色。然而,传统的基于图的学习方法主要针对覆盖所有实例的齐次图,不能很好地区分多类型链接和对象的不同语义。本文针对异构网络数据的特点,对基于图的学习框架进行了扩展

    3.问题定义

    在本节中,我们将介绍几个相关的概念和符号,然后正式定义问题。

    定义1。异构信息网络。给定m种数据对象,表示为
    ,图G=〈V,E,W〉 称为异构信息网络,如果
    m≥2,E是V的任意两个数据对象之间的链接集,W是链接上的权值集。当m=1时,G退化为一个齐次信息网络。

    定义2。分类。给定一个异构信息网络G=〈V,E,W〉 ,类被定义为G′=〈V′,E′,W′〉,其中V′⊆V、E′⊆E。。注意,V′还包含从的多种类型的对象。

    定义2如下[16]。请注意,异构信息网络中的类实际上是一个子网络,其中包含相互密切相关的多类型对象。现在我们的问题可以形式化如下。

    定义3。异构信息网络的归纳分类。给定异构信息网络G=〈V,E,W〉,数据对象的子集V′⊆,用Y标记表示每个对象属于哪个类的值,预测所有未标记对象V−V′的类标签。

    在多类分类任务中,我们设计了一套一对一的软分类器。假设类的数目是K,对于任何对象类型,我们试图计算一个类指示矩阵其中每个测量每个对象属于k类的置信度。然后我们可以通过在的第p行中找到最大值来将类型中的第p个对象分配给类。

    在异构信息网络中,可以建立一个关系图,对应于两类数据对象之间的每种连接关系。注意,i=j是可能的。设是对应于图关系矩阵。的第p行和第q列中的元素表示为,表示链接上的权重。有很多方法可以定义链接的权重,也可以结合领域知识。一个简单的定义如下:

    这里我们考虑无向图,例如
    为了对标签信息进行编码,我们基本上设置了一个向量,对于每个数据对象类型,使: 

    对于每个类k∈{1,...,k},我们的目标是从,i,j∈{1,...,m}中推断出一组

    第四章 基于图的正则化框架

    在本节中,我们首先描述我们方法的直觉。然后,我们提出了一个基于图的正则化框架的问题。最后,提出了求解优化问题的有效计算方案。

    4.1直觉

    考虑图4.1中一个简单的书目信息网络。四种类型的对象(论文、作者、会议和术语)通过多类型链接(用实心黑线表示)互连,如示例1所述。假设我们想把他们分成研究群体。标记的对象是着色的,而未着色对象的标签是未知的。鉴于作者A1、论文P1和会议C1属于数据挖掘领域的先验知识,很容易推断出作者A2(撰写论文P1)和术语T1(包含在P1中)都与数据挖掘高度相关。类似地,作者A3、会议C2以及术语T2和T3可能属于数据库区域,因为它们直接链接到数据库论文P3。对于论文P2,事情变得更加复杂,因为它与标记和未标记的对象都链接在一起。属于某一类的置信度不仅可以从标记对象(会议C1和作者A4)转移,还可以从未标记对象(作者A2和A3,术语T1、T2和T3)转移。分类过程可视为知识在整个网络中传播的过程,如图4.1所示,粗阴影箭头表示可能的知识流。对象x与k类的其他对象之间的链接越多,x属于k类的可信度就越高。因此,标记对象作为先验知识的来源。尽管这种直觉本质上是在网络上保持一致性的,这与[10]和[21]类似,但由于信息的类型化,异构信息网络中的互联关系更加复杂。通过不同类型的链接进行的知识传播包含着不同的语义,因此应分别加以考虑。

    这样,我们的框架是建立在一致性假设的基础上的,即两个链接的对象可能类似。对标记对象的类预测应该类似于他们预先指定的标签。为了考虑链接和对象之间的类型差异,我们保证在与每种类型的链接分别对应的每个关系图上保持这种一致性。我们的直觉如下:

    1. 如果x_{ip}x_{jq}连接在一起,即权重值,则属于k类、的两个对象x_{ip}x_{jq}的估计置信度应该相似。
    2. 置信度估计应该类似于基本真值

    4.2算法

    对于每个关系矩,我们定义一个大小为n_{i}\times n_{i}的对角矩阵的第(p,p)元素是的第p行的和。在上述讨论之后,应该与每个关系图中的链接信息和先验知识尽可能一致,因此我们尝试最小化以下目标函数:

    其中D_{ij,pp}的第(p,p)个元素,D_{ji,qq}的第(q,q)个元素。目标函数(4.1)中的第一项是表示第一直觉的平滑度约束。该术语通过进行规范化,以减少节点受欢迎程度的影响。换句话说,我们可以在一定程度上抑制流行节点在置信度估计中的主导作用。在传统的基于图的学习中采用了归一化技术,其有效性得到了很好的证明[21]。第二项最小化了预测结果和标签之间的差异,反映了第二种直觉。

    不同条款之间的权衡由正则化参数\lambda _{ij}\alpha _{i}控制,其中0≤\lambda _{ij}<1,0<\alpha _{i}<1。对于∀i,j∈{1,...,m},\lambda _{ij}>0表示对象类型Xi和Xj是联系在一起的,并且考虑到了这一关系。\lambda _{ij}越大,对象类型之间的关系的值就越大。例如,在书目信息网络中,如果用户认为作者与论文之间的联系比会议与论文之间的链接更可信、更有影响力,那么与作者与论文关系对应的\lambda _{ij}应设置大于会议文件的链接,而分类结果将更多地依赖于作者与论文的关系。同样,在某种程度上,\alpha _{i}的值在一定程度上衡量用户对对象类型标签的信任程度。[8]中采用了相似的策略来控制不同类型的关系和对象之间的权重。但是,我们将在第5节中显示,参数设置不会对算法的性能产生显著影响。

     

    为了便于算法推导,我们定义了的规范化形式:

    对于简单的代数公式,(4.1)的第一项可以重写为:

    然后我们可以用下面的形式重写(4.1):

    4.2.1与基于同质图的学习的联系

    在这里,我们首先证明了我们算法的同质版本与基于图的学习方法是等价的[21]。然后在异构信息网络上,给出了算法与文献[21]的联系和区别。

    我们首先定义,其中是大小为n_{i}\times n_{i}的单位矩阵。注意,是对象类型上齐次子网的规范化图Laplacian[5]:

    引理1。在同质信息网络中,目标函数(4.4)简化为:
    .

    只需在函数(4.4)中设置m=1即可进行证明。很容易看出,我们算法的齐次版本等价于[21]的目标函数。

    当信息网络是异构的时,我们可以把所有类型的对象看作一个整体。我们定义:

    其中是所有1的n_{i}维列向量。我们进一步构造一个矩阵,对应于两个不同对象类型之间的每种类型的关系,如下所示:

    ,设为n×n对称矩阵,其中每一行/列对应一个对象,其阶数与中的阶数相同。与对象类型对应的行和列中的元素等于,其他所有元素都是0。这也适用于i=j

    引理2。在异构信息网络上,目标函数(4.4)等价于:

    其中

    证明可以通过分别考虑目标函数(4.4)中 i≠j 和 i=j 的每一项,然后将它们相加来完成。引理2表明,我们提出的GNetMine算法与齐次数据上基于图的学习框架[21]具有一致的形式,其中H被归一化图Laplacian L[5]代替。此外,我们尊重多类型链接的不同语义,将图正则化分别应用于每类链接对应的关系图,而不是应用于整个网络。不同的正则化参数λij还提供了更大的灵活性,可以结合用户对所有类型关系中对象类型之间的关系值的偏好。然而,即使将所有\lambda _{ij}设置为相同,我们也可以看到,只要至少有一种类型的对象通过多种类型的关系链接到其他对象,H就不同于整个网络上的规范化图Laplacian L[5]。

    4.2.2闭式解

    很容易检查是半正定的,也是半正定的。我们现在证明也是半正定的。证明。回想一下,我们定义:

    可以观察到,与图Laplacian[5]的形式相同,其中是一个对角线矩阵,其条目是的列(或行,因为是对称的)和。所以是半正定的。因此

    是半正定的。

    这样,是半正定的。我们进一步检查了目标函数(4.4)的Hessian矩阵,该矩阵很容易从方程(4.5)中导出:

    的加权和,也是半正定的。由于所有i的\alpha _{i}> 0,我们得出是正定的。因此,目标函数(4.4)是严格凸的。唯一的全局最小值是通过对每个求微分(4.4)得到的:

    对所有 i 使得:

    最后,我们通过求解以下线性方程组给出了封闭形式的解:

    可以证明是正定可逆的。

    4.2.3迭代解

    虽然得到了封闭形式的解,但有时迭代解更可取。基于等式(4.6),我们推导出算法的迭代形式如下:

    • 步骤0:对于∀k∈{ 1,...,K},∀i∈{ 1,...,m},初始化置信估计和t = 0。
    • 第一步:根据当前的,计算:

      对于∀k∈{ 1,...,K},∀i∈{ 1,...,m}
    • 第二步:重复第一步,t = t + 1,直到收敛,即直到对所有i变化不大。
    • 第三步:对于每个i∈{ 1,...,m},将类别标签分配给类型的第p个对象,如,其中

    根据类似于[21]的分析,可以证明迭代算法收敛到封闭形式的解。迭代解可视为[21]的自然延伸,其中每个对象迭代地将标签信息传播给其邻居,直到达到全局稳定状态。同时,我们通过使用分别对应于每种类型的链接的不同归一化关系图而不是覆盖所有实例的单个图来明确区分多类型链接和对象之间的语义差异。

    4.3时间复杂度分析

    我们在这里分析迭代解的计算复杂度。步骤0需要O(K|V|)时间进行初始化,其中K为类数,|V|为对象总数。在步骤1的每次迭代中,我们需要处理每个链接两次,一次是针对链接两端的对象。我们需要O(K|V|)时间来将标签信息合并到中。因此每次迭代的时间是O(K(|E|+|V|)),其中|E|是信息网络中的链接总数。最后,计算步骤3中的类预测结果需要O(K|V|)时间。因此,迭代算法的总时间复杂度为O(NK(|E|+|V|),其中N是迭代次数。

    封闭形式解的时间复杂度取决于特定的网络结构。由于篇幅限制,我们省略了分析。一般来说,迭代解的计算效率更高,因为它绕过了矩阵求逆运算。

    毕竟,分类任务是离线完成的,所有对象都可以进行一次分类,并将结果存储起来以备将来查询。

    第五章实验结果

    在这一节中,我们给出了一个基于图的正则化框架在真实异构信息网络DBLP上的有效性的实验研究。如前所述,我们试图将书目数据分类到研究社区中,每个社区都包含与同一领域密切相关的多类型对象。

    5.1数据集

    我们提取了DBLP数据集在四个方面的子网络:数据库、数据挖掘、信息检索和人工智能,自然形成四个类别。通过选择每个领域的五个代表性会议、在这些会议上发表的论文、这些论文的作者以及出现在这些论文标题中的术语,我们获得了由论文会议作者术语四种类型的对象组成的异构信息网络。在这个异构的信息网络中,我们有三种类型的链接关系:论文会议论文作者论文术语。我们使用的数据集包含14376篇论文、20次会议、14475名作者和8920个术语,共有170794个链接。通过使用我们的GNetMine算法,我们可以同时对所有类型的对象进行分类,而不管我们标记了多少类型的对象。

    为了评估准确性,我们使用了4057名作者、100篇论文和所有20次会议的标记数据集。有关已标记数据集的更多详细信息,请参考[7] [16]。在接下来的部分中,我们随机选择标记对象的子集,并使用它们的标签信息作为先验知识。分类精度通过与其余标记对象的手动标记结果进行比较来评估。由于术语甚至很难手动标注,即许多术语与多个领域密切相关,因此我们在此没有评估术语的准确性。

    5.2用于比较的算法

    我们将GNetMine与以下最先进的算法进行了比较:

    • 具有局部和全局一致性的学习(LLGC)[21];
    • 加权投票关系邻居分类器(WVRN)[10][11];
    • 仅基于网络链接的分类(nLB) [9] [11]

    LLGC是一种基于图的直推式分类算法,如果我们利用内在的网络结构来发挥亲和图的作用,它也是GNetMine的齐次约简。加权投票关系近邻分类器和基于链接的分类是两种流行的网络数据分类算法。由于本地属性/特征在我们的问题中不可用,所以我们使用基于链接的分类器(nLB)的网络唯一衍生。根据[11],nLB基于相邻信息为每个节点创建一个特征向量。

    请注意,上述算法都不能直接应用于异构信息网络。为了使所有的算法都具有可比性,我们可以通过两种方式将一个异构的信息网络转化为一个同构的信息网络:(1)忽略对象之间的类型差异,将所有对象视为同一类型;或者(2)如果对象类型被部分标记,则在一个单一类型的对象上提取同质子网络。我们在准确性研究中尝试了两种方法。在我们的实验中使用了NetKit-SRL[11]的开源实现。

    5.3准确性研究

    在本实验中,我们选择作者论文上的标签来测试分类的准确性。为了解决标签稀缺问题,我们随机选择(a%,p%) = [(0.1%,0.1%),(0.2%,0.2%),...,(0.5%,0.5%)]的作者和论文,并使用其标签信息进行直推式分类。对于每个给定的(a%,p%),我们在10次随机选择中平均结果。请注意,这里极小比例的标记对象很可能是断开的,因此我们甚至可能无法提取一个完全标记的子网络进行训练,这使得许多最先进的算法不适用。

    由于齐次LLGC算法只有一个α和一个λ,因此在模型选择中只有比率\frac{\alpha }{\lambda }是重要的。\frac{\alpha }{\lambda }通过搜索网格{0.01,0.05,0.1,0.5,1,5,10}来设置,其中\frac{\alpha }{\lambda }= 0.5时获得最佳结果。对于GNetMine,我们不认为任何对象/链接类型在这里特别重要,并使用与LLGC相同的参数集,即\alpha _{i}= 0.1,\lambda _{ij}= 0.2,∀i,j ∈ {1,...,m}。这可能不是最好的选择,但足以显示GNetMine的有效性。由于标签信息是在作者和论文上给出的,wvRN、nLB和LLGC会议的结果只能通过忽略对象和链接之间的类型差异来获得,用(A-C-P-T)表示。在对作者和论文进行分类的同时,我们还尝试以不同的方式构建同质作者-作者(A-A)和论文-论文(P-P)子网络,其中为作者呈现的最佳结果由共同作者网络给出,而为论文呈现的最佳结果是通过链接两篇在同一会议上发表的论文而生成的。我们在表5.1、5.2和5.3中分别给出了作者、论文和会议的分类精度。

    在对作者和论文进行分类时,有趣的是,wvRN和nLB在作者-作者和论文-论文子网络上的性能优于在整个异构信息网络上的性能,这验证了使用同构数据对于这种同构关系分类器的重要性。然而,如前所述,从原始异构网络到同构子网的转换会导致一些信息丢失。并且在同构子网络中只能使用一种类型的标签信息,即使另一种类型的对象的先验知识是可用的。

    当考虑整个异构信息网络(A-C-P-T)时,任务实际上变得更具挑战性,因为对象的总数上升到14376(论文)+20(会议)+ 14475(作者)+ 8920(术语)= 37791,其中最多(14376(论文)+ 14475(作者))× 0.5%/37791 = 0.4%的对象被标记。类似的结果已有报道[11],当标记对象的百分比小于20%时,分类精度可能会低于随机猜测(此处为25%)。因此,由于缺少标签,wvRN和nLB的性能较差。而将标注比例从0.1%提高到0.5%,对提高nLB的准确率并没有太大的影响。

    总的来说,GNetMine通过向有标签的作者和论文学习,在所有类型的对象上表现最好。尽管所有类型的对象和链接的参数都设置为相同的值,但GNetMine仍然优于其同构约简LLGC,因为它在分别对应于每种类型的链接的每个子图上保持一致性,并最小化聚合错误,从而以更有组织的方式对异构网络结构进行建模。

    5.4模型选择

    \alpha _{i}\lambda _{ij}是GNetMine中控制不同项相对重要性的基本参数。在之前的实验中,我们根据经验将所有的\alpha _{i}设为0.1,所有的\lambda _{ij}设为0.2。在这一部分,我们试图研究参数对GNetMine性能的影响。由于作者和论文都有标签,与作者(用\alpha _{a}表示)和论文(用\alpha _{p}表示)相关联的\alpha _{i},以及与作者-论文关系(用\lambda _{pa}表示)相关联的\lambda _{ij}在经验上比其他参数更重要。所以我们固定所有其他参数,让\alpha _{a}\alpha _{p}\lambda _{pa}变化。我们也相应地改变LLGC中的α和λ。图5.1显示了作为参数函数的三种对象(作者、论文、会议)的平均分类精度,标记了(a%,p%) = (0.5%,0.5%)作者和论文。

    可以观察到,在很大的参数范围内,GNetMine获得了比所有其他算法显著更好的性能,包括其均匀约简LLGC,其中参数以相同的方式变化。有趣的是,\alpha _{a}的精度曲线不同于\alpha _{p},说明作者和论文在分类过程中确实扮演了不同的角色。从\lambda _{pa}的精度曲线可以看出,设置\lambda _{pa}大于所有其他\lambda _{ij}(设置为0.2)可以提高精度。这是因为增加λ增加了两种标记数据之间的知识传播,这是有益的。

    总体而言,参数选择不会严重影响GNetMine的性能。如果用户对某些类型的链接的重要性有所了解,则可以相应地调整参数以模拟网络的特殊特征。

    第六章结论

    在本文中,我们开发了一个新的基于图的正则化框架来解决异构信息网络上的直推分类问题。我们提出,不同类型的对象和链接应根据不同的语义分别对待,这一点得到了理论和实践的证明。通过应用图正则化来保持与每种类型的链接分别对应的每个关系图的一致性,并最小化聚集误差,我们充分利用多类型的链接信息来预测每个对象的类标签。通过这种方式,我们的框架通常可以应用于具有任意模式的异构信息网络,该模式由许多对象/链接类型组成。在真实DBLP数据集上的实验表明,该方法优于现有算法。

    该框架通过标记一些随机选择的对象来对未标记的数据进行分类。然而,正如在过去的许多研究中观察到的那样,标签的质量会显著影响分类结果。在未来,我们计划自动检测信息最丰富的对象,如果它们被标记,这可以导致更好的分类质量。可能具有高等级或位于子网络中心的对象可能是很好的候选对象。

    展开全文
  • 我们扩展了经验剂量组合规则,该规则仅适用于强度相等的同质脉冲,以适应具有不均匀强度的多次异质声音暴露的一般情况。 除了研究和扩展经验剂量组合规则外,我们还针对独立事件的假设情况探索剂量组合规则,并将其...
  • 在正式阅读本文之前,我们考虑这样一个事实:以GCN为代表的领域聚合方式在每一轮的前向传播中,只能获取到N-hop邻域内节点的特征,并且,其最为基本的想法是基于网络同质性的,也就是相邻节点具有相似性。...

    本文的三位作者来自斯坦福大学。
    在正式阅读本文之前,我们考虑这样一个事实:以GCN为代表的领域聚合方式在每一轮的前向传播中,只能获取到N-hop邻域内节点的特征,并且,其最为基本的想法是基于网络同质性的,也就是相邻节点具有相似性。假定,对于异质网络,中心节点A的type为1,邻域节点BCD的type为2,那么在一次聚合之后,A就会变成2。并且,过深的网络会造成过平滑,这都是GCN无法解决的。
    本文提出了一种用于计算位置感知节点嵌入的新型图形神经网络——位置感知图神经网络。P-GNN首先对锚节点集进行采样,计算给定目标节点到每个锚集的距离,然后学习锚集上的非线性距离加权聚合方案。通过这种方式,P-GNNs可以捕获节点相对于锚节点的位置。P-GNN有几个优点:它们是归纳的、可伸缩的,并且可以合并节点特性信息。
    具体说来,P-GNN使用节点采样,保证选择k个随机子集的节点称为锚集。为了计算一个节点的嵌入,P-GNN首先在每一次聚合过程中对多个锚集进行采样,然后学习一种非线性聚合方案,该方案结合每个锚集的节点特征信息,并根据节点与锚集之间的距离对其进行加权。Bourgain theorem证明了为了保证图节点采样过程中的低失真,所需要的锚集的数量为k=O(log2n)k=O(log^2n)。本文还从理论上证明了P-GNN比传统的消息传递gnn更具通用性和表现力。实际上,message passing gnn可以看作是P-GNN的特殊情况下退化的距离度量和锚集采样策略。在大型应用程序中,计算节点之间的距离可能非常昂贵。因此,我们还提出了采用近似节点距离计算的P-GNN-Fast。

    Preliminaries

    Limitations of Structure-aware Embeddings

    如果两个节点的嵌入可以用来(近似地)恢复它们在网络中的最短路径距离,我们称节点嵌入为位置感知。反之,对于GCN,就是结构感知(structure-aware)。下面将说明,基于gnn的嵌入不能恢复节点之间的最短路径距离,这可能导致在需要这些信息的任务中性能不佳。
    在这里插入图片描述
    定义1给出了position-aware的定义。dsp(vi,vj)=gp(zi,zj)d_sp(v_i,v_j)=g_p(z_i,z_j)也就是embedding之后的节点特征的相关的函数可以推导出影射之前的相应结点之间的距离。这与structure-aware相对。
    在这里插入图片描述
    某个节点viv_i的embedding函数是结构感知函数,如果这个函数是节点的q-hop邻居相关的函数,也就是zi=gs(N1(vi)...)z_i=g_s(N_1(v_i)...)这个函数所指出的。
    大多数图神经网络通过聚合每个节点的q跳邻域的信息来计算节点嵌入,因此是结构感知的。相比之下,基于随机行走的(长)嵌入,如DeepWalk和Node2Vec是位置感知的,因为它们的目标函数迫使在最短路径上接近的节点在嵌入空间上也接近。通常,结构感知的嵌入不能映射到位置感知的嵌入。而且通过对以往的论文阅读也知道,GCN的性能之所以不佳就是因为他是结构感知的,而在分子和社会网络等真实图中,节点之间的结构等价性非常普遍,使得gnn难以识别不同的节点。
    在这里插入图片描述
    比如上边这个图吧,GNN不能单独根据网络结构区分节点v1和v2,从而将它们分类为不同的类别(注意节点是没有属性的)。有效的节点嵌入应该能够学会区分节点v1和v2(即将它们嵌入到空间中的不同点中),而P-GNNs可以利用v3作为锚集打破对称性,则最短路径距离(v1;v3)和(v2;v3)是不同的,因此可以区分节点v1和v2。

    Proposed Approach

    The Framework of P-GNNs

    在这里插入图片描述
    本文提出了位置感知图神经网络,它概括了图神经网络的两个概念。首先,在计算节点嵌入时,我们允许P-GNN聚合来自锚集的消息,锚集是所有节点随机选择的子集(图左),而不是只聚合从节点的本地网络邻居计算的消息。注意,锚集会在每次向前运行模型时重新采样。其次,在执行消息聚合时,不是让每个节点独立地聚合信息,而是在所有节点之间耦合聚合,以区分网络中位置不同的节点(图2,中间)。我们设计的P-GNN使每个节点嵌入维对应于根据一个锚集计算出的消息,这使得计算出的节点嵌入位置敏感(图右)。
    算法1总结了P-GNN的架构:
    在这里插入图片描述
    根据算法架构,需要确定的主要部件有:锚集内聚合函数F(v,u,hv,hu)F(v,u,h_v,h_u),它需要满足position-aware的定义,也就是能够还原节点之间的距离信息。此外,如何借助启发式的方式指导锚集的选取也是需要探究的。还有,锚集之间的聚合方式AGGSAGG_S也需要确定。

    Anchor-set Selection

    我们依靠Bourgain’s Theorem来指导锚集的选择,以保证所得到的表示具有低失真。具体来说,失真度量的是嵌入从一个度量空间映射到另一个度量空间时保留距离的正确性。接下来定义了失真率α:
    在这里插入图片描述
    这表明存在一个低失真嵌入,该嵌入可以从任意度量空间映射到lp度量空间。也就是说,在锚集采样的过程中可以保证一个低失真的子集,在借助子集的embedding之后的结果可以高度还原未embedding之前两个节点之前的距离。
    在这里插入图片描述
    定理1说明了在保持低失真的采样下所需的采样数量。这个在前文也有提到,是k=O(log2n)k=O(log^2n),也就是k=clog2nk=c·log^2ncc是一个常数。由此,定义了一个O(log2n)O(log2n)维度的embedding method,满足定理1:
    在这里插入图片描述
    注意这里的距离d(v,Si,j)d(v,S_{i,j})是中心节点到锚集内部的某个节点的最小距离。
    所提出的P-GNNs可以看作是定理2中嵌入方法的推广,其中距离度量d是通过消息计算函数F和消息聚合函数AGGM进行推广的,该函数同时考虑了节点特征信息和基于位置的相似性。定理2为在P-GNN中选择锚集提供了两个见解:首先,需要O(log2n)个锚集来保证低失真嵌入。其次,这些锚集的大小呈指数分布。对于一阶邻居的锚集定义,如果节点vi或它的任何一跳邻居包含在锚集中,一个锚集就会命中节点vi;小锚集可以提供高度确定性的位置信息,因为当小锚集命中vi时,我们知道vi位于小锚集中为数不多的节点之一附近。但是,这样小的锚集命中vi的概率很低,如果没有命中vi,锚集就没有信息性;相反,大的锚集命中vi的概率更高,因此对大的锚集采样可以获得较高的采样效率。然而,知道一个大的锚集击中vi时,提供的关于它的位置的信息很少,因为vi可能接近于锚集中许多节点中的任何一个。因此,选择不同大小的锚集可以平衡这种权衡,从而实现高效的嵌入。

    Design decisions for P-GNNs

    锚集内聚合函数F(v,u,hv,hu)F(v,u,h_v,h_u)需要包含基于位置的相似性和特征信息。基于位置的相似性是揭示节点位置信息的关键,而特征信息可能包括对预测任务有用的其他侧面信息。所以,FF需要分为两部分:衡量距离,聚合特征。
    出以下q-hop最短路径距离,也就是把超出hop的设置成无限大:
    在这里插入图片描述
    而后,把距离归一化到(0,1)之间:
    在这里插入图片描述
    最终,得到锚集内聚合函数:
    在这里插入图片描述
    我们完全可以把s(v,u)s(v,u)当成是基于距离的注意力得分,然后乘两个节点的特征拼接。至于AGGSAGG_S,则采用了平均聚合的方式。

    实验

    先说一下时间复杂度。每个节点与具有n个节点和e条边的图中的O(log2n)O(log^2n)锚集通信。假如每个锚集包含m个节点,那么复杂度就为O(mnlog2n)O(mnlog^2n),如果遵循精确的锚集选择策略,就为O(n2log2n)O(n^2log^2n)(我没太想明白为啥)。在实践中,我们观察到使用简化的聚合AGGS可以加快计算速度,而只稍微牺牲预测性能。在这里,对于每个锚集,我们只聚合来自最接近给定节点v的节点的消息。这消除了p - gnn复杂度中的因子m,使得复杂度为O(nlog2n)O(nlog^2n)。我们在实验中使用了这个实现。
    实验中使用了两种不同的P-GNN的变种,分别是:一层和二层的网络被标记为1L,2L;简化的2-hop的最短路径选取方法P-GNN-F;使用全最短路径的方法P-GNN-E。然后,针对两种不同的任务去衡量模型的效果:
    连接预测:
    在这里插入图片描述
    结点分类:
    在这里插入图片描述

    展开全文
  • 该结果是H定理的结果,该定理假定粒子具有同质性和不可区分性。 但是,当添加热反馈路径(其中热载体的物理性质与隔离器中的光子不同)时,会形成不被H定理覆盖的异质系统,从而违反了第二定律。
  • 利用空间演化博弈,在同质异质场景中探索了个体策略的演化动力学。 结果表明,在同类情况下,仅当捐赠资源的成本效益比(R)大时,叛逃者才能在平衡状态下支配网络。 在异构场景中,三种策略可以一直存在于所...
  • 引入一种新的广义PageRank (GPR) GNN架构来解决异构性与过平滑问题,该架构自适应地学习GPR权值,从而联合优化节点特征和拓扑信息提取,而不管节点标签的同质性或异质性的程度。本文模型的架构与上一篇读过的论文...
  • 我们以前已经聊过DeepWalk、Node2Vec、LINE、GraphSAGE(详见公众号历史文章),它们都是面对的同质图问题,而今天将讨论的MetaPath2Vec则是要回答**如何对于异质图也能进行低维的空间向量表示**。 结合的论文为...
  •  通用性和专用性、异质性和同质性、动态性和静态性、共时性与历时性、平行与双语,5个相互对立的特征揭示了一个重要的原则,任何语料选择都是一种平衡性的结果。   语法语料库: 训练分词、命名实体、磁性标注、...
  • 本文提出了一种将图卷积操作应用与知识图谱的变体–R-GCN,知识图谱与传统同质图的最大区别在于知识图谱存在多种类型的节点和边,虽然边的定义没有特殊含义但是连接不同节点的边存在不同的语义信息,如果同时进行...
  • 该定理不涵盖结合了不同分布的非传递性,统计上异质的系统,例如麦克斯韦-玻尔兹曼,偏半麦克斯韦-玻尔兹曼,费米-狄拉克和玻色-爱因斯坦。 如果通过根据统计温度和统计熵来表达第二定律,则可以保留第二定律。
  • 熵权法matlab

    2018-11-23 14:24:20
    2. 指标的归一化处理:异质指标同质化 由于各项指标的计量单位并不统一,因此在用它们计算综合指标前,先要对它们进行标准化处理,即把指标的绝对值转化为相对值,并令,从而解决各项不同质指标值的同质化问题。...
  • 其性能相较ACL2020中的文档级关系抽取模型LSR有一定的提升,其能够有提升的主要原因在于两点:1)构建了异质图并使用了R-GCN进行特征传播,相较之前一些构建同质图然后做特征传播的模型,使用异质图可以融合更复杂的...

空空如也

空空如也

1 2
收藏数 31
精华内容 12
关键字:

同质论异质论