論文の概要: Subgraph Counting under Edge Local Differential Privacy Based on Noisy Adjacency Matrix

• arxiv url: http://arxiv.org/abs/2507.06508v1
• Date: Wed, 09 Jul 2025 03:13:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-10 17:37:43.448065
• Title: Subgraph Counting under Edge Local Differential Privacy Based on Noisy Adjacency Matrix
• Title（参考訳）: 雑音適応行列に基づくエッジローカル差分プライバシに基づく部分グラフカウント
• Authors: Jintao Guo, Ying Zhou, Chao Li, Guixun Luo,
• Abstract要約: 本稿では、差分プライバシーとグラフの隣接行列を組み合わせたノイズ適応行列(NAM)を提案する。 NAMに基づいて、三角形、四角形、および2つ星の3種類のサブグラフをカウントする5つのアルゴリズムを設計した。 我々は、信頼区間インスパイアされた手法を用いて、ノイズの多いデータに対するエッジLDPを実装し、ランダム化されたデータに対するDP保証を提供する。
• 参考スコア（独自算出の注目度）: 12.264804926096593
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When analyzing connection patterns within graphs, subgraph counting serves as an effective and fundamental approach. Edge-local differential privacy (edge-LDP) and shuffle model have been employed to achieve subgraph counting under a privacy-preserving situation. Existing algorithms are plagued by high time complexity, excessive download costs, low accuracy, or dependence on trusted third parties. To address the aforementioned challenges, we propose the Noisy Adjacency Matrix (NAM), which combines differential privacy with the adjacency matrix of the graph. NAM offers strong versatility and scalability, making it applicable to a wider range of DP variants, DP mechanisms, and graph types. Based on NAM, we designed five algorithms (TriOR, TriTR, TriMTR, QuaTR, and 2STAR) to count three types of subgraphs: triangles, quadrangles, and 2-stars. Theoretical and experimental results demonstrate that in triangle counting, TriOR maximizes accuracy with reduced time complexity among one-round algorithms, TriTR achieves optimal accuracy, TriMTR achieves the highest accuracy under low download costs, and QuaTR stands as the first quadrangle counting algorithm under pure edge-LDP. We implement edge-LDP for noisy data via a confidence interval-inspired method, providing DP guarantees on randomized data. Our 2STAR algorithm achieves the highest accuracy in 2-star counting and can be derived as a byproduct of two-round triangle or quadrangle counting algorithms, enabling efficient joint estimation of triangle, quadrangle, and 2-star counts within two query rounds.
• Abstract（参考訳）: グラフ内の接続パターンを分析する際、グラフカウントは効果的で基本的なアプローチとして機能する。 エッジローカルディファレンシャルプライバシ(edge-LDP)とシャッフルモデルを用いて、プライバシ保護状況下でのサブグラフカウントを実現している。 既存のアルゴリズムは、高い時間的複雑さ、過剰なダウンロードコスト、低い精度、信頼できるサードパーティへの依存に悩まされている。 上記の課題に対処するために、差分プライバシーとグラフの隣接行列を組み合わせたノイズ適応行列(NAM)を提案する。 NAMは強力な汎用性とスケーラビリティを提供し、より広い範囲のDP変種、DP機構、グラフタイプに適用できる。 NAMに基づいて,三角形,四角形,2つ星の3種類のサブグラフをカウントする5つのアルゴリズム(Trior,TriTR,TriMTR,QuaTR,2STAR)を設計した。 理論的および実験的な結果から,TriORは1ラウンドのアルゴリズムで時間複雑性を低減して精度を最大化し,TriTRは最適な精度を達成し,TriMTRは低ダウンロードコストで最高精度を達成し,QuaTRは純エッジLDPで最初の四角計数アルゴリズムであることが示された。 我々は、信頼区間インスパイアされた手法を用いて、ノイズの多いデータに対するエッジLDPを実装し、ランダム化されたデータに対するDP保証を提供する。 我々の2STARアルゴリズムは2つ星計数において最高精度を達成し、2ラウンドの三角形または四角形計数アルゴリズムの副産物として導出可能であり、2ラウンド以内の三角形、四角、及び2つ星の効率的な連成推定を可能にする。

関連論文リスト

• SEED: A Simple and Effective 3D DETR in Point Clouds [72.74016394325675]
  ポイントクラウドの分散度が高く,不均一な分布のため,主な課題は困難である,と我々は主張する。 点雲から3次元物体を検出するための簡便で効果的な3次元DETR法(SEED)を提案する。
  論文  参考訳（メタデータ） (2024-07-15T14:21:07Z)
• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [7.466687780705626]
  本稿では, 点集合の密度に基づくクラスタリングについて検討する。 密度ピークの異なる変種を単一のフレームワークPECANNに統合する。 PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
  論文  参考訳（メタデータ） (2023-12-06T22:43:50Z)
• KECOR: Kernel Coding Rate Maximization for Active 3D Object Detection [48.66703222700795]
  我々は、ラベルの取得に最も有用なポイントクラウドを特定するために、新しいカーネル戦略を利用する。 1段目(SECOND)と2段目(SECOND)の両方に対応するため、アノテーションに選択した境界ボックスの総数と検出性能のトレードオフをよく組み込んだ分類エントロピー接点を組み込んだ。 その結果,ボックスレベルのアノテーションのコストは約44%,計算時間は26%削減された。
  論文  参考訳（メタデータ） (2023-07-16T04:27:03Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。 実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。 本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-13T02:44:05Z)
• 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)
• Canny-VO: Visual Odometry with RGB-D Cameras based on Geometric 3D-2D Edge Alignment [85.32080531133799]
  本稿では,自由形式の曲線登録に関する古典的な問題をレビューし,効率的なrgbdビジュアルオドメトリシステムcanny-voに適用する。 エッジ登録でよく用いられる距離変換の代替として、近似近接近傍場と配向近接近傍場という2つの方法が提案されている。 3D2Dエッジアライメントは、効率性と精度の両方の観点から、これらの代替製剤の恩恵を受けます。
  論文  参考訳（メタデータ） (2020-12-15T11:42:17Z)
• NOMA in UAV-aided cellular offloading: A machine learning approach [59.32570888309133]
  複数の無人航空機(UAV)によるセルローディングのための新しい枠組みの提案 非直交多重アクセス(NOMA)技術は、無線ネットワークのスペクトル効率をさらに向上するために、各UAVに採用されている。 相互深いQ-network (MDQN) アルゴリズムは,UAVの最適3次元軌道と電力配分を共同で決定するために提案される。
  論文  参考訳（メタデータ） (2020-10-18T17:38:48Z)
• TEASER: Fast and Certifiable Point Cloud Registration [30.19476775410544]
  最初の高速かつ堅牢な3Dポイントの登録アルゴリズムは、大量の外れ値の存在下での3Dポイントの登録である。 TEASER++という名前の第二の高速で堅牢な認証翻訳は、大規模なサブプロブレムを解決するために、既成の非コンポーネントを使用する。
  論文  参考訳（メタデータ） (2020-01-21T18:56:00Z)

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

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