# Hyperbolic groups with logarithmic separation profile

Nir Lazarovich and Corentin Le Coz Supported by the Israel Science Foundation
(grant no. 1562/19), and by the German-Israeli Foundation for Scientific
Research and Development.Supported by the Israel Science Foundation (grant no.
2919/19)

###### Abstract

We prove that hyperbolic groups with logarithmic separation profiles split
over cyclic groups. This shows that such groups can be inductively built from
Fuchsian groups and free groups by amalgamations and HNN extensions over
finite or virtually cyclic groups. However, we show that not all groups
admitting such a hierarchy have logarithmic separation profile by providing an
example of a surface amalgam over a cyclic group with superlogarithmic
separation profile.

##  1 Introduction

The separation profile was first introduced by Benjamini-Schramm-Timár [1] in
2012. It measures large scale connectivity of infinite graphs, in the spirit
of the celebrated theorem of Lipton and Trajan for planar graphs [12].

######  Definition 1.1 (Benjamini-Schramm-Timár [1]).

Given a finite graph $\Gamma=(V\Gamma,E\Gamma)$, we shall say that a set of
vertices $C\subset V\Gamma$ cuts (or separates) the graph $\Gamma$ if the
connected components of the subgraph induced by $V\Gamma-C$ contain at most
$\frac{1}{2}|V\Gamma|$ vertices.

We define the cut of the graph $\Gamma$, denoted $\operatorname{cut}\Gamma$,
as the minimal size of a separating set.

We define the separation profile of a bounded degree infinite graph $G$ as the
following non-decreasing function from $\mathbb{N}^{*}$ to $\mathbb{N}^{*}$:

$\operatorname{sep}_{G}(n)=\sup_{\Gamma\subset G,|V\Gamma|\leq
n}\operatorname{cut}\Gamma$

We shall consider such function endowed with the partial order defined by
$g\preceq h$ if and only if there exists $D>0$ such that $g(n)\leq Dh(Dn)+D$
for any $n\geq D$. We denote by $\asymp$ and $\prec$ the associated
equivalence relation and strict partial order, respectively.

As noticed in [1], the factor $1/2$ does not play an important role in the
previous definition. Replacing it by any $\beta\in(0,1)$ would give an
equivalent profile.

The separation profile is a coarse-geometric monotone invariant (see
Proposition 3.1). To our knowledge, the only such invariants that were
previously defined are volume growth and asymptotic dimension [7]. The
separation profile is a much finer invariant and has been generalized by Hume-
Mackay-Tessera [9, 10] into a spectrum of profiles called Poincaré profiles.
For a survey on this topic, we refer to the first part of the thesis of the
second author [11].

It is proved in [1] (see also [8]) that if a hyperbolic group has
$\operatorname{sep}_{G}(n)\prec\log(n)$ then $\operatorname{sep}_{G}(n)$ is
bounded and $G$ is virtually free.

In this paper we investigate the smallest possible non-virtually free case,
namely $\operatorname{sep}_{G}(n)\preceq\log(n)$.

######  Theorem A.

Let $G$ be a hyperbolic group with $\operatorname{sep}_{G}(n)\preceq\log(n)$,
then $G$ is Fuchsian or splits over finite or virtually cyclic subgroups.

This theorem is proved in Section 2, but let us give here a sketch of proof.
The first step consists in showing that the spheres of $G$ have bounded
separating sets. This is done by projecting the separating set of some
suitable annulus. Then, we make these sphere separating sets converge in
$\partial G$. This implies the existence of local cut points in $\partial G$,
and the conclusion follows from Bowditch [3].

######  Corollary 1.2.

Let $G$ be a hyperbolic group without 2-torsion. If
$\operatorname{sep}_{G}(n)\preceq\log(n)$ then $G$ can be inductively built
from Fuchsian groups and free groups by amalgamations and HNN extensions over
finite or virtually cyclic groups.

###### Proof.

We can apply Theorem A to $G$. Either $G$ is Fuchsian and we are done.
Otherwise, $G$ splits over virtually cyclic groups. The edge groups are
virtually cyclic, hence quasiconvex in $G$. This implies that the vertex
groups of this splitting are quasiconvex and hence hyperbolic. By the
monotonicity of the separation profile, the separation profile of the vertex
groups $H$ is
$\operatorname{sep}_{H}(n)\preceq\operatorname{sep}_{G}(n)\asymp\log(n)$.
Therefore, we can successively apply Theorem A to split $G$ over virtually
cyclic subgroups. Using the Strong Accessibility by Louder-Touikan [13] this
process terminates. ∎

A group with conformal dimension at least one always has a separation profile
bounded below by $\log$, from [8]. Using a recent result of Carrasco-Mackay
[4] giving a characterization of hyperbolic groups with conformal dimension
one, we get the following corollary.

######  Corollary 1.3.

Let $G$ be a one-ended hyperbolic group with no $2$-torsion. If the (Ahlfors
regular) conformal dimension of $G$ is strictly greater than $1$, then its
separation profile is strictly greater than $\log$.

In this generality, to our knowledge this improves the previously known lower
bounds. We do not know if this is sharp.

Lower bounds on separation profiles can be obtained from Poincaré inequalities
in the boundary at infinity of hyperbolic groups, see Hume-Mackay-Tessera [9,
Theorem 13]. Finding general Poincaré inequalities is an important challenge
and this corollary can be seen as a step in this direction.

The following theorem shows that the converse of Theorem A (and the subsequent
corollaries) is false.

######  Theorem B.

Let $S$ be the surface amalgam obtained by gluing two closed orientable
hyperbolic surfaces along a closed filling curve in each. Then,
$\operatorname{sep}_{\pi_{1}S}(n)\succ\log(n)$.

From Carrasco-Mackay [4], such a group has conformal dimension equal to $1$.

From [9], a hyperbolic group with conformal dimension one always have a
separation profile bounded above by any $n^{\epsilon}$, with $\epsilon>0$. To
our knowledge, this is this is the first example of such a group whose
separation profile is not logarithmic. This implies in particular that the
conformal dimension is not attained [9, Theorem 11].

We believe that when the curves are not filling, the separation profile is
actually $\log$.

######  Question 1.4.

Let $S$ be a simple surface amalgam obtained by gluing two closed hyperbolic
orientable surfaces along simple curves. Do we have
$\operatorname{sep}\pi_{1}S\asymp\log$?

From Hume-Mackay-Tessera [9] study of relations between conformal dimension
and separation profiles, we as well can formulate the following question:

######  Question 1.5.

If a hyperbolic group has a separation profile bounded above by $n^{\epsilon}$
for every positive $\epsilon$, does it imply that it has conformal dimension
one?

Acknowledgments: The authors would like to thank John Mackay and Ilya Gekhtman
for interesting discussions.

##  2 Proof of Theorem A

Let $G$ be a one-ended hyperbolic group. By abuse of notation let us denote by
$G$ also the Cayley graph of $G$ with respect to some fixed finite generating
set, and assume it is $\delta$-hyperbolic. We denote by $o$ the identity
element of $G$. For every $R>0$, $B_{R}$ (resp. $S_{R}$) denote the ball
(resp. the sphere) of radius $R$ centred at $o$.

######  Definition 2.1.

For each $R>0$, let $\pi_{R}:G-B_{R}\to S_{R}$ be a projection defined by
$\pi_{R}(y)=[o,y]\cap S_{R}$, where $[o,y]$ is some choice of geodesic joining
$o$ and $y$.

For any $\alpha>0$, we call $\alpha$-step path any family of vertices
$v_{1},\ldots,v_{k}$ such that $d(v_{i},v_{i+1})\leq\alpha$ for any
$i=1,\ldots,k-1$.

######  Fact 2.2.

For each $R>0$, $\pi_{R}$ is $2\delta$-Lipschitz. As a consequence, there is a
constant $\delta^{\prime}$ such that the $\delta^{\prime}$-neighbourhood of
any sphere in $G$ is connected. Moreover, we can choose $\delta$ large enough
so that we can take $\delta^{\prime}=\delta$.

###### Proof.

The fact that the projection map $\pi_{R}$ is $2\delta$-Lipschitz is a
straightforward consequence of the $\delta$-slimness of geodesic triangles in
$G$. Let us prove the second assertion, let us take $x,y\in S_{R}$. From [2],
there is some $C$ such that there exist $x^{\prime},y^{\prime}\in S_{R}$ such
that $d(x,x^{\prime}),d(y,y^{\prime})\leq C$ satisfying that $x^{\prime}$ and
$y^{\prime}$ lie in some infinite connected component of $G-B_{R}$. Since $G$
is one-ended, $G-B_{R}$ contains a single infinite connected component $D$,
and thus $x^{\prime},y^{\prime}\in D$. The vertices $x^{\prime}$ and
$y^{\prime}$ can then be joined by a path in $G-B_{R}$. We can project this
path on $S_{R}$ using the map $\pi_{R}$. Since $\pi_{R}$ is
$2\delta$-Lipschitz, the projected path is a $2\delta$-step path in $S_{R}$.
It follows that the $\max(\delta,C)$-neighbourhood of any sphere of $G$ is
connected. ∎

In the sequel, we will assume that $\delta$ is chosen large enough so that the
spheres of $G$ are $\delta$-connected. This motivates the following
definition.

######  Definition 2.3.

We say that $G$ has bounded spheres separation if every $\delta$-neighbourhood
of a sphere has a cut-set of uniformly bounded size.

We are now able to state our key lemma.

######  Lemma 2.4.

If $G$ is hyperbolic and $\operatorname{sep}_{G}(n)\preceq\log(n)$, then $G$
has bounded spheres separation.

Before proving this lemma, let us give few definitions and a fact that we will
use in the proof. We shall denote $(S_{R})_{\delta}$ the
$\delta$-neighbourhood of the sphere $S_{R}$. Moreover, $A(R)$ (or simply $A$)
denotes the annulus $B_{3R}-B_{2R}$.

######  Definition 2.5.

Given $x\in S_{R}$ and $r>0$, let $\Sigma_{x}=\pi_{R}^{-1}(x)$ and
$\Sigma_{x,r}=\pi_{R}^{-1}(B(x,r))$ be respectively the shadow, and the
$r$-shadow of $x$ in $G$.

Let us write the sector $\Sigma^{A}_{x}=\Sigma_{x}\cap A$ and $r$-sector
$\Sigma^{A}_{x,r}=\Sigma_{x,r}\cap A$. Let finally
$\Sigma_{x}(r^{\prime})=\Sigma_{x}\cap(S_{r^{\prime}})_{\delta}$ for each
$r^{\prime}\geq R$ and $\Sigma^{A}_{D}=\bigcup_{x\in D}\Sigma^{A}_{x}$ for
each $D\subseteq S_{R}$ (see Figure 1).

Figure 1: Shadows and sectors

######  Fact 2.6.

