# Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random
Graphs

Pravesh K. Kothari Princeton University<EMAIL_ADDRESS>Supported
by NSF CAREER Award #2047933, Alfred P. Sloan Fellowship and a Google Research
Scholar Award. Aaron Potechin The University of Chicago,
<EMAIL_ADDRESS>Supported in part by NSF grant CCF-2008920.  Jeff Xu
Carnegie Mellon University<EMAIL_ADDRESS>Supported in part by NSF
CAREER Award #2047933, and a Cylab Presidential Fellowship.

###### Abstract

We prove that for every $D\in\mathbb{N}$, and large enough constant
$d\in\mathbb{N}$, with high probability over the choice of $G\sim G(n,d/n)$,
the Erdős-Rényi random graph distribution, the canonical degree $2D$ Sum-of-
Squares relaxation fails to certify that the largest independent set in $G$ is
of size $o(\frac{n}{\sqrt{d}D^{4}})$. In particular, degree $D$ sum-of-squares
strengthening can reduce the integrality gap of the classical Lovász theta SDP
relaxation by at most a $O(D^{4})$ factor.

This is the first lower bound for $>4$-degree Sum-of-Squares (SoS) relaxation
for any problems on _ultra sparse_ random graphs (i.e. average degree of an
absolute constant). Such ultra-sparse graphs were a known barrier for previous
methods and explicitly identified as a major open direction (e.g., [DMO+19,
KM21]). Indeed, the only other example of an SoS lower bound on ultra-sparse
random graphs was a degree-4 lower bound for Max-Cut.

Our main technical result is a new method to obtain spectral norm estimates on
graph matrices (a class of low-degree matrix-valued polynomials in $G(n,d/n)$)
that are accurate to within an absolute constant factor. All prior works lose
$\operatorname{poly}logn$ factors that trivialize any lower bound on $o(\log
n)$-degree random graphs. We combine these new bounds with several upgrades on
the machinery for analyzing lower-bound witnesses constructed by pseudo-
calibration so that our analysis does not lose any $\omega(1)$-factors that
would trivialize our results. In addition to other SoS lower bounds, we
believe that our methods for establishing spectral norm estimates on graph
matrices will be useful in the analyses of numerical algorithms on average-
case inputs.

###### Contents

  1. 1 Introduction
    1. 1.1 Our results
    2. 1.2 Proof Plan
  2. 2 Overview of our sharp spectral bounds on graph matrices
    1. 2.1 Motivating our machinery: walk global, think local
    2. 2.2 Toy examples for sparse matrix norm bounds
    3. 2.3 Recap of graph matrix norm bounds from prior works
    4. 2.4 Our main theorems for graph matrix norm bounds
    5. 2.5 Bridging vertex separator, step-labeling and norm bound
    6. 2.6 Overview of proof for unforced-return bounds and high-mul balance
    7. 2.7 Graph matrix norm bound for grouped shapes
  3. 3 Tight matrix norm bounds: vertex encoding cost
    1. 3.1 Vertex encoding scheme
    2. 3.2 (Non-dangling) Second-use return is forced: overview
    3. 3.3 Starting from the basics: a forced-return argument for 1-in-1-out
    4. 3.4 Branching with mirror copy: a heuristic argument
    5. 3.5 Branch-chasing using R is free
    6. 3.6 Return is still ”forced” with dangling branches
    7. 3.7 Ultimate unforced return bound
    8. 3.8 (Local) 2-cycle-freeness can be useful
  4. 4 Tight matrix norm bounds: block value and maximal-value labeling
    1. 4.1 Set-up for block-value bounds
    2. 4.2 Bounding the block-value from the separator
    3. 4.3 Bounding the drawing costs for unknown shapes
    4. 4.4 Matching bundled wedges
    5. 4.5 Wrapping up block-value for grouped graph matrix
  5. 5 Moment matrix construction
    1. 5.1 Trimming the graph
    2. 5.2 Constructing pseudo-expectation for the truncated subgraph
    3. 5.3 Everything but PSDness for Independent Set
  6. 6 PSDness Analysis from Norm Bounds
    1. 6.1 Decomposition of the SoS moment matrix into the graph matrix basis
    2. 6.2 Recursive factorization overview: decomposition
    3. 6.3 Main lemmas for PSDness
    4. 6.4 Bounding the middle shapes
    5. 6.5 Charging a single middle shape
    6. 6.6 Grouping middle shapes
    7. 6.7 Wrapping up middle shape bound
    8. 6.8 Bounding intersection terms
    9. 6.9 Charging a particular intersection shape
    10. 6.10 Bounding intersection count
    11. 6.11 Wrapping up the intersection shape bound
  7. 7 Acknowledgement
  8. A Deferred details for trace-method calculation
    1. A.1 Handling singleton edges
    2. A.2 Singleton decay from absence of nearby 2-cycle
    3. A.3 Singleton decay from bounded degree
    4. A.4 Edge-value assignment
    5. A.5 From trace to concentration
  9. B Deferred details for PSD analysis
    1. B.1 Truncation error
    2. B.2 Sum of left shapes is well-conditioned

##  1 Introduction

An Erdős-Renyi random graph with average degree $d$ has an independence number
of $(1+o_{n}(1))\frac{2n\log d}{d}$ and a chromatic number of
$(1+o_{n}(1))\frac{d}{2\log d}$ with high probability [COE15, DM11, DSS16].
There is a long line of work focused on finding the best _efficiently
certifiable_ bounds on these quantities. When the average-degree of the graphs
$d=\Omega(\operatorname{poly}(\log n))$, the spectral norm of the (centered)
adjacency matrix [FO05] certifies an upper bound on the independence number of
$O(\frac{n}{\sqrt{d}})$. These bounds are off from the “ground-truth” by a
factor of $\frac{1}{\sqrt{d}}$. Upgrading eigenvalue based certificates to
those based on the “basic” semidefinite programming relaxation yields no
asymptotic improvement [CO05]. Investigating whether efficient certificates
that improve on the above bounds exist has been a longstanding and major open
question.

SDP hierarchies are natural candidates for improving on the certificates based
on the basic SDP. The sum-of-squares hierarchy of SDP relaxations [Las00,
Par00] is the strongest such hierarchy considered in the literature. Sum-of-
squares captures the best known algorithms for many worst-case combinatorial
optimization problems [GW94, ARV04] and in the past decade, has been
responsible for substantially improved and often optimal algorithms for
foundational average-case problems [BRS11, GS11, HSS15, MSS16, RRS17, KSS18,
HL18, KKM20, Hop19, BK21]. As a result, establishing sum-of-squares lower
bounds for basic average-case graph problems has been a major research
direction in the past decade and a half.

Following on the early works in proof complexity, researchers were able to
obtain essentially optimal sum-of-squares lower bounds for random constraint
satisfaction problems [Gri01, Sch08, BCK15, KMOW17]. However, going beyond
constraint satisfaction required significantly new ideas. In particular, a
sequence of papers in the last decade made progress on lower bounds for the
planted clique problems [FK02, DM15, MPW15] before it was resolved in [BHK+19]
via the new method called _pseudo-calibration_. Since then, there has been
considerable progress in obtaining strong lower bounds for foundational
average-case problems such as Sparse PCA, densest k-subgraph, and the
Sherrington-Kirkpatrick problem [HKP+17, KB19, MRX20, GJJ+20, KM21, JPR+22,
HK21, JPRX23].

##### Pseudo-calibration and Spectral Norms of Graph Matrices

Analyzing lower bound witnesses constructed via pseudo-calibration crucially
relies on decomposing certain correlated random matrices into a “Fourier-like”
basis of _graph matrices_ and understanding bounds on their spectral norms.
Each entry of such graph matrices is a polynomial in the underlying edge-
indicator variables of the input random graph. There has been considerable
progress in the past few years in understanding the spectra of such matrices
when the input is a _dense_ random graph [AMP20, CP20, JPR+22, RT23]. However,
when the input is an “ultra-sparse” random graph with a constant average
degree, known tools turn out to be rather blunt. At a high level, given the
rather complicated structure of graph matrices, prior methods only yield a
_coarse_ bound on their spectral norms. Such coarse bounds nevertheless
suffice for analyzing the lower bound witnesses for problems on dense random
graphs (with some polylogarithmic factor losses). On ultra-sparse graphs,
however, it turns out to be an absolute non-starter.

Indeed, the limited progress seen so far in the ultra-sparse regime has come
about via rather ad hoc techniques. For the “basic SDP” (i.e., degree $2$ sum-
of-squares), prior works[DMO+19, BKM19, BMR19] relied on the fact that the
spectrum of the underlying matrices (that turns out to have essentially
independent entries) can be completely understood via some powerful tools from
random matrix theory. The work of [MRX20] is the only one to go beyond the
basic SDP and obtain degree four sum-of-squares lower bounds for the
Sherrington-Kirkpatrick problem (essentially Max-Cut with independent Gaussian
weights) on ultra sparse random graphs. They accomplished this via a certain
“lifting” technique that circumvented pseudo-calibration. Their technique,
however, is unwieldy to even extend to degree 6 sum-of-squares relaxation or
problems with “hard” constraints (such as independent set, the focus of the
present work).

##### A curse of sparsity?

More generally, the ultra-sparse regime has been a challenge for understanding
algorithmic problems on graphs for a long time. For example, it took a long
sequence of works and some sophisticated tools in random matrix theory (e.g.,
the Ihara-Bass formula and spectral understanding of the _non-backtracking
walk matrix_ of random graphs) to resolve the algorithmic threshold for
_community detection_ on the stochastic block model [ABH14, AS15, Abb17, AS18,
BKM19, BMR19].

One basic issue that makes the ultra-sparse setting challenging is that the
spectrum of random matrices that arise in such settings suffers from a large
variance that makes the analysis tricky. For example, for $d=\omega(1)$, the
Erdős-Rényi random graph is almost regular (deviations in degree are
negligible compared to the average). When $d=O(1)$, however, this is no longer
true: there are bound to be vertices of super-constant degree
$\Omega(\sqrt{\log n})$ on the one end and vertices of degree $0$ (i.e.
isolated vertices) on the other. A trickier issue arises from events with
small but non-negligible probability that makes the analysis based on the
moment method (the workhorse in such analyses) tricky. For example, it can be
shown that for the adjacency matrix $A$ of an Erdős-Rényi graph, even after
removing rows and columns corresponding to high degree vertices, for large
$k$, $\mathbb{E}\left[\tr\left((A-\mathbb{E}[A])^{k}\right)\right]$ is much
larger than its typical value due to an inverse polynomial chance of the
presence of dense subgraphs.

While such issues have been tackled in the past, with significant effort
[MNS18, KMM+13, Mas14, BLM15, MNS15, HS17, LMR22, DdNS21, ZK16, KZ09, DKMZ11a,
DKMZ11b] for analyzing the spectra of _basic_ matrices associated with ultra
sparse random graphs (e.g., adjacency matrices, non-backtracking walk
matrices), in our setting the problem is significantly more involved because
of our need to understand substantially more complicated _graph matrices_
built from sparse random graphs — matrices of polynomial dimension with
entries that are low-degree polynomials in the entries of the adjacency matrix
of $G(n,d/n)$ and which are invariant (as a function of the adjacency matrix
of $G(n,d/n)$) under permutations of $[n]$.

##### This Work: a fine-grained method for sharp bounds on spectra of graph
matrices

A key contribution of this work is a new technique to analyze the spectrum of
graph matrices built from ultra sparse random graphs via the moment method. A
consequence of these techniques is estimates of spectral norms for graph
matrices that are tight to within an _absolute_ constant factor! Even in the
case of _dense_ random graphs (let alone the significantly more challenging
setting of ultra-sparse random graphs), finding techniques that yield sharp
bounds on spectral norms of graph matrices was considered significantly
challenging — a main contribution of [MRX20] was finding such bounds for a
limited subset of graph matrices.

###  1.1 Our results

In this work, we prove that for every $d\in\mathbb{N}$, constant degree sum-
of-squares strengthening of the independent set axioms fail to certify a bound
of $o(n/\sqrt{d})$ on the maximum independent set with high probability when
$G\sim G(n,d/n)$. To formulate this precisely, let us recall the notion of
pseudo-expectations consistent with a set of polynomial equations:

######  Definition 1.1 (Pseudo-expectation of degree-$d_{sos}$).

For any $d_{sos}\in\mathbb{N}$, a degree $d_{sos}$-pseudoexpectation in
variables $x=(x_{1},x_{2},\ldots,x_{n})$ (denoted by
$\widetilde{\mathbb{E}}_{d_{sos}}$) is a linear map that assigns a real number
to every polynomial $f$ of degree $\leqslant d$ in $x$ and satisfies: 1)
normalization: $\widetilde{\mathbb{E}}[1]=1$, and, 2) positivity:
$\widetilde{\mathbb{E}}[f^{2}]\geqslant 0$ for every polynomial $f$ with
degree at most $\frac{d_{sos}}{2}$. For any polynomial $g(x)$, a pseudo-
expectation satisfies a constraint $g=0$ if $\mathbb{E}[f\cdot g]=0$ for all
polynomials $f$ of degree at most $d_{sos}-deg(g)$.

We can now describe the sum-of-squares relaxation for independent set in a
graph $G$.

######  Definition 1.2 (Independent Set Axioms).

Let $G$ be a $n$-vertex graph. The following axioms describe the $0$-$1$
indicators $x$ of independent sets in $G$:

$\forall v\in V,x_{v}^{2}=x_{v}\quad{\text{(Booleanity) }}\,;$
$\forall(u,v)\in E,x_{u}x_{v}=0\quad{\text{(Independent set)}}$

The degree $d_{sos}$-sum-of-squares relaxation for independent set in $G$
maximizes $\widetilde{\mathbb{E}}[\sum_{i}x_{i}]$ over all pseudo-expectations
of degree $d_{sos}$ satisfying the above two axioms.

More precisely, we prove:

[Main result]theoremmain-indset There is a $c>0$ such that for every
$d\in\mathbb{N}$, with probability $1-o_{n}(1)$ over $G\sim G_{n,d/n}$, there
exists a degree-$d_{sos}$ pseudo-expectation satisfying the independent set
axioms (Definition 1.2) and

$\sum_{i\in[n]}\widetilde{\mathbb{E}}[x_{i}]\geqslant(1-o(1))\frac{n}{c\cdot\sqrt{d}\cdot
d_{sos}^{4}}\,.$

######  Remark 1.3.

We note that our techniques likely allow improving the dependence on $d_{sos}$
in the denominator to a linear (instead of quartic) bound. We believe that
removing this dependence altogether is possible but requires new ideas.

Our construction of the lower bound witness (aka pseudo-moment matrix) is
based on pseudo-calibration. Informally speaking, pseudo-calibration provides
a guess for the pseudo-expectation with a certain “truncated” probability
density function of a planted distribution (a distribution over graphs
containing a large independent set) that is indistinguishable for low-degree
polynomials from $G(n,d/n)$. However, as observed in prior works [JPR+22],
natural planted distributions are _not_ low-degree indistinguishable from
$G(n,d/n)$ when $d=O(1)$. Nevertheless, it turns out that one can use a
certain ad hoc truncation that drops certain carefully chosen terms to obtain
a pseudo-expectation that allows us to prove definition 1.2 above. Our
truncation strategy is an upgraded variant of the _connected truncation_ first
utilized in [JPR+22].

In the ultra-sparse regime, our analysis needs to separately consider the
vertices that have too high a degree. This trimming of the graph inevitably
introduces non-trivial correlations in the graph matrices – a significant
challenge – that we show how to overcome in our analysis.

##### Sharp bounds on spectral norms of Graph Matrices

Our main technical contribution is a new technique that yields sharp bounds on
the spectral norms of _graph matrices_ — low-degree matrix valued polynomials
in the edge indicator variables of $G\sim G(n,d/n)$. The low-degree
polynomials themselves are naturally described by graphs. All prior works
beginning with [BHK+16] rely on elegant statements that relate the spectral
norms of such graph matrices to natural combinatorial quantities associated
with the graphs. However, the precise bounds they achieve turn out to be
rather coarse and lose $\operatorname{poly}\log n$ factors. Such losses still
turn out to give non-trivial results for problems on dense random graphs.
However, they trivialize in the setting of random graphs with average degree
$\ll\log n$ — our principal interest in this work. While this might appear to
be a technical issue, finding methods that do not lose such
$\operatorname{poly}\log n$ factors was understood to be a major bottleneck in
the area. Indeed, even resolving the case of polylog n degree random graphs
took several new ideas in the recent work [JPR+22].

