Sapienza University of Rome

Department of Engineering

PhD in Data Science
Thesis For The Degree Of Doctor Of Philosophy
Topological Neural Networks
Mitigating the Bottlenecks of Graph Neural Networks via Higher-Order Interactions

[]Lorenzo Giusti

Thesis AdvisorAdvisor
Prof. Stefano Leonardi
Prof. Pietro Liò

Academic Year MMXX-MMXXIII (XXXVI cycle)

18pdflatex -frn

To Whom it May Concern

§ ABSTRACT

The irreducible complexity of natural phenomena has led Graph Neural Networks to be employed as a standard model to perform representation learning tasks on graph-structured data. While their capacity to capture local and global patterns is remarkable, the implications associated with long-range and higher-order dependencies pose considerable challenges to such models. This work addresses these challenges by starting with the identification of the aspects that negatively impact the performance of graph neural networks in learning representations of events that strongly depend on long-range interactions. In particular, when graph neural networks require to aggregate messages among distant nodes, the message passing scheme performs an over-squashing of an exponentially growing amount of information into static vectors.

It is important to notice that for some classes of graphs (i.e., path, tree, grid, ring, and ladder) the underlying connectivity allows messages to travel along edges without encountering significant interference from other paths, thus reducing the growth of information to be linear in the number of messages exchanged.

When the underlying graph does not fall into the aforementioned categories, oversquashing arises because the propagation of information happens between nodes that are connected through edges, which induces a computational graph mirroring nodes' connectivity. This phenomenon causes nodes to become insensitive to information sent from remote parts of the graph. To offer a new perspective for designing architectures that mitigate such bottlenecks, a unified theoretical framework reveals the impact of network's width, depth, and graph topology on the over-squashing phenomena in message-passing neural networks.

The thesis then drifts towards the exploitation of higher-order interactions via Topological Neural Networks.  With a multi-relational inductive bias, topological neural networks propagate messages through higher-dimensional structures, effectively providing shortcuts or additional routes for information flow. With this construction, the underlying computational graph is no longer coupled with the input graph structure, thus mitigating the aforementioned bottlenecks while accounting also for higher-order interactions. Inspired by the masked self-attention mechanism developed in Graph Attention Networks alongside the rich connectivity provided by simplicial and cell complexes, two distinct attentional architectures are proposed: Simplicial Attention Networks and Cell Attention Networks.

The rationale behind these architecture is to leverage
the extended notion of neighbourhoods provided by the particular arrangement of groups of nodes within a simplicial or cell complex. In particular, these topological attention networks exploit the upper and lower adjacencies of the underlying complex to design anisotropic aggregations able to measure the importance of the information coming from different regions of the domain. By doing so, they capture dependencies that conventional Graph Neural Networks might miss.

Finally, a communication scheme between higher-order structures is introduced with Enhanced Cellular Isomorphism Networks, which augment topological message passing schemes by letting all the cells of a cell complex receive messages from their lower neighbourhood. This upgrade enables direct interactions among node groups within a cell complex, specifically arranged in ring-like structures. This augmented scheme offers more comprehensive representation of higher-order and long-range interactions, demonstrating very high performance on large-scale and long-range benchmarks.

Keywords: Topological Deep Learning, Topological Neural Networks, Geometric Deep Learning, Graph Neural Networks.

Lorenzo Giusti

§ ACKNOWLEDGEMENTS

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

Lorenzo Giusti, Geneva, January 2024. All rights reserved.

CHAPTER: INTRODUCTION

CHAPTER: ON THE LIMITATIONS OF GRAPH NEURAL NETWORKS AND HOW MITIGATE THEM

CHAPTER: ENHANCING GRAPH REPRESENTATION WITH TOPOLOGICAL APPROACHES

CHAPTER: EXPERIMENTAL ANALYSIS

CHAPTER: CONCLUSIONS

This thesis has presented an innovative approach to measure the impact of several factors that reduce the capabilities of message-passing neural networks in capturing long-range interactions. In particular, it has been shown how the width and depth of the $\MPNN$, and the underlying graph topology can influence the performance of structured learning tasks that depend on long-range interactions. Moreover, to cope with such limitations, this thesis has proposed topological approaches to naturally decouple the computational graph from the input graph. In particular, it is possible to mitigate the bottlenecks of graph neural networks while capturing higher-order relationships without a significant increase in the complexity of the underlying model by designing proper message-passing schemes on discrete topological spaces. However, current state-of-the-art models do not naturally account for a principled way to model efficient topological message passing schemes accounting both higher-order interactions and the feature's importance. To this aim, this thesis has addressed these challenges by advancing the methods presented in the topological deep learning literature including attentional schemes on topological spaces and an enhancement of Cellular Isomorphism Networks <cit.>. The newly proposed topological message passing scheme, named CIN++, enables a direct interaction within high-order structures of the underlying cell complex, by letting messages flow within its lower neighbourhood without sacrificing the model's expressivity. By allowing the exchange of messages between higher-order structures, the model's capacity to capture multi-way relationships in the data is significantly enhanced. We have demonstrated that the ability to model long-range and group interactions is critical for capturing real-world chemistry-related problems. In particular, the natural affinity of cellular complexes for representing higher-dimensional structures and topological features will provide a more detailed understanding of complex chemical systems compared to traditional models.

§ BROADER IMPACTS

This work provides evidence of how the proposed topological message-passing schemes allows the integration of local and global information within a discrete topological space. In particular, the proposed architecture capture complex dependencies and long-range interactions more effectively. This work is foreseen to have a broad impact within the fields of computational chemistry, network neuroscience, and physics, as it offers a robust and versatile framework for predicting meaningful properties of complex systems by accurately modeling group dependencies and capturing long-range interactions.

§ LIMITATIONS

While this thesis demonstrates that topological message-passing effectively models higher-order dependencies and long-range interactions in complex systems, it is reasonable to acknowledge that the complexity of the proposed methods inherently increases due to additional operations performed on top of those provided by classic $\MPNN$s. For example, the structural lifting maps (<Ref>) and the additional messages sent throughout the complex (<ref>, <ref>). However, much of the computational overhead introduced by cellular lifting can be mitigated by mapping all graphs present in the datasets into cell complexes in a preprocessing stage and storing them for later use. Additionally, the overhead of the topological message-passing schemes is mitigated by the fact that the operations within the same layer are naturally decoupled. Efficient network implementations make it possible to update the representation of a cell $\sigma$ in a concurrent execution <cit.>, amortizing the cost to be proportional to the largest neighbourhood of $\sigma$.

§ RECOMMENDATIONS FOR FUTURE RESEARCH

One of the most promising avenues for further exploration is the application of topological neural networks to the fields of science mentioned in <Ref>. Moreover, the field of algorithmic topology aims to solve problems that are often computationally intractable or fall within the NP-hard complexity class.Moreover, it turns out that algorithmic knot theory can also be used in the very same fields of science mentioned before. For example, in chemistry, molecular chirality can be determined by the nodes' chirality within the knots <cit.>; in physics, through the relationship between the Yang-Baxter equation <cit.> and knots' invariants. Finally, algorithmic knot theory can be used to model an essential biological process such as DNA recombination <cit.>. By combining the techniques presented in this thesis, combined with the principles of neural algorithmic reasoning <cit.> it should be possible to approximate solutions to algorithmic topology problems with a feasible amount of computational resources.

CHAPTER: GLOSSARY

CHAPTER: APPENDIX OF ON OVERSQUASHING IN MPNNS

§ GENERAL PRELIMINARIES

Assume a graph $\gph$ with nodes $ \mathsf{V}$ and edges $\mathsf{E}\subset \V \times \V$, to be simple, undirected, and connected. Let $n = \lvert \V \rvert$ and
write $[n]:= \{1,\ldots,n\}$. Denote the adjacency matrix by $\mathbf{A}\in\R^{n\times n}$. Compute the degree of $v\in \V$ by $d_v = \sum_{u}A_{vu}$ and write
$\mathbf{D} = \mathrm{diag}(d_1,\ldots,d_n)$. One can take different normalizations of $\mathbf{A}$, so write $\Anorm\in\R^{n\times n}$ for a Graph Shift Operator (GSO), i.e., an $n\times n$ matrix satisfying $\Anorm_{vu} \neq 0$ if and only if $(v,u)\in \mathsf{E}$; typically, $\Anorm \in \{\mathbf{A},\mathbf{D}^{-1}\mathbf{A},\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\}$. Finally, $d_{\gph}(v,u)$ is the shortest walk (geodesic) distance between nodes $v$ and $u$.

Graph spectral properties: the eigenvalues. The (normalized) graph Laplacian is defined as $\Lnorm = \mathbf{I} - \mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}$. This is a symmetric, positive semi-definite operator on $\gph$. Its eigenvalues can be ordered as $\lambda_0 < \lambda_1 \leq \ldots \leq \lambda_{n-1}$. The smallest eigenvalue $\lambda_0$ is always zero, with multiplicity given by the number of connected components of $\gph$ <cit.>. Conversely, the largest eigenvalue $\lambda_{n-1}$ is always strictly smaller than $2$ whenever the graph is not bipartite. Finally, recall that the smallest, positive, eigenvalue $\lambda_1$ is known as the spectral gap. Several of the proofs presented here rely on this quantity to provide convergence rates. Also, recall that the spectral gap is related to the Cheeger constant – introduced in <Ref> – of $\gph$ via the Cheeger inequality:

\begin{equation}\label{eq:cheeger_inequality}
2\cheeg \geq \lambda_{1} > \frac{\cheeg^{2}}{2}.
\end{equation}

Graph spectral properties: the eigenvectors.
Throughout this section, let $\{\eigen_{\ell}\}$ be a family of orthonormal eigenvectors of $\Lnorm$. In particular, note that the eigenspace associated with $\lambda_0$ represents the space of signals that respect the graph topology the most (i.e. the smoothest signals), so that is possible to write $(\eigen_0)_v = \sqrt{d_v}/2\lvert\E\rvert$, for any $v\in\V$.

From now on, assume that the graph is not bipartite, so that $\lambda_{n-1} < 2$.
Let $\mathbf{H}^{(0)}\in\R^{n\times p}$ be the matrix representation of node features, with $p$ denoting the hidden dimension. Features of node $v$ produced by layer $l$ of an $\MPNN$ are denoted by $\mathbf{h}_{v}^{(l)}$ and write their components as $(\mathbf{h}_{v}^{(l)})^{\alpha} := h_{v}^{(l),\alpha}$, for $\alpha \in [p]$.

Einstein summation convention. To ease notations when deriving the bounds on the Jacobian, the proof below often rely on Einstein summation convention, meaning that, unless specified otherwise, sums are always repeated across indices: for example, when writing terms like $x_{\alpha}y^{\alpha}$, the symbol $\sum_{\alpha}$ is left implicit.

This Section demonstrates the results in <Ref>. In fact, it will be derived a sensitivity bound far more general than <Ref> that, in particular, extends to $\MPNN$s that can stack multiple layers (MLPs) in the aggregation phase. Let's introduce a class of $\MPNN$s of the form:

\begin{equation}\label{eq:isotropic_MPNN}
\mathbf{h}_{v}^{(l)} = \mathsf{up}^{(l)}\Big(\mathsf{rs}^{(l)}(\mathbf{h}_{v}^{(l-1)}) + \mathsf{mp}^{(l)}\Big(\sum_{u}\Anorm_{vu}\mathbf{h}_{u}^{(l-1)}\Big) \Big)
\end{equation}

for learnable update, residual, and message-passing maps $\mathsf{up}^{(l)},\mathsf{rs}^{(l)},\mathsf{mp}^{(l)}:\R^{p}\rightarrow \R^{p}$. Note that <Ref> includes common $\MPNN$s like $\mathsf{GCN}$ <cit.>, $\mathsf{SAGE}$ <cit.>, and $\mathsf{GIN}$ <cit.>, where $\Anorm$ is $\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, $\mathbf{D}^{-1}\mathbf{A}$ and $\mathbf{A}$, respectively. An $\MPNN$ usually has Lipschitz maps, with Lipschitz constants typically depending on regularization of the weights to promote generalization. An $\MPNN$ as in <Ref> is $(c_{\mathsf{up}},c_{\mathsf{rs}},c_{\mathsf{mp}})$-regular, if for $t\in[m]$ and $\alpha\in[p]$, it holds

\begin{align*}
\| \nabla (\mathsf{up}^{(l)})^{\alpha}\|_{L_{1}} \leq c_{\mathsf{up}}, \quad \| \nabla (\mathsf{rs}^{(l)})^{\alpha}\|_{L_{1}} \leq c_{\mathsf{rs}}, \quad
\| \nabla (\mathsf{mp}^{(l)})^{\alpha}\|_{L_{1}} \leq  c_{\mathsf{mp}}.
\end{align*}

As in <cit.>, the interest is on the propagation of information in the $\MPNN$ via the Jacobian of node features after $m$ layers. A small derivative of $\mathbf{h}_v^{(m)}$ with respect to $\mathbf{h}_u^{(0)}$ means that – at the first-order – the representation at node $v$ is mostly insensitive to the information contained at $u$ (e.g. its atom type, if $\gph$ is a molecule).
Given a $(c_{\mathsf{up}},c_{\mathsf{rs}},c_{\mathsf{mp}})$-regular $\MPNN$ for $m$ layers and nodes $v,u\in\mathsf{V}$, it holds

\begin{equation}
\left\|\frac{\partial \mathbf{h}_{v}^{(m)}}{\partial \mathbf{h}_{u}^{(0)}}\right\|_{L_1} \leq p\cdot c^{m}_{\mathsf{up}}\left(\left(c_{\mathsf{rs}}\mathbf{I} +  c_{\mathsf{mp}}\Anorm\right)^{m}\right)_{vu}.
\end{equation}

The result above will be proven by induction on the number of layers $m$. Fix $\alpha,\beta \in [p]$. In the case of $m=1$, get (omitting to write the arguments where the maps are being evaluated, and using the Einstein summation convention over repeated indices):

\begin{equation*}
\Big| \frac{\partial h_v^{(1),\alpha}}{\partial h_u^{(0),\beta}}\Big| = \Big| \partial_{p}\mathsf{up}^{(0),\alpha}\Big(\partial_r\mathsf{rs}^{(0),p}\frac{\partial h_v^{(0),r}}{\partial h_u^{(0),\beta}} + \partial_q\mathsf{mp}^{(0),p}\Anorm_{vz}\frac{\partial h_z^{(0),q}}{\partial h_u^{(0),\beta}}\Big) \Big|,
\end{equation*}

which can be readily reduced to

\begin{equation*}
\Big| \frac{\partial h_v^{(1),\alpha}}{\partial h_u^{(0),\beta}}\Big| = \Big| \partial_{p}\mathsf{up}^{(0),\alpha}\Big(\partial_\beta\mathsf{rs}^{(0),p}\Lnorm_{vu} + \partial_\beta\mathsf{mp}^{(0),p}\Anorm_{vu}\Big) \Big| \leq c_{\mathsf{up}}\left(c_{\mathsf{rs}}\mathbf{I}+ c_{\mathsf{mp}}\Anorm\right)_{vu},
\end{equation*}

