論文の概要: Fully Dynamic Graph Algorithms with Edge Differential Privacy

• arxiv url: http://arxiv.org/abs/2409.17623v1
• Date: Thu, 26 Sep 2024 08:17:49 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-28 21:53:57.543622
• Title: Fully Dynamic Graph Algorithms with Edge Differential Privacy
• Title（参考訳）: エッジ微分プライバシーを持つフルダイナミックグラフアルゴリズム
• Authors: Sofya Raskhodnikova, Teresa Anna Steiner,
• Abstract要約: 完全動的更新を伴う連続リリースの難易度設定において,グラフを解析するための差分プライベートアルゴリズムについて検討した。 これまでの研究では、挿入のみや削除のみを処理できる多くのグラフ問題に対して、差分プライベートなアルゴリズムが提案されてきた。 いくつかの基本グラフ問題に対して、事象レベルとアイテムレベルの完全動的アルゴリズムの誤差について、上下境界を与える。
• 参考スコア（独自算出の注目度）: 1.4732811715354455
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates, where edges are inserted and deleted over time, and the algorithm is required to update the solution at every time step. Previous work has presented differentially private algorithms for many graph problems that can handle insertions only or deletions only (called partially dynamic algorithms) and obtained some hardness results for the fully dynamic setting. The only algorithms in the latter setting were for the edge count, given by Fichtenberger, Henzinger, and Ost (ESA 21), and for releasing the values of all graph cuts, given by Fichtenberger, Henzinger, and Upadhyay (ICML 23). We provide the first differentially private and fully dynamic graph algorithms for several other fundamental graph statistics (including the triangle count, the number of connected components, the size of the maximum matching, and the degree histogram), analyze their error and show strong lower bounds on the error for all algorithms in this setting. We study two variants of edge differential privacy for fully dynamic graph algorithms: event-level and item-level. We give upper and lower bounds on the error of both event-level and item-level fully dynamic algorithms for several fundamental graph problems. No fully dynamic algorithms that are private at the item-level (the more stringent of the two notions) were known before. In the case of item-level privacy, for several problems, our algorithms match our lower bounds.
• Abstract（参考訳）: 完全動的更新による連続リリースの難易度設定におけるグラフ解析のための差分プライベートアルゴリズムについて検討し,エッジの挿入と削除が時間とともに行われ,アルゴリズムは各ステップで解を更新する必要がある。 従来の研究は、挿入のみや削除のみを処理できる多くのグラフ問題に対して微分プライベートなアルゴリズム(部分動的アルゴリズムと呼ばれる)を示し、完全な動的設定に対していくつかの硬度結果を得た。 後者の設定における唯一のアルゴリズムは、Fichtenberger, Henzinger, Ost (ESA 21) のエッジカウントと、Fichtenberger, Henzinger, Upadhyay (ICML 23) のグラフカットの値の解放である。 我々は、他のいくつかの基本グラフ統計量(三角形数、連結成分数、最大マッチングのサイズ、度数ヒストグラムなど)に対して、最初の微分プライベートで完全に動的なグラフアルゴリズムを提供し、その誤差を分析し、この設定における全てのアルゴリズムの誤差に強い下界を示す。 完全動的グラフアルゴリズムにおけるエッジ差分プライバシーの2つの変種(事象レベルとアイテムレベル)について検討する。 いくつかの基本グラフ問題に対して、事象レベルとアイテムレベルの完全動的アルゴリズムの誤差について、上下境界を与える。 アイテムレベル(二つの概念のより厳密な部分)でプライベートな完全な動的アルゴリズムは以前には知られていなかった。 アイテムレベルのプライバシの場合、いくつかの問題に対して、アルゴリズムは低いバウンドにマッチします。

関連論文リスト

• The Power of Graph Sparsification in the Continual Release Model [48.65946341463292]
  本研究では,非プライベートなストリーミングアルゴリズムと静的グラフアルゴリズムによるスペーシング手法を新たに活用する。 エッジ微分プライベートアルゴリズムは、グラフ内のエッジの数に関して、サブ線形空間を使用する。 完全動的設定において、エッジプライバシーに対する加算誤差の低い境界を結論付ける。
  論文  参考訳（メタデータ） (2024-07-24T20:15:07Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation [1.42693144277707]
  連続リリース設定においてノード差分プライバシーの標準概念を満たす最初のアルゴリズムについて述べる。 従来の作業は、グラフの最大度に強制されない約束を仮定することで、ノードプライベートな連続的なリリースに対処する。 我々のアルゴリズムは、いくつかの基本的なグラフ問題に対してスパースグラフ上で正確である。
  論文  参考訳（メタデータ） (2024-03-07T16:14:08Z)
• Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
  本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。 この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。 我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-02-27T18:12:58Z)
• Improved Exact and Heuristic Algorithms for Maximum Weight Clique [1.2074552857379273]
  最大重量傾き問題の解法として,精度の向上とラベリングアルゴリズムを提案する。 提案アルゴリズムは, 局所グラフ構造を用いた新しいデータ削減規則を用いて, 成功した手法をインターリーブする。 我々は,アルゴリズムを合成および実世界のグラフで評価し,ほとんどの入力において,その技術の現状よりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-01T14:02:06Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。 我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
  論文  参考訳（メタデータ） (2021-12-09T02:27:52Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか? 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
  論文  参考訳（メタデータ） (2021-06-08T16:10:36Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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