In this work, we finally build methods that overcome the bottlenecks in the
prior works and obtain bounds that sharp _up to absolute constants_ on the
spectral norms of graph matrices. At a high-level, the trace moment method for
bounding the spectral norm of a matrix relies on counting the contributions of
closed walks on the entries of the matrix. A key new high-level idea in our
analysis is a certain _localization_ of the walk that allows understanding the
contribution of a walk from a single step. This localization allows us to
obtain a tractable method to bound total contributions to the weighted count
of closed walks with negligible losses.

##### Upgrading the decompose-and-recurse machinery for analyzing pseudo-
expedctations

Our analysis of the pseudo-moment matrix we construct requires a substantial
upgrade of the machinery for establishing sum-of-squares lower bounds [BHK+19,
GJJ+20, PR23] via pseudo-calibration. In particular, the strategy in prior
works involves “charging” graph matrices of various shapes (see the technical
overview for a more detailed exposition) that arise in the decomposition to
positive semidefinite (PSD) terms in the decomposition. Such a charging
argument requires a careful count of the terms charged to each PSD term. In
the coarse-grained analysis a bound on such a count that is tight up to an
exponential in the size of the shape defining the graph matrix suffices. Such
an analysis is one of the reasons that even the tightest previous analyses
[JPR+22] loses $polylog(n)$ factors that trivialize the final bounds in the
ultra sparse regime, even combined with our tight norm bounds. A key idea that
we utilize in this work (that builds on the insight developed from our new
techniques in establishing strong spectral norm bounds) involves a careful
grouping of terms arising in the graph matrix decomposition of the pseudo-
moment matrix so as to avoid the above loss.

##### Organization

In Section 2, we introduce the preliminaries and notations for our arguments.
We showcase the techniques we develop for proving tight norm bounds of graph
matrices with formal details in Section 3: specifically, we bound the
”counting” factor for long walks on graph matrices in Section 3, and use it to
conclude the final norm bound in Section 4.

We then apply our norm bounds to PSD analysis of the moment matrix. We
describe our moment matrix in Section 5 as it is not sufficient to apply
pseduo-calibration in a black-box manner due to fluctuation of vertex degree,
Moreover, we strengthen the ”connected truncation” idea developed in [JPR+22]
due to lower-order dependence of norm bounds that can become potentially
detrimental in our regime.

Finally, we apply the machinery developed in [JPR+22, PR23] with our norm
bounds to prove the PSDness of our moment matrix.

###  1.2 Proof Plan

Pseudo-calibration [BHK+19] provides a general recipe for designing pseudo-
expectation as required by Theorem 1.2. As we mentioned before, our analysis
involves a modified version of the naive construction given by pseudo-
calibration with a certain appropriate truncation (see Section 5). As in the
prior works, the main challenge is establishing the positivity property. This
property is equivalent to proving the positive semidefiniteness of a certain
“pseudo-moment” matrix $\Lambda$ associated with a pseudo-expectation. As has
been the standard approach since [BHK+16], we proceed to analyze the pseudo-
moment matrix $M$ by decomposing it as a linear combination of special “bases”
called graph matrices:

$\Lambda=Id+\sum_{\alpha\in\tau}\lambda_{\alpha}\cdot M_{\alpha}\,.$

Here, $\tau$ ranges over graph matrices and $\lambda_{\alpha}$ are real
coefficients on graph matrices $M_{\alpha}$ for $\alpha\in\tau$. In order to
understand the eigenvalues of $\Lambda$ and establish positive
semidefiniteness, it is natural to understand the spectral properties of the
bases $M_{\alpha}$. In order to focus attention on our main technical
contribution, we will dedicate the upcoming overview section to our method for
establishing sharp bounds on the spectral norm of such graph matrices.

##  2 Overview of our sharp spectral bounds on graph matrices

The main challenge in analyzing graph matrices is that their entries are
highly correlated. In particular, an $N\times N$ graph matrix generally has
entries that are polynomial functions of $N^{o(1)}$ bits of independent
randomness. This makes analyzing the trace powers of graph matrices
complicated. As a result, previous analyses of the norms of graph matrices
lose poly-logarithmic factors even when the input graph is a dense random
graph. Our main contribution is developing a new method for conducting such an
analysis that somewhat surprisingly yields estimates that are sharp up to
absolute constant factors.

To describe our new techniques for obtaining the above improved spectral norm
bounds, we will focus this overview on two specific and simple examples of
graph matrices and then discuss how our ideas extend more generally. Let’s
start with the formal definition of graph matrices.

######  Definition 2.1 (Fourier character for $G_{n,d/n}$).

Let $\chi$ denote the $p$-biased Fourier character,

$\chi_{G}(1)=\sqrt{\frac{1-p}{p}}=(1+o_{n}(1))\sqrt{\frac{n}{d}},\quad\chi_{G}(0)=-\sqrt{\frac{p}{1-p}}=-(1+o_{n}(1))\sqrt{\frac{d}{n}}$

For a subset of edges $H\subseteq\binom{n}{2}$, we write
$\chi_{G}(H)=\prod_{e\in H}\chi_{G}(e)$.

######  Definition 2.2 (Shape).

A shape $\alpha$ is a graph on vertices $V(\alpha)$ with edges $E(\alpha)$ and
two ordered tuples of vertices $U_{\alpha}$ (left boundary) and $V_{\alpha}$
(right-boundary) We denote a shape $\alpha$ by
$(V(\alpha),E(\alpha),U_{\alpha},V_{\alpha})$.

######  Definition 2.3 (Shape transpose).

For each shape $\alpha$, we use $\alpha^{T}$ to denote the shape obtained by
flipping the boundary $U_{\alpha}$ and $V_{\alpha}$ labels. In other words,
$\alpha^{T}=(V(\alpha),E(\alpha),U_{\alpha^{T}}=V_{\alpha},V_{\alpha^{T}}=U_{\alpha})$.

######  Definition 2.4 (Embedding).

Given an underlying random graph sample $G$, a shape $\alpha$ and an injective
function $\psi(\alpha):V(\alpha)\to[n],$ we define $M_{\psi(\alpha)}$ to be
the matrix of size
$\frac{n!}{(n-|U_{\alpha}|)!}\times\frac{n!}{(n-|V_{\alpha}|)!}$ with rows and
columns indexed by ordered tuples of $[n]$ of size $|U_{\alpha}|$ and
$|V_{\alpha}|$ with a single nonzero entry

$M_{\psi(\alpha)}[\psi(U_{\alpha}),\psi(V_{\alpha})]=\prod_{(i,j)\in
E(\alpha)}\chi_{G}\left(\psi(i),\psi(j)\right).$

and $0$ everywhere else.

######  Definition 2.5 (Graph matrix of a shape).

For a shape $\alpha$, the graph matrix $M_{\alpha}$ is

$M_{\alpha}=\displaystyle\sum_{\text{injective
}\psi:V(\alpha)\to[n]}M_{\psi(\alpha)}.$

When analyzing the sum of squares hierarchy, we extend $M_{\alpha}$ to have
rows and columns indexed by all tuples of vertices of size at most
$\frac{d_{sos}}{2}$ by filling in the remaining entries with $0$.

######  Example 2.6 (Line-graph graph matrix $M_{line}$).

Define $M_{line}\in\mathbb{R}^{n\times n}$ to be a matrix with zeros on the
diagonal and off-diagonal entries $M_{line}[u,v]=\chi_{G}(u,v)$.

$M_{line}$ is, up to rescaling, the centered adjacency matrix of a random
graph from $G_{n,d/n}$. We will also use the following $Z$-shape matrix as a
slightly complicated example in our discussion in this section.

######  Example 2.7 ( $Z$-shape graph matrix $M_{Z}$).

Define $M_{Z}\in\mathbb{R}^{n(n-1)\times n(n-1)}$ by
$M_{Z}[(i,j),(k,\ell)]=\chi_{G}(i,k)\chi_{G}(j,k)\chi_{G}(j,\ell)$ whenever
$i,j,k,\ell$ are distinct and $0$ otherwise.

Observe that $M_{Z}$ has $n^{2}(n-1)^{2}$ entries that are low-degree
polynomials in the underlying $\ll n^{2}$ bits of randomness and are thus
highly correlated. Note also that $M_{Z}$ is not a tensor product of
$M_{line}$ and thus does not admit an immediate description of its spectrum in
terms of $M_{line}$111For the dense case, Cai and Potechin [CP22] showed that
surprisingly, the spectrum of the singular values of $M_{Z}$ has a relatively
simple description in terms of the spectrum of the singular values of
$M_{line}$.

Figure 1: Line-graph
$M_{line}[u,v]=\chi_{G}(u,v)$

Figure 2: Z-shape $M_{Z}[(i,j),(k,\ell)]=$
$\chi_{G}(i,k)\cdot\chi_{G}(j,k)\cdot\chi_{G}(j,\ell)$

In this section, we will sketch the following two lemmas that are special
cases of our main result on spectral norms of graph matrices and illustrate
some of our key new ideas. Our spectral bounds hold when $M_{Z}$ and
$M_{line}$ are defined as function of $G^{\prime}$ obtained from $G\sim
G(n,d/n)$ by removing all edges incident on vertices of degree $\geqslant
O(d)$.

######  Lemma 2.8 (Informal version of Lemma 2.28, 2.29).

With high probability over the random graph sample $G\sim G_{n,d/n}$, we have

$\|M_{line}(G^{\prime})\|\leqslant O(\sqrt{n})\,,$

and

$\|M_{Z}(G^{\prime})\|\leqslant O(\sqrt{\frac{n}{d}}\cdot\sqrt{n}^{2})\,.$

where $O(\cdot)$ hides an absolute constant independent of $d$. Here,
$G^{\prime}$ is obtained from $G$ by removing all edges incident to vertices
of degree $\geqslant O(d)$.

We note that the above bounds are tight up to absolute constant factors
(independent of $d$).

##### Trace moment method

Our proof proceeds by analyzing trace moments of matrices using that for any
$A$, the spectral norm $\left\lVert
A\right\rVert_{spec}\leqslant\tr((AA^{\top})^{q})^{1/2q}$. Taking $q$ to be
logarithmic in the dimension of $A$ suffices to get a bound on $\left\lVert
A\right\rVert$ sharp up to $1+\delta$ for an arbitrarily small $\delta>0$. The
trace power can be expanded as a sum of weighted walks of length $2q$ over the
entries of $M_{\alpha}$. Notice that each walk can be viewed as a labeling of
a graph composed of $q$ blocks of $\alpha$ and $\alpha^{T}$, in particular, it
suffices for us to consider the following labelings of walks.

Each term in the expansion of $\tr((M_{\alpha}M_{\alpha}^{\top})^{q})$
corresponds to a labeling of the vertices in $q$ copies of $\alpha$ and
$\alpha^{\top}$ with labels from $[n]$ (i.e, vertices of the graph $G$)
satisfying some additional constraints that correspond to a valid walk. The
following definition captures these constraints.

######  Definition 2.9 (Shape walk and its valid labelings).

Let $\alpha$ be a shape and $q\in\mathbb{N}$. For each walk $P$, let
$G_{P}(\alpha,2q)$ be the _shape-walk_ graph of the shape-walk $P$ vertices on
vertices $V_{P}(\alpha,2q)$ formed by the following process,

  1. 1.

Take $q$ copies of $\alpha_{1},\dots,\alpha_{q}$ of $\alpha$, and $q$ copies
of $\alpha_{1}^{T},\dots,\alpha_{q}^{T}$ of $\alpha^{T}$;

  2. 2.

For each copy of $\alpha_{i}$ (and $\alpha_{i}^{T}$), we associate it with a
labeling, i.e., an injective map $\psi_{i}:V(\alpha)\rightarrow[n]$ (and
respectively $\psi_{i}^{\prime}$ for $\alpha^{T}$);

  3. 3.

For each $i\in[q]$, we require the boundary labels to be consistent as ordered
tuples, i.e. $\psi_{i}(U_{\alpha})=\psi^{\prime}_{i-1}(V_{\alpha})$ and
$\psi^{\prime}_{i}(U_{\alpha^{T}})=\psi_{i}(V_{\alpha_{i}})$;

  4. 4.

Additionally, each such walk must be closed, i.e.,
$\psi^{\prime}_{q}(V_{\alpha^{T}})=\psi_{1}(U_{\alpha})$ as a tuple-equality;

  5. 5.

We call each $\alpha_{i}$ and $\alpha^{T}_{i}$ block a block-step in the walk.

For each walk-graph , we associate it with a natural decomposition
$P=\psi_{1}\circ\psi_{1}^{\prime}\circ\psi_{2}\circ\dots\circ\psi_{q}\circ\psi_{q}^{\prime}$.

With the walks identified, we may now unpack the trace inequality we are in
pursuit of, and offer some motivation for the counting scheme to be described.
For any $q\in\mathbb{N}$,

$\displaystyle\mathbb{E}_{G\sim
G_{n,d/n}}\left[\Tr\left((M_{\alpha}M_{\alpha}^{T})^{2q}\right)\right]$
$\displaystyle=\sum_{\begin{subarray}{c}\text{shape
walk}P:V(\alpha,2q)\rightarrow[n]\\\ \text{locally injective at each
piece}\end{subarray}}\mathbb{E}_{G}[\prod_{t\in[q]}\prod_{(i,j)\in
E(\alpha)}\chi_{G}(\psi_{t}(i),\psi_{t}(j))\cdot\chi_{G}(\psi^{\prime}_{t}(i),\psi^{\prime}_{t}(j))]$
$\displaystyle=\sum_{\begin{subarray}{c}\text{shape
walk}P:V(\alpha,2q)\rightarrow[n]\\\ \text{locally injective at each
piece}\end{subarray}}\mathbb{E}_{G}[\text{val}_{G}(P)]$

where we use the short form

$\text{val}_{G}{(P)}\coloneqq\prod_{e=(i,j)\in E(P)}\chi_{G}(e)=\prod_{e\in
E(P)}\chi_{G}^{\text{mul}_{P}{(e)}}(e)$

where we denote $E(P)$ be the set of edges traversed in the walk $P$, and
$\text{mul}_{P}(e)$ is the multiplicity of $e$ appearing in the walk, where
the dependence on $P$ is usually dropped when it is clear from the context.
Our goal now is to bound the sum of $\text{val}_{G}(P)$ over all possible
labelings $P$ that are locally injective, and that could possibly occur in the
trace power expansion above.

##### Pruning and Conditioning

A complication that arises from our setting is that the high moments of the
trace are in fact too large. As mentioned in the introduction, there are two
fundamental sources responsible for this issue: 1) fluctuations in the vertex
degrees which have a large effect on the norm (so the improved norm bound is
false without pruning high degree vertices); and 2) rare events happening with
inverse-polynomial probability that dominate the contribution to the expected
trace power, eg., the event of having a small dense subgraph. To address these
two challenges, we work with $\mathcal{G}$ which is a pruned subgraph of a
graph sample from $G\sim G_{n,d/n}$, which is further conditioned on the high
probability event that the graph has $2$-cycle free radius
$\Theta(\log_{d}n)$.

######  Definition 2.10 ($2$-cycle freeness).

Given a graph $G=(V,E)$, we call it a $2$-cycle free graph if for any pair of
vertices $u,v\in V(G)$, there are at most $2$ simple paths between $u$ and
$v$. Equivalently, each connected component of $G$ has at most one cycle.

######  Definition 2.11 ($2$-cycle free radius).

The $2$-cycle free radius of a graph is the largest $r$ such that for any
vertex $v$, the induced subgraph of vertices within distance $r$ of $v$ is a
$2$-cycle free graph.

######  Definition 2.12 (Indicator functions).

