A counterexample to the partition-graph de-anonymization conjecture

The comparison in Infeld, Conjecture 1 fails even when every user and every behavior has degree $4$. The counterexample uses $10$ users, and it extends to arbitrarily many users. Here a perfect matching is chosen uniformly, as in the conjecture.

For a bipartite graph $Q$, write $M(Q)$ for its number of perfect matchings. If $x$ is a user and $M_{xy}$ counts the perfect matchings containing $xy$, the expected number of matchings remaining after revealing the behavior of $x$ is

$$F_x(Q)=\frac{\sum_{y\sim x}M_{xy}^{\,2}}{M(Q)}.$$

Thus the optimizing attack leaves $F(Q)=\min_x F_x(Q)$ expected matchings. Since $\sum_{y\sim x}M_{xy}=M(Q)$, Cauchy–Schwarz gives

$$F_x(Q)\geq \frac{M(Q)}{d(x)}.$$

In particular, if all user degrees are at most $4$, then $F(Q)\geq M(Q)/4$. If $Q$ has an unchanged complete bipartite component $K_{4,4}$, equality holds: for a user in that component, each of the four behaviors occurs in exactly one quarter of the perfect matchings.

The two graphs

Let $C=K_{5,5}\setminus P$, where $P$ is a perfect matching. This is the $4$-regular component on five users in the partition construction of Section 3.2. It has

$$M(C)=5!\sum_{j=0}^{5}\frac{(-1)^j}{j!}=44$$

perfect matchings. The four neighbors of any fixed user are symmetric, so each incident edge belongs to $11$ perfect matchings.

Let $B$ be the bipartite graph with biadjacency matrix

$$A_B= \begin{pmatrix} I_3&J_3\\ J_3&I_3 \end{pmatrix},$$

where $I_3$ is the identity matrix and $J_3$ is the all-ones matrix. Every vertex has degree $4$. A perfect matching uses the same number $j$ of edges in each of the two off-diagonal blocks. Choose the $j$ indices in each group, and then the two bijections between them. All remaining vertices must use their diagonal edges. Consequently,

$$M(B)=\sum_{j=0}^{3}\binom{3}{j}^{\!2}(j!)^2 =1+9+36+36=82.$$

The block $B$ is classical: it is the bipartite complement within $K_{6,6}$ of $C_6\sqcup C_6$ from McKay and Wanless (1998), Theorem 4; Section 4 of that paper records its permanent $82$.

For any integer $t\geq0$, put

$$\begin{aligned} H_t&=C\sqcup C\sqcup tK_{4,4},\\ G_t&=B\sqcup(t+1)K_{4,4}. \end{aligned}$$

Both graphs have $n=10+4t$ users, $n$ behaviors, and $m=4n$ edges. Moreover, $H_t$ is exactly the partition graph prescribed in Section 3.2: writing $n=4a+b$ gives $a=t+2$ and $b=2$, so the construction has two components of size $5$ and $t$ components of size $4$.

The strict comparison

Perfect-matching counts multiply over components. Hence

$$\begin{aligned} M(H_t)&=44^2\,24^t=1936\,24^t,\\ M(G_t)&=82\,24^{t+1}=1968\,24^t. \end{aligned}$$

Every incident edge in $H_t$ occurs with probability $1/4$. In $G_t$, the degree bound gives $F(G_t)\geq M(G_t)/4$, and a user in one of its $K_{4,4}$ components attains equality. Therefore,

$$\begin{aligned} F(H_t)&=484\,24^t,\\ F(G_t)&=492\,24^t>F(H_t). \end{aligned}$$

Taking $k=4$ and $r=0$ gives parameters explicitly included in Conjecture 1. Thus the conjectured inequality is false; in particular, the asserted $r=0$ comparison in Lemma 4 also fails.

A one-edge-deleted comparison

The strict inequality persists under a positive, fixed edge deficiency. Delete any one edge from $H_t$, obtaining $H_t^-$. Every edge of $H_t$ belongs to one quarter of its perfect matchings, so

$$M(H_t^-)=\frac34M(H_t)=1452\,24^t.$$

At least one of the two $C$ components remains unchanged. Its users still have four equally likely behaviors, while all degrees are at most $4$. Thus

$$F(H_t^-)=\frac14M(H_t^-)=363\,24^t.$$

Delete one edge from a $K_{4,4}$ component of $G_t$, obtaining $G_t^-$. Again the deleted edge belongs to one quarter of the original perfect matchings, so

$$M(G_t^-)=\frac34M(G_t)=1476\,24^t.$$

The degree bound now yields

$$F(G_t^-)\geq\frac14M(G_t^-) =369\,24^t>F(H_t^-).$$

This beats every choice of the deleted edge in the prescribed partition graph. Both graphs have $m=4n-1$ edges, so this additional comparison has $r=1$ and $r/n\to0$ as $t\to\infty$.