# Failure of the trilinear operator space Grothendieck Theorem

Jop Briët Supported by a VENI grant and the Gravitation grant
NETWORKS-024.002.003 from the Netherlands Organisation for Scientific Research
(NWO). Carlos Palazuelos Supported by the Spanish “Ramón y Cajal program”
(RYC-2012-10449), “Severo Ochoa Programe” for Centres of Excellence
(SEV-2015-0554) and MEC (grant MTM2017-88385-P)

###### Abstract

We give a counterexample to a trilinear version of the operator space
Grothendieck theorem. In particular, we show that for trilinear forms on
$\ell_{\infty}$, the ratio of the symmetrized completely bounded norm and the
jointly completely bounded norm is in general unbounded, answering a question
of Pisier. The proof is based on a non-commutative version of the generalized
von Neumann inequality from additive combinatorics.

title = Failure of the trilinear operator space Grothendieck Theorem, author =
Jop Briët and Carlos Palazuelos, plaintextauthor = Jop Briet and Carlos
Palazuelos, plaintexttitle = Failure of the trilinear operator space
Grothendieck Theorem, keywords = Grothendieck theorem, operator spaces,
additive combinatorics, year=2019, number=8, received=18 January 2019,
revised=19 April 2019, published=4 June 2019, doi=10.19086/da.8805,

[classification=text]

##  1 Introduction

In the following, let $\mathcal{A},\mathcal{B}$ be $C^{*}$-algebras and let
$\Phi:\mathcal{A}\times\mathcal{B}\to\mathbb{C}$ be a bilinear form. The
fundamental theorem in the metric theory of tensor products, better known as
Grothendieck’s theorem or GT [11] implies that if $\mathcal{A},\mathcal{B}$
are commutative, then the following holds. There exists a universal constant
$K$ such that $\|\Phi\|\leq\|\Phi\|_{\gamma_{2}}\leq K\|\Phi\|$, where
$\|\Phi\|$ is the operator norm and $\|\Phi\|_{\gamma_{2}}$ is the
factorization norm, which quantifies how well the bilinear form factorizes
through the inner product of Hilbert spaces:

$\|\Phi\|_{\gamma_{2}}=\inf\\{\|\Psi_{1}\|\|\Psi_{2}\|\\},$

where the infimum is taken over Hilbert spaces $\mathcal{H}$ and linear maps
$\Psi_{1}:\mathcal{A}\to\mathcal{H},\Psi_{2}:\mathcal{B}\to\mathcal{H}$ such
that for any $a\in\mathcal{A},b\in\mathcal{B}$, we have
$\Phi(a,b)=\langle\Psi_{1}(a),\Psi_{2}(b)\rangle$. In the same work,
Grothendieck conjectured that the assumption that $\mathcal{A},\mathcal{B}$
are commutative is unnecessary. This was first proved by Pisier in [19] under
some approximation assumptions and later in full generality by Haagerup [12].
These results are not only important to Banach space theory, but also found
applications in quantum information theory [26, 8, 23, 1], computer science
[14, 15, 5] and combinatorics [7].

###  1.1 The operator space GT

The fact that $C^{*}$-algebras have a natural operator space structure [20]
invites the study of Grothendieck’s theorem in this context. In this setting,
the relevant norms are the so-called completely bounded norms, which we
introduce below; we refer to [21] for much more detailed information. We will
identify $M_{d}(\mathcal{A})$, the space of $\mathcal{A}$-valued $d\times d$
matrices, with $\mathcal{A}\otimes M_{d}$ (and similarly for $\mathcal{B}$).

The _completely bounded norm_ of $\Phi$ is defined by

$\|\Phi\|_{\operatorname{cb}}=\sup_{d\in\mathbb{N}}\|{\Phi}_{d}\|,$

where ${\Phi}_{d}:M_{d}(\mathcal{A})\times M_{d}(\mathcal{B})\to M_{d}$ is the
“lift” given by

$\displaystyle\Big{(}\sum_{i}a_{i}\otimes X_{i},\sum_{j}b_{j}\otimes
Y_{j}\Big{)}\mapsto\sum_{i,j}\Phi(a_{i},b_{j})X_{i}Y_{j}.$

The _jointly completely bounded norm_ of $\Phi$ is defined by

$\|\Phi\|_{\operatorname{jcb}}=\sup_{d\in\mathbb{N}}\|\widetilde{\Phi}_{d}\|,$

where $\widetilde{\Phi}_{d}:M_{d}(\mathcal{A})\times M_{d}(\mathcal{B})\to
M_{d^{2}}$ is given by

$\displaystyle\Big{(}\sum_{i}a_{i}\otimes X_{i},\sum_{j}b_{j}\otimes
Y_{j}\Big{)}\mapsto\sum_{i,j}\Phi(a_{i},b_{j})X_{i}\otimes Y_{j}.$

It is easy to see that
$\|\Phi\|_{\operatorname{jcb}}\leq\|\Phi\|_{\operatorname{cb}}$ (consider the
operators $X_{i}\otimes\mathop{\rm Id}\nolimits$ and $\mathop{\rm
Id}\nolimits\otimes Y_{j}$ when computing $\|\Phi_{d}\|$). It follows from
Grothendieck’s theorem that if $\mathcal{A},\mathcal{B}$ are commutative
$C^{*}$-algebras, then these norms are equivalent. However, their ratio is
unbounded in general. An important difference between these two norms is that
only the second is commutative, by which we mean the following. Define
$\Phi^{\mathsf{T}}:\mathcal{B}\times\mathcal{A}\to\mathbb{C}$ by
$\Phi^{\mathsf{T}}(b,a)=\Phi(a,b)$. Then, the jointly completely bounded norm
is invariant with respect to this operation, but the completely bounded norm
generally is not. The following “symmetrized” version of the completely
bounded norm, introduced in [16], is again commutative in this sense:

$\|\Phi\|_{\operatorname{sym}}=\inf\big{\\{}\|\Psi_{1}\|_{\operatorname{cb}}+\|\Psi_{2}^{\mathsf{T}}\|_{\operatorname{cb}}:\,\Phi=\Psi_{1}+\Psi_{2}\big{\\}},$

where the infimum is over bilinear forms
$\Psi_{1},\Psi_{2}:\mathcal{A}\times\mathcal{B}\to\mathbb{C}$. It turns out
that this norm is equal to an operator space version of the factorization norm
mentioned above, provided Hilbert spaces are endowed with the right operator
space structure [21, Section 18]. It still holds that
$\|\Phi\|_{\operatorname{jcb}}\leq\|\Phi\|_{\operatorname{sym}}$. Indeed, it
follows from the above that for any decomposition $\Phi=\Psi_{1}+\Psi_{2}$, we
have

$\|\Phi\|_{\operatorname{jcb}}\leq\|\Psi_{1}\|_{\operatorname{jcb}}+\|\Psi_{2}\|_{\operatorname{jcb}}=\|\Psi_{1}\|_{\operatorname{jcb}}+\|\Psi_{2}^{\mathsf{T}}\|_{\operatorname{jcb}}\leq\|\Psi_{1}\|_{\operatorname{cb}}+\|\Psi_{2}^{\mathsf{T}}\|_{\operatorname{cb}}.$

Pisier and Shlyakhtenko [22] proved that under certain conditions on the
$C^{*}$-algebras, the jointly completely bounded norm and the symmetrized
completely bounded norm are equivalent, giving an operator space version of
Grothendieck’s theorem. This result was refined by Haagerup and Musat [13]
showing the following result.

######  Theorem 1.1 (Operator space GT).

Let $\mathcal{A},\mathcal{B}$ be $C^{*}$-algebras and let
$\Phi:\mathcal{A}\times\mathcal{B}\to\mathbb{C}$ be a bilinear form. Then,
$\|\Phi\|_{\operatorname{jcb}}\leq\|\Phi\|_{\operatorname{sym}}\leq
2\|\Phi\|_{\operatorname{jcb}}$.

###  1.2 Trilinear operator space GT

A natural question is whether Theorem 1.1 generalizes to trilinear forms. In
particular, Pisier [21, Problem 21.3] asked the following: Let
$\mathcal{A}_{1}$, $\mathcal{A}_{2}$, $\mathcal{A}_{3}$ be $C^{*}$-algebras
and let $S_{3}$ denote the permutation group on $\\{1,2,3\\}$. For a trilinear
form
$\Phi:\mathcal{A}_{1}\times\mathcal{A}_{2}\times\mathcal{A}_{3}\to\mathbb{C}$
and $\pi\in S_{3}$, define the trilinear form
$\Phi\circ\pi:\mathcal{A}_{\pi(1)}\times\mathcal{A}_{\pi(2)}\times\mathcal{A}_{\pi(3)}\to\mathbb{C}$
by

$\Phi\circ\pi(a_{\pi(1)},a_{\pi(2)},a_{\pi(3)})=\Phi(a_{1},a_{2},a_{3}).$ (1)

Define

$\|\Phi\|_{\operatorname{sym}}=\inf\Big{\\{}\sum_{\pi\in
S_{3}}\|\Psi_{\pi}\circ\pi\|_{\operatorname{cb}}:\,\Phi=\sum_{\pi\in
S_{3}}\Psi_{\pi}\Big{\\}},$

where the infimum is over trilinear forms
$\Psi_{\pi}:\mathcal{A}_{1}\times\mathcal{A}_{2}\times\mathcal{A}_{3}\to\mathbb{C}$
indexed by $S_{3}$. Define $\|\Phi\|_{\operatorname{jcb}}$ in the obvious way,
using three-fold tensor products. Then, is it true that
$\|\Phi\|_{\operatorname{jcb}}\leq\|\Phi\|_{\operatorname{sym}}\leq
K\|\Phi\|_{\operatorname{jcb}}$ for some absolute constant $K\in(0,\infty)$?

This question was originally formulated by asking if any trilinear form
$\Phi:\mathcal{A}_{1}\times\mathcal{A}_{2}\times\mathcal{A}_{3}\to\mathbb{C}$
that is _jointly completely bounded_ , which is to say that
$\|\Phi\|_{\operatorname{jcb}}<\infty$, is always _completely bounded_ , which
is to say that $\|\Phi\|_{\operatorname{sym}}<\infty$. However, this
formulation is equivalent by the Open Mapping Theorem.

Here we answer this question in the negative. In particular, we show that such
an inequality can fail already in the simplest possible scenario; that is for
commutative $C^{*}$-algebras.

######  Theorem 1.2.

There exist absolute constants $C>0$ and $c>0$ such that the following holds.
For every $n\in\mathbb{N}$, there exists a trilinear form
$\Phi:\ell_{\infty}^{n}\times\ell_{\infty}^{n}\times\ell_{\infty}^{n}\to\mathbb{C}$
such that $\|\Phi\|_{\operatorname{sym}}\geq
Cn^{c}\|\Phi\|_{\operatorname{jcb}}$.

Other trilinear versions of Grothendieck’s theorem have already been shown to
fail in the past. Smith [24] gave counterexamples to hoped-for trilinear
versions of a Grothendieck-type theorem for completely bounded bilinear forms
on $C^{*}$-algebras due to Pisier [19] and Haagerup [12]. Blecher [4]
introduced the notion of tracially completely bounded multilinear forms. These
maps form a subspace strictly contained in the space of completely bounded
multilinear forms. It was shown there that bounded bilinear forms on
$C^{*}$-algebras are always tracially completely bounded, which may be
interpreted as another Grothendieck-type theorem, but that this is false for
trilinear forms in general. However, these works did not concern the jointly
completely bounded norm, which is the appropriate norm in the context of
operator spaces. In [18] it was shown that the operator norm and the jointly
completely bounded norm are not equivalent for trilinear forms on commutative
$C^{*}$-algebras (proving the existence of bounded trilinear forms which are
not jointly completely bounded). This can be understood as a failure of yet
another version of Grothendieck’s theorem. The main result in [18] was later
quantitatively improved in [6], but the optimal ratio between these norms as a
function of the dimension is still an open problem.

Remarkably, both the jointly and symmetrized completely bounded norms again
turn out to play an important role in quantum information theory. While the
first appears naturally in the context of tri-partite entanglement, in
particular as the quantum bias of three-player XOR games (or equivalently, the
quantum value of a tripartite correlation Bell inequality) [17], the second
norm was recently used in the context of quantum algorithms, to give a
characterization of quantum query complexity [2]. In a sense, Theorem 1.2 can
be also read as an absence of a direct connection between these topics.

The proof of Theorem 1.2 uses a non-commutative version of the generalized von
Neumann inequality from additive combinatorics. This inequality allows us to
upper bound the jointly completely bounded norm of certain structured
trilinear forms, given by a function $f$ on a finite Abelian group $\Gamma$,
by the Gowers 3-uniformity norm of $f$. An argument of Varopoulos can be used
to show that the symmetrized completely bounded norm of such trilinear forms
is always at least $|\Gamma|\|f\|_{\ell_{2}}^{2}$. A simple explicit choice of
a function $f$ from the group $\mathbb{Z}_{p}:=\mathbb{Z}/p\mathbb{Z}$ for
prime $p\geq 5$ to the complex unit circle gives the result with $c=1/8$. This
follows from an elementary Weil-type exponential sum estimate used to upper
bound the Gowers 3-uniformity norm of $f$ by $(2/p)^{1/8}p^{2}$, while the
Varopoulos bound shows that the symmetrized completely bounded norm is at
least $p^{2}$. In the last section we comment on possible modifications of our
construction.

##  2 Proof of Theorem 1.2

###  2.1 Preliminaries

We use the following notational conventions and basic facts. Denote
$[n]=\\{1,\dots,n\\}$ and $\mathbb{T}=\\{w\in\mathbb{C}:\,|w|=1\\}$. For a set
$S$ let $(e_{s})_{s\in S}$ be the standard basis for $\mathbb{C}^{S}$. Below,
the set $S$ will vary but will be clear from the context. Let
${B_{M_{d}}=\\{X\in M_{d}:\,\|X\|\leq 1\\}}$, where $\|X\|$ denotes the usual
operator norm on $M_{d}$. Recall that the commutator of $X,Y\in M_{d}$ is
defined by $[X,Y]=XY-YX$ and that $X,Y$ are said to commute if their
commutator is zero. We will use the standard notation $\ell_{\infty}^{n}$ for
the $n$-dimensional commutative $C^{*}$-algebra given by $\mathbb{C}^{n}$
endowed with the sup norm and coordinate-wise multiplication. We refer to a
trilinear form
$\Phi:\ell_{\infty}^{n}\times\ell_{\infty}^{n}\times\ell_{\infty}^{n}\to\mathbb{C}$
as a trilinear form on $\ell_{\infty}^{n}$.

