In this paper we develop a framework to study observability for uniform hypergraphs. Hypergraphs are generalizations of graphs in which edges may connect any number of nodes, thereby representing multi-way relationships which are ubiquitous in many real-world networks including neuroscience, social networks, and bioinformatics. We define a canonical multilinear dynamical system with linear outputs on uniform hypergraphs which captures such multi-way interactions and results in a homogeneous polynomial system. We derive a Kalman-rank-like condition for assessing the local weak observability of this resulting system and propose techniques for its efficient computation. We also propose a greedy heuristic to determine the minimum set of observable nodes, and demonstrate our approach numerically on different hypergraph topologies, and hypergraphs derived from an experimental biological dataset.

§ INTRODUCTION

In this paper, we develop a framework for studying observability of complex networks represented as hypergraphs. Complex  networks arise in various disciplines, e.g.,  in sociology, biology, cyber-security, telecommunications, and physical infrastructure [1, 2, 3]. Networks are often represented as graphs, which while simple and to some degree universal, are limited to representing only pairwise relationships between network entities. However, real-world phenomena can be rich in multi-way relationships. Examples include computer networks where the dynamic relations are defined by packets exchanged over time between computers, co-authorship networks where relations are articles written by two or more authors, brain activity where multiple regions can be highly active at the same time, film actor networks, and protein-protein interaction networks [4, 5, 6, 7]. A hypergraph is a generalization of a graph in which its hyperedges can join any number of vertices [8]. Thus, hypergraphs can capture multi-way relationships unambiguously, and are a natural representation of a broad range of systems mentioned above. An expanding body of research attests to the increased utility of hypergraph-based analyses, see [4] for a recent review. As tensors provide a natural framework to represent multi-dimensional patterns and capture higher-order interactions [9], they are finding an  increasing role in context of hypergraphs, e.g., see [10, 11, 12].

Observability is a property of a dynamical system that determines if it is possible to reconstruct the temporal evolution of the internal states of a system from a given set of outputs/measurements. In the context of network systems, two key objectives related to observability are to determine: i) if a given set of sensor nodes is sufficient to render the full network observable; and ii) the  minimum set of nodes (MON) among different possible combinations that lead to the most accurate estimation of the network state. Observability for network systems has been extensively studied, see [13] for a recent review and references therein. Network observability has been studied from different perspectives: structural observability which involves determining yes/no observability question based on, for example, the Kalman rank condition; dynamic observability which involves using matrix properties, e.g. singular values, determinant, trace, associated with either the observability matrix [14] or the observability gramian [15]; and topological observability in which the focus is on exploring relationship between observability and graph topology/properties [16, 17]. While hypergraphs are finding increasing use in representing complex networks as mentioned above, the problem of analyzing observability for hypergraphs remains unexplored.

Following the framework introduced in  [10] to study controllability of hypergraphs, we define a canonical multilinear or tensor dynamical system with linear outputs on uniform hypergraphs. By uniform hypergraph we mean a hypergraph in which all hyperedges have same size. We use the notion of local weak observability as it lends to a simple algebraic test involving generic rank computation of an associated nonlinear observability matrix. We derive the nonlinear observability matrix for the hypergraph dynamics and devise a recursive technique for its efficient computation.  We also propose a greedy heuristic to determine MON, and demonstrate our approach numerically on different uniform hypergraph topologies and hypergraphs derived from an experimental mouse endomicroscopy dataset.

§ PRELIMINARIES

Let $\Z = \{0,1, 2,\cdots\}$ be the set of whole numbers, $\Z^+=\Z\setminus\{0\}$ the set of positive integers, $\R$ the set of real numbers and $\C$ be set of complex numbers. Let $\Id_{n\times n}$
denote the identity matrix of order $n$. For any pair of vectors $\xv\in \R^n$ and $\yv \in \R^m$ their Kronecker product $\wv\in\R^{nm}$  is defined as

\begin{eqnarray*}\label{eq:kron}
\wv&=&\xv\otimes\yv\\
&=&(x_1y_1,\cdots, x_1y_m, \cdots , x_ny_1,\cdots , x_ny_m)^\tra,
\end{eqnarray*}

where, $\tra$ denotes vector/matrix transpose. Similarly, the Kronecker product of  $\Av\in\R^{m\times n}$ and $\mathbf{B}\in\R^{p\times q}$ is given by,

\begin{equation}\label{eq:kronM}
\Cv=\Av\otimes\Bv=\left(
\begin{array}{ccc}
a_{11}\Bv & \cdots & a_{1n}\Bv \\
\vdots & \ddots & \vdots \\
a_{m1}\Bv & \cdots & a_{mn}\Bv \\
\end{array}
\right),
\end{equation}

where, $\mathbf{C}\in \R^{mp\times nq}$. Furthermore,  the mixed product property implies that [18],

\begin{equation}\label{eq:kronprod}
\end{equation}

The Kronecker power is a convenient notation to express all possible products of elements of a vector up to a given order, and it is denoted by,

\begin{equation}\label{eq:powx}
\xv^{[i]}=\underbrace{\xv\otimes\xv\cdots\otimes\xv}_{i-\textsf{times}}.
\end{equation}

Moreover, $\mbox{dim} \xv^{[i]}= n^i$,  and each component of $\xv^{[i]}$ is of the form $x_1^{\omega_1}x^{\omega_2}\cdots x_n^{\omega_n} $ for some multi-index $\mathbf{\omega}\in \Z^n$  of weight $\sum_{j=1}^n\omega_j=i$.

§.§ Lie Derivatives

Let $h: \R^n\rightarrow \R$ be a scalar function, then its gradient is defined as a row vector of partial derivatives,

\begin{equation*}
dh=(\frac{\partial}{\partial x_1}h \cdots \frac{\partial}{\partial x_n}h).
\end{equation*}

This definition can be generalized to gradient of a vector valued function $\hv: \R^n\rightarrow \R^m$ with components $\hv=(h_1,\cdots,h_m)^\prime$,   as

\begin{equation*}
\nabla_{\xv}\hv=\left(\begin{array}{c}
dh_1 \\
\vdots \\
\end{array}\right).
\end{equation*}

Let $\langle \cdot,\cdot \rangle$ be the standard inner product on $\R^n$. Let $\fv: \R^n\rightarrow \R^n$ be a vector field, then Lie derivative of a scalar function $h$ along $\fv$ is defined as

\begin{equation*}
L_{\fv}h=\langle dh,\fv\rangle.
\end{equation*}

One can generalize this to higher order Lie derivatives $L^i_{\fv}h, i\in\Z$ defined recursively as follows,

\begin{equation*}
L^i_{\fv}h=L_{\fv}(L^{i-1}_{\fv}h),\mbox{with } L^0_{\fv}h=h.
\end{equation*}

For vector valued function $\hv$ one can similarly define the Lie derivative as

\begin{equation*}
L_{\fv}h_1 \\
\vdots \\
\end{array}\right)=
\left(\begin{array}{c}
\langle dh_1,\fv\rangle \\
\vdots \\
\langle dh_m,\fv\rangle
\end{array}\right).
\end{equation*}

This definition can be naturally extended to higher order  by applying the definition of higher order Lie derivatives for scalar functions to the components of $\hv$.

§.§ Tensors

A tensor is a multidimensional array [19, 9, 20, 21]. The order of a tensor is the number of its dimensions, and each dimension is called a mode. An $m$-th order real valued tensor will be denoted by $\tT\in \mathbb{R}^{J_1\times J_2\times  \dots \times J_m}$, where $J_k$ is the size of its $k$-th mode. We will denote by $\mathcal{J}=(J_1,J_2,\cdots,J_m)$. It is therefore reasonable to consider scalars $x\in\mathbb{R}$ as zero-order tensors, vectors $\xv\in\mathbb{R}^{n}$ as first-order tensors, and matrices $\mathbf{X}\in\mathbb{R}^{m\times n}$ as second-order tensors. A tensor is called cubical if every mode is the same size, i.e., $\textsf{T}\in \mathbb{R}^{n\times n\times  \dots \times n}$. A cubical tensor $\tT$ is called supersymmetric if $\tT_{j_1j_2\dots j_k}$ is invariant under any permutation of the indices.

The tensor vector multiplication $\tT \times_{p} \textbf{v}$ along mode $p$ for a vector $\textbf{v}\in  \mathbb{R}^{J_p}$ is defined  by

\begin{equation}
(\tT \times_{p} \textbf{v})_{j_1j_2\dots j_{p-1}j_{p+1}\dots j_k}=\sum_{j_p=1}^{J_p}\tT_{j_1j_2\dots j_p\dots j_k}\textbf{v}_{j_p},
\end{equation}

which can be extended to

\begin{equation}\label{eq6}
\begin{split}
\tT\times_1 \textbf{v}_1 \times_2\textbf{v}_2\times_3\textbf{v}_3\dots \times_{k}\textbf{v}_k=\tT\textbf{v}_1\textbf{v}_2\textbf{v}_3\dots\textbf{v}_m\in\mathbb{R}
\end{split}
\end{equation}

for $\textbf{v}_p\in \mathbb{R}^{J_p}$. The expression (<ref>) is also known as the homogeneous polynomial associated with $\tT$. If $\textbf{v}_p=\textbf{v}$ for all $p$, we write  (<ref>)  as $\tT\textbf{v}^{m}$ for simplicity.

Tensor unfolding is considered as a critical operation in tensor computations [19, 9]. In order to unfold a tensor $\tT\in\R^{J_1\times J_2\times\cdots \times J_m}$ into a vector or a matrix, we use an index mapping function $ivec(\cdot,\mathcal{J}):\mathbb{Z}\times \mathbb{Z}\times \stackrel{\scriptscriptstyle m}{\cdots} \times \mathbb{Z} \rightarrow \mathbb{Z}$ as defined in [22], which is given by

\begin{equation*}
ivec(\textbf{j},\mathcal{J}) = j_1+\sum_{k=2}^m(j_k-1)\prod_{l=1}^{k-1}J_l.
\end{equation*}

where, $\textbf{j}=(j_1,j_2,\cdots,j_m)$.

The $k$-mode unfolding of $\tT$ denoted by $\tT_{(k)}$, is a $J_k \times (J_1\cdots J_{k-1}J_{k+1}\cdots J_m)$ matrix, whose $(i,p)$-th entries are given by

\begin{equation*}
\tT_{(k)}(i,p)=\tT_{j_1,\cdots,j_{k-1},i,j_{k},\cdots,j_m},
\end{equation*}

where, $\tilde{\textbf{j}}=(j_1,\cdots, j_{k-1},j_{k+1},\cdots,j_m)$ is such that $p=ivec(\tilde{\textbf{j}},\tilde{\mathcal{J})}$ with $\tilde{\mathcal{J}}=(J_1,\cdots,J_{k-1},J_{k+1}\cdots J_m)$.

§ NONLINEAR OBSERVABILITY CRITERION

For nonlinear systems, notions of controllability and observability were introduced in the seminal work [23]. The notion of observability is based on the indistinguishability of states. In contrast to the linear case there are different nonlinear observability concepts, such as local, weak and global observability [23, 24, 25]. Unfortunately, unlike the linear case where the Kalman rank condition can be used to determine observability, no easy criteria exist for nonlinear systems.

