マニュアルのmutable関係をみました。私の望んでいた動作は
これで実現できそうです。

type node = { id : string; mutable succs : node list }
type graph = { mutable nodes : node list }

let add_succ n1 n2 =
　　n1.succs <- n2 :: n1.succs

let add_node g n =
　　g.nodes <- n :: g.nodes

これなら実体の間でリンクが張られているので、サクセッサも
直接たどれます。
どうもお騒がせしました。