Neighbor-aware Geodesic Transportation for Neighborhood Refinery

1. More Explanation to the MNE Module

Manifold learning assumes that high-dimensional data lies on a lower-dimensional manifold. The goal is to learn this manifold's structure to perform tasks like retrieval while respecting the data's intrinsic geometry. In machine learning, particularly in manifold learning, graphs are used to represent the manifold. Each node in the graph represents a data point, and edges represent pairwise similarities or affinities between data points. Manifold-aware Neighbor Encoding (MNE) strategy uses this graph representation to capture local neighborhoods and propagates information across the graph to reveal the global structure. Specifically, MNE introduces a novel bidirectional smoothness criterion as a regularization term, ensuring that the learned similarities are smooth across the manifold and helping maintain its local structure in the learned representations. The visualization result in Figure 6 highlights that after encoding into the new manifold space, the features exhibit improved manifold properties, which contribute to enhanced retrieval performance.

2. Notation Issues

In line 258, we aim to define a simple diagonal matrix where each diagonal entry is 1. To formalize this, we utilize the delta function, defined as $\delta(i-j)=1$ when $i=j$, and $\delta(i-j)=0$ when $i\neq j$. These two cost matrices can take the same values, but as mentioned in Section 3.2, designing them separately can yield better results. In the revised manuscript, we have refined this definition to improve clarity and the overall readability.

3. Dataset Information

Thanks for your advice. We have provided detailed information about the datasets used and summarized this information in Table 19 of the revised version.

4. Effect of Parameter $k_1$

In our approach, we involve the parameter $k_1$ to determine the activation item for the manifold-aware encoding. The effect of $k_1$ is exhibit in Figure 4. The peak performance is achieved when $k_1$ is around 50, but the performance does not largely vary when $k_1$ exceed 20. The outliers would unavoidably involved in the encoding procedure when $k_1$ increases, but the bidirectional similarity diffusion strategy successfully mitigate their influence, such that the retrieval performance can exhibit a robustness in a wide range. Moreover, we also compare it with the traditional method using the same value in constructing the affinity graph for diffusion, further validate the effectiveness of our manifold-aware neighbor encoding strategy.

5. Mistake Highlight

Sorry for the mistake, we have already corrected it in the revised version.

6. More Explanation on the Influence of Outliers

Actually, to prove that our method can effectively reduce the negative influence of outliers, we involve the purity metric to observe the accuracy of true samples in the top-k neighborhood shown in Figure 2, the higher purity represents the more outliers being excluded. Moreover, the retrieval performance which is measured by mean average accuracy metric, quantitatively reflect the ability of reducing the negative impact of outliers in neighborhoods. For the visual explanation, we select some instances and exhibit the corresponding weight for constructing manifold-aware neighbor encoding in Figure 5 and provide a t-SNE visualization of MNE feature space in Figure 6. The comparison validates the effectiveness of MNE in strengthening clustering performance and mitigating the effect of outliers. Please refer to the revised version in appendix for more details.

1. Lack of Novelty

The Neighbor-aware Geodesic Transportation (NGT) introduces unique innovations by systematically combining Manifold-aware Neighbor Encoding (MNE), Regularized Barycenter Refinery (RBR), and Geodesic Transportation (GT) to address the challenges of neighborhood refinery. Specifically, MNE innovatively encodes global manifold relationships using a bidirectional diffusion process to overcome the limitations of local-only methods. RBR incorporates a Wasserstein distance term for robust neighbor integration, mitigating the influence of outliers in a novel way. GT introduces geodesic path-based transportation, integrating global geometric and contextual information for refined distance computation. These components represent novel contributions within the context of deep clustering and image retrieval, enabling a systematic framework that advances the state of the art.

2. Complexity and Computational Cost

We acknowledge the computational complexity associated with our approach. However:

