Recovering Consensus in Multi-Modal Graphs: Provable Multi-Modal Spectral Clustering

This paper studies clustering algorithms for multi-modal graphs, in which each modality might have a different structure of clusters caused by the unique information of each modality, and the modality-consensus clusters are defined such that vertices belong to the same cluster if and only if they appear in the optimal cluster of every single modality. The paper presents a spectral algorithm to approximate these modality-consensus clusters, and provides a theoretical analysis of the algorithm’s output with respect to the optimal clusters. The paper further compares the performance of the proposed algorithm with the previous state-of-the-art on both synthetic and real-world datasets, with experimental results demonstrating its superiority.