論文の概要: Differentially Private Range Subgraph Counting

• arxiv url: http://arxiv.org/abs/2606.08179v1
• Date: Sat, 06 Jun 2026 13:56:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:05.895483
• Title: Differentially Private Range Subgraph Counting
• Title（参考訳）: Differentially Private Range Subgraph Counting
• Authors: Xian Chen, Ruobing Bai, Pan Peng,
• Abstract要約: グラフ解析におけるグラフカウントは基本的な問題である。 目的は、誘導されたサブグラフ内の固定パターングラフの発生をプライベートにカウントすることである。 加算誤差の少ないDPRSCのアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 5.978091728687093
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Subgraph counting is a fundamental problem in graph analysis. Motivated by practical scenarios where graph analytics are performed on subgraphs induced by selected vertices -- rather than on the entire graph -- and by growing privacy concerns, we initiate the study of differentially private range subgraph counting (DPRSC). The goal is to privately count occurrences of a fixed pattern graph within induced subgraphs defined by multi-dimensional attribute ranges. Unlike classical point counting, subgraph counting is inherently nonlinear and exhibits high sensitivity: a single edge modification can affect many subgraph occurrences. We present the first efficient algorithms for DPRSC with small additive error. Our approach introduces a subgraph projection that reduces DPRSC to weighted orthogonal range counting, enabling the use of range trees and local sensitivity estimation to achieve accurate private query answering. We complement our algorithms with matching lower bounds, obtained by reducing reconstruction attacks to DPRSC and leveraging discrepancy theory. In particular, we show that any differentially private algorithm for DPRSC must incur additive error exponential in the dimension. Empirical evaluations demonstrate that our algorithms significantly outperform baseline methods in accuracy and runtime while maintaining strong privacy guarantees.
• Abstract（参考訳）: グラフ解析におけるグラフカウントは基本的な問題である。 グラフ分析は,グラフ全体ではなく,選択された頂点によって誘導されるサブグラフ上で実施される,という現実的なシナリオによって動機付けられ,プライバシー上の懸念が高まることにより,差分的にプライベートな範囲のサブグラフカウント(DPRSC)の研究が開始される。 目的は、多次元の属性範囲で定義された誘導サブグラフ内の固定パターングラフの発生をプライベートにカウントすることである。 古典的な点カウントとは異なり、部分グラフカウントは本質的に非線形であり、高い感度を示す。 加算誤差の少ないDPRSCのアルゴリズムを提案する。 提案手法では, DPRSCを重み付き直交範囲カウントに還元し, 範囲木の利用と局所感度推定により, 高精度なプライベートクエリ応答を実現する。 我々は,DPRSCに対する再構成攻撃を減らし,不一致理論を活用することにより,アルゴリズムを一致した下界で補完する。 特に、DPRSCの微分プライベートアルゴリズムは、その次元において指数的に加法誤差を発生させなければならないことを示す。 経験的評価により,我々のアルゴリズムは高いプライバシー保証を維持しつつ,精度と実行時のベースライン手法を著しく上回っていることが示された。

関連論文リスト

• Sparse Graph Learning from Sparse Data via Fiedler Number Maximization [16.83442282933831]
  ここでは、RNにおける信号 x の信号次元 N よりも観測数 K がかなり小さくなり、基礎となる分布が不明であるスパースデータからスパースグラフと連結グラフを学習することを目的とする。 スパースグラフ学習目的において、フィドラー数(連結性を定量化するグラフラプラシア行列の第2固有値)を頑健な正規化項として組み込む。 シミュレーション実験により、ファイドラー数はスパースグラフ推定を強固にし、従来のスパースグラフ学習アルゴリズムより優れていることが示された。
  論文  参考訳（メタデータ） (2026-04-28T21:40:39Z)
• Practical and Accurate Local Edge Differentially Private Graph Algorithms [11.49857418691547]
  我々は、kコア分解と三角形カウントという2つの基本グラフ統計量に対して、新しい LDP アルゴリズムを導入する。 提案手法は、入力依存のプライベートグラフ特性、特にグラフの退化性と最大度を活用して、理論的有用性を向上させる。 我々のkコア分解は正確な値の3倍以内の誤差を達成し、Dhulipalaなどのベースラインで131倍の誤差をはるかに上回っている。
  論文  参考訳（メタデータ） (2025-06-25T20:54:07Z)
• Pruning Spurious Subgraphs for Graph Out-of-Distribution Generalization [90.74916553208153]
  PrunEは,OODの一般化性を改善するために急激なエッジを除去する最初のプルーニングベースグラフOOD法である。 PrunE は2つの正規化項を使い、1) グラフサイズ制約は非形式的なスパイラスエッジを除外し、2) スパイラスエッジの発生をさらに抑制するために、$epsilon$-probability アライメントを使用する。
  論文  参考訳（メタデータ） (2025-06-06T10:34:48Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  我々は,非プライベートなストリーミングと静的アルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。 これには、最も高密度な部分グラフのためのアルゴリズム、最大マッチング、および最初の連続リリース$k$-core分解アルゴリズムが含まれる。
  論文  参考訳（メタデータ） (2024-07-24T20:15:07Z)
• Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank [74.53857412207034]
  本稿では,近似的なPPRを出力し,入力エッジに有界な感度を持つアルゴリズムを提案する。 我々の感度バウンドPPRは、差分プライベート(DP)PPRランキング、DPノード分類、DPノード埋め込みなど、グラフ学習のいくつかのツールのプライベートアルゴリズムを直接意味している。
  論文  参考訳（メタデータ） (2022-07-14T14:08:59Z)
• HSolo: Homography from a single affine aware correspondence [0.0]
  Inlier-poor領域に特に適したホモグラフィー推定のための新しい手法を提案する。 特に低い不整合率では,新しいアルゴリズムにより劇的な性能向上が期待できる。
  論文  参考訳（メタデータ） (2020-09-10T17:13:23Z)

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

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