0 Research

# Co-Designing Unstructured Text Data Visualization Systems

Beck Langstone
Department of Human-Computer Interaction
Carleton University e-mail<EMAIL_ADDRESS>Fateme Rajabiyazdi
Department of Systems and Computer Engineering
Carleton University e-mail<EMAIL_ADDRESS>
###### Abstract

We present our in-progress work on co-designing a visualization tool for
presenting unstructured text. We have conducted a focus group with a variety
of professionals who regularly analyze large corpora of unstructured text. Our
preliminary insights indicate there is an unmet need to visually explore the
dynamics between entities and actors extracted from unstructured text.
Additionally, large corpora contain multiple perspectives on the same series
of events. There is a need to disentangle these perspectives and visually show
the multiple narratives present in the data. In our future work, we will co-
design low-fidelity prototypes to create a broad consideration space of
possible solutions for visualizing unstructured text.

Human-centered computingVisualizationVisualization techniquesText Data
Visualization; Human-centered computingVisualizationVisualization design and
evaluation methods

##  1 Introduction

There has been an explosion in the amount of qualitative data generated every
day, and it is expected to continue growing. Unstructured text data is
ubiquitous, and can be found in open-ended surveys, comments, social media
posts, news articles, and more. With the growth in the amount of qualitative
data, there’s also an increasing need to understand the data. Finding trends,
identifying risks, actors, influencers, and other patterns will become
increasingly difficult as the quantity of data increases. Visualizing this
data can be a solution to address these challenges.

††Poster presented at Graphics Interface Conference 2022
16-19 May - Montreal, QC, Canada
Copyright held by authors.

In the literature, there are design guidelines for developing quantitative
data visualizations. However, there is a lack of understanding and guidelines
on how to design and develop qualitative data visualizations. Additionally,
while there are existing qualitative data visualization tools, they are often
tailored for a specific goal or use case [5, 3]. For example, Storifier [5] is
a text visualization tool that is designed to support journalists with close
reading tasks, but it is not well suited for short bodies of text.
ConceptVector [3] is a text visualization tool that allows users to analyze
text using interactive lexicon building, but does not allow users to explore
the actors, entities and narratives of the text data. There is a need to
create a qualitative data visualization tool with a level of generality and
customizability that makes it applicable to a wide variety of use cases.

The objective of this research is to design and develop a qualitative data
visualization dashboard that provides users with ways to gain insights from
unstructured text data. Our goal is to maintain a level of generality and
customization that makes the tool applicable to a variety of use cases. With
our in-progress research, we are defining requirements for an unstructured
text data visualization tool. Using focus groups, we are gathering
requirements to design a solution.

##  2 Background and Related Work

Our review of related work focuses on existing visualization tools and
approaches to text visualization. ConceptVector [3] is a text analysis
visualization tool that allows users to build their own concepts from a set of
seed terms. The unique concept building features of ConceptVector were
designed to mitigate errors that arise as a result of natural language
polysemy and homonymy in other text analysis systems that use pre-built
lexicons to define concepts. Polysemy and hononymy both are traits of words
that have multiple senses associated with one lexical form, which creates
lexical ambiguity. ConceptVector supports the creations of concepts generally,
but the concept of a particular actor or entity is not particularly well
supported with this tool. We are tackling this issue by designing our tool
with the tasks of exploring and understanding entities and actors in mind.
There is not a straightforward way to understand multiple storylines as they
are reported by differing perspectives, which is a need we aim to address with
our design.

Lu et al. [2] designed a tool to assist users with large-scale analysis of
text data aggregated from different media sources, across more than one
corpus. Users can explore, link, and annotate data from multiple sources to
investigate drivers of discourse. This tool employs a user guided semantic
lexical matching scheme, causality metrics for identifying media drivers, and
a causality-driven annotation scheme for exploring data. These causality
features allow users to see which events may have caused another using a
Granger causality test. While this causality metric is unique and interesting,
it makes the assumption that causal effects can only occur in one direction,
where X causes Y. However, causality can be bidirectional, where X can cause Y
and Y can cause X. The relationship between cause and effect can be understood
as part of a narrative, and there may be differing narratives in data sources.
We aim to address this challenge by supporting multiple storylines in our
visualization.

Storifier [5] is a text visualization tool that helps journalists and news
analysts with the task of close reading. While automated text analysis is used
by journalists, they do not replace the human judgement needed for fine-
grained, qualitative forms of analysis. This tool focuses on supporting the
task of reading, allowing users to drill down to the original text from a
corpus-level overview. Users are able to quickly and easily transition between
levels of detail, starting with a summarized view that provides a top-down
awareness of corpus trends and high level patterns. Users are able to navigate
and explore their dataset with a variety of compoundable filters. In these
views, users are able to tag and annotate their data, allowing them to revisit
user-defined segments of interest within documents. This ability to explore a
large corpus of text data at the macro and micro scale offers a supportive
interface to users to efficiently explore narratives. While this tool is well
suited for long sections of unstructured text, it is not ideal for analyzing
short unstructured text sourced from tweets or other short posts. Our tool
will be designed with the flexibility to tackle both forms of unstructured
text.

##  3 Methodology

Our goal is to design and develop a visualization with a level of generality
and customization options to create a flexible tool that is applicable to a
variety of use cases. To accomplish this goal, we have conducted an initial
focus group to gather requirements. In order to build this visualization tool,
we have developed our approach on previous research. We are using Kerzner’s
Framework for Creative Visualization-Opportunities Workshops [1] as an
approach to explore and characterise domain problems and visualization focus
groups with our industry partners. This general approach has guided our first
focus group session successfully, and we are in the process of analysing and
coding the transcript data before beginning our next focus group session.

Due to the pandemic, our focus group session has been conducted online via
Microsoft Teams. Sessions were audio and video recorded for analysis.
Following Kezner’s model, our focus group session was made of 3 main stages:
Opening, core, and closing. In the opening, we introduced ourselves to foster
agency and encourage collegiality and trust. We were able to establish
interest in our area of research, which was shown by our participants’
enthusiasm and willingness to share. In our first session, we explored the
following questions.

  * •

What are your current analysis methods?

  * •

What are your current analysis challenges?

  * •

Are there limitations to the existing tools you use?

These questions elicited thoughtful responses from our participants, who each
had unique backgrounds and experiences.

After a break, we moved on to a wishful thinking exercise. In this exercises,
we asked participants to imagine they had just been given a new dataset to
analyze. Next, we asked the following.

  * •

What would you like to know about the data?

  * •

What tasks would you like to do with the data?

  * •

Is there a visual representation of the data that could be helpful to you?

We are also following guidance from Munzner’s nine stage design study
methodology [4] to guide our research. At this point, we are in the discover
phase where we are focusing on problem characterization and abstraction. This
stage is particularly critical to our work, as one of our research goals is to
create a visualization tool that is applicable to a variety of use cases. This
stage will help us ensure that our abstractions are well supported and
transferable to other domains. While the refinement of the abstraction begins
in this stage, it will continue through all subsequent stages of this model.

##  4 Preliminary Findings

From our initial focus group session, we have uncovered themes that will
inform the design of our visualization tool. Two main tasks our participants
are trying to accomplish with their data analysis are uncovering narratives
and storytelling. Often, our participants will begin their analysis with a
research question that helps inform how they go about their data analysis.
Their data analysis is exploratory in nature, which presents an opportunity
for supporting exploration with visualization.

Participants expressed that they experience difficulty in analyzing and
understanding the relationships between entities in text over time, and from
differing perspectives. While they are able to extract entities from
unstructured text, a significant challenge is understanding the source’s
perspective and bias. In large, multi-source data sets of unstructured text
there are inevitably multiple perspectives, leading to multiple entangled
storylines. The dynamics of these entities are made complex by these two
aspects: the changes of these dynamics over time, and the way these dynamics
are described by different sources. There is a need to visually explore these
dynamics to understand the relationships between entities and actors.

##  5 Conclusion and Future Work

As we continue to characterize the challenges of visualizing text data and
refine abstractions, we will conduct further focus group sessions. The design
requirements gathered from the first focus group will help us design lo-fi
prototypes to validate our data abstractions and test visual encoding and
interaction mechanisms. As Munzer points out, While there is usually not a
best solution, there are many good and ok ones. [4]. By creating multiple lo-
fi prototypes, we will create a broad consideration space of possible
solutions.

###### Acknowledgements.

This work was supported in part by NSERC and OCE grants and our industry
partner, Novacene.ai. We’d like to thank our study participants for their
contributions.

## References

  * [1] E. Kerzner, S. Goodwin, J. Dykes, S. Jones, and M. Meyer.  A framework for creative visualization-opportunities workshops.  IEEE transactions on visualization and computer graphics, 25(1):748–758, 2018. doi: 10 . 1109/TVCG . 2018 . 2865241
  * [2] Y. Lu, H. Wang, S. Landis, and R. Maciejewski.  A visual analytics framework for identifying topic drivers in media events.  IEEE Transactions on Visualization and Computer Graphics, 24(9):2501–2515, Sept. 2018. doi: 10 . 1109/TVCG . 2017 . 2752166
  * [3] D. Park, S. Kim, J. Lee, J. Choo, N. Diakopoulos, and N. Elmqvist.  ConceptVector: Text visual analytics via interactive lexicon building using word embedding.  IEEE Transactions on Visualization and Computer Graphics, 24(1):361–370, Jan. 2018. doi: 10 . 1109/TVCG . 2017 . 2744478
  * [4] M. Sedlmair, M. Meyer, and T. Munzner.  Design study methodology: Reflections from the trenches and the stacks.  IEEE transactions on visualization and computer graphics, 18(12):2431–2440, 2012. doi: 10 . 1109/TVCG . 2012 . 213
  * [5] N. Sultanum, A. Bezerianos, and F. Chevalier.  Text visualization and close reading for journalism with storifier.  In 2021 IEEE Visualization Conference (VIS), pp. 186–190. IEEE, 2021. doi: 10 . 1109/VIS49827 . 2021 . 9623264


\path[->,black](U1) edge node[right=-2,font=\tiny] {$\beta_{4}$} (Uk-1);
\path[->,black](U1) edge node[above=1,font=\tiny] {$\beta_j$} (U7);

