异构信息网挖掘：概念、技术与未来

尹丹++高宏

摘要： 信息网络是一种由图建模的网络，包含顶点和边两个元素。其中顶点代表现实世界中的实体对象，边代表实体之间的联系。实体以及相互之间的联系就构成了信息网络。信息网络广泛存在于现实世界中，如社交网络、生物网络、道路网络、知识库等。信息网络是无所不在的。在现实世界中，信息网络通常被假定为同构的，即网络中顶点的类型是相同的，顶点之间的关系类型也是相同的。然而，大多数真实世界的网络是异构的，即顶点和关系的类型是不同的。异构信息网是包括多种类型顶点和多种类型的边的信息网。异构信息网可以在很多领域中构建得到，如社交网络、电子商务、在线电影数据库等许多数据库应用中。因此，异构信息网能够很好地表达现实世界中不同类型实体和实体之间复杂的关系。全面介绍了异构信息网的现有研究工作，并对该领域未来可能的发展方向进行了总结和展望。

关键词：异构信息网； 数据挖掘； 查询

中图分类号： TP311.1

文献标志码： A

文章编号： 2095-2163（2016）06-0094-04

0引言

信息网络是一种由图建模的数学模型，其中包含顶点和边两个元素。顶点代表现实世界中的实体对象，边代表实体之间的联系，实体以及实体之间的联系就构成了信息网络。随着信息技术的发展，越来越多的领域开始关注于数据对象之间错综复杂的关系。例如，生物信息学领域中研究基因、酶、蛋白质之间复杂的调控、代谢与交互关系；互联网搜索领域中研究网页与网页之间超链接的关系；社会学和商业领域中研究人与人之间的社会关系。随着信息技术的发展，特别是互联网技术的发展，各种应用领域的信息量都呈爆炸性增长趋势。在现实应用中积累了大量的图数据，例如生物信息学中的基因调控网络、酶代谢网络、蛋白质交互网络；互联网领域的网页拓扑结构图、邮件通讯关系图；在线社交网站中用户之间的社会关系图；城市的道路交通网络、供水排水网络等。信息网络广泛存在于现实世界中，如社交网络、生物网络、道路网络、知识库等。信息网络上的查询和挖掘问题也具有重要的研究意义。

这些图数据的规模还在不断快速增长，其中蕴含了大量有用的知识。挖掘和处理图数据可以得到这些有用的信息帮助用户分析决策。截至2009年9月，全球最大的社交网络Facebook已有3亿多个顶点。这些大规模图数据承载了海量信息。用户根本无法通过视觉观察或手工方法来理解和分析。并且，现实世界中实体不仅仅是单纯的一种类型，而是多种类型的实体同时存在一个网络中；再有，联系也不仅仅存在于同一类型的实体内部，在不同类型的实体之间同样也存在着关系。异构多属性图是包含多种类型顶点和多种类型边的图，其中每种类型顶点具有一组属性。如生物网络、社交媒体网络、在线分享网络等。在图数据规模爆炸式增长的同时，图数据的形式也越来越复杂。因此，海量图数据模型中蕴含着大量有用的知识与信息，亟需从不同维度和不同粒度上对其进行研究提取、挖掘分析。

[BT4]1异构信息网

[BT5]1.1异构信息网的概念

在现实世界中，信息网络通常被假定为同构的，即网络中顶点的类型是相同的（如用户），顶点之间的关系类型也是相同的（如朋友关系）。然而，大多数真实世界的网络是异构的，即顶点和关系的类型是不同的。例如，在医疗保健网络中，顶点可以是病人、医生、医疗检查、疾病、药物、医院、治疗等。把顶点全部看作一种类型，也就是同构信息网络，可能导致丢失重要的语义信息。因此，对具有丰富信息和复杂结构的异构信息网进行分析和挖掘研究是非常重要的。下面将给出异构信息网的形式化定义。

异构信息网是一个有向图G=（V，E，T，R，V，E，A，D，A），其中V是頂点集合，EV×V是边集合，T是顶点的类型集合，R是边的类型集合。V：V→T是顶点类型映射函数，E：E→R是边类型的映射函数。A是顶点的属性集合，D是A的域。A：T→A是从顶点类型到属性的映射函数。

[BT5]1.2异构信息网的应用

