GNN从入门到入门02：异质图

上一篇文章我们介绍了图的基础与图嵌入，从 DeepWalk 一路走到 GCN 与 GAT。但真实世界的图往往不止一种节点和一种边：社交网络里有用户、帖子、话题，交通网络里有路口、路段、车辆，摄像头网络里有相机、轨迹、目标。这类图被称为异质图（Heterogeneous Graph），而处理它的难点在于如何让消息传递在"不同类型的节点和边"之间正确地流动。本文从同质图的两个局限出发，先回顾同质 GNN 的基础，再介绍异质图的定义、元路径与早期的异质图嵌入方法，然后介绍三类代表性异质图神经网络（RGCN、HAN、MAGNN、HGT），接着沿着注意力机制的演进路线，详细介绍图 Transformer 的结构编码设计，最后讨论异质图 Transformer 的交汇及其与跨摄像头多目标跟踪场景的联系。

第一部分：从同质图到异质图

同质 GNN 基础回顾

在进入异质图之前，我们先回顾同质 GNN 的三种代表性架构，它们构成后续所有讨论的基线。给定图 $G = (\mathcal{V}, \mathcal{E})$，节点特征矩阵 $X \in \mathbb{R}^{|\mathcal{V}| \times d}$，邻接矩阵 $A$，图神经网络的目标是学习节点表示 $H = \{h_1, \ldots, h_{|\mathcal{V}|}\}$。

GCN（Graph Convolutional Network）：谱域方法的简化近似，核心是邻居特征的平均聚合：

$$h_i^{(l+1)} = \sigma\left( \sum_{j \in \mathcal{N}_i \cup \{i\}} \frac{1}{\sqrt{\hat{d}_i \hat{d}_j}} W^{(l)} h_j^{(l)} \right)$$

其中 $\hat{d}_i$ 是带自环的度数，$\mathcal{N}_i$ 是节点 $i$ 的邻居集合。GCN 的聚合权重是结构决定的固定常数（由度数归一化），不随特征变化。

GraphSAGE：把聚合推广为可学习的采样与聚合：

$$h_i^{(l+1)} = \sigma\left( W^{(l)} \cdot \text{AGG}\left( \{h_j^{(l)}, \forall j \in \mathcal{N}_i\} \right) \right)$$

AGG 可以是均值、LSTM 或池化，并且 GraphSAGE 支持归纳学习（inductive），即对未见过的图也能泛化。

GAT（Graph Attention Network）：把聚合权重从固定常数升级为注意力系数：

$$e_{ij} = \text{LeakyReLU}\left( a^{\top} [W h_i \| W h_j] \right), \quad \alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k \in \mathcal{N}_i} \exp(e_{ik})}$$

$$h_i^{(l+1)} = \sigma\left( \sum_{j \in \mathcal{N}_i} \alpha_{ij} W h_j^{(l)} \right)$$

GAT 的注意力系数由节点特征决定，这是"图注意力"范式的起点。这三种架构构成了同质 GNN 的主干，也决定了它们对图的假设：节点同质、边同质、邻居无差别聚合。

同质图的两个局限

经典 GNN（GCN、GAT、GraphSAGE）都假设图是同质的：所有节点一种类型，所有边一种类型，消息传递时对邻居一视同仁。这个假设在实际场景中有两个明显局限：

• 类型信息被丢弃。摄像头网络里，"相机节点"和"行人节点"语义完全不同，但同质图把它们放进同一个特征空间，用同一组参数做聚合，类型差异只能靠特征向量隐式表达，信息利用率低。
• 关系语义被压平。边的含义（“属于”、“观测到”、“相似于”）决定了消息应该如何传递，同质图把不同关系的邻居混在一起聚合，关系结构信息基本丢失。

我们需要知道，这两个局限正是异质图建模要解决的问题：显式建模节点与边的类型，让消息传递沿着类型感知的路径进行。

异质图的定义

异质图（Heterogeneous Graph）定义为带类型映射的图：

$$G = (\mathcal{V}, \mathcal{E}, \phi, \psi)$$

其中 $\mathcal{V}$ 是节点集合，$\mathcal{E}$ 是边集合，$\phi: \mathcal{V} \to \mathcal{A}$ 将每个节点映射到节点类型 $\mathcal{A}$，$\psi: \mathcal{E} \to \mathcal{R}$ 将每条边映射到关系类型 $\mathcal{R}$。当 $|\mathcal{A}| > 1$ 或 $|\mathcal{R}| > 1$ 时，图是异质的。

