SENSE: $\underline{\text{SEN}}$sing Similarity $\underline{\text{SE}}$eing Structure

We thank the reviewer for their valuable feedback and careful reading. Due to space limits, we refer to responses given to other reviewers for some similar concerns.

W1&Q1: We appreciate this important question. We address it in 3 parts: (1) theoretical non-invertibility, (2) incompatibility of standard attacks with our setting, and (3) empirical attack simulations.

1. Theoretical Non-Invertibility & Privacy-by-Design: In SENSE, clients share only the distance vector between local non-anchor (NA) points & a known set of $K$ anchors; no raw features, labels, or model parameters are exposed. These vectors are inherently non-invertible due to geometric underdetermination. Given $K$ anchors $\{\mathbf{a}_1, \mathbf{a}_2, \dots, \mathbf{a}_K\} \subset \mathbb{R}^d$, recovering $\mathbf{x} \in \mathbb{R}^d$ from $\|\mathbf{x} - \mathbf{a}_i\|$ results in a system of $K$ equations with $d$ unknowns. When $K < d$, the system is underdetermined and has infinitely many solutions. Using squared distances: $\|\mathbf{x} - \mathbf{a}_i\|^2 = \|\mathbf{x}\|^2 - 2 \langle \mathbf{x}, \mathbf{a}_i \rangle + \|\mathbf{a}_i\|^2$ . This yields $K$ quadratic equations in $d$ variables, which are non-unique when $K < d$ (as shown in Theorem 3.2 and proof in Appendix). Hence, inversion is ambiguous by design (also check Reviewer yoyK: Ans to W2).

2. Inapplicability of Standard Privacy Attacks: a) Model Inversion Attacks: These attacks aim to reconstruct input data (e.g., faces, records) by optimizing overtrained models or partial layers, supervised predictions (logits, class scores), gradients, or overfitted behaviors. SENSE bypasses all of these vectors, as no supervised model is trained at the server, & no labels, logits, or gradients are exposed. The server only sees numeric distance values, a compressed geometric abstraction. Thus, inversion attacks lack a viable attack surface in our setting. b) Membership Inference Attacks (MIA): MIA strategies typically rely on changes in model confidence when queried with “seen” vs. “unseen” samples. However, SENSE is model-free; the server observes only static distance vectors. There’s no model behavior to exploit. While standard MIA assumptions do not apply we still simulate such attacks on SENSE for empirical completeness.

3. Empirical Attack Simulations: We test MIA and inversion attacks across four datasets. MIA Goal: Determine whether a point was part of the client dataset. Method: Extract statistical features (mean, std, min, max, quantiles) from DNA vectors and train classifiers (MLP, RF) to predict membership. Inversion Goal: Reconstruct $\mathbf{x}$ from ${d_i = |\mathbf{x} - \mathbf{a}_i|}$ .

Method: Solve,

We assess privacy using three metrics: MIA Accuracy, Pixel Error, and Reconstruction Accuracy ($1 - \text{Pixel Error}$). MIA accuracy reflects the success of membership inference; values near 50% indicate strong privacy. Pixel Error measures the average deviation between reconstructed and original inputs; higher values mean better protection. We categorize privacy into three levels: HIGH (MIA ≤ 51%, Pixel Error ≥ 20%), MEDIUM (MIA 48–51%, Pixel Error 15–20%), and LOW (MIA < 48%, Pixel Error < 15%). These thresholds offer a compact, interpretable view of privacy risk across attacks.

Table1: Privacy Results

Datasets with higher input dimensionality and well-spanned $K$ anchor sets demonstrate greater resilience to reconstruction, validating the theory behind our design. Result: MIA Accuracy Range: $48\%$ to $51\%$. These results are near random guessing, indicating strong privacy protection. Result for model inversion attack: Avg Pixel Reconstruction Error: $20.42\%$. Even in low-error cases reconstructions were visually degraded, confirming the underconstrained nature of inversion.

W2: In addition to 14 standard DR datasets (section 4.1 SENSE), we provide the runtime & metric evaluations on Tiny ImageNet: 90K NA (ResNet features $d = 512$), Street View House Numbers (SVHN) Dataset: ~80K NA (ResNet features $d = 512$):

Table2: Shows SENSE: Achieves strong performance even for large sophisticated datasets, with runtimes of ~12–14 sec per iteration:

W3&Q2: SENSE depends on 2 factors: number of anchors $K$ & anchor selection. 1) $K$: We sample anchors such that we fix total (global + local) anchors to $K = d_h - 1$, where $d_h$ is input dim. This is not arbitrary; it’s theoretically optimal under our privacy guarantee. By Thrm 3.1, if $K < d_h$, to ensure privacy. Thus, $K = d_h - 1$ is the largest safe choice that preserves privacy & yields strong approximations. There’s a privacy–utility–compute trade-off - Higher $K$: better fidelity, higher runtime, weaker privacy. Lower $K$: stronger privacy, lower compute, possible fidelity drop. We empirically validate this trade-off on both synthetic and real datasets.

For low-dim data ($d_h = 100$, $N = 500$):

• $K = 99$ → FS = 0.79, time = 16s
• $K = 90$ → FS = 0.78, time = 13s

For high-dim data ($d_h = 700$, $N = 500$):

• $K = 699$ → FS = 0.82, time = 660s
• $K = 350$ → FS = 0.78, time = 312s

