論文の概要: Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy

• arxiv url: http://arxiv.org/abs/2507.10627v1
• Date: Mon, 14 Jul 2025 07:04:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-16 19:46:02.792967
• Title: Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy
• Title（参考訳）: ローカル差分プライバシー下での暗号支援グラフデグレーシーケンスのリリース
• Authors: Xiaojian Zhang, Junqing Wang, Kerui Chen, Peiyuan Zhao, Huiyuan Bai,
• Abstract要約: ドメイン $mathcalG$ で定義されたグラフ $G$ が与えられたとき、我々は、$mathcalG$ で次列を解放する局所的に微分プライベートなメカニズムを調査する。 本稿では、暗号技術と微分プライベート機構を組み込んだ効率的なフレームワークであるCADR-LDPについて述べる。
• 参考スコア（独自算出の注目度）: 0.7123645379986315
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a graph $G$ defined in a domain $\mathcal{G}$, we investigate locally differentially private mechanisms to release a degree sequence on $\mathcal{G}$ that accurately approximates the actual degree distribution. Existing solutions for this problem mostly use graph projection techniques based on edge deletion process, using a threshold parameter $\theta$ to bound node degrees. However, this approach presents a fundamental trade-off in threshold parameter selection. While large $\theta$ values introduce substantial noise in the released degree sequence, small $\theta$ values result in more edges removed than necessary. Furthermore, $\theta$ selection leads to an excessive communication cost. To remedy existing solutions' deficiencies, we present CADR-LDP, an efficient framework incorporating encryption techniques and differentially private mechanisms to release the degree sequence. In CADR-LDP, we first use the crypto-assisted Optimal-$\theta$-Selection method to select the optimal parameter with a low communication cost. Then, we use the LPEA-LOW method to add some edges for each node with the edge addition process in local projection. LPEA-LOW prioritizes the projection with low-degree nodes, which can retain more edges for such nodes and reduce the projection error. Theoretical analysis shows that CADR-LDP satisfies $\epsilon$-node local differential privacy. The experimental results on eight graph datasets show that our solution outperforms existing methods.
• Abstract（参考訳）: ドメイン $\mathcal{G}$ で定義されたグラフ $G$ が与えられたとき、実次数分布を正確に近似する$\mathcal{G}$ 上の次数列を局所的に独立に解放するメカニズムを調査する。 既存の解法は主にエッジ削除プロセスに基づくグラフ投影技術を用いており、閾値パラメータ $\theta$ を用いてノードの次数を求める。 しかし,本手法は閾値パラメータ選択の基本的なトレードオフを示す。 大きな$\theta$値はリリースされた次数列にかなりのノイズをもたらすが、小さな$\theta$値は必要以上に多くのエッジを削除する。 さらに$\theta$選択は、過剰な通信コストにつながる。 既存のソリューションの欠陥を補うため,CADR-LDPは,暗号化技術と差分秘密機構を組み込んだ効率的なフレームワークであり,次数列を解放する。 CADR-LDPでは、まず暗号支援のOptimal-$\theta$-Selection法を用いて、通信コストの低い最適パラメータを選択する。 次に, LPEA-LOW法を用いて各ノードにエッジを追加し, エッジの追加処理を局所投影で行う。 LPEA-LOWは、プロジェクションを低次ノードで優先順位付けすることで、そのようなノードのエッジをより多く保持し、プロジェクションエラーを低減することができる。 CADR-LDPは$\epsilon$-nodeローカル差分プライバシーを満足している。 8つのグラフデータセットの実験結果から,既存の手法よりも優れた解が得られた。

関連論文リスト

• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  フェデレートされた学習は、参加者のプライバシを備えた機械学習モデルを可能にする。 トレーニングやフィードバックのない問題に対して、差分にプライベートな分散手法は存在しない。 証明可能な収束保証付き分散アルゴリズム$alpha$-$sf NormEC$を導入する。
  論文  参考訳（メタデータ） (2025-02-19T07:10:32Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• PrivSGP-VR: Differentially Private Variance-Reduced Stochastic Gradient Push with Tight Utility Bounds [9.47030623916154]
  そこで本研究では,分散化による勾配プッシュを応用し,各ノードのプライバシを保証する,差分プライベートな分散学習手法(PrivSGPVR)を提案する。 この理論解析により, DP雑音下では, PrivGPS-VR は$mathcalO (1/sqrtnK)$のサブ線形収束速度を達成できることがわかった。
  論文  参考訳（メタデータ） (2024-05-04T11:22:53Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Optimizing $k$ in $k$NN Graphs with Graph Learning Perspective [30.290306866355536]
  グラフ信号処理に基づいて、隣接するグラフ(k$NNGs)の$k$ in $k$-nearestの選択を最適化する手法を提案する。 本手法を用いて得られた$k$NNGsは,実データセットで実験した結果,各ノードあたりのエッジの適切な変数数を決定することができることがわかった。
  論文  参考訳（メタデータ） (2024-01-16T09:59:36Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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