- 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 diverges at the boundaries. However, the optimization variable is . By the chain rule, this derivative is multiplied by , which also vanishes in these limits. So it seems worth checking explicitly whether the embedding gradient diverges.
Consider binary observed relations, , and let . For the kernel in Eq. (2) with fixed , a direct calculation gives the following. For a false-positive edge,
and for a false-negative non-edge,
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 .
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 , 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 , 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 to , 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 and each negative-pair gradient by , 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 , is large for typical sparse graphs; for example, when and . In this case,
uniformly over . The negative-pair loss is then almost linear in , 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
goes to zero as , so close negative pairs are suppressed most strongly. Near a collision,
while the cross-entropy gradient diverges as . This supports the idea of suppressing singular repulsion.
At the same time, the large default also weakens repulsion for all negative pairs, and 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 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 . Switching to 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 . Increasing 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 is bounded by , whereas the gradient of the negative-pair loss diverges as . 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 ?
2. Role of
Under the default , the negative-pair loss is nearly linear in (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 ? 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?
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