SENSE: SENsing Similarity SEeing Structure

Low-dimensional embeddings are central to analyzing and visualizing high-dimensional data. However, widely adopted NE methods assume centralized access to all data an unrealistic constraint in privacy-sensitive, decentralized environments. We propose SENSE, a geometry-aware, privacy-preserving framework for global neighbor embedding without raw data exchange. SENSE reconstructs global structure using local distance measurements and structured matrix completion, enabling embeddings that preserve both local and global geometry in Euclidean and hyperbolic spaces. It further integrates contrastive learning by deriving cross-client positive and negative pairs from estimated similarities, effectively generalizing negative sampling under structural constraints. Experiments across diverse real-world datasets show that SENSE achieves embedding quality on par with centralized baselines, while offering strong privacy guarantees. Theoretical analysis provides formal bounds on reconstruction fidelity and privacy, establishing conditions under which structure and confidentiality are jointly preserved.