一个常用的简化表示是网络模式（Network Schema）：它只保留类型层面的结构，忽略具体实例。网络模式定义在类型集合 $\mathcal{A}$ 上，是带类型标签的有向图，其中节点是类型、边是关系。例如摄像头-轨迹网络的 schema 可以表示为：

Camera --observes--> Tracklet --has--> Target

网络模式刻画了"哪些类型之间可以存在哪些关系"，是异质图消息传递的骨架。需要注意，网络模式是语义级的抽象，同一网络模式可以对应无数个具体的异质图实例。

元路径（Meta-path）

异质图消息传递的关键问题是：消息该沿着什么路径走。同质图里邻居就是邻居，异质图里"邻居"需要按类型组合来定义，这就是元路径：

$$P = A_1 \xrightarrow{R_1} A_2 \xrightarrow{R_2} \cdots \xrightarrow{R_l} A_{l+1}$$

元路径 $P$ 是网络模式上的一个类型序列，定义了节点 $A_1$ 与 $A_{l+1}$ 之间的一类复合关系。例如在学术网络中，元路径 “作者-论文-作者”（APA）表示合著关系，“作者-论文-会议-论文-作者”（APCPA）表示同会关系。不同元路径刻画不同的语义视角，同一个节点对在不同元路径下的关系强度完全不同。

元路径的引入让"邻居"有了语义：沿着元路径 $P$ 可达的节点集合 $\mathcal{N}_i^P$ 才是节点 $i$ 在语义 $P$ 下的邻居。形式化地说，给定元路径 $P$，其路径实例是满足类型约束的具体节点序列，节点 $i$ 与 $j$ 之间存在路径实例当且仅当 $j \in \mathcal{N}_i^P$。

元路径还有一个重要性质：对称元路径（如 APA、APCPA）定义了节点类型相同的节点对之间的等价关系，这类路径常用于同类型节点之间的相似度计算，是异质图推荐与聚类的常用工具。

为什么元路径是异质图的核心抽象

同质图只需要定义"邻居"，异质图必须定义"哪类邻居"。元路径把"类型序列"当作语义单元：每一条元路径就是一个视图，节点在不同视图下有不同的邻居结构。异质图模型的核心设计差异，就在于如何选择、加权、聚合多条元路径下的邻居信息。

元路径的扩展：元图与带权元路径

元路径假设类型序列是"一条链"，但真实关系往往比链更复杂。**元图（Meta-graph）**是元路径的推广：它允许类型序列带有分支结构。例如"作者-论文-（作者，会议）"这种多分支关系只能用元图表达。元图比元路径表达力更强，但计算复杂度也更高，实践中需要权衡。

另一个扩展方向是带权元路径：不同路径实例对目标节点的贡献不同，可以给路径实例赋权。例如在摄像头网络中，路径 “Camera-A-Tracklet-observed by-Camera-B” 的实例，其权重可以与该轨迹的置信度、时间接近度相关。带权元路径为"路径语义 + 实例强度"的统一建模提供了接口。

异质图嵌入的早期方法：metapath2vec

在异质图神经网络之前，异质图建模主要靠异质图嵌入。metapath2vec 是代表性工作，它的核心想法是：用元路径约束随机游走，再用 Skip-gram 学习嵌入。

元路径随机游走：在每一步，游走者不是随机选择任意邻居，而是沿着预设元路径的类型序列选择邻居。对于元路径 $P = A_1 \to A_2 \to \cdots \to A_l$，在类型 $A_k$ 的节点上，下一步只允许走向类型 $A_{k+1}$ 的邻居。这保证了游走轨迹在语义上是连贯的，不跨类型乱跳。

异构 Skip-gram：游走得到节点序列后，用 Skip-gram 最大化共现概率，但输出层按节点类型分组做 softmax：

$$p(v_{t+c} \mid v_t) = \frac{\exp(x_{v_{t+c}} \cdot x_{v_t})}{\sum_{v' \in \mathcal{V}_{t+c}} \exp(x_{v'} \cdot x_{v_t})}$$

其中 $\mathcal{V}_{t+c}$ 是与目标节点 $v_{t+c}$ 同类型的节点集合。这个"类型分组 softmax"是异构 Skip-gram 的关键：嵌入空间按类型结构化，不同类型节点的嵌入不会互相挤压。