Consider a control system $\Sigma$ affine in the input variables,

\begin{equation}
\Sigma\begin{cases}
\dot{\xv}=\fv(\xv,\uv)=\hv_0(\xv)+\sum_{i=1}^k\hv_i(\xv)u_i\\
\yv=\gv(\xv)
\end{cases}
\end{equation}

where, $\uv=(u_1,\cdots,u_k)^\tra\in \R^k$ denotes the input vector, $\xv\in M\subset \R^n$ is the state vector and $\yv\in\R^m$ is the output/measurement vector. We assume that $\Sigma$ is analytic, i.e., the functions $\hv_i:M\rightarrow M, i=0,\cdots,k$ and $g_i:M\rightarrow \R, i=1,\cdots,m$ where $\gv=(g_1,\cdots,g_m)^\tra$ are assumed to be analytic functions defined on $M$. We also have to assume $\Sigma$ is complete, that is, for every bounded measurable input $\uv(t)$ and every $\xv_0\in M$ there exists a solution $\xv(t)$ of $\Sigma$ such that $\xv(0) = \xv_0$ and $\xv(t)\in M$ for all $t\in \R$. We review different notions of observability from [26] which are equivalent to those introduced in [23], but use a slightly different terminology.

Let $U$ be an open subset of $M$. A pair of points $\xv_0$ and $\xv_1$ in $M$ are called $U$-distinguishable  if there exists a measurable input $\uv(t)$ defined on the interval $[0,T]$ that generates solutions $\xv_0(t)$ and $\xv_1(t)$ of system $\Sigma$ satisfying $\xv_i(0)=\xv_i,i=0,1$ such that $\xv_i(t)\in U$ for $t\in[0,T]$ and $\hv(\xv_0(t))\neq \hv(\xv_1(t))$ for some $t\in [0,T]$. We denote by $I(\xv_0,U)$ all points $\xv_1\in U$ that are not $U$–distinguishable  from $\xv_0$

The system $\Sigma$ is observable at $\xv_0\in M$ if $I(\xv_0,M)=\xv_0$.

The system $\Sigma$ is locally observable at $\xv_0\in M$ if for every open neighbourhood $U$ of $\xv_0$, $I(\xv_0,U)=\xv_0$

Local observability implies observability. On the other hand, since $U$ can be chosen arbitrarily small, local observability implies that we can distinguish between neighboring points instantaneously. Both the definitions above ensure that a point $\xv_0\in M$   can be distinguished from every other point in $M$. For practical purposes though, it is often enough to be able to distinguish between neighbours in $M$, which leads to the following two analogous concepts.

The system $\Sigma$ is weakly observable at $\xv_0\in M$ if $\xv_0$ has an open neighbourhood $U$ s.t. $I(\xv_0,M)\bigcap U=\xv_0$.

The system $\Sigma$ is locally weakly observable at $\xv_0\in M$ if $\xv_0$ has an open neighbourhood $U$ s.t. for every open neighbourhood $V$ of $\xv_0$ contained in $U$, $I(\xv_0,V)=\xv_0$.

Clearly, local observability implies local weak observability as we can set $U=M$. The local weakly observability lends itself to a simple algebraic test.  Let $\h$ be the observation space,

\begin{eqnarray}
\h&=&\{L_{\hv_{i_1}}L_{\hv_{i_2}}\cdots L_{\hv_{i_r}}(g_{i}): r\geq 0, i_j=0,\cdots,k,\notag\\
&&i=1,\cdots,m\}, \label{eq:defG}
\end{eqnarray}

\begin{equation}\label{eq:defdG}
d\h=\mbox{span}_{\R_x}\{d\phi:\phi \in \h\},
\end{equation}

be the space spanned by the gradients of the elements of $\h$, where $\R_x$ is space of meromorphic functions on $M$. The following result was proved in [23], see Theorems $3.1$ and $3.11$.

The analytic system $\Sigma$ is locally weakly observable for all $\xv$ in an open dense set of $M$ if and only if $dim_{\R_x}(d\h) = n$.

Here $dim_{\R_x}(d\h)$ is the generic or maximal rank of $d\h$, that is, $dim_{\R_x}(d\h)= \max_{\xv\in M}(dim_{\R} d\h(\xv))$.

For system $\Sigma$ with no control inputs, i.e. $\hv_i\equiv0,i=1,\cdots,k$ the condition for local weak observability simplifies to checking,

\begin{equation}\label{eq:obsr}
\mbox{rank}(\mathcal{O}(\xv))=n,
\end{equation}

where, $\mathcal{O}(\xv)$ is the nonlinear observability matrix (NOM),

\begin{equation}\label{eq:obsrmat}
\mathcal{O}(\xv)=\nabla_{\xv}\begin{pmatrix}
\vdots\\
\end{pmatrix},
\end{equation}

for some $r\in \Z$. One can use symbolic computation to check the generic rank condition (<ref>), for example see the Sedoglavic's algorithm in [27].

In general the value of $r$  to use in (<ref>) is not known apriori. For analytic system $\Sigma$, $r$ can be set to the state dimension $n$, see Theorem $4.1$ in [26].

For a polynomial system $\Sigma$, i.e., when $\fv$ and $\gv$ are polynomials, observability has also been studied from the perspective of algebraic geometry, see [25] and references therein.

Unless otherwise stated we will use the local weak observability as the notion of nonlinear observability in this paper.

§ UNIFORM HYPERGRAPHS

Let $\Vs$ be a finite set. A undirected hypergraph $\g$ is a pair $(\Vs,\Es)$ where $\Es\subseteq \mathcal{P}(\Vs)\setminus \{\emptyset\}$, the power set of $\Vs$. The elements of $\Vs$ are called the nodes, and the elements of $\Es$ are called the hyperedges. We note that in this definition of hypergraph we do not allow for repeated nodes within an hyperedge (often called hyperloops).  The degree $d(v)$ of a node $v\in\Vs$ is $d(v)=|\{e\in \Es|v\in e\}|$, where $|\cdot|$ denotes set cardinality. The degree of an hyperedge $e$ is denoted by $d(e) = |e|$. For $k$-uniform hypergraphs, the degree of each hyperedge is the same, i.e. $d(e) = k$.

Let $\g= (\Vs,\Es)$ be a $k$-uniform hypergraph with $n=|\Vs|$ nodes. The adjacency tensor $\tA\in\mathbb{R}^{n\times n\times \dots\times n}$ of $\g$, which is a $k$-th order $n$-dimensional supersymmetric tensor, is defined as

\begin{equation}\label{eq:98}
\tA_{j_1j_2\dots j_k} = \begin{cases} \frac{1}{(k-1)!} \text{ if $(j_1,j_2,\dots,j_k)\in \Es$}\\ \\0, \text{ otherwise}\end{cases}.
\end{equation}

Similarly to standard graphs, the degree of vertex $j$ of a uniform hypergraph is defined as

\begin{equation}\label{eq:r6}
d_j=\sum_{j_2=1}^n\sum_{j_3=1}^n\dots \sum_{j_k=1}^n\tA_{jj_2j_3\dots j_k}.
\end{equation}

Note that the choice of the nonzero coefficient $\frac{1}{(k-1)!}$ in (<ref>) guarantees that the degree of each node is equal to the number of hyperedges that contain that node, which is consistent with the notion of degree in standard graphs. The degree distribution of a hypergraph is the distribution of the degrees over all nodes. If all nodes have the same degree $d$, then $\g$ is called $d$-regular.  We recall definitions of uniform hypergraph chain, ring, star and complete hypergraphs following [10].

A $k$-uniform hyperchain is a sequence of $n$ nodes such that every $k$ consecutive nodes are adjacent, i.e., nodes $j,j+1,\dots,j+k-1$ are contained in one hyperedge for $j=1,2,\dots,n-k+1$.

A $k$-uniform hyperring is a sequence of $n$ nodes such that every $k$ consecutive nodes are adjacent, i.e., nodes $\sigma_n(j),\sigma_n(j+1),\dots,\sigma_n(j+k-1)$ are contained in one hyperedge for $j=1,2,\dots,n$, where $\sigma_n(j)=j$ for $j\leq n$ and $\sigma_n(j)=j-n$ for $j>n$.

A $k$-uniform hyperstar is a collection of $k-1$ internal nodes that are contained in all the hyperedges, and $n-k+1$ leaf nodes such that every leaf node is contained in one hyperedge with the internal nodes.

A $k-$uniform complete hypergraph is a set of $n$ vertices with all $\binom{n}{k}$ possible subsets as hyperedges.

In $k$-uniform hyperchains, hyperrings and hyperstars, every two hyperedges have exactly $k-1$ overlapping nodes, see Fig. <ref> in Section <ref>. When $k=2$, they are reduced to standard chains, rings and stars.

§ OBSERVABILITY COMPUTATION FOR UNIFORM HYPERGRAPHS

§.§ Uniform Hypergraph Dynamics with Outputs

Following [10] we represent the dynamics of a uniform hypergraph by multilinear time-invariant differential equations with outputs as follows.

Given a $k$-uniform undirected hypergraph $\g$ with $n$ nodes, the dynamics of $\g$ with outputs $\yv\in \R^m$ is defined as

\begin{eqnarray}
\dot{\xv}&=&\fv(\xv)=\tA\xv^{k-1},\label{eq:hypdyn1}\\
\yv&=&\gv(\xv)=\Cv\xv,\label{eq:hypdyn2}
\end{eqnarray}

where, $\tA\in\mathbb{R}^{n\times n\times \dots \times n}$ is the adjacency tensor of $\g$, and $\Cv\in\mathbb{R}^{m\times n}$ is the output matrix.

See Fig. <ref> for an example of uniform hypergraph and associated dynamics. All the interactions are characterized using multiplications instead of the additions that are typically used in a standard graph based representation as also shown in the Fig. <ref>. For detailed discussion on relationship between graph vs. hypergraph dynamic representation, see [10].

Note that hypergraph dynamics (<ref>-<ref>) can be represented in Kronecker form as:

\begin{eqnarray}
\dot{\xv}&=&\Av\xv^{[k-1]},\label{eq:hypdynkron1}\\
\yv&=&\Cv\xv,\label{eq:hypdynkron2}
\end{eqnarray}

where, $\Av=\tA_{(k)}\in \R^{n\times n^{k-1}}$ is any $k$-th mode unfolding of $\tA$. Since $\tA$ is a super-symmetric tensor, all $k$-th mode unfoldings give rise to the same matrix $\Av$.

Furthermore, $\fv$ and $\gv$ are homogeneous polynomials and hence analytic functions. Thus, one can in principle use Sedoglavic's algorithm [27] for rank computation of NOM associated with above system as discussed in Section <ref>. Alternatively, algebraic geometric techniques for polynomial systems can also be used as indicated in the Remark <ref>. These approaches while general purpose tend to be computationally expensive. Moreover, the topological nonlinear observability analysis developed in [16] for polynomial dynamics arising in directed metabolic reaction networks is not applicable in our case as we are dealing with undirected hypergraphs.  We develop a specialized framework exploiting structure of hypergraph dynamics introduced above for potentially more efficient observability computation.

