論文の概要: The Power of Graph Sparsification in the Continual Release Model

• arxiv url: http://arxiv.org/abs/2407.17619v2
• Date: Wed, 01 Jan 2025 20:31:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-03 14:32:54.624157
• Title: The Power of Graph Sparsification in the Continual Release Model
• Title（参考訳）: 連続リリースモデルにおけるグラフスカラー化の力
• Authors: Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, Felix Zhou,
• Abstract要約: 我々は,非プライベートなストリーミングおよび静的グラフアルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。 完全動的設定において、エッジプライバシーに対する加算誤差の低い境界を結論付ける。
• 参考スコア（独自算出の注目度）: 48.65946341463292
• License:
• Abstract: The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of edge updates where new private solutions are released after each update. Thus far, previously known edge-differentially private algorithms for most graph problems including densest subgraph and matchings in the continual release setting only output real-value estimates (not vertex subset solutions) and do not use sublinear space. Instead, they rely on computing exact graph statistics on the input [FHO21,SLMVC18]. In this paper, we leverage sparsification to address the above shortcomings for edge-insertion streams. Our edge-differentially private algorithms use sublinear space with respect to the number of edges in the graph while some also achieve sublinear space in the number of vertices in the graph. In addition, for the densest subgraph problem, we also output edge-differentially private vertex subset solutions; no previous graph algorithms in the continual release model output such subsets. We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms literature to achieve new results in the sublinear space, continual release setting. This includes algorithms for densest subgraph, maximum matching, as well as the first continual release $k$-core decomposition algorithm. We conclude with polynomial additive error lower bounds for edge-privacy in the fully dynamic setting.
• Abstract（参考訳）: 差分プライバシーのグラフ連続リリースモデルは、各更新後に新しいプライベートソリューションがリリースされるエッジアップデートのストリームの下で、グラフ問題に対する差分プライベートソリューションを作成しようとしている。 これまでのところ、最も密度の高い部分グラフや連続的なリリース設定におけるマッチングを含むほとんどのグラフ問題に対するエッジ微分プライベートアルゴリズムは、実値推定(頂点部分解ではない)を出力するだけで、部分線型空間を使用しない。 その代わりに、入力[FHO21, SLMVC18]の正確なグラフ統計の計算に依存する。 本稿では,エッジ挿入ストリームにおける上記の欠点に対処するためにスペーシフィケーションを利用する。 我々のエッジ微分プライベートアルゴリズムは、グラフ内のエッジ数に関して部分線型空間を使用し、またグラフ内の頂点数における部分線型空間も達成する。 さらに、最も高密度な部分グラフ問題に対しては、エッジ微分的にプライベートな頂点部分集合解も出力するが、連続的なリリースモデルにおける以前のグラフアルゴリズムではそのような部分集合を出力しない。 本研究では,非プライベートなストリーミングと静的グラフアルゴリズムによるスペーシフィケーション手法を新たに活用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。 これには、最も高密度な部分グラフのためのアルゴリズム、最大マッチング、および最初の連続リリースである$k$-core分解アルゴリズムが含まれる。 完全動的設定におけるエッジプライバシーに対する多項式加法誤差の下限を結論とする。

関連論文リスト

• Fully Dynamic Graph Algorithms with Edge Differential Privacy [1.4732811715354455]
  完全動的更新を伴う連続リリースの難易度設定において,グラフを解析するための差分プライベートアルゴリズムについて検討した。 これまでの研究では、挿入のみや削除のみを処理できる多くのグラフ問題に対して、差分プライベートなアルゴリズムが提案されてきた。 いくつかの基本グラフ問題に対して、事象レベルとアイテムレベルの完全動的アルゴリズムの誤差について、上下境界を与える。
  論文  参考訳（メタデータ） (2024-09-26T08:17:49Z)
• Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation [1.42693144277707]
  連続リリース設定においてノード差分プライバシーの標準概念を満たす最初のアルゴリズムについて述べる。 従来の作業は、グラフの最大度に強制されない約束を仮定することで、ノードプライベートな連続的なリリースに対処する。 我々のアルゴリズムは、いくつかの基本的なグラフ問題に対してスパースグラフ上で正確である。
  論文  参考訳（メタデータ） (2024-03-07T16:14:08Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• Maximal Independent Vertex Set applied to Graph Pooling [0.0]
  畳み込みニューラルネットワーク(CNN)は、畳み込みとプーリングによる画像分類の大きな進歩を可能にしている。 特に、画像プーリングは、接続された離散グリッドを同じ接続で縮小グリッドに変換し、画像のすべてのピクセルを考慮に入れられるようにします。 そこで本研究では,MIVSPoolと呼ばれる新しいプーリング手法を用いて,両方の問題を克服することを提案する。
  論文  参考訳（メタデータ） (2022-08-02T14:42:58Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか? 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
  論文  参考訳（メタデータ） (2021-06-08T16:10:36Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models? [13.572602792770288]
  ラプラシアン制約ガウス図形モデルの下でグラフを学習する問題を考察する。 我々は、大きな正規化パラメータが驚くほど完全なグラフ、すなわちエッジで接続されたすべてのエッジにつながることを示した。
  論文  参考訳（メタデータ） (2020-06-26T12:06:10Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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