There are constants $K,\alpha>0$ such that for all $R\gg 0$ and $D\subseteq
S_{R}$ we have

$K^{-1}\alpha^{R}|D|\leq|\Sigma^{A}_{D}|\leq K\alpha^{R}|D|.$

In particular,

$K^{-1}\alpha^{R}|S_{R}|\leq|A(R)|\leq K\alpha^{R}|S_{R}|.$

###### Proof.

This follows from the proof of the Shadow Lemma, see Coornaert [5, Proposition
6.1] (see also Gouëzel-Mathéus-Maucourant [6, Lemma 2.13]). ∎

###### Proof of Lemma 2.4.

It follows from Fact 2.6 that $|A(R)|\asymp\exp(R)$. Let $C\subset A(R)$ such
that each connected component of $A(R)-C$ contains at most $\beta|A(R)|$
vertices, with $\beta=\left({4|B_{8\delta}|^{3}K^{3}}\right)^{-1}$, where $K$
is given by Fact 2.6. From the assumption that
$\operatorname{sep}_{G}\preceq\log$, we can suppose
$|C|\preceq\log(|A(R)|)\preceq R$. Concretely, let $|C|\leq cR$ for some $c$.

Let $P\subset S_{R}$ be the set of all $x$ such that
$\Sigma_{x,6\delta}(r)\cap C\neq\emptyset$ for all $2R\leq r\leq 3R$. If $x\in
P$ then $|\Sigma^{A}_{x}\cap C|\geq R/12\delta$. Since the $6\delta$-sectors
of pairs of vertices that are $12\delta$ apart are disjoint, it follows that
$|P|\leq 12\delta c|B_{12\delta}|$. So, there is a uniform bound on the size
of $P_{\delta}$, the $\delta$-neighbourhood of $P$. It remains to show that
$P_{\delta}$ separates $(S_{R})_{\delta}$.

######  Claim 2.7.

There exists $K^{\prime}>0$ such that for every $R\gg 0$, if $x\in S_{R}-P$
then $\Sigma^{A}_{x}-C$ has a component $T_{x}$ of size
$|T_{x}|\geq\frac{1}{2K^{\prime}}|\Sigma^{A}_{x}|$.

###### Proof.

Since $x\notin P$, there exists $r\in[2R,3R]$ such that
$\Sigma_{x,6\delta}(r)\cap C=\emptyset$.

######  Fact 2.8.

$\Sigma_{B_{2\delta}(x)}(r)$ is contained in a single connected component of
$\Sigma^{A}_{x,6\delta}-C$

###### Proof.

Given two points $y_{1},y_{2}\in\Sigma_{x,2\delta}(r)$, if $z$ is a vertex on
a geodesic joining $y_{1}$ and $y_{2}$, then it is at distance at most
$\delta$ from a point $z^{\prime}\in[o,y_{1}]\cup[o,y_{2}]$. The
$\delta$-slimness of the triangle given by $o,z$ and $z^{\prime}$ implies that
$\pi_{R}(z)$ is at distance at most $4\delta$ from $x$. Projecting the
geodesic $[y_{1},y_{2}]$ using $\pi_{r}$ gives a $2\delta$-step path joining
$y_{1}$ and $y_{2}$ in $\Sigma_{x,4\delta}\cap S_{r}$. By proceeding to an
interpolation process, we obtain a path joining $y_{1}$ and $y_{2}$ in
$\Sigma_{x,6\delta}\cap(S_{r})_{\delta}=\Sigma_{x,6\delta}(r)$. Since
$\Sigma_{x,6\delta}(r)$ do not meet $C$ and is included in $A$, this means
exactly that $\Sigma_{x,2\delta}(r)$ is contained in a single connected
component of $\Sigma^{A}_{x,6\delta}-C$. ∎

Let $T_{x}$ be the component of $\Sigma^{A}_{x,6\delta}-C$ that contains
$\Sigma_{B_{2\delta}(x)}(r)$. We shall consider shadows of vertices in
$\Sigma_{x}(2R)$ and their intersection with $A$. In a similar way as in Fact
2.6, we have a constant $K^{\prime}$ such that any subset
$Q\subset\Sigma_{x}(2R)$ satisfies

(2.1)
$\displaystyle(K^{\prime})^{-1}\frac{\Sigma_{Q}^{A}}{\Sigma_{x}^{A}}\leq\frac{|Q|}{\Sigma_{x}(2R)}\leq
K^{\prime}\frac{\Sigma_{Q}^{A}}{\Sigma_{x}^{A}}$

Let $Q_{x}$ be the collection of all points $y\in\Sigma_{x,2\delta}(2R)$ such
that $\Sigma_{y,4\delta}^{A}\cap C\neq\emptyset$. Since $|C|\leq cR$ it
follows that $|Q_{x}|\leq c|B_{4\delta}|R\asymp R$. Since
$|\Sigma_{B_{2\delta}(x)}(2R)|\asymp\exp(R)$, the complementary set
$Q_{x}^{c}=\Sigma_{B_{2\delta}(x)}(2R)-Q_{x}$ satisfies

(2.2) $\displaystyle|Q_{x}^{c}|\geq\frac{1}{2}|\Sigma_{x}(2R)|,$

for any large enough $R$.

For points $y\in Q_{x}^{c}$, in a similar manner as in Fact 2.8,
$\Sigma_{y}^{A}$ is contained in a single connected component of
$\Sigma^{A}_{x,6\delta}-C$ and intersects $\Sigma_{B_{2\delta}(x)}(r)$. Thus,
$\Sigma_{y}^{A}\subseteq T_{x}$. Therefore we have
$\Sigma_{Q_{x}^{c}}^{A}=\bigcup_{y\in Q_{x}^{c}}\Sigma_{y}^{A}\subset T_{x}$,
which implies $|T_{x}|\geq\frac{1}{2K^{\prime}}\Sigma_{x}^{A}$ from (2.1) and
(2.2). ∎

Let $D^{\prime}\subset(S_{R})_{\delta}-P_{\delta}$ be a connected subset. We
need to show that $|D^{\prime}|\leq\frac{|(S_{R})_{\delta}|}{2}$. Let $D$ be
the set of elements of $S_{R}$ that are at distance at most $\delta$ from
$D^{\prime}$. Recall that $\Sigma^{A}_{D}=\bigcup_{x\in D}\Sigma^{A}_{x}$, and
define similarly $T_{D}=\bigcup_{x\in D}T_{x}$, with $T_{x}$ given by Claim
2.7.

######  Claim 2.9.

$T_{D}$ is connected in $A(R)-C$.

###### Proof.

Since $D_{\delta}$ is connected, it suffices to show that for any
$x,x^{\prime}\in D$ at distance at most $\delta$ from each other, $T_{x}$ and
$T_{x^{\prime}}$ are connected in $A(R)-C$.

Let then $x,x^{\prime}\in D$ be such that $d(x,x^{\prime})\leq\delta$. Then
$\Sigma_{x,2\delta}(2R)\cap\Sigma_{x^{\prime},2\delta}(2R)$ contains $\exp(R)$
points. Repeating the argument of the previous claim we see that, if $R$ is
large enough, one of those points
$y\in\Sigma_{x,2\delta}(2R)\cap\Sigma_{x^{\prime},2\delta}(2R)$ is not in
$Q_{x}$ nor in $Q_{x^{\prime}}$. As above, $\Sigma_{y}^{A}$ is included in a
single connected component of $A(R)-C$ and is also included in $T_{x}$ and
$T_{x^{\prime}}$. Thus $T_{x}$ and $T_{x^{\prime}}$ are in the same connected
component of $A(R)-C$. ∎

By assumption on $C$, this implies that we have

(2.3)
$\displaystyle|T_{D}|\leq\beta|A(R)|=\frac{|A(R)|}{4|B_{8\delta}|^{3}K^{3}}.$

######  Claim 2.10.

We have

(2.4) $\displaystyle\sum_{x\in D}|T_{x}|\leq|B_{8\delta}||T_{D}|.$

###### Proof.

Let us show that there exists a map $\phi:D\to D$ such that

  * •

$d(x,\phi(x))\leq 8\delta$ and in particular
$|\phi^{-1}(\phi(x))|\leq|B_{8\delta}|$,

  * •

$|T_{x}|\leq|T_{\phi(x)}|$, and

  * •

if $y\neq y^{\prime}\in\operatorname{Im}\phi$ then $T_{y}\cap
T_{y^{\prime}}=\emptyset$.

Assuming we have constructed such a map, the claim follows by

(2.5) $\displaystyle\sum_{x\in
D}|T_{x}|\leq|B_{8\delta}|\sum_{y\in\operatorname{Im}\phi}|T_{y}|\leq|B_{8\delta}||T_{D}|$

To construct the map $\phi$, let $x\in D$ be a point maximizing $|T_{x}|$.

Let $Z\subseteq D$ be the collection of all points $x^{\prime}\in D$
satisfying $T_{x^{\prime}}\cap T_{x}\neq\emptyset$. Define $\phi$ on $Z$ by
$\phi(x^{\prime})=x$. Note that each $x^{\prime}\in Z$ is at distance
$d(x,x^{\prime})\leq 8\delta$, and by the choice of $x$,
$|T_{x^{\prime}}|\leq|T_{x}|$.

Remove all the points in $Z$ from $D$, and iterate the construction above
until $\phi$ is defined on all $D$. ∎

Without any loss of generality we can assume that we have $K>K^{\prime}$. We
deduce:

$\displaystyle|D^{\prime}|$ $\displaystyle\leq|B_{8\delta}||D|$
$\displaystyle\leq|B_{8\delta}|K\alpha^{-R}|\Sigma_{D}^{A}|\quad\text{from
Fact \ref{fact: size of sectors}}$
$\displaystyle\leq|B_{8\delta}|K\alpha^{-R}\sum_{x\in D}|\Sigma_{x}^{A}|$
$\displaystyle\leq 2|B_{8\delta}|K^{2}\alpha^{-R}\sum_{x\in
D}|T_{x}|\quad\text{from Claim \ref{claim: size of component in sector},
assuming $K>K^{\prime}$}$ $\displaystyle\leq
2|B_{8\delta}|^{2}K^{2}\alpha^{-R}|T_{D}|\quad\text{from \eqref{eq: evaluating
TD on Tx''s}}$
$\displaystyle\leq\frac{1}{2K|B_{8\delta}|}\alpha^{-R}|A(R)|\quad\text{from
\eqref{eq: TD is small}}$
$\displaystyle\leq\frac{1}{2}\frac{|S_{R}|}{|B_{8\delta|}}\quad\text{from Fact
\ref{fact: size of sectors}}$ $\displaystyle\leq\frac{1}{2}|(S_{R})_{\delta}|$

This ends the proof of Lemma 2.4. ∎

######  Definition 2.11.

Let $X$ be a connected topological space. We say that a subset $F$
topologically separates $X$ if $X-F$ is not connected.