thanks to the Lipschitz bounds on the $\MPNN$, which confirms the case of a single layer (i.e. $m=1$). Also, assume the bound to be satisfied for $m$ layers and use induction to derive

\begin{align*}
\Big| \frac{\partial h_v^{(m+1),\alpha}}{\partial h_u^{(0),\beta}}\Big| &= \Big| \partial_{p}\mathsf{up}^{(m),\alpha}\Big(\partial_r\mathsf{rs}^{(m),p}\frac{\partial h_v^{(m),r}}{\partial h_u^{(0),\beta}} + \partial_q\mathsf{mp}^{(m),p}\Anorm_{vz}\frac{\partial h_z^{(m),q}}{\partial h_u^{(0),\beta}}\Big) \Big| \\
&\leq \Big|\partial_{p}\mathsf{up}^{(m),\alpha}\Big|\Big(\left\vert \partial_r\mathsf{rs}^{(m),p}\right\vert \left(c_{\mathsf{up}}^{m}\left(\left(c_{\mathsf{rs}}\mathbf{I} + c_{\mathsf{mp}}\Anorm\right)^{m}\right)_{vu}\right) + \Big|\partial_q\mathsf{mp}^{(m),p} \Big| \Anorm_{vz}\left(c_{\mathsf{up}}^{m}\left(\left(c_{\mathsf{rs}}\mathbf{I} + c_{\mathsf{mp}}\Anorm\right)^{m}\right)_{zu}\right) \Big) \\
&\leq \Big|\partial_{p}\mathsf{up}^{(m),\alpha}\Big|\Big(c_{\mathsf{rs}} \left(c_{\mathsf{up}}^{m}\left(\left(c_{\mathsf{rs}}\mathbf{I} + c_{\mathsf{mp}}\Anorm\right)^{m}\right)_{vu}\right) + c_{\mathsf{mp}} \Anorm_{vz}\left(c_{\mathsf{up}}^{m}\left(\left(c_{\mathsf{rs}}\mathbf{I} + c_{\mathsf{mp}}\Anorm\right)^{m}\right)_{zu}\right) \Big) \\
&\leq c_{\mathsf{up}}^{m+1}\left(c_{\mathsf{rs}}\left(\left(c_{\mathsf{rs}}\mathbf{I} + c_{\mathsf{mp}}\Anorm\right)^{m}\right)_{vu} + c_{\mathsf{mp}}\Anorm_{vz}\left(\left(c_{\mathsf{rs}}\mathbf{I} + c_{\mathsf{mp}}\Anorm\right)^{m}\right)_{vu}\right) \\
& = c_{\mathsf{up}}^{m+1}\Big(\left(c_{\mathsf{rs}}\mathbf{I} + c_{\mathsf{mp}}\Anorm\right)^{m+1}\Big)_{vu},
\end{align*}

using the Lipschitz bounds on the maps $\mathsf{up},\mathsf{rs},\mathsf{mp}$. This completes the induction argument.

From now on the focus will be on the class of $\MPNN$ adopted in <Ref>, whose layer are report below for convenience:

\begin{equation*}
\mathbf{h}_{v}^{(l+1)} = \up\Big(c_{\rs}\W_{\rs}^{(l)} \mathbf{h}_{v}^{(l)} + c_{\mpas}\W_{\mpas}^{(l)}\sum_{u}\Anorm_{vu}\mathbf{h}^{(l)}_{u}\Big).
\end{equation*}

The general argument can be adapted to derive <Ref>.

One can follow the steps in the proof of <Ref> and, again, proceed by induction. The case $m=1$ is straightforward, so consider the inductive step and assume the bound to hold for $m$ arbitrary. Given $\alpha,\beta \in [p]$, it holds

\begin{align*}
\Big| \frac{\partial h_v^{(m+1),\alpha}}{\partial h_u^{(0),\beta}}\Big| &\leq \lvert \up' \rvert \Big( c_{\rs}\left\vert(\W_{\rs})^{(m)}_{\alpha\gamma}\right\vert\Big|\frac{\partial h_v^{(m),\gamma}}{\partial h_u^{(0),\beta}}\Big| + c_{\mpas}\left\vert (\W_{\mpas})^{(m)}_{\alpha\gamma}\right\vert \Anorm_{vz} \Big| \frac{\partial h_z^{(m),\gamma}}{\partial h_u^{(0),\beta}}\Big|\Big) \\
&\leq c_{\up}w\left(c_{\rs}\left\|  \frac{\partial \mathbf{h}_v^{(m)}}{\partial \mathbf{h}_u^{(0)}}\right\|_{L_1} + c_{\mpas}\Anorm_{vz}\left\|  \frac{\partial \mathbf{h}_z^{(m)}}{\partial \mathbf{h}_u^{(0)}}\right\|_{L_1}  \right) \\
&\leq c_{\sigma}w\left(c_{\sigma}wp\right)^{m}\left( c_{\rs}\left(\left(c_{\rs}\mathbf{I} + c_{\mpas}\Anorm\right)^{m}\right)_{vu} + c_{\mpas}\Anorm_{vz}\left(\left(c_{\rs}\mathbf{I} + c_{\mpas}\Anorm\right)^{m}\right)_{zu}\right) \\
&\leq c_{\sigma}w\left(c_{\sigma}wp\right)^{m} \Big(\left(c_{\rs}\mathbf{I} + c_{\mpas}\Anorm\right)^{m+1}\Big)_{vu}.
\end{align*}

By summing over $\alpha$ on the left will conclude the proof (this will generate an extra $p$ factor on the right hand side).

Convention: From now on always consider $\Anorm = \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$. The bounds in this Section extend easily to $\mathbf{D}^{-1}\mathbf{A}$ in light of the similarity of the two matrices since $\Anorm^{k} = \mathbf{D}^{1/2}\left(\mathbf{D}^{-1}\mathbf{A}\right)^{k}\mathbf{D}^{-1/2}$. For the unnormalized matrix $\mathbf{A}$ instead, things are slightly more subtle. In principle, this matrix is not normalized, and in fact, the entry $(\mathbf{A}^{k})_{vu}$ coincides with the number of walks from $v$ to $u$ of length $k$. In general, this will not lead to bounds decaying exponentially with the distance. However, in expectation over the computational graph as in <cit.>, Appendix A of <cit.> and <Ref>, one finds that nodes at smaller distance will still have sensitivity exponentially larger than nodes at large distance. This is also confirmed by $\mathsf{Graph}$ $\mathsf{Transfer}$ synthetic experiments, where $\mathsf{GIN}$ struggles with long-range dependencies (in fact, even slightly more than $\mathsf{GCN}$, which uses the symmetrically normalized adjacency $\Anorm$).

A sharper bound for <Ref> will be proven foreword, it is important to notice that it contains <Ref> as a particular case.

Given an $\MPNN$ as in <Ref>, let $v,u\in\mathsf{V}$ be at distance $r$. Let $c_{\up}$ be the Lipschitz constant of $\sigma$, $w$ the maximal entry-value over all weight matrices, $d_{\mathrm{min}}$ be the minimal degree, and $\gamma_{\ell}(v,u)$ be the number of walks from $v$ to $u$ of maximal length $\ell$. For any $0 \leq k < r$, it holds

\begin{equation}
\left\| \frac{\partial \mathbf{h}_{v}^{(r+k)}}{\partial \mathbf{h}_{u}^{(0)}}\right\|_{L_1} \leq \gamma_{r+k}(v,u) (c_{\up}(c_{\rs} + c_{\mpas})w p(k+1))^k \Big(\frac{2c_{\up}wpc_{\mpas}}{d_{\mathrm{min}}}\Big)^r.
\end{equation}

Fix $v,u\in\V$ as in the statement and let $0 \leq k < r$. By using the sensitivity bounds in <Ref> and writing that

\begin{equation*}
\left\| \frac{\partial \mathbf{h}_{v}^{(r+k)}}{\partial \mathbf{h}_{u}^{(0)}}\right\|_{L_1} \leq \left(c_{\up}wp\right)^{r+k}\Big(\left(c_{\rs}\mathbf{I} + c_{\mpas}\Anorm\right)^{r+k}\Big)_{vu} = \left(c_{\up}wp\right)^{r+k}\sum_{i = 0}^{r+k}\binom{r+k}{i}c_{\rs}^{r+k - i}c_{\mpas}^{i}(\Anorm^{i})_{vu}.
\end{equation*}

Since nodes $v,u$ are at distance $r$, the first $r$ terms of the sum above vanish. Since $\Anorm = \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, the polynomial in the previous equation can be bounded by

\begin{align*}
\sum_{i = 0}^{r+k}\binom{r+k}{i}c_{\rs}^{r+k - i}c_{\mpas}^{i}(\Anorm^{i})_{vu} &= \sum_{i = r}^{r+k}\binom{r+k}{i}c_{\rs}^{r+k - i}c_{\mpas}^{i}(\Anorm^{i})_{vu} \leq \gamma_{r+k}(v,u)\sum_{i = r}^{r+k}\binom{r+k}{i}c_{\rs}^{r+k - i}\left(\frac{c_{\mpas}}{d_{\mathrm{min}}}\right)^{i} \\
&= \gamma_{r+k}(v,u) \sum_{q = 0}^{k}\binom{r+k}{r+q}c_{\rs}^{k - q}\left(\frac{c_{\mpas}}{d_{\mathrm{min}}}\right)^{r + q} \\
&= \gamma_{r+k}(v,u)\left(\frac{c_{\mpas}}{d_{\mathrm{min}}}\right)^{r} \sum_{q = 0}^{k}\binom{r+k}{r+q}c_{\rs}^{k - q}\left(\frac{c_{\mpas}}{d_{\mathrm{min}}}\right)^{q}.
\end{align*}

A simple estimate for

\begin{align*}
\binom{r+k}{r+q} &= \frac{(r+k)(r-1+k)\cdots(1+k)}{(r+q)(r-1+q)\cdots(1+q)}\binom{k}{q} \leq \frac{(r+k)(r-1+k)\cdots(1+k)}{r!}\binom{k}{q}  \\
&\leq \left(1 + \frac{k}{r}\right)\cdots (1+k) \binom{k}{q} \leq \left(1+\frac{k}{k+1}\right)^{r-k}(1+k)^{k}\binom{k}{q} \\
\end{align*}

can be provided by expanding the polynomial above can be as:

\begin{align*}
\sum_{i = 0}^{r+k}\binom{r+k}{i}c_{\rs}^{r+k - i}c_{\mpas}^{i}(\Anorm^{i})_{vu} &\leq \gamma_{r+k}(v,u)\left(1+\frac{k}{k+1}\right)^{r-k}(1+k)^{k}\left(\frac{c_{\mpas}}{d_{\mathrm{min}}}\right)^{r} \sum_{q = 0}^{k}\binom{k}{q}c_{\rs}^{k - q}\left(\frac{c_{\mpas}}{d_{\mathrm{min}}}\right)^{q} \\
&=  \gamma_{r+k}(v,u)\left(\frac{(1+k)^{2}}{2k+1}\left(c_{\rs} + \frac{c_{\mpas}}{d_{\mathrm{min}}}\right)\right)^{k}\left(\left(1+\frac{k}{k+1}\right)\frac{c_{\mpas}}{d_{\mathrm{min}}}\right)^{r} \\
&\leq \gamma_{r+k}(v,u)\left(\frac{(1+k)^{2}}{2k+1}\left(c_{\rs} + \frac{c_{\mpas}}{d_{\mathrm{min}}}\right)\right)^{k}\left(\frac{2c_{\mpas}}{d_{\mathrm{min}}}\right)^{r}.
\end{align*}

Combining all the ingredients together, the bound can be written as

\begin{align*}
\left| \frac{\partial \mathbf{h}_{v}^{(r+k)}}{\partial \mathbf{h}_{u}^{(0)}}\right\|_{L_1} &\leq\gamma_{r+k}(v,u) \left(c_{\up}wp\right)^{r+k}\left(\frac{(1+k)^{2}}{2k+1}\left(c_{\rs} + \frac{c_{\mpas}}{d_{\mathrm{min}}}\right)\right)^{k}\left(\frac{2c_{\mpas}}{d_{\mathrm{min}}}\right)^{r} \\
& = \gamma_{r+k}(v,u)\left(c_{\up}wp\,\frac{(1+k)^{2}}{2k+1}\left(c_{\rs} + \frac{c_{\mpas}}{d_{\mathrm{min}}}\right)\right)^{k}\left(\frac{2c_{\up}wpc_{\mpas}}{d_{\mathrm{min}}}\right)^{r} \\
&\leq \gamma_{r+k}(v,u)\left(c_{\up}\left(c_{\rs} + c_{\mpas}\right)wp(1+k)\right)^{k}\left(\frac{2c_{\up}wpc_{\mpas}}{d_{\mathrm{min}}}\right)^{r},
\end{align*}

which completes the proof. Notice that this also proves <Ref>.

§.§ Vanishing gradients result

Here it will be reported and proven a more explicit version of <Ref>.

Consider an $\MPNN$ as in Eq. (<ref>) for $m$ layers with a quadratic loss $\mathcal{L}$. Assume that (i) $\sigma$ has Lipschitz constant $c_{\up}$ and $\sigma(0) = 0$, and (ii) that all weight matrices have spectral norm bounded by $\mu > 0$.
Given any weight $\theta$ entering a layer $k$, there exists a constant $C > 0$ independent of $m$, such that

\begin{align}
\left\vert \frac{\partial \mathcal{L}}{\partial \theta}\right\vert &\leq C\left(c_{\up}\mu(c_{\rs} + c_{\mpas})\right)^{m-k}\left(1  +\left(c_{\up}\mu(c_{\rs} + c_{\mpas})\right)^{m}\right),
\end{align}

where $\lvert\lvert \mathbf{H}^{(0)}\rvert\rvert_{F}$ is the Frobenius norm of the input node features.

Consider a quadratic loss $\mathcal{L}$ of the form

\begin{equation*}
\mathcal{L}(\mathbf{H}^{(m)}) = \frac{1}{2}\sum_{v\in\V}\| \mathbf{h}_v^{(m)} - \mathbf{y}_v\|^{2},
\end{equation*}

and let $\mathbf{Y}$ represent the node ground-truth values. Given a weight $\theta$ entering layer $k < m$, it is possible to write the gradient of the loss as

\begin{equation*}
\Big| \frac{\partial \mathcal{L}(\mathbf{H}^{(m)})}{\partial\theta}\Big| = \Big| \sum_{v,u\in\V}\sum_{\alpha,\beta\in[p]}\frac{\partial \mathcal{L}}{\partial h_v^{(m),\alpha}}\frac{\partial h_v^{(m),\alpha}}{\partial h_u^{(k),\beta}}\frac{\partial h_u^{(k),\beta}}{\partial \theta}\Big|.
\end{equation*}

