Quantile-Calibrated Multi-Scale Spectral Regularizer
Implementation & benchmark of arXiv:2608.08704 — Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery
Source paper: Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery arXiv:2608.08704 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Build several Gaussian similarity matrices on minibatch embeddings, using empirical distance quantiles as their bandwidths, then combine them before degree normalization and spectral embedding. Add a regularizer that encourages the resulting row-normalized spectral coordinates to form compact pseudo-clusters, making the representation robust to multiple geometric scales rather than one manually tuned temperature.
Formulas
Mathematical statement
For embeddings z_1,...,z_B in R^d, define r_{ij}=||z_i-z_j||_2^2 for i not equal to j. Let q_m be the empirical alpha_m-quantile of the upper-triangular distances {r_{ij}:i<j}, where 0<alpha_1<...<alpha_M<1, and set h_m^2=q_m+epsilon. The multi-kernel similarities are K^{(m)}_{ij}=exp(-r_{ij}/(2h_m^2)), with zero diagonal. Aggregate K=sum_m w_m K^{(m)}, where w_m are nonnegative and sum to one. Define D=diag(K 1) and the normalized similarity operator S=D^{-1/2} K D^{-1/2}. If U contains the top k eigenvectors of S, row-normalize them as Y_{i:}=U_{i:}/(||U_{i:}||_2+epsilon). The paper's useful mathematical mechanism is row-wise control of Y: preserving each row's location supports accurate point-level clustering more directly than only bounding a global eigenspace distance. In the neural adaptation, use a stop-gradient pseudo-label matrix P from k-means on Y and centroids H, with spectral loss L_spec=(1/B) min_{P,H} ||Y-PH||_F^2. Quantile selection is non-differentiable and should be treated as an adaptive estimator, while gradients can flow through the kernels and optionally through the eigensolver.
Implementation notes
(1) Integrate the method after the encoder and before the projection head in a self-supervised image representation learner. For each minibatch, obtain embeddings z with shape B by d and L2-normalize them. Compute the pairwise squared-distance matrix R, use three quantiles alpha=(0.1,0.5,0.9), and combine the three kernels with equal weights. Maintain an exponential moving average of each bandwidth so minibatch noise does not destabilize training. (2) Pseudocode: z=normalize(encoder(x)); R=squared_distances(z,z); q[m]=quantile(R[off_diagonal],alpha[m]); h[m]=beta*h[m]+(1-beta)*(q[m]+eps); K=sum(exp(-R/(2*h[m]*h[m])) for m); K.fill_diagonal(0); d=K.sum(-1)+eps; S=K/sqrt(d[:,None]*d[None,:]); eigvals,U=top_eigenvectors(S,k); Y=U/(row_norm(U)+eps); labels=stop_gradient(kmeans(Y,k)); loss_spec=mean(sum((Y-centroid[labels])**2)); loss=loss_base+lambda*loss_spec. Run the spectral branch every 10 optimizer steps initially and detach U if eigendecomposition gradients are unstable. (3) The paper supplies the kernel aggregation, quantile bandwidth rule, degree normalization, and spectral coordinates. Estimate k, lambda, EMA decay beta, and pseudo-label reliability empirically. (4) First test: compare SimCLR with a single median-bandwidth kernel against this three-scale method on CIFAR-10 using ResNet-18, equal batch size and training FLOPs. Measure linear-probe accuracy, nearest-neighbor accuracy, ARI/NMI of embeddings, and sensitivity to a tenfold temperature change. On a synthetic mixture with clusters of different variances, success means higher recovery accuracy and lower dependence on the chosen temperature.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.