論文の概要: Private Graph Property Testing

• arxiv url: http://arxiv.org/abs/2609.14394v1
• Date: Sun, 13 Sep 2026 09:12:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:05.807978
• Title: Private Graph Property Testing
• Title（参考訳）: プライベートグラフプロパティテスト
• Abstract要約: グラフプロパティテストは、巨大なグラフが与えられたプロパティを満たすかどうかを問う。 プロパティテスタは通常、入力の小さな、ランダムにサンプリングされた部分のみを検査するので、サブサンプリングによって異なるプライバシとプライバシの増幅と自然に互換性があるように見える。 提案手法は, グラフサンプリング, ランダムウォーク, k-disc サンプリングなど, 広く利用されているいくつかのグラフサンプリング手法に対して, 新たなプライバシ増幅定理を開発した。
• 参考スコア（独自算出の注目度）: 5.254472084022827
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph property testing asks whether a massive graph satisfies a given property, or is far from doing so, using only a sublinear number of queries to the graph. Since property testers typically inspect only a small, randomly sampled portion of the input, they appear naturally compatible with differential privacy and privacy amplification by subsampling. Despite this, few results link these two fields. We initiate a systematic study of differentially private graph property testing with the goal of designing efficient testers with formal privacy guarantees in the dense and bounded-degree graph models. We develop new privacy amplification theorems for several widely used graph-sampling procedures such as induced subgraph sampling, random walks and k-disc sampling. We then leverage these privacy amplification techniques to design a private canonical tester in the dense graph model, as well as private bipartiteness testers and subgraph freeness testers in the dense and bounded-degree graph models. Finally, using the new privacy amplification theorem for k-disc sampling, we prove that every property of hyperfinite graphs is privately testable. The resulting query complexities of our private testers are comparable to those of their non-private counterparts.
• Abstract（参考訳）: グラフプロパティテストは、巨大なグラフが与えられたプロパティを満たすかどうかを問う。 プロパティテスタは通常、入力の小さな、ランダムにサンプリングされた部分のみを検査するので、サブサンプリングによって異なるプライバシとプライバシの増幅と自然に互換性があるように見える。 これにもかかわらず、これらの2つの分野を結び付ける結果はほとんどない。 我々は,密度グラフモデルと有界グラフモデルにおいて,形式的なプライバシ保証を備えた効率的なテスタを設計することを目的として,微分プライベートグラフプロパティテストの体系的研究を開始した。 提案手法は, グラフサンプリング, ランダムウォーク, k-disc サンプリングなど, 広く利用されているいくつかのグラフサンプリング手法に対して, 新たなプライバシ増幅定理を開発した。 次に、これらのプライバシー増幅技術を活用して、密グラフモデルにおけるプライベートな標準テスターを設計し、密グラフモデルにおけるプライベートな二分性テスターと、密グラフモデルと有界グラフモデルにおけるサブグラフ自由度テスターを設計します。 最後に、k-discサンプリングのための新しいプライバシー増幅定理を用いて、超有限グラフのすべての性質がプライベートにテスト可能であることを証明する。 プライベートテスタのクエリの複雑さは、プライベートでないテスタに匹敵するものです。

関連論文リスト

• Near-Optimal Private Tests for Simple and MLR Hypotheses [13.738306418341729]
  ガウス微分プライバシーの枠組みに基づく準最適試験法を開発した。 我々は、非プライベートで最も強力なテストと同等の相対効率を達成するプライベートテスト統計を構築した。 私たちのテストは、中程度の小さなサンプルサイズとプライバシ損失予算であっても、プライベートでない最も強力なテストに匹敵する力を提供します。
  論文  参考訳（メタデータ） (2026-01-29T16:36:21Z)
