GlobalGraphOperations in Neo4j are not transactionally sound -- speed vs. consistency boolean.

    public static boolean isDeleted(final Node node) {
        try {
            node.getLabels().iterator().next();
            return false;
        } catch (final IllegalStateException e) {
            return true;
        }
    }
 
    public static boolean isDeleted(final Relationship relationship) {
        try {
            relationship.getType();
            return false;
        } catch (final IllegalStateException e) {
            return true;
        }
    }