Note that $\ell_{\infty}^{n}$ can be identified with the space of $n\times n$
diagonal matrices endowed with the operator norm. In turn, this implies that
$M_{d}(\ell_{\infty}^{n})$ can be identified with the space of maps $X:[n]\to
M_{d}$, where $X(i)$ corresponds to the $i$th diagonal block of an element in
$M_{d}(\ell_{\infty}^{n})$. As such, the unit ball of
$M_{d}(\ell_{\infty}^{n})$ consists of the maps $X$ such that $X(i)\in
B_{M_{d}}$ for all $i\in[n]$. Then, it is not hard to see that

$\|\Phi\|_{\operatorname{cb}}=\sup\big{\\{}\big{\|}\Phi_{d}(X,Y,Z)\|_{M_{d}}:\,d\in\mathbb{N},\>X,Y,Z:[n]\to
B_{M_{d}}\big{\\}},$ (2)

where

$\Phi_{d}(X,Y,Z)=\sum_{i,j,k=1}^{n}\Phi(e_{i},e_{j},e_{k})X(i)Y(j)Z(k).$ (3)

Note that if $\Phi=\sum_{\pi\in S_{3}}\Psi_{\pi}$ for some trilinear forms
$\Psi_{\pi}$, then this decomposition holds also for the “lifts”:
$\Phi_{d}=\sum_{\pi\in S_{3}}(\Psi_{\pi})_{d}$. Similarly,

$\|\Phi\|_{\operatorname{jcb}}=\sup\big{\\{}\big{\|}\widetilde{\Phi}_{d}(X,Y,Z)\|_{M_{d^{3}}}:\,d\in\mathbb{N},\>X,Y,Z:[n]\to
B_{M_{d}}\big{\\}},$ (4)

where

$\widetilde{\Phi}_{d}(X,Y,Z)=\sum_{i,j,k=1}^{n}\Phi(e_{i},e_{j},e_{k})X(i)\otimes
Y(j)\otimes Z(k).$ (5)

###  2.2 The example

Let $\Gamma$ be a finite Abelian group and $f_{0}:\Gamma\to\mathbb{C}$ be some
function. Identify $\ell_{\infty}^{\Gamma}$ with the function space
$L_{\infty}(\Gamma)$. Define the trilinear form $\Phi:L_{\infty}(\Gamma)\times
L_{\infty}(\Gamma)\times L_{\infty}(\Gamma)\to\mathbb{C}$ by

$\Phi(f_{1},f_{2},f_{3})=\sum_{x,y\in\Gamma}f_{0}(y)f_{1}(x)f_{2}(x+y)f_{3}(x+2y).$
(6)

Theorem 1.2 is based on a form as above, for the group $\mathbb{Z}_{p}$ with
prime $p\geq 5$. To get an example for arbitrary integer $n\geq 4$, one can
choose an odd prime between $n/2$ and $n$ (which exists by Bertrand’s
postulate) and embed $\Phi$ as in (6) based on this group into a trilinear
form on $\ell_{\infty}^{n}$ in the obvious way. In the following two
subsections we upper and lower bound the jointly completely bounded norm and
the symmetrized completely bounded norm, respectively.

###  2.3 Bounding the jointly completely bounded norm

Let $\Phi$ be a trilinear form as in (6). We bound its jointly completely
bounded norm using a non-commutative version of the generalized von Neumann
inequality. The scalar version of this inequality, a basic tool in additive
combinatorics, shows that the operator norm of $\Phi$ can be bounded from
above in terms of the Gowers uniformity norm of $f_{0}$. It was observed
already in [3] that this inequality holds also for the jointly completely
bounded norm; in fact, they prove a more general version than what we use
here. Here, we give an alternative short proof—a straightforward adaptation of
the standard proof of the scalar case [25, Chapter 11]—for the version that is
sufficient for our purpose. To state the inequality, we first define the
Gowers uniformity norms (we refer to [25] for more information on these
norms).

For a finite set $S$, denote

${\mathbb{E}}_{s\in S}[f(s)]=\frac{1}{|S|}\sum_{s\in S}f(s).$

######  Definition 2.1 (Gowers uniformity norms).

Let $k$ be a positive integer, let $\Gamma$ be a finite Abelian group and
$f:\Gamma\to\mathbb{C}$ be some function. Then, the Gowers $U^{k}$-norm of $f$
is given by

$\|f\|_{U^{t}(\Gamma)}=\big{|}{\mathbb{E}}_{x,h_{1},\dots,h_{k}}\big{[}(\Delta_{h_{1}}\cdots\Delta_{h_{k}}f)(x)\big{]}\big{|}^{\frac{1}{2^{k}}},$

where $\Delta_{h}f(x)=\overline{f(x)}f(x+h)$.

The case $k=1$ is strictly speaking not a norm but it is a seminorm. As an
example, the 8th power of the Gowers $U^{3}$-norm is given by

$\big{|}{\mathbb{E}}\big{[}\overline{f(x)}f(x+h_{1})f(x+h_{2})f(x+h_{3})\overline{f(x+h_{1}+h_{2})}\times\\\
\overline{f(x+h_{1}+h_{3})f(x+h_{2}+h_{3})}f(x+h_{1}+h_{2}+h_{3})\big{]}\big{|},$
(7)

where the expectation is over independent uniform
$x,h_{1},h_{2},h_{3}\in\Gamma$.

Our upper bound on $\|\Phi\|_{\operatorname{jcb}}$ is based on the following
inequality.

######  Proposition 2.2.

Let $\Gamma$ be a finite Abelian group and let $f_{0}:\Gamma\to\mathbb{C}$ be
some function. Then, for $\Phi$ as in (6), we have

$\|\Phi\|_{\operatorname{jcb}}\leq|\Gamma|^{2}\,\|f_{0}\|_{U^{3}(\Gamma)}.$

To prove this result, let us introduce the following non-commutative version
of the Gowers uniformity norms.

######  Definition 2.3.

For positive integes $d,k$, a finite Abelian group $\Gamma$ and function
$F:\Gamma\to M_{d}$, define

$\|F\|_{U^{k}(\Gamma)}=\big{\|}{\mathbb{E}}_{x,h_{1},\dots,h_{k}}(\Delta_{h_{1}}\cdots\Delta_{h_{k}}F)(x)\big{\|}^{\frac{1}{2^{k}}},$

where (with abuse of notation) $(\Delta_{h}F)(x)=F(x)^{*}F(x+h)$.

######  Remark 2.4.

In general it appears to be unknown if these functions are also norms (but for
our purposes we do not need them to be). Expressions related to the case $k=2$
were studied in works of Gowers and Hatami [10] and Chiffre, Ozawa and Thom
[9].

Proposition 2.2 follows from the following key lemma, which is a non-
commutative version of the generalized von Neumann theorem.

######  Lemma 2.5.

Let $d\in\mathbb{N}$ and let $\Gamma$ be a finite Abelian group. Let
$A_{0},A_{1},A_{2},A_{3}:\Gamma\to B_{M_{d}}$ be maps such that for all
$x,y\in\Gamma$ and distinct $i,j=0,1,2,3$, we have
$[A_{i}(x),A_{j}(y)]=[A_{i}(x)^{*},A_{j}(y)]=0$. Then,

$\big{\|}{\mathbb{E}}_{x,y\in\Gamma}A_{0}(y)A_{1}(x)A_{2}(x+y)A_{3}(x+2y)\big{\|}\leq\|A_{0}\|_{U^{3}(\Gamma)}.$

A version of Lemma 2.5 with $k$-term arithmetic progressions instead of 3-term
arithmetic progressions also holds with the right-hand side replaced with
$\|A_{0}\|_{U^{k}(\Gamma)}$. More generally, other known variants of the
scalar case hold also in this non-commutative setting. The proof of Lemma 2.5
uses the following “matrix van der Corput lemma”.

######  Lemma 2.6.

Let $\Gamma$ be a finite Abelian group, let $S$ be a finite set and for each
$s\in S$ let $F_{s}:\Gamma\to M_{d}$. Then, for any map ${\bf B}:S\to
B_{M_{d}}$,

$\big{\|}{\mathbb{E}}_{s\in S}{\mathbb{E}}_{x\in\Gamma}{\bf
B}(s)F_{s}(x)\big{\|}\leq\big{\|}{\mathbb{E}}_{s\in
S}{\mathbb{E}}_{x,h\in\Gamma}(\Delta_{h}F_{s})(x)\big{\|}^{\frac{1}{2}}.$

  * Proof:

Let $F(s)={\mathbb{E}}_{x\in\Gamma}F_{s}(x)$. The Cauchy–Schwarz inequality
and boundedness of ${\bf B}$ give

$\displaystyle\big{\|}{\mathbb{E}}_{s\in S}{\mathbb{E}}_{x\in\Gamma}{\bf
B}(s)F_{s}(x)\big{\|}$ $\displaystyle=\big{\|}{\mathbb{E}}_{s\in S}{\bf
B}(s)F(s)\big{\|}$ $\displaystyle\leq\big{\|}{\mathbb{E}}_{s\in S}{\bf
B}(s){\bf B}(s)^{*}\big{\|}^{\frac{1}{2}}\big{\|}{\mathbb{E}}_{s\in
S}F(s)^{*}F(s)\big{\|}^{\frac{1}{2}}$
$\displaystyle\leq\big{\|}{\mathbb{E}}_{s\in
S}{\mathbb{E}}_{x,y\in\Gamma}F_{s}(x)^{*}F_{s}(y)\big{\|}^{\frac{1}{2}}.$

The claim now follows by substituting $y=x+h$. $\Box$

  * Proof of Lemma 2.5:

We will repeatedly use the fact that the map $(x,y)\mapsto(x-y,y)$ on
$\Gamma\times\Gamma$ is bijective. The proof uses Lemma 2.6 three times, with
different choices of $S,{\bf B}$ and $F_{s}$.

First, let $S=\Gamma$, let ${\bf B}=A_{1}$ and let
$F_{x}(y)=A_{2}(x+y)A_{3}(x+2y)A_{0}(y)$. Then Lemma 2.6 and commutativity of
the $A_{i}$ give

$\displaystyle\big{\|}{\mathbb{E}}_{x,y}A_{0}(y)A_{1}(x)A_{2}(x+y)A_{3}(x+2y)\big{\|}^{8}$
$\displaystyle=\big{\|}{\mathbb{E}}_{x}{\bf
B}(x){\mathbb{E}}_{y}F_{x}(y)\big{\|}^{8}$
$\displaystyle\leq\big{\|}{\mathbb{E}}_{x}{\mathbb{E}}_{y,h_{1}}(\Delta_{h_{1}}F_{x})(y)\big{\|}^{4}.$
(8)

Using the above-mentioned change of variables, the right-hand side of (8)
equals

$\big{\|}{\mathbb{E}}_{x,h_{1}}{\mathbb{E}}_{y}F_{x-y}(y)^{*}F_{x-y}(y+h_{1})\big{\|}^{4}.$
(9)

Second, using the properties of the maps $A_{2},A_{3},A_{0}$, it follows that

$F_{x-y}(y)^{*}F_{x-y}(y+h_{1})=A_{2}(x)^{*}A_{2}(x+h_{1})A_{3}(x+y)^{*}A_{3}(x+y+2h_{1})\,(\Delta_{h_{1}}A_{0})(y).$

Now let $S=\Gamma\times\Gamma$ and factor the above as

$\displaystyle{\bf B}(x,h_{1})$ $\displaystyle=A_{2}(x)^{*}A_{2}(x+h_{1})$
$\displaystyle F_{x,h_{1}}(y)$
$\displaystyle=A_{3}(x+y)^{*}A_{3}(x+y+2h_{1})\,(\Delta_{h_{1}}A_{0})(y).$

From Lemma 2.6 and another change of variables, it follows that the right-hand
side of (9) is at most

$\big{\|}{\mathbb{E}}_{x,h_{1}}{\mathbb{E}}_{y,h_{2}}(\Delta_{h_{2}}F_{x,h_{1}})(y)\big{\|}^{2}=\big{\|}{\mathbb{E}}_{x,h_{1},h_{2}}{\mathbb{E}}_{y}F_{x-y,h_{1}}(y)^{*}F_{x-y,h_{1}}(y+h_{2})\big{\|}^{2}.$
(10)

Third, it follows from the properties of $A_{3},A_{0}$ that

$F_{x-y,h_{1}}(y)^{*}F_{x-y,h_{1}}(y+h_{2})=A_{3}(x+2h_{1})^{*}A_{3}(x)A_{3}(x+h_{2})^{*}A_{3}(x+2h_{1}+h_{2})(\Delta_{h_{2}}\Delta_{h_{1}}A_{0})(y).$

Finally set $S=\Gamma\times\Gamma\times\Gamma$ and factor the above as

$\displaystyle{\bf B}(x,h_{1},h_{2})$
$\displaystyle=A_{3}(x+2h_{1})^{*}A_{3}(x)A_{3}(x+h_{2})^{*}A_{3}(x+2h_{1}+h_{2})$
$\displaystyle F_{x,h_{1},h_{2}}(y)$
$\displaystyle=(\Delta_{h_{2}}\Delta_{h_{1}}A_{0})(y).$

Again by Lemma 2.6, the right-hand side of (10) is at most

$\big{\|}{\mathbb{E}}_{x,h_{1},h_{2}}{\mathbb{E}}_{y,h_{3}}(\Delta_{h_{3}}F_{x,h_{1},h_{2}})(y)\big{\|}=\big{\|}{\mathbb{E}}_{h_{1},h_{2},h_{3},y}(\Delta_{h_{3}}\Delta_{h_{2}}\Delta_{h_{1}}A_{0})(y)\big{\|},$

giving the claim. $\Box$

  * Proof of Proposition 2.2:

For any $d\in\mathbb{N}$ and $X,Y,Z:\Gamma\to B_{M_{d}}$, define
$A_{0},A_{1},A_{2},A_{3}:\Gamma\to B_{M_{d^{3}}}$ by