Thus, for high-dim where $d_h \gg N$, using fewer anchors (e.g., $K < d_h - 1$) leads to substantial computational gains while preserving utility, useful in large-scale deployments such as hospital networks.

2) Anchor Geometry: Beyond count, anchor geometry impacts fidelity. We show that affinely independent anchors improve reconstruction. On the digits dataset ($N = 1797$, $d_h = 64$), we fixed $K = 63$ and varied anchor matrix rank $r$. NA set: 1000 points, split across 10 clients (multisite-full). Table 3: Validates that higher affine rank of anchors improves neighborhood fidelity, consistent with our theory.

3) Anchor Selection: We also study how anchor selection affects downstream performance. Random anchors sampling perform worse than those sampled from the underlying data distribution. Table 4: Confirms that in-distribution anchors preserve structure better. Setup: 10 clients, 1000 NA points, multisite-full setting.

4) Practical Anchor Sources: Anchors in real-world settings can come from: Patient-consented samples (healthcare), Reference transactions (finance), Public/synthetic data from similar distributions, MMD-based generation [43] (though limited: adversarial risk, pointwise-only, high compute see Reviewer yoyK: Q2 Ans & Reviewer rkR3: W2 Table1). Such server-curated anchors are common in privacy-sensitive domains: Healthcare [7, 27], Genomics [35, 44], Finance [2], Mobile/NLP [23, 32] offering auditability, stability, and robustness. Theoretical and practical support for shared anchors exists in prior distance geometry/localization works: Low-rank recovery from structured distances [52], Dual basis for robust Euclidean geometry [29] , Gram matrix completion in partial sensor networks [31]. These validate our anchor-based design in decentralized settings.

W4: We agree that introducing anchor-based reconstruction methods will improve clarity. In the revised Section 2, we will briefly describe both classical methods from distance geometry and localization [1–5] and recent global embedding methods using anchors for t-SNE/UMAP-style visualizations (related work [43, 47, 48]). While these works motivate anchor-based embedding, SENSE goes further by supporting structured distance sharing under privacy constraints and enabling accurate recovery without centralized access. We will also revise Figure 1 to more clearly illustrate the end-to-end pipeline and how anchor-based distance sharing enables global coordination in distributed low-dimensional embedding.

References [1] P. Biswas & Y. Ye, “Distance matrix reconstruction from incomplete distance info for sensor network localization,” Sensor Network Operations, IEEE, 2004, pp. 285–294.
[2] Z. Zhu, A. M.-C. So, Y. Ye, “A dual basis approach for structured robust Euclidean distance geometry,” Comput. Optim. Appl., 45(1), pp. 97–121, 2010.
[3] S. T. Smith, “Localization from structured distance matrices via low-rank recovery,” Inverse Problems, 29(11), 2013.
[4] K. Weinberger & L. Saul, “FastMap, MetricMap, and Landmark MDS are all Nyström algorithms,” Proc. ICML, 2008, pp. 1160–1167.
[5] M. A. Alfakih, “Exact reconstruction of Euclidean distance geometry via low-rank matrix completion,” Linear Algebra Appl.

We thank the reviewer for their valuable feedback & careful reading. Due to space limits we refer to answers provided to other reviewers where similar concerns were addressed.

W2: Addressed in 3 parts: comparison with prior work; SENSE runtime/complexity; large-scale results on SVHN & Tiny ImageNet.

1. Prior Limitations: SMAP uses SMC for t-SNE, incurring ~32–50 hrs runtime for just 4k points (32D) due to encryption-related ops. It lacks UMAP support (encrypted k-NN is infeasible), doesn’t allow collaborative analysis, is tied to t-SNE, and risks privacy if partial distances leak unprotected (details [57]). FedNE [33] uses surrogate distillation with $\mathcal{O}(N^2)$ inter-client exchange, unscalable as client count grows. Surrogates are vulnerable to gradient/model inversion attacks without DP or encryption. FedTSNE [43] synthesizes anchors via MMD, prone to poisoning if any client/sample is adversarial. It supports only multisite setting, needs iterative communication, and depends on external privacy tools. SENSE Advantages: No encryption: operates on partial distances with anchor count $< d_h$ (see Thms 3.1, 3.2). Privacy is built-in, not bolted on. Requires one round of client-server communication, clients send anchor–NA distances once. No iterative or inter-client messaging.

Table 1: SENSE outperforms FedTSNE on both runtime & acc. Runtime includes full pipeline: anchor generation+matrix completion+t-SNE emb.

2. Runtime&Complexity: Let $N$ = #points, $K$ = #anchors, $d$ = dim. Anchored-MDS has complexity $\mathcal{O}(K^2 d + K N d)$, efficient as $K \ll N$ & $K < d$ (privacy). Global embedding uses fast NE methods: FIt-SNE runs in $\mathcal{O}(k n \log n \cdot d)$ [Appx G, 11]; NC-t-SNE/UMAP with contrastive loss run in $\mathcal{O}(k m d)$ , with $m \ll n$ repulsive samples/epoch [11]. Overall linear in $d$ scalable to large datasets.

Table2: Runtime for SENSE pipeline stages: stage1: Incomplete matrix, stage2: matrix completion

3. Large-scale results: For this please see our response to Reviewer 7okJ: W2.

