論文の概要: The Power of Graph Sparsification in the Continual Release Model
- arxiv url: http://arxiv.org/abs/2407.17619v1
- Date: Wed, 24 Jul 2024 20:15:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-26 15:57:05.158098
- 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of updates where new private solutions are released after each update. Streaming graph algorithms in the non-private literature also produce (approximately) accurate solutions when provided updates in a stream, but they additionally try to achieve two other goals: 1) output vertex or edge subsets as approximate solutions to the problem (not just real-valued estimates) and 2) use space that is sublinear in the number of edges or the number of vertices. Thus far, all previously known edge-differentially private algorithms for graph problems in the continual release setting do not meet the above benchmarks. Instead, they require computing exact graph statistics on the input [SLMVC18, FHO21, JSW24]. In this paper, we leverage sparsification to address the above shortcomings. 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 most of our problems, we also output differentially private vertex subsets. We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms literature and achieve new results in the sublinear space, continual release setting for a variety of problems including densest subgraph, $k$-core decomposition, maximum matching, and vertex cover. In addition to our edge-differential privacy results, we use graph sparsification based on arboricity to obtain a set of results in the node-differential privacy setting, illustrating a new connection between sparsification and privacy beyond minimizing space. We conclude with polynomial additive error lower bounds for edge-privacy in the fully dynamic setting.
- Abstract（参考訳）: 差分プライバシーのグラフ継続リリースモデルは、更新毎に新しいプライベートソリューションがリリースされる一連の更新の下で、グラフ問題に対する差分プライベートソリューションを作成しようとしている。
プライベートでない文献でグラフアルゴリズムをストリーミングすることは、ストリームに更新を提供したときに(およそ)正確なソリューションも生成しますが、他にも2つの目標を達成しようと試みています。
1)問題の近似解として頂点またはエッジ部分集合を出力し(実測値だけでなく)、
2) エッジ数や頂点数に準線形な空間を使用する。
これまでのところ、連続リリース設定におけるグラフ問題に対するエッジ微分プライベートアルゴリズムはすべて、上記のベンチマークを満たしていない。
その代わりに、入力[SLMVC18, FHO21, JSW24]の正確なグラフ統計を計算する必要がある。
本稿では,スパシフィケーションを活用し,上記の問題点に対処する。
我々のエッジ微分プライベートアルゴリズムは、グラフ内のエッジ数に関して部分線型空間を使用し、またグラフ内の頂点数における部分線型空間も達成する。
さらに、ほとんどの問題に対して、微分的にプライベートな頂点部分集合も出力する。
我々は,非プライベートなストリーミングアルゴリズムと静的グラフアルゴリズムによるスペーシフィケーション手法を新たに活用し,高密度部分グラフ,$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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。