# Optimal consensus control models on the sphere

Hui Huang
Institute of Mathematics and Scientific Computing, University of Graz,
Universitätspl. 3, 8010 Graz, Austria<EMAIL_ADDRESS>and  Hansol Park
Department of Mathematics, Simon Fraser University, 8888 University Dr,
Burnaby, BC V5A 1S6, Canada<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In this paper, we investigate the consensus models on the sphere with control
signals, where both the first and second order systems are considered. We
provide the existence of the optimal control-trajectory pair and derive the
first order optimality condition taking the form of the Pontryagin Minimum
Principle. Numeric simulations are also presented to show that the obtained
optimal control can help to accelerate the process of reaching a consensus.

###### Key words and phrases:

optimal control, swarm sphere model, aggregation, synchronization, Pontryagin
Minimum Principle

###### 1991 Mathematics Subject Classification:

49J15, 34D06

Acknowledgment. The work of H. Park is supported by Pacific Institute for the
Mathematical Science (PIMS), Canada postdoctoral fellowship.

##  1\. Introduction

Large systems of interacting particles arise in the study of collective
behaviours of biological and physical systems on manifolds, such as nematic
patterns on a sphere [11], application to launching unmanned spacecrafts [5],
and crystals on a cylinder [6]. It is receiving lots of attention due to the
appearance of a consensus emergence of these particle systems. This paper
addresses centralized control problems for one of the well known consensus
models on the sphere, i.e. the swarm sphere model [10], whose first order form
is given by:

(1.1)
$\displaystyle\begin{cases}\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}x_{i}=\Omega_{i}x_{i}+\frac{\kappa}{N}\sum_{k=1}^{N}\left(x_{k}-\frac{\langle
x_{i},x_{k}\rangle}{\|x_{i}\|^{2}}x_{i}\right),\\\
x_{i}(0)=x_{i}^{0}\in\mathbb{S}^{d-1},\quad\forall~{}i\in[N]:=\\{1,2,\cdots,N\\},\end{cases}$

where $\Omega_{i}\in\mathrm{Skew}(d):=\\{A\in\mathbb{R}^{d\times
d}:A^{\top}=-A\\}$ is the natural frequency of the $i$-th particle, $\kappa$
is the coupling strength, $x_{i}^{0}$ is the initial position of the $i$-th
particle, $N$ is the number of particles, and $\|\cdot\|$ represents the
standard Euclidean norm. Adding the inertia (mass) term to system (1.1) as in
[8] we can obtain the second order model satisfying:

(1.2)
$\displaystyle\begin{cases}\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}x_{i}=v_{i},\\\
\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}v_{i}=-\frac{\gamma}{m}v_{i}-\frac{\|v_{i}\|^{2}}{\|x_{i}\|^{2}}x_{i}+\frac{1}{m}\Omega_{i}x_{i}+\frac{\kappa}{mN}\sum_{k=1}^{N}\left(x_{k}-\frac{\langle
x_{i},x_{k}\rangle}{\|x_{i}\|^{2}}x_{i}\right),\\\ \displaystyle
x_{i}(0)=x_{i}^{0}\in\mathbb{S}^{d-1},\quad
v_{i}(0)=\frac{\mathrm{d}}{\mathrm{d}t}x_{i}\Big{|}_{t=0+}=v_{i}^{0}\in
T_{x_{i}^{0}}\mathbb{S}^{d-1}\quad\forall~{}i\in[N],\end{cases}$

where $m$ is the mass, $\gamma$ is the friction coefficients, and $v_{i}^{0}$
is the initial velocity of the $i$-th particle. Actually, the systems (1.1)
and (1.2) can be also seen as generalized Kuramoto models on the sphere.
According to [8], if the identical natural frequencies satisfies
$\Omega_{i}\equiv O_{d-1}$ for all $i\in[N]$, then the emergent dynamics for
both systems (1.1) and (1.2) with generic initial can be observed, namely it
satisfies

$\lim_{t\to\infty}\|x_{i}(t)-x_{j}(t)\|=0\quad\forall~{}i,j\in[N].$

In this context the consensus is understood as a travelling formulation in
which every particle has the same position. However this behaviour strongly
depends on the initial configuration of the particle system. In the present
work we are interested in the design of centralized control signals enforcing
consensus emergence in systems (1.1) and (1.2) in order to generate an
external intervention able to steer the system towards a desired
configuration. Very related to this work, [1, 4, 3] study the problem of
consensus control for Cucker–Smale type models. Meanwhile, according to [9],
the Kuramoto model (position synchronization model) can be derived from the
Cucker–Smale model (velocity alignment model). So in this work we are aiming
to extend those results on velocity alignment as in [1] to our position
synchronization models (1.1) and (1.2).

##  2\. Swarm sphere models with controls

In this section we consider both the first order and second order swarm sphere
models with control signals.

###  2.1. Second order model

We consider a set of $N$ particles with state $(x_{i}(t),v_{i}(t))\in
T\mathbb{S}^{d-1}\subset\mathbb{R}^{d}\times\mathbb{R}^{d}$ moving on a sphere
via system (1.2) with $\Omega_{i}\equiv O_{d-1}$ for all $i\in[N]$. We are
interested in the study of consensus emergence, i.e. the convergence towards a
configuration in which
$x_{i}=\bar{x}=\frac{1}{N}\sum_{j=1}^{N}x_{j},~{}\forall\,i\in[N]\,.$ In
particular we are concerned with inducing the consensus through the synthesis
of an external forcing term $\mathbf{u}(t):=(u_{1}(t),\dots,u_{N}(t))^{\top}$
in the form of

(2.3)
$\displaystyle\begin{cases}\displaystyle\frac{\mathrm{d}x_{i}}{dt}=v_{i},\\\
\displaystyle\frac{\mathrm{d}v_{i}}{dt}=-\frac{\|v_{i}\|^{2}}{\|x_{i}\|^{2}}x_{i}-\frac{\gamma}{m}v_{i}+\frac{\kappa}{mN}\sum_{j=1}^{N}\left(x_{j}-\frac{\langle
x_{i},x_{j}\rangle}{\|x_{i}\|^{2}}x_{i}\right)+\left(u_{i}-\frac{\langle
u_{i},x_{i}\rangle x_{i}}{\|x_{i}\|^{2}}\right)\\\ \displaystyle
x_{i}(0)=x_{i}^{0}\in\mathbb{S}^{d-1},\quad
v_{i}(0)=\frac{\mathrm{d}}{\mathrm{d}t}x_{i}\Big{|}_{t=0+}=v_{i}^{0}\in
T_{x_{i}^{0}}\mathbb{S}^{d-1}\quad\forall~{}i\in[N],\end{cases}$

where the control signals $u_{i}\in L^{2}([0,T];\mathbb{R}^{d})=:\mathcal{U}$.
Formally, for $T>0$ and given a set of admissible control signals
$\textbf{u}\in\mathcal{U}^{N}$ for the entire population, it holds that
$\|u_{i}\|_{2}\leq\max_{i\in[N]}\\{\|u_{i}\|_{2}\\}=:M$ for all $i\in[N]$. Our
goal is then to seek a solution to the minimization problem

(2.4)
$\displaystyle\min\limits_{\mathbf{u}(\cdot)\in\mathcal{U}^{N}}\mathcal{J}(\mathbf{u}(\cdot);\mathbf{x}(0),\mathbf{v}(0)):=\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|x_{j}-\bar{x}\|^{2}dt+\lambda\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|u_{j}\|^{2}dt\,,$

with some regularization parameter $\lambda>0$. Here we have used the notation
$\mathbf{x}(t):=(x_{1}(t),\dots,x_{N}(t))^{\top}$ and
$\mathbf{v}(t):=(v_{1}(t),\dots,v_{N}(t))^{\top}$.

######  Theorem 2.1.

For any given $T>0$ and $\mathbf{u}(\cdot)\in\mathcal{U}^{N}$, assume the
initial data $(\mathbf{x}(0),\mathbf{v}(0))$ and parameters
$m,\gamma,\kappa,T$ satisfy

$\frac{m}{\gamma}\left(\mathcal{V}(0)+\frac{2\kappa
T}{m}+2MT^{\frac{1}{2}}\right)\left(\exp\left(\frac{\gamma
T}{m}\right)-1\right)<1\,,$

then there exists a pathwise unique global solution
$\\{(x_{i},v_{i})\\}_{i=1}^{N}$ to the Kuramoto system (2.3) up to time $T$.
Moreover for all $i\in[N]$ and $t\in[0,T]$ it holds that

(2.5) $\|x_{i}(t)\|=1,\quad\langle x_{i}(t),v_{i}(t)\rangle=0$

and

(2.6) $\sup\limits_{t\in[0,T]}\mathcal{V}(t)\leq\frac{\exp\left(\frac{\gamma
T}{m}\right)\left(\mathcal{V}(0)+\frac{2\kappa
T}{m}+2MT^{\frac{1}{2}}\right)}{1-\frac{m}{\gamma}\left(\mathcal{V}(0)+\frac{2\kappa
T}{m}+2MT^{\frac{1}{2}}\right)\left(\exp\left(\frac{\gamma
T}{m}\right)-1\right)}=:C_{V}\,,$

where $\mathcal{V}(t)=\max\limits_{i=1,\dots,N}\|v_{i}(t)\|$.

###### Proof.

Let $\phi$ be a map on $\mathbb{R}^{d}$ with bounded derivatives of all orders
such that $\phi(x)=\frac{x}{\|x\|^{2}}$ for all $x$ with
$\|x\|\geq\frac{1}{2}$. Then we consider the following regularized system

(2.7)
$\displaystyle\begin{cases}\displaystyle\frac{\mathrm{d}x_{i}}{\mathrm{d}t}=v_{i},\\\
\displaystyle\frac{\mathrm{d}v_{i}}{\mathrm{d}t}=-\phi(x_{i})\|v_{i}\|^{2}-\frac{\gamma}{m}v_{i}+\frac{\kappa}{m}\frac{1}{N}\sum_{j=1}^{N}(x_{j}-\langle
x_{i},x_{j}\rangle\phi(x_{i}))+u_{i}-\langle u_{i},x_{i}\rangle\phi(x_{i})\\\
\displaystyle x_{i}(0)=x_{i}^{0}\in\mathbb{S}^{d-1},\quad
v_{i}(0)=\frac{\mathrm{d}}{\mathrm{d}t}x_{i}\Big{|}_{t=0+}=v_{i}^{0}\in
T_{x_{i}^{0}}\mathbb{S}^{d-1}\quad\forall~{}i\in[N],\end{cases}$

It is obvious that the coefficients are local Lipschitz, so one has local
existence and uniqueness up to some time $\tau\in[0,T]$.

Next we prove the global existence up to time $T$. Actually, as long as
$\|x_{i}\|\geq\frac{1}{2}$ one has

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\langle
x_{i},v_{i}\rangle=\|v_{i}\|^{2}+\left\langle
x_{i},\frac{\mathrm{d}v_{i}}{\mathrm{d}t}\right\rangle=\|v_{i}\|^{2}-\|v_{i}\|^{2}-\frac{\gamma}{m}\langle
x_{i},v_{i}\rangle=-\frac{\gamma}{m}\langle x_{i},v_{i}\rangle\,,$

which implies $\langle x_{i}(t),v_{i}(t)\rangle=\langle
x_{i}(0),v_{i}(0)\rangle e^{-\frac{\gamma}{m}t}=0$ for all $t\in[0,T]$ since
$\langle x_{i}(0),v_{i}(0)\rangle=0$. Then we have

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\|x_{i}\|^{2}=2\langle
x_{i},v_{i}\rangle=0\,,$

which following the initial condition $\|x_{i}(0)\|=1$ leads to
$\|x_{i}(t)\|=1$ for all $t\in[0,T]$. In addition, notice that

$\displaystyle\|v_{i}(t)\|\leq\|v_{i}(0)\|+\int_{0}^{t}(\|v_{i}(s)\|^{2}+\frac{\gamma}{m}\|v_{i}(s)\|)ds+\frac{2\kappa
T}{m}+2\int_{0}^{t}\|u_{i}(s)\|ds\,.$

Using Gronwall’s lemma one has

$\displaystyle\sup\limits_{t\in[0,T]}\|v_{i}(t)\|$
$\displaystyle\leq\frac{\exp(\frac{\gamma T}{m})(\|v_{i}(0)\|+\frac{2\kappa
T}{m}+2\int_{0}^{T}\|u^{i}(s)\|ds)}{1-\frac{m}{\gamma}(\|v_{i}(0)\|+\frac{2\kappa
T}{m}+2\int_{0}^{T}\|u^{i}(s)\|ds)(\exp(\frac{\gamma
T}{m})-1)}\leq\frac{\exp(\frac{\gamma T}{m})(\|v_{i}(0)\|+\frac{2\kappa
T}{m}+2MT^{\frac{1}{2}})}{1-\frac{m}{\gamma}(\|v_{i}(0)\|+\frac{2\kappa
T}{m}+2MT^{\frac{1}{2}})(\exp(\frac{\gamma T}{m})-1)}\,.$

This means that if initially $\frac{m}{\gamma}(\|v_{i}(0)\|+\frac{2\kappa
T}{m}+2MT^{\frac{1}{2}})(\exp(\frac{\gamma T}{m})-1)<1$, then we have global
existence and pathwise uniqueness for (2.7) up to time $T$.

Now the solution to (2.7) for the given $\phi$ is a solution to (2.3) since
$\|x_{i}\|=1$ for all $i=1,\dots,N$ and $t\in[0,T]$, which provides global
existence to (2.3). If we consider two solutions to (2.3) for the same initial
data, then they satisfies $\|x_{i}\|=1$. So they are also solutions to the
regularized system (2.7), for which pathwise uniqueness holds. Hence they are
equal, which completes the proof. ∎

From (2.5), now we can assume $\|x_{i}(t)\|=1$ for all $t\geq 0$ and $i\in[N]$
if $\\{(x_{i},v_{i})\\}_{i=1}^{N}$ satisfy (2.3), and one can prove the
existence of the optimal control-trajectory pair:

######  Theorem 2.2.

Under the same assumptions as in Theorem 2.1, there exists some control
$u_{i}^{*}\in L^{2}(0,T;\mathbb{R}^{d})$, $i\in[N]$ and the corresponding
$\\{(x_{i}^{*},v_{i}^{*})\\}_{i=1}^{N}$ trajectories solving the optimal
control problem (2.3)-(2.4).

###### Proof.

For any given $u_{i}\in L^{2}(0,T;\mathbb{R}^{d})$, $i\in[N]$, by Theorem 2.1
there exists a corresponding solution $\\{(x_{i}^{u},v_{i}^{u})\\}_{i=1}^{N}$
to (2.3). Note that $u_{i}=0\in L^{\infty}(0,T;\mathbb{R}^{d})$, so that

$\mathcal{J}(\mathbf{0};\mathbf{x}(0),\mathbf{v}(0))=\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|x_{j}^{0}-\bar{x}^{0}\|^{2}\mathrm{d}t\leq
4T$

