Add directionality to the relationships.  This apparently speeds things up.

Some examples for creating even arbitrary relationship directions:
https://graphaware.com/neo4j/2013/10/11/neo4j-bidirectional-relationships.html

"Best practice to always include an arbitrary direction": http://stackoverflow.com/questions/16876378/neo4j-one-directional-two-directional-relationships

