Accelerating Spectral Clustering under Fairness Constraints

Alex Lambert; Francesco Tonin; Johan A. K. Suykens; Volkan Cevher

REVIEW 3 major objections 5 minor 15 references

Accelerating Spectral Clustering under Fairness Constraints

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that fair spectral clustering can be made 4-8x faster by recasting it as a difference-of-convex program with an ADMM variable split whose subproblems need only gradient steps and small SVDs, never a full…

desk verdict A well-tested and honest surrogate-based fast fair spectral clustering algorithm whose unproven equivalence to the original problem is the main caveat—worth reviewing, with revisions requested. read the letter →

arxiv 2506.08143 v1 pith:Y7RJR7XO submitted 2025-06-09 cs.LG

Francesco Tonin , Alex Lambert , Johan A. K. Suykens , Volkan Cevher This is my paper

classification cs.LG

keywords fairspectralclusteringdifferenceofconvexfunctionsADMMgroupfairnessconstraintseigendecompositionStiefelmanifoldscalability

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that fair spectral clustering—clustering with the constraint that each demographic group appears in every cluster in the same proportion as in the whole dataset—can be made practical on large real-world graphs. Its central claim is that the Fair SC trace-maximization problem can be recast as a difference-of-convex (DC) program with a deliberately chosen ADMM variable augmentation, so that every subproblem reduces to fast gradient steps and small SVDs instead of the expensive eigendecomposition of a fairness-modified graph Laplacian. If the claim is right, fair clusterings that previously took minutes can be computed in seconds on datasets of tens of thousands of points, with reported speedups of about 4-8x over the fastest prior method and comparable balance and clustering quality. The experiments in the paper support this with consistent runtime reductions on synthetic and real benchmarks, with the advantage growing as the number of points and clusters increases.

What carries the argument

The machinery is the DC formulation of the fair spectral clustering problem, built from $f(X) = \tfrac12\|X\|_F^2$, $g$ the indicator of the Stiefel manifold $\{H : H^\top H = I_k\}$, and $h$ the indicator of the fairness constraint $F^\top H = 0$. Two design choices carry the argument: replacing the affinity $M$ by $M^2$ in the objective so that $M^{1/2}$ never has to be computed, and augmenting the variables with the linear constraint $MH = Y$ so that the $H$-subproblem dualizes into a smooth problem solvable by fast gradient methods using the closed-form conjugate $g^\star(MV) = \operatorname{Tr}(\sqrt{V^\top M^2 V})$, while the $Y$-subproblem becomes a closed-form projection onto the null space of $F^\top$. Final primal recovery is a single SVD of a $k \times k$ matrix, making the per-iteration cost dominated by $O(k n^2)$ matrix multiplication.

What would settle it

On a small graph where the exact optimum of the original Fair SC problem can be computed by full eigendecomposition, run the proposed surrogate and measure balance and the fairness residual $\|F^\top H\|$: if systematically skewed group proportions make the surrogate's balance or constraint residual diverge from the exact solution, the claim that the substitution does not sacrifice solution quality is refuted.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is an algorithmic reformulation: the constrained trace maximization $\max_{H} \operatorname{Tr}(H^\top M H)$ with $H^\top H = I_k$ and $F^\top H = 0$, whose standard solvers require a null-space projection followed by an eigendecomposition of $M_Z = Z^\top M Z$, is replaced by a DC program in $M^2$ with an ADMM splitting that enforces the fairness constraint on $MH$ rather than on $H$. The authors claim this substitution allows them to bypass the computation of $M^{1/2}$ without sacrificing solution quality, and that enforcing fairness on $MH$ effectively promotes the same group balance, pointing to the benchmark tables as evidence. If that is correct, the method simultaneously avoids forming $M^{1/2}$, avoids the projected eigenproblem, and concentrates all hard work in $O(k n^2)$ matrix multiplications, which are far cheaper in practice than cubic eigendecompositions.

Load-bearing premise

The speedup rests on an unproven equivalence: solving the surrogate that uses $M^2$ in the objective and imposes fairness on $MH$ is assumed to deliver essentially the same fair clustering as the original problem, and the paper defends this only with empirical comparisons.

Editorial extensions

If this is right

