A quasicancellation property for the direct product of graphs

We are motivated by the following question concerning the direct product of graphs. If A×C≅B×CA×C≅B×C, what can be said about the relationship between AA and BB? If cancellation fails, what properties must AA and BB share? We define a structural equivalence relation ∼∼ (called similarity) on graphs, weaker than isomorphism, for which A×C≅B×CA×C≅B×C implies A∼BA∼B. Thus cancellation holds, up to similarity. Moreover, if CC is bipartite, then A×C≅B×CA×C≅B×C if and only if A∼BA∼B. We conjecture that the prime factorization of connected bipartite graphs is unique up to similarity of factors, and we offer some results supporting this conjecture.