Mike,
du bör kunna lagra dina relationsdata i grafdatabasen. Dess höga prestanda för att korsa stora grafer kommer från lokalitet, det vill säga du kör inte frågor globalt utan istället startar en uppsättning noder (vilka är lika med dokument i ditt fall, som slås upp av ett index. du kan till och med lagra start-nod- id för snabb åtkomst i dina mongodokument). Därifrån kan du korsa godtyckligt stora vägar i konstant tid (wrt datamängdsstorlek).
Vilka är dina övriga krav (d.v.s. datamängdsstorlek, antal samtidiga åtkomster etc, relations-/grafkomplexitet).
Dina frågor är en riktigt bra passform för grafdatabasen och lätt att uttrycka i dess termer.
Jag skulle föreslå att du bara tar en graphdb som neo4j och gör en snabb spik med din domän för att verifiera den allmänna genomförbarheten och även ta reda på ytterligare frågor du skulle vilja ha besvarat innan du investerar i den andra tekniken.
P.S. Om du inte hade börjat ännu, kunde du också ha gått med en ren graphdb-metod då grafdatabaser är en superset av dokumentdatabaser. Och du talar hellre om domän i ditt fall än bara generiska dokument. (T.ex. structr är ett CMS byggt ovanpå Neo4j).