# A Neighborhood-preserving Graph Summarization

Abd Errahmane KIOUCHE  Univ Lyon, Université Lyon 1, LIRIS UMR CNRS 5205,
F-69621, Lyon, France.
E-mail<EMAIL_ADDRESS>LCSI, Ecole nationale Supérieure d’Informatique (ESI),Algeria.  Julien BASTE
Univ. Lille, CNRS, Centrale Lille, UMR 9189 - CRIStAL - Centre de Recherche en
Informatique Signal et Automatique de Lille, F-59000 Lille, France. E-mail:
<EMAIL_ADDRESS>Mohammed HADDAD  Univ Lyon, Université Lyon 1,
LIRIS UMR CNRS 5205, F-69621, Lyon, France.
E-mail<EMAIL_ADDRESS>Hamida SEBA  Univ Lyon, Université Lyon 1, LIRIS UMR CNRS 5205, F-69621, Lyon,
France.
E-mail<EMAIL_ADDRESS>
(date)

###### Abstract

We introduce in this paper a new summarization method for large graphs. Our
summarization approach retains only a user-specified proportion of the
neighbors of each node in the graph. Our main aim is to simplify large graphs
so that they can be analyzed and processed effectively while preserving as
many of the node neighborhood properties as possible. Since many graph
algorithms are based on the neighborhood information available for each node,
the idea is to produce a smaller graph which can be used to allow these
algorithms to handle large graphs and run faster while providing good
approximations. Moreover, our compression allows users to control the size of
the compressed graph by adjusting the amount of information loss that can be
tolerated. The experiments conducted on various real and synthetic graphs show
that our compression reduces considerably the size of the graphs. Moreover, we
conducted several experiments on the obtained summaries using various graph
algorithms and applications, such as node embedding, graph classification and
shortest path approximations. The obtained results show interesting trade-offs
between the algorithms runtime speed-up and the precision loss.

_K_ eywords Graph compression $\cdot$ Graph summarization $\cdot$ Algorithm
speed-up $\cdot$ Node embedding $\cdot$ Graph embedding

##  1 Introduction

Graphs are widely used in data modeling because of their ability to represent,
in a simple and intuitive way, complex relations and interactions between
objects: social interactions, protein-protein interactions, chemical molecule
bonds, transport networks, etc. We recall that a graph $G=(V,E)$ is a data
modeling tool consisting of a set $V$ of vertices, also called nodes, and a
set $E$ of edges that connect vertices. Vertices represent objects, while
edges represent relationships between them. Edges can be directed, and both
vertices and edges can have labels. As we are witnessing an explosion in the
number of data generated and processed by our applications, it becomes
important to deal efficiently with large graphs the processing of which
remains a challenging issue. In fact, the amount of generated data is
continuously increasing. Our basic and simple daily activities such as sending
emails, surfing websites, purchasing online, and interacting via social
networks, generate, on their own, a huge amount of data each day. For example,
in 2019 Facebook social network had more than 2.4 Billion monthly active users
with an average of 155 friendship links for each
user111https://www.omnicoreagency.com/facebook-statistics/ visited July.2020.
This large volume of data makes graph querying and analysis a very challenging
task. However, a viable solution seems to emerge from the possibilities
offered by graph summarizing.
Graph summarization, also known by graph compression or simplification, is a
solution that tackles scalability and performance issues when dealing with
massive graph data. Beyond the reduction of the volume of data which is the
main aim of compression, graph summarization looks for significant summaries
that can be used, in graph analysis, without decompression.

In fact, using graph summaries helps to speed-up graph algorithms so that they
can efficiently run on large graphs. Compression algorithms produce smaller
graphs or simpler graph representations, which can be maintained in main
memory and queried and analyzed in reasonable time.
Many graph algorithms, such as node embedding, node classification,
recommendations, shortest path approximation and graph comparison, are based
on the neighborhood information available for each node. Finding this
information may be difficult in practice as dealing with all the neighbors for
each node requires all the edges (links) of the graph to be processed, which
is time and space consuming. This motivated us to introduce a graph
compression that controls the size of the preserved neighborhood of vertices
in the computed summary. So, in this paper, we propose a new graph compression
which retains only a user-specified proportion of the neighbors of each node
to reduce the size of the graph while preserving neighborhood queries.

The main idea is to sparsify the graph by removing edges, while ensuring that
a predefined proportion of the neighbors of each node is included in the set
of $t$-hops neighbors of the node in the compressed graph ($t\geq 1$).

The main advantages of our neighborhood-preserving compression are:

  * •

Reduction in storage space of the graph:  our compression can decrease
drastically the number of edges in the graph, thus allowing the compressed
graph to be loaded into main memory. The size of the compressed graph can be
controlled by adjusting the proportion of the preserved neighborhood’s
information.

  * •

Fast Approximation of graph algorithms:  Many graph algorithms, such as
community detection, shortest path lengths and graph comparison, are mainly
based on the neighborhood information of the graph nodes. These algorithms
cannot efficiently run on large graphs since they require all the edges of the
original graph to be loaded in main memory. Since our compression produces a
smaller graph that maintains the principal neighborhood’s information, it can
be used to allow these algorithms to handle large graphs and run faster while
providing good approximations of the original results.

  * •

User-controlled trade-off between compression ratio and information loss: with
our compression, the user can control the size of the compressed graph by
adjusting the amount of information loss that can be tolerated. This is a very
useful property, since the amount of tolerated information loss differs
significantly from one application to another, and the desired size of the
compressed graph depends mainly on the available memory.

The remainder of this paper is organized as follows: Section 2 reviews related
works on graph compression methods and their applications. Section 3 formally
defines the problem of neighborhood-preserving graph compression and studies
its complexity. Then, Section 4 provides a description of the algorithms used
to implement this compression. Section 5 presents the results obtained through
the extensive experiments we undertook to evaluate the compression approach,
as well as the usefulness of the obtained summaries. Finally, Section 6
concludes the paper and points out some research perspectives.

##  2 Related Work

Graph compression is attracting increasing interest in various domains and
applications [1]. The aim of graph compression, considered here, is to compute
a graph summary that retains all or part of the original graph properties,
thus allowing use of the summary instead of the original graph in certain
applications. The obtained summary can be either a graph that is simpler or
smaller than the original graph, or any other data structure that is more
compact or is simpler to use than the original graph. Compression algorithms
can be classified in three main categories according to how they simplify the
input graph: (1) sampling, (2) sparsification, and (3) regularity encoding.
Sampling and sparsification based methods generate lossy graph compression and
their results are generally a graph. Regularity encoding based methods allow
having lossy, as well as loss-less, graph summaries, either as graphs or other
data structures:

  1. 1.

Graph sampling [2, 3] consists in using a fraction of the graph to make
inferences about the whole dataset. It is generally used for dynamic graphs
for which a sample at time $t$ is a likely representation of the graph. It is
also used with very large graphs, such as protein to protein interactions,
where dealing with the whole graph is too slow. Several graph sampling methods
are proposed in the literature. They generally start with a set of initial
vertices (and/or edges) which can be empty and expand the sample based on a
specific algorithm such as graph exploration and traversal algorithms. As
examples, Breadth-First sampling is used for social network analysis [4] and
graph mining [5]. In [6], the authors apply a traversal based sampling that
utilizes only the local information of nodes, combined with estimated values
of a set of properties, to guide the sampling process and extract tiny samples
that preserve the properties of the graph and closely approximate their
distributions in the original graph. Random walks based methods are also
largely applied in large-scale graph analysis [7, 8, 9]. Frontier sampling, an
edge sampling method using multidimensional random walkers, is used to
estimate the degree distributions and the global clustering coefficient in
[10]. In [11], the authors approximate betweenness centrality based on a
sampled set of shortest paths.

  2. 2.

Graph sparsification stands for the methods that compute a sparse subgraph of
the input graph, which preserves some of its properties such as cuts or
shortest paths [12]. Graph sparsification methods can also rely on sampling as
a tool to achieve sparsification. Given a social graph and a log of past
propagations, the authors of [13] prune the network to a prefixed extent,
while maximizing the likelihood of generating the propagation traces in the
log. A similar work is described in [14]. It tackles the problem of
simplifying a graph, while maintaining the connectivity recorded in a given
set of observed activity traces represented by a set of DAGs (or trees) with
specified roots. The problem consists in selecting a subset of arcs in the
graph so as to maximize the number of nodes reachable in all DAGs by the
corresponding DAG roots. This is a cover-maximization problem that the authors
bring to a problem of minimizing a submodular function under size constraints
and using an algorithm introduced in [15] to solve it.

  3. 3.

