Matt,
I have done something like this. The framework I've created uses a query language that allows the client to describe what it is interested in and then the server, as you say, essentially traverses the graph of resources on the server side.
I'm not using HAL, but the principle really doesn't change. I'm using Siren and much of the code is related to traversing the relations, so I would imagine the same concepts would apply in both cases.
To be honest, I was trying to figure out exactly what should be in the query language. I looked at various examples and tried to come up with something minimalistic yet sufficient. It is entirely possible that the query language could have been better, but it seems quite reasonable to me. It allows for not only selecting what relations it is interested in following, but it includes "skip/limit" functionality, sorting, filtering by resource properties and metadata.
--
Mike