Kiefel et al. introduce convolutional neural networks based on the permutohedral lattice. The main idea is the construction of a permutohedral lattice, replacing the regular grid in two or three dimension used for convolutions. In this sense, convolutional layers are replaced by the following operations:
An illustration can be found in Figure 1. According to Kiefel et al., the main advantage of this construction is the ability to train convolutional neural networks on sparse input data (in their paper, this is demonstrated on the MNIST  dataset). In another application scenario, the permutohedral lattice allows to incorporate more complex invariances such as rotation (in contrast to convolutions on a regular grid which are usually only invariant to translation).
Unfortunately, Kiefel et al. do not give details on training permutohedral lattice convolutional neural networks as they omit the corresponding backpropagation rules. Furthermore, the experiments are not discussed in detail.