A brief analysis of graph pooling

Graph Pooling analysis

Pooling It is a technology for graph feature extraction , It is usually used for graph classification .

Some marks

Let's remember one with $N$ Attribute graph of nodes (attributed graph) by $\mathcal{G}=(\mathcal{X},\mathcal{E})$

among $\mathcal{X}=\{(i,x_i){\}}_{i=1:N}$ Is a node set ,$x_i$ It's No $i$ Attribute vector of nodes

$\mathcal{E}=\{((i,j),e_{ij}){\}}_{i,j\in 1:N}$ It's an edge set , among $e_{ij}$ Is the attribute vector of the edge

Let's remember that the adjacency matrix of this graph is $A\in \{0,1{\}}^{N\times N}$

With the help of papers “Understanding Pooling in Graph Neural Networks” We use SRC Come on Pooling Methods to summarize .

Select, Reduce, Connect

about Pooling, We can understand it as a graph to graph mapping , namely ：$\mathcal{G}\to {\mathcal{G}}^{\prime }=({\mathcal{X}}^{\prime },{\mathcal{E}}^{\prime })$

As shown in the figure above ,Select The function divides the node into multiple node clusters , These node clusters can be considered as a super node

Reduce The function will put a supernode （ May contain one or more nodes ） Map to an attribute vector , The attribute vector corresponds to Pooling Supernode of the post graph

Connect Function accounting calculates the edge set of super nodes

stay Pooling After the operation , We will N The graph of nodes is mapped to a K Graph of nodes

In this way , We can give a table , Some of the current Pooling Method , utilize SRC Summarize in a way

Here we use DiffPool For example , Explain SRC Three parts ：

First , Suppose we have a N Graph of nodes , Where the node vector is written as $X\in {\mathbb{R}}^{N\times d}$, The dimension of each node vector is $d$

Select The function will output a $N\times N^{\prime }(N<N^{\prime })$ Mapping matrix $S$, Also is to $N$ A point is mapped to $N’$ A little bit

There is a GNN To the matrix $S$ To study

Reduce The function is the mapping matrix S Take one GNN The matrix after that , That is to say $N^{\prime }\times N$ Multiply the matrix of $N\times d^{\prime }$

Output is $N^{\prime }\times d$ A vector matrix of , representative Pooling The node vectors of these supernodes after one time

Connect The function outputs the adjacency matrix $A^{\prime }\in \{0,1{\}}^{N^{\prime }\times N^{\prime }}$