SIGMOD 2026: Shared Computation for Query Subgraph Matching & Fast MPC Shortest Paths

In this session we examine two recent SIGMOD 2026 papers that address efficiency and privacy challenges in large‑scale graph analytics.

Beyond Maximum Common Subgraph (MASC)

The authors observe that existing multi‑query subgraph matching approaches focus on maximizing the size of the maximum common subgraph, which does not guarantee maximal reuse of computation across queries. They argue that the key to performance is whether different queries share candidate vertices and can reuse local matching processes.

To exploit this, they introduce the MASC framework , shifting the optimization goal from “maximizing common structure” to “maximizing shared computation”. MASC implements three sharing mechanisms:

Shared filtering of candidate vertices.

Shared access to candidate sets.

Shared reuse of partial match structures.

By eliminating redundant work, MASC achieves up to two orders of magnitude speedup over prior methods in their experiments.

PrivHop: Scalable Privacy‑Preserving Shortest Path via MPC

Shortest‑path distance computation is fundamental for many applications, but when graph data resides with mutually distrustful parties, direct data sharing incurs privacy and compliance risks.

The paper proposes PrivHop , a framework that integrates 2‑hop labeling with secure multi‑party computation (MPC). PrivHop first builds a Hop‑Boundary index and a boundary graph offline, converting a global shortest‑path query into a smaller, secure computation on the boundary graph. It also incorporates a differentially private dynamic pruning strategy to reduce the number of online query iterations.

Experimental results show that PrivHop scales to graphs with millions of nodes and reduces both runtime and communication overhead by roughly 10^6× compared with existing approaches.

Both works demonstrate how algorithmic redesign—maximizing shared computation in subgraph matching and combining indexing with MPC for privacy—can unlock massive efficiency gains for graph‑centric workloads.