# A short geometric derivation of the dual Steenrod algebra

Kiran Luecke

###### Abstract

This two-page note gives a non-computational derivation of the dual Steenrod
algebra as the automorphisms of the formal additive group. Instead of relying
on computational tools like spectral sequences and Steenrod operations, the
argument uses a few simple universal properties of certain cohomology
theories.

All algebras are graded and commutative. $C_{2}$ is the cyclic group of order
2.

Preamble: Let $MT$ be the category of pairs $(F,s)$ where $F$ is a
contravariant functor from the homotopy category of finite spectra to the
category of graded abelian groups that takes sums to products and $s$ is a
natural isomorphism from $F$ to $[1]\circ F\circ\Sigma$, where $[1]$ denotes
the shift-of-grading functor. A morphism $(F,s)\to(F^{\prime},s^{\prime})$ is
a natural transformation $F\to F^{\prime}$ that takes $s$ to $s^{\prime}$. Let
$E$ be a homotopy ring spectrum and $E^{*}=\pi_{-*}E$. Consider the “Conner-
Floyd” functor $\text{Alg}_{E^{*}}\rightarrow MT$

$A\mapsto(X\mapsto EA^{*}X:=E^{*}X\otimes_{E^{*}}A).$

Suppose that $E_{*}E$ is flat over $E^{*}$, so that $E(E_{*}E)$ is represented
by $E\wedge E$. Consider the natural transformation

$\eta_{E}:\text{Spec}E_{*}E\rightarrow\text{Hom}_{MT}(E,E-)$
$(E_{*}E\xrightarrow{f}A)\mapsto\eta_{E}(f):=(E^{*}X\xrightarrow{1\wedge\text{id}}(E\wedge
E)^{*}X\simeq E(E_{*}E)^{*}X\xrightarrow{F}EA^{*}X)$

The coproduct on $E_{*}E$ induced by the map $E\wedge
E\xrightarrow{\text{id}\wedge 1\wedge\text{id}}E\wedge E\wedge E$ induces an
“internal” composition of morphisms $E\rightarrow EA$ in the image of
$\eta_{E}$. If $EA$ is a cohomology theory (e.g. if $A$ is flat over $E^{*}$)
then it corresponds to a (homotopy ring) spectrum which is an $E$-module,
harmlessly denoted by $EA$, and there is an inverse to $\eta$ given by sending
a transformation $T:E\rightarrow EA$ to the map on homotopy induced by
$E\wedge E\xrightarrow{\text{id}\wedge T}E\wedge EA\rightarrow EA.$

######  Lemma 0.0.1.

Let $E$ be a real oriented homotopy ring spectrum such that $E_{*}E$ is flat
over $E^{*}$. Write $\mathbb{G}_{E}$ for the formal group with coordinate
$\text{Spf}E^{*}BC_{2}$ and write $\text{Aut}\mathbb{G}_{E}$ for the group-
valued presheaf on $\text{Alg}_{E^{*}}$ sending $R$ to the group of strict
automorphisms of $\mathbb{G}_{H}(R)$. Then there is a morphism
$\text{Spec}(E_{*}E)\xrightarrow{ev_{E}}\text{Aut}\mathbb{G}_{E}$ of monoid-
valued presheaves on $\text{Alg}_{E^{*}}$.

###### Proof.

Let $e$ be the canonical generator of $E^{*}BC_{2}$. Let $R$ be an
$E^{*}$-algebra and let $T$ be an element of $\text{Hom}_{MT}(E,ER)$. The
element $T(e)$ may be identified with a power series $f(e)\in R[[x]]$.
Moreover by multiplicativity of $T$ and naturality applied to the
multiplication map $BC_{2}\times BC_{2}\rightarrow BC_{2}$, the power series
$f(e)$ must be an endomorphism of the formal group law of $\mathbb{G}_{E}$.
The linear coefficient $f_{0}$ is forced to be 1 by considering the pullback
of $e$ along $S^{1}\hookrightarrow BC_{2}$ and invoking stability of $T$.
Hence $f(e)$ defines a strict automorphism of $\mathbb{G}_{E}$. Precomposition
of the assignment $T\mapsto f(e)$ with $\eta_{E}$ defines the desired map
$ev_{E}:\text{Spec}E_{*}E(R)\rightarrow\text{Aut}\mathbb{G}_{E}(R)$ which is
clearly natural in $R$ and commutes with the monoidal structure on both sides
by inspection. ∎

######  Lemma 0.0.2.

Suppose that there is a homotopy commutative ring spectrum $M$ such that

  1. 1.

There is a map $M\rightarrow H$ inducing an isomorphism on $\pi_{0}$.

  2. 2.

$M$ is real oriented with real orientation $e_{M}\in M^{1}BC_{2}$ and formal
group $\mathbb{G}_{M}$ with formal group law $F_{M}$.

  3. 3.

$M_{*}M$ is flat over $M^{*}$, and the map $ev_{M}(R)$ afforded by the
previous lemma is injective when $MR$ is a cohomology theory.

  4. 4.

For an $\mathbb{F}_{2}$-algebra $R$ let $\text{Aut}\mathbb{G}_{M}(R)$ be the
groupoid whose objects are $\mathbb{F}_{2}$-algebra maps
$M^{*}\xrightarrow{f}R$ and whose morphisms from $f$ to $g$ are strict
isomorphisms of formal group laws $\phi$ from $f_{*}F_{M}$ to $g_{*}F_{M}$.
Write $R_{f}$ for the induced $M^{*}$-algebra structure whose underlying ring
is $R$. Note that $MR_{f}$ is canonically real oriented by the class
$e_{MR_{f}}=[e_{M}\otimes 1]\in
MR_{f}^{*}BC_{2}=M^{*}BC_{2}\otimes_{M^{*}}R_{f}$. Then there is a functor

$\gamma:\text{Aut}\mathbb{G}_{M}(R)\rightarrow MT$

which on objects sends $f$ to $MR_{f}$ and on morphisms sends $\phi$ to the
transformation $\gamma(\phi):MR_{f}\rightarrow MR_{g}$ such that
$\gamma(\phi)(e_{MR_{f}})=\phi(e_{MR_{g}})\in MR_{g}^{*}BC_{2}\simeq
R_{g}[[e_{MR_{g}}]]$ as a power series.

Then the evaluation map $ev_{H}$ from the previous lemma is an isomorphism. In
particular if $\mathcal{A}_{2}$ denotes a Hopf algebra corepresenting
$\text{Aut}\mathbb{G}_{H}$ then there is an isomorphism of Hopf algebras
$H_{*}H\simeq\mathcal{A}_{2}.$

###### Proof.

By item 1 $\mathbb{F}_{2}$ is an algebra over $M^{*}$. By item 2 the formal
group law of $M^{*}BC_{2}$ has vanishing 2-series $[2](e_{M})=0$ and so it is
isomorphic to the additive one. Transporting such an isomorphism $\phi$ with
$\gamma$ produces a natural isomorphism

$M^{*}X\simeq
M^{*}X\otimes_{M^{*}}M^{*}\xrightarrow{\gamma(\phi)}M^{*}X\otimes_{M^{*}}\mathbb{F}_{2}\otimes_{\mathbb{F}_{2}}M^{*}=M\mathbb{F}_{2}\otimes_{\mathbb{F}_{2}}M^{*}.$

Thus $M\mathbb{F}_{2}$ is a summand of a cohomology theory and hence a
cohomology theory. The map in item 1 induces a map $M\mathbb{F}_{2}\rightarrow
H$ which by Eilenberg-Steenrod uniqueness must be an isomorphism. Thus,
combining item 3 with the pullback along the surjection $M\rightarrow
M\mathbb{F}_{2}\simeq H$, the map $ev_{H}$ must be injective. So to produce an
inverse it suffices to produce a section. Now since $\mathbb{F}_{2}$ is a
field we have $MR\simeq HR$ for all $\mathbb{F}_{2}$-algebras $R$. Note that
there is an inclusion
$B\text{Aut}\mathbb{G}_{H}\hookrightarrow\text{Aut}\mathbb{F}_{H}$ since
$F_{M}$ is sent to the additive formal group law by the map
$M^{*}\rightarrow\mathbb{F}_{2}$ in item 1. Then the desired section of
$ev_{H}$ is given as follows. Write $\mathbb{F}_{2}\xrightarrow{u}R$ for the
unit map of an $\mathbb{F}_{2}$-algebra $R$. Start with an automorphism of
$\text{Aut}\mathbb{G}_{H}(R)$ and view this as an automorphism of the object
$M^{*}\rightarrow\mathbb{F}_{2}\rightarrow R$ in
$\text{Aut}\mathbb{G}_{M}(R)$. Using $\gamma$ that produces an automorphism of
$MR\simeq HR$, which one then precomposes with the morphism $H\rightarrow HR$
induced by $u$. ∎

######  Lemma 0.0.3.

A cohomology theory $M$ satisfying the conditions of the previous lemma
exists. It is $MO$.

###### Proof.

Let $e_{MO}$ denote the homotopy class of the inclusion
$\mathbb{RP}^{\infty}\hookrightarrow\Sigma MO$. This exhibits $(MO,e_{MO})$ as
the universal real oriented multiplicative cohomology theory. Hence there is a
map $MO\rightarrow H$ sending $e_{MO}$ to $e\in H^{*}BC_{2}$. Thus items 1 and
2 are satisfied. Since $MO$ is real oriented, an easy calculation111The real
orientation $e_{MO}$ implies that all the differentials in the relevant
Atiyah-Hirzebruch sequences are trivial. shows that $MO_{*}MO\simeq
MO_{*}[a_{1},a_{2},...]$ which is free and hence flat over $MO^{*}$. Let $A$
be an $MO^{*}$-algebra and $T:MO\rightarrow MOA$ a multiplicative natural
transformation. Let $\Theta_{n}\in MO^{*}MO(n))$ be the universal Thom class.
By the splitting principle $T(\Theta_{1})$ determines $T(\Theta_{n})$, which
determines all of $T$ by universality. Therefore if $MOA$ is a cohomology
theory then $ev_{MO}(A)$ is the composition of an isomorphism ($\eta_{MO}(A)$)
and an injection ($T\mapsto T(\Theta_{1})$) so item 3 is satisfied. Let $A$ be
an $\mathbb{F}_{2}$-algebra receiving two maps $f,g:MO^{*}\rightarrow A$ and
let $\phi\in A[[x]]$ be an isomorphism from $f_{*}F_{MO}$ to $g_{*}F_{MO}$.
Note that $MOA_{f}$ and $MOA_{g}$ are canonically oriented by $e_{MOA_{f}}$
and $e_{MOA_{g}}$ as defined in item 4. It remains to construct (functorially)
an automorphism $\gamma(\phi):MOA_{f}\rightarrow MOA_{g}$ such that
$T(e_{MOA_{f}})=\phi(e_{MOA_{g}})$. By the calculation $MO_{*}MO\simeq
MO_{*}\otimes_{\mathbb{F}_{2}}\mathbb{F}_{2}[a_{1},a_{2},...]$, the pair
$(g,\phi)$ corresponds222By strictness
$f(e_{MOA_{g}})=e_{MOA_{g}}+f_{1}e_{MOA_{g}}^{2}+...$ and the corresponding
map $\Phi:MO_{*}[a_{1},...]\rightarrow A$ sends $a_{i}$ to $f_{i+1}$. to an
$\mathbb{F}_{2}$-algebra map $\Phi:MO_{*}MO\rightarrow A$ and so using the
natural transformation $\eta_{MO}$ from the preamble one gets multiplicative
transformation $\eta_{MO}(\Phi):MO\rightarrow MOA_{g}$ with the property that
$\eta_{MO}(\Phi)(e_{MO})=f(e_{MOA_{g}})$. Indeed the image of $e_{MO}$ under
the map $MO^{*}BC_{1}\xrightarrow{1\wedge\text{id}}(MO\wedge
MO)^{*}BC_{2}\simeq MO^{*}BC_{2}\otimes_{MO^{*}}MO_{*}MO$ is $[e_{MO}\otimes
1]+[e_{MO}^{2}\otimes a_{1}]+...$ by a simple calculation using the pairing
between homology and cohomology333See e.g. Adams [1] Lemma 6.3 page 60 for the
complex version.. Note that the map
$\eta_{MO}(\Phi)(\text{pt}):MO^{*}\rightarrow A$ is not equal to $g$. Now
$\eta_{MO}(\Phi)$ induces an $A$-linear map $MOA_{f}^{*}X\rightarrow
MOA_{g}^{*}X$ and produces the desired map $\gamma(\phi):MOA_{f}\rightarrow
MOA_{g}$ which is what we are really after. Functoriality444This argument for
functoriality is due to Quillen in [4]. is proved by noting that
$\gamma(\phi)$ is uniquely characterized by the properties of being
$A$-linear, multiplicative, and sending $e_{MOA_{f}}$ to $\phi(e_{MOA_{g}})$.
∎