Regularity encoding based methods search for regularities within the graph
structure, i.e., particular patterns or just repetitive patterns, and then
encode these regularities so as to obtain a compact representation of the
graph. Several approaches are proposed in the literature and differ by both
the kind of considered regularities and how these regularities are encoded
within the computed summary. Some methods of this class consist in merging or
combining similar nodes, or subgraphs into super-nodes, and similar edges into
super-edges. Others work directly on the adjacency matrix of the graph using
for example $k2$-trees [16]. In [17], the authors propose a summarizing
approach that iteratively aggregates similar nodes, i.e., those that have the
greatest number of common neighbors. This aggregation is controlled by an
objective function that represents the cost of the compressed output graph and
is defined according to the principle of Minimum Description Length (MDL)
[18]. The graph is encoded with a summary and a set of correcting edges. These
corrections, applied to the summary, enable the initial graph to be
reconstructed. Identifying vertices with a similar neighborhood is a well-
studied topic known as modular decomposition of graphs [19, 20], which aims to
highlight groups of vertices that have the same neighbors outside the group.
These subsets of vertices are called modules. Modular decomposition is used in
[21] to compress a graph and compute its exact list of triangles using solely
the computed summary. The compression consists in considering each module as a
super-node. Several works such as [22] and [23] take advantage of the
regularities of the web graph structure, such as locality and similarity
properties, to compress its adjacency lists and reduce the number of bits
needed to encode a link. In [24, 25], the authors compress graphs using MDL on
a predefined vocabulary of substructures. In [26], graphs are compressed by
recursively detecting repeated substructures and representing them through
grammar rules. In [27], the authors use a clustering algorithm to partition
the original set of vertices into a number of clusters, which will be super-
nodes connected by super-edges to form a complete weighted graph. The super-
edge weights are the edge densities between vertices in the corresponding
super-nodes. The goal is to produce a summary that minimizes the
reconstruction error of the original graph. In [28], the authors merge into
super-nodes graph vertices that have common neighbors so that the obtained
compression ensures that the efficiency of a given task does not drop below a
user-specified threshold. In [29], the authors accelerate node grouping using
a divide and conquer approach that allows parallel node merging. In [30], the
authors use tensor decomposition to group nodes of an evolving graph according
to their connectivity patterns into super-nodes. In [31], the authors address
the problem of preserving node attributes while summarizing diffusion
networks. They propose a sub-quadratic parallelizable algorithm that finds the
best set of candidate nodes and merges them to construct a smaller network of
super-nodes that ensures similar diffusion properties to the original graph.
In [32], the authors use MDL to measure motif relevance based on motif
capacity to compress a graph. In [33], the authors incrementally compute a
summary of an evolving graph using frequent patterns and MDL principle,
combined with a set of operations (merge, split, etc.) on the patterns, in
order to provide changes that have occurred in the data since the previous
state.

In [34], the authors hybrid regularity encoding with sparsification by using
both node grouping and edge sparsification. This allows optimizing the size of
the obtained summary and the graph reconstruction error.

It is interesting to note that few works explore the usefulness of the
computed summaries beyond simple neighborhood or reachability queries.
Summaries obtained by graph sampling are used to estimate graph parameters and
are rarely used as input for graph applications. Most regularity-encoding
based methods do not investigate this issue at all. Graph sparsification
methods are generally designed for specific applications because it is
difficult to have lossy summaries that can be used in several kind of graph
applications. By targeting neighborhood information in our compression and
allowing to control the amount of information loss in the computed summary, we
aim to be able to use our summaries in a variety of graph applications. In
fact, several graph applications, such as node embedding, node classification,
recommendations, etc. are based on the availability of node neighborhood
information. In the remainder of the paper, we show that controlling the
amount of this information in the computed summary allows to reach good trade-
off between algorithm speed-up and precision loss when using the summary as
input instead of the original graph.

##  3 A Neighborhood-preserving graph compression

In this section, we explore a new graph sparsification method that aims to
control the amount of neighborhood information available for each node in the
graph. Our goal is to compute a graph summary that can be used instead of the
original graph in several applications.

###  3.1 Problem Statement

Let $t\geq 1$ be a positive integer. The main idea of neighborhood-preserving
graph compression is to sparsify the input graph by removing edges, while
ensuring that, for all $1\leq i\leq t$, a proportion $p(i)$ of the neighbors
of each node $v$ is included in the set of the $i$-hops neighbors of $v$ in
the compressed graph. We denote such compression by $(p,t)$-compression where:

  * •

$p:\mathbb{N}^{*}\to[0,1]$ is a monotonically increasing function, which
represents the proportion of each node’s original neighbors that must be
retrieved in its $i$-hops neighborhood in the compressed graph.

  * •

$t$ : is the minimum value for which $p$ reaches its maximal value i.e.,
$p(x)=p(t),\forall x\geq t$.

More formally, given an undirected graph $G=(V,E)$, where $V$ is the set of
vertices and $E$ is the set of edges, a $(p,t)$-compression of $G$ is defined
as follows:

###### Definition 1

Let $t$ be an integer and $p:\mathbb{N}\to[0,1]$ be a monotonically increasing
function satisfying $p(x)=p(t)$, $\forall x>t$. A _$(p,t)$ -compression_ of a
graph $G=(V,E)$ consists in finding a subgraph $G_{c}=(V_{c},E_{c})$ of $G$
such that $V_{c}=V$, $E_{c}\subseteq E$, and, for each $0<x\leq t$ and each
$v\in V$, $\left|N_{G}^{1}(v)\cap
N_{G_{c}}^{x}(v)\right|\geq\left|N_{G}^{1}(v)\right|p(x)$, where
$N_{G}^{x}(v)$ is the set of all $x$-hop neighbors of $v$ in $G$.

In other words, the compressed graph $G_{c}$ contains less edges than $G$ and
preserves a given amount (equal to $p(t)$) of the original neighbors for each
node. In fact, it is required that, for each $0<x\leq t$, a proportion $p(x)$
of the original neighbors must be accessible within a maximum of $x$ hops in
$G_{c}$ using a simple BFS traversal with depth $x$.

Figure 1 illustrates an example of our compression in which $50\%$ of the
original neighbors of each vertex are preserved in the compressed graph and
are reachable within maximum $2$ hops. The resulting compressed graph is
$30\%$ smaller than the original one.

(a) (a) Original graph

(b) (b) Compressed graph

Figure 1: $(p,2)$-compression of Zachary’s karate club network [35] where
$p(1)=0.5$ and $p(2)=1$ for each node.

With $(p,t)$-compression, function $p$ aims to control the loss of
neighborhood information at each neighborhood depth. It is obvious that the
smaller the preserved proportions, the better the compression ratio, and vice-
versa. As regards parameter t, the higher it is, the bigger the stretch factor
of the compressed graph, and vice-versa. The following corollary gives a lower
bound of the size of the compressed graph.

###### property 1

For any $(p,t)$-compression, the number of edges $|E_{c}|$ of the compressed
graph satisfies the following inequality: $|E|p(1)\leq|E_{c}|$

###### proof 1

According to the handshaking theorem, we have $\sum_{v\in V}deg(v)=2|E|$.
Since at least a proportion equal to $p(1)$ of the original neighbors of each
node must be kept in the compressed graph, we have $\sum_{v^{{}^{\prime}}\in
V_{c}}deg(v^{{}^{\prime}})\geq\sum_{v\in V}deg(v)p(1)=2|E|p(1)$, thus
$|E_{c}|\geq p(1)|E|$.

It is interesting to note that spanners [36] are special cases of
$(p,t)$-compression. Given a graph $G$, possibly edge-weighted, a _graph
spanner_ (or _spanner_ for short) is a subgraph $G^{\prime}$ which preserves
lengths of shortest paths in $G$ up to a multiplicative and/or additive error.
A $t$-spanner is a subgraph $G^{\prime}$ such that the distance between two
vertices in $G^{\prime}$ is at most $t$ times the distance between the same
two vertices in $G$. Thus, a $t$-spanner is a particular $(p,t)$-compression
that could be defined such that $p(i)=0$ for every positive integer $i<t$ and
$p(i)=1$ for $i\geq t$. In other words, a $t$-spanner is a $(p,t)$-compression
whose proportion function $p(x)$ is the Shifted Unit Step Function $u(x-t)$.
From a structural point of view, Figure 2 gives an illustration of a 2-spanner
of the Diamond graph (Figure 2.(b)) a 2-spanner of the Diamond graph which is
also a $(p,2)$-compression where $p(1)=\frac{1}{2}$ and $p(2)=1$ (Figure
2.(c)) and a $(p,2)$-compression where $p(1)=\frac{1}{3}$ and
$p(2)=\frac{2}{3}$ which is not a 2-spanner (Figure 2.(d)).

Figure 2: a Diamond graph and some of its compressions.

We can see in this figure that with a $2$-spanner, the left-most vertex is
only connected to $\frac{1}{3}$ of its original neighbors in the Diamond graph
(see Figure 2 (b)), while all the vertices keep at least half of their
original neighbors with a $(p,t)$-compression (see Figure 2 (c)).

###  3.2 NP-hardness and hardness of approximation

Peleg and Schäffer [36] showed that, given an unweighted graph $G$, and
integers $t\geq 2$, $m\geq 1$, determining if $G$ has a $t$-spanner containing
$m$ or fewer edges is NP-complete, even when $t$ is fixed to be $2$. The
reduction is from the edge dominating set problem on bipartite graphs. Since a
$t$-spanner is a particular $(p,t)$-compression of the graph $G$, we can
deduce the following result:

###### theorem 1

Finding the optimal (smallest) compressed graph satisfying the
$(p,t)$-compression constraints for $t\geq 2$ is an NP-Hard problem.

Another work giving us an alternative proof is Cai’s [37]. He showed that for
any fixed $t\geq 2$, the minimum $t$-spanner problem is NP-hard, and for
$t\geq 3$, the problem is NP-hard even when restricted to bipartite graphs.
The reduction is from the 3-SAT problem.

Dinitz et al. [38] show that for $t\leq 3$, and for all $\epsilon>0$, the
$t$-spanner problem cannot be approximated with a ratio better than
$2^{(log^{1-\epsilon}n)/k}$ unless $NP\subseteq BPTIME(2^{polylog(n)})$. This
implies the same inapproximability result for $(p,t)$-compression.

