|
一、引言 现实生活中的大多数实际系统是由大量相互作用、不同类型组件所构成，当前的分析方法通常将其建模为同质信息网络（Homogeneous information network）。采用同质网络的建模方法往往只是抽取实际交互系统的部分信息，或者没有区分交互系统中对象和关系的差异性。这样都会造成信息不完整或信息损失。最近，越来越多的研究人员开始将这些互连的多类型网络化数据建模为异质信息网络（Heterogeneous information network），（这里我们将Homogeneous/Heterogeneous information network翻译成为同质/异质信息网络。虽然有些学者将其翻译为同构/异构信息网络，但是这种翻译容易和通信网络中的同构/异构网络的概念混淆。另外，同质/异质更能反映网络中的节点和边的类型和性质不一样这种特性。）并且通过利用网络中丰富的对象和关系信息来设计结构分析方法。与广泛研究的同质信息网络相比，异质信息网络包含全面的结构信息和丰富的语义信息，这也为数据挖掘提供了新的机遇与挑战。这里我们简单通俗介绍这种建模方式的基本概念、分析方法和未来发展。 二、基本概念 我们先讲解一下异质信息网络中的基本概念。 2.1概念 异质信息网络[1]被定义为一个有向图，它包含有多种类型的对象或者关系，每个对象属于一个特定的对象类型，每条关系属于一个特定的关系类型。网络模式[1]是定义在对象类型和关系类型上的一个有向图，是信息网络的元描述。 图1(a)是一个由科技文献数据构成的典型的异质信息网络实例[1]。该网络包含三种类型的对象：论文，会议和作者；每篇论文有到作者和会议的链路关系，每条链路属于一种关系类型。图1(b)是该网络的网络模式，描述了文献网络包含的对象类型（会议、论文、作者）和相应的关系（撰写/被撰写、出版/被出版、引用/被引用）。 异质信息网络分析中一个重要的概念是元路径[2]。元路径是定义在网络模式上的链接两类对象的一条路径，形式化定义为 ,表示对象类型之间的一种复合关系 其中 代表关系之间的复合算子， 表示对象类型， 表示关系类型。 元路径不仅刻画了对象之间的语义关系，而且能够抽取对象之间的特征信息。图1(c)显示了文献网中的两个元路径的例子，分别简记为“APA”和“APVPA”（A、P、V分别表示作者、论文和会议类型）。可以看出，基于不同的元路径，对象之间的语义关系是不同的。元路径“作者-论文-作者”（APA）表示两个作者合作撰写了同一篇论文；元路径“作者-论文-会议-论文-作者”（APVPA）表示两个作者在同一会议上发表了论文。链接两类对象的不同元路径表示了不同的语义关系和不同链接网络，这样造成不同的分析结果和不同的特征表示。 图1.由文献数据构建的异质信息网络 实际上，大多数真实系统都是多种类型的对象相互交互。例如，社交媒体网站（如微信和微博）包含多种类型的对象（如用户、帖子和标签）和这些对象之间的复杂交互（如用户之间的朋友、跟帖、通信等关系，用户和帖子之间的发布关系）。医疗系统包含医生、病人、疾病和设备等对象类型和他们之间的交互。一般来说，这些交互系统都可以被建模为异质信息网络。传统的同质网络建模方法（如社会网络分析）只是抽取了这些实际交互系统的部分信息，而且这些信息往往也可以从异质信息网络中推导出来。例如，经常分析的作者合作网络可以通过元路径“APA”从上面的科技文献网络中得到。 2.2为什么要进行异质信息网络分析 作为数据挖掘的重要研究方向，在过去的近20年里，网络分析方法已经被深入研究，并且应用在很多数据挖掘任务，这些工作往往将网络化数据建模成同质信息网络。然而，异质信息网络的一些独特特征使得异质信息网络研究十分重要。首先，异质信息网络分析是数据挖掘的新发展。近年来，大量涌现的社会媒体网站包含许多不同类型的对象和对象之间复杂的交互。将这些相互作用的对象建模为同质网络是很困难的，然而将其建模成异质信息网络却是很自然的方式。特别是，大数据的一个显著特征是数据的多样性。作为半结构化的表示方法，异质信息网络可以有效建模和处理复杂多样的数据。其次，异质信息网络是融合更多信息的有效工具。与同质网络相比，异质网络可以融合更多类型的对象及其复杂交互关系，也可以融合多个社交网络平台的信息。最后，异质信息网络包含丰富的语义。在异质网络中，不同类型的对象和链接共存，它们具有不同的语义含义。考虑到语义信息将导致更细微的知识发现。同质网络中的大多数方法并不能直接应用于异质网络中，因此在异质信息网络中发现有趣的模式是十分必要的。 三、应用 3.1应用概述 异质信息网络为更好地分析网络化数据提供了一种新的研究模式，同时也给许多数据挖掘任务带来了新的挑战。很多基于异质信息网络的数据挖掘问题已经被广泛研究。图2是对过去6年这一方向相关研究工作的100多篇论文按照研究问题分类的分布图[1]。从图中可以看出，异质信息网络已经广泛应用于主要的数据挖掘问题，特别是相似性度量[2]、聚类[3]、分类[4]、链接预测[5]等任务。这里我们主要通过相似性度量和语义推荐两个应用介绍异质信息网络分析的有趣特性。更多的应用可以见相关论文和专著[6]。 图2 异质信息网络分析的论文分布情况 3.2相似性度量 相似性度量是计算对象之间的相似性，它是许多数据挖掘任务的基础，如搜索、查询、和聚类等。传统的相似性度量往往是度量相同类型对象之间的相似性。然而在许多应用中需要对不同类型的对象进行相似性度量。例如，推荐系统中需要度量用户和电影之间的相似性，自动简历生成需要度量用户与其他对象的相似性。不同类型的对象可以共处于同一个异质信息网络中，因此可以在异质信息网络中度量不同对象的相似性。 石川等人[7]提出了HeteSim相似性度量标准。该度量标准定义如下式，它可以基于给定的元路径度量任意类型节点对之间的相似性。由于链接两类节点的不同元路径具有不同的语义和链接关系，因此异质网络中节点对的相似性度量是和元路径相关的。基于相似的对象链接到相似的对象的假设，该度量标准采用沿着元路径的双向随机游走模型度量对象的相似性。通过采用路径分解和规范化等策略，该模型本质上是度量初始节点s沿着元路径和终止节点t逆着元路径到达中间类型节点的概率分布的Cos值。HeteSim度量具有一些良好的特征：对称性，值范围位于[0,1]。此外，可以证明SimRank[8]是HeteSim的特例。表1比较了几种经典相似性度量标准。可以发现HeteSim更具一般性：能够基于任意元路径度量任意节点对的相似性。 表1 不同相似性度量标准比较 下面以科技文献网络为例，介绍HeteSim在自动简历生成方面的应用。如果要生成数据挖掘大牛CMU教授Christos Faloutsos的学术简历，我们可以通过设置元路径度量Christos和其他对象之间的相似性，例如会议、术语、主题以及合作者等等。表2展示了和Christos最相关的前五个各类对象。基于元路径“APVC”，我们可以发现Christos经常参加的一些会议，例如KDD和SIGMOD；基于元路径“APT”，可以发现他的研究兴趣包括：数据挖掘、模式发现、图挖掘和社交网络等；基于元路径“APA”，可以发现他的合作者，大部分是他的学生，如Hanghang Tong等。文献[7]中展示了HeteSim在领域专家发现、查询、聚类等问题上的应用。HeteSim也被应用于生物医药领域的基因和药品相似性度量以及金融领域的用户相似性度量。 表2 基于元路径的Christos Faloutsos的个人简历生成 3.3 基于元路径的语义推荐 推荐是解决信息过载的有效方法，被广泛应用于电子商务和互联网服务。融合更多的信息进行混合推荐是解决数据稀疏性的有效技术。异质信息网络作为有效的信息融合方法可以用于整合推荐系统中的对象和关系。图3展示了由电影推荐系统构建的异质信息网络。我们可以发现该异质网络整合了推荐系统中的打分、社交关系、属性等信息，而且网络中的节点和边包含了丰富的语义信息。因此基于异质信息网络的推荐可能产生更加准确的推荐结果。 基于该框架，张志强等人[9]提出了个性化语义推荐方法SemRec。图4显示了该方法的基本思想。作为一种基本的推荐技术，协同过滤方法通过相似的用户对用户进行推荐。在异质网络中，可以利用元路径找到不同特性的相似用户。例如，通过元路径“UU”（U，M，T分别表示用户，电影，电影类型），可以找到用户的朋友，这实际上对应于社会化推荐；通过元路径“UMU”，可以找到具有相同观影记录的用户，对应于传统的协同过滤；通过元路径“UMTMU”，可以找到喜欢相同类型电影的用户，对应于内容推荐。不同的相似用户有不同的推荐结果，有效整合这些推荐结果，可以产生综合的最终推荐。该方法还考虑了用户和电影之间的打分关系上的分值（即关系权重），提出了带权异质信息网络和带权元路径等概念，以及相应的相似性计算方法。此外，该方法还采用了组推荐技术对具有相同的打分偏好的用户进行了聚类。 实验表明：由于融合了更多信息，该方法不仅具有更高的推荐准确性，而且能够有效缓解冷启动问题。图5展示了对于冷启动的用户和物品，不同方法对PMF的性能提升结果。此外，该方法能够根据用户的打分特性对用户进行聚类。实例研究表明聚类结果较好反映了用户群体特征。 推荐的可解释性一直是透明可信的推荐结果的必要条件，也是很多推荐模型所缺乏的功能。由于元路径的语义特性，SemRec可以对推荐结果进行解释，进而设计了可解释的语义推荐原型系统RecExp [10]。图6的左上图显示了系统提供的由不同元路径产生的不同的推荐功能；当用户选择混合推荐功能时(Hybrid recommendation)，图6的右上图将给出推荐原因。根据权重最高的三条元路径的路径语义给出推荐原因。 图3. 豆瓣数据集构成的异质信息网络及其网络模式 图4. 基于元路径的语义推荐方法 图5.用户或者物品冷启动实验结果。 纵坐标是不同方法对PMF的性能提升 图6. 可解释的语义推荐原型系统RecExp的主要功能界面 四、未来发展 虽然异质信息网络已经应用于很多数据挖掘任务，但它仍然是一个年轻而且快速发展的研究领域。在这里我们简单讨论一下未来的研究方向。 4.1 更加复杂的网络构建 当前的研究大多假定异质信息网络是明确定义的，网络中的对象和关系是清晰的。然而，实际应用中，从真实的数据中构造异质信息网络会遇到很多挑战。对于像关系数据库等结构化数据，构造异质信息网络是比较容易的，然而在这种网络中，对象和关系可能是有噪声的。比如，会出现对象重名或关系不完整等问题；对于像文本、图像等非结构化数据，如何准确的抽取出相应的对象和关系进而建立更加完善和准确的异质信息网络也将面临更多的挑战，会用到诸如信息抽取，自然语言处理、图像处理等各种技术。 4.2 更加强大的分析方法 在异质信息网络中，对象可通过不同的方式组织在一起。星型模式是广泛使用的异质信息网络类型，例如前面介绍的科技文献网络。之后，又出现了带环的星型模式和有多中心网络等网络模式。实际应用中，网络化数据通常是更加复杂和没有规律性。某些实际网络中的链路会包含属性值，而这些属性值可能包含有重要的信息，这样构成了带权异质信息网络，例如前面介绍的电影网络。一些应用中，用户可能存在于多个异质网络中；这时需要对齐不同网络中的用户，有效的融合不同网络的信息[11]。还有很多网络数据，例如知识图谱，包含有很多种类型的对象和关系，很难用简单的网络模式来描述[12]。这种丰富模式的异质网络中也出现了很多新的研究问题，例如多种类型对象关系的管理以及元路径的自动产生等。这些复杂的网络化数据，给异质信息网络建模与分析提出了更多的机遇和挑战。 异质信息网络中的对象和关系包含有丰富的语义信息，而元路径可以捕捉这种语义信息。此外，元路径也可以用于特征抽取，进而用于各类数据挖掘问题。异质信息网络中的很多数据挖掘任务也是基于元路径进行研究的。但是元路径在某些应用场景中并不能捕捉到精细的语义信息。例如，“作者-论文-作者”路径表示了作者之间的合作关系，但却不能描述特定条件下（例如KDD领域）的合作关系。为了克服这个不足，很多研究者提出了受限元路径[13]、带权元路径[9]、元结构[14]等概念扩展元路径的语义抽取能力。针对更加复杂的网络结构（如知识图谱），如何设计更加灵活精细的语义探索工具仍然需要进一步研究。 近些年出现的深度学习在图像、自然语言等高维复杂数据处理上展现了优异的特征抽取能力，因此可以利用深度学习方法处理异质网络数据。当前深度学习和表示学习已经开始用于网络的结构特征表示[15]。异质网络中包含不同类型的节点和边，而且元路径体现了丰富的语义信息。这些特征使得异质网络的特征表示学习表现出很大的不同。异质网络的表示学习对异质网络分析提出了新思路，也为结构信息与其他模态信息融合提供了新途径。 图7从网络结构和语义探索两个角度，总结了该领域的一些典型工作[1]。沿着X轴，网络结构变得更加复杂；沿着Y轴，语义信息变得更加丰富。例如，PathSim [2]可以处理星型模式网络，并使用元路径挖掘语义关系。SemRec [9]在基本的元路径上增加了链接的权值约束，以在带权异质网络中探索更微妙的语义信息。从图中我们还可以发现，大多数研究都集中在简单的网络结构（例如，二分或星型模式网络）和基本语义探索（例如，元路径）上。在未来，我们可以利用更强大的语义探索工具来分析更复杂的异质网络。 图7 从网络结构和语义探索维度上对异质网络的 典型工作的总结 4.3更大数据的处理 为了展现异质网络建模的优势，我们需要在更广泛的领域中对大型网络化数据设计实用的数据挖掘算法。多样性是大数据的重要特征，异质网络是处理大数据多样性的有效方法。然而，构建一个真正的基于异质网络的分析系统也是具有挑战性的工作。实际的异质网络是巨大的，甚至是动态的，所以它通常不能存储在内存中直接处理。由于用户往往只对一小部分节点、链接或子网络感兴趣，我们可以根据用户需求，从现有网络中动态地提取子网络进行分析。另外，设计基于异质网络的快速算法和并行算法也是亟需研究的内容。 五、结论 近年来由于异质信息网络包含全面的结构和丰富的语义信息，采用异质网络建模和分析的研究大量涌现。本文对这个发展快速的领域进行了一个简单通俗的介绍。希望研究者更好地了解异质信息网络分析的基本思路和特点，能够采用这种模式对实际的网络化数据进行建模和分析。 参考文献 [1] C. Shi, Y. Li, J.Zhang, Y.Sun, P. Yu. A survey of heterogeneous information network analysis [J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(1): 17-37. [2] Y. Sun, J. Han, X. Yan, P. Yu, and T. Wu, “PathSim: meta pathbased top-k similarity search in heterogeneous information networks,” in VLDB, pp. 992–1003 (2011). [3] Sun, Y., Norick, B., Han, J., Yan, X., Yu, P.S., Yu, X.: Integrating meta-path selection with user-guided object clustering in heterogeneous information networks. In: KDD, pp. 1348–1356 (2012). [4] Kong, X., Yu, P.S., Ding, Y., Wild, D.J.: Meta path based collective classification in heterogeneous information networks. In: CIKM, pp. 1567–1571 (2012). [5] Cao, B., Kong, X., Yu, P.S.: Collective prediction of multiple types of links in heterogeneous information networks. In: ICDM, pp. 50–59 (2014). [6]Chuan Shi and Philip S. Yu. Heterogeneous Information Network Analysis and Applications. Springer (ISBN 978-3-319-56212-4), 2017. [7] C. Shi, X. Kong, Y. Huang, S. Y. Philip, and B. Wu, “HeteSim: A general framework for relevance measure in heterogeneous networks,” IEEE Transactions on Knowledge & Data Engineering, vol. 26, no. 10, pp. 2479–2492, 2014. [8] G. Jeh and J. Widom, “SimRank: a measure of structural-context similarity,” in KDD, pp. 538–543 (2002). [9] C. Shi, Z. Zhang, P. Luo, P. S. Yu, Y. Yue, and B. Wu, “Semantic path based personalized recommendation on weighted heterogeneous information networks,” in CIKM, pp.453-462 (2015). [10] J.Hu, Z.Zhang, J.Liu, C.Shi et al. RecExp: A semantic recommender system with explanation based on heterogeneous information network. RecSys 2016. [11] J. Zhang and P. Yu, “Integrated anchor and social link predictions across social networks,” in IJCAI, 2015. [12] C.Wang, Y. Sun, Y. Song, J. Han, Y. Song, L.Wang, and M. Zhang, “RelSim: Relation similarity search in schema-rich heterogeneous information networks.” [13] C. Shi, Y. Li, P. S. Yu, and B. Wu, “Constrained-meta-path-based ranking in heterogeneous information network,” Knowledge and Information Systems, pp. 1–29 (2016). [14] Huang, Z., Zheng, Y., Cheng, R., Sun, Y., Mamoulis, N., Li, X.: Meta structure: Computing relevance in large heterogeneous information networks. In: KDD, pp. 1595–1604 (2016). [15] Perozzi B., Al-Rfou R., Skiena S., Deepwalk: Online learning of social representations, in KDD, pp. 701-710 (2014). 作者简介 石川 石川，博士、北京邮电大学计算机学院教授、博士研究生导师、智能通信软件与多媒体北京市重点实验室副主任。主要研究方向: 数据挖掘、机器学习、人工智能和演化计算。近五年来，作为第一作者或通信作者发表高水平学术论文40余篇，英文专著一部，包括数据挖掘领域的顶级期刊和会议IEEE TKDE、ACM TIST、KAIS、DKE、KDD、SDM、EDBT、ECML、CIKM等。获得ADMA2011国际会议最佳论文奖、CCF-腾讯犀牛鸟基金及优秀奖，并指导学生获得顶尖国际数据挖掘竞赛IJCAI Contest 2015 全球冠军。获得北京市高等学校青年英才计划支持。 “犀牛鸟论道”是由腾讯高校合作团队打造的原创类科技文章专栏，提倡深度、前瞻性、权威性与通俗晓畅的可读性。专栏聚焦科研前沿与趋势，评点技术与壁垒，探究创新之本源，旨在为学术界和产业界专家提供一片智慧与卓越见解的分享之地，让思考和成就得以沉淀。 版权所有，欢迎个人转发。 来信来稿请联系：kunyuan@tencent.com |
|
|
