論文の概要: 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を低減できることがわかった。
関連論文リスト
- Unbounded Differentially Private Quantile and Maximum Estimation [2.855485723554975]
単純な$textttAboveThreshold$の呼び出しは、最高の量子化に対してより正確でロバストな見積もりを提供する。
我々は、textttAboveThreshold$を改良することで、広く使われているスパースベクトルテクニックのプライバシー保証を改善することができることを示す。
論文 参考訳(メタデータ) (2023-05-02T03:23:07Z) - 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 Binary Matrices [84.60886611165573]
この作業では、スパースデータセット全体を第三者とプライベートに操作し、共有することを目的としています。
実際、差分プライバシーは、プライバシの金の標準として現れていますが、スパースデータセットの共有に関しては、主要な結果の1つとして、偏微分プライベートメカニズムが極めて弱いプライバシ保証を持つ運命にあることを証明しています。
我々は、スムーズな$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) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳(メタデータ) (2020-12-23T17:07:26Z) - A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
差別化プライバシ(DP)は、正式な証明可能な保証を通じて、プライバシとユーティリティのトレードオフを説明する魅力的なプライバシ定義である。
本稿では,回帰,分類,密度推定など,多数の機械学習タスクをサポートするプライベートスケッチを提案する。
このスケッチは,局所性に敏感なハッシュをインデックス化して,効率的なワンパスアルゴリズムで構築したランダムな一致テーブルで構成されている。
論文 参考訳(メタデータ) (2020-06-16T17:47:48Z) - BUDS: Balancing Utility and Differential Privacy by Shuffling [3.618133010429131]
シャッフルやtextitBUDS によるユーティリティと差分プライバシーのバランスをとることは、クラウドソースの統計データベースへのアプローチである。
損失推定法とリスク最小化法を併用したワンホット符号化と反復シャッフル法により,新しいアルゴリズムを提案する。
バランスのとれたユーティリティとプライバシの実証テストの間、BUDSは$epsilon = 0.02$を生成します。
論文 参考訳(メタデータ) (2020-06-07T11:39:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。