So in total there ~5 millions of nodes and 120 millions of such simple relations. Nodes ids are indexed with Btree index. Neo4j is running on AWS server with 4 vCPUs and 8 RAM. Not all nodes are directly linked, but by their child relations they do.
General goal is to find list of shortest paths between 2 nodes sorted by depth and sum of positions.