【Intro】Heterogeneous Graph Attention Network（HAN）

论文链接：https://arxiv.org/pdf/1903.07293

Abstract

异构性和丰富的语义信息给面向异构图的图形神经网络设计带来了巨大的挑战。

-> 一种基于分层注意的异构图神经网络，包括节点级注意和语义级注意。具体来说，节点级关注旨在学习节点与其基于元路径的邻居之间的重要性，而语义级关注能够学习不同元路径的重要性。通过对节点级和语义级的关注，可以充分考虑节点和元路径的重要性。然后，该模型可以通过分层方式聚合基于元路径的邻居的特征来生成节点嵌入。

metapath 元路径

metapath及其相关概念（持续更新ing...）-CSDN博客

https://arxiv.org/pdf/2309.17113

【Embedding】Metapath2vec：异构网络表征-腾讯云开发者社区-腾讯云

Meta Path_meta-path-CSDN博客

meta-path $\mathcal{P}$ 定义在network schema $T_G = \left ( \mathcal{A}, \mathcal{R} \right )$ 上，具体形式为：

$\mathcal{A}_1\overset{ \mathcal{R}_1}{\rightarrow} \mathcal{A}_2\overset{ \mathcal{R}_2}{\rightarrow} \cdot \cdot \cdot \overset{ \mathcal{R}_l}{\rightarrow} \mathcal{A}_{l+1}$

这其实是在节点类型 $\mathcal{A}_1, \mathcal{A}_{l+1}$ 之间定义了一个组合关系 $\mathcal{R} = \mathcal{R}_1 \circ \mathcal{R}_2 \circ \cdot \cdot \cdot \circ \mathcal{R}l$ 。其中 $\circ$ 代表relation之间的操作。

network schema是啥？

def： $T_G = \left ( \mathcal{A}, \mathcal{R} \right )$

是信息网络 $G=\left ( V, E \right )$ 的一种meta模板，这个信息网络有一个object类型映射函数 $\phi: V \rightarrow \mathcal{A}$ 和link类型映射函数 $\psi: E \rightarrow \mathcal{R}$ 。信息网络G是一个定义在object类型 $\mathcal{A}$ 上的有向图，并且边是 $\mathcal{R}$ 中的relation。

信息网络是啥？

信息网络是只一个有向图 $G=(V,E)$ ，同时还有一个object类型的映射函数 $\phi: V \rightarrow \mathcal{A}$ 和边类型映射函数 $\psi: E \rightarrow \mathcal{R}$ 。

每一个object $v \in V$ 都有一个特定的object类型 $\phi(v) \in \mathcal{A}$

每一条边都有一个特定的relation $\psi(e) \in \mathcal{R}$

heterogeneous network 指的是object类型的 $\left | \mathcal{A} \right |> 1$ 或者relation的类型 $\left | \mathcal{R} \right |> 1$

Introduction

最近深度学习的一个研究趋势是注意机制，它处理可变大小的数据，并鼓励模型关注数据中最突出的部分。它已经在深度神经网络框架中证明了有效性，并被广泛应用于各种应用，如文本分析、知识图和图像处理。图注意网络(GAT)是一种新颖的卷积式图神经网络，它利用了同构图的注意机制，同构图只包含一种类型的节点或链接。

尽管注意机制在深度学习中取得了成功，但在异构图的图神经网络框架中并没有考虑到注意机制。事实上，现实世界的图通常具有多种类型的节点和边，也被广泛称为异构信息网络(HIN)。

由于异构图包含更全面的信息和丰富的语义，它被广泛应用于许多数据挖掘任务中。元路径[32]是一种连接两个对象的复合关系，被广泛用于捕获语义。以图1(a)中的电影数据集IMDB为例，它包含电影、演员和导演三种类型的节点。

电影-演员-电影元路径(Movie-Actor-Movie, MAM)描述了合作演员关系，而电影-导演-电影元路径(MDM)则表示两部电影由同一导演执导。可以看到，根据元路径的不同，异构图中节点之间的关系可以具有不同的语义。由于异构图的复杂性，传统的图神经网络不能直接应用于异构图。

->因此在设计具有异构图注意机制的图神经网络体系结构时，需要解决以下新要求：

