Kerangka Berbasis Graf untuk Memperluas Mekanisme Privasi Diferensial Metrik

Merumuskan perluasan sebagai paradigma desain umum untuk privasi diferensial metrik pada domain terstruktur berskala besar

Ruiyao Liu; Chenxi Qiu· 2026· DOI 10.48550/arXiv.2609.14125

Masalah inti

Privasi diferensial metrik (mDP) adalah gagasan privasi yang cocok untuk domain rahasia terstruktur, di mana sensitivitas suatu rahasia bergantung pada jarak metrik antara elemen domain. Namun, membangun mekanisme mDP yang sadar utilitas secara langsung pada domain besar atau berbutir halus sering kali sangat mahal secara komputasi. Makalah ini mengkaji **desain mDP berbasis perluasan**, di mana mekanisme pertama-tama ditentukan pada himpunan berhingga *seed record* lalu diperluas ke *target domain* yang lebih besar. Penulis berargumen bahwa, sepengetahuan mereka, ini adalah karya pertama yang secara sistematis merumuskan perluasan sebagai paradigma desain umum untuk mDP, bukan sebagai konstruksi yang spesifik pada metode tertentu. Pertanyaan penelitian utamanya adalah: dalam kondisi apa perluasan dari mekanisme yang ditentukan secara lokal menghasilkan mekanisme global yang terdefinisi dengan baik dan memenuhi ε -mDP pada domain target? Makalah ini menjawabnya dengan mengusulkan kerangka perluasan berbasis graf, mengidentifikasi tiga persyaratan kebenaran, dan menginstansiasi kerangka tersebut dengan algoritma berbasis pohon untuk grid multi-resolusi.

Inovasi

Makalah ini melaporkan eksperimen pada **dataset peta jalan**. Evaluasi menunjukkan bahwa pendekatan yang diusulkan mencapai **trade-off utilitas-skalabilitas** yang kuat sekaligus mempertahankan **jaminan mDP yang eksak**. Dengan kata lain, kerangka perluasan memungkinkan mekanisme dibangun secara efisien pada domain besar dan berbutir halus tanpa mengorbankan jaminan privasi formal. Eksperimen membandingkan utilitas mekanisme yang diperluas dengan manfaat skalabilitas, menunjukkan bahwa perluasan berbasis graf dan instansiasi berbasis pohonnya dapat menangani domain grid multi-resolusi secara efektif. Abstrak tidak memberikan hasil numerik spesifik, tetapi klaim kualitatifnya adalah metode ini menyeimbangkan utilitas dan skalabilitas lebih baik daripada konstruksi langsung pada seluruh domain.

Privasi diferensial metrik (mDP) adalah gagasan privasi yang cocok untuk domain rahasia terstruktur, di mana sensitivitas suatu rahasia bergantung pada jarak metrik antara elemen domain. Namun, membangun mekanisme mDP yang sadar utilitas secara langsung pada domain besar atau berbutir halus sering kali sangat mahal secara komputasi. Makalah ini mengkaji **desain mDP berbasis perluasan**, di mana mekanisme pertama-tama ditentukan pada himpunan berhingga *seed record* lalu diperluas ke *target domain* yang lebih besar. Penulis berargumen bahwa, sepengetahuan mereka, ini adalah karya pertama yang secara sistematis merumuskan perluasan sebagai paradigma desain umum untuk mDP, bukan sebagai konstruksi yang spesifik pada metode tertentu. Pertanyaan penelitian utamanya adalah: dalam kondisi apa perluasan dari mekanisme yang ditentukan secara lokal menghasilkan mekanisme global yang terdefinisi dengan baik dan memenuhi ε -mDP pada domain target? Makalah ini menjawabnya dengan mengusulkan kerangka perluasan berbasis graf, mengidentifikasi tiga persyaratan kebenaran, dan menginstansiasi kerangka tersebut dengan algoritma berbasis pohon untuk grid multi-resolusi.

Penulis memformalkan desain mDP berbasis perluasan menggunakan kerangka berbasis graf. Domain target direpresentasikan sebagai graf yang simpulnya adalah record dan sisinya menyandikan relasi ketetanggaan atau penerus. Mekanisme pertama-tama didefinisikan pada himpunan berhingga seed record, lalu diperluas ke seluruh domain dengan menyebarkan mekanisme sepanjang struktur graf.

Mengapa penting

Kontribusi utama karya ini bersifat konseptual: karya ini merumuskan ulang perluasan sebagai paradigma desain umum untuk mDP, bukan sebagai kumpulan trik yang spesifik pada metode tertentu. Dengan mengidentifikasi tiga persyaratan kebenaran—batasan mDP lokal, konsistensi tumpang tindih, dan pemeliharaan mDP pada tingkat penerus—penulis menyediakan cetak biru yang dapat digunakan kembali untuk memperluas mekanisme mDP yang ditentukan secara lokal ke domain terstruktur yang lebih besar. Kerangka berbasis graf ini bersifat umum dan pada prinsipnya dapat menampung berbagai struktur graf dan aturan perluasan. Instansiasi berbasis pohon untuk grid multi-resolusi menunjukkan satu cara konkret untuk mewujudkan kerangka tersebut, menggunakan interpolasi satu dimensi dan komposisi per dimensi untuk menangani domain multi-dimensi. Pendekatan ini sangat relevan untuk domain seperti jaringan jalan, di mana rahasianya adalah lokasi dan metriknya adalah jarak jalan. Membangun mekanisme mDP secara langsung pada semua lokasi berbutir halus akan sangat mahal secara komputasi, tetapi perluasan dari himpunan seed record membuat masalahnya menjadi terkelola. Pemeliharaan jaminan ε -mDP yang eksak menjadi kekuatan utama, karena memastikan bahwa keuntungan skalabilitas tidak diperoleh dengan mengorbankan privasi. Pekerjaan selanjutnya dapat mengeksplorasi struktur graf lain, aturan perluasan alternatif, dan aplikasi di luar dataset peta jalan. Kerangka ini juga membuka jalan bagi pendekatan desain modular, di mana mekanisme lokal dan algoritma perluasan dapat dikembangkan dan dianalisis secara independen.

Siapa yang sebaiknya membaca

Praktisi dan peneliti ilmu komputer

Membuka konten member…