because $\|x_{i}^{0}\|=1$, where $\\{(x_{i}^{0},v_{i}^{0})\\}_{i=1}^{N}$ is
the solution to (2.3) with given $u_{i}=0$. Since
$\mathcal{J}(\mathbf{u}(\cdot);\mathbf{x}(0),\mathbf{v}(0))\geq 0$ for all
$\mathbf{u}(\cdot)\in\mathcal{U}^{N}$, it holds that

$0\leq\min\limits_{\mathbf{u}(\cdot)\in\mathcal{U}^{N}}\mathcal{J}(\mathbf{u}(\cdot);\mathbf{x}(0),\mathbf{v}(0))\leq\mathcal{J}(\mathbf{0};\mathbf{x}(0),\mathbf{v}(0))\leq
4T\,.$

By the definition of the infimum, we know that there exists a sequence of
controls $(\mathbf{u}^{n})_{n\in\mathbb{N}}\subset\mathcal{U}^{N}$ with
corresponding $(\mbox{\boldmath$x$}^{u^{n}},\mbox{\boldmath$v$}^{u^{n}})$
solving (2.3), such that

$0\leq\min\limits_{\mathbf{u}(\cdot)\in\mathcal{U}^{N}}\mathcal{J}(\mathbf{u}(\cdot);\mathbf{x}(0),\mathbf{v}(0))\leq\mathcal{J}(\mathbf{u}^{n}(\cdot);\mathbf{x}(0),\mathbf{v}(0))\leq\min\limits_{\mathbf{u}(\cdot)\in\mathcal{U}^{N}}\mathcal{J}(\mathbf{u}(\cdot);\mathbf{x}(0),\mathbf{v}(0))+\frac{1}{n}\,,$

and so

$\lim_{n\to\infty}\mathcal{J}(\mathbf{u}^{n}(\cdot);\mathbf{x}(0),\mathbf{v}(0))=\min\limits_{\mathbf{u}(\cdot)\in\mathcal{U}^{N}}\mathcal{J}(\mathbf{u}(\cdot);\mathbf{x}(0),\mathbf{v}(0))\,.$

Notice that

$\lambda\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|u_{j}^{n}\|^{2}\mathrm{d}t\leq\mathcal{J}(\mathbf{u}^{n}(\cdot);\mathbf{x}(0),\mathbf{v}(0))<\infty\,,$

and by Banach-Alaoglu theorem, for all $i$ there exists a subsequence
$(u_{i}^{n_{k}})_{k\in\mathbb{N}}$ and $u_{i}^{*}\in
L^{2}(0,T;\mathbb{R}^{d})$ such that

(2.8)
$u_{i}^{k}:=u_{i}^{n_{k}}\underset{k\rightarrow+\infty}{\rightharpoonup}u_{i}^{*}\quad\text{
in }L^{2}(0,T;\mathbb{R}^{d})\,.$

For the corresponding solutions
$(\mbox{\boldmath$x$}^{k},\mbox{\boldmath$v$}^{k})_{k\in\mathbb{N}}:=(\mbox{\boldmath$x$}^{u^{n_{k}}},\mbox{\boldmath$v$}^{u^{n_{k}}})_{k\in\mathbb{N}}$,
we have from Theorem 2.1 that

$\displaystyle\max\limits_{i=1,\dots,N}\|\dot{v_{i}}^{k}(t)\|$
$\displaystyle\leq\max\limits_{i=1,\dots,N}\|v_{i}^{k}(t)\|^{2}+\frac{\gamma}{m}\max\limits_{i=1,\dots,N}\|v_{i}^{k}(t)\|+\frac{2\kappa}{m}+2\max\limits_{i=1,\dots,N}\|u_{i}^{k}(t)\|\leq
C_{V}^{2}+\frac{C_{V}\gamma}{m}+\frac{2\kappa}{m}+2M\,.$

This combining with (2.6) implies the equi-boundedness and equi-absolute
continuity of $v_{i}^{k}(t)$ uniformly with respect to $k$, for all
$i=1,\dots,N$. This also yields the equi-Lispchitzanity of $x_{i}^{k}(t)$. By
Ascoli-Arzela theorem there exits a subsequence, again renamed
$(\mbox{\boldmath$x$}^{k},\mbox{\boldmath$v$}^{k})_{k\in\mathbb{N}}$ and an
absolutely continuous trajectory
$(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$v$}^{*})$ in $[0,T]$ such that for
$k\to\infty$:

(2.9) $\displaystyle\begin{cases}x_{i}^{k}\rightarrow x_{i}^{*},\mbox{ in
}[0,T],\mbox{ for all }i=1,\cdots,N,\\\ v_{i}^{k}\rightarrow v_{i}^{*},\mbox{
in }[0,T],\mbox{ for all }i=1,\cdots,N,\\\
\dot{x}_{i}^{k}\rightarrow\dot{x}_{i}^{*},\mbox{ in }[0,T],\mbox{ for all
}i=1,\cdots,N,\\\ \dot{v}_{i}^{k}\rightharpoonup\dot{v}_{i}^{*},\mbox{ in
}L^{2}(0,T;\mathbb{R}^{d}),\mbox{ for all }i=1,\cdots,N\,.\end{cases}$

Thus it is easy to see that

(2.10) $\frac{\mathrm{d}x_{i}^{*}}{\mathrm{d}t}=v_{i}^{*}\mbox{ and
}\lim\limits_{k\to\infty}\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|x_{j}^{k}-\bar{x}^{k}\|^{2}\mathrm{d}t=\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|x_{j}^{*}-\bar{x}^{*}\|^{2}\mathrm{d}t\,.$

Moreover, one notice that for all $\psi\in L^{2}(0,T;\mathbb{R}^{d})$

$\displaystyle\int_{0}^{T}\psi\dot{v}_{i}^{k}\mathrm{d}t=\int_{0}^{T}\left(-\frac{\|v_{i}^{k}\|^{2}}{\|x_{i}^{k}\|^{2}}\langle
x_{i}^{k},\psi\rangle-\frac{\gamma}{m}\langle
v_{i}^{k},\psi\rangle+\frac{\kappa}{m}\frac{1}{N}\sum_{j=1}^{N}\left(\langle
x_{j}^{k},\psi\rangle-\frac{\langle
x_{i}^{k},x_{j}^{k}\rangle}{\|x_{i}^{k}\|^{2}}\langle
x_{i}^{k},\psi\rangle\right)+\langle u_{i}^{k},\psi\rangle-\frac{\langle
u_{i}^{k},x_{i}^{k}\rangle\langle
x_{i}^{k},\psi\rangle}{\|x_{i}^{k}\|^{2}}\right)\mathrm{d}t$

Let $k\to\infty$, and by using (2.8) and (2.9) we have

$\displaystyle\int_{0}^{T}\psi\dot{v}_{i}^{*}\mathrm{d}t=\int_{0}^{T}\left(-\frac{\|v_{i}^{*}\|^{2}}{\|x_{i}^{*}\|^{2}}\langle
x_{i}^{*},\psi\rangle-\frac{\gamma}{m}\langle
v_{i}^{*},\psi\rangle+\frac{\kappa}{m}\frac{1}{N}\sum_{j=1}^{N}\left(\langle
x_{j}^{*},\psi\rangle-\frac{\langle
x_{i}^{*},x_{j}^{*}\rangle}{|x_{i}^{*}|^{2}}\langle
x_{i}^{*},\psi\rangle\right)+\langle u_{i}^{*},\psi\rangle-\frac{\langle
u_{i}^{*},x_{i}^{*}\rangle\langle
x_{i}^{*},\psi\rangle}{\|x_{i}^{*}\|^{2}}\right)\mathrm{d}t\,,$

which leads to

(2.11)
$\frac{\mathrm{d}v_{i}^{*}}{\mathrm{d}t}=-\frac{\|v_{i}^{*}\|^{2}}{\|x_{i}^{*}\|^{2}}x_{i}^{*}-\frac{\gamma}{m}v_{i}^{*}+\frac{\kappa}{m}\frac{1}{N}\sum_{j=1}^{N}\left(x_{j}^{*}-\frac{\langle
x_{i}^{*},x_{j}^{*}\rangle}{\|x_{i}^{*}\|^{2}}x_{i}^{*}\right)+u_{i}^{*}-\frac{\langle
u_{i}^{*},x_{i}^{*}\rangle x_{i}^{*}}{\|x_{i}^{*}\|^{2}}\quad\mbox{a.e.}\,.$

Since $(u_{i}^{k})_{k\in\mathbb{N}}\subset L^{2}(0,T;\mathbb{R}^{d})$
converges weakly to $u_{i}^{*}$ for all $i\in[N]$, we also have

$\lambda\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|u_{j}^{*}\|^{2}\mathrm{d}t\leq\lim\inf\limits_{k\to\infty}\lambda\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|u_{j}^{k}\|^{2}\mathrm{d}t$

by the weak lower-semicontinuity of the $L^{2}$-norm. This implies that

$\displaystyle\mathcal{J}(\mathbf{u}^{*}(\cdot);\mathbf{x}(0),\mathbf{v}(0))=\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|x_{j}^{*}-\bar{x}^{*}\|^{2}\mathrm{d}t+\lambda\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|u_{j}^{*}\|^{2}\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle\lim\inf\limits_{k\to\infty}\left(\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|x_{j}^{k}-\bar{x}^{k}\|^{2}\mathrm{d}t+\lambda\int_{0}^{T}\frac{1}{N}\sum_{j=1}^{N}\|u_{j}^{k}\|^{2}\mathrm{d}t\right)$
$\displaystyle=$
$\displaystyle\lim\inf\limits_{k\to\infty}\mathcal{J}(\mathbf{u}^{k}(\cdot);\mathbf{x}(0),\mathbf{v}(0))=\lim_{n\to\infty}\mathcal{J}(\mathbf{u}^{n}(\cdot);\mathbf{x}(0),\mathbf{v}(0))=\min\limits_{\mathbf{u}(\cdot)\in\mathcal{U}^{N}}\mathcal{J}(\mathbf{u}(\cdot);\mathbf{x}(0),\mathbf{v}(0))\,.$

This together with (2.10) and (2.11) implies the limit
$(\textbf{x}^{*},\textbf{v}^{*},\textbf{u}^{*})$ is a solution to the optimal
control problem (2.3)-(2.4). ∎

While the existence of $(\mathbf{x}^{*},\mathbf{v}^{*},\mathbf{u}^{*})$ to the
optimal control problem (2.3)-(2.4) has been obtained in Theorem 2.2, the
Pontryagin Minimum Principle [7] yields first-order necessary conditions for
the optimal control. Let
$(p_{i}^{*}(t),q_{i}^{*}(t))\in\mathbb{R}^{d}\times\mathbb{R}^{d}$ be adjoint
variables associated to $(x_{i}^{*},v_{i}^{*})$, and we set
$\mathbf{p}^{*}=\\{p_{i}^{*}\\}_{i=1}^{N}$,
$\mathbf{q}^{*}=\\{q_{i}^{*}\\}_{i=1}^{N}$. Then the optimality system
consists of a solution
$(\mathbf{x}^{*},\mathbf{v}^{*},\mathbf{u}^{*},\mathbf{p}^{*},\mathbf{q}^{*})$
satisfying (2.3) along with the adjoint equations

(2.12)
$\displaystyle\begin{cases}\displaystyle-\frac{\mathrm{d}p_{i}^{*}}{\mathrm{d}t}=-\|v_{i}^{*}\|^{2}q_{i}^{*}+\frac{\kappa}{mN}\sum_{j=1}^{N}\left(q_{j}^{*}-\langle
x_{i}^{*},x_{j}^{*}\rangle q_{i}^{*}-\langle x_{i}^{*},q_{i}^{*}\rangle
x_{j}^{*}-\langle x_{j}^{*},q_{j}^{*}\rangle x_{j}^{*}\right)-q_{i}^{*}\langle
u_{i}^{*},x_{i}^{*}\rangle-u_{i}^{*}\langle
x_{i}^{*},q_{i}^{*}\rangle-\frac{2}{N}(\langle\bar{x}^{*},\bar{x}_{i}^{*}\rangle\bar{x}^{*}-x_{i}^{*})\,,\\\
\displaystyle-\frac{\mathrm{d}q_{i}^{*}}{\mathrm{d}t}=p_{i}^{*}-2\langle
x_{i}^{*},q_{i}^{*}\rangle v_{i}^{*}-\frac{\gamma}{m}q_{i}^{*}\,,\\\
p_{i}^{*}(T)=0,q_{i}^{*}(T)=0,\quad i\in[N]\,,\end{cases}$

and the optimality condition

$\mathbf{u}^{*}=\arg\min_{\mathbf{w}\in\mathbb{R}^{dN}}\sum_{j=1}^{N}\left(\left\langle
q_{j}^{*},\frac{\mathrm{d}v_{j}^{*}}{\mathrm{d}t}\right\rangle+\frac{\lambda}{N}|w_{j}|^{2}\
\right)=-\frac{N}{2\lambda}\left[q_{j}^{*}-\langle q_{j}^{*},x_{j}^{*}\rangle
x_{j}^{*}\right]_{j=1}^{N}.$

Recall that the gradient of the functional $\mathcal{J}$ introduces in (2.4)
is given as follows:

(2.13)
$\displaystyle\nabla\mathcal{J}=\frac{2\lambda}{N}\mathbf{u}+\left[q_{j}-\langle
q_{j},x_{j}\rangle
x_{j}\right]_{j=1}^{N}=\left[\frac{2\lambda}{N}u_{j}+(q_{j}-\langle
q_{j},x_{j}\rangle x_{j})\right]_{j=1}^{N}.$

We will apply this gradient form to the gradient descent method in Section
3.2.

###  2.2. First order model

We are also interested in the following first-order control problem:

(2.14)
$\displaystyle\begin{cases}\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}x_{i}=\frac{\kappa}{N}\sum_{k=1}^{N}\left(x_{k}-\langle
x_{i},x_{k}\rangle x_{i}\right)+u_{i}-\langle u_{i},x_{i}\rangle x_{i},\\\
x_{i}(0)=x_{i}^{0}\in\mathbb{S}^{d-1}\quad\forall~{}i\in[N],\end{cases}$

with the following payoff functional

(2.15)
$\tilde{\mathcal{J}}(\mathbf{u}(\cdot);\mathbf{x}(0))=\int_{0}^{T}\frac{1}{N}\sum_{i=1}^{N}\left(\|x_{i}-\bar{x}\|^{2}+\lambda\|u_{i}\|^{2}\right)\mathrm{d}t.$

The existence of the above optimal control problem can be obtained similarly
as the second order model, so here we omit the proofs and only present the
theorems:

######  Theorem 2.3.

For any $T>0$ and given $\mathbf{u}(\cdot)\in\mathcal{U}^{N}$, there exists a
pathwise unique global solution $\\{x_{i}\\}_{i=1}^{N}$ to the Kuramoto system
(2.14) up to time $T$. Moreover for all $i\in[N]$ and $t\in[0,T]$ it holds
that $\|x_{i}(t)\|=1$.

