Quasi-CliquePool: Hierarchical Graph Pooling for Graph Classification

Graph Neural Networks (GNNs) have revolutionized graph learning through efficiently learned node embeddings and achieved promising 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 intending 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 operations, 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, overlapping 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.