Translating anti-vertex in cypher for graph databases and graph mining systems

An Anti-vertex is a declarative construct that indicates absence of a vertex, i.e., the resulting subgraph should not have a vertex in its specified neighborhood that matches the anti-vertex. Anti-vertices are natively supported in Peregrine, a state-of-the-art graph mining system, and has been proposed as a prototype extension to Cypher graph query language. The semantics of Anti-vertices have been well-established in accordance with semantics of subgraph matching, which includes isomorphism, homomorphism, and no-repeated-edge matching. This project focuses on enabling two cypher-based backends, Neo4j and Graphflow, to support anti-vertices. The two backends support anti-vertex queries by executing WHERE NOT EXISTS queries to match patterns based on the absence of a particular vertex. The query engine in Graphflow has been modified to support nested subqueries using the WHERE NOT EXISTS queries. The Cypher grammar in Graphflow is updated to accept anti-vertex query syntax as user input. The anti-vertex queries are translated to an appropriate WHERE NOT EXISTS queries by the backend. We have benchmarked the translated anti-vertex queries in Neo4j and Graphflow against the natively supported anti-vertex queries in Peregrine. The native anti-vertex query support in Peregrine performs significantly faster than the translated WHERE NOT EXISTS query in Graphflow and Neo4j. The performance gap highlights opportunities to improve graph database systems by natively support anti-vertex constructs.