# Clustering via Max-Cut

I wonder if there are papers that uses max cut algorithm(s) to cluster data. For example, if an edge between two nodes $u$ and $v$ indicate that $u$ and $v$ are different, then the max-cut in some sense partition the data into two clusters in a meaningful way.

• Usually you want to cut as few edges as possible, so min cut or sparsest cut seems more appropriate. – Yuval Filmus Jun 30 '18 at 6:33
• And you usually have edges between nodes that are similar and not different. Then you get back the classic clustering problem. – Pål GD Jun 30 '18 at 7:25
• Max-cut for general graphs is known to be $\text{NP-Complete}$. So usually, when people use graph-cuts to cluster data into two parts, they tend to use an "energy function" that penalize dividing the graph at certain points. Graph-cuts (with max-flow min-cut) are used a lot in Computer Graphics and Computer Vision for example. Here is one example for such use: csd.uwo.ca/~yuri/Papers/iccv01.pdf ("Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images") – Mickey Jun 30 '18 at 17:24
• I am aware of min cut formulation. However, I was wondering if there are applications where the notion of being "different" instead of being "similar", represented by graphs, is easier to see in the data. – HTV Jun 30 '18 at 20:37