Q2&W1: We acknowledge the confusion in phrasing. Clarification: Our formal guarantees apply only to privacy: Thms3.1&2 shows when $K < d_h$ exact recovery of features from anchor–NA distances is impossible. Regarding fidelity we intended to convey that as $K \to d_h - 1$ SMACOF preserves relative neighborhood structure not raw features. This reconstruction is consistent up to Euclidean isometries (translation, rotation) & potential global scaling which are standard ambiguities in metric embedding methods such as classical MDS & SMACOF [15]. In privacy-preserving settings this is sufficient for downstream tasks. We support this empirically (Fig.3). We agree that we have not included formal fidelity bounds as these results are well established in literature. Notably, the quality of distance-based reconstruction using different solvers is known to depend on geometry & condition of observed distances. Our choice of SMACOF was guided by ease of implementation & its compatibility with distance-based privacy, but we acknowledge that stronger theoretical guarantees are available via other solvers. To strengthen the work,we will include a remark clarifying that: Our notion of "fidelity" refers to preservation of neighborhood structure not raw feature recovery. For tighter bounds the reader may consult existing theoretical work on distance matrix completion & MDS-based recovery eg., SVD-based recovery in localization:
$\| D - S_4 \|_F^2 = \mathcal{O}(n\, d_{\text{max}}^4 + n^{3/2} d_{\text{max}}^3)$ , Expected EDM recovery error: $\frac{1}{n} \mathbb{E}\| \hat{D} - D \|_F \leq C \sqrt{\frac{r n}{m}} (\zeta + \nu)$ , IRLS-based distance recovery & Dual-basis convex relaxations with RIP-style guarantees. These validate the feasibility of accurate distance recovery under structural priors & motivate future integration into our framework. If required we can include heuristic bound with proof: Let $X$ be true NA features, $\hat{X}$ the SMACOF-reconstructed ones using $K$ anchors, & $G$, $\hat{G}$ their squared distance matrices. If $\sigma_j(X) \le \frac{C_0}{j^p}$ for $p > 1$, then: $\text{DE} = \frac{\| \hat{G} - G \|_F}{\| G \|_F} \le \frac{C}{K - \delta}, \quad \text{for } K \in \left[\frac{d}{2}, d - 1\right]$ where $C > 0$ & $\delta$ captures anchor degeneracy.
We thank the reviewer for the insightful suggestion. It not only improves the clarity of our current work but also opens a valuable direction for future research developing formal fidelity guarantees under partial distance constraints.

Q3: The ans is threefold: 1) Practical View: SENSE Enforces Privacy by Design: It is built for strict privacy raw features are never shared. Clients only send partial structured distance vectors which are disjoint & never centralized. This prevents any adversary from reconstructing global data geometry or latent structure. Even with $K < d_h$ the adversary lacks enough information to infer client embeddings.

2. Theoretical View: Structure-Aware Adversaries Can Reconstruct if a sophisticated adversary infers intrinsic structure e.g, embeddings lie on a low-rank subspace (rank $r$ ) then the underdetermined system $A_j x_j = b$ may be solvable using structured regularization: nuclear norm minimization for low-rank or LASSO for sparsity. In literature it is proven that privacy can break if both structured distances & strong geometric priors are available. For eg, in [52] exact recovery with $r+1$ anchors is shown using convex solvers (Appx B, Sec 5.4) & also nuclear norm recovers full distance matrices under standard assumptions (Thms 1–2, Remark 2).

3. Proposing 2 solutions: 1) Local Differential Privacy (LDP), Apply LDP to each client’s DNA vector before sending. Clients clip distances to threshold $\delta$ & add Laplace noise with scale $\lambda$, with privacy budget $\epsilon = \frac{2 \delta}{\lambda}$ ; 2) Rank-Aware Anchor Capping: If the server receives clients estimated ranks $\{r_1, r_2, \dots, r_N\}$ it sets #anchor $K = \min(r_1, r_2, \dots, r_N) - 1$ . This ensures no client gets more than $r$ affinely independent anchors keeping the system underdetermined & preserving privacy regardless of structure.

We test both solutions under adversaries on structured data. Data: $X_{\text{struct}} = X_{\text{low-rank}} + 0.5 \cdot X_{\text{sparse}}$ , size $n \times d$, rank $r = 50$, $d = 100$. Attacks: Low-rank (SVD-based), Sparse (LASSO), Baseline (anchor feature mean). Metrics: RE: Reconst error, FS: F1score (true vs recons), PL: Privacy leak $1 - \frac{\text{RE}}{\text{RE}_{\text{baseline}}}$ , Vulnerable: True if RE<0.1

Table4: On synthetic low-rank+sparse data attacks fail to leak private data when LDP is applied even with anchor $K \geq r$.

As $K \to r$ or exceeds, adversaries can exploit affine structure evidenced by low RE & high FS indicating successful reconstruction (privacy leak). However, LDP nullifies leakage even for $K \geq r$. Also, when $K < r$ the system remains underdetermined no privacy risk. This validates our two solutions. Here RE & FS indicate adversary success low RE & high FS imply a breach. So higher RE & lower FS mean stronger privacy.

Q4&1: Please see response to Reviewer 7okJ: W3 & Q2 & W1 (theoretical non-invertibility) We would appreciate it if you could kindly refer to that section as it provides a detailed clarification aligned with your concern.

