arXiv:2611.04240v2 Announce Type: replace Abstract: Graph databases are widely used to manage relationship-rich data and support multi-hop traversal and shortest-path queries in applications such as financial risk control and social networks. When a client issues such queries to a database owner, the returned result may be incorrect. However, the client cannot directly verify it because the graph is typically large and private, making re-executing the query both infeasible and insecure. Verifiable and confidential graph query evaluation thus plays an important role in such applications. We present VerfGraph, a zero-knowledge verifiable graph query evaluation system, which enables a client to verify that the query result was correctly computed over a committed graph, without revealing anything beyond the public inputs and what is implied by the query result. While adopting the expansion-centric operator model introduced by ZKGraph (ICDE'26), VerfGraph improves both proving efficiency and query expressiveness in two key ways. First, we propose new proof methods for the core operators in ZKGraph, such as graph expansion and shortest path, that require substantially fewer expensive comparisons and eliminate edge canonicalization for bidirectional edge relations. Second, we introduce dedicated proofs for count and weighted shortest-path operators, which ZKGraph does not support, broadening the class of graph queries that can be verified. We evaluate VerfGraph using the LDBC Social Network Benchmark. Compared with the state-of-the-art zero-knowledge graph query system ZKGraph on complex IC queries, VerfGraph achieves $33.9\times$-$59.7\times$ speedups in proof generation and reduces peak prover memory by a factor of $4.5\times$-$6.6\times$, while maintaining millisecond-level verification and producing sub-MB proofs.