acceptodds
Withdrawn from ICLR 2027

Predictive Affinity Learning for Laplacian Eigenmaps

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

In many scientific studies, reducing high-dimensional measurements to a few coordinates simplifies prediction and visualization. Laplacian Eigenmaps construct coordinates from a neighborhood graph, but nuisance features can distort its distances and the standard eigenmap loss can favor almost disconnected graphs. In this article, we study how to learn a feature-weighted distance for Laplacian Eigenmaps using a predictive criterion. We propose predictive affinity learning, which predicts excluded features from neighbor averages and constructs spectral coordinates from the selected features. Theoretical results show that, under the stated identification and regularity conditions, the method removes independent nuisance features and its spectral representation converges to that of the population predictive distance, even when the same observations estimate the distance and construct the graph. The selected features persist under small departures from independence when the population criterion strictly separates the selected and excluded coordinates. Through simulations and multiview data analyses, we identify settings where the learned distance improves neighborhood recovery and prediction over isotropic eigenmaps.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Feature selection, Laplacian Eigenmaps, Metric learning, Multiview learning, Privileged information, Self-supervised learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_QkGdOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes PALE, a method that employs neighborhood-averaging predictions based on features excluded via masking, utilizing a doubly stochastic kernel, to learn feature-weighted distances for Laplacian Eigenmaps, incorporating ridge regularization into the prediction loss. After selecting features through thresholding, the method constructs spectral coordinates. The paper first demonstrates that the standard eigenmap loss can approach zero on nearly disconnected graphs, indicating that this loss is unsuitable as an objective for learning affinities. Subsequently, under an "independent nuisance" model, the authors prove that the population criterion drives nuisance weights toward their lower bounds. They also provide results concerning metric estimation, support recovery, and spectral convergence for a fixed dimensionality (allowing the same set of samples to be used for both distance estimation and graph construction). Empirical validation includes simulations on surfaces, tori, and spheres, as well as analyses of two molecular datasets: CITE-seq and PBMC data.

Critical strengths
  1. The results of Theorem 1 are clean and convincing: neither bi-random normalization, positive off-diagonal elements, nor forward entropy can prevent the eigenmap loss from going to zero. This provides a strict counterexample to "small spectral loss does not represent an informative representation". It is the most valuable conceptual contribution of the entire paper and also provides a real motivation for the predictive criterion.

  2. Consistent spectral convergence (Theorem 19 + Corollary 1) that allows simultaneous estimation of distance and composition for the same observation is technically non-trivial. Consistent coverage of a compact metric family avoids sample splitting. This "simultaneity" processing is rare in similar work.

  3. The optimization certification mechanism (branch-and-bound global target gap certificate, explicit accounting of numerical errors) rarely combines statistical theory with verifiable calculations. It is more rigorous than the usual practice of only reporting optimizer convergence information, and the reproducibility statement is also more complete.

Critical weaknesses
  1. The core theory holds only under a fixed feature dimension mm: the primary convergence and support recovery results require mm to be fixed, with b≫mlog⁡(mb)b \gg m \log(mb). In contrast, the simulations (such as the spherical experiment with m=192m=192 and N=4096N=4096) and the real-world data applications are inherently high-dimensional.

  2. The theoretical constants are vacuous for practical sample sizes: "Condition 1" requires bounded measurements and a value h/mh/\sqrt{m} that is bounded away from zero, with a kernel lower bound of k−=exp⁡(−2B2/(π−τ−2))k_- = \exp(-2B^2/(\pi_- \tau_-^2)). The authors themselves note that for surface/torus designs, k−k_- evaluates to e−100e^{-100} or e−100/3e^{-100/3}. Consequently, all error bounds are scaled by constants on the order of e100e^{100}.

  3. Empirical gains are marginal and inconsistent: The analysis includes only two real-world datasets, where the improvement in paired MSE over "isotropic LE" is negligible (0.0023). Moreover, as the authors themselves admit, "MLKR spectral" consistently outperforms PALE across both datasets and both dimensions.

