  Recent years have seen a surge in research on deep interpretable neural
networks with decision trees as one of the most commonly incorporated tools.
There are at least three advantages of using decision trees over logistic
regression classification models: they are easy to interpret since they are
based on binary decisions, they can make decisions faster, and they provide a
hierarchy of classes. However, one of the well-known drawbacks of decision
trees, as compared to decision graphs, is that decision trees cannot reuse the
decision nodes. Nevertheless, decision graphs were not commonly used in deep
learning due to the lack of efficient gradient-based training techniques. In
this paper, we fill this gap and provide a general paradigm based on Markov
processes, which allows for efficient training of the special type of decision
graphs, which we call Self-Organizing Neural Graphs (SONG). We provide an
extensive theoretical study of SONG, complemented by experiments conducted on
Letter, Connect4, MNIST, CIFAR, and TinyImageNet datasets, showing that our
method performs on par or better than existing decision models.
