  Task-oriented dialogue systems typically rely on large amounts of
high-quality training data or require complex handcrafted rules. However,
existing datasets are often limited in size considering the complexity of the
dialogues. Additionally, conventional training signal inference is not suitable
for non-deterministic agent behaviour, i.e. considering multiple actions as
valid in identical dialogue states. We propose the Conversation Graph
(ConvGraph), a graph-based representation of dialogues that can be exploited
for data augmentation, multi-reference training and evaluation of
non-deterministic agents. ConvGraph generates novel dialogue paths to augment
data volume and diversity. Intrinsic and extrinsic evaluation across three
datasets shows that data augmentation and/or multi-reference training with
ConvGraph can improve dialogue success rates by up to 6.4%.
