論文の概要: Differentially Private Densest-$k$-Subgraph

• arxiv url: http://arxiv.org/abs/2505.03858v1
• Date: Tue, 06 May 2025 14:10:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-08 19:07:35.877049
• Title: Differentially Private Densest-$k$-Subgraph
• Title（参考訳）: Differentially Private Densest-$k$-Subgraph
• Authors: Alireza Khayatian, Anil Vullikanti, Aritra Konar,
• Abstract要約: 本稿では、Densest-$k$-subgraph問題に対して、正式な差分プライバシー保証を提供するアルゴリズムを最初に設計する。 計算コストは概ね高いが,私的でないPCの計算と並行して,PTRを実装するための新しい手法を設計する。
• 参考スコア（独自算出の注目度）: 20.806820384111113
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many graph datasets involve sensitive network data, motivating the need for privacy-preserving graph mining. The Densest-$k$-subgraph (D$k$S) problem is a key primitive in graph mining that aims to extract a subset of $k$ vertices with the maximum internal connectivity. Although non-private algorithms are known for D$k$S, this paper is the first to design algorithms that offer formal differential privacy (DP) guarantees for the problem. We base our general approach on using the principal component (PC) of the graph adjacency matrix to output a subset of $k$ vertices under edge DP. For this task, we first consider output perturbation, which traditionally offer good scalability, but at the expense of utility. Our tight on the local sensitivity indicate a big gap with the global sensitivity, motivating the use of instance specific sensitive methods for private PC. Next, we derive a tight bound on the smooth sensitivity and show that it can be close to the global sensitivity. This leads us to consider the Propose-Test-Release (PTR) framework for private PC. Although computationally expensive in general, we design a novel approach for implementing PTR in the same time as computation of a non-private PC, while offering good utility for \DkS{}. Additionally, we also consider the iterative private power method (PPM) for private PC, albeit it is significantly slower than PTR on large networks. We run our methods on diverse real-world networks, with the largest having 3 million vertices, and show good privacy-utility trade-offs. Although PTR requires a slightly larger privacy budget, on average, it achieves a 180-fold improvement in runtime over PPM.
• Abstract（参考訳）: 多くのグラフデータセットにはセンシティブなネットワークデータが含まれており、プライバシ保護グラフマイニングの必要性を動機付けている。 Densest-$k$-subgraph (D$k$S) 問題は、最大内部接続で$k$頂点の部分集合を抽出することを目的としたグラフマイニングにおける重要なプリミティブである。 非プライベートなアルゴリズムはD$k$Sで知られているが、この問題に対して正式な差分プライバシー(DP)保証を提供するアルゴリズムを最初に設計する。 我々は、グラフ隣接行列の主成分(PC)を用いて、エッジDPの下で$k$頂点のサブセットを出力する一般的なアプローチを基礎とする。 このタスクのために、我々はまず、従来は優れたスケーラビリティを提供するが、ユーティリティを犠牲にして出力の摂動を考慮する。 ローカルな感度は、グローバルな感度と大きなギャップがあることを示し、プライベートPCにインスタンス固有の感度メソッドを使うことを動機付けています。 次に、スムーズな感度に厳密な拘束力を与え、グローバルな感度に近くなることを示す。 これにより,PC 用 Propose-Test-Release (PTR) フレームワークを検討することができる。 計算コストは概ね高いが,非プライベートPCの計算と同時にPTRを実装するための新しい手法を設計し,DkS{} に優れたユーティリティを提供する。 また、大規模ネットワーク上でのPTRよりも大幅に遅いにもかかわらず、プライベートPCの反復的プライベートパワー方式(PPM)についても検討する。 私たちは様々な現実世界のネットワーク上でメソッドを実行し、最大で300万の頂点を持ち、優れたプライバシーとユーティリティのトレードオフを示しています。 PTRは多少大きなプライバシー予算を必要とするが、平均すると、PPMよりも180倍のランタイム改善を実現している。

関連論文リスト

• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。 DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。 本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
  論文  参考訳（メタデータ） (2024-11-27T00:48:48Z)
• Privacy Profiles for Private Selection [21.162924003105484]
  私たちは、ReportNoisyMaxとPrivateTuningのプライバシプロファイルを、それらが相関するベースアルゴリズムのプライバシプロファイルを使ってバウンドする、使いやすいレシピを開発しています。 このアプローチはすべての利害関係を改善し、エンドツーエンドのプライベート学習実験において大きなメリットをもたらす。
  論文  参考訳（メタデータ） (2024-02-09T08:31:46Z)
• Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank [74.53857412207034]
  本稿では,近似的なPPRを出力し,入力エッジに有界な感度を持つアルゴリズムを提案する。 我々の感度バウンドPPRは、差分プライベート(DP)PPRランキング、DPノード分類、DPノード埋め込みなど、グラフ学習のいくつかのツールのプライベートアルゴリズムを直接意味している。
  論文  参考訳（メタデータ） (2022-07-14T14:08:59Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  しかし、スパースデータセットを共有するという点では、差分プライバシーがプライバシのゴールドスタンダードとして浮上している。 本研究では、スムーズな$k$匿名性(スムーズな$k$匿名性)と、スムーズな$k$匿名性(スムーズな$k$匿名性)を提供する単純な大規模アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-07-13T17:09:25Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Pre-trained Perceptual Features Improve Differentially Private Image Generation [8.659595986100738]
  差分降下勾配(DP-SGD)を用いた中等度生成モデルの訓練も困難である。 私たちは、情報のある公開データセット上に適切な、関連する表現を構築し、その表現でプライベートデータをモデル化することを学びます。 私たちの研究は、プライベートと非プライベートの深層生成モデルの間のギャップを減らすための、シンプルで強力な基盤を導入しています。
  論文  参考訳（メタデータ） (2022-05-25T16:46:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。