metapath2vec 的价值在于它最早证明了"元路径约束 + 类型感知训练"能学到高质量的异质节点嵌入。但它有两个局限：一是静态嵌入，无法对未见节点直接推理（需要重新训练）；二是路径类型需要人工指定，元路径的选择直接影响嵌入质量。这两个局限正是后续异质图神经网络要解决的。

第二部分：异质图神经网络

RGCN：关系感知的消息传递

RGCN（Relational Graph Convolutional Network）是异质图建模的早期代表，它的思路很直接：为每种关系准备一组独立的变换参数。节点 $i$ 在第 $l+1$ 层的表示：

$$h_i^{(l+1)} = \sigma\left( \sum_{r \in \mathcal{R}} \sum_{j \in \mathcal{N}_i^r} \frac{1}{c_{i,r}} W_r^{(l)} h_j^{(l)} + W_0^{(l)} h_i^{(l)} \right)$$

其中 $\mathcal{N}_i^r$ 是节点 $i$ 在关系 $r$ 下的邻居，$W_r^{(l)}$ 是关系 $r$ 专属的变换矩阵，$c_{i,r}$ 是归一化常数（通常取 $|\mathcal{N}_i^r|$），$W_0$ 是自环变换。

RGCN 的优点是简单直接，每种关系有独立的参数，关系语义被显式建模。但有两个实际问题：

参数规模问题：参数随关系数量线性增长。设隐藏维度为 $d$，关系数为 $|\mathcal{R}|$，则每层参数量为 $|\mathcal{R}| \cdot d^2$。当 $|\mathcal{R}|$ 很大时（知识图谱常有数百种关系），模型极易过拟合。

基分解（Basis Decomposition）：为解决参数爆炸，RGCN 提出用一组基矩阵的线性组合表示每种关系的变换：

$$W_r^{(l)} = \sum_{b=1}^{B} a_{rb}^{(l)} \cdot V_b^{(l)}$$

其中 $V_b$ 是共享的基矩阵（$B \ll |\mathcal{R}|$），$a_{rb}$ 是关系 $r$ 在基 $b$ 上的系数。基分解让不同关系共享底层参数，既能控制参数量，又能通过系数区分关系语义。另一个方案是块对角分解，把 $W_r$ 限制为块对角结构，进一步降低参数量。

RGCN 的实际应用包括知识图谱补全和链接预测，但只建模了关系类型，没有建模"路径"语义，因此表达能力仍受限：两个节点之间即使有完全相同的直接关系集合，其语义也可能因为"如何到达"而不同。

HAN：元路径感知的层级注意力

HAN（Heterogeneous Graph Attention Network）的思路是：先用元路径定义邻居，再用两级注意力聚合。它针对每个元路径 $P$ 构建一个元路径邻居图，然后在这个图上做节点级注意力，最后用语义级注意力融合多条元路径。

节点级注意力：对于元路径 $P$，节点 $j$ 对节点 $i$ 的注意力系数：

$$e_{ij}^P = \sigma\left( a_P^{\top} \cdot [h_i' \| h_j'] \right), \quad \alpha_{ij}^P = \frac{\exp(e_{ij}^P)}{\sum_{k \in \mathcal{N}_i^P} \exp(e_{ik}^P)}$$

其中 $h_i' = M_P \cdot h_i$ 是元路径 $P$ 下的类型专属投影，$\|$ 表示拼接，$a_P$ 是元路径 $P$ 的注意力向量。聚合后得到节点 $i$ 在元路径 $P$ 下的表示：

$$z_i^P = \sigma\left( \sum_{j \in \mathcal{N}_i^P} \alpha_{ij}^P \cdot h_j' \right)$$

语义级注意力：不同元路径 $\{P_1, \ldots, P_M\}$ 对最终表示的重要性不同，语义级注意力学习每条元路径的权重 $\beta_P$：

$$\beta_P = \frac{\exp(w_{\beta}^{\top} \cdot \tanh(W_{\beta} z^P))}{\sum_{P'} \exp(w_{\beta}^{\top} \cdot \tanh(W_{\beta} z^{P'}))}$$

最终表示是各元路径表示的加权和：

$$Z = \sum_{P \in \{P_1, \ldots, P_M\}} \beta_P \cdot Z^P$$

HAN 的核心贡献是把"元路径选择"从人工设计变成了注意力学习：每个节点在不同元路径下的表示由语义级注意力自动加权。它证明了元路径 + 双级注意力是异质图建模的有效范式。HAN 的局限也在于此：它需要预先枚举元路径集合，元路径的质量仍然依赖领域知识，且不同任务的最优元路径不同。

