(1) There are usually some nodes of very high degree and traversing those nodes will explode your query, (2) if you are following N links and the average degree is d, you are going to come across dᴺ nodes and that is a lot of nodes as N gets big!
Tim-Berners Lee told me that if you can't send the whole graph you should send a subset of the graph that contains the most important facts.
It's a right answer but also a frustrating one to a programmer who sees correct implementation of algorithms to mean that you get the ticket done and they don't come at you with a ticket about it again. That is, that query I'm writing is part of an algorithm that depends on getting a certain answer and getting an uncertain answer for one query is like some spoiled milk that ruins the whole batch.