acceptodds
Under review as a conference paper at ICLR 2027

RobustVis: High-Dimensional Data Visualization from Sparse Similarity Graphs with Uncertain Non-edges

Abstract

Neighborhood-graph-based high-dimensional data visualization methods depend on pairwise relations that are inevitably imperfect. Under conventional cross-entropy objectives, a single false-positive edge or false-negative non-edge can have unbounded loss and gradient influence near the boundary of the low-dimensional affinity. We introduce RobustVis, a bounded-influence optimization framework for high-dimensional data visualization. Its asymmetric positive- and negative-pair losses place robustness parameters inside the logarithms, uniformly bounding pairwise losses and derivatives while retaining strong attraction for trusted edges. We establish perturbation bounds for both the objective and the embedding gradient under graph corruption, and derive an importance-weighted negative-pair estimator for scalable optimization. Moreover, we develop an extension for RobustVis that can effectively account for uncertainty in positive edges. Experiments on synthetic manifold data and diverse real datasets demonstrate the effectiveness of the proposed methods in comparison to strong baselines.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Dimentionality Reduction, Data Visualization, Sparse Graph

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_VBJMOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes RobustVis, a high-dimensional data visualization method designed to be robust to errors in sparse neighborhood graphs. The authors point out that conventional cross-entropy-based objectives can have unbounded losses and derivatives with respect to low-dimensional affinities when false-positive or false-negative neighborhood relations are present.

To address this issue, the authors introduce an asymmetric loss function that bounds the influence of individual pairwise relations. They also provide theoretical bounds on objective and gradient perturbations, develop an importance-weighted negative sampling scheme that preserves the original objective and its gradient in expectation, and propose confidence-weighted extensions for positive edges.

The proposed methods are evaluated on synthetic manifold datasets, 13 real-world datasets, and five graph datasets. The experiments compare RobustVis with existing dimensionality reduction and graph visualization methods in terms of embedding quality, downstream task performance, sensitivity to neighborhood size, and computational efficiency.

Critical strengths

The paper addresses the practical problem of imperfect neighborhood graphs in high-dimensional visualization. The proposed bounded-influence objective is simple and mathematically well motivated. The theoretical analysis of objective and gradient perturbations provides a useful perspective on how errors in pairwise relations affect the optimization objective. The unbiased negative sampling scheme also makes the proposed objective computationally practical.

The authors evaluate their approach on a broad range of synthetic and real-world datasets and compare it against several established methods. The results indicate that RobustVis can achieve competitive visualization quality and strong downstream task performance. In particular, the confidence-weighted variant RobustVis-BR performs well on classification and clustering metrics, and the graph visualization experiments also show promising computational efficiency.

Critical weaknesses

I find the proposed objective interesting, and the bounds established for RobustVis appear sound. My main question is whether the reported improvements come specifically from the bounded-influence mechanism. I think the comparison with cross-entropy could be stated more precisely, and it would help to separate two effects in the experiments: suppressing singular gradients, and changing the attraction–repulsion balance.

1. Affinity derivatives versus embedding gradients

Section 3.2 shows that the derivative of the cross-entropy loss with respect to AijA_{ij} diverges at the boundaries. However, the optimization variable is Z\mathbf{Z}. By the chain rule, this derivative is multiplied by ∇ZAij\nabla_{\mathbf{Z}}A_{ij}, which also vanishes in these limits. So it seems worth checking explicitly whether the embedding gradient diverges.

Consider binary observed relations, Sij∈{0,1}S_{ij}\in\lbrace 0,1\rbrace, and let rij=∥zi−zj∥2r_{ij}=\Vert\mathbf{z}_i-\mathbf{z}_j\Vert_2. For the kernel in Eq. (2) with fixed σ>0\sigma>0, a direct calculation gives the following. For a false-positive edge,

∥∇zi[−log⁡Aij]∥2=(l+1)rijσ2+rij2≤l+12σ,\Vert\nabla_{\mathbf{z}_i}[-\log A_{ij}]\Vert_2 = \frac{(l+1)r_{ij}}{\sigma^2+r_{ij}^2} \leq \frac{l+1}{2\sigma},

