論文の概要: Trinqet: Private Triangle and Quadrangle Counting over Distributed Graphs

• arxiv url: http://arxiv.org/abs/2609.14737v1
• Date: Sun, 13 Sep 2026 18:59:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:05.91164
• Title: Trinqet: Private Triangle and Quadrangle Counting over Distributed Graphs
• Title（参考訳）: Trinqet: 分散グラフ上のプライベートな三角形と四角数
• Abstract要約: Trinqetは、プライベートな三角形と四角数のグラフ解析システムである。 斬新な技法を駆使して、華麗さを生かしている。 評価では、実行時に5つのベースラインを最大105まで上回ります。
• 参考スコア（独自算出の注目度）: 3.638424730268566
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Triangle and quadrangle counts are core statistics in graph analysis. Yet many real-world graphs are distributed across multiple parties and encode highly sensitive relationships, precluding direct data sharing. Secure multi-party computation (MPC) provides a principled alternative, but introduces a fundamental tension: the protocol must hide the graph's topology, forcing fully data-oblivious operations over all potential edges--while real-world graphs are extremely sparse, making most of this work wasted. We propose Trinqet, a system that resolves this tension through new MPC-friendly algorithms for private triangle and quadrangle detection. Trinqet safely exploits sparsity using a suite of novel techniques that eliminate vast numbers of unnecessary operations while preserving strong security in the malicious threat model. Trinqet supports both counting and enumeration and, in our evaluation, outperforms all five baselines by up to 10^5 in runtime.
• Abstract（参考訳）: 三角数と四角数(英語版)はグラフ解析における中心となる統計である。 しかし、多くの実世界のグラフは複数のパーティに分散し、直接データ共有を前に非常に敏感な関係をエンコードする。 プロトコルはグラフのトポロジを隠さなければならないため、すべての潜在的なエッジに対して完全なデータ公開操作を強制しなければならない。 我々は,このテンションを,プライベートな三角形と四角い検出のための新しいMPCフレンドリなアルゴリズムによって解決するシステムであるTrinqetを提案する。 Trinqetは、悪意のある脅威モデルにおける強力なセキュリティを維持しながら、膨大な数の不要な操作を排除した、一連の新しいテクニックを使用して、疎結合を安全に活用する。 Trinqetはカウントと列挙の両方をサポートし、我々の評価では、実行時に最大10^5までの5つのベースラインを上回ります。

関連論文リスト

• Multi-view Graph Condensation via Tensor Decomposition [3.3346316632716313]
  グラフニューラルネットワーク(GNN)は、薬物発見、物体検出、ソーシャルメディア分析、レコメンダシステム、テキスト分類など、様々な現実世界の応用において顕著な結果を示してきた。 巨大なポテンシャルとは対照的に、それらを大規模グラフでトレーニングすることは、そのストレージと処理に必要なリソースのため、重大な計算上の課題を示す。 グラフ凝縮は、GNNの予測性能を維持しながら、元のグラフの本質的な情報を保存する合成コンパクトグラフを学習することで、これらの要求を減らすための有望な解決策として現れてきた。
  論文  参考訳（メタデータ） (2025-08-20T01:02:18Z)
• Practical and Accurate Local Edge Differentially Private Graph Algorithms [11.49857418691547]
  我々は、kコア分解と三角形カウントという2つの基本グラフ統計量に対して、新しい LDP アルゴリズムを導入する。 提案手法は、入力依存のプライベートグラフ特性、特にグラフの退化性と最大度を活用して、理論的有用性を向上させる。 我々のkコア分解は正確な値の3倍以内の誤差を達成し、Dhulipalaなどのベースラインで131倍の誤差をはるかに上回っている。
  論文  参考訳（メタデータ） (2025-06-25T20:54:07Z)
• GRAND : Graph Reconstruction from potential partial Adjacency and Neighborhood Data [4.893653298798788]
  セキュアなマルチパーティ計算のような暗号手法は、各参加者のデータに集中することなく、分散グラフの機能のセキュアな計算に使用できる。 本稿では,グラフの隣接行列を再構成する手法を提案する。 共役行列のみを観測する2つの逆数モデルと、元のグラフの部分的知識を持つ知識のある2つのモデルを考える。
  論文  参考訳（メタデータ） (2024-12-03T09:42:28Z)
• STAT: Shrinking Transformers After Training [72.0726371426711]
  微調整なしで変圧器モデルを作成するための簡単なアルゴリズムSTATを提案する。 STATは、次の層の重みを補正して精度を保ちながら、注意頭とニューロンの両方をネットワークから排除する。 われわれのアルゴリズムは、BERTを圧縮するのに数分を要し、単一のGPUを用いて7Bパラメータを持つモデルを圧縮するのに3時間もかからない。
  論文  参考訳（メタデータ） (2024-05-29T22:59:11Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• CARGO: Crypto-Assisted Differentially Private Triangle Counting without Trusted Servers [19.049132615031674]
  我々はCARGOという暗号支援の差分私的三角形計数システムを提案する。 CARGOは中央モデルと同様の高ユーティリティを実現するが、ローカルモデルのような信頼できるサーバは必要としない。
  論文  参考訳（メタデータ） (2023-12-20T11:28:20Z)
• HUGE: Huge Unsupervised Graph Embeddings with TPUs [6.108914274067702]
  グラフ埋め込み(Graph Embedding)は、グラフ内のノードを連続的に表現するプロセスである。 高帯域幅メモリを利用した高性能グラフ埋め込みアーキテクチャを提案する。 実・合成大規模データセット上での埋め込み空間の品質を検証する。
  論文  参考訳（メタデータ） (2023-07-26T20:29:15Z)
• Partition and Code: learning how to compress graphs [50.29024357495154]
  まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。 提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
  論文  参考訳（メタデータ） (2021-07-05T11:41:16Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。 AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。 本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
  論文  参考訳（メタデータ） (2021-05-22T07:05:48Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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