异构信息网可以从交互的大规模数据中构建得来，例如社交网络、科学网络、工程及商业应用等，下面文中则给出几个例子用以具体说明。

1）社交媒体网。 Twitter也可以被看做一个异构信息网络，其中包含顶点类型有用户、推文、标签和词语。2个用户可以互相关注，用户可以发布或回复推文，推文可以使用词语、并包含某些标签。Flickr是一个图片分享网站，也可以被看成异构信息网。其实现结构中包含的顶点类型有：图片、用户、标签、分组和评论。用户可以上传图片，图片包含某些标签、图片属于某个分组，用户可以对图片发表评论，图片可以有不同的评论。

2）物联网。在智能家居、交通、物流、农业等物联网中，都可以构建出异构信息网。例如，在智能家居网络中，顶点类型有用户、智能终端（空调、热水器、音响等）、智能控制系统、传感器节点、手机或电脑。用户通过手机或电脑远程发送命令给智能控制系统，智能控制系统将命令发送给相应的传感器节点，传感器节点再根据用户的需求发送命令给指定的智能终端对其进行操作。

3）文献信息网络。从DBLP中提取的计算机科学文献信息就是一个典型的异构信息网，其中包含4种类型顶点：论文、会议、作者和关键词。每篇论文对应一个作者集合、一个会议和一组关键词，构成了3种类型的关系。同时，在论文之间还存在引用关系。

4）医疗健康网络。 医疗健康系统也可以被看成一个异构信息网，其中包含的顶点类型有医生、病人、疾病、治疗和设备。病人患有某种疾病，该疾病可以采取特定的治疗方案，使用某种设备，此外，病人也需要由特定的医生负责。

异构信息网可以在很多领域中构建得到，如社交网络、电子商务、社交媒体等许多数据库应用中。异构信息网包含多种类型的顶点和多种类型的边，每种类型顶点包含一组属性。例如，用户的属性可以是其编号、姓名、年龄、城市等。

2异构信息网研究现状

除了异构信息网上复杂的结构信息，顶点的属性信息对于挖掘异构信息网也发挥着至关重要的作用。信息网上现有大多数研究成果都是基于同构信息网的，比如社交网络[1]上的排序、社团发现、链接预测、影响力传播等。然而，这些方法都不能直接用于异构信息网上。这不仅因为连接不同类型顶点之间的不同类型的边所具有的语义不同，也是因为异构信息网包含了比同构网络更丰富的信息。同构信息网可以通过在异构信息网上的投影得到，但是却丢失了大量的信息。例如，作者合作网络可以从更复杂的异构的文献信息网络中投影得到。然而，这种投影操作丢失了有用的信息，如该论文的主题以及该论文作者合作的其它论文等。另外，在原始的异构信息网中蕴藏着丰富的信息，需要设计有效的数据挖掘方法用来探索这些有用的信息。

相比传统同构信息网上的研究，异构信息网上的研究工作才获发展起步。但在最近几年，越来越多的工作开始关注异构信息网方面的研究。异构信息网上现有的研究工作还都比较零散，也未形成规模体系，主要有聚簇[2–7]、基于排序的分类[8- 9]、顶点的相似性搜索[10- 11]、关系预测[12-14]、子图查询[15- 16]、社区发现[17]、实体识别[18]、无结构查询[19]等。下面，文中将分别介绍这些已有的研究成果。

2.1异构信息网上聚簇问题的研究

Rankclus[2]将DBLP网络构建成二分图，根据排序将相同类型的定点进行聚集。信息网络的分析中，文献[4， 7]根据用户选择的顶点类型和簇的种子顶点，对该类型的顶点进行聚簇。文献[6]在顶点属性不完整的情况下，基于顶点的属性和不同类型的关系，对网络进行聚簇。系统通过学习得到不同类型的关系的权重，将用户指定的属性集合带有权重的不同类型关系合并，建立一个概率模型，用于训练出最符合用户需求的聚簇结果。文献[5]以网络中的一种类型顶点为中心，根据元路径将网络分解成为若干个路径图。元路径是不同类型顶点构成的序列，表示了顶点由不同的关系连接起来。例如元路径“作者-论文-作者”代表作者之间的合作关系，元路径“作者-论文-会议-论文-作者”表示在同一个会议发表过论文的作者。通过学习得到每个路径图的权重，将所有路径图加权得到统一的路径图。在该路径图上对顶点进行聚簇。

