Exactly the same as you, I was just trying out neo4j today with a small dataset (30mb) and was getting memory exceptions trying to add a relationship.
e.g.,
//grabs literally EVERY node in your database
MATCH (Person)-[KNOWS]-(Friend)
//only the people who have a KNOWS relationship between them
MATCH (person:Person)-[:KNOWS]-(Friend:Person)