Abstract Co-clustering refers to the simultaneous clustering of rows and columns in a data matrix, uncovering joint patterns between two distinct sets, such as documents and terms or users and products. Traditional co-clustering algorithms typically rely on discrete optimization techniques based on enumeration, which can limit both scalability and flexibility. In this paper, we introduce a differentiable programming approach to co-clustering that enables the continuous optimization of co-partitions using graph neural networks. Our method is grounded in an associative co-clustering quality measure that is independent of the number of clusters and dynamically adjusts this parameter by jointly considering both partitions. By leveraging automatic differentiation and graph neural networks, our approach scales to very large datasets while maintaining high-quality co-cluster structures. We evaluate our method using different types of graph neural networks and initialization strategies. Furthermore, when compared with recent state-of-the-art methods for co-clustering and graph clustering, our approach achieves competitive or superior results in terms of accuracy. Most importantly, it is the only algorithm that successfully completes on the largest benchmark dataset.

Graph Neural Networks (GNNs) have proven their effectiveness in various graph-structured data applications. However, one of the significant challenges in the realm of GNNs is representation learning, a critical concept that bridges graph pooling, aimed at creating compressed graph representations, and explainable artificial intelligence, which focuses on building models with transparent reasoning mechanisms. This research paper introduces a novel approach called Interpretable Memory-based Prototypical Pooling (IMPO) to address this challenge. IMPO is a graph pooling layer designed to enhance the interpretability of GNNs while maintaining high performance in graph classification tasks. It builds upon the MemPool algorithm and incorporates prototypical components to cluster nodes around class-aware centroids. This approach allows IMPO to selectively aggregate relevant substructures, paving the way for generating more interpretable graph representations. The experimental results in our study underscore the potential of pooling architectures in constructing inherently explainable GNNs. Notably, IMPO achieves state-of-the-art results in both classification and explanatory capacities across a diverse set of graph classification datasets.