GraphPooling简析

Pooling 是一种用于图表征提取的技术&＃xff0c;通常用在图分类上面。

一些记号

我们记一个带有 $N$ 个节点的属性图 (attributed graph) 为 $\mathcal{G}\&＃61;(\mathcal{X},\mathcal{E})$

其中 X&＃61;{(i,xi)}i&＃61;1:N\mathcal X &＃61;\{(i,x_i)\}_{i&＃61;1:N}X&＃61;{(i,xi​)}i&＃61;1:N​ 是节点集&＃xff0c;xix_ixi​ 是第 $i$ 个节点的属性向量

E&＃61;{((i,j),eij)}i,j∈1:N\mathcal E &＃61; \{((i,j), e_{ij})\}_{i,j\in 1:N}E&＃61;{((i,j),eij​)}i,j∈1:N​ 是边集&＃xff0c;其中 eije_{ij}eij​ 是边的属性向量

我们记这个图的邻接矩阵为 A∈{0,1}N×NA \in \{0,1\}^{N\times N}A∈{0,1}N×N

借助论文“Understanding Pooling in Graph Neural Networks” 我们使用其中的 SRC 来对Pooling方法进行总结。

Select, Reduce, Connect

对于Pooling&＃xff0c;我们可以理解成一个图到图的映射&＃xff0c;即&＃xff1a;G→G′&＃61;(X′,E′)\mathcal G \rightarrow \mathcal G&＃39; &＃61; (\mathcal X&＃39;, \mathcal E&＃39;)G→G′&＃61;(X′,E′)

如上图所示&＃xff0c;Select函数会将节点划分成多个节点簇&＃xff0c;这些节点簇可以被认为是一个超节点

Reduce函数会将一个超节点&＃xff08;可能包含一个或多个节点&＃xff09;映射到一个属性向量&＃xff0c;该属性向量对应Pooling后图的超节点

Connect函数会计算出超节点的边集

在Pooling操作之后&＃xff0c;我们将一个N节点的图映射到一个K节点的图

按照这种方法&＃xff0c;我们可以给出一个表格&＃xff0c;将目前的一些Pooling方法&＃xff0c;利用SRC的方式进行总结

这里以 DiffPool 为例&＃xff0c;说明一下SRC三个部分&＃xff1a;

首先&＃xff0c;假设我们有一个N个节点的图&＃xff0c;其中节点向量记作 X∈RN×dX\in \mathbb R^{N\times d}X∈RN×d&＃xff0c;每个节点向量的维度是 $d$

Select函数会输出一个 N×N′(NN×N′(N<N′) 的映射矩阵$S$, 也就是将$N$个点映射成$N’$个点

这里面使用了一个GNN来对矩阵$S$ 进行学习

Reduce函数为映射矩阵S乘上一个GNN之后的矩阵&＃xff0c;也就是N′×NN&＃39;\times NN′×N 的矩阵乘上 N×d′N\times d&＃39;N×d′

输出为 N′×dN&＃39;\times dN′×d 的一个向量矩阵&＃xff0c;代表Pooling一次之后的这些超节点的节点向量

Connect函数输出邻接矩阵A′∈{0,1}N′×N′A&＃39;\in \{0,1\}^{N&＃39;\times N&＃39;}A′∈{0,1}N′×N′