# An Empirical Comparison of Big Graph Frameworks in the Context of Network
Analysis

Jannis Koch  Christian L. Staudt  Maximilian Vogel  Henning Meyerhenke

###### Abstract

Complex networks are relational data sets commonly represented as graphs. The
analysis of their intricate structure is relevant to many areas of science and
commerce, and data sets may reach sizes that require distributed storage and
processing.

We describe and compare programming models for distributed computing with a
focus on graph algorithms for large-scale complex network analysis. Four
frameworks – GraphLab, Apache Giraph, Giraph++ and Apache Flink – are used to
implement algorithms for the representative problems Connected Components,
Community Detection, PageRank and Clustering Coefficients. The implementations
are executed on a computer cluster to evaluate the frameworks’ suitability in
practice and to compare their performance to that of the single-machine,
shared-memory parallel network analysis package NetworKit. Out of the
distributed frameworks, GraphLab and Apache Giraph generally show the best
performance.

In our experiments a cluster of eight computers running Apache Giraph enables
the analysis of a network with about 2 billion edges, which is too large for a
single machine of the same type. However, for networks that fit into memory of
one machine, the performance of the shared-memory parallel implementation is
far better than the distributed ones. The study provides experimental evidence
for selecting the appropriate framework depending on the task and data volume.

Keywords: big graph frameworks, distributed computing, graph algorithms,
complex networks, network analysis

##  1 Introduction

Complex networks are data sets which map items and the links among them,
forming complex relational patterns. They are typically represented as graphs,
i.e. a set of $n$ vertices $V$ and $m$ edges $E$. This abstraction is as
general as it is powerful, and has been employed in numerous problem domains
[Costa et al., 2011]. The task of network analysis is to characterize the
structure of the network as a whole or identify important elements in it,
typically by applying a collection of graph algorithms tailored to this
purpose (see Section 4).

Many applications – think for example of the networks collected by online
social networking sites – produce enormous amounts of network data that exceed
the memory of any single computer, calling for distributed solutions. A
distributed system consists of a set of autonomous processors, each with their
own memory, running software that performs computations and exchanges data as
messages via a network. Distributed systems are highly scalable in the sense
that additional computers can be added easily. Of course, additional computers
may mean additional overhead as well.

Figure 1: Overview and classification of distributed programming models
(black) and implementations (blue) considered in this paper.

Multiple programming models for distributed parallel computing have been
introduced, some general-purpose (like MapReduce), others focus on the
processing of large graphs (like Pregel) – sometimes called Big Graph
frameworks to express their relation to Big Data. Among the software
frameworks implementing these programming models, we consider Apache Giraph
[Apache, 2015b], Apache Giraph++ [Tian et al., 2013], GraphLab [Dato, 2015]
and Apache Flink [Apache, 2015a] in our study. An overview of programming
models and their implementations is shown in Figure 1.

Considering performance, the scalability and expressiveness enabled by such
frameworks comes at the cost of overhead: A recent experimental study [Satish
et al., 2014] compares implementations of graph algorithms based on frameworks
(including GraphLab and Giraph) to ad hoc, hand-optimized code and observes a
substantial performance gap. Similar algorithms chosen for our study were also
used recently by [McColl et al., 2014]. They experience the aforementioned
performance gap, too. However, they test only on graphs generated with the
synthetic R-MAT model, which lacks realism in several respects. Moreover, our
focus is on distributed frameworks and we include some not used in their
study.

Complex networks present certain inherent performance challenges for
distributed systems: Computation is data-driven in this case, i.e. it is
largely determined by the graph structure. This makes it difficult to exploit
opportunities for parallelism, because they depend heavily on the input. Real-
world networks often have a skewed degree distribution, which adversely
affects load balance. In synchronous execution models, the few high-degree
vertices will delay the whole system. Performance depends also on how vertices
are distributed among the processor nodes, i.e. the graph must be partitioned
so as to reduce communication volume and to balance the work load – a problem
whose optimal solution is NP-hard to compute. Given these challenges,
performance experiments on real-world networks are crucial for choosing the
right framework for the problem at hand.

##### Contribution.

We address the shortage of comparative studies and report performance results
for several distributed frameworks. Apache Giraph, GraphLab, Giraph++ and
Apache Flink are described and compared regarding both theoretical and
practical aspects. The theoretical areas of comparison include the programming
models and their suitability for expressing graph algorithms. For an
experimental comparison, several well-known graph algorithms were implemented
using the frameworks. With real-world complex networks (mainly from web
applications) as input, the implementations were executed on a computer
cluster to reveal how the frameworks compare in practice with regards to
performance and memory footprint. Additionally, we compare performance with
implementations in a shared-memory parallel framework, NetworKit [Staudt et
al., 2014]. While the small-scale cluster we had available for this study is
not enough to test out the true scalability of distributed frameworks, our
results enable an informed choice on which framework to use for a given
network analysis problem. It becomes clear that, compared to shared-memory
parallel solutions, distributed frameworks come with a significant overhead.
Consequently, opting for a distributed solution must be justified by the fact
that the graphs to be processed cannot fit into main memory, which currently
applies to graphs above the size range of several billion edges.

##  2 Programming Models for Distributed Graph Processing

###  2.1 General-purpose Models

##### MapReduce and its Limitations.

MapReduce is a programming model for general distributed computation [Dean and
Ghemawat, 2008], and is often considered the de facto standard for this
purpose [Karloff et al., 2010]. A basic MapReduce program is defined by two
user functions - a map and a reduce function. Both functions receive and emit
data as key-value pairs. A program is executed in three phases - a map, a
shuffle and a reduce phase. Although MapReduce is able to express many common
graph algorithms [Lin and Dyer, 2010], it has limited practicality in this
area: Many graph analysis algorithms are iterative. Since the MapReduce model
does not provide seamless support for iteration, this can only be reproduced
by scheduling several consecutive jobs, resulting in significant overhead.
Because each iteration needs the initial input graph data, the map function
does not only emit an intermediate result for the input vertex, but also the
vertex data itself, i.e. the vertex adjacency list and its current state.
Consequently, graph data is sent over the network unnecessarily. Workarounds
like emitting the graph structure make MapReduce implementations harder to
develop and understand. We do not include MapReduce in the experimental study,
since the models we discuss in the following offer more intuitive ways of
expressing graph algorithms.

##### PACT Model.

The PACT ("Parallelization Contract") model [Battré et al., 2010] was proposed
to extend MapReduce in both functionality and optimization opportunities. It
can be seen as a generalization of MapReduce that offers additional operators.
A PACT operator receives a user-defined function and an input data set
containing tuples of predefined types. It applies the user-function to the
input data in parallel and returns the output. The operator is described by a)
the _Input Contract_ , which defines how the user function can be applied to
the input data set in parallel and b) the _Output Contract_ , which gives
additional information on the data output. It can be optionally attached by
the programmer and allows the PACT compiler to apply optimization techniques
to the execution. When writing a PACT program, the programmer uses an operator
by defining its user function and the input data it operates on. The output of
an operator can be used as the input of another, which creates a directed
acyclic graph of operators (see Figure 3). Unlike MapReduce, the PACT model
does not force a specific order of the operators. The PACT compiler examines
the structure of the resulting operator graph and infers an optimization
strategy for the execution, e. g. rearranging operators in the graph. A PACT
program therefore has a declarative style, reminiscient of the SQL language.
The PACT model is implemented by the Apache Flink framework [Apache, 2015a].

###  2.2 Vertex-centric Models

Vertex-centric models express programs from a vertex perspective. These
programs are executed iteratively for each vertex in the graph. The models are
tailored to graph algorithms and, by incorporating vertices and edges, they
include the data dependencies of graphs in the programming model.

##### Pregel.

The Pregel model was introduced by Google in 2010 [Malewicz et al., 2010]. It
is based on the Bulk Synchronous Parallel model (BSP), which is a general,
iterative model for parallel computation [Valiant, 1990]. An iteration
consists of an algorithm that is executed on each processor, followed by a
communication phase for data exchange between processors. Such an iteration is
called a _superstep_. The execution is synchronous, thus a processor will only
start executing a superstep if all other processors have finished with the
previous one. The Pregel model is implemented by the Apache Giraph framework
[Apache, 2015b].

##### Gather-Apply-Scatter (GAS).

The GAS model was proposed as part of the PowerGraph abstraction [Gonzalez et
al., 2012], which is implemented in the GraphLab framework. GAS programs are
iterative and vertex-centric like Pregel programs, but decompose an iteration
into the gather, apply and scatter phases. Accordingly, a GAS program is
defined by a gather, apply and scatter and an optional gather_sum function. A
further decomposition of the vertex program enables the framework to execute
gather and scatter concurrently on several machines to balance the workload of
high-degree vertices. In the gather phase, a vertex can gather information
from neighbors. The gather function is called for each edge of the vertex and
returns the desired data. The values returned are aggregated by the gather_sum
function. The apply function is called once per vertex on the result of the
gather aggregation. Apply is the only phase where the vertex data can be
changed. Finally, the scatter function is called for each edge again. Scatter
can be used to update edge data. The gather and scatter functions only have
read access to vertex data. This allows them to be executed concurrently
without the need for synchronization. The GAS model is implemented by the
GraphLab framework [Dato, 2015].

###  2.3 Graph-centric Model

Figure 2: A graph with two partitions $P_{1}$ and $P_{2}$. The dashed vertices
in $P_{2}$ are boundary vertices of $P_{1}$ and therefore part of the subgraph
$G_{1}$.

One of the reasons why vertex programs are so intuitive is that the
abstraction hides details of the distributed execution, like graph
partitioning. However, this information could be used for algorithm-specific
optimizations. The graph-centric model [Tian et al., 2013] is a lower-level
abstraction which provides information on the partition structure to the
programmer: A program is no longer expressed for one vertex, but for the whole
block (or several blocks) of a partition. Each vertex of the graph is part of
exactly one block. The graph is divided into $k$ subgraphs $G_{i}$ (the
blocks), each of which contains the vertices of a block $P_{i}$ as well as all
vertices adjacent to vertices of Pi. The vertices in Pi are called _internal
vertices_ of Gi, all others are called _boundary vertices_ (see Figure 2 for
an example).

A graph program is executed iteratively and synchronously, just like a Pregel
program. It is defined by a compute function, which can access the data of all
vertices, both internal and boundary. Yet, only internal vertices can be
changed. Updates to boundary vertices are only possible by sending a message
to the corresponding internal vertex. The owner of the vertex receives
incoming messages and can update it accordingly.

The lower-level graph-centric abstraction is useful in the following areas: In
vertex programs, data can be passed to neighbors only, so it can take many
supersteps to propagate information across a graph. This is slow and could be
accelerated for the vertices that are in the same partition. In the graph-
centric model, messages need to be sent to boundary vertices only, as we can
directly update vertex states of internal vertices. This reduces the amount of
messages that are sent and processed. It may also reduce the number of
supersteps: Information of one vertex is available to all vertices in the
partition in the same superstep, which leads to faster convergence and
therefore execution time for some problems. The graph-centric model also
allows the use of sequential algorithms as they can be easily applied to the
subgraph represented by the partition. Graph-centric programs are executed
synchronously, as a synchronization barrier waits for the last computation to
finish after each superstep. However, local asynchrony is possible, as updates
made to vertex data are available within the computation of one partition
immediately. The graph-centric model is implemented by the Giraph++ [Tian et
al., 2013] framework.

##  3 Frameworks

