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$ – Yuval Filmus Jun 30 '18 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 '18 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 '18 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$ – HTV Jun 30 '18 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.