$\displaystyle A_{0}(x)$ $\displaystyle=f_{0}(x)\mathop{\rm
Id}\nolimits\otimes\mathop{\rm Id}\nolimits\otimes\mathop{\rm Id}\nolimits$
$\displaystyle A_{1}(x)$ $\displaystyle=X(x)\otimes\mathop{\rm
Id}\nolimits\otimes\mathop{\rm Id}\nolimits$ $\displaystyle A_{2}(x)$
$\displaystyle=\mathop{\rm Id}\nolimits\otimes Y(x)\otimes\mathop{\rm
Id}\nolimits$ $\displaystyle A_{3}(x)$ $\displaystyle=\mathop{\rm
Id}\nolimits\otimes\mathop{\rm Id}\nolimits\otimes Z(x).$

Then, the statement follows trivially from Lemma 2.5 and noting that the
factor $|\Gamma|^{2}$ comes from replacing sums with expectations. $\Box$

######  Remark 2.7.

Note that Lemma 2.5 also applies if $M_{d}$ is replaced by the space
$B(\mathcal{H})$ of bounded operators on a (possibly infinite-dimensional)
Hilbert space $\mathcal{H}$. Moreover, the upper bound stated in Proposition
2.2 even applies if one replaces the jointly completely bounded norm by

$\displaystyle\|\Phi\|_{\mathrm{com}}:=\sup\Big{\\{}\Big{\|}\sum_{i,j,k=1}^{n}\Phi(e_{i},e_{j},e_{k})X_{1}(i)X_{2}(j)X_{3}(k)\Big{\|}_{\mathcal{B}(\mathcal{H})}\Big{\\}},$

where the supremum is over maps $X_{1},X_{2},X_{3}:[n]\to
B_{\mathcal{B}(\mathcal{H})}$ such that $[X_{i}(k),X_{j}(l)]=0$ and
$[X_{i}(k)^{*},X_{j}(l)]=0$ for all $k,l\in[n]$ and $i\neq j$.

######  Proposition 2.8.

Let $p\geq 5$ be a prime, $\omega=e^{2\pi i/p}$ and
$f_{0}:\mathbb{Z}_{p}\to\mathbb{C}$ be the function given by
$f_{0}(x)=\omega^{x^{3}}$. Then,

$\|f_{0}\|_{U^{3}(\mathbb{Z}_{p})}\leq(2/p)^{1/8}.$

  * Proof:

A straightforward calculation shows that for
$x,h_{1},h_{2},h_{3}\in\mathbb{Z}_{p}$, we have

$(\Delta_{h_{1}}\Delta_{h_{2}}\Delta_{h_{3}}f_{0})(x)=\omega^{6h_{1}h_{2}h_{3}}.$

It follows that

$\displaystyle\|f_{0}\|_{U^{3}(\mathbb{Z}_{p})}^{8}={\mathbb{E}}_{h_{1},h_{2}\in\mathbb{Z}_{p}}\big{[}{\mathbb{E}}_{h_{3}\in\mathbb{Z}_{p}}[\omega^{6h_{1}h_{2}h_{3}}]\big{]}.$

The inner expectation over $h_{3}$ is 1 if $h_{1}=0$ or $h_{2}=0$ and, since
$6$ is coprime relative to $p$ and $\mathbb{Z}_{p}$ is a field, it is 0
otherwise. Hence, the right-hand side equals $(2p-1)/p^{2}$, which gives the
claim. $\Box$

######  Corollary 2.9.

Let $p\geq 5$ be a prime, let $\Gamma=\mathbb{Z}_{p}$ and let $f_{0}$ be as in
Proposition 2.8. Then, for $\Phi$ as in (6), we have

$\|\Phi\|_{\operatorname{jcb}}\leq p^{2}(2/p)^{1/8}.$

###  2.4 Bounding the symmetrized completely bounded norm

To lower bound the symmetrized completely bounded norm, we first prove the
following result.

######  Lemma 2.10.

Let $\Psi$ be a trilinear form on $\ell_{\infty}^{n}$. Then,

$\|\Psi\|_{\operatorname{sym}}\geq\sup\big{\\{}\|\Psi_{d}(X_{1},X_{2},X_{3})\|_{M_{d}}:\,d\in\mathbb{N},\>X_{1},X_{2},X_{3}:[n]\to
B_{M_{d}}\big{\\}},$

where the supremum is over maps $X_{i}$ such that $[X_{i}(k),X_{j}(l)]=0$ for
all $k,l\in[n]$ and $i\neq j$.111Note that in contrast with the norm
$\|\Psi\|_{\mathrm{com}}$ defined above, here we do not require that
$[X_{i}(k)^{*},X_{j}(l)]=0$.

This result was already proved in [16] in much greater generality and the
authors showed that the quantities appearing in Lemma 2.10 are equivalent.
Since the proof of the inequality we need is straightforward, we add it for
completeness.

  * Proof:

Let $\Psi=\sum_{\pi\in S_{3}}\Psi_{\pi}$ be some decomposition. Let $d$ be a
positive integer and let $X_{1},X_{2},X_{3}:[n]\to M_{d}$ be maps with
commuting ranges as in the lemma. By the triangle inequality,

$\displaystyle\|\Psi_{d}(X_{1},X_{2},X_{3})\|_{M_{d}}$
$\displaystyle\leq\sum_{\pi\in
S_{3}}\|(\Psi_{\pi})_{d}(X_{1},X_{2},X_{3})\|_{M_{d}}.$ (11)

We claim that each term on the right-hand side equals

$\|(\Psi_{\pi}\circ\pi)_{d}(X_{\pi(1)},X_{\pi(2)},X_{\pi(3)})\|_{M_{d}}.$

This implies the lemma because the above is clearly at most
$\|\Psi_{\pi}\circ\pi\|_{\operatorname{cb}}$. To see the claim, first observe
that by commutativity, it holds that for every $i_{1},i_{2},i_{3}\in[n]$ and
$\pi\in S_{3}$, we have

$X_{1}(i_{1})X_{2}(i_{2})X_{3}(i_{3})=X_{\pi(1)}(i_{\pi(1)})X_{\pi(2)}(i_{\pi(2)})X_{\pi(3)}(i_{\pi(3)}).$
(12)

Let $\chi$ be some trilinear form on $\ell_{\infty}^{n}$. Recall from (1) that

$\chi(e_{i_{\pi^{-1}(1)}},e_{i_{\pi^{-1}(2)}},e_{i_{\pi^{-1}(3)}})=(\chi\circ\pi)(e_{i_{1}},e_{i_{2}},e_{i_{3}}).$
(13)

Then,

$\displaystyle\chi_{d}(X_{1},X_{2},X_{3})$
$\displaystyle=\sum_{i_{1},i_{2},i_{3}=1}^{n}\chi(e_{i_{1}},e_{i_{2}},e_{i_{3}})X_{1}(i_{1})X_{2}(i_{2})X_{3}(i_{3})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:Xcomm}}}{{=}}\sum_{i_{1},i_{2},i_{3}=1}^{n}\chi(e_{i_{1}},e_{i_{2}},e_{i_{3}})X_{\pi(1)}(i_{\pi(1)})X_{\pi(2)}(i_{\pi(2)})X_{\pi(3)}(i_{\pi(3)})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:chipi}}}{{=}}\sum_{i_{1},i_{2},i_{3}=1}^{n}(\chi\circ\pi)(e_{i_{1}},e_{i_{2}},e_{i_{3}})X_{\pi(1)}(i_{1})X_{\pi(2)}(i_{2})X_{\pi(3)}(i_{3})$
$\displaystyle=(\chi\circ\pi)_{d}(X_{\pi(1)},X_{\pi(2)},X_{\pi(2)}).$

Applying this to $\chi=\Psi_{\pi}$ for each $\pi$ gives the claim. $\Box$

A trilinear form $\Psi$ on $\mathbb{C}^{n}$ is _symmetric_ if
$\Psi\circ\pi=\Psi$ holds for every $\pi\in S_{3}$. A _slice_ of a (not
necessarily symmetric) trilinear form $\Psi$ is an $n\times n$ matrix obtained
by fixing one of the three coordinates (so there are $3n$ slices), for example

$M_{i}=(\Psi(e_{i},e_{j},e_{k}))_{j,k=1}^{n}.$

We will denote

$\Delta(\Psi)=\max\\{\|M\|:\,\text{$M$ is a slice of $\Psi$}\\}.$

Also define

$\|\Psi\|_{\ell_{2}}=\Big{(}\sum_{i,j,k=1}^{n}|\Psi(e_{i},e_{j},e_{k})|^{2}\Big{)}^{\tfrac{1}{2}}.$

The following lemma, due to Varopoulos [27], is the key to our lower bound on
$\|\Psi\|_{\operatorname{sym}}$. Again, the proof is simple, so we add it for
completeness.

######  Lemma 2.11.

Let $\Psi$ be a symmetric trilinear form on $\ell_{\infty}^{n}$. Then,

$\|\Psi\|_{\operatorname{sym}}\geq\frac{\|\Psi\|_{\ell_{2}}^{2}}{\Delta(\Psi)}.$

  * Proof:

For each $i\in[n]$, let $M_{i}=(\Psi(e_{i},e_{j},e_{k}))_{j,k=1}^{n}$ be the
slice obtained by fixing the first coordinate to $i$. Define
$W_{i}=\Delta(\Psi)^{-1}M_{i}$ and note that this has operator norm at most 1.
For each $i\in[n]$, define the $(2n+2)\times(2n+2)$ block matrix

$X_{i}={\footnotesize\left[\begin{array}[]{c|c|c|c}\phantom{M}&&&\\\ \hline\cr
e_{i}&\phantom{M}&&\\\ \hline\cr&W_{i}^{*}&\phantom{M}&\\\
\hline\cr&&e_{i}^{*}&\phantom{M}\end{array}\right]},$

where the row and column blocks have size $1,n,n,1$, respectively, and where
the empty blocks are filled with zeros. Then, for all $i,j\in[n]$,

$X_{i}^{*}X_{i}={\footnotesize\left[\begin{array}[]{c|c|c|c}1&&&\\\
\hline\cr&W_{i}W_{i}^{*}&&\\\ \hline\cr&&e_{i}e_{i}^{*}&\\\
\hline\cr&&&\phantom{x}\end{array}\right]}\quad\text{and}\quad
X_{i}X_{j}={\footnotesize\left[\begin{array}[]{c|c|c|c}\phantom{x}&&&\\\
\hline\cr&\phantom{x}&&\\\ \hline\cr W_{i}^{*}e_{j}&&\phantom{x}&\\\
\hline\cr&e_{i}^{*}W_{j}^{*}&&\phantom{x}\end{array}\right]}.$

The first identity shows that $\|X_{i}\|=\max\\{1,\|W_{i}\|\\}\leq 1$. Since
$\Psi$ is symmetric, we have $M_{j}e_{i}=M_{i}e_{j}$ for all $i,j$. Therefore,
the second identity shows that these matrices commute with each other.
Moreover,

$X_{i}X_{j}X_{k}={\footnotesize\left[\begin{array}[]{c|c|c|c}\phantom{x}&&&\\\
\hline\cr&\phantom{x}&&\\\ \hline\cr&&\phantom{x}&\\\ \hline\cr
e_{i}^{*}W_{j}^{*}e_{k}&&&\phantom{x}\end{array}\right]=\frac{1}{\Delta(\Psi)}\left[\begin{array}[]{c|c|c|c}\phantom{x}&&&\\\
\hline\cr&\phantom{x}&&\\\ \hline\cr&&\phantom{x}&\\\
\hline\cr\overline{\Psi(e_{i},e_{j},e_{k})}&&&\phantom{\hat{\Psi}}\end{array}\right].}$

Hence, by Lemma 2.10, we get that

$\displaystyle\|\Psi\|_{\operatorname{sym}}$
$\displaystyle\geq\Big{\|}\sum_{i,j,k=1}^{n}\Psi(e_{i},e_{j},e_{k})X_{i}X_{j}X_{k}\Big{\|}_{M_{d}}\geq\frac{1}{\Delta(\Psi)}\sum_{i,j,k=1}^{n}|\Psi(e_{i},e_{j},e_{k})|^{2}.$

This concludes the proof. $\Box$

Below we present a self-contained proof of Theorem 1.2, so that no prior
knowledge of operator space theory is needed. But some of the facts we use can
be proved faster based on some well-known—albeit somewhat non-trivial—facts
from it. We briefly outline why this is the case. Readers not familiar with
this theory can safely skip the next few paragraphs and continue at
Proposition 2.12.

Lemma 2.11 also follows from the fact that for any trilinear forms $\Psi,\Phi$
on $\ell_{\infty}^{n}$, we have

$\displaystyle\|\Psi\|_{\operatorname{sym}}\Delta(\Phi)\geq|\langle\Psi,\Phi\rangle|:=\Big{|}\sum_{i,j,k=1}^{n}\Psi(e_{i},e_{j},e_{k})\overline{\Phi(e_{i},e_{j},e_{k})}\Big{|}.$
(14)

We sketch the proof of (14). The identities $\|id:\ell_{1}^{n}\rightarrow
R_{n}\|_{\operatorname{cb}}=1$ and $\|id:\ell_{1}^{n}\rightarrow
C_{n}\|_{\operatorname{cb}}=1$, where $R_{n},C_{n}$ are the row and column
operator spaces respectively, and
$R_{n}\otimes_{h}\ell_{1}^{n}\otimes_{h}C_{n}=S_{1}^{n}(\ell_{1}^{n})=\ell_{1}^{n}(S_{1}^{n})$
(see for instance [20, Corollary 5.11]), imply that the linear map
$T:\ell_{1}^{n}\otimes_{h}\ell_{1}^{n}\otimes_{h}\ell_{1}^{n}\rightarrow\ell_{1}^{n}(S_{1}^{n})$
defined by

$T(e_{i}\otimes e_{j}\otimes e_{k})=e_{j}\otimes(e_{i}\otimes e_{k}),$

is a (complete) contraction.

Then, using that the dual space of $\ell_{1}^{n}(S_{1}^{n})$ is the space
$\ell_{\infty}^{n}(S_{\infty}^{n})$, one gets that for $\Psi,\Phi$ as above,

$\|\Psi\|_{\ell_{1}^{n}\otimes_{h}\ell_{1}^{n}\otimes_{h}\ell_{1}^{n}}\Delta(\Phi)\geq\|\Psi\|_{\ell_{1}^{n}\otimes_{h}\ell_{1}^{n}\otimes_{h}\ell_{1}^{n}}\max_{j}\|M_{j}(\Phi)\|_{S_{\infty}^{n}}\geq|\langle\Psi,\Phi\rangle|.$

Hence, since $\Delta(\Phi)$ controls all the indices, it follows that for any
permutation $\pi\in S_{3}$ we have