This section introduces the software frameworks that implement the
aforementioned programming models. All of them share some common
implementation principles, which we discuss briefly before the specifics of
each framework: One is the use of a distributed file system, which provides
the means to store data sets that are too large for a single machine and
enable data locality and fault-tolerance. Files are split up into blocks which
can distributed across a cluster. The file system coordinates how clients
access and write to files. All frameworks presented support the Hadoop
Distributed File System (HDFS).

The frameworks of message-based programming models also implement message
combiners as follows: In many cases, the message receiver is not interested in
each individual message value, but some kind of aggregation of the messages.
Therefore, messages can be combined on the sender node to reduce network
traffic. The principle of combiners can be used in vertex- and graph-centric
models by implementing a combine function which is called by the framework on
messages with the same receiver.

###  3.1 Apache Flink

Apache Flink [Apache, 2015a] (previously called Stratosphere [Apache, 2015c])
is an open-source framework written in Java. It implements the PACT
programming model. PACT was put forward by this project with the goal of
extending the MapReduce model with new operators and a flexible compiler able
to infer optimization strategies from descriptive programs. Apache Flink
offers a Java and a Scala API to write PACT programs.

###  3.2 Apache Giraph

Apache Giraph [Apache, 2015b] is an open-source implementation of the Pregel
programming model. It is written and implemented in Java and uses Apache
Hadoop, a MapReduce implementation, for the execution of vertex programs.
Facebook uses Apache Giraph in practice for the analysis of its social graph
and is an active contributor to the project [Avery Ching, 2013].

###  3.3 GraphLab

The GraphLab [Dato, 2015] package was initially intended to be used on shared
memory systems, but was extended to support distributed execution [Low et al.,
2012]. Programs utilizing GraphLab are written in C++; Python bindings are
also available. With GraphLab 2, support for the GAS model was introduced,
which was proposed as part of the PowerGraph abstraction [Gonzalez et al.,
2012].

###  3.4 Giraph++

The graph-centric model originates from a paper by Tian et. al. [Tian et al.,
2013], who also put forward Giraph++, an implementation of this model
developed on top of Apache Giraph. Currently Giraph++ is not available as a
separate framework, but as a patch for Apache Giraph which adds support for
the graph-centric model to Giraph [Apache, 2014]. It is proposed to become
part of the Apache Giraph project.

##  4 Network Analysis Algorithms

For the experimental study, we select four common and typical network analysis
problems, Connected Components, Community Detection, PageRank, and Clustering
Coefficients. The former two call for a decomposition of the entire network
into cohesive parts, and we opt for algorithms based on label propagation.
Thus, both lend themselves to vertex-centric implementations. The latter two
yield a ranking of vertices by structural relevance, PageRank through a simple
iterative rule, Clustering Coefficients based on the somewhat more intricate
counting of triangles. We consider the program flow of these algorithms
representative for many algorithmic kernels used for network analysis.
Moreover, their algorithmic structure is able to highlight challenges and
benefits of distributed processing.

###  4.1 Connected Components via Label Propagation

Many real-world networks have several connected components, but one of them
usually dominates by far in size [Newman, 2010]. For network analytic purposes
it is interesting to determine whether a vertex belongs to this giant
component or not. Thus, subdividing the network into connected components is a
common analysis task and can be implemented as attaching a component label to
each vertex. The label propagation algorithm used in this study starts with
each vertex in its own component and communicates its component ID to all
neighbors. A vertex then applies the lowest component ID to itself. If the
label has changed, the vertex will notify all neighbors with the new component
ID.

Figure 3 illustrates the principle of the algorithm in PACT: The algorithm
works on tuples of vertex IDs and component labels, whereas the edge
information is used to create these tuples.

Figure 3: PACT operator graph of the Connected Components example

The implementations in Pregel and GAS can be seen in Algorithms 1 and 2: After
the initialization with the vertex ID as component label, the vertices
distribute their component label along their edges to neighbors and in turn
apply the lowest component label from all incoming labels. Figure 4 shows an
example run of the algorithm in the Pregel model.

1 compute(_vertex, messages_) begin

2 if  _getSuperstep() = 0_ then

3 vertex.component $\leftarrow$ vertex.id

4 changed $\leftarrow$ true

5

6 else

7 minMsg $\leftarrow$ getMinimum(messages)

8 changed $\leftarrow$ false

9 if  _minMsg < vertex.component_ then

_//__found smaller component_

10 changed $\leftarrow$ true

11 vertex.component $\leftarrow$ minMsg

12

13

14 if  _changed_ then

_//__component has changed - send new id to neighbors!_

15 sendToAll(vertex.component)

16

17

18

Algorithm 1 Connected Components in Pregel model

1 init(_vertex_) begin

2 vertex.component $\leftarrow$ vertex.id

3

4

5gather(_vertex, edge_) begin

6 return _vertex.component_

7

8gather_sum(_v1, v2_) begin

9 return _minimum(v1, v2)_

10

11apply(_vertex, minimum_) begin

12 changed $\leftarrow$ false

13 if  _vertex.label > minimum_ then

14 changed $\leftarrow$ true

15 vertex.component $\leftarrow$ minimum

16

17

18

19scatter(_vertex, edge_) begin

20 if  _changed_ then

_//__signal to inform neighbour of change_

21 signal(edge.target())

22

23

24

Algorithm 2 Connected Components in GAS model Figure 4: Example computation of
connected components in the vertex-centric Pregel model. The two connected
components are separated by a larger gap in the middle. Gray arrows represent
graph edges, black arrows represent message passing, inactive vertices are
indicated by a dotted line.

In the graph-centric model, the algorithm does the following: In the first
superstep, a sequential algorithm is used to find all connected components in
one partition. For each boundary vertex, a message with the newly found
component label is sent to the partition with the corresponding internal
vertex. If any of the incoming messages have a smaller label for a vertex,
then this vertex and all other vertices within the same component and
partition will be updated at once. Figure 5 shows an example run of the
computation.

Figure 5: Example computation of connected components in the graph-centric
model of Giraph++: For each boundary vertex, a message with the component
label is sent to the partition with the corresponding internal vertex.

###  4.2 Community Detection via Label Propagation

Many real-word networks exhibit a _community structure_ , i. e. they can be
decomposed into internally dense and externally sparse subgraphs named
communities. Among heuristics for detecting communities, a label propagation
algorithm [Raghavan et al., 2007] is among the fastest and easiest to
parallelize: Each vertex is initialized with a unique community label, and
vertices propagate their label to all neighbors in each iteration and update
it with the most frequent of the received labels. Ties are broken
systematically, e. g. uniformly at random or by preferring the minimum label.
The algorithm can be executed synchronously or asynchronously. As the
synchronous execution can lead to an oscillation of labels [Raghavan et al.,
2007], the asynchronous execution is preferred. When adapted suitably, the
general idea of label propagation is also useful for partitioning a network
into equally sized blocks with few edges running between different blocks
[Meyerhenke et al., 2014, Slota et al., 2014]. Such results are potentially
useful for computing partitions in the graph-centric model.

In PACT, the algorithm is expressed as follows: The label of a vertex is
initialized with the vertex ID of a random neighbor. A bulk iteration is
performed on the resulting data set. In each iteration, a join operator is
used to get tuples (vertexId, neighborLabel) for every vertex. A group
operator on both vertex and label followed by a sum aggregator counts the
labels for each vertex. This data set is then grouped by the vertex ID, a
reduce operator finds the most frequent labels and emits the result.

The label propagation algorithm can be naturally expressed in the vertex-
centric model of Pregel. In the algorithm’s initialization superstep, an
optimization is possible since in Pregel each vertex can access its neighbors’
IDs. Since these IDs are equal to the initial label value, there cannot be a
most frequent one. Thus, the label of each vertex is initialized with the
label of a randomly selected neighbor. This label will be sent to all
neighbors, which select the most frequent of the incoming labels. If the new
label differs from the previous one, a local converged flag is set to false.
Global aggregation of this flag is used to check for termination.

In GAS the algorithm works similarly, as gather and gather_sum determine the
label frequency, apply applies the new label and scatter distributes it among
neighbors.

The graph-centric implementation is again similar, with the major difference
that within a partition the labels can be updated directly, because messages
have to be exchanged for boundary vertices only. Since the label updates are
not applied globally in a synchronized way, label oscillation is less likely
to occur.

###  4.3 PageRank

PageRank is a well-known centrality algorithm, enabling a ranking of vertices
by their structural importance – and taking the importance of neighbors into
account. It was originally developed to rank websites in the web graph [Brin
and Page, 1998], but due to Google’s success it has experienced much wider
attention and applications [Newman, 2010]. The PageRank corresponds to the
dominant eigenvector of a transition matrix modeling a random surfer. In
practice one often approximates a vertex score $P(v)$ by using the power
iteration algorithm, i. e. by computing the iteration $P_{i+1}(v)=\alpha
r(v)+(1-\alpha)\cdot\sum_{\\{u,v\\}\in E}\frac{P_{i}(u)}{deg(u)}$, where
$\alpha$ is a dampening factor that models a random jump to an arbitrary
webpage (as opposed to following a link). In the following we make the usual
assumption of $r(v)=1$ for all $v\in V$ and call $P(v)$ the _score_ of vertex
$v$.

The PACT implementation works on different sets of tuples: 1) vertex ID and
score and 2) vertex ID and a list of neighboring vertices. A bulk iteration
for the vertices is then defined by a join over the neighbor tuple and the
corresponding scores. Afterwards, a group by vertex ID and the aggregation by
computing the sum follows.

In GAS, the PageRank algorithm is easily expressed as follows (also see
Algorithm 3): gather is called for all incoming edges and returns the neighbor
vertex score divided by its outdegree. apply receives the sum of these values,
which is used to calculate the new score and the delta value. If delta is
below the tolerance, the converged flag is set to true. scatter, which is
called on outgoing edges, signals neighbor vertices, but only if the vertex
score has not converged. In Pregel, the termination is handled differently as
all vertices remain active as long as the global termination criterion is not
met (Algorithm 4).

_//__gather on incoming edges_

1 gather(_vertex, edge_) begin

2 return _edge.source.score / edge.source.numOutEdges_

3

4apply(_vertex, sum_) begin

5 newScore = $\alpha$ \+ (1 - $\alpha$) * sum

6 delta $\leftarrow$ newScore - vertex.score

7 vertex.score $\leftarrow$ newScore;

8 if  _|delta| > TOLERANCE_ then

9 converged $\leftarrow$ FALSE

10

11 else

12 converged $\leftarrow$ TRUE

13

14

15

_//__scatter on outgoing edges_

16 scatter(_vertex, edge_) begin

17 if  _not converged_ then

18 signal(edge.target)

19

20

_//__alternative scatter using GraphLab’s delta caching_

21 scatter(_vertex, edge_) begin

22 if  _not converged_ then

postDelta(edge.target, delta);

_/*__post delta only if vertex has not converged */_

23

24

25

Algorithm 3 PageRank in GAS model

1 compute(_vertex, messages_) begin

2 if  _getSuperstep() = 0_ then

3 vertex.rank $\leftarrow$ 1

4

5 else

6 newScore $\leftarrow$ $\alpha$ \+ (1 - $\alpha$) * sum(messages)

7 delta $\leftarrow$ newScore - vertex.rank

8 vertex.rank $\leftarrow$ newScore

9

10 if  _|delta| > TOLERANCE_ then

11 converged $\leftarrow$ FALSE