######  Lemma 2.12.

If $G$ has bounded spheres separation, then $\partial G$ has a finite
topologically separating set.

###### Proof.

We start with the following claim.

######  Claim 2.13.

There exists $K>0$ such that for any $R<R^{\prime}$, if
$(P_{R^{\prime}})_{\delta}$ separates $(S_{R^{\prime}})_{\delta}$ into
connected components of size at most $\frac{1}{K}|(S_{R^{\prime}})_{\delta}|$,
then $\left(\pi_{R}(P_{R^{\prime}})\right)_{2\delta}$ separates
$(S_{R})_{\delta}$ into connected components of size at most
$\frac{1}{2}|(S_{R})_{\delta}|$.

###### Proof.

If $x,y\in S_{R}-\left(\pi_{R}(P_{R^{\prime}})\right)_{2\delta}$, then
$\left(\pi_{R^{\prime}}^{-1}(x_{2\delta})\right)_{\delta}$ and
$\left(\pi_{R^{\prime}}^{-1}(y_{2\delta})\right)_{\delta}$ are connected in
$(S_{R^{\prime}})_{\delta}-(P_{R^{\prime}})_{\delta}$. If moreover
$d(x,y)\leq\delta$, these two sets intersect. This implies that for every
connected subset $D$ of
$(S_{R})_{\delta}-\left(\pi_{R}(P_{R^{\prime}})\right)_{2\delta}$, the set
$D^{\prime}:=(\pi_{R}^{-1}(D\cap S_{R}))_{\delta}$ is connected in
$(S_{R^{\prime}})_{\delta}-(P_{R^{\prime}})_{\delta}$. The conclusion of claim
follows from the fact that sizes of $D$ and $D^{\prime}$ differ by some
constant factor, as in Fact 2.6. ∎

From Lemma 2.4, for any large enough $R$ there exists $P_{R}\subset S_{R}$ of
bounded size $M$ satisfying that $(P_{R})_{2\delta}$ separates
$(S_{R})_{\delta}$ into connected components of size at most
$\frac{1}{2}|(S_{R})_{\delta}|$.

######  Claim 2.14.

Without any loss of generality, we can assume that we have
$P_{R_{1}}=\pi_{R_{1}}(P_{R_{2}})$ for every $R_{1}\leq R_{2}$.

###### Proof.

We can assume without any loss of generality that the projection maps are
chosen so that we have $\pi_{R_{1}}(x)=\pi_{R_{1}}\circ\pi_{R_{2}}(x)$ for
every $R_{1}<R_{2}$ and $x\in G-B_{R_{2}}$.

For every $R^{\prime}>0$, Claim 2.13 allows us to obtain $P_{R}$ for every
$R<R^{\prime}$ by projecting some subset of $S_{R^{\prime}}$. Then, if we have
$R_{1}<R_{2}<R^{\prime}$, with $P_{R_{1}}$ and $P_{R_{2}}$ obtained by
projecting some subset of $S_{R^{\prime}}$, we have
$P_{R_{1}}=\pi_{R_{1}}(P_{R_{2}})$ since
$\pi_{R_{1}}=\pi_{R_{1}}\circ\pi_{R_{2}}$. Since the spheres of $G$ are
finite, we can proceed to an extraction to obtain a sequence $R^{\prime}_{n}$
such that for every $R>0$ the sequence $(\pi_{R}(P_{R^{\prime}_{n}}))_{n\geq
0}$ is constant (it is only defined when $R^{\prime}_{n}\geq R$). Without any
loss of generality we can assume that we have
$P_{R}=\pi_{R}(P_{R^{\prime}_{n}})$. We finally get the desired property that
$P_{R_{1}}=\pi_{R_{1}}(P_{R_{2}})$ for every $R_{1}<R_{2}$.

∎

Now the sequence $P_{R}$ has a limit $P\subseteq\partial G$ as $R\to\infty$.
To complete the proof of Lemma 2.12 it remains to show that $P$ topologically
separates $\partial G$.

From above, there exist $\xi,\eta\in\partial G$ such that $\pi_{R}(\xi)$ and
$\pi_{R}(\eta)$ are in different components of
$(S_{R})_{\delta}-(P_{R})_{\delta}$ for all large enough $R$. Assume for
contradiction that $\xi$ and $\eta$ are in the same component of $\partial
G-P$. The boundary $\partial G$ is path connected, let $\gamma$ be a path in
$\partial G-P$ connecting $\xi$ and $\eta$. There exists $\epsilon>0$ such
that the path $\gamma$ avoids the $\epsilon$-neighbourhood of $P$ in $\partial
G$. Let $R$ be big enough so that $\pi_{R}^{-1}(x_{2\delta})\cap\partial G$ is
of diameter $\leq\epsilon/2$ for each $x\in S_{R}$.

Thus, $\pi_{R}\circ\gamma$ is a $2\delta$-step path in $S_{R}$ which avoids
$(P_{R})_{2\delta}$. Completing it with a collections of geodesic arcs of
length at most $\delta$, we get a path in $(S_{R})_{\delta}$ which avoids
$(P_{R})_{\delta}$, and connects $\pi_{R}(\xi)$ and $\pi_{R}(\eta)$. A
contradiction. This ends the proof of Lemma 2.12. ∎

We are now able to prove Theorem A.

###### Proof of Theorem A.

By Lemmas 2.4 and 2.12 we see that $\partial G$ is topologically separated by
a finite set of points. It therefore has a local cut point. It follows from
Bowditch [3] that $G$ splits over a virtually cyclic group or $G$ is a
Fuchsian group. ∎

##  3 Proof of Theorem B

In this section, we construct a hyperbolic group with superlogarithmic
separation profile whose boundary has conformal dimension one. Let us start by
giving the following proposition.

######  Proposition 3.1 ([1, Lemma 1.3]).

Let $G$ and $H$ be bounded degree infinite graphs such that there exists a
coarse embedding $G\to H$. Then,
$\operatorname{sep}_{G}\preceq\operatorname{sep}_{H}$.

Recall that quasi-isometric embeddings are examples of coarse embeddings. This
proposition implies that the separation profile is invariant under coarse
equivalences and quasi-isometries. In particular we can consider separation
profiles more generally for metric spaces that are coarsely equivalent to
graphs of bounded degree. This is what we will do in this section for the
hyperbolic plane.

Let $\Sigma$ and $\Sigma^{\prime}$ be two closed hyperbolic orientable
surfaces, and $\gamma\subset\Sigma$, $\gamma^{\prime}\subset\Sigma^{\prime}$
be two simple closed filling geodesic curves. Recall that a curve on a surface
is said to be filling when its complementary is homeomorphic to a union of
disks. Let $S=(\Sigma\sqcup\Sigma^{\prime})/{\gamma\simeq\gamma^{\prime}}$ be
the space obtained by gluing $\Sigma$ and $\Sigma^{\prime}$ along $\gamma$ and
$\gamma^{\prime}$.

The universal cover $\tilde{S}$ of $S$ consists of copies of hyperbolic
planes, that we will call sheets, glued together along the geodesic lines
which correspond to the lifts of $\gamma$ and $\gamma^{\prime}$.

Let $F$ be one of the sheets covering $\Sigma$. For a lift
$\widetilde{\gamma}$ of $\gamma$ let $F_{\widetilde{\gamma}}$ be the adjacent
sheet covering $\Sigma^{\prime}$ which is glued to $F$ along
$\widetilde{\gamma}$.

Let $R>0$. Let $B_{R}$ (resp. $B_{R/3}$) be the balls of radius $R$ (resp.
$R/3$) in $F$ centered around $o$. Let us consider

$X=B_{R}\cup\bigcup_{\widetilde{\gamma}\cap
B_{R/3}\neq\emptyset}B_{F_{\widetilde{\gamma}}}(o_{\widetilde{\gamma}},R/3)\subset\tilde{S}$

where the union ranges over all lifts $\widetilde{\gamma}$ of $\gamma$ that
intersect $B_{R/3}$ and $o_{\widetilde{\gamma}}$ is the closest point to $o$
on $\widetilde{\gamma}$. See Figure 2.

######  Proposition 3.2.

The set $X$ satisfies $\operatorname{cut}X\succ R.$

Figure 2: the set $X$ of Proposition 3.2

Let us prove how Theorem B can be deduced from this proposition.

###### Proof of Theorem B.

The fundamental group $\pi_{1}S$ is quasi-isometric to the universal cover
$\tilde{S}$. Thus, we can compute the separation profile of $\tilde{S}$
instead of that of $\pi_{1}S$, and the theorem follows from Proposition 3.2. ∎

We now prove the proposition.

###### Proof of Proposition 3.2.

######  Claim 3.3.

Most of the volume of $X$ lies in the ball $B_{R}\subset F$:

$\operatorname{vol}(X)\asymp\operatorname{vol}(B_{R}).$

###### Proof.

The volume of a ball $B(o,r)$ of radius $r$ in the hyperbolic plane is

$\operatorname{vol}(B(o,r))=2\pi(\cosh(r)-1)\asymp e^{r}.$

The number of lifts of a geodesic that intersect a ball $B(o,r)$ is $\preceq
e^{r}$. Thus,

$\operatorname{vol}(B(o,R))\preceq\operatorname{vol}(X)\preceq\operatorname{vol}(B(o,R))+e^{R/3}\operatorname{vol}(B(o,R/3))\preceq\operatorname{vol}(B(o,R)).\qed$

Let $C$ be a (1-thick) cutset of $X$, that is every connected component of
$X-C$ has volume at most $\alpha\operatorname{vol}X$ for some $\alpha<1$. Up
to taking a small enough $\alpha$, $C$ has to separate the ball $B_{R}$. We
want to show that $C$ must have volume strictly bigger than
$\log\operatorname{vol}(X)\asymp\log\operatorname{vol}(B(o,R))\asymp R$. Let
us assume for a contradiction that we have (up to constants),
$\operatorname{vol}C\preceq R$.

Let $\Lambda=\partial C$. The total length of $\Lambda$ is $O(R)$: indeed, $C$
has volume $R$ and can be chosen to be a union of balls of radius 1 in a given
net and so the length of their boundary component has to be $O(R)$.

The components of $\Lambda$ are either proper arcs or simple closed curves in
$B_{R}$. Let $\hat{\Lambda}$ be the collection of geodesics with the same
endpoints as the arcs of $\Lambda$. Let $C^{\prime}$ be the union of the
components of $A-\hat{\Lambda}$ that include $C\cap\partial B_{R}$. See Figure
3.

Figure 3: the separating set $C$ of the hyperbolic ball

######  Lemma 3.4.

  1. (i)

$\operatorname{vol}(C\triangle C^{\prime})\preceq R$

  2. (ii)

Every component $E$ of $B_{R}-C$ of size $\succ R$ corresponds to a unique
component $E^{\prime}$ of $B_{R}-C^{\prime}$ such that
$\operatorname{vol}(E\triangle E^{\prime})\preceq R$, and vice versa.

