論文の概要: Acyclic Graph Pattern Counting under Local Differential Privacy

• arxiv url: http://arxiv.org/abs/2603.19671v1
• Date: Fri, 20 Mar 2026 06:12:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-23 19:48:39.019727
• Title: Acyclic Graph Pattern Counting under Local Differential Privacy
• Title（参考訳）: 局所微分プライバシー下における非巡回グラフパターンカウント
• Authors: Yihua Hu, Kuncan Wang, Wei Dong,
• Abstract要約: 局所微分プライバシー(LDP)の下での任意の非循環パターンをカウントする最初の一般解を提案する。 分散データからのパターン構築の一般化と,構築中のノード重複の排除という,2つの基本的な課題に対処する。 複数の非循環パターンをまたいだ実世界のグラフデータセットの実験により、我々のメカニズムは実用性の向上に46ドル～2600ドル、通信コストの削減に300ドル～650ドルを要した。
• 参考スコア（独自算出の注目度）: 6.729442409066558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph pattern counting serves as a cornerstone of network analysis with extensive real-world applications. Its integration with local differential privacy (LDP) has gained growing attention for protecting sensitive graph information in decentralized settings. However, existing LDP frameworks are largely ad hoc, offering solutions only for specific patterns such as triangles and stars. A general mechanism for counting arbitrary graph patterns, even for the subclass of acyclic patterns, has remained an open problem. To fill this gap, we present the first general solution for counting arbitrary acyclic patterns under LDP. We identify and tackle two fundamental challenges: generalizing pattern construction from distributed data and eliminating node duplication during the construction. To address the first challenge, we propose an LDP-tailored recursive subpattern counting framework that incrementally builds patterns across multiple communication rounds. For the second challenge, we apply a random marking technique that restricts each node to a unique position in the pattern during computation. Our mechanism achieves strong utility guarantees: for any acyclic graph pattern with $k$ edges, we achieve an additive error of $\tilde{O}(\sqrt{N}d(G)^k)$, where $N$ is the number of nodes and $d(G)$ is the maximum degree of the input graph $G$. Experiments on real-world graph datasets across multiple types of acyclic patterns demonstrate that our mechanisms achieve up to $46$-$2600\times$ improvement in utility and $300$-$650\times$ reduction in communication cost compared to the baseline methods.
• Abstract（参考訳）: グラフパターンのカウントは、広範囲の現実世界のアプリケーションによるネットワーク分析の基盤となる。 ローカルディファレンシャルプライバシ(LDP)との統合は、分散環境で機密グラフ情報を保護することで注目を集めている。 しかし、既存のLDPフレームワークはほとんどがアドホックであり、三角形や星のような特定のパターンに対してのみソリューションを提供する。 任意のグラフパターンを数えるための一般的なメカニズムは、非巡回パターンのサブクラスであっても、未解決の問題のままである。 このギャップを埋めるために、 LDP の下で任意の非巡回パターンを数えるための最初の一般解を提案する。 分散データからのパターン構築の一般化と,構築中のノード重複の排除という,2つの基本的な課題に対処する。 最初の課題に対処するために,複数の通信ラウンドにまたがるパターンを段階的に構築する LDP に適した再帰的サブパターンカウントフレームワークを提案する。 第2の課題は、計算中に各ノードをパターンのユニークな位置に制限するランダムマーキング手法を適用することである。 我々のメカニズムは強い実用性を保証する:$k$エッジを持つ任意の非巡回グラフパターンに対して、$\tilde{O}(\sqrt{N}d(G)^k)$の加算誤差を達成し、$N$はノード数、$d(G)$は入力グラフ$G$の最大次数である。 複数の非循環パターンをまたいだ実世界のグラフデータセットの実験により、我々のメカニズムは実用性の向上に46ドル-2600ドル、通信コストの削減に300ドル-650ドルを要した。

関連論文リスト

• Universal Hirschberg for Width Bounded Dynamic Programs [0.0]
  ヒルシュベルクのアルゴリズムは、格子動的プログラム(DP)上の中点二項による$O(N2)$から$O(N)$へ、最も長い共通部分列問題の空間複雑性を減少させる。 我々は、その基礎となるアイデアが、有向非巡回グラフ(DP DAG)に局所的依存を持つ広範な動的プログラムのクラスに一般化されることを示す。 前方シングルパスモデルでは$()$空間項は避けられないことを示し、ストリーミング設定における推測される$sqrtT$-type障壁について議論する。
  論文  参考訳（メタデータ） (2025-12-10T22:26:22Z)
• Learning from one graph: transductive learning guarantees via the geometry of small random worlds [8.781923502647055]
  我々は,低次元メートル法埋め込みによる大規模グラフの幾何正則性を活用する新しい集中度測定ツールを開発した。 まず、任意の決定論的 $k$-vertex グラフと、ErdHos-R'enyi グラフ $mathbfG=mathbfG(k,p)$ in the regime $p in the MathcalO((log (k)/k)1/2) で鍵幾何学的性質を共有するランダムグラフについて述べる。
  論文  参考訳（メタデータ） (2025-09-08T17:13:28Z)
• Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation [46.17999216122895]
  本稿では,新しいDGC手法である underlinetextbfComplementary underlinetextbfMulti-underlinetextbfView を提案する。 CMV-NDはグラフ構造情報を完全だが非冗長な方法で複数のビューに前処理する。 CMV-NDは,6つのグラフデータセットの実験結果から,様々な手法の性能を著しく向上させることが示された。
  論文  参考訳（メタデータ） (2025-07-09T13:42:43Z)
• Scalable Graph Generative Modeling via Substructure Sequences [50.32639806800683]
  本稿では,グラフ生成用トランスフォーマー事前学習フレームワークである生成グラフパターンマシン(G$2$PM)を紹介する。 G$2$PMはグラフインスタンス(ノード、エッジ、グラフ全体)をサブ構造のシーケンスとして表現する。 それは、一般化可能かつ伝達可能な表現を学ぶために、シーケンスに関する生成的事前学習を採用する。
  論文  参考訳（メタデータ） (2025-05-22T02:16:34Z)
• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  本稿では,グラフサブストラクチャから直接学習することで,メッセージパッシングをバイパスする新しいフレームワークであるNeural Graph Pattern Machine(GPM)を紹介する。 GPMはタスク関連グラフパターンを効率的に抽出し、エンコードし、優先順位付けする。
  論文  参考訳（メタデータ） (2025-01-30T20:37:47Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。 植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
  論文  参考訳（メタデータ） (2024-02-01T03:39:01Z)
• Analysis and Approximate Inference of Large Random Kronecker Graphs [4.417282202068703]
  大規模なランダムクロネッカーグラフの隣接性は分解可能であることを示す。 本稿では,鍵グラフパラメータを推論するデノワーズ・アンド・ソルブの手法を提案する。
  論文  参考訳（メタデータ） (2023-06-14T13:09:38Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。 AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。 本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
  論文  参考訳（メタデータ） (2021-05-22T07:05:48Z)

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

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