Concerning the best known approximation ratio, Elkin and Peleg [39] propose
approximation algorithms with a sublinear approximation ratio, and study
certain classes of graphs for which logarithmic approximation is feasible. It
is also shown in [40] that for $t=2$, the $t$-spanner problem admits an
$O(log(n))$ approximation. All these results strongly indicate that finding
better or even equivalent approximations for the $(p,t)$-compression problem
will be a hard task. In particular, finding a better result should begin with
finding better approximation than $O(log(n))$ for the $t$-spanner problem.

###  3.3 Integer linear programming formulation

In the following, we provide an integer linear programming formulation of our
problem.

Given an input graph $G=(V,E)$, we denote by $\mathcal{W}$ the set of all
paths in $G$. Given $e=\\{u,v\\}\in E$, we denote by $\mathcal{W}_{uv}$ the
set of all paths in $\mathcal{W}$ from $u$ to $v$. Note that the graph is
undirected and so $\mathcal{W}_{uv}$ also corresponds to the paths from $v$ to
$u$. Moreover, given $i\in\mathbb{N}$ we denote by $\mathcal{W}_{uv}^{i}$ the
set of all paths of $\mathcal{W}_{uv}$ of size at most $i$.

We then define the used variables:

  * •

$x_{e}$, for each $e\in E$, denotes whether $e\in E$ is selected ($x_{e}=1$)
or deleted ($x_{e}=0$).

  * •

$f_{w}$, for each $w\in\mathcal{W}$, is such that $f_{w}=0$ if at least one
edge $e$ of $w$ is such that $x_{e}=0$. Note that we can have a path
$w\in\mathcal{W}$ such that every edge $e$ of the path is such that $x_{e}=1$
but still have $f_{w}=0$.

We can now write the integer linear programming equation:

$\displaystyle\min\quad$ $\displaystyle\sum_{e\in E}x_{e}$ (1) s.t.
$\displaystyle f_{w}\leq x_{e}$ $\displaystyle\forall w\in\mathcal{W},e\in
E:~{}e\in w$ (2) $\displaystyle\sum_{w\in\mathcal{W}_{uv}}f_{w}\leq 1$
$\displaystyle\forall uv\in E,i\in\mathbb{N}$ (3) $\displaystyle\sum_{v\in
N(u)}\sum_{w\in\mathcal{W}_{uv}^{i}}f_{w}\geq p(i)|N(u)|$
$\displaystyle\forall u\in V,i\in\mathbb{N}$ (4) $\displaystyle
x_{e}\in\\{0,1\\}$ $\displaystyle e\in E$ (5) $\displaystyle
f_{w}\in\\{0,1\\}$ $\displaystyle w\in\mathcal{W}$ (6)

The variable $f_{w}$ can be seen as a flow from the source to the sink. (2)
ensures that if a path $w\in\mathcal{W}$ uses a removed edge $e$ (i.e., $e$ is
such that $x_{e}=0$), then the flow $f_{w}=0$. Using (3), we know that for
each $uv\in E$ there exists at most one path $w\in\mathcal{W}_{uv}$ such that
$f_{w}=1$. By intuition, we assume that we took the path
$w\in\mathcal{W}_{uv}$ of shortest length that is still available in the
remaining graph after removing the edges $e\in E$ such that $x_{e}=0$. Then
condition (4) ensures that the number of neighbors of a vertex $u$, which are
now at distance at most $i$ in the new graph, is at least the proportion given
by $p(i)$.

##  4 Algorithms and approximations

In this section, we present four algorithms for finding the
$(p,t)$-compression of an input graph $G$. Since finding the optimal
$(p,t)$-compression is NP-Hard and cannot be resolved in polynomial time, we
propose polynomial time approximations (sub-optimal algorithms). Algorithm 1
gives the basic implementation of our compression. It has the advantage of
simplicity and speed. Algorithm 1 takes as input a simple graph to compress
$G=(V,E)$, the compression parameters $p$ and $t$ and an order $E_{o}$ for
processing the edges of the input graph. $E_{o}$ is by default a random
ordering of the vertices. The idea is to process the edges of the initial
graph in the order $E_{o}$. The algorithm processes the edges of $G$
incrementally as follows: If an edge $e$ can be removed from $G$ without
violating the neighborhood preservation constraints, the algorithm does not
keep this edge in the summary. Otherwise, the algorithm keeps the edge in the
summary. Assume that the average branching factor ( Out/In degree) of the
graph is equal to $b$, then average time complexity of Algorithm 1 is
$O(|E|b^{t})$.

Data: $G=(V,E)$ a simple Graph,

$t$ an integer,

$p$ a monotonically increasing function $p:\mathbb{N}\to[0,1]$,

$E_{o}$ a possible order of the graph edges

Result: $G_{c}=(V_{c},E_{c})$ a compressed graph

1 $//$ Initialization Step ;

2 $G_{c}=(V_{c},E_{c})\leftarrow(V,\emptyset)$;

3 $G^{\prime}=(V^{\prime},E^{\prime})\leftarrow(V,\emptyset)$;

4 for  _$e=(u,v)\in E_{o}$_ do

5 $E^{\prime}\leftarrow E^{\prime}\cup\\{(u,v)\\}$;

6 $N_{G^{\prime}}^{1}(u)\leftarrow$ direct neighbors of node $u$ in
$G^{\prime}$;

7 $N_{G^{\prime}}^{1}(v)\leftarrow$ direct neighbors of node $v$ in
$G^{\prime}$;

8 insert $\leftarrow False$;

9 for  _$i=1$ to $t$_ do

10 $N_{Gc}^{i}(u)\leftarrow$ neighbors of node $u$ in $G_{c}$ within at most
$i$-hops;

11 $N_{Gc}^{i}(v)\leftarrow$ neighbors of node $v$ in graph $G_{c}$ within at
most $i$-hops;

12 if  _$|N_{Gc}^{i}(u)\cap N_{G^{\prime}}{1}(u)|
<p(i)|N_{G^{\prime}}^{1}(u)|$ or $|N_{Gc}^{i}(v)\cap
N_{G^{\prime}}^{1}(v)|<p(i)|N_{G^{\prime}}^{1}(v)|$_ then

13 insert $\leftarrow True$;

14 Break;

15

16 end if

17

18 end for

19 if  _insert_ then

20 $E_{c}\leftarrow E_{c}\cup\\{(u,v)\\}$;

21

22 end if

23

24 end for

Algorithm 1 Basic Algorithm

We note that different edge orderings lead to different compression
performances. Therefore, in order to improve the compression performance of
our algorithm, we propose in the three following subsections, 3 sub-optimal
algorithms which are based on the basic algorithm and try to find a near
optimal edge processing order.

###  4.1 Linear programming

We provide in Section 3.3, an optimal integer linear programming formulation
of $(p,t)$-compression. However, such a resolution is NP-hard to solve, so we
use the standard tricks consisting in relaxing the problem. For this, we keep
the same formulation but allow the values $x_{e}$, $e\in E$, and $f_{w}$,
$w\in\mathcal{W}$, to be any real values between $0$ and $1$. As we only have
to consider paths of a length at most $t$, we have a polynomial number of
variables (the degree of which depends on the fixed value $t$). The average
number of variables is of the order $O(|E|+|V|b^{t})$, where $b$ is the
average branching factor of the graph. This resolution provides a value for
each $x_{e}$, $e\in E$. The interpretation we give to this resolution is that
the higher the value of $x_{e}$, the more likely we want to keep $e$ in our
solution. In reverse, the lower the value of $x_{e}$, the more likely we want
to remove the edge $e$. Thus, we can use the values of $x_{e}$, $e\in E$, in
order to obtain an ordering for the edges and give this ordering to the basic
compression algorithm (see Algorithm 2). Since this linear problem is solvable
in polynomial time, the time complexity of Algorithm 2 is
$O(poly(|E|+|V|b^{t}))$.

Data: $G=(V,E)$ a simple Graph,

$t$ an integer,

$p$ a monotonically increasing function $p:\mathbb{N}\to[0,1]$

Result: $G_{c}=(V_{c},E_{c})$ a compressed graph

1 $//$ Computing the greedy edge order $E_{go}$ ;

2

3Solve the LP Relaxed problem to compute the edge scores $x_{e}$;

4

5$E_{go}\leftarrow$ sort edges E in descending order according to their score
$x_{e}$;

6

7$G_{c}\leftarrow$ Basic Algorithm ($G$,$t$,$p$,$E_{go}$);

Algorithm 2 LP Algorithm

###  4.2 Greedy order based on edge connectivity

Computing the LP-based order is time-consuming for large graphs according to
its time complexity. So, we propose in this subsection another edge ordering
that can be computed much faster than the LP order. The idea is to first
process the edges with a high centrality value. The centrality we consider
here is a relaxation of local edge betweenness defined in [41]. An edge with a
high edge betweenness centrality represents a bridge-like connector between
two parts of a network, the removal of which may affect the shortest paths
between them. The local edge betweenness of an edge $e$ is the number of
shortest paths running along $e$, the length of which is less than or equal to
some constant $t$. In our relaxation, we consider all simple paths of a length
at most $t$, i.e., not necessarily shortest paths. Thus, we compute for every
edge $e$ a centrality score $s(e)$ according to Equation 7.

In Equation 7, $\sigma_{t}(u,v|e)$ is the number of simple paths from $u$ to
$v$ of length $\leq t$ that pass through the edge $e$. Once all scores are
computed, we sort the edges in descending order according to their score
$s(e)$ and pass the obtained order as input to the basic algorithm (See
Algorithm 3). The average time complexity of Algorithm 3 is
$O((|E|+|V|b^{t})log(|E|+|V|b^{t}))$.

