論文の概要: Differentially Private Algorithms for Graphs Under Continual Observation

• arxiv url: http://arxiv.org/abs/2106.14756v3
• Date: Tue, 23 Sep 2025 09:51:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-24 20:41:27.329628
• Title: Differentially Private Algorithms for Graphs Under Continual Observation
• Title（参考訳）: 連続観測によるグラフの微分プライベートアルゴリズム
• Authors: Hendrik Fichtenberger, Monika Henzinger, Lara Ost,
• Abstract要約: 連続観測下でのグラフ問題に対する微分プライベートな動的グラフアルゴリズムについて検討する。 本稿では,加算誤差を因子的に改善する三角形数などの事象レベルの私的問題を提示する。 また、最小スパンニングツリー、最小カット、最密部分グラフ、最大マッチングのための$varepsilon$-differentially privateおよびpartial dynamic algorithmを与える。
• 参考スコア（独自算出の注目度）: 11.111949824180277
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and the result of the analysis. Dynamic graph algorithms maintain the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph where nodes or edges are inserted or deleted over time. They output the value of the solution after each update operation, i.e., continuously. We study (event-level and user-level) differentially private algorithms for graph problems under continual observation, i.e., differentially private dynamic graph algorithms. We present event-level private algorithms for partially dynamic counting-based problems such as triangle count that improve the additive error by a polynomial factor (in the length $T$ of the update sequence) on the state of the art, resulting in the first algorithms with additive error polylogarithmic in $T$. We also give $\varepsilon$-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching. The additive error of our improved MST algorithm is $O(W \log^{3/2}T / \varepsilon)$, where $W$ is the maximum weight of any edge, which, as we show, is tight up to a $(\sqrt{\log T} / \varepsilon)$-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error $(1+\beta)$ for any constant $\beta > 0$ and additive error $O(W \log(nW) \log(T) / (\varepsilon \beta))$. Finally, we show that the additive error for a broad class of dynamic graph algorithms with user-level privacy must be linear in the value of the output solution's range.
• Abstract（参考訳）: 異なるプライベートアルゴリズムは、データ中のユーザの存在と分析結果との間には、弱い相関しかないことを保証することで、データ分析シナリオにおける個人を保護する。 動的グラフアルゴリズムは、進化する入力上の問題(例えばマッチング)、すなわちノードやエッジが時間とともに挿入または削除されるグラフに対する解を維持する。 更新操作毎にソリューションの値を出力します。 連続的な観測下でのグラフ問題に対する(イベントレベルおよびユーザレベル)微分プライベートアルゴリズム、すなわち微分プライベートな動的グラフアルゴリズムについて検討する。 本稿では,多項式係数(更新シーケンスの長さ$T$)による加算誤差を改善する三角形数などの部分動的カウントに基づく問題に対する事象レベルプライベートアルゴリズムを提案する。 また、最小スパンニングツリー、最小カット、最密部分グラフ、最大マッチングのために、$\varepsilon$-differentially private and partial dynamic algorithmを与える。 改良MSTアルゴリズムの加算誤差は$O(W \log^{3/2}T / \varepsilon)$であり、ここでは$W$は任意のエッジの最大重みであり、示すように$(\sqrt{\log T} / \varepsilon)$-factorである。 他の問題に対して、任意の定数$\beta > 0$と加法誤差$O(W \log(nW) \log(T) / (\varepsilon \beta))$に対して、乗法誤差$(1+\beta)$と加法誤差$O(W \log(nW) \log(T) / (\varepsilon \beta))$に対して部分的に動的アルゴリズムを提案する。 最後に、ユーザレベルのプライバシを持つ広範クラスの動的グラフアルゴリズムに対する加算誤差は、出力ソリューションの範囲の値に線形でなければならないことを示す。

関連論文リスト

• Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism [5.4971134662997025]
  SVTを多次元ベクトルに一般化する新しい一般化スパースベクトル法を定式化する。 アプリケーションとして、我々は以前よりもバウンダリが良い多くの重要なグラフ問題を解く。 我々は、$O(epsilon-1log n)$加法誤差と$O(n)$ラウンドでの乗算誤差のない$k$コア分解に対して、厳密なローカルエッジDPアルゴリズムを与える。
  論文  参考訳（メタデータ） (2025-08-04T08:26:58Z)
• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
  ターンタイルストリーミングモデルにおいて、異なる要素を数えるという根本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを与える。 本結果は, 線形問題である最先端アルゴリズムの空間要求を著しく改善する。 ストリームにアイテムが現れる回数の制限付き$W$が分かっている場合、我々のアルゴリズムは$tildeO_eta(sqrtW)$ space.sqrtW)$ additive errorを提供する。
  論文  参考訳（メタデータ） (2025-05-29T17:21:20Z)
• Fully Dynamic Graph Algorithms with Edge Differential Privacy [1.4732811715354455]
  完全動的更新を伴う連続リリースの難易度設定において,グラフを解析するための差分プライベートアルゴリズムについて検討した。 これまでの研究では、挿入のみや削除のみを処理できる多くのグラフ問題に対して、差分プライベートなアルゴリズムが提案されてきた。 いくつかの基本グラフ問題に対して、事象レベルとアイテムレベルの完全動的アルゴリズムの誤差について、上下境界を与える。
  論文  参考訳（メタデータ） (2024-09-26T08:17:49Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  我々は,非プライベートなストリーミングと静的アルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。 これには、最も高密度な部分グラフのためのアルゴリズム、最大マッチング、および最初の連続リリース$k$-core分解アルゴリズムが含まれる。
  論文  参考訳（メタデータ） (2024-07-24T20:15:07Z)
• Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
  我々は、$k$-core分解のための$eps$-edge差分秘密アルゴリズムが乗算誤差なしでコア数を出力し、$O(textlog(n)/eps)$加法誤差を示す。 これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
  論文  参考訳（メタデータ） (2023-12-12T20:09:07Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)

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

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