Comment by thesz

There are lattice-based RNNs applied as language models.

In fact, if you have a graph and a path-weighting model (RNN, TDCNN or Transformer), you can use beam search to evaluate paths through graphs.