The Minimum Edit Arborescence Problem and Its Use in Compressing Graph Collections [Extended Version]Supported  by  Agence  Nationale  de  la  Recherche  (ANR),  projects STAP ANR-17-CE23-0021 and DELCO ANR-19-CE23-0016. FY acknowledges  the  support  of  the  ANR  as  part  of  the Investissements  d’avenir program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute).
The Minimum Edit Arborescence Problem

Lucas Gnecco1 0000-0002-1561-2080 Nicolas Boria1 0000-0002-0548-4257 Sébastien Bougleux2 0000-0002-4581-7570 Florian Yger1 0000-0002-7182-8062 David B. Blumenthal3 0000-0001-8651-750X

L. Gnecco et al.

PSL Université Paris-Dauphine, LAMSADE, Paris, France
<EMAIL_ADDRESS>UNICAEN, ENSICAEN, CNRS, GREYC, Caen, France
<EMAIL_ADDRESS>Department Artificial Intelligence in Biomedical Engineering (AIBE), Friedrich-Alexander University Erlangen-Nürnberg (FAU), Erlangen, Germany

The inference of minimum spanning arborescences within a set of objects is a general problem which translates into numerous application-specific unsupervised learning tasks. We introduce a unified and generic structure called edit arborescence that relies on edit paths between data in a collection, as well as the , which asks for an edit arborescence that minimizes the sum of costs of its inner edit paths. Through the use of suitable cost functions, this generic framework allows to model a variety of problems. In particular, we show that by introducing encoding size preserving edit costs, it can be used as an efficient method for compressing collections of labeled graphs. Experiments on various graph datasets, with comparisons to standard compression tools, show the potential of our method.

§ PRELIMINARIES

We consider data (sequence, tree, graph) defined by a combinatorial structure and labels attached to the elements of this structure. Labels may be of any type. Unlabeled and unstructured data are special cases.

Edit Distance.

Given a space $\Omega$ of all data of a fixed type, an edit path is a sequence of elementary modifications (or edit operations) transforming an object of $\Omega$ into another one. Typical edit operations are the deletion and the insertion of an element of the structure, and the substitution of an attribute attached to an element. Given a cost function $c\geq 0$ defined on edit operations, the edit distance $d_c:\Omega\times\Omega\rightarrow\mathbb{R}_{\geq 0}$ measures the minimal total cost required to transform $x\in\Omega$ into $y\in\Omega$, up to an equivalence relation:

$d_c(x,y)\coloneqq {\min}_{P\in\mathcal{P}(x,y)}\,c(P)$,

with $c(P)\coloneqq\sum_{o\in P}c(o)$ the cost of an edit path $P$, and $\mathcal{P}(x,y)$ the set of all edit paths transforming $x$ into an element of $[y]\coloneqq\{z\in\Omega\,|\,y\sim z\}$, the equivalence class of $y$ for an equivalence relation $\sim$ on $\Omega$.

Equality is the equivalence relation usually considered for strings or sequences (Hamming, Levenshtein or
discrete time warping distances).

Isomorphism is used for trees and graphs.

The set $\Omega$ equipped with an edit distance $d_c$ defines an edit space $(\Omega,d_c)$.
We assume that $d_c$ is metric or pseudometric (
if $\sim$ is not equality).
The set $\Omega$ contains a null (or empty) element denoted by $0_\Omega\in\Omega$. Any other element of $(\Omega,d_c)$ can be constructed by insertion operations only from $0_\Omega$.

A directed graph (digraph) is a pair $G\coloneqq(V,E)$, where $V\coloneqq\{v_0,..,v_n\}$ is a set of nodes and $E\subseteq V\times V$ is a set of directed edges. Within such a graph, a spanning arborescence is a rooted, oriented, spanning tree, , a set of edges that induces exactly one directed path from a root node $r\in V$ to each other node in $V\setminus\{r\}$. By assuming w. l. o. g. that the root element is $v_0$ and reminding that all other nodes in an arborescence have a unique parent node, an arborescence can
be represented by a sequence of node indices $\bigA$ such that, for all $i \in [1,n]$, $\bigA[i]$ denotes the index of the unique parent node of node $v_i$. The set of edges of $\bigA$ is denoted by $E^\bigA$.

§ THE

In this section, we introduce and describe the generic   (), a versatile problem. An instance of is a finite dataset $X$ living in an edit space $(\Omega,d_c)$. asks for a minimum-cost edit arborescence rooted at the null element.

Given a set $X\coloneqq\{x_0,x_1,...,x_n\}\subset\Omega$ such that $x_0\coloneqq 0_\Omega$, we define an edit arborescence as a pair $(\bigA,\Psi)$, where

$\bigA$ is a sequence of $n$ indices that defines an arborescence rooted at the index $0$, such that for all $i\in[1,n]$, $\bigA[i]$ is the parent-index of $i$.

$\Psi\coloneqq(P_1,...,P_n)$ is a sequence of edit paths, such that $P_i\in \mathcal{P}(x_{\bigA[i]},x_i)$ holds for all $\in[1,n]$,
, $P_i$ is an edit path between $x_i$ and its parent in $\bigA$.

$\spaceA(X)$ is the set of all edit arborescences on $X$.

Given a finite set $X\subset\Omega$ and an edit cost function $c$, the () asks for an edit arborescence $(A^\star,\Psi^*)$ on $X\cup\{0_\Omega\}$, which is rooted at the null element $0_\Omega\in\Omega$ and has a minimum cost $c(\Psi^\star)$ among all $(\bigA,\Psi)\in\spaceA(X)$, with $c(\Psi)\coloneqq\sum_{P\in\Psi}c(P)$.

By definition, it holds that $c(\Psi^\star)=\min_{(\bigA,\Psi)\in\spaceA_c(X)}\sum_{P_i\in\Psi}d_c(x_{\bigA[i]},x_i)$, where $\spaceA_c(X)$ is the set of edit arborescences in $(\Omega,d_c)$, , edit arborescences with edit paths restricted to minimal-cost edit paths $c$. This generic definition can translate into various optimization problems, with different characteristics in terms of complexity and/or approximability, depending on the edit space.