12

13 else

14 converged $\leftarrow$ TRUE

15

16 setAggregatorValue(CONVERGENCE, converged)

17

18 if  _getAggregatorValue(CONVERGENCE)_ then

_//__algorithm converged_

19 voteToHalt()

20 else

21 sendMessageToAllEdges(vertex.rank / vertex.numEdges)

22

23

24

25combine(_msg1, msg2_) begin

26 return _msg1 + msg2_

27

Algorithm 4 PageRank in Pregel

The graph-centric implementation is again similar to the vertex-centric
models, in this case Pregel. However, in Giraph++ the support for local
asynchrony is used: Values from vertices within the partition can be accessed
directly while for boundary vertices messages need to be exchanged. Also, here
we can make use of a minor optimization [Zhang et al., 2012] that was shown to
converge faster than the traditional iterative approach.

###  4.4 Clustering Coefficients

Transitivity is a network analytic concept to express if two neighbors of a
vertex are likely to be neighbors as well or not. In social networks, for
example, two friends of the same person are more likely to be friends as well
than a random pair of vertices [Newman, 2010]. Thus, as one formalization of
the transitivity, we can use the _average local clustering coefficient_ $C(G)$
for an undirected graph $G$ to examine its local connectivity. This particular
measure is defined as the mean over the local clustering coefficient over all
vertices, i. e. $C(G)=\frac{1}{|V^{\prime}|}\sum_{v\in
V^{\prime}}\frac{\delta(v)}{\tau(v)}$, where $V^{\prime}:=\\{v\in
V~{}|~{}\deg(v)\geq 2)$, $\delta(v)$ is the number of triangles $v$ belongs
to, and $\tau(v):={\deg(v)\choose 2}$ (see e. g. [Schank and Wagner, 2005]).
This is different from the _global clustering coefficient_ , which contrasts
the numbers of closed triangles and of connected triplets in a graph (times a
constant factor).

All of the described measures can be computed with the same algorithmic idea,
as the basic operation is counting triangles. Since the exact algorithm is
computationally expensive for large complex networks, we are also interested
in an efficient approximation algorithm. [Schank and Wagner, 2005] proposed a
sequential random sampling algorithm to approximate the clustering coefficient
with a (probabilistic) additive error bound. For the _average local clustering
coefficient_ , it randomly selects a vertex $v$, and two different neighbors
of $v$, $u$ and $w$. If $u$ and $w$ are connected, a counter is incremented.
This process is repeated for a fixed number of samples. The approximation
value of the _average local clustering coefficient_ is the number of links
found divided by the number of samples. For the _global clustering
coefficient_ the samples will be chosen with a probability proportional to
$deg(v)\cdot(deg(v)-1)$ for a vertex $v$, where $deg(v)$ denotes the degree of
$v$.

In PACT, to count the relevant edges, two join operations are necessary. The
first is carried out on the edges with themselves resulting in a set of
neighbors of neighbors of a vertex. The second join then joins the resulting
set with the edges again with respect to a vertex. The rest of the algorithm
is straightforward.

The Pregel implementation (Algorithm 5) consists of two supersteps where the
first one sends the edge information to incident vertices while the second one
computes the local clustering coefficient and sets the aggregators for the
global values.

The GAS implementation (Algorithm 6) is similar as it uses one step to
calculate the common neighbors of two vertices and uses this information in
the second step to do the final computation. Aggregation of the vertices’
values is then done using mapReduce functions. The graph-centric model does
not yield any advantages over the vertex-centric models in this application,
so the implementation basically follows the Pregel implementation. Again, the
main difference is that the computation for edges in a partition can be done
directly, whereas explicit message exchange is necessary for boundary
vertices.

The implementation of the approximation algorithm principally follows the
implementation of the exact algorithm with a few exceptions. Depending on
whether the global or the average local clustering coefficient is computed,
the probability for each vertex needs to be set. Then, instead of exchanging
the whole neighborhood, each vertex will only draw a fixed number of vertex
pairs and send it to these vertices, e.g. during a superstep in Pregel.
Another superstep is then used to intersect the neighborhoods and the incoming
messages and for each match the link counter will be incremented. Afterwards,
the usual global aggregation will compute the final values.

1 compute(_vertex, messages_) begin

2 if  _getSuperstep() = 0_ then

3 for  _edge $\in$ vertex.edges _ do

4 sendMessageToAllNghbrs(_edge.otherVertex.id_)

5

6 else if  _getSuperstep() = 1_ then

7 neighborEdges $\leftarrow$ 0

8 for  _$msg\in messages$_ do

9 if  _msg $\in$ vertex.edges_ then

10 neighborEdges $\leftarrow$ neighborEdges + 1

11

12

neighborEdges $\leftarrow$ neighborEdges / 2

_//__each link has a message from both vertices_

13 possibleEdges $\leftarrow$ vertex.numEdges * (vertex.numEdges - 1) / 2

14 vertex.localClustering $\leftarrow$ neighborEdges / possibleEdges

15

 _//__Use aggregators for global values_

16 setAggregatorValue(POSSIBLE, possibleEdges)

17 setAggregatorValue(ACTUAL, neighborEdges)

18 setAggreagtorValue(LOCALCC, vertex.localClustering)

19

20

21

22masterCompute(__) begin

23 avgLocalCC $\leftarrow$ getAggregatorValue(LOCALCC) / numVertices

24 globalCC $\leftarrow$ getAggregatorValue(ACTUAL) /
getAggregatorValue(POSSIBLE)

25

26

Algorithm 5 Clustering Coefficients in Pregel model

_//__gather on all edges_

1 gather1(_vertex, edge_) begin

2 return _[edge.otherVertex]_

3

4gather_sum1(_list1, list2_) begin

5 append(list1, list2)

6

7

8apply1(_vertex, neighbors_) begin

9 vertex.neighbors = neighbors

10

11

_//__scatter on all edges_

12 scatter1(_vertex, edge_) begin

13 otherVertex = edge.otherVertex

14 commonNeighborsList = intersection(vertex.neighbors, otherVertex.neighbors)

15 edge.commonNeighbors = commonNeighborsList.size

16

17

18

19 gather2(_vertex, edge_) begin

20 return _edge.commonNeighbors_

21

22apply2(_vertex, neighborEdges_) begin

23 vertex.neighborEdges $\leftarrow$ neighborEdges

24 vertex.possibleEdges $\leftarrow$ vertex.numEdges * (vertex.numEdges - 1) /
2

25 vertex.localClustering $\leftarrow$ neighborEdges / vertex.possibleEdges

26

27

28

29 main(_graph_) begin

30 executeVertexPrograms(graph)

31 avgLocalCC $\leftarrow$ mapReduce(vertex.localClustering) / numVertices

32 globalCC $\leftarrow$ mapReduce(vertex.neighborEdges) /
mapReduce(vertex.neighborEdges)

33

34

Algorithm 6 Clustering Coefficients in GAS model

###  4.5 Discussion

In summary, we confirm that graph-specific frameworks (Giraph, Giraph++,
GraphLab) offer a more concise and intuitive way to express graph algorithms.
Not surprisingly, vertex-centric programming models are well suited for
vertex-centric algorithmic techniques as in label propagation or PageRank’s
iterative method.

##  5 Experimental Comparison

In the following we present a comparative experimental study on the
performance of four distributed and one single-machine framework.

###  5.1 Experimental Setup

For the experiments a rather modest computer cluster of 8 nodes was used. Each
system has 24GB RAM and runs an Intel® Xeon® X5355 CPU with 2.66 GHz and 8
cores on two processors. The framework versions are GraphLab 2.2, Apache
Giraph 1.1.0, Apache Flink 0.6, and NetworKit 3.3. (The NetworKit version has
been patched with a fix for an earlier performance bug in the PageRank
implementation.) Apache Giraph was deployed in a Apache Hadoop MapReduce
environment, using Hadoop 0.20.203.0 and Apache ZooKeeper 3.4.6. For scaling
experiments, the algorithms were run on 1, 2, 4 and 8 cluster nodes. NetworKit
was run on a single node of the same type.

##### Fault tolerance.

Apache Giraph is the only one of the examined frameworks which supports the
recovery in case of a failure during the algorithm’s execution. It uses a
checkpoint mechanism which saves the current computation state of the
algorithm execution to the distributed file system. Workers regularly send
heartbeat messages to the Master to indicate they are executing, thus the
absence of a heartbeat message indicates a failure. In this case, the master
starts up new workers replacing the failed ones. Then, all workers load the
last checkpoint from the file system and resume the computation. The
checkpointing mechanism was tested in experiments for this particular purpose
by killing off one worker process. The master detects the missing worker
immediately, and computation resumes without errors. However, the overhead for
saving checkpoints regularly slows down the performance. Although GraphLab has
a similar checkpoint mechanism, it does not automatically recover in the case
of a failure. GraphLab periodically saves a binary serialization snapshot of
the graph. The algorithm has to be restarted manually using the snapshot as
the input graph.

##### A Shared-Memory Framework for Comparison.

NetworKit [Staudt et al., 2014] is a tool suite of algorithms and data
structures for the analysis of large complex networks, implemented in C++,
OpenMP in the backend and in Python for a user-friendly frontend. NetworKit
runs on a single computer, its OpenMP implementations exploit multicore
capabilities. It is based at Karlsruhe Institute of Technology and developed
with international contributors under an open-source
model.111http://networkit.iti.kit.edu The aim of the package is to provide
efficient, often parallelized graph algorithms and lean data structures for
network analysis.

For this study, we let efficient shared-memory parallel implementations of
network analysis algorithms from NetworKit compete with implementations in
distributed frameworks. The aim of the comparison is to see when it is worth
to move to distributed systems.

##### Test data sets.

Real world graph data sets used for the experiments are listed in Table 1. The
uk-2002 data set [Boldi and Vigna, 2004] originates from a web crawl of the
.uk domain. The remaining data sets were taken from the KONECT graph
collection [Kunegis, 2013]. The Wikipedia data set consists of linked
encyclopedia pages of the English Wikipedia. The orkut-links, livejournal-
links, flickr-links graphs represent the users and friendships of the
respective social networks. twitter [Kwak et al., 2010] and twitter-l [Cha et
al., 2010] are snapshots of the follower graph of the social network Twitter.
twitter-l is the largest data set used in the experiments with almost two
billion edges, taking up over 36 GB of disk space when represented in an edge
list file. The relatively small flickr-edges graph is based on images of the
Flickr website, adjacent images share common meta data. Additionally,
synthetic graphs (scale-free graphs generated using NetworKit’s Dorogovtsev-
Mendes generator) are used for weak scaling experiments. These synthetic data
sets contain 16 million edges per compute node, i.e. 16, 32, 64 and 128
million edges for the experiments on a single, 2, 4 and 8 compute node(s).

name (directed) | n | m | size
---|---|---|---
twitter-l (1) | 52M | 1,963M | 36.16
twitter (1) | 41M | 1,468M | 22.35
wikipedia-links-en (1) | 27M | 601M | 9.48
uk-2002 (1) | 18M | 261M | 8.26
orkut-links (1) | 3M | 117M | 1.65
livejournal-links-d (0) | 4.8M | 68M | 0.99
livejournal-links-u (1) | 5M | 49M | 0.67
flickr-links (0) | 1.7M | 15M | 0.18
flickr-edges (0) | 105k | 2.3M | 0.02
Table 1: Properties of the networks (with $n$ vertices and $m$ edges) used in
the experiments. Size denotes the size of the graph stored in edge list format
in GB.