######  Theorem 2.4.

There exists some control $u_{i}^{*}\in L^{2}(0,T;\mathbb{R}^{d})$, $i\in[N]$
and the corresponding $\\{x_{i}^{*}\\}_{i=1}^{N}$ trajectories solving the
optimal control problem (2.14)-(2.15).

Let $\\{p_{i}^{*}\\}_{i=1}^{N}$ be adjoint variables associated to
$\\{x_{i}^{*}\\}_{i=1}^{N}$. The corresponding PMP equation is given by

(2.16)
$\displaystyle-\frac{\mathrm{d}}{\mathrm{d}t}p_{i}^{*}=\frac{\kappa}{N}\sum_{j=1}^{N}(p_{j}^{*}-\langle
x_{i}^{*},p_{i}^{*}\rangle x_{j}^{*}-\langle x_{j}^{*},p_{j}^{*}\rangle
x_{j}^{*}-\langle x_{i}^{*},x_{j}^{*}\rangle p_{j}^{*})-\langle
u_{i}^{*},x_{i}^{*}\rangle p_{i}^{*}-\langle x_{i}^{*},p_{i}^{*}\rangle
u_{i}^{*}+\frac{2}{N}(x_{i}^{*}-\bar{x}^{*}\langle
x_{i}^{*},\bar{x}^{*}\rangle)\,,$

with the optimality condition

$\textbf{u}^{*}=\arg\min_{\textbf{w}\in\mathbb{R}^{dN}}\sum_{i=1}^{N}\left(\left\langle
p_{j}^{*},\frac{\mathrm{d}x_{j}^{*}}{\mathrm{d}t}\right\rangle+\frac{\lambda}{N}\|w_{i}\|^{2}\right)=-\frac{N}{2\lambda}[p_{j}^{*}-\langle
p_{j}^{*},x_{j}^{*}\rangle x_{j}^{*}]_{j=1}^{N}.$

Also, the gradient of functional $\tilde{\mathcal{J}}$ introduced in (2.15)
can be expressed as

(2.17)
$\displaystyle\nabla\tilde{\mathcal{J}}=\frac{2\lambda}{N}\mathbf{u}+[p_{j}+\langle
p_{j},x_{j}\rangle x_{j}]_{j=1}^{N}.$

We will apply this gradient form to the gradient descent method in Section
3.1.

##  3\. Algorithms and numeric simulations

In this section, we provide numeric simulations of controlled systems proposed
in Section 2 in order to give a simple and immediate illustration of how the
optimal control signal can be used to accelerate the process of reaching a
consensus.

###  3.1. First order model with control

Firstly, we consider the first order control problem (2.14)-(2.15). To
minimize the payoff functional $\tilde{\mathcal{J}}$ defined in (2.15), we
apply the gradient descent with Barzilai–Borwein method [2] with the explicit
form of $\nabla\tilde{\mathcal{J}}$ given in (2.17).

Algorithm 1 An algorithm with caption

$tol>0$, $k_{max}$, $\mathbf{u}^{0}$, $\mathbf{u}^{-1}$.

$k=0$;

while $\|\nabla\tilde{\mathcal{J}}\|>tol$ and $k<k_{max}$ do

1) Obtain $\mathbf{x}^{k}$ from (2.14) with $\mathbf{u}^{k}$;

2) Obtain $\mathbf{p}^{k}$ from (2.16) with $\mathbf{x}^{k}$ and
$\mathbf{u}^{k}$;

3) Compute the learning rate based on the Barzilai–Borwein method:
$\alpha_{k}:=\frac{\langle\mathbf{u}^{k}-\mathbf{u}^{k-1},\nabla\tilde{\mathcal{J}}(\mathbf{u}^{k})-\nabla\tilde{\mathcal{J}}(\mathbf{u}^{k-1})\rangle}{\|\nabla\tilde{\mathcal{J}}(\mathbf{u}^{k})-\nabla\tilde{\mathcal{J}}(\mathbf{u}^{k-1})\|^{2}}\,;$

4) Update
$\mathbf{u}^{k+1}=\mathbf{u}^{k}-\alpha_{k}\nabla\tilde{\mathcal{J}}(\mathbf{u}^{k})$;

5) $k:=k+1$;

end while

In Algorithm 1, $k_{max}$ is the maximum of the number of iteration, $tol$ is
the tolerance of $\|\nabla\tilde{\mathcal{J}}\|$, and we use the Runge-Kutta
fourth order methods in Step 1) and Step 2).

In Figure 1, we compare the optimal controlled system (2.14)-(2.15) and the
control-free swarm sphere model (1.1) with the same initial data and
parameters being set as

(3.18) $\displaystyle N=20,\quad d=3,\quad\Delta t=0.01,\quad
T=4,\quad\lambda=0.1,\quad\kappa=0.5.$

As it is shown in Figure 1 (a), the controlled system (blue) under an
approximated optimal control $\mathbf{u}^{*}$ found with Algorithm 1
approaches to a consensus state much faster than the control-free model (red).
This can also be seen in Figure 1 (b) that while the particles of the
controlled system reaches a consensus, particles of the control-free system
just move small distances. In summary, for the first order model, the
controlled system reaches consensus much faster than the uncontrolled system.

|
---|---
(a) Variations of positions | (b) Trajectories of particles
Figure 1. Controlled (blue) vs. control-free (red) first order dynamics.
Figure (a) plots the time-evolution of the variations of positions defined as
$\frac{1}{N}\sum_{i=1}^{N}\|x_{i}-\bar{x}\|^{2}$. Figure (b) shows the
trajectories of two systems, where both of them start from the same green
initial points. At the end time $T$, the optimal controlled particles reach
the unique blue consensus point, while the uncontrolled particles move only
small distances to red points (no consensus is obtained).

###  3.2. Second order model with control

Now, we consider the second order control problem (2.3)-(2.4). To minimize the
payoff functional $\mathcal{J}$, we use the explicit form of
$\nabla\mathcal{J}$ introduced in (2.13). Same parameters given by (3.18) are
used here with additionally setting the remained parameters as $m=1$ and
$\gamma=1$. In Figure 2 we give a comparison of the second order optimal
control dynamics (2.3)-(2.4) and its control-free counterpart (1.2).

|  |
---|---|---
(a) Variation of positions | (b) Variations of velocities | (c) Trajectories of particles
Figure 2. Controlled (blue) vs. control-free (red) second order dynamics.
Figure (a) and (b) plot the time-evolution of the variations of
positions/velocities, i.e. $\frac{1}{N}\sum_{i=1}^{N}\|x_{i}-\bar{x}\|^{2}$
and $\frac{1}{N}\sum_{i=1}^{N}\|v_{i}-\bar{v}\|^{2}$ respectively. Figure (c)
shows the trajectories of two systems.

## References

  * [1] R. Bailo, M. Bongini, J. A. Carrillo, and D. Kalise.  Optimal consensus control of the Cucker-Smale model.  IFAC-PapersOnLine, 51(13):1–6, 2018.
  * [2] J. Barzilai and J. M. Borwein.  Two-point step size gradient methods.  IMA journal of numerical analysis, 8(1):141–148, 1988.
  * [3] M. Bongini, M. Fornasier, and D. Kalise.  (un) conditional consensus emergence under perturbed and decentralized feedback controls.  Discrete & Continuous Dynamical Systems, 35(9):4071, 2015.
  * [4] M. Caponigro, M. Fornasier, B. Piccoli, and E. Trélat.  Sparse stabilization and optimal control of the Cucker-Smale model.  Mathematical Control and Related Fields, 3(4):447–466, 2013.
  * [5] I. Chang, S.-J. Chung, and L. Blackmore.  Cooperative control with adaptive graph Laplacians for spacecraft formation flying.  In 49th IEEE Conference on Decision and Control (CDC), pages 4926–4933. IEEE, 2010.
  * [6] M. Doi.  Molecular dynamics and rheological properties of concentrated solutions of rodlike polymers in isotropic and liquid crystalline phases.  Journal of Polymer Science: Polymer Physics Edition, 19(2):229–243, 1981.
  * [7] L. C. Evans.  An introduction to mathematical optimal control theory version 0.2.  Lecture notes available at http://math. berkeley. edu/~ evans/control. course. pdf, 1983.
  * [8] S.-Y. Ha and D. Kim.  A second-order particle swarm model on a sphere and emergent dynamics.  SIAM Journal on Applied Dynamical Systems, 18(1):80–116, 2019.
  * [9] S.-Y. Ha, C. Lattanzio, B. Rubino, and M. Slemrod.  Flocking and synchronization of particle models.  Quarterly of applied mathematics, 69(1):91–103, 2011.
  * [10] M. Lohe.  Non-Abelian Kuramoto models and synchronization.  Journal of Physics A: Mathematical and Theoretical, 42(39):395101, 2009.
  * [11] T. Sanchez, D. T. Chen, S. J. DeCamp, M. Heymann, and Z. Dogic.  Spontaneous motion in hierarchically assembled active matter.  Nature, 491(7424):431–434, 2012.


# Addendum to ”The $\hat{A}$-genus of $S^{1}$-manifolds with finite second
homotopy group”

Manuel Amann
Department of Mathematics, University of Augsburg, Germany The first named
author thanks the University of Augsburg for their continued support. Anand
Dessai
Department of Mathematics, University of Fribourg, Switzerland The second
named author was supported by the SNSF-Project 200020E_193062 and the DFG-
Priority programme SPP 2026.

Theorem 1.1 of [1] states that for any $k>1$ there exists a smooth simply
connected closed $4k$-dimensional manifold with finite $\pi_{2}$ and non-
vanishing $\hat{A}$-genus which admits a smooth effective $S^{1}$-action. The
proof of this theorem was based on a general surgery lemma [1, Lemma 2.1]. As
has been pointed out to us by Michael Wiemeler, the surgery lemma is not true
in the form stated. Additional assumptions are necessary to ensure that the
surgery can be done equivariantly. The purpose of this note is to remedy this
situation and to give a proof of the theorem above using explicit equivariant
surgeries. For $k>2$ the proof is essentially the one given in [1], for $k=2$
we apply [5, Thm. 1.3].

###### Theorem 1.1

For any $k>1$ there exists a smooth simply connected $4k$-dimensional
$\pi_{2}$-finite manifold $M^{\prime}$ with smooth effective $S^{1}$-action
and $\hat{A}(M^{\prime})\neq 0$.

Proof: As in [1] we consider $M:={\mathbb{C}}P^{2k}$ with a linear
$S^{1}$-action. More precisely, we consider the $S^{1}$-action on $M$ induced
by the linear action

$\displaystyle S^{1}\times{\mathbb{C}}^{2k+1}$
$\displaystyle\to{\mathbb{C}}^{2k+1}$
$\displaystyle(\lambda,(z_{0},\ldots,z_{2k-2},z_{2k-1},z_{2k}))$
$\displaystyle\mapsto(z_{0},\ldots,z_{2k-2},\lambda\cdot
z_{2k-1},\lambda^{-1}\cdot z_{2k}).$

The connected components of the fixed point set $M^{S^{1}}$ are two isolated
fixed points and $N:={\mathbb{C}}P^{2k-2}$.

We first assume that the dimension of $N$ is $>4$, i.e., that $k>2$. Let
$\kappa:M\to BSO$ be a classifying map for the stable normal bundle of $M$.
Consider a map $f:S^{2}\to N$ such that its composition with the inclusion map
$N\hookrightarrow M$ represents a generator of the kernel of
$\kappa_{*}:\pi_{2}(M)\to\pi_{2}(BSO)$. Since $\dim N>4$ we may assume that
$f$ is a smooth embedding.

By construction, the normal bundle of $f(S^{2})\subset M$, viewed as a real
non-equivariant vector bundle, is trivial. It splits equivariantly as a direct
sum $E\oplus F$, where $E$ is the normal bundle of $f(S^{2})$ in $N$ and $F$
is the restriction to $f(S^{2})$ of the normal bundle $\nu_{N}$ of $N$ in $M$.
We note that $\nu_{N}$ can be identified with the direct sum
$\overline{\gamma}\oplus\overline{\gamma}$, where $\gamma$ denotes the
canonical complex line bundle over $N={\mathbb{C}}P^{2k-2}$. Under this
identification, $\lambda\in S^{1}$ acts on one summand by multiplication with
$\lambda$ and on the other summand by multiplication with $\lambda^{-1}$. By
changing the complex structure, we can identify $\nu_{N}$ equivariantly with
the complex vector bundle $\gamma\oplus\overline{\gamma}$, where $\lambda\in
S^{1}$ now acts by complex multiplication on both summands. In particular, $F$
can be identified equivariantly with the complex vector bundle
$(\gamma\oplus\overline{\gamma})|_{f(S^{2})}$ which is trivial. Also, $E$ is a
trivial real vector bundle over $f(S^{2})$, since $E$ is stably trivial and
has rank $\mathrm{rk}\,E=\dim N-2=4k-6>2$. Moreover, $S^{1}$ acts trivially on
$E$. Hence, $F$ (resp. $E$) can be extended as a complex (resp. real) vector
bundle over the disk $D^{3}$.

In conclusion, the normal bundle of $f(S^{2})\subset M$ splits equivariantly
as the direct sum of a trivial vector bundle $E$ with trivial $S^{1}$-action
and a trivial vector bundle $F$ with non-trivial $S^{1}$-action, and the
direct sum extends equivariantly to the disk $D^{3}$, where $S^{1}$ acts
trivially on $D^{3}$. In particular, the sphere normal bundle of
$f(S^{2})\subset M$ can be extended equivariantly to the disk. Hence, one can
perform $S^{1}$-equivariant surgery on $f(S^{2})$. The result of the surgery
is a simply connected $S^{1}$-manifold $M^{\prime}$ with
$\pi_{2}(M^{\prime})\cong{\mathbb{Z}}/2{\mathbb{Z}}$ which is
$S^{1}$-equivariantly bordant to $M$.

It is well-known that the $\hat{A}$-genus does not vanish on
${\mathbb{C}}P^{2k}$. Since $M^{\prime}$ is bordant to ${\mathbb{C}}P^{2k}$
the same is true for $M^{\prime}$. This completes the argument if $k>2$.

For $k=2$, one cannot argue as above, since the bundle $E$ does not extend to
the disk. In fact, if $S^{2}\subset N={\mathbb{C}}P^{2}$ represents a non-
trivial element of $\pi_{2}(M)$ then the Euler class of its normal bundle in
$N$ is non-zero.

To construct $M^{\prime}$ for $k=2$ we will apply a different construction
which involves non-equivariant surgery in the orbit space. This construction,
which was pointed out to us by Michael Wiemeler, is quite general, the
argument below is a special case of [5, Thm. 1.3].

