<p>The very general intuition is that the larger the symmetry group of a property, the easier it is to <em>analyze</em> its testability. </p>

<p>The idea is the following. Suppose you have a property $\mathcal{P}$, defined as a collection of subsets of some domain $D$, and suppose that $\mathcal{P}$ is invariant under a permutation $\pi : D \to D$. In other words, a subset $S \subseteq D$ is in $\mathcal{P}$ iff $\pi(S)$ is also in $\mathcal{P}$. In testing, we want to determine whether a given set $S$ is in $\mathcal{P}$ or "far" from $\mathcal{P}$ by choosing a small number of points $X_1,\dots,X_q \in D$, querying whether each of them is a member of $S$ or not, and then making a decision based on the results of the queries. Suppose that a particular choice of points $z_1,\dots,z_q \in D$ constitutes a valid test. Then, the observation is that $\pi^{-1}(z_1),\dots,\pi^{-1}(z_q)$ also must constitute a valid test. Because using the test $\pi^{-1}(z_1),\dots,\pi^{-1}(z_q)$ on $S$ is the same as using the test $z_1, \dots, z_q$ on $\pi(S)$, and we know that $S \in \mathcal{P}$ iff $\pi(S) \in \mathcal{P}$. So, if $\mathcal{P}$ has a group of symmetry $\Pi \leq \mathsf{Sym}(D)$, then the entire orbit $\{(\pi(z_1),\dots,\pi(z_q)): \pi \in \Pi\}$ consists of valid tests. Thus, the larger the group $\Pi$ is, the more tests can be generated from a single test, and in fact, for many natural invariance groups, all possible tests can be generated from the orbits of a very restricted class of tests. When this is the case, it becomes much easier to give conditions for when a property is testable and when it's not.</p>

<p>Now, coming back to graph properties, because every graph property is invariant under relabeling of vertices, <a href="http://onlinelibrary.wiley.com/doi/10.1002/rsa.10078/abstract">Goldreich and Trevisan (2003)</a> formalized this above argument to show that the test for any graph property consists of querying induced subgraphs from the given graph. This result was crucial in a later combinatorial characterization of testability for graph properties.</p>

<p>In your question, you seem to be asking what happens if there are even more symmetries known for the graph property at hand. As far as I know, there's no general study of this question, mainly because there's already a precise characterization of testability for general graph properties. It might be interesting to ask which graph properties are "easily testable", meaning the query complexity is polynomial in the proximity parameter, and here there's no general characterization known...so putting additional symmetry restrictions on the property might make answering the question easier.</p>

CC BY-SA 3.0
2011-12-21T02:41:31.630Z
2011-12-21T02:41:31.630Z
arnab
<p>A property is said to be <em>invariant under a permutation $\pi$</em> if permuting the data points by this permutation leaves the property unchanged. </p>

<p>Invariance under permutations seems to help with property testing, see e.g. <a href="http://madhu.seas.harvard.edu/papers/2007/apt-full.pdf" rel="nofollow">Algebraic Property Testing: The Role of Invariance</a> by Tali Kaufman and Madhu Sudan, <a href="http://eccc.hpi-web.de/report/2008/040/" rel="nofollow">Property Testing of Equivalence under a Permutation Group Action</a> by Sourav Chakraborty and Laszlo Babai, and <a href="http://www.wisdom.weizmann.ac.il/~oded/PTW/mms.pdf" rel="nofollow">Invariance in Property Testing</a> by Madhu Sudan.</p>

<p>What is the general intuition for the invariance under permutations helping testing properties, e.g. testing properties of graphs?</p>

CC BY-SA 3.0
2011-12-20T21:42:30.667Z
Aren't most interesting graph properties already invariant ?
Suresh Venkat
CC BY-SA 3.0
2011-12-21T02:11:38.227Z
Since you said "data points" instead of "vertices" I'm wondering whether you mean an information graph http://en.wikipedia.org/wiki/Information_graphics rather than a mathematical graph http://en.wikipedia.org/wiki/Graph_%28mathematics%29 . Could you give a little more detail? The question is vague enough that I'm not really sure what you're asking.
Huck Bennett
<graph-theory><lg.learning><property-testing>
Invariance in Property Testing
Anonymous
# Invariance in Property Testing