$s(e)=\sum_{(u,v)\in E}\sigma_{t}(u,v|e)\ \forall(u,v)\in E$ (7)

Data: $G=(V,E)$ a simple Graph,

$t$ an integer,

$p$ a monotonically increasing function $p:\mathbb{N}\to[0,1]$

1

Result: $G_{c}=(V_{c},E_{c})$ a compressed graph

2 $//$ Computing the greedy edge order $E_{go}$ ;

3

4for  _$e\in E$_ do

5 compute the score s(e) using Equation 7;

6

7 end for

8

9$E_{go}\leftarrow$ sort the edges of $G$ in descending order according to
their score $s(e)$;

10

11$G_{c}\leftarrow$ Basic Algorithm ($G$,$t$,$p$,$E_{go}$);

Algorithm 3 Greedy Algorithm based on edge connectivity (EC)

###  4.3 Sub-optimal order based on Simulated Annealing

In the previous two subsections, we have proposed two greedy edge orderings to
improve compression performance. However, the drawback of these two solutions
is that they are more time-consumingthan Algorithm 1 with a random edge
ordering, as we will reveal in the next section with the experimental
evaluation. Moreover, the computation time cannot be controlled by the user
since the computation of both orderings, i.e., the LP ordering and the greedy
ordering based on edge connectivity, cannot be suspended, and we need to go to
the end of the calculation. To overcome this problem, we propose a third
algorithm based on Simulated Annealing (SA) [42]. The advantage of this
solution is that the computation time can be controlled by the user by
adjusting the number of SA iterations. SA is an optimization scheme that
allows efficient search space exploration by accepting, with a given
probability, worst solutions to avoid a premature convergence [42]. SA for
$(p,t)$-compression is illustrated in Algorithm 4. The initial state of the
algorithm is a random order of edges. Then, in each iteration, the algorithm
makes a slight modification to edge order by performing two permutations of
two elements in the vector representing the order and recomputes the cost of
the new solution. If the new order is better, the algorithm keeps the order.
Otherwise, the algorithm keeps it with a probability which increases over the
iterations (see line 19 of Algorithm 4).

Data: $G=(V,E)$ a simple Graph,

$t$ an integer,

$p$ a monotonically increasing function $p:\mathbb{N}\to[0,1]$,

$N$ an integer (Number of iterations),

$T_{0}$ a double ( Initial temperature),

$\alpha$ a double ( decreasing factor)

Result: $G_{c}=(V_{c},E_{c})$ a compressed graph

1

2$S\leftarrow$ Random order of $E$;

3 $T\leftarrow T_{0}$;

4 $G_{t}(V_{t},E_{t})\leftarrow$ Basic Algorithm( $G$,$t$,$p$,$S$);

5 $C_{best}\leftarrow|E_{t}|$;

6 $C_{S}\leftarrow|E_{t}|$;

7 for  _$i=1$ to $N$_ do

8 $S_{2}\leftarrow$ Perturbing $S$ by swapping the order of two random edges;

9 $G_{t}(V_{t},E_{t})\leftarrow$ Basic Algorithm($G$,$t$,$p$,$S_{2}$);

10

11 if  _$|E_{t}| <C_{best}$_ then

12 $E_{best}\leftarrow S$;

13 $C_{best}\leftarrow|E_{t}|$;

14

15 end if

16 if  _$|E_{t}| <COST_{S}$_ then

17 $S\leftarrow S_{2}$;

18 $C_{S}\leftarrow|E_{t}|$;

19

20 end if

21 else

22 $r\leftarrow$ random number between $0$ and $1$;

23 if  _$\exp(\frac{C_{S}-|E_{t}|}{T}) >r$_ then

24 $S\leftarrow S_{2}$;

25 $COST_{S}\leftarrow|E_{t}|$;

26

27 end if

28

29 end if

30 $T\leftarrow\alpha*T$;

31 end for

32$G_{c}\leftarrow$ Basic Algorithm ($G$,$t$,$p$,$E_{best}$);

Algorithm 4 $(p,t)$ Compression based on simulated annealing

##  5 Experimental Analysis

In this section, we present an experimental analysis of our compression.
First, we evaluate the approximation algorithms provided to compute the
compression. Then, we provide an analysis of the sensitivity of the
compression to parameters $p$ and $t$. Finally, we evaluate its effectiveness
on several tasks such as graph properties estimation, node embedding and whole
graph embedding. All the experiments are carried out on an Intel core $i7$
processor with $64$ Gigabytes of memory.

###  5.1 Evaluation of approximation algorithms

In this subsection, we present a comparative experimental study of the four
proposed approximations of $(p,t)$-compression. For this, we launched the 4
approximations, i.e., the basic algorithm with random edge ordering (Algorithm
1), the LP approximation (Algorithm 2), the EC approximation (Algorithm 3),
and the SA approximation (Algorithm 4), on 3 families of synthetic graphs the
properties of which are given in Table 1.

Table 1: Characteristics of the synthetic graph families Name | number of graphs | $|V|$ | $|E|$
---|---|---|---
SYNTHETIC 1 | $30$ | $20$ | $60$
SYNTHETIC 2 | $30$ | $50$ | $350$
SYNTHETIC 3 | $30$ | $100$ | $1.4K$

We use the following compression parameters $t=2$ , $p(1)=0.0$ and $p(2)=0.5$.
For a reliable and accurate comparison, we carried out around thirty tests on
each family of graphs for each algorithm. The results of the comparison are
depicted in Table 2. Note that the user configuration of the SA is $T_{0}=10$,
$N=1000$ and $\alpha=0.99$. We notice that the two greedy algorithms LP and
EC, and the SA algorithm outperform the basic algorithm with a random ordering
of edges in terms of compression performance. The results clearly show that
the greedy (EC) and the SA algorithms are the best algorithms. The greedy (EC)
algorithm seems really interesting and offers the best trade-off between
compression performance and runtime. However, all the approximations are still
much slower than the basic algorithm with a random order of edges. Therefore,
we recommend using the basic algorithm for large graphs.

Table 2: Evaluation of the approximation algorithms Dataset | Basic | Greedy ( LP) | Greedy ( EC) | SA
---|---|---|---|---
Avg $|E_{c}|$ | time | Avg $|E_{c}|$ | time | Avg $|E_{c}|$ | time | Avg $|E_{c}|$ | time
SYNTHETIC 1 | 28 | 0.001 | 25.24 | 0.02 | 23.55 | 0.01 | 21.56 | 0.5
SYNTHETIC 2 | 121.63 | 0.008 | 113.26 | 2.5 | 105.66 | 0.02 | 105.9 | 5.2
SYNTHETIC 3 | 367.03 | 0.05 | 354.36 | 212 | 323.23 | 0.09 | 340.4 | 40

###  5.2 Impact of the compression parameters

In this series of experiments, we study the effect of parameters $p$ and $t$
on compression performance. To this end, we evaluate our compression using two
metrics: the compression runtime measured in seconds and the compression ratio
that represents the ratio of the number of deleted edges over the total number
of edges (see Equation 8).

$compression\;ratio=\frac{|E|-|E^{{}^{\prime}}|}{|E|}$ (8)

Note that higher is the compression ratio better is the storage space gain
ensured by the compression. For these experiments and all the following ones
we use real graph datasets. Table 3 gives the main characteristics of these
datasets.

Table 3: Characteristics of the real datasets used in our experiments Name | number of graphs | $|V|$ | $|E|$
---|---|---|---
BLOG-CATALOG | $1$ | $10.31K$ | $333.98K$
CA-ASTROPH | $1$ | $18.77K$ | $198.11K$
CA-HEPTH | $1$ | $9.8K$ | $25.9K$
COLLAB | $5000$ | $372.5K$ | $49.1M$
ENZYMES | $600$ | $19.5K$ | $74.6K$
FLICKR | $1$ | $80.51K$ | $5.89M$
PROTEINS | $1113$ | $43.5K$ | $162.1K$

Table 4 gives the compression ratio obtained by our compression on the CA-
AstroPh dataset, while varying the neighborhood preservation proportion $p$.
As expected, the compression ratio decreases as the preserved proportion of
neighborhood increases and vice-versa. Most of the values of the compression
ratio obtained with the various combinations of parameters are satisfactory.
In addition, we remark that the compression ratio range is wide (from $7\%$ to
$75\%$) which confirms the possibility of controlling effectively the trade-
off information loss/compression ratio using parameters $p$ and $t$.
Furthermore, we set $p(t)=1$ in all experiments, which means that the whole
initial neighborhood of each node can be retrieved in a neighborhood of radius
$r=t$ at maximum. This ensures that reachability queries are fully preserved
for all vertices. The choice of the best combination of parameters depends
essentially on the nature of the graph to be compressed and the user needs.
Particularly, for this example, the combinations $(0.5,1)$ and $(0.7,1)$ seem
really interesting.

Table 4: Compression ratio of the Ca-AstroPh dataset with different combinations of parameters $p$ and $t$ $t$ | $p(1)$ | $p(2)$ | $p(3)$ | compression ratio
---|---|---|---|---
$2$ | $0.2$ | $1.0$ | - | $58.13\%$
$0.5$ | $1.0$ | - | $45.82\%$
$0.7$ | $1.0$ | - | $26.39\%$
$0.9$ | $1.0$ | - | $7.43\%$
$3$ | $0.0$ | $0.2$ | $1.0$ | $75.00\%$
$0.2$ | $0.5$ | $1.0$ | $71.50\%$
$0.5$ | $0.7$ | $1.0$ | $46.73\%$
$0.7$ | $0.9$ | $1.0$ | $26.43\%$

