論文の概要: Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts

• arxiv url: http://arxiv.org/abs/2507.14835v1
• Date: Sun, 20 Jul 2025 06:20:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-22 20:51:32.081006
• Title: Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
• Title（参考訳）: 三角形モチーフカットを保存した微分プライベートな合成グラフ
• Authors: Pan Peng, Hangyu Xu,
• Abstract要約: 微分プライベート (DP) 合成グラフ $G'$ を、任意のグラフ $G'$ のすべてのカットの三角形-モチーフサイズをよく近似する問題について検討する。 このようなグラフの非公開バージョンは、グラフクラスタリング、グラフスペーシフィケーション、ソーシャルネットワーク分析といった様々な分野に応用されている。
• 参考スコア（独自算出の注目度）: 5.893124686141782
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of releasing a differentially private (DP) synthetic graph $G'$ that well approximates the triangle-motif sizes of all cuts of any given graph $G$, where a motif in general refers to a frequently occurring subgraph within complex networks. Non-private versions of such graphs have found applications in diverse fields such as graph clustering, graph sparsification, and social network analysis. Specifically, we present the first $(\varepsilon,\delta)$-DP mechanism that, given an input graph $G$ with $n$ vertices, $m$ edges and local sensitivity of triangles $\ell_{3}(G)$, generates a synthetic graph $G'$ in polynomial time, approximating the triangle-motif sizes of all cuts $(S,V\setminus S)$ of the input graph $G$ up to an additive error of $\tilde{O}(\sqrt{m\ell_{3}(G)}n/\varepsilon^{3/2})$. Additionally, we provide a lower bound of $\Omega(\sqrt{mn}\ell_{3}(G)/\varepsilon)$ on the additive error for any DP algorithm that answers the triangle-motif size queries of all $(S,T)$-cut of $G$. Finally, our algorithm generalizes to weighted graphs, and our lower bound extends to any $K_h$-motif cut for any constant $h\geq 2$.
• Abstract（参考訳）: 我々は、任意のグラフのすべてのカットの三角形-モチーフサイズをよく近似する、微分プライベート(DP)合成グラフ $G'$ をリリースする問題について研究する。 このようなグラフの非公開バージョンは、グラフクラスタリング、グラフスペーシフィケーション、ソーシャルネットワーク分析といった様々な分野に応用されている。 具体的には、最初の$(\varepsilon,\delta)$-DP メカニズムを提示し、入力グラフ $G$ with $n$ vertices, $m$ edges and local sensitivity of triangles $\ell_{3}(G)$, generate a synthetic graph $G'$ in polynomial time, approximating the triangle-motif sizes of all cuts $(S,V\setminus S)$ of the input graph $G$ to a additive error of $\tilde{O}(\sqrt{m\ell_{3}(G)}n/\varepsilon^{3/2}.} が与えられる。 さらに、すべての$(S,T)$-cut of $G$の三角形モチーフサイズクエリに答える任意のDPアルゴリズムに対する加算誤差に対して、$\Omega(\sqrt{mn}\ell_{3}(G)/\varepsilon)$の低い境界を提供する。 最後に、我々のアルゴリズムは重み付きグラフに一般化し、下限は任意の定数$h\geq 2$に対して任意の$K_h$-モチーフカットにまで拡張する。

関連論文リスト

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Almost linear time differentially private release of synthetic graphs [6.076406622352115]
  本稿では,指数関数的メカニズムから,ほぼ線形時間と空間のアルゴリズムをサンプリングする。 直接的な結果として、差分入力を指数関数的に大きな$G$mエッジとして定義する。 これらは合成グラフを公開するためのプライベートファーストのプライベートアルゴリズムである。
  論文  参考訳（メタデータ） (2024-06-04T09:44:24Z)
• Complexity of graph-state preparation by Clifford circuits [2.4032529562561176]
  我々は、グラフ状態の準備のために少なくとも2つの量子ビットで作用する一般量子アルゴリズムを考える。 グラフ状態の CZ-複素性は、|Grangle$ とグラフのランク幅 $G$ との接続を示す。 本稿では,区間グラフ,区間囲みグラフ,円グラフの3つの特定のグラフクラスに対して,グラフ状態を作成するための量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-08T18:08:09Z)
• Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
  ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。 複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
  論文  参考訳（メタデータ） (2023-06-05T15:35:00Z)
• 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)
• (1,1)-Cluster Editing is Polynomial-time Solvable [0.0]
  a*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*
  論文  参考訳（メタデータ） (2022-10-14T11:40:34Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。 偏光理論への我々の結果の即時適用について述べる。
  論文  参考訳（メタデータ） (2022-05-30T18:01:34Z)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。 近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。 副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
  論文  参考訳（メタデータ） (2022-02-22T04:14:45Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。 これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
  論文  参考訳（メタデータ） (2021-10-11T05:07:50Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)

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

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