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.

  • 2
    $\begingroup$ Usually you want to cut as few edges as possible, so min cut or sparsest cut seems more appropriate. $\endgroup$ Jun 30, 2018 at 6:33
  • $\begingroup$ And you usually have edges between nodes that are similar and not different. Then you get back the classic clustering problem. $\endgroup$
    – Pål GD
    Jun 30, 2018 at 7:25
  • $\begingroup$ 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") $\endgroup$
    – Mickey
    Jun 30, 2018 at 17:24
  • $\begingroup$ 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. $\endgroup$ Jun 30, 2018 at 20:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.