The curves depicted in Figure 3 show the runtime and the compression ratio as
a function of the value of $t$ where $p(0<x<t)=0$ and $p(t)=1$. Note that this
combination of parameters gives a particular type of subgraphs called
$t$-spanners [36]. We notice that the compression ratio grows slowly and
starts to level off from $t=5$. However, the execution time increases
exponentially and rapidly. This is due to the complexity of the compression,
which is of the order $O(|E|b^{t})$ in the average case. Although spanners
give good compression ratios on this dataset ranging from $58\%$ up to $85\%$,
they do not allow good control of the trade-off between information loss and
compression ratio. Indeed, for this dataset, spanners give a control margin of
$(85\%-58\%=27\%)$ for a maximal stretch factor $t=6$, which represents a
significant loss of neighborhood information. However, with
$(p,t)$-compression we get a larger control margin of $(75\%-8\%=67\%)$ with a
maximal stretch factor $t=3$. This confirms once again the efficiency and
usefulness of our compression and its parameter $p$ when compared to spanners.

Figure 3: Compression performance of t-spanners on the Ca-AstroPh dataset

###  5.3 Applications of $(p,t)$compression

Several graph algorithms are based on the availability of neighborhood
information of nodes. Our first motivation is to be able to use these kinds of
algorithms directly on the compressed graphs. So, the purpose of these
experiments is to show the effectiveness of our compression in terms of
speeding-up for such graph algorithms, while handling large graphs and
providing good approximations of the original results. For this, and for all
the following experiments, we use the datasets presented in Table 3 and
compute two new metrics in addition to the compression ratio namely:

  * •

Speed-up factor: the ratio between the algorithm run-time on the original
graph and its run-time on the compressed graph. he higher the speed-up factor,
the faster the graph algorithm on the compressed graph.

  * •

Performance loss: the difference between the performance metric value on the
original graph and the performance metric value on the compressed graph. For
example, for a classification task the performance loss is the difference
between the accuracy on the original graph and the accuracy on the compressed
graph.The smaller the performance loss, the better the approximation of the
graph properties on the compressed graph.

####  5.3.1 Shortest paths approximation

The most suitable application for our compression is the approximation of the
shortest paths between all nodes, since every $(p,t)$-compression where
$p(t)=1.0$ preserves all the connectivity properties between the nodes of the
graph, by stretching all the connecting paths by a factor equal to $t$ in the
worst case. In this experimental phase, we compressed three unweighted
undirected graphs with the following combination of parameters $t=2$,
$p(1)=0.5$, and $p(2)=1.0$. Then, we applied the BFS (Breadth First Search)
algorithm to compute all shortest paths between all nodes. Table 5 summarizes
the obtained compression ratio and the shortest path speed-up obtained on
three datasets: CA-ASTROPH, CA-HEPTH and BLOG-CATALOG. We notice that our
compression saves a considerable amount of storage space (compression ratio
$>31\%$) while approximating faster (speed-up ranges from $1.06$ to $1.49$)
the shortest path lengths for the 3 chosen datasets. Indeed, reducing the
number of edges of the graphs reduces the run-time of the shortest paths
computed by the BFS algorithm, which is of complexity $O(|V|(|E|+|V|))$. This
speed-up is more noticeable for denser graphs.

Table 5: Speeding-up all shortest paths computation Dataset | Space gain | Speed-up
---|---|---
CA-ASTROPH | $45.82\%$ | $1.496$
BLOG-CATALOG | $46.52\%$ | $1.323$
CA-HEPTH | $31.08\%$ | $1.065$

Figure 4 shows the distribution of the shortest path lengths in the original
and compressed graphs for the three datasets. We note that the two curves have
almost the same pace. This shows that our compression preserves the
distribution of the lengths of the shortest paths in the 3 datasets. However,
the curves of the compressed graphs are slightly stretched and shifted from
the original curves. This is due to the stretching of the paths as a result of
compression. This stretch is not really considerable because of the
preservation of $50\%$ of the direct neighbors of each vertex in the graph. In
addition, unlike $t$-spanners, $(p,t)$-compression compression controls the
shift between the two curves by adjusting the value of parameter $p$.

(a) (a) Ca-AstroPh dataset

(b) (b) Blog-Catalog dataset

(c) (c) Ca-HepTh dataset

Figure 4: Distribution of shortest path lengths of the original and compressed
graphs.

####  5.3.2 Whole graph embedding speed-up

Many whole graph embedding methods are based on the local neighborhood
information of the nodes. These methods learn graph representations by
exploring the node neighborhood and extracting some features such as walks,
shortest paths, and local substructures. Since our compression preserves the
local neighborhood within radius $t$, it is thus worth running these
algorithms on compressed graphs to see if our compression speeds up these
algorithms and to evaluate the performance loss. For this, we compressed three
different datasets COLLAB, ENZYMES, and PROTEINS where $t=3$, $p(x<t)=0.0$ and
$p(t)=1.0$ and we run three graph embedding algorithms on the compressed
graphs: shortest path delta kernel [43], graphlet kernel [44] and Graph2vec
[45]. We evaluated the performance of these algorithms on both the original
and the compressed graphs in graph classification tasks as follows: we train
an SVM classifier with $90\%$ of the graphs chosen randomly and then compute
classification accuracy on the test set composed of the remaining $10\%$
graphs. For Graph2vec, we used the best configuration of parameters given in
the original paper [45].

Table 6: Graph kernel performance on the compressed graphs
cr: compression ratio. pl: performance loss
Dataset | Kernel | cr | Speed-up | Original accuracy | Accuracy | pl
---|---|---|---|---|---|---
COLLAB | SP delta | $79\%$ | $4.52$ | $65.78\%$ | $64.78\%$ | $1.00\%$
3-Graphlet | $9.39$ | $64.62\%$ | $53.80\%$ | $10.82\%$
4-Graphlet | $\textgreater 10$ | (out of time) | $53.68\%$ | -
PROTEINS | SP delta | $40\%$ | $1.123$ | $71.91\%$ | $72.18\%$ | $0.0\%$
3-Graphlet | $1.49$ | $71.60\%$ | $71.18\%$ | $0.42\%$
4-Graphlet | $2.02$ | $71.58\%$ | $71.35\%$ | $0.23\%$
ENZYMES | SP delta | $39\%$ | $1.06$ | $29.31\%$ | $24.71\%$ | $4.60\%$
3-Graphlet | $1.6$ | $24.58\%$ | $19.58\%$ | $5.00\%$
4-Graphlet | $1.87$ | $30.03\%$ | $19.70\%$ | $10.33\%$

Table 6 shows the performance of the graph kernels on the compressed graphs.
We notice that the three kernels run faster on compressed graphs in all
experiments. This Kernel computation speed-up is more noticeable on denser
datasets, especially for the graphlet kernels. Indeed, we notice that the
4-Graphlet kernel exceeded the time limit (10 hours) on COLLAB’s original
graphs, while it takes less than one hour on the compressed dataset. Regarding
performance loss, we notice a small loss in values for the shortest path
kernels ranging from $0.0$ to $4.6\%$. However, the loss is more noticeable
for the graphlet kernel but it remains acceptable ($<11.0\%$ in all
experiments). This is due to the fact that our $(p,t)$-compression does not
preserve all graphlets, for example only $6$ graphlets are preserved among the
$11$ graphlets of size=4. Despite this, kernel computation speed-up is very
satisfactory.

Table 7: Graph2vec performance on compressed datasets Dataset | Compression ratio | Speed-up | Performance Loss
---|---|---|---
COLLAB | $79\%$ | $2.54$ | $0.00\%$
PROTEINS | $40\%$ | $1.004$ | $2.93\%$
ENZYMES | $39\%$ | $1.27$ | $5.99\%$

Table 7 shows the performance of Graph2vec on the compressed datasets.
Globally, the algorithm runs faster on the compressed graphs, and the speed-up
factor is bigger on denser datasets. Performance loss is acceptable on the
ENZYMES dataset ($<6\%$) and very satisfactory on the first two datasets
($<3.0\%$). This is due to the fact that Graph2vec considers graphs as sets of
Weisfeiler-Lehman relabeled subgraphs [46] that encompass higher order
neighborhoods of graph nodes. These subgraphs are highly preserved by our
compression. Figure 5 depicts the distribution of the classification accuracy
obtained using Graph2vec on the 3 datasets (compressed and original) by
running 10 experiments on each dataset and for each type of graph (compressed
or original). We notice that the performances on compressed graphs and
original graphs are nearly equivalent. The performance on original graphs is
slightly better for the ENZYMES and PROTEINS datasets. Moreover, the loss of
performance due to the compression is not great.

Figure 5: Graph2vec performance boxplot

####  5.3.3 Node embedding speed-up

In this series of experiments, we use two main algorithms, i.e., Node2vec [47]
and DeepWalk [48], to learn node representations for both compressed and
original graphs. We use BLOG-CATALOG and FLICKR datsets. The compressed graphs
are obtained using $(p,t)$-compression where $t=2$, $p(1)=0.5$ and $p(2)=1.0$.
The compression ratios are $\geq 45\%$ for the two datasets. Node2vec and
DeepWalk are run using the best parameter combinations given in the original
papers. To evaluate their performance on both compressed and original graphs,
we run multiple multilabel classification tasks on the obtained
representations. To this end, a sample $P_{tr}=\\{0.1,...,0.9\\}$ of the
labeled nodes is used as training data. The rest of the nodes are used for
testing. This process is repeated $10$ times, and we use Macro-F1 and Micro-F1
as performance metrics.

