論文の概要: Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks

• arxiv url: http://arxiv.org/abs/2609.10877v1
• Date: Wed, 09 Sep 2026 22:34:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-11 23:53:35.157185
• Title: Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks
• Title（参考訳）: リコンストラクションアタックを用いた個人グラフ最適化問題の下位境界
• Abstract要約: 本稿では,差分プライバシー(DP)下における基本グラフ最適化問題について検討する。 最小ウェイトなスパンニングツリーと最小ウェイトな完全マッチングを解放する問題に対して、(ncdotlog(m/n)/)$の新しいタイトなエラー境界を示す。
• 参考スコア（独自算出の注目度）: 13.028088895249786
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds. We consider a graph $G = (V, E, \vec{w})$ where the vertex set $V$ and edges $E$ are public and the weights $\mathbf{w}:E\rightarrow \mathbb{R}$ must be kept differentially private under an $\ell_1$ neighboring relation. For the problems of releasing a minimum-weight spanning tree and a minimum-weight perfect matching, we show new, tight error bounds of $Ω(n\cdot\log(m/n)/ε)$ on worst-case graphs with $n$ vertices and $m>2n$ edges. The upper bounds are known pure DP algorithms while the new lower bound holds even under approximate $(\varepsilon,δ)$-DP as long as $δ\leq (n/m)^{Ω(1)}$. Our lower bounds improve the $Ω(n/ε)$ lower bounds of Sealfon (PODS~'16). The fact that approximate DP does not reduce error for MST under the $\ell_1$ neighboring relation contrasts with the recent upper bound of Pagh et al. (PODS~'25) which shows that approximate DP allows much better error under the $\ell_\infty$ neighboring relation. Going beyond worst-case graphs, we give lower bounds for large families of sparse graphs with expansion properties. We show a lower bound of $Ω(n / ε)$ for the minimum spanning tree for any graph where the minimum cut is at least $Ω(\log(n))$. Finally, we consider the problem of private hierarchical clustering under Dasgupta's cost function (STOC~'16) and show the first approximate DP lower bound parameterized by the minimum weight of a balanced cut. This extends lower bounds of Deng et al. (ICLR~'25) to general graphs and to approximate DP.
• Abstract（参考訳）: 本稿では,差分プライバシ(DP)に基づく基本グラフ最適化問題について検討し,新しい,再構成に基づく下限を示す。 グラフ $G = (V, E, \vec{w})$ ここで、頂点集合 $V$ と辺 $E$ は公開であり、重み $\mathbf{w}:E\rightarrow \mathbb{R}$ は $\ell_1$ の近傍関係の下で微分プライベートに保たなければならない。 最小ウェイトなスパンニングツリーと最小ウェイトな完全マッチングを解放する問題に対して、$n$頂点と$m>2n$辺を持つ最悪ケースグラフ上の$Ω(n\cdot\log(m/n)/ε)$の新しいタイトなエラー境界を示す。 上界は純粋 DP アルゴリズムとして知られており、新しい下界は $(\varepsilon,δ)$-DP のときも $δ\leq (n/m)^{Ω(1)}$ である。 我々の下界は、Sealfon (PODS~'16) の$Ω(n/ε)$下界を改善する。 近似DPは、$\ell_1$ 近傍関係の下で MST の誤差を減らさないという事実は、最近の Pagh et al (PODS~'25) の上限と対照的である。 最悪のケースグラフを超えて、拡張特性を持つスパースグラフの大きな族に対して、より低い境界を与える。 最小カットが少なくとも$Ω(\log(n))$である任意のグラフに対して、最小スパンニングツリーに対して$Ω(n / ε)$の低い境界を示す。 最後に,Dasgupta のコスト関数 (STOC~'16) に基づく個人階層的クラスタリングの問題を考察し,平衡カットの最小重みによってパラメータ化された最初の近似DP下界を示す。 これは、Deng et al (ICLR~'25) の下界を一般グラフに拡張し、DP を近似する。

関連論文リスト

• Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers [9.297355862757838]
  本稿では,エッジレベルの差分プライバシーの下で,入力グラフのすべてのカットサイズを近似した合成グラフを公開する問題について検討する。 有界時間 $(varepsilon,)$-differentially private algorithm を与え、これはすべての$n$-vertex 未重み付きグラフ $G$ に対して非負重み付き合成グラフを出力する。
  論文  参考訳（メタデータ） (2026-07-21T08:35:05Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry [2.6140509675507384]
  我々は、$n$-vertex graph $G$の頂点を$n$-leafのルートツリー$mathcalB$の葉に埋め込む問題を考える。 我々は、グラフの異なる族における渋滞境界を、正規構造(ハイパーキューブと格子)、ランダムグラフ、量子回路のテンソルネットワーク表現と数値的に比較する。
  論文  参考訳（メタデータ） (2025-10-03T04:58:40Z)
• Joint estimation of smooth graph signals from partial linear measurements [5.2395896768723045]
  弱い一貫性は、個々の$G_t$sが非常に疎結合で非連結である場合でも、$G$の特定の選択に対して確立される。 結果は、$x_t$が$n$アイテムのコレクションの潜在強度に対応するマルチレイヤのランキング問題に拡張される。
  論文  参考訳（メタデータ） (2025-05-29T08:41:45Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• Planted Bipartite Graph Detection [13.95780443241133]
  ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。 ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。 k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
  論文  参考訳（メタデータ） (2023-02-07T18:18:17Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs [1.0435741631709405]
  グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。 この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
  論文  参考訳（メタデータ） (2021-10-29T07:35:46Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• 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)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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