2.2异构信息网上分类问题的研究

RankClass[8]把排序与分类相结合，对异构信息网进行更好的分析。该方法把顶点进行分类，在每个分类内对顶点进行排序。例如，对于DBLP 异构信息网，先把会议顶点按照领域进行分类，在每个领域内对顶点进行排序，可以使用户很清楚地了解每个领域内影响较大的会议。这种排序与分类相结合的方法，要好于对顶点进行全局的排序。分类对顶点进行排序提高了排序的质量，优秀的排序结果也使分类更为准确。GNetMine[9]研究异构信息网络上只有一部分顶点具有标签，通过将顶点分类，得到所有顶点的标签问题。通过衡量无标签顶点与带有标签顶点之间链接关系的一致性，把无标签顶点与其相关的带有标签顶点划为同一类，得到所有类型顶点的标签。

[BT5]2.3异构信息网上顶点相似/相关性问题的研究

基于元路径的异构信息网上的搜索技术在最近两年得到了关注与重视。Pathsim[10]提出计算2个同类型顶点在给定元路径情况下的相似性的方法。2个顶点通过不同的元路径连接表示不同的含义，其相似性也不相同。信息网上现有的相似性所有工作大多数都集中在同构信息网上。这些工作都忽略了顶点由不同类型的关系连接，具有的含义不同。进一步地，给定查询顶点，Pathsim能够有效地计算出与查询相似度最高的k个顶点，效率远远高于PageRank和SimRank. HeteSim[11]提出異构信息网上同类型或不同类型顶点之间相关性的度量。衡量不同类型顶点之间的相似性是十分有意义的。如作者J.F. Naughton与会议SIGMOD相关程度比会议KDD大，青少年更喜欢电影哈利波特，而不是肖申克的救赎。这种不同类型顶点的相关性研究有着大范围的广泛应用，例如推荐系统、聚簇和协同过滤。该方法描述的顶点相关性是基于搜索路径的，2个顶点通过特定的元路径相连。不同的搜索路径含义不同，导致2个顶点的相关程度也将出现不同变化。因此相关性的度量函数也是不对称的。

[BT5]2.4异构信息网上链接预测问题的研究

异构信息网上的链接预测问题已然面世推出了一些重点研究成果。PathPredict[12]提出了异构信息网上预测合作关系的方法。文章用4种度量函数：路径个数、标准化路径个数、随机游走、对称随机游走，来计算2个顶点在所有元路径上的相似性。通过监督模型去训练出不同结构特征的预测权重，得到统一的预测模型。大多数的链接预测工作都是集中在同构网上，并且只关注链接是否发生，而无法预测发生的时间。针对这个问题，文献[13]提出一种链接预测模型，并给出链接发生的未来时间，如作者将于某年在会议上发表论文，用户在某个时间将会对电影做出评论等。Anchoring[14]对多个异构信息网之间的用户进行链接预测。单个用户可能在多个社交网络上都拥有注册账号，这篇文章就是为了识别不同的社交网络之间哪些账号是属于同一个用户的。通过用户在社交网络上展现的个人信息、活动时间、地点和文本信息，清晰确认并识别账户的对应关系。当一个人刚刚注册某个社交网站时，利用这种链接预测方法，就可以对其推荐符合标准预期的理想朋友。

2.5异构信息网上子图查询问题的研究

文献[15]研究异构信息网上搜索结构和语义都相似的子图。为了提高效率，利用离线的索引生成候选子图，进一步递归剪枝对候选子图进行验证。文献[16]研究给定查询的模式，计算top-k相似子图的方法。为了解决这个问题，文章提出2种低代价索引：图拓扑索引和最大元路径索引。利用这2种索引，对候选的子图进行剪枝，快速计算得到查询结果。

[BT5]2.6异构信息网上社区发现问题的研究

文献[17]提出动态异构信息网上社区发现的方法。该方法为异构信息网建立社区模型，每个社区包含网络上所有类型的顶点和边。用Dirichlet混合模型为每个时间窗上的网络社区实现建模，能够自动确定社区的实现数量并考虑前一时刻的社区对现在时刻的影响。利用Gibbs采样方法推理出该模型。在该模型上解决符合网络演变规律的社区发现问题。