###  5.2 Results

##### Connected Components via Label Propagation.

Figure 6: Running times [in seconds] of Connected Components.

As Figure 6 shows, the shared-memory parallel implementation in NetworKit is
much faster than the distributed frameworks. Out of the latter, GraphLab
performs best, followed by Apache Giraph. Giraph++ cannot benefit from graph-
centric optimizations and although it reduces the number of supersteps, it
performs worse. Apache Flink is much slower than the other frameworks on a
single node (over 13x slower than GraphLab and 6x slower than Giraph for the
orkut-links graph). It catches up in the cluster setup due to higher speedup
rates, but remains slower than GraphLab and Giraph. For smaller graphs such as
the flickr-links graph, GraphLab and Apache Giraph running times increase with
adding additional compute nodes due to overhead, while Giraph++ and Apache
Flink do achieve a speedup. The connected components on uk-2002 can only be
computed with at least 4 nodes by any of the distributed frameworks. The
billion-edge twitter network can only be processed with GraphLab and Giraph
(besides NetworKit), and the two distributed frameworks require at least 8
nodes. Figure 7 shows that only the Giraph implementation has a stable weak
scaling behavior, and that GraphLab has the largest relative increase, with
the time quadrupling from the single node to the eight node execution.

1248$0$$200$$400$Time in sGraphLabGiraphGiraph++Flink

Figure 7: Weak scaling of connected components with generated data sets of 16
million edges per node

Figure 8: Running times [in seconds] of Community Detection on 1, 2, 4 and 8
nodes. The flash symbol indicates that a graph is too large to be processed
with the respective tool using the given number of nodes.

##### Community Detection via Label Propagation.

Out of the distributed frameworks, GraphLab has a clear advantage over the
other frameworks with its asynchronous model, which is evident in the running
times (Figure 8). NetworKit is again much faster. For flickr-edges and
livejournal-links-u, GraphLab gets slower when more computing nodes are added.
Flink can only handle the flickr-edges data set. Giraph++ computes data sets
up to the orkut-links graph, but is very slow (6x the execution time of Giraph
for livejournal-links-u). Both GraphLab and Giraph process graphs up to the
size of wikipedia-links-en on a cluster of eight nodes. The synchronous
execution of this algorithm can cause convergence problems that prevented some
implementations from terminating. Label oscillations can occur as two
neighboring vertices join the community of the other vertex and because the
communication happens synchronized after local computations are done, they
effectively exchange their labels. This is a disadvantage of frameworks only
supporting synchronous execution (Giraph, Giraph++ and Flink) for this type of
algorithms.

##### PageRank.

With the exception of NetworKit’s implementation, the PageRank implementations
tested run for a fixed number of iterations. PageRank was executed on the
directed test graphs. The livejournal-links-d graph could be processed by all
frameworks in every setting. uk-2002 and wikipedia-links-en could be processed
by the distributed frameworks with 4 and 8 nodes only, twitter only in the 8
node setting. The largest graph, twitter-l, could only be processed by Apache
Giraph. GraphLab stopped with memory allocation errors and Flink aborted the
computation.

GraphLab and NetworKit achieve the best performance for PageRank (see Figure
9): Apache Giraph is slower than GraphLab by a factor of 1.6 to 2.5 for the
smaller livejournal-links-d, and 2.8 to 3 for the larger wikipedia-links-en
and twitter. The differences to Apache Flink are even larger, the latter’s
running time is up to 12 times (uk-2002) higher than that of GraphLab. The
Giraph++ algorithm exhibits poor performance. GraphLab is sometimes faster
than NetworKit due to the fact that NetworKit iterates longer until a higher
accuracy is achieved.

Figure 9: Running times [in seconds] of PageRank.

##### Clustering Coefficients.

Figure 10: Running times [in seconds] of the _exact_ clustering coefficient
for the flickr-edges graph. Figure 11: Running times [in seconds] for the
_approximate_ average local clustering coefficient using 100.000 samples.

The exact local clustering coefficients algorithm is the most challenging
algorithm for the frameworks. It needs a lot of memory, as every vertex
exchanges its total neighborhood with every neighbor, so the number of
messages sent is in $O(n\cdot d_{max}^{2})$. Of the test data sets, only the
small flickr-edges graph can be handled by NetworKit, GraphLab, and Apache
Giraph, even when the distributed frameworks use all 8 servers (see Figure
10). Apache Flink runs the algorithm for two hours, after which the execution
is aborted. NetworKit has again the fastest execution time on a single node,
followed by GraphLab and Apache Giraph. GraphLab needs 8 nodes to be faster
than NetworKit, and Apache Giraph still takes four times as long on 8 nodes.

As expected, the approximation of the clustering coefficients allows much
larger graphs to be analyzed (see Figure 11). NetworKit’s implementation is by
far the fastest as it can access the graph structure much faster, while in
distributed frameworks this requires message exchange, possibly over the
network. In most cases, adding additional cluster nodes does not benefit the
running time (with the exception of the Giraph implementation).

##### Memory Usage.

The memory footprint of the frameworks is crucial to their use in practice –
all the more as we often experience a rather poor scaling behavior in terms of
running time for the graph computations we investigate here. Factors important
for memory usage are the underlying programming language, data structures, and
the framework structure and functionality. In Apache Giraph for example,
messages sent in a vertex program are cached and only sent at the end of a
superstep, which requires additional memory.

GraphLab can only process graphs which can be loaded into memory entirely,
i.e. up to twitter. Giraph, on the other hand, offers an optional graph
swapping functionality. With this feature enabled, Giraph is able to load the
twitter-l graph, but only the memory efficient algorithms PageRank and
ConnectedComponents can be executed without memory errors. Swapping functions
naturally slow down algorithm execution due to the I/O operations. Out of the
test data sets, the largest graph Giraph++ can load on 8 nodes is uk-2002.
Apache Flink’s engine also swaps out data to disk when memory runs out. In
this experimental setting, it can process graphs up to the size of twitter.
NetworKit is able to load the test graphs up to the size of uk-2002 on a
single machine.

##### CPU and Network Utilization.

In the following, the CPU and network utilization of the distributed
frameworks is examined on the basis of the PageRank algorithm executed on the
uk-2002 graph. The values were obtained using Sysstat utilities, which
monitors CPU values with a time resolution of one second. Figure 13 shows the
CPU utilization during the execution of the algorithm, starting after the I/O
phase. Iterations are visible most clearly in the Giraph execution, with low
CPU activity during synchronization phases between supersteps. On average,
Flink has the highest CPU utilization with over 90%, followed by Giraph with
85% and GraphLab with 81.4 %. Giraph++ comes last with 74.4 %.

Figure 12: CPU utilization of the first 100 seconds of the PageRank execution
on the uk-2002 graph. The average values are taken from the whole computation.

Figure 13: Network utilization of the first four minutes of the PageRank
execution on the uk-2002 graph. The values give the send and received number
of kB/s in thousands.

The network utilization is shown in Figure 13, which gives the send and
receive rates of network communication in kB/s. When comparing the vertex-
centric frameworks GraphLab and Giraph, it is noticeable that GraphLab’s
network communication is more evenly distributed. This can be explained with
the GAS model with its decomposition in three phases, each of which requires
the exchange of data for synchronization. Furthermore, GraphLab sends network
messages as they arrive and not at the end of each superstep. Apache Giraph,
in contrast, buffers messages during the vertex program, and sends them
collectively at the end of each superstep. Therefore, there is no
communication during the execution of a vertex program. Giraph++ stands out
with extraordinarily low values. The peak rate of both curves is only at
around 8500 kB/s. This explains the long synchronization times and the weak
performance in general of Giraph++’s executions. In the diagram of Apache
Flink, the longer execution time of iterations are visible.

##### Tuning GraphLab.

Since GraphLab has emerged as the generally fastest distributed framework, we
examine some of its features and tuning options in more detail.

GraphLab’s asynchronous execution engine provides opportunities for a faster
algorithm convergence, but also requires synchronization to ensure
serializability. The execution of PAGERANK-FIXED and CON-COMP shows that the
asynchronous engine indeed leads to faster convergence: The top graphs in
Figure 14 show the total number of updated vertices during algorithm execution
for the livejournal-links-u graph. The number of vertex updates in the
asynchronous execution is consistently lower than in the synchronous execution
(only about 30% to 65%).

1248$5$$10$$15$$20$$25$vertex updates in millionsCON-COMPsynchasynch (a)

1248$10$$15$$20$$25$$30$CON-COMP-MSGsynchasynch (b)

1248$6$$8$$10$PAGERANK-FIXEDsynchasynch (c)

1248$20$$30$$40$$27$$26$$23$$21.3$$24$$45$$34$$26.9$Time in ssynchasynch (d)

1248$10$$20$$30$$40$$50$$60$$25$$24$$21$$17.6$$44$$57$$45$$33$synchasynch (e)

1248$10$$20$$30$$40$$37$$27$$9$$9.3$$40$$33$$11$$12.3$synchasynch (f)

Figure 14: Comparison of Graphlab’s synchronous and asynchronous execution for
Connected Components, message based Connected Components and PageRank (from
left to right) on the livejournal-links graph. The top diagrams shows the
number of updated vertices, the middle and bottom ones the algorithm exection
time.

However, the increased convergence does not translate into faster execution
times: The synchronous execution is almost always faster than the asynchronous
execution. The difference is moderate with PAGERANK-FIXED, but drastic with
CON-COMP-MSG, where the execution time is 1.7 to 2.4 times slower than the
synchronous execution time. What is also noteworthy is that some algorithms
are faster when executed on a single machine than with two or four nodes. If
executed on more than one node, GraphLab needs to maintain copies of vertices
on several machines and also coordinate the execution of a vertex program to
ensure serializability. This overhead can exceed the advantage of the
increased computational power, thus leading to higher execution times. This
behavior depends on both the algorithm and the input graph.

GraphLab provides a message API that allows vertices to send messages to other
vertices, just like in the Pregel model. Furthermore, GraphLab offers delta
caching which caches a vertex’s gather result and updates it using delta
values from neighbors. The impact of those two GraphLab functions is examined
using the Connected Components algorithm, which is run in three different
versions: The standard GAS implementation, a GAS implementation with delta
caching, and a message-based implementation.

Figure 15 shows the execution times of the various implementations. In the
synchronous execution (top graphs), the performance differences of the
implementations is relatively small (5% - 15%). The standard implementation is
slower than the delta caching and message-based variants in almost all cases.
The message based implementation is slower than the delta caching
implementation on the livejournal-links-u graph in the single- and two-node
setup, but slightly slower on four and eight nodes and on all orkut-links
graph executions. In the asynchronous execution mode, the differences are
clearer. The message-based implementation is slower than the standard GAS one
in almost all cases, by up to 36.7%.

1248$20$$40$$60$$61.7$$41$$29.2$$1$$55.6$$37.5$$25.5$$17.6$$52.2$$37$$26.9$$21.03$Time
in slivejournal-links-u, syncStandardMessage APIDelta Caching (a)

1248$10$$20$$30$$27.4$$26$$23.2$$1$$24.6$$24$$20.9$$19.33$$24.6$$24.5$$23.9$$23.7$orkut-
links, sync (b)

1248$40$$60$$80$$50.2$$60.2$$40.2$$26.9$$79.3$$59.4$$47.2$$33$Time in
slivejournal-links-u, async (c)

