論文の概要: 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（参考訳）: デンセスト部分グラフ検出は基礎的なグラフマイニング問題であり、多くの応用がある。 大規模ネットワークにおける最も密集した部分グラフを見つけるための効率的なアルゴリズムには多くの研究があった。 しかし、多くのドメインでは、ネットワークはプライベートであり、最も密度の高いサブグラフを返すと、ネットワークに関する情報が明らかになる。 差分プライバシーはそのような設定を扱うための強力なフレームワークである。 本稿では,グラフのエッジがプライベートなエッジプライバシモデルにおいて,最も密度の高いサブグラフ問題について検討する。 この問題に対する最初の逐次および並列微分プライベートアルゴリズムを提案する。 我々は,アルゴリズムが付加近似を保証することを示す。 我々は,本アルゴリズムを多数の実世界のネットワーク上で評価し,ネットワークの密度が高い場合に適切なプライバシーと精度のトレードオフを観測する。

関連論文リスト

• The Power of Graph Sparsification in the Continual Release Model [48.65946341463292]
  本研究では,非プライベートなストリーミングアルゴリズムと静的グラフアルゴリズムによるスペーシング手法を新たに活用する。 エッジ微分プライベートアルゴリズムは、グラフ内のエッジの数に関して、サブ線形空間を使用する。 完全動的設定において、エッジプライバシーに対する加算誤差の低い境界を結論付ける。
  論文  参考訳（メタデータ） (2024-07-24T20:15:07Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• A Unifying Privacy Analysis Framework for Unknown Domain Algorithms in Differential Privacy [1.5773159234875098]
  我々は、未知のドメイン上でヒストグラムをリリースするための、既存の微分プライベートアルゴリズムのいくつかを再検討する。 未知の領域でヒストグラムをリリースする主な実用的利点は、アルゴリズムが欠落したラベルを埋める必要がないことである。 いくつかの既存アルゴリズムのプライバシー分析のための統一的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-09-17T05:47:33Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  しかし、スパースデータセットを共有するという点では、差分プライバシーがプライバシのゴールドスタンダードとして浮上している。 本研究では、スムーズな$k$匿名性(スムーズな$k$匿名性)と、スムーズな$k$匿名性(スムーズな$k$匿名性)を提供する単純な大規模アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-07-13T17:09:25Z)
• 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)

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

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