We continue our study of naturalness in nonrelativistic QFTs of the Lifshitz type, focusing on scalar fields that can play the role of Nambu-Goldstone (NG) modes associated with spontaneous symmetry breaking. Such systems allow for an extension of the constant shift symmetry to a shift by a polynomial of degree $P$ in spatial coordinates. These "polynomial shift symmetries" in turn protect the technical naturalness of modes with a higher-order dispersion relation, and lead to a refinement of the proposed classification of infrared Gaussian fixed points available to describe NG modes in nonrelativistic theories. Generic interactions in such theories break the polynomial shift symmetry explicitly to the constant shift. It is thus natural to ask: Given a Gaussian fixed point with polynomial shift symmetry of degree $P$, what are the lowest-dimension operators that preserve this symmetry, and deform the theory into a self-interacting scalar field theory with the shift symmetry of degree $P$? To answer this (essentially cohomological) question, we develop a new graph-theoretical technique, and use it to prove several classification theorems. First, in the special case of $P=1$ (essentially equivalent to Galileons), we reproduce the known Galileon $N$-point invariants, and find their novel interpretation in terms of graph theory, as an equal-weight sum over all labeled trees with $N$ vertices. Then we extend the classification to $P>1$ and find a whole host of new invariants, including those that represent the most relevant (or least irrelevant) deformations of the corresponding Gaussian fixed points, and we study their uniqueness.