异构图HAN

迈不过友情╰ 2022-09-12 13:43 295阅读 0赞

异构图：节点类别的数量加边的类别的数量大于等于2，也就是包含不同类型节点和连接的异构图。下面的图就是一个异构图，包含电影、演员、导演。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_15_color_FFFFFF_t_70_g_se_x_16]  
这里介绍异构图的一个图算法**Heterogeneous Graph Attention Network**

定义异构图：节点的类别 + 边的类别 数量大于2

**Meta-path 元路径**就是连接两个对象的复合关系，是一种广泛使用的捕获语义的结构  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_10_color_FFFFFF_t_70_g_se_x_16]  
例如上面的异构图中包含三类节点，演员、电影、导演。  
`(c)`图定义了两个Meta-path：`movie-actor-movie`和`movie-director-movie`

如果我们选择`movie-actor-movie`这样一条Meta-path，那么`m1-a1-m2`就满足这个Meta-path关系，那么久可以说`m1`和`m2`就是互为邻居节点。此外`m1-a3-m3`也满足这个Meta-path，那么`m1`和`m3`也是互为邻居节点。同理`m1-a1-m1`也满足。综上，`m1`的邻居节点包括`m1,m2,m3`

# HAN 最主要的两个步骤 #

**1. 节点级别的attention**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_20_color_FFFFFF_t_70_g_se_x_16]  
我们定义了一个meta-path：`movie-director-movie`， 那么就可以形成下面的这个同构图：  
![在这里插入图片描述][6dfd9fcb21694aa69b328484c9fa8b7f.png]  
那么就可以根据`Terminator`的邻居节点`Terminator2`和`Titanic`，进行聚合，学习到`Terminator`的特征表示。那么就学习到节点级别的attention。

如果Meta-path定义为`movie-year-movie`那么形成下面的同构图：  
![在这里插入图片描述][e46c8b6806334eddba3d3a95e0a03730.png]  
同理可以根据邻居节点，可以求得这个Meta-path下`Terminator`的节点的特征。

**2. 语义级别的attention**  
语义级别的attention旨在了解每个元路径的重要性，并为其分配适当的权重。  
![在这里插入图片描述][104728fb0e36432c929a481f86d68da8.png]  
根据上面两个不同的Meta-path，可以得到两个不同的`Terminator`的特征，而我们的最终目标是要得到一个`Terminator`的特征，那么将这两个特征进行加权求和，这样的方式就是语义级别的方式。

![在这里插入图片描述][91cd5eeeda2541e3bcfd02c3ff2b8cb9.png]  
上图中利用Meta-path形成一个同构图。

# 节点级别attention流程 #

计算流程：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_11_color_FFFFFF_t_70_g_se_x_16]

1.  公式二： e i j Φ = a t t n o d e ( h i ′ , h j ′ ; Φ ) e\_\{ij\}^\\Phi=att\_\{node\}(h\_i^\\prime,h\_j^\\prime;\\Phi) eijΦ=attnode(hi′,hj′;Φ)表示连接节点与节点之间的特征值，其中 Φ \\Phi Φ表示在这个Meta-path下。在图中表示`1节点`与周围的邻居节点的特征，也就是求 e 11 Φ 0 e\_\{11\}^\{\\Phi \_0\} e11Φ0、 e 12 Φ 0 e\_\{12\}^\{\\Phi \_0\} e12Φ0、 e 13 Φ 0 e\_\{13\}^\{\\Phi \_0\} e13Φ0、 e 16 Φ 0 e\_\{16\}^\{\\Phi \_0\} e16Φ0
2.  公式三：对上面求得的 e 11 Φ 0 e\_\{11\}^\{\\Phi \_0\} e11Φ0、 e 12 Φ 0 e\_\{12\}^\{\\Phi \_0\} e12Φ0、 e 13 Φ 0 e\_\{13\}^\{\\Phi \_0\} e13Φ0、 e 16 Φ 0 e\_\{16\}^\{\\Phi \_0\} e16Φ0进行归一化操作得到，这里的方法与GAT的方法如出一辙，学习到attention系数，得到 α 11 Φ 0 \\alpha\_\{11\}^\{\\Phi \_0\} α11Φ0、 α 12 Φ 0 \\alpha\_\{12\}^\{\\Phi \_0\} α12Φ0、 α 13 Φ 0 \\alpha\_\{13\}^\{\\Phi \_0\} α13Φ0、 α 16 Φ 0 \\alpha\_\{16\}^\{\\Phi \_0\} α16Φ0
3.  公式四：将上面得到的attention系数与`1节点`周围邻居的特征进行加权求和，然后经过激活函数，得到`1节点`的特征表示。 即 z 1 Φ 0 = σ ( α 11 Φ 0 ⋅ x 1 0 + α 12 Φ 0 ⋅ x 2 0 + α 13 Φ 0 ⋅ x 3 0 + α 16 Φ 0 ⋅ x 6 0 ) z\_1^\{\\Phi\_0\}=\\sigma(\\alpha\_\{11\}^\{\\Phi\_0\} \\cdot x\_1^0 +\\alpha\_\{12\}^\{\\Phi\_0\} \\cdot x\_2^0 + \\alpha\_\{13\}^\{\\Phi\_0\} \\cdot x\_3^0+\\alpha\_\{16\}^\{\\Phi\_0\} \\cdot x\_6^0) z1Φ0=σ(α11Φ0⋅x10\+α12Φ0⋅x20\+α13Φ0⋅x30\+α16Φ0⋅x60)
4.  然后求其他节点的特征表示，最终就可以得到在Meta-path  Φ 0 \\Phi\_0 Φ0下的节点特征： Z Φ = \{ z 1 Φ 0 , z 2 Φ 0 , z 3 Φ 0 . . . \} Z\_\\Phi=\\\{z\_1^\{\\Phi\_0\},z\_2^\{\\Phi\_0\},z\_3^\{\\Phi\_0\}...\\\} ZΦ=\{ z1Φ0,z2Φ0,z3Φ0...\}
5.  然后得到多个Meta-path下的特征 \{ Z Φ 0 , Z Φ 1 , Z Φ 2 . . . \} \\\{Z\_\{\\Phi\_0\},Z\_\{\\Phi\_1\},Z\_\{\\Phi\_2\}...\\\} \{ ZΦ0,ZΦ1,ZΦ2...\}

