Да, это не проблема с Neo4j, он запускает графики с миллионами или миллиардами узлов и отношений.
Вы можете легко создать PoC [Подтверждение концепции], импортировав свой график и затем выполнить операции с ним, которые вас интересуют.
Не могли бы вы описать некоторые подробностимодель предметной области и варианты использования / операции?