Q5: SENSE uses a 2-stage pipeline. This is practically necessary due to limitations of existing NE methods (e.g., t-SNE, UMAP) as they assume access to full raw data or complete similarity matrices. SENSE operating under partial & distributed visibility uses Stage1 to reconstruct the structure needed for such methods to work. Matrix completion (e.g, SMACOF-MDS) is relatively stable with clearer convergence while NE objectives are non-convex & sensitive to both initialization & structural noise. Separating stages improves stability & interpretability. Importantly our privacy guarantees are tied to Stage1. Merging both stages is a promising direction we're exploring end-to-end approaches that learn global embeddings directly from partial distances without requiring explicit matrix reconstruction. Promising directions include: joint optimization $\mathcal{L} = \alpha \cdot \text{CompletionLoss}(X) + \beta \cdot \text{NE/CNE Loss}(Y)$ where $X$ are intermediate embeddings consistent with observed distances & $Y$ are final projections (an early idea). Missing-data-aware NE methods: Exploring variants of NE/CNE that work directly on incomplete distances. Low-rank embedding from partial distances using matrix factorization. While the current 2-stage SENSE design reflects practicality, modularity & privacy guarantees we agree that a unified formulation is the natural next step. Building an end-to-end SENSE is part of our ongoing research.

W3: We’ll fix typos & clarify notation in revision.

Thank you for the response to my review. I am satisfied with how the concerns raised on runtime, scalability, theoretical support, clarification on privacy and potential structure-aware adversaries were addressed. I hope that the authors will modify the paper accordingly.

We thank the reviewer for their valuable feedback & careful reading. Due to space limits, we refer to answers provided to other reviewers where similar concerns were addressed.

Q1: While Thems 3.1 & 3.2 establish the geometric conditions under which private data cannot be uniquely recovered, we agree that adding an explicit privacy definition will enhance clarity. The notion we adopt, geometric non-identifiability via underdetermined distance systems is well established. It aligns with prior literature in privacy-preserving embedding & fed learning including FedNE, dTSNE, FedTSNE & dSNE. Though these methods differ in technique (e.g., surrogate models, synthetic or MMD-generated anchors) they all rely on the same principle: client data remains unrecoverable, while only indirect distance/similarity information is shared for global embedding. We will formalize this definition in the revised manuscript for completeness.

Definition:
A mechanism is privacy-preserving if, for each private point $x_i \in \mathbb{R}^{d_h}$, the $K$ anchor distances shared are insufficient to uniquely determine $x_i$. That is, when $K < d_h$, the inverse problem is underdetermined and $x_i$ lies in a high-dimensional affine subspace of $\mathbb{R}^{d_h}$.

This definition ensures privacy by design and applies broadly to domains like healthcare, finance, and mobile systems where sensitive data must remain private but collaboration is critical for global modeling.

Q2: This addresses core of SENSE’s geometric privacy guarantee rooted in linear algebra & Euclidean distance geometry. Privacy is preserved when the system formed by anchor distances is underdetermined i.e., there are more unknowns than equations. This occurs when the number of anchors $K$ is less than the feature dimension $d_h$. In this case, many valid solutions exist for the feature vector consistent with the observed distances making exact recovery impossible. The threshold $K = d_h$ is critical: at or above this point the system becomes solvable, enabling unique feature reconstruction and violating privacy. This is a fundamental result not a heuristic arising from the rank conditions of the linear system

Why does $K = d_h$ break privacy? At $K = d_h$, the system becomes square & full-rank. The client’s feature vector $x$ can now be uniquely solved using only the shared distances directly violating our privacy guarantee. This sharp threshold is not arbitrary it emerges naturally from linear algebra and localization theory used in: GPS trilateration, Wireless sensor network localization & Euclidean distance geometry. Now if $d_h \to \infty$: As $d_h$ grows the anchor count needed for recovery also grows. In high dimensions (e.g., ResNet with $d_h = 512$) even $K = 100$ yields a highly underdetermined system making inversion practically infeasible. Thus, larger $d_h$ ⇒ strong privacy for fixed $K$ (check ans Reviewer 7okJ: W3 & Q2). Is uncertainty alone enough for privacy?: No. SENSE ensures privacy via deterministic non-identifiability not random uncertainty. The recovered feature lies in an affine subspace of dimension ≥ $d_h - K + 1$ guaranteed by geometry not noise & independent of data distribution. See empirical support (Fig. 3).

Q3: While adding noise seems intuitive, it’s inadequate without formal guarantees. We highlight 2 cases: 1) Noise to Raw Features (No Anchor Setup): Perturbing raw features and using them to compute distances leaves systems vulnerable to advanced denoising, as shown in deep learning literature [1,2,3]. Techniques like adversarial Monte Carlo or feature-conditioned modulation can recover original features with high accuracy in structured datasets. 2) Noise Added to Distance Vectors in Anchor-Based Setup (e.g., $K = d_h$): In setups where $K = d_h$ and noise is added to distance vectors, the distance map becomes fully determined. If the noise distribution is known (Gaussian), adversaries can use MLE or Bayesian inference to recover features. Without formal mechanisms like ($\epsilon$, $\delta$)-DP, even small noise offers no provable privacy especially in structured or high-dimensional regimes. Noise-based privacy is heuristic and fragile. In contrast, SENSE ensures deterministic privacy via geometric non-identifiability: By setting $K < d_h$, the system remains underdetermined. Observed distances correspond to an affine subspace with infinitely many valid solutions. Even with exact distances, recovery is impossible due to structural ambiguity. Empirical support (Fig. 3): As $K \to d_h - 1$, fidelity (F1, cosine sim.) remains strong. Beyond that, Frobenius error and Pearson correlation spike indicate potential leakage. This aligns with our core claim: privacy is preserved as long as $K < d_h$.

