本研究探 討在「可達性完全保留」 之嚴 格 功能 限 制下， 資料 血 緣圖 （Data Lineage Graphs）之結構隱私保護問題。在實務應用中，資料血緣廣泛用於除錯、稽核與影響分析，然而其結構亦可能洩漏敏感資訊，使得在維持功能正確性的前提下進行隱私保護成為一項具挑戰性的課題。
本研究指出，當系統必須維持可達性關係不變時，圖結構中將存在不可修改之核心骨架，進而形成可被利用之穩定結構特徵。我們將此現象定義為「不變性悖論（Invariance Paradox）」，並進一步證明該現象導致一自然形成之「隱私飽和邊界（Privacy Saturation Boundary）」，使得結構隱私無法隨擾動程度無限提升。
在方法上，本研究提出一套基於結構指紋（Structural Fingerprint）之隱私保護框架，透過在不改變可達性語意的前提下，選擇性地新增可行邊以降低節點可辨識性。該方法結合整數線性規劃（Integer Linear Programming, ILP）以求解小型關鍵子圖之最佳解，並採用具可擴展性的貪婪演算法處理大型圖結構。
實驗結果顯示，在有限擾動預算下，結構隱私可於初期快速提升，但隨後迅速達到飽和，多數資料集之飽和點落於 0.02 至 0.07 之間。同時，本方法在維持可達性正確性（F1 = 1.0）之條件下，可將攻擊成功率降低超過 60%。
綜上所述，本研究證明在可達性保留條件下，資料血緣圖之結構隱私存在本質性上限。此結果顯示未來在設計隱私保護機制時，必須同時考量功能約束與結構限制，而非單純依賴擾動方法以提升隱私。

This thesis investigates the problem of structural privacy in data lineage graphs under the strict requirement of preserving reachability semantics. In practical systems, data lineage is widely used for debugging, auditing, and impact analysis. However, the structural information of lineage graphs may also leak sensitive knowledge, making privacy preservation particularly challenging when functional correctness must be maintained.
We show that under exact reachability preservation, a core structural backbone of the graph must remain unchanged, resulting in persistent structural signatures that can be exploited for re-identification. We characterize this phenomenon as the Invariance Paradox and further demonstrate that it induces a natural privacy saturation boundary, beyond which additional perturbations yield diminishing privacy gains.
To address this challenge, we propose a fingerprint-based construction framework that enhances structural privacy while preserving reachability semantics. The framework combines an exact integer linear programming (ILP) formulation for small critical subgraphs with a scalable greedy algorithm for large graphs.
Experimental results show that structural privacy improves rapidly under small perturbation budgets but saturates early, with median saturation points typically ranging from 0.02 to 0.07 across datasets. The proposed method reduces attack success rates by more than 60% while maintaining perfect reachability correctness (F1 = 1.0).
Overall, our findings reveal that structural privacy in reachability-preserving lineage graphs is fundamentally bounded. This highlights the necessity of explicitly considering structural constraints when designing privacy-preserving mechanisms for metadata sharing systems.