On the reported benchmarks, the proposed method finishes fair spectral clustering in seconds where the previous scalable solver s-FSC takes 19-167 seconds, and the original o-FSC cannot finish the largest datasets within 500 seconds.
The runtime advantage widens with the number of clusters $k$, because the baseline's eigendecomposition needs more Arnoldi iterations for extra eigenvectors while the new method only computes SVDs of $k \times k$ matrices.
The method never forms $M^2$ or the modified Laplacian explicitly; it needs only matrix-vector products with $M$, keeping the dominant cost at $O(k n^2)$ matrix multiplications.
Across the tested real-world datasets, the clustering cost and balance of the surrogate solution are close to those of the exact eigendecomposition solution, with speedups of 4-8x over s-FSC.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's surrogate—maximizing with $M^2$ and enforcing fairness on $MH$—is validated only empirically; a direct comparison with the exact optimum of the original problem on small instances would quantify the approximation gap that the speedup buys.
Because the paper mostly reports average balance, cases where one cluster badly under-represents a group could be hidden; reporting minimum balance or per-cluster constraint residuals would be the more stringent test for fairness-critical deployment.
The same DC-plus-small-SVD recipe likely transfers to other linearly constrained spectral problems, such as must-link and cannot-link constraints, by changing the indicator function $h(\cdot)$, a direction the paper itself sketches as future work.
Combining this fast solver with fair-graph-learning approaches that preprocess an induced fairer graph could give end-to-end fairness improvements at a fraction of the current computational cost.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Here is my quick take on Tonin et al. The paper gives a faster algorithm for fair spectral clustering (Fair SC) by recasting the problem as a DC program and solving it with ADMM, where each subproblem is handled by fast gradient methods and small SVDs rather than the expensive eigendecomposition of a modified Laplacian. On real datasets it reports 4–8x speedups over the state-of-the-art s-FSC baseline, with comparable balance and clustering cost. That part is solid and reproducible: the experiments cover multiple synthetic and real datasets, varying n and k, with standard deviations, and the runtime gains are consistent.

The genuinely new ingredient is the variable augmentation that couples the ADMM splitting via M H instead of H, plus the use of M^2 in the objective instead of M. That choice lets them avoid computing M^{1/2} and keeps each subproblem efficient. The construction is nontrivial, the dualization is worked out carefully, and the proofs in the appendix look correct. The citation pattern is appropriate, building on prior DC-PCA work and the Fair SC literature.

The soft spot is exactly the one flagged in the reader's report. The algorithm optimizes a surrogate problem: it replaces Tr(H^T M H) with Tr(H^T M^2 H) and enforces fairness through F^T M H = 0 rather than the original F^T H = 0. The paper says these changes do not sacrifice solution quality and demonstrates this empirically, but there is no theorem or bound connecting solutions of the surrogate to solutions of (6). The empirical evidence is encouraging, especially on LastFMNet and 4area, but it is not a guarantee. Proposition 3.4 only gives stationarity of the surrogate under a dual convergence assumption. So the 4–8x speedup claim is real for the surrogate, and likely for the original problem in the tested regimes, but that equivalence remains unproven. This is not a fatal flaw: the authors are transparent about the replacement, and a revision should either provide a sharper analysis of the surrogate gap or at least test on more adversarial data where the approximation could fail.

One minor point: code is not released, and the reader requested it. That would help adoption and is easy to address.

Overall, this is a solid, well-written algorithmic paper that deserves peer review. The surrogate gap is a serious question but not a reason to reject; it is a reason to request a revision that addresses it. I would bring it to the reading group and would likely cite it if I worked on fair spectral clustering.

Recommendation: send it to review.

Referee Report

3 major / 5 minor

Summary. The paper proposes an ADMM-type algorithm for fair spectral clustering (Fair SC). The authors cast the Fair SC problem in a difference-of-convex (DC) framework, introduce a variable augmentation that couples the auxiliary variable with M H, and derive dual subproblems whose gradients are computable via small SVDs and matrix multiplications, thereby avoiding the explicit eigendecomposition used by prior methods (o-FSC and s-FSC). They report speedups of roughly 4-8x over s-FSC on real-world datasets and larger speedups on synthetic benchmarks, with comparable balance and clustering cost. The paper includes synthetic and real experiments, a sensitivity analysis of the ADMM penalty parameter, and proofs of subproblem derivations in the appendix.