Given a set of vertices $V\subseteq V(G)$, let $1_{{\mathcal{F}}}[V]$ be the
indicator function for each vertex in $V$ having bounded degree, i.e.,
$1_{{\mathcal{F}}}[V]=1$ if every vertex in $V$ has degree at most
$c_{degree}\cdot d$ and $0$ otherwise. For a shape walk $P$, we let
$1_{{\mathcal{F}}}[P]=1_{{\mathcal{F}}}[V(P)]$ where $V(P)$ is the set of
vertices visited by the shape walk.

We set $\kappa=0.3\log_{d}n$. Let $1_{{\mathcal{E}}}[G]=1$ if $G$ has 2-cycle
free radius at least $\kappa$ and $1_{{\mathcal{E}}}[G]=0$ otherwise.

######  Fact 2.13 ([Fri03, BLM15, FM17, Bor19]).

A random graph from $G_{n,d/n}$ has $2$-cycle free radius at least
$\kappa=0.3\log_{d}n$ with high probability $1-o_{n}(1)$.

Therefore, the distribution we work with needs to to be considerably modified,
and we are ultimately interested in the following value,

$\displaystyle\mathbb{E}_{\mathcal{G}}\left[\Tr\left((M_{\alpha}M_{\alpha}^{T})^{2q}\right)\cdot
1_{{\mathcal{E}}}\right]$ $\displaystyle=\sum_{\begin{subarray}{c}\text{shape
walk}P:V(\alpha,2q)\rightarrow[n]\\\ \text{locally injective at each
piece}\end{subarray}}\mathbb{E}_{\mathcal{G}}[\text{val}_{\mathcal{G}}(P)\cdot
1_{{\mathcal{E}}}\ ]$ $\displaystyle=\sum_{P:\text{shape-
walk}}\mathbb{E}_{G\sim G_{n,d/n}}\left[\text{val}_{G}(P)\cdot
1_{{\mathcal{E}}}\cdot 1_{{\mathcal{F}}}[P]\right]$ (1)

###  2.1 Motivating our machinery: walk global, think local

##### Global vs local counts

The trace moments are typically analyzed by inferring global constraints on
contributing walks. For example, in the analysis for tight norm bound for
Gaussian random matrices, the dominant contributing walks have a one-to-one
correspondence with the Dyck walk with exactly half of the steps going to
“new” vertices, and the other half going to ”old” vertices. However, such
global analyses become unwieldy once applied to slightly more complicated
graph matrices e.g., the $Z$-shape matrix we defined earlier. Our main idea is
a new _local_ bound that holds on each step of the walk. This local bound
generalizes naturally to graph matrices with more complicated shapes while
still giving bounds sharp up to an absolute constant.

For each block-step (a step corresponds to a labeling of a shape $\alpha$ when
bounding weighted walks on a graph matrix $M_{\alpha}$) in a walk that
contributes to eq. 1, we will associate two types of charges:

  1. 1.

$\mathsf{vtxcost}$ that is used to identify the labels of the vertices
appearing (counting);

  2. 2.

$\mathsf{edgeval}$ that captures the expectation of random variables of edges
traversed in the walk;

In total, we will bound the contribution due to block step in the walks
contributing to eq. 1 as

$\mathsf{vtxcost}\cdot\mathsf{edgeval}\leqslant B_{q}(\alpha)$

where $B_{q}(\alpha)$ is some desired upper bound for shape $\alpha$, which we
shall refer to as block-value bound. An assignment of valid block cost
$B_{q}(\alpha)$ for each block translates immediately into a bound for the
final trace moment. Formally, we define the block-value function as the
following,

######  Definition 2.14.

For any shape $\alpha$, and $q\in\mathbb{N}$, for any vertex/edge-factor
assignment scheme, we call $B_{q}(\alpha)$ a valid block-value function of the
given scheme if

$\mathbb{E}[\tr(M_{\alpha}M_{\alpha}^{T})^{q}]\leqslant\text{matrix-
dimension}\cdot\mathsf{auxcost}\cdot B_{q}(\alpha)^{2q}$

for some auxiliary function $\mathsf{auxcost}$ such that

$\left(\text{matrix-dimension}\cdot\mathsf{auxcost}\right)^{1/2q}\leqslant
1+o_{n}(1)\,,$

and for each block-step $\mathsf{BlockStep}_{i}$ throughout the walk,

$\mathsf{vtxcost}(\mathsf{BlockStep}_{i})\cdot\mathsf{edgeval}(\mathsf{BlockStep}_{i})\leqslant
B_{q}(\alpha)$

We stress that the block-value function $B_{q}(\alpha)$ depends on the shape
$\alpha$, the length-$q$, and the vertex/edge-factor assignment scheme. The
bulk of our work is in finding a vertex/edge-factor assignment scheme that
produces a minimal valid $B_{q}(\alpha)$ — the _local_ component of our
argument.

##### Labeling the steps

Our strategy starts by identifying the ”status” of the random variable used in
a given block, which we coin ”step-label”.

######  Definition 2.15 (Edge and step).

We use ”edge” to refer to the undirected edge in the underlying random graph
sample, and ”step” to refer to a directed edge when mentioned in the context
of a walk.

The following vertex labeling scheme is a key component of our new local
argument. Each step in the walk corresponds to a vertex labeling of the shape.
Each such labeling yields a block contributing equal to the product of the
characters on edges appearing in the labeled shape. For each such edge, we
will use four types of labels in order to help us construct $\mathsf{vtxcost}$
and $\mathsf{edgeval}$.

######  Definition 2.16 (Step-label).

We categorize the status of each step as the following. For a step whose
underlying edge/random variable appears at least twice throughout the walk,

  1. 1.

$F$ (a fresh step): an edge (or random variable) appearing for the first time,
and the destination vertex is appearing for the _first_ time in the walk;

  2. 2.

$S$ (a surprise step/visit): an edge (or random variable) appearing for the
first time, and the destination vertex is _not_ appearing for the first time
in the walk;

  3. 3.

$R$ (a return step): an edge (or random variable) appearing for the last time;

  4. 4.

$H$ (a high-mul step) : an edge (or random variable) appearing for neither the
first nor last time.

For a step whose underlying edge/random variable appears only once throughout
the walk, we call the step a _singleton_ step, and additionally call its
underlying edge a _singleton edge_. We will be able to consider a singleton
step as a subclass of $F$ steps in our accounting.

######  Observation 2.17.

Each step receives a single step-label among $\\{F,R,S,H,\text{Singleton}\\}$.

When working with a graph matrix, a single block-step corresponds to several
edge steps (random variables). Hence, we extend the step label to a labeling
for an entire block-step,

######  Definition 2.18 (Block-step labeling).

Given a shape $\alpha$, a labeling
$\mathcal{L}:E(\alpha)\rightarrow\\{F,R,S,H,\text{Singleton}\\}$ for a block-
step is a collection of step labels for for each edge random variable in
$\alpha$.

##### Vertex appearance and redistribution

We will use a different cost for a vertex label depending on how it appears in
a walk. A careful choice of such costs is important.

For example, in the standard argument for bounding the spectral norm of
$n\times n$ Gaussian random matrices, each step, if leading to a new vertex,
contributes a value of $n$ as the destination vertex takes a label in $[n]$,
while on the other hand, if going to a “seen” vertex, contributes a value of
$1$. In this case, if one applies the block-value bound naively, observe that
it would yield a bound of $O(n)$ as opposed to a bound of $O(\sqrt{n})$ with
the contribution being dominated by the steps leading to new vertices. For
this particular example, this bound can be improved by observing at most half
of the blocks attaining a value of $n$ while the other half has a value of $1$
thus geometrically averaging out to $\sim\sqrt{n}$.

However, such reasoning does not readily fit into our local reasoning
framework. We will instead introduce a vertex redistribution scheme. In the
walk, we first formally place vertex’s ”appearance” into three categories.

######  Definition 2.19 (Vertex appearance in a block-step).

Let $v$ be a vertex in the current block-step. We say that $v$ is making its
first appearance if $v$ is not contained in any previous block-steps. We say
that $v$ is making its last appearance if $v$ is not contained in any later
block-steps. We say that $v$ is making a middle appearance if $v$ appears in
both an earlier block-step and a later block-step. Note that we consider a
vertex appearing on the block-step boundary ($U_{\alpha}$ or $V_{\alpha}$) as
appearing in both adjacent blocks.

######  Example 2.20.

If $v\in V_{i}=U_{i+1}$, $v\in V_{j-1}=U_{j}$ for some $j>i+2$, and $v$ does
not appear anywhere else in the walk then $v$ makes its first appearance in
block $i$, makes middle appearances in blocks $i+1$ and $j-1$, and makes its
last appearance in block $j$.

To handle the disparity in the magnitude due to the step-choices, we adopt the
following vertex-factor redistribution scheme.

Each vertex, when it first appears, requires a label in $[n]$. We redistribute
this factor as follows. 1. Assign a $\sqrt{n}$ factor to the block-step in
which the vertex first appears; 2. Assign a $\sqrt{n}$ factor to the block-
step in which the vertex last appears.

Observe that each vertex picks up in the end a factor of $n$ throughout the
walk as it gets $\sqrt{n}$ factor each from its first and last appearance, and
thus the vertex factor (for identifying new vertices) is preserved. To
illustrate the vertex redistribution scheme, we apply the above machinery to
get a loose bound for random $\pm 1$ matrix that is tight up to
polylogarithmic factors.

##### Warm up: a loose bound for random $\pm 1$ matrix

For the following discussion, let $G$ be an $n\times n$ symmetric matrix with
each (off-diagonal) entry sampled i.i.d. from $\\{\pm 1\\}$.

######  Lemma 2.21 (Naive bound on symmetric random matrices via local
argument).

We can bound its block-value function by

$B_{q}(G)\leqslant\sqrt{n\operatorname{polylog}n}\,,$

As a corollary, with probability at least $1-o_{n}(1)$, we have
$\|G\|\leqslant O(\sqrt{n}\operatorname{polylog}n)$.

###### Proof.

Since each edge contributes a value $1$ in expectation whenever the walk is
non-zero, bounding the trace value reduces from bounding weighted closed walks
to simply bounding walk-counts. Hence, it suffices for us to focus on vertex-
factors for this example. We start by casing the step-label, and suppose we
are traversing from (left) $U$ to (right) $V$,

  1. 1.

$F$-step: the left vertex cannot be making its first appearance by definition,
and it cannot be last appearance as otherwise the edge appears only once
throughout the walk. The destination vertex is making a first appearance,
hence contributing a vertex-cost of $\sqrt{n}$;

  2. 2.

$S/H$-step: the left vertex cannot be making its first appearance by
definition, and it cannot be last appearance as otherwise the edge appears
only once throughout the walk. The destination vertex is making a middle
appearance, hence contributing a vertex-cost of $2q=\operatorname{poly}\log
n$;

  3. 3.

$R$-step: The vertex on the left boundary is potentially making a last
appearance, hence contributing a vertex-cost of at most $\sqrt{n}$; the right
vertex cannot be making its first appearance as the edge appears in prior
steps, and the vertex is not making its last appearance by definition. It can
be further specified at a cost of $2q=\operatorname{poly}\log n$;

  4. 4.

Summing the above, we can bound $B_{q}(G)\leqslant 2\sqrt{n}\cdot
q=\sqrt{n}\operatorname{polylog}(n)$ by setting $q=\operatorname{polylog}n$
where we remind the reader that we need to set $q=\Omega(\log n)$ to obtain a
bound that holds with probability $1-o_{n}(1)$.

∎

##### The challenge of a local argument

We note that previous techniques [AMP20, JPR+22, RT23] for analyzing graph
matrices give norm bounds that are tight up to $O(\log^{O(|V(\alpha)|)}n)$
loss for any $M_{\alpha}$. The main challenge in our new local argument is to
obtain bounds tight up to an absolute constant factor.

For readers familiar with trace-method calculation for the example of G.O.E.
matrices, or non-backtracking walk matrices for sparse random graph, observe
that the bound for the $R$-step in the above example is lossy when we use a
label in $2q$ to specify the destination of an $R$-step. This is indeed the
source of the $\operatorname{polylog}$ gap in the above argument. In contrast,
should one imagine the walk proceeds in a tree-like manner, we may consider
the $F/R$ steps as either walking towards or away from the root and for the
case of an $R$ step walking towards the root, the destination of an $R$-step
is _fixed_ as each vertex has only one edge that is moving closer to the root,
avoiding a naive cost of $2q$ to specify the destination.

With the above intuition, one still needs to be careful as there is no reason
a priori to focus exclusively on walks that are strictly tree-like, and the
$R$-destination is no longer fixed once we start seeing cycles, or more
formally, surprise/high-mul steps in the walk. However, as the tight argument
for G.O.E. matrices shows, the effect of surprise steps is in some sense
_local_ as it can be shown that each surprise step can only “confuse” at most
$2$ different $R$-steps, i.e., $R$-steps whose destinations are not unique. To
exploit this observation, one may observe that there is a tremendous _gap_
opened up by an $S$-step in the warm-up example, in particular, we have a
budget of $\sqrt{n}$ per step, while an $S$-step only requires a cost of $2q$
to specify the destination. That said, as opposed to paying just a cost of
$2q$ to specify the destination, one may additionally pay a cost of $(2q)^{2}$
to specify the destination of the $2$ $R$-confusions that the $S/H$-step may
incur. By paying this extra cost for $S$-step (as well as for $H$-step in a
similar fashion), one can assume that _$R$ -destination is fixed_ throughout
the walk, shaving the polylog overhead. Broadly speaking, we will call the
cost used to settle $R$-confusion $\mathsf{Pur}$-factors/costs (_potentially
unforced-return_) and we defer this to Section 3.2. The above argument is
formalized by the following,

######  Lemma 2.22 (Tight bound for random $\pm 1$ matrix).

Consider $G$ an $n\times n$ symmetric matrix with each off-diagonal entry
sampled i.i.d. from random $\pm 1$ entry. Assuming each $S/H$-step incurs at
most $2$ $R$-confusions, we can bound its block-value function by

$B_{q}(G)\leqslant(1+o_{n}(1))\cdot 2\sqrt{n}\,,$

for $q\ll n^{O(1)}$. As a corollary, with probability at least $1-o_{n}(1)$,
we have $\|G\|\leqslant(1+o_{n}(1))\cdot 2\sqrt{n}$. This bound is tight even
in the leading constant.

###### Proof.

Identical to above, we focus on the vertex factors, and consider the step-
label when we traverse the walk from left to right (i.e. from $U_{\alpha}$ to
$V_{\alpha}$).

  1. 1.

$F$-step: the left vertex cannot be making its first appearance by definition,
and it cannot be last appearance as otherwise the edge appears only once
throughout the walk. The destination vertex is making a first appearance,
hence contributing a vertex-cost of $\sqrt{n}$;

  2. 2.

$S/H$-step: the left vertex cannot be making its first appearance by
definition, and it cannot be last appearance as otherwise the edge appears
only once throughout the walk. The destination vertex is making a middle
appearance, hence can be specified by a cost of $2q$. Moreover, under our
assumption that each $S/H$ step incurs at most $2$ $R$-confusions, each of
which can be specified by label in $2q$, we have a total cost of

$\underbrace{2q}_{\text{destination of $S$
step}}\cdot\underbrace{(2q)^{2}}_{\text{destination of potential
R-confusions}}\ll\sqrt{n}$

  3. 3.

$R$-step: the vertex on the left boundary is potentially making a last
appearance, hence contributing a vertex-cost of at most $\sqrt{n}$; the right
vertex cannot be making its first appearance as the edge appears in prior
steps, and the vertex is not making its last appearance by definition.

  4. 4.

Summing the above, we can bound
$B_{q}(G)\leqslant\sqrt{n}+(2q)^{3}+\sqrt{n}\leqslant(1+o_{n}(1))\cdot
2\sqrt{n}$ by setting $q=\operatorname{polylog}n$.

∎

######  Remark 2.23.

In our general analysis, we will utilize that a bound $O(1)$ in the exponent
of $q$ would have sufficed for us in the above argument.

The key to the argument above is that each $S/H$ step incurs at most $2$
different $R$-confusions. We note that this is where our machinery departs
from a completely ”local” argument, which allows us to improve from prior
bounds for graph matrices. On a high level, a key component of our analysis
relies upon showing _return-is-fixed_ , i.e., there are $O(1)$ choices for the
destination of an $R$-step, and our machinery follows a rule of thumb inspired
by the above example,