MAGNN：元路径内部节点

HAN 的节点级聚合只聚合元路径的端点（$\mathcal{N}_i^P$ 里的目标节点），忽略了元路径内部的中间节点。MAGNN（Metapath Aggregated Graph Neural Network）指出这是一个信息损失：元路径内部的中间节点往往携带关键语义（例如 APA 路径中连接两个作者的论文标题、发表年份）。

MAGNN 的做法是对整个元路径实例做编码。对于元路径 $P$ 的一个实例 $(v_0, v_1, \ldots, v_l)$，用一个编码器（如 LSTM 或 mean-pooling）把整条路径编码为消息：

$$h_{P}(v_0, v_l) = f_{\theta}(v_0, v_1, \ldots, v_l)$$

然后按注意力加权聚合所有以 $v_0$ 为端点的路径实例消息：

$$h_{v_0}^P = \sigma\left( \sum_{(v_0, \ldots, v_l) \in \mathcal{I}_P(v_0)} \alpha_{(v_0, \ldots, v_l)} \cdot h_P(v_0, v_l) \right)$$

MAGNN 的语义级融合与 HAN 类似（也用语义级注意力），但它的节点级编码更完整。实验表明，在需要路径内部语义的任务（如链接预测、推荐）上，MAGNN 优于只聚合端点的 HAN。

HGT：动态异质注意力

HAN 和 MAGNN 都需要预先指定元路径集合，HGT（Heterogeneous Graph Transformer）则试图摆脱这个限制：不再依赖手工元路径，而是通过注意力机制动态建模任意类型的节点对关系。

HGT 的核心是三个类型感知的映射。给定边 $(s, t)$，源节点类型 $\tau(s)$、目标节点类型 $\tau(t)$、关系 $\delta(e)$：

QKV 投影：目标节点 $t$ 的查询向量由目标类型决定，源节点 $s$ 的键值向量由源类型决定：

$$Q^{(l)}[t] = W_{Q}^{(l)} \cdot \tilde{H}^{(l-1)}[t], \quad K^{(l)}[s] = W_{K}^{(l)} \cdot \tilde{H}^{(l-1)}[s], \quad V^{(l)}[s] = W_{V}^{(l)} \cdot \tilde{H}^{(l-1)}[s]$$

其中 $\tilde{H}^{(l-1)}$ 是前一层的节点表示，$W_Q^{(l)}[\tau(t)]$ 按目标类型索引，$W_K^{(l)}[\tau(s)]$、$W_V^{(l)}[\tau(s)]$ 按源类型索引。

异质注意力：注意力系数由目标类型矩阵和关系矩阵共同决定：

$$\text{Attn}(s, t) = \text{Softmax}_{\forall s \in N(t)} \left( \mu_{\langle \tau(s), \delta(e), \tau(t) \rangle} \cdot \frac{Q[t] K[s]^{\top}}{\sqrt{d}} \right)$$

其中 $\mu$ 是类型三元组 $\langle \text{源类型}, \text{关系}, \text{目标类型} \rangle$ 的注意力偏置，这是 HGT 区别于同质 Transformer 的关键：每个类型组合有自己的注意力偏置。$\mu$ 由一个共享的矩阵 $M$ 按类型索引得到：

$$\mu_{\langle \tau(s), \delta(e), \tau(t) \rangle} = M_{\tau(s), \delta(e), \tau(t)}$$

消息传递与更新：源节点消息经关系专属矩阵变换后加权聚合：

$$\tilde{H}^{(l)}[t] = \bigoplus_{\forall s \in N(t)} \text{Attn}(s, t) \cdot \text{Msg}(s, t), \quad \text{Msg}(s, t) = W_{\delta(e)}^{(l)} V^{(l)}[s]$$

最后经过残差连接、层归一化与前馈网络得到第 $l$ 层的输出：

$$H^{(l)}[t] = \text{FFN}\left( \text{LN}\left( \tilde{H}^{(l)}[t] + H^{(l-1)}[t] \right) \right)$$

相对时间编码：HGT 还引入了相对时间编码，将目标节点 $t$ 与源节点 $s$ 的时间差映射为一个向量 $R(\Delta t)$，加到注意力计算中：

