Few thoughts on this:
I would try modelling your Neo4j domain model to include the attributes of each node in the graph. By separating your data into two different data stores you might limit some operations that you might want to do.
I guess it comes down to what you will be doing with your graph. If, for example, you want to find all the nodes connected to a specific node whose attributes (ie name, age.. whatever) are certain values, would you first have to find the correct node ID in your MySQL database and then go into Neo4j? This just seems slow and overly complicated when you could do all this in Neo4j. So the question is: will you need the attributes of a node when traversing the graph?
Will your data change or is it static? By having two separate data stores it will complicate matters.
Whilst generating statistics using a MySQL database might be easier than doing everything in Neo4j, the code required to traverse a graph to find all the nodes that meet a defined criteria isn’t overly difficult. What these stats are should drive your solution.
I can’t comment on the performance of the MySQL query to select node ids. I guess that comes down to how many nodes you will need to select and your indexing strategy. I agree about the performance side of things when it comes to traversing a graph though.
This is a good article on just this: MySQL vs. Neo4j on a Large-Scale Graph Traversal and in this case, when they say large, they only mean a million vertices/nodes and four million edges. So it wasn’t even a particularly dense graph.