”If the walk gets too messy to encode, there must be “savings” in the
combinatorial factor from previous blocks, that allows us to encode auxiliary
information for decoding.”

To exploit the loss in previous steps, it is no longer sufficient for us to
_narrowly_ consider a single local step. Towards this end, we employ a global
potential function argument to identify the source of such loss throughout the
walk, and more importantly, we incorporate the global potential function into
our local block-value bound such that our machinery is ultimately a ”local”
argument. In particular, the only ”global” component of our argument is
establishing the assumption that _each $S/H$ step incurs at most $2$
$R$-confusions_, and its further generalizations to other steps that come with
_gaps_ when compared with the dominant block-step (a.k.a. _maximal-value
labeling_).

##### Further challenges from ultra-sparsity

The above showcases the bulk of our ideas while extra care is required for our
applications for _ultra_ -sparse random graphs. To illustrate these
challenges, we will use line-graph as an running example and showcase the new
ideas needed to migrate the local analysis to sparse random graphs.

For the following discussions, let $M_{G}$ be an $n\times n$ symmetric matrix
with each entry an independent sample from the $p$-biased distribution. For
readers familiar with the $O(\sqrt{d})$ spectral radius bound for sparse
random graph with average degree-$d$, the desired bound translates into a
bound of $O(\sqrt{n})$ under the $p$-biased basis. That said, our goal is to
recover an $O(\sqrt{n})$ bound for the following ”shape” within our machinery.

##### Handling singleton edges due to pruning and conditioning

For staters, one immediate challenge from the ultra-sparse regime is that we
are not working directly with a genuine random graph sample in which each edge
is an independent sample: instead, we work with random graphs with pruned
vertices, as well as conditioning on the event of $2$-cycle-free subgraphs.
With this alternative distribution, we need to take into account of
_singleton_ edges, since it is no longer true the $p$-biased character has
mean-$0$, as opposed to typical trace-method calculation for mean-$0$ random
variable. This effect is manifest within our framework when we consider a
singleton $F$-step. To illustrate the challenge posed by singleton edges, we
first formally describe our edge-factor assignment scheme, inspired by the
previous work of [JPR+22].

For each random variable $x$, 1. $F$-step: for the first time the random
variable appears, • $\mathsf{Singleton}$: for random variable $x$ that appears
only once throughput the walk, we assign a factor
$\sqrt{\frac{n}{d}}\cdot\frac{d}{n}\cdot\mathsf{Singdecay}$ for
$\mathsf{Singdecay}\leqslant\exp(-d)$; • $F$: for random variable $x$ that
appears at least twice throughout the walk, this gets assigned a factor of
$1$; 2. $H$-step: we assign a factor of
$\sqrt{\frac{1-p}{p}}\approx\sqrt{\frac{n}{d}}$. 3. $R$-step: we assign a
factor of $1$.

At this point, we would like to emphasize that the key to handling singleton
edges is that we are able to identify $\mathsf{Singdecay}$, an extra decay
term coming from edge-value for each singleton edge, which we call _singleton-
decay_. Furthermore, we show $\mathsf{Singdecay}\ll\exp(-d)$, providing us
with enough slack to offset potential combinatorial blow-up from singleton
edges. To highlight the importance of this extra decay term, we consider the
local block-value for a singleton $F$ step within our framework.

Hypothetically, suppose there is no singleton decay, we consider the block-
step value for the singleton step: the source vertex may be now be making a
last appearance, while the destination vertex may be making as well its first
appearance. This shall be contrasted with the non-singleton $F$ case in which
we pick up only one first appearance factor. Combining the above, we pick a
factor of

$\underbrace{\sqrt{n}}_{\begin{subarray}{c}\text{redistributed vertex cost}\\\
\text{ for the destination's first
appearance}\end{subarray}}\cdot\underbrace{\sqrt{n}}_{\begin{subarray}{c}\text{redistributed
vertex cost}\\\ \text{ for the source's last
appearance}\end{subarray}}\cdot\underbrace{\sqrt{\frac{n}{d}}\cdot\frac{d}{n}}_{\text{singleton-
edge value without decay}}=\sqrt{nd}\,.$

Notice that this yields a block value of $\sqrt{nd}$, which gives us a bound
equivalent to the simple row-sum bound. That said, it is crucial to improve
the above analysis for singleton step, and in this case, it is clear that the
extra decay of $\mathsf{Singdecay}\leqslant\exp(-d)$ comes in handy, and
allows us to bound the above by $\sqrt{n}$ as desired.

The key technical lemma concerning this component is to show the above is a
valid assignment scheme, i.e., we indeed pick up extra decay by unpacking the
trace-bound for singleton edges. The proof is deferred to the appendix in
Section A.1.

######  Proposition 2.24 ( Proposition A.12).

The above is a valid edge-value assignment scheme.

##### Challenges from unbounded higher-order moments

Another challenge due to ultra-sparsity is that $p$-biased character has
unbounded higher moment. In our edge-value assignment scheme described above,
each $H$-step gets assigned a value of
$\sqrt{\frac{1-p}{p}}\approx\sqrt{\frac{n}{d}}$ and this poses extra
challenges for our previous argument of each $S/H$ step incurring at most $2$
$R$-confusions. In particular, we can no longer afford each $H$ edge incurring
unforced return since it no longer comes with any extra gap. We address this
issue by improving upon the unforced-return bound, and show that each $H$-step
does not incur any $R$-confusion in Section 3.2.

Besides the effect of $H$-steps on $R$-confusion, we also need to be careful
in our encoding for destination of an $H$-step. In particular, even though
each vertex has degree at most $c_{trunc}\cdot d$ under the pruned subgraph, a
cost of $O(d)$ is still too much for specifying the destination of an
$H$-step. Again, we illustrate this issue by zooming into the block-step
analysis for an $H$-step. With a naive bound of $O(d)$, observe that we would
pick up a factor of

$O(d)\cdot\sqrt{\frac{n}{d}}=O(\sqrt{nd})$

once combined with the edge-value. This is again a trivial bound comparable to
a row-sum bound, however, it also prompts us to improve the encoding cost from
$O(d)$ to $O(\sqrt{d})$ for the desired block-value of $O(\sqrt{n})$. In
particular, we show that

######  Proposition 2.25.

A cost of $O(\sqrt{d})$ is sufficient for identifying the destination of an
$H$-step.

To show that a cost of $\sqrt{d}$ is sufficient, we crucially rely upon the
assumption that the random graph sample is $2$-cycle free in any
$\Omega(\log_{d}n)$-radius neighborhood. This is further discussed in Section
2.6.2 and Section 3.8. The underlying idea also hinges upon another crucial
observation for vertex factors, that there are occasions the cost of
$O(\sqrt{d})$ may even be spared. To identify such vertices, we make the
following formal definition,

######  Definition 2.26 (Doubly constrained).

We call a vertex $v$ doubly constrained by a set of vertices $S$ if there is a
path between $i,j\in S$ that passes through $v$.

######  Proposition 2.27 (Informal: doubly-constrained vertices are fixed).

Any vertex that is doubly-constrained by a set of known vertices via $H$ steps
can be identified at a cost of $O(1)$.

Combining the above components together, we are ready to introduce our desired
vertex-factor assignment scheme,

Each vertex requires a label in $[n]$ when it first appears. We redistribute
factors as follows: 1. Assign a $\sqrt{n}$ factor to the block-step in which
the vertex first appears; 2. For any middle appearance, • if it is arrived via
an $S$ step: assign the corresponding $\mathsf{Pur}$ cost and the cost of
specifying the vertex (which is again at most $2|V(\alpha)|q$); • if it is
arrived via an $H$ step and it is not doubly constrained: assign a cost of
$O(\sqrt{{d}})$; • if it is reached via an $R$ step or it is doubly
constrained by an $H$-path: assign a cost of $O(1)$; 3. Assign a $\sqrt{n}$
factor to the block-step in which the vertex last appears.

There are several other technical challenges that arise once we start working
with more complicated graph matrices and with matrices that are a sum of a
collection of shapes as opposed to a single shape. We defer these discussions
to the latter part after we introduce the connection between vertex separators
and matrix norm bounds. However, with the ideas already highlighted, we are
already able to recover the desired $O(\sqrt{n})$ bound for the line-graph and
even get tight norm bounds for some less trivial graph matrices.

###  2.2 Toy examples for sparse matrix norm bounds

######  Lemma 2.28 (Tight bound for scaled adjacency matrix/line graph for
$G_{n,d/n}$).

Let $G$ be a random graph sample from $G_{n,d/n}$, and let $M_{G}$ be its
corresponding matrix in the $p$-biased basis once vertices of degree more than
$c_{trunc}\cdot d$ are pruned away. Conditioning on the event $G$ has
$2$-cycle free radius at least $\kappa=\Omega(\log_{d}n)$, we can bound the
block-value by

$B_{q}(M_{G})\leqslant O(\sqrt{n})$

for $q\ll n^{O(1)}$. As a corollary, conditioned on the event of $2$-cycle
free radius being $\Omega(\log_{d}n)$, with probability at least
$1-o_{n}(1))$, we have $\|M_{G}\|\leqslant O(\sqrt{n})$ where $O(\cdot)$ hides
some absolute constant independent of $d$ .

###### Proof.

We analyze the block-value by assuming the technical lemmas highlighted in the
above section. Again, we start by casing on the step-label, and assume we are
traversing from left $(U_{\alpha})$ to right $(V_{\alpha})$.

  1. 1.

Singleton-$F$ step: the vertex on the left boundary may be making last but not
first appearance, and the vertex on the right boundary may be making first but
not last appearance. The edge is a singleton edge that gets assigned a value
of $\sqrt{\frac{n}{d}}\cdot\frac{d}{n}\cdot\mathsf{Singdecay}$, combining the
above gives,

$\sqrt{n}^{2}\cdot\sqrt{\frac{n}{d}}\cdot\frac{d}{n}\cdot\mathsf{Singdecay}\leqslant\sqrt{n}\cdot\exp(-d)\,;$

  2. 2.

Non-singleton $F$ and $R$ step: this is identical to their analogs in the
warm-up example of random $\pm 1$ matrix, and gets a value of $\sqrt{n}$ each;

  3. 3.

$H$-step: neither vertices are making first nor last appearances. Since it
does not incur $R$-confusions, we do not incur any cost of $2q$ (to be
contrasted with the warm-up example). Moreover, a cost of $O(\sqrt{d})$ is
sufficient to identify the destination, combining with the edge value gives us
a bound of

$O(\sqrt{d})\cdot\sqrt{\frac{n}{d}}=O(\sqrt{n})\,;$

  4. 4.

$S$-step: this is identical to the analog in warm-up example, and gives a
value of $(2q)^{3}$;

  5. 5.

Summing the above gives us a bound of $O(\sqrt{n})$.

∎

##### Z-shape: an entry-level graph matrix

Now that we have seen how this strategy applies to arguably the most familiar
case of the adjacency matrix, we will now power up the above machinery with
the Z-shape matrix as illustrated in the following diagram.

Figure 3: Z-shape
$M_{Z}[(i,j),(k,\ell)]=\chi_{G}(i,k)\cdot\chi_{G}(j,k)\cdot\chi_{G}(j,\ell)$

As defined, $M_{Z}$ is a matrix in dimension $n(n-1)\times n(n-1)$, and has
its rows/columns indexed by ordered pairs of vertices in $[n]$.

######  Lemma 2.29 (Norm bound for $Z$-shape).

We can take the block-value of $Z$ shape to be

$B_{q}(M_{Z})\leqslant O(\sqrt{n}^{2}\cdot\sqrt{\frac{n}{d}})$

As a corollary, with probability at least $1-o_{n}(1)$, we have
$\|M_{Z}\|\leqslant O\left(\sqrt{n}^{2}\cdot\sqrt{\frac{n}{d}}\right)$.

###### Proof.

Generalizing from the walk for the adjacency matrix, for the Z-shape, we
consider a step in the walk starting from $U_{\alpha}$ and analyze the factor-
assignment scheme introduced above.

  1. 1.

Observe that $i,j$ cannot be making their first appearance since they are on
the left boundary, and $k,\ell$ cannot be making their last appearance since
they are on the right boundary;

  2. 2.

For simplicity, we ignore the case of singleton edges as they are analogous to
the previous case;

  3. 3.

If vertex $k$ is new, we pick up at most a factor of $\sqrt{n}$ for the vertex
factor from $k$, and an $O(1)$ factor of $\mathsf{Pur}$ since one of the edges
$(i,k),(j,k)$ is a surprise visit; since both are non-singleton $F$ edges,
$i,j$ do not contribute vertex factors as they are not making their last
appearances; we pick up at most another factor of $\sqrt{n}$ from $\ell$ when
$j$ is making a middle appearance (either via an $F$ edge to $\ell$, or an $H$
edge). This combines to a factor of $\sqrt{n}^{2}q^{O(1)}$ for
$q\sim\log^{2}n$.

  4. 4.

If vertex $k$ is old, i.e., making a middle appearance,

     * •

In the case $(i,k)=R,(j,k)=H$, $i$ contributes a factor of $\sqrt{n}$ from its
last appearance, and the edge $(i,j)$ is ”fixed” when called upon from $i$ and
hence does not contribute any factor; the edge $j,k$ contributes a factor of
$\sqrt{\frac{n}{d}}$ and no vertex factor since $k$ has already been
identified from the $R$ edge on $(i,j)$; this combines to a total of
$\sqrt{n}^{2}\cdot\sqrt{\frac{n}{d}}$ assuming $\ell$ is making its first
appearance (similar to the case in adjacency matrix), and this is the dominant
term;

     * •

For the case of $(i,k)=H,(j,k)=R$, it is almost analogous, and we pick up at
most a factor of $\sqrt{\frac{n}{d}}$ from the $H$ edge, and $k$ is identified
for free since it is reached by an $R$ edge;

     * •

However, we need to further case on whether $j$ is making its last appearance,
if not, $\ell$ may be new and contributes a factor of $\sqrt{n}$ (either via
vertex factor, or $H$ edge-value combined with vertex factor of $\sqrt{d}$),
and this gives a total of $\sqrt{n}\cdot\sqrt{\frac{n}{d}}$.

     * •

In the case where $j$ is making its last appearance, there is no vertex factor
from $j$ and $\ell$ cannot be new, hence, it does not contribute a factor of
$\sqrt{n}$ (notice $(j,\ell)$ must be $R$). This combines to a total of
$\sqrt{\frac{n}{d}}$ (notice the tremendous gap from
$\sqrt{n}^{2}\sqrt{\frac{n}{d}}$ even though there may not be any surprise
visit locally);

     * •

In the case both $(i,k),(j,k)$ are $H$ edges, we observe that vertex $k$ can
be identified at a cost of $\sqrt{d}$ and we additionally pick up an edge-
value of $\sqrt{\frac{n}{d}}^{2}$ from two $H$ edges; moreover, we may pick up
an extra factor of $\sqrt{n}$ from $\ell$ since $j$ is making a middle
appearance; that said, this combines to a factor of
$\sqrt{\frac{n}{d}}^{2}\cdot\sqrt{n}\cdot O(\sqrt{d})\leqslant
O(\sqrt{\frac{n}{d}}\sqrt{n}^{2})$.

  5. 5.

Summing over the above choices gives us a bound of
$O(\sqrt{n}^{2}\cdot\sqrt{\frac{n}{d}})$ as there are $O(1)$ step-labelings.

∎

It should be pointed out that this toy example conveys an essential feature
coming from our edge-value assignment scheme: despite the lucrative vertex
factor of $n$ for a new vertex, it is not always optimal to go to one!
Moreover, we want to emphasize this is a local argument as we are traversing
the walk and deciding the next step from the current boundary.

###  2.3 Recap of graph matrix norm bounds from prior works

Before we dig into our new results, we first travel back in time and remind
the reader of what is known about graph matrix norm bounds previously. The
discovery of vertex-separator being the combinatorial quantity that controls
spectral norm bounds of graph matrices was first identified in the
investigation of the planted clique problem for $G_{n,1/2}$,

######  Definition 2.30 (Vertex-separator).