# 语义级别attention流程 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_20_color_FFFFFF_t_70_g_se_x_16 1]

1.  公式七：选择一个Meta-path下的所有节点，这里选择 Φ 0 \\Phi\_0 Φ0，将每个节点经过全连接层 W ⋅ z i Φ 0 + b W \\cdot z\_i^\{\\Phi\_0\} +b W⋅ziΦ0\+b，然后经过激活函数 t a n h tanh tanh，然后乘以一个可学习的参数 q T q^T qT，这样就得到每一个节点在Meta-path Φ 0 \\Phi\_0 Φ0下的一个标量，然后对所有节点进行加权求和，并除以节点数量。得到在 Φ 0 \\Phi\_0 Φ0这个Meta-path下的对应的一个系数 w Φ 0 w\_\{\\Phi\_0\} wΦ0

举例：在 Φ 0 \\Phi\_0 Φ0下，`1节点`的特征 z 1 Φ 0 = \[ 0.1 , 0.2 , 0.1 , 0.5 , 0.8 \] T , z 2 Φ 0 = \[ 0.3 , 0.1 , 0.2 , 0.4 , 0.9 \] T z\_1^\{\\Phi\_0\}=\[0.1,0.2,0.1,0.5,0.8\]^T,z\_2^\{\\Phi\_0\}=\[0.3,0.1, 0.2,0.4,0.9\]^T z1Φ0=\[0.1,0.2,0.1,0.5,0.8\]T,z2Φ0=\[0.3,0.1,0.2,0.4,0.9\]T ，将 z 1 Φ 0 z\_1^\{\\Phi\_0\} z1Φ0经过 t a n h ( W ⋅ z + b ) tanh(W \\cdot z+b) tanh(W⋅z\+b)得到 \[ 0.12 , 0.25 , 0.8 \] T \[0.12, 0.25, 0.8\]^T \[0.12,0.25,0.8\]T，然后乘以可学习的参数 q T = \[ 0.5 , 1.2 , 0.8 \] q^T=\[0.5, 1.2, 0.8\] qT=\[0.5,1.2,0.8\]得到这个`1节点`的标量 q T ⋅ z 1 Φ 0 = 0.73 q^T \\cdot z\_1^\{\\Phi\_0\}=0.73 qT⋅z1Φ0=0.73， 同理得到`2节点`的标量 − 0.5 -0.5 −0.5，然后求和取平均 W Φ 0 = a v g ( 0.73 + ( − 0.5 ) ) W\_\{\\Phi\_0\}=avg(0.73+(-0.5)) WΦ0=avg(0.73\+(−0.5))，这个得到的 W Φ 0 W\_\{\\Phi\_0\} WΦ0就是Meta-path  Φ 0 \\Phi\_0 Φ0所对应到的attention的值。  
2. 公式八：将所有的Meta-path进行计算得到 W Φ 0 , W Φ 1 , W Φ 2 . . . W\_\{\\Phi\_0\},W\_\{\\Phi\_1\},W\_\{\\Phi\_2\}... WΦ0,WΦ1,WΦ2...，然后进行softmax操作进行归一化  
3. 公式九：将节点与上述的softmax结果进行加权求和，得到节点最终对应的embedding。即： Z 1 = β Φ 0 Z 1 Φ 0 + β Φ 1 Z 1 Φ 1 Z^1=\\beta\_\{\\Phi\_0\}Z\_1^\{\\Phi\_0\} + \\beta\_\{\\Phi\_1\}Z\_1^\{\\Phi\_1\} Z1=βΦ0Z1Φ0\+βΦ1Z1Φ1

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_12_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/4c5d10d57abf4f7ebf9de38c4fadee2a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/90e281e0885b4530b9357145e0df20e4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/633b5d3c5a694cd7b49a89f89e834661.png
[6dfd9fcb21694aa69b328484c9fa8b7f.png]: /images/20220828/992fa65097294bb082940ee5979971d0.png
[e46c8b6806334eddba3d3a95e0a03730.png]: /images/20220828/df4ebf4927f0488ead16b2e87738a90c.png
[104728fb0e36432c929a481f86d68da8.png]: /images/20220828/56bdeb3da5784e2ea7e953af6d8b0c9f.png
[91cd5eeeda2541e3bcfd02c3ff2b8cb9.png]: /images/20220828/47befcd698084d728ba17df46c431a0b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/79b0b14194194e04a847a50f96dfcaf8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/8b9d5aea2e1b4d7591e3d3949a450041.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAdmluY2VudF9kdWFu_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e0af2368b49342a3be3cf33fe402f72f.png