MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product

Q1:Undefined error rate in Sec 4.3

A1:Thank you for pointing this out. We agree that the evaluation metric in Section 4.3 should be clarified.

All experiments in Section 4.3 use Normalized Mean Squared Error (NMSE), as defined in Section 4.2, to measure reconstruction quality. Specifically, we:

• Compute the ground-truth distance matrix using pairwise Euclidean distances;
• Apply noise or masking to simulate degradation;
• Use NMSE to quantify both pre- and post-recovery error;
• Set missing entries to zero to ensure consistent NMSE calculation.

For example, in the M30 setting, NMSE drops from 35.50% (before recovery) to 13.85% (after), showing a clear performance gain.

Our method leverages the assumption that mildly corrupted metric-consistent matrices retain latent structure, and that enforcing metric constraints during recovery improves reconstruction accuracy.

Q2:Data handling ambiguity (Sec 4.4)

A2:Thank you for your comment. Section 4.4 demonstrates the online update capability of our method—an aspect largely overlooked in prior work.

We simulate an online setting where the model is incrementally updated as new data arrives, without access to future entries. Starting from a partially observed distance matrix (e.g., 20% revealed), we iteratively expose 20% new entries at each timestep. The model is updated using only these newly observed entries.

This setup respects causality and highlights our method’s ability to refine predictions progressively. Traditional convex optimization methods require full data access and incur high computational costs (e.g., $O(N^3)$), making them impractical for real-time updates.

In contrast, our method uses efficient, localized gradient-based updates via backpropagation, avoiding full retraining. As demonstrated in our experiments, this approach achieves 10×–1000× speedups over baseline methods while maintaining or improving accuracy. These properties make our method well-suited for real-time applications that demand continuous adaptation.

Q3:Error undefined, metric mismatch (Sec 4.6)

Thank you for your comment.

Regarding the evaluation metric in Section 4.6, we again adopt the Normalized Mean Squared Error (NMSE) to quantify how well the compressed representation preserves the original distances.

Regarding the assumption about metric nearness, we agree that the closest metric under a given norm is not necessarily of the same type as the one used to generate the original distances (e.g., Euclidean, cosine, etc.). However, the goal of this experiment is not to recover the exact generating metric, but rather to demonstrate that our method can serve as a general-purpose, low-rank, metric-preserving approximation of distance matrices. Specifically A fully specified distance matrix typically requires $O(n^2)$ parameters. Our method seeks to compress this representation to O(nk) parameters, while:

• (a) Guaranteeing that the reconstructed matrix satisfies the metric properties, and

• (b) Maintaining low computational complexity, suitable for large-scale applications.

Traditional methods such as SVD or spectral decomposition offer low-rank approximations but do not guarantee metric validity, and often incur $O(n^3)$ complexity. In contrast, our method can be viewed as a tropical analogue of SVD, which:

• Operates in a multiplication-free space,
• Enforces metric constraints by design,
• And achieves efficient approximation using only O(n·k) parameters. In this experiment, we evaluate performance in a controlled setting where the original distance matrices are generated using known distance functions . Our method does not assume knowledge of the underlying metric but still achieves high-fidelity reconstructions, as evidenced by low NMSE and strong performance in downstream tasks (e.g., 0.79 accuracy on the Cora dataset).

Q4:Uncovered case: bullet 3 violation (Sec 4.2)

A4：Thank you for your comment. We will revise Theorem 8 to clarify that satisfying both Bullet 2 and Bullet 3 implies the triangle inequality.

Our experiments deliberately use matrices with heavily violated metric properties—e.g., 99.7% of entries in the graph-t1 dataset ($N=1000$) violate Bullet 3.

Q5: Unnecessary Theorems 1–4

A5: Thank you. We agree that Theorems 1–4 are standard and will streamline or move them to the appendix to improve clarity without losing completeness.

Q6: Essential References Not Discussed

A6: Thank you for the suggestion. We have reviewed references [A–I] and will revise the related sections accordingly. Detailed updates will be provided in the next rebuttal stage.

Q7:PAF

For $N = 2000$, our method (Tropical) achieves an NMSE of 0.18 in 34s with 0 violations, while PAF yields a lower NMSE (0.068) but takes 3133.91s, produces 3.7e7 violations, and fails to converge—highlighting our method’s superior efficiency, and suitability for large-scale applications.

Q1：Please clarify whether the proposed training procedure for MetricEmbedding is guaranteed to achieve a plausible minimum and under which conditions.

A1：The short answer is no, because it is a non-convex optimization problem. Nevertheless, our algorithm is guaranteed to converge to a local minimum, as we solve the problem using a gradient descent approach.

We prove this by the following:

(1) consider one layer case， $\min_X \| X \odot_{\max} X^T - Y \|_F^2$ Let: $A = [[1,3,3],[3,1,3][3,3,1]], B = [[3,1,1][1,3,1][1,1,3]]$ Taking $\alpha = \frac{1}{2}$, then: f(\frac{1}{2}A + \frac{1}{2}B) > \frac{1}{2}f(A) + \frac{1}{2}f(B) This violates convexity, proving that even in a single-layer case, the problem is non-convex. (2) Now consider the general multi-layer formulation，We can instead set all parameters of the network to zero except for those in the first layer, keeping the form consistent with the one-layer result described above. Then the entire deep network reduces to the form $W_0$, and we recover exactly the same objective as in the single-layer case.

end of proof

Since global optima are hard to attain in non-convex problems, we instead focus on finding good local optima. Our approach achieves a balance between optimization space and efficiency.