[scale=0.91, transform shape]
[vertex,text=white,scale=0.7] (v1) 1;
[vertex,above right = 11pt and 1.5pt of v1,text=white,scale=0.7] (v2) 2;
[vertex,below right = 11pt and 1.5pt of v2,text=white,scale=0.7] (v3) 3;

[vertex,below right = 3pt and 40pt of v2,white,scale=0.5] (v7);
[vertex,below right = 3pt and 6pt of v2,white,scale=0.5] (v8);
[vertex,below right = -9pt and 12pt of v2,white,scale=0.7,text=black] (v9)  $\dot{\textbf{x}}$=$\textbf{A}\textbf{x}$;
[rectangle,below right = -20pt and 40pt of v2,white,scale=0.7,text=black] (v6)
\begin{cases}
\dot{x}_1 = x_2+x_3\\
\dot{x}_2 = x_1 + x_3\\
\dot{x}_3 = x_1 + x_2
\end{cases}
[vertex,above of=v2,node distance=20pt,white,text=black,scale=0.7] (text1) A;
[->,shorten >=1pt,shorten <=1pt, thick](v8) edge node[left]  (v7);

[vertex,right of=v3,node distance=120pt,text=white,scale=0.7](w1) 1;
[vertex,above right = 11pt and 1.5pt of w1,text=white,scale=0.7] (w2) 2;
[vertex,below right = 11pt and 1.5pt of w2,text=white,scale=0.7] (w3) 3;
[vertex,below right = 3pt and 40pt of w2,white,scale=0.5] (w7);
[vertex,below right = 3pt and 6pt of w2,white,scale=0.5] (w8);
[vertex,below right = -10pt and 12pt of w2,white,scale=0.7,text=black] (w9)  $\dot{\textbf{x}}$=$\textsf{A}\textbf{x}^{2}$;

[rectangle,below right = -20pt and 40pt of w2,white,scale=0.7,text=black] (w6)
\begin{cases}
\dot{x}_1 = x_2x_3\\
\dot{x}_2 = x_1x_3\\
\dot{x}_3 = x_1x_2
\end{cases}
[vertex,above of=w2,node distance=20pt,white,text=black,scale=0.7] (text1) B;

[->,shorten >=1pt,shorten <=1pt, thick](w8) edge node[left]  (w7);

[edge,color=orange,line width=8pt] (v1) – (v2);
[edge,color=red,line width=8pt] (v2) – (v3);
[edge,color=green,line width=8pt] (v3) – (v1);

[edge,color=orange,line width=8pt] (w1) – (w2) – (w3) – (w1);

Graphs versus uniform hypergraphs. (A) Standard graph with three nodes and edges $e_1=\{1,2\}$, $e_2=\{2,3\}$ and $e_3=\{1,3\}$, and its corresponding linear dynamics. (B) 3-uniform hypergraph with three nodes and a hyperedge $e_1=\{1,2,3\}$, and its corresponding nonlinear dynamics.

§.§ Observability Criterion

To determine the NOM (<ref>) for the system (<ref>- <ref>), we compute
the Lie derivatives,

\begin{eqnarray*}
L_{\fv}^0\gv(\xv) & =& \Cv\xv,\\
L_{\fv}^1\gv(\xv) & = & \frac{d}{dt}\Cv\xv=\Cv\Av\xv^{[k-1]},\\
L_{\fv}^2\gv(\xv) & = & \frac{d}{dt}\Cv\Av\xv^{[k-1]}\\
& = & \Cv\Av\frac{d}{dt}\bigg(\overbrace{\xv\otimes \xv\dots\otimes\xv}^{\text{$k-1$ times}}\bigg)\\
& = & \Cv\Av\bigg(\dot{\xv}\otimes\dots\otimes \xv+\cdots+\xv\otimes\dots\otimes\dot{\xv}\bigg)\\ %\xv\otimes\dot{\xv}\otimes\dots\otimes \xv
& = & \Cv\Av\bigg(\sum \xv\otimes\dots\otimes \Av\xv^{[k-1]}\otimes\dots\otimes \xv\bigg)\\
& = & \Cv\Av\bigg[\bigg(\sum \Id\otimes\dots\otimes \Av\otimes\dots\otimes \Id\bigg) \xv^{2k-3}\bigg]\\
& = & \Cv\Av\Bv_2 \xv^{2k-3},\\
& \vdots &\\
L_{\fv}^n\gv(\xv) & = & \Cv\Av\Bv_2\dots \Bv_n \xv^{[nk-(2n-1)]} \quad \forall n>2,
\end{eqnarray*}

where, we have used the identity (<ref>), and $\Bv_p$ is given by,

\begin{equation}\label{eq:B}
\Bv_p=\sum_{i=1}^{(p-1)k-(2p-3)} \overbrace{\Id\otimes\dots\otimes \underbrace{\Av}_{i\text{-th pos.}}\otimes\dots\otimes \Id}^{(p-1)k-(2p-3) \text{times}},
\end{equation}

for $p=2,\cdots,n$. The NOM may then be written as

\begin{equation}\label{eq:hgobsv}
\mathcal{O}(\xv)=\nabla_{\xv}\begin{pmatrix}
\Cv\xv\\
\Cv\Av\xv^{[k-1]}\\
\Cv\Av\Bv_2\xv^{[2k-3]}\\
\vdots\\
\Cv\Av\Bv_2\dots \Bv_n \xv^{[nk-(2n-1)]}
\end{pmatrix},
\end{equation}

where, we have used $r=n$ as per Remark <ref>.

For the case $k=2$, the hypergraph reduces to a graph with adjacency matrix $\textsf{A}$. In that case the hypergraph dynamics (<ref>) becomes linear, and $\mathcal{O}$ reduces to the Kalman observability matrix as expected.

§.§ Computational Framework

First we express NOM  (<ref>) in the form,

\begin{equation}\label{eq:hgobsv1}
\mathcal{O}(\xv)=\nabla_{\xv}\begin{pmatrix}
\Cv\Jv_0(\xv)\\
\Cv\Jv_1(\xv)\\
\Cv\Jv_2(\xv)\\
\vdots\\
\Cv\Jv_n(\xv)
\end{pmatrix},
\end{equation}

where, $\Jv_i(\xv)\in \R^n$ are vectors defined as,

\begin{eqnarray}
\Jv_0(\xv)&=&\xv,\notag\\
\Jv_1(\xv)&=&\Av\xv^{[k-1]},\notag
\end{eqnarray}

\begin{eqnarray}
\Jv_p(\xv)&=&\Av\Bv_2\dots \Bv_p \xv^{[pk-(2p-1)]},\label{eq:J}
\end{eqnarray}

for $p=2,\cdots,n-1$. While expression (<ref>) is a compact representation of NOM, computationally it is more efficient to calculate $\Bv_p\xv^{[pk-(2p-1)]}$ directly as,

\begin{eqnarray}\label{eq:mixedProduct1}
&=&\sum_{i=1}^{(p-1)k-(2p-3)} \overbrace{\xv\otimes\dots\otimes \underbrace{\Av\xv^{[k-1]}}_{i\text{-th vpos.}}\otimes\dots\otimes \xv}^{(p-1)k-(2p-3) \text{times}}
\end{eqnarray}

rather than first explicitly constructing $\Bv_p$ using the Eqn. (<ref>). This idea can be further extended to compute products $\Bv_2\cdots \Bv_p\xv^{[pk-(2p-1)]}$ appearing in $\Jv_p(\xv)$ recursively, as discussed below.

From Eqn. <ref>, define sets $S_1,\dots, S_{(p-1)k-(2p-3)}$ such that

\begin{equation}
S_i=\bigg\{{\xv,\dots, \underbrace{\Av \xv^{[k-1]}}_{i\text{-th pos.}},\dots, \xv}^{}\bigg\},
\end{equation}

where $|S_i|=(p-1)k-(2p-3).$ Given all sets $S_i,$ the calculation of $\Bv_{p-1}\Bv_p\xv^{[pk-(2p-1)]}$ follows a similar procedure to Eqn. <ref> to obtain the result that $\Bv_{p-1}\Bv_p\xv^{[pk-(2p-1)]}$ may be written as

\begin{multline}\label{eq: recursive mixed product}
\sum_{i=1}^{\substack{(p-2)k\\-(2p-5)}}\ \sum_{j=1}^{\substack{(p-1)k\\-(2p-3)}}\bigg(S_{j,1}\otimes\dots
\otimes\underbrace{\Av\big(S_{j,i}
\otimes\dots\otimes S_{j,i+k-2}\big)}_{i\text{-th pos.}}\\
\otimes\dots\otimes S_{j,(p-1)k-(2p-3)}\bigg),
\end{multline}

where there are $(p-2)k-(2p-5)$ vectors in $\R^n$ that are Kronecker product within each calculation of the inner sum. These $(p-2)k-(2p-5)$ vectors form elements in the recursively calculated sets $S_i$. Algorithm <ref> performs the recursive calculation of $\Jv_p(\xv).$

A recursive algorithm for computing $\mathbf{J_p(x)}$

[1]
RecursiveJp($\Av,\ p,\ k, S_j)$
$\Jv_p(\xv)=\Av\big(S_{j,1}\otimes\dots\otimes S_{j,(k-1)}\big)$
return: $\Jv_p(\xv)$
$S_i'=\{S_{j,1},\dots,\overbrace{\Av\big(S_{j,i}\otimes\dots\otimes S_{j,i+k-2}\big)}^{i\text{th pos.}},\dots, S_{j,pk-(2p-1)}\}$

