If you really want a graph approach to this problem, I would recommend to have the properties of the cities as nodes, and link the cities to the nodes.
Therefore, you would have something along these lines :
(user)-[:visited]->(city)-[:has_property]->(property #i)
You could easily find similar cities by the number of links they have to the same properties.
You query would simply amount to a basic recommendation that can be implemented with cypher, with something along these lines (not tested, but you should get the idea) :
start A=node:users("")
match A-[:visited]->()-[:has_properties]->p
with distinct p as p
match p<-[r:has_properties]-cities
with distinct cities, count(r) as sim_score
order by sim_score desc limit 10
match cities<-[r:visited]-similar
return count(r) as score, similar
order by score desc limit 5
It works in 3 steps:
- get the properties of the cities visited by user A (the "feature extraction" part)
- then from the features, get the most similar cities
- and finally retrieve the similar users who have the same "profile"
For performance issue, you can calculate the cities similarities offline, because it is something that shouldn't change very often, and focus on the "real-time" only for users similarity, which is less predictable.
Also don't forget to put enough RAM to your server ;)