論文の概要: Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation

• arxiv url: http://arxiv.org/abs/2403.04630v1
• Date: Thu, 7 Mar 2024 16:14:08 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-17 16:51:18.972306
• Title: Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation
• Title（参考訳）: 時間を考慮した予測:連続観測による真にノード固有のグラフ統計
• Authors: Palak Jain, Adam Smith, Connor Wagaman,
• Abstract要約: 連続リリース設定においてノード差分プライバシーの標準概念を満たす最初のアルゴリズムについて述べる。 従来の作業は、グラフの最大度に強制されない約束を仮定することで、ノードプライベートな連続的なリリースに対処する。 我々のアルゴリズムは、いくつかの基本的なグラフ問題に対してスパースグラフ上で正確である。
• 参考スコア（独自算出の注目度）: 1.42693144277707
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We describe the first algorithms that satisfy the standard notion of node-differential privacy in the continual release setting (i.e., without an assumed promise on input streams). Previous work addresses node-private continual release by assuming an unenforced promise on the maximum degree in a graph; indeed, the algorithms from these works exhibit blatant privacy violations when the degree bound is not met. Our algorithms are accurate on sparse graphs, for several fundamental graph problems: counting edges, triangles, other subgraphs, and connected components; and releasing degree histograms. Our unconditionally private algorithms generally have optimal error, up to polylogarithmic factors and lower-order terms. We provide general transformations that take a base algorithm for the continual release setting, which need only be private for streams satisfying a promised degree bound, and produce an algorithm that is unconditionally private yet mimics the base algorithm when the stream meets the degree bound (and adds only linear overhead to the time and space complexity of the base algorithm). To do so, we design new projection algorithms for graph streams, based on the batch-model techniques of Day et al. 2016 and Blocki et al. 2013, which modify the stream to limit its degree. Our main technical innovation is to show that the projections are stable -- meaning that similar input graphs have similar projections -- when the input stream satisfies a privately testable safety condition. Our transformation then follows a novel online variant of the Propose-Test-Release framework (Dwork and Lei, 2009), privately testing the safety condition before releasing output at each step.
• Abstract（参考訳）: 本稿では,ノード差分プライバシの標準概念を連続的なリリース設定で満たすアルゴリズムについて述べる。 従来の作業は、グラフの最大度に対して強制されない約束を仮定することで、ノードプライベートなリリースに対処する。 我々のアルゴリズムは疎グラフ上で正確であり、エッジ、三角形、その他の部分グラフ、連結成分の計数、等級ヒストグラムの放出など、いくつかの基本的なグラフ問題に対して正確である。 我々の非条件プライベートアルゴリズムは一般に、多対数係数と低次項を含む最適誤差を持つ。 我々は、約束される次数境界を満たすストリームに対してのみプライベートである必要のある連続リリース設定のベースアルゴリズムを基本変換とし、ストリームが次数境界を満たすときにベースアルゴリズムを非条件で模倣するアルゴリズムを生成する(そして、ベースアルゴリズムの時間と空間の複雑さに線形オーバーヘッドのみを加える)。 そこで我々は,Day et al 2016とBlocki et al 2013のバッチモデルに基づく,グラフストリームの新しいプロジェクションアルゴリズムを設計した。 我々の主要な技術的革新は、入力ストリームがプライベートにテスト可能な安全条件を満たすとき、プロジェクションが安定していること(つまり、類似の入力グラフが同様のプロジェクションを持っていること)を示すことです。 当社のトランスフォーメーションは、Propose-Test-Releaseフレームワーク(Dwork and Lei, 2009)の新たなオンライン版に従い、各ステップで出力をリリースする前に、安全条件をプライベートにテストします。

関連論文リスト

• Fully Dynamic Graph Algorithms with Edge Differential Privacy [1.4732811715354455]
  完全動的更新を伴う連続リリースの難易度設定において,グラフを解析するための差分プライベートアルゴリズムについて検討した。 これまでの研究では、挿入のみや削除のみを処理できる多くのグラフ問題に対して、差分プライベートなアルゴリズムが提案されてきた。 いくつかの基本グラフ問題に対して、事象レベルとアイテムレベルの完全動的アルゴリズムの誤差について、上下境界を与える。
  論文  参考訳（メタデータ） (2024-09-26T08:17:49Z)
• 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)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs [3.707290781951909]
  観測データから因果効果を推定することは経験科学の基本的な課題である。 本論文は, 観測媒介者を用いて, 保存されていない共同設立者の存在下においても, 因果関係を識別できる古典的な手法である, 正面調整に焦点を当てたものである。
  論文  参考訳（メタデータ） (2022-11-29T18:44:03Z)
• Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
  三角形の数と4サイクルを推定するための,データ駆動型ワンパスストリーミングアルゴリズムを提案する。 従来の"古典的"アルゴリズムを改善するために、ストリーム要素の特定の特性を予測できるトレーニングされたオラクルを使用します。 提案手法は,従来のマルチパスおよびランダム順序ストリーミングアルゴリズムを特殊なケースとみなすことができるため,従来の"古典的"ストリーミングアルゴリズムの取り組みを拡大する。
  論文  参考訳（メタデータ） (2022-03-17T19:26:00Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか? 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
  論文  参考訳（メタデータ） (2021-06-08T16:10:36Z)
• Policy Gradient for Continuing Tasks in Non-stationary Markov Decision Processes [112.38662246621969]
  強化学習は、マルコフ決定プロセスにおいて期待される累積報酬を最大化するポリシーを見つけることの問題を考える。 我々は、ポリシーを更新するために上昇方向として使用する値関数の偏りのないナビゲーション勾配を計算する。 ポリシー勾配型アルゴリズムの大きな欠点は、定常性の仮定が課せられない限り、それらがエピソジックなタスクに限定されていることである。
  論文  参考訳（メタデータ） (2020-10-16T15:15:42Z)

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

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