Heterogeneity of graph
异构性是异构图的一种内在属性，即节点和边的类型多种多样。例如，不同类型的节点具有不同的特征，其特征可能落在不同的特征空间中。
仍以IMDB数据集为例。演员的特征可能涉及性别、年龄和国籍。另一方面，电影的特点可能涉及情节和演员。如何在处理如此复杂的结构信息的同时，保留各种特征信息是一个迫切需要解决的问题。
semantic-level attention
异构图中涉及不同的有意义的复杂语义信息，这些信息通常通过元路径反映出来。异构图中不同的元路径可以提取不同的语义信息。如何为特定任务选择最有意义的元路径并融合语义信息是一个悬而未决的问题。
语义级关注的目的是了解每个元路径的重要性，并为它们分配适当的权重。仍以IMDB为例，《终结者》可以通过movie - actor - movie(均由施瓦辛格主演)连接《终结者2》，也可以通过Movie-Year-Movie(均拍摄于1984年)连接《鸟人》。然而，在确定电影《终结者》的类型时，MAM通常扮演更重要的角色，而不是MYM。因此，平等地对待不同的元路径是不切实际的，并且会削弱一些有用的元路径提供的语义信息。
node-level attention
在异构图中，节点可以通过各种类型的关系连接起来，例如元路径。给定一条元路径，每个节点都有许多基于元路径的邻居。如何区分这些邻居的细微差别，选择一些有信息的邻居是需要的。对于每个节点，节点级关注的目的是学习基于元路径的邻居的重要性，并为它们分配不同的关注值。
仍以IMDB为例，当使用movie - director - movie元路径(电影由同一导演执导)时，终结者将通过导演詹姆斯卡梅隆连接到泰坦尼克号和终结者2。为了更好地识别《终结者》是科幻电影的类型，模型应该更多地关注《终结者2》，而不是《泰坦尼克号》。因此，如何设计一个能够发现邻域的细微差别并正确学习其权值的模型将是人们所需要的。

->本文提出了HAN，Heterogeneous graph Attention Network

既考虑节点级，也考虑语义级的信息。

特别是，给定节点特征作为输入，我们使用特定类型的变换矩阵将不同类型的节点特征投影到同一空间中。节点级注意能够学习节点与基于元路径的邻居之间的注意值，而语义级注意则能够学习异构图中特定任务在不同元路径上的注意值。基于学习到的两个层次的注意力值，模型能够以分层的方式得到邻居和多个元路径的最优组合，使得学习到的节点嵌入能够更好地捕获异构图中复杂的结构和丰富的语义信息。之后，整个模型可以通过端到端的反向传播进行优化。

Related work

近年来，对图结构数据的泛化卷积运算兴起。图卷积神经网络工作一般分为两类，即谱域和非谱域。一方面，谱方法使用图的谱表示。

图卷积网络，通过谱图卷积的局部一阶逼近设计了一个图卷积网络。另一方面，我们也有非谱方法，它直接在图上定义卷积，在空间近邻的群上操作。graphsage，它在固定大小的邻居上执行基于神经网络的聚合器。它可以学习一个函数，通过聚合节点的局部邻域的特征来生成嵌入。图注意网络（GAT）学习节点与其邻居之间的重要性，并融合邻居进行节点分类。然而，上述图神经网络不能处理各种类型的节点和边，只能应用于齐次图。

网络嵌入（network embedding）即网络表示学习(network representation learning，NRL)，是在保持网络结构和性质的同时，将网络嵌入到低维空间中，使学习到的嵌入可以应用到下游的网络任务中。例如，基于随机行走的方法，基于深度神经网络的方法，基于矩阵分解的方法等，例如LINE。然而，所有这些算法都是针对齐次图提出的。

异构图嵌入主要关注基于元路径的结构信息的保存。ESim接受用户定义的元路径作为指导，在用户偏好的嵌入空间中学习顶点向量，进行相似性搜索。即使ESim可以使用多个元路径，它也无法了解元路径的重要性。为了达到最佳性能，ESim需要进行网格搜索，以找到hmeta-paths的最优权值，然而要找到适合特定任务的最佳组合是相当困难的。

Metapath2vec设计了一种基于元路径的随机游走，并利用skip-gram进行异构图嵌入。但是，metapath2vec只能利用一个元路径，并且可能会忽略一些有用的信息。

与metapath2vec类似，HERec提出了一种类型约束策略来过滤节点序列，捕获异构图中反映的复杂语义。

HIN2Vec执行多个预测训练任务，同时学习节点和元路径的潜在向量。

投影度量嵌入模型（project metric embedding model），称为PME，它可以通过欧几里得距离来保持节点的接近性。PME将不同类型的节点投影到同一关系空间中，进行异构链路预测。

为了研究异构图的综合描述问题，提出了HEER（heterogeneous information network embedding via edge representations）算法，该算法通过边缘表示嵌入异构图。