Given a shape $\alpha$, we call $S$ a vertex-separator for $\alpha$ if all
path between $U_{\alpha}$ (the left boundary) and $V_{\alpha}$ (the right
boundary) contain at least one vertex in $S$.

######  Theorem 2.31 (Informal statement of dense norm bounds [AMP20, RT23] ).

For a shape $\alpha$, with high probability over the choice of underlying
random graphs from $G_{n,1/2}$, the following bound holds,

$\|M_{\alpha}\|\leqslant\tilde{O}\left(\max_{S:\text{separator for
}\alpha}\sqrt{n}^{|V(\alpha)\setminus S|}\cdot\sqrt{n}^{iso(\alpha)}\right)$

and more specifically, $\tilde{O}$ hides polylogarithmic factors of
$\operatorname{polylog}(n)$ in the dimension, and _polynomial_ factor
dependence $\operatorname{poly}(|V(\alpha)|)$ in the size of the shape (which
is presumed to be $\tilde{O}(1)$ as the size of shape is limited to
$\operatorname{poly}\log(n)$ for planted cliques).

More recently, the above bound has been extended into the somewhat sparse
regime when $d=\Omega(\operatorname{poly}\log n)$,

######  Theorem 2.32 (Informal statement of sparse norm bounds [JPR+22, RT23]
).

For a shape $\alpha$, with high probability over the choice of underlying
random graphs from $G_{n,d/n}$, the following bound holds,

$\|M_{\alpha}\|\leqslant\tilde{O}\left(\max_{S:\text{separator for
}\alpha}\sqrt{n}^{|V(\alpha)\setminus
S|}\cdot\left(\sqrt{\frac{n}{d}}\right)^{E(S)}\cdot\sqrt{n}^{iso(\alpha)}\right)$

with $\tilde{O}$ hiding the identical polylog dependence on $n$ and polynomial
factor in the size of shape as the previous version.

One may notice that the above bound in fact continues to hold in the ultra-
sparse regime of $d=O(1)$, however, these bounds become less meaningful here
due to the loss of $\operatorname{polylog}$ factors that render the bound
comparable, if not inferior, to the naive bound from a row-sum bound, losing
the usual _square-root_ gain.

Although the norm bound falls short in the regime we are interested in due to
polylog factors, the prior works indeed carry an important message about the
polynomial-factor dependence.

  1. 1.

Each vertex outside the separator contributes a factor of $\sqrt{n}$ (if not
isolated);

  2. 2.

And in the sparse regime, each edge inside the separator contributes a factor
of $\sqrt{\frac{n}{d}}$.

A starting question for our sparse norm bounds is whether these leading-
factors continue to be the only dominant terms in the ultra-sparse regime, or
whether they get overwhelmed by the ”prior” lower-order dependence such as the
polylog factors. On a high level, we resolve the question with the following
answer,

  1. 1.

The above two factors are indeed the only dominant terms even in the ultra-
sparse regime;

  2. 2.

Most lower-order dependence is unnecessary while some lower-order dependence
of $\operatorname{polylog}(n)$ factors is needed for shapes due to floating
and dangling structures.

###  2.4 Our main theorems for graph matrix norm bounds

To enable us to obtain a more fine-grained understanding of the spectral
behavior graph matrices, it turns out to be crucial that we give a more
detailed decomposition of each component in a shape, as they are now the
determining factor for matrix norm bounds below $\operatorname{polylog}$ order
dependence that has been overlooked in prior works.

######  Definition 2.33 (Floating vertex, and floating component).

For a given shape $\alpha$, we call a connected component $Q\subseteq
V(\alpha)$ a floating component if $Q$ is not connected to $U_{\alpha}\cup
V_{\alpha}$. For each floating component, we arbitrarily pick a vertex to be
the first vertex of the component in the encoding. Let
$E_{\alpha}(\mathsf{float})\subseteq E_{\alpha}$ be the set of edges in a
floating component.

######  Definition 2.34 (Floating factor).

We use $\mathsf{float}(\alpha)$ to capture the extra overhead for norm bounds
due to floating components.

######  Definition 2.35 (Dangling and non-dangling vertex).

For a given shape $\alpha$, we call a vertex $v\in V(\alpha)$ a ”dangling”
vertex if it is not on any simple path from $U_{\alpha}$ to $V_{\alpha}$;
otherwise, we call the vertex ”non-dangling”.

######  Remark 2.36.

Note that any vertex of degree $1$ outside $U_{\alpha}\cup V_{\alpha}$ is a
dangling vertex.

The following is an example of a shape with a dangling vertex.

Figure 4: Line-graph with a dangling vertex
$M_{dang}[u,v]=\sum_{t_{1},t_{2}\neq
u,v}\chi_{G}(u,t_{1})\cdot\chi_{G}(v,t_{1})\cdot\chi_{G}(t_{1},t_{2})$

######  Definition 2.37 (Dangling branch).

Given a shape $\alpha$, for any non-dangling vertex $v$ incident to dangling
vertices, consider the collection of dangling-vertices reachable from $v$
without passing through any other non-dangling vertex, by possibly removing
excess edges that lead to visited vertices, this is a tree of dangling-
vertices rooted at $v$, and we can pick an arbitrary order to go through the
leaves, and identify a tree-path to the leaf such that each path-segment is a
branch whose

  1. 1.

branch-head is either a vertex in some previously identified branch or $v$;

  2. 2.

branch-tail is a leaf.

Moreover, we write $\mathsf{branch}(\alpha)$ as a collection of dangling
branches in $\alpha$.

######  Definition 2.38 (Dangling factor).

We use the factor $\mathsf{dangling}(\alpha)$ to capture the extra overhead
for norm bounds due to dangling branches.

######  Remark 2.39.

For clarity, the reader should keep in mind the example where each non-
floating degree-$1$ vertex in $V(\alpha)\setminus U_{\alpha}\cup V_{\alpha}$
is dangling and a branch-tail.

For some $\delta>0$, for any shape $\alpha$ with $|V(\alpha)|\leqslant
n^{\delta}$, we obtain the following theorems,

######  Theorem 2.40 (User-friendly version without dangling/floating
vertices).

Given a shape $\alpha$ with no floating or dangling component, we define

$\displaystyle
B_{q}(\alpha)=\max_{S:\text{separator}}c_{\mathsf{norm}}^{|V(\alpha)|}\cdot
c_{\mathsf{norm}}^{|E(S)|}\cdot\sqrt{n}^{|V(\alpha)\setminus
S|}\left(\sqrt{\frac{n}{d}}\right)^{|E(S)|}\sqrt{n}^{|I(\alpha)|}$

where $c_{\mathsf{norm}}>2$ is an absolute constant independent of $d$ and
$\alpha$ and $I(\alpha)$ is the set of isolated vertices in $\alpha$ outside
$U_{\alpha}\cup V_{\alpha}$.

Recall that $1_{{\mathcal{E}}}$ is the indicator function for $G$ having
2-cycle free radius at least $\kappa=0.3\log_{d}n$. For any $\epsilon>0$, and
for any $q=\Omega(\sqrt{|U_{\alpha}||V_{\alpha}|}\log^{2}n)$ and $q\leqslant
n^{O(\delta)}$,

$\mathbb{E}_{G}\left[\Tr\left((M_{\alpha}M_{\alpha}^{T})^{q}\right)\cdot
1_{{\mathcal{E}}}\right]\leqslant\bigg{(}(1+\epsilon)B_{q}(\alpha)\bigg{)}^{2q}$

where $G$ is sampled from $G_{n,d/n}$ with high-degree vertices (degree at
least $d=c_{\text{trunc}}\cdot d$) removed.

As a corollary, with probability at least $1-o_{n}(1)$ ,

$\|M_{\alpha}\|\leqslant(1+\varepsilon)\cdot B_{q}(\alpha)\,.$

######  Theorem 2.41 (Full-power).

Given a shape $\alpha$, letting $\mathsf{float}$ be the floating factor and
letting $\mathsf{dangling}(\alpha\setminus S)$ be dangling factor outside the
separator $S$, we define

$\displaystyle B_{q}(\alpha)$
$\displaystyle=\max_{S:\text{separator}}c_{\mathsf{norm}}^{|V(\alpha)|}\cdot
c_{\mathsf{norm}}^{|E(S)|}\cdot\sqrt{n}^{|V(\alpha)\setminus
S|}\left(\sqrt{\frac{n}{d}}\right)^{|E(S)|}\sqrt{n}^{|I(\alpha)|}\cdot\mathsf{dangling}(\alpha\setminus
S)\cdot\mathsf{float}(\alpha)$

where $c_{\mathsf{norm}}>2$ is an absolute constant independent of $d$ and
$\alpha$, $F(\alpha)$ is the collection of floating components in $\alpha$,
$\mathsf{branch}(\alpha\setminus S)$ is the collection of dangling branches
outside the separator, and $I(\alpha)$ is the set of isolated vertices in
$\alpha$ outside $U_{\alpha}\cup V_{\alpha}$.

Additionally, the dangling/floating factor are bounded by the following,

$\mathsf{dangling}(\alpha\setminus
S)\leqslant\prod_{i\in\mathsf{branch}(\alpha\setminus
S)}\min(\sqrt{2|V(\alpha)|q},\sqrt{d}^{|\mathsf{branch}(i)|})\,,$

and

$\mathsf{float}(\alpha)\leqslant\prod_{C_{i}\in
F(\alpha)}\max\left(2|V(\alpha)|q_{\alpha},\sqrt{n}\cdot\mathsf{Singdecay}^{|E(C_{i})|}\cdot
1_{V(C_{i})\cap S=\emptyset}\right)\,,$

For any $\epsilon>0$, and for any
$q=\Theta(\sqrt{|U_{\alpha}||V_{\alpha}|}\log^{2}n)$ and $q\leqslant
n^{O(\delta)}$, we have the following bound

$\mathbb{E}_{G}\left[\Tr\left((M_{\alpha}M_{\alpha}^{T})^{q}\right)\cdot
1_{{\mathcal{E}}}\right]\leqslant\bigg{(}(1+\epsilon)B_{q}(\alpha)\bigg{)}^{2q}$

where $G$ is sampled from $G_{n,d/n}$ with high-degree vertices (degree at
least $c_{degree}\cdot d$) removed.

As a corollary, with probability at least $1-o_{n}(1)$,

$\|M_{\alpha}\|\leqslant(1+\varepsilon)\cdot B_{q}(\alpha)\,.$

######  Remark 2.42.

Throughout this work, we will pick $q=c(|U_{\alpha}||V_{\alpha}|)\log^{2}n$
for any shape $\alpha$.

######  Remark 2.43.

For the purpose of our application in Sum-of-Squares lower bounds in this
work, a size bound of $|V(\alpha)|\leqslant O(\log^{2}n)$ already suffices as
we truncate at $|V(\alpha)|\leqslant c\cdot d_{sos}\log n$. However, we state
the stronger bound here as we would like to emphasize that the norm bound
analysis is crucially no longer the bottleneck for proving SoS lower bounds
anymore, even in the _ultra-sparse_ regime.

######  Remark 2.44.

The bottleneck of our probabilistic norm bound concentration comes from the
conditioning of a random graph sample having 2-cycle free radius at least
$\kappa=0.3\log_{d}n$. Conditioned on that event, our bound holds with
probability at least $1-n^{-100}$, and can be readily strengthened to
$1-n^{-\omega(1)}$.

As a careful reader may point out that in the user-friendly version of our
result, the block-value bound $B_{q}$ despite being stated with dependence in
$q$, does not ultimately depend on $q$. However, the final bound in the full-
power version does have dependence in $q$. We opt to keep the notation $B_{q}$
for consistency. On the other hand, we would like to emphasize that the
dependence on $q$ factor is the usual ”log”-factor for random matrix norm
bounds, and our main result reveals that the exact dependence on $q$ can be
improved for a large family of shapes, though some dependence is also
necessary for specific shapes due to special structural properties which we
call ”dangling” and ”floating”.

######  Example 2.45 (Shape with log factors).

Consider the following shape of a single floating triangle with
$|U_{\alpha}|=|V_{\alpha}|=|U_{\alpha}\cap V_{\alpha}|=1$, i.e. this is a
diagonal matrix with entries

$M[i,i]=\sum_{\text{injective
}\phi(a,b,c)\in[n]\setminus\\{i\\}}\chi_{G}(\phi(a),\phi(b))\cdot\chi_{G}(\phi(b),\phi(c))\cdot\chi_{G}(\phi(a),\phi(c))$

for any i.

Applying our main theorem to this shape gives a norm bound of $\|M\|\leqslant
O(1)\cdot\sqrt{n}^{3}\log^{2}n$ as the separator is mandatory as
$U_{\alpha}=V_{\alpha}$, and we pick up an extra floating factor of
$q=O(\log^{2}n)$. Note that some log factor here is needed as for any fixed
diagonal, the entry is a sum of mean $0$ and variance $\Theta(n^{3})$, and we
are looking for a bound that holds with probability $1-o_{n}(1)$.

Figure 5: Floating triangle

######  Remark 2.46.

For our application, for shapes with floating and dangling factors, we do not
optimize for the tight polylog dependence (or generally, dependence in $q$)
once they are present.

###  2.5 Bridging vertex separator, step-labeling and norm bound

In the following section, we will show how we rediscover the polynomial
dependence as predicted from prior norm bounds in the ultra-sparse regime,
especially in the context of our new technique via step-labeling. We first
remind the reader that our main theorem (using the vanilla version) gives the
following bound for any shape $\alpha$,

$\displaystyle
B_{q}(\alpha)=\max_{S:\text{separator}}c_{\mathsf{norm}}^{|V(\alpha)|}\cdot
c_{\mathsf{norm}}^{|E(S)|}\cdot\sqrt{n}^{|V(\alpha)\setminus
S|}\left(\sqrt{\frac{n}{d}}\right)^{|E(S)|}\sqrt{n}^{|I(\alpha)|}$

Let’s now zoom back into the examples that we just discuss, and see how the
previous bound may fall out of an application of the main theorem in its full
generality. We first consider the following construction of vertex-separators
from the edge-labeling for the upcoming block,

  1. 1.

Include any vertex incident to both _non-singleton_ $F$ and $R$ edges into
$S$;

  2. 2.

Include any vertex in $U_{\alpha}$ incident to some _non-singleton_ $F$ edge
into $S$;

  3. 3.

Include any vertex in $V_{\alpha}$ incident to some $R$ edge into $S$;

  4. 4.

Include any vertex incident to an $H$ edge into $S$.

Figure 6: Line-graph
$M_{line}[u,v]=\chi_{G}(u,v)$

Figure 7: Z-shape
$M_{Z}[(i,j),(k,\ell)]=\chi_{G}(i,k)\cdot\chi_{G}(j,k)\cdot\chi_{G}(j,\ell)$

##### Adjacency matrix revisited

In the case of adjacency matrix, the maximal-value edge-labeling is either a
(non-singleton) $F$ or an $R$ edge, in which case, one (but not both) of the
vertices is included into the separator, while the other vertex remains
outside and thus gives a factor of $\sqrt{n}$. In the case of $H$ edges, we
note that this can be reduced into the $F/R$ case by turning the edge into an
$F/R$ which yields the same block-value while we now have exactly one vertex
outside the separator again. As a result, in all these edge-labelings, there
is a vertex separator either $u\in U_{\alpha}$ or $v\in V_{\alpha}$ that can
be constructed and the block-value is dictated by the corresponding vertex
separator: each vertex outside the separator continues to contribute a factor
of $\sqrt{n}$ as they do in the dense case. In this case, applying the main
theorem gives a bound of

$\displaystyle
B_{q}(M_{line})=\max_{S:\text{separator}}c_{\mathsf{norm}}^{|V(\alpha)|}\cdot
c_{\mathsf{norm}}^{|E(S)|}\cdot\sqrt{n}^{|V(\alpha)\setminus
S|}\left(\sqrt{\frac{n}{d}}\right)^{|E(S)|}\sqrt{n}^{|I(\alpha)|}=c_{\mathsf{norm}}^{3}\cdot\sqrt{n}=O(\sqrt{n})$

#####  $Z$-shape revisited