\path[->,black](U1) edge node[above=1,font=\tiny] {$\beta_{(n-2)}$} (U6);

\path[->,black](U5) [bend right] edge node[left=1,font=\tiny] {$\alpha_{(n-1)}$} (U1);
\path[->,black](U1)  edge node[above=7,font=\tiny] {$\beta_{(n-1)}$} (U5);

\path[->,black] (U1) edge  [in=60,out=120,loop] node[above=-3,font=\tiny] {$c_{L^{n}_{i_{n}}, n}$}

\node at (-12,0)(U11) {\color{white}$(46)$};
\node at (11,0)(U10) {$(53)$};
\end{tikzpicture}
\label{examplebca}
\end{center}

$\alpha_{j}$, $\beta_{j}$ and $c_{L^{n}_{i_{n}},n}$ denote  $j\times 1$-matrices of the form:
\par\bigskip
$\alpha_{j}=\left[\begin{array}{ccc}\alpha^{j}_{L^{1}_{i_{1}},n}  \\\alpha^{j}_{L^{2}_{i_{2}},n} \\\vdots  \\\alpha^{j}_{L^{s}_{{i_{s}}},n}  \\\vdots \\\alpha^{j}_{L^{j}_{i_{j}}, n}\end{array}\right]$, \hspace{0.2cm} $\beta_{j}=\left[\begin{array}{ccc}\beta^{j}_{L^{1}_{i_{1}},n}  \\\beta^{j}_{L^{2}_{i_{2}},n} \\\vdots  \\\beta^{j}_{L^{s}_{i_{s}},n}  \\\vdots \\\beta^{j}_{L^{j}_{i_{j}}, n}\end{array}\right]$, \hspace{0.2cm} $c_{L^{n}_{i_{n}},n}=\left[\begin{array}{ccc}c_{L^{n}_{{1}},n}  \\c_{L^{n}_{{2}},n} \\\vdots  \\c_{L^{n}_{{i}},n} \\\vdots \\c_{L^{n}_{(u_{n}-u_{(n-1)}),n}}\end{array}\right] $\par\bigskip

where $\alpha^{j}_{L^{s}_{i_{s}},n}$ ($\beta^{j}_{L^{s}_{i_{s}},n}$) is a set of arrows defined by the successor sequence at vertex $L^{s}_{i_{s}, n}$ connecting the corresponding polygons (polygon $P_{n}$ with the corresponding $P_{j}$). And $c_{L^{n}_{i_{n},n}}$ is a set of loops defined by vertices ${L^{n}_{i_{n},n}}$, $1\leq i_{n}\leq u_{n}-u_{(n-1)}$.

\par\bigskip

The following relations generate the admissible ideal $J$ of the Brauer configuration algebra $\Lambda_{D^{n}}=kQ_{D^{n}}/J$, for all possible values of $i, i', j, j', r, r'$ and $n$.