The original problem is defined under standard metric constraints (triangle inequality and zero diagonals). Our method introduces a stricter condition (**Theorem 8 bullet point 3 **), which defines a narrower solution space we refer to as the tropical metric space.

While existing methods like HLWB optimize over the general metric space, our approach is more effective when the optimal solution lies close to this constrained space. However, we currently lack a formal proof of convergence.

To encourage convergence to good local minima, we adopt several practical strategies:

• Initialize outputs around the mean of the target matrix $D$, ensuring triangle inequality via a constructed matrix $M$.
• Add controlled randomness for better optimization dynamics.
• Use parallel optimization to avoid poor local minima, which significantly improves results.

Q2:Lack of evaluation on non-synthetic datasets makes it unclear how applicable the method is for real world applications.

A2: Thanks for your feedback. To address your concern about the real-world applicability of our method, we conducted additional experiments on the MNIST dataset and a real graph dataset.

To further validate our method for metric matrix recovery, we tested it on MNIST using two non-metric cases: noisy Euclidean distances following [1] and naturally non-metric cosine similarities following.

Noisy Euclidean Distance (MNIST)

Cosine Similarity Distance (MNIST)

Experiments on a Real Graph Dataset

To further validate the practicality of our approach, we applied MetricPlug (Section 3.3) to a real-world graph learning task.

Task Setup

We used graph contrastive learning (based on GRACE [2]) for node classification, replacing standard similarity metrics with MetricPlug using the tropical inner product.

Dataset and Baselines

We experimented on the Cora dataset (2,708 nodes), with train/val/test splits following GCN [3]. MetricPlug was compared against cosine, Hamming, Euclidean, and Manhattan distances.

Experimental Settings

We used PyG’s dropout_adj to perturb edges (ratio = 0.1) for data augmentation. Training was run for 1,000 epochs with a learning rate of 0.01 and 64-dimensional hidden/projection layers. Accuracy was used for evaluation.

Q1:but one can also easily optimize over multiple starting matrices A in parallel as another means of avoiding local minima.

A1:Thanks for your valuable suggestion. We conducted experiments using the proposed strategy with a single-layer model, and indeed observed further performance improvements over the baseline approach. In our experiments, we constructed a set of non-metric matrices using the MNIST dataset, following the approach described in [1]. We fixed the number of model iterations to 1000. Under this configuration: The convergence error improved from 0.0583 to 0.0536. The improved model required 3.58 seconds, compared to 0.97 seconds for the original method. This demonstrates a clear trade-off between convergence quality and computational cost.

Q2：I don't think I saw any evidence supporting the purported downstream task benefits of MetricPlug as proposed in section 3.3, specifically compared to existing approaches.

A2: We conducted additional experiments on real-world tasks to demonstrate the applicability of our approach, specifically MetricPlug as described in Section 3.3.

• Task Definition:
  We applied graph contrastive learning, an unsupervised method for learning node representations using contrastive loss. Specifically, we used the approach from GRACE [2], which involves perturbing edges to generate augmented views. Unlike traditional methods that use cosine or Euclidean similarity metrics, we replaced them with MetricPlug, which uses the tropical inner product to calculate node pair similarity, satisfying the triangle inequality. The evaluation task focuses on node classification.

• Dataset and Baseline:
  We used the Cora dataset, which contains 2708 nodes, and follows the standard data split used in GCN [3]. We compared our MetricPlug method with existing methods based on cosine, Hamming, Euclidean, and Manhattan distances.

• Experiment Settings:
  We utilized the dropout_adj function in PyG to randomly perturb edges with a perturbation ratio of 0.1 to generate augmented views. The configuration used a learning rate of 0.01, 1000 epochs, with hidden and projection dimensions set to 64. Accuracy was the evaluation metric. The results are summarized below:

As shown in the table, the MetricPlug method outperforms other distance-based methods, achieving the best results on both validation and test sets.

Q3：Can the miniabatch-based algorithm in appendix C.2 guarantee the triangle inequality property at a global scale across all pairs i,j? Or only up to its maximum output shape? The answer to the first question is affirmative.

Our proposed minibatch-based training method guarantees that, in any iteration, the model's predictions satisfy the triangle inequality for all index pairs $(i, j)$. Specifically, as long as the two matrices involved in the final Tropical inner product are constrained to be non-negative, the resulting matrix—obtained via Tropical inner product—will satisfy the triangle inequality for any pair $(i, j)$.

Although the minibatch algorithm only updates a subset of the model's weights based on the current batch, we explicitly enforce non-negativity constraints on all model parameters throughout training. As a result, regardless of the update stage, the forward pass of the model will always produce a full matrix $H$ whose entries satisfy the triangle inequality across all index pairs $(i, j)$.

For example, consider a $1000 \times 1000$ matrix with a batch size of 16. In a single iteration, the model only computes the values for those 16 selected positions and updates the weights based on the corresponding loss. However, since all weights remain non-negative due to the imposed constraints, the full $1000 \times 1000$ matrix outputted by the model at this point will still satisfy the triangle inequality for any pair $(i, j)$. This property is guaranteed by Theorem 6.

Other cases follow by the same reasoning.

Q4：Some of the math notation can be cleaned up a bit.

A4:Thank you very much for pointing out this issue. We will address and correct it in the subsequent version of the manuscript

[1] Li W, et al. Metric nearness made practical. AAAI2023

[2] Zhu, Y et al. Deep graph contrastive representation learning. ArXiv.

[3] Kipf, T. N et al. Semi-Supervised Classification with Graph Convolutional Networks. ICLR2016.