$\|\Psi\circ\pi\|_{\ell_{1}^{n}\otimes_{h}\ell_{1}^{n}\otimes_{h}\ell_{1}^{n}}\Delta(\Phi)\geq|\langle\Psi,\Phi\rangle|,$

from which (14) is easily obtained. Note that based on this argument, $\Psi$
is not required to be symmetric and as a consequence, Proposition 2.13 below
is no longer needed.

######  Proposition 2.12.

Let $p\geq 3$ be a prime, let $\Gamma=\mathbb{Z}_{p}$, let
$f_{0}:\Gamma\to\mathbb{T}$ and let $\Phi$ be a trilinear form as in (6).
Then, $\|\Phi\|_{\ell_{2}}^{2}=p^{2}$ and ${\Delta(\Phi)=1}$.

  * Proof:

The first assertion is straightforward to check. Let
$\\{e_{x}:\,x\in\Gamma\\}$ denote the standard basis for
$\mathbb{C}^{\Gamma}$. Fix a $x\in\Gamma$ and consider the slice obtained by
fixing the first coordinate of the tensor corresponding to $\Phi$ to $x$:

$\displaystyle M_{x}$
$\displaystyle=\sum_{y,z\in\Gamma}\Phi(e_{x},e_{y},e_{z})e_{y}\otimes e_{z}$
$\displaystyle=\sum_{y,z\in\Gamma}\sum_{u,v\in\Gamma}f_{0}(v)e_{x}(u)e_{y}(u+v)e_{z}(u+2v)e_{y}\otimes
e_{z}$
$\displaystyle=\sum_{y,z\in\Gamma}\sum_{v\in\Gamma}f_{0}(v)e_{y}(x+v)e_{z}(x+2v)e_{y}\otimes
e_{z}$ $\displaystyle=\sum_{y,z\in\Gamma}f_{0}(y-x)e_{z}(2y-x)e_{y}\otimes
e_{z}$ $\displaystyle=\sum_{y\in\Gamma}f_{0}(y-x)e_{y}\otimes e_{2y-x}.$

Since for our group $\mathbb{Z}_{p}$, the map $y\mapsto 2y$ is injective, it
follows that $M_{x}$ is a unitary matrix and therefore has norm $1$. The other
slices can similarly be seen to have norm $1$. $\Box$

###  2.5 Putting everything together

To apply Lemma 2.11 we need to symmetrize our form. We do this so as to
approximately preserve $\Delta(\Phi)$, $\|\Phi\|_{\ell_{2}}$ and
$\|\Phi\|_{\operatorname{jcb}}$.222Perhaps a more natural symmetrization to
consider is $\Phi_{s}=\sum_{\pi}\Phi\circ\pi$. However, the relevant values
can be dramatically affected by this procedure, since we could get a zero
tensor from a non-zero one. To this end, we first consider the trilinear form
$E:\mathbb{C}^{3}\times\mathbb{C}^{3}\times\mathbb{C}^{3}\to\mathbb{C}$ given
by

$E(u,v,w)=u_{1}v_{2}w_{3}.$

For a trilinear form $\Psi$ on $\mathbb{C}^{n}$, the trilinear form
$\Psi\otimes E$ on $\mathbb{C}^{3n}$ is given by

$(\Psi\otimes E)(x\otimes u,y\otimes v,z\otimes w)=\Psi(x,y,z)E(u,v,w),$

for $x,y,z\in\mathbb{C}^{n}$ and $u,v,w\in\mathbb{C}^{3}$. If $\Psi$ is a
trilinear form on $\ell_{\infty}^{n}$, then we define the symmetrized version
of $\Psi$ to be the trilinear form $\overline{\Psi}$ on $\ell_{\infty}^{3n}$
by

$\displaystyle\overline{\Psi}=\sum_{\pi\in S_{3}}(\Psi\otimes E)\circ\pi.$
(15)

It is easy to see that $\overline{\Psi}$ is symmetric. Moreover, as per (1),
for any $x_{i}\in\mathbb{C}^{n}$ and $u_{i}\in\mathbb{C}^{3}$ for $i=1,2,3$,
we have

$\overline{\Psi}(x_{1}\otimes u_{1},x_{2}\otimes u_{2},x_{3}\otimes u_{3})=\\\
\sum_{\pi\in
S_{3}}\Psi(x_{\pi^{-1}(1)},x_{\pi^{-1}(2)},x_{\pi^{-1}(3)})E(u_{\pi^{-1}(1)},u_{\pi^{-1}(2)},u_{\pi^{-1}(3)})=\\\
\sum_{\pi\in
S_{3}}\Psi(x_{\pi(1)},x_{\pi(2)},x_{\pi(3)})E(u_{\pi(1)},u_{\pi(2)},u_{\pi(3)}).$
(16)

######  Proposition 2.13.

Let $\Psi$ be a trilinear form on $\ell_{\infty}^{n}$. Then, its
symmetrization $\overline{\Psi}$ as in (15) satisfies:

  * •

$\Delta(\overline{\Psi})=\Delta(\Psi)$

  * •

$\|\overline{\Psi}\|_{\ell_{2}}^{2}=6\|\Psi\|_{\ell_{2}}^{2}$

  * •

$\|\overline{\Psi}\|_{\operatorname{jcb}}\leq 6\|\Psi\|_{\operatorname{jcb}}$.

  * Proof:

We begin with the first item. The lower bound
$\Delta(\overline{\Psi})\geq\Delta(\Psi)$ follows easily from the fact that

$\overline{\Psi}(x\otimes e_{1},y\otimes e_{2},z\otimes e_{3})=\Psi(x,y,z).$

By symmetry of $\overline{\Psi}$, for the upper bound
$\Delta(\overline{\Psi})\leq\Delta(\Psi)$, it suffices to show that for any
$i\in[n]$ and $a\in[3]$, the slice corresponding to the bilinear form
$B:\mathbb{C}^{3n}\times\mathbb{C}^{3n}\to\mathbb{C}$ given by

$B(x,y)=\overline{\Psi}(e_{i}\otimes e_{a},x,y)$

has operator norm at most $\Delta(\Psi)$. Let $x,y\in\mathbb{C}^{3n}$ be unit
vectors. Write $x=x_{1}\otimes e_{1}+x_{2}\otimes e_{2}+x_{3}\otimes e_{3}$
for $x_{1},x_{2},x_{3}\in\mathbb{C}^{n}$ and similarly for $y$. Then,

$\displaystyle|B(x,y)|$
$\displaystyle=\Big{|}\sum_{b,c=1}^{3}\overline{\Psi}(e_{i}\otimes
e_{a},x_{b}\otimes e_{b},y_{c}\otimes e_{c})\Big{|}$
$\displaystyle=\Big{|}\sum_{b,c=1}^{3}\sum_{\pi\in S_{3}}\big{(}(\Psi\otimes
E)\circ\pi\big{)}(e_{i}\otimes e_{a},x_{b}\otimes e_{b},y_{c}\otimes
e_{c})\Big{|}$ $\displaystyle=\Big{|}\sum_{\pi\in
S_{3}}\sum_{b,c=1}^{3}(\Psi\circ\pi)(e_{i},x_{b},y_{c})\cdot(E\circ\pi)(e_{a},e_{b},e_{c})\Big{|}.$

Observe that $(E\circ\pi)(e_{a},e_{b},e_{c})$ equals 1 if
$a=\pi(1),b=\pi(2),c=\pi(3)$ and $0$ otherwise. Hence, the above is at most

$\displaystyle\sum_{\pi\in
S_{3}:\,\pi(1)=a}\big{|}(\Psi\circ\pi)(e_{i},x_{\pi(2)},y_{\pi(3)})\big{|}$
$\displaystyle\leq\Delta(\Psi)\,\sum_{\pi\in
S_{3}:\,\pi(1)=a}\|x_{\pi(2)}\|\,\|y_{\pi(3)}\|.$

By the Cauchy-Schwarz inequality, the last sum is at most

$\Big{(}\sum_{\pi\in
S_{3}:\,\pi(1)=a}\|x_{\pi(2)}\|^{2}\Big{)}^{\tfrac{1}{2}}\Big{(}\sum_{\pi\in
S_{3}:\,\pi(1)=a}\|y_{\pi(3)}\|^{2}\Big{)}^{\tfrac{1}{2}}\leq 1.$

This proves the first item.

The second item is a straightforward calculation. It follows from (16) that

$\displaystyle\|\overline{\Psi}\|_{\ell_{2}}^{2}$
$\displaystyle=\sum_{i_{1},i_{2},i_{3}=1}^{n}\sum_{j_{1},j_{2},j_{3}=1}^{3}\Big{|}\overline{\Psi}(e_{i_{1}}\otimes
e_{j_{1}},e_{i_{2}}\otimes e_{j_{2}},e_{i_{3}}\otimes e_{j_{3}})\Big{|}^{2}$
$\displaystyle=\sum_{i_{1},i_{2},i_{3}=1}^{n}\sum_{j_{1},j_{2},j_{3}=1}^{3}\Big{|}\sum_{\pi\in
S_{3}}\Psi(e_{i_{\pi(1)}},e_{i_{\pi(2)}},e_{i_{\pi(3)}})E(e_{j_{\pi(1)}},e_{j_{\pi(2)}},e_{j_{\pi(3)}})\Big{|}^{2}.$

Observe that $E(e_{j_{\pi(1)}},e_{j_{\pi(2)}},e_{j_{\pi(3)}})=1$ only if
$j_{1},j_{2},j_{3}\in[3]$ are distinct and that in that case there is a unique
$\pi\in S_{3}$ for which this holds. Since for any fixed $\pi\in S_{3}$ we
have

$\sum_{i_{1},i_{2},i_{3}=1}^{n}|\Psi(e_{i_{\pi(1)}},e_{i_{\pi(2)}},e_{i_{\pi(3)}})|^{2}=\|\Psi\|_{\ell^{2}}^{2},$

and there are 6 ways to choose $j_{1},j_{2},j_{3}$ distinct, the second item
follows.

For the third item, observe that the jointly completely bounded norm is
commutative, which is to say that
$\|\Psi\circ\pi\|_{\operatorname{jcb}}=\|\Psi\|_{\operatorname{jcb}}$ for
every $\pi\in S_{3}$. The claim then follows from the identity $\|\Psi\otimes
E\|_{\operatorname{jcb}}=\|\Psi\|_{\operatorname{jcb}}$ and triangle
inequality. To see the identity, recall the expressions (4) and (5) for the
jointly completely bounded norm. Let $d$ be a positive integer and let
$X,Y,Z:[n]\times[3]\to B_{M_{d}}$. Then,

$\sum_{i,j,k=1}^{n}\sum_{a,b,c=1}^{3}\Psi(e_{i},e_{j},e_{j})E(e_{a},e_{b},e_{c})X(i,a)\otimes
Y(j,b)\otimes Z(k,c)\\\
=\sum_{i,j,k=1}^{n}\Psi(e_{i},e_{j},e_{j})X(i,1)\otimes Y(j,2)\otimes Z(k,3).$

Taking norms and suprema over $X,Y,Z$ and $d\in\mathbb{N}$ gives identity.
$\Box$

With this, the proof of Theorem 1.2 is straightforward.

  * Proof of Theorem 1.2:

Let $p\geq 5$ be a prime number and let $\Gamma=\mathbb{Z}_{p}$. Let $\Phi$ be
a trilinear form as in (6) and let $f_{0}:\Gamma\to\mathbb{C}$ be as in
Proposition 2.8. Let $\overline{\Phi}$ be the symmetrization of $\Phi$ as in
(15). Then, it follows from Corollary 2.9 and Proposition 2.13 that
$\|\overline{\Phi}\|_{\operatorname{jcb}}\leq 6p^{2}(2/p)^{1/8}$. On the other
hand, it follows from Lemma 2.11, Proposition 2.12 and Proposition 2.13 that
$\|\overline{\Phi}\|_{\operatorname{sym}}\geq 6p^{2}$. $\Box$

##  3 Alternative tensors

A straightforward argument based on splitting the tensor associated to the
trilinear form $\Psi$ as in (6) into real and complex parts shows that Theorem
1.2 holds also for a trilinear form
$\Phi:\ell_{\infty}^{n}\times\ell_{\infty}^{n}\times\ell_{\infty}^{n}\to\mathbb{C}$
whose associated tensor is real, which is to say that
$\Phi(e_{i},e_{j},e_{k})\in\mathbb{R}$ for every $i,j,k\in[n]$. Alternatively,
one can directly get such a form by replacing Proposition 2.8 in our
construction with the following statement [25, Exercise 11.1.17], giving a
random example.

######  Proposition 3.1.

Let $\Gamma$ be a finite Abelian group and $f:\Gamma\to\\{-1,1\\}$ be a
uniformly random mapping. Then, $\|f\|_{U^{t}(\Gamma)}\leq
O_{t}(|\Gamma|^{-1/2^{t}})$ with probability $1-o_{t}(1)$.

## Acknowledgments

The authors thank the anonymous referee for pointing out the short abstract
operator space proof of Lemma 2.11.