Q4: Indeed your intuition is correct trust. & cont. are widely used to quantify local neighborhood preservation and are now standard in recent DR and federated visualization work. Though less common than kNN recall in classic NE, they offer complementary views of embedding quality. Steadiness and cohesiveness assess inter-cluster reliability, crucial for global structural tasks. Metric Recap (see also Section 4): 1) Trust.: Preserves high-dim neighbors in low-dim space. 2) Continuity: Low-dim neighbors reflect true neighbors in input space. 3) Steadiness: Checks for spurious groupings & 4) Cohesiveness: Detects missing cluster structures. These metrics are supported in prior works: FedNE, Deep Recursive Embedding & ZADU. To further clarify, we also include common NE metrics used in FedTSNE (ICLR 2024), such as CA (kNN Classification Accuracy), NMI (Normalized Mutual Info), SC (Silhouette Coef.), and Overlap@k. We simulate adversarial conditions: A1: 60% clients adversarial, all samples. A2: 60% clients, 30% samples adversarial. Results are in Table 1: For metric definitions: CA = Classification Accuracy with kNN, NMI = Normalized Mutual Information, SC = Silhouette Coefficient, and Overlap@k = Neighborhood Overlap for top-k.

W1: Curated Example to Demonstrate Privacy: We created a curated dataset with private attributes such as age & categorical features like gender or occupation. The setup includes: 5 clients (denoted $C_1$ to $C_5$), Each with 5 attributes (i.e., $d = 5$) & 4 reference anchors (i.e., $K = 4 < d$). The SENSE framework is used to compute embeddings using only client-to-anchor distances.

SENSE emb

It is evident that the embeddings generated by the SENSE framework do not expose any sensitive details of the original data.

W2: We agree that several points in the original version could benefit from clearer exposition. Below we address each point and outline revisions: 1)"MDS is not NE": Correct, MDS is a classical DR method, not a modern NE technique. In our text, MDS was cited broadly among methods using pairwise structure. We'll revise to clearly separate MDS (distance-preserving) from NE methods (e.g., t-SNE, UMAP) that preserve local neighborhoods. 2) "Why problematic for t-SNE/UMAP?": These methods need complete pairwise graphs to compute attraction/repulsion. In privacy/decentralized settings, missing distances distort this balance leading to poor embeddings (e.g., collapsed neighborhoods). We'll clarify this with support from decentralized NE literature. 3) "Contrastive learning & NE?": NE is often framed as contrastive learning ([33], [56]): positive pairs = neighbors, negative = non-neighbors. These require reliable similarity graphs hard to obtain under privacy. SENSE overcomes this using anchor-based structured similarity. 4) Related work: Addressed in detail in Reviewer rkR3 Answer W2. Kindly refer there for a complete explanation. 5) "What are anchors/sharing?": Anchors are non-sensitive reference points aiding localization without exposing features. See our response to Reviewer 7okJ: W3 & Q2. for full clarification. 7) "CNE doesn’t use an encoder": True for the original CNE [33]. However, recent variants (e.g., FedNE, SelfGNN) use encoder-based adaptations. SENSE is compatible with both. 8) "Unfamiliar metrics (e.g., trustworthiness)": Fully addressed in Q4. 9) "Recovery impossible from distances?": Covered in Q2. We show recovery becomes possible when anchors ≥ $d_h$, hence our privacy bound $K < d_h$. We’ll revise the intro to improve flow, define NE clearly, and better motivate our method. Thank you again for the insightful critique.

Limitation: We appreciate the suggestion and will include a formal limitations section in the revised version. On problem demand: recent work shows increasing interest in privacy-preserving NE (FedNE, dSNE, dTSNE, FedTSNE & SMAP). This shows our formulation is timely & relevant. SENSE adds to this space by offering a modular, geometry-driven solution. Regarding privacy we clarified. This aligns with definitions implicitly used in the above prior works, all of which aim to prevent raw data recovery while supporting global embedding. We agree that stronger privacy models and extending SENSE toward these (e.g., via noise or DP mechanisms) is a promising future direction, which we will mention in our limitations.

We thank the reviewer for this suggestion; as per our understanding, a global rotation does not provide privacy in a multi-client setting. It is only effective if applied to the entire dataset, which is infeasible in decentralized settings where clients don’t share raw features or a common coordinate frame. Moreover, if the rotation is known (shared in encrypted form), then it may be inverted using existing techniques (discussed in points 1-3). If it’s unknown, coordination between clients becomes impossible. SENSE avoids both issues by never assuming access to global feature vectors; privacy arises from the geometric ambiguity of the reconstruction problem itself, not from post-hoc obfuscation.

1. Image encryption and decryption using bit rotation and Hill Cipher: A paper discusses an encryption approach for images using bit rotation reversal and extended Hill cipher techniques. Decryption involves reversing the bit rotation and applying the inverse Hill cipher [1]
2. Vertical Bit Rotation (VBR) Algorithm: The decryption process for this algorithm involves applying the opposite rotation (e.g., rotating vertically upwards if encryption rotated downwards) using the same key to restore the original data [2]
3. Permutation based Image Encryption Technique: This technique involves multiple phases including bit, pixel, and block permutation. Decryption reverses these permutation steps in the correct order to reveal the secret image [3]