\begin{enumerate}
\item $(c_{L^{n}_{{r},n}})^{2}$,\quad $c_{L^{n}_{{r},n}}c_{L^{n}_{{r'},n}}$,\quad $r\neq r'$,
\item $\alpha^{j}_{L^{i}_{{r}},n} \alpha^{j}_{L^{i'}_{{r'}}, n} $,\quad$i\neq i'$,
\item $\alpha^{j}_{L^{i}_{{r}},n} \alpha^{(j+1)}_{L^{i'}_{{r'}}, n}$,
\item  $c_{L^{n}_{i_{n},n}}\beta_{i}$,
\item  $\alpha_{(n-1)}c_{L^{n}_{i_{n},n}}$,
\item For $1\leq j\leq n$, fixed and $1\leq i\leq j$, $s_{L^{i}_{j, n}}-s_{L^{j}_{j', n}}$ where $s_{x}$ is a special cycle associated to the vertex $x$,
\item $\beta_{i}\alpha_{i}$,
\end{enumerate}
products of the form; $\beta_{i}\alpha_{i}$, $\alpha_{(n-1)}c_{L^{n}_{i_{n},n}}$, $c_{L^{n}_{i_{n},n}}\beta_{i}$ means that relations of the form $xx'$, $y'y$ and $z'z$ have place where $x'$, $y'$ and $z'$ are entries of the corresponding matrices.\par\bigskip
The following result categorifies numbers of a counting function $u_{t}$, for $t\geq1$.
\addtocounter{teor}{4}

\begin{teor}\label{gral1}
\textit{For $1\leq i\leq n$ and $n>1$ fixed, the number of summands in the heart of the indecomposable projective module $P_{i}$ over the algebra $\Lambda_{D^{n}}$ is $u_{i}$.}

\end{teor}

\textbf{Proof.}  Since $\mathrm{rad}^{2}\hspace{0.1cm}P_{i}\neq0$, then the number of summands in the heart of the indecomposable projective module $P_{i}$ equals the number of its nontruncated vertices counting repetitions, which by definition is given by the sum $u_{1}+(u_{2}-u_{1})+\dots+(u_{(i-1)}-u_{(i-2)})+(u_{i}-u_{(i-1)})=u_{i}$. We are done.\hspace{0.5cm} $\square$

\begin{teor}\label{gral2}
\textit{For $n\geq 1$ fixed, $\mathrm{dim}_{k}\hspace{0.1cm}\Lambda_{D^{n}}=2n+n(n-1)u_{1}+2\underset{i=2}{\overset{n}{\sum}}t_{(n-i)}(u_{i}-u_{(i-1)})$.}

\end{teor}

\textbf{Proof.} It suffices to note that $val(L^{i}_{i_{s},n})=n-i+1$ and $\mu^{n}(L^{i}_{i_{s},n})=1$ for any $L^{i}_{i_{s},n}\in D_{0}^{n}\backslash P^{n}_{n}$, whereas for any $x\in P^{n}_{n}$, it holds that $val(x)=1$ and $\mu^{n}(x)=2$. We are done.\hspace{0.5cm}$\square$
\par\bigskip
Since for any $n>1$, $\mathrm{rad}^{2}\hspace{0.1cm}\Lambda_{D^{n}}\neq0$, then we have the following result regarding the center of these algebras.
\begin{teor}\label{gral3}
\textit{For $n\geq 2$ fixed, $\mathrm{dim}_{k}\hspace{0.1cm}Z(\Lambda_{D^{n}})=(u_{n}-u_{(n-1)})+(n+1)$.}
\end{teor}

\textbf{Proof.} Note that $|D_{0}^{n}|=u_{n}$,\quad $|D_{1}^{n}|=n$,\quad $\underset{\alpha\in D_{0}^{n} }{\sum}\mu^{n}(\alpha)=2u_{n}-u_{(n-1)}$. Since $\#(Loops\hspace{0.1cm} Q_{D^{(n-1)}})=|\mathscr{C}_{\mathscr{D}^{n}}|$, the theorem holds.\hspace{0.5cm}$\square$

\addtocounter{Nota}{3}

\begin{Nota}\label{general}
Perhaps, the sequence $C_{n}$ of Catalan numbers is one of the most interesting counting functions, they count the number of plane binary trees with $n+1$ endpoints (or $2n+1$ vertices), the number of triangulations of an $(n+3)$ polygon, or the number of paths $L$ in the $(x, y)$-plane from $(0,0)$ to $(2n, 0)$ with steps $(1, 1)$ and $(1, -1)$ that never pass below the $x$-axis, such paths are called \textit{Dyck paths} \cite{Stanley}. Thus, if $u_{n}=C_{n+1}$, $n\geq 1$ then Theorem \ref{gral1} categorifies numbers in this sequence $C_{n}$ via these enumeration problems.\par\bigskip

Since the number of compositions (partitions in which the order of the summands is considered) of a positive integer $n$ in which no 1's appear is the Fibonacci number $f_{(n-1)}$ \cite{Andrews}. Then Theorem \ref{gral1} categorifies these numbers by assuming that $u_{n}=f_{(n-1)}$ with $n\geq 4$. If $j>4$, then $\mathrm{dim}_{k}\hspace{0.1cm}(Z(\Lambda_{D^{j}})/C_{j})-1=f_{(j-4)}$, where $C_{j}$ is a $k$-subspace of $Z(\Lambda_{D^{j}})$ isomorphic to $Z(\Lambda_{D^{j-1}})$.\par\bigskip

Theorem \ref{gral1} categorifies the sequence $p(n)$ which gives the number of partitions of a positive integer $n$, recall the Hardy-Ramanujan theorem which states that for large $n$, $p(n)\sim \frac{1}{4n\sqrt{3}}e^{\pi\sqrt{\frac{2n}{3}}}$ (see also the sequence A002865 whose numbers give the differences $p(n)-p(n-1)$). In this case, we use $u_{n}=p(n+1)$, $n\geq1$.\par\bigskip

Another interesting sequence categorified by Theorem \ref{gral1} is the sequence $M(n)$ encoded in the OEIS as A000372, which consists of Dedekind numbers, these numbers count the number of antichains in the powerset $2^{\textbf{n}}$ (i.e., the set consisting of all the subsets of $\textbf{n}=\{1, 2,3,\dots, n\}$) ordered by inclusion or the number of elements in a free distributive lattice on $n$ generators. In this case $u_{n}=M(n)$, for $n\geq1$, worth noting that up to date only 8 numbers of this sequence are known.

\end{Nota}

\begin{bibdiv}
\begin{biblist}
%\bib{Ahmed}{book}{title={Algebraic Combinatorics of Magic Squares},Author={M. Ahmed}, Author={}, Author={}, date={2004},Publisher={California University}, address={Dissertation}}

\bib{Andrews}{book}{title={The Theory of Partitions},
Author={G. Andrews}, Author={}, Author={}, date={1998},
Publisher={Cambridge University. Press}, address={Cambridge}}

\bib{Brenner1}{article}{title={Endomorphism algebras of vector spaces with distinguished sets of subspaces}, subtitle={}, Author={S. Brenner},
Author={}, Author={}, Author={}, journal={J. Algebra},
volume={6}, date={1967}, number={}, pages ={100-114}, note={}

\bib{Brenner2}{article}{title={On four subspaces of a vector space}, subtitle={}, Author={S. Brenner},
Author={}, Author={}, Author={}, journal={J. Algebra},
volume={29}, date={1974}, number={}, pages ={587-599}, note={}

\bib{Canadas3}{article}{title={Categorification of some integer sequences via Kronecker modules}, subtitle={}, Author={A. M. Ca\~nadas},
Author={I.D. Marin}, Author={P.F.F. Espinosa}, Author={}, journal={JPANTA},
volume={38}, date={2016}, number={4}, pages ={339-347}, note={}

\bib{Fahr1}{article}{title={A partition formula for Fibonacci numbers}, subtitle={}, Author={P. Fahr},
Author={}, Author={C. M. Ringel}, Author={}, journal={J. Integer Seq.}, volume={11}, date={2008}, number={08.14}, pages

\bib{Fahr2}{article}{title={Categorification of the Fibonacci numbers using representations of quivers}, subtitle={}, Author={P. Fahr},
Author={}, Author={C. M. Ringel}, Author={}, journal={J. Integer Seq.},
volume={15}, date={2012}, number={12.2.1}, pages ={}

\bib{Fahr3}{article}{title={The Fibonacci triangles}, subtitle={}, Author={P. Fahr},
Author={}, Author={C. M. Ringel}, Author={}, journal={Advances in Mathematics.},
volume={230}, date={2012}, number={}, pages ={2513--2535}

\bib{Gelfand}{article}{title={Problems of linear algebra and classification of quadruples of subspaces
in a finite dimensional vector space},
subtitle={}, Author={I.M. Gelfand}, Author={V.A. Ponomarev}, journal={Colloq. Math. Soc. János Bolyai, Hilbert Space
Operators, Tihany}, volume={5},
date={1970}, pages={163--237}}

\bib{Green}{article}{title={Brauer configuration algebras: A generalization of
Brauer graph algebras}, subtitle={}, Author={E.L. Green},
Author={}, Author={S. Schroll}, Author={}, journal={Bull. Sci. Math.},
volume={141}, date={2017}, number={}, pages ={539--572}

\bib{Knuth}{book}{title={The Art of Computer Programming},
Author={D. Knuth}, Author={}, Author={}, edition={}, date={2004},
Publisher={Addison-Wesley}, address={}, volume={4}, note={Fascicle. 3}}

\bib{Lin}{article}{title={On the applications of partition diagrams for integer partitioning},
Author={R.B. Lin}, Author={}, Author={}, journal={Proc.  The 23rd workshop on combinatorial mathematics and computation theory}, date={2006},
volume={}, number={}, note={}}

\bib{Luschny}{book}{title={Counting with partitions},
Author={P. Luschny}, Author={}, Author={}, journal={} , date={2011}, volume={OEIS.org},
publisher={}, number={}, note={http://www.luschny.de/math/seq/CountingWithPartitions.html}}

\bib{Nazarova2}{article}{title={Representations of a tetrad}, Author={L.A. Nazarova}, Author={},
Author={}, Author={}, Author={}, journal={ Izv. AN SSSR Ser. Mat.},
volume={7}, date={1967}, number={4}, pages ={1361-1378 (in Russian)}, note={English transl. in: Math. USSR Izvestija 1 (1967) 1305-1321, 1969.}

\bib{Ringel}{article}{title={Catalan combinatorics of the hereditary artin algebras}, subtitle={}, Author={C.M. Ringel},
Author={}, Author={}, Author={} journal={},
volume={}, date={}, number={}, pages ={}, Note={In Developments in Representation Theory, Contemp Math, 673, AMS, Providence, RI, 2016, 51-177}

\bib{Schroll}{book}{title={Brauer Graph Algebras}, Author={S. Schroll}, Publisher={Springer}, Address={Cham}, Date={2018}, Note={In: Assem I., Trepode S. (eds), Homological Methods, Representation Theory, and Cluster Algebras, CRM Short Courses, 177-223}, pages={177-223}}

\bib{Sierra}{article}{title={The dimension of the center of a Brauer configuration algebra}, subtitle={}, Author={A. Sierra},
Author={}, Author={}, Author={}, journal={J. Algebra},
volume={510}, date={2018}, number={}, pages ={289-318}

\bib{Simson}{book}{title={Linear Representations of Partially Ordered Sets and Vector Space Categories}, Author={D. Simson}, Publisher={Gordon and Breach, London}, Address={London}, Date={1992}}

\bib{Stanley}{book}{title={Enumerative Combinatorics},
subtitle={}, Author={R. Stanley}, Author={}, journal={},
publisher={Cambridge University Press}, volume={1}, date={1997},
pages={}, address={Cambridge}

\bib{Zavadskij1}{article}{title={The four subspace problem; An elementary
solution}, subtitle={}, Author={A.G. Zavadskij},
Author={G. Medina}, Author={}, Author={}, journal={Linear Algebra Appl.},
volume={392}, date={2004}, number={}, pages ={11-23}

\bib{Zavadskij2}{article}{title={On the Kronecker problem and related problems of linear algebra}, subtitle={}, Author={A.G. Zavadskij},
Author={}, Author={}, Author={}, journal={Linear Algebra Appl.},
volume={425}, date={2007}, number={}, pages ={26-62}

\bib{OEIS0}{book}{title={On-Line Encyclopedia of Integer Sequences},
subtitle={}, Author={N.J.A. Sloane}, Author={}, journal={},
publisher={The OEIS Foundation}, volume={http://oeis.org/A132262, A110122, A002061, A005586, A024166, A100705, A052558, A052591},
date={}, pages={}, address={}

\end{biblist}
\end{bibdiv}

Agust\'{\i}n Moreno Ca\~{n}adas\hspace{30mm}Pedro Fernando Fern\'andez Espinosa\\
Department of Mathematics\hspace{26mm}Department of Mathematics\\
Universidad Nacional de Colombia\hspace{17mm}Universidad Nacional de Colombia.\\
Kra 30 No 45-03\\
ZIP Code 11001000\\

\par\bigskip

Isa\'ias David Mar\'in Gaviria\hspace{27mm}Gabriel Bravo R{i}os\\
Department of Mathematics\hspace{26mm}Department of Mathematics\\
Universidad Nacional de Colombia\hspace{17mm}Universidad Nacional de Colombia.

\section{Appendix}\label{Appendix}

In this section, we present the set of helices\par\smallskip
\begin{centering}
$(4_{P}, 2_{P}, P_{A}=\{p_{3,2},p_{1,3},p_{2,5}\}, P_{B}=\{p_{4,1},p_{1,4}, p_{3,6}\})$\par\smallskip
\end{centering}

associated to a matrix $P$ of type $\mathscr{H}_{3}$ and defined by the word $W_{P}=BAABAB$. The corresponding copies (see Theorem \ref{invariant11}) in \par\smallskip

\begin{centering}$(4_{P}, 1_{P}, P_{A}=\{p_{2, 1}, p_{1, 3}, p_{3, 6}\}, P_{B}=\{p_{3,2}, p_{2, 4}, p_{4, 5}\})$\par\smallskip
\end{centering}

are also shown according with the associated word $ABABBA$.
\addtocounter{equation}{1}
\begin{equation}\label{hx1}
\xymatrix@=30pt{
\underline{p_{4,1}}\ar@[blue][u]&\ar@[blue][l]p_{4,2}&p_{4,3}&p_{4,4}&p_{4,5}&p_{4,6}&i_{A}\\
\end{equation}

\begin{equation}\label{hx2}
\xymatrix@=30pt{
\underline{p_{2,1}}&p_{2,2}&p_{2,3}&\underline{p_{2,4}}\ar@[blue][u]&{p_{2,5}}&p_{2,6}\ar@[blue][ll]&\\
\end{equation}

\begin{equation}\label{hx3}
\xymatrix@=30pt{
\underline{p_{4,1}}\ar@[red][uu]&\ar@[red][l]p_{4,2}&p_{4,3}&p_{4,4}&p_{4,5}&p_{4,6}&i_{A}\\
\end{equation}

\begin{equation}\label{hx4}
\xymatrix@=30pt{
\underline{p_{2,1}}&p_{2,2}\ar@[red][rr]&p_{2,3}&\underline{p_{2,4}}&{p_{2,5}}&p_{2,6}&\\
\end{equation}

\begin{equation}\label{hx5}
\xymatrix@=30pt{
\underline{p_{4,1}}\ar@[green][uu]&\ar@[green][l]p_{4,2}&p_{4,3}&p_{4,4}&p_{4,5}&p_{4,6}&i_{A}\\
\end{equation}

\begin{equation}\label{hx6}
\xymatrix@=30pt{
\underline{p_{2,1}}&p_{2,2}&p_{2,3}\ar@[green][r]&\underline{p_{2,4}}\ar@[green][d]&{p_{2,5}}&p_{2,6}&\\
\end{equation}

\begin{equation}\label{hx7}
\xymatrix@=30pt{
\underline{p_{4,1}}\ar@[black][uuu]&\ar@[black][l]p_{4,2}&p_{4,3}&p_{4,4}&p_{4,5}&p_{4,6}&i_{A}\\
\end{equation}

\begin{equation}\label{hx8}
\xymatrix@=30pt{
\underline{p_{2,1}}\ar@[black][d]&p_{2,2}&p_{2,3}&\underline{p_{2,4}}&{p_{2,5}}\ar@[black][llll]&p_{2,6}&\\
\end{equation}

\end{document}

%---- Last Introduction---------

According to Ringel and Fahr \cite{Fahr2} a categorification of a sequence of
numbers means to consider instead of these numbers suitable objects in a category (for instance, representation of quivers) so that the numbers in question occur as invariants of the objects, equality of numbers may be visualized by isomorphisms of objects functional relations by functorial ties.  The notion of this kind of categorification arose from  the use of suitable arrays of numbers to obtain integer partitions of dimensions of indecomposable preprojective modules over the 3-Kronecker algebra (see Figure (\ref{covering}) where it is shown the 3-Kronecker quiver and a piece of the oriented 3-regular tree or universal covering $(T,E,\Omega_{t})$ as described by Ringel and Fahr in \cite{Fahr1}). Firstly they noted that  the vector dimension of these kind of modules consists of even-index Fibonacci numbers (denoted $f_{i}$ and such that $f_{i}=f_{i-1}+f_{i-2}$, for $i\geq2$, $f_{0}=0$, $f_1=1$) then they used results from the universal covering theory developed by Gabriel and his students to identify such Fibonacci numbers with dimensions of representations of the corresponding universal covering. In particular, preinjective and preprojective representations of the 3-Kronecker quiver were used in \cite{Fahr1} by Ringel and Fahr in order to derive a partition formula for even-index Fibonacci numbers $f_{2n}$.

\begin{center}

\begin{figure}[H]

\begin{tikzpicture}[scale=0.6]
%\draw[step=0.5cm,gray,very thin] (0,0) grid (14,8);

\node[inner sep=0pt] at (9,0.5)(k){The 3-Kronecker quiver and an illustration of its corresponding universal covering.};
\node at (18,4)(d){$(1)$};
\node["1"] at (2,4)(a){$\circ$};
\node["2"] at (5,4)(b){$\circ$};
\node[inner sep=0pt] at (9,6.5)(9){$\bullet$};
\node[inner sep=0pt] at (12,6.5)(10){$\bullet$};
\node[inner sep=0pt] at (8,5.5)(11){$\bullet$};
\node[inner sep=0pt] at (13,5.5)(12){$\bullet$};

\node[inner sep=0pt] at (10,5.5)(3){$\bullet$};

\node[inner sep=0pt] at (11,5.5)(4){$\bullet$};

\node[inner sep=0pt] at (9,4.5)(1){$\bullet$};

\node[inner sep=0pt] at (12,4.5)(2){$\bullet$};

\node[inner sep=0pt] at (9,3.5)(5){$\bullet$};

\node[inner sep=0pt] at (12,3.5)(6){$\bullet$};

\node[inner sep=0pt] at (10,2.5)(7){$\bullet$};

\node[inner sep=0pt] at (11,2.5)(8){$\bullet$};

\node[inner sep=0pt] at (8,2.5)(13){$\bullet$};

\node[inner sep=0pt] at (13,2.5)(14){$\bullet$};

\node[inner sep=0pt] at (9,1.5)(15){$\bullet$};

\node[inner sep=0pt] at (12,1.5)(16){$\bullet$};

\path[->] (b) edge (a);

\path[->](b) edge  [bend left](a);

\path[->](b) edge  [bend right](a);

\path[->] (3) edge (1);

\path[->] (3) edge (4);

\path[->] (3) edge (9);

\path[->] (11) edge (1);

\path[->] (10) edge (4);

\path[->] (2) edge (4);

\path[->] (2) edge (12);

\path[->] (5) edge (1);

\path[->] (2) edge (6);

\path[->] (5) edge (13);

\path[->] (5) edge (7);

\path[->] (14) edge (6);

\path[->] (8) edge (7);
\path[->] (15) edge (7);
\path[->] (8) edge (16);
\path[->] (8) edge (6);
\end{tikzpicture}
\end{figure}\label{covering}

\end{center}

For the sake of clarity we give here a brief insight into the program of Ringel and Fahr.\par\bigskip
First of all note that the road to a categorification of the Fibonacci numbers has several stops some of them dealing with diagonal (lower) arrays of numbers of the form $D=(d_{i, j})$ with $0\leq j\leq i\leq n$, (columns numbered from right to the left, see array $(5)$) for some $n\geq0$ fixed and such that:
\par\bigskip
\addtocounter{equation}{1}
\begin{equation}\label{farray}
\begin{split}
d_{i,i}&=1, \quad\text{for all}\hspace{0.1cm}i\geq0,\\
d_{2, 0}&=2, \\
d_{2k+1,0}&=0,\quad\text{for all}\hspace{0.1cm}k\geq0,\\
d_{i+2k, i-1}&=0, \quad\text{if}\hspace{0.1cm}i\geq 1, \hspace{0.1cm}k\geq0,\\
2d_{i, j}+d_{i, j-2}-d_{i-1, j-1}&=d_{i+1, j-1},\quad i, j\geq2.
\end{split}
\end{equation}
Besides, if $i \geq 4$ then the following identity (hook rule) holds;

\begin{equation}
\begin{split}
\underset{k=0}{\overset{i-2}{\sum}}d_{i+k, i-k}+d_{2i-2, 0}&=d_{2i-1, 1}.
\end{split}
\end{equation}

Note that to each entry $d_{i, i-j}$ it is possible to assign a weight $w_{i, i- j}$ such that:

\[w_{i, i-j}=
\begin{cases}
3.2^{2\lfloor\frac{i-j}{2}\rfloor+a},  & \hspace{0.2cm}\text{if}\hspace{0.2cm}j\hspace{0.2cm}\text{is even},\hspace{0.2cm}i\neq j, \\
0,            &\hspace{0.2cm}\text{if}\hspace{0.2cm}j\hspace{0.2cm}\text{is odd},\hspace{0.2cm}i\neq j, \\
1,\hspace{0.2cm}\text{if}\hspace{0.2cm}i=j=2h\hspace{0.2cm}\text{for some}\hspace{0.1cm}h\geq0.
\end{cases}\]

Where $\lfloor x\rfloor$ is the greatest integer number less than $x$, $a\in\{0,-1\}$, $a=-1$ if $i$ is even, it is 0 otherwise.\par\bigskip

The first stop consists of defining partitions of the even-index Fibonacci numbers in the following form:
\begin{equation}
\begin{split}
f_{2i+2}&=\underset{j=0}{\overset{i}{\sum}}(w_{i,i-j})(d_{i, i-j}),
\end{split}
\end{equation}

to do that, Ringel and Fahr interpreted weights $w_{i, i-j}$ as distances in a 3-regular tree $(T,E)$ (with $T$ a vertex set and $E$ a set of edges) from a fixed point $x_{0}\in T$ to any point $y\in T$. They define sets $T_{r}$ whose points have distance $r$ to $x_{0}$, in such a case $T_{0}=\{x_{0}\}$, $T_{1}$ are the neighbors of $x_{0}$ and so on. A given vertex $y$ is said to be even or odd according to this parity \cite{Fahr1}.  \par\bigskip

Any vertex $y\in T$ yields a suitable reflection $\sigma_{y}$ on
the set of functions $T\rightarrow \mathbb{Z}$ with finite support, denoted $\mathbb{Z}[T]$, and some reflection products denoted
$\Phi_{0}$ and $\Phi_{1}$ according to the parity of $y$ are introduced in \cite{Fahr1}. Then some maps
$a_{t}:\mathbb{N}_{0}\rightarrow \mathbb{Z}\in\mathbb{Z}[T]$ are defined in such a way that if $a_{0}$ is
the characteristic function of $T_{0}$ then\par\bigskip
\begin{centering}

$a_{0}(x)=0$ unless $x=x_{0}$ in which case $a_{0}(x_{0})=1$,\quad and\quad $a_{t}=(\Phi_{0}\Phi_{1})^{t}a_{0}$, for $t\geq0$,\par\bigskip
\end{centering}

with $a_{t}[r]=a_{t}(x)$, for $r\in\mathbb{N}_{0}$ and $x\in T_{r}$, these maps $a_{t}$ give the values $d_{i, j}$ of the array (\ref{farray}). The following table is an example of such array with $n=12$. Rows are giving by the values of $t$, $P_{t}$ is a notation for a 3-Kronecker preprojective module with dimension vector $[f_{2t+2}\hspace{0.2cm}f_{2t}]$  (see \cite{Fahr3}).

\begin{center}

\begin{tikzpicture}[scale=0.78]

%\draw[step=0.5cm,gray,very thin] (-5,0) grid (15,18);
\node at (11,9)(a){$(5)$};

\node at (10,15)(a){$0$};
\node at (10,14)(a){$1$};
\node at (10,13)(a){$2$};
\node at (10,12)(a){$3$};
\node at (10,11)(a){$4$};
\node at (10,10)(a){$5$};
\node at (10,9)(a){$6$};
\node at (10,8)(a){$7$};
\node at (10,7)(a){$8$};
\node at (10,6)(a){$9$};
\node at (10,5)(a){$10$};
\node at (10,4)(a){$11$};
\node at (10,3)(a){$12$};

\node at (10,1)(a){$t$};
%%%%%% 0
\node at (9,15)(a){$f_2$};
\node at (9,14)(a){$f_4$};
\node at (9,13)(a){$f_6$};
\node at (9,12)(a){$f_8$};
\node at (9,11)(a){$f_{10}$};
\node at (9,10)(a){$f_{12}$};
\node at (9,9)(a){$f_{14}$};
\node at (9,8)(a){$f_{16}$};
\node at (9,7)(a){$f_{18}$};
\node at (9,6)(a){$f_{20}$};
\node at (9,5)(a){$f_{22}$};
\node at (9,4)(a){$f_{24}$};
\node at (9,3)(a){$f_{26}$};

\node at (9,1)(a){$f_{2t+2}$};

%%%%%%%%%%%%%% Orbit 1
\node at (8,15)(1){$1$};
\node at (8,13)(2){$2$};
\node at (8,11)(3){$7$};
\node at (8,9)(4){$29$};
\node at (8,7)(5){$130$};
\node at (8,5)(6){$611$};
\node at (8,3)(7){$2965$};
%%%%%%%%% Orbit 2 Rigth to Left
\node at (7,14)(8){$1$};
\node at (7,12)(9){$3$};
\node at (7,10)(10){$12$};
\node at (7,8)(11){$53$};
\node at (7,6)(12){$247$};
\node at (7,4)(13){$1192$};
%%%%%%%%% Orbit 3 Rigth to Left
\node at (6,13)(14){$1$};
\node at (6,11)(15){$4$};
\node at (6,9)(16){$18$};
\node at (6,7)(17){$85$};
\node at (6,5)(18){$414$};
\node at (6,3)(19){$2062$};

%%%%%%%%% Orbit 4 Rigth to Left
\node at (5,12)(20){$1$};
\node at (5,10)(21){$5$};
\node at (5,8)(22){$25$};
\node at (5,6)(23){$126$};
\node at (5,4)(24){$642$};

%%%%%%%%% Orbit 5 Rigth to Left
\node at (4,11)(25){$1$};
\node at (4,9)(26){$6$};
\node at (5,9){\tiny{(2(6)+18)-5}};
\node at (4,7)(27){$33$};
\node at (4,5)(28){$177$};
\node at (4,3)(29){$943$};

%%%%%%%%% Orbit 6 Rigth to Left
\node at (3,10)(30){$1$};
\node at (3,8)(31){$7$};
\node at (3,6)(32){$42$};
\node at (3,4)(33){$239$};

%%%%%%%%% Orbit 7 Rigth to Left
\node at (2,9)(34){$1$};
\node at (2,7)(35){$8$};
\node at (2,5)(36){$52$};
\node at (2,3)(37){$313$};

%%%%%%%%% Orbit 8 Rigth to Left
\node at (1,8)(38){$1$};
\node at (1,6)(39){$9$};
\node at (1,4)(40){$63$};

%%%%%%%%% Orbit 9 Rigth to Left
\node at (0,7)(41){$1$};
\node at (0,5)(42){$10$};
\node at (0,3)(43){$75$};
%%%%%%%%% Orbit 10 Rigth to Left
\node at (-1,6)(44){$1$};
\node at (-1,4)(45){$11$};
%%%%%%%%% Orbit 11 Rigth to Left
\node at (-2,5)(46){$1$};
\node at (-2,3)(47){$12$};
%%%%%%%%% Orbit 12 Rigth to Left
\node at (-3,4)(48){$1$};
%%%%%%%%% Orbit 13 Rigth to Left
\node at (-4,3)(49){$1$};

%%%%%% Last part II
\node at (-5,2)(50){$$};
\node at (-3,2)(51){$$};
\node at (-1,2)(52){$$};
\node at (1,2)(53){$$};
\node at (3,2)(54){$$};
\node at (5,2)(55){$$};
\node at (7,2)(56){$$};

%%%%%% Last part
\node at (-6,1)(57){};
\node at (-4,1)(58){};
\node at (-2,1)(59){};
\node at (0,1)(60){};
\node at (2,1)(61){};
\node at (4,1)(62){};
\node at (6,1)(63){};

%%%% P(i)

%%%%%% 0
\node at (-4,14.5)(a){$P_1$};
\node at (-4,13.5)(a){$P_2$};
\node at (-4,12.5)(a){$P_3$};
\node at (-4,11.5)(a){$P_4$};
\node at (-4,10.5)(a){$P_5$};
\node at (-4,9.5)(a){$P_6$};
\node at (-4,8.5)(a){$P_7$};
\node at (-4,7.5)(a){$P_8$};
\node at (-4,6.5)(a){$P_9$};
\node at (-4,5.5)(a){$P_{10}$};

\path[->] (1) edge (8);
\path[->] (8) edge (2);
\path[->] (2) edge (9);
\path[->] (9) edge (3);
\path[->] (3) edge (10);
\path[->] (10) edge (4);
\path[->] (4) edge (11);
\path[->] (11) edge (5);
\path[->] (5) edge (12);
\path[->] (12) edge (6);
\path[->] (6) edge (13);
\path[->] (13) edge (7);

\path[->] (8) edge (14);
\path[->] (14) edge (9);
\path[->] (9) edge (15);
\path[->] (15) edge (10);
\path[->] (10) edge (16);
\path[->] (16) edge (11);
\path[->] (11) edge (17);
\path[->] (17) edge (12);
\path[->] (12) edge (18);
\path[->] (18) edge (13);
\path[->] (13) edge (19);

\path[->] (14) edge (20);
\path[->] (20) edge (15);
\path[->] (15) edge (21);
\path[->] (21) edge (16);
\path[->] (16) edge (22);
\path[->] (22) edge (17);
\path[->] (17) edge (23);
\path[->] (23) edge (18);
\path[->] (18) edge (24);
\path[->] (24) edge (19);

\path[->] (20) edge (25);
\path[->] (25) edge (21);
\path[->] (21) edge (26);
\path[->] (26) edge (22);
\path[->] (22) edge (27);
\path[->] (27) edge (23);
\path[->] (23) edge (28);
\path[->] (28) edge (24);
\path[->] (24) edge (29);

\path[->] (25) edge (30);
\path[->] (30) edge (26);
\path[->] (26) edge (31);
\path[->] (31) edge (27);
\path[->] (27) edge (32);
\path[->] (32) edge (28);
\path[->] (28) edge (33);
\path[->] (33) edge (29);

\path[->] (30) edge (34);
\path[->] (34) edge (31);
\path[->] (31) edge (35);
\path[->] (35) edge (32);
\path[->] (32) edge (36);
\path[->] (36) edge (33);
\path[->] (33) edge (37);

\path[->] (34) edge (38);
\path[->] (38) edge (35);
\path[->] (35) edge (39);
\path[->] (39) edge (36);
\path[->] (36) edge (40);
\path[->] (40) edge (37);

\path[->] (38) edge (41);
\path[->] (41) edge (39);
\path[->] (39) edge (42);
\path[->] (42) edge (40);
\path[->] (40) edge (43);

\path[->] (41) edge (44);
\path[->] (44) edge (42);
\path[->] (42) edge (45);
\path[->] (45) edge (43);

\path[->] (44) edge (46);
\path[->] (46) edge (45);
\path[->] (45) edge (47);

\path[->] (46) edge (48);
\path[->] (48) edge (47);

\path[->] (48) edge (49);

\draw[line width=2pt] (1) -- (2);
\draw[line width=2pt] (2) -- (3);
\draw[line width=2pt] (3) -- (4);
\draw[line width=2pt] (4) -- (5);
\draw[line width=2pt] (5) -- (6);
\draw[line width=2pt] (6) -- (7);

%________________ Last part

\path[->] (50) edge (57);
\path[->] (51) edge (58);
\path[->] (52) edge (59);
\path[->] (53) edge (60);
\path[->] (54) edge (61);
\path[->] (55) edge (62);
\path[->] (56) edge (63);

\path[-] (7) edge (56);
\path[-] (19) edge (56);
\path[-] (19) edge (55);
\path[-] (29) edge (54);
\path[-] (29) edge (55);
\path[-] (37) edge (53);
\path[-] (37) edge (54);
\path[-] (43) edge (52);
\path[-] (43) edge (53);
\path[-] (47) edge (51);
\path[-] (47) edge (52);
\path[-] (49) edge (50);
\path[-] (49) edge (51);

\draw[dotted] (-4.5,15) -- (7,15);
\draw[dotted] (-4.5,14) -- (6,14);
\draw[dotted] (-4.5,13) -- (5,13);
\draw[dotted] (-4.5,12) -- (4,12);
\draw[dotted] (-4.5,11) -- (3,11);
\draw[dotted] (-4.5,10) -- (2,10);
\draw[dotted] (-4.5,9) -- (1,9);
\draw[dotted] (-4.5,8) -- (0,8);
\draw[dotted] (-4.5,7) -- (-1,7);
\draw[dotted] (-4.5,6) -- (-2,6);
\draw[dotted] (-4.5,5) -- (-3,5);

\node at (8,16)(a){$a_t[0]$};
\node at (7,16)(a){$a_t[1]$};
\node at (6,16)(a){$a_t[2]$};
\node at (5,16)(a){$a_t[3]$};
\node at (4,16)(a){$a_t[4]$};
\node at (3,16)(a){$a_t[5]$};

\node at (2,16)(a){$\cdots$};

\node at (2,0.5)(w){The even-index Fibonacci partition triangle \cite{Fahr3}.};
\label{triangle}
\end{tikzpicture}
\end{center}

For example for $t=3$ and $t=4$, we compute $f_{8}$ and $f_{10}$ as follows:\par\bigskip
\addtocounter{equation}{1}
\begin{equation}
\begin{split}
\end{split}
\label{3}
\end{equation}

sequences $a_{t}[0]=d_{2i,0}$ and $a_{t}[1]=d_{2i+1,1}$ are encoded respectively as A132262 and A110122 in the OEIS (On-Line Encyclopedia of Integer Sequences). Actually, sequence $a_{t}[0]$ had not been registered in the OEIS before the publication of Ringel and Fahr.

\par\bigskip

In a second stop of the trip to a categorification of Fibonacci numbers, Ringel and Fahr generalized the results obtained in \cite{Fahr1}, and proved that the following exact sequences (\ref{categorification1}), (\ref{categorification2}) and filtration (\ref{categorification3}) are categorifications of identities (\ref{categorification4}). Where, for $t\geq1$, $P_{t}(x)$ and $R_{t}(x, y)$ are indecomposable representations of the quiver $Q=(T,E,\Omega^{x}_{t})$ ($\Omega^{x}_{t}$ is a bipartite orientation such that $x$ is a sink in case $t$ is even and a source in case $t$ is odd) for which $s_{t}(x)$ and $R_{t}(x, y)$ denote respectively their corresponding dimension vectors, assuming that for even $t$ the vertex $x$ is a sink, and that for $t$ odd the vertex $x$ is a source. In this setting, the sequences $x_{0}, x_{1},\dots, x_{t}$ and $x_{-1},x_{0},\dots, x_{t},x_{t+1}$ denote suitable paths with $x_{0}$ as a sink and $z_{i}$ being a neighbor of $x_{i}$ different from $x_{i-1}$ and $x_{i+1}$.

\begin{equation}\label{categorification1}
\begin{split}
0&\rightarrow P_{t-1}(y)\rightarrow P_{t}(x)\rightarrow R_{t}(x, y)\rightarrow 0\\
0&\rightarrow P_{t-1}(y')\rightarrow R_{t}(x, y)\rightarrow R_{t-1}(y'',x)\rightarrow 0.
\end{split}
\end{equation}

\begin{equation}\label{categorification2}
\begin{split}
P_{0}(x_{0})&\subset P_{1}(x_{1})\subset\dots\subset P_{t}(x_{t})\hspace{0.1cm}\text{with factors}\\
P_{i}(x_{i})/P_{i-1}(x_{i-1})&=R_{i}(x_{i},x_{i-1}),\quad 1\leq i\leq t.
\end{split}
\end{equation}

\begin{equation}\label{categorification3}
\begin{split}
0&\rightarrow P_{0}(z_{0})\oplus \dots\oplus P_{t}(z_{t})\rightarrow R_{t+1}(x_{t}, x_{t+1})\rightarrow R_{0}(x_{-1},x_{0}).
\end{split}
\end{equation}

\begin{equation}\label{categorification4}
\begin{split}
f_{2t+1}&=1+\underset{i=1}{\overset{t}{\sum}}f_{2i} \hspace{0.2cm}\text{and}\\
\end{split}
\end{equation}

Finally, we also recall that the Auslander-Reiten sequences
\begin{equation}\label{categorification5}
\begin{split}
0&\rightarrow P_{n-1}\rightarrow P^{3}_{n}\rightarrow P_{n+1}\rightarrow 0\hspace{0.2cm}\text{and}\\
0&\rightarrow R_{n-1,\lambda}\rightarrow E(n,\lambda)\rightarrow R_{n+1,\lambda}\rightarrow 0
\end{split}
\end{equation}

where $E(n,\lambda)$ is an indecomposable module having dimension vector $3(\mathrm{dim} R(n,\lambda))$ are categorifications of the identity

\begin{equation}\label{categorification6}
\begin{split}
\end{split}
\end{equation}

In a third stop of the road to a categorification of Fibonacci numbers Ringel and Fahr \cite{Fahr3} named the  array (\ref{farray}) a Fibonacci triangle and stated that its entries (nonzero entries) are categorified by the modules $P_{n}=P_{n}(x)$ (called Fibonacci modules) provided that such entries give the Jordan-H\"older multiplicities of these modules.\par\bigskip

In this work, we follow the ideas of Ringel et al. to categorify some integer sequences but instead of using finite-representation algebras or the 3-Kronecker algebra, we use the 2-Kronecker algebra (or simply the Kronecker algebra) and Brauer configuration algebras (introduced recently by Green and Schroll \cite{Green}) to obtain categorifications of some integer sequences. In particular, we use these settings to define categorifications of the sequences encoded in the OEIS as A052558 and A100705. Such Brauer configuration algebras are defined by configurations of some multisets called polygons.
\par\bigskip
Let us point out more clearly some differences and similarities  between the work of Ringel and Fahr and our approach. Firstly we note that in the scenario of
Ringel and Fahr, Fibonacci numbers (sequence A000045 in the OEIS) are categorified by identifying information arising from the preprojective (preinjective and regular) component of the Auslander-Reiten quiver of the 3-Kronecker quiver with information arising from indecomposable representations of an oriented 3-regular quiver by using the theory of universal covering, whereas in our proposal numbers in the sequences $n!(\frac{((-1)^{n}+2n+3)}{4})$ (A052558 in the OEIS), $n^{3}+(n+1)^{2}$ (A100705 in the OEIS) and other related integer sequences are categorified by identifying information arising from the preprojective components of the Auslander-Reiten quiver of the 2-Kronecker quiver and the category $\mathrm{rep}\hspace{0.1cm}\mathscr{P}$ of $k$-linear representations of four incomparable points with information arising from indecomposable modules over some suitable Brauer configuration algebras. We recall here  that the Kronecker problem is equivalent to the problem of determining the indecomposable representations over a field $k$ of the following quiver $Q$ (2-Kronecker quiver):

\begin{equation}\label{QKronecker}
\underset{0}{\circ}&\ar@/_/[l]_{\alpha}\ar@/^/[l]^{\beta}\underset{1}{\circ}
\end{equation}

whereas to determine the indecomposable representations of four incomparable points (a tetrad) is  a very well known matrix problem named the four subspace problem (FSP). The solution of this problem is essentially equivalent to determine all of the indecomposable representations of the four subspace quiver $F$ with the following form \cite{Gelfand, Nazarova2, Simson, Zavadskij1}:

\begin{equation}\label{F}
\xymatrix@=30pt{
\end{equation}

We will see that some invariants associated to indecomposable projective modules over some suitable Brauer configuration algebras allow categorifications of integer numbers. In fact, since polygons in Brauer configurations are multisets, we will often assume that such polygons consists of words of the form

\begin{equation}\label{word}
\begin{split}
w&=x_{1}^{f_1}x_{2}^{f_2}\dots x^{f_k-1}x_{k}^{f_{k}}
\end{split}
\end{equation}

where for each $i$, $1\leq i\leq k$, $x_{i}$ is an element of the polygon called vertex and $f_{i}$ is the number of times that the vertex $x_{i}$ occurs in the polygon. In particular, if vertices $x_{i}$ in a polygon $V$ of a Brauer configuration are integer numbers then the corresponding word $w$ will be interpreted as a partition of an integer number $n_{V}$ associated to the polygon $V$ where it is assumed that each vertex $x_{i}$ is a part of the partition and $f_{i}$ is the number of times that the part $x_{i}$ occurs in the partition and $n_{V}=\underset{i=1}{\overset{k}{\sum}}f_{i}x_{i}$.\par\bigskip

This paper is distributed as follows: In section 2, we recall main definitions and notation used throughout the document, in particular, in this section we define Brauer configuration algebras, the Kronecker problem and the four subspace problem. In section 3, in order to categorify numbers in the sequence A052558, we prove that numbers in this sequence give the number of some helices associated to preprojective Kronecker modules, besides, it is defined a Brauer configuration algebra whose indecomposable projective modules are in bijective correspondence with preprojective Kronecker modules via the number of summands in the heart of such indecomposable modules. Formulas for the dimension of this type of algebras and corresponding centers are given as well. In section 4, several integer sequences are categorified (the sequence $(n+1)^{2}+n^{3}$, for $n\geq 1$ amongst them), to do that, we define Brauer configuration algebras whose indecomposable projective modules are also in bijective correspondence with preprojective representations of the tetrad via some cycles associated to these indecomposable representations. The dimension of these algebras and corresponding quotients are also obtained in this section. Examples of helices are given in section \ref{Appendix}.


# Federated Learning with Autotuned Communication-Efficient Secure Aggregation

Keith Bonawitz1, Fariborz Salehi 2, Jakub Konečný1, Brendan McMahan1 and Marco
Gruteser1  1Google, {bonawitz, konkey, mcmahan<EMAIL_ADDRESS>2California Institute of Technology<EMAIL_ADDRESS>
(November 2019)

###### Abstract

Federated Learning enables mobile devices to collaboratively learn a shared
inference model while keeping all the training data on a user’s device,
decoupling the ability to do machine learning from the need to store the data
in the cloud. Existing work on federated learning with limited communication
demonstrates how random rotation can enable users’ model updates to be
quantized much more efficiently, reducing the communication cost between users
and the server. Meanwhile, secure aggregation enables the server to learn an
aggregate of at least a threshold number of device’s model contributions
without observing any individual device’s contribution in unaggregated form.
In this paper, we highlight some of the challenges of setting the parameters
for secure aggregation to achieve communication efficiency, especially in the
context of the aggressively quantized inputs enabled by random rotation. We
then develop a recipe for auto-tuning communication-efficient secure
aggregation, based on specific properties of random rotation and secure
aggregation – namely, the predictable distribution of vector entries post-
rotation and the modular wrapping inherent in secure aggregation. We present
both theoretical results and initial experiments.††2Work performed while
interning at Google.

##  I Introduction

It is increasingly the case that systems and applications are depending on
machine learning models, often deep neural networks, in order to power the
features their users require. Training these machine learning models requires
access to data. In many cases, this training data arises naturally in a
distributed fashion, such as on the millions of smartphones with which users
interact daily. In many problem domains, the training data may also be privacy
sensitive. For example, a virtual keyboard application on a smartphone
typically requires one or more machine learning models to power features such
as tap typing, gesture typing, auto-corrections, and so on. The most
applicable training data for such models are the actual interactions of real
users with their virtual keyboards as they live their digital lives. Because
of the potential sensitivity of this training data, there is broad desire for
solutions which systematically preserve privacy, for example by ensuring that
raw training data never needs to leave the users’ devices.

###  I-A Federated Learning with Limited Communication

Federated Learning addresses this need by enabling mobile devices to
collaboratively learn a shared inference model while keeping all the training
data on device, decoupling the ability to do machine learning from the need to
store the data in the cloud. In a federated learning system, each user device
maintains a local set of private training examples generated by on-device
interactions or measurements, while a central server maintains the current
version of the model parameters. For each iteration of model training, the
federated learning server selects a cohort of devices from those available for
training. Each device in the cohort downloads a copy of the current model
parameters from the server, then uses the devices local training examples to
form a model update, i.e. by taking some number of steps of stochastic
gradient descent and computing the difference between the model parameters
received from the server and the model parameters after local training. The
server then aggregates the model updates from all devices into average model
update, which it then adds to the current model parameters to form a new set
of model parameters, ready for then next iteration of training.

In federated learning systems for consumer devices such as smartphones, the
devices are interacting with the server over consumer internet connections.
While these interactions may be scheduled at times when the consumer internet
connections are most reliable and least expensive, e.g. when the device is
connected to a broadband internet service while in the user’s home, it is
still desired to minimize the bandwidth needs as much as possible since these
bandwidth needs would add to those of many other device update and maintenance
processes. A more communication-efficient secure aggregation technique could
also allow training more models or rounds within a given user bandwidth quota.

Much research has explored how to minimize communication costs during
distributed stochastic gradient descent, including in federated learning
scenarios. For example, [1, 2] demonstrate how distributed mean estimation, as
used in federated learning to aggregate model updates from user devices, can
be achieved with limited communication. They describe a scheme in which the
server randomly selects a rotation matrix $R$ for each aggregation round; each
user multiplies their update vector by the random rotation matrix before
quantizing and submitting for aggregation. The server applies the inverse
rotation to the aggregate vector to recover an estimate of the distributed
mean. Suresh et al. [1] show that even aggressive quantization benefits
greatly from pre-processing with a random rotation: for $n$ users, when the
rotated update vector $x^{(u)}$ is quantized to a single bit per dimension, a
mean squared error (MSE) of $\Theta\left(\frac{\log
d}{n}\cdot\frac{1}{n}\sum_{u=1}^{n}||x^{(u)}||^{2}_{2}\right)$ is achieved,
compared to
$\Theta\left(\frac{d}{n}\cdot\frac{1}{n}\sum_{u=1}^{n}||x^{(u)}||^{2}_{2}\right)$
when the same quantization is used without random rotation. Furthermore, the
same MSE is achieved when the random rotation is replaced with a structured
random orthogonal matrix $R=HD$, where $H$ is a Walsh-Hadamard matrix [3] and
$D$ is a random diagonal matrix with i.i.d. Rademacher entries ($\pm 1$ with
equal probability), while achieving $O(d\log d)$ computation in $O(1)$
additional space and with $O(1)$ additional communication (for a seed to a
PRNG that generates the $D$ matrix). We note that logarithmic dependence on
$d$ in the above MSE bound can be replaced with a constant [4], by appropriate
use of Kashin’s representation [5]. However, the technique would not be
compatible with the statistical analysis that follows.

###  I-B Secure Aggregation

In order to further preserve users’ privacy, federated learning systems can
use techniques from trusted computing or secure multiparty computation to
ensure that the server only gets to see the aggregate of user cohorts’ model
updates and learns nothing further about the individual users’ model updates.

Bonawitz et al. demonstrate SecAgg, a practical protocol for secure
aggregation in the federated learning setting, achieving $<2\times$
communication expansion while tolerating up to $\frac{1}{3}$ user devices
dropping out midway through the protocol and while maintaining security
against an adversary with malicious control of up to $\frac{1}{3}$ of the user
devices and full visibility of everything happening on the server [6]. The key
idea in SecAgg is to have each pair of users agree on randomly sampled $0$-sum
pairs of mask vectors of the same lengths as the model updates. Before
submitting their model update to the server, each user adds their half of each
mask-pair that they share with another user; by working in the space of
integers $\bmod~{}k$ and sampling masks uniformly over $[0,k)^{d}$, SecAgg
guarantees that each user’s masked update is indistinguishable from random
value on its own. However, once all the users updates are added together, all
the mask-pairs cancel out and the desired value (the sum of users inputs
$\bmod~{}k$) is recovered exactly. To achieve robustness while maintaining
security, SecAgg uses $k$-of-$n$ threshold secret sharing to support
recovering the pair-wise masks of a limited number of dropped-out users.

Note that model updates are generally real-valued vectors in federated
learning, but SecAgg (and similar cryptographic protocols) require input
vector elements to be integers $\bmod~{}k$. In practice, this is typically
solved by choosing a fixed range of the real numbers, say $[-t,t]$, clipping
each user update $x^{(u)}$ onto this range, then uniformly quantizing the
remaining values using $\kappa$ bins, each of width $\frac{2t}{\kappa-1}$,
such that a real value of $-t$ maps to a quantized value of 0 and a real value
of $+t$ maps to a quantized value of $\kappa-1$. Note that in SecAgg, the same
modulus $k$ applies both to the users’ individual inputs and to the aggregated
vector. As such, choosing the SecAgg modulus to be $k=n\kappa$, where $n$ is
the number of users, ensures that all possible aggregate vectors will be
representable without overflow [6].

##  II Autotuning Communication-Efficient Secure Aggregation

In this Section, we explain why a straightforward combination of SecAgg and
the compression techniques affects the relative efficiency, and propose a
concrete approach which yields better results.

###  II-A Challenges

We first note that the majority of the bandwidth expansion for SecAgg comes
from the choice of $k=n\kappa$. For $n=2^{10}$ users and $\kappa=2^{16}$ (i.e.
16 bit fixed point representation), Bonawitz et al. [6] reports $1.73\times$
bandwidth expansion over just sending the quantized input vector in the clear.
Some of this bandwidth expansion is associated with secret sharing and other
cryptographic aspects of the protocol. However, observe that choosing
$k=n\kappa$ with $n=2^{10}$ means that the SecAgg modulus is 10 bits wider
than $\kappa$; this alone accounts for $\frac{26}{16}=1.625\times$ bandwidth
expansion – the majority of what is reported.

If we consider combining SecAgg with aggressive quantization, e.g. as
described in [1], the relative expansion cost becomes even more pronounced, as
aggressive quantization reduces $\kappa$ but leaves $n$ unchanged. In the
extreme example of single bit quantization, the relative expansion grows to
$11\times$ just to ensure the SecAgg modulus can accommodate the sum111Note
that the absolute communication overhead remains constant; only the relative
overhead increases.

We also observe that quantizing to a fixed point representation requires
selecting the clipping range $[-t,t]$ _a priori_ – it needs to be the same for
each user and thus the server, or an engineer, chooses an appropriate $t$
before the start of a training round. If the clipping range is set smaller
than the dynamic range of the users’ model updates, then individual model
updates may be distorted due to clipping, thereby distorting the computed
aggregate as well. However, as the clipping range increases, one must either
(a) increase the number of quantization bits used, hence driving up the
communication cost, or (b) incur a higher variance estimate of the aggregate
due to coarser effective quantization.

Establishing an explicit clipping range can be challenging for the model
engineer. Many ML engineers have little intuition about the dynamic range of
model updates, in part because that dynamic range can depend on a variety of
factors including the neural network architecture, activation functions,
learning rate, number of passes through the data per model update, and even
vary as training progresses. The dynamic range will typically also vary
between different model variables/layers.

As such, we desire an automated means by which the clipping range can be
selected.

Secure Aggregation can make this more difficult to determine empirically,
because the ML engineer is only able to view the aggregate model update across
all users in the round, after any distortion from clipping has already
occurred on the user devices. While we could gather additional signals from
user devices to facilitate setting the clipping range appropriate, we would
prefer not to do so. SecAgg is generally used in order to protect the privacy
of the users’ input signals; any additional signals would also have to have
their privacy properties reasoned about. For example, if SecAgg is being used
to facilitate differential privacy, then some portion of the privacy budget
would need to be allocated to privacy costs associated with any additional
signals gathered for clipping range tuning.

###  II-B Autotuning Overview

Fortunately, we can take advantage of two unusual properties of SecAgg and
randomized rotation in order to construct a recipe for automated tuning that
requires no additional signals from the user devices. First, modular wrapping
in SecAggallows users to compute values $\bmod~{}k$ instead of clipping them,
which preserves a signal from the tails of the distribution in the sum.
Second, the randomized rotation step produces inputs with a normal
distribution that changes based on the degree to which values “wrap around” in
the modular operation. This allows the server to estimate the original
distribution and adjust the quantization range to minimize such wrapping. With
this precisely tuned quantization, secure aggregation can then operate with
significantly smaller fixed point integer representations and achieve improved
communication efficiency.

We consider these properties and the automated tuning recipe further in the
next subsections.

###  II-C Modular Wrapping in SecAgg

Recall that SecAgg computes sums $\bmod~{}k$. Because $\bmod~{}k$ is an
idempotent operation, and because $\bmod$ and summation commute, we find that
each user can compute their input $\bmod~{}k$ before submitting it to secure
aggregation without affecting the result at all. That is, if $x^{(u)}$ is the
update from user $u$, and $\mathcal{U}$ denote the set of all the users
participating in an execution of the secure aggregation protocol, then
$\textsc{SecAgg}(\\{x^{(u)}\\}_{u\in\mathcal{U}})=\big{(}\sum_{u\in\mathcal{U}}x^{(u)}\big{)}\bmod~{}k=\big{(}\sum_{u\in\mathcal{U}}\left(x^{(u)}\bmod~{}k\right)\big{)}\bmod~{}k=\textsc{SecAgg}\big{(}\\{x^{(u)}\bmod~{}k\\}_{u\in\mathcal{U}}\big{)}$.

This suggests an alternative to the standard approach of clipping to a fixed
range, then quantizing the result. Instead, we’ll consider quantizing first
(over an unbounded range), then applying the $\bmod~{}k$ operation instead of
clipping. When we clip before quantizing, distortion is introduced whenever an
individual user’s contribution exceeds the fixed point range allocated to that
individual. In contrast, by quantizing then applying $\bmod~{}k$, we only
introduce distortion if the _true sum over all users’ inputs
$\sum_{u}x^{(u)}$_ lies outside the fixed point range allocated to the
representation of sum.

###  II-D Randomized Rotation Produces (Almost) Normally Distributed Inputs

When a randomized rotation matrix $R$ is applied to a vector $x$, the entries
of $y=Rx$ have identical distribution with mean $0$ and variance equal to
$||x||^{2}_{2}/d$. It can be shown that as $d$ grows large, the distribution
of each of the entries of the vector $y$ will approach a Gaussian
distribution, i.e., $N(0,||x||^{2}_{2}/d)$. That is, for any input vector $x$,
if we form a histogram of the entries in $y$, we expect to see a normal
distribution222For large values of $d$, it can also be shown that the a vector
$v\in\mathbb{R}^{d}$ with entries drawn independently from the Gaussian
distribution $N(0,\frac{1}{d})$ will concentrate around the unit sphere..

To show this, we first note that a random rotation $R\in\mathbb{R}^{d\times
d}$ is a unitary matrix, with the columns forming an orthonormal basis.
Because random rotation is simply representing the vectors in a new basis, it
follows immediately that the $\ell_{2}$-norm is preserved, i.e.
${||Rx||}_{2}={||x||}_{2}$.

Let $\mathcal{O}_{d}$ denote the set of all unitary rotation matrices over
$\mathbb{R}^{d}$, i.e., $\mathcal{O}_{d}=\\{M\in\mathbb{R}^{d\times
d}:MM^{T}=M^{T}M=I_{d}\\}$. Let $v\in{\mathbb{S}}^{d-1}$ be a vector in the
unit sphere, and choose a random matrix $R$ uniformly from the set
$\mathcal{O}_{d}$. We then observe that $Rv$ has a uniform distribution on the
unit sphere, i.e.,
$Rv\sim\operatorname{{\textsc{Uniform}}}({\mathbb{S}}^{d-1})$. The same
argument gives the following,

$y\sim\operatorname{{\textsc{Uniform}}}({||x||}_{2}\cdot\mathbb{S}^{d-1})~{},$
(1)

where $\mathbb{S}^{d-1}$ denotes the unit sphere in $\mathbb{R}^{d}$. As a
direct consequence of the isoperimetric inequality on the unit sphere [7], we
find that

$\operatorname{\mathbb{P}}\\{|y_{i}|>\tau\\}\leq
2e^{-\frac{d\tau^{2}}{2{||x||}_{2}^{2}}}$ (2)

which implies that the entries of $y$ have a sub-Gaussian distribution.

This applies directly to the randomly rotated model updates $x^{(u)}$ from
each user. However, because summation and matrix multiplication commute, the
entries of the sum of the users’ rotated values will also be (almost) normally
distributed, with $\bar{y}_{k}\sim
N\left(0,\frac{||\bar{x}||^{2}_{2}}{d}\right)$ where $\bar{x}=\sum_{u}x^{(u)}$
and $\bar{y}=\sum_{u}Rx^{(u)}=R\bar{x}$.

Similarly, when we replace the random rotation by the randomized Hadamard
matrix $R=HD$ as in [1], the entries are _approximately_ normal, and
identically but not independently distributed. Nevertheless, for high
dimensional values of interest here, the difference is small and we will see
later that the theoretical insights presented next carry over to practice.

###  II-E Combining Modularity and Random Rotation

We have established that if we randomly rotate each input vector $x^{(u)}$
before aggregating, then we expect the sum $\bar{y}$ to have normally
distributed entries. Observe further that if we randomly rotate $x^{(u)}$ and
then stochastically quantize (without clipping or modular wrapping), we still
expect the entries of the (dequantized) sum to be approximately normally
distributed.

Now consider randomly rotating the $x^{(u)}$, quantizing, then applying the
$\bmod~{}k$ before computing the sum $\bmod~{}k$, as in the SecAgg setting.
After dequantizing the sum, we can no longer expect a normal distribution: the
domain of the tails of the normal distribution correspond to values outside
the range $[-t,t]$ that maps to the valid quantized values $[0,k-1]$. Instead,
we find that the tails of the normal distribution “wrap around,” producing
instead a wrapped normal distribution [8], see Figure 1, with the probability
density function

$\operatorname{{\textsc{WrappedNormal}}}(x;\mu,\sigma)=\\\
\frac{1}{\sigma\sqrt{2\pi}}\sum_{k=-\infty}^{\infty}\exp\left[\frac{-(x-\mu+2\pi
k)^{2}}{2\sigma^{2}}\right]$

where $\mu$ and $\sigma$ are the mean and variance of the unwrapped normal
distribution, and the domain is assumed to be $[-\pi,\pi]$. The range $[-t,t]$
can be obtained by scaling the distribution appropriately.

Figure 1: The pdf of a normal distribution (left) and a corresponding
$\operatorname{{\textsc{WrappedNormal}}}$ distribution (right). Note how the
green and yellow tails of the normal distribution “wrap around” in the
$\operatorname{{\textsc{WrappedNormal}}}$.

###  II-F A Recipe for Autotuning Communication-Efficient SecAgg

Taken together, sections II-C through II-E suggest a concrete recipe for
performing communication-efficient secure aggregation, while autotuning the
quantization strategy, and without requiring any additional signals to be
communicate to the server. Given $\alpha$, the probability that an individual
entry of the rotated sum $\bar{z}$ can be distorted, proceed as follows:

  1. 1.

The server selects a structured pseudorandom rotation matrix $R=HD$ and
communicates it to each user.

  2. 2.

Each user randomly rotates their input $z^{(u)}=Rx^{(u)}$

  3. 3.

Each user quantizes $z^{(u)}$ (over an unbounded range) with the current
quantization bin size $b$, then applies the $\bmod~{}k$ operation to produce
the user’s SecAgg input $y^{(u)}$

  4. 4.

The SecAgg protocol is run to produce $\bar{y}=\sum_{u}y^{(u)}\bmod~{}k$.

  5. 5.

The server computes a histogram of the dequantized entries of $\bar{y}$ and
fits a $\operatorname{{\textsc{WrappedNormal}}}(0,\sigma,t)$ distribution of
unknown variance $\sigma^{2}$ to the result. From this, the server infers that
$\bar{z}=\sum_{u}z^{(u)}$, the sum of the users’ contributions as if we hadn’t
used quantization or modular wrapping in our aggregation, is distributed as
$\bar{z}_{i}\sim N(0,\sigma)$.

  6. 6.

The server uses the inverse cdf for $N(0,\sigma)$ to set $t$ such that
$\operatorname{\mathbb{P}}(\bar{z}_{k}\not\in[-t,t])\leq\alpha$ for some
constant $\alpha$. Recall that, $\alpha$ is the probability that an individual
entry of the rotated sum $\bar{z}$ is distorted due to modular wrapping,
$(1-\alpha)^{d}$ is the probability that no entry in $\bar{z}$ is distorted,
and $\alpha d$ is the expected number of distorted entries.

  7. 7.

The server compute the new quantization bin size $b^{*}=\frac{2t}{k-1}$, such
that the range $[-t,t]$ maps to the full set of quantized output values
$[0,k-1]$.

  8. 8.

The next iteration of federated learning repeats this recipe using the new bin
size $b^{*}$.

###  II-G Fitting a Wrapped Normal Distribution

In order to implement the recipe above, we still require a practical way to
fit the wrapped normal distribution to the observed dequantized entries of
$\bar{y}$.

Following [8], we observe that a (biased) estimator of $\sigma^{2}$ for
$\bar{y}\sim\operatorname{{\textsc{WrappedNormal}}}(0,\sigma)$ can be formed
by computing

$\bar{R}^{2}=\left(\frac{1}{d}\sum_{i=1}^{d}\cos\bar{y}_{i}\right)^{2}+\left(\frac{1}{d}\sum_{i=1}^{d}\sin\bar{y}_{i}\right)^{2}~{},$
$R_{e}^{2}=\frac{d}{d-1}\left(\bar{R}^{2}-\frac{1}{d}\right)~{},$
$\hat{\sigma}^{2}=\ln\left(\frac{1}{R_{e}^{2}}\right)~{}.$

##  III Experiments

Following the recipe outlined in section II-F and using the Federated
Averaging algorithm for federated learning [9], we conducted experiments on
the CIFAR-10 dataset [10]. CIFAR-10 consists of 50000 training images + 10000
test images, each 32x32 color pixels, balanced across 10 classes (e.g.
airplane, automobile, etc.). We used a version of the all-convolutional neural
architecture in [11], the same as used previously for such experiment [2]. We
simulated 100 devices for federated learning with a balanced i.i.d. partition
of the training data across devices. In each round of federated learning, we
selected $10\%$ of the devices to participate. To compute a device’s model
update, we used a batch size of 10 training examples and made a single pass
through the device’s data with a learning rate of 0.1. We fixed the SecAgg
modulus for the entries of the sum to $k=2^{8}$, i.e. 8 bit fixed point
quantization.

Figure 2: Evaluation accuracy for CIFAR-10 experiments, considering various
values of $\alpha$. The legend also lists the equivalent $\frac{\sigma}{t}$
ratio for each $\alpha$. Figure 3: Evaluation accuracy for CIFAR-10
experiments. In this range of $\alpha$ values, one can see that being too
conservative in the $\alpha$ setting (i.e. driving the probability of modular
wrapping towards 0) causes a loss in accuracy, due to overly coarse
quantization bins.

Figures 2 and 3 show the results of the experiments, using various values of
$\alpha$ for the autotuning recipe. Note that in Figure 3, one can see that
being too conservative in the $\alpha$ setting (i.e. driving the probability
of modular wrapping towards 0) causes a loss in accuracy, due to overly coarse
quantization bins.

##  IV Discussion

In this paper, we derived and tested a recipe for federated learning with
autotuned communication-efficient secure aggregation, with initial results on
CIFAR-10 showing promising potential.

In future experiments, we hope to explore the behavior of the autotuning
system on more complex neural networks and further explore the trade off
between the number of bits in the SecAgg modulus, the setting of $\alpha$, and
the achievable machine learning accuracy. In addition, while we believe it to
be easier to reason about $\alpha$ than to accurately guess the dynamic range
of the model updates, we also hope to develop a better theoretical
understanding of the impact of $\alpha$ on the convergence of the training
algorithm.

## References

  * Suresh et al. [2017] A. T. Suresh, F. X. Yu, H. B. McMahan, and S. Kumar, “Distributed mean estimation with limited communication,” in _International Conference on Machine Learning_ , 2017.
  * Konečný et al. [2016] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” _arXiv preprint arXiv:1610.05492_ , 2016.
  * Horadam [2012] K. J. Horadam, _Hadamard matrices and their applications_. Princeton university press, 2012.
  * Caldas et al. [2018] S. Caldas, J. Konečný, H. B. McMahan, and A. Talwalkar, “Expanding the reach of federated learning by reducing client resource requirements,” _arXiv preprint arXiv:1812.07210_ , 2018.
  * Lyubarskii and Vershynin [2010] Y. Lyubarskii and R. Vershynin, “Uncertainty principles and vector quantization,” _IEEE Transactions on Information Theory_ , vol. 56, no. 7, pp. 3491–3501, 2010.
  * Bonawitz et al. [2017] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_. ACM, 2017, pp. 1175–1191.
  * Vershynin [2018] R. Vershynin, _High-dimensional probability: An introduction with applications in data science_. Cambridge University Press, 2018, vol. 47.
  * Mardia and Jupp [2009] K. V. Mardia and P. E. Jupp, _Directional statistics_. John Wiley & Sons, 2009, vol. 494.
  * McMahan et al. [2017] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial Intelligence and Statistics_ , 2017, pp. 1273–1282.
  * Krizhevsky [2009] A. Krizhevsky, “Learning multiple layers of features from tiny images,” Tech. Rep., 2009.
  * Springenberg et al. [2015] J. Springenberg, A. Dosovitskiy, T. Brox, and M. Riedmiller, “Striving for simplicity: The all convolutional net. in arxiv: cs,” _arXiv preprint arXiv:1412.6806_ , 2015.