Product-like discrete structures appear e.g. in an attempt to model phenotypic evolution. This has lead to the question when a graph can be approximated either globally or locally as a non-trivial product of graphs. To investigate such structures we have developed algorithms for graph factorization that operate locally and hence can tolerate deviations from global product structures. Current work addresses the so-called square property of relations on the edge set of a graph. Some of its generalizations turn out to be intimately connected to quotient graphs that are factorizable even though the original graph is prime.