論文の概要: Communication Cost Reduction for Subgraph Counting under Local
Differential Privacy via Hash Functions
- arxiv url: http://arxiv.org/abs/2312.07055v1
- Date: Tue, 12 Dec 2023 08:12:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-13 17:00:11.170279
- Title: Communication Cost Reduction for Subgraph Counting under Local
Differential Privacy via Hash Functions
- Title（参考訳）: ハッシュ関数による局所微分プライバシに基づくサブグラフカウントの通信コスト削減
- Authors: Quentin Hillebrand, Vorapong Suppakitpaisarn and Tetsuo Shibuya
- Abstract要約: エッジローカル差分プライバシーの下でのサブグラフのカウントにおいて,ハッシュ関数を用いて通信コストを削減することを提案する。
サンプリングレートが$s$であれば,通信コストを$s2$に削減できる。
- 参考スコア（独自算出の注目度）: 3.1815791977708834
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We suggest the use of hash functions to cut down the communication costs when
counting subgraphs under edge local differential privacy. While various
algorithms exist for computing graph statistics, including the count of
subgraphs, under the edge local differential privacy, many suffer with high
communication costs, making them less efficient for large graphs. Though data
compression is a typical approach in differential privacy, its application in
local differential privacy requires a form of compression that every node can
reproduce. In our study, we introduce linear congruence hashing. With a
sampling rate of $s$, our method can cut communication costs by a factor of
$s^2$, albeit at the cost of increasing variance in the published graph
statistic by a factor of $s$. The experimental results indicate that, when
matched for communication costs, our method achieves a reduction in the
$\ell_2$-error for triangle counts by up to 1000 times compared to the
performance of leading algorithms.
- Abstract（参考訳）: エッジローカルディファレンシャルプライバシの下でサブグラフをカウントする場合の通信コストを削減するためのハッシュ関数の利用を提案する。
グラフ統計の計算には、エッジの局所微分プライバシー下でのサブグラフ数を含む様々なアルゴリズムが存在するが、多くのアルゴリズムは高い通信コストを被り、大きなグラフでは効率が低下する。
データ圧縮は、差分プライバシーの典型的なアプローチであるが、そのローカル差分プライバシーのアプリケーションは、すべてのノードが再現できる圧縮形式を必要とする。
本研究では,線形整合ハッシュを導入する。
サンプリングレートが$s$であれば、公開グラフ統計のばらつきを増加させるコストを$s^2$とすることで、通信コストを$s^2$に削減できる。
実験の結果,提案手法が通信コストに合致すると,先行アルゴリズムの性能と比較して最大1000倍の精度で三角数に対する$\ell_2$-errorを低減できることがわかった。
関連論文リスト
- On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
例えば$binomn2-1 sum_i ne j f(x_i, x_j)$, $x_i$ は$i$thユーザへの入力を表し、ローカルモデルでは差分プライバシ(DP)である。
この定式化は、Kendallの$tau$ coefficient、Area Under Curve、Giniの平均差、Giniのエントロピーなどの重要なメトリクスをキャプチャする。
論文 参考訳（メタデータ） (2024-06-24T04:06:09Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Unbounded Differentially Private Quantile and Maximum Estimation [2.855485723554975]
単純な$textttAboveThreshold$の呼び出しは、最高の量子化に対してより正確でロバストな見積もりを提供する。
我々は、textttAboveThreshold$を改良することで、広く使われているスパースベクトルテクニックのプライバシー保証を改善することができることを示す。
論文 参考訳（メタデータ） (2023-05-02T03:23:07Z) - Privacy Amplification via Shuffling: Unified, Simplified, and Tightened [20.10078781197001]
シングルメッセージとマルチメッセージのシャッフルプロトコルの両方において、プライバシーを増幅するための包括的なフレームワークを提案する。
我々の理論的な結果は、特に極端確率設計を持つ局所確率化器に対して、我々のフレームワークがより厳密な境界を提供することを示している。
私たちのバウンダリは、非常に効率的な$tildeO(n)$アルゴリズムで、$n=108$ユーザに対して10$秒未満で、数値的にプライバシを増幅します。
論文 参考訳（メタデータ） (2023-04-11T06:27:25Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - 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) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Differentially Private Quantiles [12.917299605014419]
我々は,$n$のデータポイントから$m$quantilesを同時に推定する指数的メカニズムの例を提案する。
本手法は, 実データと合成データの両方において, 技術の現状を著しく上回っている。
論文 参考訳（メタデータ） (2021-02-16T16:02:59Z) - BUDS: Balancing Utility and Differential Privacy by Shuffling [3.618133010429131]
シャッフルやtextitBUDS によるユーティリティと差分プライバシーのバランスをとることは、クラウドソースの統計データベースへのアプローチである。
損失推定法とリスク最小化法を併用したワンホット符号化と反復シャッフル法により,新しいアルゴリズムを提案する。
バランスのとれたユーティリティとプライバシの実証テストの間、BUDSは$epsilon = 0.02$を生成します。
論文 参考訳（メタデータ） (2020-06-07T11:39:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。