1248$30$$40$$50$$60$$24.4$$45$$34.3$$27.7$$44.3$$56.8$$44.6$$43.4$orkut-links,
async (d)

Figure 15: GraphLab’s execution times of the standard, message based and delta
caching versions of CON-COMP for the livejournal-links-u graph (left) and the
orkut-links graph (right) in synchronous and asynchronous modes

##  6 Conclusion

We examined several distributed computing frameworks with a focus on graph
algorithms for network analysis. The prominent MapReduce model was discarded
due to its restrictions in the context of graph algorithms. The PACT model
extends the approach of MapReduce and is more powerful, although graph
algorithms are generally more difficult to express than in the graph-specific
models. On the other hand, the vertex-centric Pregel and GAS are very
intuitive models for this purpose. The graph-centric extension allows to add
optimizations to vertex-centric algorithms by giving the programmer access to
partition information.

We implemented representative network analysis algorithms in distributed
frameworks, each of which employs one of the presented programming models. The
implementations show how the programming models can be used in practice to
express typical graph algorithms for network analysis, and how existing
sequential algorithms such as the Clustering Coefficient approximation can be
adapted to distributed programming models. Generally, the vertex-centric
Apache Giraph and GraphLab programs are very similar and the easiest to
implement. The resulting programs in Giraph++ are slightly more verbose and
complex, but can use optimizations impossible in the vertex-centric model.

Experiments were conducted on a cluster of eight nodes. We show that this
distributed setting is able to process graphs of almost two billion edges,
using standard commodity hardware. Not all frameworks perform equally well:
Generally, GraphLab shows the best performance. Apache Giraph is less
efficient in most cases, but offers an out-of-core mechanism which enables it
to handle larger data sets. It is the only framework that could process the
twitter-l graph. Giraph++ unexpectedly performs worse than the vertex-centric
models. However, it must be remembered that only an experimental version of
Giraph++, based on an outdated version of Apache Giraph, is available. Apache
Flink performed worse than the vertex-centric frameworks. Also, larger graphs
could not be processed for some of the algorithms due to issues with memory.
Support for asynchronous execution is essential for the label propagation
community detection algorithm, since the heuristic may not converge for
synchronous execution due to label oscillation.

The single-machine software package NetworKit outperforms the distributed
frameworks in almost all scenarios. It can handle larger graphs than the
distributed frameworks on a single machine, and its execution times are often
only a fraction of the other frameworks’, due to efficient native code and
lack of overhead associated with the software machinery that enables and
supports distributed computing. Consequently, the decision for a distributed
computing solution for complex network analysis should come out of the
necessity of massive graph data volumes that exhaust typical main memory
capacity.

#### Acknowledgements.

This work is partially supported by the German Research Foundation (DFG) under
grant ME 3619/3-1 within the Priority Programme 1736 _Algorithms for Big
Data_. Parts of this paper have been published in preliminary form as [Koch et
al., 2015].

## References

  * [Apache, 2014] Apache (2014).  Giraph++ patch for apache giraph.  https://issues.apache.org/jira/browse/GIRAPH-818.  [Online; accessed 31-July-2014].
  * [Apache, 2015a] Apache (2015a).  Website of the framework apache flink.
  * [Apache, 2015b] Apache (2015b).  Website of the framework apache giraph.
  * [Apache, 2015c] Apache (2015c).  Website of the research project stratosphere.
  * [Avery Ching, 2013] Avery Ching (2013).  Scaling apache giraph to a trillion edges.  https://www.facebook.com/notes/facebook-engineering/scaling-apache-giraph-to-a-trillion-edges/10151617006153920.  [Online; accessed 30-July-2014].
  * [Battré et al., 2010] Battré, D., Ewen, S., Hueske, F., Kao, O., Markl, V., and Warneke, D. (2010).  Nephele/pacts: A programming model and execution framework for web-scale analytical processing.  In Proc. 1st ACM Symp. on Cloud Computing, SoCC ’10, pages 119–130, New York. ACM.
  * [Boldi and Vigna, 2004] Boldi, P. and Vigna, S. (2004).  The WebGraph framework I: Compression techniques.  In Proc. of the Thirteenth International World Wide Web Conference (WWW 2004), pages 595–601, Manhattan, USA. ACM Press.
  * [Brin and Page, 1998] Brin, S. and Page, L. (1998).  The anatomy of a large-scale hypertextual web search engine.  In COMPUTER NETWORKS AND ISDN SYSTEMS, pages 107–117. Elsevier Science Publishers B. V.
  * [Cha et al., 2010] Cha, M., Haddadi, H., Benevenuto, F., and Gummadi, K. P. (2010).  Measuring User Influence in Twitter: The Million Follower Fallacy.  In Proceedings of the 4th International AAAI Conference on Weblogs and Social Media (ICWSM).
  * [Costa et al., 2011] Costa, L. d. F., Oliveira Jr, O. N., Travieso, G., Rodrigues, F. A., Villas Boas, P. R., Antiqueira, L., Viana, M. P., and Correa Rocha, L. E. (2011).  Analyzing and modeling real-world phenomena with complex networks: a survey of applications.  Advances in Physics, 60(3):329–412.
  * [Dato, 2015] Dato (2015).  Website of the company distributing graphlab.
  * [Dean and Ghemawat, 2008] Dean, J. and Ghemawat, S. (2008).  Mapreduce: simplified data processing on large clusters.  Communications of the ACM, 51(1):107–113.
  * [Gonzalez et al., 2012] Gonzalez, J. E., Low, Y., Gu, H., Bickson, D., and Guestrin, C. (2012).  Powergraph: Distributed graph-parallel computation on natural graphs.  In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI’12, pages 17–30, Berkeley, CA, USA. USENIX Association.
  * [Karloff et al., 2010] Karloff, H., Suri, S., and Vassilvitskii, S. (2010).  A model of computation for mapreduce.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 938–948. Society for Industrial and Applied Mathematics.
  * [Koch et al., 2015] Koch, J., Staudt, C. L., Vogel, M., and Meyerhenke, H. (2015).  Complex network analysis on distributed systems: An empirical comparison.  In Pei, J., Silvestri, F., and Tang, J., editors, Proc. 2015 IEEE/ACM Intl. Conf. on Advances in Social Networks Analysis and Mining, ASONAM 2015, pages 1169–1176. ACM.
  * [Kunegis, 2013] Kunegis, J. (2013).  Konect: the koblenz network collection.  In Proc. 22nd Intl. Conf. on World Wide Web companion, pages 1343–1350. International World Wide Web Conferences Steering Committee.
  * [Kwak et al., 2010] Kwak, H., Lee, C., Park, H., and Moon, S. (2010).  What is Twitter, a social network or a news media?  In WWW ’10: Proceedings of the 19th international conference on World wide web, pages 591–600, New York, NY, USA. ACM.
  * [Lin and Dyer, 2010] Lin, J. and Dyer, C. (2010).  Data-intensive Text Processing with MapReduce.  G - Reference,Information and Interdisciplinary Subjects Series. Morgan & Claypool.
  * [Low et al., 2012] Low, Y., Gonzalez, J., Kyrola, A., Bickson, D., Guestrin, C., and Hellerstein, J. M. (2012).  Distributed graphlab: A framework for machine learning in the cloud.  CoRR, abs/1204.6078.
  * [Malewicz et al., 2010] Malewicz, G., Austern, M. H., Bik, A. J., Dehnert, J. C., Horn, I., Leiser, N., and Czajkowski, G. (2010).  Pregel: a system for large-scale graph processing.  In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 135–146. ACM.
  * [McColl et al., 2014] McColl, R. C., Ediger, D., Poovey, J., Campbell, D., and Bader, D. A. (2014).  A performance evaluation of open source graph databases.  In Proc. 1st Workshop on Parallel Programming for Analytics Applications, PPAA ’14, pages 11–18, New York, NY, USA. ACM.
  * [Meyerhenke et al., 2014] Meyerhenke, H., Sanders, P., and Schulz, C. (2014).  Partitioning complex networks via size-constrained clustering.  In Proc. 13th Intl. Symp. on Experimental Algorithms (SEA 2014), volume 8504 of LNCS, pages 351–363. Springer.
  * [Newman, 2010] Newman, M. (2010).  Networks: An Introduction.
  * [Raghavan et al., 2007] Raghavan, U. N., Albert, R., and Kumara, S. (2007).  Near linear time algorithm to detect community structures in large-scale networks.  Physical Review E, 76(3):036106.
  * [Satish et al., 2014] Satish, N., Sundaram, N., Patwary, M. M. A., Seo, J., Park, J., Hassaan, M. A., Sengupta, S., Yin, Z., and Dubey, P. (2014).  Navigating the maze of graph analytics frameworks using massive graph datasets.  In Proc. 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD ’14, pages 979–990, New York, NY, USA. ACM.
  * [Schank and Wagner, 2005] Schank, T. and Wagner, D. (2005).  Approximating clustering-coefficient and transitivity.  Journal of Graph Algorithms and Applications, 9(2):265–275.
  * [Slota et al., 2014] Slota, G. M., Madduri, K., and Rajamanickam, S. (2014).  Pulp: Scalable multi-objective multi-constraint partitioning for small-world networks.  In 2014 IEEE Intl. Conf. on Big Data, Big Data 2014, pages 481–490.
  * [Staudt et al., 2014] Staudt, C. L., Sazonovs, A., and Meyerhenke, H. (2014).  NetworKit: A tool suite for large-scale complex network analysis.  arXiv:1403.3005.
  * [Tian et al., 2013] Tian, Y., Balmin, A., Corsten, S. A., Tatikonda, S., and McPherson, J. (2013).  From "think like a vertex" to "think like a graph".  PVLDB, 7(3):193–204.
  * [Valiant, 1990] Valiant, L. G. (1990).  A bridging model for parallel computation.  Communications of the ACM, 33(8):103–111.
  * [Zhang et al., 2012] Zhang, Y., Gao, Q., Gao, L., and Wang, C. (2012).  Accelerate large-scale iterative computation through asynchronous accumulative updates.  In Proceedings of the 3rd workshop on Scientific Cloud Computing Date, pages 13–22. ACM.


$\displaystyle=\frac{\sqrt{2\kappa_{0}}}{\varepsilon_{a}[\omega]-\mathcal{G}^{2}\varepsilon_{d}[\omega]^{-1}},$
(94)

with $\varepsilon_{a}[\omega]=\kappa+i(\Delta-\omega)$ and
$\varepsilon_{d}[\omega]=\gamma_{d}+i(\Delta_{d}-\omega)$. Note that in this
section the $*$ exponent denotes the complex conjugate and not an optimal
value like in the part on the squeezing. The mechanical susceptibility is
given by

$\chi_{\text{mec}}^{\text{eff}}[\omega]^{-1}=\chi^{0}_{\text{mec}}[\omega]^{-1}+\chi^{\text{eff}}_{\text{opt}}[\omega]^{-1},$
(95)

where
$\chi^{0}_{\text{mec}}[\omega]=\Omega_{\text{mec}}\left(\Omega_{\text{mec}}^{2}-\omega^{2}-i\omega\gamma\right)^{-1}$
is the mechanical susceptibility of the bare resonator and
$\chi^{\text{eff}}_{\text{opt}}[\omega]$ the optical contribution to the
susceptibility, which reads

