The number of homomorphisms from a finite graph \(F\) to the complete graph \(K_n\) is the evaluation of the chromatic polynomial of \(F\) at \(n\). Suitably scaled, this is the Tutte polynomial evaluation \(T(F;1-n,0)\) and an invariant of the cycle matroid of \(F\). De la Harpe and Jaeger \cite{dlHJ95} asked more generally when is it the case that a graph parameter obtained from counting homomorphisms from \(F\) to a fixed graph \(G\) depends only on the cycle matroid of \(F\). They showed that this is true when \(G\) has a generously transitive automorphism group (examples include Cayley graphs on an abelian group, and Kneser graphs). Using tools from multilinear algebra, we prove the converse statement, thus characterizing finite graphs \(G\) for which counting homomorphisms to \(G\) yields a matroid invariant. We also extend this result to finite weighted graphs \(G\) (where to count homomorphisms from \(F\) to \(G\) includes such problems as counting nowhere-zero flows of \(F\) and evaluating the partition function of an interaction model on \(F\)).