Table 8 shows the performance of Node2vec and Deepwalk on the compressed
graphs where $P_{tr}=0.5$. We notice that Deepwalk runs at the same speed on
both the original and compressed graphs. This is because the time complexity
of Deepwalk depends only on the number of nodes in the graph, which remains
the same after our compression. However, Node2vec runs much faster on the
compressed graphs than on the original graphs. This is justified by the fact
that Node2vec’s time complexity depends on the square of the branching factor
$b$ of the graph [49], which is implicitly related to the number of edges in
the graph. The Micro-F1 and Macro-F1 scores obtained on the compressed graphs
are nearly equivalent to the original scores. The performance loss rates are
low ($\leq 4\%$) for both methods, and insignificant on the FLICKR dataset
($\leq 1.2\%$).

For more fine-grained results, we also compared the performance of the two
algorithms on compressed and original graphs while varying the size of the
training sample $P_{tr}$ from $0.1$ to $0.9$. We summarize the results
graphically for the Micro-F1 and Macro-F1 scores for both methods, i.e.,
Node2vec and Deepwalk, in Figures 6 and 7 respectively. Here we make the same
observations: the performances of the two algorithms on compressed graphs are
almost similar to their performances on the original graphs for all training
rates. With the BLOG-CATALOG dataset, the performance drops by $4\%$ on
compressed graphs in the worst case. However the performance curves on
original and compressed graphs are almost identical in the FLICKR dataset.

Table 8: Performance of node embedding algorithms on compressed datasets Dataset | Method | Space gain | Speed-up | Loss ( Micro F1) | Loss ( Macro F1)
---|---|---|---|---|---
BlogCatalog | DeepWalk | $46.52\%$ | $0.99$ | $3.6\%$ | $3.4\%$
Node2vec | $2.87$ | $3.4\%$ | $2.5\%$
Flickr | DeepWalk | $45.59\%$ | $0.99$ | $0.9\%$ | $1.2\%$
Node2vec | $5.32$ | $0.3\%$ | $0.0\%$
Figure 6: Performance of Node2vec on compressed graphs  Figure 7: Performance
of DeepWalk on compressed graphs

##  6 Conclusion and future work

In this paper, we presented a graph summarization approach designed to control
the amount of neighborhood information preserved in the computed summary. This
approach relies on two parameters: a function $p$ that gives the proportion of
each node’s original neighbors to be preserved in its $i$-hops neighborhood in
the compressed graph, and a threshold $t$ for which $p$ reaches its maximal
value.

We presented algorithms to compute this compression with the minimum cost, and
showed their effectiveness in compressing input graphs through experimental
evaluation on multiple real life as well as synthetic graph datasets.

We also showed that the summaries computed by the proposed approach can be
used without any decompression as input to multiple graph applications, such
as node embedding, graph classification, and shortest path approximations. The
results show interesting trade-offs between algorithm runtime speed-up and
precision loss.

As for future work, we consider a more thorough analysis of
$(p,t)$-compression impact on walks based graph learning algorithms such as
Node2vec and DeepWalk. In fact, we observed some situations where learning
accuracy increased when the graph was compressed. This was a quite unexpected
observation. While we guess that walks are biased in the right direction by
removing edges, characterizing such edges remains an open question. Another
important open question is to find an efficient method to order graph edges.
This would allow us to significantly improve the time complexity of the
approach. In addition, we aim to design an incremental version of our
compression to deal with dynamic graphs or graph streams.
We note also that our approach can be used on both directed and undirected
graph. However, our compression do not consider the labels of the edges. To
compress edge-labelled graphs, a new model need to be defined so as to take
into account these labels for example when defining the edge ordering.

#####  Acknowledgement:
This work is funded by ANR under grant ANR-20-CE23-0002.

## References

  * [1] Y. Liu, T. Safavi, A. Dighe, and D. Koutra.  Graph summarization methods and applications: A survey.  ACM Comput. Surv., 51(3):62:1–62:34, June 2018.
  * [2] A.R. Bloemena.  Sampling from a Graph.  Mathematical Centre tracts. Mathematisch Centrum, 1976.
  * [3] L.-C. Zhang and M. Patone.  Graph sampling.  METRON, 75(3):277–299, Dec 2017.
  * [4] Yong-Yeol Ahn, Seungyeop Han, Haewoon Kwak, Sue Moon, and Hawoong Jeong.  Analysis of topological characteristics of huge online social networking services.  In Proceedings of the 16th International Conference on World Wide Web, WWW ’07, page 835–844, New York, NY, USA, 2007. Association for Computing Machinery.
  * [5] Irma Ravkic, Martin Žnidaršič, Jan Ramon, and Jesse Davis.  Graph sampling with applications to estimating the number of pattern embeddings and the parameters of a statistical relational model.  Data Mining and Knowledge Discovery, 32(4):913–948, July 2018.
  * [6] Muhammad Irfan Yousuf and Suhyun Kim.  Guided sampling for large graphs.  Data Mining and Knowledge Discovery, 34(4):905–948, July 2020.
  * [7] Azade Nazi, Zhuojie Zhou, Saravanan Thirumuruganathan, Nan Zhang, and Gautam Das.  Walk, not wait: Faster sampling over online social networks.  Proc. VLDB Endow., 8(6):678–689, February 2015.
  * [8] Y. Li, Z. Wu, S. Lin, H. Xie, M. Lv, Y. Xu, and J. C. S. Lui.  Walking with perception: Efficient random walk sampling via common neighbor awareness.  In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 962–973, 2019.
  * [9] Junzhou Zhao, Pinghui Wang, John C. S. Lui, Don Towsley, and Xiaohong Guan.  Sampling online social networks by random walk with indirect jumps.  Data Mining and Knowledge Discovery, 33(1):24–57, January 2019\.
  * [10] Bruno Ribeiro and Don Towsley.  Estimating and sampling graphs with multidimensional random walks.  In Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement, IMC ’10, page 390–403, New York, NY, USA, 2010. Association for Computing Machinery.
  * [11] Matteo Riondato and Evgenios M. Kornaropoulos.  Fast approximation of betweenness centrality through sampling.  Data Mining and Knowledge Discovery, 30(2):438–475, March 2016\.
  * [12] L. Paul Chew.  There are planar graphs almost as good as the complete graph.  Journal of Computer and System Sciences, 39(2):205 – 219, 1989\.
  * [13] Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, and Antti Ukkonen.  Sparsification of influence networks.  In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’11, page 529–537, New York, NY, USA, 2011. Association for Computing Machinery.
  * [14] Francesco Bonchi, Gianmarco De Francisci Morales, Aristides Gionis, and Antti Ukkonen.  Activity preserving graph simplification.  Data Mining and Knowledge Discovery, 27(3):321–343, November 2013\.
  * [15] Kiyohito Nagano, Yoshinobu Kawahara, and Kazuyuki Aihara.  Size-constrained submodular minimization through minimum norm base.  In Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Proceedings of the 28th International Conference on Machine Learning, ICML 2011, pages 977–984, 2011.  28th International Conference on Machine Learning, ICML 2011 ; Conference date: 28-06-2011 Through 02-07-2011.
  * [16] Nieves R. Brisaboa, Susana Ladra, and Gonzalo Navarro.  k2-trees for compact web graph representation.  In Jussi Karlgren, Jorma Tarhio, and Heikki Hyyrö, editors, String Processing and Information Retrieval, pages 18–30, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
  * [17] Saket Navlakha, Rajeev Rastogi, and Nisheeth Shrivastava.  Graph summarization with bounded error.  In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD ’08, page 419–432, New York, NY, USA, 2008. Association for Computing Machinery.
  * [18] J. Rissanen.  Modeling by shortest data description.  Automatica, 14(5):465 – 471, 1978.
  * [19] T. Gallai.  Transitiv orientierbare graphen.  Acta Mathematica Hungarica, 18:25–66, 1967.
  * [20] Michel Habib and Christophe Paul.  A survey of the algorithmic aspects of modular decomposition.  Computer Science Review, 4(1):41 – 59, 2010.
  * [21] Sofiane Lagraa and Hamida Seba.  An efficient exact algorithm for triangle listing in large graphs.  Data Mining and Knowledge Discovery, 30(5):1350–1369, September 2016.
  * [22] T. Suel and Jun Yuan.  Compressing the graph structure of the web.  In Proceedings DCC 2001. Data Compression Conference, pages 213–222, 2001.
  * [23] P. Boldi and S. Vigna.  The webgraph framework i: Compression techniques.  In Proceedings of the 13th International Conference on World Wide Web, WWW ’04, page 595–602, New York, NY, USA, 2004. Association for Computing Machinery.
  * [24] Danai Koutra, U Kang, Jilles Vreeken, and Christos Faloutsos.  Summarizing and understanding large graphs.  Stat. Anal. Data Min., 8(3):183–202, June 2015.
  * [25] Neil Shah, Danai Koutra, Tianmin Zou, Brian Gallagher, and Christos Faloutsos.  Timecrunch: Interpretable dynamic graph summarization.  KDD ’15, page 1055–1064, New York, NY, USA, 2015. Association for Computing Machinery.
  * [26] Sebastian Maneth and Fabian Peternek.  Grammar-based graph compression.  Information Systems, 76:19 – 45, 2018.
  * [27] Matteo Riondato, David García-Soriano, and Francesco Bonchi.  Graph summarization with quality guarantees.  Data Mining and Knowledge Discovery, 31(2):314–349, March 2017\.
  * [28] K. Ashwin Kumar and Petros Efstathopoulos.  Utility-driven graph summarization.  Proc. VLDB Endow., 12(4):335–347, December 2018.
  * [29] Kijung Shin, Amol Ghoting, Myunghwan Kim, and Hema Raghavan.  Sweg: Lossless and lossy summarization of web-scale graphs.  In The World Wide Web Conference, WWW ’19, page 1679–1690, New York, NY, USA, 2019. Association for Computing Machinery.
  * [30] Sofia Fernandes, Hadi Fanaee-T, and João Gama.  Dynamic graph summarization: a tensor decomposition approach.  Data Mining and Knowledge Discovery, 32(5):1397–1420, September 2018.
  * [31] Sorour E. Amiri, Liangzhe Chen, and B. Aditya Prakash.  Efficiently summarizing attributed diffusion networks.  Data Mining and Knowledge Discovery, 32(5):1251–1274, September 2018.
  * [32] Peter Bloem and Steven de Rooij.  Large-scale network motif analysis using compression.  Data Mining and Knowledge Discovery, 34(5):1421–1453, September 2020.
  * [33] Sarang Kapoor, Dhish Kumar Saxena, and Matthijs van Leeuwen.  Online summarization of dynamic graphs using subjective interestingness for sequential data.  Data Mining and Knowledge Discovery, September 2020.
  * [34] Kyuhan Lee, Hyeonsoo Jo, Jihoon Ko, Sungsu Lim, and Kijung Shin.  Ssumm: Sparse summarization of massive graphs.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’20, page 144–154, New York, NY, USA, 2020. Association for Computing Machinery.
  * [35] Wayne W Zachary.  An information flow model for conflict and fission in small groups.  Journal of anthropological research, 33(4):452–473, 1977.
  * [36] David Peleg and Alejandro A. Schäffer.  Graph spanners.  Journal of Graph Theory, 13(1):99–116, 1989.
  * [37] Leizhen Cai.  Np-completeness of minimum spanner problems.  Discrete Applied Mathematics, 48(2):187 – 194, 1994.
  * [38] Michael Dinitz, Guy Kortsarz, and Ran Raz.  Label cover instances with large girth and the hardness of approximating basic k-spanner.  ACM Trans. Algorithms, 12(2), December 2016.
  * [39] Michael Elkin and David Peleg.  Approximating k-spanner problems for k>2\.  Theoretical Computer Science, 337(1):249 – 277, 2005.
  * [40] G. Kortsarz and D. Peleg.  Generating sparse 2-spanners.  Journal of Algorithms, 17(2):222 – 236, 1994.
  * [41] Steve Gregory.  A fast algorithm to find overlapping communities in networks.  In Walter Daelemans, Bart Goethals, and Katharina Morik, editors, Machine Learning and Knowledge Discovery in Databases, pages 408–423, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
  * [42] Peter JM Van Laarhoven and Emile HL Aarts.  Simulated annealing.  In Simulated annealing: Theory and applications, pages 7–15. Springer, 1987.
  * [43] Karsten M Borgwardt and Hans-Peter Kriegel.  Shortest-path kernels on graphs.  In Fifth IEEE international conference on data mining (ICDM’05), pages 8–pp. IEEE, 2005.
  * [44] Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt.  Efficient graphlet kernels for large graph comparison.  In Artificial Intelligence and Statistics, pages 488–495, 2009\.
  * [45] Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal.  graph2vec: Learning distributed representations of graphs.  arXiv preprint arXiv:1707.05005, 2017.
  * [46] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt.  Weisfeiler-lehman graph kernels.  Journal of Machine Learning Research, 12(9), 2011.
  * [47] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864, 2016.
  * [48] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710, 2014.
  * [49] Tiago Pimentel, Adriano Veloso, and Nivio Ziviani.  Fast node embeddings: Learning ego-centric representations.  2018\.