and for a false-negative non-edge,

∥∇zi[−log⁡(1−Aij)]∥2∼2rijas rij→0.\Vert\nabla_{\mathbf{z}_i}[-\log(1-A_{ij})]\Vert_2 \sim \frac{2}{r_{ij}} \quad\text{as } r_{ij}\to 0.

In other words, the gradient of the positive loss term is uniformly bounded, while the negative loss term is singular only when two points collide. The attraction from a distant false-positive edge even decays as (l+1)/rij(l+1)/r_{ij}.

For this reason, it would be helpful if the discussion after Theorem 3.1 distinguished between the objective and the gradient. For a false-positive edge with Aij→0A_{ij}\to 0, the cross-entropy objective discrepancy diverges, but the gradient perturbation stays bounded. To be fair, this does not give a global bound for cross-entropy: the gradient difference can still diverge as Aij→1A_{ij}\to 1, even for a false-positive label flip.

So, for distant false-positive edges, the main effect of the proposed loss seems to be a faster decay of attraction, from O(rij−1)O(r_{ij}^{-1}) to O(rij−(l+2))O(r_{ij}^{-(l+2)}), rather than turning an unbounded gradient into a bounded one. Clarifying this would make the motivation more precise, and it would not affect the validity of the bounds for RobustVis.

2. Two effects of the robust loss

For binary observed relations, the robust loss multiplies each positive-pair gradient by Aij/(Aij+α)A_{ij}/(A_{ij}+\alpha) and each negative-pair gradient by (1−Aij)/(1−Aij+β)(1-A_{ij})/(1-A_{ij}+\beta), compared with cross-entropy. These factors apply to all pairs, whether the relation is correct or not. (For fractional positive affinities, Eq. (7) has both attractive and repulsive terms, so the positive-pair factor does not describe the whole gradient.)

The negative-pair term is especially interesting. With the default β=2n/K\beta=2n/K, β\beta is large for typical sparse graphs; for example, β≈1333\beta\approx 1333 when n=104n=10^4 and K=15K=15. In this case,

ℓij−=−log⁡(1+β)+Aij1+β+O(β−2),\ell^-_{ij} = -\log(1+\beta) + \frac{A_{ij}}{1+\beta} + O(\beta^{-2}),

uniformly over Aij∈[0,1]A_{ij}\in[0,1]. The negative-pair loss is then almost linear in AijA_{ij}, and its derivative changes by less than 0.1% over this interval in the example above.

This is not simply a uniform rescaling of cross-entropy repulsion. The relative factor

1−Aij1−Aij+β\frac{1-A_{ij}}{1-A_{ij}+\beta}

goes to zero as Aij→1A_{ij}\to 1, so close negative pairs are suppressed most strongly. Near a collision,

∥∇ziℓij−∥2∼l+1βσ2rij,\Vert\nabla_{\mathbf{z}_i}\ell^-_{ij}\Vert_2 \sim \frac{l+1}{\beta\sigma^2}r_{ij},

while the cross-entropy gradient diverges as 2/rij2/r_{ij}. This supports the idea of suppressing singular repulsion.

At the same time, the large default β\beta also weakens repulsion for all negative pairs, and α\alpha changes attraction. So the proposed objective changes both the behavior near the boundaries and the overall attraction–repulsion balance. The improvements could come from either effect, or from both, and it would be valuable to see their contributions separated.

3. Separating these effects in the experiments

Two comparisons would help clarify the mechanism.

The first is a controlled ablation. Section 4.1 uses RobustVis w/o LRV\mathcal{L}_{\mathrm{RV}} to show that the gain comes from the robust loss rather than the binary graph. However, this baseline uses the effective UMAP objective in Eq. (5), which has its own repulsive weight m(di+dj)/(2n)m(d_i+d_j)/(2n). Switching to LRV\mathcal{L}_{\mathrm{RV}} changes both the form of the losses and their weighting. This comparison shows the benefit of the new objective as a whole, but not the contribution of bounded influence alone.