The example of adjacency matrix, despite its simplicity, falls short in
conveying another important message that each edge inside the separator
contributes a factor of $\sqrt{\frac{n}{d}}$. However, this phenomena has
already manifested itself in the $Z$-shape matrix. Following the dominant
edge-labeling in the $Z$ shape that gives labels $R,H,F$ to all three edges
from top to bottom, the separator is thus given by $(j,k)$ and the edge inside
contributes a factor of $\sqrt{\frac{n}{d}}$ while the two vertices outside
contribute a factor of $\sqrt{n}$ each.

In this case, applying the main theorem gives a bound of

$\displaystyle
B_{q}(M_{Z})=\max_{S:\text{separator}}c_{\mathsf{norm}}^{|V(\alpha)|}\cdot
c_{\mathsf{norm}}^{|E(S)|}\cdot\sqrt{n}^{|V(\alpha)\setminus
S|}\left(\sqrt{\frac{n}{d}}\right)^{|E(S)|}\sqrt{n}^{|I(\alpha)|}=O\left(\sqrt{n}^{2}\cdot\sqrt{\frac{n}{d}}\right)$

##### Singleton edges affecting the separator?

It should be acknowledged that the idea of vertex separators falls slightly
short in capturing the potential effect due to singleton edges. In the prior
settings, any edge that appears only one throughout the walk would immediately
zero out the contribution from the particular walk as this is taking
expectation over symmetric random variables with mean $0$. However, this is
not true in our ultra-sparse setting since we apply conditioning on the degree
boundedness of each vertex and the absence of dense subgraph, which
unfortunately destroys the perfect balance of the random variable- it is no
longer mean $0$. That said, as we observe in the previous examples, the bound
continue to hold as long as we get a singleton decay that is at most
$\frac{1}{\sqrt{d}}$. Put in the context of vertex separators, this reveals
that despite the fact that the above construction of $S$ from any edge-
labeling does not immediately produce a vertex separator for the shape, its
value may still be bounded if we can consider an alternate edge-labeling that
1) yields a higher block-value, and 2) corresponds to an honest vertex
separator of the shape if it does not contain any singleton edge.

In our main technical analysis, we show that this is indeed true for
components that are connected to $U_{\alpha}$ and $V_{\alpha}$, while
singleton edges do indeed have a non-trivial influence when the shape contains
floating components, in particular, tree-like floating components. Fortunately
in our setting for SoS lower bounds, this turns out to influence a collection
of shapes that are previously already ”small” in norm, and thus, does not pose
qualitively significant differences for our application.

#####  $R-H-F$ structure lemma

More than just illustrating the power of our factor assignment scheme, these
two examples we showcase above may also serve for the broader theme in
exposing the connection between step-labeling and vertex separator, and
ultimately how this connection enables us to obtain tight norm bounds. As a
by-product of our analysis that proceeds by understanding the status of each
edge, as opposed to simply by casing on the status of each vertex whether
inside the separator, we in fact obtain a more fine-grained understanding of
how a walk that maximizes the norm should behave. This is encapsulated in the
following structure lemma that we discover. For the clarify of presentation,
we restrict our attention to the most interesting collection of shapes that do
not contain floating and dangling component, while it can be extended to
capture those shapes in a straightforward fashion.

######  Lemma 2.47 (Structure lemma for graph matrix (See formal discussion in
Section 4.2.1)).

Given a shape $\alpha$, and for a fixed separator $S$ of $\alpha$, fix the
traversal direction from $U_{\alpha}$ to $V_{\alpha}$, the maximum-edge-
labeling is given by

  1. 1.

Label each edge that can be reached from $U_{\alpha}$ without passing through
$S$ an $R$ edge;

  2. 2.

Label each edge inside the separator an $H$ edge;

  3. 3.

Label each edge that can be reached from $V_{\alpha}$ without passing through
$S$ an $F$ edge.

As evident in the two examples we showcase, any $F$ edge before reaching the
separator in fact corresponds to a surprise visit so that we can immediately
improve the value locally by flipping it to an $R$ edge, assuming there is a
large enough gap created by surprise visits, which is
$2|V(\alpha)|q_{\alpha}\ll n^{\delta}$ for some tiny constant $\delta>0$
versus the $\sqrt{n}$ contribution if we avoid the surprise visit.
Analogously, any $R$ edge that is used after we pass through the separator
render a gap we can improve as flipping it to an $F$ edge can be shown to give
us an additional vertex contribution of $\sqrt{n}$. Finally, each edge in
$E(S)$, if turned to an $H$ edge from $F/R$, now contributes a factor of
$\sqrt{\frac{n}{d}}$ which again allows us to attain a higher block-value.

###  2.6 Overview of proof for unforced-return bounds and high-mul balance

At this point, it should be noted that there is an adjustment which we make to
this high-level picture. For the polynomial factors, it is most convenient to
have the $R$ edges be the last time the edge appears. However, for analyzing
the factors of $d$ and $q$, it is more convenient to instead have the $R$ edge
be the second time that the edge appears and have the subsequent appearances
be $H$ edges. We make this switch for the remainder of the analyzing vertex-
encoding-cost in the norm bound analysis. With this in mind, we now return to
fill in the technical details that we defer from the earlier section, in
particular,

Why can an $R$-step be specified in $O(1)$, i.e., why is an edge being used
the second-time forced?

and additionally,

Why is a cost of $\sqrt{d}$ sufficient to specify an $H$ edge, which has
already appeared $\geqslant 2$ times?

####  2.6.1 Forced-return bound

##### Starting from line-graph

To see that an edge being used the second-time is fixed, we may first trace
back to what happens if the walk takes place on a tree where things are
considerably simpler. In this case, each step in the walk either goes away
from the root or backtracks towards it, and moreover, each vertex has only $1$
edge which backtracks to the root (which is the edge that discovers the
vertex). If we further know that each edge appears only twice in the walk,
i.e., no branch is traversed repeatedly, then this is indeed the second-
appearance of the edge . As a result, return is forced if the walk proceeds on
a tree, or more generally, on an arbitrary graph where the walk proceeds in a
tree-like manner.

However, although a sparse random graph is locally tree-like, since we take a
long walk of length $q=\Theta(\log n)$, it is unrealistic for us to impose a
tree-like assumption on the walk. That said, to generalize the argument for
cycles, we observe that each cycle formed in the walk results from an edge
leading to a visited vertex, which we call a _surprise visit_ , and such an
edge can be much more succinctly encoded using a label in $q=\Theta(\log n)$
than its counterpart of a new edge leading to a new vertex. From this
perspective, the tremendous gap opened up prompts us to show that as long as
each surprise visit does not create ”too many” unforced-returns, as we we can
then use the gap from corresponding surprise visits to encode auxiliary data
so that each return, despite the possible confusion caused by surprise visits,
continues to be fixed.

Towards this end, we focus on how the number of unforced return legs from a
vertex $v$ may change if we depart and arrive back at the vertex again
assuming there is no $H$ edge involved in the walk and each edge appears at
most two times. Suppose we depart the vertex by using a new $F$ edge, the
subsequent arrival either closes an $R$ edge, or it is a surprise visit which
comes with a gap. Moreover, the subsequent surprise visit may see an increment
of at most $2$ unforced-return from the particular vertex $v$: with one being
the most recent departure $F$ edge, and another one being the surprise visit
in the current arrival. That said, each surprise visit can be used to charge
at most $2$ unforced-returns. This argument turns out to be surprisingly
powerful beyond the simple line-graph case, and this formalized in Section 3.3
and further extended to capture the influence from $H$ edges by considering
$H$-component as opposed to a single vertex.

##### Extending to branching vertices with mirror copy

The above argument addressees unforced-return restricted to vertices that push
out at most $1$ $F$ edge when it is on the boundary, however, this is not
always the case for graph matrices. For example, consider the middle vertex in
the following shape: fix the traversal from left to right, it pushes out $2$
edges in each block. For convenience, we call each such vertex a _branching_
vertex. They fall out of reach of the argument we outline above, and we indeed
need an upgraded argument to take into account of such vertices, as they are
also crucially why the graph matrix norm bounds in the dense setting is
governed by _Minimum Vertex Separator_ , i.e., the separator of the shape with
the fewest number of vertices.

It turns out that such vertices can be easily addressed, at least in the case
when apply trace-method for a single shape, since we know that each block of
$\alpha$ is followed by its symmetric copy $\alpha^{T}$ in the subsequent
block, and this enables us to use a completely local argument for
understanding the influences of such vertices.

For each branching vertex, look at its copy in the subsequent block, either
all the paths are mirror-copies of each other, or there is a surprise visit
(since locally we have cycles).

With the above observation, in the case each path is a mirror-copy of each
other, i.e., each path goes to the boundary and immediately backtracks, each
$F$ edge that gets opened up is immediately closed, and hence does not
contribute any confusion to unforced-returns. On the other hand, suppose some
path does not backtrack immediately, there is a surprise visit along the path
that can be assigned to _charge_ the corresponding confusion it may incur, and
we formalize this via the _missed-immediate-return_ function.

####  2.6.2 High-mul balance: $\sqrt{d}$ is sufficient for $H$-step

With the unforced return bound settled, we may now proceed to potentially the
last missing component to complete our matrix norm bounds for graph matrix of
a fixed shape. Under our bounded-degree graph assumption of the underlying
random graph sample, it is not immediately true that we only consider walks
such that each vertex has bounded degree. Throughout this section, for
convenience, let $d$ be the threshold of degree truncation. It is not true
that we constrain our walks to use at most $d$ edges for each vertex: in fact,
each vertex may have $q\sim\Theta(\operatorname{poly}\log(n))$ edges in the
walk, however, the bounded degree assumption allows us to deduce a decay
whenever some vertex has degree more than $d$: in particular, our edge-value
bound holds by assuming each edge appears in the random graph, and thus gives
a spike of $\sqrt{\frac{n}{d}}$. However, given the prior that some edge is
missing, we can in fact assign a decay for each edge that is missing, and
creates a tremendous gap as each non-edge contributes a factor of
$-\sqrt{\frac{d}{n}}$ instead. That said, it still suffices for us to assume
each vertex to be incident to at most $d$ edges in the walk.

However, this is not quite sufficient: for example, in the case of adjacency
matrix, this allows us to avoid a pessimistic bound of
$O(\operatorname{poly}\log n)$, while not entirely sufficient towards getting
a meaningful bound of $O(\sqrt{d})$, as a priori, a label in $[d]$ is needed
for each $H$ edge which would then lead to the trivial bound of $O(d)$
equivalent to a row-sum bound. That said, getting the extra square-root gain
is crucial in the ultra-sparse regime. We now restate the proposition from
earlier section,

######  Proposition 2.48 (Restatement of Proposition 2.25).

A cost of $\sqrt{c_{degree}\cdot d}=O(\sqrt{d})$ is sufficient for identifying
the destination of an $H$-step.

Towards this goal, we apply our conditioning that the graph has no
nearby-$2$-cycle at radius $c\log_{d}n$ for some constant $c>0$, and give a
potential-function argument for showing a cost of $\sqrt{d}$ is sufficient.
For the example of the adjacency matrix, assuming there is no surprise visit
involved (as otherwise we get an extra gap), we can split the walks into
intervals of at most $\frac{c}{2}\log_{d}n$. For each interval, suppose all
edges used throughout the interval have been revealed by the beginning of the
interval, it suffices for us to identify a label in $[q]$ that represents the
end of the interval, which is possible as we assume each edge has been
revealed. Since the walk is locally $2$-cycle free within the interval, a
label in $[2]$ is sufficient to identify the non-backtracking segment from the
start to the end of the interval, and observe that

  1. 1.

We can partition the chunk of $H$ edges into either main-path (non-
backtracking segment) and off-track segment attached to the main-path
(backtracking segment);

  2. 2.

Each $H$ edge on the main-path is fixed once the start and end point is
identified;

  3. 3.

Each backtracking edge requires $d$ going away off-track. This is fixed when
traversing back towards the main path and thus give an average of $\sqrt{d}$;

  4. 4.

The additional label in $[q]$ is then offset by the long chunk as we have
$q^{O(1/\log_{d})n}\leqslant 1+\varepsilon$ for $q\leqslant n^{\delta}$ for
some constant $\delta\leqslant O(\frac{1}{\log d})$.

###  2.7 Graph matrix norm bound for grouped shapes

##### Single trace-method for a collection of various shapes

As we shed light upon in the overview for our PSDness analysis, our moment
matrix consists of $\Omega(\exp(d_{sos}\log n))$ many shapes. Despite the
intuition in prior works that apply conditioning to reduce dense shapes to
sparse shapes, the analysis in [JPR+22] inevitably loses extra
$\operatorname{polylog}(n)$ factors due to its edge-reservation idea. On a
high-level, for ease of the technical analysis, it is helpful in the prior
works to assume the shapes that arise in the charging to have various ”nice”
properties that preserve the prescribed _minimum vertex separator_. This
proceeds in the manner of putting aside $O(V(\alpha))$ edges, while applying
conditioning on the rest. Unfortunately, this inevitably leads to a loss of
$\operatorname{polylog}$ factors as there may still be $O(|V(\alpha)|)$ excess
edges, as each of which requires a potential
$|V(\alpha)|=\Theta(\operatorname{poly}\log n)$ factor for encoding.

Though it is foreseeable that a more powerful conditioning lemma equipped with
combinatorial charging argument would carry through, we observe in this work
that it is in fact more convenient to group shapes together (as well as with
their shape coefficients from pseudo-calibration) and apply one single trace-
method calculation as our spectral norm bounds machinery is amenable to be
applied on a sum of graph matrices. In particular, for our final charging, we
consider graph matrix for grouped shapes defined as the following,

######  Definition 2.49 (Graph matrix for grouped shapes).

Consider $\mathcal{P}$ a collection of shapes, we define the graph matrix of
grouped shapes of $\mathcal{P}$ as

$M_{\mathcal{P}}=\sum_{\alpha\in\mathcal{P}}M_{\alpha}$

The main motivation behind this grouping is the observation that the cost of
identifying ”excess edges” in the outer union bound is in fact the
fundamentally the same as having _surprise visits_ in our trace-method
calculation, which we know by now that each comes with a gap! That said, we
can hope to offset the drawing cost by the gap from surprise visit, and as we
will soon see, the cost of encoding these ”excess edges” is in the end $O(1)$!

To shed light into our analysis, we note that as we apply trace-method
calculation on $M_{\mathcal{P}}$ directly without partitioning on the shapes,
a block-walk may indeed behave as the following,

Figure 8:  Block walk for grouped shapes

##### Strategy overview for bounding drawing factor

At this point, we are ready to extend the block-value analysis to capture
additionally the cost of drawing out a shape, and avoid the ”potential”
encoding cost should one try to apply a triangle inequality in a naive way.

We remind the reader that the encoder knows the shape to-be drawn out, and the
decoder has a map of the random graph sample being explored up-to the current
timestamp in the walk as well as the edge-labeling of the upcoming block. The
task for the decoder is to assign each active vertex in the current boundary a
label to help draw out the upcoming shape.

Out strategy proceeds as the following,

  1. 1.

We extend the block-value bound to additionally take into account of the cost
of drawing out the upcoming shape;

  2. 2.

Given the labeling $\mathcal{L}_{\alpha}$ for the current $\alpha$ block
(which is known to the encoder), we consider a subshape $\alpha_{H}$ obtained
by removing edges from $\alpha$ that receive an $F$ label in $\mathcal{L}$,
and remove isolated vertices not in $U_{\alpha_{H}}$, and this produces us a
list of wedges $W=\\{W_{i}\\}$;

  3. 3.

(Bundle) For each wedge $W$, we first identify it as an edge set
$W\subseteq\binom{n}{2}$ (via Claim 4.22) ;

  4. 4.

(Draw) The rest of the shape can be easily drawn out as it either requires a
single constant (i.e. going to a new vertex), or it leads to a seen vertex
with a new edge and hence is accounted for as a surprise visit.

##### Branch-chasing: forced-return bound without mirror copy