Significance. If the algorithm truly solved the Fair SC problem (6) at the claimed speed, this would be a practically valuable contribution to fair clustering, particularly for larger datasets and larger numbers of clusters. The empirical study is solid: multiple datasets, runtime and balance comparisons, sensitivity analysis, and standard deviations in the appendix all support the practical efficiency claim. The dualization of the subproblems is elegant, and the small-SVD construction for the k×k matrix is a nice algorithmic device. The manuscript also correctly identifies the computational bottleneck of existing methods. The main weakness is theoretical: the algorithm optimizes a surrogate problem with an unquantified gap to (6), and the DC/convex duality derivation relies on assumptions that are not fully stated or verified. These gaps make the central claim--that Algorithm 1 is an accelerated solver for Fair SC--conditional on an empirical assumption.

major comments (3)

[Section 3, Eqs. (10)-(11)] The proposed method solves a surrogate problem: the objective in (10) is Tr(H^T M^2 H) instead of Tr(H^T M H), and the fairness constraint in (11) is F^T M H = 0 rather than F^T H = 0 as in the original Fair SC problem (6). The paper gives no theorem or bound relating the optima of the surrogate to those of (6). The statements in Section 3 that optimizing with M^2 is "without sacrificing solution quality" and that enforcing fairness on M H "effectively promotes the same group balance" are supported only by empirical comparisons of final clusterings in Tables 1-3. Since the speedup claim is conditional on the surrogate being a faithful proxy, this gap is load-bearing and should be addressed, for example by a bound on the surrogate gap or by experiments on regimes where the two problems are known to diverge.
[Section 3, Propositions 3.2-3.3 and Remark 3.1] The DC formulation is not rigorously established. The paper defines g(H) = ι_{S_n^k}(H) with S_n^k the nonconvex Stiefel manifold, yet the dual derivation in Proposition 3.2 and the conjugate computation g^*(M V) = Tr(sqrt(V^T M^2 V)) in Proposition 3.3 rely on Fenchel duality and conjugate calculus that require convexity of g. Remark 3.1 notes that the Stiefel constraint can be relaxed to its convex hull, but the definitions of f, g, h and the primal update (17) still use the original Stiefel constraint. The authors must either prove that this nonconvex indicator fits the DC framework with strong duality, or explicitly state that the algorithm solves the convex relaxation of (10) and justify the final Stiefel projection.
[Section 3.3 (Proposition 3.4) and Appendix D.1] Proposition 3.4 only establishes that, under the assumption that the dual sequence P^(i) converges, any limit point satisfies first-order conditions of the surrogate (11). Neither the convergence of P^(i) nor the approximation of the original problem (6) is proven. The verification of the assumptions in Appendix D.1 also relies on the linear independence of constraint gradients, which requires F to have full column rank; the paper mentions a possible rank fix but does not confirm that it is used in the experiments. As a result, the convergence analysis does not currently support the claim that Algorithm 1 computes a Fair SC solution.

minor comments (5)

[Throughout] There are several typos: "exisiting" in the Introduction, "mantains" in the Figure 3 caption, "summmarized" in Appendix B, "m-SMB" in the Table 7 caption, and "no-FSC" in Table 6.
[Table 3] The column labeled "Time" actually reports speedup ratios (e.g., 4.16×, 8.65×). Rename the column to "Speedup" and put the raw times in Table 2 or a separate table to avoid confusion.
[Figure 8 caption] The legend uses "s-FSC (green)" and "the proposed algorithm (blue)", whereas all other figures use blue for s-FSC and orange for the proposed method. Unify the color scheme across figures.
[Section 3.3] The complexity claim that matrix multiplication is "much more efficient in practice" than eigendecomposition is informal; provide operation counts or explicitly state the total cost including the ADMM iterations T and L-BFGS iterations, so readers can compare with the one-time O(n^3) eigendecomposition cost.
[Table 3 and Section 4.1] The reported average balance values for LastFM, Thyroid, and Census are very low (0.01, 0.003, 0.0004). The paper should explicitly note that this reflects the known limitation of the embedding-level fairness constraint (6) in producing balanced clusters on these datasets, and that the method's contribution is acceleration of the same objective rather than improved fairness over s-FSC.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the DC/ADMM reformulation is self-contained; the unproven surrogate gap is an approximation concern, not a definitional reduction.