$$\text{Attn}(s, t) = \text{Softmax}\left( \mu \cdot \frac{Q[t] K[s]^{\top} + R(\Delta t)^{\top} \cdot W_R}{\sqrt{d}} \right)$$

这在动态图上（如随时间演化的社交网络）尤其重要。

HGT 的优势是不需要枚举元路径，注意力自动发现重要的类型组合，且能处理动态图（新增类型）。它把 Transformer 架构完整迁移到异质图上，是异质图建模从"路径枚举"走向"注意力学习"的标志性工作。

RGCN / HAN / MAGNN / HGT 的演进主线

四者回答同一个问题"异质图上消息怎么传"，但答案的深度逐级提升：RGCN 用关系专属参数（参数层面），HAN 用元路径 + 双级注意力（路径层面），MAGNN 把路径内部节点编码进消息（路径实例层面），HGT 用类型三元组注意力偏置（注意力层面）。演进方向是从"显式枚举"走向"自动学习"：关系靠参数枚举、路径靠注意力选择、类型组合靠偏置建模。

异质图神经网络的设计选择总结

综合上述方法，异质图神经网络的设计空间可以归纳为三个决策维度：

维度	选项	代表方法
邻居定义	关系邻居 / 元路径邻居 / 注意力全邻居	RGCN / HAN / HGT
聚合方式	均值 / 注意力 / 路径编码	GCN / GAT / MAGNN
类型建模	类型专属参数 / 类型专属投影 / 类型三元组偏置	RGCN / HAN / HGT

这三个维度正交组合，构成了异质图建模的方法论地图。邻居定义决定了"看谁"，聚合方式决定了"怎么看"，类型建模决定了"差异如何表达"。

第三部分：图 Transformer

Transformer 基础回顾

图 Transformer 是 Transformer 架构在图上的迁移，因此先回顾标准 Transformer 的核心组件。给定输入序列 $X = \{x_1, \ldots, x_n\}$，Transformer 层的自注意力为：

$$Q = XW_Q, \quad K = XW_K, \quad V = XW_V$$

$$\text{Attn}(Q, K, V) = \text{Softmax}\left( \frac{QK^{\top}}{\sqrt{d_k}} \right) V$$

其中 $d_k$ 是键向量的维度，$\sqrt{d_k}$ 用于缩放防止点积过大导致 softmax 饱和。多头注意力把注意力拆成 $h$ 个头并行计算，再拼接投影：

$$\text{MultiHead}(Q, K, V) = \text{Concat}(\text{head}_1, \ldots, \text{head}_h) W_O$$

$$\text{head}_i = \text{Attn}(QW_Q^i, KW_K^i, VW_V^i)$$

位置编码：注意力是置换等变的（打乱输入顺序结果不变），必须注入位置信息。标准做法是正弦位置编码：

$$PE_{(pos, 2i)} = \sin\left( \frac{pos}{10000^{2i/d}} \right), \quad PE_{(pos, 2i+1)} = \cos\left( \frac{pos}{10000^{2i/d}} \right)$$

序列模型需要位置编码因为顺序即语义；图模型需要结构编码因为连接即语义，这是图 Transformer 的核心挑战。

从 GAT 到 GATv2：注意力机制的演进

同质图上的注意力演进是理解图 Transformer 的捷径。GAT 的注意力系数：

$$e_{ij} = \text{LeakyReLU}\left( a^{\top} [W h_i \| W h_j] \right)$$

GATv2（2022）指出了 GAT 的一个理论缺陷：GAT 的注意力是"先拼接后线性变换再点积"，其表达能力受限，退化为一种静态注意力。具体来说，GAT 的注意力评分函数 $a^{\top} \cdot \text{LeakyReLU}(W[h_i \| h_j])$ 中，$W$ 与 $a$ 的复合使得评分对查询节点 $h_i$ 的敏感度被限制，注意力排序几乎由目标节点单独决定。

GATv2 改为先线性变换再拼接：

$$e_{ij} = a^{\top} \text{LeakyReLU}\left( W [h_i \| h_j] \right)$$

这个改动让注意力系数可以对输入特征做任意近似，称为"动态注意力"。理论分析表明 GAT 的注意力排序对查询节点不敏感（静态），而 GATv2 是动态的，表达力严格更强：GATv2 的注意力评分函数是通用近似器，可以表达任意注意力模式，而 GAT 只能表达受限的子集。

GATv2 是我们之前 MC-MOT 工作中使用的注意力机制，它对查询敏感的特性正是跨摄像头匹配所需要的：同一个目标在不同摄像头下出现的可靠性不同，动态注意力允许模型根据查询节点（目标）调整对各个邻居（相机观测）的信任权重。