Let us consider $M={\mathbb{C}}P^{4}$ with the $S^{1}$-action as before. Let
$M_{0}$ denote the union of principal orbits and $i:M_{0}\hookrightarrow M$
the inclusion map. Note that the complement of $M_{0}$ is the union of $N$ and
a 2-sphere which contains the two isolated fixed points. The restriction of
the action to $M_{0}$ defines a principal $S^{1}$-bundle $p:M_{0}\to B_{0}$
with base space $B_{0}:=M_{0}/S^{1}$. Note that
$i_{*}:\pi_{2}(M_{0})\to\pi_{2}(M)$ is an isomorphisms and
$p_{*}:\pi_{2}(M_{0})\to\pi_{2}(B_{0})$ is injective.

Consider a map $f:S^{2}\to M_{0}$ such that $i\circ f$ represents a generator
of the kernel of $\kappa_{*}:\pi_{2}(M)\to\pi_{2}(BSO)$. Up to homotopy we may
assume that $f$ and $\overline{f}:=p\circ f:S^{2}\to B_{0}$ are smooth
embeddings. It follows that the restriction of the principal $S^{1}$-bundle to
$\overline{f}(S^{2})$ is trivial (with a section given by $f$) and that the
normal bundle of $\overline{f}(S^{2})\subset B_{0}$ is trivial. Hence, the
disk normal bundle of $\overline{f}(S^{2})$ can be identified with
$\overline{f}(S^{2})\times D^{5}$ and the disk normal bundle of $S^{1}\cdot
f(S^{2})=p^{-1}(\overline{f}(S^{2}))\cong S^{1}\times f(S^{2})$ can be
identified equivariantly with $S^{1}\times f(S^{2})\times D^{5}$, where
$S^{1}$ acts on $S^{1}$ by left multiplication and acts trivially on the other
factors. Next perform surgery for $\overline{f}(S^{2})\times D^{5}\subset
B_{0}$ and make the corresponding modification for $S^{1}\times f(S^{2})\times
D^{5}\subset M_{0}$, i.e., consider

$\Bigl{(}M_{0}-(S^{1}\times
f(S^{2})\times\overset{\circ}{D^{5}})\Bigr{)}\cup\Bigl{(}{S^{1}\times
D^{3}\times S^{4}}\Bigr{)}.$

Let us denote the results of these modifications by $B_{0}^{\prime}$ and
$M_{0}^{\prime}$, respectively, and let

$M^{\prime}:=M_{0}^{\prime}\cup(M-M_{0}).$

As before, the inclusion $M_{0}^{\prime}\hookrightarrow M^{\prime}$ induces an
isomorphism on $\pi_{2}$ and the projection in the principal $S^{1}$-bundle
$M_{0}^{\prime}\to B_{0}^{\prime}$ is injective on $\pi_{2}$. It follows that
$\pi_{2}(M^{\prime})\cong{\mathbb{Z}}/2{\mathbb{Z}}$. In addition, the long
exact sequence of homotopy groups for the principal $S^{1}$-bundles together
with the Seifert-van Kampen theorem shows that $M^{\prime}$ is simply
connected. By construction, $M^{\prime}$ is equivariantly bordant to
$M={\mathbb{C}}P^{4}$. Hence,
$\hat{A}(M^{\prime})=\hat{A}({\mathbb{C}}P^{4})\neq 0$. This completes the
argument for $k=2$. $\square$

###### Remarks 1.2

  1. 1.

LeBrun and Salamon conjectured that any positive quaternionic Kähler manifold
is symmetric. The conjecture has been proved by Hitchin, Poon-Salamon and
LeBrun-Salamon in dimensions $\leq 8$. Haydeé and Rafael Herrera [3] offered a
proof in dimension $12$ involving a vanishing statement for the
$\hat{A}$-genus of $\pi_{2}$-finite manifolds with $S^{1}$-action. The purpose
of [1, Thm. 1.1] was to show that this statement cannot be correct.

  2. 2.

Recently, Buczyński, Wiśniewski and Weber [2] gave a proof of the LeBrun-
Salamon conjecture in dimensions $12$ and $16$ by showing that the
corresponding twistor spaces are adjoint varieties.

  3. 3.

In [5] Wiemeler uses equivariant surgery to construct examples of manifolds,
as in Thm. 1.1, which have non-trivial fundamental group. The examples have
non-spin universal covering. On the other hand, Wiemeler shows that the
elliptic genus is rigid for any closed even-dimensional $S^{1}$-manifold whose
universal covering is spin. Using an argument of Hirzebruch and Slodowy [4] he
concludes that the $\hat{A}$-genus of such a manifold vanishes if the action
is non-trivial.

We like to thank Michael Wiemeler for discussions and valuable comments.

## References

  * [1] M. Amann and A. Dessai, The $\hat{A}$-genus of $S^{1}$-manifolds with finite second homotopy group, C. R. Math. Acad. Sci. Paris 348 (2010) 283–285
  * [2] J. Buczyński, J. A. Wiśniewski, A. Weber, Algebraic torus actions on contact manifolds, J. Differential Geom. 121 (2022) 227–289
  * [3] H. and R. Herrera, $\hat{A}$-genus on non-spin manifolds with $S^{1}$ actions and the classification of positive quaternion-Kähler 12-manifolds, J. Differential. Geom. 61 (2002) 341–364
  * [4] F. Hirzebruch and P. Slodowy, Elliptic genera, involutions and homogeneous spin manifolds, Geom. Ded. 35 (1990) 309–343
  * [5] M. Wiemeler, Rigidity of elliptic genera for non-spin manifolds, preprint arXiv:2212.01059 (2022)


# Fast Redescription Mining Using Locality-Sensitive Hashing

Maiju Karjalainen  Esther Galbrun  Pauli Miettinen