######  Remark 0.0.4.

There is a similar but slightly messier derivation of the dual Steenrod
algebra at odd primes which uses a mod $p$ analog of $MO$ constructed by Shaun
Bullett [2] using manifolds with singularities. I decided to leave the odd
primes to forthcoming work555This work will also discuss derivations of
algebras of cohomology operations of other spectra as well as a derivation of
the Dyer-Lashof algebra. since the added technical difficulties (which in this
business are usual at odd primes) obscures the simplicity and brevity of the
exposition, which is a cardinal virtue of this note.

Acknowledgements: Thanks to Tim Campion for extensive comments on previous
drafts, and to Robert Burklund for catching a gap in a proof.

##  1 References

[1] Adams, F. Stable homotopy and generalised homology. Chicago Lectures in
Mathematics. The University of Chicago Press, 1995.

[2] Bullett, S. A Z/p Analogue for Unoriented Bordism. University of Warwick
PhD Thesis (1973)

[3] Peterson, E. Formal geometry and bordism operations. Cambridge Studies in
Advanced Mathematics, v17 (2019)

[4] Quillen, D. Elementary Proofs of Rome Results of Cobordism Theory Using
Steenrod Operations. Advances in Mathematics, 7 29-56 (1971)


# On the Effect of Data Dimensionality on Eigenvector Centrality

Gregory J. Clark, Felipe Thomaz, and Andrew Stephen
Saïd Business School
University of Oxford
<EMAIL_ADDRESS>

###### Abstract

Graphs (i.e., networks) have become an integral tool for the representation
and analysis of relational data. Advances in data gathering have lead to
multi-relational data sets which exhibit greater depth and scope. In certain
cases, this data can be modeled using a hypergraph. However, in practice
analysts typically reduce the dimensionality of the data (whether consciously
or otherwise) to accommodate a traditional graph model. In recent years
spectral hypergraph theory has emerged to study the eigenpairs of the
adjacency hypermatrix of a uniform hypergraph. We show how analyzing multi-
relational data, via a hypermatrix associated to the aforementioned
hypergraph, can lead to conclusions different from those when the data is
projected down to its co-occurrence matrix. In particular, we provide an
example of a uniform hypergraph where the most central vertex (à la
eigencentrality) changes depending on the order of the associated matrix. To
the best of our knowledge this is the first known hypergraph to exhibit this
property.

##  1 Introduction

There is a class of problems which seeks to quantify the importance of
vertices (i.e., nodes) in a graph (i.e., network) according to some criterion.
Centrality measures are typically employed in such cases. Examples of such
measures include degree, betweeness, closeness, and eigenvector centrality.
While the aforementioned notions of centrality are related they can vary in
practice. This is particularly troublesome when two centrality measures
identify different vertices as being ‘the most central’. Famously, the
Krakhardt kite is an example of a graph where different vertices have the
greatest degree, betweeness, and closeness centrality [1]. In a similar vein
we construct a hypergraph whose most central vertex (by eigenvector
centrality) changes depending on the order of the associated matrix (see
Figure 2). We explore this phenomenon by examining its underlying spectral
properties.

In recent years, the principal eigenvector of the (normalized) adjacency
hypermatrix of a $k$-uniform hypergraph (see [2, 3, 4]) has received
increasing attention as a way to model multi-relational data which faithfully
analogizes the graph case [5, 6, 7, 8, 9, 10]. Despite these developments, the
term ‘hypergraph’ has been historically employed in various contexts. For
example, in [6] the authors define the adjacency _matrix_ of a hypergraph to
be $A=HWH^{T}-D$ where $H$ is the $|V|\times|E|$ incidence matrix, $W$ is a
square matrix of edge-weights, and $D$ is the diagonal degree matrix. Note
that $A$ is precisely the co-occurrence matrix of $H$ when $W$ is the identity
matrix. This approach of using the co-occurrence matrix, or some variation
thereof, as a stand-in for the adjacency hypermatrix has been the basis for a
longstanding corpus of work. To facilitate the adoption of spectral hypergraph
theory in practice the field needs to overcome this historical momentum. In
particular spectral hypergraph theory needs to establish its computational
feasibility and analytical novelty compared to traditional graph methods.

There have been great strides in the computation of the principal eigenvector
of a hypergraph as a constrained optimization problem [11, 12]. One can also
consider the problem from a algebraic approach via the Lu-Man Method which was
introduced in [13] and further developed in [14, 15]. Herein we consider the
question of novelty. That is, how ‘different’ is the principal eigenvector of
a hypergraph from the graph formed from its co-occurrence matrix? We take a
practical approach by addressing the following questions. To what extent can
the spectral ranking of a hypergraph and its co-occurrence matrix differ?
Moreover, how much can these vectors vary coordinate-wise?

We begin by presenting the necessary background for our discussion in the
following section. In Section 3 we describe a property of the principal
eigenvector of a $k$-partite $k$-uniform hypergraph. We leverage this property
to construct a hypergraph whose most central vertex depends on the order of
the accompanying hypermatrix in Section 4. In Section 5 we pivot to a
structural approach and show how the loss of information incurred from
depreciating data can lead to variations in the spectral ranking. Finally, in
Section 6 we answer the second question by providing an upper bound on the
Chebyshev distance between the aforementioned vectors. We further provide a
family of hypergraphs which achieves this bound in the limit.

##  2 Preliminaries

A _$k$ -uniform hypergraph_, abbreviated _$k$ -graph_, is an ordered pair
$H=([n],E)$ where $E\subseteq\binom{[n]}{k}$. Throughout we will assume that
all hypergraphs are uniform and we reserve the language of “hypergraph”
specifically for $k$-graphs where $k>2$. We maintain the notation of [4]. The
_(normalized) adjacency hypermatrix_ of a $k$-graph $H$ is an _order $k$ and
dimension $n$ hypermatrix_, denoted ${\cal A}(H)$, which is a collection of
$n^{k}$ elements where,

