論文の概要: VerfGraph: Efficient Zero-Knowledge Verifiable Graph Query Evaluation System

• arxiv url: http://arxiv.org/abs/2611.04240v1
• Date: Tue, 03 Nov 2026 03:24:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-11 00:54:18.094311
• Title: VerfGraph: Efficient Zero-Knowledge Verifiable Graph Query Evaluation System
• Title（参考訳）: VerfGraph: 効率的なゼロ知識検証グラフクエリ評価システム
• Abstract要約: 検証可能なグラフクエリ評価のためのゼロ知識システムであるVerfGraphを提案する。 本稿では,コア展開と最短パス演算のための新しい演算子保護手法を提案する。 また、カウントと重み付けされたショートパス演算子に対する正当性を導入し、検証可能なグラフクエリのクラスを広げる。
• 参考スコア（独自算出の注目度）: 9.807066555842184
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph databases are often used to manage relationship-rich data, whose graph structure and attributes may be sensitive. In many applications, a database owner or a service provider evaluates queries over a private graph for a client. Because the graph cannot be fully disclosed and independently re-executing the query may be impractical, the client cannot directly verify the returned result. This creates a need for verifiable graph query evaluation that preserves data confidentiality. We present VerfGraph, a zero-knowledge system for verifiable graph query evaluation, which enables a client to verify that the query result was correctly computed over a committed graph data, without revealing private graph records or intermediate query values beyond the public inputs and what is implied by the query result. Building on the expansion-centric model introduced by the state-of-the-art zero-knowledge verifiable graph query evaluation system ZKGraph (ICDE'26), VerfGraph achieves more efficient and expressive zero-knowledge verifiable graph query evaluation by advancing design in two key ways. First, we propose novel operator-proof methods for core expansion and shortest-path operations that reduce costly sorting and comparison checks and eliminate edge canonicalization for bidirectional expansion. Furthermore, we introduce correctness proofs for count and weighted shortest-path operators, broadening the class of graph queries that can be verified. We evaluate VerfGraph using the LDBC Social Network Benchmark. Compared with ZKGraph on complex IC queries, VerfGraph achieves $33.9\times$-$59.7\times$ speedups in proof generation and reduces peak prover memory by factors of $4.5\times$-$6.6\times$, while maintaining millisecond-level verification and producing sub-MB proofs.
• Abstract（参考訳）: グラフデータベースは、しばしば関係に富むデータを管理するために使われ、そのグラフ構造と属性は敏感である。 多くのアプリケーションでは、データベース所有者またはサービスプロバイダがクライアントのプライベートグラフ上でクエリを評価します。 グラフは完全には公開されず、クエリを独立して再実行することは現実的ではない可能性があるため、クライアントは返された結果を直接検証することはできない。 これにより、データの機密性を保持する検証可能なグラフクエリ評価の必要性が生じる。 本稿では,グラフクエリ評価を検証可能なゼロ知識システムであるVerfGraphを提案する。これは,クエリ結果が,公開入力を超えるプライベートグラフレコードや中間クエリ値や,クエリ結果にインプットされるものを明らかにすることなく,コミットグラフデータ上で正しく計算されたことをクライアントが確認することを可能にする。 最先端のゼロ知識検証グラフクエリ評価システムZKGraph(ICDE'26)によって導入された拡張中心モデルに基づいて、VerfGraphはより効率的で表現力豊かなゼロ知識検証グラフクエリ評価を実現する。 まず,高コストなソートと比較チェックを削減し,双方向展開のためのエッジ正準化を解消する,コア展開と最短パス演算のための新しい演算子保護手法を提案する。 さらに、カウントと重み付けされたショートパス演算子に対する正当性証明を導入し、検証可能なグラフクエリのクラスを広げる。 LDBC Social Network Benchmark を用いた VerfGraph の評価を行った。 複雑なICクエリのZKGraphと比較すると、VerfGraphは33.9\times$-59.7\times$を証明生成のスピードアップし、ピーク証明メモリを4.5\times$-6.6\times$の係数で削減し、ミリ秒レベルの検証とサブMB証明の生成を維持できる。

関連論文リスト

• SelfGraphRAG: Bridging the Supervision Gap in Graph-Based RAG with Synthetic QA Generation [10.08021023788401]
  SelfGraphRAGは知識グラフ構造から直接質問応答ペアを生成し、クエリ条件のグラフ検索をトレーニングするフレームワークである。 本稿では,SelfGraphRAGにより,埋め込みベースラインよりも検索精度と下流推論性能が向上することを示す。
  論文  参考訳（メタデータ） (2026-08-25T20:18:05Z)
• VeriGraph: Towards Verifiable Data-Analytic Agents [71.17693022916896]
  LLMをベースとしたエージェントは、データ集約分析タスクにおいて強力な能力を示してきたが、その出力は滅多に検証されていない。 We propose VeriGraph, a traceable neuro-symbolic reasoning framework that agent can construct an explicit heterogeneous evidence directed acyclic graph。 以上の結果から,明示的なエビデンスグラフ構築がデータ分析エージェントの検証に期待できる道のりであることが示唆された。
  論文  参考訳（メタデータ） (2026-06-15T11:50:56Z)
• AutoGraph-R1: End-to-End Reinforcement Learning for Knowledge Graph Construction [60.51319139563509]
  強化学習(RL)を用いたタスクパフォーマンスのKG構築を直接最適化する最初のフレームワークであるAutoGraph-R1を紹介する。 我々は2つの新しいタスク対応報酬関数を設計し、1つは知識担体としてのグラフと、もう1つは知識指標としてのグラフを設計する。 私たちの研究は、構築とアプリケーションの間のループを閉じることが可能であることを示している。
  論文  参考訳（メタデータ） (2025-10-17T06:03:36Z)
• Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMs [15.558119182035995]
  検索型拡張フレームワーク(GRRAF)を用いた新しい学習不要なグラフ推論手法を提案する。 GRRAFは、大規模な言語モデル(LLM)のコード生成機能とともに、検索拡張生成(RAG)を活用して、幅広いグラフ推論タスクに対処する。 GraphInstructデータセットの実験的評価により、ほとんどのグラフ推論タスクにおいて、GRRAFが100%の精度を達成することが明らかになった。
  論文  参考訳（メタデータ） (2025-09-16T06:58:58Z)
• Graph Inference with Effective Resistance Queries [2.2349172369559156]
  一対の頂点間の有効抵抗(ER)を返すオラクルを用いてグラフ推論を研究する。 ERクエリから$n$-vertexグラフを一意に再構築できることは知られているが、他にはほとんど知られていない。
  論文  参考訳（メタデータ） (2025-02-25T16:37:25Z)
• An Automatic Graph Construction Framework based on Large Language Models for Recommendation [49.51799417575638]
  本稿では,大規模言語モデルに基づく自動グラフ構築フレームワークであるAutoGraphを紹介する。 LLMはユーザ好みとアイテムの知識を推論し、セマンティックベクターとして符号化する。 潜在因子は、ユーザ/イテムノードをリンクする余分なノードとして組み込まれ、結果として、深いグローバルビューセマンティクスを持つグラフとなる。
  論文  参考訳（メタデータ） (2024-12-24T07:51:29Z)
• NAS-Bench-Graph: Benchmarking Graph Neural Architecture Search [55.75621026447599]
  NAS-Bench-Graphは、GraphNASの統一的、再現可能、効率的な評価をサポートする調整されたベンチマークである。 具体的には,26,206のユニークなグラフニューラルネットワーク(GNN)アーキテクチャを網羅した,統一的で表現力のあるコンパクトな検索空間を構築する。 提案したベンチマークに基づいて,GNNアーキテクチャの性能を検索テーブルから直接取得できるが,それ以上の計算は行わない。
  論文  参考訳（メタデータ） (2022-06-18T10:17:15Z)
• Interactive Visual Pattern Search on Graph Data via Graph Representation Learning [20.795511688640296]
  視覚分析システムGraphQは、ループ内、サンプルベース、サブグラフパターン検索をサポートする。 高速で対話的なクエリをサポートするために、グラフニューラルネットワーク(GNN)を使用して、グラフを固定長潜在ベクトル表現としてエンコードする。 また,NuroAlignと呼ばれるノードアライメントのための新しいGNNを提案し,クエリ結果の検証と解釈を容易にする。
  論文  参考訳（メタデータ） (2022-02-18T22:30:28Z)

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

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