[1] Faraz Ahmed, Alex X. Liu, and Rong Jin. Social graph publishing with privacy guarantees.In 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS),pages 447–456, 2016.
[2] Lars Backstrom, Cynthia Dwork, and Jon Kleinberg. Wherefore art thou r3579x?anonymized social networks, hidden patterns, and structural steganography. Commun.ACM, 54(12):133–141, 2011.
[3] Rajendra Bose and James Frew. Lineage retrieval for scientific data processing: A survey.ACM Comput. Surv., 37(1):1–28, 2005.
[4] Justin Brickell and Vitaly Shmatikov. The cost of privacy: destruction of data-mining utility in anonymized data publishing. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’08, pages 70–78. Association for Computing Machinery, 2008.
[5] Peter Buneman, Sanjeev Khanna, and Tan Wang-Chiew. Why and where: A characterization of data provenance. In Jan Van den Bussche and Victor Vianu, editors, Database Theory —ICDT 2001, pages 316–330.Springer, 2001.
[6] Jordi Casas-Roma, Jordi Herrera-Joancomartí, and Vicenç Torra. An algorithm for k-degree anonymity on large networks. In Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM ’13, pages 671–675. Association for Computing Machinery, 2013.
[7] James Cheney, Stephen Chong, Nate Foster, Margo Seltzer, and Stijn Vansummeren.Provenance: a future history. In Proceedings of the 24th ACM SIGPLAN conference companion on Object oriented programming systems languages and applications, OOPSLA’09, pages 957–964. Association for Computing Machinery, 2009.
[8] Susan B. Davidson, Sanjeev Khanna, Tova Milo, Debmalya Panigrahi, and Sudeepa Roy.Provenance views for module privacy. In Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS ’11, pages 175–186. Association for Computing Machinery, 2011.
[9] Xuan Ding, Lan Zhang, Zhiguo Wan, and Ming Gu. A Brief Survey on De-anonymization Attacks in Online Social Networks. In 2010 International Conference on Computational Aspects of Social Networks, pages 611–615, 2010.
[10] European Union. General data protection regulation GDPR, regulation (eu) 2016/679.https://gdpr-info.eu/, 2016.
[11] Calancea Georgiana, Alboaie Lenuta, and Titchiev Inga. Linked data lineage as a foundation of continuous data integration and modern data governance. Computer Science Journal of Moldova, 2025.
[12] Michael Hay, Gerome Miklau, David Jensen, Don Towsley, and Philipp Weis. Resisting structural re-identification in anonymized social networks. Proc. VLDB Endow., 1(1):102–114, 2008.
[13] Xiaoyun He, Jaideep Vaidya, Basit Shafiq, Nabil Adam, and Vijay Atluri. Preserving privacy in social networks: A structure-aware approach. In 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, volume 1,pages 647–654, 2009.
[14] Melanie Herschel, Ralf Diestelkämper, and Houssem Ben Lahmar. A survey on provenance:What for? what form? what from? The VLDB Journal, 26(6):881–906, 2017.
[15] Shouling Ji, Prateek Mittal, and Raheem Beyah. Graph Data Anonymization, De-Anonymization Attacks, and De-Anonymizability Quantification: A Survey. IEEE Communications Surveys & Tutorials, 19(2):1305–1326, 2017.
[16] Zach Jorgensen, Ting Yu, and Graham Cormode. Publishing attributed social graphs with formal privacy guarantees. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD ’16, pages 107–122. Association for Computing Machinery,2016.
[17] Nitish Korula and Silvio Lattanzi. An efficient reconciliation algorithm for social networks.Proc. VLDB Endow., 7(5):377–388, 2014.
[18] Kun Liu and Evimaria Terzi. Towards identity anonymization on graphs. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, SIGMOD’08, pages 93–106. Association for Computing Machinery, 2008.
[19] Jiangtao Ma, Yaqiong Qiao, Guangwu Hu, Yongzhong Huang, Arun Kumar Sangaiah,Chaoqin Zhang, Yanjun Wang, and Rui Zhang. De-anonymizing social networks with random forest classifier. IEEE Access, 6:10139–10150, 2018.
[20] Luc Moreau, Ben Clifford, Juliana Freire, Joe Futrelle, Yolanda Gil, Paul Groth, Natalia Kwasnikowska, Simon Miles, Paolo Missier, Jim Myers, Beth Plale, Yogesh Simmhan, Eric Stephan, and Jan Van den Bussche. The open provenance model core specification (v1.1).Future Gener. Comput. Syst., 27(6):743–756, 2011.
[21] Arvind Narayanan and Vitaly Shmatikov. Robust De-anonymization of Large Sparse Datasets. In 2008 IEEE Symposium on Security and Privacy (Sp 2008), pages 111–125, 2008.
[22] Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. In 2009 30th IEEE Symposium on Security and Privacy, pages 173–187, 2009.
[23] Bofeng Pan, Natalia Stakhanova, and Suprio Ray. Data provenance in security and privacy.ACM Comput. Surv., 55(14):323:1–323:35, 2023.
[24] Alessandra Sala, Xiaohan Zhao, Christo Wilson, Haitao Zheng, and Ben Y. Zhao. Sharing graphs using differentially private graph models. In Proceedings of the 2011 ACM SIGCOMM conference on Internet measurement conference, IMC ’11, pages 81–98. Association for Computing Machinery, 2011.
[25] Pegdwendé Sawadogo and Jérôme Darmont. On data lake architectures and metadata management. J. Intell. Inf. Syst., 56(1):97–120, 2021.
[26] Yogesh L. Simmhan, Beth Plale, and Dennis Gannon. A survey of data provenance in e-science. SIGMOD Rec., 34(3):31–36, 2005.
[27] J. Teuhola. Path signatures: a way to speed up recursion in relational databases. IEEE Transactions on Knowledge and Data Engineering, 8(3):446–454, 1996.
[28] Sushil Kumar Tiwari. Transparent ETL and data lineage frameworks: Building trust-worthy AI for financial services. Journal of Computational Analysis and Applications(JoCAAA), 34(12):568–578, 2025.
[29] Xiaowei Ying and Xintao Wu. Randomizing social networks: a spectrum preserving approach. In Proceedings of the 2008 SIAM International Conference on Data Mining, pages 739–750. Society for Industrial and Applied Mathematics, 2008.
[30] Bin Zhou, Jian Pei, and WoShun Luk. A brief survey on anonymization techniques for privacy preserving publishing of social network data. SIGKDD Explor. Newsl., 10(2):12–22,2008.
[31] Lei Zou, Lei Chen, and M. Tamer Özsu. k-automorphism: a general framework for privacy preserving network publication. Proc. VLDB Endow., 2(1):946–957, 2009.