Technical Summary: PathFinder: Returning Paths in Graph Queries

Problem Statement

Modern graph query languages, including SPARQL, Cypher, SQL/PGQ, and the emerging GQL standard, rely heavily on path queries. While SPARQL supports Regular Path Queries (RPQs) to identify pairs of nodes connected by paths matching a regular expression, it returns only the endpoints. In contrast, Cypher, SQL/PGQ, and GQL allow users to return the entire paths (witnesses) that satisfy these queries.

However, a significant gap exists between the theoretical capabilities of these languages and their practical implementation. Current graph database engines lack comprehensive support for returning paths under the full spectrum of 27 path modes defined by the GQL and SQL/PGQ standards. These modes include various restrictions (e.g., WALK, TRAIL, SIMPLE, ACYCLIC) and selectors (e.g., ANY, ALL SHORTEST, SHORTEST k, SHORTEST k GROUPS). Existing engines either:

1. Support all RPQs but cannot return paths (SPARQL engines).
2. Can return paths but only for a limited subset of regular expressions or path modes (property graph engines like Neo4j, Kuzu, Nebula).
3. Suffer from scalability issues, often failing to handle path queries efficiently due to the potential exponential number of matching paths.

Furthermore, while the theoretical complexity of finding simple paths or trails is known to be NP-complete, practical implementations often struggle to provide stable performance even for theoretically intractable queries on real-world data.

Methodology

The paper introduces PATHFINDER, a unified framework for evaluating RPQs and returning paths under all 27 GQL path modes. The core of the approach relies on the product graph construction, combining the input graph database $G$ with a non-deterministic finite automaton (NFA) $A$ derived from the regular expression of the query.

Core Algorithmic Principles

1. Product Graph Construction: The framework constructs a product graph $G \times A$ where nodes are pairs $(v, q)$ representing a node $v$ in the graph and a state $q$ in the automaton. Edges in the product graph correspond to transitions in the automaton that match edge labels in the graph.
2. Lazy Construction: The product graph is constructed lazily, meaning only the necessary portions are generated to evaluate the query, allowing for pipelined execution where results are returned as soon as they are detected.
3. Path Multiset Representation (PMR): The algorithms maintain a compact representation of all matching paths using search states. A search state typically includes the current node, automaton state, depth, and pointers to predecessor states, enabling the reconstruction of paths without storing them explicitly during the search.

Specific Algorithms for Path Modes

The paper details specific adaptations of the product graph search for different path modes:

• WALK Modes (ANY, ANY SHORTEST, ALL SHORTEST, ANY k, SHORTEST k, SHORTEST k GROUPS):

  • ANY/ANY SHORTEST: Uses standard BFS or DFS on the product graph. To handle non-determinism and ensure a single path per endpoint pair, the algorithm tracks visited states $(n, q)$ and uses a ReachedFinal set to prevent duplicate returns.
  • ALL SHORTEST: Extends BFS to track all shortest paths to a node. The search state includes a list of pointers (prevList) to all predecessors that yield a shortest path, allowing the enumeration of multiple shortest paths.
  • SHORTEST k / ANY k: Tracks paths of increasing lengths up to a limit $k$. The algorithm maintains counts of paths reaching each state to ensure termination and returns the $k$ shortest paths.
  • SHORTEST k GROUPS: Similar to the above but groups paths by length, returning all paths up to the $k$-th distinct length found.

• Restricted Modes (TRAIL, SIMPLE, ACYCLIC):

  • These modes are known to be NP-complete in the worst case. The framework employs a brute-force exploration of the product graph with pruning.
  • The isValid function checks if extending a path violates the specific restriction (e.g., repeating an edge for TRAIL or a node for SIMPLE).
  • While the worst-case complexity remains exponential, the approach is designed to be efficient on real-world graphs where the number of valid paths is often manageable.

Implementation and Integration

• Property Graphs: Implemented on top of MillenniumDB, an open-source graph engine. The syntax extends Cypher-like patterns to include path variables and modes (e.g., MATCH (src)=[MODE ?p rgx]=>(tgt)).
• SPARQL Extension: The framework extends SPARQL syntax to support path returning (e.g., src MODE (path AS ?p) tgt), demonstrating that existing RDF engines can be augmented with these capabilities.
• Execution Model: Algorithms are implemented using linear iterators for pipelined execution, ensuring that paths are returned on-the-fly rather than requiring the construction of the entire solution set before output.

Key Contributions

1. First Unified Framework: PATHFINDER is the first system to support returning paths for all 27 path modes prescribed by the GQL and SQL/PGQ standards for all regular path queries.
2. Algorithmic Novelty: It provides implementable algorithms based on the product graph construction that handle the complexities of path modes, including the handling of non-deterministic automata and the enumeration of multiple shortest paths or groups of paths.
3. SPARQL Extension: It demonstrates the feasibility of extending SPARQL to return path witnesses, bridging the gap between RDF and property graph query capabilities.
4. Practical Feasibility: Through extensive experimentation, the paper shows that despite theoretical hardness for certain modes (like TRAIL), the approach yields remarkably stable performance on real-world datasets.

Experimental Results

The authors evaluated PATHFINDER using three datasets: Pokec (social network), Wikidata (large-scale knowledge graph), and a synthetic Diamond graph (designed to have exponentially many paths).

• Performance: PATHFINDER consistently outperformed state-of-the-art engines (Neo4j, Nebula, Kuzu, Jena, Blazegraph, Virtuoso) by one to two orders of magnitude (10x–100x speedup).
• Scalability:
  • On Pokec, PATHFINDER maintained stable performance as path lengths increased, whereas other systems frequently timed out.
  • On Wikidata, PATHFINDER successfully processed 659 complex queries, while SPARQL engines (which do not return paths) were significantly slower, and property graph engines (Neo4j) timed out on the vast majority of queries.
  • On the Diamond graph, PATHFINDER demonstrated linear time complexity for WALK modes, while other engines exhibited exponential growth. For TRAIL modes, the Depth-First Search (DFS) variant of PATHFINDER proved superior to BFS in handling massive numbers of paths.
• Robustness: The system handled theoretically intractable queries (e.g., TRAIL on large graphs) with stable performance, suggesting that real-world data distributions mitigate the worst-case theoretical complexity.

Significance and Claims

The paper claims that PATHFINDER represents a significant step forward in graph query processing by unifying the theoretical capabilities of GQL/SQL/PGQ with practical implementation.

• Feasibility of Path Returning: The work proves that returning full path witnesses for complex RPQs is not only theoretically possible but practically efficient, even for modes previously considered intractable.
• Standard Compliance: It is the first engine to fully support the 27 path modes of the GQL standard, addressing a critical gap in current database technology.
• Extensibility: The successful integration into MillenniumDB and the extension to SPARQL demonstrate that these algorithms can be incorporated into existing database pipelines without requiring a complete rewrite of the underlying engine.
• Modest Future Outlook: The authors note that while the current implementation handles standard RPQs, future work will explore more expressive queries involving node and edge data properties, and further investigation is needed on how path-returning semantics integrate with the specific property path syntax of SPARQL.

In conclusion, PATHFINDER offers a sound, high-performance strategy for path-returning queries, challenging the notion that such features must come at the cost of scalability or require limiting the expressive power of the query language.