$\chi^{\text{eff}}_{\text{opt}}[\omega]^{-1}=\frac{2ig^{2}}{\varepsilon_{a}^{*}[-\omega]-\mathcal{G}^{*2}\varepsilon_{d}^{*}[-\omega]^{-1}}-\frac{2ig^{2}}{\varepsilon_{a}[\omega]-\mathcal{G}^{2}\varepsilon_{d}[\omega]^{-1}}.$
(96)

We then identify the optical contribution to the mechanical damping rate,

$\Gamma_{\text{opt}}[\omega]=-\frac{\Omega_{\text{mec}}}{\omega}\Im{\chi^{\text{eff}}_{\text{opt}}[\omega]^{-1}}.$
(97)

Therefore, in the weak-coupling regime, the resonator’s coupling to the
effective cold bath, given by $\Gamma_{\text{opt}}[\Omega_{\text{mec}}]$, is
different from the one of the standard setup.

####  D.2.2 Lyapunov equation

Like in Section B.2.2, we write the Langevin equations for the quadratures and
obtain the Lyapunov equation $\derivative{V}{t}=AV+VA^{T}+B$ for
$\vec{Y}=\left(\delta\hat{X}_{a},\delta\hat{P}_{a},\delta\hat{q},\delta\hat{p},\delta\hat{X}_{d},\delta\hat{P}_{d}\right)$,
with

$\displaystyle\\!\\!\\!\\!\\!A$
$\displaystyle=\\!\begin{bmatrix}-{\kappa}&\\!{\Delta}&\\!0&\\!0&\\!\\!-\sqrt{{\gamma_{d}}{\kappa_{\text{L}}}}&\\!\sqrt{{\gamma_{d}}{\kappa_{0}}}\\\
-{\Delta}&\\!-{\kappa}&\\!2g&\\!0&\\!\\!-\sqrt{{\gamma_{d}}{\kappa_{0}}}&\\!-\sqrt{{\gamma_{d}}{\kappa_{\text{L}}}}\\\
0&\\!0&\\!0&\\!\Omega_{\text{mec}}&\\!0&\\!0\\\
2g&\\!0&\\!\\!-\Omega_{\text{mec}}&\\!-{\gamma}&\\!0&\\!0\\\
-\sqrt{{\gamma_{d}}{\kappa_{\text{L}}}}&\\!\sqrt{{\gamma_{d}}{\kappa_{0}}}&\\!0&\\!0&\\!-{\gamma_{d}}&\\!{\Delta_{d}}\\\
-\sqrt{{\gamma_{d}}{\kappa_{0}}}&\\!-\sqrt{{\gamma_{d}}{\kappa_{\text{L}}}}&\\!0&\\!0&\\!-{\Delta_{d}}&\\!-{\gamma_{d}}\end{bmatrix}\\!,\\!\\!$
(98a) $\displaystyle\\!\\!\\!\\!\\!B$
$\displaystyle=\\!\begin{bmatrix}{\kappa}&0&0&0&\\!\sqrt{{\gamma_{d}}{\kappa_{\text{L}}}}\\!&0\\\
0&{\kappa}&0&0&0&\\!\sqrt{{\gamma_{d}}{\kappa_{\text{L}}}}\\!\\\
0&0&0&0&0&0\\\
0&0&0&{\left(2{\bar{n}_{\text{mec}}}+1\right)}{\gamma}\\!&0&0\\\
\sqrt{{\gamma_{d}}{\kappa_{\text{L}}}}&0&0&0&{\gamma_{d}}&0\\\
0&\sqrt{{\gamma_{d}}{\kappa_{\text{L}}}}&0&0&0&{\gamma_{d}}\end{bmatrix}\\!.\\!\\!$
(98b)

These results are in agreement with the ones from the supplementary material
of [50]. The matrices are now too big to get a tractable analytical solution
so we solve the Lyapunov equation numerically instead (using python and in
particular `scipy.linalg.solve_continuous_lyapunov(A, -B)`). As previously,
$\bar{n}_{\text{fin}}$ is given by Eq. (49) and the efficiencies
$\eta_{\text{conv}}$ and $\eta_{\text{full}}$ by Eqs. (51) and (50).
$\eta_{\text{conv}}^{\prime}$ (Eq. (37)) is obtained from

$\eta_{\text{conv}}^{\prime}=\frac{-2g\bar{V}_{14}}{2g\bar{V}_{23}-\sqrt{\gamma_{d}\kappa_{\text{L}}}(\bar{V}_{15}+\bar{V}_{26})+\sqrt{\gamma_{d}\kappa_{0}}(\bar{V}_{16}-\bar{V}_{25})}.$
(99)

####  D.2.3 Beyond the white-noise approximation

Like for the standard setup in Appendix B.2.3, we can go beyond the white-
noise approximation for the mechanical noise and compute the effective phonon
number from position fluctuation spectrum. Using Eq. (D.2.1), we obtain

$S_{q}[\omega]=\absolutevalue{\chi_{\text{mec}}^{\text{eff}}[\omega]}^{2}(S_{\text{th}}[\omega]+S^{\text{Fano}}_{\text{rp}}[\omega])$
(100)

where $S_{\text{th}}[\omega]$ is given by Eq. (65) and the radiation pressure
noise spectrum reads

$S^{\text{Fano}}_{\text{rp}}[\omega]=2g^{2}(\absolutevalue{t_{\text{L}}[\omega]}^{2}+\absolutevalue{t_{\text{R}}[\omega]}^{2}).$
(101)

####  D.2.4 Weak-coupling limit

We study here the weak-coupling limit $g\ll\kappa,\Omega_{\text{mec}}$. In
this limit, illustrated in Fig. 3(c), the Stokes and anti-Stokes rates are
given by

$A^{\text{Fano}}_{\pm}=g^{2}(\absolutevalue{t_{\text{L}}[\mp\Omega_{\text{mec}}]}^{2}+\absolutevalue{t_{\text{R}}[\mp\Omega_{\text{mec}}]}^{2}).$
(102)

Therefore, at $\Delta_{d}=\Omega_{\text{mec}}$ and the optimal $\gamma_{d}$,
which is relevant for the sideband-resolved systems (1)-(3) considered in this
article (see Tab. 2), we have

$\displaystyle\\!\\!\frac{A^{\text{Fano}}_{-}}{A_{-}}$
$\displaystyle=\frac{(4\Omega_{\text{mec}})^{2}}{\Gamma\kappa_{\text{eff}}},$
(103) $\displaystyle\\!\\!\frac{A^{\text{Fano}}_{+}}{A_{+}}$
$\displaystyle=\frac{2\Gamma\kappa_{\text{eff}}(4\Omega_{\text{mec}})^{2}(4\Omega_{\text{mec}}^{2}+\kappa_{\text{eff}}^{2})}{(4\Omega_{\text{mec}})^{2}\left((4\Omega_{\text{mec}})^{2}+2\Gamma\kappa_{\text{eff}}\right)^{2}+\Gamma^{2}\kappa_{\text{eff}}^{4}},$
(104)

where $A_{\pm}$ are the rates (Eqs. (17)) for the cavity in the standard setup
of equivalent linewidth and associated loss rate $\kappa_{\text{eff}}$ (see
Sec. II.1.3). Namely, in systems (1) to (3), the use of the Fano-mirror setup
reduces the rate of the detrimental Stokes process by 10 to 12 orders of
magnitude while the rate of the anti-Stokes process that cools down the
resonator is only decreased by 2 to 4 orders of magnitude. As a consequence,
the temperature of the effective cold phonon bath is lower
($\bar{n}_{\text{opt}}$ is 8 to 10 orders of magnitude smaller) but
$\Gamma_{\text{opt}}$ is also a couple of orders of magnitude smaller. This
explains the shift of curves for the Fano-mirror setup in terms of
cooperativity in Fig. 4. Indeed, expressing $\Gamma_{\text{opt}}$ as a
function of the cooperativity, $\Gamma_{\text{opt}}=\alpha_{\text{opt}}C$, and
neglecting $\Gamma_{\text{opt}}\bar{n}_{\text{opt}}$ in Eq. (19), we obtain
$\bar{n}_{\text{fin}}\simeq\gamma\bar{n}_{\text{mec}}/(\gamma+\alpha_{\text{opt}}C)$.
The reduction of the phonon number starts to be non-negligible when $C$
becomes larger than $\gamma/\alpha_{\text{opt}}$, but $\alpha_{\text{opt}}$ is
a few orders of magnitude smaller for the Fano-mirror setup, hence the shift
in cooperativity. For a system in the resolved-sideband regime, with
$\Delta=\Omega_{\text{mec}}$, the cooperativity threshold to start seeing a
decrease in $\bar{n}_{\text{fin}}$ is $C\sim 1/\bar{n}_{\text{mec}}$ for the
standard setup and
$C\sim\Gamma\kappa_{\text{eff}}/((4\Omega_{\text{mec}})^{2}\bar{n}_{\text{mec}})$
for the Fano-mirror setup.

####  D.2.5 Optimal detuning in the non-resolved-sideband regime

In the non-sideband-resolved regime, for the standard and squeezed-light
setups, the best cooling is not obtained for a detuning $\Delta$ close to
$\kappa$. However, for the Fano-mirror setup, the optimal choice is
$\Delta_{d}\simeq 2.5\Omega_{\text{mec}}$, not
$\Delta_{d}=\kappa_{\text{eff}}$. We can understand it by looking at the
phonon number in the cold bath in the weak-coupling regime:
$\bar{n}_{\text{opt}}^{\text{Fano}}=A^{\text{Fano}}_{+}/(A^{\text{Fano}}_{-}-A^{\text{Fano}}_{+})$
(see Eq. (102)). Indeed, the parameters of the Fano-mirror setup are such that
$\gamma_{d}=4\Omega_{\text{mec}}\zeta_{0}$ and
$\zeta_{0}=4\Omega_{\text{mec}}/\kappa_{\text{eff}}$ (see Sec. II.3.3), so in
the limit $\Omega_{\text{mec}}\ll\kappa_{\text{eff}}$ and
$\gamma_{d}\ll\Gamma$, we find that the minimum of
$\bar{n}_{\text{opt}}^{\text{Fano}}$ is reached for

$\displaystyle\frac{\Delta_{d}}{\Omega_{\text{mec}}}$
$\displaystyle=\frac{{\left(3\,\sqrt{37}+26\right)}^{\frac{2}{3}}+2\,{\left(3\,\sqrt{37}+26\right)}^{\frac{1}{3}}+7}{3\,{\left(3\,\sqrt{37}+26\right)}^{\frac{1}{3}}}$
$\displaystyle\simeq 2.5.$ (105)

##  Appendix E Comparison with absorption refrigerators

Optomechanical cooling has also been studied in the context of absorption
refrigerators [30, 32], which are, like the setups we study, autonomous
thermal machines. However, this framework is different from the situation we
consider in this article as it typically assumes a three-body interaction,
where three system parts interact with three heat baths [31]. One of the baths
has to be hotter than the other and can, for example, be realized by thermal
light.

Conversely, in our case, we study a cavity optomechanical system, which is a
two-body system (cavity and mechanical resonator), where each subsystem is
coupled to a bath. Those baths are typically at the same temperature.
Furthermore, we analyze coherent or squeezed light incident to the cavity -
which are both minimum uncertainty states - and therefore interpreted as work.
The valve picture depicted in Fig. 1(a) is quite intuitive to describe the
standard optomechanical setup and can be straightforwardly adapted to the
squeezed-light and Fano-mirror setups. In contrast, the result of a quantum
absorption refrigerator is that one can cool with thermal light, which we do
not consider in our work.