• Benchmarking Fraud Detectors on Private Graph Data [70.4654745317714]
  現在、多くの種類の不正は、グラフ上で動く自動検出アルゴリズムによって部分的に管理されている。 データ保有者が不正検知器の開発を第三者にアウトソースしようとするシナリオを考察する。 サードパーティは、不正検出をデータ保持者に送信し、これらのアルゴリズムをプライベートデータセットで評価し、その結果を公表する。 本システムに対する現実的なプライバシ攻撃を提案し,評価結果のみに基づいて個人データの匿名化を可能にする。
  論文  参考訳（メタデータ） (2025-07-30T03:20:15Z)
• Independent Distribution Regularization for Private Graph Embedding [55.24441467292359]
  グラフ埋め込みは属性推論攻撃の影響を受けやすいため、攻撃者は学習したグラフ埋め込みからプライベートノード属性を推測することができる。 これらの懸念に対処するため、プライバシ保護グラフ埋め込み手法が登場した。 独立分散ペナルティを正規化項として支援し, PVGAE(Private Variational Graph AutoEncoders)と呼ばれる新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-08-16T13:32:43Z)
• Privacy-Preserved Neural Graph Similarity Learning [99.78599103903777]
  本稿では,グラフ類似性学習のためのプライバシ保存型ニューラルグラフマッチングネットワークモデルPPGMを提案する。 再構成攻撃を防ぐため、提案モデルではデバイス間でノードレベルの表現を通信しない。 グラフプロパティに対する攻撃を軽減するため、両方のベクトルの情報を含む難読化機能は通信される。
  論文  参考訳（メタデータ） (2022-10-21T04:38:25Z)
• On the Statistical Complexity of Estimation and Testing under Privacy Constraints [17.04261371990489]
  差分プライバシー下での統計的テストのパワーをプラグアンドプレイ方式で特徴付ける方法を示す。 プライバシ保護のレベルが非常に高い場合にのみ、プライバシの維持が顕著なパフォーマンス低下をもたらすことを示す。 最後に,プライベート凸解法であるDP-SGLDアルゴリズムを高信頼度で最大推定できることを示した。
  論文  参考訳（メタデータ） (2022-10-05T12:55:53Z)
• Model Inversion Attacks against Graph Neural Networks [65.35955643325038]
  グラフニューラルネットワーク(GNN)に対するモデル反転攻撃について検討する。 本稿では,プライベートトレーニンググラフデータを推測するためにGraphMIを提案する。 実験の結果,このような防御効果は十分ではないことが示され,プライバシー攻撃に対するより高度な防御が求められている。
  論文  参考訳（メタデータ） (2022-09-16T09:13:43Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  DP-SGDで訓練されたモデルをリリースする際の個々の事例に対するプライバシー保証を特徴付ける。 ほとんどの例では、最悪のケースよりも強力なプライバシー保証を享受しています。 これは、モデルユーティリティの観点からは守られないグループが同時に、より弱いプライバシー保証を経験することを意味する。
  論文  参考訳（メタデータ） (2022-06-06T13:49:37Z)
• Uniformity Testing in the Shuffle Model: Simpler, Better, Faster [0.0]
  均一性テスト(英: Uniformity testing)または独立した観察が均一に分散されているかどうかをテストすることは、分散テストにおける問題である。 本研究では,シャッフルモデルにおける既知の一様性試験アルゴリズムの解析を大幅に単純化する。
  論文  参考訳（メタデータ） (2021-08-20T03:43:12Z)
• A practical test for a planted community in heterogeneous networks [0.0]
  実ネットワークデータの場合、密な部分グラフの存在は一般に不明である。 テストのパワーを理論的に検討し、シミュレーションと実データ例を用いてテストの性能を評価します。
  論文  参考訳（メタデータ） (2021-01-15T01:34:14Z)
• Towards practical differentially private causal graph discovery [74.7791110594082]
  因果グラフ発見は、純粋な観測データから因果関係グラフを発見する過程を指す。 そこで本稿では,Priv-PCによる個人用因果グラフ探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-15T18:30:41Z)

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

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