論文の概要: Local Node Differential Privacy
- arxiv url: http://arxiv.org/abs/2602.15802v1
- Date: Tue, 17 Feb 2026 18:41:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-18 16:03:18.164626
- Title: Local Node Differential Privacy
- Title（参考訳）: ローカルノードの差分プライバシー
- Authors: Sofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov,
- Abstract要約: グラフのノード差分プライバシをプライベートデータ分析の局所モデルで検討する。
LNDPと呼ばれるこのモデルでは、各ノードが独自のエッジリストを見て、この入力に対してローカルなランダム化器の出力を解放する。
この設定のための新しいアルゴリズムフレームワークを開発し、任意の線形クエリを正確に答えることを可能にする。
- 参考スコア（独自算出の注目度）: 6.7576664180067105
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We initiate an investigation of node differential privacy for graphs in the local model of private data analysis. In our model, dubbed LNDP, each node sees its own edge list and releases the output of a local randomizer on this input. These outputs are aggregated by an untrusted server to obtain a final output. We develop a novel algorithmic framework for this setting that allows us to accurately answer arbitrary linear queries on a blurry approximation of the input graph's degree distribution. For some natural problems, the resulting algorithms match the accuracy achievable with node privacy in the central model, where data are held and processed by a trusted server. We also prove lower bounds on the error required by LNDP that imply the optimality of our algorithms for several fundamental graph statistics. We then lift these lower bounds to the interactive LNDP setting, demonstrating the optimality of our algorithms even when constantly many rounds of interaction are permitted. Obtaining our lower bounds requires new approaches, since those developed for the usual local model do not apply to the inherently overlapping inputs that arise from graphs. Finally, we prove structural results that reveal qualitative differences between local node privacy and the standard local model for tabular data.
- Abstract（参考訳）: 我々は,グラフのノード差分プライバシーについて,個人データ分析の局所モデルを用いて調査を開始する。
LNDPと呼ばれるこのモデルでは、各ノードが独自のエッジリストを見て、この入力に対してローカルなランダム化器の出力を解放する。
これらの出力は、信頼できないサーバによって集約され、最終的な出力を得る。
入力グラフの次数分布のぼやけた近似に基づいて任意の線形クエリを正確に答えることのできる,この設定のための新しいアルゴリズムフレームワークを開発した。
いくつかの自然な問題に対して、結果のアルゴリズムは、信頼されたサーバによってデータが保持され処理される中央モデルのノードプライバシと達成可能な精度に一致します。
また、いくつかの基本グラフ統計量に対するアルゴリズムの最適性を示唆するLNDPの誤差の低い境界を証明した。
次に、これらの下位境界を対話型LNDP設定に引き上げ、連続的に多くの相互作用が許される場合でも、アルゴリズムの最適性を示す。
なぜなら、通常の局所モデルのために開発されたものは、グラフから生じる本質的に重なり合う入力には適用されないからである。
最後に、局所ノードプライバシと表データの標準ローカルモデルとの質的な違いを示す構造的結果を示す。
関連論文リスト
- Benchmarking Fraud Detectors on Private Graph Data [70.4654745317714]
現在、多くの種類の不正は、グラフ上で動く自動検出アルゴリズムによって部分的に管理されている。
データ保有者が不正検知器の開発を第三者にアウトソースしようとするシナリオを考察する。
サードパーティは、不正検出をデータ保持者に送信し、これらのアルゴリズムをプライベートデータセットで評価し、その結果を公表する。
本システムに対する現実的なプライバシ攻撃を提案し,評価結果のみに基づいて個人データの匿名化を可能にする。
論文 参考訳（メタデータ） (2025-07-30T03:20:15Z) - Practical and Accurate Local Edge Differentially Private Graph Algorithms [11.49857418691547]
我々は、kコア分解と三角形カウントという2つの基本グラフ統計量に対して、新しい LDP アルゴリズムを導入する。
提案手法は、入力依存のプライベートグラフ特性、特にグラフの退化性と最大度を活用して、理論的有用性を向上させる。
我々のkコア分解は正確な値の3倍以内の誤差を達成し、Dhulipalaなどのベースラインで131倍の誤差をはるかに上回っている。
論文 参考訳（メタデータ） (2025-06-25T20:54:07Z) - Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
我々は,非プライベートなストリーミングと静的アルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。
これには、最も高密度な部分グラフのためのアルゴリズム、最大マッチング、および最初の連続リリース$k$-core分解アルゴリズムが含まれる。
論文 参考訳（メタデータ） (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) - Graph Learning Across Data Silos [10.448384704100684]
本稿では,スムーズなグラフ信号からグラフトポロジを推定する問題を考える。
データは分散クライアントにあり、プライバシー上の懸念などの要因により、ローカルクライアントを去ることは禁じられている。
本稿では,各ローカルクライアントに対してパーソナライズされたグラフと,全クライアントに対して単一のコンセンサスグラフを共同で学習する,自動重み付き多重グラフ学習モデルを提案する。
論文 参考訳（メタデータ） (2023-01-17T02:14:57Z) - Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging [20.39986955578245]
ローカルディファレンシャルプライバシ(LDP)の緩和であるペアワイズネットワークディファレンシャルプライバシを導入する。
我々は、局所勾配降下ステップとゴシップ平均化を交互に交互に行う、微分プライベートな分散最適化アルゴリズムを導出する。
我々のアルゴリズムは,グラフ内のノード間距離の関数として,プライバシー保証を増幅することを示す。
論文 参考訳（メタデータ） (2022-06-10T13:32:35Z) - Scaling Structured Inference with Randomization [64.18063627155128]
本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。
我々の手法は古典的DPベースの推論に広く適用できる。
また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
論文 参考訳（メタデータ） (2021-12-07T11:26:41Z) - Private Weighted Random Walk Stochastic Gradient Descent [21.23973736418492]
グラフ内のノードに分散したデータを分散する分散学習環境を考える。
本稿では,データの一様サンプリングと重要サンプリングという2種類のランダムウォークに基づく2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-03T16:52:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。