## References

  * [1] S. Aaronson, A. Ambainis, J. Iraids, M. Kokainis, and J. Smotrovs.  Polynomials, quantum query complexity, and Grothendieck’s inequality.  In Proc. 31st Conf. Comput. Complexity (CCC’16), pages 25:1–25:19, 2016.
  * [2] S. Arunachalam, J. Briët, and C. Palazuelos.  Quantum query algorithms are completely bounded forms.  SIAM J. Comput, 48(3):903–925, 2019.  Preliminary version in ITCS’18.
  * [3] T. Bannink, J. Briët, H. Buhrman, F. Labib, and T. Lee.  Non-local games with near-perfect quantum strategies.  In Proc. 36th Int. Symp. Theoretical Aspects Comput. Sci. (STACS’19), 2019.  To appear. Available at arXiv: 1811.11068.
  * [4] D. P. Blecher.  Tracially completely bounded multilinear maps on $C^{*}$-algebras.  J. London Math. Soc. (2), 39(3):514–524, 1989.
  * [5] J. Briët, O. Regev, and R. Saket.  Tight hardness of the non-commutative Grothendieck problem.  Theory Comput., 13:1–24, 2017.  Paper No. 15. Earlier version in FOCS’15.
  * [6] J. Briët and T. Vidick.  Explicit lower and upper bounds on the entangled value of multiplayer XOR games.  Commun. Math. Phys., 321(1):181–207, 2013.
  * [7] D. Conlon and Y. Zhao.  Quasirandom Cayley graphs.  Discrete Anal., pages 1–14, 2017.  Paper No. 6.
  * [8] T. Cooney, M. Junge, C. Palazuelos, and D. Pérez-García.  Rank-one quantum games.  Comput. Complexity, 24(1):133–196, 2015.
  * [9] M. De Chiffre, N. Ozawa, and A. Thom.  Operator algebraic approach to inverse and stability theorems for amenable groups.  Mathematika, 65(1):98–118, 2019.
  * [10] W. T. Gowers and O. Hatami.  Inverse and stability theorems for approximate representations of finite groups.  Mat. Sb., 208(12):70–106, 2017.
  * [11] A. Grothendieck.  Résumé de la théorie métrique des produits tensoriels topologiques (French).  Bol. Soc. Mat. São Paulo, 8:1–79, 1953.
  * [12] U. Haagerup.  The Grothendieck inequality for bilinear forms on $C^{\ast}$-algebras.  Adv. Math., 56(2):93–116, 1985.
  * [13] U. Haagerup and M. Musat.  The Effros-Ruan conjecture for bilinear forms on $C^{*}$-algebras.  Invent. Math., 174(1):139–163, 2008.
  * [14] S. Khot and A. Naor.  Grothendieck-type inequalities in combinatorial optimization.  Comm. Pure Appl. Math., 65(7):992–1035, 2012.
  * [15] A. Naor, O. Regev, and T. Vidick.  Efficient rounding for the noncommutative Grothendieck inequality.  Theory Comput., 10(11):257–295, 2014.  Earlier version in STOC’13.
  * [16] T. Oikhberg and G. Pisier.  The “maximal” tensor product of operator spaces.  Proc. Edinb. Math. Soc., 42(2):267–284, 1999.
  * [17] C. Palazuelos and T. Vidick.  Survey on nonlocal games and operator space theory.  J. Math. Phys., 57(1):015220, 2016.
  * [18] D. Pérez-García, M. Wolf, C. Palazuelos, I. Villanueva, and M. Junge.  Unbounded violation of tripartite Bell inequalities.  Commun. Math. Phys., 279:455, 2008.
  * [19] G. Pisier.  Grothendieck’s theorem for noncommutative $C^{\ast}$-algebras, with an appendix on Grothendieck’s constants.  J. Funct. Anal., 29(3):397–415, 1978.
  * [20] G. Pisier.  Introduction to operator space theory, volume 294 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 2003.
  * [21] G. Pisier.  Grothendieck’s theorem, past and present.  Bull. Amer. Math. Soc., 49(2):237–323, 2012.  Updated version available at arXiv: 1101.4195.
  * [22] G. Pisier and D. Shlyakhtenko.  Grothendieck’s theorem for operator spaces.  Invent. Math., 150(1):185–217, 2002.
  * [23] O. Regev and T. Vidick.  Quantum XOR games.  ACM Trans. Comput. Theory, 7(4):15:1–15:43, 2015.
  * [24] R. R. Smith.  Completely bounded multilinear maps and Grothendieck’s inequality.  Bull. London Math. Soc., 20(6):606–612, 1988.
  * [25] T. Tao and V. H. Vu.  Additive combinatorics, volume 105.  Cambridge University Press, 2006.
  * [26] B. S. Tsirelson.  Quantum analogues of the Bell inequalities. The case of two spatially separated domains.  J. Soviet Math., 36:557–570, 1987.
  * [27] N. T. Varopoulos.  On an inequality of von Neumann and an application of the metric theory of tensor products to operators theory.  J. Funct. Anal., 16:83–100, 1974.

[jop] Jop Briët
CWI - Centrum Wiskunde & Informatica
Amsterdam, The Netherlands
j.brietcwi.nl
https://homepages.cwi.nl/ jop/ [carlos] Carlos Palazuelos
Dep. Análisis Matemático y Matemática Aplicada
Universidad Complutense de Madrid
Madrid, Spain
cpalazuemat.ucm.es
https://www.ucm.es/mathqi/carlos-palazuelos-cabezon


# DRAG: Dynamic Region-Aware GCN for Privacy-Leaking Image Detection

Guang Yang1,2, Juan Cao1,2, Qiang Sheng1,2, Peng Qi1,2, Xirong Li3, Jintao Li1

###### Abstract

The daily practice of sharing images on social media raises a severe issue
about privacy leakage. To address the issue, privacy-leaking image detection
is studied recently, with the goal to automatically identify images that may
leak privacy. Recent advance on this task benefits from focusing on crucial
objects via pretrained object detectors and modeling their correlation.
However, these methods have two limitations: 1) they neglect other important
elements like scenes, textures, and objects beyond the capacity of pretrained
object detectors; 2) the correlation among objects is fixed, but a fixed
correlation is not appropriate for all the images. To overcome the
limitations, we propose the Dynamic Region-Aware Graph Convolutional Network
(DRAG) that dynamically finds out crucial regions including objects and other
important elements, and models their correlation adaptively for each input
image. To find out crucial regions, we cluster spatially-correlated feature
channels into several region-aware feature maps. Further, we dynamically model
the correlation with the self-attention mechanism and explore the interaction
among the regions with a graph convolutional network. The DRAG achieved an
accuracy of 87% on the largest dataset for privacy-leaking image detection,
which is 10 percentage points higher than the state of the art. The further
case study demonstrates that it found out crucial regions containing not only
objects but other important elements like textures. The code and more details
are in https://github.com/guang-yanng/DRAG.

## Introduction

Figure 1: Example of images that people share online in the Image Privacy
dataset (Yang et al. 2020). (a) is a public image that is safe for sharing,
while (b) is a private image that may leak sensitive information. Public and
private images contain many common elements as well as specific ones. The co-
occurrence and interaction of the elements provide semantic clues of scenes,
activities, etc., which is crucial for privacy-leaking image detection.
Therefore, methods for this task need to find out the elements and take their
co-occurrence and interaction into consideration.

Social media like Facebook has been part of our daily life. People post a
large number of images on social media to record and share their lives.
However, the convenience of online image sharing brings about the risk of
privacy leakage. The shared images contain rich information like personal
relationships and physical disability (Orekondy, Schiele, and Fritz 2017).
Malicious use of such information has been documented (Solsman 2020) causing
dire consequences like fraud and cyber violence (Equifax 2020). As a severe
issue that is close to our daily life, privacy-leaking image is attracting
increasing concerns.

Social media platforms allow users to set privacy preferences like the
visibility of their content to protect privacy, but many users still
unconsciously share images that may leak privacy. Although people have common
expectations about the privacy setting of online images (Hoyle et al. 2020),
they often lack the awareness of the privacy risk of the shared images
(Tuunainen, Pitkänen, and Hovi 2009; Wang et al. 2011). Liu et al. (2011)
proved that there is a gap between users’ expectations and the reality of
users’ privacy settings of the shared images. The above phenomenon and the
potential harms make it urgent to help users reduce the privacy risks during
image sharing. Users may unintentionally share images that leak privacy and
the spread of the images is almost uncontrollable. Therefore, a feasible
method to reduce the privacy risks is to automatically identify images that
may leak privacy and give warnings to users before sharing.

We use private images to refer to images that may leak privacy and public
images to refer to images that are safe for sharing. Researchers mainly
consider non-personalized consensus and build corresponding datasets, and
several examples are presented in Fig. 1. Following Tran et al. (2016) and
Yang et al. (2020), we formulate privacy-leaking image detection as a binary
classification task (i.e., predict whether a given image is private or
public). Fig. 1 demonstrates that the interaction among the elements in the
images provides clues and helps distinguish between private and public images.
Yang et al. focuses on objects and their correlation to identify private
images based on object detection. However, they neglect other important
elements like scenes (Tonge and Caragea 2019), textures, and objects beyond
the capacity of pre-trained object detectors. Furthermore, the correlation
among objects is fixed, but the elements vary in different images, making the
fixed correlation inappropriate.

To overcome the limitations, we propose Dynamic Region-Aware Graph
Convolutional Network (DRAG) to dynamically find out regions of the crucial
elements, and model their correlation adaptively per image. The workflow of
DRAG is presented in Fig. 2, which contains two main parts. In the first part
(Fig. 2 (2)), the DRAG finds out $N$ crucial regions from the feature map
without the reliance on the object detectors. Specifically, based on the
feature map obtained from the backbone, the DRAG clusters the spatially-
correlated feature channels into $N$ region-aware feature maps. In the second
part (Fig. 2 (3)), DRAG adopts the graph convolutional network (GCN) to model
the interaction among the $N$ regions. The regions are obtained dynamically
for each image, and thus the correlation among the regions should be adaptive
rather than predefined and fixed. We dynamically model the correlation with
the self-attention mechanism to initialize the correlation matrix for GCN.
Then the interaction among the $N$ crucial regions is explored by propagating
corresponding features through GCN with the adaptive correlation matrix.
Finally (Fig. 2 (4)), the propagated features are concatenated with a global
representation of the image to identify private images. Compared with existing
works, the dynamic nature of the DRAG enables it to find out more diverse
elements (not only objects) and model their correlations adaptively.

Our main contributions are summarized as follows:

  1. (1)

We proposed a novel framework DRAG for privacy-leaking image detection. The
DRAG dynamically finds out crucial regions without the limitation of
pretrained object detectors and models the correlation among crucial regions
adaptively for each image.

  2. (2)

To explore the interaction among the crucial regions, we proposed a region-
aware method to initialize the graph for GCN based on spatially-correlated
channels clustering and self-attention mechanism.

  3. (3)

The experimental results prove the effectiveness of the proposed framework for
privacy-leaking image detection. The DRAG that only utilizes visual features
outperformed existing methods, including visual-based and multi-modal ones.

Figure 2: Workflow of the Dynamic Region-Aware GCN (DRAG) for privacy-leaking
image detection. (1) DRAG first extracts the feature $\mathbf{F_{b}}$ of the
input image. (2) The channels of $\mathbf{F_{b}}$ are then clustered into $N$
groups with Channel Grouping Layer ($CGL$). According to the approximate
clustering result $\mathbf{cr^{\prime}}$, $\mathbf{F_{b}}$ are aggregated into
$N$ feature maps $\mathbf{F_{w}}$ to represent $N$ differentiated regions
(Examples are at the bottom). (3) DRAG formulates a graph with
$\mathbf{F_{w}}$ as the $N$ nodes and uses the self-attention mechanism to
obtain the correlation matrix $\mathbf{A}$. Then a GCN is used for feature
learning on this graph. (4) The learned feature $\mathbf{F_{p}}$ is
concatenated with a global representation of the image $\mathbf{F_{c}}$ to
identify private images.

## Related Work

### Privacy-Leaking Image in Online Image Sharing

Liu et al. (2020) concluded several privacy issues of online image sharing. In
this paper, we focus on the unawareness of privacy during image sharing. There
are two main types of methods to deal with the risk of unawareness of privacy.

The first type of method mainly adopts classification models to identify
private images. Zerr, Siersdorfer, and Hare (2012) proposed a privacy-aware
classifier based on visual features like face and color histograms. Buschek et
al. (2015) proposed a multi-modal method that assigns privacy labels to the
images based on visual features and metadata like location and publication
time. Tonge, Caragea, and Squicciarini (2018) utilized another kind of
metadata, tag, and Tonge and Caragea (2019) further derived features of the
object, scene, and tags for privacy-leaking image detection. Yang et al.
(2020) extracted a knowledge graph from the images and identified private
images based on object detection and graph neural networks.

The second type of method focuses on sensitive regions in the images,
including approaches like object detection and semantic segmentation. Some
detected private attributes such as faces (Sun, Wu, and Hoi 2018), license
plates (Zhou et al. 2012), and social relationship (Li et al. 2017a).
Orekondy, Schiele, and Fritz (2017) defined a list of privacy attributes and
detected them simultaneously. Some works attempted to protect privacy-leaking
image based on blurring (Fan 2018), blocking (Li et al. 2017b), cartooning
(Hasan et al. 2017), and perturbation (Oh, Fritz, and Schiele 2017). Shetty,
Fritz, and Schiele (2018) removed private objects from the images based on a
generative method. However, a person may be recognized even his face is not
visible (Oh et al. 2016), and the redacted image may be recovered (Shen et al.
2019). As the usage of shared images is almost uncontrollable, it is better to
prevent the risk from the beginning. Therefore, we follow the first type of
method to solve the issue of privacy-leaking images by classification.

### Graph-based Methods in Visual Tasks

Graph-based methods have shown great potential in many vision tasks in recent
years, including visual question answering (Teney, Liu, and van den Hengel
2017), person re-identification (Wu et al. 2019), multi-label image
recognition (Marino, Salakhutdinov, and Gupta 2017), and relationship
recognition (Wang et al. 2018). Ye et al. (2020) utilized GCN (Kipf and
Welling 2017) for multi-label classification. Yang et al. (2020) adopted graph
neural networks for privacy-leaking image detection and showed that modeling
the interaction among crucial elements is an effective way. However, their
framework only focuses on the objects that the pretrained object detector can
recognize. Inspired by Ye et al. (2020) and Yang et al. (2020), we proposed
DRAG that can model the interaction among more crucial elements dynamically
with GCN. Furthermore, instead of a fixed correlation matrix for all the
images (Yang et al. 2020), we extract the correlation matrix for each input
image adaptively based on the self-attention mechanism.

## Approach

### Overview of DRAG

The DRAG dynamically finds out crucial regions and models their correlation
adaptively for each input image. Then the DRAG explores the interaction among
the crucial regions with GCN and identifies the private images.

Specifically, the DRAG contains two main parts (see Fig. 2). In the first part
(Fig. 2 (2)), the DRAG extracts diverse and tiny clues and then clusters them
to obtain region-aware feature maps as the representation of crucial regions,
without the reliance on the object detectors. In the second part (Fig. 2 (3)),
the DRAG models the correlation among the crucial regions based on the self-
attention mechanism and initializes the correlation matrix for GCN. Then the
features of crucial regions are propagated through GCN with the adaptive
correlation matrix to explore the interaction among these regions. Finally
(Fig. 2 (4)), the propagated features are concatenated with a global
representation of the image to classify a given image as private or public.

### Dynamic Crucial Regions Exploring

Tasks like object detection and fine-grained image recognition need to focus
on objects for better performance. For example, the Region Proposal Network
(Ren et al. 2015) is used to select regions that may contain objects,
attention-based methods (Fu, Zheng, and Mei 2017) are used to focus on the
details of objects for fine-grained image classification. However, the clues
for privacy-leaking image detection are revealed not only by the objects but
also by other elements such as scenes and textures . To focus on these crucial
elements, we find out differentiated regions in an image based on the channel
grouping mechanism (Zheng et al. 2017).