2.7异构信息网上实体识别问题的研究

SHINE[18]提出了异构信息网上实体识别方法。该文结合实体普及模型和实体目标模型，对异构信息网上的实体识别进行建模。实体普及模型依赖于内容，例如，名字是“Wei Wang”的老师比名字是“Wei Wang”的学生发表的论文数量多。实体目标模型确定元路径的概率，通过期望最大化算法自动学习元路径的权重。

2.8异构信息网上无结构查询问题的研究

GQBE[19]提出在用户不知道网络的顶点类型和结构情况下，只给出查询的元组示例，计算与查询相近的结果。如查询示例为，查询结果可能是，，表示了创立人与公司的关系。该方法构建基于输入的最大查询图，生成查询图的晶格。在晶格上得到top-k相似的查询结果。SLQ研究用户在不了解网络结构的情况下，无需给出准确的查询形式，通过转换函数，查找网络中符合查询的匹配。由于转换函数的代价不同，应用条件随机场得到匹配结果关于转换代价的打分函数，最终输出最佳匹配的top-k个结果。

3异构信息网的未来和挑战

异构信息网的应用日趋宽泛普及，随着信息技术、特别是互联网技术的发展，各种应用领域的信息量都已呈现爆炸性增长趋势。传统技术虽然推出了众多研究成果，但却大多集中在同构网络上。

异构信息网上在线分析处理问题的研究对于异构信息网上知识的提取是至关重要的。现有的信息网络在线处理算法都很简单，缺乏对具体模型定义、执行过程分析（时间、空间、I/O、能耗）、核心步骤优化等层面的深入研究。从立方体计算、物化到OLAP操作，以及复杂的冰山立方体计算等，但却并不适用于图数据。

当前，大规模的信息网络上的挖掘和分析工作已有大量的研究人员在开展理论和技术上的各类探讨，但却仍无法从不同的维度和粒度上为用户分析决策提供有效的视图，以及灵活的在线分析处理。时下的在线处理技术缺乏对信息网络方体格、方体、方体单元详细定义，对于其空间爆炸式增长缺乏可行性技术解决方案；而且，现有技术也缺乏对物化方式、实现算法等的深入研究（对于信息网络而言，中间结果的表示和重用对在线信息网络处理的性能至关重要），缺乏对时间性能、空间开销等的切实充分考虑；现有的信息网络OLAP技术在处理大规模数据方面缺乏良好的数据组织、中间结果物化、高效OLAP算法等性能需求的必须解除设施。在实际问题中，用户关注的目标常常是复杂的信息网络度量，并且只关注那些度量大于给定阈值的立方体，如冰山立方体。迄今为止，这方面的研究工作几乎是零起步、全空白；

随着数据规模的日益增大，信息网络的增长尤其巨大。如何解决信息网络立方体中的海量空间开销即已成为首要关键问题，在每个立方体单元中存储的都是一个子图，而不是传统数据立方体中的聚集值，这就给立方体物化过程提出了现实巨大挑战；

巨量的信息网络除了消耗海量的存储空间外，在其上的巨量计算时间也给研究带来了严峻挑战，尤其是对于复杂信息网络度量。通常情况下，立方体计算需要多次遍历信息网络，这就大大降低了在线处理的效率。如何与用户进行快速交互、且高效实现在线处理已经成为研究学界亟待解决的重要问题。

挖掘带有噪声的、不确定的异构信息网。异构信息网的数据往往是由多个数据源集成而来，而每个数据源的质量不尽相同。数据往往带有噪声，同时部分数据也是不确定的。因此，研究帶有噪声的、不确定的异构信息网上的挖掘问题对于异构信息网的实际应用则表现出其独特意义及实用价值。

4结束语

随着大数据时代的到来，数据的形式也越来越复杂。随着信息网络的飞速发展，如社交网络、生物网络、道路网络、知识库等，异构信息网应运而生。大多数真实世界的网络都是异构的，即顶点和关系的类型是不同的。异构信息网是包括多种类型顶点和多种类型的边的信息网。异构信息网可以在很多领域中构建得到，如社交网络、电子商务、在线电影数据库等许多数据库应用中。异构信息网能够很好地表达现实世界中不同类型实体以及实体之间的复杂关系。异构信息网上的挖掘问题对于复杂数据形式的分析是十分重要的。本文系统介绍了异构信息网上广泛的应用背景和现有的研究工作，并提出未来的进一步发展方向，期望有更多的研究者投身到这一领域的学术关注和研究中。