The second is an evaluation under controlled graph corruption. The main-text experiments cover visualization quality, downstream performance, and sensitivity to KK. Increasing KK may add short-circuit edges on Swiss Roll, but it does not control false-positive and false-negative relations separately, and it also changes the neighborhood scale.

The paper mentions robustness experiments in Appendix F. Since robustness to graph errors is the central motivation, a short quantitative summary of these results in the main text would be very helpful, together with controls that separate robustness from a different attraction–repulsion balance.

Suggested experiments. I think the following comparisons would make the paper more convincing:

(a) cross-entropy with a tuned attraction–repulsion weighting, using the same graph, kernel, initialization, negative-pair sampling and importance correction in Eq. (13), and optimization settings as RobustVis;

(b) cross-entropy with clipping applied to each pair’s gradient with respect to the embedding coordinates, with its weighting and clipping threshold also tuned;

(c) experiments that separately add false-positive edges and remove true edges at controlled rates, reporting both absolute performance and degradation relative to the uncorrupted graph.

These comparisons would show whether RobustVis offers robustness beyond what can be achieved by adjusting the attraction–repulsion balance. The comparison with gradient clipping would also show the benefit of the proposed loss over another way of bounding pairwise gradients. Of course, outperforming clipping alone would not prove that boundedness fully explains the improvement.

Questions for authors

1. Embedding gradients under false-positive and false-negative relations

As discussed in Weakness 1, for the kernel in Eq. (2), the gradient of the cross-entropy positive-pair loss with respect to zi\mathbf{z}_i is bounded by (l+1)/(2σ)(l+1)/(2\sigma), whereas the gradient of the negative-pair loss diverges as rij→0r_{ij}\to 0. Do the authors agree with this analysis? If so, could they revise the motivation in Section 3.2 and the remark after Theorem 3.1 to distinguish between objective and gradient sensitivity, and to clarify in which regimes each type of graph error leads to unbounded gradients during the optimization of Z\mathbf{Z}?

2. Role of β\beta

Under the default β=2n/K\beta=2n/K, the negative-pair loss is nearly linear in AijA_{ij} (Weakness 2). Compared with cross-entropy, this suppresses close negative pairs most strongly, but it also weakens repulsion for all negative pairs. How do the results change for smaller values of β\beta? If such results are already included in the hyperparameter study in Appendix E, a short summary would be helpful. In addition, how does the effective ratio of repulsion to attraction in RobustVis compare with that of UMAP's effective objective in Eq. (5)?

3. Isolating the benefit of the bounded-influence objective

Could the authors provide a comparison that separates bounded influence from changes in the attraction–repulsion balance? Specifically, I would suggest comparing RobustVis with (a) cross-entropy with a tuned attraction–repulsion weighting, and (b) cross-entropy with clipping applied to each pair's gradient with respect to the embedding coordinates, with its weighting and clipping threshold also tuned. It would be ideal to keep the graph, kernel, initialization, negative-pair sampling and importance correction in Eq. (13), and optimization settings identical across all three.

4. Robustness to controlled graph corruption

Could the authors include a direct evaluation of robustness to graph errors in the main text, for example as a summary of Appendix F? On synthetic manifold datasets, ground-truth neighborhood relations can be defined from the latent coordinates. Starting from such a reference graph, one could add false-positive edges or remove true edges at gradually increasing rates, treating the two types of corruption separately. It would be helpful to report both absolute performance and degradation relative to the uncorrupted graph, for RobustVis, the baselines (a) and (b) above, and the other methods. Given the analysis in Question 1, one might expect the benefit of RobustVis to come mainly from false-negative non-edges. Does the experiment confirm this, or does RobustVis also help substantially against false-positive edges?

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