We first trained a backbone (here, ResNet (He et al. 2016)) and got the
convolutional feature of the input image
$\mathbf{F_{b}}\in\mathcal{R}^{C\times H\times W}$, where $W$, $H$, and $C$
are the width, height, and channel number of the feature. According to Simon
and Rodner (2015), the peak responses of the channels correspond to various
visual patterns. Following Zheng et al. (2017), we clustered the channels by
K-means (MacQueen et al. 1967) according to spatial correlation among the
corresponding peak responses and adopted the cluster results as the
representation of crucial regions. To combine the clustering with neural
networks, the clustering process was approximated by several fully-connected
layers ($FCs$), and the details are as follows:

A group of channels whose peak responses appear in neighboring locations were
clustered together. For each channel, we got the coordinates of the peak
response $\left[t_{x},t_{y}\right]$ of all training images and formulated them
into a vector:
$\left[t_{x}^{1},t_{y}^{1},t_{x}^{2},t_{y}^{2},\ldots,t_{x}^{\Omega},t_{y}^{\Omega}\right]$,
where $t_{x}^{i}$ and $t_{y}^{i}$ are the coordinates of peak response of the
$i^{th}$ training image, and $\Omega$ refers to the size of the training set.
This vector was used as the feature for clustering with K-means. The channels
were clustered into $N$ groups to represent $N$ differentiated regions. The
clustering results were formulated as a matrix
$\mathbf{cr}\in\mathcal{R}^{N\times C}$ with $cr_{ij}=1$ or $0$, which
indicates that if the $j^{th}$ channel belongs to the $i^{th}$ group (i.e.,
the $i^{th}$ region).

The pretrained backbone initially focuses on the objects and will be fine-
tuned to adapt to privacy-leaking image detection. To let the clustering
results obtained from the backbone be optimized together, we adopted $FCs$ to
approximate the clustering process, which is called the channel grouping layer
($CGL$). $CGL$ takes the feature map $\mathbf{F_{b}}$ as input, then outputs
the estimated result of clustering
$\mathbf{cr^{\prime}}\in\mathcal{R}^{N\times C}$:

$\mathbf{cr^{\prime}}=CGL(\mathbf{F_{b}})=sigmoid(FCs(\mathbf{F_{b}})),$ (1)

We used the $\mathbf{cr^{\prime}}$ to get the feature of each region with an
averaged weighted sum mechanism. For the $i^{th}$ region, its corresponding
feature $\mathbf{F_{wi}}\in\mathcal{R}^{H\times W}$ was obtained by :

$\mathbf{F_{wi}}=\frac{1}{C}\sum_{c}\mathbf{F_{bc}}*cr^{\prime}_{ic},$ (2)

where $C$ is the number of channels in $\mathbf{F_{b}}$, $\mathbf{F_{bc}}$ is
the feature of the $c^{th}$ channel. $\mathbf{cr^{\prime}_{ic}}$ is the
estimated indicator that if the $c^{th}$ channel belongs to the $i^{th}$
region. By concatenating features of all regions, we finally obtained the
$\mathbf{F_{w}}\in\mathcal{R}^{N\times H\times W}$.

Initialization To obtain a proper initialization, $CGL$ was pretrained to let
the $\mathbf{cr^{\prime}}$ be as close to $\mathbf{cr}$ as possible, and the
details are described in the Experiments section. During the joint learning,
we adopted two losses, $Dis(\cdot)$ and $Div(\cdot)$, to force the $CGL$ to
learn differentiated regions as follows:

$\displaystyle Dis\\!\left(\mathbf{F_{w}}\right)$ $\displaystyle=\\!\sum_{i\in
N}\\!\sum_{(x,y)\\!\in\\!\mathbf{r_{i}}}\\!\mathbf{F_{wi}}(x\\!,\\!y)^{2}\\!\left[\left\|x\\!-\\!t_{ix}\right\|^{2}\\!+\\!\left\|y\\!-\\!t_{iy}\right\|^{2}\right],$
(3) $\displaystyle Div\\!\left(\mathbf{F_{w}}\right)$
$\displaystyle=\\!\sum_{i\in
N}\\!\sum_{(x,y)\\!\in\\!\mathbf{r_{i}}}\\!\mathbf{F_{wi}}(x\\!,\\!y)^{2}\left[\max_{j\neq
i}\mathbf{F_{wj}}(x\\!,\\!y)\\!-\\!mrg\right]^{2}\\!,$

where $i$ refers to the $i^{th}$ region, $t_{ix}$ and $t_{iy}$ are the
coordinates of peak response in the $i^{th}$ region. $mrg$ is the mean of all
the values in feature map $\mathbf{F_{w}}$, which represents a margin to make
$Div(\cdot)$ less sensitive to noise. The $Dis(\cdot)$ encourages a compact
distribution in the feature of a region (i.e., similar visual patterns from a
specific part to be grouped together), while the $Div(\cdot)$ forces the model
to learn diverse regions rather than similar ones. Such constraints make the
$CGL$ learn differentiated regions for image privacy detection.

### Dynamic Correlation Modeling

We obtained the feature of several crucial regions $\mathbf{F_{w}}$ based on
$CGL$. To explore the interaction among these crucial regions for privacy-
leaking image detection, we formulated a graph with regions as nodes and
correlation among the regions as the edges to take the advantage of GCN. The
regions were obtained dynamically for each image, and thus the correlation
should be adaptive rather than predefined and fixed. Inspired by Ye et al.
(2020) and Vaswani et al. (2017), we proposed a dynamic way to get an adaptive
correlation matrix for GCN.

To model the correlation among the $N$ crucial regions, we adopted the self-
attention mechanism (Vaswani et al. 2017) which is widely used in NLP tasks to
learn the correlation among words. We first got three vectors query ($q$), key
($k$), and value ($v$) from $\mathbf{F_{wi}}$ for each region $r_{i}$ with
three fully-connected layers. For all the $N$ regions, the matrices
$\mathbf{Q\in\mathcal{R}^{N\times d_{k}}}$, $\mathbf{K}\in\mathcal{R}^{N\times
d_{k}}$ and $\mathbf{V}\in\mathcal{R}^{N\times N}$ were calculated by:

$\displaystyle\mathbf{Q}$
$\displaystyle=\\!\mathbf{W_{q}}\mathbf{F}_{w}\\!+\\!\mathbf{b_{q}},\mathbf{K}\\!$
$\displaystyle=\\!\mathbf{W_{k}}\mathbf{F}_{w}\\!+\\!\mathbf{b_{k}},\mathbf{V}$
$\displaystyle=\\!\mathbf{W_{v}}\mathbf{F}_{w}\\!+\\!\mathbf{b_{v}},$ (4)

where $d_{k}$ is the dimension of both $q$ and $k$, and $\mathbf{W}$ and
$\mathbf{b}$ refer to the weights and biases in fully-connected layers,
respectively. The results of self-attention $\mathbf{A}$ was given by:

$\mathbf{A}=Attention(\mathbf{Q,K,V})=softmax\left(\frac{\mathbf{Q}\mathbf{K}^{T}}{\sqrt{d_{k}}}\right)\mathbf{V}.$
(5)

Each value in the matrix $\mathbf{A}\in\mathcal{R}^{N\times N}$ is obtained by
considering one region and all other ones. As a result, $\mathbf{A}$ is able
to represent the correlation among the $N$ regions.

### Feature Integration and Classification

We adopted GCN with the activation function of $ReLU$ to explore the
interaction among the crucial regions, which propagates features through the
nodes as follows:

$GCN(\mathbf{X})=ReLU(\hat{\mathbf{D}}^{-1/2}\hat{\mathbf{A}}\hat{\mathbf{D}}^{-1/2}\mathbf{X}\Theta),$
(6)

where $\mathbf{I}$ refers to an identical matrix,
$\hat{\mathbf{A}}=\mathbf{A}+\mathbf{I}$ denotes the adjacency matrix with
inserted self-loops, $\hat{D}_{ii}=\sum_{j=0}\hat{A}_{ij}$ is the diagonal
degree matrix, and $\Theta$ is the learned weights. To avoid over-smoothing of
node features, we only adopted two GCN layers and finally got the propagated
feature $\mathbf{F_{p}}\in\mathcal{R}^{N\times H\times W}$:

$\mathbf{F_{p}}=GCN(GCN(\mathbf{F_{w}})).$ (7)

To prevent that the learned regions neglect important global information in
the image, we got a compressed feature $\mathbf{F_{c}}\in\mathcal{R}^{1\times
H\times W}$ from the original feature map $\mathbf{F_{b}}$ by average
$\mathbf{F_{b}}$ through the channels. At last, the $\mathbf{F_{c}}$ was
concatenated with $\mathbf{F_{p}}$ for classification with a fully-connected
layer $FC$ and the activation function of $softmax$:

${\hat{y}}=softmax(FC(\mathbf{F_{c}}\oplus\mathbf{F_{p}})),$ (8)

where $\oplus$ denotes the concatenating operation. The output $\hat{y}$
represents the probability that if the input image is private.

## Experiments

### Experimental Setup

#### Datasets

PicAlert PicAlert (Zerr et al. 2012) is the first dataset for privacy-leaking
image detection on social media, which was built on an average community
notion of privacy. They first crawled images from image-sharing social media
Flickr111https://www.flickr.com/, then asked external viewers to judge the
privacy of the photos via a social annotation game. After removing invalid
annotations, they finally proposed a dataset of images with user-classified
privacy labels. The PicAlert we used contains 7,518 private images and 24,615
public images.

Image Privacy The PicAlert is somewhat biased as most of the private images in
PicAlert is person-containing. To diversify private images, Yang et al. (2020)
extended PicAlert to include more types of images reported in the previous
study (Tran et al. 2016), such as driver licenses, ID cards, and legal
documents. The Image Privacy dataset contains 13,910 private images and 24,615
public images.

#### Methods for Comparison

We compared DRAG with state-of-the-art methods, including Privacy-CNH (Tran et
al. 2016) and GIP (Yang et al. 2020) that only utilize visual information
obtained from the images, as well as Combination of Object, Scene, and User
Tags (Tonge, Caragea, and Squicciarini 2018) and DMFP (Tonge and Caragea 2019)
that utilize extra user tags222Tags that users annotate when sharing images,
often contain information that cannot be obtained from the image..

Privacy-CNH (Hereafter, PCNH) (Tran et al. 2016) proposed a framework that
utilized both object and convolutional features for privacy-leaking image
detection. The features are finally concatenated for classification.

GIP (Yang et al. 2020) is the first to adopt graph neural networks for
privacy-leaking image detection. The GIP first detects objects in an image
based on Faster-RCNN (Ren et al. 2015), and propagates the object features
through a predefined graph which is extracted from the training set.

Combination of Object, Scene, and User Tags (Hereafter, Combination) (Tonge,
Caragea, and Squicciarini 2018) combines object tags, scene tags, and user
tags for privacy-leaking image detection, which is a basic multi-modal method.
The object tags and scene tags are extracted from the visual features, while
the user tags are extra collected.

DMFP (Tonge and Caragea 2019) is also a multi-modal method that utilizes
object features, scene features, and tag features instead of the tags. The
DMFP estimates the competence of the modalities and fuses the decisions
dynamically. DMFP-O and DMFP-S denote DMFP that only utilize object features
and scene features, respectively.

#### Implementation

We conducted experiments on the two datasets to compare with state-of-the-art
methods for privacy-leaking image detection. To make a fair comparison, we
adopted the same experiment settings as Tonge and Caragea (2019) and Yang et
al. (2020). The ratio of train, val, and test set is 15:7:10 in both datasets.
The public and private images are in the ratio of about 3:1 in PicAlert and
about 7:4 in Image Privacy.

The models were implemented with python 3.6.8, PyTorch 1.4.0 (Paszke et al.
2019), torchvision 0.5.0 (Marcel and Rodriguez 2010), and torch-geometric
1.6.1 (Fey and Lenssen 2019). We first pretrained a ResNet as the backbone
model. We extracted the feature outputted by the last convolutional layer and
obtained $\mathbf{F_{b}}\in\mathcal{R}^{2048\times 14\times 14}$. We clustered
the channels into different regions following the process described in the
Approach section and got the clustering result
$\mathbf{cr}\in\mathcal{R}^{N\times 2048}$. We experimented with several
region numbers $N$, including $4,6,8,10$, and $12$, to explore the influence
of different region numbers. The clustering result $\mathbf{cr}$ was used to
pretrain the $CGL$ to let the $\mathbf{cr^{\prime}}$ be as close to
$\mathbf{cr}$ as possible, to enable the $CGL$ to learn differentiated
regions. We calculated the cross-entropy loss of all the $N$ regions and
$2048$ channels to optimize the $CGL$:

$L_{CGL}\\!=\\!-\\!\sum_{i\in N}\\!\sum_{j\in
C}\left[y_{ij}\log\left(\hat{y_{ij}}\right)\\!+\\!\left(1-y_{ij}\right)\log\left(1-\hat{y_{ij}}\right)\right],$
(9)

where $y_{ij}$ is the true label of the $j^{th}$ channel in the $i^{th}$
group, and $\hat{y_{ij}}$ is the corresponding predicted probability.

The correlation matrix $\mathbf{A}$ used for $GCN$ was learned during training
with the self-attention mechanism. For the self-attention module, the
dimension of $q$ and $k$ was $64$, while the dimension of $v$ was $N$. For the
$GCN$, the number of nodes was the same as the number of regions $N$. Feature
of each region was used to initialize the corresponding node, and thus the
feature of each node $i$ was $\mathbf{F_{wi}}\in\mathcal{R}^{14\times 14}$.
After exploring the interaction among nodes, the $GCN$ outputted
$\mathbf{F_{p}}\in\mathcal{R}^{N\times 14\times 14}$. Finally, by
concatenating the global feature $\mathbf{F_{c}}\in\mathcal{R}^{1\times
14\times 14}$,
$\mathbf{(F_{c}}\oplus\mathbf{F_{p}})\in\mathcal{R}^{(N+1)\times 14\times 14}$
was used for classification. For the binary classification task, we adopted
cross-entropy loss function:

$L_{cls}=-\sum_{i}\left[y_{i}\log\left(\hat{y_{i}}\right)+\left(1-y_{i}\right)\log\left(1-\hat{y_{i}}\right)\right],$
(10)