Once $k$ is fixed,, the term $\lvert \partial h_u^{(k),\beta} / \partial \theta \rvert$ is independent of $m$ and is possible to bound it by some constant $C$. Since the loss is quadratic, to bound $\partial \mathcal{L} / \partial h_v^{(m),\alpha}$, it suffices to bound the solution of the $\MPNN$ after $m$ layers. First, use the Kronecker product formalism to rewrite the $\MPNN$-update in matricial form as

\begin{equation}
\mathbf{H}^{(m)} = \up\left(\left(c_{\rs}\OMEga^{(m)}\otimes \mathbf{I} + c_{\mpas}\W^{(m)}\otimes \Anorm\right)\mathbf{H}^{(m-1)}\right).
\end{equation}

Thanks to the Lipschitzness of $\up$ and the requirement $\up(0) = 0$, is possible to derive

\begin{equation*}
\| \mathbf{H}^{(m)} \|_{F} \leq c_{\up}\| c_{\rs}\OMEga^{(m)}\otimes \mathbf{I} + c_{\mpas}\W^{(m)}\otimes \Anorm\|_{2} \|\mathbf{H}^{(m-1)}\|_{F},
\end{equation*}

where $F$ indicates the Frobenius norm. Since the largest singular value of $\mathbf{B}\otimes \mathbf{C}$ is bounded by the product of the largest singular values, it is easy to deduce that – recall that the largest eigenvalue of $\Anorm = \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$ is $1$:

\begin{equation}\label{app:eq:norm_bounded}
\| \mathbf{H}^{(m)} \|_{F} \leq c_{\up}\mu(c_{\rs} + c_{\mpas})\|\mathbf{H}^{(m-1)}\|_{F} \leq (c_{\up}\mu(c_{\rs} + c_{\mpas}))^{m}\|\mathbf{H}^{(0)}\|_{F},
\end{equation}

which affords a control of the gradient of the loss w.r.t. the solution at the final layer being the loss quadratic. Then, find

\begin{align}
\Big| \frac{\partial \mathcal{L}(\mathbf{H}^{(m)})}{\partial\theta}\Big| &\leq C\Big| \sum_{v,u\in\V}\sum_{\alpha,\beta\in[p]}\frac{\partial \mathcal{L}}{\partial h_v^{(m),\alpha}}\frac{\partial h_v^{(m),\alpha}}{\partial h_u^{(k),\beta}}\Big| \notag \\
&\leq C \sum_{v,u\in\V}\sum_{\beta\in[p]}\left\|\frac{\partial \mathcal{L}}{\partial \mathbf{h}_v^{(m)}}\right\|\left\|\frac{\partial \mathbf{h}_v^{(m)}}{\partial h_u^{(k),\beta}}\right\| \notag \\
&\leq C \sum_{v,u\in\V}\sum_{\beta\in[p]}\Big(\|\mathbf{H}^{(m)}\|_{F} + \|\mathbf{Y}\|_{F}\Big)\left\|\frac{\partial \mathbf{h}_v^{(m)}}{\partial h_u^{(k),\beta}}\right\| \notag \\
&\leq C \sum_{v,u\in\V}\sum_{\beta\in[p]}\Big((c_{\up}\mu(c_{\rs} + c_{\mpas}))^{m}\|\mathbf{H}^{(0)}\|_{F} + \|\mathbf{Y}\|_{F}\Big)\left\|\frac{\partial \mathbf{h}_v^{(m)}}{\partial h_u^{(k),\beta}}\right\| \label{eq:app:proof:vanishing:1}
\end{align}

where in the last step used <Ref>. Now it will be given a new bound on the sensitivity – differently from the analysis in earlier Sections.
Given that is necessary to integrate over all possible pairwise contributions to compute the gradient of the loss, the topological information depending on the choice of $v,u$ is no loger needed. The idea below, is to apply the Kronecker product formalism to derive a single operator in the tensor product of feature and graph space acting on the Jacobian matrix – this allows to derive much sharper bounds. Note that, once a node $u$ is fixed and a $\beta\in[p]$, is possible to write

\begin{align*}
\left\|\frac{\partial \mathbf{H}^{(m)}}{\partial h_u^{(k),\beta}}\right\|^{2} &\leq \sum_{v\in\V}\sum_{\alpha\in [p]}c_{\up}^{2}\Big( c_{\rs}\OMEga^{(m)}_{\alpha\gamma}\frac{\partial h_v^{(m-1),\gamma}}{\partial h_{u}^{(k),\beta}} + c_{\mpas}\W^{(m)}_{\alpha\gamma}\Anorm_{vz}\frac{\partial h_z^{(m-1),\gamma}}{\partial h_{u}^{(k),\beta}}  \Big)^{2} \\
&= c_{\up}^{2}\sum_{v\in\V}\sum_{\alpha\in [p]}\Big(\Big(c_{\rs}\OMEga^{(m)}\otimes \mathbf{I} + c_{\mpas}\W^{(m)}\otimes \Anorm \Big)\frac{\partial \mathbf{H}^{(m-1)}}{\partial h_u^{(k),\beta}}\Big)_{v,\alpha}^{2} \\
&\leq c_{\up}^{2}\| c_{\rs}\OMEga^{(m)}\otimes \mathbf{I} + c_{\mpas}\W^{(m)}\otimes \Anorm \|_{2}^{2} \left\|\frac{\partial \mathbf{H}^{(m-1)}}{\partial h_u^{(k),\beta}}\right\|_{F}^{2}
\end{align*}

meaning that

\begin{equation*}
\left\|\frac{\partial \mathbf{H}^{(m)}}{\partial h_u^{(k),\beta}}\right\| \leq (c_{\up}\mu(c_{\rs} + c_{\mpas}))^{m-k},
\end{equation*}

where (i) the largest singular value of the weight matrices is $\mu$, (ii) that the largest eigenvalue of $c_{\rs}\mathbf{I} + c_{\mpas}\Anorm$ is $c_{\rs} + c_{\mpas}$ (as follows from $\Anorm = \mathbf{I} - \Lnorm$, and the spectral analysis of $\Lnorm$), (iii) that $\| \partial\mathbf{H}^{(k)} / \partial h_u^{(k),\beta} \| = 1$. The proof is complexed once the term $\| \mathbf{Y}\|$ is absorbed in the constant $C$ in <Ref>.

This Section considers the convolutional family of $\MPNN$ in <Ref>.
Before proving the main results of this Section, it is necessary to comment the main assumption on the nonlinearity and formulate it more explicitly. Take $k < m$. When the sensitivity of $\mathbf{h}_v^{(m)}$ w.r.t $\mathbf{h}_u^{(k)}$ is computed, it yields a sum of different terms over all possible paths from $v$ to $u$ of length $m-k$. In this case, the derivative of
$\mathsf{ReLU}$ acts as a Bernoulli variable evaluated along all these possible paths. Similarly to <cit.>, it is necessary that  following assumption holds:

Assume that all paths in the computation graph
of the model are activated with the same probability of
success $\rho$.
The expectation $\mathbb{E}[\partial \mathbf{h}_{v}^{(m)} / \partial \mathbf{h}_{u}^{(k)}]$, means taking the average over such Bernoulli variables.

Thanks to <Ref>, is possible to follow the same argument in the proof of Theorem 1 in <cit.> to derive

\begin{equation*}
\mathbb{E}\left[\frac{\partial \mathbf{h}_{v}^{(m)}}{\partial\mathbf{h}_{u}^{(k)}}\right] = \rho\prod_{s = k+1}^{m}\W^{(s)}(\oper^{m-k})_{vu}.
\end{equation*}

Now, let's proceed to prove the relation between sensitivity analysis and access time.

Under <Ref>, The term $\mathbf{J}_k^{(m)}(v,u)$ can be rewritten as

\begin{align*}
\mathbb{E}\Big[\mathbf{J}_k^{(m)}(v,u)\Big] &= \mathbb{E}\Big[ \frac{1}{d_v}\frac{\partial \mathbf{h}_{v}^{(m)}}{\partial \mathbf{h}_{v}^{(k)}} - \frac{1}{\sqrt{d_v d_u}}\frac{\partial \mathbf{h}_{v}^{(m)}}{\partial \mathbf{h}_{u}^{(k)}}\Big] \\
&= \rho\prod_{s = k+1}^{m}\W^{(s)}\Big(\frac{1}{d_v}(\oper^{m-k})_{vv} - \frac{1}{\sqrt{d_v d_u}}(\oper^{m-k})_{vu} \Big).
\end{align*}

Since $\oper = c_{\rs}\mathbf{I} + c_{\mpas}\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, the spectral decomposition of the graph Laplacian can be employed – see the conventions and notations introduced in <Ref> – to write

\begin{equation*}
\oper = \sum_{\ell = 0}^{n-1}\left(c_{\rs} + c_{\mpas}(1-\lambda_{\ell})\right)\eigen_{\ell}\eigen_{\ell}^\top,
\end{equation*}

where $\Lnorm \eigen_\ell = \lambda_\ell \eigen_\ell$. Therefore, is possible to bound (in expectation) the Jacobian obstruction by

\begin{align*}
\obst^{(m)}(v,u) &= \sum_{k=0}^{m}\| \mathbf{J}^{(m)}_k(v,u) \| \geq \sum_{k = 0}^{m} \rho\nu^{m-k}\Big|\Big(\frac{1}{d_v}(\oper^{m-k})_{vv} - \frac{1}{\sqrt{d_v d_u}}(\oper^{m-k})_{vu} \Big)\Big| \\
&\geq \rho \Big|\sum_{k = 0}^{m} \nu^{m-k}\Big(\frac{1}{d_v}(\oper^{m-k})_{vv} - \frac{1}{\sqrt{d_v d_u}}(\oper^{m-k})_{vu} \Big)\Big| \\
&= \rho \Big|\sum_{k = 0}^{m} \nu^{m-k}\sum_{\ell = 0}^{n-1}\Big(c_{\rs} + c_{\mpas}(1-\lambda_{\ell})\Big)^{m-k}\left(\frac{\eigen^{2}_\ell(v)}{d_v} - \frac{\eigen_\ell(v)\eigen_\ell(u)}{\sqrt{d_u d_v}}\right)\Big| \\
&= \rho\Big| \sum_{\ell = 0}^{n-1}\Big(\sum_{k = 0}^{m} \nu^{m-k}\left(c_{\rs} + c_{\mpas}(1-\lambda_{\ell})\right)^{m-k}\Big)\Big(\frac{\eigen^{2}_\ell(v)}{d_v} - \frac{\eigen_\ell(v)\eigen_\ell(u)}{\sqrt{d_u d_v}}\Big)\Big|\\
&= \rho\Big|\sum_{\ell = 1}^{n-1}\sum_{k = 0}^{m} \left(\nu(c_{\rs} + c_{\mpas}(1-\lambda_{\ell}))\right)^{m-k}\Big(\frac{\eigen^{2}_\ell(v)}{d_v} - \frac{\eigen_\ell(v)\eigen_\ell(u)}{\sqrt{d_u d_v}}\Big)\Big|,
\end{align*}

where the last equality uses $\eigen_0(v) = \sqrt{d_v}/(2\lvert \E\rvert)$ for each $v\in\V$. By expanding the geometric sum using the assumption $\nu(c_{\rs} + c_{\mpas}) = 1$ and writing

\begin{equation*}
\obst^{(m)}(v,u) \geq \rho\Big|\sum_{\ell = 1}^{n-1}\frac{1 - \left(\nu(c_{\rs} + c_{\mpas}(1-\lambda_\ell))\right)^{m+1}}{1 - \nu(c_{\rs} + c_{\mpas}) +\nu c_{\mpas}\lambda_\ell}\Big(\frac{\eigen^{2}_\ell(v)}{d_v} - \frac{\eigen_\ell(v)\eigen_\ell(u)}{\sqrt{d_u d_v}}\Big)\Big|;
\end{equation*}

since $\nu(c_{\rs} + c_{\mpas}) = 1$, is possible to simplify the lower bound as

\begin{equation*}
\obst^{(m)}(v,u) \geq \rho\Big|\sum_{\ell = 1}^{n-1}\frac{1}{\nu c_{\mpas}\lambda_\ell} \Big(\frac{\eigen^{2}_\ell(v)}{d_v} - \frac{\eigen_\ell(v)\eigen_\ell(u)}{\sqrt{d_u d_v}}\Big)\Big| - \rho\Big| \sum_{\ell = 1}^{n-1}\frac{\left(\nu(c_{\rs} + c_{\mpas}(1-\lambda_\ell))\right)^{m+1}}{\nu c_{\mpas}\lambda_\ell}\Big(\frac{\eigen^{2}_\ell(v)}{d_v} - \frac{\eigen_\ell(v)\eigen_\ell(u)}{\sqrt{d_u d_v}}\Big) \Big|.
\end{equation*}

By <cit.>, the first term is equal to $\lvert (\nu c_{\mpas})^{-1}\mathsf{t}(u,v)/2\lvert\E\rvert \rvert$ which is a positive number. Concerning the second term, recall that the eigenvalues of the graph Laplacian are ordered from smallest to largest and that $\eigen_\ell$ is a unit vector, so

\begin{equation*}
\obst^{(m)}(v,u) \geq \frac{\rho}{\nu c_{\mpas}}\frac{\mathsf{t}(u,v)}{2\lvert \E\rvert} - \frac{\rho(1 - \nu c_{\mpas}\lambda^\ast)^{m+1}}{\nu c_{\mpas}\lambda_1}\frac{n-1}{d_{\mathrm{min}}},
\end{equation*}

with $\lambda^\ast$ such that $\lvert 1 - \lambda^\ast \rvert = \max_{\ell > 0}\lvert 1 - \lambda_\ell \rvert$ which completes the proof.

This proof follows the same strategy used in the proof of <Ref>. Under <Ref>, the term $\mathbf{J}_k^{(m)}(v,u)$ can be written as

\begin{align*}
\mathbb{E}\Big[\mathbf{J}_k^{(m)}(v,u)\Big] &= \mathbb{E}\left[ \frac{1}{d_v}\frac{\partial \mathbf{h}_{v}^{(m)}}{\partial \mathbf{h}_{v}^{(k)}} - \frac{1}{\sqrt{d_v d_u}}\frac{\partial \mathbf{h}_{v}^{(m)}}{\partial \mathbf{h}_{u}^{(k)}} + \frac{1}{d_u}\frac{\partial \mathbf{h}_{u}^{(m)}}{\partial \mathbf{h}_{u}^{(k)}}  - \frac{1}{\sqrt{d_v d_u}}\frac{\partial \mathbf{h}_{u}^{(m)}}{\partial \mathbf{h}_{v}^{(k)}}\right] \\
&= \rho\prod_{s = k+1}^{m}\W^{(s)}\Big(\frac{1}{d_v}(\oper^{m-k})_{vv} + \frac{1}{d_u}(\oper^{m-k})_{uu} - 2(\oper^{m-k})_{vu} \Big)
\end{align*}