Graph Transformer 的核心设计

图 Transformer 把 NLP 的 Transformer 迁移到图上，核心挑战是：注意力机制天然无视图结构，需要显式注入结构信息。标准的图 Transformer 层：

$$\text{Attn}(Q, K, V) = \text{Softmax}\left( \frac{QK^{\top}}{\sqrt{d_k}} + B \right) V$$

其中 $B$ 是结构编码矩阵。区别不同图 Transformer 的关键就在于 $B$ 怎么定义。结构编码大致分三类：

位置编码（Positional Encoding）：把节点在图中的"位置"编码进表示。两类主流方案：

• 拉普拉斯位置编码（LapPE）：取图拉普拉斯矩阵的特征向量，作为节点位置。设拉普拉斯矩阵 $L = I - D^{-1/2} A D^{-1/2}$，其前 $k$ 小特征值对应的特征向量 $U = [u_1, \ldots, u_k]$，节点 $i$ 的位置编码为 $U[i]$。拉普拉斯特征向量是图结构的谱表示，能区分结构上不同的节点。
• 随机游走位置编码（RWPE）：用随机游走的返回概率作为位置信号，$P_i = [RW^i_{ii}, RW^2_{ii}, \ldots, RW^k_{ii}]$，其中 $RW$ 是随机游走转移矩阵。返回概率刻画了节点在局部结构中的"角色"。

结构编码（Structural Encoding）：把节点对之间的结构关系编码进注意力偏置 $B$：

• 最短路径距离（SPD）：Graphormer 用 $b_{\phi(i,j)}$，其中 $\phi(i,j)$ 是节点 $i$、$j$ 的最短路径距离，$b$ 是可学习的偏置。距离越近的节点对获得越大的注意力偏置。
• 连通性掩码：直接对不连通的节点对施加 $-\infty$ 偏置，注意力只在结构邻居间流动。

边特征编码（Edge Encoding）：把边的类型、权重等特征编码进注意力。设节点 $i$、$j$ 之间最短路径上的边特征序列为 $\{e_1, \ldots, e_m\}$，编码为：

$$c_{ij} = \frac{1}{m} \sum_{k=1}^{m} e_k W_E$$

最终注意力偏置为 $B_{ij} = b_{\phi(i,j)} + c_{ij}$。

**Graphormer（2021）**是代表性工作，它的核心设计有三个：

1. 中心性编码（Centrality Encoding）：把节点的度（入度 + 出度）作为可学习的加性编码，注入节点表示：$h_i = h_i + z_{\deg^-(v_i)} + z_{\deg^+(v_i)}$。度是节点在图中的重要性信号，显式注入让注意力能感知"hub 节点"。
2. 空间编码（Spatial Encoding）：如上所述，用最短路径距离作为注意力偏置。

$$A_{ij} = \frac{(h_i W_Q)(h_j W_K)^{\top}}{\sqrt{d}} + b_{\phi(i,j)}$$

3. 全局节点（[VNode]）：为图添加一个虚拟全局节点，与所有节点连接，作为图级信息的汇聚点，类似 NLP 中的 [CLS] token。图级任务（如图分类）直接读取全局节点表示。

Graphormer 在分子性质预测等任务上大幅超越当时的 GNN，验证了"结构编码 + 全局节点"设计范式的有效性。

通用框架 GraphGPS

GraphGPS（Graph Processing with a General and Scalable architecture，2022）试图统一图 Transformer 的设计空间，提出了一个模块化框架：局部消息传递（GNN）与全局注意力（Transformer）并行，再融合。

$$H^{(l+1)} = \text{FFN}\left( \text{MPNN}_l(H^{(l)}) + \text{Transformer}_l(H^{(l)} + \text{PENode}) \right)$$

其中 MPNN 处理局部结构（保持 GNN 的归纳偏置），Transformer 处理全局交互（弥补 GNN 的感受野限制），位置编码（PE）注入结构信息。GraphGPS 的价值在于它是配方式的：任何 GNN 层与任何图 Transformer 层都可以组合进这个框架，研究者只需选择"局部模块 + 全局模块 + 编码方式"三件套。它同时强调可扩展性，用子图采样让 Transformer 能处理大图。

图 Transformer 的计算复杂度与可扩展性