Exact Solver.
Whenever exact edit distances and corresponding edit paths can be computed, the following procedure produces an optimal solution for $\MEA$:

* Construct the complete directed weighted graph on the set $X\cup\{0_\Omega\}$, denoted by $\mathcal{K}(X,d_c)\coloneqq(V^\mathcal{K},E^\mathcal{K},w)$, with node set $V^\mathcal{K}\coloneqq X\cup\{0_\Omega\}$ and edge weights $w(u,v)\coloneqq d_c(u,v)$ for all $(u,v)\in E^\mathcal{K}$. Note that any edge entering the root can be removed.

* Solve the Minimum Spanning Arborescence Problem () on $\mathcal{K}(X,d_c)$  with $0_\Omega$ as root node.

For a connected weighted directed graph $G$ and a root node $r$ in $G$, the () asks for a spanning arborescence $A^\star$ on $G$, which is rooted in $r$ and has minimum weight $w(A^\star)$, where $w(A)\coloneqq\sum_{(u,v)\in A}w(u,v)$ [12].
can be solved in polynomial time, , in $O(|V^G|^2)$ time with Tarjan's implementation [21] of Edmonds' algorithm [12]. Hence, the main difficulty of the problem consists in computing the edge weights in $\mathcal{K}$, , the edit distances between elements of $X$.

As long as the edit space $(\Omega,d_c)$ allows for a polynomial time computation of minimum-cost edit paths, the corresponding version of belongs to the complexity class $\mathcal{P}$.

By assumption,
$d_c$ is computed in polynomial time by some algorithm that is called $O(n^2)$ times with complexity $O_{\ALGDIST}$ in order to generate the complete graph
$\mathcal{K}(X,d_c)$. So, can be solved in
$O(n^2O_{\ALGDIST}+(n+1)^2)$ time complexity by using Tarjan's implementation of Edmond's algorithm.

A Heuristic for Non-Polynomial Cases.

adapt the
algorithm described above to cases where the edit distance is not solvable in polynomial time. It is based on
approximations or heuristics to estimate the edit distance.

A generic heuristic for $\MEA$.
[1]
A finite set $X$ of elements from an edit space $(\Omega,d)$ with origin $0_\Omega$, a parameter $k\in[0,|X-1|]$, two edit distance heuristics and .
A low-cost edit arborescence $(\mathcal{A},\Psi)$ for the $\MEA$ problem.
Set $x_0\coloneqq 0_\Omega$ and initialize auxiliary graph $\mathcal{K}(X\cup x_0,E^{\mathcal{K}},w)$ with $E^{\mathcal{K}}\coloneqq\{x_0\}\times X$.

for $x\in X$ do Sample $k$ children $\Tilde{X}\in\binom{X\setminus\{x\}}{k}$ and set $E^\mathcal{K}\coloneqq E^\mathcal{K}\cup(\{x\}\times \Tilde{X})$.
prior information available
Add promising edges to $E^{\mathcal{K}}$.

$ (x_i,x_j) \in E^\mathcal{K}$
Analytically compute the edit path $P_{ij}$.
identifiers available
Compute edit path $P_{ij}$ induced by identifiers.
Call to compute low-cost edit path $P_{ij}$.
Set $w(x_i,x_j)\coloneqq c(P_{ij})$.

Run Edmonds' algorithm on $\mathcal{K}$ to obtain $\bigA$.

if tightening then for $i\in [1,n]$ do Call to compute tighter edit path $P_{\bigA[i]i}$.

$ i \in [1,n]$
Set $\Psi[i]\coloneqq P_{\bigA[i]i}$.
return $(\mathcal{A},\Psi)$

We adapt the algorithm described above to cases where the edit distance is not solvable in polynomial time. Given a set $X\subset\Omega$, <Ref> computes a low-cost edit arborescence $(\bigA,\Psi)\in\spaceA(X)$ based on approximations or heuristics to estimate the edit distance. It starts by constructing a size-reduced auxiliary digraph $\mathcal{K}$ (lines <ref> to <ref>) that connects $0_\Omega$ to each element $x_i\in X$, and each $x_i$ to $k\leq|X|-1$ randomly selected elements of $X\,{\setminus}\,\{x_i\}$. If some promising edges are known a priori (, if $X$ has an implicit internal structure), they are added to $\mathcal{K}$.

Then, <Ref> computes optimal or low-cost edit paths whose costs provide weights for the edges of $\mathcal{K}$ (lines <ref> to <ref>). For $0_\Omega$' out-edges, optimal edit paths can be computed analytically (insertions only). If identifying attributes are available for all elements of $X$ (, unique node labels if $X$ is a set of graphs), it is sometimes possible to compute optimal edit paths from these identifiers. Otherwise, low-cost edit paths are computed by calling a polynomial edit distance heuristic . Once all edge weights for $\mathcal{K}$ have been computed, an optimal arborescence $\bigA$ on $\mathcal{K}$ is constructed by Edmonds' algorithm (line <ref>). Optionally, a tighter edit distance heuristic can be called to shorten the paths in $\bigA$ before returning the edit arborescence (line <ref>).

A generic algorithm for $\MEA$
[1]
A set $\mathcal{C}$ of space $\Omega$ with origin $\omega$,  a cost function $f$ on the dit operations with $\Omega$
An optimal solution $\mathcal{A}$ for the $\MEA$ problem
Initialize $GE(\mathcal{C},f)$ as a complete digraph over $n+1$ vertices $v_0,...,v_n$
$ (i,j) \in [0,...,n+1]\times [1,..,n+1]$ s.t. $i\neq j$:
compute the edit distance $d(\omega_i,\omega_j)$ using  $ \verb|P_DIST| $ and set it as the weight of edge $(v_i,v_j)$ in $GE(\mathcal{C},f)$
Compute an optimal arborescence $\mathcal{A^*}$ rooted at $v_0$ in  $GE(\mathcal{C},f)$ using a  Tarjan's implementation of Edmonds' algorithm.

