Renormalization in local quantum field theory relies on the possibility to subtract all subdivergences in a Feynman diagram as described for example by Zimmermann’s forest formula or the Connes-Kreimer Hopf algebra. Here we show how this can be generalized to field theories with combinatorially non-local interactions such as matrix or tensor field theories. In particular, this gives a general recipe for renormalization of various field-theory approaches to quantum gravity.