where $y_{i}$ is the true label of the $i^{th}$ sample, and $\hat{y_{i}}$ is
the corresponding predicted probability given by the model. The final loss
function was:

$L=L_{cls}+Dis(\cdot)+Div(\cdot).$ (11)

We adopted Adam (Kingma and Ba 2015) as the optimizer with the weight decay of
$1e-7$. The $L_{cls}$ and $(Dis(\cdot)+Div(\cdot))$ were optimized
alternately. The learning rate was set to be $1e-3$ for $CGL$, $1e-3$ for
$GCN$ and $1e-5$ for backbone during initialization. The models were trained
with the same strategy: pretrain the backbone; pretrain the $CGL$; optimize
the $CGL$; optimize the $GCN$ for several epochs; optimize the $GCN$ and the
backbone; optimize the $CGL$ again if necessary; fine-tune the backbone and
the $GCN$ for several epochs until convergence. Please refer to the source
code for more details.

Table 1: Comparison with the state of the art. The best and second-best results in each column are boldfaced and underlined, respectively. “*” indicates multi-modal methods that utilize extra user tags, while other methods only utilize the visual information obtained from the images. Dataset | Model | Source | Accuracy | Private |  | Public
---|---|---|---|---|---|---
Precision | Recall | F-1 |  | Precision | Recall | F-1
PicAlert | PCNH | AAAI (2016) | 83.15% | 0.689 | 0.514 | 0.589 |  | 0.862 | 0.929 | 0.894
GIP | PR (2020) | 83.49% | 0.552 | 0.684 | 0.610 |  | 0.922 | 0.871 | 0.895
*Combination | AAAI (2018) | 83.09% | 0.671 | 0.551 | 0.605 |  | 0.869 | 0.912 | 0.892
*DMFP | WWW (2019) | 86.36% | 0.752 | 0.627 | 0.684 |  | 0.891 | 0.936 | 0.913
DRAG | Ours | 86.84% | 0.719 | 0.719 | 0.719 |  | 0.914 | 0.914 | 0.914
Image | GIP | PR (2020) | 77.09% | 0.812 | 0.751 | 0.780 |  | 0.730 | 0.795 | 0.761
Privacy | DRAG | Ours | 87.68% | 0.811 | 0.842 | 0.826 |  | 0.914 | 0.895 | 0.905

### Experimental Results

#### Comparison with the State of the Art

Following previous works, we compared DRAG with state-of-the-art methods on
PicAlert and present the precision, recall, and F1 score of each class to
validate the effectiveness. We select the models with the best performances on
the validation set and report their performances on the test set. The
comparisons between the DRAG and the state of the art are presented in Table
1. Note that Combination (Tonge, Caragea, and Squicciarini 2018) and DMFP
(Tonge and Caragea 2019) are multi-modal methods that utilize extra user tags,
while other methods only utilize the visual information obtained from the
images. As the DRAG only utilizes visual information, we further compare with
the state-of-the-art visual-based method (i.e., GIP) on the more challenging
Image Privacy dataset.

We get several observations from the results. The DRAG outperforms other
methods in most metrics on both datasets, which proves the effectiveness of
the proposed framework. The accuracy and F-1 score of the DRAG is higher than
all other methods, including visual-based and multi-modal ones. Specifically,
the performances in the public class are similar for all methods, and the main
difference lies in the private class, which is also the class that we need to
pay more attention to. The DRAG achieved the highest F-1 score and also the
highest recall in the private class, which means that the DRAG will
significantly reduce the false-negative rate. Considering the practical task
of privacy-leaking image detection, this phenomenon means that fewer private
images will be classified as public incorrectly, and thus the DRAG will better
help reduce the unintentional sharing of private images compared with other
methods.

We observe that the DRAG achieved much better performance compared with GIP,
especially on the harder Image Privacy dataset. We analyzed the rationality as
follows, and we provide the corresponding Precision-Recall Curve in the
supplementary. First, as described in the Dataset section, the public images
are the same in the two datasets, while Image Privacy contains more images in
the private class. Therefore, Image Privacy is more balanced than PicAlert,
and the performances in the public class of both methods dropped on Image
Privacy. Second, objects are important clues for privacy-leaking image
detection, and thus GIP that relies on the object detector performed well on
PicAlert. But when dealing with a more complex dataset, the pretrained object
detector limits the ability to focus on other crucial elements like unseen
objects, scenes, and textures. Compared with GIP, the DRAG dynamically focus
on regions of the crucial elements and thus achieved better performances in
both classes. Our ablation studies in the next subsection also suggest that
the model needs to pay more attention to differentiated regions for privacy-
leaking image detection on Image Privacy than on PicAlert.

#### Ablation Study

Effectiveness of Dynamic Crucial Regions Exploring To obtain a variant without
the ability to dynamically explore crucial regions, we fixed the $CGL$ with
its initial features that mainly focus on objects, because the used backbone
was pretrained on the object-focused task. The results are presented in cyan
in Fig. 3 (“w/o CGL fine-tuned”). The performances drop on both datasets,
especially on the more complex Image Privacy. This phenomenon proves that the
model needs to explore more elements besides objects, especially for a more
complex task.

Effectiveness of Dynamic Correlation Modeling To obtain a variant without the
ability to dynamically model the correlation among crucial regions, we adopted
a graph that all nodes in the graph are connected with each other (i.e. a
graph with a fixed all-ones correlation matrix). The performances are
presented in green in Fig. 3 (“with fixed correlation”), which are worse than
those of DRAG in general. We further proposed a variant that completely
disregards the correlation, which is implemented by removing GCN from DRAG and
directly adopts the region features $\mathbf{F_{w}}$ for classification.
Similar to Eq. 8, we concatenate the features with a global feature, and feed
them into a fully connected layer for final prediction:
${\hat{y}}=FC(\rm\mathbf{F_{c}}\oplus\mathbf{F_{w}})$. The results are
presented in orange in Fig. 3 (“w/o GCN”), and the performances further
degrade. These results prove that considering the correlation among the
crucial elements is essential, while a dynamic correlation is better than a
fixed one.

(a) PicAlert

(b) Image Privacy

Figure 3: Ablation study and hyperparameter sensitivity. The baseline refers
to ResNet pretrained on the corresponding dataset (presented in red). The
performances drop when removing components from the DRAG, proving the
effectiveness of these components. The DRAG is relatively robust for region
number $N$, while $N=8$ achieved slightly better performance than other $N$ on
both datasets.

Discussion For DRAG, the performance is better on Image Privacy than on
PicAlert, but for the baseline is the opposite. As described before, Image
Privacy is an extension of PicAlert with challenging samples, which makes the
basic model perform worse. The DRAG benefits from the ability to dynamically
find out crucial regions and model their correlation, and still achieve
remarkable performance.

The dynamic crucial regions exploring and the dynamic correlation modeling
complement each other, but the importance of them is different for the two
datasets. The dynamic correlation modeling affects the performances more for
PicAlert, while the dynamic crucial regions exploring affects the performances
more for Image Privacy. We speculate that for a simpler dataset, the
pretrained $CGL$ is good enough to find out crucial regions, and the model
should pay more attention to the interaction among the regions. But for a more
complex dataset, the model needs to make more effort to focus on the crucial
regions that reflect subtle differences. This may also explain why GIP that
relies on the object detector and GNN performed well on PicAlert, but the
performances dropped a lot on Image Privacy.

(a) Region features of a private image (b) Region features of a public image

Figure 4: Two examples of the learned region feature obtained from $CGL$. In
the private image (a), the $CGL$ focuses on the lamp, the window, the person,
the doll on the chair, and the wall. In the public image (b), the $CGL$
focuses on the plant, the people, the doors, and the railing. The results show
that the $CGL$ can capture regions of crucial elements to differentiate
private and public images.

#### Hyperparameter Sensitivity

To validate the robustness of the model under parameter variations, we
investigated the sensitivity of the hyperparameter $N$, which determines the
number of regions during channel grouping, and also the number of nodes in the
GCN. The results are presented in Fig. 3. We explore the influence of ${N}$
with the complete model as well as the models in the ablation studies. The
tendencies are consistent for all models, and we can get several conclusions.
First, for most models, the variances of the performances between different
${N}$ are not very significant, suggesting that the DRAG is relatively robust.
Second, comparing the subtle differences , we found that the region number of
$8$ is most suitable for our experimental setups on both datasets. During our
experiments, we infer that the best selection of $N$ may depend on the size of
the feature map $\mathbf{F_{b}}$ used for clustering. A larger $N$ may be more
appropriate for a larger feature map. We will explain this inference based on
the following case study.

### Case study

Qualitative Analyses of the Region Features  We visualized the original image
and corresponding features of the crucial regions obtained from $CGL$ to
illustrate the capability of $CGL$. From Fig. 4, we observe that the $CGL$
learned differentiated regions of crucial elements as we expected. We also
notice that there exist overlaps between the peak responses in the feature
maps, and several feature maps are not very compact. During the training
stage, we combined the losses to ensure the classification performance and did
not make a quite strict constraint on the $Dis(\cdot)$ and $Div(\cdot)$, and
thus the results are reasonable. This may also explain why the region number
$N$ of $8$ is the most suitable one in our experiments — too small $N$ may
neglect important region features, while too large $N$ may result in overlaps.

(a) Public images that are misclassified into private. (b) Private images that
are misclassified into public.

Figure 5: Cases of misclassified images.

Limitation of DRAG  We conduct this study to learn what kind of images are
more likely to be misclassified. Fig. 5 (a) shows public images that were
misclassified into private. Although group photos are often related to private
occasions like family gatherings, the images here are actually art photography
and photos of public events. In Fig. 5 (b), the misclassified private images
contain elements such as ticket, medicine, age, and credit card number. The
examples indicate that the model may fail to understand the given images when
the external social context of sharing motivation and textual privacy is
necessary. Therefore, we argue that future works may obtain a deeper
understanding of the images by introducing social context. For example,
techniques of text recognition and natural language understanding can be used
to understand the specific types of card-like elements.

## Conclusion

In this paper, we proposed the DRAG for privacy-leaking image detection. The
DRAG dynamically finds out crucial regions and models their correlation
adaptively for each input image without the limitation of pretrained object
detectors. The experimental results show that the DRAG that only utilizes
visual features outperformed existing methods, including visual-based and
multi-modal ones. Further works may consider introducing external social
context to obtain a deeper understanding of the images. The code will be
released to facilitate further research.

## Acknowledgements

The corresponding author is Juan Cao. This work was supported by the Zhejiang
Provincial Key Research and Development Program of China (NO. 2021C01164), the
Project of Chinese Academy of Sciences (E141020), and the National Natural
Science Foundation of China (No. 62172420).

The authors thank Wu Liu, Xinchen Liu, Tianyun Yang, Lei Li, and anonymous
reviewers for their helpful advice on the paper. We also thank Yanyan Wang and
Lei Zhong for their help on the implementation of the model.