In the remainder of the paper, we will focus on the specific case of where the space $\Omega$ is a space of labeled graphs.

We assume
that graphs are finite, simple, undirected, and labeled. However, all presented techniques can be straightforwardly adapted to directed or unlabeled graphs.
A labeled graph $G$ is a four-tuple $G\coloneqq(V^G,E^G,\ell^G_V,\ell^G_E)$, where $V^G$ and $E^G$ are sets of nodes and edges, while  $\ell^G_V:V^G\to\Sigma_V$ and $\ell^G_E:E^G\to\Sigma_E$ are labeling functions that annotate nodes and edges with labels from alphabets $\Sigma_V$ and $\Sigma_E$, respectively. $\spaceG(\Sigma_V,\Sigma_E)$, or $\spaceG$ for short, denotes the set of all graphs for fixed alphabets $\Sigma_V$ and $\Sigma_E$. $0_\spaceG$ denotes the empty graph (the null element of $\spaceG$). Two graphs $G,H\in\spaceG$ are isomorphic, denoted by $G\simeq H$, if and only if there is a bijection between
$V^G$ and $V^H$ that preserves both edges and labels.

Edit Operations and Edit Paths.

We consider the following elementary edit operations, where $\epsilon$ is a dummy node and $\epsilon_\ell$ is a dummy label:

* Node deletion (nd): $(v,\epsilon_\ell)$, with $v\in V^G$ isolated.

* Edge deletion (ed): $(e,\epsilon_\ell)$, with $e\in E^G$.

* Node relabeling (nr): $(v,\ell)\in V^G\times(\Sigma_V\setminus\{\ell^G_V(v)\})$.

* Edge relabeling (er): $(e,\ell)\in E^G\times(\Sigma_E\setminus\{\ell^G_E(e)\})$.

* Node insertion (ni): $(\epsilon,\ell)$, with $\ell\in\Sigma_V$.

* Edge insertion (ei): $(e,\ell)\in(\binom{V^G}{2}\setminus E^G)\times\Sigma_E$.

For each edit path $P$ composed of such
operations, there are many equivalent edit paths with a same edit cost, obtained just by reordering the operations in $P$. In particular, as the deletion of a node assumes that its incident edges have been previously deleted, these operations can be replaced by node-edge deletions (ned): delete all the edges incident to a node and then delete this node. So we can distinguish two different types of edge deletions:

* Implied edge deletion (i-ed): an edge deletion in a node-edge deletion.

* Non-implied edge deletion (ni-ed): an edge deletion between two nodes that are not deleted by $P$.

implied edge deletion (i-ed), , an edge deletion in a node-edge deletion, and non-implied edge deletion (ni-ed), , an edge deletion between two nodes that are not deleted by $P$.

The cost of an edit path $P$ can thus be rewritten as

c(P)=\sum_{t\in T}\sum_{o\in P^t}c^t(o)\text{,}

where $P^t$ is the (possibly empty) set of all edit operations of type $t\in T$, with $T\coloneqq\{\text{ni-ed},\text{i-ed},\text{nd},\text{nr},\text{er},\text{ni},\text{ei}\}$, and $c^t$ is an edit cost function for type $t$.

Any concatenation $\sigma_{\text{ni-ed}}(P^{\text{ni-ed}})\sqcup\sigma_{\text{i-ed}}(P^{\text{i-ed}})\sqcup\ldots\sqcup\sigma_{\text{ei}}(P^{\text{ei}})$ of edit operations, with $\sigma_t$ a permutation on $P^t$, defines an edit path equivalent to $P$.

$c(P)=\sum_{t\in T}c^t|P^t|$ if $c_t$ is a constant for each type of operation $t$.

Node Maps and Induced Edit Paths.
A node map (or error-correcting bipartite matching) between a graph $G$ and a graph $H$ is a relation $\pi\in(V^G\cup\{\epsilon\})\times(V^H\cup\{\epsilon\})$ such that the following two conditions hold:

* For each node $u\in V^G$, there is exactly one node $v\in V^H\cup\{\epsilon\}$ such that $(u,v)\in\pi$. We denote this node $v$ by $\pi(u)$.
* For each node $v\in V^H$, there is exactly one node $u\in V^G\cup\{\epsilon\}$ such that $(u,v)\in\pi$. We denote this node $u$ by $\pi^{-1}(v)$.

