1.1.2　复杂图

我们前面讨论的简单图都是同质的, 它们只有一种节点类型和一种边类型。实际上, 现实世界中的图要复杂得多, 下面介绍常见的复杂图。

首先, 我们将介绍异质图的定义。异质图又称为异质信息网络 (Heterogeneous Infor-mation Network, HIN), 用于在实际应用中对多种类型的节点之间的多种关系进行建模。我们在图 1.2 (a) 中描述了一个异质图的示例, 异质图可以形式化地定义如下。

定义 1.7　异质图　异质图 包含一组节点 和一组边 , 。每个节点 和边 都与它们的类型映射函数 和 相关联,其中 。

由于异质图包含多种节点类型和边类型, 为了理解其整体结构, 我们有必要提供关于图的元级别 (或模式级别) 描述。于是, 网络模式被提出以对图进行抽象描述。例如, 我们在图 1.2 (b) 中展示了一个网络模式的示例, 并进一步给出了以下定义。

定义 1.8　网络模式^[244]　给定异质图 ,网络模式 可以看作 的元格板,其中包括节点类型映射函数 和边类型映射函数 。图 1.2 (b) 展示了学术异质图的网络模式。

为了捕捉异质图中的结构和语义相关性, 人们设计了基于元路径 [见图 1.2 (c) ] 或基于元图 [见图 1.2 (d) ] 的方法。元路径可以用来引导随机游走, 基于元路径的随机游走是给定元路径下随机生成的实例。

图1.2　学术异质图示例,包括(a)4种类型节点(作者(A)、论文(P)、会议(C)和术语(T))和3种类型连接(即发表、包含和撰写),(b)网络模式,(c)元路径[作者-论文-作者(APA)和作者-论文-会议-论文-作者(APCPA)],以及(d)元图

定义 1.9　元路径^[175]　给定异质图 ,元路径 表示为 , 其中 和 分别表示某些类型的节点和边。元路径定义了从类型 到类型 的复合关系,其中关系可以表示为 。

不同的元路径从不同的视角捕捉语义关系。图 1.2中展示的那个元路径的例子, 可以看作元路径 “APA” 和 “APCPA” 的组合, 反映了两个节点的高阶相似性。例如, 元路径“APA” 表示合著关系, 元路径 “APCPA” 表示共同会议关系, 它们都可以用于描述作者之间的相似度。请注意, 元图可以是对称的或非对称的。

虽然元路径可以用来描述节点之间的连接, 但它无法捕捉更复杂的关系, 比如 motif。元图的提出解决了这个挑战, 元图使用节点和链接类型的有向无环图来捕捉两个异质图节点之间更复杂的关系。

定义 1.10　元图^[87]　元图 是由多个具有共同节点的元路径构成的有向无环图 (Directed Acyclic Graph,DAG)。在形式上,元图定义为 ,其中 是节点集合, 是链接集合。对于任何节点 ; 对于任何链接 。

另外, 为了捕捉不同对象之间的交互, 另一种被广泛使用的图称为二分图。例如, 在许多电商平台 (如亚马逊) 上, 用户的单击历史可以建模为一个二分图, 其中用户和商品是两个不相交的节点集合, 而用户的单击行为则构成它们之间的边。具体来说, 我们在图 1.3 (a) 中展示了一个二分图的例子。

定义 1.11　二分图　给定一个二分图 ,其中 由两个不相交的节点集合 和 组成,即 且 。此外,任意两个来自相同节点集合的节点之间不存在边。对于任意一条边 ,我们有 和 。

接下来, 我们将讨论能够捕获时间信息的图。上述提到的图都是静态的, 即在观察时，节点之间的连接是固定的。然而在许多实际应用中, 图是不断演化的, 新的节点被添加到图中, 新的边不断出现。例如, 我们在图 1.3 (b) 中展示了一个具有动态链接信息的图。下面我们给出动态图的正式定义。

图1.3　二分图和动态图的示例

定义 1.12　动态图　动态图 具有不断变化的节点集合 和边集合 。具体而言,每个节点或每条边都与指示它们出现的时间戳 相关联。

现实中, 我们可能无法记录每个节点和 (或) 每条边的所有时间戳, 因此通常使用快照来检查图的演变,其中,时间戳为 时观察到的图可以表示为 。例如,图 1.3 (b) 中的动态图由多个图的快照组成。