論文の概要: Subgraph Counting with Local Node Differential Privacy

• arxiv url: http://arxiv.org/abs/2610.22278v1
• Date: Thu, 15 Oct 2026 17:39:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-17 06:09:33.231797
• Title: Subgraph Counting with Local Node Differential Privacy
• Title（参考訳）: ローカルノード差分プライバシによるサブグラフカウント
• Abstract要約: 局所ノード差分プライバシー(LNDP)の下での約数部分グラフの問題について検討する。 我々は,非インタラクティブな$(varepsilon,0)$-LNDPアルゴリズムを設計し,機密性のない$n$ノードグラフにおける$H$の発生をカウントする。 この結果はLNDPで近似可能であることが知られているネットワーク統計のタイプを大幅に拡張する。
• 参考スコア（独自算出の注目度）: 6.7576664180067105
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analyses of distributed social networks. We design a noninteractive $(\varepsilon,0)$-LNDP algorithm that, given any public $k$-node template graph $H$, counts occurrences of $H$ in a sensitive undirected $n$-node graph with additive error $O(n^{k-\frac{1}{2}}/\varepsilon^{k-1})$, for any constant $k$. We complement this algorithm with a lower bound showing that every noninteractive $(\varepsilon,δ)$-LNDP algorithm for counting copies of any $k$-node template graph with maximum degree greater than $1$ must have error $Ω(n^{k - \frac{1}{2}})$. Thus, our algorithm achieves optimal error for counting constant-size subgraphs, up to $\mathrm{poly}(1/\varepsilon)$ factors. Our results substantially expand the types of network statistics known to be approximable under LNDP: prior work considered only functions of the degree distribution. In addition, our lower bound yields the first known $\mathrm{poly}(n)$ gap between central and local node differential privacy when accuracy is required for all input graphs. Previous separations either only involved $\mathrm{poly}(1/\varepsilon)$ factors or only applied to promise problems.
• Abstract（参考訳）: 最近導入された分散ソーシャルネットワークの分析において、強力なプライバシー保証を強制するモデルであるLNDP(Local node differential privacy)の下で、およそ1つのサブグラフをカウントする問題について検討する。 我々は、任意のパブリックな$k$-nodeテンプレートグラフ$H$を与えられた場合、加算誤差$O(n^{k-\frac{1}{2}}/\varepsilon^{k-1})$で、感度のない$n$-nodeグラフにおける$H$の発生をカウントする非インタラクティブな$(\varepsilon,0)$-LNDPアルゴリズムを設計する。 我々はこのアルゴリズムを、任意の$k$-nodeテンプレートグラフのコピーを1ドル以上の最大値でカウントするすべての非インタラクティブ$(\varepsilon,δ)$-LNDPアルゴリズムがエラー$Ω(n^{k - \frac{1}{2}})$であることを示す下界で補完する。 そこで,本アルゴリズムは定数サイズの部分グラフを最大$\mathrm{poly}(1/\varepsilon)$因子にカウントする際の最適誤差を実現する。 この結果はLNDPで近似可能であることが知られているネットワーク統計のタイプを大幅に拡張し、以前の研究は次数分布の関数のみを考慮したものであった。 さらに、我々の下界は、すべての入力グラフに対して精度が要求されるとき、中央ノードと局所ノードの差分プライバシーの間のギャップを、最初の既知の$\mathrm{poly}(n)$にする。 以前の分離は $\mathrm{poly}(1/\varepsilon)$ factor か、あるいは、保証問題にのみ適用された。

関連論文リスト

• Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism [5.4971134662997025]
  SVTを多次元ベクトルに一般化する新しい一般化スパースベクトル法を定式化する。 アプリケーションとして、我々は以前よりもバウンダリが良い多くの重要なグラフ問題を解く。 我々は、$O(epsilon-1log n)$加法誤差と$O(n)$ラウンドでの乗算誤差のない$k$コア分解に対して、厳密なローカルエッジDPアルゴリズムを与える。
  論文  参考訳（メタデータ） (2025-08-04T08:26:58Z)
• Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
  我々は、$k$-core分解のための$eps$-edge差分秘密アルゴリズムが乗算誤差なしでコア数を出力し、$O(textlog(n)/eps)$加法誤差を示す。 これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
  論文  参考訳（メタデータ） (2023-12-12T20:09:07Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。 当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
  我々は,シャッフルDPおよびパンプライベートモデルにおいて,$tildeO_varepsilon(sqrtn)$とほぼ一致する誤差を保証するアルゴリズムを提案する。 我々のアルゴリズムは非常に単純で、離散的なラプラスノイズヒストグラムを後処理するだけである。
  論文  参考訳（メタデータ） (2022-10-27T05:11:00Z)
• Differentially Private Algorithms for Graphs Under Continual Observation [11.111949824180277]
  連続観測下でのグラフ問題に対する微分プライベートな動的グラフアルゴリズムについて検討する。 本稿では,加算誤差を因子的に改善する三角形数などの事象レベルの私的問題を提示する。 また、最小スパンニングツリー、最小カット、最密部分グラフ、最大マッチングのための$varepsilon$-differentially privateおよびpartial dynamic algorithmを与える。
  論文  参考訳（メタデータ） (2021-06-28T14:31:37Z)
• Maximizing Influence of Leaders in Social Networks [15.05158252504978]
  我々は、$n$ノードと$m$エッジを持つソーシャルネットワークにおける意見力学のDeGrootモデルに対するエッジ加算問題を考察する。 提案アルゴリズムは,100万以上のノードを持つ大規模ネットワークに対して,効率的かつ効果的であることを示す。
  論文  参考訳（メタデータ） (2021-06-11T02:31:46Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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