Let $\Pi(V^G,V^H)$ be the set of all node maps. Each node map $\pi\in\Pi(G,H)$ can be transformed into an edit path, denoted by $P[\pi]$ (induced edit path), such that, for each $(u,v)\in\pi$, there is a corresponding edit operation $(u,\ell)$: $u$ is deleted if $v=\epsilon$, it is relabeled if $(u,v)\in V^G\times V^H$ and $\ell_V^G(u)\not=\ell_V^H(v)$, or a new node is inserted if $u=\epsilon$. Operations on edges are induced by the operations on nodes, , from the pairs $((u,\pi(u)),(v,\pi(v))$ with $u,v\in V^G\cup\{\epsilon\}$. For details, we refer to [6]. What is important here is that any type of edit operation is taken into account by a node map. In particular, implied and non-implied edge deletions can be distinguished with a specific cost for each type.

Graph Edit Distance.
The cost of an optimal edit path from a graph $G$ to a graph $H^\prime\simeq H$ defines the graph edit distance (GED) from $G$ to $H$ ($d_c$ with graph isomorphism as equivalence relation):

$\GED(G,H)\coloneqq{\min}_{P \in \mathcal{P}(G,H)}\,c(P)$.

is hard to compute and approximate, even when restricting to simple special cases [22, 5]. However, many heuristics are able to reach tight upper and/or lower bounds.
They are based on a reformulation of as

an Error-Correcting Graph Matching Problem:
$\GED(G,H)={\min}_{\pi\in\Pi(V^G,V^H)}\,c(P[\pi])$, which is equivalent to the above definition under mild assumptions on the edit cost function $c$.

We refer to [18, 6] for an overview.

Problem Formulation and Hardness.

We can now define :

The () is a problem with $\Omega\,{\coloneqq}\,\spaceG$, $X\,{\coloneqq}\,\{G_1,...,G_n\}$ and $d_c\coloneqq\GED$.

As the problem of computing is $\NP$-hard, <Ref> does not apply here.

is -hard.

The Hamiltonian cycle problem is an -hard problem which asks to decide if an undirected, unlabeled $G$ contains a cycle passing through all of its nodes. Let $X\coloneqq\{G,H\}$ be a set of graphs with $H$ a cycle on $|V^G|$ nodes, and let $(\bigA^\star,\Psi^\star)$ be an optimal edit arborescence for X. Moreover, we assume that $G$ contains more edges than $H$.

There are three different edit arborescences for $X$, , $\bigA(X)=\{(\bigA_1,\Psi_1)(\bigA_2,\Psi_2),(\bigA_3,\Psi_3)\}$ with edges $E^{\bigA_1}=\{(0_\spaceG,H),(H,G)\}$, $E^{\bigA_2}=\{(0_\spaceG,H),(0_\spaceG,G)\}$, and $E^{\bigA_3}=\{(0_\spaceG,G),(G,H)\}$, respectively.

Assume that $G$ is Hamiltonian. Then, by construction of $H$, an optimal node map $\pi^\star_{H,G}\in\argmin_{\pi\in\Pi(G,H)}c(P[\pi])$ induces an edit path that contains only edge insertions, the edges of $G$ not mapped to an edge of $H$. So $c(\Psi_1)=c(P[\pi_{0_\spaceG,G}])$. As $H$ is non-empty and $G$ has more edges than $H$, it holds that $c(\Psi_1)<c(\Psi_2)$. Similarly, if edge deletion costs are strictly positive, then $c(\Psi_1)<c(\Psi_3)$, otherwise $c(\Psi_1)=c(\Psi_3)=c(P[\pi_{0_\spaceG,G}])$. This implies $c(\Psi^\star)=c(\Psi_1)=c(P[\pi_{0_\spaceG,G}])$ in all cases.

For the reciprocal, we show its contraposition. Assume that $G$ is not Hamiltonian. By choice of $G$ and $H$, an optimal node map $\pi^\star_{H,G}\in\argmin_{\pi\in\Pi(G,H)}c(P[\pi])$ induces an edit path composed of both edge insertions from $G$ and edge removals from $H$. So the concatenation of the path induced by $\pi_{0_\spaceG,H}$ and the path induced by $\pi^\star_{H,G}$ contains $|E^G|$ edge insertions and at least one insertion and deletion of a same edge in $H$. By consequence, $c(\Psi_1)>c(P[\pi_{0_\spaceG,G}])$. Similarly, we obtain $c(\Psi_2)>c(P[\pi_{0_\spaceG,G}])$ and $c(\Psi_3)>c(P[\pi_{0_\spaceG,G}])$. This implies $c(\Psi^\star)\not=c(P[\pi_{0_\spaceG,G}])$.

Let $P$ be the path in $\bigA^\star$ from the root $0_\spaceG$ to $G$, and $\pi^\star_{H,G}$ be an optimal node map from $H$ to $G$:

\begin{eqnarray}
c(\bigA^\star)&\geq c(P)\geq c(P[\pi^\star_{G_0,G}])\label{eq:hardness}
\end{eqnarray}

Moreover, the following statements hold:

* An edit path from the empty graph $G_0$ to any other graph is optimal if and only if it contains only insertion operations.

Since $G$ contains more edges than $H$ and $G$ is non-empty, we know that $c(\bigA)>|\enc(G)|-\beta_G$ holds for all edit arborescence with topology $E^{\bigA}_2$ or $E^{\bigA}_3$. Moreover, the above statements imply that the edit arborescence $(\{G_0,H,G\},E^{\bigA}_1,\{\pi^\star_{G_0,H},\pi^\star_{H,G}\})$ has cost $|\enc(G)|-\beta_G$ if and only if $G$ is Hamiltonian. By <ref>, this proves the theorem.

§ ARBORESCENCE-BASED COMPRESSION

In this section, we show how to leverage for compressing a set of labeled graphs. For this, we introduce reconstructible and non-reconstructible edit arborescences, formulate the (), and present an encoding for induced edit paths.

Reconstructible Edit Arborescence.

[cramped,column sep=1.8em]
0_𝔾[rd,"P_1"]     G_1[rd,"P_2"]      G_2[rd,"P_3"]     G_3[rd,dashrightarrow]

G^'_1     G^'_2     G^'_3   G

[column sep=2.7em]
G_1[d,"π_G_1,G^'_1"][r,dashrightarrow]     G_i-1[d,"π_G_i-1,G^'_i-1"][r, "π_G_i-1,G_i"]     G_i[d,"π_G_i,G^'_i"]

G^'_1 [r,dashrightarrow]     G^'_i-1[r,"π_G^'_i-1,G^'_i"']     G^'_i

(a)   (b)

(a) Paths in a non-reconstructible edit arborescence. (b) Composition of node maps used to construct reconstructible edit arborescences.

When $d_c\coloneqq\GED$, since the definition of is based on graph isomorphism,

applying an induced edit path $P[\pi_{G,H}]$ to a graph $G$ yields a graph $H^\prime\simeq H$.
When using such edit paths within an edit arborescence $(\bigA,\Psi)\in\spaceA(X)$, with $X\subset\spaceG$ a set of graphs, the configuration described in <Ref>(a) occurs. Namely, the edit paths in $\Psi$ may be disjoint due to the isomorphism relation between the source graphs $G_i$ and target graphs $G_i^\prime$. Thus, the arborescence does not allow the reconstruction of any graph that is not directly connected to the root element. In this sense, only specific edit arborescences
allow to reconstruct all graphs in $X$ up to isomorphism.

An edit arborescence $(\bigA,\Psi)\in\spaceA(X)$ is reconstructible if and only if each graph $G_i\in X$ can be constructed up to isomorphism by applying the sequence of edit paths $P\coloneqq(P_{s^1}, P_{s^2},\ldots, P_i)$ to the empty graph $0_\mathbb{G}$, where $(0_\spaceG,G_{s^1},G_{s^2},\ldots,G_i)$ is the path from $0_\spaceG$ to $G_i$ in $\bigA$.

By composition of node maps (<Ref>(b)), it is easy to show
the following property (proof omitted due to space constraints).

For any edit arborescence $(\bigA,\Psi)$ on a set of graphs $X$, there is a reconstructible edit arborescence  $(\bigA,\Psi^\prime)$ on a set $X^\prime$, such that $X^\prime$ is isomorphic to $X$ and it holds that $c(\Psi^\prime)=c(\Psi)$.

According to <Ref> and <Ref>, we encode an edit arborescence $\bigA\in\spaceA$ as the encoding $\enc(\bigA^\prime)$ of an encodable edit arborescence $\bigA^\prime\simeq\bigA$, and so with encoding size $|\enc(\bigA^\prime)|$. Encoding sizes $|\enc(\bigA)|$ and $|\enc(\bigA^\prime)|$ may be different, it depends on the code $\enc$ for induced edit paths. In particular, if $\enc$ satisfies $|\enc(P[\pi_{G,H}^\bigA])|=|\enc(P[\pi^{\bigA^\prime}_{f(G),f(H)}])|$ for each $(G,H)\in E^\bigA$, with $f$ defined in <Ref>, then $|\enc(\bigA)|=|\enc(\bigA^\prime)|$ is guaranteed. Then, we directly obtain the following property from <Ref> and <Ref>.

Let $(\enc,c)$ be an encoding size preserving pair. Then $|\enc(\bigA)|=|\enc(\bigA^\prime)|$ holds for any edit arborescence $\bigA$ and encodable edit arborescence $\bigA^\prime\simeq\bigA$.

By <Ref>, the set of graphs $X$ can be reconstructed up to graph isomorphism based on the encoding of a reconstructible edit arborescence.

Problem Formulation.

For compressing a finite set of graphs $X\subset\spaceG$, we are interested in finding a reconstructible edit arborescence $(\bigA,\Psi)\in\spaceA(X)$ with a small encoding size $|\enc(\bigA,\Psi)|$, where $\enc(\cdot)$ denotes the encoding (a binary string) for the code $\enc$. Ideally we would like to minimize this size over $\spaceA(X)$ and all possible codes. To encode an edit arborescence, we encode both of its elements, , the arborescence $\bigA$ defined as a sequence of indices, and the sequence $\Psi$ of edit paths induced by the node maps. In order to derive a useful expression for the code length function $|\enc(\cdot)|$, the edit path encodings  are concatenated. Thus, the encoding size to optimize is given by

$|\enc(\bigA,\Psi)|=|\enc(M_\bigA)|+|\enc(\bigA)|+{\sum}_{P \in\Psi} |\enc(P)|$,

where $M_\bigA$ is the overhead for decoding the different parts of $\enc(\bigA,\Psi)$. In order to optimize this size
, we must define an encoding size preserving cost function which forces the encoding sizes of edit paths to coincide with their edit cost.

Let $\enc$ be a code for edit paths. An edit cost function $c$ is encoding size preserving code $\enc$ if and only if there is a constant $\gamma$ such that $|\enc(P)|=c(P)+\gamma$ holds for any edit path $P$. Put differently, an encoding size preserving cost function assigns to each edit operation the space required in memory to encode the operations with code $\enc$.

Assuming that a code $\enc$ and an encoding size preserving cost function $c$ $\enc$ exist, the encoding size for any edit arborescence $(\bigA,\Psi)\in\spaceA(X)$ can be rewritten as $|\enc(\bigA,\Psi)|=|\enc(M_\bigA)|+|\enc(\bigA)|+c(\Psi)+\gamma|X|$. Since the encoding size for
$\bigA$ depends only on the number of nodes, the problem of minimizing $|\enc(\bigA,\Psi)|$ amounts to minimizing $c(\Psi)$. Consequently, finding a compact encoding of a set of graphs $X$ reduces to a problem as introduced in <Ref>.

Let $X\coloneqq\{G_1,\ldots,G_n\}\subset\spaceG$ be a finite set of graphs, $\enc$ be a code for edit paths, and $c$ be an encoding size preserving edit cost function for $\enc$. Then, the () asks for a minimum weight reconstructible edit arborescence $(\mathcal{A},\Psi^\prime)$ on some set of graphs $X^\prime\coloneqq\{G_1^\prime,\ldots,G_n^\prime\}$ such that, for all $i\in[1,n]$, $G^\prime_i\simeq G_i$.

We stress that, thanks to the use of encoding size preserving edit costs, the value that is optimized by corresponds to the length of the code $\enc(\bigA,\Psi^\prime)$ up to a constant. In other words, solving $\ABC$ produces the most compact arborescence-based representation of $X$. Given the simple correspondence between reconstructible edit arborescences and their non-reconstructible counterparts,
reduces to  by restricting to encoding size preserving edit costs. Since is -hard (Theorem <ref>), we propose to heuristically compute a low-cost edit arborescence as detailed below.

Heuristic Solver for ABC.

If $|\enc(P[\pi_{0_\spaceG,G}])|=|\enc(G)|$ for any graph $G\in\spaceG$, the problem reduces to a compression problem which asks to find an edit forest spanning $X$ (a disjoint union of edit arborescences), with unknown root graphs in $X$ (not at $0_\spaceG$), minimizing the encoding size $\sum_{G_r}|\enc(G_r)|+\sum_{(G,H)\in E^\mathcal{F}}|\enc(P[\pi_{G,H}^\mathcal{F}])|$, where $G_r\in X$ are the root nodes of the forest $\mathcal{F}$.

encoding of graph collections.
[1]
A set of graphs $X$, a code $\enc$, and an edit cost function $c$.
Encoding $\enc(\bigA,\Psi^\prime)$ of a reconstructible edit arborescence $(\bigA,\Psi^\prime)$ on $X$.
Compute $(\mathcal{A},\Psi)$ with Algorithm <ref>.
Initialize list $L\coloneqq[(0_\spaceG,\pi_{\text{id}})]$, where $\pi_{\text{id}}$ is the identity.
Initialize encoding $\enc(\bigA,\Psi^\prime)\coloneqq\enc(M_\bigA)\enc(E^\bigA)$.
Pop an element $(G_i,\pi_{G_i,G_i^\prime})$ from $L$.
children $G_j$ of $G_i$ in $\bigA$
Get $\pi\in\Pi(G_i,G_j)$ with $P[\pi]=\Psi[j]$ and initialize node ID $v^\prime\coloneqq1$.
Initialize $\pi^\prime\in\Pi(G^\prime_i,G^\prime_j)$ as node map of insertions and deletions only.
for all $v\in V^{G_i}$ if $\pi(v)\neq\epsilon$ then Set $\pi^\prime(\pi_{G_i,G_i^\prime}(v))\coloneqq v^\prime$ and increment $v^\prime$.
Concatenate $\enc(P[\pi^\prime])$ to $\enc(\bigA,\Psi^\prime)$.
$G_j$ is no leaf in
Append $(G_j,\pi^\prime\circ\pi_{G_i,G_i^\prime}\circ\pi^{-1})$ to $L$.
return $\enc(\bigA^\prime,\Psi^\prime)$

Algorithm <ref> sketches our strategy to tackle the  problem.

Given a set $X$ of graphs, it first uses Algorithm <ref>, which outputs a non-reconstructible edit arborescence $(\bigA,\Psi)$ on $X$. After initializing the code, it starts encoding a reconstructible edit arborescence by  going through the arborescence in BFS order (line <ref>). For each new node $G_j$ with parent node $G_i$, a node map $\pi^\prime$ from $G^\prime_i\simeq G_i$ to $G^\prime_j\simeq G_j$ is reconstructed (lines <ref> to <ref>), and the code of its induced edit path is added to the code of the arborescence (line <ref>). If $G_j$ is not a leaf, the node map representing the isomorphism between $G_j$ and $G_j^\prime$ is computed for later use (line <ref>).

In the worst case, we obtain a star $\bigS\in\spaceA(X)$, which connects the empty graph $0_\spaceG$ to all the graphs in $X$. This yields the upper bound $|\enc(\bigA,\Psi)|\leq|\enc(\bigS)|$ on the encoding size of the obtained arborescence.  Since encoding a graph from the empty graph by insertion operations only is similar to encoding the graph itself, the encoding size for the star is close to the encoding size for $X$, for a similar encoding strategy. Consequently, the star ratio $|\enc(\bigA)|/|\enc(\bigS)|$ provides a good indicator for the compression quality.

The encoded structure is designed to allow a straightforward decompression of any graph $G_i$, which, starting from the empty graph, simply consists in consecutively applying the edit paths along the path from the root to $G_i$ in .

A Code for Induced Edit Paths.

We show that there is a code $\enc$ for edit paths and an edit cost function $c$ such that $c$ is encoding size preserving $\enc$. Using the notations introduced in <Ref>,
we encode an edit path as the concatenated string $\enc(P[\pi])\coloneqq\enc(M_P)\enc(P^\textnormal{ni-ed})\enc(P^\textnormal{nd})\enc(P^\textnormal{nr})\enc(P^\textnormal{er})\enc(P^\textnormal{ni})\enc(P^\textnormal{ei})$, where $M_P$ denotes the overhead for decoding each string $\enc(P^t)$. Note that the set $P^\text{i-ed}$ is not encoded, since implied edge deletions can be implicitly represented by node deletions. Similarly, we encode a set of edit operations $P^t$ as $\enc(P^t)\coloneqq\enc(o^t_1)\enc(o^t_2)\cdots\enc(o^t_{|P^t|})$, with $o_i^t\in P^t$. Any edit operation $o\coloneqq(a,\ell)$ is encoded as $\enc(o)\coloneqq\enc(a)\enc(\ell)$, with $\enc(a)\coloneqq\emptyset$ if $a=\epsilon$, and $\enc(\ell)\coloneqq\emptyset$ if $\ell=\epsilon_\ell$. That is, the dummy elements $\epsilon$ and $\epsilon_\ell$ in deletion operations and node insertions are not encoded. Ultimately, the encoding size for $P[\pi]$ hence depends on how the nodes, edges, and their labels are encoded in the codes of the edit operations.

We consider fixed-length codes for nodes, edges, and their labels (other codes will be studied in future works). For a set $X\in\spaceG$, nodes are encoded as integers on $\beta_V$ bits, edges are encoded as a pairs of integers on $2\beta_V$ bits, and node or edge labels are encoded on, respectively, $\beta_{\Sigma_V}$ and $\beta_{\Sigma_E}$ bits.
Dictionaries can be used for the labels and encoded in the overhead $M_\bigA$ or known a priori. In order to decode each set of edit operation $P^t$, $M_P$ must contain their sizes $|P^t|$. They are encoded on $\beta_P$ bits
for each edit path. We

$|\enc(P[\pi])|=\beta_{P}+\sum_{t\in T}c^t|P^t|$,

$c^\textnormal{nr}\coloneqq\beta_V+\beta_{\ell_V}$, $c^\textnormal{nd}\coloneqq\beta_V$, $ c^\textnormal{ni}\coloneqq\beta_{\Sigma_V}$, $c^\textnormal{er}\coloneqq c^\textnormal{ei}\coloneqq 2\beta_V+\beta_{\Sigma_E}$, $c^\textnormal{ed-ni}\coloneqq 2\beta_V$, and $c^\textnormal{ed-i}\coloneqq 0$.

With these constant costs, the pair $(\enc,c)$ defined above is encoding size preserving (<Ref> and <Ref>) with constant $\beta_P$ for any node map $\pi$, , $|\enc(P[\pi])|=c(P[\pi])+\beta_P$.
Therefore, the encoding size for a spanning edit arborescence $(\bigA,\Psi)\in\spaceA(X)$ reduces to $|\enc(\bigA,\Psi)|=|\enc(M_\bigA)|+|\enc(\bigA)|+c(\Psi)+\beta_P|X|$, which implies that minimizing  $|\enc(\cdot)|$ is an problem.

§ EXPERIMENTS

We performed an empirical evaluation of our compression method in the context of data archiving. Since no dedicated algorithms for compressing graph collections exist in this context, we compared it to the generic tar.bz compression, sufficient to highlight the potential of our method. For the evaluation, we used compression ratio (size of compressed graph collection divided by size of original graph collection), compression and decompression times, and star ratio (<Ref>). Further investigations, , comparisons against graph compression methods, applied to each graph individually or to a disjoint union of the graphs in the collection, will be carried out in future work. Other generic compression tools such as zip or tar.gz yielded worse compression ratios than tar.bz in initial tests.

We used eight different datasets (<Ref>). The datasets and from the IAM Graph Database Repository [19], and , , and from GREYC's Chemistry Dataset[<https://brunl01.users.greyc.fr/CHEMISTRY/index.html>] contain graphs modeling chemical compounds. We also tested on time-evolving minimum spanning trees (MSTs) induced by the pairwise correlations of a large-scale U. S. stocks time series dataset.[<https://www.kaggle.com/borismarjanovic/price-volume-data-for-all-us-stocks-etfs>]
Such MSTs are widely used for detecting critical market events such as financial crises [10, 15].
We constructed three versions of the MSTs with the code in [15]: (edge labels are floating-point stocks correlations), (the correlations are rounded to integers), and (no edge label).
For all datasets, graphs were initially stored in GXL format.[<https://userpages.uni-koblenz.de/ ist/GXL/index.php>]

Number of graphs $|X|$, maximum and average number of nodes $|V|$, as well as node and edge label alphabet sizes $|\Sigma_V|$ and $|\Sigma_E|$ for all datasets.

Parameters and Implementation.

We tested two versions of our method (<Ref>) —
with and without additional tar.bz compression of the obtained codes. For both versions, the out-degree $k$ of all nodes
in $\mathcal{K}$ was varied across $\{0.1\cdot|X|,0.2\cdot|X|,\ldots,1.0\cdot|X|\}$, and we did 5 repetitions for each value. For the experiments reported in Table <ref>, we performed 10 repetitions for each dataset. For ,
we also added all temporal edges to $\mathcal{K}$ and always used the node maps induced by the stock identities across time (cf. lines <ref> and <ref> in <Ref>). On the other datasets, the node maps were computed and refined using the heuristics  $\ALGONE\coloneqq\BRANCHUNIFORM$ [23] and $\ALGTWO\coloneqq\IPFP$ [6].

All algorithms were implemented in C++ using the library GEDLIB [7] and the library MSArbor [13].
Tests were run on a Linux system with an Intel Haswell CPU (24 cores, 2.4 GHz each) and 19 GB of main memory.

group style=group name=groupplot, group size=4 by 2, horizontal sep=0.9cm, vertical sep=1.4cm,

at ($(groupplot c1r1.north) !.5! (groupplot c4r1.north)$) [inner sep=0pt,anchor=south, yshift=4ex] ratiolegend;

Mean compression ratios out-degree $k$ for tar.bz and w/ or w/o tar.bz.
For , the values for $k=0$ in the plots correspond to the setting where the auxiliary graph $\mathcal{K}$ only contains temporal edges.

Compression Ratio.
<Ref> shows that, for all datasets except , with tar.bz significantly outperformed tar.bz compression alone and led to smaller compression ratios than w/o tar.bz for all datasets except . Using out-degrees $k>0.4\cdot|X|$ only marginally improved compression. For , using only temporal edges ($k=0$) led to very good results. Moreover, can be more compressed with than the other datasets, as cheaper edit paths can be computed for graphs with unlabeled edges.

Arborescence Structure, Star Ratio, and Runtime.
Columns 2 to 4 of <Ref> provide statistics regarding the arborescences computed with $k=0.4\cdot|X|$. They seem to have a good balance between depth and width (
number of leaves vs. number of internal nodes).
The star ratios (column 5) indicate how much space is gained by using encoding each graph separately with the same underlying encoding scheme (a star ratio of $1$ means no compression). Columns 6 to 9 summarize the compression and decompression times.
The most important observation is that, although is much slower than tar.bz, the runtimes are still acceptable in application scenarios where a data holder wants to offer compressed graph datasets for download (compressing the largest dataset took about four to five hours).

Mean compression and decompression times (in sec.), and standard deviations, of with tar.bz for $k=0.4\cdot|X|$, as well as mean depths, star ratios, numbers of leafs $|\mathcal{L}|$ and inner nodes $|\mathcal{I}|$ of the computed arborescences.

Indeed, unlike compression, decompression is fast even on the largest datasets (a couple of seconds).
Runtime variations $k$ are detailed in <Ref> for four datasets. As expected, the time required for computing the arborescences increases linearly with $k$, and the runtime of the refinement phase is independent of $k$. As the refinement algorithm is randomized, the runtimes of the refinement phase have a higher variability than the runtimes of the arborescence phase.

group style=group name=groupplot, group size=4 by 2, horizontal sep=1cm, vertical sep=1.5cm,

at ($(groupplot c1r1.north) !.5! (groupplot c4r1.north)$) [inner sep=0pt,anchor=south, yshift=3ex] ctimelegend;

Means and standard deviations of runtimes (in sec.) for with tar.bz and its subroutines, and tar.bz alone. -total includes the final tar.bz step.

§ CONCLUSIONS

In this paper, we have proposed the concept of an edit arborescence and have introduced the (). yields a generic framework for inferring hierarchies in finite sets of complex data objects such as graphs or strings, which can be compared via edit distances. We have shown how to leverage for the lossless compression of collections of labeled graphs — a task, for which no dedicated algorithms are available to date. Experiments on eight datasets show that our approach clearly outperforms standard compression tools in terms of compression ratio and that it achieves reasonable compression and decompression times. More precisely, the experiments showed that (1) on seven out of eight datasets, our method clearly outperformed tar.bz compression in terms of compression ratio; (2) compressing with is computationally expensive but still reasonable in settings where the compression is carried out by an institutional data holder; (3) decompression is much faster and only takes a couple of seconds even for the largest test datasets.

[1]
Adler, M., Mitzenmacher, M.: Towards compressing web graphs. In: Proceedings of
the Data Compression Conference. p. 203. IEEE Computer Society (2001).

[2]
Almodaresi, F., Pandey, P., Ferdman, M., Johnson, R., Patro, R.: An efficient,
scalable, and exact representation of high-dimensional color information
enabled using de bruijn graph search. Journal of Computational Biology
27(4),  485–499 (2020). 10.1089/cmb.2019.0322

[3]
Besta, M., Hoefler, T.: Survey and taxonomy of lossless graph compression and
space-efficient graph representations. CoRR  arXive:1806.01799
[cs.DS] (2018)

[4]
Besta, M., Peter, E., Gerstenberger, R., Fischer, M., Podstawski, M., Barthels,
C., Alonso, G., Hoefler, T.: Demystifying graph databases: Analysis and
taxonomy of data organization, system designs, and graph queries. CoRR
arXive:1910.09017 [cs.DB] (2019)

[5]
Blumenthal, D.B.: New Techniques for Graph Edit Distance Computation. Ph.D.
thesis, Free University of Bozen-Bolzano (2019)

[6]
Blumenthal, D.B., Boria, N., Gamper, J., Bougleux, S., Brun, L.: Comparing
heuristics for graph edit distance computation. VLDB J.  29(1),
419–458 (2020). 10.1007/s00778-019-00544-1

[7]
Blumenthal, D.B., Bougleux, S., Gamper, J., Brun, L.: GEDLIB: A C++
library for graph edit distance computation. In: GbRPR 2019. LNCS, vol.
11510, pp. 14–24. Springer, Cham (2019). 10.1007/978-3-030-20081-7_2

[8]
Bookstein, A., Klein, S.: Compression of correlated bit-vectors. Information
Systems  16(4),  387–400 (1991). 10.1016/0306-4379(91)90030-D

[9]
Chwatala, A.M., Raidl, G.R., Oberlechner, K.: Phylogenetic comparative methods.
J. Math. Model. Algorithms  8,  293–334 (2009).

[10]
Coelho, R., Gilmore, C.G., Lucey, B., Richmond, P., Hutzler, S.: The evolution
of interdependence in world equity markets—evidence from minimum spanning
trees. Physica A  376,  455–466 (2007).

[11]
Cornwell, W., Nakagawa, S.: Phylogenetic comparative methods. Curr. Biol.
27(9),  R333–R336 (2017). 0.1016/j.cub.2017.03.049

[12]
Edmonds, J.: Optimum branchings. J. Res. Natl. Bur. Stand. B  71(4),
233–240 (1967). 10.6028/jres.071b.032

[13]
Fischetti, M., Toth, P.: An efficient algorithm for the min-sum arborescence
problem on complete digraphs. INFORMS J. Comput.  5(4),  426–434
(1993). 10.1287/ijoc.5.4.426

[14]
Guralnik, V., Srivastava, J.: Event detection from time series data. In:
Fayyad, U.M., Chaudhuri, S., Madigan, D. (eds.) SIGKDD 1999. pp. 33–42.
ACM (1999). 10.1145/312129.312190

[15]
Liu, T., Coletti, P., Dignös, A., Gamper, J., Murgia, M.: Correlation graph
analytics for stock time series data. In: EDBT 2021 (2021),

[16]
Luo, J., Narasimhan, K., Barzilay, R.: Unsupervised learning of morphological
forests. Trans. Assoc. Comput. Linguistics  5,  353–364 (2017)

[17]
Moschitti, A., Pighin, D., Basili, R.: Semantic role labeling via tree kernel
joint inference. In: CoNLL 2006. pp. 61–68. ACL (2006)

[18]
Riesen, K.: Structural Pattern Recognition with Graph Edit Distance:
Approximation, Algorithms and Applications. Advances in Computer Vision and
Pattern Recognition, Springer (2016). 10.1007/978-3-319-27252-8

[19]
Riesen, K., Bunke, H.: IAM graph database repository for graph based pattern
recognition and machine learning. In: S+SSPR 2008. LNCS, vol. 5342, pp.
287–297. Springer, Berlin, Heidelberg (2008).

[20]
Sourek, G., Zelezny, F., Kuzelka, O.: Lossless compression of structured
convolutional models via lifting. CoRR  arXiv:2007.06567 [cs.LG]

[21]
Tarjan, R.E.: Finding optimum branchings. Networks  7(1),  25–35
(1977). 10.1002/net.3230070103

[22]
Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L.: Comparing stars: On
approximating graph edit distance. Proc. VLDB Endow.  2(1),  25–36
(2009). 10.14778/1687627.1687631

[23]
Zheng, W., Zou, L., Lian, X., Wang, D., Zhao, D.: Efficient graph similarity
search over large graph databases. IEEE Trans. Knowl. Data Eng.
27(4),  964–978 (2015). 10.1109/TKDE.2014.2349924