标签：CS224W Neural Graph MLP right operatorname injective left

Expressive Graph Neural Networks

寄 鸽了一周没有写课程笔记，这次课程讲的是选择一个expressive的GNNmodel（当然还是要依据实际情况选择模型）

从一个简单的栗子开始理解叭，假设有这么一个简单图

再没有特征和标签序的情况下，我们可以发现点1和点2是不可区分的。因为在使用GNN时，会生成计算树，而两者计算树相同。

可以看见，去掉1和2，两棵树就长得一样。所以不管怎样，GNN都是无法区分的，我们把这种计算树当成一种特征，并且定义，the most expressive的模型能够区分每个长得不一样的计算树。

key idea: injective function

中文名叫单射函数（数学概念）。计算树是从下往上进行计算的，如果我们可以保证从下往上的每一层aggregation是injective，那么最后的计算结果就是injective的，不同的计算树就会得到区分。所以判断GNN model的方法就是判断aggregation是不是injective。

一些栗子

• GCN (mean-pool)，明显的非injective

• GraphSAGE (max-pool)，明显的非injective

目前学的模型都不是injective的

GIN : a injective model

核心思想，利用多重感知机(MLP)近似一个injective model

\[\left.\operatorname{MLP}_{\Phi}\left((1+\epsilon) \cdot \operatorname{MLP}_{f}\left(c^{(k)}(v)\right)\right)+\sum_{u \in N(v)} \operatorname{MLP}_{f}\left(c^{(k)}(u)\right)\right) \]

where \(\epsilon\) is a learnable scalar

GIN‘s neighbor aggregation function is injective

others

其实 WL Graph Kernel 也是一个injective function，在于那个hash

\[c^{(k+1)}(v)=\operatorname{HASH}\left(c^{(k)}(v),\left\{c^{(k)}(u)\right\}_{u \in N(v)}\right) \]

comparison

标签：CS224W,Neural,Graph,MLP,right,operatorname,injective,left
From： https://www.cnblogs.com/iridescense/p/16819736.html