Renormalization in perturbative quantum field theory is based on a Hopf algebra of Feynman diagrams. A precondition for this is locality. Therefore one might suspect that non-local field theories such as matrix or tensor field theories cannot benefit from a similar algebraic understanding. Here I show that, on the contrary, perturbative renormalization of a broad class of such field theories is based in the same way on a Hopf algebra. Their interaction vertices have the structure of graphs. This gives the necessary concept of locality and leads to Feynman diagrams defined as “2-graphs” which generate the Hopf algebra. These results set the stage for a systematic study of perturbative renormalization as well as non-perturbative aspects, e.g....