Heterogeneous Graph Transformer

Definition

Heterogeneous graph transformer (HGT) is an extension of the GCN designed to handle the graph with multiple types of nodes and edges.

Architecture

Meta-relation triplets

$t$ is the target node, $s_1$ and $s_2$ are the source nodes, $e_1=(s_1,t)$ and $e_2=(s_2,t)$ are the edges, and the corresponding meta-relations are $⟨\tau (s_1),\varphi (e_1),\tau (t)⟩$ and $⟨\tau (s_2),\varphi (e_2),\tau (t)⟩$.

HGT uses meta-relation triplets $⟨\tau (s),\varphi (e),\tau (t)⟩$ (source node type, edge type, target node type) to describe the relationships between different entity types in a graph.

Heterogeneous Mutual Attention

HGT uses an attention mechanism that considers node types and edge types. The attention weights are computed based on the meta-relation triplets, allowing for type-specific information propagation.

For a meta-relation $⟨\tau (s),\varphi (e),\tau (t)⟩$, the attention is calculated by ${\mathrm{Attention}}_{\text{HGT}}(s,e,t)=\underset{s\in \mathcal{N}(t)}{\mathrm{softmax}}\left(\mathrm{concat}(\{{ATT-head}^i(s,e,t)|i=1,\dots ,h\})\right)$ where $\mathcal{N}(t)$ is the neighbors of the node $t$, and $h$ is the number of attention heads.

The attention head is calculated by ${ATT-head}^i(s,e,t)=\left(K^{(i)}(s)W_{\varphi (e)}^{\text{ATT}}{Q}^{(i)}(t{)}^{⊺}\right)$ where:

• $Q(t)=W_{\tau (t)}^Q{H}_t^{(l-1)}$ is a query vector
• $K(s)=W_{\tau (s)}^K{H}_s^{(l-1)}$ is a key vector
• $H_s^{(l-1)}$ and $H_t^{(l-1)}$ are the feature vectors of the source and target nodes at layer $l-1$.
• $W_{\tau (t)}^Q$, $W_{\varphi (e)}^{\text{ATT}}$, and $W_{\tau (s)}^K$ are learnable parameter matrices specific to the meta-relation.

Heterogeneous Message Passing

The information of source nodes are passed to the target node. Similar to the attention process, the meta-relations of edges are incorporated into the message passing process.

For a meta-relation $⟨\tau (s),\varphi (e),\tau (t)⟩$, the multi-head message is calculated by ${\mathrm{Message}}_{\text{HGT}}(s,e,t)=\mathrm{concat}(\{{MSG-head}^i(s,e,t)|i=1,\dots ,h\})$ where $h$ is the number of message heads.

The message head is calculated by ${MSG-head}^i(s,e,t)=\left(V^{(i)}(s)W_{\varphi (e)}^{\text{MSG}}\right)$ where:

• $V(s)=W_{\tau (s)}^V{H}_s^{(l-1)}$ is a value vector
• $W_{\tau (s)}^V$, $W_{\varphi (e)}^{\text{MSG}}$ are learnable parameter matrices specific to the meta-relation.

Target-Specific Aggregation

The heterogeneous multi-head attention and message are aggregated from the source nodes to the target node. The attention values are used as weights averaging corresponding messages from the source nodes.

The updated vector ${\tilde{H}}_t^{(l)}$ is calculated by ${\tilde{H}}_t^{(l)}=\underset{s\in \mathcal{N}(t)}{\oplus }\left({\mathrm{Attention}}_{\text{HGT}}(s,e,t)\cdot {\mathrm{Message}}_{\text{HGT}}(s,e,t)\right)$

The final output, contextualized representation of the node, is calculated using the updated vector. $H_t^{(l)}=W_{\tau (t)}^H\sigma ({\tilde{H}}_t^{(l)})+H_t^{(l-1)}$ where

• $H_t^{(l-1)}$ is the feature vectors of the target node at layer $l-1$, and works as a residual connection.
• $W_{\tau (t)}^H$ is learnable parameter matrix specific to the meta-relation.
• $\sigma$ is a non-linear Activation Function