• We provide a detailed time complexity analysis (Section 4.3 of the paper), demonstrating that the $\mathcal{O}(n^3)$ complexity of NGT aligns with previously proposed context-based and diffusion-based methods.
• Our method is computationally efficient in practice due to the adoption of iterative optimization strategies and parallelization (e.g., Sinkhorn-Knopp iterations for GT). As shown in Figure 7 and 8, the iterations involved in our methods converge within a few epochs.
• As noted in Table 6, NGT achieves competitive re-ranking latency on large-scale datasets. Moreover, the coarse-to-fine strategy (explained in Section 4.3) further reduces computational burden for large-scale applications. Thus, the observed computational cost is a justified trade-off for the significant performance improvements achieved across diverse datasets.

3. Limited Scope

While the current work focuses on image retrieval and deep clustering, the core methodology of NGT—manifold encoding, robust barycenter computation, and geodesic transportation—offers generalizable components. Potential applications include: graph-based machine learning tasks, contextual similarity refinement in natural language processing and geometric-aware embedding learning in other domains. We appreciate this feedback and have outlined future work in the conclusion section to explore these broader applications.

4. Incremental Improvement

We respectfully disagree with this assessment. The improvements achieved by NGT are substantial and consistent across multiple benchmarks. For deep clustering, NGT demonstrates a 7.8% improvement in NMI on CIFAR-10 compared to BYOL and outperforms state-of-the-art contrastive and non-contrastive methods (Table 4). For image retrieval, NGT achieves 5.7% and 9.8% higher mAP on ROxf(M) and ROxf(H) compared to the most related ConAff with image feature extracted by R-GeM, highlighting its transformative impact (Tables 1–3). In the appendix (Table 11, 12), we further incorporate NGT with different image retrieval models. These results validate that the proposed framework offers a significant leap in performance, especially considering its robustness to outliers and enhanced neighbor relationships.

Thanks for your carefully review. To address your concern, here we provide some further explanations below.

1. Complexity and Computational Cost

In our proposed NGT, we modularized our neighborhood refinery method into three distinct modules: Manifold-aware Neighbor Encoding, Regularized Barycenter Refinery and Geodesic Transportation. This modular design not only reduces the implementation difficulty, but also facilitates easy adaptation to different tasks. Moreover, the performance of our algorithm is robust to variations in most parameters, enabling optimal results with minimal fine-tuning. In terms of time complexity, the theoretical complexity $\mathcal{O}(n^3)$ of our method remains consistent with previous approaches. We have also implemented extensive optimizations, including parallelization of key processes, which significantly reduce execution time. As a result, our algorithm achieves lower deployment latency compared to most existing methods and can seamlessly integrate into self-supervised learning frameworks. For large-scale datasets, our current strategy focuses on refining the top-ranked sequences, which has been proven to be effective in handling real-world scenarios.

Nevertheless, recalculating the optimal transport distance for each pair of samples leads to substantial computational overhead. To address this, we will focus on developing approximation techniques to further reduce time complexity while maintaining performance in our future work.

2. Overall Description and Presentation Issue

Thanks for your valuable advice, we have placed a brief description of the overall algorithm in the beginning of Section 3 and provided some visual explanations in appendix. And we will further improve our writing for clear readability.

3. Notation Issue

In Eq.(6), our initial intention is to present a basic objective function to define the regularized barycenter $a$, with its derivation detailed in Appendix B. To maintain simplicity and consistency with the appendix, we initially omitted subscripts in this definition. While in the subsequent Eq.(7), we modify the formula and introduce subscripts to assign a barycenter $a_i$ to each image. We apologize for any potential confusion caused by the similar notation. In the revised version, we have consistently included subscripts throughout the main text to ensure clarity and improve the overall readability.

4. Caption Mistake

Thanks! We have already fixed this issue.

5. Analysis of $\theta$ in GT

Here we replace $\theta=0.05$ with $\theta=0$ and introduce additional comparison intervals with a step size of 0.1. When theta recede to 0,performance is evaluated solely based on the optimal transport distance. Conversely, $\theta=1.0$ represents the case where only the Euclidean distance is used. Since our distance calculation is conducted in an unsupervised manner, it may misclassify individual points as samples from different categories, assigning them larger distances. In contrast, the original Euclidean distance exhibits higher accuracy in distinguishing closely related samples. Through linearly combining these two distance metrics, we can further refine the optimal transport distance to achieve superior performance.