full rationale

The paper's central derivation is a reformulation of the fair spectral clustering problem into a DC objective with variable augmentation (Eqs. 10, 11, Algorithm 1). The dual subproblem and its gradient are derived in Propositions 3.2 and 3.3, with proofs given in Appendix D.3-D.4 using standard Fenchel conjugacy and the nuclear norm identity. Although the cited DC-PCA work (Tonin et al., 2023) shares authors with the present paper, it is not load-bearing: the needed dualization and conjugate identities are re-proved in the appendix, and they do not assume the paper's conclusions. The replacement of M by M^2 in the objective and the replacement of F^T H = 0 by F^T M H = 0 is an explicit modeling/approximation choice, not a definitional equivalence: the paper states it is done to avoid M^{1/2} and that equivalence is demonstrated empirically, and the reported balance is measured independently rather than being constructed from the constraint. An unproven bound between the surrogate (10)-(11) and the original problem (6) is a correctness/approximation risk, not circularity: no equation is shown to equal another by construction, no fitted parameter is renamed as a prediction, and no uniqueness claim is imported from the authors' prior work. The runtime speedups are measured comparisons against o-FSC and s-FSC, not fitted predictions. No self-definitional, fitted-input, self-citation-load-bearing, imported-uniqueness, ansatz-smuggling, or renaming step was found.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard optimization theory (Fenchel duality, ADMM) plus several domain or ad hoc assumptions: full-rank M, alpha<1, convergence of ADMM multipliers, and the empirical surrogate equivalence. The method has no data-fitted constants in the prediction sense, but it does have several hand-chosen hyperparameters. No invented physical or mathematical entities are introduced.

free parameters (5)

Initial ADMM penalty alpha0 = 0.005
Chosen via sensitivity analysis (Table 5); smaller alpha gives better fairness constraint satisfaction. This is a tuning parameter chosen by hand, not fitted to the central result.
ADMM penalty update factors tau, mu = tau=2, mu=10
Standard values from Boyd et al. (2011), chosen by hand for the residual balancing rule in Eq. (19).
ADMM iteration count T = 10
Fixed for all experiments; Table 5 shows convergence within about 5-9 iterations on one dataset, but T is not derived from a guarantee.
L-BFGS tolerances gtol, ftol = 1e-3, 1e-4
Optimizer stopping tolerances for the dual DC subproblem, set in Appendix B. They are practical choices, not derived.
RBF kernel width gamma = 1/d, or 1/(0.01 d) for Thyroid
Hyperparameter for graph construction on real datasets; a standard heuristic, not optimized for the reported results.

assumptions (4)

domain assumption The affinity matrix M is full rank
Stated before Proposition 3.3 to guarantee existence of gradients in the dual problem. The authors note this typically holds for positive definite kernels, but it is not checked for graph-derived M from Remark 2.3.
domain assumption alpha < 1 for convexity of the H-subproblem
Proposition 3.2 requires alpha < 1 for the DC formulation to be convex. The ADMM update rule (19) can increase alpha above 1 via tau=2, and no cap or analysis for this case is provided.
domain assumption The sequence of dual variables P^(i) converges
Proposition 3.4 assumes convergence of P^(i) to establish first-order optimality of limit points; this convergence is not proven in the paper.
ad hoc to paper Surrogate problem: maximizing Tr(H^T M^2 H) with F^T M H=0 approximates the original Fair SC problem (6)
The paper replaces M with M^2 and enforces fairness on MH instead of H, claiming empirical equivalence. No theorem or bound relates the surrogate to the original problem; this is the central unproven modeling assumption.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Accelerating Spectral Clustering under Fairness Constraints." pith.science (2026). https://pith.science/paper/Y7RJR7XO

@misc{pith2026250608143,
  author       = {Pith},
  title        = {Pith review of: Accelerating Spectral Clustering under Fairness Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y7RJR7XO}},
  note         = {Machine review of arXiv:2506.08143}
}