We also acknowledge that every privacy mechanism has its strengths and limitations. While noise and rotation-based methods offer certain guarantees, SENSE takes a different approach, grounded in deterministic geometry and suitable for decentralized, structured, and privacy-sensitive scenarios. We see this as a complementary direction in the space of privacy-preserving representation learning. We will add a remark in the revised manuscript to explicitly discuss: Future directions, including potential hybrid methods that combine SENSE with noise-based or rotation-based techniques. Opportunities to strengthen SENSE's privacy guarantees using additional regularization or uncertainty modeling. We sincerely thank the reviewer for these insightful suggestions and would be happy to explore them further in future work.

References: [1] Kumar et al. (IJCA’12). Bit Rotation & Hill Cipher. [2] Pertiwi et al. (JoSCE’22). Vertical Bit Rotation Algorithm. [3] Indrakanti & Avadhani (IJCA). Permutation-Based Image Encryption.

We agree that our writing in some parts conflates different types of ambiguity (e.g., “non-uniqueness” vs “reversibility”). To address this, we will: 1) Add a formal definition of privacy in the introduction and make the introduction more clear by clarifying how the NE and DR methods suffer in decentralized settings. 2) Clarify why we are choosing $K<d$ and not $K = d$. 3) Remove confusing language like “small-structured & reversible” unless we define it precisely with illustrative examples (e.g., 3D circle on sphere intersection, 2D mirror reflection). 4) Clearly distinguish between anchors (non-sensitive) and private points, justifying anchor sharing in practice and theory. 5) Emphasize why post-hoc rotation or noise is insufficient in decentralized settings without raw feature sharing or coordination.

Appeal to Reviewer: We sincerely thank the reviewer for pushing us to sharpen our definitions and improve the clarity of our manuscript. We hope that the combination of empirical evidence, theoretical grounding, and clearer articulation addresses the key concerns raised. As all other reviewers are leaning toward acceptance, your feedback is critical in determining the final outcome of this work. If you feel your concerns have now been sufficiently addressed, we would deeply appreciate if you could consider revisiting your overall score to reflect your updated assessment. We are fully committed to incorporating all your suggestions in the final revision.

We sincerely thank the reviewer for identifying this issue, and we agree that our earlier phrasing may not have made the distinctions clear. Below we address both subpoints in turn.

1. Anchor Sharing Does Not Violate Our Privacy Definition: The 10% anchor sharing in the multisite setting (line 239) is used only for empirical evaluation. These anchors are not private they act as public or semi-public landmarks, similar to those in GPS or radar systems. This is standard practice in localization literature [6,7], where landmarks aid positioning but are not themselves privacy-sensitive [8]. Our privacy definition protects only the high-dimensional features of NA points. Anchors are fixed & visible and either synthetic, public, or explicitly consented. Not part of any client's private data. We do not rely on anchor secrecy but instead limit anchor quantity, ensuring $K < d$ to maintain ambiguity.

Real-World Anchor Sources: In practical deployments, anchors are selected based on domain knowledge and are not sampled arbitrarily from private data. Eg, Healthcare: Publicly released reference scans or patient-consented samples [1,2]. Finance: Standard transaction patterns or aggregated customer profiles [3]. Genomics: Population-level reference genomes (e.g., 1000 Genomes, UK Biobank) [4,5]. Synthetic Anchors: Via MMD minimization [5], though limited in coverage and potentially adversarial (see also Reviewer yoyK Q4 and rkR3 W2, Table 1). Trusted server-curated anchors are auditable, robust, and independent of client records, reducing leakage risks like membership inference [5]

This design is further supported by theory on low-rank recovery via anchor distances [9], matrix completion in non-orthogonal bases [10], and Gram matrix-based localization [11].

2. Why SENSE Avoids Noise-Based Privacy: We thank the reviewer for raising the important question of noise-based privacy mechanisms. While we acknowledge that such approaches can be used, the goal of SENSE is fundamentally different. Our objective is to reconstruct or approximate inter-point distances not the raw features while ensuring that high-dim features of NA points remain private. Importantly in SENSE distances are not treated as private. Instead, they are intermediate coordination variables similar to how they are used in classical MDS or sensor network localization. The core idea is to protect the original feature representations, not to hide the distance map itself. That said, we recognize that noise-based privacy mechanisms may be appropriate in some scenarios, particularly where (a) robust denoising resistance is guaranteed & (b) added noise does not critically degrade performance. However, we chose not to use noise-based methods in SENSE for the following reasons (also see Reviewer yoyK ans to Q3):

Empirical Evaluation: 1) Noise Added to DNA Matrix: We randomly selected a percentage of clients & added noise to their client-to-anchor distances. Evaluation on datasets (Iris & Seeds) shows a clear trade-off between privacy & performance:

As noise increases (that is, increasing the noisy entries in DNA block by inc noisy clients percentage), both FS drops & DE rises, demonstrating that such noise harms utility in SENSE.

2. Noise to Raw Features: We also added Gaussian noise directly to raw features (e.g., pixel-level perturbation of MNIST data) with $K = d_h$ anchors & a client set of 10 clients & 100 NA. In the noise-based variant (NS), we added element-wise zero-mean Gaussian noise with varying standard deviations proportional to data range: |Method|DE|FS| |-|-|-| |SENSE|0.006023|0.974955| |NS1|0.074474|0.946917| |NS2|0.268156|0.887382| |NS3|0.535183|0.801178| |NS4|0.843552|0.691761| |NS5|1.175783|0.573909|

These results show that even mild noise causes sharp performance degradation, confirming that noise-based privacy comes at a significant cost to utility (comparing SENSE without noise with NS). In real-world applications such as healthcare or finance, where precision is critical, this trade-off is often unacceptable.

