Hi Will,
Relationships can only exists between nodes of a single database; they cannot span between nodes in multiple databases. Selection and traversal is based upon the number of relationships on the node itself (limited also in type and/or direction as well), and not the total number of nodes or the total number of relationships in the graph, and at that point you're pointer hopping between nodes to attached relationships to the node at the other end etc.
So nothing has changed about the fundamentals here.
If you're querying across multiple graphs with Fabric, assuming that you have sharded the same kind of data across multiple databases, then you have delegated the work to those databases to execute in parallel, then retrieve results over the network (assuming that they're remote databases instead of local databases on the current dbms), and then any further work that needs to be done on the query. So there is parallel execution in play, and there is also potentially network I/O in play, but neither of these changes the efficiency of traversing through the graph based upon Neo4j's native graph implementation.
