論文の概要: K-stars LDP: A Novel Framework for (p, q)-clique Enumeration under Local Differential Privacy

• arxiv url: http://arxiv.org/abs/2403.01788v1
• Date: Mon, 4 Mar 2024 07:30:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-06 19:46:43.565416
• Title: K-stars LDP: A Novel Framework for (p, q)-clique Enumeration under Local Differential Privacy
• Title（参考訳）: k-stars ldp: (p, q)-clique enumerationの局所微分プライバシー下での新しいフレームワーク
• Authors: Henan Sun and Zhengyu Wu and Rong-Hua Li and Guoren Wang and Zening Li
• Abstract要約: (p,q)-clique enumeration on a bipartite graph is critical to compute clustering coefficient and detection densest subgraph。 最近の研究は、エッジLDPに基づくプライバシ保護アルゴリズムに焦点を当てている。 そこで我々は,k-stars LDP の新たなアイデアと (p, q)-clique enumeration の k-stars LDP アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 27.83322523750288
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: (p,q)-clique enumeration on a bipartite graph is critical for calculating clustering coefficient and detecting densest subgraph. It is necessary to carry out subgraph enumeration while protecting users' privacy from any potential attacker as the count of subgraph may contain sensitive information. Most recent studies focus on the privacy protection algorithms based on edge LDP (Local Differential Privacy). However, these algorithms suffer a large estimation error due to the great amount of required noise. In this paper, we propose a novel idea of k-stars LDP and a novel k-stars LDP algorithm for (p, q)-clique enumeration with a small estimation error, where a k-stars is a star-shaped graph with k nodes connecting to one node. The effectiveness of edge LDP relies on its capacity to obfuscate the existence of an edge between the user and his one-hop neighbors. This is based on the premise that a user should be aware of the existence of his one-hop neighbors. Similarly, we can apply this premise to k-stars as well, where an edge is a specific genre of 1-stars. Based on this fact, we first propose the k-stars neighboring list to enable our algorithm to obfuscate the existence of k-stars with Warner' s RR. Then, we propose the absolute value correction technique and the k-stars sampling technique to further reduce the estimation error. Finally, with the two-round user-collector interaction mechanism, we propose our k-stars LDP algorithm to count the number of (p, q)-clique while successfully protecting users' privacy. Both the theoretical analysis and experiments have showed the superiority of our algorithm over the algorithms based on edge LDP.
• Abstract（参考訳）: (p,q)-clique enumeration on a bipartite graph はクラスタリング係数の計算と最も密度の高い部分グラフの検出に重要である。 機密情報を含む可能性があるため、潜在的な攻撃者からユーザーのプライバシーを保護しながら、サブグラフ列挙を行う必要がある。 最近の研究では、エッジldp(local differential privacy)に基づくプライバシー保護アルゴリズムに焦点を当てている。 しかし、これらのアルゴリズムは大量のノイズのために大きな推定誤差を被る。 本稿では、k-stars ldpの新しいアイデアと、(p, q)-clique enumeration for (p, q)-clique enumeration のための新しいk-stars ldpアルゴリズムを提案する。 エッジLDPの有効性は、ユーザと彼のワンホップ隣人のエッジの存在を曖昧にする能力に依存している。 これは、ユーザが自分のワンホップ隣人の存在に気付くべきだという前提に基づいている。 同様に、この前提をk-スターにも適用でき、エッジは1-スターの特定のジャンルである。 この事実に基づいて,本アルゴリズムがワーナーのs rrとk-starsの存在を曖昧にするために,まずk-starsの隣り合うリストを提案する。 そこで本研究では,絶対値補正手法とk-starsサンプリング手法を提案し,推定誤差をさらに低減する。 最後に,2ラウンドのユーザ・コレクタインタラクション機構を用いて,ユーザのプライバシ保護に成功しながら, (p, q)-cliqueの数をカウントするk-stars LDPアルゴリズムを提案する。 理論解析と実験はともにエッジldpに基づくアルゴリズムよりもアルゴリズムの優越性を示した。

関連論文リスト

• Sketches-based join size estimation under local differential privacy [3.0945730947183203]
  機密データの結合サイズ推定は、プライバシー漏洩のリスクをもたらす。 ローカルディファレンシャルプライバシ(LDP)は、機密データを収集しながらプライバシを保存するソリューションである。 スケッチベースジョインサイズ推定のための LDPJoinSketch という新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-19T01:21:54Z)
• A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
  エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。 提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
  論文  参考訳（メタデータ） (2023-10-23T18:52:17Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。 近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。 ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
  論文  参考訳（メタデータ） (2023-09-21T21:51:55Z)
• Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling [6.599344783327054]
  グラフクラスタリングは、グラフの他の部分と疎結合なノードの集合を検出することを目的としている、ネットワーク分析における基本的なタスクである。 NPハードなパラメータ化クラスタリングフレームワークLambdaCCに対して,高速な近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-08T02:29:37Z)
• 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)
• Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank [74.53857412207034]
  本稿では,近似的なPPRを出力し,入力エッジに有界な感度を持つアルゴリズムを提案する。 我々の感度バウンドPPRは、差分プライベート(DP)PPRランキング、DPノード分類、DPノード埋め込みなど、グラフ学習のいくつかのツールのプライベートアルゴリズムを直接意味している。
  論文  参考訳（メタデータ） (2022-07-14T14:08:59Z)
• Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy [8.12606646175019]
  本稿では,DPRR (Degree-Preserving Randomized Response) と呼ばれる新しいLDPアルゴリズムを提案する。 我々のDPRRは、各ユーザの次数を保存するので、エッジ LDP を提供しながらグラフ構造を保ちます。 我々は,GNNのタスクとしてのグラフ分類に注目し,3つのソーシャルグラフデータセットを用いてDPRRを評価する。
  論文  参考訳（メタデータ） (2022-02-21T13:35:03Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2021-07-05T19:20:34Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)

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

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