References: [1] Bycroft et al. (Nature’18). UK Biobank, Genomics. [2] Johnson et al. (SciData’16). MIMIC-III Dataset. [3] Awosika et al. (Access’24). XAI & FL in Finance. [4] Litvinuková et al. (Nature’20). Human Heart Atlas. [5] Qiao et al. (2024). Fed t-SNE & UMAP. [6] Patil & Zaveri (WSN’11). Trilateration via MDS. [7] Fang & Chen (Sensors’20). RSS-Based Trilateration. [8] Nikoo & Behnia (TAES’18). Passive Localization. [9] Lichtenberg & Tasissa (TIT’24). Low-Rank Recovery. [10] Tasissa & Lai (LAA’21). Matrix Completion (Non-Orth. Basis). [11] Kundu et al. (CISS’25). Sampling for Distance Geometry. [12] Xu et al. (TOG’19). Adversarial Denoising (AMC). [13] Tan et al. (arXiv’25). Attribution in Gen Models.

In earlier responses, we used the phrase “small, structured, and reversible ambiguity” when describing the solution space under $K = D$ affinely independent anchors. We now agree that this wording was vague & potentially contradictory. Below, we clarify each term:

1. "Structured ambiguity": Although the solution is not unique, it lies on a low-dimensional, geometrically constrained manifold (e.g., a circle or mirrored points).
2. "Small": The space of plausible reconstructions has very low entropy (e.g., one degree of freedom), making it easier for an adversary to infer the correct solution.
3. "Reversible": In practice, such constrained ambiguity can often be resolved using side information, statistical priors, or optimization heuristics, as shown in localization literature and attack papers ([1–7]).

So while $K = D$ doesn’t yield exact recovery, the structured ambiguity reduces effective privacy.

In distance-based reconstruction (eg, DGP, localization, hyperbolic recovery) the anchor setup determines how constrained the solution space is. Privacy favors ambiguity, ideally the true point lies among many plausible candidates. Choosing $K<D$ affinely independent anchors increases uncertainty while preserving structure. This is critical for protecting sensitive attributes & holds across both geometries.

1. $K = D$ small, structured ambiguity: Knowing distances from $x \in \mathbb{R}^D$ to $D$ affinely independent anchors constrains $x$ to a 1D manifold (typically a circle), the intersection of $D$ hyperspheres in $\mathbb{R}^D$, yield1 DoF (rotation around the affine hull). E.g, in 2D: 2 anchors->2 symmetric positions. In 3D: 3 anchors -> point lies on a circle [8–10]. This is structured ambiguity-non-unique but tightly constrained and reversible, weakening privacy.

If the $D$ anchors are affinely dependent (e.g., lie on a hyperplane), the system degenerates & the solution expands from a curve to a surface or higher. Eg: In 2D: 2 collinear anchors-> infinite feasible points on a circle. In 3D: 3 coplanar anchors -> solution on a cylindrical surface (2D ambiguity) [9]. While ambiguity aids privacy, affine dependence is fragile, hard to detect, & unreliable in high dimensions.

2. $K<D$ robust, privacy-safe ambiguity: When the #anchors is reduced to $K = D - 1$ & they are affinely independent, the intersection of $D - 1$ hyperspheres in $\mathbb{R}^D$ leaves the unknown point on a 1D manifold (if $K = D - 1$) or a 2D manifold (if $K = D - 2$). This increases ambiguity while preserving structure & analyzability. Eg: In 3D: 2 anchors->solution on sphere surface (2D ambiguity). In 4D: 3 anchors-> 2D manifold in $\mathbb{R}^4$. ([9], Ch. 3.2). This ambiguity is affine-robust even poorly placed anchors preserve uncertainty. Moreover, L-HYDRA shows recovery is possible when $K \geq d$ (Thm 3.1), so $K = D-1$ is the last point before identifiability arises.

Why $K<D$ is a Privacy-Safe Design Choice: More Ambiguity = More Privacy: Fewer constraints expand the solution space (e.g., curve -> surface), making inference harder. Affine-Robust: Unlike $K = D$, no risk of degeneracy from anchor placement. No Utility Loss: Most applications (e.g., clustering, visualization) only need recovery up to isometry; more anchors add identifiability risk [1-6] without added benefit. Thus, choosing $K < d$ affinely independent anchors is a principled privacy strategy it maximizes ambiguity, avoids degeneracy & generalizes across both spaces, making it broadly applicable. In contrast, $K = D$ imposes tight constraints & narrows the solution space. SENSE intentionally limits anchor access to protect against this.

NOTE1: Mirror ambiguity [10-16] occurs when localization via anchor distances yields multiple symmetric solutions, especially at $k = d$ (eg, 2 anchors in 2D). [10] studies this in 3D WSNs where flip ambiguity causes 2 equally plausible mirrored node positions due to geometry or noise. Why it happens: In 2D with $k = 2$, the 2 anchor distances define circles intersecting at 2 symmetric points, reflections across the anchor line. Symmetric distances: Knowing a distance, the point may lie on either side of the anchor. In [16] localization is framed as embedding a weighted graph (nodes = unknowns + anchors, edges = distances) into $\mathbb{R}^k$. With few anchors, especially $k = D$, mirror symmetry arises: multiple equally valid placements of unknown nodes exist, reflected across the affine subspace spanned by the anchors.

