論文の概要: 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つの変種(事象レベルとアイテムレベル)について検討する。 いくつかの基本グラフ問題に対して、事象レベルとアイテムレベルの完全動的アルゴリズムの誤差について、上下境界を与える。 アイテムレベル(二つの概念のより厳密な部分)でプライベートな完全な動的アルゴリズムは以前には知られていなかった。 アイテムレベルのプライバシの場合、いくつかの問題に対して、アルゴリズムは低いバウンドにマッチします。

関連論文リスト

• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs [0.13654846342364307]
  グラフ上に定義された2-局所ハミルトニアンを最適化する2つの変分アルゴリズムを設計する。 無限大極限におけるランダム正則グラフに対して,これらのアルゴリズムによって達成されるエネルギーを高い確率で解析する公式を開発する。 アルゴリズムの5つの層だけで、QMCの基底状態エネルギーの1.62%の誤差を無限の1Dリングで生成できることが示される。
  論文  参考訳（メタデータ） (2024-12-19T18:27:39Z)
• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。 我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。 我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
  論文  参考訳（メタデータ） (2024-12-03T18:36:45Z)
• 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)
• 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)
• 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)

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

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