$\Jv_p(\xv) =\Jv_p(\xv)\ +$ RecursiveJp($\Av,\ p-1, k, S_i'$)
return: $\Jv_p(\xv)$

Recursive application of the mixed product property of Kronecker products computes $
\Jv_p(\xv)$ without computing a Kronecker exponentiation larger than $\xv^{[k-1]}.$

Recursive use of the mixed product property in computing $\Jv_p(\xv)$ generates a series of sets $S_i'$ for $i=1,\dots,(p-1)k-(2p-3)$ where every term in the sets is a vector in $\R^n.$ From Eqn. (<ref>), each term in the sets $S_i'$ is taken directly from $S_i$ or through the multiplication of $\Av$ with the Kronecker product of $k-1$ vectors in $S_i$ (Step 9 in Algorithm 1), which requires computing vectors of size at most $n^{k-1}$ with the Kronecker product.

§ MINIMUM OBSERVABLE NODE SELECTION

Finding the minimum set of observable nodes (MON) is a combinatorial optimization problem, and is in general intractable using brute-force search. We provide a greedy heuristic approach for estimating the MON of a uniform hypergraph in which nodes are chosen as measurements based on the maximum change in the rank of $\mathcal{O}_D(\xv)$, see Algorithm <ref>. Here $\mathcal{O}_D(\xv)$ denotes the NOM for nodes in the index set $D=\{i_1,\cdots,i_m\}\subset S=\{1,\cdots,n\}$ as the outputs, and is given by,

\begin{equation}\label{eq:OD}
\mathcal{O}_D(\xv)=\left(
\begin{array}{c}
\Ov_{i_1}(\xv) \\
\Ov_{i_2}(\xv)  \\
\vdots \\
\Ov_{i_m}(\xv)  \\
\end{array}
\right),
\end{equation}

where, construction of $\Ov_i(\xv),i\in D$ is as follows. Let the gradient of entries $\Jv_{p,i}(x),i=1,\cdots,n$ of vector $\Jv_{p},p=1,\cdots,n$  (see Eqn. (<ref>)) be denoted by,

\begin{equation}\label{eq:Jo}
\overline{\Jv}_{p,i}(\xv)=d\Jv_{p,i}(\xv).
\end{equation}

Consider output matrix $\Cv_i\in\Z^{1\times n}$, with $1$ at $i$-th entry and zero otherwise, i.e.,

\begin{equation}\label{eq:C}
\Cv_i=[0 \cdots \overbrace{1}^{ith position} \cdots 0],
\end{equation}

\begin{equation}\label{eq:O}
\Ov_i(\xv)=\nabla_{\xv} \left(
\begin{array}{c}
\Cv_i\Jv_0(x) \\
\Cv_i\Jv_2(x) \\
\vdots \\
\Cv_i\Jv_{n-1}(x) \\
\end{array}
\right)= \left(
\begin{array}{c}
\overline{\Jv}_{0,i}(x) \\
\overline{\Jv}_{1,i}(x) \\
\vdots \\
\overline{\Jv}_{n-1,i}(x) \\
\end{array}
\right),
\end{equation}

is the NOM  with $i$-th node as the measurement, see Eqn. (<ref>). Note that $\mathcal{O}(\xv)$ is computed once in Step 3, and can be reused to compute $\mathcal{O}_D(\xv)$ for any $D\subset S$ making the determination of MON computationally efficient.

For calculating generic matrix rank computation in Step 7, we use the Symbolic Toolbox in MATLAB.

If a uniform hypergraph is non-connected, we can first identify the connected components (which can be defined similarly as in graphs), and then apply the algorithm to each component, further simplifying the MON computation.

In Step 7, if multiple $s^*$ are obtained, we can pick one randomly, or use some other conditions to break the tie, e.g., by selecting the node with the highest degree.

Greedy MON Selection.
[1]
Given a $k$-th order $n$ dimensional super-symmetric tensor $\textsf{A}$

Unfold $\textsf{A}$ to a $n\times n^{k-1}$ matrix $A$

Compute $\mathcal{O}_i(\xv), i=1,\cdots,n$

Let $S=\{1,2,\dots,n\}$ and $D=\emptyset$

$s\in S\setminus D$
Compute $\Delta(s)=\text{rank}(\mathcal{O}_{D\cup \{s\}}(\xv))-\text{rank}(\mathcal{O}_D(\xv))$

Set $s^{*} = \text{argmax}_{s\in S\setminus D}\Delta(s)$

Set $D=D\cup \{s^*\}$

The set $D$.

§ NUMERICAL RESULTS

We demonstrate the identification of MON on uniform hypergraph chain, rings, and stars as well as a  hypergraph constructed from time series data. These calculations were performed symbolically with MATLAB R2022b.

§.§ Synthetic Uniform Hypergraphs

We identified the MON set for uniform hypergraph chains, rings and stars and $k=2,\dots,n$ with $n=3,\dots,7$. For the hyperstar, the size of the MON increases with $n$ and decreases with $k$. As examples, in Fig. <ref>, six hypergraphs are shown with the identified MON. Future work aims to develop a theoretical characterization of the MON for these types of hypergraphs.

[scale=1, transform shape]
[vertex,text=white,scale=0.7] (v1) 1;
[vertex,above of=v1,node distance=20pt,mygray,scale=0.7] (v1a) ;
[->,red, shorten >=1pt,shorten <=1pt, thick](v1a) edge node[left]  (v1);
[vertex,right of=v1,text=white,scale=0.7,node distance = 20pt] (v2) 2;
[vertex,right of=v2,text=white,scale=0.7,node distance = 20pt] (v3) 3;
[vertex,right of=v3,text=white,scale=0.7,node distance = 20pt] (v4) 4;
[vertex,left of=v1,node distance=30pt,mygray,text=black,scale=0.7] (text1) A;

[vertex,right of=v4,text=white,scale=0.7,node distance=30pt] (v5) 1;
[vertex,above of=v5,node distance=20pt,mygray,scale=0.7] (v5a) ;
[->,red, shorten >=1pt,shorten <=1pt, thick](v5a) edge node[left]  (v5);
[vertex,right of=v5,text=white,scale=0.7,node distance = 20pt] (v6) 2;
[vertex,right of=v6,text=white,scale=0.7,node distance = 20pt] (v7) 3;
[vertex,right of=v7,text=white,scale=0.7,node distance = 20pt] (v8) 4;
[vertex,right of=v8,text=white,scale=0.7,node distance = 20pt] (v9) 5;

[vertex,below of=v1,text=white,scale=0.7,node distance=30pt] (a1) 1;
[vertex,above of=a1,node distance=20pt,mygray,scale=0.7] (a1a) ;
[->,red, shorten >=1pt,shorten <=1pt, thick](a1a) edge node[left]  (a1);
[vertex,right of=a1,text=white,scale=0.7,node distance = 20pt] (a2) 2;
[vertex,below of=a2,text=white,scale=0.7,node distance = 20pt] (a3) 3;
[vertex,left of=a3,text=white,scale=0.7,node distance = 20pt] (a4) 4;

[vertex,below of=v5,text=white,scale=0.7,node distance=30pt] (a5) 1;
[vertex,above of=a5,node distance=20pt,mygray,scale=0.7] (a5a) ;
[->,red, shorten >=1pt,shorten <=1pt, thick](a5a) edge node[left]  (a5);
[vertex,right of=a5,text=white,scale=0.7,node distance = 20pt] (a6) 2;
[vertex,right of=a6,text=white,scale=0.7,node distance = 20pt] (a7) 3;
[vertex,below of=a7,text=white,scale=0.7,node distance = 20pt] (a8) 4;
[vertex,left of=a8,text=white,scale=0.7,node distance = 20pt] (a9) 5;
[vertex,left of=a9,text=white,scale=0.7,node distance = 20pt] (a10) 6;

[vertex,left of=a1,node distance=30pt,mygray,text=black,scale=0.7] (text2.1) B;

[vertex,below of=a3,text=white,scale=0.7,node distance=40pt] (c1) 1;
[vertex,above left of=c1,text=white,scale=0.7,node distance=15pt] (c2) 2;
[vertex,above right=12 pt and 7 pt of c1,text=white,scale=0.7,node distance=20pt] (c3) 3;
[vertex,above of=c3,node distance=20pt,mygray,scale=0.7] (c3a) ;
[->,red, shorten >=1pt,shorten <=1pt, thick](c3a) edge node[left]  (c3);
[vertex,left= 18pt of c1,text=white,scale=0.7] (c4) 4;
[vertex,above of=c4,node distance=20pt,mygray,scale=0.7] (c4a) ;
[->,red, shorten >=1pt,shorten <=1pt, thick](c4a) edge node[left]  (c4);
[vertex,below=18pt of c2,text=white,scale=0.7] (c5) 5;
[vertex,below of=text2.1,node distance=50pt,mygray,text=black,scale=0.7] (text2.2) C;

[vertex,below of=a9,text=white,scale=0.7,node distance=30pt] (c6) 1;
[vertex,right of=c6,text=white,scale=0.7,node distance=20pt] (c7) 3;
[vertex,above of=c7,node distance=20pt,mygray,scale=0.7] (c7a) ;
[->,red, shorten >=1pt,shorten <=1pt, thick](c7a) edge node[left]  (c7);
[vertex,below of=c7,text=white,scale=0.7,node distance=20pt] (c8) 4;
[vertex,below of=c8,node distance=20pt,mygray,scale=0.7] (c8a) ;
[->,red, shorten >=1pt,shorten <=1pt, thick](c8a) edge node[left]  (c8);
[vertex,left of=c8,text=white,scale=0.7,node distance=20pt] (c9) 2;
[vertex,left of=c9,text=white,scale=0.7,node distance=20pt] (c10) 6;
[vertex,above of=c10,text=white,scale=0.7,node distance=20pt] (c11) 5;
[vertex,above of=c11,node distance=20pt,mygray,scale=0.7] (c11a) ;
[->,red,shorten >=1pt,shorten <=1pt, thick](c11a) edge node[left]  (c11);

[vertex,below of=c2,text=white,scale=0.7,node distance=60pt] (d1) 1;
[vertex,below right= 5pt and 10pt of d1,text=white,scale=0.7,node distance=20pt] (d2) 2;
[vertex,below left= 10pt and 1pt of d2,text=white,scale=0.7,node distance=20pt] (d3) 3;
[vertex,below left= 5pt and 10pt of d1,text=white,scale=0.7,node distance=20pt] (d5) 5;
[vertex,below right= 10pt and 1pt of d5,text=white,scale=0.7,node distance=20pt] (d4) 4;
[vertex,above of=d1,node distance=20pt,mygray,scale=0.7] (d1a) ;
[->,red,shorten >=1pt,shorten <=1pt, thick](d1a) edge node[left]  (d1);
[vertex,below of=text2.2,node distance=50pt,mygray,text=black,scale=0.7] (text2.3) D;

[vertex,below of=c9,text=white,scale=0.7,node distance=30pt] (e1) 1;
[vertex,right of=e1,text=white,scale=0.7,node distance=20pt] (e2) 2;
[vertex,below right= 10pt and 5pt of e2,text=white,scale=0.7,node distance=20pt] (e3) 3;
[vertex,below of=e2,text=white,scale=0.7,node distance=40pt] (e4) 4;
[vertex,below of=e1,text=white,scale=0.7,node distance=40pt] (e5) 5;
[vertex,below left= 10pt and 5pt of e1,text=white,scale=0.7,node distance=20pt] (e6) 6;
[vertex,above of=e1,node distance=20pt,mygray,scale=0.7] (e1a) ;
[->, red, shorten >=1pt,shorten <=1pt, thick](e1a) edge node[left]  (e1);

[transparency group,opacity=.9]
[edge,color=aureolin, line width=8pt] (v1) – (v2) – (v3);
[edge,color=asparagus, line width=8pt] (v2) – (v3) – (v4);

[edge,color=capri, line width=8pt] (v5) – (v6) – (v7);
[edge,color=darkpink, line width=8pt] (v6) – (v7) – (v8);
[edge,color=eggplant, line width=8pt] (v7) – (v8) – (v9);

[edge,color=fuchsia, line width=8pt] (a1) – (a2) – (a3);
[edge,color=goldenrod, line width=8pt] (a2) – (a3) – (a4);
[edge,color=green(pigment), line width=8pt] (a3) – (a4) – (a1);
[edge,color=salmon, line width=8pt] (a4) – (a1) – (a2);

[edge,color=amber, line width=8pt] (a5) – (a6) – (a7);
[edge,color=amethyst, line width=8pt] (a6) – (a7) – (a8);
[edge,color=applegreen, line width=8pt] (a7) – (a8) – (a9);
[edge,color=ashgrey, line width=8pt] (a8) – (a9) – (a10);
[edge,color=babyblue, line width=8pt] (a9) – (a10) – (a5);
[edge,color=bittersweet, line width=8pt] (a10) – (a5) – (a6);

[edge,color=amber, line width=8pt] (c1) – (c2) – (c3) – (c1);
[edge,color=amethyst, line width=8pt] (c1) – (c2) – (c4) – (c1);
[edge,color=applegreen, line width=8pt] (c1) – (c2) – (c5) – (c1);

[edge,color=blue-green, line width=8pt] (c6) – (c9) – (c7) – (c6);
[edge,color=darkcerulean, line width=8pt] (c6) – (c9) – (c8) – (c6);
[edge,color=brilliantrose, line width=8pt] (c6) – (c9) – (c10) – (c6);
[edge,color=emerald, line width=8pt] (c6) – (c9) – (c11) – (c6);

[edge,color=sandstorm, line width=6pt] (d1) – (d2) – (d3) – (d1);
[edge,color=teal, line width=7pt] (d1) – (d2) – (d4) – (d1);
[edge,color=sealbrown, line width=8pt] (d1) – (d2) – (d5) – (d1);
[edge,color=bleudefrance, line width=9pt] (d1) – (d3) – (d4) – (d1);
[edge,color=aureolin, line width=10pt] (d1) – (d3) – (d5) – (d1);
[edge,color=asparagus, line width=6pt] (d1) – (d4) – (d5) – (d1);
[edge,color=capri, line width=7pt] (d2) – (d3) – (d4) – (d2);
[edge,color=darkpink, line width=8pt] (d2) – (d3) – (d5) – (d2);
[edge,color=eggplant, line width=9pt] (d2) – (d4) – (d5) – (d2);
[edge,color=goldenrod, line width=10pt] (d3) – (d4) – (d5) – (d3);

[edge,color=sandstorm, line width=6pt] (e1) – (e2) – (e3) – (e1);
[edge,color=teal, line width=7pt] (e1) – (e2) – (e4) – (e1);
[edge,color=sealbrown, line width=8pt] (e1) – (e2) – (e5) – (e1);
[edge,color=bleudefrance, line width=9pt] (e1) – (e3) – (e4) – (e1);
[edge,color=aureolin, line width=10pt] (e1) – (e3) – (e5) – (e1);
[edge,color=asparagus, line width=6pt] (e1) – (e4) – (e5) – (e1);
[edge,color=capri, line width=7pt] (e2) – (e3) – (e4) – (e2);
[edge,color=darkpink, line width=8pt] (e2) – (e3) – (e5) – (e2);
[edge,color=eggplant, line width=9pt] (e2) – (e4) – (e5) – (e2);
[edge,color=goldenrod, line width=10pt] (e3) – (e4) – (e5) – (e3);
[edge,color=green(pigment), line width=6pt] (e6) – (e2) – (e3) – (e6);
[edge,color=salmon, line width=7pt] (e6) – (e2) – (e4) – (e6);
[edge,color=amber, line width=8pt] (e6) – (e2) – (e5) – (e6);
[edge,color=amethyst, line width=9pt] (e6) – (e3) – (e4) – (e6);
[edge,color=applegreen, line width=10pt] (e6) – (e3) – (e5) – (e6);
[edge,color=ashgrey, line width=6pt] (e6) – (e4) – (e5) – (e6);
[edge,color=babyblue, line width=7pt] (e6) – (e1) – (e4) – (e6);
[edge,color=bittersweet, line width=8pt] (e6) – (e1) – (e5) – (e6);
[edge,color=blue-green, line width=9pt] (e6) – (e1) – (e2) – (e6);
[edge,color=darkcerulean, line width=10pt] (e6) – (e1) – (e3) – (e6);

MON of 3-uniform hyperchains, hyperrings and hyperstars. The nodes with arrows are denoted as the MON nodes. (A) $3-$uniform hyperchain on $n=4$ (left) and $n=5$ (right) vertices. (B) $3-$uniform hyperring on $n=4$ (left) and $n=6$ (right) vertices. (C) $3-$uniform hyperstar on $n=5$ (left) and $n=6$ (right) vertices. (D) $3-$uniform complete hypergraphs with $n=5$ (left) and $n=6$ (right) vertices. The red arrows indicate the MON.

§.§ Mouse Neuron Endomicroscopy Hypergraph

Hypothalamus neural activity during a feeding, fasting, and refeeding experiment was monitored with endomicroscopy to generate a time series data set [6]. Similar to [10] and [12], we construct 3 hypergraph representations of the activity of $15$ neurons during the different phases of the experiment. First, we compute the multi-correlation of all pairs of 3 neurons, which is defined

\begin{equation}
\rho = (1-\det(\mathbf{R}))^{1/2},
\end{equation}

where $\mathbf{R}\in\R^{3\times 3}$ is the correlation matrix among 3 neurons [28]. When the multi-correlation $\rho$ is greater than a prescribed threshold, we define a hyperedge among the 3 vertices. Following [10], we used a threshold of $0.95$.

For each of the three hypergraphs, we identified the MON. Fig. <ref> depicts the hypergraph structure during each phase of the feeding experiment and depicts the MON. A similar correlation, thresholding, and graph construction was performed on all 3 phases of the experiment to identify the linear MON. Across all phases of the experiment, the MON size is reduced for hypergraphs as opposed to graphs. During the fast phase of the experiment, the multi-correlation among all neurons decreases, which results in a less connected hypergraph and an increased size of the MON. Given that the number of observed nodes on the connected component is minimal, it appears that the size of the MON set is largely driven by hypergraph connectivity. While the hypergraph MON sets is greatly reduced compared to the graph MON sets during all three phases of the experiment, the size of the MON set is the same order of magnitude as the minimum control node sets identified on this data in [10].

[circle,inner sep=0.8] at  (60,150) Fed;

[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v1) at  (110,36) ;
[circle,draw,fill=black,color=black,inner sep=4.24264/4] (v2) at  (13,78) ;
[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v3) at  (96,58) ;
[circle,draw,fill=black,color=black,inner sep=5.65685/4] (v4) at  (85,102) ;
[circle,draw,fill=black,color=black,inner sep=5.83095/4] (v5) at  (42,22) ;
[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v6) at  (47,34) ;
[circle,draw,fill=black,color=black,inner sep=4.24264/4] (v7) at  (53,67) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v8) at  (85,89) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v9) at  (78,42) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v10) at  (53,2) ;
[circle,draw,fill=black,color=black,inner sep=4.24264/4] (v11) at  (62,23) ;