嵌入模型metagraph2vec，其中结构和语义都最大限度地保留了恶意软件检测。Sun等[30]提出了基于元图（meta-graph-based）的网络嵌入模型，该模型同时考虑了元图中所有元信息（）meta information）之间的隐藏关系。综上所述，上述所有算法都没有考虑异构图表示学习中的注意机制。

Preliminary

一个异构图手一种特殊的信息网络，其中包含了多种object或者多种连接。

定义看原文或参考摘要部分：

🌰

如上图(a)，仍以IMDB数据集为例，我们构造了一个异构图来描述IMDB。其包含了多种object（演员A，电影M，导演D），和多种关系（电影和导演中的拍摄关系，演员和电影之间的出演关系）。在异构图中，两个object可以通过不同的语义路径连接，将其称为meta-path

两个电影可以通过多条meta-path连接。如：电影-演员-电影（MAM）和电影-导演-电影（MDM）。不同的元路径总是揭露不同的语义。比如MAM意味着共同演员的关系，MDM表述电影是由同一位导演执导的。

给定一个元路径 $\Phi$ ，就存在一系列基于每个节点邻居的元路径，这一系列元路径可以揭露异构图中不同的结构信息和丰富语义信息。

🌰

以上图为例，给定元路径MAM，以 $m_1$ 的邻居为基础的元路径包含 $m_1$ （自己）、 $m_2$ 以及 $m_3$ 。类似的，以 $m_1$ 的邻居为基础的元路径MDM包含了 $m_1$ 和 $m_2$ 。显然，以邻域为基础的元路径可以探索异构图的不同角度的结构信息。我们可以通过邻接矩阵序列的乘法得到基于元路径的邻居。

参数定义见下表：

The Proposed Model

semi-supervised gnn for heterogeneous graph

follows a hierarchical attention structure: node-level attention → semantic-level attention.

HAN结构如下图所示：

首先，我们节点级注意力来学习基于元路径的邻居的权值，并将它们聚合以获得特定语义的节点嵌入。然后，人工神经网络通过语义级关注来区分元路径的差异，并得到针对特定任务的语义特定节点嵌入的最优加权组合。

Node-level Attention

在聚合每个节点的元路径邻居信息之前，我们应该注意到每个节点的基于元路径的邻居在特定任务的学习节点嵌入中扮演着不同的角色，表现出不同的重要性。引入节点级关注可以学习基于元路径的邻居对异构图中每个节点的重要性，并将这些有意义的邻居的表示聚合形成节点嵌入

由于节点的异质性，不同类型的节点具有不同的特征空间。因此，对于每种类型的节点（如节点类型为 $\phi_i$ ）设计设计特定类型的变换矩阵 $\mathbf{M}_{\phi _i}$ 将不同类型节点的特征投影到同一特征空间中。类型特定的转换矩阵基于节点类型而不是边缘类型。投影过程如下:

${\mathbf{h}_i}' = \mathbf{M}_{\phi _i} \cdot \mathbf{h}_i$

这里 $\mathbf{h}_i \ {\mathbf{h}_i}'$ 分别是节点i的原始特征和投影特征。通过特定类型的投影运算，节点级注意可以处理任意类型的节点。

之后，利用自关注来学习各种节点之间的权重。给定由元路径 $\Phi$ 连接的节点对 $\left ( i,j \right )$ ，节点级的注意力 $e_{ij}^{\Phi}$ 指的是对于节点i，节点j有多重要。基于节点对 $\left ( i,j \right )$ 的元路径重要性可以描述为：

$e_{ij}^{\Phi} = att_{node}({\mathbf{h}_i}', {\mathbf{h}_j}'; \Phi)$

这里 $att_{node}$ 表示节点级注意的深度神经网络。给定元路径 $\Phi$ ， $att_{node}$ 是基于节点对的所有元路径所共享的，这是因为在一个元路径下存在一些相似的连接模式。对于给定元路径 $\Phi$ ，基于节点对 $\left ( i,j \right )$ 的元路径的权重取决于他们的特征。请注意这里的 $e_{ij}^{\Phi}$ 是不对称的。即，节点i对节点j的重要性与节点j对节点i的重要性是不一样的。这表明节点级的注意力可以保持非对称性，这是异构图的一个关键特性。

然后，我们将结构信息注入到模型中，这意味着对于节点 $j \in \mathcal{N}_i ^{\Phi}$ （ $\mathcal{N}_i ^{\Phi}$ 表示节点i以及其邻居）我们只能计算 $e_{ij}^{\Phi}$ 。在获得基于节点对的元路径的重要性之后，我们对其做归一化，通过softmax函数获得权重系数：

