Many graph clustering methods replace the hard problem of splitting a graph into groups with a smoother version. In that version each data point gets a vector of soft cluster memberships, and the membership matrix is required to have nonnegative entries and orthonormal columns. The appeal is that labels come out directly: assign each point to its largest entry, with no k-means step afterward. This note starts from an elementary fact that this literature does not exploit. Two nonnegative vectors are orthogonal only when they are never both positive at the same coordinate. A nonnegative matrix with orthonormal columns therefore has at most one nonzero per row. It is exactly a partition of the points with a positive weight on each point. The so-called relaxation is not a relaxation at all, but a combinatorial problem in disguise. The multiplicative-update solvers used for it work in the interior of the nonnegative orthant and only approximately enforce orthogonality. That explains why their results depend so strongly on where they start.
We propose to make this fact operational. For the common trace-form objectives, once the partition is fixed, the best weights have a closed form: a Perron eigenvector of each cluster's block of the graph matrix. The objective of any partition can therefore be computed exactly. The standard unconstrained spectral solution, the sum of the top or bottom $k$ eigenvalues, gives a bound that no partition can beat. The difference between the two is a computable, per-run certificate of how far a solution is from optimal. We use the certificate in three ways. It measures initialization sensitivity honestly across seeds. It tells a practitioner when restarting is worth the cost. It also drives a partition-space local search, seeded from spectral rotation, that decreases the true objective monotonically.
Core Claim
Let $W \ge 0$ be a symmetric $n \times n$ similarity matrix and consider $\max_Q \operatorname{tr}(Q^\top W Q)$ subject to $Q \ge 0$ and $Q^\top Q = I_k$. The same structure holds for minimizing $\operatorname{tr}(Q^\top L Q)$ with a graph Laplacian $L$. Every feasible $Q$ corresponds to a partition $C_1,\dots,C_k$ together with unit-norm positive weight vectors $q_j$, one supported on each cluster. For a fixed partition the objective separates as $\sum_j q_j^\top W_{C_j C_j} q_j$, where $W_{C_j C_j}$ is the principal submatrix of $W$ restricted to cluster $C_j$. Each term is therefore maximized by the leading eigenvector of $W_{C_j C_j}$, which Perron–Frobenius guarantees is nonnegative. The problem reduces exactly to
$$ \max_{C_1,\dots,C_k} \sum_{j=1}^{k} \lambda_{\max}\!\left(W_{C_j C_j}\right) \;\le\; \sum_{j=1}^{k} \lambda_j(W), $$
where $\lambda_j(W)$ is the $j$-th largest eigenvalue of $W$. The inequality is Ky Fan's maximum principle applied to the orthonormality constraint alone. For the Laplacian version the per-cluster quantity becomes the smallest eigenvalue of the principal block $L_{C_j C_j}$. This is a Dirichlet eigenvalue that includes the edges leaving the cluster, so it carries the cut cost. Its eigenvector is positive when the cluster is connected, because the block is an irreducible M-matrix. The right-hand side is a lower bound in that case.
Two claims follow and would be new. First, initialization sensitivity in nonnegative orthogonal clustering is a choice among partition basins of this exact combinatorial objective, not a smooth-landscape phenomenon. Its severity can be measured per run as the gap between the left and right sides above. Second, searching directly over partitions with exact closed-form weights reaches smaller certified gaps than the best of many multiplicative-update restarts, at comparable cost. The local search is warm-started from spectral rotation.
The closed-form weights cover objectives that are quadratic in $Q$. The structure of the feasible set holds for any objective, but other objectives need a numerical inner solve. One example is the MinMax Cut ratio objective of Improved MinMax Cut Graph Clustering with Nonnegative Relaxation. Another is the joint feature-selection objective of Unsupervised Feature Selection Using Nonnegative Spectral Analysis.
Relation to Prior Work
Three papers motivate the proposal by showing that nonnegative orthogonal relaxations beat k-means post-processing, while leaving their own solvers' starting points unexamined. Improved MinMax Cut Graph Clustering with Nonnegative Relaxation imposes $Q \ge 0$, $Q^\top Q = I$ and solves with multiplicative updates that converge monotonically. It reports 79.88% accuracy on AT&T faces, against 75.92% for Normalized Cut. Nonnegative Spectral Clustering with Discriminative Regularization (NSDR) adds a Fisher-style scatter term and reports 86.3% accuracy on MSRA and 86.2% NMI on USPS. Unsupervised Feature Selection Using Nonnegative Spectral Analysis uses the same constraint to produce pseudo-labels.
All three treat the constrained problem as a continuous relaxation solved to a local optimum. We instead identify it as a partition problem, which makes their reported results single draws from a distribution over partition basins. Orthogonal and Nonnegative Graph Reconstruction for Large Scale Clustering (ONGR) uses the same pair of constraints on an anchor graph for scale. Our analysis applies to its constraint set unchanged, so it serves as a scalability reference rather than a competitor on the question of optimality.
Two papers supply the starting point and the closest competitor. Spectral Rotation versus K-Means in Spectral Clustering rotates the unconstrained eigenvectors toward a discrete indicator and improves COIL-20 accuracy from about 61.2% to 67.5%. It never optimizes the nonnegative objective itself. We reuse its output as our seed and then optimize the exact objective, which it does not do. Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts is the conceptual cousin. Its RatioDCA method works with an exact continuous reformulation of balanced cuts and comes with an improvement guarantee from a spectral seed, cutting MNIST error from 22.5% to 14.9%. It works through nonlinear 1-Laplacians with nested primal-dual solves. We show that the matrix-factorization line already holds an exact problem with closed-form inner solutions, plus a spectral bound that RatioDCA lacks as a certificate.
The initialization literature constrains the design. Inexact Block Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization and Clustering by Low-Rank Doubly Stochastic Matrix Decomposition both seed nonnegative solvers with mixed-sign eigenvectors that are truncated heuristically. Our closed-form Perron weights avoid truncation entirely, because the seed is a partition and its weights are nonnegative by theorem. Improved SVD-based initialization for nonnegative matrix factorization using low-rank correction shows that careful spectral seeding matters, reaching an initial error of 15.29% against 21.35% for NNDSVD on AT&T at rank 100. It addresses unconstrained-orthogonality asymmetric NMF, where no partition structure exists.
Basin-of-attraction theory exists only for unconstrained low-rank factorization. Dropping Convexity for Faster Semi-definite Optimization and A Unified Variance Reduction-Based Framework for Nonconvex Low-Rank Matrix Recovery are examples. We do not attempt a radius of attraction. Our certificate is a posteriori and applies to any run. The symmetric NMF solvers Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization and Fast and Effective Algorithms for Symmetric Nonnegative Matrix Factorization lack the orthogonality constraint, so their feasible sets are genuinely continuous. They mark the boundary of our scope and serve as external baselines on shared datasets.
Research Program
The work has three parts.
The first part is analytical and short. We state and prove the support-disjointness characterization, the per-cluster eigenvector form of the optimal weights for trace objectives, and the eigenvalue bound for both the similarity and the Laplacian versions. We will then check which published objectives fall within the quadratic case. That includes whether NSDR's discriminative term can be written as $\operatorname{tr}(F^\top M F)$ for a fixed $M$, which we expect but must verify against the paper's exact form. For the MinMax ratio objective we fall back to a one-dimensional inner optimization per cluster.
The second part is an empirical audit of existing solvers through this lens. For each published multiplicative-update method we run many random seeds. At convergence we measure two kinds of residual. The first is the orthogonality residual $\|Q^\top Q - I\|_F$. The second is the fraction of rows with more than one significant entry. Together they show how far the solver actually ends from the feasible set it claims to enforce. We then round each solution to its argmax partition and compute the exact partition objective and its certified gap. This produces, per dataset, a distribution of gaps and of accuracy across seeds. We check whether the exact objective predicts accuracy across seeds; reconstruction error famously fails to do so, as the doubly stochastic decomposition study notes.
The third part is the algorithm, which works directly over partitions. It starts from the spectral-rotation partition and refines it with greedy single-point moves and pairwise swaps. Each move is accepted only if it raises the exact objective, so the objective improves monotonically and the method stops at a local optimum with respect to moves. The cost of a move is dominated by updating the leading eigenvalue of two cluster blocks. We estimate it from the current Perron vectors with a first-order Rayleigh-quotient update and confirm accepted moves with a few warm-started Lanczos iterations. On sparse k-nearest-neighbor graphs this keeps the cost of a full sweep close to the number of edges times a small constant.
The certificate also decides when to stop. If the gap after local search is within a tolerance of the spectral bound, no restart can help much. Otherwise the method spends a restart budget, seeding from perturbed rotations.
Baselines
The naive reference point is standard spectral clustering followed by k-means with many random restarts, keeping the lowest within-cluster sum of squares. It is the procedure most practitioners use, and it costs one eigendecomposition. Spectral Rotation versus K-Means in Spectral Clustering reports about 61.2% accuracy for it on COIL-20. Nonnegative Spectral Clustering with Discriminative Regularization reports 52.7% accuracy on MSRA and 61.6% NMI on USPS for k-means. We give it 100 restarts on the same graph.
The strongest existing methods for the exact question asked here are the published nonnegative orthogonal solvers themselves, run with a matched restart budget and selected by their own objective. On AT&T the reference figure is 79.88% accuracy for nonnegative MinMax Cut Improved MinMax Cut Graph Clustering with Nonnegative Relaxation. On Binalpha its cluster-balance score is 9.26. On MSRA and USPS the references are NSDR's 86.3% accuracy and 86.2% NMI. On COIL-20 the reference is 67.5% for spectral rotation alone. On MNIST we compare against RatioDCA's 14.9% error from Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts, and against the doubly stochastic decomposition's 0.97 purity from Clustering by Low-Rank Doubly Stochastic Matrix Decomposition. On ORL we compare against SymANLS's 0.8075 accuracy from Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization.
Published numbers come from different graph constructions. Fairness therefore comes from reimplementing every method on one k-nearest-neighbor graph per dataset, with the neighbor count and bandwidth chosen once by a fixed rule and shared by all methods. Each method gets the same wall-clock budget, spent on restarts where the method has nothing else to spend it on. Each also gets the same hyperparameter grid size where hyperparameters exist. We will report the published figures alongside, clearly labeled, and will not mix them into our comparisons. Beating the strongest baseline means two things on most of the benchmark datasets: a certified gap that is lower in median and in worst case across seeds, and matching or better accuracy and NMI, at equal compute.
One ablation isolates the key ingredient, exact partition-space optimization. It runs the same local search but replaces the closed-form Perron weights with uniform within-cluster weights, which turns the objective into an ordinary average-association cut. A second ablation runs the local search from a random partition instead of the spectral-rotation seed, to separate the contribution of the seed from that of the search.
Why not just…?
Why not just warm-start the existing multiplicative updates from spectral rotation? This is the obvious move at the intersection and a genuine threat to the algorithmic half of the proposal. We run it as a baseline: the rotation indicator is converted to Perron weights and handed to the published update rule. If it reaches the same certified gaps as partition-space search, the algorithmic claim fails. The proposal then reduces to the characterization and the certificate, which still stand, because only the certificate can say whether either method is near optimal. There are two reasons to expect a difference. The updates leave the feasible set as soon as they start, since they enforce orthogonality only approximately. And entries that reach zero cannot recover under multiplicative updates. That second weakness is the known stalling problem, and it bites hardest when the seed is already sparse, as an indicator is.
Why not just use spectral clustering with many k-means restarts? The evidence above shows it trails nonnegative relaxations by large margins on MSRA and USPS and produces skewed partitions on Binalpha. More to the point, k-means restarts optimize a Euclidean objective in the embedding, not the graph objective. Our certificate will show directly how large the graph-objective gap of its best restart is.
Why not just run RatioDCA, which already has an improvement guarantee from a spectral seed? RatioDCA optimizes a different, 1-Laplacian balanced cut and requires nested primal-dual solves. It is the right comparison on MNIST, where its 14.9% error is the bar to clear. We compare its partitions under our exact objective and its own, and compare runtimes. We concede that on balanced-cut objectives it may remain more accurate. Our claim is limited to trace-form nonnegative orthogonal objectives, where we expect exact closed-form inner solves to be cheaper.
Proposed Experiments
The datasets are those with reported numbers for the competing methods: AT&T/ORL, Binalpha, MSRA, USPS, COIL-20, JAFFE and MNIST. MNIST-extend is added as a scaling test against ONGR's reported time of under 150 seconds. Metrics are accuracy, NMI, cluster balance, the exact partition objective, the certified gap, the orthogonality residual at convergence, and wall-clock time. All are reported as distributions over 100 seeds rather than single best runs.
Three checks decide the proposal. The first is whether published multiplicative-update solvers converge to points measurably off the feasible set, with nonzero orthogonality residual and multi-support rows, and whether their argmax roundings vary across seeds in exact objective. If they do not, the sensitivity story is weaker than the literature suggests. The second is whether the exact objective, unlike reconstruction-style losses, ranks seeds by accuracy. That is what would justify the certificate as a model-selection tool without labels. The third is whether partition-space search from spectral rotation reaches strictly smaller certified gaps than the best of 100 warm-started or random multiplicative-update runs at equal time. It would have to do so on at least five of the seven datasets, with no loss in accuracy.
A negative result on the third check paired with positive results on the first two would still be publishable. It would show that the field's nonnegative relaxations are exact partition problems whose optimality can be certified after the fact, even if better solvers are not needed.
References
- Improved MinMax Cut Graph Clustering with Nonnegative Relaxation
- Unsupervised Feature Selection Using Nonnegative Spectral Analysis
- Nonnegative Spectral Clustering with Discriminative Regularization
- Orthogonal and Nonnegative Graph Reconstruction for Large Scale Clustering
- Spectral Rotation versus K-Means in Spectral Clustering
- Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts
- Inexact Block Coordinate Descent Methods For Symmetric Nonnegative Matrix Factorization
- Clustering by Low-Rank Doubly Stochastic Matrix Decomposition
- Improved SVD-based initialization for nonnegative matrix factorization using low-rank correction
- Dropping Convexity for Faster Semi-definite Optimization
- A Unified Variance Reduction-Based Framework for Nonconvex Low-Rank Matrix Recovery
- Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization
- Fast and Effective Algorithms for Symmetric Nonnegative Matrix Factorization