# Efficient and Privacy-Preserved Link Prediction via Condensed Graphs

arXiv: https://arxiv.org/abs/2503.12156 · HTML: https://mlsanity.com/paper/2503.12156/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 38 of its 65 references that are in the map.
- First posted on arXiv 15 Mar 2025.

## Builds on (most cited first, 30 of 38)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Dataset Condensation with Gradient Matching](https://mlsanity.com/paper/2006.05929/) (2020)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [Quantifying Privacy Leakage in Graph Embedding](https://mlsanity.com/paper/2010.00906/) (2020)
- [Computing Graph Neural Networks: A Survey from Algorithms to Accelerators](https://mlsanity.com/paper/2010.00130/) (2020)
- [Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data](https://mlsanity.com/paper/2306.02664/) (2023)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [Graph Condensation via Receptive Field Distribution Matching](https://mlsanity.com/paper/2206.13697/) (2022)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Federated Graph Neural Networks: Overview, Techniques and Challenges](https://mlsanity.com/paper/2202.07256/) (2022)
- [Training Speech Recognition Models with Federated Learning: A Quality/Cost Framework](https://mlsanity.com/paper/2010.15965/) (2020)
- [Does Graph Distillation See Like Vision Dataset Counterpart?](https://mlsanity.com/paper/2310.09192/) (2023)
- [Fast Graph Condensation with Structure-based Neural Tangent Kernel](https://mlsanity.com/paper/2310.11046/) (2023)
- [Knowledge Graph Large Language Model (KG-LLM) for Link Prediction](https://mlsanity.com/paper/2403.07311/) (2024)
- [Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching](https://mlsanity.com/paper/2402.05011/) (2024)
- [Dataset Distillation for Medical Dataset Sharing](https://mlsanity.com/paper/2209.14603/) (2022)
- [Graph Condensation: A Survey](https://mlsanity.com/paper/2401.11720/) (2024)
- [A Survey on Privacy in Graph Neural Networks: Attacks, Preservation, and Applications](https://mlsanity.com/paper/2308.16375/) (2023)
- [Graph Distillation with Eigenbasis Matching](https://mlsanity.com/paper/2310.09202/) (2023)
- [A Review of Anonymization for Healthcare Data](https://mlsanity.com/paper/2104.06523/) (2021)
- [GC-Bench: An Open and Unified Benchmark for Graph Condensation](https://mlsanity.com/paper/2407.00615/) (2024)
- [A Graph Federated Architecture with Privacy Preserving Learning](https://mlsanity.com/paper/2104.13215/) (2021)

## Abstract (arXiv)

Link prediction is crucial for uncovering hidden connections within complex networks, enabling applications such as identifying potential customers and products. However, this research faces significant challenges, including concerns about data privacy, as well as high computational and storage costs, especially when dealing with large-scale networks. Condensed graphs, which are much smaller than the original graphs while retaining essential information, has become an effective solution to both maintain data utility and preserve privacy. Existing methods, however, initialize synthetic graphs through random node selection without considering node connectivity, and are mainly designed for node classification tasks. As a result, their potential for privacy-preserving link prediction remains largely unexplored. We introduce HyDROtextsuperscript+, a graph condensation method guided by algebraic Jaccard similarity, which leverages local connectivity information to optimize condensed graph structures. Extensive experiments on four real-world networks show that our method outperforms state-of-the-art methods and even the original networks in balancing link prediction accuracy and privacy preservation. Moreover, our method achieves nearly 20* faster training and reduces storage requirements by 452*, as demonstrated on the Computers dataset, compared to link prediction on the original networks. This work represents the first attempt to leverage condensed graphs for privacy-preserving link prediction information sharing in real-world complex networks. It offers a promising pathway for preserving link prediction information while safeguarding privacy, advancing the use of graph condensation in large-scale networks with privacy concerns.