异构信息网络

与homogeneous同构信息网络相区别,异构信息网络的网络模式限定了对象集合以及对象间关系的类型约束。这些约束使得异构信息网络具有半结构化的特点,引导着网络语义的探究。异构信息网络可以由许多相互连接的、大规模的数据集来构造,范围涉及社会、科学、工程、商业应用等。

简介

要理解异构信息网络,首先需要对信息网络的概念有所了解。信息网络是对现实世界的抽象表示,侧重于对象和对象之间的交互,一个信息网络的正式定义如下:

信息网络是带有对象类型映射ϕ: V → A和链接映射ψ: E → R的有向图G=(V,E)。每个对象v∈V属于某一个特定对象类型φv∈A,且每个链接e∈E属于关系类型集合Rψe∈R中的特定关系类型。如果两个链接属于相同的关系类型,这两个链接共享相同的起始对象类型以及结束对象类。

当代大多数信息网络分析都有一个基本假设:对象或链接的类型是独特的。也就是说,网络是同构的,包含相同类型的对象和链接。这些同构网络通常是通过简单地忽略物体和链接的异质性或仅考虑一种类型的对象之间的一种类型的关系。然而,大多数真实网络都包含多类型的交互关系,我们可以用不同类型的对象和链接将它们建模为异构信息网络(简称HIN或异构网络)。基于这个概念之上,异构信息网络的定义为:

如果对象的类型| A |>1 或关系类型| R | > 1,信息网络被称为异构信息网络;否则,它是一个同质的信息网络。

与广泛研究的同构网络相比,异构信息网络包含更丰富的结构和语义信息,为数据挖掘提供了大量的机会和挑战。

例如,在书目数据库中,论文通过作者,场所和术语连接在一起,下图显示了一个关于书目数据的HIN例子—— 书目信息网络——例如涉及计算机科学研究人员的书目网络,这是一个典型的异构网络,包含三种信息实体(information entity):论文,刊物和作者。对于每篇论文,它都链接到一组作者和一个刊物,这些链接属于链接类型的集合。

[图片来源:

Shi, C.; Li,Y.;Zhang J.; Sun, Y.; Yu, P. S. (2017). A Survey of Heterogeneous Information Network Analysis.IEEE Transactions on Knowledge and Data Engineering.29(1):17 - 37.

]

此外,社交网络也是一个典型的例子,如在Flickr中,照片通过用户,群组,标签和评论链接在一起。这个异构信息网络的对象类型包括图片、用户、标签、分组、评论等,它的关系类型包括用户与图片之间的上传、图片与标签之间的包含、图片与分组之间的属于、用户与评论之间的发表、评论与图片之间的评论等。

异构网络vs同构网络:异构网络包括不同类型的节点或链接,而同构网络只有一种类型的对象和链接。同构网络可被视为异构网络的特例。而且,异构网络可以通过网络映射(network projection)或忽略对象异质性转化为同构网络,但同时会造成重要信息丢失。传统的链接挖掘(link mining)通常基于同构网络,许多同构网络分析技术不能直接应用于异构网络。

下面区别一些相近概念:

异构网络vs多关系网络(multi-relational network:与异构网络不同,多关系网络只有一种类型的对象,但有多种对象之间的关系。因此,多关系网络可以看作是异构网络的一个特例。

异构网络vs多维/模式网络(multi-dimensional/mode network):多维/模式网络与多关系网络具有相同含义,也就是说,网络只有一种类型的对象和多种对象之间的关系。因此,多维/模式网络也是异构网络的特例。

异构网络与复合网络(composite network):复合网络中的用户具有不同的关系,在每个单独的网络或子网中表现出不同的行为,并且同时在网络上共享一些共同的潜在兴趣。所以复合网络实际上是一个多关系网络,异构网络的一个特例。

异构网络vs复杂网络(complex network):一个复杂网络是具有复杂的拓扑特征和元素之间的连接模式,既不纯粹规则也不纯粹随机的网络。复杂网络的研究汇集了包括数学,物理学,生物学,计算机科学,社会学等许多领域。许多真实的网络是复杂的网络,如社交网络,信息网络,技术网络,生物网络等。所以可以说很多真正的异构网络都是复杂的网络。然而,对复杂网络的研究通常集中在网络的结构,功能和特征上,这与异构网络还是有所不同。

[描述来源:Shi, C.; Li,Y.;Zhang J.; Sun, Y.; Yu, P. S. (2017). A Survey of Heterogeneous Information Network Analysis.IEEE Transactions on Knowledge and Data Engineering.29(1):17 - 37.]

发展历史

描述

由于异构信息网络相对同构信息网络复杂许多,Yizhou SunJiawei Han等学者于2011年提出了元路径(meta path)的概念,基于元路径来分析异构信息网络。其中元路径是由在不同对象类型(即,元级上的结构路径)之间定义的一系列关系组成的路径。在元路径框架下,他们定义了一种名为PathSim的新型相似度量方法,它能够在网络中找到对等对象。同样基于元路径的相似度量方法还有Chuan ShiXiangnan Kong等人于2014年提出的HeteSim,它具有以下属性:(1)统一度量(uniform measure):它可以在统一的框架下度量相同或不同类型对象的相关度; 2)路径约束度量(path-constrained measure):基于通过遵循一系列节点类型连接两个对象的搜索路径来定义对象对的相关性;3)一个半度量度量(semi-metric measure):HeteSim具有一些很好的属性(例如,自身最大和对称),这对许多数据挖掘任务是至关重要的。RenSun等学者的研究也是基于元路径的,但主要针对推荐技术。