Questions for authors
  1. In the spherical experiment with m=192m=192 and N=4096N=4096, how are the block size bb and the number of blocks RR chosen? Do they satisfy the condition mlog⁡(mb)/b→0m \log(mb)/b \to 0 as well as the growth conditions required by Theorem 8? If the experimental setup does not meet these theoretical prerequisites, do the paper’s guarantees regarding spectral convergence still apply?

  2. Given that MLKR consistently yields lower errors on the CITE-seq/PBMC dataset, what is the practical advantage of PALE over MLKR when the response view is available? Is there any empirical evidence from real-world datasets where PALE significantly outperforms other methods in a label-free setting?

  3. What are the typical number of iterations and the computational runtime required for the branch-and-bound procedure to obtain ηR\eta_R? Does this approach scale effectively with mm?

  4. Since the threshold tNt_N and the eigengap γp\gamma_p are interdependent and both require tuning, how can they be selected in a stable manner in practice? Given that spectral error is amplified by a factor of 1/γp1/\gamma_p, how do the authors address cases involving real-world data where γp\gamma_p is small?

2 comments
AuthorsOpenReview ↗

Response to Reviewer QkGd (2/2)

In the spherical experiment with m=192m=192 and N=4096N=4096, how are the block size bb and the number of blocks RR chosen? Do they satisfy the condition mlog⁡(mb)/b→0m \log(mb)/b \to 0 as well as the growth conditions required by Theorem 8? If the experimental setup does not meet these theoretical prerequisites, do the paper’s guarantees regarding spectral convergence still apply?

Thank you for this question, and we apologize that our block scaling was unclear. For b=2Nb=2\sqrt N, R=N/2R=\sqrt N/2, both growth conditions hold at fixed m=192m=192 as N→∞N\to\infty. Spectral bounds do not certify N=4096N=4096.

  1. With R=16R=16, b=64b=64 at N=1024N=1024 and R=32R=32, b=128b=128 at N=4096N=4096 (Appendix I.6, p. 105), mlog⁡(mb)/bm\log(mb)/b is 28.2528.25 and 15.1615.16 (large). In Theorem 8 (p. 35), log⁡(2m)/R+log⁡(2mb)/b\log(2m)/R+\log(2mb)/b is 0.5300.530 and 0.2700.270.
  2. Our guarantees are asymptotic without a finite-sample bound at N=4096N=4096. We recover support in 9999 and 100100 of 100100 data sets at N=1024N=1024 and N=4096N=4096, and spectral error decreases from 0.14480.1448 to 0.04660.0466 (Table 6, p. 106).

Given that MLKR consistently yields lower errors on the CITE-seq/PBMC dataset, what is the practical advantage of PALE over MLKR when the response view is available? Is there any empirical evidence from real-world datasets where PALE significantly outperforms other methods in a label-free setting?

  1. With VV, MLKR spectral has lower RNA test MSE at p∈5,10,20p\in\\{5,10,20\\} and selects no coordinates (Table 11, p. 109). Corollary 1 (p. 7) establishes spectral convergence for fixed dimension under its identification, manifold, eigengap, threshold, graph-rate, and optimization-error conditions. These conditions have not been verified for the molecular fits. In the response-view PBMC experiment, PALE retains 10.7110.71 of 1717 PBMC antibodies and excludes all three isotype controls in all fits (Appendix I.8, p. 108).
  2. Label-free protein-only PALE improves on isotropic LE. At dimension five, PALE minus development-selected Laplacian Score (LS) has mean MSE difference −0.002581-0.002581 in CBMC (paired 95% resampling interval [−0.003319,−0.001843][-0.003319,-0.001843] from fixed-cohort repartitioning, lower error in 83 of 100 partitions) and 0.0041350.004135 in PBMC ([0.003239,0.004952][0.003239,0.004952], favoring LS). Both LS rules have lower PBMC error at dimensions five and ten. RNA enters only the final readout, not the metric fit (Appendix AA.1, Table 31, pp. 181–182).

What are the typical number of iterations and the computational runtime required for the branch-and-bound procedure to obtain ηR\eta_R? Does this approach scale effectively with mm?

  1. On the sphere at n=4096n=4096 (Table 23, p. 161), Proposition 8 (p. 41) certifies the root without subdivision. Each fit uses 33 SLSQP iterations, 55 objective evaluations, and 0.19370.1937 seconds mean metric-stage time (untimed certificate included).
  2. At ρ=1/200\rho=1/200, Proposition 55 (p. 175) certifies local minima. Subdivision (1,131,5421{,}131{,}542 cells, 119.85119.85 minutes) leaves global gap bounds 0.4030.403 and 0.5800.580 above 10−310^{-3} (optimization errors in statistical comparison, Appendix Z.10, p. 179).
  3. On two fixed protein-only training fixtures (one per cohort), for the distinct ρ=49\rho=49 objective, Proposition 54 and Corollary 25 certify gaps 3.99×10−43.99\times10^{-4} and 8.64×10−48.64\times10^{-4} (all coordinates exceed threshold 0.520.52 and are retained), while ρ=1/200\rho=1/200 global 10−310^{-3}-tolerance certification is unresolved (Appendix AB, p. 182).
  4. After the one-box certificate succeeds, Proposition 17 (p. 52) gives polynomial dependence on mm for fixed candidate-set size ss, with a covering factor exponential in s−1s-1. Under the additional conditions of Theorem 18 (p. 69), projected gradient descent requires no subdivision.