Interestingly, as we extend our block-value bound in order to apply graph
matrix norm bounds on a collection of shapes as opposed to a single shape,
some component of our prior analysis in fact slightly falls short: in
particular, our forced return argument for branching vertex. Note that
previously as we apply trace method for a single shape, we know that each
branching vertex that pushes out multiple edges in the current block
inevitably faces a pull-back in the subsequent block, and we use this
observation to give a lightweight local argument that such branching vertex
does not interefer with out forced return bound. However, as shown in the
example of fig. 8, this is not true for branching vertex anymore (for example,
the middle vertex in $\alpha_{1}$ pushes out two edges while they don’t get
immediately pulled back in the subsequent block). In fact, not only is it not
true that pull-backs do not immediately happen in the subsequent block, they
may never happen either: consider the example where the first block consists
of branching vertices pushing out, while any subsequent block proceeds via
parallel disjoint paths, and therefore, the paths never rejoin.

##### Chase confusion

We now make this issue concrete. Consider the following example at fig. 9,
suppose $v$ at the first block branches out to $a$ and $b$, even though the
path to $a$ immediately backtracks, the path to $b$ keeps pushing forward. At
the end of the second block, if an $R$ edge is used from $v$ for the third-
block, it is potentially unclear which edge it points to, as it can be either
pointing to $s_{1}$ or $b$, which is then considered a $R$-chase as we picture
it as a walker chasing another.

Put simply in the example of tree, our prior unforced return bound can be seen
as saying for each edge, when traversed the second time, it must be traversed
in the opposite direction from when it is first created, as seen in the
example of backtracking towards the root (unless there is a cycle that can be
charged to it in the general case). However, in this setting, this is no
longer true as we may traverse the edge $(v,b)$ twice in the same direction,
while there is no surprise visit.

To address this issue, we note that unless there is a surprise visit that can
again be charged to this, we can ask each walker on the matrix boundary a
single question ”whether you are being chased?” Note that for a single walker,
this is a question that can be answered in $[2]$ as it is unnecessary to
specify which particular walker is chasing. As we additionally maintain a
branch-chasing graph that is a tree, we show in Section 3.5 that a single
constant cost per active walker on the boundary (i.e. per vertex on the matrix
boundary), is sufficient to determine which edge is being used to chase. As a
result, $R$-chase remains to be fixed up to factor of an absolute constant per
vertex in each block.

Figure 9:  Chase confusion

##  3 Tight matrix norm bounds: vertex encoding cost

As illustrated in our technical overview, our starting point here is
step(edge)-labeling,

######  Definition 3.1 (Swapped Step label for vertex-encoding cost).

A labeling $\mathcal{L}$ for a walk assigns each edge in the length-$q$ walk a
label in $\\{F,R,S,H\\}$, with

  * •

$F$ (a fresh step): an edge (or random variable) appearing for the first time,
and the destination vertex is appearing for the _first_ time in the walk;

  * •

$R$ (a return step): an edge (or random variable) appearing for the second
time;

  * •

$S$ (a surprise step/visit): an edge (or random variable) appearing for the
first time, and the destination vertex is _not_ appearing for the first time
in the walk;

  * •

$H$ (a high-mul step) : an edge (or random variable) appearing for neither the
first nor the second time.

By default, we assume $\mathcal{L}$ assigns the labels according to the
traversal from $U_{\alpha}$ to $V_{\alpha}$; analogously, we denote
$\mathcal{L}^{T}$ if we traverse $\mathcal{L}$ in a reverse direction from
$V_{\alpha}$ to $U_{\alpha}$.

It should be noted here that as we work with vertex-encoding cost in this
section, we consider $R$-step for an edge making its second-appearance.

######  Remark 3.2.

With some abuse of notation, we will also use $\mathcal{L}$ (and analogously
$\mathcal{L}^{T})$ to denote the labeling of a walk restricted to a a single
block.

We now describe our encoding scheme given the edge-labeling. The encoding
works by maintaining a set $W_{t}$ of the vertices in the current block
revealed to us already, and walk along edges greedily to expand $W_{t}$ until
all vertices in the walk are encoded, i.e.,
$W_{t}=V((\alpha\circ\alpha^{T})^{q})$ .

###  3.1 Vertex encoding scheme

For a fixed set $W_{t}$ at time-stamp $t$, and a given shape $\alpha$, we
consider the edges across the cut produced by $W_{t}$, let $B_{t}\subseteq
V((\alpha\circ\alpha^{T})^{q})\setminus W_{t}$ be the set of unknown vertices
incident to some cut edge, and let $(i,j)$ be some edge across the cut with
$i\in W_{t},j\notin W_{t}$,

1. By default, we set $W_{0}=U_{\alpha}$: any vertex in $U_{\alpha}$ is the starting point revealed to us from the last block, hence no encoding needed; 2. if there’s an $R$ edge $(i,j)$ across the cut, we expand $W$ along this edge o.w.; 3. if there is a path of $H$ edges connected to $W$ across the cut of length at least $\log_{d}2q|V(\alpha)|$, split the path into chunks of length at most $\kappa$ and encode each chunk’s boundary in $2q|V(\alpha)|$ with an extra constant in $[2]$ indicating cycle orientation using $2$-cycle freeness; 4. if there is some vertex $v\in B_{t}$ that has (at least) two paths of $H$ edges connected to $W$, the vertex is doubly-constrained (unless the path crosses $U_{\alpha}$ or $V_{\alpha}$), and all vertices along this path can be encoded using a label in $[2]$ to indicate the orientation of the cycle altogether by using $2$-cycle freeness; (specifically, if the path has a combined length of $\ell\gg\kappa$, we need to encode additional vertices in $|2qV(\alpha)|$ with a label in $[2]$ for every $\kappa$ vertices to identify the entire cycle, however, this is $(1+o(1))$ per vertex on average); o.w., 5. if there are multiple high-mul paths crossing $U_{\alpha}$ or $V_{\alpha}$, and it is a mirror copy, we expand along these high-mul paths until the entire mirror copy is encoded into $W$; o.w., 6. if there is an $H$ edge $(i,j)$ across the cut, we expand $W$ along this edge; 7. if there is an $F$ edge $(i,j)$ across the cut for $j\notin U_{\alpha}\cup V_{\alpha}$, and $j$ is incident to some $H$ edge or $R$ edge outside the cut, or $j\in U_{\alpha}\cup V_{\alpha}$ while $j$ is incident to some $H$ edge outside the cut, we expand along this edge; o.w., 8. expand along the $F$ edges; 9. we additionally require all vertices in the current length-$2$ block to be decoded before decoding vertices in the new block (except the vertices decoded by doubly-constrained vertices crossing the boundary or by mirror copy); 10. (Excess $F$ edge clean-up) for each length-$2$ block, if there is any $F$ edge that does not get encoded as the cut edge, we assign an extra label in $|2qV(\alpha)|$ for each such edge indicating their second-time being used (if any).

######  Remark 3.3.

The above encoding scheme applies in a straightforward way for traversing
walks in a reversed direction from $V_{\alpha}$ to $U_{\alpha}$.

We would like to remind the reader that cases 2-5 allow the next vertex to be
encoded in $O(1)$ factor, case 6 allows us to specify the next vertex using a
factor of $d$ , case 7 allows us to specify the next vertex using a factor of
$O(q_{\alpha}|V(\alpha)|))$, and case 8 requires the full factor of $n$ .

In the remaining of this section, we bound the vertex-encoding cost of the
above encoding scheme.

###  3.2 (Non-dangling) Second-use return is forced: overview

In this subsection, we identify the cost of identifying a vertex arrived using
some $R$ edge, i.e., an edge that appears for the second-time. At a high-
level, the vertex-choice for the destination of such an edge is fixed: for
example, when we are traversing a tree from some root, each vertex only has
$1$ edge that goes towards the root. That said, things might get slightly more
complicated when the walk is no longer tree-like. Intuitively, any confusion
for determining the vertex reached by an $R$ edge can be settled with a cost
of $O(d)$ using a degree bound, however, this would render us a trivial bound
of $\sqrt{nd}$ analogous to a row-sum bound.

To get around with this, we note that any such confusion can be charged with a
gap in the previous walk, which offers us a gap to encode auxiliary data for
settling such confusion. Concretely, we relate the potential confusion in
determining destination of a return edge via _surprise visits_ 222The argument
in this section also relies upon another quantity _missed-immediately-return_
which can be seen as a proxy to surprise visits , i.e., edges leading to
visited vertices in the walk which correspond to some gap in our walk.

######  Definition 3.4 (Potential-unforced-return factor $\mathsf{Pur}$).

At time $t$, for each vertex $v$, let $\mathsf{Pur}_{t}(v)$ be defined as the
following,

  1. 1.

Each return leg closed from $v$ contributes $1$ to $\mathsf{Pur}_{t}(v)$;

  2. 2.

Each unclosed $F$ edge currently incident to $v$ contributes $1$;

  3. 3.

An extra $-1$ as we can maintain a counter for each vertex such that there is
always one potential return-leg presumed to be forced.

Let $H_{v,t}$ be the component reachable using subsequent $H$ edges from $v$
at time $t$, and define

$\mathsf{Pur}_{t}(H_{v})\coloneqq\sum_{i\in H_{v,t}}\mathsf{Pur}_{t}(i)$

######  Remark 3.5.

The definition of $\mathsf{Pur}_{t}(v)$ does not require $v$ to be on the
boundary at time $t$ (similarly for $H_{v,t}$), while we are only interested
at the desired invariant when they are at the boundary.

######  Definition 3.6 (Surprise visit counter).

For a time-stamp $t$, for each vertex $v$ and $H_{v,t}$ defined above, let
$s_{t}(v)$ be the number of surprise visits arriving at $v$ revealed by time
$t$; we analogously define $s_{t}(H_{v})=\sum_{i\in H_{v}}s_{t}(i)$.

###  3.3 Starting from the basics: a forced-return argument for 1-in-1-out

######  Proposition 3.7.

Throughout the walk where any vertex opens up at most $1$ edge at the
boundary, we maintain the invariant

$\mathsf{Pur}_{t}(H_{v,t})\leqslant 2\cdot s_{t}(H_{v,t})$

for $H_{v,t}$ the $H$-component reachable from the current boundary vertex
$v$.

##### Overview: unforced-return ignoring $H$ edges

For starters, we observe for a single vertex $v$, if there is no $H$ edge
being used throughout the walk and each vertex opens up at most $1$ edge on
the boundary,

  1. 1.

For the base case, when $v$ is first revealed, the return from $v$ must be
using the edge that explores $v$, and we have $\mathsf{Pur}(v)=0$;

  2. 2.

Each departure from $v$ may add $1$ potential-unforced-return edge as it adds
an unclosed incidental $F$ edge to $v$, and departure from $v$ using $R$ edge
does not change the $\mathsf{Pur}$ factor at $v$;

  3. 3.

However, the subsequent arrival may close an $F$ edge that is previously
contributing as an unclosed $F$ edge incident to $v$ (though not necessarily
the $F$ edge opened by the last departure), and hence $\mathsf{Pur}(v)$ does
not change from the last time when $v$ is at the boundary if arriving via an
$R$ edge;

  4. 4.

The arrival, if using a new $F$ edge, is a surprise visit arriving at $v$ and
contributes an $1$ to $s_{t}$ and an $1$ to $\mathsf{Pur}$ on LHS; the bound
holds if we assign an increment of $2$ via the one single surprise visit.

##### Incorporating $H$ edges

To extend our above argument for using $H$ edges, we give an argument based on
$H$-components which may evolve over time. We first appeal to the following
two claims building upon the prior observation that arriving at a vertex via
an $R$ edge does not increase its $\mathsf{Pur}$ factor compared to when it
last appears on the boundary (for the case only a single edge may be opened
up),

######  Claim 3.8 (Calling an $R$ edge does not change $\mathsf{Pur}$ on
vertices already in the current $H$-comp).

Let $v$ be the current boundary at time $t$, let $H_{v,t}$ be the
$H$-component of the boundary at time $t$, and an $R$ edge is called from
$H_{v,t}$ (concretely from $v$)

$\sum_{i\in H_{v,t}}\mathsf{Pur}_{t+1}(i)\leqslant\sum_{i\in
H_{v,t}}\mathsf{Pur}_{t}(i)$

In other words, despite $H_{v,t}$ is not necessarily the same as $H_{v,t+1}$
since calling an $R$ edge may expand the current $H$ component, it does not
increase $\mathsf{Pur}$ factor restricted to the vertices in the current $H$
component.

###### Proof.

To see the upper bound, observe that calling an $R$ edge from an $H$
component, restricted to the vertices already in the $H$ component prior to
the closing of this $R$ edge, we simply have an edge contributing as an
unclosed $F$ edge shifted to a closed return leg called from the component.
The inequality follows when we close an $R$ edge between vertices already in
the same $H$ component. ∎

######  Claim 3.9 (Getting merged into an $H$ component via an $R$ edge does
not change $\mathsf{Pur}$ on the annexed vertices).

Let $v$ be the boundary at time $t$, and let $t^{\prime}$ be the subsequent
time-mark such that $H_{v,t}$ is $H$-connected to the boundary (at
$t^{\prime}$) again and an $R$ edge is used at this step, i.e.,
$H_{v,t}\subseteq H_{u,t^{\prime}}$, the $H_{v,t}$ component gets merged into
a $H$ component via an $R$ edge at the current step for $u$ the boundary
vertex at $t^{\prime}$ followed by an $R$ edge

$\sum_{i\in H_{v,t}}\mathsf{Pur}_{t^{\prime}}(i)=\sum_{i\in
H_{v,t}}\mathsf{Pur}_{t}(i)$

###### Proof.

Since we depart from $H_{v,t}$ at time $t$ via an $F$ edge, we have
$\mathsf{Pur}_{t_{m}}(H_{v,t})=\mathsf{Pur}_{t}(H_{v,t_{m}})+1$ for any
$t<t_{m}<t^{\prime}$; however, since we arrive back at a vertex in $H_{v,t}$
at time $t^{\prime}$ by closing an $R$ edge, we have $\sum_{j\in
H_{v,t}}\mathsf{Pur}_{t^{\prime}}(j)=\sum_{j\in
H_{v,t}}\mathsf{Pur}_{t^{\prime}-1}(j)-1=\sum_{j\in
H_{v,t}}\mathsf{Pur}_{t}(j)$, giving us the desired. ∎

We now proceed to prove the main proposition.

###### Proof to Proposition 3.7.

Suppose this is true throughout the walk so far, and we are currently at
$H_{v,t}$, and move to $u$ from $v$ at time $t$, we need to show the above for
$H_{u,t+1}$. By construction, it suffices for us to consider whether this is
an $F/R$ edge. Notice this is immediate if $v$ is a new vertex, as
$H_{u,t+1}=\\{u\\}$, and there is no potential-unforced-return from $u$ at
this time. Otherwise, if the $v\rightarrow u$ leg opens up a new surprise
visit,

  1. 1.

If $u\in H_{v,t}$, the new $F$ edge that gets open may contribute $1$ to both
$\mathsf{Pur}_{t+1}(v)$ and $\mathsf{Pur}_{t+1}(u)$ while $\mathsf{Pur}$
factor of other vertices in $H_{v,t}$ does not get changed. That said, we pick
up a gain of $2$ on the LHS, while the surprise visit also now contributes to
$s_{t+1}(H_{v,t+1})$, giving an increment of $2$ on the RHS as well;

  2. 2.

If $u\notin H_{v,t}$, let $t_{u}$ be the last time vertex $u$ appears at a
boundary $H$ component, and call this component $H_{u,t_{u}}$, in addition to
the factors contributing to $\mathsf{Pur}_{t_{u}}(H_{u,t})$, the departure at
time $t_{u}$ opens up $1$ $F$ edge from $H_{u,t_{u}}$. Plus the new surprise
visit that we just open up, we have

$\displaystyle\mathsf{Pur}_{t+1}(H_{u,t+1})$
$\displaystyle=\mathsf{Pur}_{t_{u}}(H_{u,t_{u}})+2$ $\displaystyle\leqslant
2\cdot s_{t_{u}}(H_{u,t_{u}})+2$ $\displaystyle=2\cdot s_{t+1}(H_{u,t})$

where we observe that $s_{t+1}(H_{u,t})=s_{t_{u}}(H_{u,t_{u}})+1$ as we just
pick up a new surprise visit, and $H_{u,t_{u}}=H_{u,t}$ as a set of vertices.

