Quasi-CliquePool: Hierarchical Graph Pooling for Graph Classification

Graph Neural Networks (GNNs) have revolutionized graph learning through efficiently learned node embeddings and achieved promis- ing results in various graph-related tasks such as node and graph classification. Within GNNs, a pooling operation reduces the size of the input graph by grouping nodes that share commonalities intend- ing to generate more robust and expressive latent representations. For this reason, pooling is a critical operation that significantly affects downstream tasks. Existing global pooling methods mostly use readout functions like max or sum to perform the pooling op- erations, but these methods neglect the hierarchical information of graphs. Clique-based hierarchical pooling methods have recently been developed to overcome global pooling issues. Such clique pooling methods perform a hard partition between nodes, which destroys the topological structural relationship of nodes, assuming that a node should belong to a single cluster. However, overlap- ping clusters widely exist in many real-world networks since a node can belong to more than one cluster. Here we introduce a new hierarchical graph pooling method to address this issue. Our pooling method, named Quasi-CliquePool, builds on the concept of a quasi-clique, which generalizes the notion of cliques to extract dense incomplete subgraphs of a graph. We also introduce a soft peel-off strategy to find the overlapping cluster nodes to keep the topological structural relationship of nodes. For a fair comparison, we follow the same procedure and training settings used by state- of-the-art pooling techniques. Our experiments demonstrate that combining the Quasi-Clique Pool with existing GNN architectures yields an average improvement of 2% accuracy on four out of six graph classification benchmarks compared to other existing pooling methods.