read the original abstract

Fairness of decision-making algorithms is an increasingly important issue. In this paper, we focus on spectral clustering with group fairness constraints, where every demographic group is represented in each cluster proportionally as in the general population. We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework. To this end, we introduce a novel variable augmentation strategy and employ an alternating direction method of multipliers type of algorithm adapted to DC problems. We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work, which required a computationally expensive eigendecomposition. Numerical experiments demonstrate the effectiveness of our approach on both synthetic and real-world benchmarks, showing significant speedups in computation time over prior art, especially as the problem size grows. This work thus represents a considerable step forward towards the adoption of fair clustering in real-world applications.

Figures

Figures reproduced from arXiv: 2506.08143 by the authors.

**Figure 2.** Fair clustering of Elliptical dataset. The clustering label is represented by different colors, and sensitive attributes by shapes. The legend is “C-i, G-j” for Cluster-i, Group-j. These plots show that our method produces assignments comparable to exact algorithms (o-FSC, s-FSC). Critically, we achieve this with reduced computations [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Runtime and fairness across k. Fair SC on realword datasets (a) LastFMNet, (b) 4area with s-FSC (Wang et al., 2023) (blue) and the proposed algorithm (orange). In each dataset, the left plot shows the runtime comparison and the right plot shows the average balance, for multiple numbers k of clusters. Left plots show that our method is consistently faster than s-FSC, with even better efficiency gains as k increase… view at source ↗

Figures from the paper (6 more)

**Figure 4.** Figure 4: Scalability. Runtime (in seconds) of our algorithm, s-FSC, and o-FSC on RandLaplace at multiple sample sizes n ∈ {5000, 7500, 10000} with h = 5 and k ∈ {10, 25, 50} [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

**Figure 5.** Figure 5: Fair spectral clustering on LastFMNet with s-FSC ( [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]

**Figure 6.** Figure 6: Fair spectral clustering on Thyroid with s-FSC ( [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]

**Figure 7.** Figure 7: Fair spectral clustering on 4area with s-FSC ( [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]

**Figure 8.** Figure 8: Fair spectral clustering on Census with s-FSC ( [PITH_FULL_IMAGE:figures/full_fig_p014_8.png]

**Figure 9.** Figure 9: Clustering results on synthetic datasets. The top panel shows the Elliptical dataset with [PITH_FULL_IMAGE:figures/full_fig_p016_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages

[6]

The results show that our algorithm outperforms the compared ones in terms of computational time for all tested sample sizes and cluster sizes

and s-FSC (Wang et al., 2023), is depicted in Figure 4 and reported for completeness in Table 6 here. The results show that our algorithm outperforms the compared ones in terms of computational time for all tested sample sizes and cluster sizes. These results indicate that our algorithm exhibits superior scalability as the data size and number of clusters...

work page 2023
[10]

The affinity graphs for Thyroid, Census, and 4area are obtained by a radial basis function (RBF) kernel k(xi, xj) = exp(−γ∥x i −x j∥2), where γ= 1/d and γ= 1/d∗0.01 for the smaller Thyroid, with xi ∈R d, i= 1, . . . , n. We compare with the fastest available Fair SC algorithm, i.e., s-FSC from (Wang et al., 2023). Here, we report the complete results for ...

work page 2023
[11]

by applying our faster algorithm to their learned graph. Other works on fair clustering include (Bera et al., 2019b; Backurs et al., 2019), which are not directly comparable to our work as they do not consider the spectral clustering objective. (Bera et al., 2019b) propose LP-based k-(means, median, center) clustering. Using their formulation in our work ...

work page 2019
[12]

However, extending the fairlet analysis, which relies on the k-median and k-center cost of the fairlet decomposition, to the spectral setting is not trivial

use fairlets for prototype-based clustering. However, extending the fairlet analysis, which relies on the k-median and k-center cost of the fairlet decomposition, to the spectral setting is not trivial. SC involves a spectral embedding step followed by a clustering in the embedding space, where reassigning points within a fairlet can significantly alter t...

work page 2016
[13]

17 Accelerating Spectral Clustering under Fairness Constraints To apply their result, we verify that four key assumptions hold, namely Assumption D.1, Assumption D.2, Assumption D.4 and Assumption D.5 that can be found in Magnusson et al. (2016). Assumption D.1.The functionsuandvare continuously differentiable. This is satisfied in our setting. Assumption...

work page 2016
[14]

Since polynomial functions possess derivatives of all orders, each ψij is smooth (i.e., C ∞)

To establish smoothness, observe that each component ψij(x) is a quadratic polynomial in the elements of x. Since polynomial functions possess derivatives of all orders, each ψij is smooth (i.e., C ∞). Consequently, the vector-valued function ψ is smooth. Therefore, the orthogonality constraint on matrixAadmits a smooth representation. 18 Accelerating Spe...

work page 2016
[15]

Therefore, the only linear combination of the gradients ∇xψij(¯x)that equals zero is the trivial one, which proves thatC(¯x)is linearly independent

This implies λij = 0 for all i, j. Therefore, the only linear combination of the gradients ∇xψij(¯x)that equals zero is the trivial one, which proves thatC(¯x)is linearly independent. Lemma D.7.Let F∈R n×h and H∈R n×k. Define z= vec(H)∈R nk and consider the constraint F ⊤H= 0 . Let θ(z) = vec(F ⊤H)∈R hk. The set of constraint gradients C(z) ={∇ zθi(z)|i= ...

work page 2023
[16]

Proof of Proposition 3.2 Proof.Expandingϕ(M H)to recover the expression of the augmented Lagrangian shows thatH7→ϕ(M H)is convex as long asα <1

D.3. Proof of Proposition 3.2 Proof.Expandingϕ(M H)to recover the expression of the augmented Lagrangian shows thatH7→ϕ(M H)is convex as long asα <1. Then, following Proposition 3.1 from (Tonin et al., 2023), equivalently we can write the problem as inf H∈R n×k g(H)−sup V∈R n×k {⟨V, M H⟩ −ϕ∗(V)} = inf H∈R n×k g(H) + inf V∈R n×k {ϕ∗(V)− ⟨V, M H⟩}(30) = inf...

work page 2023

Show all 15 references

[1987]

Rösner, C

DOI: https://doi.org/10.24432/C5D010. Rösner, C. and Schmidt, M. Privacy preserving clustering with constraints. InICALP,

doi
[2008]

P., Schwarting, W., Bhatia, S

Amini, A., Soleimany, A. P., Schwarting, W., Bhatia, S. N., and Rus, D. Uncovering and mitigating algorithmic bias through learned latent structure. InProceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 289–295,

2019
[2011]

The parameters τ and µ are set to 2 16 Accelerating Spectral Clustering under Fairness Constraints Table 10: Description of the real-world datasets used for the experiments

and is given by α(i+1) =    τ α(i) if R(i) F > µ S(i) F α(i)/τif S(i) F > µ R(i) F α(i) otherwise ,(19) with primal and dual residuals R(i) =M H(i) −Y (i) and S(i) =α (i)(Y (i) −Y (i+1)). The parameters τ and µ are set to 2 16 Accelerating Spectral Clustering under Fairne...

2019
[2018]

Carreira-Perpinán, M. A. and Wang, W. The k-modes al- gorithm for clustering.arXiv preprint arXiv:1304.6478,

arXiv
[2019]

Evaluating the fairness of discriminative foundation models in computer vision

Ali, J., Kleindessner, M., Wenzel, F., Budhathoki, K., 9 Accelerating Spectral Clustering under Fairness Constraints Cevher, V ., and Russell, C. Evaluating the fairness of discriminative foundation models in computer vision. In Proceedings of the 2023 AAAI/ACM Conference on A...

2023
[2024]

Another related work is (Zhang & Wang, 2024)

solves a different problem than (6): their solution is far from the exact one leading to higher spectral cost and potential training instability. Another related work is (Zhang & Wang, 2024). Our work designs a much faster method for the existing Fair SC problem defined in (Kl...

2024
[7500]

These plots show that our method produces assignments comparable to exact algorithms (o-FSC,s-FSC)

235.62 (4.48) 88.99 (4.35)5.29(0.21) m-SMB (n= 10000) 495.70 (9.49) 107.94 (5.10)9.19(0.36) LastFMNet 103.82 (2.87) 19.08 (1.96)4.59(0.30) Thyroid 279.03 (4.21) 30.49 (3.17)7.38(0.16) Census - 136.60 (0.69)15.78(1.06) 4area - 166.92 (0.73)25.85(1.4) dataset (top) and the DS-57...

2019

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [6]

The results show that our algorithm outperforms the compared ones in terms of computational time for all tested sample sizes and cluster sizes

and s-FSC (Wang et al., 2023), is depicted in Figure 4 and reported for completeness in Table 6 here. The results show that our algorithm outperforms the compared ones in terms of computational time for all tested sample sizes and cluster sizes. These results indicate that our algorithm exhibits superior scalability as the data size and number of clusters...

work page 2023

[2] [10]

The affinity graphs for Thyroid, Census, and 4area are obtained by a radial basis function (RBF) kernel k(xi, xj) = exp(−γ∥x i −x j∥2), where γ= 1/d and γ= 1/d∗0.01 for the smaller Thyroid, with xi ∈R d, i= 1, . . . , n. We compare with the fastest available Fair SC algorithm, i.e., s-FSC from (Wang et al., 2023). Here, we report the complete results for ...

work page 2023

[3] [11]

by applying our faster algorithm to their learned graph. Other works on fair clustering include (Bera et al., 2019b; Backurs et al., 2019), which are not directly comparable to our work as they do not consider the spectral clustering objective. (Bera et al., 2019b) propose LP-based k-(means, median, center) clustering. Using their formulation in our work ...

work page 2019

[4] [12]

However, extending the fairlet analysis, which relies on the k-median and k-center cost of the fairlet decomposition, to the spectral setting is not trivial

use fairlets for prototype-based clustering. However, extending the fairlet analysis, which relies on the k-median and k-center cost of the fairlet decomposition, to the spectral setting is not trivial. SC involves a spectral embedding step followed by a clustering in the embedding space, where reassigning points within a fairlet can significantly alter t...

work page 2016

[5] [13]

17 Accelerating Spectral Clustering under Fairness Constraints To apply their result, we verify that four key assumptions hold, namely Assumption D.1, Assumption D.2, Assumption D.4 and Assumption D.5 that can be found in Magnusson et al. (2016). Assumption D.1.The functionsuandvare continuously differentiable. This is satisfied in our setting. Assumption...

work page 2016

[6] [14]

Since polynomial functions possess derivatives of all orders, each ψij is smooth (i.e., C ∞)

To establish smoothness, observe that each component ψij(x) is a quadratic polynomial in the elements of x. Since polynomial functions possess derivatives of all orders, each ψij is smooth (i.e., C ∞). Consequently, the vector-valued function ψ is smooth. Therefore, the orthogonality constraint on matrixAadmits a smooth representation. 18 Accelerating Spe...

work page 2016

[7] [15]

Therefore, the only linear combination of the gradients ∇xψij(¯x)that equals zero is the trivial one, which proves thatC(¯x)is linearly independent

This implies λij = 0 for all i, j. Therefore, the only linear combination of the gradients ∇xψij(¯x)that equals zero is the trivial one, which proves thatC(¯x)is linearly independent. Lemma D.7.Let F∈R n×h and H∈R n×k. Define z= vec(H)∈R nk and consider the constraint F ⊤H= 0 . Let θ(z) = vec(F ⊤H)∈R hk. The set of constraint gradients C(z) ={∇ zθi(z)|i= ...

work page 2023

[8] [16]

Proof of Proposition 3.2 Proof.Expandingϕ(M H)to recover the expression of the augmented Lagrangian shows thatH7→ϕ(M H)is convex as long asα <1

D.3. Proof of Proposition 3.2 Proof.Expandingϕ(M H)to recover the expression of the augmented Lagrangian shows thatH7→ϕ(M H)is convex as long asα <1. Then, following Proposition 3.1 from (Tonin et al., 2023), equivalently we can write the problem as inf H∈R n×k g(H)−sup V∈R n×k {⟨V, M H⟩ −ϕ∗(V)} = inf H∈R n×k g(H) + inf V∈R n×k {ϕ∗(V)− ⟨V, M H⟩}(30) = inf...

work page 2023