If $v\rightarrow u$ is an $R$ leg that closes some $F$ edge, let $t_{u}$ be
defined as earlier,

  1. 1.

$u\notin H_{v,t}$: This yields a merge of $H$ components, and we can partition
$H_{u,t+1}$ into vertices $H$-reachable either via $u$ or $v$ at time $t$,

$\displaystyle\mathsf{Pur}_{t+1}(H_{u,t+1})$ $\displaystyle=\sum_{i\in
H_{v,t}}\mathsf{Pur}_{t+1}(i)+\sum_{j\in H_{u,t}}\mathsf{Pur}_{t+1}(j)$

By our claim that calling $R$ edge does not increase $\mathsf{Pur}$ on the
vertices in the current $H$ component,

$\displaystyle\sum_{i\in H_{v,t}}\mathsf{Pur}_{t+1}(i)\leqslant\sum_{i\in
H_{v,t}}\mathsf{Pur}_{t}(i)=\mathsf{Pur}_{t}(H_{v,t})\leqslant 2\cdot
s_{t}(H_{v,t})$

Since $u\notin H_{v,t}$, for component $H_{u,t}=H_{u,t_{u}}$, it gets annexed
into a new $H$-comp via an $F$ departure and a $R$ return,

$\sum_{j\in H_{u,t}}\mathsf{Pur}_{t+1}(j)=\sum_{j\in
H_{u,t}}\mathsf{Pur}_{t_{u}}(j)=\mathsf{Pur}_{t_{u}}(H_{u,t_{u}})\leqslant
2\cdot s_{t_{u}}(H_{u,t_{u}})$

Combining the above yields

$\displaystyle\mathsf{Pur}_{t+1}(H_{u,t+1})$ $\displaystyle\leqslant 2\cdot
s_{t+1}(H_{v,t})+2\cdot s_{t+1}(H_{u,t_{u}})=2\cdot s_{t+1}(H_{u,t+1})$

as $H_{v,t}$ and $H_{u,t_{u}}$ form a partition for $H_{u,t+1}$ for $u\notin
H_{v,t}$, and the surprise visits inherit over time.

  2. 2.

$u\in H_{v,t}$: This is a return within an $H$-component, and we have

$\mathsf{Pur}_{t+1}(H_{u,t})\leqslant\mathsf{Pur}_{t}(H_{v,t})$

since calling a return leg within the same $H$ component does not increase
$\mathsf{Pur}$ factor (in fact, a decrease by $1$ as the corresponding $F$
edge contributes a factor $1$ to both endpoints in the $H$ component, while
after being closed, it only contributes as a closed $R$ edge to one endpoint).

∎

###  3.4 Branching with mirror copy: a heuristic argument

##### Branching

The above argument crucially relies upon that each vertex can only encode at
most $1$ edge when it is on the boundary each time, however, this is not true
in the general setting for graph matrix, and particularly why rough matrix
norm bounds depend crucially on _minimum vertex separator_ of the underlying
graph. That said, we note that the argument can be extended in a lightweight
manner to the general case when the matrix is indexed by order-tuple, i.e.,
there is no permutation-jump involved in the walk.

For concreteness, we call a vertex an _anchor_ vertex if it encodes multiple
(out-going) edges on the boundary at a single time in the walk. The crux of
the argument observes that we can further constrain each such vertex to have
each of its $F$ edge opens up in the branching to be closed before the vertex
appears again on the boundary, as otherwise there is a gap from surprise visit
that we can identify locally in the constraint graph, and this is captured by
the counter $\mathsf{mir}$ to be defined momentarily.

##### Return bound for tuple-indexed walk

Let’s start with some definitions in this setting, and fix the traversal
direction from $U_{\alpha}$ to $V_{\alpha}$.

######  Definition 3.10 (Anchor vertex).

For a vertex $v$ in the shape $\alpha$ (or $\alpha^{T}$) and an edge-labeling
$\mathcal{L}$, we call it an _anchor_ vertex if it pushes out more than $1$
non-dangling edge, i.e., an edge on a simple path from $v$ to the next
boundary.

######  Definition 3.11 (Mirror copy).

For any vertex $v$ in $\alpha$ (or in $\alpha^{T}$), we let $\sigma(v)\in
V(\alpha^{T})$ or (in $V(\alpha)$) be the counterpart of $v$ obtained by
shape-transpose.

######  Definition 3.12 (Missed-immediate-return factor counter
$\mathsf{mir}$).

For a vertex $v$ that opens up multiple $F$ edges from the boundary, let
$\mathsf{mir}_{t}(v)$ be the number of $F$ edges it opens up as an anchor
vertex so far in the walk that are not immediately closed when $v$ appears on
the boundary again. Analogously, we define $\mathsf{mir}_{t}(H_{v,t})$ for the
corresponding $H$-component.

######  Remark 3.13.

For adjacency matrix or line graph, $\mathsf{mir}_{t}(v)=0$ throughout the
walk as each vertex may open up at most $1$ $F$ edge when at boundary.

######  Proposition 3.14.

For each block, process the anchor-vertices pair according to their distance
in increasing order in $\alpha\circ\alpha^{T}$. For each starting anchor
vertex being processed, each path-segment crossing the boundary starting with
$F$ edges is either immediately backtracking, or we can assign a surprise
visit from the path segment (or its adjacent one) to the starting anchor
vertex for its corresponding $\mathsf{mir}$ factor. Moreover, each surprise
visit is assigned to at most $2$ $\mathsf{mir}$ factors.

###### Proof.

We first observe that for any path-segment that departs from the starting
anchor vertex with $F$ edge may only return to the anchor vertex (with label
in $[n]$) within the path-segment at the corresponding mirror copy location
(aka. the ending anchor vertex) if the starting anchor vertex (labeled in
$[n]$) ever appears again in the path segment. This follows from the
injectivity assumption: the starting anchor vertex may only appear in the
current block, and unless there is a surprise visit in the segment, the path
returning to the starting anchor vertex lands the starting anchor vertex (its
label in $[n]$) at the ending anchor vertex location in the constraint graph.
That said, for any anchor vertex that gets returned too early, aka. prior to
the corresponding mirror copy location, the branch that returns to the current
vertex gets assigned a surprise visit and each other path-segment that opens
up new $F$ branches departing from the anchor vertex also gets assigned a
surprise visit.

Next, we observe that the return to the starting anchor vertex at its mirror
location is mandatory for any segment starting with $F$. Suppose the current
path-segment does not return, the starting anchor-vertex picks up $1$
$\mathsf{mir}$ factor from the path-segment. Suppose there is no surprise
visit in the current segment (i.e., the $\mathsf{mir}$ factor from the segment
is uncharged yet), we claim that this must be the first processed path-segment
between the current pair of starting and ending vertices, as otherwise the
current path-segment has to arrive at some known vertex at the mirror-copy
location which gives a surprise visit to assign to the corresponding
$\mathsf{mir}$ factor. However, notice for any anchor vertex with path-segment
added to its mirror copy in its subsequent block, there are at least two edge-
disjoint paths (given by distinct path segments) to its mirror copy. For
concreteness, call the second path-segment processed the adjacent of the first
segment. Notice these two path segments are disconnected in the graph sample
once the starting anchor vertex is removed, while these two paths need to
merge eventually at the mirror copy location. By assumption, the mirror copy
is not the starting anchor vertex, hence there must be a surprise visit in the
second path-segment and we can charge it to the $\mathsf{mir}$ factor of both
the first and second path-segments.

Furthermore, to see that a factor of $2$ is sufficient, notice each subsequent
path-segment between the current pair of starting and ending anchor vertex
either comes with a surprise visit or it is an immediate backtracking segment
itself that does not contribute $\mathsf{mir}$ factor to the starting anchor
vertex. This completes the proof of our proposition. ∎

###  3.5 Branch-chasing using R is free

##### Troubles for yje immediate-return based argument

To recap our prior argument, we essentially give a special treatment for
_branching_ vertices, i.e., those in the constraint graph that may encode
multiple edges across the boundary, and we claim that for any such vertex,
each $F$ edge that gets opened up when departing from this vertex must be
immediately closed before this vertex appears again in the boundary: in
particular, the branching vertex needs to match in its mirror-copy location
unless there is a surprise visit that offers a gap for charging potential
unforced return due to the vertex opening up multiple $F$ edges simultaneously
in a single-shot.

However, this heuristic falls apart when we apply it for grouped shapes, as we
no longer have injectivity assumption across the boundary: in particular,
mirror copy is no longer well-defined. That said, as highlighted in the
overview section, we can consider a branching vertex that simultaneously opens
up multiple $F$ branches, and one of them returns sooner than others, causing
a potential confusion when calling an $R$ edge at the anchor vertex, that it
may refer to any of the $F$ edges leading to the alive $F$ branch (and the $F$
edge leading to the anchor vertex before any of the $F$ branches get opened
up).

##### Branch-chasing graph

We start by considering an auxiliary graph constructed as the following. It
should be noted that _boundary_ in the following section typically refers to
the boundary of the walk unless otherwise specified. Notice that each vertex
on the boundary gives us a tiny constant decay via their edges. However, the
core of our argument relies upon coloring the edges such that red edges are
the only possible source of confusions, and furthermore, we maintain the
invariants that each vertex is not incident to _too many red edges_ and each
black directed edge leads to a path to some walker on the current boundary.

1. This is a directed graph with each vertex receiving a label in $[n]$, moreover, we can color the edges into _red_ and _black_ , such that we are interested in the desired invariant each vertex is incident to only one out-going red edge unless there are further surprised visits assigned to this vertex; 2. Observe that there is no confusion if there the incident red-edge is _unique_ ; 3. We start with an empty graph and build the graph as the walk proceeds; 4. For each $F$ edge, we open up a _directed black_ edge from the original vertex to the vertex it arrives at; 5. If the $F$ edge that gets opened up is a surprise visit, i.e., it leads to a previously explored vertex, we flip all the _black_ unclosed $F$ edges that have a directed path in the branch-chasing graph to the surprise destination to _red_.

With this graph in hand, we first see how it may help us in deciding $R$ edges
that arise in the chasing process when there are multiple walkers.

######  Observation 3.15.

If there is no dangling branch, any black edge is on a directed path to the
current boundary of the walk, i.e., the boundary of the branch-chasing graph
is equivalent to the walk boundary.

######  Corollary 3.16.

Each chase using a black edge is fixed.

###### Proof.

Even though each vertex may be incident to multiple black edges, observe that
the subgraph cut across by any black edge is a rooted tree, in particular,
with some _active_ walker in the current boundary. We then consider the
following process, at each (block) step in the walk, it suffices for us to go
through the vertices on the current boundary and query

  1. 1.

whether it is a _branching_ vertex looking for $R$ chase;

  2. 2.

whether it is a vertex assigned to _beacon guidance_ for $R$ chase;

For each step, for each walker at some branching vertex looking for $R$ chase,
the encoder can assign the boundary vertex on the path promised by the out-
going $R$ edge as the following,

  1. 1.

For vertex $v$ looking for beacon-guidance, consider the subtree reached by
the desired outgoing edge, assign beacon guidance for any branching vertex
with $R$ chase query contained in the subtree;

  2. 2.

Assign an arbitrary vertex in its subtree reached by the desired out-going
edge not assigned for beacon-guidance to $v$.

To decode, since the branch-chasing graph (restricted to black edges) is a
directed tree (forest), there exists some query node whose (out-going) subtree
is query-node free; by out encoding, there is also promised to be at least one
guidance node in that subtree, assign the outgoing edge pointing to the
(potentially multiple) guidance beacon to the query-node. Remove their colors
(temporarily), and repeat this process. ∎

######  Remark 3.17.

It should be pointed out that we only aim to identify the edge-set used by $R$
chase from this process, as any further confusion is then resolved using edge-
decay and automorphism factor.

We now proceed to handle the potential confusion caused by surprise visit in
the branch-chasing graph, i.e., red edges. Throughout the process, a surprise
visit may turn black edges into red edges, and call this path the
corresponding flip path of the surprise visit.

######  Proposition 3.18.

Consider the path of edges that have their colors flipped, this _flip path_
passes through at most $2$ vertices that are incident to _out-going_ red edge
before the current flip.

###### Proof.

Without loss of generality, suppose the surprise visit proceeds from
$a\rightarrow b$, we observe that any edge that gets flipped by this surprise
visit. Let $u_{a}$ be the closest vertex on the flipped path to $a$ that is
already incident to some out-going red edge before the current flip, and
suppose there is some other vertex $v_{a}$ that also has a black path to $a$
before the current flip. We observe that it needs to pass through $u_{a}$ as
the subgraph restricted to black edges is a directed tree. However, consider
the supposedly black path from $v_{a}$ to $u_{a}$, we claim that it must
already be red before the current flip as $u_{a}$ has an out-going red-edge,
which by construction, requires the $v_{a}$ to $u_{a}$ path to be flipped to
red. Therefore, there can be at most $1$ vertex incident to an _out-going_ red
edge before the current flip that has a flip-path to $a$; applying the above
argument to the flip-path leading to $b$ then gives us the desired bound. ∎

######  Corollary 3.19.

Assigning each surprise visit to two of the vertices its flipped path passes
through that may be incident to more than $1$ out-going red edge captured by
the factor redsurprise, we can maintain the following invariant for each
vertex

$\text{out-going red edges incident to $v$}\leqslant 1+w_{t}(v)$

where $w_{t}(v)$ accounts the number of surprise visits assigned to vertex $v$
for creating new excess red edge originating from $v$.

###  3.6 Return is still ”forced” with dangling branches

Before we dig into our final bound, we first see how having dangling edges may
affect our forced return bound. Notice that having dangling edges indeed
brings $\mathsf{Pur}$ factor that does not get assigned to any surprise visit,
however, our goal in this section is to show that beyond the ”anticpated”
$\mathsf{Pur}$ factors, dangling edges do not contribute further confusion.

##### Attaching dangling branches and dangling factor assignment

Recall that the return for each dangling branch is not necessarily fixed, and
our focus here is to see each dangling branch, despite how many vertices it
may pass through, only incur $1$ factor of potential-unforced-return.

Let’s start by recalling dangling branches (in a shape) can be encoded in the
following manner: we can recursively attach a dangling branch to some
identified vertex in the shape. And this begets our dangling factor assignment
scheme:in each block-step, we assign each dangling factor to the vertex it
attaches to, and update the $\mathsf{Pur}$ function for each vertex on the
newly attached segment via the $1$-in-$1$-out argument. At this point, it
should be clear that the $\mathsf{Pur}$ factor is associated with the number
of dangling branches as opposed to dangling vertices. To formalize this
intuition, we introduce attachment edge, as this is the edge part of a
dangling branch that comes with extra $\mathsf{Pur}$ factor in our argument.
Notice not all the edges in a dangling branch come with extra $\mathsf{Pur}$
factor, and this is crucial for us in obtaining a norm bound with extra factor
only depending on the number of dangling branches as opposed to the number of
dangling vertices.

######  Definition 3.20 (Attachment edge).

Given a shape and a block-step walk of the corresponding shape, for each
dangling branch, call the edge an attachment edge of the corresponding branch
if its origin vertex is identified using $R/H$ edge while it spits out some
$F$ edge part of the dangling branch.

######  Observation 3.21.

For any dangling branch, at any block-step of the walk, there is at most one
attachment edge unless there is a surprise visit locally along the branch.

We now upgrade our edge-coloring scheme in the branch-chasing graph to take
into account dangling branch. For each dangling branch that gets encoded, we
will color its $F$ edges as the following scheme,  1. Following the encoding
order that we start from some non-dangling vertex or landing vertex if
dangling, and encode the edges along the dangling branch; 2. We restrict our
attention to $F$ edges along the dangling branch, and 3. Color each attachment
edge _yellow_ ; 4. Color each non-attachment edge _green_.

######  Remark 3.22.

An out-going green edge is an edge opened as part of dangling branched while
it does not get assigned dangling factor.

######  Claim 3.23.

For any vertex $v$, let $s_{\mathsf{dangling},t}(v)$ be the number of surprise
visits arriving at $v$ by time $t$ that is part of any dangling branch, we
have