論文の概要: 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分解,最大マッチング,頂点被覆などの様々な問題に対する連続的なリリース設定,サブ線形空間における新しい結果を実現する。
エッジ差分プライバシー結果に加えて、ノード差分プライバシー設定における一連の結果を得るために、空白度に基づくグラフスペーシフィケーションを使用し、空間の最小化を超えて、スペーシフィケーションとプライバシの新たな接続を図示します。
完全動的設定におけるエッジプライバシーに対する多項式加法誤差の下限を結論とする。
関連論文リスト
- Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation [1.42693144277707]
連続リリース設定においてノード差分プライバシーの標準概念を満たす最初のアルゴリズムについて述べる。
従来の作業は、グラフの最大度に強制されない約束を仮定することで、ノードプライベートな連続的なリリースに対処する。
我々のアルゴリズムは、いくつかの基本的なグラフ問題に対してスパースグラフ上で正確である。
論文 参考訳（メタデータ） (2024-03-07T16:14:08Z) - GraphPub: Generation of Differential Privacy Graph with High
Availability [21.829551460549936]
差分プライバシー(DP)は、グラフデータのプライバシーを保護する一般的な方法である。
グラフデータの複雑なトポロジ構造のため、グラフにDPを適用すると、GNNモデルのメッセージパッシングや集約に影響を及ぼすことが多い。
グラフトポロジを保護しつつ,データの可用性が基本的に変化しないことを保証するグラフパブリッシャ(GraphPub)を提案する。
論文 参考訳（メタデータ） (2024-02-28T20:02:55Z) - Ising on the Graph: Task-specific Graph Subsampling via the Ising Model [0.8192907805418581]
本稿では,ノードあるいはエッジ上で定義されたIsingモデルを用いて,グラフ構造をサブサンプリングする手法を提案する。
エンド・ツー・エンドの方法で特定の下流タスクに対するグラフの削減方法を学ぶことができるため、我々のアプローチはタスク固有である。
論文 参考訳（メタデータ） (2024-02-15T18:58:18Z) - 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) - GraphMI: Extracting Private Graph Data from Graph Neural Networks [59.05178231559796]
GNNを反転させてトレーニンググラフのプライベートグラフデータを抽出することを目的とした textbfGraph textbfModel textbfInversion attack (GraphMI) を提案する。
具体的には,グラフ特徴の空間性と滑らかさを保ちながら,グラフエッジの離散性に対処する勾配モジュールを提案する。
エッジ推論のためのグラフトポロジ、ノード属性、ターゲットモデルパラメータを効率的に活用するグラフ自動エンコーダモジュールを設計する。
論文 参考訳（メタデータ） (2021-06-05T07:07:52Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳（メタデータ） (2020-10-20T05:54:31Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。