論文の概要: Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs
- arxiv url: http://arxiv.org/abs/2409.16688v2
- Date: Fri, 27 Sep 2024 03:48:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-09-30 11:04:03.117716
- Title: Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs
- Title(参考訳): デジェネリアシー境界グラフの局所微分プライバシーに基づくサイクルカウント
- Authors: Quentin Hillebrand, Vorapong Suppakitpaisarn, Tetsuo Shibuya,
- Abstract要約: そこで本稿では,デジェネリティーに縛られた入力グラフに対して,局所的な差分プライバシーの下でサイクル数をカウントするアルゴリズムを提案する。
我々のアルゴリズムは、退化性有界グラフに対して、$O(d_max0.5 n0.5) = O(n)$の予測$ell$-errorを達成する。
- 参考スコア(独自算出の注目度): 2.9123921488295768
- License:
- Abstract: We propose an algorithm for counting the number of cycles under local differential privacy for degeneracy-bounded input graphs. Numerous studies have focused on counting the number of triangles under the privacy notion, demonstrating that the expected $\ell_2$-error of these algorithms is $\Omega(n^{1.5})$, where $n$ is the number of nodes in the graph. When parameterized by the number of cycles of length four ($C_4$), the best existing triangle counting algorithm has an error of $O(n^{1.5} + \sqrt{C_4}) = O(n^2)$. In this paper, we introduce an algorithm with an expected $\ell_2$-error of $O(\delta^{1.5} n^{0.5} + \delta^{0.5} d_{\max}^{0.5} n^{0.5})$, where $\delta$ is the degeneracy and $d_{\max}$ is the maximum degree of the graph. For degeneracy-bounded graphs ($\delta \in \Theta(1)$) commonly found in practical social networks, our algorithm achieves an expected $\ell_2$-error of $O(d_{\max}^{0.5} n^{0.5}) = O(n)$. Our algorithm's core idea is a precise count of triangles following a preprocessing step that approximately sorts the degree of all nodes. This approach can be extended to approximate the number of cycles of length $k$, maintaining a similar $\ell_2$-error, namely $O(\delta^{(k-2)/2} d_{\max}^{0.5} n^{(k-2)/2} + \delta^{k/2} n^{(k-2)/2})$ or $O(d_{\max}^{0.5} n^{(k-2)/2}) = O(n^{(k-1)/2})$ for degeneracy-bounded graphs.
- Abstract(参考訳): そこで本稿では,デジェネリティーに縛られた入力グラフに対して,局所的な差分プライバシーの下でサイクル数をカウントするアルゴリズムを提案する。
多くの研究は、プライバシーの概念の下で三角形の数を数えることに重点を置いており、これらのアルゴリズムの期待$\ell_2$-errorが$\Omega(n^{1.5})$であることを示す。
長さ 4 (C_4$) のサイクル数によってパラメータ化されるとき、最良の三角法カウントアルゴリズムは、$O(n^{1.5} + \sqrt{C_4}) = O(n^2)$の誤差を持つ。
本稿では,$\ell_2$-error of $O(\delta^{1.5} n^{0.5} + \delta^{0.5} d_{\max}^{0.5} n^{0.5})$, $\delta$ is the degeneracy and $d_{\max}$ is the maximum degree of the graphを紹介する。
実用的なソーシャルネットワークで一般的に見られる退化性有界グラフ(\delta \in \Theta(1)$)に対して、我々のアルゴリズムは$O(d_{\max}^{0.5} n^{0.5}) = O(n)$の$\ell_2$-errorを達成する。
我々のアルゴリズムの中核的な考え方は、全てのノードの次数をほぼソートする前処理ステップに続く正確な三角形の数である。
このアプローチは、同じ$\ell_2$-error、すなわち$O(\delta^{(k-2)/2} d_{\max}^{0.5} n^{(k-2)/2} + \delta^{k/2} n^{(k-2)/2})$または$O(d_{\max}^{0.5} n^{(k-2)/2}) = O(n^{(k-1)/2})$を維持して長さ$k$のサイクル数を近似するために拡張することができる。
関連論文リスト
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳(メタデータ) (2024-06-07T08:26:31Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization [20.54801745090522]
我々は、mathbbRd f(x) 三角形q mathbbE_xi [Fxi]$inf(x)$ Lipschitz における $min_x という形式の問題を考察する。
最近提案された勾配なし法は、少なくとも$mathcalO(L4 d3/2 epsilon-4 + Goldstein L d3/2 delta-1 epsilon-4)$ 0次複雑性を必要とする。
論文 参考訳(メタデータ) (2023-01-16T13:33:37Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - Escape saddle points by a simple gradient-descent based algorithm [6.7298812735467095]
非最適化において、サドルポイントのエスケープは中心的な研究トピックである。
滑らかな関数 $fcolonmathbbRntomathbbR$ に対して、$epsilonO(log n)2/epsilon4)$ を出力する。
技術的に、我々の主な貢献は勾配のみを用いたロバストなヘッセンパワー手法の実装である。
論文 参考訳(メタデータ) (2021-11-28T07:32:54Z) - Robust Estimation for Random Graphs [47.07886511972046]
我々は、$n$ノード上のErdHos-R'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。
情報理論の限界であるすべての$gamma 1/2$に対して、同様の精度で非効率なアルゴリズムを与える。
論文 参考訳(メタデータ) (2021-11-09T18:43:25Z) - A Stochastic Path-Integrated Differential EstimatoR Expectation
Maximization Algorithm [19.216497414060658]
予測最大化(EM)アルゴリズムは、回帰器と専門家の混在を含む潜在変数モデルにおける推論において重要な要素である。
本稿では,条件予測推定器からの推測のための新しいEMであるtextttSPを提案する。
論文 参考訳(メタデータ) (2020-11-30T15:49:31Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳(メタデータ) (2020-11-24T22:39:21Z) - Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments [9.853329403413701]
Sutton and Witt (GECCO) が分析した選択自由定常遺伝的アルゴリズムは、特定のターゲット探索点を見つけるために、期待する数$Omega (2n / sqrt n)$を取ることを証明している。
我々の結果は、以前の$Omega(exp(ndelta/2))$の下位境界よりも改善され、人口規模が$muに対して有効である。
論文 参考訳(メタデータ) (2020-06-08T15:04:51Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。