(University of Eastern Finland
<EMAIL_ADDRESS>
###### Abstract

Redescription mining is a data analysis technique that has found applications
in diverse fields. The most used redescription mining approaches involve two
phases: finding matching pairs among data attributes and extending the pairs.
This process is relatively efficient when the number of attributes remains
limited and when the attributes are Boolean, but becomes almost intractable
when the data consist of many numerical attributes. In this paper, we present
new algorithms that perform the matching and extension orders of magnitude
faster than the existing approaches. Our algorithms are based on locality-
sensitive hashing with a tailored approach to handle the discretisation of
numerical attributes as used in redescription mining.

##  1 Introduction

A redescription is a pattern that characterises roughly the same entities in
two different ways, and redescription mining is the task of automatically
extracting redescriptions from the input dataset, given user-defined
constraints. Redescription mining has found applications in various fields of
science, such as ecometrics. Ecometrics aims to identify and model the
functional relationships between traits of organisms and their environments
[5, 7]. For instance, the teeth of large plant-eating mammals are adapted to
the food that is available in their environment, which in turn depends on the
climatic conditions, potentially allowing one to reason about the climate in
the past based on the fossil record.

To apply redescription mining in this context, the entities in the dataset
represent localities, with two sets of attributes recording respectively the
distribution of dental traits among species and the climatic conditions at
each locality [11, 19]. Galbrun et al. [11] mined redescriptions from this
dataset using the ReReMi [8] algorithm in about $50$ minutes on a commodity
laptop. Replicating the experiment, we obtained a comparable time (bar D of
Fig. 1 (left)).

In contrast, the two top bars represent our proposed method, Fier (Fast
Initialisation and Extension of Redescriptions), based on locality-sensitive
hashing (LSH). Our approach uses the same two-phase procedure as ReReMi: it
finds initial pairs in the first phase, and extends them in the second phase
(see Sect. 2 for details). The top bar, Fier_full, uses a LSH-based approach
for both phases, while the second bar, Fier_init, uses LSH approach only for
the first part. The third bar represents a straightforward speed-up of initial
pair generation of ReReMi that we use as a baseline. It is obtained by
replacing on-the-fly discretisation of numerical attributes by discretisation
as a pre-processing step.

Figure 1 (left) shows that using Fier the whole mining process is completed
before the standard ReReMi has even finished mining the initial pairs. The
process is reduced from 66 to mere 12; mining the initial pairs takes only 25.

Fier, being significantly faster than the existing methods, allows the use of
redescription mining on even larger datasets. Alternatively, the speedup
affords more responsive interactive redescription mining [10] and quickly
testing parameter and constraint combinations to ‘get a feel’ for what kind of
setup to use with the more exhaustive ReReMi algorithm. The price Fier has to
pay for its speed is its probabilistic nature: unlike ReReMi, it does not
guarantee to return the best initial pairs nor the (locally) best extensions.

Figure 1: Left: Running times on the DentalW dataset for finding initial pairs
(blue) and extending pairs (yellow) using (A) the proposed algorithm
(Fier_full), (B) Fier_init for initial pairs and ReReMi for extensions, (C)
ReReMi with pre-bucketing (ReReMiBkt) and (D) standard ReReMi. The number
within each bar indicates how many initial pairs were found. Right: Example
redescription.

#### Redescription mining.

The input of redescription mining is a pair of _data tables_ which we refer to
as the left-hand side and right-hand side, denoted respectively
$\mathbf{D}_{L}$ and $\mathbf{D}_{R}$, over the same _entities_ , denoted
$\mathcal{E}$. Then, a redescription is a pair of _queries_ , denoted
$q^{\phantom{x}}_{L}$ and $q^{\phantom{x}}_{R}$, consisting of _literals_ over
the attributes of the corresponding table, combined with logical conjunction
and disjunction operators, possibly involving negations. The set of entities
that satisfy both queries, only the left-hand side query, only the right-hand
side query, and neither of them are denoted respectively $\mathcal{E}_{11}$,
$\mathcal{E}_{10}$, $\mathcal{E}_{01}$ and $\mathcal{E}_{00}$. The set
$\mathcal{E}_{11}$ is also called the support of the redescription, and more
in general, we call _support_ ($\operatorname{supp}$) of a literal or query
the set of entities that satisfy it. The Jaccard index between the sets of
entities that satisfy either query is called the _accuracy_ of the
redescription (we use the terms Jaccard and accuracy interchangeably) and is
defined

$J(q^{\phantom{x}}_{L},q^{\phantom{x}}_{R})=\frac{\left\lvert\mathcal{E}_{11}\right\rvert}{\left\lvert\mathcal{E}_{10}\right\rvert+\left\lvert\mathcal{E}_{11}\right\rvert+\left\lvert\mathcal{E}_{01}\right\rvert}\,.$

Since it is meant to provide two ways to characterise roughly the same
entities, accuracy is the main measure of the quality of a redescription.
Further constraints that can be applied to redescriptions include a maximum
threshold on the number of attributes they involve, since long queries might
be difficult to interpret, and minimum thresholds on the number of entities
that satisfy both queries and that satisfy neither, since redescriptions that
characterise too few or too many of the entities are typically not considered
interesting.

Going back to the application in ecometrics, the right-hand side query of the
example redescription shown in Fig. 1 (right) characterises the climatic
conditions encountered at the locality, in this case requiring high
isothermality (TIso) and high annual precipitation (PTotY). The left-hand side
query ($q^{\phantom{x}}_{L}$) is more complex and involves four literals over
dental traits, requiring a limited prevalence of hypsodont species (Hyp3) and
fairly low fraction of species with acute lophs (AL), or a very low fraction
of hypsohorizodont species (Hod3), but allowing up to a rather large fraction
of species with obtuse lophs (OL). Hypsodont and hypsohorizodont species refer
to species with elongated teeth respectively along the vertical and the
horizontal dimension, while acute and obtuse lophs refer respectively to the
presence of sharp and blunt edges on the tooth across the chewing direction.
In the considered dataset, $\left\lvert\mathcal{E}_{11}\right\rvert=6\,185$ of
the $28\,886$ localities satisfy both queries, representing about
$J=\qty{62}{}$ of the $10\,011$ localities that satisfy at least one of the
queries.

#### Related work.

In the two decades since redescription mining was introduced [25], various
algorithms have been proposed for this task, including based on decision tree
induction [25, 26, 21], itemset mining [12], as well as iterative greedy
heuristics [12, 8]. The ReReMi algorithm [8] belongs to the latter family.

Other lines of work have focused for instance on selecting a good set of
redescriptions [16], designing an interactive tool [10] and providing
differentially private methods for redescription mining [22, 17]. Meanwhile,
redescription mining has been used in applications from domains as diverse as
medicine [23], political sciences [9] and palaeontology [11, 19].

Also relevant here is the work of Meeng and Knobbe [20] studying the impact of
different discretisation strategies on subgroup discovery, a task very similar
to redescription mining.

Locality-sensitive hashing was introduced for efficient nearest neighbour
search [15]. It has proven to be very useful for various tasks, such as
collaborative filtering [4], clustering [2] and privacy preservation [6]. The
work most related to the present work is the early application to faster
association rule mining [3].

##  2 The Algorithm

We divide our full algorithm into two parts for the two phases: Fier_init
computes the initial pairs and Fier_ext the extensions. The full algorithm is
called Fier_full. Before presenting the algorithms, we provide short primers
on the ReReMi algorithm and on locality-sensitive hashing.

###  2.1 The ReReMi algorithm

The algorithm on which we build, ReReMi [8], mines redescriptions in two main
phases. In the first phase, the InitialPairs method returns candidate
redescriptions with a single literal on either side. In the second phase, up
to a chosen number of the best initial pairs are considered. Each is extended
in turn through a greedy process that iteratively appends a literal to either
of the queries to produce more refined and accurate redescriptions. The ReReMi
algorithm can handle Boolean, categorical and numerical attributes. In
particular, when forming literals for a numerical attribute, it performs on-
the-fly discretisation, trying to find the interval that yields the best
accuracy for the considered candidate, rather than using pre-determined
buckets.

Going a bit further into technical details, the way ReReMi finds the initial
pairs is simple but time consuming: Iterate over all pairs of attributes, one
from either side; For each such pair, consider the possible pairs of literals
over the two attributes; Compute the support and accuracy of the corresponding
redescription and keep the best matches that satisfy support constraints.

Given a redescription to extend, ReReMi considers every available literal and
the candidate extensions obtained by appending it (or its negation if allowed)
to the current query on the corresponding side, with either the disjunction or
the conjunction operator. The support and accuracy of each candidate extension
are computed, the best one-step extensions are selected and extended in turn,
for each one considering again all the possible ways to extend it with the
remaining available literals. Starting with an initial pair, this greedy
extension process is applied until no further improvement (in terms of
accuracy) can be found or the maximum length of the queries (in terms of the
number of involved literals) has been reached. The algorithm then proceeds
with the next initial pair.

Computing the support and accuracy for a pair of literals involves computing
the cardinality of the intersection and union of the sets of entities
satisfying either literal. Similarly for computing the support and accuracy
for an extension, although it has been shown [8] that not all entities can
change status in the support of an extension. For instance, when extending a
redescription by adding a literal to the left-hand side with a conjunction,
entities that do not satisfy the current left-hand side query will not satisfy
the extended one either. This fact is used to quickly identify the entities
that need to be considered when performing the set operations to determine the
quality of an extension.

###  2.2 Primer on LSH

The idea of Locality-Sensitive Hashing (LSH) is to calculate hash values for
input items so that similar items get the same hash value with a high
probability. The type of hash function depends on the similarity measure used.
In this work we use two measures of similarity between binary vectors
representing support sets, namely the Jaccard similarity and the Hamming
distance.

When using the Jaccard similarity, the corresponding hashing technique is
called minhashing [1]. To compute minhash values, we use $k$ random hash
functions ${h_{1},\ldots,h_{k}}$ that map the row indices to values between
$0$ and the maximum number of rows. To calculate the minhash signature of a
vector, we consider the indices of all the rows containing a $1$. For every
hash function we obtain the hash values for all of these rows and take the
smallest value. These concatenated smallest hash values make up the signature
of the vector [18].

When using the Hamming distance, we calculate the length-$k$ signature of the
vector as the values of the binary vector in $k$ random indices.

To match two binary vectors based on their signatures, the signatures are
divided into $b$ smaller sections called bands, each containing $r$ hash
values (total $k=r\cdot b$). Two vectors are paired if all $r$ hash values
match in at least one band.

The parameters $b$ and $r$ determine the matching probability, i.e. the
probability with which two vectors will be paired. If the similarity of the
vectors is $p$, then the matching probability is $1-(1-p^{r})^{b}$. The
relation between the similarity and the matching probability follows an
S-curve; its threshold point can be approximated as $p_{T}=(1/b)^{1/r}$ [18].
With this approximation, only two parameters need to be set and the third one
can be calculated accordingly. To increase the chances of finding pairs with
an accuracy above a desired threshold, one can use a slightly lower value,
whereas a slightly higher value yields a faster algorithm finding fewer pairs.

###  2.3 Finding Initial Pairs

For simplicity we first focus on Boolean attributes. The pseudocode for the
algorithm is given in Algorithm 1. Starting with the left-hand side dataset
$\mathbf{D}_{L}$, we go through the literals and obtain $r_{J}$ minhash
signatures for each of the corresponding binary support vectors. Literals with
the same signature get hashed into the same bin, and we keep track of which
side each literal belongs to.

We go through the right-hand side dataset $\mathbf{D}_{R}$ similarly, except
that we discard signatures that point to an empty bin. After calculating
signatures for all literals, we go through each signature bin and form
candidate pairs between the literals from $\mathbf{D}_{L}$ and
$\mathbf{D}_{R}$ hashed into that bin.

We repeat this process $b_{J}$ times, calculating a different minhash
signature for the literals for each band. If the same two literals already
formed a pair in a previous band, we do not consider it again. After the
candidate pairs have been formed, we calculate their actual accuracy and
support, and we filter out any candidate that does not satisfy user-defined
support and accuracy thresholds.

Algorithm 1 Generating initial pairs from Boolean attributes

1:Data $\mathcal{D}=(\mathbf{D}_{L},\mathbf{D}_{R})$, number of bands $b_{J}$,
width of bands $r_{J}$

2:A set of initial redescriptions
$\mathcal{R}=\\{(q^{\phantom{x}}_{L},q^{\phantom{x}}_{R})\\}$

3:function Fier_init$\left(\mathcal{D},b,r\right)$

4: for $band=1,\ldots,b$ do

5: $B\leftarrow\emptyset$

6: generate $r$ hash functions $h_{1},\ldots,h_{r}$ that permute the row
indexes

7: for side in $\mathcal{D}$ do

8: for attribute $a$ in side do

9:
$\mathit{sig}\leftarrow\bigl{(}\min\bigl{(}h_{1}(\operatorname{supp}(a))\bigr{)},\ldots,\min\bigl{(}h_{r}(\operatorname{supp}(a))\bigr{)}\bigr{)}$

10: $B[\mathit{sig}]\leftarrow B[\mathit{sig}]\cup\\{a\\}$

11: for all $\mathit{sig}\in B$ do

12: $\mathcal{R}\leftarrow\mathcal{R}\cup\\{$pairs of literals $(a_{L},a_{R})$
in $B[\mathit{sig}]$, $a_{L}\in\mathbf{D}_{L},a_{R}\in\mathbf{D}_{R}\\}$

13: return $\mathcal{R}$

Building initial pairs from categorical attributes is slightly more
complicated, as we can create several different literals by considering the
different categories, separately or combined. We first consider the literals
obtained by considering each category of an attribute $a$ separately and
calculate their minhash signatures the same way as for Boolean literals. Next,
we create combinations of the categories by joining them with the disjunction
operator, e.g. $[a=c_{1}\lor a=c_{2}]$. The number of categories that are
combined can be limited with a user-defined parameter. Since we already
calculated the signatures for the separate categories, we can obtain the
signature for a combination by simply taking the smallest minhash value among
the categories included in the combination.

Creating literals out of numerical attributes is similar to categorical
attributes, but by specifying intervals such as $[a\leq x]$ or $[x\leq a\leq
y]$, instead of categories. We determine the intervals in two steps. First, we
discretise the attribute values into $n_{b}$ small buckets
$[\mathit{buk}_{l}\leq y\leq\mathit{buk}_{u}]$ (line 7 in Algorithm 2) and
calculate signatures for the literals corresponding to the separate buckets.
Second, we create extended intervals by combining consecutive buckets, and
calculate the signature for an extended interval by taking the smallest
minhash values of the buckets included in the interval (line 15). We use
support thresholds $\operatorname{supp}_{\min}$ and
$\operatorname{supp}_{\mathrm{out}}$ to limit the size of intervals so that
they do not cover too few or too many entities. The
$\operatorname{supp}_{\mathrm{out}}$ threshold defines the minimum number of
entities not covered by the literal.

The discretisation of attribute values into buckets can be done in different
ways. We found that the bucketing method did not have a significant impact on
the running time nor on the quality of the results. In our experiments we used
equal-height binning, where each bucket covers a similar number of entities.

To avoid creating multiple pairs that are very similar to each other, we
filter out any subinterval that has the same signature as the interval it is
contained in. We do this by keeping track of the signatures we have seen for
an attribute (within one band) as we iterate over the intervals.

We iterate over the intervals by progressively narrowing them down.
Considering the ordered bucket edges
$\mathit{buk}_{0},\mathit{buk}_{1},\ldots,\mathit{buk}_{n_{b}}$, we start by
setting $\mathit{buk}_{0}$ as the lower and $\mathit{buk}_{n_{b}}$ as the
upper bound of the interval. We lower the upper bound by removing buckets from
the top $\mathit{buk}_{n_{b}-1},\mathit{buk}_{n_{b}-2},\ldots$ until the
support criteria is met. We calculate the signature as the smallest minhash
values of the buckets contained in the interval. We lower the upper bound
until the support of the interval is below the minimum support criterion.
Then, we set $\mathit{buk}_{1}$ as the lower bound and repeat the process
until we have gone through all lower bounds. We filter out subintervals of
already seen intervals during this process, by discarding those intervals
whose signature we have already seen, and whose upper bound is smaller than
the largest seen upper bound for that signature (line 16).

Algorithm 2 Generating initial pairs from numerical attributes

1:Data $\mathcal{D}=(\mathbf{D}_{L},\mathbf{D}_{R})$, number of bands $b_{J}$,
width of bands $r_{J}$, number of buckets $n_{b}$, min. nb. of entities not in
the support $\operatorname{supp}_{\mathrm{out}}$, minimum support
$\operatorname{supp}_{\min}$

2:A set of initial redescriptions
$\mathcal{R}=\\{(q^{\phantom{x}}_{L},q^{\phantom{x}}_{R})\\}$

3:function
Fier_init$\left(\mathcal{D},b,r,n_{b},\operatorname{supp}_{\mathrm{out}},\operatorname{supp}_{\min}\right)$

4: for $band=1,\ldots,b$ do

5: for data table in $\mathcal{D}$ do

6: for attribute $a$ in data table do

7:
$[\mathit{buk}_{0},\mathit{buk}_{2},\ldots,\mathit{buk}_{n_{b}}]\leftarrow\textsc{Discretise}(a,n_{b})$

8: for $k=1,\ldots,n_{b}$ do

9: Signatures$[k,:]\leftarrow r_{J}$ minhash values for
$[\mathit{buk}_{k-1}\leq a\leq\mathit{buk}_{k}]$

10: $S\leftarrow\emptyset$

11: for $l=0,\ldots,n_{b}-1$ do

12: $u\leftarrow n_{b}$

13: while $\operatorname{supp}([\mathit{buk}_{l}\leq
a\leq\mathit{buk}_{u}])>\left\lvert\mathcal{E}\right\rvert-\operatorname{supp}_{\mathrm{out}}$
do $u\leftarrow u-1$

14: while $\operatorname{supp}([\mathit{buk}_{l}\leq
a\leq\mathit{buk}_{u}])\geq\operatorname{supp}_{\min}$ do

15: $\mathit{sig}\leftarrow\min_{i=l+1}^{u}($Signatures$[i,\colon])$

16: if $u>S[\mathit{sig}]$ then

17: $B[\mathit{sig}]\leftarrow B[sig]\cup\\{[\mathit{buk}_{l}\leq
a\leq\mathit{buk}_{u}]\\}$

18: $S[\mathit{sig}]\leftarrow u$

19: $u\leftarrow u-1$

20: for all $\mathit{sig}\in B$ do

21: $\mathcal{R}\leftarrow\mathcal{R}\cup\\{$pairs of literals
$([\mathit{buk}_{l}\leq
a_{L}\leq\mathit{buk}_{u}],[\mathit{buk}^{\prime}_{l}\leq
a_{R}\leq\mathit{buk}^{\prime}_{u}])$ in $B[sig]$,
$a_{L}\in\mathbf{D}_{L},a_{R}\in\mathbf{D}_{R}\\}$

22: return $\mathcal{R}$

###  2.4 Extending Initial Pairs

#### Computing signatures for literals.

We start the process by computing the Hamming signatures for all data columns.
For this we first randomly select indices over the number of rows in the data,
so that we have $b_{H}$ sets of length $r_{H}$ random indices to create all
signatures from. Note that these are different parameters than $b_{J}$ and
$r_{J}$ used with the initial pair mining. For each literal to extend with, we
store $b_{H}$ sets of length $r_{H}$ signatures.

The discretisation of the numerical attributes is done differently from the
initial pair search. We start with a small number of buckets to discretise the
values into and compute the Hamming signature corresponding to each bucket.
Next, we double the number of buckets, perform the discretisation again and
compute new signatures. We repeat this process a fixed number of times. We
store the signatures for each bucket of each attribute, but we do not store
the actual intervals, as they will be re-calculated later. This approach has
only a modest effect on the running time, as we only need to compute the
signatures for literals once. On the other hand, it sidesteps the issue of
choosing the correct bucketing by using many different ones.

#### The target vector.

As mentioned earlier, only some entities in the data matter when extending a
redescription. Let us consider a redescription
$(q^{\phantom{x}}_{L},q^{\phantom{x}}_{R})$ which we want to extend on the
right side with a conjunction. To improve
$J(q^{\phantom{x}}_{L},q^{\phantom{x}}_{R})$, we want to find a literal that
is satisfied by entities in $\mathcal{E}_{11}$ (so that the numerator does not
shrink) and not by entities in $\mathcal{E}_{01}$ (so that the denominator
shrinks). Entities in $\mathcal{E}_{10}$ and $\mathcal{E}_{00}$ do not matter,
and we call these rows the ‘don’t-care’ rows. In terms of LSH, we can see this
as having a target vector that has $1$s in rows corresponding to
$\mathcal{E}_{11}$ and $0$s in rows corresponding to $\mathcal{E}_{01}$. We
can easily find data columns that match this target vector using the Hamming
distance restricted to these rows (we use Hamming instead of Jaccard to reward
matches on $1$s and on $0$s equally). Similarly, when extending the left side
with a disjunction, we want to find literals that have $1$s in rows
corresponding to $\mathcal{E}_{01}$ and $0$s in rows corresponding to
$\mathcal{E}_{00}$, with $\mathcal{E}_{11}$ and $\mathcal{E}_{10}$ being the
‘don’t-care’ rows. When extending the right side either by conjunction or
disjunction the target vectors are otherwise same as with the left side,
except that $\mathcal{E}_{10}$ and $\mathcal{E}_{01}$ switch places. As these
subsets of rows are different for each redescription to be extended, we would
have to re-compute the signatures for all data columns considering every
candidate redescription and both connectives used to extend it on each side.
This would clearly cancel the speed benefit. Instead, we replace the
‘don’t-care’ rows in the target vector with $0$s when extending with
conjunction and with $1$ when extending with disjunction. This way we only
need to compute the signatures for the data columns once and we can use the
same signatures for all extensions.

#### Extending redescriptions.

The algorithm for extending the redescriptions, denoted Fier_ext, is presented
in Algorithm 3. We start by storing the initial pairs in a priority queue $Q$,
using accuracy as the key. We always expand the redescription with the current
highest accuracy. A redescription can be extended on either of its sides, with
a conjunction or a disjunction operator. The corresponding target vectors are
computed by ComputeTargetVector. ComputeCandidates uses LSH to find the
columns that match the target vectors, recording also the associated side and
operator. The same column can match multiple times (in different bands, or
different buckets for a numerical attribute), only the first match is stored.
The actual extensions are then computed using the same approach as with ReReMi
(i.e. using the cut-point method [8] for numerical attributes) and the best
extension is stored and pushed back to $Q$ if it has not already been extended
to maximum length. Compared to ReReMi, the speed of Fier_ext benefits from not
trying every column as a candidate extension, but only those that match with
LSH.

Algorithm 3 Fier_ext: Extend redescriptions

1:Initial pairs $\mathcal{P}$, buckets with signatures for each possible
extension $B$, maximum length of a redescription $t$

2:A set of extended redescriptions $\mathcal{R}$

3:function Fier_ext$\left(P,B,t\right)$

4: $Q\leftarrow$ heapify the list of initial pairs with accuracy as the key;
$R\leftarrow\emptyset$

5: while $Q\neq\emptyset$ do

6: $(q^{\phantom{x}}_{L},q^{\phantom{x}}_{R})\leftarrow Q.\mathrm{pop()}$

7: $V\leftarrow$
ComputeTargetVectors($(q^{\phantom{x}}_{L},q^{\phantom{x}}_{R})$)

8: $C\leftarrow$ ComputeCandidates($V,B$)

9: for (column, side, operator) $\in C$ do

10: $E\leftarrow$
ComputeExtensions($(q^{\phantom{x}}_{L},q^{\phantom{x}}_{R})$, column, side,
operator)

11: if $E\neq\emptyset$ then

12: $\mathrm{best}\leftarrow$ extension with the highest Jaccard

13: $\mathcal{R}\leftarrow\mathcal{R}\cup\\{\mathrm{best}\\}$

14: if $\operatorname{len}(\mathrm{best})<t$ then
$Q.\mathrm{push}(\mathrm{best})$

15: return $\mathcal{R}$

###  2.5 Time Complexity

The time complexity for mining initial pairs from Boolean attributes is
$O(N\cdot{}b\cdot{}r\cdot{}\left\lvert\mathcal{E}\right\rvert+n_{L}\cdot{}n_{R})$,
where $\left\lvert\mathcal{E}\right\rvert$ is the number of entities, $N$ is
the total number of attributes, $b\cdot{}r$ is the total number of hash
functions in LSH, $n_{L}$ is the largest number of left-hand side literals
hashed to the same bin, and $n_{R}$ is the largest number of right-hand side
literals hashed to the same bin. The first term is for computing the
signatures. The second term is for building the pairs; in the worst case it is
quadratic, but in practise much smaller.

The time complexity for numerical attributes is
$O\bigl{(}N(\left\lvert\mathcal{E}\right\rvert\log\left\lvert\mathcal{E}\right\rvert+n_{b}\cdot{}b\cdot{}r\cdot{}\left\lvert\mathcal{E}\right\rvert+n_{b}^{2})+n_{L}\cdot{}n_{R}\bigr{)}$;
assuming $n_{b}$, $b$, and $r$ are constants, this becomes
$O(N\left\lvert\mathcal{E}\right\rvert\log\left\lvert\mathcal{E}\right\rvert+n_{L}\cdot{}n_{R})$.
Bucketing with equal-height binning takes
$O\bigl{(}N(\left\lvert\mathcal{E}\right\rvert\log\left\lvert\mathcal{E}\right\rvert)\bigr{)}$.
We can think of each bucket as creating a new literal, so creating the
signatures takes
$O(N\cdot{}n_{b}\cdot{}b\cdot{}r\left\lvert\mathcal{E}\right\rvert)$.
Subinterval filtering (Algorithm 2 line 11) takes $O(n_{b}^{2})$ for each of
the $N$ attributes. Similarly to Boolean attributes we assume at most $n_{L}$
and $n_{R}$ literals hashed to the same bin. The time complexity for the
categorical attributes falls between the Boolean and numerical attributes.

The time complexity for mining the extensions is $\tau\cdot n_{c}\cdot T_{R}$,
where $\tau$ is the number of extensions done (at most the number of initial
pairs times the maximum length of a redescription), $n_{c}$ is the maximum
number of candidate extensions for a target vector (at most the number of
literals in the data but typically much fewer), and $T_{R}$ is the time ReReMi
takes to compute an extension for a given redescription and a literal.

##  3 Experimental Evaluation

The experimental evaluation asserts that the results obtained by Fier are
comparable to ReReMi in quality and that Fier is significantly faster than
ReReMi. It is split into three parts: generating the initial pairs (Sect.
3.2), extending initial pairs (Sect. 3.3) and the full system (Sect. 3.4). We
also test the sensitivity of Fier to the parameters of locality-sensitive
hashing. We did not test the effects of standard redescription mining
parameters, such as $\operatorname{supp}_{\min}$, that are common to all
algorithms of this family and not a property of our proposed approach.

###  3.1 Experimental Setup

We used twelve different datasets. Their properties are listed in Table 1.

Table 1: dataset properties. dataset |  ${\left\lvert\mathcal{E}\right\rvert,\text{entities}}$ |  $\mathbf{D}_{L}$ attributes |  $\mathbf{D}_{R}$ attributes
---|---|---|---
EuroClim |  $2\,575$ | $12$ | numerical | $12$ | numerical
NoisyClim |  $2\,575$ | $36$ | numerical | $36$ | numerical
MammalsW |  $54\,013$ | $48$ | numerical | $4\,754$ | Boolean
Ethno |  $1\,267$ | $23$ | numerical and categorical | $90$ | numerical
DentalW |  $28\,886$ | $11$ | numerical | $19$ | numerical
DentalA |  $6\,404$ | $7$ | numerical | $19$ | numerical
VAA |  $1\,656$ | $9$ | categorical | $107$ | categorical
CMSd |  $d$ | $152$ | numerical | $452$ | numerical

The MammalsW dataset contains information about which mammal species inhabit
which areas of the world on one side, and climate information on the other
side [14]. That same climate data restricted to Europe, with monthly average
temperatures on one side and monthly total precipitations on the other,
constitutes the EuroClim dataset. NoisyClim contains three copies of the
columns of EuroClim. The first copy is as is, the second and third copies are
perturbed by adding noise distributed following $\mathcal{N}(0,1)$ and
$\mathcal{N}(0,3)$ respectively.

DentalW is the dataset from the ecometrics study [11] presented in the
introductory example. One side contains dental traits aggregated over the
resident large herbivorous species whereas the other side contains climate
information, at localities across the world. DentalA is a similar dataset,
restricted to Southeast Asia and China and considering a slightly different
set of dental traits [19].

Ethno is based on Murdock’s Ethnographic Atlas [24]. It contains ecological
attributes on the left-hand side, and nominal attributes recording cultural
features of various tribes on the right hand side. VAA [13] contains the
background information and answers to questions regarding political opinions
of candidates to the Finnish parliamentary elections of 2011, as collected by
an online voting advice application (VAA).

Finally, the CMS data are based on the synthetic data released by the Centers
for Medicare and Medicaid Services.111https://www.cms.gov/Research-
Statistics-Data-and-Systems/Downloadable-Public-Use-Files/SynPUFs/DE_Syn_PUF
We used five versions of the data, all having the same attributes, but
increasing number of rows ($7199$, $14\,414$, $29\,136$, $58\,204$ and
$116\,395$). The differently sized versions of CMS are indicated with the
numbers of rows in subscript where relevant.

All algorithms are implemented in Python and the experiments (except when
mentioned otherwise) are run with Python 3.6.8 on a machine with $2$ AMD EPYC
7702 processors with $64$ cores each and $1\text{\,}\mathrm{TB}$ of main
memory. All experiments were run single-threaded. For ReReMi, we used the
publicly available version.222https://pypi.org/project/python-clired/ Our
code is publicly available.333https://github.com/maijuka/fier

Unless otherwise noted, all comparative experiments were run with parameters
$b_{J}=40$, $r_{J}=10$,
$\operatorname{supp}_{\min}=0.1\left\lvert\mathcal{E}\right\rvert$,
$\operatorname{supp}_{\mathrm{out}}=0.3\left\lvert\mathcal{E}\right\rvert$ and
with $n_{b}=40$ buckets for numerical attributes. An exception to this are the
DentalW and DentalA datasets, for which we used the parameters $b_{J}=40$,
$r_{J}=5$, $n_{b}=50$ and
$\operatorname{supp}_{\min}=0.01\left\lvert\mathcal{E}\right\rvert$. For
DentalW we set $\operatorname{supp}_{\mathrm{out}}$ to
$0.6\left\lvert\mathcal{E}\right\rvert$ and for DentalA to
$0.3\left\lvert\mathcal{E}\right\rvert$. When using Fier,
$\operatorname{supp}_{\mathrm{out}}$ was further multiplied by $1.15$ for
DentalW and $1.2$ for DentalA. Further experimental results are presented in
Appendix A.

###  3.2 Finding Initial Pairs

#### Quality of the pairs.

We compare the quality of the pairs found by Fier_init and ReReMiBkt, the
ReReMi algorithm with pre-bucketing. ReReMiBkt gives more comparable running
times and the quality of the initial pairs was essentially the same as with
ReReMi, as shown in Fig. 2 for the CMS116395, CMS7199 and MammalsW datasets.
They show that ReReMiBkt and ReReMi get the same results with the MammalsW
dataset and there are no dots in the $x$-axis, which would indicate pairs
found only by ReReMi. With the CMS datasets, ReReMi and ReReMiBkt find
somewhat different initial pairs. ReReMiBkt finds almost always equally good
initial pairs as ReReMi, as well as many intial pairs that ReReMi does not
find. This indicates that comparison to ReReMiBkt for the quality of the
initial pairs is fair.

Figure 2: Comparing the accuracy of pairs found by ReReMiBkt and ReReMi. Each
dot represents a pair of columns, and its location indicates the highest-
accuracy initial pair ReReMiBkt and ReReMi.

Results on the CMS, EuroClim, NoisyClim, Ethno, MammalsW, VAA, DentalW and
DentalA datasets are shown in Fig. 3.

Figure 3: Comparing the accuracy of pairs found by Fier_init and ReReMiBkt.
Each dot represents a pair of columns, and its location indicates the highest-
accuracy initial pair Fier_init and ReReMiBkt found. The light blue line at
the bottom shows the density of the dots that lie along the $x$-axis. All axes
range across the unit interval.

The optimal outcome for these experiments is a diagonal line, indicating that
Fier_init finds pairs equivalent to those found by ReReMiBkt. This is mostly
the case. With CMS, MammalsW and VAA, there are also some dots along the
$x$-axis, meaning that there are pairs of columns that Fier did not find, but
most of those dots are at the left end of the $x$-axis, as indicated by the
density plots (light blue). That is, they have low accuracy. DentalW and
DentalA show weaker correlation, but still a clear diagonal pattern. Ethno is
an outlier, where Fier_init does not find some pairs of literals although they
have reasonably high accuracy (indicated by the peak around the middle of the
$x$-axis), but also finds pairs that have significantly higher accuracy than
what ReReMiBkt returns.

#### Speed of execution.

The running times on different datasets are presented in Table 2. The running
times for DentalW and DentalA are not comparable to other datasets as they
were carried out using a different setup (to reflect [11, 19]).

Table 2: Comparing the running times (in seconds) of the algorithms on all datasets. Running times with DentalA and DentalW are not comparable with others, as they were run using a different setup. Algorithm | EuroClim | NoisyClim | Ethno | VAA | DentalW | DentalA
---|---|---|---|---|---|---
ReReMi | $1\,184.89$ | $12\,922.03$ | $9\,069.96$ | $0.56$ | $1\,569.01$ | $1\,960.38$
ReReMiBkt | $341.90$ | $3\,163.01$ | $102.70$ | $0.68$ | $320.09$ | $233.02$
Fier_init | $10.50$ | $68.52$ | $13.65$ | $1.87$ | $20.66$ | $18.24$
| MammalsW | $\textsf{CMS}_{7199}$ | $\textsf{CMS}_{14414}$ | $\textsf{CMS}_{29136}$ | $\textsf{CMS}_{58204}$ | $\textsf{CMS}_{116395}$
ReReMi | $138.52$ | $336.61$ | $436.53$ | $626.02$ | $953.50$ | $1\,961.12$
ReReMiBkt | $143.35$ | $308.39$ | $418.40$ | $610.99$ | $943.21$ | $1\,899.83$
Fier_init | $47.66$ | $21.22$ | $40.22$ | $71.02$ | $145.20$ | $290.54$

Overall, we see that Fier_init is consistently an order of magnitude faster
than ReReMiBkt, and often two orders of magnitude faster than ReReMi. The only
exception to this is VAA; the small size of the data and categorical
attributes mean that the overhead of the hashing dominates the running time.
Another case where the difference is smaller is MammalsW; here, the Boolean
attributes mean less benefit for Fier_init, and the on-the-fly discretisation
of numerical attributes by ReReMi is actually faster than pre-bucketing of
ReReMiBkt.

Looking at the different-sized CMS datasets, we also see that the running time
of Fier_init grows linearly with the number of rows, matching the asymptotic
runtime. Even though Fier_init uses more complex data structures for hashing,
its memory consumption was only slightly larger than that of ReReMi (≈30).

#### Sensitivity to parameters.

We evaluated the sensitivity of Fier_init to the parameters affecting
locality-sensitive hashing. Overall, we found it to be very robust.

We tested all combinations of values $20$, $40$, $60$ and $80$ for $b_{J}$ and
values $3$, $5$, $7$, $10$, $12$ and $15$ for $r_{J}$ and evaluated the
results both w.r.t. running time and quality of answers. For these experiments
we used the EuroClim dataset.

Table 3 shows how the parameters impact the running time and accuracy. We can
see that $r_{J}$ has the largest impact, the running time increasing with
smaller values of $r_{J}$. This is because $r_{J}$ determines the length of
the minhash signature, and shorter signatures imply a higher chance of
matching and forming a candidate pair. On the other hand, the parameters do
not have much impact on the average accuracy of the fifth-best result
($\bar{J}@5$).

As the average quality does not change by much, we can conclude that the user
can set rows and bands primarily based on how many initial pairs they want to
find, but that the settings we have used throughout these experiments
($r_{J}=10$, $b_{J}=40$) seem to give a good balance.

Table 3: The effect of LSH parameters to running time (left) and average Jaccard of the fifth best result $\bar{J}@5$ (right) depending on the number ($b$) and the width ($r$) of bands in LSH, for five repetitions and using EuroClim data. | time (s) | $\bar{J}@5$
---|---|---
| $r_{J}$ | $r_{J}$
$b_{J}$ | ${3}$ | ${5}$ | ${7}$ | ${10}$ | ${12}$ |  ${15}$ | ${3}$ | ${5}$ | ${7}$ | ${10}$ | ${12}$ | ${15}$
20 | $33.89$ | $21.34$ | $15.00$ | $6.94$ | $5.68$ |  $5.14$ | $0.69$ | $0.70$ | $0.63$ | $0.69$ | $0.50$ | $0.63$
40 | $45.71$ | $33.22$ | $23.09$ | $13.46$ | $11.30$ |  $9.54$ | $0.71$ | $0.73$ | $0.65$ | $0.72$ | $0.57$ | $0.67$
60 | $56.91$ | $40.77$ | $29.79$ | $18.59$ | $15.66$ |  $13.88$ | $0.73$ | $0.73$ | $0.65$ | $0.71$ | $0.62$ | $0.70$
80 | $68.86$ | $48.69$ | $35.61$ | $23.76$ | $20.35$ |  $17.73$ | $0.72$ | $0.71$ | $0.66$ | $0.73$ | $0.63$ | $0.70$

###  3.3 Extending Initial Pairs

The next phase of the Fier algorithm is the extension of the initial pairs. To
test this phase, we use the same pre-mined initial pairs for all algorithms
and compare extensions obtained with Fier_ext versus with the exhaustive
attempts of ReReMi. For the extensions, pre-bucketing as done by ReReMiBkt is
not expected to bring any benefits for ReReMi, as its cut-point algorithm is
very efficient (cf. Table 2). Fier_ext might extend some initial pairs with
literals that are somewhat inferior to the ones found by ReReMi, or it might
fail to find any extensions at all. On the other hand, it should be much
faster than ReReMi. For these tests we only consider MammalsW, DentalW and two
CMS datasets due to space reasons.

#### Extending once.

In the first test, we check how similar the extensions are after one round of
extensions. The results are presented in Fig. 4. This plot is similar to Fig.
3. As we can see, there are some initial pairs for which Fier_ext does not
find any valid extension, but for those that it does find, the results are
generally as good as those of ReReMi.

Figure 4: Comparing the accuracy of once extended initial pairs by Fier_ext and ReReMi. Each dot represents a pair of columns, and its location indicates the highest-accuracy initial pair Fier and ReReMi found. All axes range across the unit interval. Table 4: Accuracy, total number of extension steps, and time in seconds when extending the ReReMi initial pairs multiple times. All results are averages over 5 runs. |  |  | MammalsW | DentalW
---|---|---|---|---
algorithm | $r_{H}$ | $b_{H}$ | $J@10$ | # ext. | time (s) | $J@10$ | # ext. | time (s)
Fier_ext | $10$ | $10$ | $0.77$ | $296.4$ | $1471.74$ | $0.60$ | $535.8$ | $643.16$
|  | $20$ | $0.79$ | $329.0$ | $1664.60$ | $0.61$ | $547.8$ | $712.50$
|  | $40$ | $0.79$ | $354.8$ | $1764.90$ | $0.62$ | $543.8$ | $776.40$
| $20$ | $10$ | $0.72$ | $112.6$ | $768.05$ | $0.57$ | $500.2$ | $390.47$
|  | $20$ | $0.72$ | $130.6$ | $973.91$ | $0.58$ | $523.0$ | $472.29$
|  | $40$ | $0.75$ | $237.4$ | $1383.91$ | $0.59$ | $530.6$ | $578.33$
| $30$ | $10$ | $0.68$ | $60.0$ | $438.41$ | $0.54$ | $402.8$ | $245.93$
|  | $20$ | $0.70$ | $65.4$ | $641.48$ | $0.57$ | $462.2$ | $348.41$
|  | $40$ | $0.71$ | $101.0$ | $990.65$ | $0.57$ | $512.8$ | $483.04$
| $40$ | $10$ | $0.63$ | $38.4$ | $285.89$ | $0.51$ | $229.0$ | $125.20$
|  | $20$ | $0.68$ | $54.6$ | $473.24$ | $0.53$ | $329.0$ | $221.54$
|  | $40$ | $0.70$ | $62.0$ | $727.29$ | $0.54$ | $426.2$ | $395.37$
ReReMi |  |  | $0.83$ | $410.0$ | $3263.28$ | $0.61$ | $517.0$ | $1494.44$
|  |  | CMS7199 | CMS116395
algorithm | $r_{H}$ | $b_{H}$ | $J@10$ | # ext. | time (s) | $J@10$ | # ext. | time (s)
Fier_ext | $10$ | $10$ | $0.82$ | $28.8$ | $90.08$ | $0.77$ | $90.0$ | $1072.10$
|  | $20$ | $0.82$ | $40.0$ | $181.25$ | $0.78$ | $106.8$ | $1906.59$
|  | $40$ | $0.82$ | $47.0$ | $299.37$ | $0.80$ | $126.4$ | $2646.13$
| $20$ | $10$ | $0.80$ | $4.0$ | $7.56$ | $0.72$ | $11.4$ | $202.65$
|  | $20$ | $0.81$ | $6.4$ | $17.68$ | $0.73$ | $20.4$ | $303.56$
|  | $40$ | $0.81$ | $8.6$ | $31.13$ | $0.74$ | $41.8$ | $532.56$
| $30$ | $10$ | $0.80$ | $0.6$ | $6.82$ | $0.71$ | $5.0$ | $148.69$
|  | $20$ | $0.80$ | $1.4$ | $12.58$ | $0.72$ | $5.6$ | $228.74$
|  | $40$ | $0.81$ | $3.0$ | $23.88$ | $0.72$ | $8.4$ | $421.66$
| $40$ | $10$ | $0.79$ | $0.0$ | $7.35$ | $0.71$ | $1.4$ | $117.36$
|  | $20$ | $0.79$ | $0.6$ | $13.86$ | $0.71$ | $2.8$ | $223.92$
|  | $40$ | $0.80$ | $0.8$ | $25.98$ | $0.71$ | $2.8$ | $396.22$
ReReMi |  |  | $0.83$ | $55.0$ | $695.85$ | $0.81$ | $154.0$ | $7626.95$
Table 5: Accuracy, number of extension steps, number of resulting redescriptions and time in seconds for full redescription mining. All results are averages over 5 runs. |  |  | MammalsW | DentalW
---|---|---|---|---
alg. | $r_{H}$ | $b_{H}$ | $J@10$ | # ext. | # results | time | $J@10$ | # ext. | # results | time
Fier_full | $20$ | $20$ | $0.74$ | $94.6$ | $32.4$ | $765$ | $0.57$ | $486.8$ | $216.8$ | $445$
|  | $40$ | $0.72$ | $75.0$ | $24.0$ | $901$ | $0.59$ | $505.8$ | $222.6$ | $549$
| $30$ | $20$ | $0.63$ | $39.0$ | $14.2$ | $446$ | $0.52$ | $423.8$ | $189.0$ | $315$
|  | $40$ | $0.69$ | $66.8$ | $20.8$ | $705$ | $0.55$ | $454.6$ | $202.6$ | $447$
| $40$ | $20$ | $0.63$ | $28.0$ | $10.6$ | $333$ | $0.51$ | $258.8$ | $139.6$ | $199$
|  | $40$ | $0.58$ | $37.0$ | $13.2$ | $500$ | $0.53$ | $362.8$ | $178.2$ | $358$
ReReMi |  |  | $0.83$ | $410.0$ | $71.0$ | $3401$ | $0.61$ | $517.0$ | $93.0$ | $3063$
ReReMiBkt |  |  | $0.83$ | $410.0$ | $71.0$ | $3381$ | $0.63$ | $512.0$ | $90.0$ | $1866$
|  |  | CMS7199 | CMS116395
alg. | $r_{H}$ | $b_{H}$ | $J@10$ | # ext. | # results | time | $J@10$ | # ext. | # results | time
Fier_full | $20$ | $20$ | $0.75$ | $12.2$ | $18.8$ | $34$ | $0.76$ | $19.6$ | $21.4$ | $463$
|  | $40$ | $0.77$ | $23.2$ | $23.0$ | $53$ | $0.76$ | $22.8$ | $23.8$ | $592$
| $30$ | $20$ | $0.74$ | $3.6$ | $17.0$ | $30$ | $0.75$ | $4.2$ | $17.2$ | $381$
|  | $40$ | $0.75$ | $8.8$ | $19.8$ | $41$ | $0.75$ | $6.4$ | $18.4$ | $517$
| $40$ | $20$ | $0.73$ | $3.0$ | $17.6$ | $31$ | $0.73$ | $0.6$ | $16.0$ | $367$
|  | $40$ | $0.72$ | $2.4$ | $17.2$ | $41$ | $0.74$ | $1.4$ | $16.4$ | $510$
ReReMi |  |  | $0.83$ | $55.0$ | $22.0$ | $1032$ | $0.81$ | $154.0$ | $45.0$ | $96$
ReReMiBkt |  |  | $0.83$ | $55.0$ | $22.0$ | $957$ | $0.83$ | $79.0$ | $29.0$ | $5796$

#### Extending multiple times.

Genuine redescription mining involves extending the pairs more than just once.
At this point it is no longer sensible to compare the accuracies of individual
initial pairs, as small differences in each extension step can yield vastly
different redescriptions, and the greedy extension done by ReReMi can
sometimes yield worse results than Fier_ext. Instead, we consider the average
Jaccard of the 10th best result ($\bar{J}@10$). We also measure the number of
extension steps done by the algorithms _in total_. That is, if there are $100$
initial pairs, and each pair is extended $3$ times on both sides, the total
number of extension steps is $600$. Notice that ReReMi stops extensions when
it cannot find any literal to extend with. The results of this experiment are
presented in Table 4. Further parameter combinations are presented in Appendix
A.1.

As can be seen in Table 4, the average $\bar{J}@10$ for Fier_ext is somewhat
less than for ReReMi. With appropriate parameters, however, the difference is
small. On the other hand, the running times can differ significantly. With
DentalW for instance, ReReMi takes almost $1500$ seconds while Fier_ext
achieves the same accuracy in half the time (using $r_{H}=10,b_{H}=20$), or
comparable accuracy in less than a quarter of the time (using
$r_{H}=30,b_{H}=20$). We can also see that for the extensions, smaller values
of $r_{H}$ yield higher running times. This is because with smaller $r_{H}$,
LSH is more random and tends to generate much more potential extensions. On
the other hand, higher values of $b_{H}$ tend to increase the accuracy, as LSH
then simply does more repetitions.

###  3.4 Building Full Redescriptions

The final test is for the full algorithm Fier_full, where we use LSH for both
initial pairs and extensions. The results are presented in Table 5 with
further results in Appendix A.2.

For the CMS datasets, Fier_full cannot find many extensions. This situation is
the same as in Table 4, indicating that it is probably a feature of the
extension algorithm rather than of the initial pairs. On the other hand, the
average accuracies are still quite high, indicating that the lack of
extensions might be a consequence of having high-accuracy initial pairs that
cannot be extended with higher accuracy. The running times of the algorithm
are very low, showing a significant improvement over ReReMi and ReReMiBkt.

##  4 Conclusions

Locality-sensitive hashing in Fier significantly speeds up finding the initial
pairs and extending them, without sacrificing the quality. Handling intervals
from numerical variables requires a more complex approach, especially for the
initial pairs, but it pays off with notably improved running times. Based on
our experiments, we can recommend using Fier for the initialisation of greedy
redescription mining without reservation. The extension phase is somewhat more
sensitive to hyperparameters and is usually not as significant a bottleneck.
For larger data sets or for quick or interactive testing, we can recommend
Fier_full.

## References

  * [1] Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-wise independent permutations. In: STOC’98. pp. 327–336 (1998). https://doi.org/10.1145/276698.276781
  * [2] Cochez, M., Mou, H.: Twister tries: Approximate hierarchical agglomerative clustering for average distance in linear time. In: SIGMOD’15. pp. 505–517 (2015). https://doi.org/10.1145/2723372.2751521
  * [3] Cohen, E., Datar, M., Fujiwara, S., Gionis, A., Indyk, P., Motwani, R., Ullman, J.D., Yang, C.: Finding interesting associations without support pruning. IEEE Trans. Knowl. Data Eng. 13(1), 64–78 (2001). https://doi.org/10.1109/69.908981
  * [4] Das, A.S., Datar, M., Garg, A., Rajaram, S.: Google news personalization: Scalable online collaborative filtering. In: WWW’07. pp. 271–280 (2007). https://doi.org/10.1145/1242572.1242610
  * [5] Eronen, J.T., Polly, P.D., Fred, M., Damuth, J., Frank, D.C., Mosbrugger, V., Scheidegger, C., Stenseth, N.C., Fortelius, M.: Ecometrics: The traits that bind the past and present together. Integrative Zoology 5(2), 88–101 (2010). https://doi.org/10.1111/j.1749-4877.2010.00192.x
  * [6] Fernandes, N., Kawamoto, Y., Murakami, T.: Locality sensitive hashing with extended differential privacy. In: ESORICS’21. pp. 563–583 (2021). https://doi.org/10.1007/978-3-030-88428-4_28
  * [7] Fortelius, M., Eronen, J., Jernvall, J., Liu, L., Pushkina, D., Rinne, J., Tesakov, A., Vislobokova, I., Zhang, Z., Zhou, L.: Fossil mammals resolve regional patterns of Eurasian climate change over 20 million years. Evol. Ecol. Res. 4(7), 1005–1016 (2002)
  * [8] Galbrun, E., Miettinen, P.: From black and white to full color: Extending redescription mining outside the Boolean world. Stat. Anal. Data Min. 5(4), 284–303 (2012). https://doi.org/10.1002/sam.11145
  * [9] Galbrun, E., Miettinen, P.: Analysing political opinions using redescription mining. In: ICDM’16 Workshops. pp. 422–427 (2016). https://doi.org/10.1109/ICDMW.2016.0066
  * [10] Galbrun, E., Miettinen, P.: Mining Redescriptions with Siren. ACM Trans. Knowl. Discov. Data 12(1), 6 (2018). https://doi.org/10.1145/3007212
  * [11] Galbrun, E., Tang, H., Fortelius, M., Žliobaitė, I.: Computational biomes: The ecometrics of large mammal teeth. Palaeontol. Electron. (2018). https://doi.org/10.26879/786
  * [12] Gallo, A., Miettinen, P., Mannila, H.: Finding subgroups having several descriptions: Algorithms for redescription mining. In: SDM’08. pp. 334–345 (2008). https://doi.org/10.1137/1.9781611972788.30
  * [13] Helsingin Sanomat: Parliamentary elections 2011: Candidate responses to helsingin sanomat candidate selector (2016), http://urn.fi/urn:nbn:fi:fsd:T-FSD2701, version 2.1
  * [14] Hijmans, R.J., Cameron, S.E., Parra, L.J., Jones, P.G., Jarvis, A.: Very High Resolution Interpolated Climate Surfaces for Global Land Areas. Int. J. Climatol. 25, 1965–1978 (2005), www.worldclim.org
  * [15] Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: STOC’98. pp. 604–613 (1998). https://doi.org/10.1145/276698.276876
  * [16] Kalofolias, J., Galbrun, E., Miettinen, P.: From sets of good redescriptions to good sets of redescriptions. In: ICDM’16. pp. 211–220 (2016). https://doi.org/10.1109/ICDM.2016.0032
  * [17] Karjalainen, M., Galbrun, E., Miettinen, P.: Serenade: An approach for differentially private greedy redescription mining. In: Proc. of the 20th anniv. Workshop on KDID at ECML-PKDD’22. pp. 31–46. CEUR Workshop Proceedings (2022)
  * [18] Leskovec, J., Rajaraman, A., Ullman, J.: Mining of massive data sets. Cambridge university press (2020)
  * [19] Liu, L., Galbrun, E., Tang, H., Kaakinen, A., Zhang, Z., Zhang, Z., Žliobaitė, I.: The emergence of modern zoogeographic regions in Asia examined through climate–dental trait association patterns. Nat. Commun. 14(1) (2023). https://doi.org/10.1038/s41467-023-43807-w
  * [20] Meeng, M., Knobbe, A.: For real: A thorough look at numeric attributes in subgroup discovery. Dat Min. Knowl. Discov. 35(1), 158–212 (2021). https://doi.org/10.1007/s10618-020-00703-x
  * [21] Mihelčić, M., Džeroski, S., Lavrač, N., Šmuc, T.: A framework for redescription set construction. Expert Syst. Appl. 68, 196–215 (2017). https://doi.org/10.1016/j.eswa.2016.10.012
  * [22] Mihelčić, M., Miettinen, P.: Differentially private tree-based redescription mining. Data Min. Knowl. Discov. 37(4), 1548–1590 (2023). https://doi.org/10.1007/S10618-023-00934-8
  * [23] Mihelčić, M., Šimić, G., Babić-Leko, M., Lavrač, N., Džeroski, S., Šmuc, T.: Using redescription mining to relate clinical and biological characteristics of cognitively impaired and alzheimer’s disease patients. PLOS ONE 12(10) (2017). https://doi.org/10.1371/journal.pone.0187364
  * [24] Murdock, G.P.: Ethnographc atlas: A summary. Ethnology 6(2), 109–236 (1967)
  * [25] Ramakrishnan, N., Kumar, D., Mishra, B., Potts, M., Helm, R.F.: Turning CARTwheels: An alternating algorithm for mining redescriptions. In: KDD’04. pp. 266–275 (2004). https://doi.org/10.1145/1014052.1014083
  * [26] Zinchenko, T., Galbrun, E., Miettinen, P.: Mining Predictive Redescriptions with Trees. In: ICDM’15 Workshops. pp. 1672–1675 (2015). https://doi.org/10.1109/ICDMW.2015.123

##  Appendix A Further Experimental Evaluation

###  A.1 Extending Initial Pairs

#### Extending multiple times.

The full results for extending pre-mined initial pairs are presented in Table
6.

Table 6: Accuracy, total number of extensions, and time in seconds when extending the ReReMi initial pairs multiple times. All results are averages over 5 runs. |  |  | MammalsW | DentalW
---|---|---|---|---
alg. | $r_{H}$ | $b_{H}$ | $J@10$ | # of ext. | time (s) | $J@10$ | # of ext. | time (s)
Fier_ext | $10$ | $10$ | $0.7714$ | $296.4$ | $1471.736$ | $0.6042$ | $535.8$ | $643.160\,000\,000\,000\,1$
|  | $20$ | $0.788$ | $329.0$ | $1664.6$ | $0.609$ | $547.8$ | $712.504$
|  | $40$ | $0.7862$ | $354.8$ | $1764.898$ | $0.6152$ | $543.8$ | $776.4$
|  | $80$ | $0.8244$ | $447.8$ | $2176.341\,999\,999\,999\,6$ | $0.613\,599\,999\,999\,999\,9$ | $545.6$ | $819.516$
| $20$ | $10$ | $0.718$ | $112.6$ | $768.05$ | $0.572\,599\,999\,999\,999\,9$ | $500.2$ | $390.47$
|  | $20$ | $0.721\,399\,999\,999\,999\,9$ | $130.6$ | $973.910\,000\,000\,000\,1$ | $0.584\,199\,999\,999\,999\,9$ | $523.0$ | $472.288$
|  | $40$ | $0.7468$ | $237.4$ | $1383.914$ | $0.591\,999\,999\,999\,999\,9$ | $530.6$ | $578.334\,000\,000\,000\,1$
|  | $80$ | $0.7522$ | $259.6$ | $1674.146$ | $0.5986$ | $541.0$ | $727.704$
| $30$ | $10$ | $0.6778$ | $60.0$ | $438.406\,000\,000\,000\,06$ | $0.5424$ | $402.8$ | $245.926\,000\,000\,000\,02$
|  | $20$ | $0.700\,399\,999\,999\,999\,9$ | $65.4$ | $641.48$ | $0.5678$ | $462.2$ | $348.409\,999\,999\,999\,97$
|  | $40$ | $0.7132$ | $101.0$ | $990.647\,999\,999\,999\,9$ | $0.572\,399\,999\,999\,999\,9$ | $512.8$ | $483.035\,999\,999\,999\,94$
|  | $80$ | $0.7212$ | $133.8$ | $1369.424\,000\,000\,000\,2$ | $0.5772$ | $519.0$ | $686.516\,000\,000\,000\,1$
| $40$ | $10$ | $0.6268$ | $38.4$ | $285.886$ | $0.5128$ | $229.0$ | $125.196$
|  | $20$ | $0.6836$ | $54.6$ | $473.238$ | $0.5344$ | $329.0$ | $221.538$
|  | $40$ | $0.697$ | $62.0$ | $727.286$ | $0.538$ | $426.2$ | $395.374$
|  | $80$ | $0.701\,199\,999\,999\,999\,9$ | $63.6$ | $1162.734$ | $0.5658$ | $480.0$ | $658.671\,999\,999\,999\,9$
| $50$ | $10$ | $0.6202$ | $34.6$ | $209.512$ | $0.481\,799\,999\,999\,999\,95$ | $105.4$ | $79.452\,000\,000\,000\,01$
|  | $20$ | $0.627$ | $40.8$ | $333.932$ | $0.499\,399\,999\,999\,999\,96$ | $168.4$ | $133.859\,999\,999\,999\,99$
|  | $40$ | $0.665\,999\,999\,999\,999\,9$ | $53.8$ | $677.988$ | $0.5164$ | $255.0$ | $256.282\,000\,000\,000\,04$
|  | $80$ | $0.6926$ | $57.2$ | $1122.534$ | $0.538$ | $349.8$ | $538.832$
ReReMi |  |  | $0.829$ | $410.0$ | $3263.28$ | $0.609$ | $517.0$ | $1494.44$
|  |  | CMS7199 | CMS116395
alg. | $r_{H}$ | $b_{H}$ | $J@10$ | # of ext. | time (s) | $J@10$ | # of ext. | time (s)
Fier_ext | $10$ | $10$ | $0.817\,799\,999\,999\,999\,9$ | $28.8$ | $90.084\,000\,000\,000\,02$ | $0.77$ | $90.0$ | $1072.096$
|  | $20$ | $0.818\,800\,000\,000\,000\,1$ | $40.0$ | $181.25$ | $0.7758$ | $106.8$ | $1906.588\,000\,000\,000\,2$
|  | $40$ | $0.822\,199\,999\,999\,999\,9$ | $47.0$ | $299.37$ | $0.7984$ | $126.4$ | $2646.127\,999\,999\,999\,7$
|  | $80$ | $0.8228$ | $52.4$ | $383.05$ | $0.803\,000\,000\,000\,000\,2$ | $127.6$ | $4366.603\,999\,999\,999$
| $20$ | $10$ | $0.803\,800\,000\,000\,000\,1$ | $4.0$ | $7.564$ | $0.7194$ | $11.4$ | $202.652$
|  | $20$ | $0.8058$ | $6.4$ | $17.676$ | $0.730\,399\,999\,999\,999\,9$ | $20.4$ | $303.563\,999\,999\,999\,96$
|  | $40$ | $0.813\,999\,999\,999\,999\,8$ | $8.6$ | $31.131\,999\,999\,999\,998$ | $0.7402$ | $41.8$ | $532.560\,000\,000\,000\,1$
|  | $80$ | $0.8164$ | $14.6$ | $60.589\,999\,999\,999\,996$ | $0.752$ | $55.0$ | $964.702$
| $30$ | $10$ | $0.795\,800\,000\,000\,000\,1$ | $0.6$ | $6.82$ | $0.710\,199\,999\,999\,999\,9$ | $5.0$ | $148.69$
|  | $20$ | $0.800\,999\,999\,999\,999\,9$ | $1.4$ | $12.575\,999\,999\,999\,999$ | $0.717\,799\,999\,999\,999\,9$ | $5.6$ | $228.744$
|  | $40$ | $0.809\,800\,000\,000\,000\,1$ | $3.0$ | $23.876$ | $0.719\,799\,999\,999\,999\,9$ | $8.4$ | $421.656\,000\,000\,000\,06$
|  | $80$ | $0.8116$ | $4.6$ | $46.206$ | $0.7236$ | $9.4$ | $730.606$
| $40$ | $10$ | $0.791$ | $0.0$ | $7.354\,000\,000\,000\,001$ | $0.706$ | $1.4$ | $117.359\,999\,999\,999\,99$
|  | $20$ | $0.7942$ | $0.6$ | $13.857\,999\,999\,999\,999$ | $0.708\,599\,999\,999\,999\,9$ | $2.8$ | $223.916$
|  | $40$ | $0.7982$ | $0.8$ | $25.977\,999\,999\,999\,998$ | $0.706$ | $2.8$ | $396.219\,999\,999\,999\,97$
|  | $80$ | $0.7964$ | $0.8$ | $49.286\,000\,000\,000\,01$ | $0.713\,399\,999\,999\,999\,9$ | $4.6$ | $732.576$
| $50$ | $10$ | $0.791$ | $0.0$ | $7.975\,999\,999\,999\,999$ | $0.706$ | $0.6$ | $120.486\,000\,000\,000\,02$
|  | $20$ | $0.791$ | $0.0$ | $14.9$ | $0.706$ | $0.8$ | $197.45$
|  | $40$ | $0.7942$ | $0.4$ | $28.248$ | $0.706\,199\,999\,999\,999\,9$ | $1.6$ | $368.977\,999\,999\,999\,95$
|  | $80$ | $0.797$ | $0.8$ | $55.203\,999\,999\,999\,99$ | $0.708\,599\,999\,999\,999\,9$ | $2.8$ | $730.672\,000\,000\,000\,1$
ReReMi |  |  | $0.827$ | $55.0$ | $695.85$ | $0.807$ | $154.0$ | $7626.95$

###  A.2 Building Full Redescriptions

The results are presented in Table 7.

Table 7: Accuracy, total number of extensions, total number of resulting redescriptions, and total time in seconds for full redescription mining. All results are averages over 5 runs. |  |  | MammalsW | DentalW
---|---|---|---|---
alg. | $r_{H}$ | $b_{H}$ | $J@10$ | # ext. | # results | time | $J@10$ | # ext. | # results | time
Fier_full | $20$ | $10$ | $0.6794$ | $60.4$ | $19.2$ | $517.910\,000\,000\,000\,1$ | $0.5514$ | $446.8$ | $194.6$ | $345.454$
|  | $20$ | $0.742$ | $94.6$ | $32.4$ | $764.646$ | $0.5702$ | $486.8$ | $216.8$ | $444.752\,000\,000\,000\,07$
|  | $40$ | $0.720\,399\,999\,999\,999\,9$ | $75.0$ | $24.0$ | $900.902$ | $0.5854$ | $505.8$ | $222.6$ | $548.526$
| $30$ | $10$ | $0.602\,200\,000\,000\,000\,1$ | $33.2$ | $12.4$ | $285.202$ | $0.5322$ | $348.2$ | $169.0$ | $216.944\,000\,000\,000\,02$
|  | $20$ | $0.6316$ | $39.0$ | $14.2$ | $445.631\,999\,999\,999\,95$ | $0.524$ | $423.8$ | $189.0$ | $315.474$
|  | $40$ | $0.688\,800\,000\,000\,000\,1$ | $66.8$ | $20.8$ | $704.894$ | $0.5514$ | $454.6$ | $202.6$ | $447.442$
| $40$ | $10$ | $0.5572$ | $28.2$ | $13.0$ | $213.428\,000\,000\,000\,03$ | $0.477\,599\,999\,999\,999\,97$ | $227.6$ | $124.0$ | $144.465\,999\,999\,999\,98$
|  | $20$ | $0.6332$ | $28.0$ | $10.6$ | $332.844$ | $0.509\,400\,000\,000\,000\,1$ | $258.8$ | $139.6$ | $199.18$
|  | $40$ | $0.576\,800\,000\,000\,000\,1$ | $37.0$ | $13.2$ | $500.09$ | $0.527\,400\,000\,000\,000\,1$ | $362.8$ | $178.2$ | $357.586$
ReReMi |  |  | $0.827$ | $410$ | $71$ | $3401.796$ | $0.609$ | $517$ | $93$ | $3063.450\,799$
ReReMiBkt |  |  | $0.829$ | $410$ | $71$ | $3381.180\,000\,000\,000\,3$ | $0.63$ | $512$ | $90$ | $1866.48$
|  |  | CMS7199 | CMS116395
alg. | $r_{H}$ | $b_{H}$ | $J@10$ | # ext. | # results | time | $J@10$ | # of ext. | # results | time
Fier_full | $20$ | $10$ | $0.7442$ | $8.8$ | $18.4$ | $30.137\,999\,999\,999\,998$ | $0.7416$ | $9.6$ | $19.2$ | $352.42$
|  | $20$ | $0.750\,200\,000\,000\,000\,1$ | $12.2$ | $18.8$ | $33.986\,000\,000\,000\,004$ | $0.7558$ | $19.6$ | $21.4$ | $462.912$
|  | $40$ | $0.7654$ | $23.2$ | $23.0$ | $52.64$ | $0.761\,400\,000\,000\,000\,1$ | $22.8$ | $23.8$ | $591.665\,999\,999\,999\,9$
| $30$ | $10$ | $0.7416$ | $2.0$ | $19.8$ | $23.75$ | $0.725\,399\,999\,999\,999\,9$ | $1.6$ | $17.6$ | $302.238$
|  | $20$ | $0.7426$ | $3.6$ | $17.0$ | $30.312$ | $0.7458$ | $4.2$ | $17.2$ | $380.928$
|  | $40$ | $0.7498$ | $8.8$ | $19.8$ | $41.31$ | $0.7486$ | $6.4$ | $18.4$ | $517.136$
| $40$ | $10$ | $0.733\,200\,000\,000\,000\,1$ | $0.6$ | $15.0$ | $24.004$ | $0.7236$ | $1.0$ | $15.4$ | $295.44$
|  | $20$ | $0.7312$ | $3.0$ | $17.6$ | $30.812$ | $0.7338$ | $0.6$ | $16.0$ | $366.614\,000\,000\,000\,03$
|  | $40$ | $0.724\,599\,999\,999\,999\,9$ | $2.4$ | $17.2$ | $40.564$ | $0.7358$ | $1.4$ | $16.4$ | $510.042\,000\,000\,000\,03$
ReReMi |  |  | $0.827$ | $55$ | $22$ | $1032.46$ | $0.807$ | $154$ | $45$ | $9588.07$
ReReMiBkt |  |  | $0.827$ | $55$ | $22$ | $957.24$ | $0.83$ | $79$ | $29$ | $5796.780\,000\,000\,001$
|  |  | Ethno | VAA
alg. | $r_{H}$ | $b_{H}$ | $J@10$ | # ext. | # results | time | $J@10$ | # of ext. | # results | time
Fier_full | $20$ | $10$ | $0.5542$ | $79.2$ | $50.2$ | $38.266$ | $0$ | $0$ | $0$ | $0$
|  | $20$ | $0.552\,999\,999\,999\,999\,9$ | $105.6$ | $55.8$ | $53.456$ | $0.389$ | $0.0$ | $1.0$ | $1.57$
|  | $40$ | $0.553\,800\,000\,000\,000\,1$ | $137.4$ | $66.2$ | $73.630\,000\,000\,000\,01$ | $0$ | $0$ | $0$ | $0$
| $30$ | $10$ | $0.494\,200\,000\,000\,000\,03$ | $30.0$ | $37.0$ | $14.85$ | $0$ | $0$ | $0$ | $0$
|  | $20$ | $0.509\,400\,000\,000\,000\,1$ | $39.4$ | $34.8$ | $21.962$ | $0$ | $0$ | $0$ | $0$
|  | $40$ | $0.5464$ | $69.6$ | $45.4$ | $33.822$ | $0$ | $0$ | $0$ | $0$
| $40$ | $10$ | $0.4784$ | $6.0$ | $27.8$ | $9.84$ | $0$ | $0$ | $0$ | $0$
|  | $20$ | $0.454$ | $13.0$ | $25.0$ | $12.224$ | $0.356$ | $0.0$ | $1.0$ | $1.71$
|  | $40$ | $0.4988$ | $26.6$ | $35.2$ | $17.568$ | $0$ | $0$ | $0$ | $0$
ReReMi |  |  | $0.652$ | $13$ | $3$ | $184.417$ | $0.39$ | $6$ | $4$ | $7.68$