图 Transformer 的全局注意力需要计算所有节点对的相关性，复杂度为 $O(|\mathcal{V}|^2)$，这在节点数超过万级时不可接受。目前有三类缓解方案：

• 图稀疏化：注意力只在结构邻居或采样邻居间计算（如 GraphSAGE 式采样 + 注意力），复杂度降为 $O(|\mathcal{V}| \cdot k)$。
• 子图采样：GraphGPS 对节点做子图采样，每个 Transformer 层只处理子图内的节点。
• 线性注意力：用核方法近似注意力（如 Performer、线性注意力），复杂度降到 $O(|\mathcal{V}|)$。

图 Transformer 与 GNN 的取舍：GNN 的消息传递是局部且归纳偏置强的（同构图等变性），图 Transformer 是全局且灵活的，但需要更多数据与更强的结构编码才能收敛。近年研究表明，结构编码的质量决定图 Transformer 的性能，这也是为什么"图结构编码"成为独立的研究方向。

第四部分：异质图 Transformer 的交汇

HGT：异质图上的 Transformer

把第三部分的"结构编码"与第二部分的"类型建模"放在一起看，会发现 HGT 本质上是异质图上的图 Transformer：

• 类型三元组注意力偏置 $\mu_{\langle \tau(s), \delta(e), \tau(t) \rangle}$ 就是异质化的结构编码，它编码的是"类型组合"这一结构信号；
• HGT 的 QKV 投影按类型索引，等价于按节点类型分组的线性层，与 Graphormer 的中心性编码是同类思想（把重要属性显式注入注意力）；
• HGT 的残差、归一化、前馈结构与标准 Transformer 一致。

因此，异质图建模与图 Transformer 两条研究线在 HGT 处合流：异质图为 Transformer 提供了类型感知的结构偏置，Transformer 为异质图提供了免元路径的全局注意力。

异质图 Transformer 的设计空间

以 HGT 为参照，异质图 Transformer 的设计空间包括：

维度	选项	说明
类型编码方式	类型专属 QKV / 类型三元组偏置 / 类型嵌入	控制类型信息的注入位置
结构编码	元路径偏置 / 最短路径偏置 / 拉普拉斯 PE	控制结构信息的表达
注意力范围	关系邻居 / 全节点	控制计算复杂度与感受野
动态性	静态图 / 时间编码	是否建模时序演化

这些维度与第二部分的异质 GNN 设计维度（邻居定义、聚合方式、类型建模）相互对应，异质图 Transformer 可以视为在"类型建模"维度上使用了最强方案（注意力偏置）的异质 GNN。

与跨摄像头多目标跟踪的联系

跨摄像头多目标跟踪（MC-MOT）天然是异质图场景：摄像头、轨迹、目标三类节点，观测、匹配、关联多种关系。我们之前的工作正是建立在这个理解之上：

1. Camera-Tracklet 二分异质图：相机节点与轨迹节点分属两种类型，观测关系（哪个相机看到了哪个轨迹）是唯一的边类型。异质图建模让"相机视野"与"轨迹特征"在消息传递中保持类型分离，避免同质化混聚。
2. CTPM 偏置的 GATv2 注意力：GATv2 的动态注意力负责"按查询调整对邻居的信任"，而 CTPM（Camera-Tracklet Pattern Mining）偏置则是在注意力中注入相机拓扑先验，相当于一种领域定制的结构编码，与图 Transformer 注入结构偏置的思路同源。
3. Sinkhorn 双随机松弛匹配：图注意力输出的是软匹配分布，Sinkhorn 迭代把它约束为双随机矩阵，保证匹配的行列一致性（每个轨迹至多匹配一个目标、每个目标至多一个轨迹）。这是把图表示学习与组合优化衔接的一步。

从本文的视角看，这套方案是"异质图 + 动态注意力 + 结构偏置"的组合，恰好落在异质图 Transformer 设计空间的一个具体点上。理解这个设计空间，有助于我们在后续工作中做有依据的选择，而不是凭直觉堆叠模块。

异质图 × 图 Transformer：两条线的交汇

异质图建模的演进（RGCN → HAN → MAGNN → HGT）与注意力机制的演进（GAT → GATv2 → Graph Transformer）在 HGT 处交汇：HGT 本质上是"异质图上的图 Transformer"，类型三元组注意力偏置就是异质化的结构编码。对 MC-MOT 这类任务而言，Camera-Tracklet 二分异质图 + GATv2 动态注意力 + Sinkhorn 匹配的组合，正是这两条线在我们场景中的具体落点。