参考文献：

[1] AGGARWAL C C. Social network data analytics[M]. New York： Springer， 2011.

[2] SUN Y， HAN J， ZHAO P， et al. RankClus： integrating clustering with ranking for heterogeneous information network analysis[C]//Proceedings of International Conference on Extending Database Technology： Advances in Database Technology. New York， USA： ACM， 2009：565-576.

[3] SUN Y ，YU Y， HAN J. Rankingbased clustering of heterogeneous information networks [JP3]with star network schema[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York， USA： ACM， 2009：797-806.[JP]

[4] SUN Y， NORICK B， HAN J， et al. Integrating metapath selection with userguided object clustering in heterogeneous information networks[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York， USA： ACM， 2012：1348-1356.

[5] YANG Z， LING L， DAVID B. Integrating vertexcentric clustering with edgecentric clustering for meta path graph analysis[C]//Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York， USA： ACM， 2015：1563-1572.

[6] SUN Y， AGGARWAL C C， HAN J. Relation strengthaware clustering of heterogeneous information networks with incomplete attributes[J]. Endowment of Very Large DataBases， 2012， 5（5）：394-405.

[7] SUN Y， NORICK B， HAN J， et al. PathSelClus： Integrating metapath selection with user-guided object clustering in Heterogeneous information networks[J]. ACM Transactions on Knowledge Discovery from Data， 2013， 7（3）：1-23.

[8] JI M， HAN J， DANILEVSKY M. Rankingbased classification of heterogeneous information networks[C]//Proceedings of ACM SIGKDD Int. Conference on Knowledge Discovery and Data Mining. New York， USA： ACM ， 2011：1298-1306.

[9] JI M， SUN Y， DANILEVSKY M， et al. Graph regularized transductive classification on heterogeneous information networks[C]//Proceedings of European Conference Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Springer Berlin Heidelberg， 2010：570-586.

[10] SUN Y， HAN J， YAN X， et al. Pathsim： Meta pathbased topk similarity search in heterogeneous information networks[C]//Proceedings of Very Large Databases Endowment. New York， USA： ACM， 2011：992-1003.

[11] SHI C， KONG X， YU P S， et al. Relevance search in heterogeneous networks[C]//Proceedings of international conference on extending database technology. New York， USA： ACM， 2012：180-191.

[12] SUN Y， BARBER R， GUPTA M. Coauthor relationship prediction in heterogeneous bibliographic networks[C]//International Conference on Advances in Social Networks Analysis and Mining. Piscataway， NJ： IEEE， 2011：121-128.

[13] SUN Y， HAN J， AGGARWAL C C， et al. When will it happen？ Relationship prediction in heterogeneous information networks[C]//Proceedings of ACM International Conference on Web Search and Data Mining. New York， USA： ACM， 2012：663-672.

[14] KONG X， ZHANG J， YU P S. Inferring anchor links across multiple heterogeneous social networks[C]//Proceedings of ACM International Conference on Information & Knowledge Management. New York， USA： ACM， 2013：179-188.

[15] YU X， SUN Y， ZHAO P， et al. Querydriven discovery of semantically similar substructures in heterogeneous networks[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2012：1500-1503.

[16] GUPTA M， GAO J， YAN X. Topk interesting subgraph discovery in information networks[C]//Proceedings of IEEE International Conference on Data Engineering. Piscataway， NJ： IEEE， 2014：820-831.

[17] SUN Y， TANG J， HAN J， et al. Community evolution detection in dynamic heterogeneous information networks[C]//Proceedings of the Eighth Workshop on Mining and Learning with Graphs MLG at KDD. New York， USA： ACM， 2010：137-146.

[18] SHEN W， HAN J， WANG J. A probabilistic model for linking named entities in web text with heterogeneous information networks[C]//Proceedings of ACM SIGMOD International conference on Management of Data. New York， USA： ACM， 2014：1199-1210.

[19] YANG S， WU Y， SUN H. Schemaless and structureless graph querying[J]. Endowment of Very Large Databases， 2014， 7（8）：565-576.