論文の概要: Differentially Private Densest Subgraph Detection
- arxiv url: http://arxiv.org/abs/2105.13287v1
- Date: Thu, 27 May 2021 16:36:03 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-28 16:09:23.665395
- Title: Differentially Private Densest Subgraph Detection
- Title(参考訳): 差分プライベートデンセストサブグラフ検出
- Authors: Dung Nguyen and Anil Vullikanti
- Abstract要約: 多くのドメインでは、ネットワークはプライベートであり、最も密度の高いサブグラフを返すと、ネットワークに関する情報が明らかになる。
本稿では,グラフのエッジがプライベートなエッジプライバシモデルにおいて,最も密度の高いサブグラフ問題について検討する。
我々は,アルゴリズムが付加近似を保証することを示す。
- 参考スコア(独自算出の注目度): 8.290536618677235
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Densest subgraph detection is a fundamental graph mining problem, with a
large number of applications. There has been a lot of work on efficient
algorithms for finding the densest subgraph in massive networks. However, in
many domains, the network is private, and returning a densest subgraph can
reveal information about the network. Differential privacy is a powerful
framework to handle such settings. We study the densest subgraph problem in the
edge privacy model, in which the edges of the graph are private. We present the
first sequential and parallel differentially private algorithms for this
problem. We show that our algorithms have an additive approximation guarantee.
We evaluate our algorithms on a large number of real-world networks, and
observe a good privacy-accuracy tradeoff when the network has high density.
- Abstract(参考訳): デンセスト部分グラフ検出は基礎的なグラフマイニング問題であり、多くの応用がある。
大規模ネットワークにおける最も密集した部分グラフを見つけるための効率的なアルゴリズムには多くの研究があった。
しかし、多くのドメインでは、ネットワークはプライベートであり、最も密度の高いサブグラフを返すと、ネットワークに関する情報が明らかになる。
差分プライバシーはそのような設定を扱うための強力なフレームワークである。
本稿では,グラフのエッジがプライベートなエッジプライバシモデルにおいて,最も密度の高いサブグラフ問題について検討する。
この問題に対する最初の逐次および並列微分プライベートアルゴリズムを提案する。
我々は,アルゴリズムが付加近似を保証することを示す。
我々は,本アルゴリズムを多数の実世界のネットワーク上で評価し,ネットワークの密度が高い場合に適切なプライバシーと精度のトレードオフを観測する。
関連論文リスト
- Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳(メタデータ) (2024-01-12T17:57:07Z) - Hub-aware Random Walk Graph Embedding Methods for Classification [68.8204255655161]
ノード分類問題に特化して設計されたランダムウォークに基づく2つの新しいグラフ埋め込みアルゴリズムを提案する。
提案手法は,実世界のネットワークの埋め込みを訓練した3つの分類アルゴリズムの分類性能を解析して実験的に評価する。
論文 参考訳(メタデータ) (2022-09-15T20:41:18Z) - Degree-Based Random Walk Approach for Graph Embedding [0.0]
計算量が少なく,ノード接続性に配慮した一様サンプリング手法を提案する。
提案アルゴリズムの利点は,大規模グラフに適用した場合にさらに向上する。
論文 参考訳(メタデータ) (2021-10-21T19:16:16Z) - Deep Fraud Detection on Non-attributed Graph [61.636677596161235]
グラフニューラルネットワーク(GNN)は不正検出に強い性能を示している。
ラベル付きデータは大規模な産業問題、特に不正検出には不十分である。
よりラベルのないデータを活用するための新しいグラフ事前学習戦略を提案する。
論文 参考訳(メタデータ) (2021-10-04T03:42:09Z) - Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか?
本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
論文 参考訳(メタデータ) (2021-06-08T16:10:36Z) - The Generalized Mean Densest Subgraph Problem [30.33731479053404]
1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。
我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。
我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
論文 参考訳(メタデータ) (2021-06-02T02:58:35Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-06-24T11:37:33Z) - Locally Private Graph Neural Networks [12.473486843211573]
ノードデータプライバシ(ノードデータプライバシ)の問題として,グラフノードが機密性の高いデータをプライベートに保持する可能性について検討する。
我々は、正式なプライバシー保証を備えたプライバシー保護アーキテクチャに依存しないGNN学習アルゴリズムを開発した。
実世界のデータセット上で行った実験は、我々の手法が低プライバシー損失で満足度の高い精度を維持することができることを示した。
論文 参考訳(メタデータ) (2020-06-09T22:36:06Z) - Analyzing Neural Networks Based on Random Graphs [77.34726150561087]
様々なタイプのランダムグラフに対応するアーキテクチャを用いて,ニューラルネットワークの大規模評価を行う。
古典的な数値グラフ不変量は、それ自体が最良のネットワークを選び出すことができない。
また、主に短距離接続を持つネットワークは、多くの長距離接続が可能なネットワークよりも性能が良いことも見出した。
論文 参考訳(メタデータ) (2020-02-19T11:04:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。