Constrained Graph Clustering: A Spectral Algorithm with Generalized Eigenvectors

Given a must-link graph $G = (V, E_G)$ and a cannot-link graph $H=(V,E_H)$ as input, the objective of constrained clustering is to partition $V$ into $k$ parts while minimizing the maximum cut ratio between $G$ and $H$. In this paper we design and analyze a variant of the spectral clustering algorithm using the $k$ smallest generalized eigenvectors as the embedding space. We prove that our proposed algorithm achieves an $O(1)$-approximation of the optimal cut-ratio under a natural assumption on the input graphs. We further study the case in which the cannot-link constraints might not be available, and develop an iterative pipeline that repeatedly applies the output of spectral clustering or constrained clustering to generate new constraints, thereby progressively improving cluster quality. We experimentally compare our proposed algorithm with the previous state-of-the-art, and demonstrate the superior performance of our algorithms on both synthetic and real-world datasets.