1. Limited Novelty in Techniques and Mapping to Nonlinear Space

We would like to clarify that our Manifold-aware Neighbor Encoding (MNE) strategy is a novel and effective approach in mapping original image feature into a nonlinear space, which can encode the essential global and local relationships within the data manifold. Specifically, the Gaussian kernel used in MNE is tailored to capture the global structure of the manifold by leveraging a bidirectional similarity diffusion process. This ensures that pairwise relationships are iteratively refined to reflect the intrinsic data geometry, addressing the shortcomings of standard similarity measures. Additionally, the k-reciprocal neighbor search (Eq. 3) is designed to guarantee robust and consistent neighborhood definitions, which are crucial for the refinement process in tasks such as re-ranking and deep clustering. These elements form the foundation of a unique encoding framework that systematically captures both local and global dependencies in a way that directly benefits neighborhood refinery tasks. In Figure 6, we employ a t-SNE visualization of our MNE feature space, compare with the original image feature, MNE can achieve better clustering performance and reduce the effect of outliers, resulting in a higher retrieval result.

2. Euclidean Distance and Outliers

The concern about Euclidean distance’s sensitivity to outliers in the Regularized Barycenter Refinement (RBR) module is valid. However, our choice to include Euclidean distance stems from the following considerations,

• complementarity: Euclidean distance captures proximity in the original feature space, while the Wasserstein term accounts for distributional alignment. The Euclidean distance demonstrates high accuracy when retrieving close samples. To effectively address the challenges posed by complex practical datasets, it can be retained as a valuable metric. The dual objectives ensure a balance between locality and distributional robustness.
• outlier mitigation: The influence of outliers is mitigated through the Wasserstein regularization, which acts as a stabilizing term. Furthermore, our formulation (Eq. 6) includes entropy regularization to facilitate the solution to the optimization problem.

3. Use of Existing Techniques in Geodesic Transportation

We acknowledge that shortest-path computation is a standard technique, but we would like to clarify that the novelty of the Geodesic Transportation (GT) module lies in its integration within the NGT framework:

• We choose the geodesic distance to model the transportation trajectory. In our NGT framework, it is employed as a cost metric within the optimal transport problem, enabling the incorporation of both global geometric and contextual relationships.
• The combination of geodesic paths with manifold-aware distributions enhances the refinement of neighborhood relationships in a way that conventional methods do not achieve.

Thus, the value of GT lies in how it synergizes with MNE and RBR to improve neighborhood refinery.

4. Visual or Convincing Evidence of Robustness to Outliers

We appreciate the reviewer’s request for visual evidence to substantiate the robustness claim. To address this, we introduce neighborhood purity metric to empirically demonstrate the robustness improvements achieved by the proposed method. Additionally, we select some instances and exhibit the corresponding weight for constructing manifold-aware neighbor encoding in Figure 5 and provide a t-SNE visualization of MNE feature space in Figure 6. The comparison validates the effectiveness of MNE in strengthening clustering performance and mitigating the effect of outliers. Please refer to the revised version in appendix for more details.

5. Global Relationship Claims and Lack of Visual Evidence

We understand the concern regarding global relationship claims and the need for further evidence. To strengthen this aspect, we include t-SNE visualizations of the feature space before and after applying our proposed MNE in Figure 6, showcasing enhanced global and local structure alignment.

6. Missing Experimental Details

For more experimental details, we have rerun the experiments across multiple seeds, on CIFAR-10, the impact of random numbers on the results does not exceed 0.2 at most. Moreover, our approach introduces NGT into the BYOL framework to perform deep clustering, which leads to a significant enhancement, e.g., 7.8% improvement in NMI on CIFAR-10. Additionally, we report the convergence analysis in Figures 7 and 8. Both the iterations in MNE and RBR converge quickly within 10 epochs, validating the effectiveness of our method.