where it has been used the symmetry of $\oper$. Notice that the term within brackets can be equivalently reformulated as

\begin{equation*}
\frac{1}{d_v}(\oper^{m-k})_{vv} + \frac{1}{d_u}(\oper^{m-k})_{uu} - 2(\oper^{m-k})_{vu} = \langle \frac{\mathbf{e}_v}{\sqrt{d_v}} - \frac{\mathbf{e}_u}{\sqrt{d_u}}, \oper^{m-k}\Big(\frac{\mathbf{e}_v}{\sqrt{d_v}} - \frac{\mathbf{e}_u}{\sqrt{d_u}}\Big)\rangle
\end{equation*}

where $\mathbf{e}_v$ is the vector with $1$ at entry $v$, and zero otherwise. In particular,

Please notice an important fact: since, by assumption, $c_{\rs} \geq c_{\mpas}$ and $\lambda_{n-1} < 2$, whenever $\gph$ is not bipartite, $\oper$ is a positive definite operator. Then a bound (in expectation) the Jacobian obstruction can be computed by

\begin{align*}
\tilde{\obst}^{(m)}(v,u) &= \sum_{k=0}^{m}\| \mathbf{J}^{(m)}_k(v,u) \| \leq \sum_{k = 0}^{m} \rho\mu^{m-k}\sum_{\ell = 0}^{n-1}\left(c_{\rs} + c_{\mpas}(1-\lambda_{\ell})\right)^{m-k}\Big(\frac{\eigen_\ell(v)}{\sqrt{d_v}} - \frac{\eigen_\ell(u)}{\sqrt{d_u}}\Big)^{2} \\
&= \rho\sum_{\ell = 0}^{n-1}\left(\sum_{k = 0}^{m} \mu^{m-k}\left(c_{\rs} + c_{\mpas}(1-\lambda_{\ell})\right)^{m-k}\right)\Big(\frac{\eigen_\ell(v)}{\sqrt{d_v}} - \frac{\eigen_\ell(u)}{\sqrt{d_u}}\Big)^{2} \\
&= \rho\sum_{\ell = 1}^{n-1}\left(\sum_{k = 0}^{m} \mu^{m-k}\left(c_{\rs} + c_{\mpas}(1-\lambda_{\ell})\right)^{m-k}\right)\Big(\frac{\eigen_\ell(v)}{\sqrt{d_v}} - \frac{\eigen_\ell(u)}{\sqrt{d_u}}\Big)^{2},
\end{align*}

where in the last equality $\eigen_0(v) = \sqrt{d_v}/(2\lvert \E\rvert)$. Therefore, is possible to expand the geometric sum by using the assumption $\mu(c_{\rs} + c_{\mpas})\leq 1$ and write

\begin{align*}
\tilde{\obst}^{(m)}(v,u) &\leq \rho\sum_{\ell = 1}^{n-1}\frac{1 - \left(\mu(c_{\rs} + c_{\mpas}(1-\lambda_\ell))\right)^{m+1}}{1 - \mu(c_{\rs} + c_{\mpas}) +\mu c_{\mpas}\lambda_\ell}\Big(\frac{\eigen_\ell(v)}{\sqrt{d_v}} - \frac{\eigen_\ell(u)}{\sqrt{d_u}}\Big)^{2} \\
&\leq \sum_{\ell = 1}^{n-1}\frac{\rho}{\mu c_{\mpas}\lambda_\ell}\Big(\frac{\eigen_\ell(v)}{\sqrt{d_v}} - \frac{\eigen_\ell(u)}{\sqrt{d_u}}\Big)^{2} \\
& = \frac{\rho}{\mu c_{\mpas}}\sum_{\ell = 1}^{n-1}\frac{1}{\lambda_\ell}\Big(\frac{\eigen_\ell(v)}{\sqrt{d_v}} - \frac{\eigen_\ell(u)}{\sqrt{d_u}}\Big)^{2} \\
& = \frac{\rho}{\mu c_{\mpas}}\res(v,u)
\end{align*}

where in the last step, the spectral characterization of the effective resistance derived in <cit.> has been used – which was also leveraged in <cit.> to derive a novel rewiring algorithm. Since by <cit.> it holds $2\res(v,u)\lvert\E\rvert = \tau(v,u)$, this completes the proof of the upper bound. The lower bound case follows by a similar argument. In fact, one arrives at the estimate

\begin{align*}
\tilde{\obst}^{(m)}(v,u) &\geq \rho\sum_{\ell = 1}^{n-1}\frac{1 - \left(\nu(c_{\rs} + c_{\mpas}(1-\lambda_\ell))\right)^{m+1}}{1 - \nu(c_{\rs} + c_{\mpas}) +\nu c_{\mpas}\lambda_\ell}\Big(\frac{\eigen_\ell(v)}{\sqrt{d_v}} - \frac{\eigen_\ell(u)}{\sqrt{d_u}}\Big)^{2}.
\end{align*}

\[
1 - \left(\nu(c_{\rs} + c_{\mpas}(1-\lambda_\ell))\right)^{m+1} \geq 1 - \left(\nu(c_{\rs} + c_{\mpas}(1-\lambda^\ast))\right)^{m+1},
\]

where $\lvert 1 -\lambda^\ast\rvert = \max_{\ell > 0} \lvert 1 - \lambda^\ast\rvert$.
Next, find that

\[
\frac{1}{1 - \nu(c_{\rs} + c_{\mpas}) +\nu c_{\mpas}\lambda_\ell} \geq \frac{\epsilon}{\nu c_{\mpas}\lambda_\ell} \Longleftrightarrow \lambda_\ell \geq \frac{\epsilon}{1-\epsilon}\, \frac{1-\nu (c_{\rs} + c_{\mpas})}{\nu c_{\mpas}}.
\]

Since the eigenvalues are ordered from smallest to largest, it suffices that

\[
\lambda_1 \geq \frac{\epsilon}{1-\epsilon}\, \frac{1-\nu (c_{\rs} + c_{\mpas})}{\nu c_{\mpas}} \Longleftrightarrow \epsilon \leq \epsilon_\gph := \frac{\lambda_1}{\lambda_1 + \frac{1 - \nu(c_{\rs}+c_{\mpas})}{\nu c_{\mpas}}}.
\]

This completes the proof.

It worth emphasize that without the degree normalization, the bound would have an extra-term (potentially diverging with the number of layers) and simply proportional to the degrees of nodes $v,u$. The extra-degree normalization is off-setting this uninteresting contribution given by the steady state of the Random Walks.

CHAPTER: ON THE SYMMETRIES OF TOPOLOGICAL NEURAL NETWORKS

§ PRIMER ON CATEGORY THEORY

Category theory is a branch of mathematics that deals with abstract structures and relationships between them. It provides a unified framework to study mathematical concepts in a way that emphasizes their relationships, rather than the objects themselves. While the  main goal of this thesis, is to study topological neural networks, a grasp of category theory can provide a bird-eye view of the underlying symmetries of these models.

§.§.§ Objects and Morphisms

A ["id"description, loop, distance=2em, in=125, out=55]        B        C
["f", from=1-1, to=1-3]
["g", from=1-3, to=1-5]
["g ∘f", curve=height=-24pt, from=1-1, to=1-5]

Illustration of the Composition concept. If there is a morphism $ f $ from object $ A $ to $ B $ and another morphism $ g $ from $ B $ to $ C $, then there is a morphism $ g \circ f $ from $ A $ to $ C $.

The foundation of category theory groudns on the fundamental notion of
a category $\mathcal{C}$ composed by objects and morphisms.

Objects can be thought of as mathematical entities or structures. For the purposes of this thesis, think of them as containers or placeholders that represent mathematical objects, such as sets, groups, rings and so on. In this case, objects are discrete topological spaces equipped with signals. In <Ref>, the objects are denoted wiht $A$, $B$ and $C$.

Morphisms are the relationships between objects. They can be described as transformations between two objects within the catorgy $\mathcal{C}$. Morphisms must satisfy two properties: composition: if there exists a morphism $f$ from object $A$ to $B$ and another morphism $g$ from $B$ to $C$, then a morphism $g \circ f$ from $A$ to $C$ must also exist (<Ref>) and identity For every object, there exists a morphism that maps it to itself, called the identity morphism. Since often this is omitted from the diagrams, in <Ref> the identity morphism is represented only for the object $A$.

A category $\mathcal{C}$  consists in a collection of objects and morphisms with the condition that morphisms can be composed, and this composition is associative. Each object has an associated identity morphism.

In essence, a category captures a mathematical world where objects and their relationships live. To relate different mathematical structures, the concept of functor bridges the gap between seemingly unrelated categories .

A functor $F$ is a map between two categories that maintains the object-morphism structure. Think of it as a transformer (not the transformer architecture <cit.>) that takes objects and morphisms from one category and produces corresponding objects and morphisms in another category while preserving their relationships.

§.§ Why Category Theory for Topological Neural Networks?

By modeling the symmetries of topological neural networks within the framework of category theory, is possible to exploit powerful mathematical concepts to elegantly express and prove the equivariance of such models. When objects like simplicial or cell complexes and morphisms like permutation matrices are considered, the problem is naturally embedded into a categorical framework, giving a rich language and toolkit to work with.

§.§.§ A Categorical Perspective on the Symmetries of Topological Neural Networks

Let $\mathcal{C}$ be a category such that, in the context of message passing schemes on discrete topological spaces the objects in $\mathcal{C}$ are complexes $\xph$ equipped with sequences of boundary matrices, $\mathbf{B} = (\Bnorm_1, \ldots, \Bnorm_K)$, and feature matrices $\mathbf{H} = (\mathbf{H}_0, \ldots, \mathbf{H}_K) $. The morphisms in $\mathcal{C}$ are sequences of permutation matrices $\mathbf{P} = (\Pnorm_0, \ldots, \Pnorm_K)$. These act on the complexes, permuting them as: $\mathbf{P}: \xph \to P(\xph)$.

Given this structure, permutation equivariance and invariance can be defined in terms of functoriality.

A functor $F: \mathcal{C} \to \mathcal{C} $ is equivariant if, for any object $\xph$ in $\mathcal{C}$ and any morphism $\mathbf{P}: \xph \to \mathbf{P}(\xph)$ in $\mathcal{C}$, it holds

\begin{equation}
F(\mathbf{P}(\xph)) = (F  \circ \mathbf{P})(\xph) =( F \circ \mathbf{P}   )(\xph) = \mathbf{P}\, F(\xph),
\end{equation}

such that the following diagram commutes:

r𝐏 [swap]dF     P() dF

F() rF(𝐏)     F(P())

A functor $ F: \mathcal{C} \to \mathcal{C} $ is invariant if, for any object $\xph$ in $\mathcal{C}$ and any morphism $ \mathbf{P}: \xph \to \mathbf{P}(\xph) $ in $\mathcal{C}$,

\begin{equation}
F(\mathbf{P}(\xph)) = (F  \circ \mathbf{P})(\xph) =( F \circ \mathbf{P}   )(\xph) = F(\xph)
\end{equation}

such that the following diagram commutes:

["F(𝐏)"', from=1-1, to=3-3]
["F", from=1-3, to=3-3]
["𝐏", from=1-1, to=1-3]

Assume a topological neural network $\mathsf{TNN}_{\theta}$ as in <Ref> which acts as a functor $F$. Consider any complex $\xph$ with boundary $\mathbf{B}$ and feature matrices $\mathbf{H}$. When the sequence of permutation matrices $\mathbf{P}$ acts on $\xph$, it results in a permuted complex $P(\xph)$.

For permutation equivariance, it holds:

\begin{equation}
\mathsf{TNN}_{\theta}(\mathbf{P} \mathbf{H}, \mathbf{P} \mathbf{B} \mathbf{P}^\top) = \mathbf{P} \, \mathsf{TNN}_{\theta}(\mathbf{H}, \mathbf{B}),
\end{equation}

which is analogous to:

\begin{equation}
F(\mathbf{P}(\xph)) =   (\mathbf{P} \circ F)(\xph).
\end{equation}

When $\mathbf{P}$ is applied on $\xph$, the topological neural network represented with the functor $F$ respects the permuted relationships and produces an output that is a permuted version of the original. Thus, the network $\mathsf{TNN}_{\theta}$ satisfies the condition of being equivariant as defined in category theory.

This concludes the proof of permutation equivariance for topological neural networks from a categorical perspective.

CHAPTER: COMPUTATIONAL COMPLEXITY AND LEARNABLE PARAMETERS OF CELL ATTENTION NETWORKS

Structural Lift

Although this operation can be pre-computed for the entire dataset and the connectivity results stored for later use, it is worth eliciting its complexity, noting that for some applications, the storage of the upper and lower connectivity for the entire dataset might not be possible.

The chord-less cycles in a graph can thus be enumerated in $\mathcal{O}((|E| + |V| R) \, \textrm{polylog} |V|)$ time <cit.> where $R$ is upper bounded by a small constant. Thus, the complexity of this operation can be approximated to be linear in the size of the complex (i.e., the overall number of cells $\sigma \in \cph$. Intuitively, structural lifts do not involve any parameter to be learned during training.

Functional Lift

The complexity of this operation is equivalent to a multi-head attention message passing scheme over the entire graph. For a single node pair $i,j \in \V$ connected by an edge $e \in \E$, the functional lift defined in <Ref> can be decomposed into $F_e$ independent transformations. Each map requires $\mathcal{O}(F_n)$ computations, where $F_n$ is the number of input node features. Thus, for the pair $i,j$, the functional lift is performed in $\mathcal{O}(F_e F_n)$, where $F_e$ is a parameter to be chosen as the number of input edge features. Accounting all the edges of the complex yields an amount of $\mathcal{O}(\vert \E \vert F_e F_n)$ operations to lift node features into edge ones. In the context of lifting a pair of graph node features $\mathbf{x}_u, \mathbf{x}_v \in \mathbb{R}^{F_n}$ to obtain edge features $\mathbf{x}_{e} \in \mathbb{R}^{F_e}$, the attention parameters are involved. The parameters to learn the transformations $\Wnorm_1 \in \mathbb{R}^{2 F_n \times F_e}$ and $\Wnorm_2 \in \mathbb{R}^{F_e \times F_e}$ are therefore on the order of $\Theta \left( F_e F_n \right)$.

Cell Attention

This operation consists in two independent masked self-attention message passing schemes over the upper and lower neighbourhoods of the complex, namely cell attention, an inner linear transformation of the edges' features and an outer point-wise nonlinear activation (<Ref>). For a layer $l$, the number of messages that an edge $e$ receives from its lower neighbourhood is equal to $\vert \mathcal{N}_{\downarrow}(e) \vert$, the number of edges that share a common node with $e$.  The same computation yields for the upper neighbourhood: edge $e$ receives $\vert \mathcal{N}_{\doarr}(e) \vert$ messages, from edges that are in the same cell's boundaries as $e$. Recalling that $\E^{(l+1)} \subseteq \E^{(l)}$ and $R$ is upper bounded by a small constant <cit.>, in a single message passing the number of messages that and edge $e$ receives is bounded by $\mathcal{O}(\vert \E \vert )$, where $\E$ is the initial number of edges of $\cph$. The inner linear transformation that propagates the information contained in $\mathbf{h}_e$ is upper bounded by $\mathcal{O}(F_e^2)$. Extending this to all edges of the complex, the complexity of a cell attention layer can be rewritten as $\mathcal{O}(|\E|\, F_e^2)$. In the case of a multi-head cell attention, the complexity receives an overhead induced by the number of attention heads involved within the layer, i.e., a multiplication by a factor $H$, the number of cell attention heads. In terms of learnable parameters and in the case of the  GAT-like attention functions <cit.>, a single cell attention layer is composed of: two independent vectors of attention coefficients $\mathbf{a}_{\doarr}, \mathbf{a}_{\uparr} \in \mathbb{R}^{2F_e}$ for properly weighting the lower and upper neighbourhoods, respectively. Moreover, the layer is equipped with three linear transformations, $\mathbf{W}, \mathbf{W}_{\doarr}, \mathbf{W}_{\uparr} \in \mathbb{R}^{F_e \times F_e}$ acting respectively on: $\mathbf{h}_e$, the latent representation of edge $e$  and the hidden features $\mathbf{h}_k$ in the lower and upper neighbourhoods of the edge $e$. If instead the dynamic attention proposed in <cit.> is used, the size of the weight matrices increases to $\mathbf{W}, \mathbf{W}_{\doarr}, \mathbf{W}_{\uparr} \in \mathbb{R}^{F_e \times 2 F_e}$ while the vectors of attention coefficients reduce to $\mathbf{a}_{\doarr}, \mathbf{a}_{\uparr} \in \mathbb{R}^{F_e}$.. Thus, independently on the particular graph attention mechanism employed, the number of learnable parameters of a cell attention layer is $\mathcal{O}(F_e^2)$.

Edge Pool

The operations involved in the pooling layer can be decomposed in: (i) computing the self-attention scores for each edge of the complex ($\gamma_e$ from <Ref>); (ii) select the highest $\lceil k \, \vert \E \vert \, \rceil$ values from a collection of self-attention scores ($\text{top-k}(\{\gamma_e\}_{e \in \E}, \lceil k |\E| \rceil)$); and (iii) adjust the connectivity of the complex (<Ref>). To compute the computational complexity of this layer, it is convenient to view the selection operation as a combination of a sorting algorithm over a collection of self-attention scores and the selection of the first $\lceil k , \vert \E \vert , \rceil$ elements from the sorted collection. Since the computations involved in (i) and (iii) are linear in the dimension of the complex, the overall complexity of this layer in can be upper bounded by the sorting algorithm, i.e., $\mathcal{O}(|\E| \; log (|\E|))$. Please notice that, in the context of the edge pooling operation the number of elements of $\E$ is reduced after each layer. For this operation, learnable parameters are employed only in computing the self-attention scores ($\gamma_e$ (<Ref>)). In the case of the GAT-like attention functions <cit.>, they consist of a shared vector of attentional scores' coefficients $\mathbf{a}_p \in \mathbb{R}^{F_e}$, similarly to the lift layer, leading to $\Theta \left( F_e \right)$.

CHAPTER: APPENDIX CIN++

§ EXPRESSIVE POWER

This section analyse the expressive power of enhanced topological message passing. Two complexes $\cph_1$ and $\cph_2$ are said to be isomorphic (written $\cph_1 \simeq \cph_2$) if there exists a bijection $\varphi:\mathcal{P}_{\cph_1} \to \mathcal{P}_{\cph_2}$ such that $\sigma \in \cph_1 \iff \varphi(\sigma) \in \cph_2$ <cit.>. Also, a cell coloring $c$ refines a cell coloring $d$, written $c \sqsubseteq d$, if $c(\sigma) = c(\tau) \implies d(\sigma) = d(\tau)$ for every $\sigma,\tau \in \cph$.
Two colorings are equivalent if $c \sqsubseteq d$ and $d \sqsubseteq c$, and it is written as: $c \equiv d$ <cit.>.

Let $c^l$ be the colouring of CWL <cit.> at iteration $l$ and $h^l$ the colouring (i.e., the multi-set of features) provided by a CIN++ network at layer $l$ as in <Ref>.

To show that CIN++ inherits all the properties of Cellular Isomorphism Networks <cit.> it is necessary to show that the proposed topological message passing scheme produces a colouring of the complex that satisfies Lemma 26 of <cit.>.

To show $c^t \sqsubseteq h^t$ by induction, assume $h^l = h^L$ for all $l > L$, where $L$ is the number of the network's layers.
Let also $\sigma, \tau$ be two arbitrary cells with $c^{l+1}_\sigma = c^{l+1}_\tau$. Then, $c^l_\sigma = c^l_\tau$, $c^l_\mathcal{B}(\sigma) = c^l_\mathcal{B}(\tau)$, $c^l_\uparrow(\sigma) = c^l_\uparrow(\tau)$ and $c^l_\downarrow(\sigma) = c^l_\downarrow(\tau)$. By the induction hypothesis, $h^l_\sigma = h^l_\tau$, $h^l_\mathcal{B}(\sigma) = h^l_\mathcal{B}(\tau)$, $h^l_\uparrow(\sigma) = h^l_\uparrow(\tau)$ and $h^l_\downarrow(\sigma) = h^l_\downarrow(\tau)$.

If $l+1 > L$, then $h^{l+1}_\sigma = h^{l}_\sigma = h^l_\tau = h^{l+1}_\tau$. Otherwise, $h^{l+1}$ is given by the update function in Equation <ref>. Given that the inputs passed to these functions are equal for $\sigma$ and $\tau$, $h^{l+1}_\sigma = h^{l+1}_\tau$.

For showing  $h^l \sqsubseteq c^l$, suppose the aggregation from Equation <ref> is injective and the model is equipped with a sufficient number of layers such that the convergence of the colouring is guaranteed. Let $\sigma, \tau$ be two cells with $h^{l+1}_\sigma = h^{l+1}_\tau$. Then, since the local aggregation is injective $h^l_\sigma = h^l_\tau$, $h^l_\mathcal{B}(\sigma) = h^l_\mathcal{B}(\tau)$, $h^l_\uparrow(\sigma) = h^l_\uparrow(\tau)$ and $h^l_\downarrow(\sigma) = h^l_\downarrow(\tau)$. By the induction hypothesis, $c^l_\sigma = c^l_\tau$, $c^l_\mathcal{B}(\sigma) = c^l_\mathcal{B}(\tau)$,  $c^l_\uparrow(\sigma) = c^l_\uparrow(\tau)$ and   $c^l_\downarrow(\sigma) = c^l_\downarrow(\tau)$ which implies that $c^{l+1}_\sigma = c^{l+1}_\tau$.

Given that $c^t \sqsubseteq h^t$ and $h^l \sqsubseteq c^l$, is possible to conclude that $h^l \equiv c^l$.

As a result, CIN++ inherits all the properties of Cellular Isomorphism Networks, in accordance with Lemma 26 from <cit.>.

§ A CATEGORICAL INTERPRETATION: SHEAVES

It worth to notice that CIN++ can be seen as a particular case of a message passing scheme over a cellular sheaf.
Let $\cph$ be a regular cell complex. A cellular sheaf is a mathematical object that attaches data spaces to the
cells of $\cph$ together with relations that specify when assignments to these data
spaces are consistent.

<cit.> A cellular sheaf of vector spaces on a regular cell complex $\cph$ is an
assignment of a vector space $\mathcal{F}(\sigma)$ to each cell $\sigma$ of $\cph$
together with a linear transformation $\mathcal{F}_{\sigma\face\tau}\colon \mathcal{F}(\sigma)
\to \mathcal{F}(\tau)$ for each incident cell pair $\sigma\,\face\,\tau$. These must
satisfy both an identity relation $\mathcal{F}_{\sigma\face\sigma}={id}$ and the
composition condition:

\[
\rho\,\face\,\sigma\,\face\,\tau
\mathcal{F}_{\rho\face\tau} = \mathcal{F}_{\sigma\face\tau}\circ\mathcal{F}_{\rho\face\sigma}.
\]

It is also natural to consider a dual construction to a
cellular sheaf to preserves stalk data but reverses
the direction of the face poset, and with it, the restriction maps.
A cellular cosheaf of vector spaces on a regular cell complex $\cph$ is an
assignment of a vector space $\mathcal{F}(\sigma)$ to each cell $\sigma$ of  $\cph$
together with linear maps $\mathcal{F}^{\text{op}}_{\sigma\face\tau}\colon \mathcal{F}(\tau) \to
\mathcal{F}(\sigma)$ for each incident cell pair $\sigma\,\face\,\tau$ which satisfies
the identity ($\mathcal{F}^{\text{op}}_{\sigma\face\sigma}={id}$) and composition condition:

\[
\rho\,\face\,\sigma\,\face\,\tau
\mathcal{F}^{\text{op}}_{\rho\face\tau} = \mathcal{F}^{\text{op}}_{\rho\face\sigma}\circ\mathcal{F}^{\text{op}}_{\sigma\face\tau} .
\]

The vector space $\mathcal{F}(\sigma)$ is called the stalk of $\mathcal{F}$ at $\sigma$ and will encode the features supported over $\sigma$. The maps $\mathcal{F}_{\sigma\face\tau}$ and $\mathcal{F}^{\text{op}}_{\sigma\face\tau}$ are called the restriction maps and will provide a principled way to respectively move features from lower dimensional cells to higher dimensional ones and vice-versa.

From a categorical perspective, a cellular sheaf is a functor $\mathcal{F} : \mathcal{P}_{\cph} \rightarrow \mathbf{Vect}_{\mathbb{R}}$ that maps the indexing set $\mathcal{P}_{\cph}$ to the category of vector spaces over $\mathbb{R}$ while a cellular cosheaf is a functor $ \mathcal{F}^{\text{op}} : \mathcal{P}_{\cph}^{\text{op}} \to
\mathbf{Vect}_{\mathbb{R}}$ such that, for a two dimensional regular cell complex $\cph$, a sheaf $(\mathcal{F}, \mathbb{R})$ and its dual cosheaf $(\mathcal{F}^{\text{op}}, \mathbb{R})$ on  $\cph$, the following diagram commutes:

Pictorial example of a sheaf and cosheaf of vector spaces structure on a ring of a regular cell complex $\cph$.

\[\begin{tikzcd}[sep=2.25em]
{\mathcal{F}(v)} &&& {\mathcal{F}(e)} \\
\\
\\
&&& {\mathcal{F}(r)}
\arrow["{\mathcal{F}_{v\face e}}", from=1-1, to=1-4]
\arrow["{\mathcal{F}_{e \face r}}", from=1-4, to=4-4]
\arrow["{\mathcal{F}_{v \face r}}"', shift right=1, curve={height=30pt}, dashed, from=1-1, to=4-4]
\arrow["{\mathcal{F}_{v \face r}^{\text{op}}}"', shift right=1, curve={height=-30pt}, dashed, from=4-4, to=1-1]
\arrow["{\mathcal{F}_{e \face r}^{\text{op}}}", shift left=2, from=4-4, to=1-4]
\arrow["{\mathcal{F}_{v \face e}^{\text{op}}}", shift left=2, from=1-4, to=1-1]
\end{tikzcd}\]

In the given commutative diagram, the arrow is dashed to indicate that the morphism (map) it represents is not explicitly defined in the diagram, but rather it is implied by the other morphisms. In this case, the dashed arrow is used to show the existence of a unique morphism that makes the diagram commute. This relationship is important in the context of cellular sheaves, where these morphisms represent restrictions on different cells and their overlaps. The dashed arrows shows that there is a unique way to go from $\mathcal{F}(v)$ to $\mathcal{F}(r)$  and back that is consistent with the other restrictions, even if it is not directly defined in the diagram.


aainstitutetext: Institute for Theoretical Physics, Heidelberg University,
Philosophenweg 19, Germany

#  Group averaging and BRST quantization in de Sitter space

Mendrit Ljatifi<EMAIL_ADDRESS>
###### Abstract

In this note we give a BRST interpretation of inner product of group averaging
on de Sitter group $SO(2,1)$. Quantization approaches can be divided in two
classes, without introducing additional degrees of freedom and with
introducing ghosts, antighosts, Lagrange multipliers and canonically
conjugated momenta. The first class of quantization methods includes Dirac
method and group averaging method. The Dirac method is based on imposing the
constraint conditions on physical states, while in group averaging method one
modifies the physical inner product due to constrains.
One should distinguish the abelian case for which you can have continuous
spectrum and discrete spectrum for which there are internal topological
problems in BRST-BFV approach, and the non- abelian case.

##  1 Introduction

In this article, we review Refined Algebraic Quantization(RAQ) and the group
averaging on a de Sitter group and give a possible correspondence with the
BRST quantization.
Refined Algebraic Quantization is a set up for implementing Dirac quantization
method by beginning with unconstrained system in which also the gauge depended
operators act on the "primary" auxiliary Hilbert space $\mathcal{H}_{aux}$.
One can introduce constraints as operators $C_{i}$ on some space and then take
states that only are annihilated by those constraints which we label as
physical states $\ket{\psi}_{phys}$ Higuchi:1991tk ; Higuchi:1991tm ;
Giulini:1998kf . An important step in RAQ is defining a subspace
$\Phi\in\mathcal{H}_{aux}$ which is mapped into itself by constraints, that is
$C_{i}:\Phi\rightarrow\Phi$. Since RAQ looks for solutions of the constraints
in $\Phi^{*}$ which is the algebraic dual of $\Phi$. For RAQ to be complete we
need a map, say $\eta$, from $\Phi$ to $\Phi^{*}$, $\eta:\Phi\rightarrow\Phi$
called the "rigging" map. The importance of the "rigging" map is that we can
write the Hermitian inner product on the image of $\eta$ completing into a
Hilbert space Higuchi:1991tk ; Higuchi:1991tm ; Giulini:1998kf ;
Giulini:1998rk ; Marolf_2009 :

$\big{(}\eta(\psi_{1}),\eta(\psi_{2})\big{)}_{phys}=\eta(\psi_{1})[\psi_{2}]$
(1)

The following of the article is constructed as follow; in Section 2, we review
group averaging method for a general theory, in Section 3 we review free
scalar fields in (1+1) dimensional de Sitter space. In Section 4 we calculate
the inner product of group averaging method for $SO(2,1)$ group while in
Section 5 we give the BRST interpretation of the inner product (38).
Finally in Section 6, following Witten:2022xxp  we discuss a possible gauge
fixing model that can be constructed for our interpretation.

##  2 Review of Group Averaging

A powerful technique for studying constrained systems is what is called group
averaging Higuchi:1991tk ; Higuchi:1991tm , although it is likely to be well
defined except in certain limited cases it still allows us to many constrained
systems and physical theories.
Recall that Dirac method of quantization involves introducing the constrains
as operators on some space and then taking those states which are annihilated
by the constrains to be what we call physical states Higuchi:1991tm ;
Higuchi:1991tk .Considering that Dirac procedure is closely related to BRST
approach Becchi:1974md  those become very powerful and useful techniques when
studying quantum gauge systems.
There are number of variants of Dirac method that have been discussed
Woodhouse:1981zd  and also Higuchi:1991tk ; Higuchi:1991tm ; Kuchar:1986jj ;
Ordonez:1995kz  and Refined algebraic quantization(RAQ)Higuchi:1991tk ;
Higuchi:1991tm ; Ashtekar:1995zh ; Giulini:1998rk .
However RAQ technique becomes much more powerful when is possible to apply
what is known as "group averaging". Group averaging starts with the integral

$\int_{G}\braket{\phi_{1}}{U(g)}{\phi_{2}}dg$ (2)

over the gauge group $G$ where we define the physical Hilbert space and $dg$
is the Haar measure on G Giulini:1998kf . In particular, group averaging
provides the unique Hilbert space representation with a unique inner product
of the algebra of observables which is compatible with RAQ Gomberoff:1998ms ;
Chandrasekaran:2022cip ; Chandrasekaran:2022eqq . As described in
Giulini:1998kf  the convergent group averaging ensures a unique representation
of the algebra of observables and it must diverge in the presence of any
superselection rules Giulini:1998kf .
In the following, we consider the group $G=SO_{n}(n,1)$ acting on
$L^{2}(M^{n,1},d^{n}x)$ where $L^{2}$ is the set of square integrable
$L^{2}$-functions. The infinitesimal action of group is defined by generators
of the Lie Algebra,

$J_{\mu\nu}=\eta_{\mu\nu}x^{\alpha}\frac{\partial}{\partial
x^{\nu}}-\eta_{\nu\alpha}x^{\alpha}\frac{\partial}{\partial x^{\alpha}}$ (3)

taking the exponent of generators gives the unitary action $U(g)$ on the
group. Generators $J_{\mu\nu}$ also define the constrains of the theory where
physical states satisfy the condition

$J_{\mu\nu}\ket{\psi}_{phys}=0$ (4)

and since there is no such a normalizable states, in the language of REQ this
condition can be written as

$\bra{\psi}_{phys}J_{\mu\nu}=0$ (5)

When computing (2) we are interested in some domain $\Phi$, if the integral
converges or if it can be defined in a sensible way, it will define a map
(which we know as "rigging map") from $\Phi$ into the space of physical
states. Before going into the calculation, we first need to compute its Haar
measure. Any element $g$ in $G=SO_{c}(n,1)$ is a product of a boost and a
rotation and we can use Cartan decomposition Barut:1986dd . Choosing $x_{0}$
as time coordinate in Minkowski space, we can write an element of $G$ as
$g=h_{0}k_{0}$ for $k_{0}\in K=SO_{c}(n)$ subgroup of $G$ that preserves the
$x_{0}$ axis and $h_{0}$ a symmetric positive definite matrix(boost). In
general for $h_{0}$ we can write $h_{0}=k_{1}b(\lambda)k_{1}^{-1}$ for a
rotation $k_{1}\in K$ and $b(\lambda)$ a boost with $\lambda$ being the boost
parameter in $x^{0},x^{1}$-plane.
It is convenient to write $k=k_{1}^{-1}k_{0}$ and $h=k_{1}b(\lambda)$ so that
we have

$g=hk,\,k\in K,\,\,\,\text{and}\quad h\in H_{+}^{n}$ (6)

where $H_{+}^{n}$ can be identified as the right coset space $SO_{c}(n,1)/K$.
With a help from the equation of hyperboloid, we can represent this space as
the upper sheet of it hyperboloid

$-(x^{0})^{2}+(x^{1})^{2}+...+(x^{n})^{2}=-1$ (7)

A generic element of $H_{+}^{n}$ can be written as

$h=k_{n-1}(\theta_{n-1})k_{n-2}(\theta_{n-2})...k_{1}(\theta_{1})b(\lambda)$
(8)

where $k_{m}$ is a rotation in the plane $(x^{m},x^{m+1})$ and $b(\lambda)$ is
a hyperbolic rotation in $(x^{0},x^{1})$.
Using (7) and (8), in Minkowski coordinates we can write

$\begin{split}x^{0}&=\cosh{\lambda}\\\
x^{1}&=\sinh{\lambda}\cos{\theta_{1}}\\\
x^{2}&=\sinh{\lambda}\sin{\theta_{1}}\cos{\theta_{2}}\\\ \vdots\\\
x^{n}&=\sinh{\lambda}\sin{\theta_{1}}\sin{\theta_{2}}...\sin{\theta_{n-2}}\sin{\theta_{n-1}}\\\
\end{split}$ (9)

Writing the measure $d^{n+1}x$ as $s^{n}ds\,dh$ leads to an
$SO_{c}(n,1)$-invariant measure $dh$ for $H_{+}^{n}$ given by

$dh=\sinh^{n-1}{\lambda}\sin^{n-2}{\theta_{1}}...\sin{\theta_{n-2}}d\lambda
d\theta_{1}...d\theta_{n-1}$ (10)

where $d\lambda$ and $d\theta_{i}$ are the Lebesgue measures on certain
intervals. Following Gomberoff:1998ms ; Ashtekar:1995zh  we can write $dg$ as
$dg=dhdk$ as a Haar measure on G.
Once we have the Haar measure, we can proceed with calculation of (2). We want
to study this integral in some domain $\Phi\in\mathcal{H}_{aux}$. We proceed
by introducing distributional states $\ket{x}$ for $x\in M^{n,1}$ which
satisfy

$\braket{x_{1}}{x_{2}}=\delta^{n+1}(x+1,x_{2})$ (11)

where now we can study (2) as a distribution in both $x_{1}$ and $x_{2}$, for
which we can write

$\begin{split}I=\int dg\braket{x_{1}}{U(g)}{x_{2}}=&\frac{1}{V_{SO(n)}}\int
dk\int dg\braket{x_{1}}{U(kg)}{x_{2}}\\\ =&\frac{1}{V_{SO(n)}}\int
dkdhdk^{\prime}\braket{x_{1}}{U(khk^{\prime})}{x_{2}}\end{split}$ (12)

where $V_{SO(n)}=\int dk$ is the volume of $SO(n)$. Using the $SO(n)$
translation invariance of $dk$ (12) can be written as

$I=\frac{V_{S_{n-1}}}{V_{SO(n)}}\int
dkdk^{\prime}d\lambda\sinh^{n-1}{\lambda}\braket{x_{1}}{U(k)U(b(\lambda))U(k^{\prime})}{x_{2}}$
(13)

where $V_{S_{n-1}}=\frac{\pi^{n/2}}{\Gamma(n/2)}$ is the volume of the
$(n-1)$-sphere. Following Gomberoff:1998ms  the integral I can be easily done
for $n=1$,

$I_{n=1}=\delta\big{(}(x_{1}^{2}-t_{1}^{2}),(x_{2}^{2}-t_{2}^{2})\big{)}$ (14)

This result is in analogy with the integral $\int e^{iks}dx$ which converges
to $\delta(k)$.
For $n>1$ the integral $I$ can be written as

$I=\frac{\delta(s_{1}^{2},s_{2}^{2})}{r_{1}^{n-2}r_{2}^{n-2}}\int
d\xi\Big{[}s_{1}^{2}\xi^{2}+2t_{1}t_{2}\xi-(r_{1}^{2}+t_{2}^{2})\Big{]}^{\frac{n-3}{2}}$
(15)

where $s_{a}^{2}=\eta_{\mu\nu}x_{a}^{\mu}x_{a}^{\nu}$, for $a=1,2$,
$r^{2}=\sum_{i>0}x^{i}x^{i}$, and $\xi=\sinh{\lambda}$.
In the case when $x_{1}$ is time-like and $x_{2}$ is space-like the integral
(2) will vanish, while in the case when both $s_{1}$ and $s_{2}$ are space-
like the situation changes. In that case one can write $I$ as a divergent
factor times a Lorentz invariant quantity Gomberoff:1998ms  while for $s_{1}$
and $s_{2}$ it can be shown Gomberoff:1998ms  that the integral (2) is
convergent for $n>1$.

##  3 Free scalar fields in 1+1 de Sitter

Any theory of quantum gravity should include a description of de Sitter space
Marolf_2009 ; Hajicek:1994px ; Higuchi:1991tk , at least as an approximation.
We recall that field theories on spacetimes with Killing symmetries have
conserved charges and we regard this type of theory as zero-order perturbative
approximation to a theory of matter plus gravity. This is interesting in the
case when the background also has a compact Cauchy surface, then if you apply
the equivalent of Gauss’ law for gravity, the above charge must vanish in
order for a solution to consistently couple to dynamical gravity. These are
known as linearization-stability constrains and require that in de Sitter
space, linearized quantum states to be invariant under the de Sitter group
$SO_{0}(D,1)$ where $D$ is the space-time dimension.
Because the de Sitter group is non-compact, the standard Fock which we call
$\mathcal{H}_{aux}$ space contains no de Sitter-invariant states except for a
possible vacuum. This however is not a rich physical theory and we need a
better description of the Fock space. One may use the standard Fock space to
build a new physical one that we call $\mathcal{H}_{phys}$. We shall call this
physical Hilbert space of de Sitter invariant states. The way we build the new
physical space is via group averaging, where one considers linear
superposition of auxilary states $|\ket{\psi}$ of the form

$\ket{\psi}:=\int_{g\in G}dgU(g)|\ket{\psi}$ (16)

where G is the de Sitter group, $dg$ is the unique Haar measure of G, and
$U(g)$ gives the unitary representation of G on $\mathcal{H}_{aux}$. Since the
de Sitter group G is non-compact, the state (16) is not normalizable in
$\mathcal{H}_{aux}$. However we can define a new inner product on the group
averaged states as

$\bra{\psi_{1}}\ket{\psi_{2}}:=\bra{\psi_{1}}|\cdot|\ket{\psi_{2}}=\int_{g\in
G}dg\bra{\psi_{1}}||U(g)||\ket{\psi_{2}}$ (17)

In this section we review the group averaging for massless scalar field in
$1+1$ de Sitter space. We write the $1+1$ de Sitter metric as

$ds^{2}=\frac{l^{2}}{\cos^{2}\tau}(-d\tau^{2}+d\theta^{2})$ (18)

This form of metric is adopted from conventions of conformal field theory
which is just a conformal factor times the metric on the cylinder. $\tau$ is
the conformal time and has a range $-\pi/2<\tau<\pi/2$, and $\theta$ is
periodic $\theta\equiv\theta+2\pi$ and $l$ is the de Sitter length scale.
Adopting the light-cone coordinates, the metric can be written as

$ds^{2}=\frac{l^{2}}{2\cos^{2}\tau}\big{(}(dx^{+})^{2}+(dx^{-})^{2}\big{)}$
(19)

The action of a free scalar field is

$S=-\frac{1}{2}\int dx^{2}\sqrt{-g}g^{ab}\nabla_{a}\phi\nabla_{b}\phi=\int
dx\partial_{+}\phi\partial_{-}\phi$ (20)

The equation of motion for $\phi$ is given by $\partial_{+}\partial_{-}\phi=0$
where the solutions can be decomposed into left- and right-moving modes as

$\partial_{+}\phi(x^{+})=\frac{1}{2\sqrt{\pi}}\sum_{m}\alpha_{m}\exp[-imx^{+}],\quad\quad\partial_{-}\phi(x^{-})=\frac{1}{2\sqrt{\pi}}\sum_{m}\tilde{\alpha}_{m}\exp[-imx^{-}]$
(21)

Integrating and combining the solution we find that

$\phi(x)=\frac{\phi_{0}}{4\pi}+\alpha_{0}x^{+}+\tilde{\alpha}_{0}x^{-}+\frac{i}{2\sqrt{\pi}}\sum_{m\neq
0}\Big{[}\frac{\alpha_{m}}{m}e^{-imx^{+}}+\frac{\tilde{\alpha}_{m}}{m}e^{-imx^{-}}\Big{]}$
(22)

substituting back the light-cone coordinates, $x^{\pm}=\tau\pm\theta$ we get

$\begin{split}\phi(x)=&\frac{\phi_{0}}{4\pi}+(\alpha_{0}+\tilde{\alpha}_{0})\tau+(\alpha_{0}+\tilde{\alpha}_{0})\theta\\\
&+\frac{i}{m\sqrt{\pi}}\sum_{m\neq
0}\frac{1}{m}e^{-im\tau}\Big{[}\alpha_{m}e^{-im\theta}+\tilde{\alpha}_{m}e^{+im\theta}\big{]}\end{split}$
(23)

The term linear in $\tau$ we label it as a momentum
$p\varpropto(\alpha_{0}-\tilde{\alpha}_{0})$. Since $\phi(x)$ must be single-
valued, we can consider two cases.
1\. The target space of $\phi(x)$ is the real line and if we impose the
periodicity condition of $\theta$, that is
$\phi(\tau,\theta)=\phi(\tau,\theta+2\pi)$ we get
$\alpha_{0}=\tilde{\alpha}_{0}$ and the linear term in $\theta$ in (23)
vanishes.
2\. The second case would be if target space of $\phi(x)$ is a circle $S^{1}$
with radius $R$. Since $\phi(x)$ must be single valued, this requires that
$\phi(\tau,\theta+2\pi)=\phi(\tau,\theta)+2\pi Rw$ where $w$ is the winding
number of the field. From (23) we can see that
$Rw=(\alpha_{0},\tilde{\alpha}_{0})$.
Now, if we combine both these cases, since $\phi(x)$ is periodic, then $p$ is
quantized: $p=k/R$, for $K\in\mathbb{Z}$. We can write our mode expansion (23)
as

$\phi(x)=\frac{\phi_{0}}{4\pi}+2p\tau+Rw\theta+\frac{i}{m\sqrt{\pi}}\sum_{m\neq
0}\frac{1}{m}e^{-im\tau}\Big{[}\alpha_{m}e^{-im\theta}+\tilde{\alpha}_{m}e^{+im\theta}\big{]}$
(24)

We continue the quantization of scalar field using the canonical techniques
where at the end we get the auxilary Hilbet space $\mathcal{H}_{aux}$. In
canonical quantization, $\phi_{0},p,w,\alpha_{m},$ and $\tilde{\alpha}_{m}$
become operators. Imposing the canonical commutation relation
$[\phi(\tau,\theta_{1}),\phi(\tau,\theta_{2})]=i\delta(\theta_{1}-\theta_{2})$
one finds that

$[\phi_{0},p]=i,\quad[\alpha_{m},\alpha_{n}]=[\tilde{\alpha}_{m},\tilde{\alpha}_{n}]=m\delta_{m,-n}$
(25)

In the usual fashion, $\alpha_{m}$ and $\tilde{\alpha}_{m}$ are interpreted as
left- and right- moving operators. For $m<0$ we have creation operators while
for $m>0$ annihilation operators. Following [ref28 in paper] we can write the
Virasoro generators $L_{0},L_{\pm 1}$ as

$L_{m}=\frac{1}{2}\sum_{n=-\infty}^{\infty}:\alpha_{m-n}\alpha_{n}:$ (26)

which obey the algebra

$[L_{\pm 1},L_{0}]=\pm L_{\pm 1},\quad\quad[L_{1},L_{-1}]=2L_{0}$ (27)

the same is for $\tilde{L}_{0},\tilde{L}_{\pm 1}$.
There are two parameter family of vacua distinguished by their eigenvalues of
$\alpha_{0}$ and $\tilde{\alpha}_{0}$ i.e the momentum and winding mode of
each vacuum. This is equivalent of labeling the vacua by their eigenvalues $h$
and $\tilde{h}$ of the Virasoro generators $L_{0}$ and $\tilde{L}_{0}$.

$h=\frac{1}{2}\Big{(}p+\frac{Rw}{2}\Big{)}^{2},\quad\quad\tilde{h}=\frac{1}{2}\Big{(}p-\frac{Rw}{2}\Big{)}^{2},$
(28)

where we denote the vacuum state as $|\ket{0;h,\tilde{h}}$. We will show that
the only de Sitter invariant vacuum is the $p=w=0$ vacuum i,e $|\ket{0;0,0}$.
Excited states are created by acting on the vacuum with creation operators
$\alpha_{m}$ and $\tilde{\alpha}_{m}$ for $m<0$, where a general state will be
labeled as $|\ket{n,\tilde{n};h,\tilde{h}}$ where $n$ and $\tilde{n}$ are
eigenvalues of $L_{0}-h$ and $\tilde{L}_{0}-\tilde{h}$, respectively.
Introducing the operator

$H=L_{0}+\tilde{L}_{0}$ (29)

which generates translation in $\tau$. Even that H is not thought as de Sitter
Hamiltonian, it agrees with the flux of de Sitter stress-energy through the
sphere at $\tau=0$. The action of $H$ on a general state
$|\ket{n,\tilde{n};h,\tilde{h}}$ is

$\begin{split}H|\ket{n,\tilde{n};h,\tilde{h}}=&\bigg{(}h\tilde{h}+n+\tilde{n}\bigg{)}|\ket{n,\tilde{n};h,\tilde{h}}\\\
&=\bigg{(}p+\frac{R^{2}w^{2}}{4}+n+\tilde{n}\bigg{)}|\ket{n,\tilde{n};h,\tilde{h}}\end{split}$
(30)

where the energy of a such a state is $E=n+\tilde{n}+h+\tilde{h}$.
The $1+1$ de Sitter space-time has three independent killing vector fields.
The Killing fields act on $\mathcal{H}_{aux}$ via the operators $J,B_{1}$ and
$B_{2}$ which satisfy. the $SO(2,1)$ algebra

$[B_{1},B_{2}]=iJ,\quad[B_{1},J]=iB_{2},\quad[B_{2},J]=-iB_{1}$ (31)

One can express the $SO(2,1)$ generators in terms of Virasoro generators via

$\begin{split}J&=L_{0}-\tilde{L}_{0}\\\
B_{1}&=\frac{1}{2}\Big{(}L_{1}+L_{-1}+\tilde{L}_{1}+\tilde{L}_{-1}\Big{)}\\\
B_{2}&=-\frac{i}{2}\Big{(}L_{1}+L_{-1}-\tilde{L}_{1}+\tilde{L}_{-1}\Big{)}\end{split}$
(32)

Because boost generators $B_{1}$ and $B_{2}$ contain both raising and lowering
Virasoro generators it is hard o construct a state that is boost invariant.
What can be checked is that the only de Sitter invariant state is $p=w=0$
vacuum $|\ket{0;0,0}$ where $|\ket{0;0,0}\in\mathcal{H}_{aux}$.

##  4 Group averaging for SO(2,1)

We use group averaging over de Sitter group SO(2,1) to construct physical
states that satisfy $M_{AB}\ket{\psi}=0$ where $M_{AB}$ are generators of the
group. For $SO(2,1)$ the condition $M_{AB}\ket{\psi}=0$ reads (34). These
physical states live in the physical Hilbert space $\mathcal{H}_{phys}$ but
first we define the space $\mathcal{H}_{bas}=\\{|\ket{\psi}_{phys}\\}$ such
that $|\ket{\psi}_{phys}$:

$\begin{split}&J|\ket{\psi}_{bas}\\\
&L_{1}|\ket{\psi}_{bas}=\tilde{L}_{1}|\ket{\psi}_{bas}=0\end{split}$ (33)

and which are the states in the subspace corresponding to eigenvalues
$E=n+\tilde{n}+h+\tilde{h}>1$

$\begin{split}&J|\ket{\psi}_{bas}=0w\\\
&B_{1}|\ket{\psi}_{bas}=(L_{1}+\tilde{L}_{1})|\ket{\psi}_{bas},\quad\quad\bra{\psi}_{bas}|_{phys}B_{1}=\bra{\psi}_{phys}|(L_{1}+\tilde{L}_{1})\end{split}$
(34)

We can decompose the group elements of $SO(2,1)$ as a product of group
elements of two $SO(2)$ rotations and a boost Barut:1986dd .

$U(g)=e^{i\alpha J}e^{i\lambda B_{1}}e^{i\gamma J}$ (35)

where $e^{i\alpha J}$ is the $SO(2)$ rotation through an angle $\alpha$ and
$e^{i\lambda B_{1}}$ is the boost along one of the Killing vector fields.
The Haar measure can be written as

$dg=\frac{1}{4\pi}d\alpha d\beta d\lambda\sinh{\lambda}$ (36)

Then the group averaging inner product of to basic states $\bra{\psi}_{bas}$
is

$\bra{\psi_{1}}\ket{\psi_{2}}=\frac{1}{4\pi}\int d\alpha d\beta
d\lambda\sinh{\lambda}\bra{\psi_{1}}|e^{i\alpha J}e^{i\lambda B_{1}}e^{i\gamma
J}|\ket{\psi_{2}}$ (37)

after some calculations Marolf_2009  the last integral is

$\bra{\psi_{1}}\ket{\psi_{2}}=\delta_{\psi_{1},\psi_{2}}$ (38)

The equation(38) completes the group averaging inner product of two basic
states.

The question that we want to answer in this note is, how to relate this
calculation with BRST quantization?

##  5 The BRST interpretation

The question that we want to answer in this note is, how to relate this
calculation with BRST quantization?
A good part of this section is based on Appendix B of Chandrasekaran:2022cip
. Let $t_{p},p=1,...,dimG_{dS}$ be the linear operators that generate the
action of $G_{dS}$ on $\mathcal{H}_{0}$. They obey the commutation relations

$[t_{p},t_{q}]=f_{pq}^{r}t_{r}$ (39)

where $f_{pq}^{r}$ are the structure constants of $G_{dS}$ and obey the Jacobi
identity.
Next we introduce fermionic operators $c^{r}$ and $b_{s}$, known as ghosts and
anti-ghosts, respectively, with anti-commutation relations

$\begin{split}&\\{c^{r},b_{s}\\}=\delta_{s}^{r}\\\
&\\{c^{r},c^{s}\\}=\\{b_{r},b_{s}\\}=0\end{split}$ (40)

Ghost number is defined so that $c^{r}$ has ghost number 1 and $b_{s}$ has a
ghost number -1. The anti-ghost operators have an irreducible representation
on a finite-dimensional vector space $\mathcal{K}$ that contains a state
$\ket{\downarrow}$ of a minimum ghost number, with $b_{s}\ket{\downarrow}=0$.
Other states in $\mathcal{K}$ are obtained by acting on $\ket{\downarrow}$
with a polynomial in the c’s, while $\mathcal{K}$ contains the state
$\ket{\uparrow}=c^{1}c^{2}...c^{dimG_{dS}}\ket{\downarrow}$ of a maximum ghost
number
The group $G_{dS}$ acts on the combined space
$\mathcal{H}_{0}\otimes\mathcal{K}$ with generators

$T_{r}=t_{r}-\sum_{s,t}f_{rs}^{t}c^{s}b_{t}$ (41)

and the BRST operator is given by

$Q=\sum_{r}c^{r}t_{r}-\frac{1}{2}\sum_{r,s,t}f_{rs}^{t}c^{s}b_{t}$ (42)

The cohomology of Q at ghost number $n$ is defined as the space of states
$\Psi$ of ghost number $n$ that satisfy $Q\Psi=0$ modulo those of the form
$\Psi=Q\chi$. We denote this cohommology group as $H^{n}(Q,\mathcal{H}_{0})$
In the BRST approach to quantization, the space of physical states is defined
via the cohomology of the BRST operator Q at a specific value of the ghost
number. In the example of the de Sitter space with weakly coupled gravity,
there are two important values of the ghost number, namely the minimum and the
maximum possible values. A state in $\mathcal{H}_{0}\otimes\mathcal{K}$ of the
minimum possible ghost number is of the general form
$\hat{\Psi}=\Psi\otimes\ket{\downarrow}$ with $\Psi\in\mathcal{H}_{0}$. The
condition $Q\hat{\Psi}=0$ reduced to $t_{a}\Psi=0$ which means that $\Psi$
must be $G_{dS}$ invariant. The problem here is that, except $\Psi_{dS}$ there
are no $G_{dS}$ invariant states in $\mathcal{H}_{0}$.
On the other hand if you consider states with maximum ghost number, such
states are $\hat{\Psi}=\Psi\otimes\ket{\uparrow}$, then the condition
$Q\hat{\Psi}=0$ is trivial since the ghost number of $Q\hat{\Psi}$ exceeds the
maximum possible value. However, one needs to consider the equivalence
relation $\hat{\Psi}\equiv\Psi+Q\chi$ where
$\chi=\sum_{a}\chi^{a}b_{a}\ket{\uparrow}$ for some state
$\chi^{a}\in\mathcal{H}_{0}$. Then the equivalence relation becomes

$\hat{\Psi}\equiv\Psi\sum_{a}t_{a}\chi^{a}$ (43)

Thus, the conclusion is that for states of maximum ghost number, the
equivalence relation reduced to an equivalence relation on $\mathcal{H}_{0}$,
namely $t_{a}\chi\equiv=0$ for any state $\chi\in\mathcal{H}_{0}$. This is the
same as the equivalence relation $(1-g)\chi\equiv 0$ that you get from group
averaging. The next question is how to construct the inner product in the BRST
language?
There are different ways of quantizing a system, first class of Dirac
method,refined algebraic quantization( group averaging) and BRST-BFV
quantization method. The Dirac method is based on imposing imposing the
constraint conditions on physical states but introducing inner product in this
case could be challenging. Meanwhile in the refined algebraic method instead
of imposing constrains on physical states, one modifies the inner product due
to constrains.
Let us try to build up the inner product between two states in BRST-BFV
quantization method.
Following paper3  and Hwang:1988ak  the BRST operator Q can be decomposed as

$Q=\delta+\delta^{\dagger},\quad\delta^{2}=0,\quad[\delta,\delta^{\dagger}]=0$
(44)

where

$\delta\ket{\psi}=\delta^{\dagger}\ket{\psi}=0$ (45)

. with $\ket{\psi}$ being a physical state. This decomposition is possible
provided that there is a bigrading of the state of space $\Omega$ such that

$F\ket{k,m}=k\ket{k,m}\quad\quad F^{\dagger}=m\ket{k,m}$ (46)

where $F$ satisfies

$\delta=[F,Q]\quad\quad N=F-F^{\dagger}$ (47)

with $N$ being the ghost number operator
$N=\frac{1}{2}(c^{a}P_{a}-c_{a}P^{a})$. The state $\ket{k,m}$ in (46)
represents a general state as a combination of matter states and ghosts. The
operator that makes the grading possible is the ghost number operator which
does the grading of the stace space $\Omega$ into
$\Omega=\sum_{n}\bigoplus\Omega_{n}$, consequently this does the bigrading for
us. In paper1 ; paper2 ; paper3  it was shown that there exists a
$\delta$-operator which satisfies the (44). With the construction of
$\delta$-operator it is possible to solve (45) where you get the solution

$\ket{\psi}=e^{[Q,\xi]}\ket{\phi}$ (48)

where $\xi$ is fermionic gauge fixing operator with ghost number $-1$ and
$\ket{\phi}$ is a BRST invariant state. If $U$ is an unitary operator, then we
can add

$\delta^{\prime}=U\delta U^{\dagger},\quad\quad[Q,U]=0$ (49)

to the conditions . Then for a physical state $\ket{\psi}$ we have

$\ket{\psi^{\prime}}=U\ket{\psi}$ (50)

and BRST invariant states are determined up to a unitary transformation

$\ket{\psi^{\prime}}=e^{[Q,\xi^{\prime}]}\ket{\psi^{\prime}},\quad\psi^{\prime}=U\psi
U^{\dagger},\quad\quad\ket{\phi^{\prime}}=U\ket{\phi}$ (51)

If $U$ is of the form $U=e^{[Q,\xi]}$, then it represents unitary gauge
transformation.
Let $t_{a}$ be the generators of the gauge group which are bosonic and satisfy
the Lie Algebra relation

$[t_{a},t_{b}]=if_{ab}^{c}t_{c}$ (52)

.

and the BRST operator is

$Q=t_{a}c^{a}-\frac{1}{2}if_{bc}^{a}P_{a}c^{b}c^{c}-\frac{1}{2}if_{ab}^{b}c^{a}-\bar{P}_{a}\pi^{a}$
(53)

where $c^{a},b_{a}$ are ghost and anti-ghosts respectively,
$P_{a},\bar{P}^{a}$ are their conjugate momenta, and $\pi_{a}$ are the
conjugate momenta to the Lagrange multipliers $v^{a}$ which satisfy the
algebra

$[c^{a},P_{b}]=[b^{a},\bar{P}_{b}]\delta_{b}^{a},\quad\quad[v^{a},\pi_{b}]=\delta_{b}^{a}$
(54)

A physical state could be written as

$\ket{\psi}=e^{\alpha[\rho,Q]}\ket{\phi}$ (55)

From paper1  it is found that

$\rho=P_{a}v^{a}$ (56)

and the fact that $\ket{\phi}$ satisfies the conditions

$c^{a}\ket{\phi}=b_{a}\ket{\phi}=\pi_{a}\ket{\phi}$ (57)

which means that $\ket{\phi}$ has no ghost and Lagrange multipliers
dependence.
We can write the inner product for solutions which satisfy (55) as

$\braket{\psi}{\psi}=\bra{\phi}e^{2\alpha[\rho,Q]}\ket{\phi}$ (58)

and for the gauge fixing we have

$\ket{\psi}_{\alpha}=U(\beta)\ket{\psi}_{\pm}\quad\quad\ket{\psi}\equiv\ket{\psi}$
(59)

where $\alpha=\pm e^{\beta}$ and $U(\beta)$ is the unitary operator

$U(\beta)=e^{-i\beta[v^{a}b_{a},Q]}$ (60)

In the case of $SL(2,R)$ gauge theory the structure constant is given by
$\epsilon_{ab}^{c}$ and the gauge fixing term is the same as above.
Following the inner product $\bra{\phi}e^{[\rho,Q]}\ket{\phi}$ can be written
as

$_{\pm}\braket{\psi}{\psi}_{\pm}=\bra{\phi}e^{[\rho,Q]}\ket{\phi}=\begin{cases}\bra{\phi}e^{\psi_{a}^{\prime}v^{a}}e^{i(L^{-1})_{b}^{a}(iv)P_{A}\bar{P}^{b}}\ket{\phi}\\\
\bra{\phi}e^{i(L^{\dagger-1})_{b}^{a}(iv)P_{A}\bar{P}^{b}}e^{\psi_{a}^{\prime\prime}v^{a}}\ket{\phi}\end{cases}$
(61)

where $L_{b}^{a}(iv)$ is the left invariant vielbein on group manifold and
$\psi^{\prime}=\psi_{a}-\frac{1}{2}if_{ab}^{c}$ and
$\psi^{\prime\prime}=(\psi^{\prime})^{\dagger}$.
For $\ket{\phi}$ we can write

$\ket{\phi}=\ket{\phi_{1}}\ket{0}_{\pi}\ket{0}_{cb}$ (62)

where $\ket{0}_{\pi}$ is a Lagrange multiplier vacuum and $\ket{0}_{cb}$ is a
ghost vacuum. The ghost vacuum is normalized as paper7

${}_{cb}\bra{0}(iP_{a}\bar{P}^{a}\ket{0}_{cb}=1$ (63)

In the case of $SL(2,R)$ gauge theory

$[\rho,Q]_{+}=\psi_{a}v^{a}+\frac{1}{2}i\epsilon_{bc}^{c}(P_{c}c^{b}-c^{b}P_{c})v^{a}+iP_{a}\bar{P}^{a}$
(64)

Using equation (61) we can write

$\begin{split}&{}_{+}\braket{\psi}{\psi}_{+}=\bra{\phi}e^{[\rho,Q]_{+}}\ket{\phi}=\bra{\phi_{1}}_{\pi}\bra{0}e^{\psi_{a}v^{a}}det(L^{-1})_{b}^{a}(iv)\ket{0}_{\pi}\ket{\phi_{1}}\\\
&{}_{-}\braket{\psi}{\psi}_{-}=\bra{\phi}e^{[\rho,Q]_{+}}\ket{\phi}=\bra{\phi_{1}}_{\pi}\bra{0}e^{-\psi_{a}v^{a}}det(L^{-1})_{b}^{a}(iv)\ket{0}_{\pi}\ket{\phi_{1}}\end{split}$
(65)

The explicit form of $det(L^{-1})^{a}_{b}(iv)$ is given as

$det(L^{-1})^{a}_{b}(iv)=\frac{2(1-\cos v)}{v^{2}}$ (66)

substituting (66) in (65) then we get

$\begin{split}&{}_{+}\braket{\psi}{\psi}_{+}=\int d^{3}u\frac{2(\cosh
u-1)}{u^{2}}\bra{\phi_{1}}e^{i\psi_{a}v^{a}}\ket{\phi}\\\
&{}_{-}\braket{\psi}{\psi}_{-}-=_{+}\braket{\psi}{\psi}_{+}\end{split}$ (67)

Finally we need to factorize the exponential $e^{\psi_{a}v^{a}}$ as

$e^{\psi_{a}v^{a}}=e^{\alpha\psi_{3}}e^{\beta\psi_{2}}e^{\gamma\psi_{3}}=e^{\alpha\psi_{3}}e^{\lambda\psi_{2}}e^{\gamma\psi_{3}}$
(68)

then for the case of $SL(2,R)$ which is isomorphic with $SO(2,1)$ we can write
the decomposition as in (68). Then for $d^{3}u\frac{2(\cosh u-1)}{u^{2}}$ we
can write

$d^{3}u\frac{2(\cosh u-1)}{u^{2}}=id\alpha d\lambda d\gamma\sinh\lambda$ (69)

Substituting (69) in (67) we end up

$_{+}\braket{\psi}{\psi}_{+}=\int d\alpha d\lambda
d\gamma\bra{\phi_{1}}e^{\alpha\psi_{3}}e^{\lambda\psi_{2}}e^{\gamma\psi_{3}}\ket{\phi_{1}}$
(70)

Identifying $\psi_{3}=J$ and $\psi_{2}=B_{1}$ we see that the integral. (70)
is similar to (37).

##  6 Discussion

Finally, I would mention a paper written by Witten Witten:2022xxp  where the
canonical formalism for gravity has been studied and a gauge fixing model has
been constructed in the case of the Hilbert space of quantum gravity for
asymptotically Anti de Sitter space-time. Einstein’s equations are equations
for a metric $h$ on an initial value surface and symmetric tensor field
$K_{ij}$ on that surface. For a general relativity theory with a cosmological
constant $\Lambda$ and no matter fields, equations read

$\begin{split}&P^{j}(\vec{x})=0\\\ &\mathcal{H}(\vec{x})=0\end{split}$ (71)

where the first equation is known as momentum constrain and the second one as
Hamiltonian constrain. Both together they are known as Wheeler-DeWitt
equation.
In the most basic version of the canonical approach of quantum gravity, the
wave function $\Psi(h)$ is a function of the metric of S and the "usual"
(traditional) interpretation of Wheeler-DeWitt equation is that a quantum
state has to be taken from the function $\Psi(h)$ satisfying Wheeler-DeWitt
equation.
As explained in a paper by Witten Witten:2022xxp , one can construct such a
states but there are drawbacks. The idea of constructing a Hilbert space of
quantum states is that one wants to factorize transition amplitudes and sum
over intermediate states but the difficulty is that there is no argument that
such a wave function takes part in the “sum over states” formulas and another
drawback is that the path integral which is supposed to be computed by such a
wave function is not well defined in perturbation theory Witten:2018lgb ;
Avramidi:1997sh ; Anderson:2006lqb .
Recently, in two papers Chakraborty:2023yed ; Chakraborty:2023los  it was
demonstrated that by solving the WdW equation on a late-time slice in the non-
gravitational limit, one can obtain the states and inner product of group
averaging Higuchi:1991tk ; Higuchi:1991tm . As we mentioned above, this is the
"usual" (traditional) interpretation of Wheeler-DeWitt equation, however there
is also a “revised” description which one constructs states that could appear
in the factorization formulas, sometimes known as refined algebraic
quantization (RAQ) or group averaging. In this method one still imposes the
momentum constraint to the wave function $P^{i}\Psi(h)=0$ but the Hamiltonian
constraint $\mathcal{H}\Psi=0$ is replaced by an equivalence relation.

$\Psi(h)=\Psi(h)+\sum\mathcal{H}(\vec{x}_{i})\xi_{i}(h)$ (72)

In this description, any state that satisfies the momentum constraint is
considered physical and the inner product of two such states is given in a
similar form as (12).
The "usual"(traditional) and the "revised" Wheeler-DeWitt theories can be
viewed as special cases of a BRST quantization. In BRST quantization, one
introduces ghosts fields with ghost number 1 which transform as generators of
gauge group, while in the case of gravity ghost fields are anti-commuting
vector fields $c^{\mu}(\vec{x},t)$. In the paper by Witten Witten:2022xxp  the
BRST operator in the case of gravity has been constructed. This operator obeys
the usual BRST operator relations, $Q^{2}=0$ which defines the cohomology of
states $\Psi$ that satisfy $Q\Psi=0$. In the case where we are interested in
the states that are annihilated by $c^{0}$ and not by $c^{i}$ the condition
$Q\Psi=0$ gives the momentum constraint$\mathcal{H}\Psi=0$ and for the
Hamiltonian constraint one should get (72), whereas if one is interested in
the states that are annihilated by all modes of $c^{\mu}$ then for the
Hamiltonian constraint gets $\mathcal{H}\Psi=0$.
As it is explained in the paper Witten:2022xxp  neither of these methods
correspond to the usual BRST quantization method where one introduces ghosts
and anti-ghosts and where those two fields are treated similarly as other
fields.
It would be interesting to further study Witten:2022xxp  and analyse the
gauge-fixing procedure, since it was mentioned that the usual treatment of the
BRST quantization does not correspond to "revised" Wheeler-DeWitt theory;group
averaging, and the task would be obtain (70) from a gauge-fixing constructed
following Witten:2022xxp .

###### Acknowledgements.

I’m grateful to Edward Witten for constructive criticism and comments on the
first draft of the paper. I also would like to thank Zeqë Tolaj for useful
comments and discussions. I would like to thank Atsushi Higuchi for point out
to me the references Moncrief:1978te ; Moncrief:1979bg ; Hajicek:1994px  and
for pointing out a more mathematical treatment known as Riefel induction
Landsman:1993xe  and Joydeep Chakravarty for useful comments on their method
of obtaining group averaged Hilbert space by solving WdW equation.

## References

  * (1) A. Higuchi, Quantum linearization instabilities of de Sitter space-time. 1, Class. Quant. Grav. 8 (1991) 1961–1981.
  * (2) A. Higuchi, Quantum linearization instabilities of de Sitter space-time. 2, Class. Quant. Grav. 8 (1991) 1983–2004.
  * (3) D. Giulini and D. Marolf, A Uniqueness theorem for constraint quantization, Class. Quant. Grav. 16 (1999) 2489–2505, [gr-qc/9902045].
  * (4) D. Giulini and D. Marolf, On the generality of refined algebraic quantization, Class. Quant. Grav. 16 (1999) 2479–2488, [gr-qc/9812024].
  * (5) D. Marolf and I. A. Morrison, Group averaging of massless scalar fields in 1+ 1 de sitter, Classical and Quantum Gravity 26 (2009), no. 3 035001\.
  * (6) E. Witten, A Note On The Canonical Formalism for Gravity, arXiv:2212.08270.
  * (7) C. Becchi, A. Rouet, and R. Stora, Renormalization of the Abelian Higgs-Kibble Model, Commun. Math. Phys. 42 (1975) 127–162.
  * (8) N. Woodhouse, GEOMETRIC QUANTIZATION AND THE BOGOLYUBOV TRANSFORMATION, Proc. Roy. Soc. Lond. A 378 (1981) 119–139.
  * (9) K. V. Kuchar, Covariant Factor Ordering of Gauge Systems, Phys. Rev. D 34 (1986) 3044–3057.
  * (10) C. R. Ordonez and J. M. Pons, Dirac and reduced quantization: A Lagrangian approach and application to coset spaces, J. Math. Phys. 36 (1995) 1146–1165.
  * (11) A. Ashtekar, J. Lewandowski, D. Marolf, J. Mourao, and T. Thiemann, Quantization of diffeomorphism invariant theories of connections with local degrees of freedom, J. Math. Phys. 36 (1995) 6456–6493, [gr-qc/9504018].
  * (12) A. Gomberoff and D. Marolf, On group averaging for SO(n,1), Int. J. Mod. Phys. D 8 (1999) 519–535, [gr-qc/9902069].
  * (13) V. Chandrasekaran, R. Longo, G. Penington, and E. Witten, An Algebra of Observables for de Sitter Space, arXiv:2206.10780.
  * (14) V. Chandrasekaran, G. Penington, and E. Witten, Large N algebras and generalized entropy, arXiv:2209.10454.
  * (15) R. Raczka and A. O. Barut, Theory of group representations and applications.  World Scientific Publishing Company, 1986.
  * (16) P. Hajicek, A. Higuchi, and J. Tolar, Group quantization of parametrized systems. 2. Pasting Hilbert spaces, J. Math. Phys. 36 (1995) 4639–4666, [gr-qc/9412048].
  * (17) R. Marnelius, Proper BRST quantization of relativistic particles, Nucl. Phys. B 418 (1994) 353–378, [hep-th/9309002].
  * (18) S. Hwang and R. Marnelius, Principles of BRST Quantization, Nucl. Phys. B 315 (1989) 638–662.
  * (19) R. Marnelius, Simple BRST quantization of general gauge models, Nucl. Phys. B 395 (1993) 647–660, [hep-th/9212003].
  * (20) I. Batalin and R. Marnelius, Solving general gauge theories on inner product spaces, Nucl. Phys. B 442 (1995) 669–696, [hep-th/9501004].
  * (21) R. Marnelius, Fermionic Quantum Mechanics and Superfields, Int. J. Mod. Phys. A 5 (1990) 329.
  * (22) E. Witten, A note on boundary conditions in Euclidean gravity, Rev. Math. Phys. 33 (2021), no. 10 2140004, [arXiv:1805.11559].
  * (23) I. G. Avramidi and G. Esposito, Lack of strong ellipticity in Euclidean quantum gravity, Class. Quant. Grav. 15 (1998) 1141–1152, [hep-th/9708163].
  * (24) M. T. Anderson, On boundary value problems for Einstein metrics, Geom. Topol. 12 (2008), no. 4 2009–2045, [math/0612647].
  * (25) T. Chakraborty, J. Chakravarty, V. Godet, P. Paul, and S. Raju, The Hilbert space of de Sitter quantum gravity, arXiv:2303.16315.
  * (26) T. Chakraborty, J. Chakravarty, V. Godet, P. Paul, and S. Raju, Holography of information in de Sitter space, arXiv:2303.16316.
  * (27) V. Moncrief, Invariant States and Quantized Gravitational Perturbations, Phys. Rev. D 18 (1978) 983–989.
  * (28) V. Moncrief, QUANTUM LINEARIZATION INSTABILITIES, Gen. Rel. Grav. 10 (1979) 93–97.
  * (29) N. P. Landsman, Rieffel induction as generalized quantum Marsden-Weinstein reduction, hep-th/9305088.
  * (30) E. Witten, Why Does Quantum Field Theory In Curved Spacetime Make Sense? And What Happens To The Algebra of Observables In The Thermodynamic Limit?, arXiv:2112.11614.
  * (31) O. Y. Shvedov, On correspondence of BRST-BFV, Dirac and refined algebraic quantizations of constrained systems, Annals Phys. 302 (2002) 2–21, [hep-th/0111270].
  * (32) I. Y. Park, Holographic quantization of gravity in a black hole background, J. Math. Phys. 57 (2016), no. 2 022305, [arXiv:1508.03874].
  * (33) A. J. Nurmagambetov and I. Y. Park, Quantum-induced trans-Planckian energy near horizon, JHEP 05 (2018) 167, [arXiv:1804.02314].