$\alpha_{ij}^{\Phi} = softmax_{j}(e_{ij}^{\Phi}) = \frac{exp(\sigma(\mathbf{a}_{\Phi}^T \cdot \left [ {\mathbf{h}_i}' || {\mathbf{h}_j}' \right ]))}{\sum_{k \in N_i^{\Phi}}^{} exp(\sigma(\mathbf{a}_{\Phi}^T \cdot \left [ {\mathbf{h}_i}' || {\mathbf{h}_k}' \right ]))}$

此处 $\sigma$ 表示激活函数， $||$ 表示连接操作， $\mathbf{a}_{\Phi }$ 是对于元路径 $\Phi$ 的节点级注意力向量。从上面的公式可以看出， $\left ( i,j \right )$ 的权重系数取决于他们的特征。同时，请注意权重系数 $\alpha _{ij}^{\Phi }$ 是非对称的，这意味着他们对彼此做出了不同的贡献。不仅因为分子的连接顺序不同，还因为它们有不同的邻居，所以标准化项(分母)会有很大的不同。

然后，基于元路径的节点i的嵌入可以通过邻居的投影特征进行聚合，相应的系数如下：

$z_i ^{\Phi} = \sigma\left ( \sum_{j \in \mathcal{N}_i ^{\Phi}}^{} \alpha_{ij}^{\Phi} \cdot {\mathbf{h}_j}' \right )$

这里 $z_i ^{\Phi}$ 是节点i关于元路径 $\Phi$ 学到到嵌入。参考下图，理解节点级的聚合操作：

每个嵌入的节点由它的邻居聚合。由于关注权值 $\alpha _{ij}^{\Phi }$ 是针对单个元路径生成的，所以它是特定于语义的，能够捕获一种语义信息。

由于异构图具有无标度的特性，因此图数据的方差很大。为了解决上述挑战，将节点级注意力扩展到多头注意力，从而使训练过程更加稳定。具体来说，我们重复节点级关注𝐾次，并将学习到的嵌入连接为特定于语义的嵌入:

给定元路径集合 $\left \{ \Phi _1, ..., \Phi_p \right \}$ ，将节点特征喂到节点级注意力之后，我们可以得到P组特定语义的嵌入，记作 $\left \{ \mathbf{Z}_{\Phi _1}, ..., \mathbf{Z}_{\Phi _p} \right \}$

Semantic-level Attention

通常，异构图中的每个节点都包含多种类型的语义信息，特定语义的节点嵌入只能从一个方面反映节点。为了学习更全面的节点嵌入，需要融合多个语义，这些语义可以通过元路径显示。为了解决异构图中元路径选择和语义融合的挑战，-> 以从节点级关注中学习到的语义特定节点嵌入的权重为输入，得到每个元路径的学习权重（ $\beta_{\Phi _1}, ..., \beta_{\Phi _p}$ ）:

$\left ( \beta_{\Phi _1}, ..., \beta_{\Phi _p} \right ) att_{sem}\left ( \mathbf{Z}_{\Phi _1}, ..., \mathbf{Z}_{\Phi _p} \right )$

此处， $at t_{sem}$ 表示执行语义级注意的深度神经网络。结果表明，语义层面的注意可以捕获异构图背后的各种类型的语义信息。

为了了解每个元路径的重要性，我们首先通过非线性转换(例如:，单层MLP)。然后我们用语义级关注向量 $\mathbf{q}$ 来衡量语义特定嵌入的重要性。此外，我们平均了所有语义特定节点嵌入的重要性，这可以解释为每个元路径的重要性。每个元路径的重要性，记作 $w_{\Phi _i}$ ：

$w_{\Phi_p} = \frac{1}{| \mathcal{V}|} \sum_{i \in \mathcal{V} }^{} \mathbf{q}^T \cdot tanh\left ( \mathbf{W} \cdot \mathbf{z}_i ^{\Phi_p} + \mathbf{b} \right )$

此处， $\mathbf{W}$ 是权重矩阵， $\mathbf{b}$ 是偏差向量， $\mathbf{q}$ 是语义级的注意力向量。请注意，为了进行有意义的比较，所有元路径和特定语义的嵌入都共享上述所有参数。在得到每个元路径的重要性后，通过softmax函数对它们进行归一化。元路径 $\Phi _i$ 的权重记作 $\beta_{\Phi_i}$ ，可以通过使用softmax函数对上述所有元路径重要性做归一化得到：