Heterogeneous Graph Attention Network-526互联

Wang X., Ji H., Shi C., Wang B., Cui P., Yu P. and Ye Y. Heterogeneous graph attention network. WWW, 2019.

概

Attention + 异构图.

\(\mathcal{G} = (\mathcal{V, E})\), 图;
\(\phi: \mathcal{V} \rightarrow \mathcal{T}\), \(\phi(v)\) 返回结点 \(v\) 所属的类别, 如上图所示, 存在三种类型的结点 (即 \(|\mathcal{T}|=3\)): Actor, Movie, Director;
\(\psi: \mathcal{E} \rightarrow \mathcal{R}\), \(\psi(e)\) 返回边 \(e\) 所属的类别, 如上图所示, 存在两种类型的边 (即 \(|\mathcal{R}| = 2\)).
显然, 一个图当且仅当 \(|\mathcal{T}| + |\mathcal{R}| > 2\) 的时候, 这个图才是异构图.
Meta-Path: Meta-Path 指的就是由一种结点类型到另一种结点类型的路径:

\[T_1 \mathop{\longrightarrow} \limits^{R_1} T_2 \mathop{\longrightarrow} \limits^{R_2} \cdots \mathop{\longrightarrow} \limits^{R_l} T_{l+1}, \]
我们称结点 \(v_i, v_j\) 关于 meta-path \(\Phi\) 是相邻的, 若存在一路径为该 meta-path 的实例且连接这两个结点. 记 \(\mathcal{N}_i^{\Phi}\) 为关于 \(\Phi\) 与 \(v_i\) 向量的结点的集合.
基于 \(\Phi\) 我们也可以推导出 meta-path based adjacency matrix \(A^{\Phi}\), 其中 \(A_{ij}^{\Phi} = 1\) 当且仅当 \(v_i, v_j\) 关于 \(\Phi\) 是相邻的.

Node-level attention 希望对指定的关系 \(\Phi\) 得到 node-level 的特征表示, 故下面的操作对于任意的 \(\Phi\) 都是通用的.
首先, 由于不同的结点类型原本特征所处的空间是不一致的, 所以首先通过转换矩阵 \(\mathbf{M}_{\phi}\) (注意, \(\phi\) 代表某种结点类型):

\[\mathbf{h}_i' \leftarrow \mathbf{M}_{\phi} \mathbf{h}_i. \]
对于每个结点 \(v_i\) 以及它的邻居结点集合 \(\mathcal{N}_i^{\Phi}\), 计算其邻居对于它的重要性:

\[\mathbf{e}_{ij}^{\Phi} = \text{att}_{node} (\mathbf{h}_i', \mathbf{h}_j'; \Phi) = \sigma(\mathbf{a}_{\Phi}^T [\mathbf{h}_i'\| \mathbf{h}_j']), \]
其中 \(\|\) 表示 concatenate operation.
于是, attention 为:

\[\alpha_{ij}^{\Phi} = softmax(e_{ij}^{\Phi}) = \frac{\exp(e_{ij}^{\Phi})}{\sum_{k \in \mathcal{N}_i^{\Phi}} \exp(e_{ik}^{\Phi})}. \]
最后 \(v_i\) 的特征表示为:

\[\mathbf{z}_i^{\Phi} = \sigma(\sum_{j \in \mathcal{N}_i^{\Phi}}\alpha_{ij}^{\Phi} \cdot \mathbf{h}_j'). \]

实际上, 对于每个 meta-path, 每个结点都会有这样的一个 \(\mathbf{z}_i^{\Phi}\), 假设共有 \(P\) 个 meta-paths, 那么就有:

\[\mathbf{z}_{i}^{\Phi_1}, \ldots, \mathbf{z}_{i}^{\Phi_P}, \]
那么我们应该怎么将这些融合在一起呢 ?
作者希望计算出每个 meta-path 的重要性然后加权求和.
每个 \(\Phi_i\) 的权重计算公式为:

\[w_{\Phi_i} = \frac{1}{|\mathcal{V}|} \sum_{i \in \mathcal{V}} \mathbf{q}^T \tanh (\mathbf{W} \mathbf{z}_i^{\Phi} + \mathbf{b}), \]
注意, 该权重不是是所有结点的平均, 故不是 node-level 的.
接着每个 meta-path 的 attention 为:

\[\beta_{\Phi_i} = \frac{\exp(w_{\Phi_i})}{\sum_{i=1}^P \exp(w_{\Phi_i})}, \]
然后加权:

\[\mathbf{z}_i = \sum_{j=1}^P \beta_{\Phi_j} \cdot \mathbf{z}_i^{\Phi_j}. \]
可以发现, 所有的结点特征都是共享相同的 meta-path 权重的, 个人感觉还是非常合理的. 但愿没有哪个倒霉蛋把这个扩展到 node-level 上去.