Since the threshold tNt_N and the eigengap γp\gamma_p are interdependent and both require tuning, how can they be selected in a stable manner in practice? Given that spectral error is amplified by a factor of 1/γp1/\gamma_p, how do the authors address cases involving real-world data where γp\gamma_p is small?

  1. We select (tN,p)(t_N,p) by development error, while γp\gamma_p is a population eigengap. By Equation (8) (p. 4), each of at most mm supports has a fixed graph and minimizer set, and a positive empirical boundary eigengap gives a unique selected pp-dimensional subspace (Appendix W, p. 159).
  2. Development MSE selects p=20p=20 in all 100100 fits per cohort. Support at tN=0.49t_N=0.49 matches the default in 8686 CITE-seq and 8080 PBMC fits, and when support changes at tN=0.55t_N=0.55, mean subspace distance at p=20p=20 is 1.2781.278 and 1.1601.160 (Table 22, p. 160).
  3. At p=20p=20, median relative boundary gaps (0.0210.021, 0.0160.016) do not estimate γp\gamma_p (Appendix Q, p. 137). Proposition 49 selects p^=7\widehat p=7 in all 100100 PBMC fits. We do not interpret individual coordinates at small boundary eigengaps, and we recommend a fixed pp, or a stable p^\widehat p, with an identified basis before interpreting coordinates.
Reviewer_QkGdOpenReview ↗

review

Thank you for your rebuttal.

Given that the paper is extremely long, and I share the same concerns as reviewer HTYb, I have lowered my confidence score to 1; therefore, I am inclined to maintain my current rating.

Reviewer_n3wPOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors propose predictive affinity learning, which predicts excluded features using weighted neighbor averages and constructs spectral coordinates from the selected features. Under the stated assumptions, the theoretical results show that the method removes independent nuisance features and that its spectral representation converges to the representation induced by the population predictive distance. Simulations and multiview data analyses demonstrate settings in which the method improves neighborhood recovery and prediction over isotropic Laplacian Eigenmaps.

Critical strengths
  1. The paper learns affinities by predicting features excluded from the distance calculation, avoiding the nearly disconnected graph degeneracy that can arise from directly optimizing the eigenmap loss. This provides a principled criterion for assessing whether neighborhoods are informative.
  2. The paper connects feature selection and metric estimation to spectral convergence while allowing the same observations to be used for both metric learning and graph construction. This extends the contribution beyond empirical feature weighting and gives the method substantial statistical grounding.
  3. Extensive simulations, nonlinear prediction tasks, and real single-cell data analyses evaluate feature recovery, spectral error, and predictive performance, providing evidence of the method’s practical value.
Critical weaknesses
  1. The method evaluates features through their ability to predict held-out measurements. However, correlated noise or batch effects may also be predictive, while useful signals unique to individual features may offer little predictive value for other measurements. This raises questions about whether the criterion reliably distinguishes informative structure from nuisance variation.
  2. Equation (5) performs prediction using a Gaussian kernel and a bistochastic affinity matrix, whereas the final representation uses a local nearest-neighbor graph built from the thresholded metric in Eqs. (8)–(9). Consequently, the metric optimized for prediction may not be optimal for the final graph. The connection between these two stages needs further explanation.
  3. In Table 21, PALE reduces held-out pixel prediction error but achieves lower classification accuracy than isotropic LE. This shows that improved prediction does not necessarily yield a more useful downstream representation, limiting the case for this criterion as a general-purpose dimensionality reduction objective.
Questions for authors

Please see the weaknesses.

2 comments

The authors have substantively addressed all three of my concerns by acknowledging the limitations and delineating the supported regimes, rather than fully resolving the issues. Since the concerns themselves remain valid, I maintain my score.