挑战与展望

异质图的元路径依赖

HAN、MAGNN 依赖人工枚举元路径，HGT 摆脱了元路径但引入了对类型三元组数量的依赖（类型组合数可能比关系数更大）。如何在"免人工设计"与"参数可控"之间取得平衡仍是开放问题。一个方向是让元路径本身可学习（如 GTN 用 soft 选择组合类型序列），另一个方向是用元学习初始化类型偏置。

结构编码的可迁移性

图 Transformer 的结构编码（拉普拉斯 PE、最短路径偏置）通常假设静态图结构。跨摄像头网络的结构会随摄像头增删、视角调整而变化，结构编码需要支持增量更新与迁移，这是实际部署中的硬约束。

大规模异质图的可扩展性

异质图的类型多样性放大了计算压力：元路径游走、类型分组 softmax、全类型注意力都需要在大图上保持效率。异质图上的采样策略（类型感知采样）与分布式训练是当前工程化的重点。

与序列模型的结合

图结构 + 时序演化的组合（时空异质图）是 MC-MOT 的直接需求：摄像头网络是静态结构，但轨迹、目标是动态的。如何把本文的异质图建模与序列模型（如 Mamba、时序 Transformer）结合，建模"结构上的时间演化"，是值得探索的方向。

小结

本文沿着三条线梳理了 GNN 的进阶路径：

1. 异质图建模：从同质图的类型信息丢失出发，定义了异质图、网络模式与元路径，回顾了 metapath2vec 的异质嵌入，介绍了 RGCN（关系专属参数）、HAN（元路径双级注意力）、MAGNN（路径内部节点编码）、HGT（类型三元组注意力偏置）的演进。
2. 图 Transformer：从 GAT 的静态注意力缺陷到 GATv2 的动态注意力，再梳理了图 Transformer 的结构编码设计（位置编码、结构编码、边编码）、Graphormer 的三个核心设计、GraphGPS 的通用框架与可扩展性方案。
3. 异质图 Transformer 的交汇：HGT 作为两条线的合流点，以及它在我们 MC-MOT 场景（Camera-Tracklet 二分异质图 + GATv2 + CTPM 偏置 + Sinkhorn）中的具体映射。

三条线的共同主题是如何把"类型"与"结构"显式注入消息传递：RGCN 用参数、HAN 用路径、HGT 与图 Transformer 用注意力偏置。对于跨摄像头多目标跟踪这类真实异质场景，理解这条演进主线，比记忆某个具体模型更有价值。

参考

[1] Kipf, T. N., & Welling, M. Semi-Supervised Classification with Graph Convolutional Networks. ICLR 2017.
[2] Hamilton, W., Ying, Z., & Leskovec, J. Inductive Representation Learning on Large Graphs. NeurIPS 2017.
[3] Veličković, P., et al. Graph Attention Networks. ICLR 2018.
[4] Brody, S., Alon, U., & Yahav, E. How Attentive are Graph Attention Networks? ICLR 2022.
[5] Schlichtkrull, M., et al. Modeling Relational Data with Graph Convolutional Networks. ESWC 2018.
[6] Wang, X., et al. Heterogeneous Graph Attention Network. WWW 2019.
[7] Fu, X., et al. MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding. WWW 2020.
[8] Dong, Y., Chawla, N. V., & Swami, A. metapath2vec: Scalable Representation Learning for Heterogeneous Networks. KDD 2017.
[9] Hu, Z., et al. Heterogeneous Graph Transformer. WWW 2020.
[10] Dwivedi, V. P., & Bresson, X. A Generalization of Transformer Networks to Graphs. 2020.
[11] Ying, C., et al. Do Transformers Really Perform Badly for Graph Representation? (Graphormer) NeurIPS 2021.
[12] Rampášek, L., et al. Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2022.
[13] Vaswani, A., et al. Attention Is All You Need. NeurIPS 2017.
[14] Yun, S., et al. Graph Transformer Networks. NeurIPS 2019.
[15] Kreuzer, D., et al. Rethinking Graph Transformers with Spectral Attention. ICLR 2021.
[16] Wu, Z., et al. A Comprehensive Survey on Graph Neural Networks. IEEE TNNLS 2021.
[17] Wang, X., et al. Heterogeneous Graph Neural Networks. 2021.
[18] Choromanski, K., et al. Rethinking Attention with Performers. ICLR 2021.