(Asked by: username_0 on 2011-12-20)

A property is said to be *invariant under a permutation $\pi$* if permuting the data points by this permutation leaves the property unchanged.

Invariance under permutations seems to help with property testing, see e.g. [Algebraic Property Testing: The Role of Invariance](http://madhu.seas.harvard.edu/papers/2007/apt-full.pdf) by Tali Kaufman and Madhu Sudan, [Property Testing of Equivalence under a Permutation Group Action](http://eccc.hpi-web.de/report/2008/040/) by Sourav Chakraborty and Laszlo Babai, and [Invariance in Property Testing](http://www.wisdom.weizmann.ac.il/~oded/PTW/mms.pdf) by Madhu Sudan.

What is the general intuition for the invariance under permutations helping testing properties, e.g. testing properties of graphs?

**Tags:** graph-theory, lg.learning, property-testing
> **Comments:**
> **username_1**: Aren't most interesting graph properties already invariant ?  
> **username_2**: Since you said "data points" instead of "vertices" I'm wondering whether you mean an information graph http://en.wikipedia.org/wiki/Information_graphics rather than a mathematical graph http://en.wikipedia.org/wiki/Graph_%28mathematics%29 . Could you give a little more detail? The question is vague enough that I'm not really sure what you're asking.  

---

## 1 answers

### Answer by username_3 on 2011-12-21. Score: 6 | Accepted answer

The very general intuition is that the larger the symmetry group of a property, the easier it is to *analyze* its testability.

The idea is the following. Suppose you have a property $\mathcal{P}$, defined as a collection of subsets of some domain $D$, and suppose that $\mathcal{P}$ is invariant under a permutation $\pi : D \to D$. In other words, a subset $S \subseteq D$ is in $\mathcal{P}$ iff $\pi(S)$ is also in $\mathcal{P}$. In testing, we want to determine whether a given set $S$ is in $\mathcal{P}$ or "far" from $\mathcal{P}$ by choosing a small number of points $X\_1,\dots,X\_q \in D$, querying whether each of them is a member of $S$ or not, and then making a decision based on the results of the queries. Suppose that a particular choice of points $z\_1,\dots,z\_q \in D$ constitutes a valid test. Then, the observation is that $\pi^{-1}(z\_1),\dots,\pi^{-1}(z\_q)$ also must constitute a valid test. Because using the test $\pi^{-1}(z\_1),\dots,\pi^{-1}(z\_q)$ on $S$ is the same as using the test $z\_1, \dots, z\_q$ on $\pi(S)$, and we know that $S \in \mathcal{P}$ iff $\pi(S) \in \mathcal{P}$. So, if $\mathcal{P}$ has a group of symmetry $\Pi \leq \mathsf{Sym}(D)$, then the entire orbit $\{(\pi(z\_1),\dots,\pi(z\_q)): \pi \in \Pi\}$ consists of valid tests. Thus, the larger the group $\Pi$ is, the more tests can be generated from a single test, and in fact, for many natural invariance groups, all possible tests can be generated from the orbits of a very restricted class of tests. When this is the case, it becomes much easier to give conditions for when a property is testable and when it's not.

Now, coming back to graph properties, because every graph property is invariant under relabeling of vertices, [Goldreich and Trevisan (2003)](http://onlinelibrary.wiley.com/doi/10.1002/rsa.10078/abstract) formalized this above argument to show that the test for any graph property consists of querying induced subgraphs from the given graph. This result was crucial in a later combinatorial characterization of testability for graph properties.

In your question, you seem to be asking what happens if there are even more symmetries known for the graph property at hand. As far as I know, there's no general study of this question, mainly because there's already a precise characterization of testability for general graph properties. It might be interesting to ask which graph properties are "easily testable", meaning the query complexity is polynomial in the proximity parameter, and here there's no general characterization known...so putting additional symmetry restrictions on the property might make answering the question easier.


---

