# Uniform Pooling for Graph Networks
## 1 Introduction  
Convolution neural network (CNN) has achieved great success in processing data on Euclidean domains (grid structure) [1; 2], such as image, speech, and video [3; 4; 5; 6]. Therefore, many recent studies have devoted to the extension of convolution operations to the data on non-Euclidean domains and proposed the graph convolution network (GCN) [7; 8; 9].Then GCN has been successfully used to achieve improvements in several research fields, such as protein interface [10], action recognition [11], and traffic data processing [12]. The GCN mainly includes the spectral-based and spatial-based methods, which can leverage the topology information of the graph data to aggregate the local node features, and then automatically learn the embeddings for graph nodes. In many of the graph-related tasks, such as recommender systems [13; 14], chemical research [15; 16] and natural language processing [17], the GCN exhibits outstanding performance. The research on graph pooling methods is much less than that of the graph convolution models. In fact, the graph pooling technique is very important for obtaining the scaled-down graphs and graph-level embeddings. The most primitive graph pooling methods use graph topology information for node partitioning and graph coarsening [8; 18; 19]. Recently, a differentiable graph pooling has been proposed to obtain hierarchical graphs by learning end-to-end [20]. Moreover, there are more advanced graph pooling methods that can automatically learn the scores of nodes or edges and then pool nodes with high scores or merge nodes connected by edges with high scores to achieve the coarsening graph [21; 22; 23; 24]. However, how to pool nodes using node scores is not well understood and discussed, which may affect effective graph coarsening. If pooling only the highest-scoring nodes as the existing papers might throw away whole neighbourhoods of nodes and therefore information, because it can be intuitively seen from the GCN formulation that similar nodes in feature-space or topological space are assigned similar scores (we have proven it in the following section). The coarsening graph with pooling top nodes is difficult to uniformly inherit the representative features of the original graph, which in turn affects the representation capacity of the GCN. Here, we proposed a new graph pooling method UGPool with a new point-of-view on selecting pooled nodes, which assigns a score to each node, and uniformly pool the neighboring nodes in score-space instead of pooling top nodes as in existing papers. Pooling only the highest-scoring nodes might throw away whole neighbourhoods of nodes and therefore information, because of that the neighboring nodes in feature-space are also adjacent in score-space, which can be intuitively seen from the GCN formulation and has been proven in the following section. Specifically, we introduced a fully connected layer, taking node features or topology information as input, and learning the score of each graph node. Next, we sort the nodes according to their scores and perform normal pooling for one-dimensional data. Finally, update the adjacency matrix of the nodes according to the coarsening graphs. Our method can learn more comprehensive graph representations in an end-to-end fashion, which may improve the classification performance of the GCN. In short, we transformed the graph pooling problem into a popular one-dimensional data pooling problem by introducing a node automatic sorting mechanism. The implementation principle of our method is simple, and the performance or efficiency of our method is significantly better than the previous graph pooling on several standard benchmark datasets.Specifically, in multiple graph classification tasks, the proposed UGPool method achieves an average accuracy gain of 1.08% compared with other node-based pooling methods and achieves performance comparable to edge-based EdgePool with an average reduction in runtime of 64%.