Seeing All From a Few: Nodes Selection Using Graph Pooling for Graph Clustering

Recently, there has been considerable research interest in graph clustering aimed at data partition using graph information. However, one limitation of most graph-based methods is that they assume that the graph structure to operate is reliable. However, there are inevitably some edges in the graph that are not conducive to graph clustering, which we call spurious edges. This brief is the first attempt to employ the graph pooling technique for node clustering to the best of our knowledge. In this brief, we propose a novel dual graph embedding network (DGEN), which is designed as a two-step graph encoder connected by a graph pooling layer to learn the graph embedding. In DGEN, we assume that if a node and its nearest neighboring node are close to the same clustering center, this node is informative, and this edge can be considered as a cluster-friendly edge. Based on this assumption, the neighbor cluster pooling (NCPool) is devised to select the most informative subset of nodes and the corresponding edges based on the distance of nodes and their nearest neighbors to the cluster centers. This can effectively alleviate the impact of the spurious edges on the clustering. Finally, to obtain the clustering assignment of all nodes, a classifier is trained using the clustering results of the selected nodes. Experiments on five benchmark graph datasets demonstrate the superiority of the proposed method over state-of-the-art algorithms.