論文の概要: The Power of Interaction in Locally Edge-Private Subgraph Counting

• arxiv url: http://arxiv.org/abs/2611.05038v1
• Date: Tue, 03 Nov 2026 15:10:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-07 14:55:15.659719
• Title: The Power of Interaction in Locally Edge-Private Subgraph Counting
• Title（参考訳）: 局所的に有意な部分グラフカウントにおける相互作用の力
• Abstract要約: 対話型ローカルエッジ差分プライバシ(LEDP)におけるサブグラフカウントの検討 私たちの目標は、エッジのプライバシを保持しながら、そのコピーを任意の$n-vertex un graphにカウントすることにあります。 すべての$varepsilon$-LEDPアルゴリズムに対して、加算誤差とルート平均二乗誤差は、すべての$nk-3/2/varepsilonellに対して$O(nk-3/2/varepsilonell)$である。
• 参考スコア（独自算出の注目度）: 6.718776009356437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP). Given a fixed pattern graph $H$ with $k$ vertices, $\ell\ge1$ edges, and $q$ connected components, our goal is to approximately count its copies in an arbitrary $n$-vertex undirected graph while preserving edge privacy. We give two complementary accuracy guarantees. First, for every $H$, we give Linear Noise Cancellation (LNC), a two-round $\varepsilon$-LEDP algorithm with additive error and root mean square error both $O(n^{k-3/2}/\varepsilon^\ell)$ on every $n$-vertex graph. For fixed sufficiently small $\varepsilon$, this improves the optimal noninteractive additive error for triangles by a factor of $\sqrt n$ and gives the same improvement in worst-case root mean square error for all cliques on at least three vertices. To our knowledge, this is the first separation between interactive and noninteractive LEDP subgraph counting, showing that a single additional round can improve worst-case accuracy polynomially. Second, we determine how accuracy improves when the graph has maximum degree at most a public bound $d$. Our Predict and Correct (PC) framework gives an $(\ell+2)$-round $\varepsilon$-LEDP algorithm with additive error $O(n^{q-1/2}d^{k-q-1}\log^{3\ell-2}n/\varepsilon^\ell)$. For connected patterns, its polynomial factor is $\sqrt n\,d^{k-2}$, giving sublinear error on constant-degree graphs at fixed privacy. We prove matching lower bounds in $n$ and $d$, up to logarithmic factors at fixed privacy, even under arbitrary interaction and approximate privacy with sufficiently small $δ$. At $d=Θ(n)$, the lower bound also establishes the optimality of LNC's dependence on $n$.
• Abstract（参考訳）: 対話型ローカルエッジ差分プライバシ(LEDP)下での(非誘導的な)サブグラフカウントについて検討した。 固定パターングラフ$H$、$k$ vertices、$\ell\ge1$ edges、$q$接続されたコンポーネントが与えられた場合、私たちの目標は、エッジプライバシを保持しながら、そのコピーを任意の$n$-vertexundirected graphにカウントすることにあります。 2つの補完的正確性を保証する。 まず、各$H$に対して、2ラウンドの$\varepsilon$-LEDPアルゴリズム、加法誤差とルート平均二乗誤差を持つ$O(n^{k-3/2}/\varepsilon^\ell)を各$n$頂点グラフ上で与える。 十分小さな$\varepsilon$に対して、これは三角形の最適非インタラクティブな加法誤差を$\sqrt n$ の係数で改善し、少なくとも3つの頂点上のすべての傾きに対して最悪の根平均二乗誤差を同様に改善する。 我々の知る限り、これはインタラクティブなLEDPサブグラフと非インタラクティブなLEDPサブグラフのカウントの最初の分離であり、単一の追加ラウンドが最悪のケースの精度を多項式的に改善できることを示している。 第二に、グラフが最大等級の公有界$d$のとき、どれだけ精度が向上するかを決定する。 我々の予測と訂正(PC)フレームワークは$(\ell+2)$-round $\varepsilon$-LEDPアルゴリズムに加算誤差$O(n^{q-1/2}d^{k-q-1}\log^{3\ell-2}n/\varepsilon^\ell)$を与える。 連結パターンの場合、多項式係数は$\sqrt n\,d^{k-2}$であり、固定プライバシーにおける定次グラフのサブ線形誤差を与える。 任意の相互作用や近似プライバシーの下でも、固定プライバシーにおける対数的要因まで、$n$と$d$の低いバウンダリを十分に小さな$δ$で表す。 d = = (n)$ のとき、下界は LNC の $n$ への依存の最適性も確立する。

関連論文リスト

• Tilted Convexity and an Exact Offline-Online Separation [51.97268646814437]
  凸性は、アフィン関数によるサポート、部分微分の単調性、セカント勾配の増加の3つの等価な記述を持つ。 これら3つ全てをパラメータ $in(0,1) で1つの歪みで弱め、正の変化を$$で乗算し、負の変化を$で割る。 結果として生成されるクラスは、$=1の凸関数であり、$$1の値は区別され、ネストされる。
  論文  参考訳（メタデータ） (2026-11-02T17:13:21Z)
• Subgraph Counting with Local Node Differential Privacy [6.7576664180067105]
  局所ノード差分プライバシー(LNDP)の下での約数部分グラフの問題について検討する。 我々は,非インタラクティブな$(varepsilon,0)$-LNDPアルゴリズムを設計し,機密性のない$n$ノードグラフにおける$H$の発生をカウントする。 この結果はLNDPで近似可能であることが知られているネットワーク統計のタイプを大幅に拡張する。
  論文  参考訳（メタデータ） (2026-10-15T17:39:36Z)
• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers [9.297355862757838]
  本稿では,エッジレベルの差分プライバシーの下で,入力グラフのすべてのカットサイズを近似した合成グラフを公開する問題について検討する。 有界時間 $(varepsilon,)$-differentially private algorithm を与え、これはすべての$n$-vertex 未重み付きグラフ $G$ に対して非負重み付き合成グラフを出力する。
  論文  参考訳（メタデータ） (2026-07-21T08:35:05Z)
• Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts [3.652509571098291]
  微分プライベート (DP) 合成グラフ $G'$ を、任意のグラフ $G'$ のすべてのカットの三角形-モチーフサイズをよく近似する問題について検討する。 このようなグラフの非公開バージョンは、グラフクラスタリング、グラフスペーシフィケーション、ソーシャルネットワーク分析といった様々な分野に応用されている。
  論文  参考訳（メタデータ） (2025-07-20T06:20:53Z)
• 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)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
  ランダムな幾何グラフの古典的モデルを考えると、$n$の点が一様に領域$n$の正方形に散らばっている。 グラフ距離と近距離推定のハイブリッドを用いてユークリッド距離を推定する。 本手法は, グラフ距離と近辺点数に基づく短距離推定のハイブリッドを用いてユークリッド距離を推定する。
  論文  参考訳（メタデータ） (2021-07-29T20:37:28Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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