$a_{i_{1},i_{2},\dots,i_{k}}=\frac{1}{(k-1)!}\left\\{\begin{array}[]{ll}1&:\\{i_{1},i_{2},\dots,i_{k}\\}\in
E(H)\\\ 0&:\text{otherwise}.\end{array}\right.$

Let $H$ be a simple $k$-uniform hypergraph and $x\in\mathbb{C}^{|V|}$. For
$e\in E$ we denote $x^{e}=\prod_{v\in e}x_{v}$. The hypergraph $H$ defines a
polynomial form,

$F_{{\cal{A}}(H)}(x)=k\cdot\sum_{e\in H}x^{e}.$ (1)

###### Lemma 1

([4]) In the case when $H$ is connected there is a unique strictly positive
eigenpair $(\lambda,x)$ where $||x||_{k}=1$ and

$\lambda=\max_{y:||y||_{k}^{k}=1}F_{{\cal A}(H)}(y).$

Moreover $x$ is the only strictly positive eigenvector which satisfies
Equation 1.

We refer to the eigenpair in Lemma 1 as the principal eigenpair of $H$. More
generally we have that $(\lambda,x)$ is an _eigenpair_ of $H$ if it satisfies
the _eigenequations_

$\lambda x_{i}^{k-1}=\sum_{\begin{subarray}{c}e\in E\\\ i\in
e\end{subarray}}x^{e\setminus i}\text{ for }i\in[n].$

The enterprise of this paper is to motivate the use of $k$-order hypergraphs
to model $k$-relational data. We do so by comparing the principal eigenvector
of the normalized adjacency hypermatrix of $H$ with its co-occurrence matrix.

###### Definition 1

For a hypergraph $H=([n],E)$, we define the _clique-shadow_ of $H$ as the
multigraph

$\partial^{*}H=([n],\\{uv:uv\in e\in E(H)\\})$

where $\mu(uv)=|\\{e\in E(H):u,v\in e\\}|$ is the number of edges in $H$
containing $u$ and $v$.

An example of a $3$-graph and its clique-shadow is given in Figure 1. The term
‘clique-expansion’ or ‘$2$-shadow’ is sometimes used for Definition 1. The
nomenclature of ‘clique-shadow’ was chosen instead to synthesize the language.
We also note that the shadow of a hypergraph, denoted $\partial H$, replaces
each $k$-edge of a hypergraph with all possible $(k-1)$-subedges. To avoid
confusion we adopt the notation of $\partial^{*}$.

###### Remark 1

The adjacency matrix of $\partial^{*}(H)$ is the co-occurrence matrix of $H$.
Note that the co-occurrence matrix of $H$ preserves multiplicity.

Throughout we consider a hypergraph $H$ and its clique-shadow $\partial^{*}H$.
For clarity, we reserve $(\rho,y)$ and $(\lambda,x)$ for the principal
eigenpair of a hypergraph and a graph, respectively.

We adopt the language of spectral ranking as in [16] so that ‘the most central
vertices by eigenvector centrality’ have spectral rank 1. We say that a
hypergraph is _opaque_ if its spectral ranking differs from that of its
clique-shadow. We further define the umbral index of a hypergraph
$\mathfrak{u}(H)$ to be the least index for which the spectral ranking of $H$
and $\partial^{*}(H)$ differ. In the case when $H$ is not opaque (i.e., $H$
and $\partial^{*}(H)$ have the same spectral ranking) we write
$\mathfrak{u}(H)=0$.

##  3 Principle Eigenvector of a $k$-partite $k$-graph

The following elegant result, given in [17], provides insight into how
vertices in an independent set ‘compete’ for centrality in a bipartite graph.

###### Theorem 2

([17]) If $S$ is an independent set of a connected graph $G$ and $x$ is the
principal eigenvector of $G$, then

$\sum_{i\in S}x_{i}^{2}\leq\frac{1}{2}.$

Equality happens if and only if $G$ is bipartite having $S$ as one color
class.

We extend Theorem 2 to hypergraphs. A $k$-graph is _$k$ -partite_, or a _$k$
-cylinder_, if its vertices can be partitioned into $k$ sets so that every
edge uses exactly one vertex from each set [4]. Our proof is similar to that
of Theorem 2. We include it as it succinctly highlights the mechanisms
underpinning this phenomenon.

###### Theorem 3

If $S$ is an independent set of a connected $k$-uniform hypergraph $H$ and $y$
is the principal eigenvector of $H$, then

$\sum_{i\in S}y_{i}^{k}\leq\frac{1}{k}.$

Equality occurs if and only if $H$ is a $k$-cylinder having $S$ as one color
class.

###### Proof.

For each $i\in S$ we have

$\rho y_{i}^{k-1}=\sum_{\begin{subarray}{c}e\in E\\\ i\in
e\end{subarray}}y^{e\setminus{i}}.$

Multiplying each equation by $y_{i}$ and summing over $i\in S$ yields

$\rho\sum_{i\in S}y_{i}^{k}=\sum_{i\in S}\sum_{i\in e}y^{e\setminus{i}}.$

Since $S$ is independent and the entries of $y$ are positive we have that

$\sum_{i\in S}\sum_{i\in
e}y^{e\setminus{i}}\leq\frac{F_{H}(y)}{k}=\frac{\rho}{k}.$

The desired inequality follows whence $\rho>0$ .

Moreover, equality occurs if and only if every edge $e$ which does not have a
vertex in $S$ has $y_{e}=0$. Since $y$ is strictly positive this implies that
every edge must have a vertex in $S$. Whence $S$ is an independent set it
follows that each edge of $H$ contains exactly one node from $S$. Thus $S$ is
a color class of $H$. ∎

Theorem 3 shows that vertices in the same color class in a $k$-partite
$k$-graph ‘compete for centrality’ like in a zero-sum game. However, this
relationship breaks down when the number of color classes exceeds the order of
the (hyper)graph. Note that the clique-shadow operation preserves the color
classes of a hypergraph so that vertices in a $k$-partite $k$-graph ‘compete’
in a stricter sense than in the clique-shadow. This observation forms the
basis of our constructions moving forward.

##  4 Generalized Bowtie

We construct a hypergraph which has the property that it and its clique-shadow
identify different vertices as being the most central under eigenvector
centrality. Consider the following _$t$ -pleated bowtie_ $3$-graph,

$B_{t}=\\{[c,\ell_{1},\ell_{2}],[c,r_{1},r_{2}]\\}\cup\left(\bigcup_{i=1}^{t}\\{[c,\ell_{1},\ell_{i+1}],[r_{1},r_{2},r_{i+2}]\\}\right).$

A drawing of $B_{1}$ and $\partial^{*}B_{1}$ is given in Figure 1.

We establish a spectral characterization for the spectral rank 1 vertices of
$B_{t}$ and $\partial^{*}B_{t}$, respectively. In particular we show that
$r_{1}$ and $r_{2}$ are the most central vertices in $B_{t}$ precisely when
$\rho$ is large (compared to $t$). We further show that vertex $c$ is the most
central in $\partial^{*}B_{t}$ precisely when $\lambda$ is big (compared to
$t$). We conclude by showing that both $\rho$ and $\lambda$ are sufficiently
large when $t=8$. A drawing of $B_{8}$ is given in Figure 2.

Figure 1: The one-pleated bowtie, $B_{1}$ where edges are drawn as triangular
faces (left), and its clique-shadow (right).

###### Lemma 4

Fix $t$ and let $(\rho,y)$ be the principal eigenvector of $B_{t}$. Then the
spectral rank 1 vertices of $B_{t}$ are $\\{r_{1},r_{2}\\}$ if and only if
$t<\rho\sqrt{\rho-1}-1$.

###### Proof.

For simplicity we write

$\alpha=y(c),\beta=y(r_{1})=y(r_{2}),\gamma=y(r_{i})\text{ for
}i>2,\delta=y(\ell_{1})\text{ and }\varepsilon=y(\ell_{j})\text{ for }j>1.$

As such, the eigenequations of $B_{t}$ are

$\left\\{\begin{array}[]{ll}\rho\alpha^{2}&=\beta^{2}+(t+1)\delta\varepsilon\\\
\rho\beta^{2}&=\alpha\beta+t\beta\gamma\\\ \rho\gamma^{2}&=\beta^{2}\\\
\rho\delta^{2}&=(t+1)\alpha\varepsilon\\\
\rho\varepsilon^{2}&=\alpha\delta\end{array}\right.$

We show that $\beta>\alpha>\gamma,\delta,\varepsilon$ if and only if
$t<\rho\sqrt{\rho-1}$. From the last two eigenequations we have

$\frac{\rho\delta^{2}}{(t+1)\varepsilon}=\alpha=\frac{\rho\varepsilon^{2}}{\delta}.$

It follows that $\delta^{3}=(t+1)\varepsilon^{3}$. We further have

$\displaystyle\rho\alpha^{2}$
$\displaystyle=\beta^{2}+(t+1)\delta\varepsilon=\beta^{2}+(t+1)^{4/3}\varepsilon^{2}$
$\displaystyle=\beta^{2}+(t+1)^{4/3}\left(\frac{\alpha^{2}(t+1)^{2/3}}{\rho^{2}}\right)=\beta^{2}+\frac{\alpha^{2}(t+1)^{2}}{\rho^{2}}.$

Thus

$\left(\frac{\alpha}{\beta}\right)^{2}=\frac{\rho^{2}}{\rho^{3}-(t+1)^{2}}.$

Hence $\beta>\alpha$ if and only if $t<\rho\sqrt{\rho-1}-1$.

The difference of first and third eigenequation yield $\alpha>\gamma$ . We now
show $\alpha>\delta$. Rearranging the fourth eigenequation yields

$\varepsilon=\frac{\rho\delta^{2}}{(t+1)\alpha}.$

Substitution into fifth eigenequation yields

$\left(\frac{\alpha}{\delta}\right)^{3}=\frac{\rho^{3}}{(t+1)^{2}}.$

Indeed, $\alpha>\delta$ if and only if $\rho^{3}>(t+1)^{2}$. This inequality
is satisfied when $\rho\sqrt{\rho-1}-1>t$. Finally we take the ratio of fourth
eigenequation multiplied by $\delta$ and the fifth eigenequation multiplied by
$\varepsilon$ to conclude

$\left(\frac{\delta}{\varepsilon}\right)^{3}=t+1$

so that $\delta/\varepsilon>\sqrt[3]{t+1}$ implying that $\delta>\varepsilon$.
It follows that $\alpha>\varepsilon$ concluding the proof. ∎

We now establish a similar characterization for $\partial^{*}B_{t}$.

###### Lemma 5

Fix $t$ and let $(\lambda,x)$ be the principal eigenvector of
$\partial^{*}B_{t}$. We have that the only vertex of spectral rank 1 is $c$ if
and only if $t<(2\lambda-\lambda^{2})/(\lambda+1)$ or equivalently

$\lambda>\frac{t+2+\sqrt{t^{2}+12t+4}}{2}.$

###### Proof.

For simplicity, we write

$a=x(c),b=x(r_{1})=x(r_{2}),c=x(r_{i})\text{ for }i>2,d=x(\ell_{1}),\text{ and
}e=x(\ell_{j})\text{ for }j>1.$

As such, the eigenequations of $\partial^{*}B_{t}$ are

$\left\\{\begin{array}[]{ll}\lambda a&=2b+(t+1)(d+e)\\\ \lambda
b&=a+(t+1)b+tc\\\ \lambda c&=2b\\\ \lambda d&=(t+1)(a+e)\\\ \lambda
e&=a+d\end{array}\right.$

We prove our claim by showing that $a>b,c,d,e$ when $\lambda$ is sufficiently
large.

Substituting the third eigenequation into the second yields

$\lambda b=a+(t+1)b+tc=a+(t+1)b+t(2b/\lambda)$

so that

$\frac{a}{b}=\frac{\lambda^{2}-\lambda(t+1)-2t}{\lambda}.$

Indeed $a>b$ if and only if $t<(\lambda^{2}-2\lambda)/(\lambda+2)$ or
equivalently

$\lambda>\frac{t+2+\sqrt{t^{2}+12t+4}}{2}.$

Taking the difference between the first and third eigenequations yields

$\lambda(a-c)=(t+1)(d+e).$

Whence $\lambda,t,d,e>0$ we have that $a>c$.

Now consider the difference of the first and fourth eigenequations,

$\lambda(a-d)=2b+(t+1)(d-a).$

Suppose to the contrary that $a\leq d$. Then $\lambda(a-d)\leq 0$. Moreover,
we have that $2b+(t+1)(d-a)>0$ since $b,t>0$ and $d-a\geq 0$. This implies
that $0<0$ which is a contradiction. It must be the case that $a>d$.

We conclude by showing $d>e$. Substituting the fifth eigenequation into the
fourth yields

$\lambda d=(t+1)(\lambda e-d+e)$

so that

$d=e\left(\frac{(t+1)(\lambda+1)}{\lambda-(t+1)}\right).$

Since

$(t+1)(\lambda+1)>\lambda-(t+1)$

we have that $d>e$ as desired. ∎

Figure 2: The 8-pleated bowtie, $B_{8}$.

We now prove our main result.

###### Theorem 6

$\mathfrak{u}(B_{8})=1$. That is, the spectral rank 1 vertices of $B_{8}$ and
its clique-shadow $\partial^{*}B_{8}$ are distinct.

###### Proof.

We adhere to the notation of Lemmas 4 and 5. From Theorem 3 we have that
$0<\alpha,\beta<(1/3)^{1/3}$ and

$\displaystyle 1/3$ $\displaystyle=\alpha^{3}+t\gamma^{3}$ $\displaystyle 1/3$
$\displaystyle=\beta^{3}+(t+1)\varepsilon^{3}$ $\displaystyle 1/3$
$\displaystyle=\beta^{3}+\delta^{3}.$

It follows that

$\displaystyle\gamma$
$\displaystyle=\left(\frac{1/3-\alpha^{3}}{t}\right)^{1/3}$
$\displaystyle\delta$ $\displaystyle=(1/3-\beta^{3})^{1/3}$
$\displaystyle\varepsilon$
$\displaystyle=\left(\frac{1/3-\beta^{3}}{t+1}\right)^{1/3}.$

Appealing to Equation 1 we find that the polynomial form $F_{B_{t}}$ is a
function only of $t,\alpha,$ and $\beta$. Consider $y^{\prime}$ where
$\alpha=\beta=(1/3)^{1/3}-1/8$. We have then that

$\rho\geq F_{B_{8}}(y^{\prime})\geq 4.68949$

so that $\rho\sqrt{\rho-1}-1>8.007>t$.

Further we find that the minimal polynomial of $\lambda$ is

$m_{\lambda}(x)=x^{5}-9\,x^{4}-98\,x^{3}+592\,x^{2}+2448\,x+2048$

so that $\lambda>11.097$ and thus

$\lambda>\frac{t+\sqrt{t^{2}+12t+4}}{2}\approx 10.403.$

The conclusion follows immediately from Lemmas 4 and 5. ∎

###### Conjecture 1

We have $\mathfrak{u}(B_{t})=1$ for $t\geq 8$.

##  5 Modified Octahedron

Consider the modified octahedron given in Figure 3. Let $O_{R}$ denote the
3-graph formed by taking the red faces of the octahedron and the green edge.
To be precise,

$E(O_{R})=\\{[t,p,q],[t,r,s],[b,q,r],[b,p,s],[u,p,q]\\}.$

Similarly define $O_{B}$ to be the 3-graph formed from the blue faces of the
octahedron and the green edge,

$E(O_{B})=\\{[t,p,r],[t,p,s],[b,p,q],[b,r,s],[u,p,q]\\}.$

An approximation of the principal eigenvectors of
$O_{R},O_{B},\partial^{*}O_{R}$, and $\partial^{*}O_{B}$ is given in Table 1
and the corresponding spectral rankings are given in Table 2.

###### Definition 2

We say that two hypergraphs $H_{1}$ and $H_{2}$ are co-umbral mates if
$H_{1}\neq H_{2}$ but $\partial^{*}(H_{1})=\partial^{*}(H_{2})$.

Co-umbral mates demonstrate the loss of information incurred by using the co-
occurrence matrix of a hypergraph instead of its adjacency hypermatrix.
Observe that $O_{R}$ and $O_{B}$ are co-umbral mates as $O_{R}\neq O_{B}$ and
$\partial^{*}O_{R}=\partial^{*}O_{B}$. Moreover, $t$ are $b$ are identically
situated in the clique-shadow while occupying distinct positions in $O_{R}$
(and $O_{B}$). We thus expect the spectral ranking of the red/blue modified
octahedron and its clique-shadow to differ.

(a) A Modified Octahedron

(b) $O_{R}$

(c) $O_{B}$

Figure 3: A modified octahedron, $O_{R}$, and $B_{R}$, respectively.

###### Theorem 7

$O_{R}$ and $O_{B}$ are opaque.

###### Proof.

Consider $O_{R}$. Let $(\rho,y)$ and $(\lambda,x)$ be the principal
eigenvector of $O_{R}$ and $\partial^{*}(O_{R})$, respectively. We remark that
$x_{t}=x_{b}$ by symmetry of $\partial^{*}(O_{R})$. It remains to be shown
that $y_{t}\neq y_{b}$. We will abuse notation and write $v$ for $y_{v}$, the
value of the principal eigenvector of the vertex $v$. By symmetry of $O_{R}$
we have $p=q$ and $r=s$.

First suppose to the contrary that $q=r$. Taking the difference of their
eigenequations yields

$\rho q^{2}-\rho r^{2}=(rb+tq+uq)-(tr+qb)$

so that $0=uq$. It follows that $u=0$ or $q=0$. This cannot be the case as the
principal eigenvector is non-negative. Indeed $r\neq q$.

Now consider the difference of the eigenequations of $t$ and $b$,

$\rho t^{2}-\rho b^{2}=rs+pq-(rq+ps)=r^{2}+q^{2}-2rq=(r-q)^{2}.$

Since $r\neq q$ we have that $(r-q)^{2}>0$ which implies that $t>b$.

∎

Table 1: An approximation of the principal eigenvector of $O_{R},O_{B},\partial^{*}O_{R}$ and $\partial^{*}O_{B}$. Approximations were computed via Sage [18]. Vertex | $y(O_{R})$ | $y(O_{B})$ | $x(\partial^{*}(O_{R}))=x(\partial^{*}(O_{B}))$
---|---|---|---
$p$ | 0.5938 | 0.5938 | 0.4871
$q$ | 0.5938 | 0.5938 | 0.4871
$t$ | 0.5159 | 0.5121 | 0.3579
$b$ | 0.5121 | 0.5159 | 0.3579
$r$ | 0.4986 | 0.4986 | 0.3348
$s$ | 0.4986 | 0.4986 | 0.3348
$u$ | 0.3951 | 0.3951 | 0.2121
Table 2: The spectral ranking of $O_{R},O_{B},\partial^{*}O_{R}$ and $\partial^{*}O_{B}$. Rank | $O_{R}$ | $O_{B}$ | $\partial^{*}(O_{R})=\partial^{*}(O_{R})$
---|---|---|---
1 | $p,q$ | $p,q$ | $p,q$
2 | $t$ | $b$ | $t,b$
3 | $b$ | $t$ | $r,s$
4 | $r,s$ | $r,s$ | $u$
5 | $u$ | $u$ | $\emptyset$

##  6 Hyperstars and Windmills

Consider now the $k$-order star graph ${\cal{S}}(\eta,k)$ which consists of
$\eta$ $k$-edges all sharing a common vertex. That is,

$E({\cal S}(\eta,k))=\\{[1,(i-1)(k-1)+2,\dots,(i-1)(k-1)+k]:1\leq
i\leq\eta\\}.$

The clique-shadow of a $k$-star is a windmill graph (aka fan or friendship
graph). In [19], the author determined the spectrum and network properties of
windmill graphs. Adhering to their notation, the windmill graph $W(\eta,k)$
consists of $\eta$ copies of the complete graph $K_{k}$ joined at a single
vertex. We provide a drawing of ${\cal{S}}(3,3)$ and $W(3,2)$ in Figure 4.
With this notation we have $\partial^{*}({\cal S}(\eta,k))=W(\eta,k-1)$.

Figure 4: ${\cal{S}}(3,3)$ and its shadow, $W(3,2)$, respectively.

###### Theorem 8

Let $y$ and $x$ be the principal eigenvectors of $H$ and $\partial^{*}(H)$,
respectively. Consider $\hat{y}:=(y_{v}^{k})_{v\in V}$. Then the Chebyshev
distance between

$D(\hat{y},\hat{x})=\max_{v}|y_{v}^{k}-x_{v}^{2}|\leq 1/2.$

Moreover, for

$\Delta_{k}:=\max_{H\in{{\cal H}(k)}}D(\hat{y},\hat{x}),$

where the maximum is taken over all connected $k$-graphs, we have

$\lim_{k\to\infty}\Delta_{k}=1/2.$

###### Proof.

From Theorem 3 we have that $D(\hat{y},\hat{x})\leq 1/2$. Let $(\lambda,x)$ be
the principal eigenpair of $W(\eta,k)$. From [19] we have

$\lambda=\frac{k-1}{2}+\sqrt{\left(\frac{k-1}{2}\right)^{2}+\eta k}$

where $\lambda x_{1}=1-x_{1}$ and $x_{i}=(1-x_{1})/(\eta k)$ for $i>1$.
Solving for $x_{1}$ and normalizing such that $||x||_{2}=1$ yields

$x_{1}=\frac{2}{\zeta\sqrt{\frac{\left(\frac{2}{\zeta}-1\right)^{2}}{k\eta}+\frac{4}{\zeta^{2}}}}\text{
for }\zeta=k+\sqrt{(k-1)^{2}+4k\eta}+1.$

For fixed $k$, $\lim_{\eta\to\infty}\hat{x}_{1}(\eta)=1/2$. Now consider
${\cal S}(n,k)$ which is a $k$-cylinder where vertex-$1$ forms a color class.
Appealing to Theorem 3 we have that $\hat{y}_{1}=1/k$. We have shown

$\Delta_{k}\geq\lim_{\eta\to\infty}|\hat{y}_{1}({\cal
S}(\eta,k))-\hat{x}_{1}(W(\eta,k-1)|=1/2-1/k.$

Indeed $\lim_{k}\Delta_{k}=1/2$ as desired. ∎

###### Conjecture 2

$\Delta_{k}=1/2+o(1)$ for all $k\geq 3$.

## References

  * [1] David Krackhardt and Robert N Stern.  Informal networks and organizational crises: An experimental simulation.  Social psychology quarterly, pages 123–140, 1988.
  * [2] Liqun Qi.  Eigenvalues of a real supersymmetric tensor.  J. Symbolic Comput., 40(6):1302–1324, 2005.
  * [3] L. H. Lim.  Singular values and eigenvalues of tensors: a variational approach.  Pro- ceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 1:129–132, May 2005\.
  * [4] Joshua Cooper and Aaron Dutle.  Spectra of uniform hypergraphs.  Linear Algebra Appl., 436(9):3268–3292, 2012.
  * [5] Shenglong Hu and Ke Ye.  Multiplicities of tensor eigenvalues.  Commun. Math. Sci., 14(4):1049–1071, 2016.
  * [6] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf.  Learning with hypergraphs: Clustering, classification, and embedding.  Advances in neural information processing systems, 19:1601–1608, 2006.
  * [7] Yannan Chen, Liqun Qi, and Xiaoyan Zhang.  The fiedler vector of a laplacian tensor for hypergraph partitioning.  SIAM Journal on Scientific Computing, 39(6):A2508–A2537, 2017.
  * [8] Hong-Hai Li and Bojan Mohar.  On the first and second eigenvalue of finite and infinite uniform hypergraphs.  Proceedings of the American Mathematical Society, 147(3):933–946, 2019.
  * [9] Y.-Z. Fan, T. Huang, Y.-H. Bao, C.-L. Zhuan-Sun, and Y.-P. Li.  The spectral symmetry of weakly irreducible nonnegative tensors and connected hypergraphs.  ArXiv e-prints, April 2017.
  * [10] Gregory J. Clark and Joshua N. Cooper.  A harary-sachs theorem for hypergraphs.  Journal of Combinatorial Theory, Series B, 149:1–15, 2021.
  * [11] Jingya Chang, Weiyang Ding, Liqun Qi, and Hong Yan.  Computing the p-spectral radii of uniform hypergraphs with applications.  Journal of Scientific Computing, 75(1):1–25, 4 2018.
  * [12] Liqun Qi and Ziyan Luo.  Tensor analysis: spectral theory and special tensors, volume 151\.  Siam, 2017.
  * [13] Linyuan Lu and Shoudong Man.  Connected hypergraphs with small spectral radius.  Linear Algebra Appl., 509:206–227, 2016.
  * [14] Shuliang Bai and Linyuan Lu.  A bound on the spectral radius of hypergraphs with $e$ edges.  Linear Algebra Appl., 549:203–218, 2018.
  * [15] Wei Zhang, Liying Kang, Erfang Shan, and Yanqin Bai.  The spectra of uniform hypertrees.  Linear Algebra Appl., 533:84–94, 2017.
  * [16] Sebastiano Vigna.  Spectral ranking.  Network Science, 4(4):433–445, 2016.
  * [17] Sebastian Cioabă.  A necessary and sufficient eigenvector condition for a connected graph to be bipartite.  The Electronic Journal of Linear Algebra, 20:351–353, 2010.
  * [18] The Sage-Combinat community.  Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2008.  http://sagemath.org.
  * [19] Ernesto Estrada.  When local and global clustering of networks diverge.  Linear Algebra and its Applications, 488:249–263, 2016.


11institutetext:  Continental AG, Regensburg, Germany
11email<EMAIL_ADDRESS>22institutetext:
Cognitive Systems, University of Bamberg, Bamberg, Germany

#  Verification of Size Invariance in DNN Activations using Concept
Embeddings††thanks:  The research leading to these results was partly funded
by the German Federal Ministry for Economic Affairs and Energy within the
project “KI-Absicherung”.

Gesina Schwalbe 1122 0000-0003-2690-2478

###### Abstract

The benefits of deep neural networks (DNNs) have become of interest for safety
critical applications like medical ones or automated driving. Here, however,
quantitative insights into the DNN inner representations are mandatory [10].
One approach to this is _concept analysis_ , which aims to establish a mapping
between the internal representation of a DNN and intuitive semantic concepts.
Such can be sub-objects like human body parts that are valuable for validation
of pedestrian detection. To our knowledge, concept analysis has not yet been
applied to large object detectors, specifically not for sub-parts. Therefore,
this work first suggests a substantially improved version of the Net2Vec
approach [5] for post-hoc segmentation of sub-objects. Its practical
applicability is then demonstrated on a new concept dataset by two exemplary
assessments of three standard networks, including the larger Mask R-CNN model
[9]: (1) the consistency of body part similarity, and (2) the invariance of
internal representations of body parts with respect to the size in pixels of
the depicted person. The findings show that the representation of body parts
is mostly size invariant, which may suggest an early intelligent fusion of
information in different size categories.

###### Keywords:

Concept embedding analysis MS COCO Explainable AI.

##  1 Introduction

The high performance and flexibility of deep neural networks (DNNs) makes them
interesting for many complex computer vision applications. This includes
ethically involved or safety critical fields where silent biases can become a
matter of unfairness, or even life-threatening decisions. Hence, responsible
artificial intelligence is required, allowing for thorough assessments of
trained DNNs [1]. For example in the area of automated driving, quantitative
insights into the inner representation of trained DNNs are mandatory [10].

One step towards this direction is the research area of _concept (embedding)
analysis_ [5, 11], that started with the work in [2] in 2017. Supervised
concept analysis aims to answer the question how (well) information on a
visual semantic concept is embedded in the intermediate output of one layer of
a trained DNN. A concept can be, e.g., a texture, material, scene, object, or
object part [2], and should be given as samples with binary annotations. The
question is answered by training a simple model to predict the concept from
the layer output, with simplicity ensuring interpretability [2, 11]. Once
these _concept models_ are obtained, several means for verification open up:
The embedding quality can be measured as the prediction quality of the concept
model; if a similarity measure for concept models is available, semantic
relations between concepts can be validated (e.g. legs are similar to arms)
[5]; and lastly, if the information embedding can be represented as a vector
in the latent space, one can use sensitivity analysis to investigate
dependencies of outputs on certain concepts [11]. The vector can be the normal
vector of a linear model, or the center of a cluster, and is called the
embedding of the concept [5].

While concept analysis opens up a wide variety of verification options,
existing methods suffer from some limitations. For one, the methods are either
restricted to image-level concepts, or, like Net2Vec [5], report poor results
for part objects. But part objects, such as human body parts, are substantial
to verify logical plausibility of pedestrian detectors needed for automated
driving. This brings up the second issue: To our knowledge, existing proposals
have not been evaluated on large networks like standard object detectors.
Concretely, we uncovered some severe performance limitations of Net2Vec that
impede application to state-of-the-art sized DNNs or larger concept datasets
than the original Broden dataset proposed in [2].

In order to overcome the practical issues, this paper suggests some
substantial improvements to the Net2Vec method, demonstrated on a new large MS
COCO [15] based concept dataset for human body parts. The applicability of
concept analysis for simple verification is demonstrated by exemplary
assessment of three networks with different sizes, tasks, and training data
(AlexNet, VGG16, and Mask R-CNN [9]). Concretely, the semantic similarity of
different concepts is validated, and it is checked whether the internal
representation of the networks is biased towards one size category (i.e.
distance to the camera). Interestingly, our findings suggest that
convolutional DNNs are not biased towards one size. Instead, from early layers
onwards, they use an efficient common representation for instances of the same
part object but different sizes. The main contributions of this paper are:

  * •

A Net2Vec-based concept analysis approach that can deal with large models and
large concept datasets is presented and demonstrated. It is found to
considerably surpass the state-of-the-art for object part concepts.

  * •

The first evaluation of size invariance of the internal representations of
convolutional DNNs is conducted.

  * •

For this, an approach is presented to estimate the pixel size of persons in 2D
images from skeletal annotations, which can be used for concept mask
generation.

After a revision of concept analysis methods in Sec. 2, our approach is
introduced in Sec. 3. Finally, in Sec. 4 it is validated and used for the
exemplary assessment.

##  2 Related Work

An early approach to supervised concept analysis was NetDissect by Bau et al.
[2]. They associated single convolutional filters with semantic concepts, and
provided the Broden dataset, a combined dataset featuring a wide variety of
concepts. Building upon NetDissect, Net2Vec [5] expanded from single filters
to combinations of filters and trains a $1\times 1$ convolution to predict
concept masks from latent space outputs. Intuitively, the weight vector of the
convolution, the concept embedding vector, encodes the direction within the
layer output space that adds the concept. The authors investigate the
similarity of different concepts via cosine similarity of their concept
vectors. Similarly, TCAV by Kim et al. [11] trains linear models but using a
support vector machine on the complete latent space output for binary
classification instead of segmentation. The authors suggest to use partial
directional derivatives along the concept vectors to assess how outputs depend
on concepts in intermediate layers. Future work may investigate how this can
be applied to concept segmentation instead of concept classification. Other
than the previous linear model approaches, SeVec [8] uses a k-means clustering
approach, demonstrated on a dataset other than Broden, but again only on
image-level concepts and with a manual step in the process. The Net2Vec-based
proof of concept in [19] uses a small concept dataset for traffic sign
letters. This work also details the value of concept analysis for safety
assessment, and suggests that a mismatch of concept size and receptive field
of concept models can cause a texture bias, that is, predictions purely based
on texture. This is investigated for larger nets in this paper.

More relevant for inspection than requirements verification purposes,
unsupervised concept analysis approaches aim to find and visualize repetitive
concepts in the intermediate output of a DNN. A simple example is feature
visualization [16], where noise is optimized to maximally activate a
convolutional filter. ACE [7] instead uses super-pixels as concept candidates,
which are then clustered by their latent space proximity. In the direction of
representation disentanglement, [21] introduced a measure for the completeness
of a set of concept vectors with respect a given task. Their idea is that
post-hoc adding a semantic bottleneck with unit vectors aligned to the
concepts should not decrease the model performance. Similarly, but with
invertible DNNs instead of linear maps, the recent work in [4] tries to find a
bijection of a latent space to a product of semantically aligned sub-spaces
(and a residual space).

Experiments so far have been conducted on small resolution image datasets like
the $224\times 224$ pixels of the Broden [2, 5, 11]and ImageNet [8] data or
less [19], and have not yet been applied to large models or object detectors.

##  3 Approach

This section introduces our concept analysis approach with its modifications
to the Net2Vec concept analysis method, and an approach to estimate the body
size in pixels for persons in 2D images from skeletal annotations. Size
estimation is later used to generate ground truth segmentation masks for body
part concepts, and to categorize them by size.

###  3.1 Concept Embedding Analysis

Figure 1: Illustration of the used concept analysis approach. For a concept
$c$, here “head”, it predicts binary segmentation masks from convolutional
activation maps via (1) a 1-filter convolution with kernel $w_{c}$ and bias
$b_{c}$, (2) bilinear upscaling (here depicted using nearest pixel upscaling),
and finally (3) normalization.

Our method is illustrated in Figure 1. As a foundation, the Net2Vec [5]
approach was chosen. It allows to localize non-image-level concepts like
object parts in convolutional activation maps by predicting binary
segmentation masks. For this the spatial resolution of the convolutional
layers is used: The mask predictor is a $1\times 1$ convolution followed by
bilinear upscaling, then sigmoid normalization (and, for binarizing,
thresholding at 0.5). For comparability, the quality measure set intersection
over union (set IoU) is adopted which divides the total area of intersections
by the total area of unions between the binary ground truth masks $M_{i}$ and
the predicted segmentation masks $M_{i}^{\text{pr}}$ (binarized at 0.5):

$\displaystyle\SwapAboveDisplaySkip\text{set
IoU}\left((M_{i})_{i},(M_{i}^{\text{pr}})_{i}\right)=\frac{\sum_{i}\sum
M_{i}\cap(M_{i}^{\text{pr}}>0.5)}{\sum_{i}\sum
M_{i}\cup(M_{i}^{\text{pr}}>0.5)}\;.$ (1)

We here took the mean of batch-wise set IoU values. It must be noted that the
set IoU measure penalizes errors on small objects more than on large ones, and
it suffers under low resolution of activation maps. Below, four further
limitations of Net2Vec are collected and our countermeasures explained.

Most notably, Net2Vec uses denoising of activation maps with a ReLU suggested
in [2]. The threshold is calculated to keep the 0.5% highest activations. This
requires to load activations of the complete dataset into memory at once,
which is infeasible both for large models and large datasets. Experiments
showed that denoising makes no noticeable difference, hence it is skipped.

Next, to push the decision boundary of the model towards a value of 0.5,
Net2Vec uses a binary cross-entropy (BCE) loss with per-class-weights where
each weight is the mean proportion of pixels of the opposite class. Obtaining
the weight is an expensive pre-processing step. Here we found that global
weighting could be replaced either by calculating weights batch-wise, or using
an unweighted Tversky loss [18]—also called Dice or F1 loss—that directly
optimizes the F1 score of the segmentation per $h\times w$ image (“$\cdot$”
pixel-wise):

$\displaystyle\text{Dice loss}\left(M,M^{\text{pr}}\right)=1-\frac{2\sum
M\cdot M^{\text{pr}}}{\sum M+\sum M^{\text{pr}}}\quad\text{for
$M,M^{\text{pr}}\in[0,1]^{h\times w}$.}$ (2)

Further, the original method reports average set IoU values lower than 0.05
for part objects, which we could confirm. This can be achieved by constantly
predicting white masks (1 for all pixels). In a series of experiments we found
settings fixing this: We use a Tversky loss, Adam optimizer [12] instead of
stochastic gradient descent (SGD), with a batch size of 8 instead of 64, and
learning rate of ${10}^{-3}$ rather than ${10}^{-4}$.

Another modification used in some experiments is _adaptive kernel size_. The
original Net2Vec method uses a $1\times 1$ kernel, so each prediction only has
a spatial context of one pixel. As found in [19], this may be too small for
larger concepts and layers with higher resolution, and possibly leads to a
texture bias [6]. Following [19], this can be mitigated using a kernel size
that covers an area of the expected size of the concept, assuming low size
variance. Note that this may improve performance of a concept model, but
destroys comparability amongst models of differently sized concepts due to
incompatible kernel shapes.

###  3.2 Distance Category Estimation

Formulas for total height
---
1 $\cdot$ | bbox_width/_height
1.1 $\cdot$ | body_height
2.4 $\cdot$ | hip_to_shoulder
7 $\cdot$ | head_height
1.485 $\cdot$ | leg $\cdot\frac{h}{h-0.433}$
2.77 $\cdot$ | upper_leg $\cdot\frac{h}{h-0.405}$
3.075 $\cdot$ | lower_leg $\cdot\frac{h}{h-0.501}$
3.72 $\cdot$ | upper_arm $\cdot\frac{h}{h-0.449}$
4.46 $\cdot$ | lower_arm $\cdot\frac{h}{h-0.569}$

Formulas for derived lengths
---
body_height $\approx$ |  leg* \+ hip_to_shoulder* \+ shoulder_to_eye*/_ear*/_nose
$\approx$ |  arm + shoulder_width
leg $\approx$ |  lower_leg + upper_leg
arm $\approx$ |  lower_arm + upper_arm
head_height $\approx$ |  $1.1\,\cdot$ head_width $\approx$ $\frac{8}{7}$ head_depth
head_width $\approx$ |  ear_to_opposite_ear
$\approx$ |  $2.5\,\cdot$ eye_to_eye
head_depth $\approx$ |  $2\,\cdot$ ear_to_eye* $\approx$ $\frac{7}{4}$ ear_to_nose

* involved keypoints must be on the same side

Figure 2:  Used keypoints and links with formulas to estimate the total body
height of a person from link lengths and assumed “standard” height $h$ in
meters.

Assume an image dataset is given that provides 2D skeletal information of
persons (cf. Figure 2), possibly bounding boxes, but no depth information. The
goal of this approach is to estimate and categorize the body size of a person
depicted in a 2D image in pixels, given only lengths between keypoints. The
challenges are that keypoint information may be incomplete due to occlusion or
cropping, and that 2D projected lengths may be inaccurately short. Thus,
redundant calculation of body size from as many link types as possible is
needed. One major drawback of this method is that assumptions on “standard”
proportions must be made. This cannot be overcome without additional
information. Despite that, it was found that the approach yields surprisingly
good and intuitive results, with errors not infringing the quality of body
size categorization.

The following sources were used to relate the true length $l$ of (combinations
of) keypoint links to the true body height $h$: arts for facial and head-to-
body proportions [14]; standard educational material relating the wrist-to-
wrist span [3]; and linear models used in archeology to estimate the body size
from single long bones [14]. For long bone relations, the mean model
parameters were taken between genders. Relations involving approximate
body_height and bounding box (bbox) dimensions were estimated manually. The
resulting relation models are all of the linear nature $h=s\cdot l+c$ for some
slope $s$, and offset $c$ in meters. Given the downscaled length
$l^{\prime}=f\cdot l$ in pixels, the formula for the downscaled body size is
$f\cdot h=l^{\prime}\cdot\frac{h}{h-c}$. If $c$ is non-zero, a “standard” real
person size $h$ must be assumed, which was set to $1.7\text{\,}\mathrm{m}$
following [14]. The final formulas are shown in Figure 2. Whenever one value
has several estimation results, the maximum was used to cope with possible
length shortenings due to 2D projection.

The formulas were now leveraged to sort annotations into four size categories.
These were chosen such that in each the minimum and maximum estimated size do
not differ by more than a factor of two. Very small and very large persons
were discarded. The resulting size categories with their range of relative
sizes are: _far_ in $[0.2,0.38]$, _middle_ in $[0.38,0.71]$, _close_ in
$[0.71,1.33]$, and _very close_ in $[1.33,2.5]$. Categories are depicted in
Figure 3.

##  4 Experiments

After detailing our experiment settings, this section will validate the used
approach including hyperparameters (Sec. 4.1), then conduct exemplary
assessments of embedding quality and semantics (Sec. 4.2), as well as size
bias (Sec. 4.3).

For the experiments, we chose three networks of different size, training
objective, and training dataset, with pretrained weights from the torchvision
model zoo111 https://pytorch.org/vision/stable/models.html: ImageNet-trained
classifiers VGG16 [20] and AlexNet [13], and the object detector Mask R-CNN
[9] trained on MS COCO. As layers we chose the activated convolutional output
before each downsampling step except the first. In case of Mask R-CNN we
considered the output of each residual grouping in the backbone and the
feature pyramid. For concepts we selected a set of five large and small
concepts that are common to the Broden and MS COCO datasets: leg, arm, foot
and hand (for COCO approximated via ankle and wrist keypoints), and eye.
Images were zero-padded to square size then resized to $400\times 400$
respectively $224\times 224$ (VGG16, AlexNet) pixels to avoid feature
distortion. Ground truth masks on concepts for MS COCO images were generated
by drawing links (leg, arm) respectively points (foot, hand, eye) of width
0.025 times the image height or times the body size if this can be estimated
(see Figure 5). Intermediate outputs of the DNNs were cached with bi-float 16
precision to speed up experiments, except for the very large Mask R-CNN
feature pyramid blocks 0 and 1, and backbone layer 1. On cached layers,
concept model training was done with 5-fold cross-validation. The original
train-test splits were used.

###  4.1 Validation of the Proposed Methods

#### Size Distribution in MS COCO

To validate the size estimation approach, an analysis of the size distribution
on the popular MS COCO dataset was conducted. The size of an annotation cannot
be estimated if it provides no keypoints (very small persons and crowds) or
only disconnected keypoints. Nevertheless, size estimations could be made for
a decent proportion of the annotations in both training and test set (ca.
46%), see Figure 3. Also, for each chosen body part, a sufficient amount of
annotations is available in size categories _far_ , _middle_ , and _close_ :
more than 10,000 in the train, and 300 in the test set. These categories were
thus used for experiments. Training and test set were found to be similarly
distributed, with significantly more keypoint annotations estimated far than
close. This suggests, that the total amount of positive pixels for masks of
small far body parts is similar to that of large close ones.

#### Improvement of Net2Vec

Settings for the concept analysis approach were needed that (1) work for large
models and datasets (no expensive thresholds and weights), and (2) work for
part objects. First, the necessity to threshold the activation maps was
disproved: Skipping it had no effect on the test performance. Then, without
thresholding, a series of experiments was conducted comparing different
optimizers (SGD, Adam), batch sizes (bs), learning rates (lr), and losses
(globally weighted BCE, batch-wise weighted BCE, and Tversky). Each setting
was evaluated on AlexNet and VGG16, on all selected layers and concepts, using
the original Broden dataset [2]. Firstly, the better optimizer was chosen,
then the better batch-size and learning rate combination, and lastly losses
were compared. The consistently best and stable setting proved to be Adam
optimizer with lr ${10}^{-3}$, bs 8, with maximum five epochs due to fast
convergence. Find a comparison to the baseline for AlexNet in Figure 3 (VGG16
similar).

Figure 3:  _Top:_ Distribution by estimated person size of all annotations
(_left_) and per body part (_center_) for COCO train images (padded to square
size and resized to $400\times 400$ px); used person size categories are
illustrated on the _right_. _Bottom:_ Performance comparison of used settings
with Net2Vec baseline (cf. [5, Fig. 2]). Best viewed in color.

###  4.2 Embedding Quality and Similarity Validation

Two applications of concept analysis are to verify sufficient embedding
qualities, and to use the similarity measure on the concept models for
validation of semantic relations. For this, concept models for all chosen
concepts, networks, and layers were trained on the complete MS COCO concept
dataset. Performance results are depicted in Figure 7 (size category _all_).
As before, the variance was very low, evidencing good convergence of the
linear concept models. Convincing embedding qualities were found except for
the small concepts hand and foot in small networks. This may origin from the
approximate and noisy ground truth, and the higher set IoU penalties for low
resolution. In general, later layers with low resolution showed the best
embedding results, indicating that body parts are relatively complex concepts.
These may require larger network structures, since Mask R-CNN significantly
surpassed AlexNet and VGG16. Some exemplary output for Mask R-CNN is shown in
Figure 7.

Next, the concept model similarities were measured as the mean cosine
similarity between the normal vectors of the models, shown in Figure 4. Cosine
similarity $\frac{a\cdot b}{\|a\|\cdot\|b\|}$ of vectors
$a,b\in\mathds{R}^{n}$ is the cosine of the angle between the vectors, with 1
meaning 0° angle, and -1 meaning 180°. The results show intuitive relations
between the concepts: No similarity values were below zero, so no body part
concepts are mutually exclusive. And eye is most different from the other
parts, while hand and arm are more closely related, similarly leg and foot.
Interestingly, in the later low-resolution layers concepts were more
dissimilar, so better distinguishable, explaining the better performance here.

Figure 4:  Mean cosine similarities between normal vectors of concept models
for different body parts, by layer. AlexNet results were similar to VGG16
(_top_).

Figure 5:  Overlay (green) of segmentation masks predicted by the mean concept
model of Mask R-CNN backbone layer block 3. Original images are shown in first
column, generated ground truth annotations in second column in different
colors. Mean is taken over normalized concept vectors, cf. [17]. Masks are
upsampled using nearest rule to demonstrate resolution. Note how predicted
masks clearly correlate with the ground truth instead of being purely white.
Images are taken from test set (MS COCO val2017). For the used images thanks
to: top: Oleg Klementiev
http://farm5.staticflickr.com/4115/4906536419_6113bd7de4_z.jpg © CC BY 2.0;
middle: Nick Webb
http://farm8.staticflickr.com/7015/6795644157_f019453ae7_z.jpg © CC BY 2.0;
bottom: Yandle http://farm4.staticflickr.com/3179/2986591710_d76622fdf0_z.jpg
© CC BY 2.0

###  4.3 Correlations of Person Size and Segmentation Quality

The last series of experiments means to investigate the following questions:
1) Does the internal representation of a concept differ for different sizes of
the concept? And is there a safety critical bias towards one size (i.e.
distance from the camera)?  2) Is adaptive kernel size needed to avoid texture
bias?  A yes to 1) would suggest that different and better embeddings can be
found if concept information is assessed separately for each size category.
Then, especially for larger size categories, adaptive kernel sizes might be
necessary. To answer the questions, results on a test set restricted to one
size category were collected on the MS COCO concept data. This was done and
compared for concept models trained on the complete dataset (all nets), and
models trained on the respective size category either with $1\times 1$ or
adaptive kernel size (AlexNet, VGG16). Adaptive kernel sizes were chosen to
cover the following areas relative to the mean person size of the size
category (in height$\times$width): $0.3\times 0.1$ for leg, $0.2\times 0.15$
for arm, $0.1\times 0.1$ for foot and hand, and $0.04\times 0.04$ for eye. The
two main results were: The internal representation of body parts seems to be
mostly size invariant, and adaptive kernel sizes are not necessary.

#### Results

In Figure 7 the performance of concept models trained on _all_ data was
compared for different test subsets. The differences between size categories
did not exceed what was expected from the different set IoU penalties, so no
bias could be found here. Since a concept model trained on all data may not be
the optimal one for a size, we also compared the _all_ models to models solely
trained on the respective size category, see Figure 7. This showed that a
restricted training set may even decrease test results, indicating that at
least parts of the internal representation used for the different sizes must
be shared. To substantiate that, the normal vectors of the linear models for
the different size categories were compared. In the best performing layers the
restricted size categories had high cosine similarity (over 0.7) to _all_ ,
with _far_ deviating the most. However, _all_ could not be represented as a
linear combination of the sub-sizes, and cosine similarities of least squares
solutions did not top 0.95. So, some information even seems to get lost when
training only on single size categories. Lastly, results on single size
categories were also compared to adaptive kernel size results in Figure 7.
Adaptive kernel size would show some improvements but the best layer rarely
changed.

Figure 6:  Test set IoU results of concept models trained on the complete
dataset, by layer, annotation size category, model (top to bottom), and
concept (left to right). Note that standard deviations are marked but
negligible. Best viewed in color.

Figure 7:  Test set IoU results of concept models trained on a size subset by
layer and kernel setting. Results were obtained on the test set restricted to
the respective training size category. Results for the models trained on all
data are added for comparison, cf. Figure 7. Best viewed in color.

##  5 Conclusion

This paper proposed an efficient concept analysis approach that is fit for
practical application to large networks and datasets, and to object part
concepts. It was demonstrated how this method can be used to assess
consistency and size bias in the internal representations of a DNN. For this,
a size estimation method from 2D skeletal data is proposed together with a new
concept dataset based on MS COCO keypoint annotations. Our assessment results
suggest that the representations within standard models AlexNet, VGG16, and
Mask R-CNN are mostly invariant to different sizes respectively camera
distances. Despite drawbacks of the used set IoU metric, concept analysis is
shown to be a promising approach for verification and validation of deep
neural networks. Future work will investigate further assessment possibilities
arising from post-hoc explainable access to DNN intermediate output. This can,
e.g. , be used to test or formally verify logical properties that are
formulated on the enriched DNN output.

## References

  * [1] Arrieta, A.B., Rodríguez, N.D., Ser, J.D., Bennetot, A., Tabik, S., Barbado, A., García, S., Gil-Lopez, S., Molina, D., Benjamins, R., Chatila, R., Herrera, F.: Explainable artificial intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI. Information Fusion 58, 82–115 (2020)
  * [2] Bau, D., Zhou, B., Khosla, A., Oliva, A., Torralba, A.: Network dissection: Quantifying interpretability of deep visual representations. In: Proc. 2017 IEEE Conf. Comput. Vision and Pattern Recognition. pp. 3319–3327. IEEE Computer Society (2017). https://doi.org/10.1109/CVPR.2017.354
  * [3] De Brabandere, S.: Human body ratios. Scientific American (Bring Science Home) (Mar 2017), https://www.scientificamerican.com/article/human-body-ratios/
  * [4] Esser, P., Rombach, R., Ommer, B.: A disentangling invertible interpretation network for explaining latent representations. In: Proc. 2020 IEEE Conf. Comput. Vision and Pattern Recognition. pp. 9220–9229 (Jun 2020)
  * [5] Fong, R., Vedaldi, A.: Net2Vec: Quantifying and explaining how concepts are encoded by filters in deep neural networks. In: Proc. 2018 IEEE Conf. Comput. Vision and Pattern Recognition. pp. 8730–8738. IEEE Computer Society (2018)
  * [6] Geirhos, R., Rubisch, P., Michaelis, C., Bethge, M., Wichmann, F.A., Brendel, W.: ImageNet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness. In: Proc. 7th Int. Conf. Learning Representations. OpenReview.net (2019)
  * [7] Ghorbani, A., Wexler, J., Zou, J.Y., Kim, B.: Towards automatic concept-based explanations. In: Advances in Neural Information Processing Systems 32. pp. 9273–9282 (2019)
  * [8] Gu, J., Tresp, V.: Semantics for global and local interpretation of deep neural networks. CoRR abs/1910.09085 (Oct 2019), http://arxiv.org/abs/1910.09085
  * [9] He, K., Gkioxari, G., Dollár, P., Girshick, R.: Mask R-CNN. In: 2017 IEEE International Conference on Computer Vision (ICCV). pp. 2980–2988 (Oct 2017)
  * [10] ISO/TC 22/SC 32: ISO 26262-6:2018(En): Road Vehicles — Functional Safety — Part 6: Product Development at the Software Level, ISO 26262:2018(En), vol. 6. International Organization for Standardization, second edn. (Dec 2018)
  * [11] Kim, B., Wattenberg, M., Gilmer, J., Cai, C., Wexler, J., Viegas, F., Sayres, R.: Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (TCAV). In: Proc. 35th Int. Conf. Machine Learning. Proceedings of Machine Learning Research, vol. 80, pp. 2668–2677. PMLR (Jul 2018)
  * [12] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. In: Proc. 3rd Int. Conf. Learning Representations (2015)
  * [13] Krizhevsky, A.: One weird trick for parallelizing convolutional neural networks. CoRR abs/1404.5997 (2014), http://arxiv.org/abs/1404.5997
  * [14] Larson, D.: Standard proportions of the human body (Jan 2014), https://www.makingcomics.com/2014/01/19/standard-proportions-human-body/
  * [15] Lin, T.Y., Maire, M., Belongie, S.J., Hays, J., Perona, P., Ramanan, D., Dollár, P., Zitnick, C.L.: Microsoft COCO: Common objects in context. In: Proc. 13th European Conf. Computer Vision - Part V. Lecture Notes in Computer Science, vol. 8693, pp. 740–755. Springer International Publishing (2014)
  * [16] Olah, C., Mordvintsev, A., Schubert, L.: Feature visualization. Distill 2(11) (Nov 2017). https://doi.org/10.23915/distill.00007
  * [17] Rabold, J., Schwalbe, G., Schmid, U.: Expressive explanations of DNNs by combining concept analysis with ILP. In: KI 2020: Advances in Artificial Intelligence. pp. 148–162. Lecture Notes in Computer Science, Springer International Publishing (2020). https://doi.org/10.1007/978-3-030-58285-2_11
  * [18] Salehi, S.S.M., Erdogmus, D., Gholipour, A.: Tversky loss function for image segmentation using 3D fully convolutional deep networks. In: Proc. 8th Int. Workshop Machine Learning in Medical Imaging. vol. 10541, pp. 379–387. Springer (2017)
  * [19] Schwalbe, G., Schels, M.: Concept enforcement and modularization as methods for the ISO 26262 safety argumentation of neural networks. In: Proc. 10th European Congress Embedded Real Time Software and Systems (Jan 2020), https://hal.archives-ouvertes.fr/hal-02442796
  * [20] Simonyan, K., Zisserman, A.: Very deep convolutional networks for large-scale image recognition. In: Proc. 3rd Int. Conf. Learning Representations (2015)
  * [21] Yeh, C.K., Kim, B., Arik, S., Li, C.L., Pfister, T., Ravikumar, P.: On completeness-aware concept-based explanations in deep neural networks. In: Advances in Neural Information Processing Systems 33. vol. 33, pp. 20554–20565 (2020)


DIV=10 [section]subsection [– –]– –
[font=,beforeskip=1afterskip=0.5dent=0em]section
[font=,afterskip=-1em]subsection,subsubsection
[font=,afterskip=-1em,indent=0pt, ]paragraph

[1em]1.5em1em

# A classification of
polyharmonic Maaß forms
via quiver representations

Claudia Alfes-Neumann The author was partially supported by the Daimler and
Benz Foundation and the Klaus Tschira Boost Fund. Igor Burban Martin Raum The
author was partially supported by Vetenskapsrådet Grant 2019-03551.

###### Abstract

Abstract: We give a classification of the Harish-Chandra modules generated by
the pullback to $\mathrm{SL}_{2}(\mathbb{R})$ of _poly_ harmonic Maaß forms
for congruence subgroups of $\mathrm{SL}_{2}(\mathbb{Z})$ with exponential
growth allowed at the cusps. This extends results of Bringmann–Kudla in the
harmonic case. While in the harmonic setting there are nine cases, our
classification comprises ten; A new case arises in weights $k>1$. To obtain
the classification we introduce quiver representations into the topic and show
that those associated with polyharmonic Maaß forms are cyclic, indecomposable
representations of the two-cyclic or the Gelfand quiver. A classification of
these transfers to a classification of polyharmonic weak Maaß forms. To
realize all possible cases of Harish-Chandra modules we develop a theory of
weight shifts for Taylor coefficients of vector-valued spectral families. We
provide a comprehensive computer implementation of this theory, which allows
us to provide explicit examples.
polyharmonic Maaß forms $\blacksquare$ Harish-Chandra modules $\blacksquare$
Gelfand quiver $\blacksquare$ mock modular forms $\blacksquare$ Kronecker
limit formula
MSC Primary: 11F37, 17B10 $\blacksquare$ MSC Secondary: 11F72, 16G20

Harmonic weak Maaß forms have proved to be immensely useful in number theory
and related areas such as arithmetic geometry, combinatorics, and mathematical
physics. Numerous applications were showcased by Bringmann–Folsom–Ono–Rolen
[bringmann-folsom-ono-rolen-2018], often rooted in generating series that are
“completed” to produce harmonic weak Maaß forms. Special highlights are the
confirmation of the Andrews–Dragonette Conjecture [bringmann-ono-2006],
incoherent Eisenstein series in the Kudla Program [kudla-rapoport-yang-1999],
and Mathieu Moonshine [eguchi-ooguri-tachikawa-2011, gannon-2016] associated
with $K3$–surfaces. As work by Duke, İmamoğlu, and Tóth [dit2013] shows _poly_
harmonic weak Maaß forms play an evenly important role in number theory.
Moreover, these forms appear in string theory, especially via the theory of
modular graph functions [green-vanhove-2000], and in the correspond
mathematical theory of iterated period integrals on the moduli space of marked
genus-$1$ curves [brown-2017-preprint, brown-2018].

The study of harmonic weak Maaß forms from a representation theoretic
perspective was initiated by Bringmann and Kudla [BK]. They provided a
classification of the Harish-Chandra modules generated by the pullback to
$\mathrm{SL}_{2}(\mathbb{R})$ of harmonic weak Maaß forms of integral weight.

In the present work we study polyharmonic (weak) Maaß forms, i.e. forms that
vanish under a power of the Laplace operator, transform like modular forms,
and have at most exponential growth at the cusps. Here, the weight $k$ Laplace
operator is defined as

$\displaystyle\Delta_{k}=-\mathrm{R}_{k-2}\mathrm{L}_{k},\quad\text{where\
}\mathrm{R}_{k}=2i\partial_{\tau}+ky^{-1},\,\mathrm{L}_{k}=-2iy^{2}\partial_{\overline{\tau}}\text{.}$

We call a polyharmonic Maaß form $f$ of weight $k$ satisfying
$\Delta^{d+1}_{k}f=0$ and $\Delta^{d}_{k}f\neq 0$ polyharmonic of  _exact
depth $d$_ (compare Definition LABEL:def:polyharmonic_maass_forms). A
classical example of such a form, which appears already in the Kronecker limit
formula, is the function

$\displaystyle-\tfrac{1}{6}\,\mathrm{log}\big{(}y^{12}\big{|}\eta(\tau)\big{|}^{48}\big{)}\text{,}$

where $\eta(\tau)=\exp(\pi i\tau/12)\,\prod_{n=1}^{\infty}(1-\exp(2\pi
in\tau))$.

### The classification

Our first main result is the classification of Harish-Chandra modules
corresponding to polyharmonic Maaß forms of integral weight. As a special case
we recover the classification for harmonic Maaß forms obtained by Bringmann
and Kudla. Harish-Chandra modules associated with polyharmonic Maaß forms are
formally described in Section LABEL:ssec:automorphic_forms. Informally, they
capture all $\mathrm{SL}_{2}(\mathbb{R})$-covariant differential equations
satisfied by a given form.

######  Classification A.

In Sections LABEL:ssec:classification_representation_labels and
LABEL:ssec:classification_BK_labels we give a classification comprising $10$
cases of Harish-Chandra modules associated with weight-$k$ polyharmonic weak
Maaß forms of exact depth $d$: Cases Ia–d for $k<1$, Cases IIa–b for $k=1$,
and Cases IIIa–d for $k>1$. The classification is given in terms of the
vanishing and non-vanishing of the following functions:

$k<1$ |  | $k=1$ |  | $k>1$
---|---|---|---|---
$\mathrm{L}_{k}\Delta_{k}^{d}\,f\stackrel{{\scriptstyle?}}{{=}}0$, $\mathrm{R}_{k}^{1-k}\Delta_{k}^{d}\,f\stackrel{{\scriptstyle?}}{{=}}0$ |  | $\mathrm{L}_{k}\Delta_{k}^{d}\,f\stackrel{{\scriptstyle?}}{{=}}0$ |  |  $\mathrm{L}^{k}\Delta_{k}^{d-1}\,f\stackrel{{\scriptstyle?}}{{=}}0$, $\mathrm{L}_{k}\Delta_{k}^{d}\,f\stackrel{{\scriptstyle?}}{{=}}0$, $\mathrm{L}_{k}^{k}\Delta_{k}^{d}\,f\stackrel{{\scriptstyle?}}{{=}}0$.

######  Remark 1.

  1. (1)

The three vanishing conditions that appear for $k>1$ imply one another from
left to right, so that they yield $4$ as opposed to $8$ cases.

  2. (2)

The classification of harmonic weak Maaß forms, i.e. the case $d=0$,
encompasses only $9$ cases. Each of them generalizes in a suitable way, but
there is an additional Case IIId if $k>1$, which occurs only in positive depth
$d$.

######  Example B.

In our classification, the previously mentioned form
$-\frac{1}{6}\log(y^{12}|\eta(\tau)|^{48})$ falls into Case Ia.
Bringmann–Kudla highlighted $s$-derivatives of Eisenstein series as a further
class of interesting functions that are not covered by their classification.
These are polyharmonic Maaß forms of type Id if $k<0$, of type Ia if $k=0$, of
type IIIb if $k=2$, and of type IIIa if $k>2$. The case $k=1$ gives rise to
incoherent Eisenstein series that fall under type IIa. See Section
LABEL:sec:modular_realization for details.

Elementary Lie algebra considerations that serve well in the harmonic setup
cease to work in ours. In particular, the method of classification employed by
Bringmann–Kudla relies heavily on the harmonicity condition $\Delta_{k}\,f=0$,
which implies that $K$-types of the Harish-Chandra module associated with $f$
occur with multiplicity at most $1$. The transition between $K$-types can
therefore be adequately described by the vanishing or non-vanishing of
scalars. This holds no longer true for general polyharmonic Maaß forms, which
is the major obstacle to the classification that we achieved. It turns out
that the theory of quiver representations beautifully enables us to circumvent
this obstacle. In Proposition LABEL:P:Equivalence and Theorem
LABEL:T:Equivalence, we provide equivalences between categories of specific
Harish-Chandra modules and quiver representations following [Gelfand, mp1, mp,
CB, Nodal, Gnedin]. This naturally leads us to representations of the Gelfand
quiver, which are well-known to be intricate. A key step in our classification
is Theorem LABEL:thm:corrspondence_polyharmonic_maass_to_harish_chandra, in
which we show that quiver representations that arise from polyharmonic Maaß
forms are cyclic and indecomposable. There are only few cyclic representations
of the Gelfand quiver, which we give in Theorem
LABEL:T:GelfandQuiverCyclicReps and which mirror the Cases Ia–d and IIIa–d in
our classification. Cases IIa and IIb arise from the two-cyclic quiver as
discussed in Remark LABEL:rm:CyclicQuiverCyclicReps.

### The explicit realization

Our second main result is the explicit realization of all cases of the
classification. Classification A constrains the possible Harish-Chandra
modules associated with polyharmonic weak Maaß forms, however a priori it is
not clear whether each case appears.

######  Theorem C.

For any $k\in\mathbb{Z}$ and any case of Classification A associated with this
$k$, there is a (vector-valued) polyharmonic weak Maaß form of weight $k$ that
realizes this case.

######  Remark 2.

In Theorem LABEL:thm:spectral_families_altering_weight we provide a
comprehensive theory that allows us to alter the weight of a modular
realization of Cases Ia–d or IIIa–d if it is obtained from a spectral family.
This theory involves a detailed analysis of the action of several differential
operators on spectral families and is interesting in its own right.

To prove Theorem C we construct preimages under $\Delta_{k}^{d}$ of the
realizations provided by Bringmann and Kudla. For scalar-valued realizations
we can employ a classical approach and extract polyharmonic Maaß forms from
the Taylor coefficients of a spectral family. This idea was already used by
Lagarias and Rhoades [lagariasrhoades] for Eisenstein series and by
Duke–İmamoğlu–Tóth [dit2013] for Poincaré series. For vector-valued forms we
vastly generalize this method. We show that the weight of a modular
realization can be adjusted when taking products with specific vector-valued
Maaß forms. In special cases this was also used by Bringmann and Kudla. Our
Theorem LABEL:thm:spectral_families_altering_weight extends this approach to
the broadest context compatible with our classification.

The proof of Theorem LABEL:thm:spectral_families_altering_weight depends on a
delicate analysis of the action of the Laplace operator on specific products
of Maaß forms. It can be viewed as an explicit instance of a theory by
Bernstein–Gelfand [bernstein-gelfand-1980], who studied tensor products of
Harish-Chandra modules with finite dimensional representation. Our treatment
is sufficiently explicit to accommodate a computer implementation, which is
available on the third author’s homepage and allows for the precise
calculation of coefficients in every single case.

### Structure of the paper

The paper is structured as follows. In Section 1 we provide preliminaries on
Harish-Chandra modules and investigate the structure of the relevant path
algebra. In Section LABEL:sec:cyclic_modules we classify the corresponding
cyclic modules. The bridge between these results and the classification of the
Harish-Chandra modules arising from polyharmonic weak Maaß forms is provided
in Section LABEL:sec:polyharmonic_to_quiver. In Section
LABEL:sec:spectral_taylor_coefficients we develop our results that enable us
to alter the weight of spectral families. We use these results to show that
there exist polyharmonic weak Maaß forms for each of the cases of the
classification in Section LABEL:sec:modular_realization.

##  1 Blocks of the category of Harish–Chandra–modules for
$\mathrm{SL}_{2}(\mathbb{R})$

###  1.1 Preliminaries on Harish-Chandra–modules

Let $G=\mathrm{SL}_{2}(\mathbb{R})$ and $K=\mathrm{SO}_{2}(\mathbb{R})$ be a
maximal compact subgroup. Let

$\displaystyle\mathfrak{g}:=\mathrm{Lie}(G)\otimes_{\mathbb{R}}\mathbb{C}\cong\mathfrak{sl}_{2}(\mathbb{C})=\left\langle
H=\left(\begin{smallmatrix}0&-i\\\
i&0\end{smallmatrix}\right)\text{,}\,X=\mfrac{1}{2}\left(\begin{smallmatrix}1&i\\\
i&-1\end{smallmatrix}\right)\text{,}\,Y=\left(\begin{smallmatrix}1&-i\\\
-i&-1\end{smallmatrix}\right)$

be the complexified Lie algebra of $G$ and $U(\mathfrak{g})$ be the universal
enveloping algebra of $\mathfrak{g}$. The following relations in
$\mathfrak{g}$ are satisfied:

$\displaystyle[H,X]=2X\text{,\ }[H,Y]=-2Y\text{\ and\ }[X,Y]=H\text{.}$

Let

$\displaystyle C=H^{2}-2H+4XY=H^{2}+2H+4YX\in U(\mathfrak{g})$ (1.1)

be a Casimir element. It is well-known that the center $\mathfrak{z}$ of
$U(\mathfrak{g})$ is $\mathbb{C}[C]$ (the algebra of polynomials in $C$). A
calculation shows that

$\displaystyle\begin{aligned}
&XY=\mfrac{1}{4}\bigl{(}C-H^{2}+2H\bigr{)}=\mfrac{1}{4}\bigl{(}C-(p^{2}-1)\bigr{)}\text{,}\\\
&YX=\mfrac{1}{4}\bigl{(}C-H^{2}-2H\bigr{)}=\mfrac{1}{4}\bigl{(}C-(p^{2}-1)\bigr{)}\text{.}\end{aligned}$
(1.2)

######  Definition 1.1.

A complex vector space $M$ is a $(\mathfrak{g},K)$–module if it has a
structure $(M,\circ)$ of a representation of $\mathfrak{g}$ as well as a
structure $(M,\cdot)$ of a representation of $K$ such that

$\displaystyle\bigl{(}\mathrm{Ad}_{g}(Z)\bigr{)}\circ
v=g^{-1}\cdot\bigl{(}Z\circ(g\cdot v)\bigr{)}$

for any $v\in M$, $g\in G$ and $Z\in\mathfrak{g}$, where $\mathrm{Ad}$ is the
adjoint action of $G$ on $\mathfrak{g}$. In what follows, we shall omit
$\circ$ and $\cdot$ from the notation for the action on $M$. For
$n\in\mathbb{Z}$ we put:

$\displaystyle M_{n}=\big{\\{}v\in M\,:\,H\circ v=nv\big{\\}}\text{.}$

A $(\mathfrak{g},K)$–module $M$ is a _Harish–Chandra_ module if it is finitely
generated over $U(\mathfrak{g})$ and

$\displaystyle M\cong\bigoplus_{n\in\mathbb{Z}}M_{n}\text{\ with\
}\dim_{\mathbb{C}}(M_{n})<\infty\text{\ for all\ }n\in\mathbb{Z}\text{.}$

In what follows, $\operatorname{\mathsf{HC}}(\mathfrak{g},K)$ denotes the
category of Harish–Chandra $(\mathfrak{g},K)$–modules.

######  Definition 1.2.

Let $l\in\mathbb{N}_{0}$ and $\gamma=l^{2}-1$. Let
$\operatorname{\mathsf{HC}}_{l}(\mathfrak{g},K)$ be the full subcategory of
the category of $(\mathfrak{g},K)$-modules consisting of such modules $M$
which are

  1. (i)

finitely generated as $U(\mathfrak{g})$-modules;

  2. (ii)

there exists $m\in\mathbb{N}$ (depending on $M$) such that $(C-\gamma
I)^{m}\cdot M=0$.

We have the following standard result.

######  Lemma 1.3.

The category $\operatorname{\mathsf{HC}}_{l}(\mathfrak{g},K)$ is a full
subcategory of $\operatorname{\mathsf{HC}}(\mathfrak{g},K)$. For any object
$M$ of $\operatorname{\mathsf{HC}}_{l}(\mathfrak{g},K)$ we have a direct sum
decomposition

$\displaystyle M=\bigoplus\limits_{i\in\mathbb{Z}}M_{-l-1+2i}$

and its $\mathfrak{g}$–module structure can be visualized by the following
(infinite) diagram of finite dimensional vector spaces and linear maps:

We call (1.3) a _diagram description_ of a Harish–Chandra module
$M\in\operatorname{\mathsf{HC}}_{l}(\mathfrak{g},K)$. For any
$p\in\mathbb{Z}$, consider the following fragment of (1.3):

E-Mail<EMAIL_ADDRESS>
Universität Paderborn, Mathematisches Institut, Warburger Straße 100, 33098
Paderborn, Germany E-mail<EMAIL_ADDRESS>
Chalmers tekniska högskola och Göteborgs Universitet, Institutionen för
Matematiska vetenskaper, SE-412 96 Göteborg, Sweden E-mail: martin@raum-
brothers.eu Homepage: https://martin.raum-brothers.eu