[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v14) at  (71,88) ;

[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v16) at  (117,32) ;

[circle,draw,fill=black,color=black,inner sep=5.83095/4] (v19) at  (118,27) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v20) at  (84,20) ;

[dashed, thick,gray] (v2) – (v4);
[dashed, thick,gray] (v2) – (v7);
[dashed, thick,gray] (v2) – (v5);
[dashed, thick,gray] (v2) – (v6);
[dashed, thick,gray] (v2) – (v9);
[dashed, thick,gray] (v2) – (v10);

[dashed, thick,gray] (v4) – (v5);
[dashed, thick,gray] (v4) – (v9);

[dashed, thick,gray] (v5) – (v6);
[dashed, thick,gray] (v5) – (v7);
[dashed, thick,gray] (v5) – (v8);
[dashed, thick,gray] (v5) – (v9);
[dashed, thick,gray] (v5) – (v10);

[dashed, thick,gray] (v6) – (v7);
[dashed, thick,gray] (v6) – (v8);

[dashed, thick,gray] (v7) – (v10);

[vertex,above of=v1,node distance=10pt,scale=0.7, white,opacity=0] (w1) ;
[vertex,above of=v2,node distance=10pt,scale=0.7, white,opacity=0] (w2) ;
[vertex,above of=v3,node distance=10pt,scale=0.7, white,opacity=0] (w3) ;
[vertex,above of=v11,node distance=10pt,scale=0.7, white,opacity=0] (w11) ;
[vertex,above of=v14,node distance=10pt,scale=0.7, white,opacity=0] (w14) ;
[vertex,above of=v16,node distance=10pt,scale=0.7, white,opacity=0] (w16) ;

[vertex,above of=v20,node distance=10pt,scale=0.7, white,opacity=0] (w20) ;
[vertex,above of=v4,node distance=10pt,scale=0.7, white,opacity=0] (w4) ;
[vertex,above of=v8,node distance=10pt,scale=0.7, white,opacity=0] (w8) ;

[->, red, line width=0.6pt] (w2) – (v2);
[->, red, line width=0.6pt] (w1) – (v1);
[->, red, line width=0.6pt] (w3) – (v3);
[->, red, line width=0.6pt] (w11) – (v11);
[->, red, line width=0.6pt] (w14) – (v14);
[->, red, line width=0.6pt] (w16) – (v16);

[->, red, line width=0.6pt] (w20) – (v20);

[circle,inner sep=0.8] at  (60,150) Fast;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v1) at  (110,36) ;
[circle,draw,fill=black,color=black,inner sep=4.24264/4] (v2) at  (13,78) ;
[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v3) at  (96,58) ;
[circle,draw,fill=black,color=black,inner sep=5.65685/4] (v4) at  (85,102) ;
[circle,draw,fill=black,color=black,inner sep=5.83095/4] (v5) at  (42,22) ;
[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v6) at  (47,34) ;
[circle,draw,fill=black,color=black,inner sep=4.24264/4] (v7) at  (53,67) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v8) at  (85,89) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v9) at  (78,42) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v10) at  (53,2) ;
[circle,draw,fill=black,color=black,inner sep=4.24264/4] (v11) at  (62,23) ;

[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v14) at  (71,88) ;

[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v16) at  (117,32) ;

[circle,draw,fill=black,color=black,inner sep=5.83095/4] (v19) at  (118,27) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v20) at  (84,20) ;

[dashed, thick,gray] (v3) – (v10);
[dashed, thick,gray] (v3) – (v19);
[dashed, thick,gray] (v10) – (v16);
[dashed, thick,gray] (v10) – (v19);
[dashed, thick,gray] (v16) – (v19);

[vertex,above of=v3,node distance=10pt,scale=0.7, white,opacity=0] (w3) ;
[->, red, line width=0.6pt] (w3) – (v3);

[vertex,above of=v1,node distance=10pt,scale=0.7, white,opacity=0] (w1) ;
[vertex,above of=v2,node distance=10pt,scale=0.7, white,opacity=0] (w2) ;
[vertex,above of=v4,node distance=10pt,scale=0.7, white,opacity=0] (w4) ;
[vertex,above of=v5,node distance=10pt,scale=0.7, white,opacity=0] (w5) ;
[vertex,above of=v6,node distance=10pt,scale=0.7, white,opacity=0] (w6) ;
[vertex,above of=v7,node distance=10pt,scale=0.7, white,opacity=0] (w7) ;
[vertex,above of=v8,node distance=10pt,scale=0.7, white,opacity=0] (w8) ;
[vertex,above of=v9,node distance=10pt,scale=0.7, white,opacity=0] (w9) ;
[vertex,above of=v11,node distance=10pt,scale=0.7, white,opacity=0] (w11) ;
[vertex,above of=v14,node distance=10pt,scale=0.7, white,opacity=0] (w14) ;
[vertex,above of=v19,node distance=10pt,scale=0.7, white,opacity=0] (w19) ;