## References

  * Buschek et al. (2015) Buschek, D.; Bader, M.; von Zezschwitz, E.; and De Luca, A. 2015.  Automatic privacy classification of personal photos.  In _IFIP Conference on Human-Computer Interaction_ , 428–435.
  * Equifax (2020) Equifax. 2020.  Protect against identity theft when sharing photos online.  https://www.equifax.co.uk/resources/identity-protection/protect-against-identity-theft-when-sharing-photos-online.html/.  Accessed: November, 2020.
  * Fan (2018) Fan, L. 2018.  Image pixelization with differential privacy.  In _IFIP Annual Conference on Data and Applications Security and Privacy_ , 148–162.
  * Fey and Lenssen (2019) Fey, M.; and Lenssen, J. E. 2019.  Fast Graph Representation Learning with PyTorch Geometric.  In _ICLR Workshop on Representation Learning on Graphs and Manifolds_.
  * Fu, Zheng, and Mei (2017) Fu, J.; Zheng, H.; and Mei, T. 2017.  Look closer to see better: Recurrent attention convolutional neural network for fine-grained image recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 4438–4446.
  * Hasan et al. (2017) Hasan, R.; Shaffer, P.; Crandall, D.; Apu Kapadia, E. T.; et al. 2017.  Cartooning for enhanced privacy in lifelogging and streaming videos.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , 29–38.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep residual learning for image recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 770–778.
  * Hoyle et al. (2020) Hoyle, R.; Stark, L.; Ismail, Q.; Crandall, D.; Kapadia, A.; and Anthony, D. 2020\.  Privacy Norms and Preferences for Photos Posted Online.  _ACM Transactions on Computer-Human Interaction_ , 27(4): 1–27.
  * Kingma and Ba (2015) Kingma, D. P.; and Ba, J. 2015.  Adam: A Method for Stochastic Optimization.  In _International Conference on Learning Representations_.
  * Kipf and Welling (2017) Kipf, T. N.; and Welling, M. 2017.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations_.
  * Li et al. (2017a) Li, J.; Wong, Y.; Zhao, Q.; and Kankanhalli, M. S. 2017a.  Dual-glance model for deciphering social relationships.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 2650–2659.
  * Li et al. (2017b) Li, Y.; Vishwamitra, N.; Knijnenburg, B. P.; Hu, H.; and Caine, K. 2017b.  Blur vs. block: Investigating the effectiveness of privacy-enhancing obfuscation for images.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , 1343–1351.
  * Liu et al. (2020) Liu, C.; Zhu, T.; Zhang, J.; and Zhou, W. 2020.  Privacy Intelligence: A Survey on Image Sharing on Online Social Networks.  _arXiv preprint arXiv:2008.12199_.
  * Liu et al. (2011) Liu, Y.; Gummadi, K. P.; Krishnamurthy, B.; and Mislove, A. 2011.  Analyzing facebook privacy settings: user expectations vs. reality.  In _Proceedings of the ACM SIGCOMM Internet Measurement Conference_ , 61–70.
  * MacQueen et al. (1967) MacQueen, J.; et al. 1967.  Some methods for classification and analysis of multivariate observations.  In _Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability_ , volume 1, 281–297.
  * Marcel and Rodriguez (2010) Marcel, S.; and Rodriguez, Y. 2010.  Torchvision the machine-vision package of torch.  In Bimbo, A. D.; Chang, S.; and Smeulders, A. W. M., eds., _Proceedings of the 18th International Conference on Multimedia_ , 1485–1488.
  * Marino, Salakhutdinov, and Gupta (2017) Marino, K.; Salakhutdinov, R.; and Gupta, A. 2017.  The More You Know: Using Knowledge Graphs for Image Classification.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2673–2681.
  * Oh et al. (2016) Oh, S. J.; Benenson, R.; Fritz, M.; and Schiele, B. 2016.  Faceless person recognition: Privacy implications in social media.  In _European Conference on Computer Vision_ , 19–35.
  * Oh, Fritz, and Schiele (2017) Oh, S. J.; Fritz, M.; and Schiele, B. 2017.  Adversarial image perturbation for privacy protection a game theory perspective.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 1491–1500.
  * Orekondy, Schiele, and Fritz (2017) Orekondy, T.; Schiele, B.; and Fritz, M. 2017.  Towards a visual privacy advisor: Understanding and predicting privacy risks in images.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 3686–3695.
  * Paszke et al. (2019) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; Desmaison, A.; Köpf, A.; Yang, E.; DeVito, Z.; Raison, M.; Tejani, A.; Chilamkurthy, S.; Steiner, B.; Fang, L.; Bai, J.; and Chintala, S. 2019.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In Wallach, H. M.; Larochelle, H.; Beygelzimer, A.; d’Alché-Buc, F.; Fox, E. B.; and Garnett, R., eds., _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , 8024–8035.
  * Ren et al. (2015) Ren, S.; He, K.; Girshick, R.; and Sun, J. 2015.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In _Advances in Neural Information Processing Systems_ , 91–99.
  * Shen et al. (2019) Shen, L.; Hong, R.; Zhang, H.; Zhang, H.; and Wang, M. 2019.  Single-shot Semantic Image Inpainting with Densely Connected Generative Networks.  In _Proceedings of the 27th ACM International Conference on Multimedia_ , 1861–1869.
  * Shetty, Fritz, and Schiele (2018) Shetty, R. R.; Fritz, M.; and Schiele, B. 2018.  Adversarial scene editing: Automatic object removal from weak supervision.  In _Advances in Neural Information Processing Systems_ , 7706–7716.
  * Simon and Rodner (2015) Simon, M.; and Rodner, E. 2015.  Neural activation constellations: Unsupervised part model discovery with convolutional networks.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 1143–1151.
  * Solsman (2020) Solsman, J. E. 2020.  Deepfake bot on Telegram is violating women by forging nudes from regular pics.  https://www.cnet.com/news/deepfake-bot-on-telegram-is-violating-women-by-forging-nudes-from-regular-pics/.  Accessed: October, 2020.
  * Sun, Wu, and Hoi (2018) Sun, X.; Wu, P.; and Hoi, S. C. 2018.  Face detection using deep learning: An improved faster RCNN approach.  _Neurocomputing_ , 299: 42–50.
  * Teney, Liu, and van den Hengel (2017) Teney, D.; Liu, L.; and van den Hengel, A. 2017.  Graph-structured representations for visual question answering.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 1–9.
  * Tonge and Caragea (2019) Tonge, A.; and Caragea, C. 2019.  Dynamic deep multi-modal fusion for image privacy prediction.  In _The World Wide Web Conference_ , 1829–1840.
  * Tonge, Caragea, and Squicciarini (2018) Tonge, A.; Caragea, C.; and Squicciarini, A. 2018.  Uncovering scene context for predicting privacy of online shared images.  In _Proceedings of the 32nd AAAI Conference on Artificial Intelligence_ , 8167–8168.
  * Tran et al. (2016) Tran, L.; Kong, D.; Jin, H.; and Liu, J. 2016.  Privacy-CNH: a framework to detect photo privacy with convolutional neural network using hierarchical Features.  In _Proceedings of the 30th AAAI Conference on Artificial Intelligence_ , 1317–1323.
  * Tuunainen, Pitkänen, and Hovi (2009) Tuunainen, V. K.; Pitkänen, O.; and Hovi, M. 2009.  Users’ awareness of privacy on online social networking sites-case Facebook.  _Bled 2009 Proceedings_ , 42.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , 5998–6008.
  * Wang et al. (2011) Wang, Y.; Norcie, G.; Komanduri, S.; Acquisti, A.; Leon, P. G.; and Cranor, L. F. 2011.  ” I regretted the minute I pressed share” a qualitative study of regrets on Facebook.  In _Proceedings of the Seventh Symposium on Usable Privacy and Security_ , 1–16.
  * Wang et al. (2018) Wang, Z.; Chen, T.; Ren, J.; Yu, W.; Cheng, H.; and Lin, L. 2018.  Deep reasoning with knowledge graph for social relationship understanding.  In _Proceedings of the 27th International Joint Conference on Artificial Intelligence_ , 1021–1028.
  * Wu et al. (2019) Wu, J.; Yang, Y.; Liu, H.; Liao, S.; Lei, Z.; and Li, S. Z. 2019.  Unsupervised graph association for person re-identification.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 8321–8330.
  * Yang et al. (2020) Yang, G.; Cao, J.; Chen, Z.; Guo, J.; and Li, J. 2020.  Graph-Based Neural Networks for Explainable Image Privacy Inference.  _Pattern Recognition_ , 107360.
  * Ye et al. (2020) Ye, J.; He, J.; Peng, X.; Wu, W.; and Qiao, Y. 2020.  Attention-Driven Dynamic Graph Convolutional Network for Multi-Label Image Recognition.  In _European Conference on Computer Vision_ , 649–665.
  * Zerr, Siersdorfer, and Hare (2012) Zerr, S.; Siersdorfer, S.; and Hare, J. 2012.  Picalert!: a system for privacy-aware image classification and retrieval.  In _Proceedings of the 21st ACM International Conference on Information and Knowledge Management_ , 2710–2712.
  * Zerr et al. (2012) Zerr, S.; Siersdorfer, S.; Hare, J.; and Demidova, E. 2012.  Privacy-aware image classification and search.  In _Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 35–44.
  * Zheng et al. (2017) Zheng, H.; Fu, J.; Mei, T.; and Luo, J. 2017.  Learning multi-attention convolutional neural network for fine-grained image recognition.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 5209–5217.
  * Zhou et al. (2012) Zhou, W.; Li, H.; Lu, Y.; and Tian, Q. 2012.  Principal visual word discovery for automatic license plate detection.  _IEEE Transactions on Image Processing_ , 21(9): 4269–4279.


\sum_{i=0}^{k-1} \mathbf{a}_i -  \sum_{i=0, i\neq r}^{k-1} \gamma_i \mathbf{a}_i & (\gamma_i \geq 1)\\
\vdots
\end{NiceArray}.

As we assume the tokens are one-hot, we can set the classifier layer as

\mathbf{W}_{O} = \begin{NiceArray}{ \left\lgroup ccc \right\rgroup}
\mathbf{0}_{(d_1  + 1) \times d_2 } & \mathbf{I}_{d_2  \times d_2} & \mathbf{0}_{(d' - d  \times d_2)}\\
\mathbf{0}_{(d_1  + 1) \times (c - d_2 )} & \mathbf{0}_{d_2  \times (c - d_2 )} & \mathbf{0}_{(d' - d  \times (c - d_2 ))}\\
\end{NiceArray}.

By letting $c = d_2$, the final prediction result is $\sum_{i=0}^{k-1} \mathbf{a}_i -  \sum_{i=0, i\neq r}^{k-1} \gamma_i \mathbf{a}_i \, (\gamma_i \geq 1)$, which has the largest element corresponding to the final answer $\mathbf{a}_r$.

§ EXPANDING FROM RELU TO SOFTMAX ATTENTION

When considering a transformer with a single layer and a single head, the results for a single-layer ReLU attention transformer still hold.

In the case of softmax attention, which replaces the activation function in Equation <ref> from ReLU ($\sigma(x) = \max\{0,x\}$) to softmax ($\text{softmax}(\mathbf{x})_i = \frac{e^{x_i}}{\sum_{j=1}^{K}e^{x_j}}$), the input sequence $\mathbf{X} \in \mathbb{R}^{d' \times n}$. For a single attention head with parameters $\mathbf{W}_{V}$ and $\mathbf{W}_{QK}$, we define $\sigma'(\mathbf{x}_j,\mathbf{x}_k) = \exp(\mathbf{x}_j^\top  \mathbf{W}_{QK} \mathbf{x}_k)$. Equation <ref> can be rewritten for softmax attention as follows:

\begin{align}\label{eq:transformer_spft_attn_1}
\texttt{TF}_{\text{soft}}(\mathbf{H})[k] &= \mathbf{x}_{n-1}  + \sum_{i=0}^{n-1}  \frac{ \mathbf{W}_{V}\mathbf{x}_i \sigma'(\mathbf{x}_i,\mathbf{x}_{k}) }{\sum_{j=0}^{n-1}\sigma'(\mathbf{x}_j,\mathbf{x}_{k})}
\end{align}

If the input sequences $\mathbf{X}^{(0)},\mathbf{X}^{(1)},\dots, \mathbf{X}^{(N-1)} \in \mathcal{X}^n$  are dependent, then for any single layer single head transformer with softmax attention $\texttt{TF}_{\text{soft}}$, we have

\lambda'_0 (\texttt{TF}_{\text{soft}}(\mathbf{X}^{(0)})[n-1])  + \lambda'_1 (\texttt{TF}_{\text{soft}}(\mathbf{X}^{(1)})[n-1]) + \dots + \lambda'_{N-1} (\texttt{TF}_{\text{soft}}(\mathbf{X}^{(N-1)})[n-1]) = \mathbf{0}.

where $\lambda'_i = \sum_{j=0}^{n-1}\sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1}) \lambda_i$, $\{\lambda_i\}_{i=0}^{N-1}$ represents the coefficients defined in <ref>.

Consider the last token

\texttt{TF}_{\text{soft}}(\mathbf{X}^{(e)})[n-1] = \mathbf{x}_{n-1}  + \sum_{i=0}^{n-1}  \frac{ \mathbf{W}_{V}\mathbf{x}^{(e)}_i \sigma'(\mathbf{x}^{(e)}_i,\mathbf{x}_{n-1}) }{\sum_{j=0}^{n-1}\sigma'(\mathbf{x}^{(e)}_j,\mathbf{x}_{n-1})}

then we have

\begin{equation}
\begin{split}
&\lambda'_0 (\texttt{TF}_{\text{soft}}(\mathbf{X}^{(0)})[n-1])  + \lambda'_1 (\texttt{TF}_{\text{soft}}(\mathbf{X}^{(1)})[n-1]) + \dots + \lambda'_{N-1} (\texttt{TF}_{\text{soft}}(\mathbf{X}^{(N-1)})[n-1])\\
=& \mathbf{x}_{n-1} (\sum_{i=0}^{n-1} \sum_{j=0}^{n-1}\lambda_i (\sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1})) ) +  (\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} (\lambda_i \mathbf{W}_{V}\mathbf{x}^{(i)}_j \sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1}) )
\end{split}
\end{equation}

Similar with the proof techique in <ref> we can divide the sequences into two groups $\mathcal{I}_{+}$ and $\mathcal{I}_{-}$ so in each position $j$, both side have the same occurrence for each token:

\begin{equation}
\sqcap_{i \in \mathcal{I}_{+}} (\lambda_i \otimes \mathbf{x}^{(i)}_j) = \sqcap_{i \in \mathcal{I}_{-}} (-\lambda_i \otimes \mathbf{x}^{(i)}_j) := \mathcal{S}_j,
\end{equation}

here we use $\mathcal{S}_j$ to denote the tokens occurrences at position $j$, note that

$$\lambda \mathbf{W}_{V}\mathbf{x}^{(i)}_j \sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1}) = \sum_{\mathbf{s} \in (\lambda \otimes \mathbf{x}^{(i)}_j)} \mathbf{W}_{V}\mathbf{s} \sigma'(\mathbf{s},\mathbf{x}_{n-1})$$

$$\lambda \sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1}) = \sum_{\mathbf{s} \in (\lambda \otimes \mathbf{x}^{(i)}_j)} \sigma'(\mathbf{s},\mathbf{x}_{n-1})$$

, so we can derive the following equation:

\begin{equation}
\begin{split}
&\sum_{j=0}^{n-1}\lambda_i (\sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1}))\\
=&\sum_{i \in \mathcal{I}_{+}} \lambda_i \sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1}) - \sum_{i \in \mathcal{I}_{-}} -\lambda_i \sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1}) \\
=&\sum_{\mathbf{s} \in \mathcal{S}_j} \sigma'(\mathbf{s},\mathbf{x}_{n-1}) - \sum_{\mathbf{s} \in \mathcal{S}_j} \sigma'(\mathbf{s},\mathbf{x}_{n-1})\\
\end{split},
\end{equation}

\begin{equation}
\begin{split}
&\sum_{j=0}^{n-1}\lambda_i (\mathbf{W}_{V}\mathbf{x}^{(i)}_j \sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1}))\\
=&\sum_{i \in \mathcal{I}_{+}} \lambda_i (\mathbf{W}_{V}\mathbf{x}^{(i)}_j \sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1})) - \sum_{i \in \mathcal{I}_{-}} -\lambda_i (\mathbf{W}_{V}\mathbf{x}^{(i)}_j \sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1})) \\
=&\sum_{\mathbf{s} \in \mathcal{S}_j} (\mathbf{W}_{V}\mathbf{s} \sigma'(\mathbf{s},\mathbf{x}_{n-1})) - \sum_{\mathbf{s} \in \mathcal{S}_j} (\mathbf{W}_{V}\mathbf{s}  \sigma'(\mathbf{s},\mathbf{x}_{n-1}))\\
\end{split},
\end{equation}

Based on <ref>, we observe that the single layer single head softmax transformer shares a similar dependent property with the ReLU attention only transformer:

If the input sequences $\mathbf{X}^{(0)},\mathbf{X}^{(1)},\dots, \mathbf{X}^{(N-1)} \in \mathcal{X}^n$  are dependent, then for any single layer single head softmax transformer $\texttt{TF}_{\text{soft}}$, their prediction result $\mathbf{o}^{(0)},\dots,\mathbf{o}^{(N-1)}$

\lambda'_0 \mathbf{o}^{(0)}  + \lambda'_1 \mathbf{o}^{(1)} + \dots + \lambda'_{N-1} \mathbf{o}^{(N-1)} = \mathbf{0}.

where $\lambda'_i = \sum_{j=0}^{n-1}\sigma'(\mathbf{x}^{(i)}_j,\mathbf{x}_{n-1}) \lambda_i$, $\{\lambda_i\}_{i=0}^{N-1}$ represents the coefficients defined in <ref>.

Expanding our results from <ref>,<ref> to the softmax attention only transformer, we can conclude that a single-layer single-head attention only transformer is incapable of handling our reasoning and generalization tasks.