由于元结构(meta structure)可以描述两个HIN对象之间的复杂关系,Zhipeng HuangYudian Zheng等学者建议使用元结构——这是一个有边界类型连接的对象类型的有向无环图——以测量对象之间的相似程度。他们根据元结构开发了三个相关性度量。2017Huan Zhao等学者发表了基于元结构的推荐方法,这是目前关于异构信息网络比较新的研究。

异构信息网络可以用于相似性度量、聚类分析、信息融合、排名分析、推荐系统等(见下图):

主要事件

A

B

C

1

年份

事件

相关论文/Reference

2

2011

Yizhou SunJiawei Han等学者于2011年提出了元路径(meta path)的概念

Sun, Y.Z., Han, J.W., Yan, X.F., Yu, P.S., Wu, T.(2011). PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks.Proceedings of the VLDB Endowment. 4:992-1003.

3

2014

Chuan ShiXiangnan Kong等学者提出了HeteSim

Shi, C., Kong, X., Huang, Y., Philip, S.Y., Wu, B.(2014). HeteSim: A General Framework for Relevance Measure in Heterogeneous Networks.IEEE Transactions on Knowledge and Data Engineering. 26(10), 2479–2492.

4

2014

RenSun等学者提出了基于元路径的推荐技术

Yu, X., Ren, X., Sun, Y., Gu, Q., Sturt, B., Khandelwal, U., Norick, B., Han, J.(2014). Personalized entity recommendation: a heterogeneous information network approach. WSDM, pp. 283– 292.

5

2016

Zhipeng HuangYudian Zheng等学者建议使用元结构以测量对象之间的相似程度

Huang, Z., Zheng, Y., Cheng, R., Sun, Y., Mamoulis, N., Li, X.(2016). Meta structure: computingrelevance in large heterogeneous information networks. SIGKDD, pp. 1595–1604

6

2017

Huan Zhao等学者发表了基于元结构的推荐方法,这是目前关于异构信息网络比较新的研究

Zhao, H.; Yao, Q.; Li, J.; Song, Y.; Lee D. L. (2017).Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks. KDD. pp 635-644 .

发展分析

瓶颈

当前异构信息网络融合研究尚处起步阶段,已经提出的研究方法十分有限,其中基于元路径的方法相对异构网络的复杂性仍然过于简单;基于异构信息网络融合的应用型研究是一个非常实用价值的方向,但目前也只有屈指可数的相关研究。

未来发展方向

如上文所述,基于异构信息网络的信息融合具有实用价值,此外,对异构信息网络的理论分析也值得关注。

By Yuanyuan Li

相关人物
孙怡舟
孙怡舟
加州大学洛杉矶分校计算机科学系助理教授,之前曾担任美国东北大学助理教授,2012年博士毕业于美国伊利诺伊大学香槟分校,师从数据挖掘领域领军人物韩家炜教授。研究方向包括信息与社交网络分析、数据挖掘、数据库系统、统计、信息检索、机器学习等。
韩家炜
韩家炜
韩家炜,美国伊利诺伊大学香槟分校计算机系教授,IEEE和ACM院士,美国信息网络学术研究中心主任。曾担任KDD、SDM和ICDM等国际知名会议的程序委员会主席,创办了ACM TKDD学报并任主编。在数据挖掘、数据库和信息网络领域发表论文600余篇。
Philip S. Yu
Philip S. Yu
简介
相关人物