###### Proof.

(i) The difference between the sets $C$ and $C^{\prime}$ has boundary in
$\Lambda\cup\hat{\Lambda}$. Then, since the total length of $\Lambda$ and
$\hat{\Lambda}$ is $O(R)$, it follows from the isoperimetric inequality on the
hyperbolic plane, that $\operatorname{vol}(C\triangle
C^{\prime})\preceq\operatorname{length}(\Lambda\cup\hat{\Lambda})\preceq R$.

(ii) By the isoperimetric inequality, a component $E$ of $B_{R}-C$ of size
$\succ R$ must intersect $\partial B_{R}$. There is a component $E^{\prime}$
of $B_{R}-C^{\prime}$ with $E\cap\partial B_{R}=E^{\prime}\cap\partial B_{R}$.
The difference $E\triangle E^{\prime}$ comprises of sets which are bounded by
$\Lambda$ and $\hat{\Lambda}$. The volume of this difference can be bounded by
$\preceq R$ again by the isoperimetric inequality. ∎

Let $\Lambda^{\prime}$ be set of geodesics in $\hat{\Lambda}$ that meet
$B_{R/3}=B_{F}(o,R/3)$. Any geodesic in $\Lambda^{\prime}$ must have a segment
joining $\partial B_{R/3}$ and $\partial B_{R}$, and thus must have length at
least $2R/3$. Since $\operatorname{length}(\hat{\Lambda})\preceq R$ there are
$O(1)$ many geodesics in $\Lambda^{\prime}$. Let $k$ be the number of
geodesics in $\Lambda^{\prime}$.

Let $m(x,y,z)$ denote the center of the geodesic triangle spanned by a triple
points $x,y,z\in\mathbb{H}^{2}$. Let

$M=\\{m(o,x,y)\mid x,y\in\Lambda^{\prime}\cap\partial B_{R}\\}.$

There are at most $(2k)^{2}$ points in $M$.

Divide $B_{R/3}$ into $3((2k)^{2}+1)$ radial annuli of same width, called
_layers_. By the Pigeonhole Principle, there exist three consecutive layers
$A_{-},A,A_{+}$ that do not contain a point of $M$.

######  Claim 3.5.

For $R$ large enough, we have:

  1. (i)

The intersection $\Lambda^{\prime}\cap A$ consists of geodesics joining the
inner and outer boundaries of $A$.

  2. (ii)

If $\alpha$ is a component of $\Lambda^{\prime}\cap A$, and $\alpha$ is a
subarc of $\lambda\in\Lambda^{\prime}$, then $\alpha$ is at distance at most
$\delta$ from one of the two geodesics connecting $o$ and $\partial\lambda$.

  3. (iii)

If $\alpha_{1},\alpha_{2}$ are component of $\Lambda^{\prime}\cap A$, then
either the Hausdorff distance $d_{H}(\alpha_{1},\alpha_{2})\leq 3\delta$ or
they are at distance $\sqrt{R}$ apart.111The function $\sqrt{R}$ can be
replaced by any function $o(R)$

###### Proof.

(i) Otherwise, a component $\alpha$ of $\Lambda^{\prime}\cap A$ is a geodesic
arc connecting the outer boundary of $A$ to itself. Let $p$ be the point on
$\alpha$ closest to $o$, let $\lambda$ be the geodesic of $\Lambda^{\prime}$
to which $\alpha$ belongs, and let $x,y$ be the endpoints of $\lambda$ in
$S_{F}(o,R)$. Then, $m(o,x,y)\in M$ is at distance $\delta$ from $p$,
contradicting the assumption that $A_{-}\cup A\cup A_{+}$ does not include
points of $M$.

(ii) Consider the geodesic triangle consisting of the geodesic $\lambda$ and
the two geodesics connecting its endpoints to $o$. By assumption, the center
of this geodesic is not in $A^{\prime\prime}$, hence by slimness of triangles
in $\mathbb{H}^{2}$ the segment $\alpha$ is $\delta$-close to one of the
sides.

(iii) Let $\alpha_{1},\alpha_{2}$ be components of $\Lambda^{\prime}\cap A$.
Let $\lambda_{1}$ (resp. $\lambda_{2}$) be the geodesic in $\Lambda$
containing $\alpha_{1}$ (resp. $\alpha_{2}$). By (ii), $\alpha_{1}$ (resp.
$\alpha_{2}$) is $\delta$-close to a radial geodesic $\lambda_{1}^{\prime}$
(resp. $\lambda_{2}^{\prime}$) connecting $o$ and one of the endpoints of
$\lambda_{1}$ (resp. $\lambda_{2}$). Let
$\alpha_{1}^{\prime}=\lambda_{1}^{\prime}\cap A$ (resp.
$\alpha_{2}^{\prime}=\lambda_{2}^{\prime}\cap A$). It suffices to prove that
$d_{H}(\alpha_{1}^{\prime},\alpha_{2}^{\prime})\leq\delta$, or they are at
distance $\sqrt{R}+2\delta$ apart.

Let $p_{1},q_{1}\in\alpha_{1}^{\prime}$ (resp.
$p_{2},q_{2}\in\alpha_{2}^{\prime}$) be the intersection of
$\alpha_{1}^{\prime}$ (resp. $\alpha_{2}^{\prime}$) with the inner and outer
boundaries of $A$ respectively. If $d(q_{1},q_{2})\leq\delta$ then
$d_{H}(\alpha_{1}^{\prime},\alpha_{2}^{\prime})\leq\delta$ by the convexity of
the metric. Similarly, if $d(p_{1},p_{2})\geq\sqrt{R}+2\delta$ then
$\alpha_{1}^{\prime},\alpha_{2}^{\prime}$ are at least $\sqrt{R}+2\delta$
apart. Otherwise, $d(p_{1},p_{2})\leq\sqrt{R}+2\delta$ and
$d(q_{1},q_{2})>\delta$, then the center of the triangle with sides
$\lambda_{1}^{\prime},\lambda_{2}^{\prime}$ is at distance at most
$\sqrt{R}+3\delta$ from $\alpha_{1}^{\prime}$. For $R$ large enough, such a
point must be in $A_{-}\cup A\cup A_{+}$ in contradiction to the assumption. ∎

From the claim above it follows that $\Lambda^{\prime}\cap A$ consists of at
most $2k$ geodesic segments connecting the inner and outer boundaries of $A$
and the relation defined by $\alpha_{1}\sim\alpha_{2}$ if
$d_{H}(\alpha_{1},\alpha_{2})\leq 3\delta$ is an equivalence relation. Let
$\mathcal{W}$ be a set of representatives of the classes of this relation. We
call the elements in $\mathcal{W}$ _walls_. We call the connected components
of $A-\mathcal{W}$ _regions_. By the claim, the walls bounding each region are
at distance $\sqrt{R}$ apart.

######  Claim 3.6.

Let $D$ be a region in $A$, then there exists a (unique) component $E$ of
$X-C$ such that $\operatorname{vol}(D-E)\preceq R$.

###### Proof.

Let $\alpha_{1},\alpha_{2}$ be the walls bounding $D$. Let
$\alpha_{1}^{\prime},\alpha_{2}^{\prime}$ be the inner most arcs in $D$ which
belong to the equivalence classes of $\alpha_{1},\alpha_{2}$ respectively. Let
$E^{\prime}$ be the connected component of $X-\hat{\Lambda}$ which includes
the section of $A$ between $\alpha_{1}^{\prime},\alpha_{2}^{\prime}$. This
section is contained in $D$, and $D-E^{\prime}$ consists of two regions which
are contained in the $3\delta$-neighborhood of $\alpha_{1}\cup\alpha_{2}$.
Therefore, $\operatorname{vol}(D-E^{\prime})\preceq R$. The set $C^{\prime}$
is bounded by geodesics in $\hat{\Lambda}$. It cannot contain the component
$X-E^{\prime}$, as otherwise
$\operatorname{vol}(C^{\prime})\succeq\operatorname{vol}(E^{\prime})\succ R$.
Thus $E^{\prime}$ is a component of $C^{\prime}$. By Lemma 3.4, $E^{\prime}$
corresponds to a unique component $E$ of $X-C$, and
$\operatorname{vol}(D-E)\leq\operatorname{vol}(D-E^{\prime})+\operatorname{vol}(E^{\prime}-E)\preceq
R$. ∎

######  Claim 3.7.

No component $E$ of $X-C$ contains more than $\frac{2}{3}$ of the layer $A$

###### Proof.

Let $E$ be a component of $X-C$. Assume for contradiction that
$\operatorname{vol}(E\cap A)>\frac{2}{3}\operatorname{vol}(A)$. For every
$x\in E\cap A$ consider the ray $x^{*}=\mathbb{R}_{\geq 1}x\cap B_{R}=\\{tx\in
B_{R}\mid t\geq 1\\}$. Let $E_{1}=\\{x\in E\mid x^{*}\cap C=\emptyset\\}$.
Since $\operatorname{vol}(C)$ consists of $O(R)$ balls of radius 1, the set
$E-E_{1}$ consists of at most $O(R)$ 1-neighborhoods of arcs of length $O(R)$.
Whence, $\operatorname{vol}(E-E_{1})\preceq R^{2}$. Consider the set
$E_{1}^{*}=\bigcup_{x\in E_{1}}x^{*}$. Thus
$\operatorname{vol}(E_{1})>\frac{1}{2}\operatorname{vol}(A)$, and therefore
also $\operatorname{vol}(E_{1}^{*})>\frac{1}{2}\operatorname{vol}(B_{R})$. The
set $E_{1}^{*}\subseteq E$, thus
$\operatorname{vol}(E)>\frac{1}{2}\operatorname{vol}(B_{R})$. We get a
contradiction to the assumption that the volume of components of $X-C$ are at
most $\frac{1}{2}\operatorname{vol}(B_{R})$. ∎

By the previous two claims there are two regions $D_{+},D_{-}$ of
$A-\mathcal{W}$ which correspond to two different components $E_{+},E_{-}$ of
$X-C$. We may assume that $D_{1}$ and $D_{2}$ are adjacent, and are separated
by a wall $\alpha$. Let $\alpha_{m}$ be the middle third subarc of $\alpha$.

######  Claim 3.8.

There is $k\asymp R$, and disjoint lifts
$\widetilde{\gamma}_{1},\ldots,\widetilde{\gamma}_{k}$ of $\gamma$ such that
$\widetilde{\gamma}_{i}\cap\alpha_{m}\neq\emptyset$.

###### Proof.

