論文の概要: Triangle Counting with Local Edge Differential Privacy

• arxiv url: http://arxiv.org/abs/2305.02263v3
• Date: Thu, 14 Aug 2025 22:33:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-18 14:51:22.653383
• Title: Triangle Counting with Local Edge Differential Privacy
• Title（参考訳）: 局所エッジ差分プライバシを用いた三角計数
• Authors: Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, Adam Smith,
• Abstract要約: エッジ差分プライバシーを持つ局所モデルにおける三角形計数について検討する。 本研究では,非対話的モデルと対話的モデルの両方について検討する。 我々の研究は局所モデルにおける微分プライベートグラフ解析における技術の現状を著しく改善する。
• 参考スコア（独自算出の注目度）: 3.071866762675526
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study triangle counting in the local model with edge differential privacy (that, intuitively, requires that the outputs of the algorithm on graphs that differ in one edge be indistinguishable). In this model, each party's local view consists of the adjacency list of one vertex. We investigate both noninteractive and interactive variants of the model. In the noninteractive model, we prove that additive $\Omega(n^2)$ error is necessary for sufficiently small constant $\varepsilon$, where $n$ is the number of nodes and $\varepsilon$ is the privacy parameter. This lower bound is our main technical contribution. It uses a reconstruction attack with a new class of linear queries and a novel mix-and-match strategy of running the local randomizers with different completions of their adjacency lists. It matches the additive error of the algorithm based on Randomized Response, proposed by Imola, Murakami and Chaudhuri (USENIX2021) and analyzed by Imola, Murakami and Chaudhuri (CCS2022) for constant $\varepsilon$. We use a different postprocessing of Randomized Response and provide tight bounds on the variance of the resulting algorithm. In the interactive setting, we prove a lower bound of $\Omega(n^{3/2}/\varepsilon)$ on the additive error for $\varepsilon\leq 1$. Previously, no hardness results were known for interactive, edge-private algorithms in the local model, except for those that follow trivially from the results for the central model. Our work significantly improves on the state of the art in differentially private graph analysis in the local model.
• Abstract（参考訳）: 業界における微分プライバシのデプロイの多くは、各パーティが微分プライベートなランダム化器を通じてプライベート情報をリリースする、ローカルモデルにある。 エッジ差分プライバシーを持つ局所モデルの三角形計数について検討する(直感的には、一方のエッジで異なるグラフ上のアルゴリズムの出力は区別できない)。 このモデルでは、各パーティのローカルビューは、1つの頂点の隣接リストで構成されている。 本研究では,非対話的モデルと対話的モデルの両方について検討する。 非インタラクティブモデルでは、加算$\Omega(n^2)$エラーが十分小さい定数$\varepsilon$に対して必要であることを示す。 この低い境界が私たちの主要な技術的貢献です。 新しいリニアクエリのクラスによるリコンストラクション攻撃と、隣接リストの異なる補完でローカルなランダム化器を実行する新しいミックス・アンド・マッチ戦略を使用する。 これは、Imola, Murakami and Chaudhuri (USENIX2021) が提案し、Imola, Murakami and Chaudhuri (CCS2022) が一定の$\varepsilon$で解析したランダム化応答に基づくアルゴリズムの加算誤差と一致する。 我々はランダム化応答の異なる後処理を使用し、結果のアルゴリズムの分散に厳密な境界を与える。 インタラクティブな設定では、$\Omega(n^{3/2}/\varepsilon)$の低い境界を$\varepsilon\leq 1$の加法誤差で証明する。 これまでは、中央モデルの結果から自明に追従するアルゴリズムを除いて、局所モデルにおける対話的かつエッジプライベートなアルゴリズムでは、硬さの結果は知られていなかった。 我々の研究は局所モデルにおける微分プライベートグラフ解析の最先端性を大幅に改善する。

関連論文リスト

• Differential Privacy in Kernelized Contextual Bandits via Random Projections [8.658538065693206]
  コンテキストによるカーネルの帯域幅の問題について考察する。 基礎となる報酬関数は、既知の再生ケルネルヒルベルト空間に属する。 我々は、$widetildemathcalO(sqrtgamma_TT+fracgamma_Tvarepsilon_mathrmDP)の最先端の累積後悔を実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-18T03:54:49Z)
• On the Price of Differential Privacy for Hierarchical Clustering [21.64775530337936]
  本稿では, エッジレベルのDP設定において, 既知の可視性よりもはるかに高い近似性を示す, 重み付きプライバシモデルにおける新しいアルゴリズムを提案する。 以上の結果から,提案アルゴリズムはコストの面では良好に動作し,大規模グラフに対するスケーラビリティも良好であることがわかった。
  論文  参考訳（メタデータ） (2025-04-22T04:39:40Z)
• PLAN: Variance-Aware Private Mean Estimation [12.452663855242344]
  差分的にプライベートな平均推定は、データ分析と機械学習のためのプライバシ保護アルゴリズムの重要な構成要素である。 ベクトル $boldsymbolsigma$ のスキューを利用する方法を示し、$ell$エラーで(ゼロ桁の)微分プライベート平均推定値を得る。 PLANの有効性を検証するため,合成データと実世界のデータの両方で精度を実証的に評価した。
  論文  参考訳（メタデータ） (2023-06-14T21:04:50Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• 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)
• Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
  我々は,シャッフルDPおよびパンプライベートモデルにおいて,$tildeO_varepsilon(sqrtn)$とほぼ一致する誤差を保証するアルゴリズムを提案する。 我々のアルゴリズムは非常に単純で、離散的なラプラスノイズヒストグラムを後処理するだけである。
  論文  参考訳（メタデータ） (2022-10-27T05:11:00Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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