Beyond Spectral Clustering: Probabilistic Cuts for Differentiable Graph Partitioning
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Contrastive Learninggraph partitioningSimilar Papers 제목 키워드 기반
Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts
Spectral clustering is based on the spectral relaxation of the normalized/ratio graph cut criterion. While the spectral relaxation is known to be loose, it has been shown recently that a non-linear eigenproblem yields …
ClusteringCertifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering
Spectral clustering has become one of the most widely used clustering techniques when the structure of the individual clusters is non-convex or highly anisotropic. Yet, despite its immense popularity, there exists fairly…
ClusteringSpectral Modification of Graphs for Improved Spectral Clustering
Spectral clustering algorithms provide approximate solutions to hard optimization problems that formulate graph partitioning in terms of the graph conductance. It is well understood that the quality of these approxima…
Clusteringgraph partitioningMultiway $p$-spectral graph cuts on Grassmann manifolds
Nonlinear reformulations of the spectral clustering method have gained a lot of recent attention due to their increased numerical benefits and their solid mathematical background. We present a novel direct multiway spect…
ClusteringGraph ClusteringSpectral Graph ClusteringGeneralized Clustering by Learning to Optimize Expected Normalized Cuts
We introduce a novel end-to-end approach for learning to cluster in the absence of labeled examples. Our clustering objective is based on optimizing normalized cuts, a criterion which measures both intra-cluster similari…
Clustering