# Digital Low-Level RF control system for Accumulator Ring at Advanced Light
Source Upgrade Project

Qiang Du1, Shreeharshini Murthy, Michael Betz, Kevin Bender, Wayne Lewis, Najm
Us Saqib,
Sergio Paiagua, Lawrence Doolittle, Carlos Serrano, Benjamin Flugstad, Kenneth
Baptiste  Lawrence Berkeley National Laboratory
1 Cyclotron Rd, Berkeley, CA, 94720 USA
Email<EMAIL_ADDRESS>
###### Abstract

Currently ALS is undergoing an upgrade to ALS-U to produce 100 times brighter
soft X-ray light. The LLRF system for Accumulator Ring (AR) is composed of two
identical LLRF stations, for driving RF amplifiers. The closed loop RF
amplitude and phase stability is measured as $<0.1\%$ and $<0.1^{\circ}$
respectively, using the non-IQ digital down conversion together with analog
up/down conversion, under a system-on-chip architecture. Realtime interlock
system is implemented with $<2\mu$s latency, for machine protection against
arc flash and unexpected RF power. Control interfaces are developed to enable
PLC-FPGA-EPICS communication to support operation, timing, cavity tuning, and
interlock systems. The LLRF system handles alignment of buckets to swap beams
between AR and Storage Ring by synchronous phase loop ramping between the two
cavities. The system also includes an optimization routine to characterize the
loop dynamics and determine optimal operating point using a built-in network
analyzer feature. A cavity emulator of 31 kHz bandwidth is integrated with the
LLRF system to validate the performance of the overall system being developed.

##  I Introduction

The Advanced Light Source (ALS) at Lawrence Berkeley National Laboratory is a
U.S. Department of Energy’s synchrotron light source user facility that is
operational since 1993. With circumference of 196.8 m, the ALS Storage Ring
(SR) keeps electron beam current of 500 mA at 1.9 GeV under multi–bunch mode
user operation to deliver synchrotron X-rays to surrounding 40 experimental
end stations. [1]

There is an ongoing ALS upgrade project (ALS-U), scheduled to upgrade towards
2 orders of magnitude increase in brightness and flux of 1keV soft X-rays at
diffraction limit. The ALS-U project involves a new 2.0 GeV Storage Ring (SR)
in existing tunnel optimized for low emittance, and add a new 2.0 GeV
Accumulator Ring (AR) for full energy swap-out injection and bunch train
recovery, as shown in Fig. 1. The AR is a triple-bend-achromat (TBA) lattice,
very similar to the current ALS SR lattice. The RF system requirements for the
TBA lattice can be found in Table I. Two normal conducting RF cavities have
been selected for AR. Each RF cavity is driven by an identical chain from a
high power solid-state amplifier (SSA) and low-level RF (LLRF) control system,
together with personnel safety interlocks, equipment protection interlocks,
etc.

Figure 1: ALS Upgrade with both Accumulator and Storage Rings | ALS SR | ALS-U SR | ALS-U AR |
---|---|---|---|---
Cavity RF Frequency | 499.64 | 500.394 | 500.394 | MHz
Number of Cavities | 2 | 2 | 2 |
$\frac{R}{Q}$ (ea) | 4.9 | 4.9 | 3.4–3.5 | M$\Omega$
Cavity voltage | 671 | 300 | 500 | kV
$\beta$ | 2.9 | 10.6 | 1.18 |
Energy loss per trun | 329 | 347 | 270 | keV
BM Beam Power | 141 | 125 | 13.3 | kW
ID Beam Power | 42 | 35 |  | kW
3HC Beam Power | 7.3 | 13.8 |  | kW
Parasitic Beam Power | 2.9 (est.) | 2.6 (est.) | 0.2 | kW
Total Beam Power | 192.9 | 176.4 | 13.5 | kW
Cavity Power(no beam) | 46 | 9.2 | 36.0 | kW
Cavity Power(beam) | 142.5 | 97.4 | 42.7 | kW
High Power Amplifier | 294.0 | 197.5 | 60 | kW
TABLE I: ALS and ALS-U AR and SR RF parameters

##  II Hardware Design

The AR LLRF system consists of two identical stations, each controlling one
SSA and RF cavity, but sharing communication interface with a central
interlock PLC and both stations are coordinated By common timing events for
synchronous operations. Each LLRF station consists of an analog frontend
chassis and a digital chassis. The analog chassis receives ALS-U master
oscillator and generates local oscillator (LO) signal, and provides frequency
conversions including 6 channels of down-conversion and 2 channels of up-
conversion between RF and IF frequencies, following the non-IQ down-conversion
configuration:

$\displaystyle f_{\text{MO}}$ $\displaystyle=500.39\,\text{MHz}$
$\displaystyle f_{\text{LO}}$
$\displaystyle=\frac{11}{12}f_{\text{MO}}=458.69\,\text{MHz}$ $\displaystyle
f_{\text{IF}}$ $\displaystyle=\frac{1}{12}f_{\text{MO}}=41.69\,\text{MHz}$
$\displaystyle f_{\text{Sample}}$
$\displaystyle=\frac{1}{4}f_{\text{LO}}=114.67\,\text{MHz}$
$\displaystyle\frac{f_{\text{IF}}}{f_{\text{Sample}}}$
$\displaystyle=\frac{4}{11}=\theta\simeq 130.9^{\circ}$

The analog frontend chassis assembly is shown as in Fig. 2. The up-down-
conversion PCB boards are existing designs from Jefferson Lab with 500 MHz
center frequency, featured with high channel isolation, programmable TX
attenuation, RF switch and various diagnostics and monitoring points. The LO
generation PCB board uses single side ban modulation to generate four
$f_{\text{LO}}$ signals that feed into up-down-conversion boards, and the
digital chassis for sampling clock.