[vertex,above of=v1,node distance=10pt,scale=0.7, white,opacity=0] (w1) ;
[->, red, line width=0.6pt] (w1) – (v1);
[vertex,above of=v4,node distance=10pt,scale=0.7, white,opacity=0] (w4) ;
[vertex,above of=v6,node distance=10pt,scale=0.7, white,opacity=0] (w6) ;
[vertex,above of=v8,node distance=10pt,scale=0.7, white,opacity=0] (w8) ;
[vertex,above of=v11,node distance=10pt,scale=0.7, white,opacity=0] (w11) ;

[vertex,above of=v20,node distance=10pt,scale=0.7, white,opacity=0] (w20) ;
[vertex,above of=v5,node distance=10pt,scale=0.7, white,opacity=0] (w5) ;
[vertex,above of=v10,node distance=10pt,scale=0.7, white,opacity=0] (w10) ;

[->, red, line width=0.6pt] (w1) – (v1);
[->, red, line width=0.6pt] (w2) – (v2);
[->, red, line width=0.6pt] (w4) – (v4);
[->, red, line width=0.6pt] (w5) – (v5);
[->, red, line width=0.6pt] (w6) – (v6);
[->, red, line width=0.6pt] (w7) – (v7);
[->, red, line width=0.6pt] (w8) – (v8);
[->, red, line width=0.6pt] (w9) – (v9);
[->, red, line width=0.6pt] (w11) – (v11);
[->, red, line width=0.6pt] (w14) – (v14);
[->, red, line width=0.6pt] (w20) – (v20);

[circle,inner sep=0.8] at  (60,150) Re-fed;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v1) at  (110,36) ;
[circle,draw,fill=black,color=black,inner sep=4.24264/4] (v2) at  (13,78) ;
[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v3) at  (96,58) ;
[circle,draw,fill=black,color=black,inner sep=5.65685/4] (v4) at  (85,102) ;
[circle,draw,fill=black,color=black,inner sep=5.83095/4] (v5) at  (42,22) ;
[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v6) at  (47,34) ;
[circle,draw,fill=black,color=black,inner sep=4.24264/4] (v7) at  (53,67) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v8) at  (85,89) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v9) at  (78,42) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v10) at  (53,2) ;
[circle,draw,fill=black,color=black,inner sep=4.24264/4] (v11) at  (62,23) ;

[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v14) at  (71,88) ;

[circle,draw,fill=black,color=black,inner sep=4.47214/4] (v16) at  (117,32) ;

[circle,draw,fill=black,color=black,inner sep=5.83095/4] (v19) at  (118,27) ;
[circle,draw,fill=black,color=black,inner sep=4.12311/4] (v20) at  (84,20) ;

[vertex,above of=v1,node distance=10pt,scale=0.7, white,opacity=0] (w1) ;
[->, red, line width=0.6pt] (w1) – (v1);
[vertex,above of=v4,node distance=10pt,scale=0.7, white,opacity=0] (w4) ;
[vertex,above of=v6,node distance=10pt,scale=0.7, white,opacity=0] (w6) ;
[vertex,above of=v8,node distance=10pt,scale=0.7, white,opacity=0] (w8) ;
[vertex,above of=v11,node distance=10pt,scale=0.7, white,opacity=0] (w11) ;

[vertex,above of=v20,node distance=10pt,scale=0.7, white,opacity=0] (w20) ;
[vertex,above of=v5,node distance=10pt,scale=0.7, white,opacity=0] (w5) ;
[vertex,above of=v10,node distance=10pt,scale=0.7, white,opacity=0] (w10) ;

[->, red, line width=0.6pt] (w4) – (v4);
[->, red, line width=0.6pt] (w2) – (v2);
[->, red, line width=0.6pt] (w6) – (v6);
[->, red, line width=0.6pt] (w8) – (v8);
[->, red, line width=0.6pt] (w11) – (v11);
[->, red, line width=0.6pt] (w20) – (v20);

[vertex,above of=v3,node distance=10pt,scale=0.7, white,opacity=0] (w3) ;
[->, red, line width=0.6pt] (w3) – (v3);

[dashed, thick,gray] (v1) – (v5);
[dashed, thick,gray] (v1) – (v7);
[dashed, thick,gray] (v1) – (v9);
[dashed, thick,gray] (v5) – (v7);
[dashed, thick,gray] (v5) – (v9);
[dashed, thick,gray] (v5) – (v10);
[dashed, thick,gray] (v5) – (v16);
[dashed, thick,gray] (v7) – (v9);
[dashed, thick,gray] (v7) – (v10);
[dashed, thick,gray] (v7) – (v14);
[dashed, thick,gray] (v7) – (v16);
[dashed, thick,gray] (v7) – (v19);
[dashed, thick,gray] (v9) – (v10);
[dashed, thick,gray] (v9) – (v16);
[dashed, thick,gray] (v10) – (v14);
[dashed, thick,gray] (v9) – (v19);
[dashed, thick,gray] (v9) – (v14);
[dashed, thick,gray] (v10) – (v19);

