# Uniform Pooling for Graph Networks
## 2 Related Work
### Graph Pooling  
The pooling layer enables CNN to reduce trainable parameters to overcome the overfitting problem while facilitating the network to learn multi-scale graph embeddings [1; 29]. Finding the proper pooling layer for GCN is also important but more challenging because the graph nodes are not distributed in the regular grid domains. At present, graph pooling could be group into the following three categories [23]: topology-based, global, and hierarchical pooling. Topology-based graph pooling method directly clusters nodes to coarse graph using graph theory such as spectral clustering algorithms [8; 18; 30]. However, these methods often introduce a lot of computation, especially when the node size is large. The global pooling method applies summation and neural network to integrate the node features of each layer into graph-level representations, which can be directly used for graph classification tasks [31; 32; 33]. Hierarchical pooling can obtain assignments of coarse nodes and their new topology information through neural networks, so that graph convolution can be performed on hierarchical graphs, similar to CNN being executed on multi-scale images. Most neural network-based pooling methods can be used for both global pooling and hierarchical pooling architectures, both of which can improve graph classification. [PERSON] et al. [20] proposed a differentiable graph pooling method called DiffPool, which can learn the node assignments in end-to-end fashion using specialized graph convolutional layers. The node assignment matrix \(S^{(l)}{\in}R^{n_{l}\times n_{l+1}}\) of \(l^{th}\) layer is generated by input node features \(X^{(l)}\) and adjacency matrix \(A^{(l)}\):  
\[S^{(l)}=\text{softmax}\left(\text{GNN}_{\text{l}}\left(A^{(l)},X^{(l)}\right)\right) \tag{1}\]  
Then the node assignments matrix is used to update the node features and adjacency matrix:  
\[X^{(l+1)}={S^{(l)}}^{T}Z^{(l)} \tag{2}\]  
\[A^{(l+1)}={S^{(l)}}^{T}A^{(l)}S^{(l)} \tag{3}\]  
where \(Z^{(l)}\) denotes the output embeddings of \(l^{th}\) graph convolution layer. Please note that DiffPool learns a dense assignment matrix requiring a large storage complexity of \(O\left(k\times|V|^{2}\right)\), where \(|V|\) and \(k\) denote vertices and pooling ratio, respectively. DiffPool introduces more training parameters, making it easier to overfitting. [PERSON] et al. [21] proposed a simple gPool method (also known as TopKPool) that uses a linear layer to generate a node score with node feature as input, and then pools the top K nodes with the highest score. Subsequently, gPool was applied for graph classification, and achieved performance comparable to that of DiffPool but required lower storage complexity of \(O\left(|V|+|E|\right)\), where \(|V|\) and \(|E|\) denote vertices and edges, respectively [22]. The procedure in gPool can be described by the following equation:  
\[y=X^{(l)}p^{(l)}/\|p^{(l)}\|,idx=\text{top}-\text{rank}(y,\left\lceil\text{ kN}\right\rceil) \tag{4}\]  
\[A^{(l+1)}=A^{(l)}_{idx,idx} \tag{5}\]  
where \(y\) denotes the node score, \(p\) denotes the parameter of the linear layer, \(\text{top}-\text{rank}\) means selecting the top \(\left\lceil kN\right\rceil\) nodes and \(idx\) is the index of the top nodes. [PERSON] et al. [23] introduced self-attention graph pooling (SAGPool), which uses a graph neural network (GNN) to provide self-attention scores. SAGPool is a variant of TopKPool and it combines node features and topology information when calculating node scores. Recently, [PERSON] et al. [24] proposed an EdgePool method based on the notion of edge contraction. Compared to the previous method based on node scores, EdgePool selects the combination of two connected node features as input, and calculates the edge score using the neural network. Then the model chooses a highest-scoring edge to contract by merging its nodes.