[Back]

T. Dittrich, G. Matz:
"Non-Convex Total Variation Minimization for Signed Graph Cut Clustering";
Poster: 2021 55th Asilomar Conference on Signals, Systems, and Computers (ACSSC 2021), Pacifc Grove, CA, USA; 10-31-2021 - 11-03-2021.

We consider graph cut minimization in signed graphs with three clusters. To this end, we use the signed total variation, which is convex and has shown promising results in our previous work on semi-supervised clustering. Here, we consider the unsupervised case and use a non-convex norm-constraint to avoid degenerate solutions. We solve the resulting minimization problem via the non-convex ADMM and derive conditions on the graph topology that guarantee convergence under rather weak conditions on the graph. In our numerical experiments we study the labeled stochastic block model and compare our method to a state-of-the-art clustering algorithm. The results are convincing both with regard to the fraction of mislabeled nodes and thesigned cut.

Signed Graphs, Graph Cut, non-convex Minimization, ADMM