Beyond Spectral Clustering: Probabilistic Cuts for Differentiable Graph Partitioning
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910092276793344 |
|---|---|
| author | Ghriss, Ayoub |
| author_facet | Ghriss, Ayoub |
| contents | Probabilistic relaxations of graph cuts offer a differentiable alternative to spectral clustering, enabling end-to-end and online learning without eigendecompositions, yet prior work centered on RatioCut and lacked general guarantees and principled gradients. We present a unified probabilistic framework that covers a wide class of cuts, including Normalized Cut. Our framework provides tight analytic upper bounds on expected discrete cuts via integral representations and Gauss hypergeometric functions with closed-form forward and backward. Together, these results deliver a rigorous, numerically stable foundation for scalable, differentiable graph partitioning covering a wide range of clustering and contrastive learning objectives. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_02272 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beyond Spectral Clustering: Probabilistic Cuts for Differentiable Graph Partitioning Ghriss, Ayoub Machine Learning Data Structures and Algorithms Probabilistic relaxations of graph cuts offer a differentiable alternative to spectral clustering, enabling end-to-end and online learning without eigendecompositions, yet prior work centered on RatioCut and lacked general guarantees and principled gradients. We present a unified probabilistic framework that covers a wide class of cuts, including Normalized Cut. Our framework provides tight analytic upper bounds on expected discrete cuts via integral representations and Gauss hypergeometric functions with closed-form forward and backward. Together, these results deliver a rigorous, numerically stable foundation for scalable, differentiable graph partitioning covering a wide range of clustering and contrastive learning objectives. |
| title | Beyond Spectral Clustering: Probabilistic Cuts for Differentiable Graph Partitioning |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.02272 |