also at ]Michigan State University, East Lansing, MI 48823, USA

# Using artificial-intelligence tools to make LaTeX content accessible to
blind readers

Gerd Kortemeyer<EMAIL_ADDRESS>Educational Development and Technology, ETH
Zurich, 8092 Zurich, Switzerland  [

###### Abstract

Screen-reader software enables blind users to access large segments of
electronic content, particularly if accessibility standards are followed.
Unfortunately, this is not true for much of the content written in physics,
mathematics, and other STEM-disciplines, due to the strong reliance on
mathematical symbols and expressions, which screen-reader software generally
fails to process correctly. A large portion of such content is based on source
documents written in LaTeX, which are rendered to PDF or HTML for online
distribution. Unfortunately, the resulting PDF documents are essentially
inaccessible, and the HTML documents greatly vary in accessibility, since
their rendering using standard tools is cumbersome at best. The paper explores
the possibility of generating standards-compliant, accessible HTML from LaTeX
sources using Large Language Models. It is found that the resulting documents
are highly accessible, with possible complications occurring when the
artificial intelligence tool starts to interpret the content.

##  I Introduction

Compared to paper printouts, electronic documents generally have the advantage
of being accessible to blind readers using screen-reader technology Borodin et
al. (2010): the software reads the text on the screen using speech synthesis
(oftentimes at amazing speeds!), and users can navigate the document using the
keyboard by following hyperlinks or jumping from section to section. How a
screen reader works, unfortunately, is hard to convey without observing users
Salt Lake Community College (Accessed: 2023-06-04); University of California
San Francisco (Accessed: 2023-06-04).

Particularly in physics and mathematics, but also in other STEM disciplines,
LaTeX continues to be the dominant typesetting environment for scientific
articles and reports, as well as for lecture scripts and other teaching
materials. The LaTeX source is most frequently processed into a PDF
presentation document. While screen-reader technology generally works well for
web pages, particularly if accessibility standards like WCAG WWW Consortium
(Accessed: 2023-06-03) (W3C) are followed, it frequently fails to adequately
make PDF documents accessible, which leaves large segments of scientific
content out of immediate reach for blind users Nganji (2015). Particularly in
Europe, where lectures are oftentimes accompanied by instructor-authored
scripts rather than standard textbooks, these shortcomings of PDF also
strongly disadvantage blind students while pursuing higher education Petz and
Miesenberger (2015); Gilligan (2020).

Currently, either particular LaTeX packages with some restrictions on syntax
and later rendering need to be applied when writing the LaTeX source Ahmetovic
et al. (2018); Manzoor et al. (2019), or specialized tools need to be used to
later mark up the rendered PDF Darvishy (2018); Jembu Rajkumar et al. (2020).
In an alternative approach, the LaTeX source is rendered to HTML with embedded
MathJax Cervone (2012); Cervone et al. (2016) using tools like `htlatex`;
unfortunately, this approach is also not compatible with all of LaTeX’s
syntactical variants. Given the current restrictions, some blind users prefer
having the original LaTeX source available to their screen-reader software
Sorge et al. (2014), however, students in introductory courses are likely not
proficient in LaTeX.

Narrating mathematical formulas requires either explicit semantic markup,
which is usually not provided, or other sense-making technologies. When
automated mechanisms fail, this work currently needs to be done by human
experts. The Large Language Model GPT has been shown to have remarkable
mastery of physics and mathematics Kortemeyer (2023), and it might be up to
the task. In this exploratory study, GPT-4 OpenAI (Accessed: 2023-06-03) is
used to translate the LaTeX source to HTML while narrating the formulas and
graphics in plain language.

##  II Presentation versus semantics

Any kind of document we see on paper or on screen is a presentation of
content, and we are using certain visual clues and symbols to convey meaning
(“semantics”). For example, something that is larger and boldface is
interpreted as a heading for a new section or subsection of a document, and
when we glance over the document, we might jump from heading to heading to see
what might be worth reading. Screen-reader software cannot glance over a
document, it needs to rely on semantic clues in the document. To the eye,
`\section*{Findings}` and `\textbf{\Large FINDINGS}` will look the same, but
the former has embedded meaning, namely, this is where an unnumbered section
starts, while the latter just specifies presentation that the eye (actually,
our whole image-processing pipeline) needs to interpret and make sense of.

One of the many reasons for using LaTeX is its ability to beautifully typeset
mathematical equations. A large challenge in narrating these formulas is that
mathematical typesetting is not necessarily semantic, nor even designed to be,
and that in fact there are ambiguities. LaTeX, and for that matter also
handwriting, provides a presentation view of an equation Fateman (1998). An
expert usually sees what is meant, even if the semantics are sloppily or not
explicitly presented. For example, when we see $1/kT$, we will automatically
assume $1/(kT)$ instead of $T/k$, since we are used to seeing those two
symbols as essentially conjoined. Or when we see

$\int_{R_{i}}^{R_{f}}\int_{0}^{2\pi}\int_{0}^{\pi}\varrho(r,\varphi,\theta)\
r^{2}\sin\theta\ dr\ d\varphi\ d\theta\ ,$

we assume that the first $d$ goes with the limits of the first $\int$, etc.,
and that whatever appears between the $\int$s and the $d$s is what should be
integrated (essentially abusing the span between those symbols as
parenthesis), even though there is nothing that explicitly says so.

When asked to read the above formula, we might say something like “The
integral of the density $\varrho$ as a function of the radius $r$ and the
angle $\varphi$ between the inner boundary $R_{i}$ …‘,” instead of “integral
sign lower index uppercase r lower index i upper index uppercase r lower index
f integral sign lower index ….” By the way, very likely we automatically read
“$\varrho(r,\varphi,\theta)$” as “$\varrho$ as a function of $r$, $\varphi$
and $\theta$” without even for a moment wondering if that is $\varrho$
multiplied with some three-dimensional vector $(r,\varphi,\theta)$, which
would have the same notation.

Arguably, both LaTeX and the conventions of mathematical notation would have
allowed a construct like

    \int_{R_i}^{R_f}{dr}{
       \int_{0}^{2\pi}{d\varphi}{
          \int_{0}^{\pi}{d\theta}{
             \ \varrho{(r,\varphi,\theta)}\ r^2\sin{(\theta)}
          }
       }
    }

which would have conveyed semantics in the source code and be presented as

$\int_{R_{i}}^{R_{f}}{dr}{\int_{0}^{2\pi}{d\varphi}{\int_{0}^{\pi}{d\theta}{\
\varrho{(r,\varphi,\theta)}\ r^{2}\sin{(\theta)}}}}$

Realistically, though, probably nobody would go through that kind of trouble,
and making sense of a conglomerate of symbols is left to the experience of the
reader, and yes: his or her intelligence. Can artificial intelligence do the
job of making sense of the formulas in correctly narrating them?

##  III Methodology

To explore the feasibility of using Large Language Models for the translation
of LaTeX documents into WCAG-compliant HTML, a test document was generated
using REVTeX Ogawa (2001), Tikz Walczak (2008), BibTeX Fenn (2006),
`\newcommand`, tables, equation references, and the `wasysym` package. Fig. 1
shows the PDF rendering of this document.

The document was translated using the May 24, 2023 release of GPT-4 OpenAI
(Accessed: 2023-06-03) through the ChatGPT interface, with the following
primary prompt:

> Translate the following LaTeX and BibTeX into screen-reader-accessible HTML,
> translating the formulas into English (including the indices), and
> translating labels and citations into anchors and links. For figures, just
> give a description in English, no code for embedding an image:

The LaTeX source and the BibTeX source were then pasted below this primary
prompt, and the generated HTML was copied using the built-in “Copy code”
function. This process is illustrated in Fig. 2

Figure 1: LaTeX rendering of the test document.

…

…

Figure 2: ChatGPT dialogue

As GPT-4 uses a probabilistic algorithm, every query will result in different
HTML rendering; thus, more than one output was generated. The results were
analyzed for WCAG-compliance, as well as for the subjective quality of the
transcriptions provided by GPT-4.

##  IV Findings

Figures 3 and 4 show the web-browser output rendering the HTML from one query,
while Figures 5 and 6 show the result from a second, immediately subsequent
query using ChatGPT’s “Regenerate response” function. Already at first glance,
both outputs are different, which will be explored in more detail when
considering WCAG and physics properties of the responses.

It should be emphasized at this point that the output does not, and in fact
should not, look like the PDF in Fig. 1. The “looks” literally do not matter,
instead, the HTML needs to be speakable and navigable by screen-reader
software, so blind users can listen to the content and find their way around
the document structure. Arguably, in terms of Universal Design Iwarsson and
Ståhl (2003); Persson et al. (2015), this is bad practice: the same document
should be used by seeing and non-seeing users; future work may bring
satisfactory alignment with the principles of Universal Design; alternatively,
a change in publishing practices, suggested in the discussion section, might
be called for.

Figure 3: First HTML rendering of the test document, top part.

Figure 4: First HTML rendering of the test document, bottom part.

Figure 5: Second HTML rendering of the test document, top part.

Figure 6: Second HTML rendering of the test document, bottom part.

###  IV.1 Document Structure

An important component of a screen-reader compatible document is its
structure. The screen-reader software builds an index of document sections, so
the user can quickly navigate from one segment to another. In HTML, the
essential tags are the section headers, as marked up by `<h1>...</h1>`,
`<h2>...</h2>`, etc. GPT correctly interpreted

    \begin{document}

    \title{Testing \LaTeX{} Accessibility}
    \author{Zaphod Beeblebrox}
     \affiliation{Sirius Cybernetics Corporation}
    \date{\today}

    \begin{abstract}
    This is a document to explore ...

and inserted structures such as

Testing LaTeX Accessibility

Author: Zaphod Beeblebrox, Sirius ...

Date: Today’s Date

Abstract

This is a document to explore ...

which not only use the correct section headers, but in one of the responses
also the above shown additional semantic markup like the HTML5-tags `<header>`
and `<section>`; those potentially helpful tags were missing in the second
rendering. However, both versions were perfectly accessible to and navigable
by screen-reader software.

###  IV.2 New Commands

Several HTML-rendering tools fail to interpret `\newcommand`. The test
document included

    \newcommand{\thesquareroot}{\sqrt{1-\frac{v^2}{c^2}}}

which was used in nearly all subsequent formulas and interpreted correctly in
every case. For example, `$L’=L\thesquareroot$` was interpreted as “L prime
equals L times the square root of 1 minus v squared over c squared.”

###  IV.3 Equations

GPT-4 overall did very well in narrating equations. As an example,

    \begin{equation}
    \oiint\vec{E}\cdot d\vec{S} =
       \frac{1}{\epsilon_0}\iiint\varrho dV
    \end{equation}

was translated into

> The closed integral of E dot dS equals one over epsilon zero times the
> triple integral of rho dV.

in the first version (Fig. 3), and

> The surface integral over the vector E dotted with the infinitesimal area
> vector dS equals 1 over the permittivity of free space times the volume
> integral over the volume charge density times the infinitesimal volume dV.

in the second version (Fig. 5).

Both narratives are adequate and could be spoken by screen-reader software.
The first rendering is rather literal, though, and fails to mention that the
first integral is a surface integral, and that $\vec{E}$ and $d\vec{S}$ are
vectors. A physicist will understand this concise narrative and probably be
thankful that it is not too verbose, while a learner (actually, any learner,
blind or seeing) would be thankful for the second, interpretive rendering. It
is remarkable that GPT provided the physical meaning of the symbols alongside
the narrative of their mathematical connections.

Another example is

    \begin{equation}\label{eq:famous}
    E=\frac{mc^2}{\thesquareroot}\stackrel{v=0}{=}mc^2
    \end{equation}

which is rendered

> E equals mc squared divided by the square root of 1 minus v squared over c
> squared, which simplifies to mc squared when v equals 0.

in one version, and

> E equals mc squared divided by the square root of (1 minus (v squared
> divided by c squared)) when v is not equal to 0. When v equals to 0, E
> equals mc squared.

in the other. Both are essentially equivalent, and both do a remarkable job of
interpreting `\stackrel` (even though, the full expressions is correct
regardless of $v$ being zero or not).

A true challenge could have been posed by the rotation matrix:

    \begin{eqnarray}
    \vec{x}’&=&D\vec{x}\\
    D&=&\left(\begin{array}{ccc}
    \cos\theta&\sin\theta&0\\
    -\sin\theta&\cos\theta&0\\
    0&0&1
    \end{array}\right)
    \end{eqnarray}

Intriguingly, this was incorporated into the running narrative in one version
(Fig. 4),

> Consider a rotation matrix about the z-axis in three-dimensional space, x
> prime equals D x and D equals cos theta, sin theta, 0 in the first row,
> minus sin theta, cos theta, 0 in the second row, and 0, 0, 1 in the third
> row.

and spelled out rather literally in the other (Fig. 6),

> The vector x prime equals the matrix D times the vector x.
> The rotation matrix D is a 3x3 matrix with elements cos theta, sin theta, 0
> on the first row, -sin theta, cos theta, 0 on the second row, and 0, 0, 1 on
> the third row.

Once again, both versions correctly describe the situation, and a blind person
would be able to envision the matrix in his or her head based on the
description.

On the other hand, the equation

    \begin{equation}
    x’^\nu=\sum_{\mu=0}^3\Lambda^\nu_{\ \mu}x^\mu
    \end{equation}

is the first example of a situation where one of the narratives falls short:

> x prime nu equals the sum from mu equals 0 to 3 of Lambda nu mu x mu.

is less helpful than

> x prime superscript nu equals the sum from mu equals 0 to 3 of lambda
> superscript nu subscript mu times x superscript mu.

since it fails to distinguish between covariant and contravariant indices. The
nonchalant treatment of indices are also the reason for parenthetically
introducing “including the indices” into the prompt; without that phrase, the
GPT-algorithm recognized the matrix multiplication for what it is and simply
stated

> The transformed x vector equals the sum from mu equals 0 to 3 of Lambda
> times the original x vector.

In fact, even before that, it already assumed the summation convention and
rendered $x^{\prime\nu}=\Lambda^{\nu}_{\ \mu}x^{\mu}$ as

> The transformed x vector equals Lambda times the original x vector.

This highly concise rendering would likely be appreciated by an expert, but
might generally be too far from the original.

###  IV.4 Links and References

Links and references were handled differently in both renderings. For example,
toward the bottom of the LaTeX source, it says

    One could say a lot more about Special Relativity,
    but \textit{don’t panic}~\cite{adams2010}!
    At the very least, remember equation~\ref{eq:famous}!

In the first version, the GPT algorithm had included

E equals mc squared divided ...

at the place where the formula appeared, as well as

Adams, Douglas. The Ultimate ...

into the reference list, and it rendered the LaTeX as

    ... but don’t panic[5]!
    At the very least, remember equation
    2!

This in fact only works if following the hyperlinks, since neither the
equation nor the reference have numbers appearing in the output (the reference
list used the unordered list `<ul>` instead of the ordered list `<ol>`). A
blind user, however, could follow those hyperlinks to get to the correct
equation and references.

The second version uses a different approach:

    ... but don’t panic
    Adams 2010!
    At the very least, remember equation
    E equals mc squared divided by the square root
    of (1 minus (v squared divided by c squared))!

This approach works for both blind and seeing readers, but actually quoting
the referenced equation could become awkward if the equation is a long one; in
this case, GPT only quoted the first part, which may not have been what the
author wanted to reference. This literature reference also works for seeing
readers, since the author name is used. In this version, though, the table
reference does not work for any readers, since at simply says

    Table 1 lists some of the most commonly used ...

but the table has no number.

###  IV.5 Tables

The table in the source document was coded as

    \begin{table}
    \caption{\label{tab:formulas}Some relativistic formulas}
    \begin{tabular}{p{1.8cm}p{4cm}l}
    Common Name&Meaning&Formula\\\hline
    Time\newline Dilation&Transformation ...
    \end{tabular}
    \end{table}

which, as an example, in one the HTML versions, GPT interpreted as

Some relativistic formulas

                Common Name
                Meaning
                Formula

                Time Dilation
                Transformation ...

Both versions generated by GPT were WCAG compliant and can be navigated by
screen readers. Particularly helpful is that the first row was interpreted as
column headers (`<th>` instead of `<td>`), which is not even specified in the
LaTeX markup.

###  IV.6 Figures

While GPT-4 itself is multimodal, that is, it can support audio, image, and
video input and output, the ChatGPT interface only allows for text-based
conversations. However, the figure in the test document is generated using the
popular Tikz package Walczak (2008):

    \begin{figure}
    \begin{tikzpicture}
    \draw[thick,->] (2,0) -- (4,0)
               node[anchor=north west] {$x$};
    \draw[thick,->] (2,0) -- (2,2)
               node[anchor=south east] {$y$};
    \draw[dotted,thick,->] (2,0) -- (3.732,1)
               node[anchor=north west] {$x’$};
    \draw[dotted,thick,->] (2,0) -- (1,1.732)
               node[anchor=south east] {$y’$};
    \draw(3,0) node[anchor=south east] {$\theta$};
    \end{tikzpicture}
    \caption{Rotating a coordinate system.\label{fig:coord}}.
    \end{figure}

GPT was prompted to describe this figure, but not draw it. The first version
states

             Figure 1: Rotating a coordinate system.

A coordinate system is represented
        with x and y axes.
        Two additional axes, x prime and y prime,
        are represented,
        rotated from the original x and y axes
        by an angle theta.

while the second version has a simpler description that is woven into the
narrative:

This is illustrated in Figure 1 which shows a rotation
    of a coordinate system with x, y axes and the rotated
    x prime, y prime axes.

This second version correctly recognizes the contents of the figure, but fails
to mention the angle $\theta$ that is also in the figure. Overall, both
descriptions are useful.

##  V Discussion

Ironically, if this paper gets published as a PDF, it will not be accessible
to blind users. How can this be remedied, based on the findings of this
exploratory study? In recent years, there has been a strong movement toward
Open Access publication; based on this exploratory study, maybe publications
should also become Open Source.

Over the coming years, it is to be expected that artificial-intelligence tools
will increasingly become personalized agents; this is already suggested by the
concepts that assistants like Siri and Alexa put forward, and by new product
names like Copilot. In this study, the document rendered differently every
time, and the prompt was fine-tuned in an attempt to avoid particular
interpretations that experienced physicists might in fact prefer. One could
argue that AI-assisted sense-making should be under the control of the user,
and this means any user, having a disability or not. Thus, instead of mangling
the document into a pure presentation format, the source code should be made
available, so AI-tools can render it in ways preferred by the user.

This would mean free publication, not just in the sense of “free beer,” that
is, free-of-charge, but in the sense of “free speech,” to reiterate an old
free software adage GNU Free Software Foundation (Accessed: 2023-06-04).
Publishing the source code of manuscripts would likely have to go along with
adequate licensing terms like Creative Commons Creative Commons (Accessed:
2023-06-04). Publishers and preprint servers could make a corresponding link
available to manuscripts published under those terms.

##  VI Limitations

The exact results of this study are not reproducible, since the GPT-algorithm
is not deterministic. Also, constructing a prompt for GPT is essentially
trial-and-error, and better or more specific prompts than the one used for
this study almost certainly exist. Finally, the study is purely exploratory:
while the document was designed to be demanding in terms of LaTeX structures,
there was no way to even remotely represent the creativity of LaTeX users. For
large documents, GPT might encounter limitations due to its token limit.

##  VII Conclusion

Overall, GPT was found to be a useful tool to generate screen-reader
compatible renderings of LaTeX documents, including document structure,
equations, tables, references, and even figures that are based on textual
source code. The output is compliant with accessibility standards.

As a probabilistic algorithm, the output is not reproducible, and it was found
that each time a document is processed, some elements are translated better or
worse than in other versions. Notably, in situations where GPT is able to
interpret equations based on its training data in physics, it is capable of
generating narratives that are concise and desirable for experts, as well as
more elaborative narratives that are suitable for learners.

## References

  * Borodin et al. (2010) Y. Borodin, J. P. Bigham, G. Dausch, and I. Ramakrishnan, in _Proceedings of the 2010 International Cross Disciplinary Conference on Web Accessibility (W4A)_ (2010), pp. 1–10.
  * Salt Lake Community College (Accessed: 2023-06-04) Salt Lake Community College, _Screen reader demo_ , https://www.youtube.com/watch?v=q_ATY9gimOM (Accessed: 2023-06-04).
  * University of California San Francisco (Accessed: 2023-06-04) University of California San Francisco, _Screen reader demo for digital accessibility_ , https://www.youtube.com/watch?v=dEbl5jvLKGQ (Accessed: 2023-06-04).
  * WWW Consortium (Accessed: 2023-06-03) (W3C) WWW Consortium (W3C), _Web content accessibility guidelines (WCAG) 2.0_ , https://www.w3.org/TR/WCAG20/ (Accessed: 2023-06-03).
  * Nganji (2015) J. T. Nganji, Library & Information Science Research 37, 254 (2015).
  * Petz and Miesenberger (2015) A. Petz and K. Miesenberger, in _AAATE Conf._ (2015), pp. 27–31.
  * Gilligan (2020) J. Gilligan, in _Universal Access in Human-Computer Interaction. Applications and Practice: 14th International Conference, UAHCI 2020, Held as Part of the 22nd HCI International Conference, HCII 2020, Copenhagen, Denmark, July 19–24, 2020, Proceedings, Part II 22_ (Springer, 2020), pp. 184–199.
  * Ahmetovic et al. (2018) D. Ahmetovic, T. Armano, C. Bernareggi, M. Berra, A. Capietto, S. Coriasco, N. Murru, A. Ruighi, and E. Taranto, in _Proceedings of the 20th international ACM SIGACCESS conference on computers and accessibility_ (2018), pp. 352–354.
  * Manzoor et al. (2019) A. Manzoor, S. Arooj, S. Zulfiqar, M. Parvez, S. Shahid, and A. Karim, in _Proceedings of the 2019 CHI conference on human factors in computing systems_ (2019), pp. 1–12.
  * Darvishy (2018) A. Darvishy, in _Computers Helping People with Special Needs: 16th International Conference, ICCHP 2018, Linz, Austria, July 11-13, 2018, Proceedings, Part I 16_ (Springer, 2018), pp. 113–116.
  * Jembu Rajkumar et al. (2020) A. Jembu Rajkumar, J. Lazar, J. B. Jordan, A. Darvishy, and H.-P. Hutter, in _Proceedings of the 53rd Hawaii International Conference on System Sciences (HICSS)_ (2020).
  * Cervone (2012) D. Cervone, Notices of the AMS 59, 312 (2012).
  * Cervone et al. (2016) D. Cervone, P. Krautzberger, and V. Sorge, The Journal on Technology and Persons with Disabilities 4, 167 (2016).
  * Sorge et al. (2014) V. Sorge, C. Chen, T. Raman, and D. Tseng, in _Proceedings of the 11th web for all conference_ (2014), pp. 1–10.
  * Kortemeyer (2023) G. Kortemeyer, Phys. Rev. Phys. Educ. Res. 19, 010132 (2023), URL https://link.aps.org/doi/10.1103/PhysRevPhysEducRes.19.010132.
  * OpenAI (Accessed: 2023-06-03) OpenAI, _GPT Release Notes_ , https://help.openai.com/en/articles/6825453-chatgpt-release-notes (Accessed: 2023-06-03).
  * Fateman (1998) R. Fateman, Journal of Symbolic Computation 25 (1998).
  * Ogawa (2001) A. Ogawa, TUGboat 22, 131 (2001).
  * Walczak (2008) Z. Walczak, TUGboat 20, 176 (2008).
  * Fenn (2006) J. Fenn, The PracTEX Journal 4, 2006 (2006).
  * Iwarsson and Ståhl (2003) S. Iwarsson and A. Ståhl, Disability and rehabilitation 25, 57 (2003).
  * Persson et al. (2015) H. Persson, H. Åhman, A. A. Yngling, and J. Gulliksen, Universal Access in the Information Society 14, 505 (2015).
  * GNU Free Software Foundation (Accessed: 2023-06-04) GNU Free Software Foundation, _What is free software?_ , https://www.gnu.org/philosophy/free-sw.en.html (Accessed: 2023-06-04).
  * Creative Commons (Accessed: 2023-06-04) Creative Commons, _Share your work_ , https://creativecommons.org/share-your-work/ (Accessed: 2023-06-04).


# Structured Memory for Neural Turing Machines

Wei Zhang Yang Yu Bowen Zhou
IBM Watson
<EMAIL_ADDRESS>
Alternative email for Wei Zhang<EMAIL_ADDRESS>
###### Abstract

Neural Turing Machines (NTM) [2] contain memory component that simulates
“working memroy” in the brain to store and retrieve information to ease simple
algorithms learning. So far, only linearly organized memory is proposed, and
during experiments, we observed that the model does not always converge, and
overfits easily when handling certain tasks. We think memory component is key
to some faulty behaviors of NTM, and better organization of memory component
could help fight those problems. In this paper, we propose several different
structures of memory for NTM, and we proved in experiments that two of our
proposed structured-memory NTMs could lead to better convergence, in term of
speed and prediction accuracy on copy task and associative recall task as in
[2].

##  1 Introduction

Memory components for Neural Networks has been recently introduced in Neural
Turing Machines (NTMs) [2], Memory Networks [1], and Dynamic Memory Networks
[3]. The purposes of those memory components are similar, which is to simulate
“working memory” in the brain to store temporary information through time to
be used by attention module for reading and writing. In this paper, our focus
is on NTMs. They are attractive in that memory could be randomly accessed by
controller through blurry “erase” and “write” operations, which well aligns
with Turing Machine operations. When memory size is small, nice convergence of
the NTM model could be frequently observed, although not always. But when
memory size is large, the model struggles to convergence, and sometimes the
test loss jumps drastically in a large range, which is a sign of overfitting,
as was observed in our experiments. We think that the dynamics of memory
contents takes a crucial role in controlling model convergence speed and
quality. Thus, we proposed and experimented different memory structures to
explore if specific memory structure could lead to more stable memory
contents, or say, perform “memory smoothing” so that the memory content
generated after read and write operations does not deviate too far from the
“expected” memory content, so that overfitting of parameters could be in turn
alleviated. We proposed three different architectures, NTM1, NTM2 and NTM3,
which are explained in detail in section 2, and experiments are shown in
section 3.

Figure 1: NTM and NTM variants that use Long short-term memory [5] as
controllers. Note that every module in those modules are updated recurrently
through time using their previous states. NTM1 contains only one write head,
and one of the memory $\mathbf{M}_{h}$ is not written directly by controller,
which is different from $\mathbf{M}_{2}$ in NTM2 that is written both by
$\mathbf{M}_{1}$ and write head simultaneously. NTM3 is different from NTM2 in
that NTM3 write heads takes inputs from two layers. NTM3 could also be
expanded to multiple layers as well.

##  2 Architectures

We show the NTM original architecture introduced by Graves et al. [2] and
three variants NTM1, NTM2 and NTM3 in Figure 1. Details of each model is
explained in a moment. We introduce a notion of Memory visibility: We call
memory “Controlled” if it is modified by controller outputs through write
heads directly, or “Hidden” if not.

NTM1 Compared to NTM, NTM1 has an additional hidden memory $\mathbf{M}_{h}$,
which is not controlled by controller module, but is connected to the
controlled memory $\mathbf{M}_{c}$. The hidden memory accumulates the content
in the controlled memory, so that a type of memory smoothing is performed to
prevent memory from deviating from the “expected content”. Specifically, the
memory content for hidden memory $\mathbf{M}_{h}(t)$ of time $t$ is generated
as:

$\displaystyle write:\quad$
$\displaystyle\mathbf{M}_{c}(t)=h\big{(}\mathbf{M}_{c}(t-1),\mathbf{w}(t-1),\mathbf{c}(t)\big{)}$
$\displaystyle update:\quad$
$\displaystyle\mathbf{M}_{h}(t)=a\mathbf{M}_{h}(t-1)+b\mathbf{M}_{c}(t)$
$\displaystyle read:\quad$
$\displaystyle\mathbf{r}(t)=\mathbf{w_{r}}(t)\mathbf{M}_{h}(t)$

$\mathbf{M}_{c}$ is updated by $t-1$ time write head to generate $t$ time
controlled memory output, which in turn is used to update hidden memory
$\mathbf{M}_{h}$, and then the new hidden memory is used to generate read head
at time $t$. $\textbf{w}(t)$ is write weights, $\textbf{c}(t)$ is the
controller output of time $t$, and $h()$ is the function that updates
controlled memory and write weights that implement “erase and add” operations.
$\mathbf{w_{r}}$ is read weights. $a$ and $b$ are scalar mixture weights,
which could be further extended to tensors. We use scalars in this work. The
read head is reading from $\mathbf{M}_{h}(t)$ instead of $\mathbf{M}(t)$ as is
did in [2].

NTM2 The second architecture NTM2 is similar to NTM1 in that two memory blocks
are used, and they are connected hierarchically. However, the difference from
NTM1 is that hidden memory in NTM2 is no longer hidden from the controller,
but connected to controller outputs through another write head. So two memory
blocks are all controlled memories connecting to two different write heads.
The upper level memory is denoted as $\mathbf{M}_{1}$, and the lower level one
as $\mathbf{M}_{2}$. $\mathbf{M}_{1}$ is modified solely by L1 write head, but
$\mathbf{M}_{2}$ is modified by both $\mathbf{M}_{1}$ contents and L2 write
head. The logic is:

$\displaystyle write:\quad$
$\displaystyle\mathbf{M}_{1}(t),\mathbf{w}_{1}(t)=h\big{(}\mathbf{M}_{1}(t-1),\mathbf{w}_{1}(t-1),\mathbf{c}(t)\big{)}$
$\displaystyle\widetilde{\mathbf{M}}_{2}(t),\mathbf{w}_{2}(t)=h\big{(}\mathbf{M}_{2}(t-1),\mathbf{w}_{2}(t-1),\mathbf{c}(t)\big{)}$
$\displaystyle update:\quad$
$\displaystyle\mathbf{M}_{2}(t)=a\widetilde{\mathbf{M}}_{2}(t)+b\mathbf{M}_{1}(t)$
$\displaystyle read:\quad$
$\displaystyle\mathbf{r}(t)=\mathbf{w_{r}}(t)\mathbf{M}_{2}(t)$

Additionally, $\mathbf{M}_{1}$ and $\mathbf{M}_{2}$ are all generated by the
same head function with same controller input, but with different write
weights. Single read head $\mathbf{r}$ is used, which means the output is only
read from the lowest layer memory ($\mathbf{M}_{2}$ in this case). Note that
the architecture could be easily expanded into multiple layers by increasing
number of heads and memory blocks.

NTM3 The third architecture is significantly different from the previous two.
First, the controller in the model have multiple layers. Second, each layer
output is connecting to a memory by write heads. Different layers of memory
contains different level of transformation of the input. In the case where
multi-layer LSTM is used as NTM controller, output from each layer goes
through the non-linear transformation of write heads, and writes to each
individual memory. Then the deeper level memory is updated by upper level
memory and write head jointly.

$\displaystyle write:\quad$
$\displaystyle\mathbf{M}_{1}(t),\mathbf{w}_{L1}(t)=h\big{(}\mathbf{M}_{1}(t-1),\mathbf{w}_{L1}(t-1),\mathbf{c}_{L1}(t)\big{)}$
$\displaystyle\widetilde{\mathbf{M}}_{2}(t),\mathbf{w}_{L2}(t)=h\big{(}\mathbf{M}_{2}(t-1),\mathbf{w}_{L2}(t-1),\mathbf{c}_{L2}(t)\big{)}$
$\displaystyle update:\quad$
$\displaystyle\mathbf{M}_{2}(t)=a\widetilde{\mathbf{M}}_{2}(t)+b{\mathbf{M}}_{1}(t)$
$\displaystyle read:\quad$
$\displaystyle\mathbf{r}(t)=\mathbf{w_{r}}(t)\mathbf{M}_{2}(t)$

In so doing, the memory blocks receives write operations not only from the
final layer LSTM output, but also from the intermediate layer outputs as well.
The purpose is to smooth the final layer memoroy with intermediate LSTM
outputs. We can see in a moment how those three performs on copy and
associative recall task.

Figure 2: comparison of convergence speed and quality on copy task and
associative recall task. Four figures to the left are all from copy task, and
four on the right are for associative recall task. For all the figures, X-axis
is the number of iterations (scaled by sampling once for every 25 iterations),
and for copy task, Y-axis shows the binary cross entropy loss per item
(sequence of length 8), and in recall task, Y-axis shows log of binary cross
entropy loss. Memory is 128 vectors of length 20, for every memory block shown
in Figure 1.

##  3 Experiments

The experiments is to show the convergence speed and quality of those three
variants, compared to the NTM setting. In theory, the convergence should
happen for every run of every model, which is not the case in practice.
Randomness of parameter initialization might be the reason111We applied the
technique used by https://github.com/kaishengtai/torch-ntm to initialize each
memory slot to define “write/read order” prior. But if model convergences, the
number of iterations used were quite stable across runs. Thus, to make the
evaluation reliable, we repeat experiments at least 5 times for each model and
choose the most frequent circumstance for showing.

The tasks we choose for model testing are copy task and associative recall
task as in [2]. Associative recall task requires the model to target an item
in sequence, and later on shift to the immediate next item to give as an
answer. Copy task requires the model to consecutively output items in original
input order, which requires long-term location based addressing capability. In
each training iteration, we randomly generated each item as a binary vector of
length 8. The number of items is random as well. In recall task, the items,
and number of items to be generated are all chosen at random. All those
randomness is to guarantee that every training iteration uses different
training example, so that overfit to specific data set is no longer an issue,
to guarantee that algorithms could be learned. This is critical to our further
analysis.For all the models, the training criteria is binary cross entropy,
and we use RMSProp [4] for optimization, with learning rate $1E-4$, momentum
$0.9$, and decay $0.95$.

In Figure 2 we show our results on copy and recall respectively. Copy tasks
are four graphs to the left. X-axis shows the number of iteration used
(sampled every 25 iterations), and Y-axis is the binary cross entropy loss of
each iteration. The shown result in each graph is representative among 5 runs,
among which the selected curve is observed most frequently. We can see that
NTM1 and NTM2 shows faster convergence and less outliers above the convergence
range (closely around 0 near X-axis) than NTM or NTM3. The outliers (extremely
high loss) means that the prediction on the item in that iteration is
significantly incorrect, which is a sign of overfitting or underfitting. In
NTM1 and NTM2 runs we see very few outliers, but NTM shows more outliers when
using two read and write heads (the curve with sharp values), or does not
converge as fast when using 1 read and 1 write head (flat curve). This pattern
is consistently observed over 5 runs as well. We can also read out from Figure
“NTM-copy” that using 1 read and 1 write head converges significantly slower
than 2w/r heads. The series of experiments on copy task confirms our
assumption that the introduction of additional memory in NTM1 and NTM2 do help
stabilize the memory component, which in turn leads to better tuning of the
parameters. However, NTM3 does not show nice curves, and produce outlier
almost every 1000 iterations or so. This means that the memory that is
attached to the intermediate layers of LSTM introduces more noise, which is
unexpected. Although less stable, NTM does converge about 500 iterations
faster than NTM1 and NTM2, but we observed the opposite in associative recall
task.

For associative recall, we can see that outliers are produced much more
frequently when loss significantly reduces, and we rarely observe convergence
of original NTM or NTM3. In “NTM3-recall” graph, we show a non-converged run
since it happens frequently for NTM3. But NTM1 and NTM2 converges more
frequently across runs. And NTM2 shows much faster convergence, roughly with
37,000 iterations, compared to 50,000 for NTM or NTM1. Moreover, NTM1 and NTM2
generate less outliers than NTM. This means that, the prediction accuracy for
NTM1 and NTM2 will be higher than NTM, since more training examples are
correctly predicted than NTM. And, NTM1 and NTM2 will have higher probability
to be a non-overfitting model than NTM. Unfortunately, NTM3 model does not
converge as frequent as NTM1 and NTM2, which aligns with the observation in
copy task about the difference of those models.

##  4 Conclusion

This paper discussed three new structured memory architectures for Neural
Turing Machines, and showed that organizing memory blocks in a proper
hierarchical manner could alleviate overfitting and sometimes increase
predictive accuracy compared to NTM.

##  5 Future work

In the future we would also try NTM1 NTM2 on data sets that require more
complex reasoning. We tested NTM on a synthetic QA data set proposed in [1],
and observed the instability in convergence. We would try NTM1 and NTM2 on the
same data set.

## References

[1] Jason Weston, Sumit Chopra, & Antoine Bordes. Memory Networks.
International Conference on Representation Learning, 2015

[2] Alex Graves, Greg Wayne, & Ivo Danihelka. Neural Turing Machines. arXiv
preprint arXiv:1410.5401. 2014

[3] Ankit Kumar, Ozan Irsoy, Jonathan Su, James Bradbury, Robert English,
Brian Pierce, Peter Ondruska, Ishaan Gulrajani, & Richard Socher. Ask Me
Anything: Dynamic Memory Networks for Natural Language Processing. arXiv
preprint arXiv:1506.07285. 2015

[4] Tijmen Tieleman, & Geoffrey Hinton. ”Lecture 6.5-rmsprop: Divide the
gradient by a running average of its recent magnitude.” COURSERA: Neural
Networks for Machine Learning 4\. 2012

[5] Sepp Hochreiter, & Jürgen Schmidhuber. Long short-term memory. Neural
computation, no. 8: 1735-1780. 1997


It then easily follows that if we let $\mathbfcal{Q}^{\mathbf{A}}$,
$\mathbfcal{Q}^{\mathbf{B}}$ be the partitions of $\mathcal{C}_{\mathbf{A}}$,
$\mathcal{C}_{\mathbf{B}}$ respectively given by assigning two edges to the
same partition class if the partition classes of their vertices coincide then
$(\mathbfcal{P}^{\mathbf{A}},\mathbfcal{Q}^{\mathbf{A}})$ and
$(\mathbfcal{P}^{\mathbf{B}},\mathbfcal{Q}^{\mathbf{B}})$ define a common
equitable partition of $\mathbf{A}$ and $\mathbf{B}$.

###  7.4 Proof of Theorem 15

In order to prove Theorem 15, it will be useful to introduce a simple
combinatorial game, which is a variant of the Ehrenfeucht-Fraïssé games [37,
34], that characterizes equivalence in $\mathscr{C}^{k}$.

The bijective $k$-pebble game is played by two players, $\mathrm{Spoiler}$ and
$\mathrm{Duplicator}$, by placing $k$ pairs of pebbles on a pair of structures
$\mathbf{A}$, $\mathbf{B}$ of the same size (if $\mathbf{A}$ and $\mathbf{B}$
have different sizes, $\mathrm{Spoiler}$ is always assumed to win the game).
We shall denote each pair of pebbles by $(x_{i},y_{i})$, where $x_{i}$ belongs
to $\mathrm{Spoiler}$ and $y_{i}$ belongs to $\mathrm{Duplicator}$. At every
round, $\mathrm{Spoiler}$ picks up a pebble $x_{i}$, and $\mathrm{Duplicator}$
picks up the corresponding pebble $y_{i}$. At this point,
$\mathrm{Duplicator}$ chooses a bijection $f$ between $A$ and $B$. Then,
$\mathrm{Spoiler}$ places a pebble $x_{i}$ on an element $a\in A$, and
$\mathrm{Duplicator}$ must place the corresponding pebble $y_{i}$ on $f(a)\in
B$.

$\mathrm{Duplicator}$ wins a round of the bijective $k$-pebble game if the
partial map defined by $x_{i}\mapsto y_{i}$ (i.e., where the element of $A$
under pebble $x_{i}$ is mapped to the element of $B$ under pebble $y_{i}$) is
a partial isomorphism between (the respective vertex-induced substructures of)
$\mathbf{A}$ and $\mathbf{B}$. Otherwise, $\mathrm{Spoiler}$ wins the round.
We say that $\mathrm{Duplicator}$ has a winning strategy for the bijective
$k$-pebble game if she has a strategy to win every round of the game (note
that the game has infinitely many rounds).

It is a well-known result of Hella [46] (see also [43, 1]) that two structures
$\mathbf{A}$ and $\mathbf{B}$ satisfy the same formulae in the logic
$\mathscr{C}^{k}$ if and only if Duplicator has a winning strategy for the
bijective $k$-pebble game on $\mathbf{A}$, $\mathbf{B}$.

On the other hand, the extension of the Lovász-type result of Dvořák from
graphs to relational structures (i.e., the equivalence of (2) and (3) in
Theorem 15) was shown by Dawar, Jakl and Reggio [31] using a categorical
approach based on the game comonads of Abramsky, Dawar and Wang [1].
Additionally, an independent proof of this result was given by Butti and
Dalmau [18] using purely combinatorial techniques.

Therefore, all together, we have the following result.

######  Theorem 17.

Let $r$ be the maximum arity among all relations in $\sigma$ and assume that
$r\leq k$. Then for every pair of structures $\mathbf{A}$, $\mathbf{B}$ the
following are equivalent:

  1. 1.

$\mathbf{A}\equiv_{k}\mathbf{B}$;

  2. 2.

$\hom(\mathbf{X};\mathbf{A})=\hom(\mathbf{X};\mathbf{B})$ for every
$\sigma$-structure $\mathbf{X}$ of treewidth $<k$;

  3. 3.

$\mathbf{A}$ and $\mathbf{B}$ satisfy the same formulae in the logic
$\mathscr{C}^{k}$.

  4. 4.

Duplicator has a winning strategy for the bijective $k$-pebble game on
$\mathbf{A}$, $\mathbf{B}$.

###### Proof.

By virtue of the above discussion, it only remains to prove the equivalence of
(1) and (4). First, let us make the definition of winning strategy a little
more formal.

For a $j$-tuple $\textbf{d}=(d_{1},\ldots,d_{j})$, an element $d$, and
$i\in[j+1]$, define
$\textbf{d}^{i}_{d}=(d_{1},\ldots,d_{i-1},d,d_{i},\ldots,d_{j})$.
Additionally, for $j\in[k]$ and $i\in[j]$, define
$\textbf{i}(j,i)=(1,\ldots,i-1,i+1,\ldots,j)$. Then, a winning strategy for
the bijective $k$-pebble game is a non-empty set $W\subseteq\cup_{0\leq j\leq
k}(A^{j}\times B^{j})$ such that, for every $\textbf{a}=(a_{1},\ldots,a_{j})$
and $\textbf{b}=(b_{1},\ldots,b_{j})$ with $(\textbf{a},\textbf{b})\in W$, the
following conditions hold:

  1. (i)

The partial map given by $a_{i}\mapsto b_{i}$, $i\in[j]$ is a partial
isomorphism between $\mathbf{A}$ and $\mathbf{B}$;

  2. (ii)

If $j\geq 1$, then
$(\pi_{\textbf{i}(j,i)}\textbf{a},\pi_{\textbf{i}(j,i)}\textbf{b})\in W$ for
every $i\in[j]$;

  3. (iii)

If $j<k$, there exists a bijection $f:A\to B$ such that
$(\textbf{a}^{i}_{a},\textbf{b}^{i}_{f(a)})\in W$ for every $a\in A$ and every
$i\in[j+1]$.

In what follows, we will assume without loss of generality that $A$ and $B$
are disjoint, so when we talk about the union of $\mathbf{A}$ and
$\mathbf{B}$, we will always mean the disjoint union.

$(\ref{item:eqwl})\Rightarrow(\ref{item:pebble})$. It will be convenient to
assume that $A^{*}_{k}$ and $B^{*}_{k}$ additionally include a tuple of null
arity (this will correspond to the configuration where no pebbles are placed
yet). Let $(\mathbfcal{P},\mathbfcal{Q})$ be an equitable partition of
$\mathbf{A}^{*}_{k}\cup\mathbf{B}^{*}_{k}$. A winning strategy $W$ for
$\mathrm{Duplicator}$ can be obtained as the set of all pairs
$(\textbf{a},\textbf{b})\in A^{*}_{k}\times B^{*}_{k}$ such that a and b
belong to the same class of $\mathbfcal{P}$.

To see that $W$ is a winning strategy, first observe that, by the definition
of the transformation $*_{k}$, any two tuples of
$\mathbf{A}^{*}_{k}\cup\mathbf{B}^{*}_{k}$ in the same partition class of
$\mathbfcal{P}$ must have the same isomorphism type in the original structure
$\mathbf{A}\cup\mathbf{B}$. It follows that for all elements
$(\textbf{a},\textbf{b})\in W$, the map $a_{i}\mapsto b_{i}$ is a partial
isomorphism from $\mathbf{A}$ to $\mathbf{B}$, hence $W$ satisfies condition
$(\ref{strat:1})$.

Second, it is easy to see that $W$ satisfies condition (ii), since for each
$j\in[k]$ and $\textbf{d}\in A^{j}\cup B^{j}$, d has a unique out-neighbor of
type $T_{j,\textbf{i}(j,i)}$, which is precisely
$\pi_{\textbf{i}(j,i)}\textbf{d}$. Therefore, for every
$(\textbf{a},\textbf{b})\in W$, $\pi_{\textbf{i}(j,i)}\textbf{a}$ and
$\pi_{\textbf{i}(j,i)}\textbf{b}$ must belong to the same class of
$\mathbfcal{P}$ and hence
$(\pi_{\textbf{i}(j,i)}\textbf{a},\pi_{\textbf{i}(j,i)}\textbf{b})\in W$.

Finally, to see that $W$ satisfies condition (iii), for each
$(\textbf{a},\textbf{b})\in W$ of arity $j<k$ we need to find a bijection
$f:A\to B$ in such a way that for every $a\in A$ and every $i\in[j+1]$, the
tuples $\textbf{a}^{i}_{a}$ and $\textbf{b}^{i}_{f(a)}$ belong to the same
partition class of $\mathbfcal{P}$. Since a and b belong to the same class of
$\mathbfcal{P}$ and $(\mathbfcal{P},\mathbfcal{Q})$ is equitable, there is a
one-to-one correspondence that respects the partition between the constraints
that a and b participate in; in particular, this holds for the constraints of
type $T_{j+1,\textbf{i}(j+1,i)}$. Since for each $a\in A$ and $b\in B$,
$T_{j+1,\textbf{i}(j+1,i)}(\textbf{a}^{i}_{a},\textbf{a})\in\mathcal{C}_{\mathbf{A}^{*}_{k}}$
and
$T_{j+1,\textbf{i}(j+1,i)}(\textbf{b}^{i}_{b},\textbf{b})\in\mathcal{C}_{\mathbf{B}^{*}_{k}}$,
there is a one-to-one partition-preserving correspondence between tuples
$\textbf{a}^{i}_{a}\in A^{j+1}$, $\textbf{b}^{i}_{b}\in B^{j+1}$ that induces
an appropriate bijection between $A$ and $B$. In particular, the unary
constraints of $\mathbf{A}^{*}_{k}$, $\mathbf{B}^{*}_{k}$ of the form
$T_{j+1,S}$, $S\subseteq[j+1]$ imply that $f(a_{i})=b_{i}$ for each $i\in[j]$.

$(\ref{item:pebble})\Rightarrow(\ref{item:eqwl})$. We begin with the simple
observation that, since $\operatorname{ar}(R)\leq k$ for all $R\in\sigma$, the
transformation $*_{k}$ can be substantially simplified without its basic
properties being affected (particularly, Lemma 12 and the definition of
$\equiv_{k}$ remain unchanged). Specifically, this simplification consists of
the following changes:

  1. 1.

For each $R\in\sigma$, identify $R(\textbf{a})$ with a, so the universe of
$\mathbf{A}^{*}_{k}$ is just $\cup_{j\leq k}A^{j}$;

  2. 2.

Remove from $\sigma^{*}_{k}$ all binary relation symbols of the form
$R_{\textbf{i}}$ (since for all $\textbf{i}\in[\operatorname{ar}(R)]^{j}$ and
all $\textbf{a}\in R^{\mathbf{A}}$,
$R_{\textbf{i}}(\textbf{a},\pi_{\textbf{i}}\textbf{a})$ is equivalent to
$T_{\operatorname{ar}(R),\textbf{i}}(\textbf{a},\pi_{\textbf{i}}\textbf{a})\land
R_{\emptyset}(\textbf{a})$);

  3. 3.

Remove from $\sigma^{*}_{k}$ all unary relation symbols of the form $R_{S}$
for all $S\neq\emptyset$ (since for all $S\subseteq[\operatorname{ar}(R)]$ and
all $\textbf{a}\in R^{\mathbf{A}}$,
$R_{S}(\textbf{a})=T_{\operatorname{ar}(R),S}(\textbf{a})\land
R_{\emptyset}(\textbf{a})$);

  4. 4.

Remove from $\sigma^{*}_{k}$ all binary relation symbols of the form
$T_{j,\textbf{i}}$ whenever $|[j]\setminus\\{\textbf{i}\\}|>1$. This is
because, if $|[j]\setminus\\{\textbf{i}\\}|>1$, then there exists a sequence
$\textbf{i}_{1}\in[j_{0}]^{j_{1}}$, $\textbf{i}_{2}\in[j_{1}]^{j_{2}}$,
$\ldots\ $, $\textbf{i}_{m}\in[j_{m-1}]^{j_{m}}$ with $j_{0}=j$ and $m\geq 2$
such that $|[j_{i-1}]\setminus\\{\textbf{i}_{i}\\}|\leq 1$ for each $i\in[m]$,
and
$\pi_{\textbf{i}_{m}}\ldots\pi_{\textbf{i}_{2}}\pi_{\textbf{i}_{1}}=\pi_{\textbf{i}}$.
Then, we have that

$\displaystyle T_{j,\textbf{i}}(\textbf{a},\pi_{\textbf{i}}\textbf{a})$
$\displaystyle=T_{j,\textbf{i}_{1}}(\textbf{a},\pi_{\textbf{i}_{1}}\textbf{a})\land
T_{j_{1},\textbf{i}_{2}}(\pi_{\textbf{i}_{1}}\textbf{a},\pi_{\textbf{i}_{2}}\pi_{\textbf{i}_{1}}\textbf{a})\land\ldots$
$\displaystyle\ldots\land
T_{j_{m-1},\textbf{i}_{m}}(\pi_{\textbf{i}_{m-1}}\ldots\pi_{\textbf{i}_{1}}\textbf{a},\pi_{\textbf{i}_{m}}\pi_{\textbf{i}_{m-1}}\ldots\pi_{\textbf{i}_{1}}\textbf{a}).$

Now, assume that $\mathrm{Duplicator}$ has a winning strategy for the
bijective $k$-pebble game. We need to find an equitable partition of
$\mathbf{A}^{*}_{k}\cup\mathbf{B}^{*}_{k}$ such that each class of the
partition has the same number of elements from $A^{*}_{k}$ and $B^{*}_{k}$.
Since $\mathbf{A}^{*}_{k}\cup\mathbf{B}^{*}_{k}$ is a (vertex- and edge-
coloured) digraph, it is enough to define a partition
$\mathbfcal{P}=\\{\mathcal{P}_{i}\mid i\in I\\}$ of $A^{*}_{k}\cup B^{*}_{k}$
where any two elements in the same partition class of $\mathbfcal{P}$ are
subject to the same unary constraints, and have the same number of in- and
out-neighbors in any other class of $\mathbfcal{P}$ connected by an edge of
any given colour.

Let $W$ be a winning strategy for $\mathrm{Duplicator}$. We define the set
$\overline{W}$ to contain precisely all the pairs
$(\textbf{a},\textbf{b})\in\cup_{j\leq k}A^{j}\times B^{j}$ such that there
exist $\textbf{a}_{0},\textbf{a}_{1},\ldots,\textbf{a}_{n}\in A^{j}$ and
$\textbf{b}_{0},\textbf{b}_{1},\ldots,\textbf{b}_{n}\in B^{j}$ such that
$\textbf{a}_{0}=\textbf{a}$, $\textbf{b}_{n}=\textbf{b}$,
$(\textbf{a}_{0},\textbf{b}_{0})\in W$, and for each $i\in[n]$, the pairs
$(\textbf{a}_{i},\textbf{b}_{i-1})$ and $(\textbf{a}_{i},\textbf{b}_{i})$ both
belong to $W$. That is, we think of $\overline{W}$ as the closure of $W$ under
odd chains (see Figure 3).

$\textbf{a}_{0}$$\textbf{b}_{0}$$\textbf{a}_{1}$$\textbf{b}_{1}$$\ldots$$\ldots$$\textbf{a}_{n}$$\textbf{b}_{n}$
Figure 3: A representation of the closure of $\overline{W}$ under a chain of
length $2n+1$ in $W$. Pairs in $W$ are represented as solid black arrows and
the added pairs in $\overline{W}$ are represented as dashed gray arrows.

We shall show that $\overline{W}$ is also a winning strategy for the bijective
$k$-pebble game over $\mathbf{A}$, $\mathbf{B}$. Conditions (i) and (ii) are
easily verified by using the corresponding conditions for $W$, plus the fact
that isomorphisms compose. For (iii), let
$(\textbf{a},\textbf{b})\in\overline{W}$ have arity $j$ and let
$\textbf{a}_{0},\textbf{b}_{0},\ldots,\textbf{a}_{n},\textbf{b}_{n}$ be the
odd chain witnessing this. Let $f_{i,i}$, $f_{i+1,i}$ be the bijections given
by condition (iii) of $W$ for $(\textbf{a}_{i},\textbf{b}_{i})$,
$(\textbf{a}_{i+1},\textbf{b}_{i})$ respectively. We claim that
$f:=f_{n,n}\circ f^{-1}_{n,n-1}\circ\ldots\circ f_{1,1}\circ f_{1,0}^{-1}\circ
f_{0,0}$ witnesses that (iii) is satisfied for
$(\textbf{a}_{0},\textbf{b}_{n})=(\textbf{a},\textbf{b})$ in $\overline{W}$.
Recall that for a $j$-tuple d, an element $d$, and $l\in[j+1]$, we denote by
$\textbf{d}^{l}_{d}$ the tuple obtained from d by adding $d$ to d before the
$l^{\textnormal{th}}$ coordinate. By condition (iii) for $W$, we have that for
every $l\in[j]$, every $i=0,\ldots,n$, and every $\alpha_{i}\in A$,

$((\textbf{a}_{i})^{l}_{\alpha_{i}},(\textbf{b}_{i})^{l}_{f_{i,i}(\alpha_{i})})\in
W,$

and similarly for every $l\in[j]$, every $i=0,\ldots,n-1$, and every
$\beta_{i}\in A$,

$((\textbf{a}_{i+1})^{l}_{f^{-1}_{i+1,i}(\beta_{i})},(\textbf{b}_{i})^{l}_{\beta_{i}})\in
W.$

Therefore, if for $i=0,\ldots,n-1$ we choose

$\beta_{i}=f_{i,i}(\alpha_{i}),\quad\alpha_{i+1}=f_{i+1,i}^{-1}(\beta_{i})$

we get that for every choice of $\alpha_{0}\in A$,
$((\textbf{a})^{l}_{\alpha_{0}},(\textbf{b})^{l}_{f(\alpha_{0})})\in\overline{W}$
as required. Hence, $\overline{W}$ is a winning strategy.

The partition $\mathbfcal{P}$ of $A^{*}_{k}\cup B^{*}_{k}$ is defined by the
transitive closure of $\overline{W}$. That is, $\textbf{a}\in A^{j}$ and
$\textbf{b}\in B^{j}$ are in the same set of $\mathbfcal{P}$ if
$(\textbf{a},\textbf{b})\in\overline{W}$; any two
$\textbf{a},\textbf{a}^{\prime}\in A^{j}$ are in the same set of
$\mathbfcal{P}$ if there exists some b such that
$(\textbf{a},\textbf{b}),(\textbf{a}^{\prime},\textbf{b})\in\overline{W}$; and
similarly for any two $\textbf{b},\textbf{b}^{\prime}\in B^{j}$. In
particular, there is a partial isomorphism between any two tuples
$\textbf{d},\textbf{d}^{\prime}$ in the same class of $\mathbfcal{P}$. Recall
that, since the universe of $\mathbf{A}^{*}_{k}$ is collapsed to just
$\cup_{j\leq k}A^{j}$ (see item (1) above), we do not need to worry about
defining a partition of
$\mathcal{C}_{\mathbf{A}}\cup\mathcal{C}_{\mathbf{B}}$. It remains to show
that the partition $\mathbfcal{P}$ is equitable.

It is easily seen that any two tuples in the same class of $\mathbfcal{P}$ are
subject to the same unary constraints. In particular, if there is a partial
isomorphism between d and $\textbf{d}^{\prime}$, then they are subject to the
same relations in $\mathbf{A}\cup\mathbf{B}$ (accounting for unary constraints
of the type $R_{\emptyset}$, $R\in\sigma$) and they have the same repetition
structure (accounting for unary constraints of the type $T_{j,S}$ for $j\leq
k$, $S\subseteq[j]$).

Now we are left to deal with the binary constraints of type $T_{j,\textbf{i}}$
for $j,j^{\prime}\leq k$ and $\textbf{i}\in[j]^{j^{\prime}}$. It is easy to
see that any two tuples of arity $j$ in the same class of $\mathbfcal{P}$ have
the same number of outgoing edges of type $T_{j,\textbf{i}}$ that are incident
to each other class of $\mathbfcal{P}$, since for any $j,j^{\prime}\in k$, any
two isomorphic tuples $\textbf{d},\textbf{d}^{\prime}\in A^{j}\cup B^{j}$, and
any $\textbf{i}\in[j]^{j^{\prime}}$, $\pi_{\textbf{i}}\textbf{d}$ and
$\pi_{\textbf{i}}\textbf{d}^{\prime}$ will still be isomorphic (equivalently,
any winning strategy for the bijective $k$-pebble game is trivially closed
under removing pairs of pebbles, under adding pairs of pebbles on already
pebbled elements, and under permuting pairs of pebbles).

Finally, let us deal with the incoming edges of type $T_{j,\textbf{i}}$. For
simplicity, let us start by considering two elements of the same class of
$\mathbfcal{P}$ belonging to different structures $\mathbf{A}$, $\mathbf{B}$.
That is, let $\textbf{a}\in A^{j^{\prime}}$, $\textbf{b}\in B^{j^{\prime}}$
for some $j^{\prime}\leq k$, $(\textbf{a},\textbf{b})\in\overline{W}$, and let
$j\leq k$ and $\textbf{i}\in[j]^{j^{\prime}}$. For each partition class
$\mathcal{P}_{l}$ of $\mathbfcal{P}$, we need to show that a and b have the
same number of incoming edges labelled $T_{j,\textbf{i}}$ from
$\mathcal{P}_{l}$.

Notice that, if $\\{\textbf{i}\\}=[j]$, then there is nothing to prove (since
as we pointed out above, the winning strategy is trivially closed under adding
pebbles on already pebbled elements and permuting pairs of pebbles), so we may
assume that $\\{\textbf{i}\\}\subsetneq[j]$, and for the same reasons, we may
assume that i has no repetitions and that its entries are in increasing order.
Moreover, from item (4) above, we have that
$|[j]\setminus\\{\textbf{i}\\}|=1$. All together then we may assume that
$j^{\prime}=j-1$ and $\textbf{i}=\textbf{i}(j,i)$ for some $i\in[j]$.
Therefore, for any $j^{\prime}$-tuple d,
$\pi_{\textbf{i}}\textbf{d}^{i}_{d}=\textbf{d}$.

Since $(\textbf{a},\textbf{b})\in\overline{W}$, there exists a bijection
$f:A\to B$ such that, for each $a\in A$,
$(\textbf{a}^{i}_{a},\textbf{b}^{i}_{f(a)})\in\overline{W}$. Hence, for each
$a\in A$, $\textbf{a}^{i}_{a}$ and $\textbf{b}^{i}_{f(a)}$ belong to the same
class of $\mathbfcal{P}$. By the definition of $T_{j,\textbf{i}}$, this means
that a and b have the same number of incoming edges labelled
$T_{j,\textbf{i}}$ from each class of $\mathbfcal{P}$. Since
$|A^{*}_{k}|=|B^{*}_{k}|$ and $\mathbf{A}^{*}_{k}$, $\mathbf{B}^{*}_{k}$ are
disjoint components of $\mathbf{A}^{*}_{k}\cup\mathbf{B}^{*}_{k}$, this also
implies that any partition class of $\mathbfcal{P}$ contains the same number
of elements from $A^{*}_{k}$ and $B^{*}_{k}$.

Now we still need to check that this condition holds for any two elements of
the same class of $\mathbfcal{P}$ that belong to the same structure, say
$\mathbf{A}$. But this is immediate since if
$\textbf{a},\textbf{a}^{\prime}\in A^{j^{\prime}}$ belong to the same class of
$\mathbfcal{P}$, then there exists $\textbf{b}\in B^{j^{\prime}}$ such that
$(\textbf{a},\textbf{b})$ and $(\textbf{a}^{\prime},\textbf{b})$ belong to
$\overline{W}$, and since both a and b and $\textbf{a}^{\prime}$ and b have
the same number of incoming edges labelled $T_{j,\textbf{i}}$ from each class
of $\mathbfcal{P}$, the same must hold for a and $\textbf{a}^{\prime}$. It
follows that $\mathbfcal{P}$ is equitable. ∎

## References

  * [1] Samson Abramsky, Anuj Dawar, and Pengming Wang.  The pebbling comonad in finite model theory.  In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1–12. IEEE Computer Society, 2017.
  * [2] Albert Atserias and Víctor Dalmau.  Promise Constraint Satisfaction and Width.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1129–1153. SIAM, 2022.
  * [3] Albert Atserias and Elitza Maneva.  Sherali–Adams Relaxations and Indistinguishability in Counting Logics.  SIAM Journal on Computing, 42(1):112–137, 2013.
  * [4] Per Austrin, Venkatesan Guruswami, and Johan Håstad.  $(2+\epsilon)$-Sat Is NP-hard.  SIAM J. Comput., 46(5):1554–1573, 2017.
  * [5] László Babai.  Graph Isomorphism in Quasipolynomial Time [Extended Abstract].  In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, page 684–697, New York, NY, USA, 2016. Association for Computing Machinery.
  * [6] László Babai, Paul Erdős, and Stanley M. Selkow.  Random Graph Isomorphism.  SIAM J. Comput., 9(3):628–635, 1980.
  * [7] László Babai and Ludek Kucera.  Canonical Labelling of Graphs in Linear Average Time.  In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979, pages 39–46. IEEE Computer Society, 1979.
  * [8] Libor Barto.  The collapse of the bounded width hierarchy.  Journal of Logic and Computation, 26(3):923–943, 2016.
  * [9] Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal.  Algebraic Approach to Promise Constraint Satisfaction.  J. ACM, 68(4):28:1–28:66, 2021.
  * [10] Libor Barto and Silvia Butti.  Weisfeiler-Leman Invariant Promise Valued CSPs.  In Christine Solnon, editor, 28th International Conference on Principles and Practice of Constraint Programming, CP 2022, July 31 to August 8, 2022, Haifa, Israel, volume 235 of LIPIcs, pages 4:1–4:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [11] Libor Barto, Silvia Butti, Alexandr Kazda, Caterina Viola, and Stanislav Živný.  Algebraic Approach to Approximation.  CoRR, abs/2401.15186, 2024.
  * [12] Libor Barto and Marcin Kozik.  Constraint Satisfaction Problems Solvable by Local Consistency Methods.  J. ACM, 61(1):3:1–3:19, 2014.
  * [13] Joshua Brakensiek and Venkatesan Guruswami.  Symmetric Polymorphisms and Efficient Decidability of Promise CSPs.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 297–304. SIAM, 2020.
  * [14] Joshua Brakensiek and Venkatesan Guruswami.  Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.  SIAM J. Comput., 50(6):1663–1700, 2021.
  * [15] Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný.  The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.  SIAM J. Comput., 49(6):1232–1248, 2020.
  * [16] A. A. Bulatov.  A Dichotomy Theorem for Nonuniform CSPs.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319–330, Oct 2017.
  * [17] Silvia Butti.  Symmetries in constraint satisfaction: Weisfeiler-Leman invariance and promise problems.  PhD thesis, Universitat Pompeu Fabra, 2022.
  * [18] Silvia Butti and Víctor Dalmau.  Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem.  In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia, volume 202 of LIPIcs, pages 27:1–27:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [19] Silvia Butti and Víctor Dalmau.  The Complexity of the Distributed Constraint Satisfaction Problem.  Theory of Computing Systems, 2022.
  * [20] Jin-yi Cai, Martin Fürer, and Neil Immerman.  An optimal lower bound on the number of variables for graph identifications.  Comb., 12(4):389–410, 1992.
  * [21] Clément Carbonnel, Miguel Romero, and Stanislav Živný.  The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side.  SIAM Journal on Computing, 51(1):19–69, 2022.
  * [22] Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer.  Approximate Constraint Satisfaction Requires Large LP Relaxations.  In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 350–359. IEEE Computer Society, 2013.
  * [23] Lorenzo Ciardo and Stanislav Živný.  Approximate Graph Colouring and Crystals.  In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 2256–2267. SIAM, 2023.
  * [24] Lorenzo Ciardo and Stanislav Živný.  Approximate Graph Colouring and the Hollow Shadow.  In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 623–631. ACM, 2023.
  * [25] Lorenzo Ciardo and Stanislav Živný.  Hierarchies of Minion Tests for PCSPs through Tensors.  In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 568–580. SIAM, 2023.
  * [26] David A. Cohen, Martin C. Cooper, Páidí Creed, Peter G. Jeavons, and Stanislav Živný.  An Algebraic Theory of Complexity for Discrete Optimization.  SIAM J. Comput., 42(5):1915–1939, 2013.
  * [27] David A. Cohen, Martin C. Cooper, and Peter Jeavons.  An Algebraic Characterisation of Complexity for Valued Constraint.  In Frédéric Benhamou, editor, Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006, Proceedings, volume 4204 of Lecture Notes in Computer Science, pages 107–121. Springer, 2006.
  * [28] Víctor Dalmau and Andrei A. Krokhin.  Robust Satisfiability for CSPs: Hardness and Algorithmic Results.  ACM Trans. Comput. Theory, 5(4):15:1–15:25, 2013.
  * [29] Víctor Dalmau, Andrei A. Krokhin, and Rajsekar Manokaran.  Towards a characterization of constant-factor approximable finite-valued CSPs.  J. Comput. Syst. Sci., 97:14–27, 2018.
  * [30] Víctor Dalmau and Jakub Opršal.  Local consistency as a reduction between constraint satisfaction problems.  CoRR, abs/2301.05084, 2023.
  * [31] Anuj Dawar, Tomás Jakl, and Luca Reggio.  Lovász-type theorems and game comonads.  In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–13. IEEE, 2021.
  * [32] Holger Dell, Martin Grohe, and Gaurav Rattan.  Lovász Meets Weisfeiler and Leman.  In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 40:1–40:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [33] Zdeněk Dvořák.  On recognizing graphs by numbers of homomorphisms.  J. Graph Theory, 64(4):330–342, 2010.
  * [34] Andrzej Ehrenfeucht.  An application of games to the completeness problem for formalized theories.  Fundamenta Mathematicae, 49(2):129–141, 1961.
  * [35] Tomás Feder and Moshe Y Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory.  SIAM Journal on Computing, 28(1):57–104, 1998.
  * [36] Ferdinando Fioretto, Enrico Pontelli, and William Yeoh.  Distributed Constraint Optimization Problems and Applications: A Survey.  J. Artif. Int. Res., 61(1):623–698, January 2018.
  * [37] Roland Fraïssé.  Sur quelques classifications des systèmes de relations.  Thèses présentées à la Faculté des Sciences de l’Université de Paris. impr. Durand, 1955.
  * [38] M. R. Garey and D. S. Johnson.  The Complexity of Near-Optimal Graph Coloring.  J. ACM, 23(1):43–49, jan 1976.
  * [39] Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani.  Optimal Sherali-Adams Gaps from Pairwise Independence.  In Irit Dinur, Klaus Jansen, Joseph Naor, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, volume 5687 of Lecture Notes in Computer Science, pages 125–139. Springer, 2009.
  * [40] Mrinalkanti Ghosh and Madhur Tulsiani.  From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems.  Theory Comput., 14(1):1–33, 2018.
  * [41] Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer.  Color refinement and its applications.  Van den Broeck, G.; Kersting, K.; Natarajan, S, 2017.
  * [42] Martin Grohe and Daniel Neuen.  Recent advances on the graph isomorphism problem.  In Konrad K. Dabrowski, Maximilien Gadouleau, Nicholas Georgiou, Matthew Johnson, George B. Mertzios, and Daniël Paulusma, editors, Surveys in Combinatorics, 2021: Invited lectures from the 28th British Combinatorial Conference, Durham, UK, July 5-9, 2021, pages 187–234. Cambridge University Press, 2021.
  * [43] Martin Grohe and Martin Otto.  Pebble Games and linear equations.  J. Symb. Log., 80(3):797–844, 2015.
  * [44] Martin Grohe and Pascal Schweitzer.  The graph isomorphism problem.  Commun. ACM, 63(11):128–134, 2020.
  * [45] Pavol Hell and Jaroslav Nešetřil.  Graphs and Homomorphisms.  Oxford University Press, 2004.
  * [46] Lauri Hella.  Logical hierarchies in PTIME.  Inf. Comput., 129(1):1–19, 1996.
  * [47] Neil Immerman and Eric Lander.  Describing Graphs: A First-Order Approach to Graph Canonization, pages 59–81.  Springer New York, New York, NY, 1990.
  * [48] Alexander Kazda.  Minion homomorphisms give reductions between promise valued CSPs.  Unpublished manuscript, 2021.
  * [49] Sandra Kiefer.  The Weisfeiler-Leman algorithm: an exploration of its power.  ACM SIGLOG News, 7(3):5–27, 2020.
  * [50] Vladimir Kolmogorov.  The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization.  In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 625–636. Springer, 2013.
  * [51] Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolínek.  The Complexity of General-Valued CSPs.  SIAM J. Comput., 46(3):1087–1110, 2017.
  * [52] Vladimir Kolmogorov, Johan Thapper, and Stanislav Živný.  The Power of Linear Programming for General-Valued CSPs.  SIAM J. Comput., 44(1):1–36, 2015.
  * [53] Marcin Kozik and Joanna Ochremiak.  Algebraic Properties of Valued Constraint Satisfaction Problem.  In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 846–858. Springer, 2015.
  * [54] Andrei Krokhin and Stanislav Živný.  The Complexity of Valued CSPs.  In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 233–266. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017.
  * [55] Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, and Nisheeth K. Vishnoi.  On LP-Based Approximability for Strict CSPs.  In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1560–1573. SIAM, 2011.
  * [56] Gábor Kun.  Constraints, MMSNP and expander relational structures.  Comb., 33(3):335–347, 2013.
  * [57] Gabor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou.  Linear Programming, Width-1 CSPs, and Robust Satisfaction.  In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, page 484–495, New York, NY, USA, 2012. Association for Computing Machinery.
  * [58] Benoît Larose, Cynthia Loten, and Claude Tardif.  A Characterisation of First-Order Constraint Satisfaction Problems.  Log. Methods Comput. Sci., 3(4), 2007.
  * [59] Frank Thomson Leighton.  Finite common coverings of graphs.  Journal of Combinatorial Theory, Series B, 33(3):231 – 238, 1982.
  * [60] AA Leman and B Weisfeiler.  A reduction of a graph to a canonical form and an algebra arising during this reduction.  Nauchno-Technicheskaya Informatsiya, 2(9):12–16, 1968.
  * [61] László Lovász.  Operations with structures.  Acta Mathematica Academiae Scientiarum Hungarica, 18(3-4):321–328, 1967.
  * [62] László Lovász and Alexander Schrijver.  Cones of Matrices and Set-Functions and 0-1 Optimization.  SIAM J. Optim., 1(2):166–190, 1991.
  * [63] Peter Malkin.  Sherali–Adams relaxations of graph isomorphism polytopes.  Discrete Optimization, 12:73–97, 2014.
  * [64] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten M. Borgwardt.  Weisfeiler and Leman go Machine Learning: The Story so far.  CoRR, abs/2112.09992, 2021.
  * [65] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and Leman go neural: Higher-order graph neural networks.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602–4609, 2019.
  * [66] Jaroslav Nešetřil and Vojtěch Rödl.  Chromatically optimal rigid graphs.  Journal of Combinatorial Theory, Series B, 46(2):133–141, 1989.
  * [67] Motakuri V. Ramana, Edward R. Scheinerman, and Daniel Ullman.  Fractional isomorphism of graphs.  Discrete Mathematics, 132(1):247 – 265, 1994.
  * [68] Neil Robertson and Paul D. Seymour.  Graph minors. III. Planar tree-width.  J. Comb. Theory, Ser. B, 36(1):49–64, 1984.
  * [69] Edward R Scheinerman and Daniel H Ullman.  Fractional graph theory: a rational approach to the theory of graphs.  Courier Corporation, 2011.
  * [70] Alexander Schrijver.  Theory of Linear and Integer Programming.  John Wiley & Sons, Inc., USA, 1986.
  * [71] Hanif D. Sherali and Warren P. Adams.  A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems.  SIAM J. Discret. Math., 3(3):411–430, 1990.
  * [72] Johan Thapper and Stanislav Živný.  The Power of Linear Programming for Valued CSPs.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 669–678. IEEE Computer Society, 2012.
  * [73] Johan Thapper and Stanislav Živný.  The Complexity of Finite-Valued CSPs.  J. ACM, 63(4):37:1–37:33, 2016.
  * [74] Johan Thapper and Stanislav Živný.  The Power of Sherali-Adams Relaxations for General-Valued CSPs.  SIAM J. Comput., 46(4):1241–1279, 2017.
  * [75] Gottfried Tinhofer.  Graph isomorphism and theorems of Birkhoff type.  Computing, 36(4):285–300, 1986.
  * [76] Gottfried Tinhofer.  A note on compact graphs.  Discret. Appl. Math., 30(2-3):253–264, 1991.
  * [77] Caterina Viola and Stanislav Živný.  The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains.  ACM Trans. Algorithms, 17(3):21:1–21:23, 2021.
  * [78] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How Powerful are Graph Neural Networks?  In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
  * [79] Yuichi Yoshida and Yuan Zhou.  Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems.  In Moni Naor, editor, Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014, pages 423–438. ACM, 2014.
  * [80] Dmitriy Zhuk.  A Proof of the CSP Dichotomy Conjecture.  J. ACM, 67(5):30:1–30:78, August 2020.

##  Appendix A Applying the SA method exactly

In this section we will show that the family of relaxations
$\textnormal{SA}^{k}$ considered in the present paper is closely interleaved
with the system of relaxations obtained by applying the SA method to a natural
choice of initial polytope $\mathbb{P}$.

Let $\mathbf{X}$ and $\mathbf{A}$ be $\sigma$-structures. We define the
polytope $\mathbb{P}=\mathbb{P}(\mathbf{X},\mathbf{A})$ using a system of
inequalities. The variables of the system are $y_{x,a}$ for each $x\in X$ and
$a\in A$. Each variable must take a value in the range $[0,1]$. We remark that
by fixing some arbitrary ordering on the variables $y_{x,a}$ we can represent
any assignment of the variables $y_{x,a}$ with a tuple
$\textbf{y}\in\mathbb{R}^{n}$ with $n=|X|\cdot|A|$. Therefore we shall abuse
notation and use $\textbf{y}_{x,a}$ to refer to the value of the assignment y
corresponding to variable $y_{x,a}$.

The variables are subject to the following inequalities.

$\displaystyle\sum_{a\in A}y_{x,a}=1$ $\displaystyle x\in X,$ (8)
$\displaystyle\sum_{x\in\\{\textbf{x}\\}}y_{x,f(x)}\leq|\\{\textbf{x}\\}|-1$
$\displaystyle\textnormal{for each }R\in\sigma,\ \textbf{x}\in
R^{\mathbf{X}},\,\textnormal{ and}$ (9) $\displaystyle
f:\\{\textbf{x}\\}\rightarrow A\textnormal{ with }f(\textbf{x})\not\in
R^{\mathbf{A}}.$

Note that if $h$ is a homomorphism from $\mathbf{X}$ to $\mathbf{A}$ then the
assignment setting $y_{x,h(x)}=1$ for every $x\in X$ and the rest of variables
to zero is feasible.

Now let $\mathbb{P}^{k}$, $k\geq 1$ be the sequence of polytopes obtained by
applying the SA method to $\mathbb{P}$. The following result shows that the
sequence of relaxations defined by $\textnormal{SA}^{k}$ and $\mathbb{P}^{k}$
are interleaved.

######  Lemma 18.

Let $k\geq 1$ and let $r$ be the maximum arity of a relation in $\sigma$. Then

  1. 1.

If $\mathbb{P}^{k}\neq\emptyset$ and $r\leq k$ then $\textnormal{SA}^{k}$ is
feasible.

  2. 2.

If $\textnormal{SA}^{k+r-1}(\mathbf{X},\mathbf{A})$ is feasible then
$\mathbb{P}^{k}\neq\emptyset$.

###### Proof.

(1). Assume that $\mathbb{P}^{k}\neq\emptyset$ and let z be a feasible
solution of $\mathbb{P}^{k}_{L}$. We shall construct a feasible solution of
$\textnormal{SA}^{k}(\mathbf{X},\mathbf{A})$. First, set every variable of the
form $p_{V}(f)$ to $z_{K}$ where $K=\\{(x,f(x))\mid x\in V\\}$. We first
observe that this assignment satisfies (SA1) and (SA2). Indeed, let
$U\subseteq X$ with $|U|<k$, let $f:U\to A$, and let $I=\\{(u,f(u)):u\in
U\\}$. Then, multiplying the equality (8) with $x\in X\setminus U$ by
$\Pi_{i\in I}y_{i}$ and linearizing we obtain equality (SA2) for $U$, $f$, and
$V=U\cup\\{x\\}$. In this way we can obtain all equalities in (SA2) for
$|U|+1=|V|$. We note here that the rest of equalities in (SA2) along all
equalities in (SA1) can be obtained as a linear combination.

Secondly, let us set the rest of variables. For every
$(\textbf{x},R)\in\mathcal{C}_{\mathbf{X}}$ and $f:\\{\textbf{x}\\}\to A$, set
$p_{(\textbf{x},R)}(f)$ to be $z_{K}$ where $K=\\{(x,f(x))\mid
x\in\\{\textbf{x}\\}\\}$ (note that we are using implicitly the fact that
$r\leq k$). Then, (SA3) follows directly from (SA2). Finally, it only remains
to show that (SA4) is also satisfied. Indeed, for every $f(\textbf{x})\not\in
R^{\mathbf{A}}$ we obtain equality $p_{(\textbf{x},R)}(f)=0$ if we multiply
(9) by the term $\Pi_{i\in K}$ and linearize.

(2). Assume that $\textnormal{SA}^{k+r-1}(\mathbf{X},\mathbf{A})$ is feasible.
We construct a feasible solution z of $\mathbb{P}^{k}_{L}$ as follows. For
every $K\subseteq X\times A$ which satisfies $K=\\{(x,f(x))\mid x\in U\\}$ for
some $U\subseteq X$ with $|U|\leq k$ and $f:U\to A$, we set $z_{K}:=p_{U}(f)$.
Otherwise, we set $z_{K}$ to zero.

Let us show that this assignment satisfies all inequalities in
$\mathbb{P}^{k}_{L}$. Let

$\textbf{c}^{T}\textbf{z}\leq\textbf{d}$ (10)

be any inequality defining $\mathbb{P}^{k}_{L}$. Since (10) is obtained by
multiplying an inequality which contains at most $r$ variables by a term of at
most $k-1$ variables, there exists a set $V\subseteq X$ with $|V|\leq r+k-1$
such that for every variable $z_{K}$ appearing in (10), $V$ satisfies
$K\subseteq V\times A$. Note that, by (SA1), variables $p_{V}(g)$, $g:V\to A$
define a probability distribution. For every $g:V\to A$ in the support of this
distribution, consider the assignment $\textbf{y}^{g}$ that sets
$\textbf{y}^{g}_{x,a}=1$ if $x\in V$ and $b=g(x)$ and $y_{x,b}=0$ otherwise.

Inequality (10) has been obtained by multiplying an inequality from (8) or (9)
by a term and linearizing. We claim that in both cases, the inequality that
has generated (10) is satisfied by $\textbf{y}^{g}$. If the inequality
generating (10) is $\sum_{a\in A}y_{x,a}=1$ for some $x\in X$ this follows
simply from the fact that $x\in V$. Assume now that (10) has been generated by
inequality $\sum_{x\in\\{\textbf{x}\\}}y_{x,f(x)}\leq|\\{\textbf{x}\\}|-1$. In
this case note that $\\{\textbf{x}\\}\subseteq V$ and then the claim follows
from (SA3) and (SA4). This finalizes the proof of the claim.

Consequently, since $\textbf{y}^{g}$ is integral it follows that the
assignment $\textbf{z}^{g}$ defined as $\textbf{z}^{g}_{K}=\Pi_{i\in
K}\textbf{y}^{g}_{i}$ satisfies (10). Finally, note that if we set
$\alpha^{g}=p_{V}(g)$, then for every $K\subseteq V\times A$, $\textbf{z}_{K}$
is precisely given by the convex combination
$\sum_{g}\alpha^{g}\textbf{z}^{g}_{K}$. ∎