PROPs and their variants are extremely general and powerful machines that encode operations with multiple inputs and multiple outputs. In this respect PROPs can be viewed as generalizations of operads that would allow only a single output. Variants of PROPs are important in several mathematical fields, including string topology, topological conformal field theory, homotopical algebra, deformation theory, Poisson geometry, and graph cohomology. The purpose of this monograph is to develop, in full technical detail, a unifying object called a generalized PROP. Then with an appropriate choice of pasting scheme, one recovers (colored versions of) dioperads, half-PROPs, (wheeled) operads, (wheeled) properads, and (wheeled) PROPs. Here the fundamental operation of graph substitution is studied in complete detail for the first time, including all exceptional edges and loops as examples of a new definition of wheeled graphs. A notion of generators and relations is proposed which allows one to build all of the graphs in a given pasting scheme from a small set of basic graphs using graph substitution. This provides information at the level of generalized PROPs, but also at the levels of algebras and of modules over them. Working in the general context of a symmetric monoidal category, the theory applies for both topological spaces and chain complexes in characteristic zero. This book is useful for all mathematicians and mathematical physicists who want to learn this new powerful technique