This manuscript presents RobustVis, a high-dimensional data visualization method for unreliable sparse similarity graphs. It introduces asymmetric robustness parameters inside the positive- and negative-pair logarithmic losses to limit the influence of erroneous relations, and uses importance-corrected negative sampling for scalable optimization. It also introduces confidence-weighted extensions based on UMAP fuzzy memberships and bidirectional neighbor ranks. Experiments cover synthetic manifolds, 13 real-world datasets, and five naturally occurring graphs.

Critical strengths
  1. This manuscript addresses a practically important stability issue caused by unreliable graphs, broadening the applicability of projection methods in complex scenarios such as high-dimensional and noisy data.

  2. The core objective has explicit theoretical support. The manuscript analyzes bounded pairwise losses and affinity derivatives, establishes objective- and gradient-perturbation bounds at a fixed embedding, and proves the unbiasedness of the negative-sampling estimator. These results help explain the method’s design and the scope of its guarantees.

Critical weaknesses
  1. The technical novelty needs clearer positioning. Several ingredients of RobustVis overlap with existing practice. For example, UMAP-style optimization uses gradient clipping to limit divergence, and negative sampling is already used for scalability. The manuscript should explicitly distinguish RobustVis from these mechanisms and state their respective advantages. Without such a discussion, these elements cannot be claimed as contributions.

  2. The composite score lacks sufficient justification. The composite score averages Trustworthiness, Continuity, 1−Procrustes error, 1−Stress, and Spearman correlation as a composite score. However, the first two metrics evaluate local preservation relative to the observed input geometry, whereas the other three evaluate recovery relative to latent ground truth. These metrics do not assess the same objective and are therefore unsuitable for aggregation; otherwise, the resulting composite score lacks meaningful interpretation. Moreover, Trustworthiness and Continuity often saturate at high values with compressed variance, so equal averaging may underweight them and obscure trade-offs.

  3. The robustness ablations do not sufficiently isolate the sources of improvement. Appendix F already compares robust and cross-entropy losses on Swiss Roll and COIL20 under different edge addition, edge removal, and sampling budgets. However, it does not separately test the independent effects of the bounded-loss constraints, confidence weighting, and sampling correction.Ablations of these components across multiple datasets and perturbation strengths are needed.

  4. The interpretation of Figure 2 is questionable. The authors claim that RobustVis and RobustVis-BR preserve width variation corresponding to an approximately threefold density difference along the two ends of the Swiss Roll. It is not clear that this is a desirable property: users may not infer width as density, and preserving such variation could mislead rather than inform.

Questions for authors

No Questions

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

This paper addresses imperfect neighborhood graphs by adding asymmetric offsets inside the log attraction and repulsoin losses, bounding pairwise losses and affinity derivatives. The authors are able to establish perturbation bounds for the objective and for the embedding gradient, and they derive an importance-weighted negative-pair estimator for scalable optimization. Experiments demonstrate effectiveness of the proposed mehtod with synthetic and real datasets.

Critical strengths
  • solid theoretical analysis of the objective, with explicit perturbation bounds and unbiased sampling providing a clear analytical foundation.
  • comprehensive evaluation that incudes controlled loss ablations and sensitivity analyses.
Critical weaknesses
  • in general the experiments are focused on metrics of class separability rather than visualization quality. It is not clear whether the generated visualizations are more useful than the alternatives in reality (it's hard to tell from Figure 4 which visualization is "better").
  • the ablation study supports the usefulness of the complete objective of RobustVis, but the evidence that the benefit comes from bounded influence specifically, rather than changes in attraction–repulsion weighting, is weaker.
Questions for authors

Can you compare against cross-entropy with independently tuned attraction-repulsion weights, identical importance correction, and matched optimization budgets? This is important to distinguish how much the improvement overall comes from bounded influence itself.

Comments on the paper

1 comment

Dear Reviewers,

Thank you again for reviewing our paper and for your valable suggestions regarding the experiments. We have provided the corresponding experimental results to show the superiority of the proposed robust loss over the cross-entropy with tuned weight or clipping. We look forward to your feedback.

Regards, Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.