Ref (abbreviated): [1] Fredrikson et al. (CCS’15) · [2] Shokri et al. (S&P’17) · [3] Fredrikson et al. (USENIX’14) · [4] Zhu et al. (NeurIPS’19) · [5] Geiping et al. (NeurIPS’20) · [6] Nasr et al. (S&P’19) · [7] Fang (J. Guid. Ctrl Dyn’86) · [8] Liberti et al. (SIAM Rev’14) · [9] Biswas & Ye (IPSN’04) · [10] Liu et al. (ICT’14) · [11] Bose et al. (arXiv’17) · [12] Hou (GPS Solut.’22) · [13] Gerok et al. (ICUWB’09) · [14] Betti et al. (Geo’93) · [15] Teunissen (GNSS’17) · [16] Saxe (Allerton’79)

Note: We emphasize that we are not introducing new content but thoroughly addressing your raised concerns with clearer explanations, supporting theory, citations, & empirical results. Our response is structured into 4 focused parts, each directly aligned with specific reviewer comments.

We apologize that our previous responses did not fully resolve your concerns. We also appreciate your acknowledgment of the soundness & effectiveness of our core algorithm. Upon reflection, we recognize that your main concern lies in the imprecise phrasing in few parts of the manuscript & we regret any resulting confusion. Below, we offer a clearer, more concise explanation:

We acknowledge that all similarity-based DR methods struggle in decentralized settings without global distance access. Our phrasing may have wrongly implied this issue is unique to t-SNE/UMAP. All DR methods that depend on distances or similarities between data points face challenges when global information is unavailable. However, different methods are affected in different ways, depending on how they are designed and how they use similarity information during training. Our emphasis on t-SNE and UMAP is based on the fact that these two methods use a different kind of optimization process, one that involves simulating forces between data points to create a meaningful low-dimensional layout. In both t-SNE & UMAP: (Attractive force) Each point is pulled closer to points that are similar to it in the original high-dim space (typically its nearest neighbors). (Repulsive force) Each point is pushed away from other points that are dissimilar helping prevent clusters from collapsing into each other. This balance between attraction & repulsion allows t-SNE & UMAP to preserve local structure while also encouraging global separation. This force-based layout makes them powerful for visualization but also sensitive to missing information in decentralized settings. To compute repulsive forces accurately, each point would need to know about the positions of all other points in the dataset. In a centralized setting, this is possible, though computationally expensive. However, in decentralized settings, the data is spread across multiple clients & each client only has access to its own local data. This makes it impossible to directly calculate the repulsion from points on other clients, because the client has no knowledge of them.

To reduce cost, t-SNE/UMAP use negative sampling: instead of computing repulsion from all points, they sample a few negatives. This works centrally, as samples reflect the global distribution. But in decentralized settings, clients can only sample from their own data a biased subset. So, the repulsive force is incomplete or skewed. This weakens separation, causes cluster drift, & distorts global structure. FEDNE (NeurIPS'24) confirms this: without accurate global repulsion, cluster layouts become unreliable. Their proposed solution uses lightweight surrogate models to approximate repulsion toward unknown global points, directly validating our concern. Similarly, the work “From t-SNE to UMAP with Contrastive Learning” (Yue et al 23) shows that t-SNE & UMAP can be understood as contrastive learning methods where the repulsion is implemented through a negative sampling-based loss. This view makes the importance of representative negatives even more central to correct optimization & also highlights why these models are particularly vulnerable when such negatives are missing or biased, as happens in decentralized settings.

Other methods face different issues. PCA computes variance and finds directions of maximum spread, it does not use attraction or repulsion. MDS minimizes stress to preserve pairwise distances, but it does not use iterative force-based updates as in t-SNE. LLE & Isomap construct kNN graphs & solve global optimization problems (typically via spectral decomposition). While they rely on local neighborhoods, they still require global graph connectivity & distance information to produce meaningful embeddings. Although these methods do not involve stochastic, runtime interactions like attractive & repulsive forces, they still fundamentally depend on access to global distances or similarities. In decentralized settings where such information is incomplete or fragmented across clients, their performance degrades significantly, though for different reasons than t-SNE or UMAP.

We thank the reviewer for reiterating about the earlier confusion. We clarified here that we do not claim t-SNE & UMAP are “more fragile” than other DR methods in general. Rather they face different challenges under decentralized conditions due to their dependence on both attractive & repulsive forces at every step of training. Their use of negative sampling to estimate repulsion & the fact that negative sampling becomes unreliable when clients can only see a small local view of the data. We will revise our manuscript to reflect this more precisely.

I sincerely appreciate and understand the authors' efforts in the response. Really, I do.

But, to re-iterate, my point is not in these specific concerns. I used these as examples of a more general trend in the paper. My primary issue is that the writing is consistently imprecise (makes unsubstantiated claims, lacks definitions, does not adequately express why algorithmic decisions are reached). These issues I brought up were examples of this.

While I recognize the authors' insistence regarding the examples I presented (I still disagree but this is not important), my primary concern is in the overall issue rather than the points in question.

I recognize that the authors state that they will resolve this for the camera-ready, but as I am not able to see what these revisions would be, I do not feel confident that the thematic issues will be resolved (in particular because the authors' first comments produced a definition of privacy-preserving that then led to further contradictions and imprecisions).

I believe the authors are presenting a good idea. I believe that when it is re-written so that every statement is checked/cited/substantiated, that it will be a great paper. But in the form it was presented, I do not believe it passes the bar for NeurIPS. I am sorry. As I said, I will be keeping my score.