Thank you for reading our response and for your positive assessment of our work. We agree with your summary. The three points are limits on the scope of a label-free predictive criterion. The revision states them through an explicit counterexample (Proposition 51, p. 154) and the handwritten-digits comparison (Table 21, p. 148), and Proposition 7 (p. 39) gives an upper bound that links the predictive risk to the final spectral approximation error for a prespecified response. These limits do not change the guarantees for independent nuisance features (Corollary 1, p. 7, and Proposition 25, p. 57) or for a prespecified response view (Proposition 1, p. 5). We sincerely appreciate your time and valuable comments.

Reviewer_HTYbOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper introduces PALE, a method for unsupervised feature selection and scaling prior to spectral embedding (aka Laplacian eigenmaps).

Critical strengths

The basic idea behind the method may have some merit

Critical weaknesses
  • The paper is unreadable and the presentation is not thought out. For example the headline caption of Figure 1 makes no attempt at explaining anything despite the abundance of space on the same page. Algorithm 1's description is very hard to decipher due to the large number of eqrefs. etc.

  • Baselines are not properly described and not properly motivated. For example, what is SLAPS-DAE? The paper gives a one-line high-level description in line 419 with no details and no description of hyperparameter selection. Appendix I.2 on page 100 (!) which is not refered to from the text (!!) provides more details on this. It turns out that SLAPS-DAE is a homegrown variant by the authors. The authors do not explain why they had to invent their own method instead of using an established baseline, nor do they explain why it is a reasonable choice for a baseline. It would have been much better to use established methods for feature selection and metric learning.

Questions for authors

I do not believe that there are any questions whose answers would change my assessment of the paper.

Reviewer_6Aj2OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the problem of irrelevant features interfering with the construction of neighborhood graphs. Therefore, the authors propose using prediction errors to learn feature weights by predicting masked features or pre-specified response views, and then filtering the features to construct a spectral representation. The authors conduct a theoretical analysis of metric estimation errors, spectral representation convergence, and other related topics. They also conduct relevant experiments and evaluation using synthetic and molecular data.

Critical strengths

The main advantage is that the research addresses a meaningful problem: it uses cross-feature prediction to evaluate affinities, thereby avoiding the direct involvement of the predicted feature in distance calculations. The theoretical analysis is quite comprehensive, linking metric estimation, support recovery, and spectral representation errors. In particular, this analysis allows the same set of observations to be used simultaneously for metric estimation and graph construction. The experiments are transparent, including ablation tests, relevant baseline comparisons, and some negative results.

Critical weaknesses

One concern is that the method involves multiple design components, including predictive metric estimation, symmetric bistochastic scaling, and feature selection. Although the authors provide relevant ablation experiments, the additional benefits of some of these components are not sufficiently clear. For example, in comparative experiments on CITE-seq data, there was insufficient statistical evidence to suggest a difference in predictive performance between symmetric bistochastic scaling and standard row normalization. In several experimental settings, the performance of feature removal is quite similar to that of retaining all fitted weights.

The authors provide theoretical conditions for the feature selection threshold. However, in practical applications, we usually do not know the active-weight separation or estimation errors; therefore, it remains unclear how to select the threshold for removing low-weight features in real-world data. Furthermore, it is unclear whether the selected feature set and the final representation remain stable if the threshold is appropriately adjusted higher or lower.

Questions for authors

One concern is that the method involves multiple design components, including predictive metric estimation, symmetric bistochastic scaling, and feature selection. Although the authors provide relevant ablation experiments, the additional benefits of some of these components are not sufficiently clear. For example, in comparative experiments on CITE-seq data, there was insufficient statistical evidence to suggest a difference in predictive performance between symmetric symmetric bistochastic scaling and standard row normalization. In several experimental settings, the performance of feature removal is quite similar to that of retaining all fitted weights.

The authors provide theoretical conditions for the feature selection threshold. However, in practical applications, we usually do not know the active-weight separation or estimation errors; therefore, it remains unclear how to select the threshold for removing low-weight features in real-world data. Furthermore, it is unclear whether the selected feature set and the final representation remain stable if the threshold is appropriately adjusted higher or lower.

I recommend that the authors further clarify the respective roles of these design elements and specify the advantages they offer in terms of predictive performance, theoretical guarantees, interpretability, or computational efficiency.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.