  Deep ReLU Networks can be decomposed into a collection of linear models, each
defined in a region of a partition of the input space. This paper provides
three results extending this theory. First, we extend this linear
decompositions to Graph Neural networks and tensor convolutional networks, as
well as networks with multiplicative interactions. Second, we provide proofs
that neural networks can be understood as interpretable models such as
Multivariate Decision trees and logical theories. Finally, we show how this
model leads to computing cheap and exact SHAP values. We validate the theory
through experiments with on Graph Neural Networks.