Consider the union $\Gamma=\bigcup\widetilde{\gamma}$ of all the lifts
$\widetilde{\gamma}$ of $\gamma$ to the universal cover $F$ of $\Sigma$. Since
$\gamma$ is filling in $\Sigma$, the connected components of $F-\Gamma$ are
one of finitely many types of convex hyperbolic non-ideal polygons. Let $d$ be
the maximal diameter of these polygons. There exists an angle $\theta$ such
that every geodesic line intersecting one of the polygons, forms an angle
$\theta$ with at least one of its sides. Let $\mu>0$ be such that if two
geodesic lines $l_{1},l_{2}$ in the hyperbolic plane intersect a third
geodesic line $l$ at points of distance $\geq\mu$ and at angles $\geq\theta$,
then $l_{1},l_{2}$ do not meet.

Let $\ell=\operatorname{length}(\alpha_{m})\asymp R$. Every segment of length
$2d$ on $\alpha_{m}$ intersects a lift $\widetilde{\gamma}$ of $\gamma$ in an
angle $\geq\theta$. Thus, the geodesic segment $\alpha_{m}$ intersects at
least $k=\ell/(\mu+2d)$ lifts
$\widetilde{\gamma}_{1},\ldots,\widetilde{\gamma}_{k}$ of $\gamma$ in an angle
$\geq\theta$. Note that $k\asymp\ell\asymp R$. By the choice of $\mu$,
$\widetilde{\gamma}_{1},\ldots,\widetilde{\gamma}_{k}$ are disjoint. ∎

Let $\widetilde{\gamma}_{1},\ldots,\widetilde{\gamma}_{k}$ be the disjoint
lifts as in Claim 3.8. The geodesic segments $\widetilde{\gamma}_{i}\cap
D_{\pm}$ have length at least $\succeq\sqrt{R}$ by Claim 3.5 and by the choice
of $\alpha_{m}$. The circles around the point
$\widetilde{\gamma}_{i}\cap\alpha_{m}$ in $F_{\widetilde{\gamma}_{i}}$ form
$\Theta(\sqrt{R})$ disjoint paths connecting points in $D_{+}$ to points in
$D_{-}$. Considering these paths for all $\widetilde{\gamma}_{i}$, we get
$\Theta(R^{3/2})$ disjoint paths connecting $D_{+}$ to $D_{-}$. By Claim 3.6,
$\operatorname{vol}(D_{\pm}-E_{\pm})\preceq R$, and so we have at least
$\succeq R^{3/2}-O(R)$ disjoint paths connecting $E_{+}$ to $E_{-}$. Since
$E_{+}$ and $E_{-}$ are different components of $X-C$, each of these paths
meets $C$. We get $\operatorname{vol}(C)\succeq R^{3/2}$ which contradicts
$\operatorname{vol}(C)\preceq R$. This ends the proof of Proposition 3.2. ∎

## References

  * [1] Itai Benjamini, Oded Schramm, and Ádám Timár.  On the separation profile of infinite graphs.  Groups Geom. Dyn., 6(4):639–658, 2012.
  * [2] Mladen Bestvina and Geoffrey Mess.  The boundary of negatively curved groups.  Journal of the American Mathematical Society, 4(3):469–481, 1991\.
  * [3] Brian H. Bowditch.  Cut points and canonical splittings of hyperbolic groups.  Acta mathematica, 180(2):145–186, 1998.
  * [4] Matias Carrasco and John M. Mackay.  Conformal dimension of hyperbolic groups that split over elementary subgroups.  2020\.
  * [5] Michel Coornaert.  Mesures de Patterson-Sullivan sur le bord d’un espace hyperbolique au sens de Gromov.  Pacific J. Math., 159(2):241–270, 1993.
  * [6] Sébastien Gouëzel, Frédéric Mathéus, and François Maucourant.  Entropy and drift in word hyperbolic groups.  Invent. Math., 211(3):1201–1255, 2018.
  * [7] Misha Gromov.  Asymptotic invariants of infinite groups.  In Geometric group theory, Vol. 2 (Sussex, 1991), volume 182 of London Math. Soc. Lecture Note Ser., pages 1–295. Cambridge Univ. Press, Cambridge, 1993.
  * [8] David Hume and John M. Mackay.  Poorly connected groups.  Proc. Amer. Math. Soc., 148(11):4653–4664, 2020.
  * [9] David Hume, John M. Mackay, and Romain Tessera.  Poincaré profiles of groups and spaces.  Rev. Mat. Iberoam., 36(6):1835–1886, 2020.
  * [10] David Hume, John M. Mackay, and Romain Tessera.  Poincaré profiles of Lie groups and a coarse geometric dichotomy, 2021\.
  * [11] Corentin Le Coz.  Separation and Poincaré profiles.  PhD thesis, 2020.  Thèse de doctorat dirigée par Tessera, Romain et Brieussel, Jérémie Mathématiques fondamentales université Paris-Saclay 2020.
  * [12] Richard J. Lipton and Robert Endre Tarjan.  A separator theorem for planar graphs.  SIAM J. Appl. Math., 36(2):177–189, 1979.
  * [13] Larsen Louder and Nicholas Touikan.  Strong accessibility for finitely presented groups.  Geometry & Topology, 21(3):1805–1835, 2017.