[ybar, enlargelimits=0.23, ymax =15, ymin=3.2,
symbolic x coords=A,B,C,
xtick=data, ylabel near ticks, xticklabels=Fed,Fast,Re-fed, title=D, xlabel=Phase, legend pos = north east,legend style=draw=none, xtick pos=left,ytick pos=left,legend columns=-1,
+[blue, blue, fill=blue, opacity=.7] coordinates (A,8) (B,12) (C,8);

+[orange, red, fill=red, opacity=.7] coordinates (A,15) (B,15) (C,15);

(Above) Mouse neuron endomicroscopy features. Neuronal activity networks of the three phases - fed, fast and re-fed, which depicts the spatial location and size of individual cells. Each 2-simplex (i.e., a triangle) represents a hyperedge, and red arrows indicate nodes selected in MON. (Below) MON for the neuronal activity networks modelled by 3-uniform hypergraphs and standard graphs.

§ CONCLUSION

In this paper, we proposed a framework to study observability for uniform hypergraphs. We defined a canonical multilinear dynamical system with linear outputs using uniform hypergraph adjacency tensor leading to a homogeneous polynomial system. We derived the NOM for assessing the local weak observability of this resulting system.  We also proposed a recursive technique for efficient computation of the NOM, and a greedy heuristic to determine the MON. We demonstrated our approach numerically on different hypergraph topologies, and hypergraphs derived from an experimental mouse endomicroscopy dataset.

In the future, we plan to perform theoretical analysis for determining MON for different hypergraph topologies and exploring the role of symmetry, and to extend the proposed framework for non-uniform and directed hypergraphs. We also hope to further improve efficiency of the observability computations to scale to large hypergraphs which often arise in practise.

§ ACKNOWLEDGMENTS

This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-22-1-0215 and
by NSF grant DMS-2103026. Any opinions, finding, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Air Force.

[1]
S. H. Strogatz, “Exploring complex networks,” nature, vol. 410, no.
6825, pp. 268–276, 2001.

[2]
M. Newman, Networks.1em plus 0.5em minus 0.4emOxford
university press, 2018.

[3]
F. Bullo, Lectures on network systems.1em plus 0.5em minus
0.4emKindle Direct Publishing, 2020, vol. 1.

[4]
F. Battiston, G. Cencetti, I. Iacopini, V. Latora, M. Lucas, A. Patania, J.-G.
Young, and G. Petri, “Networks beyond pairwise interactions: structure and
dynamics,” Physics Reports, 2020.

[5]
A. R. Benson, D. F. Gleich, and D. J. Higham, “Higher-order network analysis
takes off, fueled by classical ideas and new data,” arXiv preprint
arXiv:2103.05031, 2021.

[6]
P. Sweeney, C. Chen, I. Rajapakse, and R. D. Cone, “Network dynamics of
hypothalamic feeding neurons,” Proceedings of the National Academy of
Sciences, vol. 118, no. 14, 2021.

[7]
M. M. Wolf, A. M. Klinvex, and D. M. Dunlavy, “Advantages to modeling
relational data using hypergraphs versus graphs,” in 2016 IEEE High
Performance Extreme Computing Conference (HPEC).1em plus 0.5em minus
0.4emIEEE, 2016, pp. 1–7.

[8]
C. Berge, Hypergraphs: combinatorics of finite sets.1em plus
0.5em minus 0.4emElsevier, 1984, vol. 45.

[9]
T. G. Kolda, “Multilinear operators for higher-order decompositions,” 2006.

[10]
C. Chen, A. Surana, A. Bloch, and I. Rajapakse, “Controllability of
hypergraphs,” IEEE Transactions on Network Science and Engineering,

[11]
C. Chen and I. Rajapakse, “Tensor entropy for uniform hypergraphs,”
IEEE Transactions on Network Science and Engineering, vol. 7, no. 4,
pp. 2889–2900, 2020. [Online]. Available:

[12]
A. Surana, C. Chen, and I. Rajapakse, “Hypergraph similarity measures,”
IEEE Transactions on Network Science and Engineering, 2022.

[13]
A. N. Montanari and L. A. Aguirre, “Observability of network systems: A
critical review of recent results,” Journal of Control, Automation and
Electrical Systems, vol. 31, pp. 1348–1374, 2020.

[14]
——, “Particle filtering of dynamical networks: Highlighting observability
issues,” Chaos: An Interdisciplinary Journal of Nonlinear Science,
vol. 29, no. 3, p. 033118, 2019.

[15]
T. H. Summers and J. Lygeros, “Optimal sensor and actuator placement in
complex dynamical networks,” IFAC Proceedings Volumes, vol. 47,
no. 3, pp. 3784–3789, 2014.

[16]
Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Observability of complex
systems,” Proceedings of the National Academy of Sciences, vol. 110,
no. 7, pp. 2460–2465, 2013.

[17]
F. Su, J. Wang, H. Li, B. Deng, H. Yu, and C. Liu, “Analysis and application
of neuronal network controllability and observability,” Chaos: An
Interdisciplinary Journal of Nonlinear Science, vol. 27, no. 2, p. 023103,

[18]
R. A. Horn and C. R. Johnson, Topics in Matrix Analysis.1em plus
0.5em minus 0.4emCambridge: Cambridge University Press, 1991.

[19]
T. Kolda and B. Bader, “Tensor decompositions and applications,” SIAM
Review, vol. 51, no. 3, pp. 455–500, 2009.

[20]
C. Chen, A. Surana, A. Bloch, and I. Rajapakse, “Multilinear time invariant
system theory,” in 2019 Proceedings of the Conference on Control and
its Applications.1em plus 0.5em minus 0.4emSIAM, 2019, pp.

[21]
C. Chen, A. Surana, A. M. Bloch, and I. Rajapakse, “Multilinear control
systems theory,” SIAM Journal on Control and Optimization, vol. 59,
no. 1, pp. 749–776, 2021.

[22]
S. Ragnarsson and C. Van Loan, “Block tensor unfoldings,” SIAM J.
Matrix Analysis Applications, vol. 33, pp. 149–169, 2012.

[23]
R. Hermann and A. Krener, “Nonlinear controllability and observability,”
IEEE Transactions on automatic control, vol. 22, no. 5, pp. 728–740,

[24]
E. D. Sontag, “A concept of local observability,” Systems & Control
Letters, vol. 5, no. 1, pp. 41–47, 1984.

[25]
D. Gerbet and K. Röbenack, “On global and local observability of nonlinear
polynomial systems: A decidable criterion,”
at-Automatisierungstechnik, vol. 68, no. 6, pp. 395–409, 2020.

[26]
M. Anguelova, Nonlinear Observability and Identi ability: General Theory
and a Case Study of a Kinetic Model for S. cerevisiae.1em plus 0.5em
minus 0.4emChalmers Tekniska Hogskola (Sweden), 2004.

[27]
A. Sedoglavic, “A probabilistic algorithm to test local algebraic
observability in polynomial time,” in Proceedings of the 2001
international symposium on Symbolic and algebraic computation, 2001, pp.

[28]
J. Wang and N. Zheng, “Measures of correlation for multiple variables,”
arXiv preprint, 2014. [Online]. Available:


#  Face Recognition as a Method of Authentication in a Web-Based System

Ben Wycliff Mugalu  Dept. Electrical and Computer Engineering
Makerere University
<EMAIL_ADDRESS>Rodrick Calvin Wamala  Dept. of Electrical and
Computer Engineering
Makerere University
<EMAIL_ADDRESS>Jonathan Serugunda  Dept. of Electrical and Computer
Engineering
Makerere University
<EMAIL_ADDRESS>* Andrew Katumba  Dept. of Electrical and Computer
Engineering
Makerere University
<EMAIL_ADDRESS>
###### Abstract

111Corresponding author<EMAIL_ADDRESS>
Online information systems currently heavily rely on the username and password
traditional method for protecting information and controlling access. With the
advancement in biometric technology and popularity of fields like AI and
Machine Learning, biometric security is becoming increasingly popular because
of the usability advantage. This paper reports how machine learning based face
recognition can be integrated into a web-based system as a method of
authentication to reap the benefits of improved usability. This paper includes
a comparison of combinations of detection and classification algorithms with
FaceNet for face recognition. The results show that a combination of MTCNN for
detection, Facenet for generating embeddings, and LinearSVC for classification
out performs other combinations with a 95% accuracy. The resulting classifier
is integrated into the web-based system and used for authenticating users.

Keywords–FaceNet, MTCNN, Face Recognition, Machine Learning, Biometric
Authentication, LinearSVC

##  I Introduction

Information and Communication Technology usage has witnessed rapid growth in
the past decade decade all around the world. A bigger percentage of the
population has laptops, personal computers, and smart phones making it easy to
access the internet and thus changing lives of millions of people [1]. All
web-based systems that have users and store personal information about the
users require a mechanism to keep track of their users’ information. Most
commonly every user of the system is assigned an instance in the database that
represents them (their identity). To protect the user identity, an
authentication and authorization mechanism is implemented to control access to
certain information. The most common method in web-based systems is
authentication using passwords. Users regularly provide a combination of their
username and password through a form to access a remote account [9].

Passwords have well-known disadvantages in both usability and security. This
leads to promotion of biometric-based authentication. The primary motivation
of biometric authentication is usability: users are not required to remember
the passwords, there is nothing for them to carry, biometric systems are
generally easy to use, and scalable in terms of the burden exerted onto the
users. Biometric technology can be used to control the risk of sharing,
forgetting, losing, and embezzlement of passwords [10].

###  I-A Biometric Authentication

Biometric authentication is the automatic authentication that identifies a
person by analyzing their physiological and/or behaviour features. In the past
two decades, both physiological and behaviour characteristics have been used
in biometric authentication systems. Physiological features are attributed to
the person’s body shape such as the face, palm prints, DNA, e.t.c. Behavioural
characteristics are attributed to the person’s behavior: typing speed, voice,
and articulation [4].

###  I-B Artificial Intelligence

Artificial Intelligence is impacting the world with its ability to achieve the
never thought tasks, the accurate resource knowledge used can highly affect
the execution. In recent years we all have witnessed an exceptional growth in
the improvement of state of the art accuracy for multiple domains such as text
classification, speech recognition, image processing and natural language
processing [5].

The challenges faced by hard-coded systems convey that artificial intelligence
systems require an ability to extract and acquire knowledge from raw data
supplied to them. The idea of systems learning from data, identifying patterns
and making decisions with little human intervention is known as machine
learning. Real world AI applications face a difficulty caused by the fact that
the factors of variation influence every unit of data that can be observed.
For example, individual pixels in a blue object image may be very close to
those of a black object at night. The shape of the object depends on the angle
of observation. Most of the applications require us to extract the most
important factors and discard the ones we do not care about. Deep learning, a
subset of machine learning implements this by introducing factors represented
in terms of other and simpler factors. Deep learning allows the computer to
build complex problems out of simpler problems utilizing a hierarchy of
artificial neural networks to carry out machine learning processes. Artificial
neural networks are inspired and built like the biological neural network of a
human brain. It consists of neuron nodes connected together. Traditional
programs develop analysis with data in a linear way, while the hierarchical
style of deep learning systems gives machines the ability to process data with
in nonlinear way. [6][7][8].

###  I-C Face Recognition

In the present time, face recognition is a popular and important technology
integrated in many applications such as payment, door unlock, video monitoring
systems, etc. A face recognition system is a technology that can identify and
verify people from digital images and footage. The state-of-the-art face
recognition approaches for web authentication include luxand [9] and smileid
from electronicsid [10]. These are both provided as commercial products. [11].
To recognize faces (human faces), Images are taken using a digital camera. the
first step is to perform face detection, this is performed as a preprocessing
step to locate the face in an image. Faces are generally unique depending on
the environment the images were taken: illumination, brightness, facial
expressions, and the person’s face orientation. The next step is the face
recognition: a set of features are computed utilizing a special algorithm. The
set of features generated is classified to represent each person’s face
uniquely. The response from the classifier is the owner of the facial features
[12].

A number of face recognition studies are carried out but these disclose only
the pipeline representation stage. This was started years ago by the
mathematical background. In any case, from the academic perspective,
researchers from the Carnegie Mellon and Oxford universities have shared both
network structures and pre-trained models. From the commercial perspective,
companies (Google and Facebook) share only the network structures. Lucky for
us there is an encouraging open source community that has emerged who train
these models from scratch and share them. [13].

There are many face recognition algorithms in the academic field, part of the
research results are relatively mature. The state of the art face recognition
models include VGGFace [14] from the University of Oxford, DeepFace[15] from
Facebook, OpenFace [16] from the Carnegie Mellon University, and FaceNet [17]
from Google.

A study that compares the four state-of-the-art recognition models was
conducted during the development of the lightFace [13] framework (A python
framework that provides face-recognition support for each of these models). It
showed that Google’s Facenet was the best model among the four.

##  II Implementation

Our Approach on face recognition consists of three stages, that is given an
image, we perform face localization, face embeddings generation using Google’s
FaceNet pretrained model, and classification using the linearSVC classifier.

###  II-A Data Collection

In a case study on 100 different people, a total of 1424 images from the
volunteers. Captured using a 12MP dual-lens camera of the tecno camon 12 air
smartphone, the images appeared in different orientations and lightings. The
number 1424 is that which was obtained after performing data cleaning.

###  II-B Hardware Setup

The training was done on a personal computer. A HP ProBook 450 G3, with 8192MB
RAM, Intel(R) Core(TM)i5-6200U CPU @ 2.30GHz(4 CPUs) 2.4GHz processor, and AMD
Radeon (TM) R7 M340 graphics card with 2GB dedicated VRAM.

###  II-C Face Detection

For the case of face detection, two of the most commonly used ways of face
detection were compared;

####  II-C1 The Viola-Jones Haarcascade classifier

It is based on the Viola-Jones Object Detection framework. This frame work has
a quiet high (true positive rate) detection rate and a very low false positive
rate making the algorithm a robust one that also processes the images quickly.
The main objective is face detection not recognition: it distinguishes faces
from non-faces which is the first (preprocessing) step recognition. The
framework follows four main steps: Haar Feature Selection, Creating an
Integral Image, Adaboost Training and the Cascading Classifiers.[19]

####  II-C2 The Multi-Task Cascaded Convolutional Neural Network

that is based on Neural Network-Based Face Detection. A Neural Network
inspired by human brain composed of simple artificial neurons also known a
perceptrons are connected to each other in multiple layer. The MTCNN is
comprised of three layers.

Layer 1: _The Proposal Network (P-Net):_ This is a fully convolutional network
which is used to obtain the candidate windows and their bounding box
regression vectors as shown in figure 1 [20]

Figure 1: The Proposal Network Layer [20]

Layer 2: _The Refine Network (R-Net):_ The output of the P-Net is input into
the R-Net which is a Convolution Neural Network and hence denser than the
P-Net layer. The R-Net further reduces the number of candidates (which further
rejects a large number of false candidates)[20], performs calibration with
bounding box regression and employs Non-Maximum Suppression (NMS) to merge
overlapping candidates.

Figure 2: The Refine Network Layer [20]

Layer 3: _The Output Network (O-Net):_ Similar to the R-Net the O-Net aims to
describe the face in detail outputting five facial landmarks’ positions for
the main face features like the eyes, nose and mouth.

Face detection and localization was performed on the faces using the MTCNN
algorithm. The localized face is resized into a 160×160 RGB image. A face
dataset is created.

###  II-D Face Recognition

A FaceNet model pre-trained on a VGGFace2 dataset consisting of 3.3M faces and
9000 classes in an inception ResNet v1 architecture [21] was used. The
pretrained model expects 160×160 RGB images. The model was converted into a
keras compatible version [22]. The converted model was used to generate
embeddings for all images in the faces dataset. For each face image in the
faces dataset, an array of 512 different weights uniquely representing the
face was generated. A new dataset of face embeddings was prepared and compiled
for classification purposes. The generated embeddings are used to create a new
dataset consisting of face embeddings. Table I below shows information about
the pretrained Facenet model.

TABLE I: Pre-trained FaceNet Model

Model name | LFW accuracy | Training dataset | Architecture
---|---|---|---
20180402-114759 | 0.9965 | VGGFace2 | Inception ResNet v1

###  II-E Classification

With the face embeddings dataset, the next step was classification of the face
embeddings. Classification involved comparison of three classification
algorithms: the LinearSVC, OneVsRest Classifier, and the Random Forest
Classifier.

Before training the classification models, the embeddings dataset was split
into the test and train datasets, $30\%$ for testing, and $70\%$ for training.
For each classification model trained, a 10-fold stratified cross-validation
method was used for tuning the classifier to obtain improved performance. The
train set was made up of 952 images, the test set 472 images and the
validation fold 95 images.

After training each of the classification algorithms with the train data (70%
of 1424 face embeddings dataset), each trained classification model was tested
by tasking it to predict the test data. Each of the classifiers was validated
using the stratified (10-fold) cross-validation method. The individual
accuracies for different folds were determined to reflect the performance of
the model at different sections for the entirety of the training dataset. For
each fold, the validation dataset was 10% of the training dataset.

####  II-E1 LinearSVC

The classification model here was trained with a regular parameter,
$randomstate=0$, and tuned with a hyperparameter $C=1$. It took approximately
$14seconds$ to train this model, the average validation accuracy was 0.93.

####  II-E2 OneVsRest

This classifier used the SVC with a regular parameter $probability=True$, as
the binary classifier for performing multiclass classification. The model was
tuned with a hyperparameter, $n\\_jobs=100$. It took approximately $97seconds$
to train this model on the train set, and the average cross-validation
accuracy was 91%.

####  II-E3 Random Forest

The classification model was created with a regular parameter,
$randomstate=0$, and tuned with a hyperparameter $n\\_estimators=1000$. The
training for this model took approximately $120seconds$. The average
validation accuracy was $91\%$.

Each of the classification algorithms was evaluated with metrics: precision,
recall, accuracy, and the confusion matrix to visualize wrong classifications.

###  II-F Bias Test

Two datasets of the same size with images from 33 different people each were
generated. One dataset consisted of entirely white people’s images obtained
from the Georgia Institute of Technology [18]m the other consisted of entirely
black people’s images. It was a fraction of the data collected from the 100
different volunteers. Face embeddings from the respective datasets were
classified and compared, the performance metrics to determine if there is bias
in the pre-trained model.

Figure 3: Black people dataset sample Figure 4: White people dataset sample

##  III Face Authentication

A login view that captures the person’s face at the frontend was developed.
This took the image and converted it into a data URI. At the face recognition
login view, there is an event listener on the login button that makes a call
to the face recognition API with a request composed of the image data URI.
When the recognition API receives the request, it extracts the URI converts it
into an image and fowards it to the classification model to perform
recognition. The model responds with a code corresponding to the person found
in the image. The API then sends the predicted code back to the frontend. The
frontend sends this code to the system backend RESTful API. In the web-based
system, as a user registers for face recognition, the system encrypts, and
stores their special code in the database. When the frontend/client receives
the predicted code from the face recognition API, It makes a call to the
system backend RESTful API with a request composed of the unique code. The
system then extracts the code and user-email, decrypts the code it has in the
database under the corresponding user-email, and checks whether the two match.
If they match, the user is authenticated and authorized into their account,
otherwise, authentication fails.

The stack used for system development was VueJS at the frontend, expressJS for
the backend API, MongoDB for data storage, and python’s flask for the
recognition API.

Figure 5: Face authentication sequence diagram

##  IV Results

###  IV-A Face Localization

Face localization using the Viola-Jones Haarcascade algorithm produced results
in figure 6. It can be observed that the algorithm eliminated some of the
vital facial features like the chin, which in turn affected the accuracy of
recognition with a face dataset generated using this algorithm. The algorithm
failed to localize faces despite existence in the image on several occasions,
for example in figure 6, the localization in the second row third image is
faceless.

Figure 6: Localization using the Viola-Jones Haarcascade algorithm

The MTCNN algorithm, on the other hand, could perfectly detect a face whenever
one existed in the image. The results of the MTCNN detection on a similar
group of images can be seen in figure 7. By observation, the MTCNN out
performs the Viola-Jones algorithm in localizing faces.

Figure 7: Localization using the MTCNN algorithm

When the two algorithms were used to generate identical datasets, which were
further used to train the linearSVC model, the performance metrics in table II
below were obtained. A $74\%$ versus $98\%$ accuracy on a similar dataset
reflects how good a choice the MTCNN is compared to the Viola-Jones
haarcascade.

TABLE II: comparison of the face detection algorithms metrics Algorithms | Accuracy | Precision
---|---|---
Haarcascade | 0.74 | 0.74
MTCNN | 0.98 | 0.98

Table II shows the results obtained from the comparison of the two face
detection algorithms we considered in our research basing on the accuracy and
precision as metrics of performance.

###  IV-B Classification

The performance metrics for classification were as indicated in the table III.

TABLE III: Classification algorithms metrics Classifier | Precision | Accuracy | Recall | F1 Score
---|---|---|---|---
LinearSVC | 0.95 | 0.95 | 0.95 | 0.95
OneVsRest | 0.94 | 0.94 | 0.94 | 0.93
Random Forest | 0.91 | 0.91 | 0.91 | 0.91

###  IV-C Model Selection

From the results discussed above, it was determined that the LinearSVC
provided a better performance by 1% and 4% compared to the OneVsRest and
Random Forest classifiers respectively. Thus the LinearSVC model was exported
and utilized in the development of the face recognition API. Figure 8 below is
a normalized confusion matrix for 20 of the 100 classes (people) classified
using the LinearSVC classifier. From this figure, it can be determined that
the class labeled 10 was wrongly classified as the class labeled 1 for half of
its data items in the test set.

Figure 8: LinearSVC confusion matrix for 20 of the 100 classes

###  IV-D Bias Test

Table IV shows the results obtained from the comparison of the performance of
the linearSVC when trained on a black faces dataset compared to a white faces
dataset.

TABLE IV: Datasets Comparison Dataset | Precision | Accuracy | Recall | F1 Score
---|---|---|---|---
Black people | 0.94 | 0.94 | 0.93 | 0.92
White people | 1.00 | 1.00 | 1.00 | 1.00

The metrics reflect the fact that the model produced a better performance with
a white faces dataset compared to a similar size blackfaces dataset. Thus the
pretrained face recognition model used to generate face embeddings that
uniquely represent the face had bias toward black faces.

###  IV-E System

Figure 9 below displays the face-recognition login interface that the user
sees when they choose the login with face recognition option from the system
interface.

Figure 9: Face recognition login interface

##  V Conclusion

The system developed uses the MTCNN algorithm to detect the face, generates
embeddings using a FaceNet pretrained model and a linearSVC classifier to
recognize images taken through the system and authenticates users accordingly.
The combination of these algorithms resulted in a 95% recognition accuracy.
The limitations for this work include the fact that it was determined that the
pre-trained FaceNet model used had bias towards the black people dataset and
the issue of liveness at the login interface, which made it possible for one
to login into the system using an image since there is no mechanism for
liveness detection. With these limitations, we propose as our future work to
retrain the FaceNet model with a black faces dataset to eliminate bias,
implement classfication with neural networks, integrate liveness detection at
the frontend of the system face recognition login, automate the process of
classification for digital onboarding of new users.

## References

  * [1] Hacıoğlu, Müjgan & Karakaş Geyik, Seda. (2015). An Empirical Research on General Internet Usage Patterns of Undergraduate Students. Procedia - Social and Behavioral Sciences. 195. 895-904. 10.1016/j.sbspro.2015.06.369.
  * [2] van Oorschot, P. C. (2020). User Authentication—Passwords,Biometrics and Alternatives. https://doi.org/10.1007/978-3-030-33649-3 3
  * [3] Meng, X. (2008). Study on the Model of E-Commerce Identity Authentication based on Multi-biometric Features Identification. Proceedings-2008 ISECS International Colloquium on Computing, Communication, Control, and Management, 200.
  * [4] A. Alotaibi and A. Mahmmod, “Enhancing OAuth services security by an authentication service with face recognition,” 2015 IEEE Long Isl. Syst. Appl. Technol. Conf. LISAT 2015, 2015, doi: 10.1109/LISAT.2015.7160208.
  * [5] S. Khokad and V. Kala, ”A study of SLIDE Algorithm: Revolutionary AI Algorithm that Speeds Up Deep Learning on CPUs,” 2020 International Conference on Smart Innovations in Design, Environment, Management, Planning and Computing (ICSIDEMPC), AURANGABAD, 2020, pp. 188-191, doi: 10.1109/ICSIDEMPC49020.2020.9299644.
  * [6] I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning. 2016.
  * [7] SAS. (2020). Machine Learning. https://www.sas.com/en_us/insights/analytics/machine-learning.html#: :text=Machine learning is a method,decisions with minimal human intervention.
  * [8] Hargrave, M. (2020). Deep Learning. https://www.investopedia.com/terms/d/deep-learning.asp#: :text=Deep learning is an AI,is both unstructured and unlabeled.
  * [9] Luxand. (n.d.). Face recognition widget for your website. https://luxand.cloud/widget
  * [10] IDentification, E. (n.d.). SmileID. https://www.electronicid.eu/en/solutions/smileid
  * [11] T. Nyein and A. N. Oo, “University Classroom Attendance System Using FaceNet and Support Vector Machine,” 2019 Int. Conf. Adv. Inf. Technol. ICAIT 2019, pp. 171–176, 2019, doi: 10.1109/AITC.2019.8921316.
  * [12] B. Prihasto et al., “A survey of deep face recognition in the wild,” 2016 Int. Conf. Orange Technol. ICOT 2016, vol. 2018-Janua, pp. 76–79, 2018, doi: 10.1109/ICOT.2016.8278983.
  * [13] S. I. Serengil and A. Ozpinar, “LightFace: A Hybrid Deep Face Recognition Framework,” pp. 2–6, 2020.
  * [14] O. M. Parkhi, A. Vedaldi, and A. Zisserman, “Deep Face Recognition,” 2015, pp. 41.1- 41.12, doi: 10.5244/c.29.41.
  * [15] Y. Taigman, M. Yang, M. Ranzato, and L. Wolf, “DeepFace: Closing the gap to human- level performance in face verification,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2014, pp. 1701–1708, doi: 10.1109/CVPR.2014.220.
  * [16] T. Baltrusaitis, P. Robinson, and L. P. Morency, “OpenFace: An open source facial be- havior analysis toolkit,” in 2016 IEEE Winter Conference on Applications of Computer Vision, WACV 2016, 2016, pp. 1–10, doi: 10.1109/WACV.2016.7477553.
  * [17] F. Schroff, D. Kalenichenko, and J. Philbin, “FaceNet: A unified embedding for face recognition and clustering,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2015, vol. 07-12-June, pp. 815–823, doi:10.1109/CVPR.2015.7298682.
  * [18] “Geogia Tech Face Database.” http://www.anefian.com/research/face_rec o.htm.
  * [19] Mondal, S. K., Mukhopadhyay, I., Dutta, S. (2020). Review and Comparison of Face Detection Techniques. Advances in Intelligent Systems and Computing
  * [20] Zhao, Q., and Zhang, S. (2011). A face detection method based on corner verifying. 2011 International Conference on Computer Science and Service System, CSSS 2011 - Proceedings, 2854–2857. https://doi.org/10.1109/CSSS.2011.5974784
  * [21] D. Sandberg, “Facenet,” 2018. https://github.com/davidsandberg/facenet.
  * [22] H. Tania, “keras-facenet,” 2018. https://github.com/nyoki-mtl/keras-facenet.