The first setup studied in Ref. [30] couples the cavity mode to the motion of
a trapped atom (mechanical degree of freedom) and to its internal state (two-
level system) while the second couples the modes of two cavities to the motion
of a trapped atom. Both cases are quite different from the standard
optomechanical sideband cooling setup we study and therefore hard to compare.
We can nevertheless note that their predictions using sunlight (Fig. 7 in Ref.
[30]) brings the mechanics close to the ground state but
$\bar{n}_{\text{fin}}$ does not go well below 1 as in the levitated
optomechanical system which is the most similar system we study (see system
(3) in Fig. 4 and Ref. [27] for the experimental results).

The setup studied in Ref. [32] would correspond to our standard setup where
the coherent laser drive has been replaced by thermal light at temperature
$T_{w}$. But their results are hard to compare to ours as they do not study
the final phonon number and renormalize their efficiency by the Carnot
absorption refrigerator efficiency, which is ill-defined in our two-terminal
system with possibly equal temperatures.

## References

  * Seifert [2012] U. Seifert, Stochastic thermodynamics, fluctuation theorems and molecular machines, Rep. Prog. Phys. 75, 126001 (2012).
  * Lutz and Ciliberto [2015] E. Lutz and S. Ciliberto, Information: From Maxwell’s demon to Landauer’s eraser, Phys. Today 68, 30–35 (2015).
  * Ciliberto [2017] S. Ciliberto, Experiments in Stochastic Thermodynamics: Short History and Perspectives, Phys. Rev. X 7, 021051 (2017).
  * Klaers  _et al._ [2017] J. Klaers, S. Faelt, A. Imamoglu, and E. Togan, Squeezed Thermal Reservoirs as a Resource for a Nanomechanical Engine beyond the Carnot Limit, Phys. Rev. X 7, 031044 (2017).
  * O’Connell  _et al._ [2010] A. D. O’Connell, M. Hofheinz, M. Ansmann, R. C. Bialczak, M. Lenander, E. Lucero, M. Neeley, D. Sank, H. Wang, M. Weides, J. Wenner, J. M. Martinis, and A. N. Cleland, Quantum ground state and single-phonon control of a mechanical resonator, Nature 464, 697–703 (2010).
  * Binder  _et al._ [2018] F. Binder, L. A. Correa, C. Gogolin, J. Anders, and G. Adesso, eds.,  _Thermodynamics in the Quantum Regime: Fundamental Aspects and New Directions_ , Fundamental Theories of Physics (Springer, Cham, 2018).
  * Aspelmeyer  _et al._ [2014] M. Aspelmeyer, T. J. Kippenberg, and F. Marquardt, Cavity optomechanics, Rev. Mod. Phys. 86, 1391–1452 (2014).
  * Elouard  _et al._ [2015] C. Elouard, M. Richard, and A. Auffèves, Reversible work extraction in a hybrid opto-mechanical system, New J. Phys. 17, 055018 (2015).
  * Dong  _et al._ [2015] Y. Dong, K. Zhang, F. Bariani, and P. Meystre, Work measurement in an optomechanical quantum heat engine, Phys. Rev. A 92, 033854 (2015).
  * Monsel  _et al._ [2018] J. Monsel, C. Elouard, and A. Auffèves, An autonomous quantum machine to measure the thermodynamic arrow of time, Npj Quantum Inf. 4, 59 (2018).
  * Zhang  _et al._ [2014a] K. Zhang, F. Bariani, and P. Meystre, Quantum Optomechanical Heat Engine, Phys. Rev. Lett. 112, 150602 (2014a).
  * Zhang  _et al._ [2014b] K. Zhang, F. Bariani, and P. Meystre, Theory of an optomechanical quantum heat engine, Phys. Rev. A 90, 023819 (2014b).
  * Gelbwaser-Klimovsky and Kurizki [2015] D. Gelbwaser-Klimovsky and G. Kurizki, Work extraction from heat-powered quantized optomechanical setups, Sci. Rep. 5, 7809 (2015).
  * Dechant  _et al._ [2015] A. Dechant, N. Kiesel, and E. Lutz, All-optical nanomechanical heat engine, Phys. Rev. Lett. 114, 183602 (2015).
  * Mari  _et al._ [2015] A. Mari, A. Farace, and V. Giovannetti, Quantum optomechanical piston engines powered by heat, J. Phys. B: At. Mol. Opt. Phys. 48, 175501 (2015).
  * Bathaee and Bahrampour [2016] M. Bathaee and A. R. Bahrampour, Optimal control of the power adiabatic stroke of an optomechanical heat engine, Phys. Rev. E 94, 022141 (2016).
  * Dechant  _et al._ [2017] A. Dechant, N. Kiesel, and E. Lutz, Underdamped stochastic heat engine at maximum efficiency, Europhys. Lett. 119, 50003 (2017).
  * Bennett  _et al._ [2020] J. S. Bennett, L. S. Madsen, H. Rubinsztein-Dunlop, and W. P. Bowen, A quantum heat machine from fast optomechanics, New J. Phys. 22, 103028 (2020).
  * Brunelli  _et al._ [2018] M. Brunelli, L. Fusco, R. Landig, W. Wieczorek, J. Hoelscher-Obermaier, G. Landi, F. L. Semião, A. Ferraro, N. Kiesel, T. Donner, G. De Chiara, and M. Paternostro, Experimental Determination of Irreversible Entropy Production in out-of-Equilibrium Mesoscopic Quantum Systems, Phys. Rev. Lett. 121, 160604 (2018).
  * Rossi  _et al._ [2020] M. Rossi, L. Mancino, G. T. Landi, M. Paternostro, A. Schliesser, and A. Belenchia, Experimental Assessment of Entropy Production in a Continuously Measured Mechanical Resonator, Phys. Rev. Lett. 125, 080601 (2020).
  * Marquardt  _et al._ [2007] F. Marquardt, J. P. Chen, A. A. Clerk, and S. M. Girvin, Quantum Theory of Cavity-Assisted Sideband Cooling of Mechanical Motion, Phys. Rev. Lett. 99, 093902 (2007).
  * Wilson-Rae  _et al._ [2007] I. Wilson-Rae, N. Nooshi, W. Zwerger, and T. J. Kippenberg, Theory of Ground State Cooling of a Mechanical Oscillator Using Dynamical Backaction, Phys. Rev. Lett. 99, 093901 (2007).
  * Genes  _et al._ [2008] C. Genes, D. Vitali, P. Tombesi, S. Gigan, and M. Aspelmeyer, Ground-state cooling of a micromechanical oscillator: Comparing cold damping and cavity-assisted cooling schemes, Phys. Rev. A 77, 033804 (2008).
  * Wilson-Rae  _et al._ [2008] I. Wilson-Rae, N. Nooshi, J. Dobrindt, T. J. Kippenberg, and W. Zwerger, Cavity-assisted backaction cooling of mechanical resonators, New J. Phys. 10, 095007 (2008).
  * Chan  _et al._ [2011] J. Chan, T. P. Alegre, A. H. Safavi-Naeini, J. T. Hill, A. Krause, S. Gröblacher, M. Aspelmeyer, and O. Painter, Laser cooling of a nanomechanical oscillator into its quantum ground state, Nature 478, 89–92 (2011).
  * Teufel  _et al._ [2011] J. D. Teufel, T. Donner, D. Li, J. W. Harlow, M. S. Allman, K. Cicak, A. J. Sirois, J. D. Whittaker, K. W. Lehnert, and R. W. Simmonds, Sideband cooling of micromechanical motion to the quantum ground state, Nature 475, 359–363 (2011).
  * Delić  _et al._ [2020a] U. Delić, M. Reisenbauer, K. Dare, D. Grass, V. Vuletić, N. Kiesel, and M. Aspelmeyer, Cooling of a levitated nanoparticle to the motional quantum ground state, Science 367, 892–895 (2020a).
  * Rossi  _et al._ [2018a] M. Rossi, D. Mason, J. Chen, Y. Tsaturyan, and A. Schliesser, Measurement-based quantum control of mechanical motion, Nature 563, 53 (2018a).
  * [29] L. Magrini, P. Rosenzweig, C. Bach, A. Deutschmann-Olek, S. G. Hofer, S. Hong, N. Kiesel, A. Kugi, and M. Aspelmeyer, Optimal quantum control of mechanical motion at room temperature: Ground-state cooling, arXiv:2012.15188 arXiv:2012.15188 .
  * Mitchison  _et al._ [2016] M. T. Mitchison, M. Huber, J. Prior, M. P. Woods, and M. B. Plenio, Realising a quantum absorption refrigerator with an atom-cavity system, Quantum Sci. Technol. 1, 015001 (2016).
  * Mitchison and Potts [2018] M. T. Mitchison and P. P. Potts, Physical implementations of quantum absorption refrigerators, in  _Thermodynamics in the Quantum Regime: Fundamental Aspects and New Directions_, edited by F. Binder, L. A. Correa, C. Gogolin, J. Anders, and G. Adesso (Springer International Publishing, Cham, 2018) pp. 149–174.
  * Naseem  _et al._ [2020] M. T. Naseem, A. Misra, and Ö. E. Müstecaplıoğlu, Two-body quantum absorption refrigerators with optomechanical-like interactions, Quantum Sci. Technol. 5, 035006 (2020).
  * Poyatos  _et al._ [1996] J. F. Poyatos, J. I. Cirac, and P. Zoller, Quantum Reservoir Engineering with Laser Cooled Trapped Ions, Phys. Rev. Lett. 77, 4728–4731 (1996).
  * Brunner  _et al._ [2012] N. Brunner, N. Linden, S. Popescu, and P. Skrzypczyk, Virtual qubits, virtual temperatures, and the foundations of thermodynamics, Physical Review E 85, 051117 (2012).
  * Abah and Lutz [2014] O. Abah and E. Lutz, Efficiency of heat engines coupled to nonequilibrium reservoirs, Europhys. Lett. 106, 20001 (2014).
  * Niedenzu  _et al._ [2018] W. Niedenzu, V. Mukherjee, A. Ghosh, A. G. Kofman, and G. Kurizki, Quantum engine efficiency bound beyond the second law of thermodynamics, Nat. Commun. 9, 165 (2018).
  * Ghosh  _et al._ [2018] A. Ghosh, W. Niedenzu, V. Mukherjee, and G. Kurizki, Thermodynamic Principles and Implementations of Quantum Machines, in  _Thermodynamics in the Quantum Regime: Fundamental Aspects and New Directions_, Fundamental Theories of Physics, edited by F. Binder, L. A. Correa, C. Gogolin, J. Anders, and G. Adesso (Springer International Publishing, Cham, 2018) pp. 37–66.
  * Sánchez  _et al._ [2019] R. Sánchez, J. Splettstoesser, and R. S. Whitney, Nonequilibrium System as a Demon, Phys. Rev. Lett. 123, 216801 (2019).
  * Correa  _et al._ [2014] L. A. Correa, J. P. Palao, D. Alonso, and G. Adesso, Quantum-enhanced absorption refrigerators, Sci. Rep. 4, 3949 (2014).
  * Manzano  _et al._ [2016] G. Manzano, F. Galve, R. Zambrini, and J. M. R. Parrondo, Entropy production and thermodynamic power of the squeezed thermal reservoir, Phys. Rev. E 93, 052120 (2016).
  * Agarwalla  _et al._ [2017] B. K. Agarwalla, J.-H. Jiang, and D. Segal, Quantum efficiency bound for continuous heat engines coupled to noncanonical reservoirs, Phys. Rev. B 96, 104304 (2017).
  * Manzano [2018] G. Manzano, Squeezed thermal reservoir as a generalized equilibrium reservoir, Phys. Rev. E 98, 042123 (2018).
  * Francica  _et al._ [2017] G. Francica, J. Goold, F. Plastina, and M. Paternostro, Daemonic ergotropy: Enhanced work extraction from quantum correlations, Npj Quantum Inf. 3, 1–6 (2017).
  * Scully  _et al._ [2003] M. O. Scully, M. S. Zubairy, G. S. Agarwal, and H. Walther, Extracting Work from a Single Heat Bath via Vanishing Quantum Coherence, Science 299, 862–864 (2003).
  * Harrington  _et al._ [2019] P. M. Harrington, M. Naghiloo, D. Tan, and K. W. Murch, Bath engineering of a fluorescing artificial atom with a photonic crystal, Phys. Rev. A 99, 052126 (2019).
  * Monsel  _et al._ [2020] J. Monsel, M. Fellous-Asiani, B. Huard, and A. Auffèves, The Energetic Cost of Work Extraction, Phys. Rev. Lett. 124, 130601 (2020).
  * Asjad  _et al._ [2016] M. Asjad, S. Zippilli, and D. Vitali, Suppression of Stokes scattering and improved optomechanical cooling with squeezed light, Phys. Rev. A 94, 051801(R) (2016).
  * Clark  _et al._ [2017] J. B. Clark, F. Lecocq, R. W. Simmonds, J. Aumentado, and J. D. Teufel, Sideband cooling beyond the quantum backaction limit with squeezed light, Nature 541, 191–195 (2017).
  * Lau and Clerk [2020] H.-K. Lau and A. A. Clerk, Ground-State Cooling and High-Fidelity Quantum Transduction via Parametrically Driven Bad-Cavity Optomechanics, Phys. Rev. Lett. 124, 103602 (2020).
  * Černotík  _et al._ [2019] O. Černotík, A. Dantan, and C. Genes, Cavity Quantum Electrodynamics with Frequency-Dependent Reflectors, Phys. Rev. Lett. 122, 243601 (2019).
  * Schliesser  _et al._ [2008] A. Schliesser, R. Rivière, G. Anetsberger, O. Arcizet, and T. J. Kippenberg, Resolved-sideband cooling of a micromechanical oscillator, Nat. Phys. 4, 415–419 (2008).
  * Gardiner and Zoller [2004] C. Gardiner and P. Zoller,  _Quantum Noise - a Handbook of Markovian and Non-Markovian Quantum Stochastic Methods with Applications to Quantum Optics Crispin Gardiner Springer_ (Springer-Verlag Berlin Heidelberg, 2004).
  * Gardiner [1993] C. W. Gardiner, Driving a quantum system with the output field from another driven quantum system, Phys. Rev. Lett. 70, 2269–2272 (1993).
  * Rabl  _et al._ [2009] P. Rabl, C. Genes, K. Hammerer, and M. Aspelmeyer, Phase-noise induced limitations on cooling and coherent evolution in optomechanical systems, Phys. Rev. A 80, 063819 (2009).
  * Bowen and Milburn [2015] W. P. Bowen and G. J. Milburn,  _Quantum Optomechanics_ (CRC Press, Boca Raton. FL, 2015).
  * Thompson  _et al._ [2008] J. D. Thompson, B. M. Zwickl, A. M. Jayich, F. Marquardt, S. M. Girvin, and J. G. E. Harris, Strong dispersive coupling of a high-finesse cavity to a micromechanical membrane, Nature 452, 72–75 (2008).
  * Gröblacher  _et al._ [2009] S. Gröblacher, J. B. Hertzberg, M. R. Vanner, G. D. Cole, S. Gigan, K. C. Schwab, and M. Aspelmeyer, Demonstration of an ultracold micro-optomechanical oscillator in a cryogenic cavity, Nat. Phys. 5, 485–488 (2009).
  * Underwood  _et al._ [2015] M. Underwood, D. Mason, D. Lee, H. Xu, L. Jiang, A. B. Shkarin, K. Børkje, S. M. Girvin, and J. G. E. Harris, Measurement of the motional sidebands of a nanogram-scale oscillator in the quantum regime, Phys. Rev. A 92, 061801(R) (2015).
  * Fitzgerald  _et al._ [2021] J. M. Fitzgerald, S. K. Manjeshwar, W. Wieczorek, and P. Tassin, Cavity optomechanics with photonic bound states in the continuum, Phys. Rev. Research 3, 013131 (2021).
  * Riedinger  _et al._ [2016] R. Riedinger, S. Hong, R. A. Norte, J. A. Slater, J. Shang, A. G. Krause, V. Anant, M. Aspelmeyer, and S. Gröblacher, Non-classical correlations between single photons and phonons from a mechanical oscillator, Nature 530, 313–316 (2016).
  * Riedinger  _et al._ [2018] R. Riedinger, A. Wallucks, I. Marinković, C. Löschnauer, M. Aspelmeyer, S. Hong, and S. Gröblacher, Remote quantum entanglement between two micromechanical oscillators, Nature 556, 473 (2018).
  * Gieseler and Millen [2018] J. Gieseler and J. Millen, Levitated Nanoparticles for Microscopic Thermodynamics—A Review, Entropy 20, 326 (2018).
  * Rossi  _et al._ [2018b] M. Rossi, D. Mason, J. Chen, Y. Tsaturyan, and A. Schliesser, Measurement-based quantum control of mechanical motion, Nature 563, 53–58 (2018b).
  * Eichenfield  _et al._ [2009] M. Eichenfield, J. Chan, R. M. Camacho, K. J. Vahala, and O. Painter, Optomechanical crystals, Nature 462, 78–82 (2009).
  * Delić  _et al._ [2020b] U. Delić, D. Grass, M. Reisenbauer, T. Damm, M. Weitz, N. Kiesel, and M. Aspelmeyer, Levitated cavity optomechanics in high vacuum, Quantum Sci. Technol. 5, 025006 (2020b).
  * Eberle  _et al._ [2010] T. Eberle, S. Steinlechner, J. Bauchrowitz, V. Händchen, H. Vahlbruch, M. Mehmet, H. Müller-Ebhardt, and R. Schnabel, Quantum Enhancement of the Zero-Area Sagnac Interferometer Topology for Gravitational Wave Detection, Phys. Rev. Lett. 104, 251102 (2010).
  * Schönbeck  _et al._ [2018] A. Schönbeck, F. Thies, and R. Schnabel, 13dB squeezed vacuum states at 1550nm from 12mW external pump power at 775nm, Opt. Lett., OL 43, 110–113 (2018).
  * Ast  _et al._ [2013] S. Ast, M. Mehmet, and R. Schnabel, High-bandwidth squeezed light at 1550 nm from a compact monolithic PPKTP cavity, Opt. Express, OE 21, 13572–13579 (2013).
  * Kashiwazaki  _et al._ [2020] T. Kashiwazaki, N. Takanashi, T. Yamashima, T. Kazama, K. Enbutsu, R. Kasahara, T. Umeki, and A. Furusawa, Continuous-wave 6-dB-squeezed light with 2.5-THz-bandwidth from single-mode PPLN waveguide, APL Photonics 5, 036104 (2020).
  * Tasker  _et al._ [2021] J. F. Tasker, J. Frazer, G. Ferranti, E. J. Allen, L. F. Brunel, S. Tanzilli, V. D’Auria, and J. C. F. Matthews, Silicon photonics interfaced with integrated electronics for 9 GHz measurement of squeezed light, Nat. Photonics 15, 11–15 (2021).
  * Bui  _et al._ [2012] C. H. Bui, J. Zheng, S. W. Hoch, L. Y. T. Lee, J. G. E. Harris, and C. Wei Wong, High-reflectivity, high-Q micromechanical membranes via guided resonances for enhanced optomechanical coupling, Appl. Phys. Lett. 100, 021110 (2012).
  * Norte  _et al._ [2016] R. A. Norte, J. P. Moura, and S. Gröblacher, Mechanical Resonators for Quantum Optomechanics Experiments at Room Temperature, Phys. Rev. Lett. 116, 147202 (2016).
  * Chen  _et al._ [2017] X. Chen, C. Chardin, K. Makles, C. Caër, S. Chua, R. Braive, I. Robert-Philip, T. Briant, P.-F. Cohadon, A. Heidmann, T. Jacqmin, and S. Deléglise, High-finesse Fabry–Perot cavities with bidimensional Si3N4 photonic-crystal slabs, Light Sci. Appl. 6, e16190 (2017).
  * Gärtner  _et al._ [2018] C. Gärtner, J. P. Moura, W. Haaxman, R. A. Norte, and S. Gröblacher, Integrated Optomechanical Arrays of Two High Reflectivity SiN Membranes, Nano Lett. , 7171—7175 (2018).
  * Kini Manjeshwar  _et al._ [2020] S. Kini Manjeshwar, K. Elkhouly, J. M. Fitzgerald, M. Ekman, Y. Zhang, F. Zhang, S. M. Wang, P. Tassin, and W. Wieczorek, Suspended photonic crystal membranes in AlGaAs heterostructures for integrated multi-element optomechanics, Appl. Phys. Lett. 116, 264001 (2020).
  * Fan and Joannopoulos [2002] S. Fan and J. D. Joannopoulos, Analysis of guided resonances in photonic crystal slabs, Phys. Rev. B 65, 235112 (2002).
  * Peter  _et al._ [2005] E. Peter, P. Senellart, D. Martrou, A. Lemaître, J. Hours, J. M. Gérard, and J. Bloch, Exciton-Photon Strong-Coupling Regime for a Single Quantum Dot Embedded in a Microcavity, Phys. Rev. Lett. 95, 067401 (2005).
  * Wong  _et al._ [2004] C. W. Wong, P. T. Rakich, S. G. Johnson, M. Qi, H. I. Smith, E. P. Ippen, L. C. Kimerling, Y. Jeon, G. Barbastathis, and S.-G. Kim, Strain-tunable silicon photonic band gap microcavities in optical waveguides, Appl. Phys. Lett. 84, 1242–1244 (2004).
  * Yang  _et al._ [2007] X. Yang, C. J. Chen, C. A. Husko, and C. W. Wong, Digital resonance tuning of high-Q/Vm silicon photonic crystal nanocavities by atomic layer deposition, Appl. Phys. Lett. 91, 161114 (2007).
  * Bernard  _et al._ [2016] S. Bernard, C. Reinhardt, V. Dumont, Y.-A. Peter, and J. C. Sankey, Precision resonance tuning and design of SiN photonic crystal reflectors, Opt. Lett., OL 41, 5624–5627 (2016).
  * Liu  _et al._ [2014] Y.-C. Liu, Y.-F. Shen, Q. Gong, and Y.-F. Xiao, Optimal limits of cavity optomechanical cooling in the strong-coupling regime, Physical Review A 89, 053821 (2014).
  * Giovannetti and Vitali [2001] V. Giovannetti and D. Vitali, Phase-noise measurement in a cavity with a movable mirror undergoing quantum Brownian motion, Phys. Rev. A 63, 023812 (2001).
  * Barchielli and Vacchini [2015] A. Barchielli and B. Vacchini, Quantum Langevin equations for optomechanical systems, New J. Phys. 17, 083004 (2015).