In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from having the property. (An algorithm can be asked to succeed with 1-sided or 2-sided error.)  A graph is $\epsilon$-far from having a property if no $\epsilon \binom{n}{2}$ edges can be added/subtracted to make it have the property.A property is said to be testable if it can be tested in the manner specified above in a sub-linear number of queries, or better yet, in a number of queries independent of $n$ (but not $\epsilon$).  The notion of what properties are can also be formalized, but it should be clear.There are many results characterizing what properties are testable, with many examples of natural testable properties.  However, I am not aware of many natural properties that are known to not be testable (say in a constant number of queries) -- one that I am familiar with is testing for isomorphism to a given graph.So, my question is: what natural graph properties are known not to be testable?
Natural, untestable graph properties
cc.complexity theory;machine learning;query complexity;property testing
In the adjacency matrix model, there is a lower bound of $\Omega(n)$ on the query complexity of testing whether an $n$ vertex graph consists of two isomorphic copies of some $n/2$-vertex graph (see Introduction to testing graph properties - Goldreich for a survey).Also, there are many lower bounds that depend on $n$ for testers with one-sided error, e.g.: testing $\rho$-Clique,$\rho$-Cut, and $\rho$-Bisection (see Property testing and its connection to learning and approximation - Goldreich, Goldwasser, Ron)Moreover, in the bounded degree graph model, testing 3-Colorability requires $\Omega(n)$ queries, whereas testing 2-Colorability (i.e., Bipartiteness) requires $\Omega(\sqrt n)$ (see Property testing in bounded degree graphs - Goldreich, Ron).