# Uniform Pooling for Graph Networks
## 3 The Proposed Method
### Uniform Graph Pooling  
Our UGPool method is to uniformly retain node features, just like pooling on grid-like domain data. UGPool uses neural networks to learn node scores with node features or topological information as input, and ranks nodes based on their scores. Subsequently, a normal one-dimensional pooling is performed on the sorted nodes to achieve a coarse graph, and then the adjacency matrix is updated based on the pooled node.  
Graph to Vector. We introduce a layer of neural network that uses node features as input to learning the node scores. If a simple linear layer is applied, the learned node score is equivalent to a one-dimensional mapping of the node features. If the graph convolutional layer is applied, the learned node score reflects both the feature and topology information of the node [23]. The node score is generated by the following formula:  
\[y=\hat{A}^{(l)}X^{(l)}p^{(l)}/\|p^{(l)}\| \tag{9}\]  
where \(\hat{A}\) denotes the normalized adjacency matrix, \(X\) is the node features, and \(p\) is the learnable weights of the neural network. Please note that if \(\hat{A}\) is set to the identity matrix, the linear layer is used,otherwise, the graph convolutional layer is used. Next, ranking the node based on the node score for further pooling.  
Uniform Node Pooling. We can prove that the nodes with similar features or topology information will be assigned similar scores. This property allows us to perform a normal one-dimensional pooling on the sorted node vector, such as max pooling or average pooling. That is, we can use the overall statistical characteristics of the neighboring node features of a certain node as new features of the node, while the adjacent nodes are discarded. Finally, we applied a gate operation to control the information flow to avoid the gradients from the loss could not be backpropagated. The following equation roughly describes the pooling procedure in UGPool:  
\[sidx=\text{rank}(\text{y}) \tag{10}\]  
\[X_{s}^{(l)},y_{s}=\text{sort}(\text{X}^{(l)},\text{sidx}) \tag{11}\]  
\[X^{(l+1)},pidx=1\text{DPool}(\text{X}_{s}^{(l)}\odot\text{y}_{s}) \tag{12}\]  
where \(\text{rank}(\cdot)\) is the operation of node ranking, \(sidx\) denotes the sorted index for node scores \(y\), \(X\) denotes the node features. \(X_{s}\) and \(y_{s}\) denote the features and scores of the ranked nodes, respectively. \(1\text{DPool}(\cdot)\) is the normal pooling on one-dimensional data, \(pidx\) is the index for pooled nodes. UGPool retains multiple types of nodes, rather than just high-scoring nodes, which allows the pooled graph to uniformly inherit the representative features of the original graph.  
Adjacency Matrix Updating. After the pooled graph is calculated, the adjacency matrix between the pooled nodes also needs to be updated. Using the original adjacency information of the pooled nodes is a solution, but this may cause the problem of sparse edges and isolated nodes. To overcome this problem, we consider the second-order connection between nodes, as done in [23]. The update of the adjacency matrix is as follows:  
\[A^{(l+1)}=A^{(l)}_{pidx,pidx}+{A^{(l)}}^{2}_{pidx,pidx} \tag{13}\]  
where \(pidx\) denotes the index for pooled nodes. It is easy to know that \(A^{2}\) generates the second-order connection between nodes.  
Theorem 3.1: _Let \(X_{1}\), \(X_{2}\) be any graph node features and \(y_{1},y_{2}\) be output of Equation (9), respectively, then \(\|y_{1}-y_{2}\|\to 0\) as long as \(\|X_{1}-X_{2}\|\to 0\) (i.e., as long as the node features are similar, the learned node scores are similar)._  
Proof of Theorem 3.1.: \(\forall\delta\to 0\), if \(\|X_{1}-X_{2}\|<\delta\), then \(\|y_{1}-y_{2}\|=\|\tilde{A}(X_{1}-X_{2})\frac{p}{\|p\|}\|<\|\hat{A}\|\cdot\|X_ {1}-X_{2}\|\to 0\).