11institutetext: Leipzig University & ScaDS.AI Dresden/Leipzig, Germany
11email: {christen, obraczka, hofer,franke<EMAIL_ADDRESS>
# Graph-based Active Learning for Entity Cluster Repair

Victor Christen  0000-0001-7175-7359 Daniel Obraczka  0000-0002-0366-9872
Marvin Hofer  0000-0003-4667-5743 Martin Franke  Erhard Rahm
0000-0002-2665-1114

###### Abstract

Cluster repair methods aim to determine errors in clusters and modify them so
that each cluster consists of records representing the same entity. Current
cluster repair methodologies primarily assume duplicate-free data sources,
where each record from one source corresponds to a unique record from another.
However, real-world data often deviates from this assumption due to quality
issues. Recent approaches apply clustering methods in combination with link
categorization methods so they can be applied to data sources with duplicates.
Nevertheless, the results do not show a clear picture since the quality highly
varies depending on the configuration and dataset. In this study, we introduce
a novel approach for cluster repair that utilizes graph metrics derived from
the underlying similarity graphs. These metrics are pivotal in constructing a
classification model to distinguish between correct and incorrect edges. To
address the challenge of limited training data, we integrate an active
learning mechanism tailored to cluster-specific attributes. The evaluation
shows that the method outperforms existing cluster repair methods without
distinguishing between duplicate-free or dirty data sources. Notably, our
modified active learning strategy exhibits enhanced performance when dealing
with datasets containing duplicates, showcasing its effectiveness in such
scenarios.

###### Keywords:

Data integration Cluster repair Graph metrics Machine Learning Active Learning

##  1 Introduction

The upcoming trend of systems using generative large language models
tremendously simplifies knowledge acquisition, being relevant for many
industries such as economic companies, medicine, and research. However, the
performance of these language models highly depends on the availability of
large corpora. Small and specific domains lack the availability of such large
corpora. Recent work proposes the usage of knowledge graphs in combination
with large language models to overcome these issues [22, 29].

Therefore, constructing knowledge graphs is an essential cornerstone to
improve such systems based on these models [11]. Moreover, knowledge graphs
enable an integrated view of data from different heterogeneous data sources,
enhancing comprehensive analysis.

Due to the huge amount of available data sources, data integration is required
to structure data into knowledge graphs. In recent decades, many record
linkage methods have been proposed to identify records from different data
sources representing the same entity. In the case of multiple data sources,
the result of a record linkage method is a set of clusters where each cluster
consists of records representing the same entity. However, due to the
heterogeneity and various data quality problems, the resulting clusters might
not be correct regarding the matched records. Therefore, in current research,
clustering repair methods were investigated to improve the cluster quality by
modifying the clusters. The majority of proposed methods [26, 16, 20] assume
that the data sources are duplicate-free and intensively utilize that
condition to remove links so that the resulting clusters satisfy the
assumption.

However, the assumption that there are no duplicates is unrealistic for a
large number of data sources being available in the LOD cloud. Consequently,
methods that intensively use this assumption achieve poor results. Recent
works apply modified clustering methods such as hierarchical clustering or
affinity propagation [25, 12] that can be used to repair clusters from dirty
data sources. Nevertheless, the results highly depend on the configuration
with respect to a certain linkage problem.

To overcome such issues, we suggest a novel repair approach that utilizes
graph metrics as indicators for correct and incorrect links to repair clusters
based on generated similarity graphs. Specifically, we make the following
contributions:

  * •

We propose a cluster repair method based on a classification model using graph
metric-based features. In addition to the similarities, the used features
cover network information within a cluster. The repair step utilizes the model
to iteratively add or delete records from clusters depending on the prediction
and the relationship to the existing records of a cluster.

  * •

Due to the lack of training data, an active learning method is integrated into
our method. To generate representative training data regarding the different
clusters with their specific characteristic, we extend an existing active
learning method by considering cluster-specific features in the selection
phase.

  * •

We intensively evaluate our approach regarding the used labeling budget and
selection strategies on two real-world datasets. We compare the results with
existing cluster repair methods focusing on duplicate-free and dirty data
sources. In the end, we also verify the robustness according to noisy
similarity graphs by changing the similarities of edges randomly.

The remainder of this paper is structured as follows. In Section 2, we define
the problem of repairing clusters of records and discuss related work (section
3). In Section 4, we present our novel approach for repairing clusters
utilizing graph metrics with active learning. In Section 5, we evaluate our
approach on different datasets to validate its practical applicability.
Finally, we conclude our work in Section 6.

Figure 1: Outline of the complete entity resolution process including the
repair method identifying incorrect edges $\mathbf{E_{NM}}$ to construct
repaired clusters $\mathbf{C_{rep}}$.

##  2 Problem Definition

Let $\mathcal{D}$ be a set of data sources $D_{1}$, $D_{2}$, …$D_{n}$ and $SG$
a similarity graph generated by an arbitrary entity resolution tool, exemplary
depicted in Figure 1, or derived from a collection of sameAs links. The entity
resolution tool generates for each data source pair a set of sameAs links
between records by executing the typical steps: preprocessing, blocking,
similarity computation, and classification [5]. Note, that the similarity
graph is not complete because of the classification step so that not each
record pair represents an edge. Due to the transitivity of sameAs links, the
records of a connected component represent a cluster $c$ and thus the same
entity.

A repair method aims to determine incorrect clusters consisting of wrongly
assigned records according to the initial set of clusters $\mathbf{C}$ and
update them to a repaired set of clusters $\mathbf{C_{rep}}$. To identify
incorrect records, the approach can utilize the computed similarity graph
$\mathbf{SG}$ with its similarities to remove incorrect links
$\mathbf{E_{nm}}$ resulting in a partition of the connected component. In
general, a record linkage approach computes multiple similarities regarding
different attributes. In this work, we assume that the similarities are
aggregated by an aggregation function. Moreover, a similarity can also be a
probability of a classification model of how likely the match is. Due to the
high complexity of the pairwise comparison, we do not consider missing merged
clusters such as the cluster of r2’ with the cluster consisting of the other
records r2.

##  3 Related Work

Constructing knowledge graphs essentially depends on entity resolution, a
field extensively studied for decades [5, 17]. The primary objective lies in
identifying records that represent the same entity. Most of the approaches
[19, 7, 15] as well as recent research utilizing large language models [13,
23] treat entity resolution as a classification task, categorizing record
pairs as matches or non-matches. Due to the quality issues and the
transitivity of sameAs links, a pairwise view is not sufficient to generate
qualitative record clusters. The error-prone clusters can lead to a wrong
knowledge graph construction and lead to relationships failing to represent
the real world.

As a solution, methods for cluster repair become relevant to enhance the
quality of derived clusters, building upon the determined sameAs links from
any entity resolution method.

Multi-source entity resolution: Due to the increasing heterogeneity
considering data sources and the potentially high number of data sources,
multi-source entity resolution methods address these challenges. Chen et al.
[28] define a matching plan that specifies which matcher is applied to which
source and which sources are grouped. In addition to the matching task, a
repair step is required that identifies conflicts introduced by the transitive
closure and resolves them. CLIP [26] categorizes the computed links into
_strong_ , _normal_ , and _weak_ links based on the similarity graph structure
and the data sources. The different link categories distinguish if two records
from two data sources are connected by an edge that maximizes the similarity
for both records or not. Using the link categories and the assumption of
duplicate-free data sources, the method iteratively removes edges from
clusters until they are source-consistent. Lerm et al. [12] extended affinity
propagation clustering applicable for clean as well as dirty data sources.
Experiments showed that the approach leads to small clusters with high
precision but at the cost of relatively low recall. To overcome the low
recall, Saeedi et al.(2021) [25] proposed an agglomerative hierarchical
clustering-based method using the basic strategies: _single-_ , _complete-_ ,
and _average-_ linkage. To guarantee source consistency regarding clean data
sources, they adapted the general method by adding certain constraints for
merging clusters.

Active Learning: The goal of active learning methods is the interactive and
iterative training data generation by determining informative unlabeled
samples. The selected data will then be classified by an oracle and added to
the existing training data. In each iteration, the training data is utilized
to determine new informative samples. The algorithm terminates if a specific
stop criterion is achieved such as the number of manually classified samples
so-called labeling budget or the performance of the current classification
model is sufficient. Due to the lack of available training data, various
methods [1, 2, 21, 6, 14] have been proposed for entity resolution. The works
of [1, 2] aim to maximize the recall regarding a specified precision
threshold. EAGLE [21] focuses on RDF link discovery and aims at generating
link specifications representing a complex similarity function. Mozafari et
al. [14] proposed two such approaches, named _Uncertainty_ and _MinExpError_ ,
being applicable for applications beyond entity resolution. The main idea of
these approaches is to use non-parametric bootstrapping to estimate the
uncertainty of classifiers. Christen et al. [6] defined an informative measure
for selecting new samples based on the location of samples in the similarity
vector space instead of generating a model in each iteration. However, the
proposed methods only focus on linkage problems between two data sources.
Recent work [24] also addresses mutli-source entity resolution problems
introducing new challenges such as increasing heterogeneity and search space
regarding informative samples.

The mentioned active learning methods do not address the challenges of
heterogeneity introduced by various data sources. Recently, Primpeli et al.
[24] proposed a novel approach utilizing graph characteristics based on
similarity graphs to determine informative links. The advantage of this method
is that it likely selects links leading to a wrong-connected component. The
results showed that the approach outperforms existing active learning methods
based on a pairwise view using a small labeling budget.

Figure 2: Overview of the graph-based cluster repair method.

##  4 Graph-based Cluster Repair

In the following, we will present our graph-based cluster repair method
depicted in Figure 2. The approach aims to generate a set of clusters
$\mathbf{C_{rep}}$ consisting of records representing the same entity. As
input the method has an initial set of clusters $\mathbf{C}$ derived from a
similarity graph $\mathbf{SG}$ generated by an arbitrary record linkage
framework. Each connected component forms a cluster $c$ with records that
should represent the same entity. The similarity graph $\mathbf{SG}$ is a
weighted undirected graph consisting of nodes representing records and edges
indicating the similarity between two records. The similarity can be a
probability determined by a machine learning model or an aggregated similarity
regarding different attribute similarities. Similarly to CLIP [26], we also
remove edges if both adjacent records are related to edges with a higher
similarity.

Due to data quality issues and linkage errors, the resulting clusters derived
from a similarity graph might consist of records that are not the same as the
other records of the cluster. In contrast to pairwise record linkage, edges
can be characterized by the adjacency nodes and the indirectly connected
nodes. For representing the relationship of connected records, we compute
various graph metrics in the feature generation step such as PageRank, and
several centrality measures to construct node and edge features.

To determine the correctness of an edge, we classify each edge based on a
trained model $\mathbf{M}$ using the derived edge features. The training
process requires classified edges as matches and non-matches. Due to the
sparsity of available training data, we adapt an existing active learning [14]
to select informative edges as training data $\mathbf{T}$. In each iteration,
we select $iter\\_budget\geq 0$ unlabeled samples for labeling and add the
labeled edge feature vectors to the existing training dataset $\mathbf{T}$.
The iteration terminates if the specified labeling budget $b$ is exhausted. We
extend the approach by considering cluster-specific characteristics such as
the number of nodes. The intention is that the selected training data should
represent the different available clusters. Therefore, the cluster-specific
properties of the selected edges should be similar to the characteristics of
all clusters. In the last step, we iteratively repair the initial clusters
$\mathbf{C}$ using the model $\mathbf{M}$ so that each group consists of
records where the edges are classified as _match_ with a high support.

###  4.1 Feature Generation

A classification model classifies the edges in a cluster using graph metric-
based feature vectors to determine if the edges are correct. The link
categories proposed in [26] and the similarities characterize edges directly.
In addition to local edge properties, it is also represented by network
information regarding the induced similarity graph of a cluster. The set of
features forms a vector $\overrightarrow{e}$ for each edge used in the
classification step. Due to the same structure of different clusters, various
edges can be represented by the same edge vector $\overrightarrow{e}$.
Therefore, we only consider unique edge vectors in the training phase for
generating the classification model $\mathbf{M}$. We select several metrics
[18, 8] for feature computation to characterize an edge by the graph’s element
type and the information type. Table 1 shows an overview of the features.

name | element type | information
---|---|---
PageRank | node | network
Closeness Centrality | node | network
Betweenness Centrality | node | network
Cluster Coefficient | node | network
Similarity | edge | local
Link category | edge | network
Bridge | edge | network
Betweenness Centrality | edge | network
Complete ratio ($|E|/\frac{|V|\cdot(|V|-1)}{2}$) | graph | network
Table 1: Overview of computed features to characterize an edge categorized by
the element type of a graph and the type of information.

###  4.2 Cluster Characteristic Aware Active Learning

Due to the high number of clusters and the lack of evaluated clusters, we need
to generate training data efficiently. In our case, the training data consists
of edge feature vectors labeled as correct or not. Active learning techniques
enable an efficient and interactive selection of informative samples. The
current research provides various methods for record linkage. However, most of
them focus on the training data selection to train a record linkage
classification model based on attribute value similarities. In our case, we
also want to consider cluster-specific characteristics to select edge feature
vectors as training data. Therefore, we extend the active learning method of
Mozafari et al. [14] by considering the number of nodes regarding the cluster
of the selected edge. The main idea is to select iteratively a certain number
$iter\\_budget$ of unlabeled edge feature vectors being informative to extend
the current training data $\mathbf{T}$. The iterative process terminates if a
stop criterion such as a total labeling budget $b$ is reached. To determine
informative vectors Mozafari et al. use a bootstrapping technique. Therefore,
the method generates $k$ classifiers based on the current training dataset
$\mathbf{T}$ by sampling with repetition. The determined models
$m_{1},..,m_{k}$ classify the unlabeled edge feature vectors where the
predictions are utilized to compute the uncertainty $unc(\overrightarrow{e})$
of an edge $e$ shown in 1.

$unc(\overrightarrow{e})=\frac{\sum_{i=1}^{k}m_{i}(\overrightarrow{e})}{k}\cdot(1-\frac{\sum_{i=1}^{k}m_{i}(\overrightarrow{e})}{k})$
(1)

The term $m_{i}(\overrightarrow{e})$ results in 0 or 1 if the edge $e$
represents a non-match, respectively, a match.

We extend the uncertainty criterion by using the number of nodes regarding the
graphs of each edge vector $\overrightarrow{e}$ as a cluster-specific
characteristic. Note, that multiple clusters can contain edges with the same
edge vector due to the same structure and similarity. The goal is to avoid an
over and under-representation of clusters with a certain size concerning all
clusters. Consequently, an edge vector can be assigned to more than one
cluster-specific characteristic. For selecting an edge vector
$\overrightarrow{e}$, we determine a cluster-specific weight
$w_{c}(\overrightarrow{e})$ based on the cluster size distribution from all
available clusters $d_{C}$ and the current training data distribution $d_{T}$.
The distribution of $d_{C}$ and $d_{T}$ are represented as vectors with a
dimension equal to the maximum number of nodes considering all clusters. An
entry of $d_{C}$ and $d_{T}$ consists of the ratio between the frequency of
clusters with a certain number of nodes and the total number of clusters in
$\mathbf{C}$ resp. $\mathbf{T}$. The weight according to a certain cluster
size is computed by the difference $\overrightarrow{w}=d_{C}-d_{T}$. Due to
the n:m relationship between edge feature vectors and clusters, we determine
the average weight according to an edge feature vector $\overrightarrow{e}$
using the specific weights $w_{l}$ of $w$ where the $l$-th entry corresponds
to the cluster size of a cluster $c$ where $e\in c$ holds.

In addition to the cluster-specific characteristic, we extend the selection
strategy by using the average cosine distance between the unlabeled edge
feature vector $\overrightarrow{e}$ and the already selected edge vectors
$e_{T}\in T$. The intention is to select dissimilar vectors compared to the
current training dataset. Summarizing, the different measures
$unc(\overrightarrow{e})$, $w(\overrightarrow{e})$ and
$avg\\_cos(\overrightarrow{e})$ are averaged to a final informativeness score
being used to order the edge feature vectors. Using the order, we select
$iter\\_budget$ edge feature vectors in each iteration until the training data
size achieves the labeling budget.

(a) start

(b) iteration=1

(c) iteration=2

(d) iteration=3

Figure 3: Example of the iterative cluster repair procedure showing 6 records
of an initial cluster. The dashed red line is an edge being classified as non-
match.

###  4.3 Iterative Cluster Repair

The repair method resolves each cluster utilizing the generated classification
model $\mathbf{M}$. At first, we determine for each cluster $c$ the set of
edges $E_{NM}$ and $E_{M}$ classified as non-matches resp. as matches using
the related edge feature vectors. Each record $u$ and $v$ of an edge $(u,v)\in
E_{NM}$ represent a repaired cluster $c_{u}$ and $c_{v}$ of $C_{rep}$ because
$u$ and $v$ are classified as different entities. We iteratively merge the
remaining records into the existing clusters until they are stable. The
process utilizes a support value $sup(u,c)$ indicating the strength of the
assignment of record $u$ and the cluster $c$. The support is defined as the
difference concerning the number of predicted matches and non-matches between
the record $u$ and records $v\in c$ being already added to cluster $c$. The
merging process checks each cluster $c\in C_{rep}$ by considering the adjacent
nodes $u$ of a record $v\in c$. If the adjacent record $u$ is not connected
via an edge predicted as non-match and is not merged into another cluster
$c^{\prime}$, we add the adjacent record $u$ to $c$. We also maintain the
support $sup(u,c)$ of $u$ being an element of $c$. If the record $u$ is
already assigned to another cluster c’, we compare the support values
$sup(u,c)$ and $sup(u,c^{\prime})$. We change the cluster assignment, if the
support $sup(u,c)$ of the considered cluster $c$ is higher than the support
$sup(u,c^{\prime})$ of the previous cluster $c^{\prime}$. The assignment could
differ depending on the order in which the adjacent records are processed.
Therefore, we repeat this procedure for the new clusters until they do not
change.

Example: Figure 3 shows an example of the iterative cluster repair step. In
this example, we have a cluster with 6 records. The classification model
classifies the edge $(r3,r5)$ as non-match. Consequently, the records $r3$ and
$r5$ represents two clusters $c1$ and $c2$. In the first iteration, the
approach considers the adjacent records $r1$ and $r4$ according to $r3$ as
well as $r6$ connected to $r5$. Note, that $r4$ will also be considered for
$r5$. The records $r1$ and $r4$ are assigned to cluster $c1$ with a support of
1. Considering the adjacent nodes of $r5$, only $r6$ is assigned to the
cluster $c2$. The assignment of $r4$ does not change because the support
$sup(r4,c1)=1$ is equal to $sup(r4,c2)=1$. In the second iteration, the
assignment of the records $r1$ and $r4$ are the same. The record $r2$ is added
to the cluster $c1$ with $sup(r2,c1)=2$. In the next iteration, the assignment
does not change so the approach terminates.

##  5 Evaluation

We evaluate our graph metric-based cluster repair method considering two
datasets, namely MusicBrainz and Dexter. Initially, we analyze the impact of
the cluster-specific characteristics for selecting new training data in the
active learning step. Moreover, we compare the achieved results with existing
repair methods utilizing the similarities and link categories discussed in
Section 3. Due to the challenges of linking, we also evaluate how robust our
method is regarding noisy similarity graphs. To measure the effectiveness, we
compute the F1-score, defined as the harmonic mean of precision and recall. In
pre-experiments, we determined the number of labels selected for each
iteration $iter\\_budget=20$ and the number of models $k=100$ for determining
the uncertainty. We repeated the experiment three times.

In the following, we describe the datasets in section 5.1. After that, we
compare the impact of our modification of the active learning procedure in
section 5.2. We compare our method with existing approaches in section 5.3 and
finally, we verify the robustness in section 5.4.

Table 2: Dataset overview and linking configuration of MusicBrainz and Dexter. Dataset | MusicBrainz | Dexter
---|---|---
C0 | C50 | C100
#Records | 20,000 | 21,023
#Matches | 16,250 | 368,546 | 38084 | 16014
Attributes | Artist, title, album, year, | Heterog. key-value pairs
length, language, number
Blocking Key | preLen1(album) | mfr. name, model number
Similarity | Trigram(title) | Trigram(model names,
product code, sensor type),
Function | Euclid(opt./digital zoom,
| camera dim.,price,
| weight, resolution)

###  5.1 Datasets

We use datasets from two domains: records about music albums (MusicBrainz) and
consumer products of type camera (Dexter). Both datasets are multi-source
datasets and heterogeneous regarding their error characteristics. In contrast
to the MusicBrainz dataset being duplicate-free, the camera dataset is dirty
and contains intra-source duplicates.

####  5.1.1 MusicBrainz

The MusicBrainz dataset is a synthetically generated dataset from the
MusicBrainz (https://musicbrainz.org/) database. The dataset is corrupted by
[10], consisting of five sources with duplicates for $50\%$ of the original
records. Each data source is duplicate-free, but the records are heterogeneous
regarding the characteristics of attribute values, such as the number of
missing values, length of values, and ratio of errors. The similarity graphs
we used in our evaluation have been utilized in several previous studies [26,
27, 12, 25]. The linkage configuration is shown in Table 2.

####  5.1.2 Dexter

This dataset is derived from the camera dataset of the ACM SIGMOD 2020
Programming Contest
(http://www.inf.uniroma3.it/db/sigmod2020contest/index.html). The dataset
consists of 23 sources with $\approx$21,000 records and intra-source
duplicates. Each data source consists of source-specific attributes. We used
the same linkage configuration as in previous studies [25, 27] (see Table 2).
In addition to the original dataset, Lerm et al. [12] also derive various
datasets of different duplicate ratios. Therefore, they deduplicated a
specified set of data sources and selected a certain ratio of records to
construct clean data sources. The remaining data sources were used to generate
the dirty data sources. We consider the datasets $C0,C50$, and $C100$ in our
evaluation. For instance, the dataset $C50$ consists of $\approx 50\%$ records
from deduplicated sources according to the total number of records of the
constructed dataset.

Figure 4: Results on Music Brainz and Dexter(C0, C50, C100) datasets with
different duplicate ratios considering the basic selection strategy
(bootstrap) and the cluster-specific selection (bootstrap ext) in the active
learning step.

###  5.2 Cluster-specific Training Data Selection

Initially, we compare the cluster-specific active learning method (bootstrap
ext) with the original approach [14] (bootstrap) shown in Figure 4. Both
selection strategies improve the initial quality considering the given
similarity graph (dashed line) for all datasets. The results also show
robustness using different labeling budgets since the F1-score only differs by
$\approx$0.017 (bootstrap) and $\approx$0.016 (bootstrap ext).

In terms of the effectiveness regarding data quality issues, the cluster-
specific selection strategy slightly improves the results by up to
$\approx$0.018 compared to the baseline for repairing clusters of dirty
datasets such as C0. However, the baseline achieves better results for
duplicate-free datasets than the extended selection.

Figure 5: F1-score results of our proposed approach (GraphCR) as compared with
the other repair methods CLIP [26], affinity propagation clustering (MSCD-AP)
[12] as well as agglomerative hierarchical clustering methods [25] with the
different variations regarding the merging step single (MSCD S-LINK), complete
(MSCD C-LINK) and average (MSCD A-LINK). Figure 6: Decision matrix comparing
cluster repair approaches using Bayesian signed rank tests. Each cell shows
the decision when comparing the row approach to the column approach.

###  5.3 Comparison with Existing Repair Methods

We compare our method with the CLIP method [26] and two clustering-based
repair approaches based on hierarchical agglomerative clustering with the
different clustering strategies single(MSCD S-Link), complete(MSCD C-Link),
and average(MSCD A-Link) [25] as well as affinity propagation(MSCD-AP) [12].

Depending on the datasets’ dirtiness and the clustering algorithm’s
configuration, the existing methods improve the quality of the initial
similarity graphs. However, the resulting quality of a certain configuration
highly differs regarding the different datasets and thresholds. For instance,
the F1-score achieved by CLIP ranges from 0.1(C0) to 0.9(C100). Even the
results of the hierarchical clustering methods designed for mixed datasets
differ between 0.83(C0) and 0.89(C100) for MSCD A-LINK. GraphCR outperforms
the existing approaches concerning the used thresholds and datasets for
labeling budgets $\geq$ 1500\. The F1-score differences regarding the
dirtiness of datasets are especially small compared to the baseline
approaches. For instance, the F1-score difference is smaller than 0.03 for
GraphCR concerning C0 and C100 using a labeling budget of 1500 overall
thresholds.

To properly compare the performance of these approaches, we rely on the
Bayesian analysis proposed in [3]. To determine significant differences
between the two approaches, we rely on a Bayesian signed rank test [4]. Using
Bayesian statistics gives the advantage over a frequentist hypothesis testing
approach that can not only reject but also accept a null hypothesis. We can
also define a region of practical equivalence (ROPE) where approaches perform
equally well. The Autorank [9] package provides these methods and can
automatically set the ROPE in relation to effect size. The result of our
analysis then provides us with a probability that one approach is better (or
worse) than another. We provide a verdict if one of these probabilities is
$\geq 95$%, or else we see the result as inconclusive.

The result of this analysis is a decision matrix in Figure 6. We compared the
F1-score of each approach across all dataset/threshold combinations. For
GraphCR, we also compare different labeling budgets. It is evident that
GraphCR, with a labeling budget of 2000, is significantly better than all
other approaches. Even with a budget of 1500, it is still better than all
approaches that are not GraphCR.

###  5.4 Effect of Noisy Similarities

The LOD cloud consists of a large number of sameAs links. Nonetheless, a
significant portion of these connections originates from sources whose
correctness is suspect. This uncertainty can arise from various sources,
including the utilization of improperly configured entity resolution systems
or the presence of inaccurately defined links. Within this section, we aim to
assess the robustness of our proposed method in the presence of noisy
similarities. In the following experiment, we randomly select a specified
ratio of edges and set the similarity to a random number between 0 and 1. We
assume that the noisy similarity edges negatively impact the generated
classification model and, therefore, the result of the cluster repair.

(a) MusicBrainz

(b) Dexter C0

Figure 7: Results on Dexter and MusicBrainz datasets with various error ratios
of the similarities using the extended resp. Basic selection strategy in the
active learning step.

Figure 7 show the results for the MusicBrainz dataset applying the
bootstrapping selection (bootstrap) and the Dexter dataset C0 using the
extended strategy (bootstrap ext). Using the original similarity graph without
any noise (error ratio = 0) for the MusicBrainz dataset results in a small
quality difference of at most 0.007. As expected, the increase in the error
ratio leads to a decrease in quality. Especially, an error ratio of 0.5 leads
to F1 score differences up to 10%(MusicBrainz) and 6%(Dexter-C0). The
threshold and the budget influence the robustness of the results. An
increasing threshold and labeling budget positively influence the robustness.
A higher threshold reduces the number of noisy similarities being already
included in the original graph compared to a smaller threshold. Moreover, the
increasing budget leads to a reduced impact of noisy links. In summary, the
results showed that our graph-based cluster repair approach improves the
quality of the initial clusters using a moderate labeling effort. Moreover,
the method outperforms the existing cluster repair methods with less
configuration effort than the existing approaches.

##  6 Conclusion

Cluster repair methods play an integral role in data integration tasks being
relevant for knowledge graph completion. Knowledge graphs support
comprehensive analysis and the realization of complex question-answering
systems. The construction from various and heterogeneous data sources with
different quality levels requires entity resolution identifying records
representing the same entity. Due to the transitive closure of sameAs links
and incorrect edges, the result potentially consists of clusters derived by
the similarity graph with records representing different entities. Therefore,
cluster repair methods aim to identify incorrect records in clusters utilizing
the generated similarity graph. The majority of repair methods intensively
rely on the assumption of duplicate-free data sources. Current methods try to
overcome this issue by modifying general clustering approaches. However, the
results vary depending on the configuration of the entity resolution tool and
the degree of dirtiness.

Therefore, we proposed a novel cluster repair method relying on graph metric
features enabling the training of a classification model. The computed model
is used to modify the initial clusters by iteratively removing edges being
classified as non-match. Due to the lack of available training data, we
integrate and extend an active learning method by considering cluster-specific
characteristics to guarantee that the selected training samples represent the
complete dataset. We evaluated our proposed approach using two real-world
datasets. The results showed that our method outperforms existing approaches
using a moderate labeling budget.

In future work, we plan to apply our method to datasets crawled from the LOD
cloud and potentially improve the current state of link repositories. In terms
of effectiveness, we plan to consider the relations of the underlying
knowledge graphs and determine similarity edge features in combination with
the semantic edges. Due to the manual labeling process in the active learning
step, we will evaluate graph-based methods [24] to reduce the number of
selected samples. Moreover, we will also consider cluster-wise active learning
strategies where a whole cluster is labeled regarding the correct and
incorrect record. This allows the application of graph augmentation, such as
the addition of correct links regarding one cluster.

### Availability

Reference code and datasets are available from our repository at
https://anonymous.4open.science/r/graphCR-DA60 and
https://www.dropbox.com/scl/fo/xtawtr2qbeckt0esu5v0h/h?rlkey=6lkz7hwsyhnqgyhg9quh7pp96&dl=0.

### Acknowledgments

This work was partially supported by the German Federal Ministry of Education
and Research by funding the ”Center for Scalable Data Analytics and Artificial
Intelligence Dresden/Leipzig” (ScaDS.AI).

## References

  * [1] Arasu, A., Götz, M., Kaushik, R.: On active learning of record matching packages. In: ACM SIGMOD. pp. 783–794. Indianapolis (2010). https://doi.org/10.1145/1807167.1807252
  * [2] Bellare, K., Iyengar, S., Parameswaran, A.G., Rastogi, V.: Active sampling for entity matching. In: ACM SIGKDD. pp. 1131–1139. Beijing (2012). https://doi.org/10.1145/2339530.2339707
  * [3] Benavoli, A., Corani, G., Demsar, J., Zaffalon, M.: Time for a change: a tutorial for comparing multiple classifiers through bayesian analysis. J. Mach. Learn. Res. 18, 77:1–77:36 (2017), http://jmlr.org/papers/v18/16-305.html
  * [4] Benavoli, A., Corani, G., Mangili, F., Zaffalon, M., Ruggeri, F.: A bayesian wilcoxon signed-rank test based on the dirichlet process. In: Proceedings of the 31th International Conference on Machine Learning, ICML. JMLR Workshop and Conference Proceedings, vol. 32, pp. 1026–1034. JMLR.org (2014), http://proceedings.mlr.press/v32/benavoli14.html
  * [5] Christen, P.: Data Matching – Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection. Springer (2012). https://doi.org/10.1007/978-3-642-31164-2
  * [6] Christen, V., Christen, P., Rahm, E.: Informativeness-based active learning for entity resolution. In: Machine Learning and Knowledge Discovery in Databases \- International Workshops of ECML PKDD. Communications in Computer and Information Science, vol. 1168, pp. 125–141. Springer (2019). https://doi.org/10.1007/978-3-030-43887-6_11
  * [7] Doan, A., Konda, P., C., P.S.G., Govind, Y., Paulsen, D., Chandrasekhar, K., Martinkus, P., Christie, M.: Magellan: toward building ecosystems of entity matching solutions. Commun. ACM 63(8), 83–91 (2020). https://doi.org/10.1145/3405476, https://doi.org/10.1145/3405476
  * [8] Harris, J.M., Hirst, J.L., Mossinghoff, M.J.: Combinatorics and Graph Theory, Second Edition. Undergraduate Texts in Mathematics, Springer (2008)
  * [9] Herbold, S.: Autorank: A python package for automated ranking of classifiers. J. Open Source Softw. 5(48), 2173 (2020). https://doi.org/10.21105/JOSS.02173, https://doi.org/10.21105/joss.02173
  * [10] Hildebrandt, K., Panse, F., Wilcke, N., Ritter, N.: Large-scale data pollution with apache spark. IEEE Trans. Big Data 6(2), 396–411 (2020). https://doi.org/10.1109/TBDATA.2016.2637378
  * [11] Hofer, M., Obraczka, D., Saeedi, A., Kopcke, H., Rahm, E.: Construction of knowledge graphs: State and challenges. arXiv preprint (2023). https://doi.org/https://doi.org/10.48550/arXiv.2302.11509
  * [12] Lerm, S., Saeedi, A., Rahm, E.: Extended affinity propagation clustering for multi-source entity resolution. In: Datenbanksysteme für Business, Technologie und Web (BTW). pp. 217–236 (2021). https://doi.org/10.18420/btw2021-11
  * [13] Li, B., Miao, Y., Wang, Y., Sun, Y., Wang, W.: Improving the efficiency and effectiveness for bert-based entity resolution. In: Thirty-Fifth AAAI Conference on Artificial Intelligence. pp. 13226–13233. AAAI Press (2021). https://doi.org/10.1609/AAAI.V35I15.17562
  * [14] Mozafari, B., Sarkar, P., Franklin, M., Jordan, M., Madden, S.: Scaling up crowd-sourcing to very large datasets: A case for active learning. PVLDB Endowment 8(2), 125–136 (Oct 2014)
  * [15] Mudgal, S., Li, H., Rekatsinas, T., Doan, A., Park, Y., Krishnan, G., Deep, R., Arcaute, E., Raghavendra, V.: Deep learning for entity matching: A design space exploration. In: Das, G., Jermaine, C.M., Bernstein, P.A. (eds.) Proceedings of the 2018 International Conference on Management of Data. pp. 19–34. ACM (2018). https://doi.org/10.1145/3183713.3196926
  * [16] Nentwig, M., Groß, A., Möller, M., Rahm, E.: Distributed holistic clustering on linked data. In: On the Move to Meaningful Internet Systems. OTM 2017 Conferences - Confederated International Conferences: CoopIS, C&TC, and ODBASE 2017, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10574, pp. 371–382. Springer (2017). https://doi.org/10.1007/978-3-319-69459-7_25
  * [17] Nentwig, M., Hartung, M., Ngomo, A.N., Rahm, E.: A survey of current link discovery frameworks. Semantic Web 8(3), 419–436 (2017). https://doi.org/10.3233/SW-150210, https://doi.org/10.3233/SW-150210
  * [18] Newman, M.E.J.: Networks: An introduction (2010), https://api.semanticscholar.org/CorpusID:60557556
  * [19] Ngomo, A.N., Sherif, M.A., Georgala, K., Hassan, M.M., Dreßler, K., Lyko, K., Obraczka, D., Soru, T.: LIMES: A framework for link discovery on the semantic web. Künstliche Intell. 35(3), 413–423 (2021). https://doi.org/10.1007/S13218-021-00713-X, https://doi.org/10.1007/s13218-021-00713-x
  * [20] Ngomo, A.N., Sherif, M.A., Lyko, K.: Unsupervised link discovery through knowledge base repair. In: The Semantic Web: Trends and Challenges - 11th International Conference, ESWC 2014, Proceedings. Lecture Notes in Computer Science, vol. 8465, pp. 380–394. Springer (2014). https://doi.org/10.1007/978-3-319-07443-6_26
  * [21] Ngonga Ngomo, A.C., Lyko, K.: Eagle: Efficient active learning of link specifications using genetic programming. In: The Semantic Web: Research and Applications. pp. 149–163. Berlin, Heidelberg (2012)
  * [22] Pan, S., Luo, L., Wang, Y., Chen, C., Wang, J., Wu, X.: Unifying large language models and knowledge graphs: A roadmap. arXiv preprint (2023). https://doi.org/10.48550/ARXIV.2306.08302
  * [23] Peeters, R., Bizer, C.: Using ChatGPT for entity matching. In: Abelló, A., Vassiliadis, P., Romero, O., Wrembel, R., Bugiotti, F., Gamper, J., Vargas-Solar, G., Zumpano, E. (eds.) New Trends in Database and Information Systems - ADBIS 2023. Communications in Computer and Information Science, vol. 1850, pp. 221–230. Springer (2023). https://doi.org/10.1007/978-3-031-42941-5_20
  * [24] Primpeli, A., Bizer, C.: Graph-boosted active learning for multi-source entity resolution. In: The Semantic Web - ISWC 2021 - 20th International Semantic Web Conference, ISWC 2021, Virtual Event, October 24-28, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12922, pp. 182–199. Springer (2021). https://doi.org/10.1007/978-3-030-88361-4_11
  * [25] Saeedi, A., David, L., Rahm, E.: Matching entities from multiple sources with hierarchical agglomerative clustering. In: IC3K. pp. 40–50. SCITEPRESS (2021). https://doi.org/10.5220/0010649600003064
  * [26] Saeedi, A., Peukert, E., Rahm, E.: Using link features for entity clustering in knowledge graphs. In: The Semantic Web - 15th International Conference, ESWC 2018, Proceedings. Lecture Notes in Computer Science, vol. 10843, pp. 576–592. Springer (2018). https://doi.org/10.1007/978-3-319-93417-4_37
  * [27] Saeedi, A., Peukert, E., Rahm, E.: Incremental multi-source entity resolution for knowledge graph completion. In: ESWC. vol. 12123, pp. 393–408. Springer (2020). https://doi.org/10.1007/978-3-030-49461-2_23
  * [28] Shen, W., DeRose, P., Vu, L.H., Doan, A., Ramakrishnan, R.: Source-aware entity matching: A compositional approach. In: Chirkova, R., Dogac, A., Özsu, M.T., Sellis, T.K. (eds.) Proceedings of the 23rd International Conference on Data Engineering, ICDE 2007, The Marmara Hotel, Istanbul, Turkey, April 15-20, 2007. pp. 196–205. IEEE Computer Society (2007). https://doi.org/10.1109/ICDE.2007.367865
  * [29] Yang, L., Chen, H., Li, Z., Ding, X., Wu, X.: ChatGPT is not enough: Enhancing large language models with knowledge graphs for fact-aware language modeling. arXiv preprint (2023). https://doi.org/10.48550/ARXIV.2306.11489