論文の概要: Practical and Accurate Local Edge Differentially Private Graph Algorithms

• arxiv url: http://arxiv.org/abs/2506.20828v1
• Date: Wed, 25 Jun 2025 20:54:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-27 19:53:09.886229
• Title: Practical and Accurate Local Edge Differentially Private Graph Algorithms
• Title（参考訳）: 局所エッジ差分グラフアルゴリズムの実用化と精度向上
• Authors: Pranay Mundra, Charalampos Papamanthou, Julian Shun, Quanquan C. Liu,
• Abstract要約: ローカルディファレンシャルプライバシ(LDP)は、サードパーティのエンティティが信頼されていない個々のレベルでのプライバシを強制する。 我々は、kコア分解と三角形カウントという2つの基本グラフ統計量に対して、新しい LDP アルゴリズムを導入する。
• 参考スコア（独自算出の注目度）: 11.593320678280824
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The rise of massive networks across diverse domains necessitates sophisticated graph analytics, often involving sensitive data and raising privacy concerns. This paper addresses these challenges using local differential privacy (LDP), which enforces privacy at the individual level, where no third-party entity is trusted, unlike centralized models that assume a trusted curator. We introduce novel LDP algorithms for two fundamental graph statistics: k-core decomposition and triangle counting. Our approach leverages input-dependent private graph properties, specifically the degeneracy and maximum degree of the graph, to improve theoretical utility. Unlike prior methods, our error bounds are determined by the maximum degree rather than the total number of edges, resulting in significantly tighter guarantees. For triangle counting, we improve upon the work of Imola, Murakami, and Chaudhury~\cite{IMC21locally, IMC21communication}, which bounds error in terms of edge count. Instead, our algorithm achieves bounds based on graph degeneracy by leveraging a private out-degree orientation, a refined variant of Eden et al.'s randomized response technique~\cite{ELRS23, and a novel analysis, yielding stronger guarantees than prior work. Beyond theoretical gains, we are the first to evaluate local DP algorithms in a distributed simulation, unlike prior work tested on a single processor. Experiments on real-world graphs show substantial accuracy gains: our k-core decomposition achieves errors within 3x of exact values, far outperforming the 131x error in the baseline of Dhulipala et al.~\cite{DLRSSY22}. Our triangle counting algorithm reduces multiplicative approximation errors by up to six orders of magnitude, while maintaining competitive runtime.
• Abstract（参考訳）: 多様なドメインにわたる大規模ネットワークの台頭は、高度なグラフ分析を必要とし、しばしば機密データやプライバシー上の懸念を提起する。 本稿では、信頼できるキュレーターを仮定する集中型モデルとは異なり、個々のレベルでのプライバシを強制するローカルディファレンシャルプライバシ(LDP)を用いて、これらの課題に対処する。 我々は、kコア分解と三角形カウントという2つの基本グラフ統計量に対して、新しい LDP アルゴリズムを導入する。 提案手法は、入力依存のプライベートグラフ特性、特にグラフの退化性と最大度を活用して、理論的有用性を向上させる。 従来の手法とは異なり、誤差境界はエッジの総数よりも最大度で決定されるため、より厳密な保証が得られる。 三角形の計数には、Imola, Murakami, and Chaudhury~\cite{IMC21 locally, IMC21communication} が用いられる。 そこで,本アルゴリズムは,個人用外向方向,Eden et al's randomized response technique~\cite{ELRS23,および新規解析を利用して,グラフの縮退性に基づくバウンダリを実現する。 理論的なゲインの他に、我々は分散シミュレーションでローカルDPアルゴリズムを最初に評価する。 我々のkコア分解は、Dhulipala et al ~\cite{DLRSSY22} のベースラインにおける131x誤差よりもはるかに優れている。 我々の三角形計数アルゴリズムは、競合ランタイムを維持しながら、乗法近似誤差を最大6桁まで削減する。

関連論文リスト

• Pruning Spurious Subgraphs for Graph Out-of-Distribtuion Generalization [90.32406785945223]
  PrunEは,OODの一般化性を改善するために急激なエッジを除去する最初のプルーニングベースグラフOOD法である。 PrunE は2つの正規化項を使い、1) グラフサイズ制約は非形式的なスパイラスエッジを除外し、2) スパイラスエッジの発生をさらに抑制するために、$epsilon$-probability アライメントを使用する。
  論文  参考訳（メタデータ） (2025-06-06T10:34:48Z)
• On the Price of Differential Privacy for Hierarchical Clustering [21.64775530337936]
  本稿では, エッジレベルのDP設定において, 既知の可視性よりもはるかに高い近似性を示す, 重み付きプライバシモデルにおける新しいアルゴリズムを提案する。 以上の結果から,提案アルゴリズムはコストの面では良好に動作し,大規模グラフに対するスケーラビリティも良好であることがわかった。
  論文  参考訳（メタデータ） (2025-04-22T04:39:40Z)
• Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference [18.101059380671582]
  ネットワーク干渉下でのマルチアームバンディットについて検討する。 これにより指数的に大きな作用空間が生じる。 本稿では,局所グラフ構造を用いて後悔を最小限に抑える新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-03-10T17:25:24Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  我々は,非プライベートなストリーミングと静的アルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。 これには、最も高密度な部分グラフのためのアルゴリズム、最大マッチング、および最初の連続リリース$k$-core分解アルゴリズムが含まれる。
  論文  参考訳（メタデータ） (2024-07-24T20:15:07Z)
• Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust [5.037313459134419]
  本稿では,ErdHos-R'enyiランダムグラフのエッジ密度を推定するアルゴリズムについて述べる。 我々は,アルゴリズムの誤り率を対数的因子まで最適とする情報理論的下界を証明した。
  論文  参考訳（メタデータ） (2024-05-26T18:59:44Z)
• Differentially Private Domain Adaptation with Theoretical Guarantees [46.37771025567305]
  多くのアプリケーションでは、ラベル付きデータの処分におけるラベル付きデータはプライバシー上の制約を受けており、比較的制限されている。 これは、パブリックソースからプライベートターゲットドメインへのドメイン適応を監督する現代の問題である。 我々は、理論的な学習保証の恩恵を受けるために、一般の学習者を利用する。
  論文  参考訳（メタデータ） (2023-06-15T04:03:06Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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