From Labels to Graph: what machine learning approaches to use?
Your graph is characterized by a set of nodes and edges. It means given a start point x, show me the next node z1, then from z1 show me z2 and so on. This looks like the definition of graph-searching algorithm.
However, maybe by definining a 'cost function' that you want to optimize (minimize or maximize) you can convert it to a supervised learning task. Basically, given a graph composed of weighted nodes and edges, you want to choose a subset (E,V) that minimzes the cost function.
I am not sure this problem fits a generative problem (as you emphasize on the word generate) whose goal is to learn a distribution.