Figure 2: Analog frontend chassis: 6 down + 2 up conversion, LO generation

There is a centralized power supply controller board that is responsible for
configuration of LO board, continuous monitoring and interlocking of the LO
level, temperature, voltage and current consumptions, and provide an
interactive local user interface through an OLED display. Remote control is
available through an RS485 port with Modbus RTU protocol.

The digital chassis consists a Marble-Mini [2] FPGA carrier board and a Zest
digitizer board [3], as shown in Fig. 3. Both boards are available through
CERN Open Hardware License (OHL v1.2). The $f_{\text{LO}}$ signal is feed into
the clock input of Zest board for generation and distribution of
$f_{\text{Sample}}$ to two 16-bit, four channel ADC with sampling rate up to
125 MHz (AD9653), and one 16-bit, dual channel DAC with sampling rate up to
250 MHz (AD9781). The Zest board is used in LCLS-II LLRF project with superior
low noise and channel crosstalk performances. The Marble family FPGA carrier
boards are used in many other projects in ALS and PIP-II LLRF control.

Figure 3: Digital chassis: Marble-Mini FPGA carrier and Zest digitizer

For ALS-U AR LLRF control, the 6 down-converted IF signals are fed from the
analog frontend chassis for operation, including cavity probe, cavity forward
and reverse, and circulator load forward and reverse signals. The 2 additional
ADCs in Zest board are used to directly sampling the test load signals for
high power RF system commissioning.

##  III Firmware design

Figure 4: Digital Chassis Firmware architecture

Fig. 4 shows the digital chassis firmware architecture, which is built on top
of BSD licensed open source LLRF library Bedrock [4]. We use an open source,
size optimized RISC-V CPU PicoRV32 [5] to handle system configuration, boot-
time self checking, continuous status monitoring, and remote interfacing with
PLC systems via the RS485 / Modbus RTU port which is similar to the analog
frontend chassis. The footprint of the firmware is only 24 kB of RAM and
750–2000 LUTs. At the same time, we use BerkeleyLab’s realtime Ethernet fabric
infrastructure packet badger to provide a UDP communication as another local
bus master, which has the priority to directly access DSP registers for
realtime EPICS applications, including configurable waveforms for any RF
signals.

The feedback DSP core is implemented as shown in Fig. 5. A classical non-IQ
digital down conversion algorithm [6] is implemented to digitally down-convert
the IF signals and reconstruct their IQ values using a local direct digital
synthesizer (DDS): Given
$\frac{f_{\text{IF}}}{f_{\text{Sample}}}=\frac{4}{11}=\theta\simeq
130.9^{\circ}$,

$\displaystyle\begin{pmatrix}y_{n}\\\ y_{n+1}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\cos(n\theta)&\sin(n\theta)\\\
\cos((n+1)\theta)&\sin((n+1)\theta)\end{pmatrix}\begin{pmatrix}I\\\
Q\end{pmatrix}$ $\displaystyle\begin{pmatrix}I\\\ Q\end{pmatrix}$
$\displaystyle=\frac{1}{\sin\theta}\begin{pmatrix}\sin((n+1)\theta)&-\sin(n\theta)\\\
-\cos((n+1)\theta)&\cos(n\theta)\end{pmatrix}\begin{pmatrix}y_{n}\\\
y_{n+1}\end{pmatrix}$

Figure 5: Feedback DSP core firmware implementation in fabric

The total latency of the feedback DSP core is 50 clock cycles or 436 ns. In
parallel, all signals are passed to a multichannel RF waveform buffer with
configuration decimation and cascaded integral-comb (CIC) filter, where a
fixed scaling waveform branches off for realtime RF power interlocking and
machine protection purpose, as shown in Fig. 6. The fast RF power interlock
has a configurable mode of comparison between the measured RF amplitude and a
pair of programmable thresholds for disabling the DAC output in case of
unexpected RF power or phase measurements, within $<1\mu$s limit to protect
down stream high power amplifiers and equipments.

Figure 6: Multichannel RF waveforms and configurable interlock Figure 7: PI
controller

There are two Proportional–Integral (PI) controllers that are responsible for
the feedback loop control of cavity probe signal’s amplitude and phase
respectively. A classical, scalar PI controller with slew rate limiter and
phase wrapping capability is implemented as shown in Fig. 7 with simple
transfer function:

$C(z)=K_{p}+K_{i}\frac{1}{1-z^{-1}},\qquad T=\frac{1}{f_{\text{clk}}}$

We also implemented a state-machine that can synchronously rotate the phase
loop setpoints of both LLRF stations, so that the relative RF bucket can be
aligned between AR and SR. This is required for beam swapping operation for
ALS-U. This _phase ramping_ procedure is repeatably triggered by a common
timing event with delay configuration and fault handling.

Figure 8: Bucket alignment scheme between AR and SR

##  IV Software

Both LLRF stations are managed by a center master interlock PLC through RS485
/ Modbus RTU links. The PLC continuously polling registers through the
interrupt service function of the PicoRV32 CPU, which handles Modbus RTU
protocol and retrieves realtime register information for monitoring.

Figure 9: PLC–FPGA interfaces

PLC screens are developed for configuration of operation parameters including
RF power / ARC interlock mode and thresholds.

An EPICS IOC is built based on single-source-of-truth register mapping,
sharing the same architecture with LCLS-II LLRF project. An example of a
working Phoebus engineering screen is shown in Fig. 10

Figure 10: Example Phoebus GUI

##  V Performance

The single side band $f_{\text{LO}}$ generation has $>90$ dB spurious free
dynamic range (SFDR), with $-84.6$ dB MO carrier feedthrough. The measured
additive phase noise of LO signal is 29 fs [1Hz, 1MHz]. The measured RF drive
signal also has $>95$ dB SFDR, with RMS phase noise of 30 fs [1Hz, 1MHz].

LO Spurious Free Dynamic Range | $>90$ | dB
---|---|---
Carrier feedthrough in LO signal | -84.6 | dB
RMS Additive LO phase jitter [1Hz, 1MHz] | 29 | fs
TABLE II: Single Side Band LO generation benchmark TX Supurious Free Dynamic Range | $>95$ | dB
---|---|---
RMS Additive phase jitter [1Hz, 1MHz] | 30 | fs
TABLE III: RF drive signal (after up-conversion) benchmark

The measured receiver channel-to-channel isolation is $>86$ dB as shown in
Fig. 11.

Figure 11: Receiver channel-to-channel isolation

The measured RF-to-RF group delay is $<1\mu$ second by directly looping back
RF drive signal and one of the receiving signals, when pulsing the drive
signal, as shown in Fig. 12.

Figure 12: Group Delay measurement

The feedback loop noise floor is measured also by looping back TX and RX
(cavity probe signal), and using the spectrum analysis of the waveforms. We
used an external RF signal analyzzer (R&S FSWP) and measured that the out-of-
the-loop RMS amplitude stability is $<0.005\%$, and RMS phase loop stability
is $<0.008^{\circ}$.

Figure 13: In-loop stability measurement

Figure 14: Out-of-loop stability measurement

We also measured the frequency response of both loops when directly looped
back, by adding a known excitation frequency on the setpoint of either
amplitude or phase loop, and analysis the response spectrum. The resulting
Bode plot is shown in Fig. 15.

Figure 15: Bode plot of both loops when directly looped back

The _phase ramping_ bucket alignment test result is shown in Fig. 16. This is
done by ramping of phase setpoint from A to B, at a configurable speed, when
the loop is closed. The ramping successfully executed greater than 7 period of
RF cycle, after being triggered by an timing event, which is required by beam
swapping operation between AR and SR.

Figure 16: Phase ramping process when both loops are closed

##  VI Conclusion

The ALS-U AR LLRF system is developed and tested on the bench, where its
performance meats the requirements. The design is conducted using fully open
source hardware, firmware and software libraries offered by BerkeleyLab. The
same design is also tested in Brazilian Light Source (SIRIUS) at a different
frequency configuration, where
$f_{\text{LO}}=\frac{23}{34}f_{\text{MO}}=479.17\,\text{MHz}$ and
$\frac{f_{\text{IF}}}{f_{\text{Sample}}}=\frac{4}{23}$. The system is ready
for cavity test and commissioning at ALS-U project.

## Acknowledgment

This work is supported by the Office of Science, Office of Basic Energy
Sciences, of the U.S. Department of Energy under Contract No. DE-
AC02-05CH11231.

## References

  * [1] Q. Du, L. Doolittle, M. Betz, M. Vinco, and K. Baptiste, “Digital low-level rf control system for advance source storage ring,” in _Low Level RF workshop 2019, Chicago, IL, USA, Sept 29 – Oct 3, 2019_ , 2019.
  * [2] “Marble-Mini board: Dual FMC NAD/AMC FPGA Carrier,” https://github.com/BerkeleyLab/Marble-Mini, 2019.
  * [3] “Zest board: Dual FMC ADC and DAC digitizer,” https://github.com/BerkeleyLab/Zest, 2019.
  * [4] “Bedrock: Open Source LLRF FPGA Firmware Library,” https://github.com/BerkeleyLab/Bedrock, 2019.
  * [5] “PicoRV32 – A Size–Optimized RISC–V CPU,” https://github.com/cliffordwolf/picorv32, 2015.
  * [6] L. Doolittle, H. Ma, and M. S. Champion, “Digital Low–Level RF Control using Non–IQ Sampling,” in _Proceedings of LINAC 2006, Knoxville, Tennessee USA_. Citeseer, 2006, pp. 568–570.