# Clubmark: a Parallel Isolation Framework for Benchmarking and Profiling
Clustering Algorithms on NUMA Architectures ††thanks: This project has
received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement
683253/GraphInt).

Artem Lutov, Mourad Khayati and Philippe Cudré-Mauroux  eXascale Infolab,
University of Fribourg—Switzerland
Email<EMAIL_ADDRESS>
###### Abstract

There is a great diversity of clustering and community detection algorithms,
which are key components of many data analysis and exploration systems. To the
best of our knowledge, however, there does not exist yet any uniform
benchmarking framework, which is publicly available and suitable for the
parallel benchmarking of diverse clustering algorithms on a wide range of
synthetic and real-world datasets. In this paper, we introduce Clubmark, a new
extensible framework that aims to fill this gap by providing a parallel
isolation benchmarking platform for clustering algorithms and their evaluation
on NUMA servers. Clubmark allows for fine-grained control over various
execution variables (timeouts, memory consumption, CPU affinity and cache
policy) and supports the evaluation of a wide range of clustering algorithms
including multi-level, hierarchical and overlapping clustering techniques on
both weighted and unweighted input networks with built-in evaluation of
several extrinsic and intrinsic measures. Our framework is open-source and
provides a consistent and systematic way to execute, evaluate and profile
clustering techniques considering a number of aspects that are often missing
in state-of-the-art frameworks and benchmarking systems.

###### Index Terms:

benchmarking framework, clustering evaluation, parallel benchmarking,
algorithm profiling, community detection benchmarking, constraint-aware load-
balancing

##  I Introduction

Clustering is a key component of many data mining systems with many
applications encompassing statistical analysis and the exploration of
physical, social, biological and informational systems. A wide a variety of
graph algorithms have been proposed in the literature aiming to improve the
efficiency and/or accuracy of the clustering. An extensive evaluation of these
algorithms typically includes both real-world graphs with a ground truth as
well as synthetic networks of varying parameters. Moreover, the evaluation on
synthetic networks should fulfill the following desiderata:

  * •

the evaluation should be performed on various types of synthetic networks,
i.e., generating networks with diverse parameters is required to check for
bias in the clustering algorithm;

  * •

the evaluation should take into account multiple instances of each type of
synthetic network to avoid occasional bias due to particular structures in the
network;

  * •

the evaluation should consider multiple shuffles of a given network instance
to avoid bias toward a particular ordering of the input network.

The consideration of the aforementioned requirements can increase the number
of input networks by orders of magnitude (i.e., by
$network\\_types*instances*shuffles$), which is hardly practical when using
sequential execution frameworks even when considering a single clustering
algorithm. In addition, parallel executions of the algorithm on multiple
networks having diverse structures may affect the benchmarking results. In
particular,  a) the growing memory consumption of parallel processes may
utilize almost all the available physical memory and cause swapping, which
significantly affects execution time;  b) execution of cache-intensive
processes may result in conflicting CPU cache evictions and increasing page
faults, negatively affecting the execution time;  c) a bug in one algorithm or
a high computational complexity on a particular network may result in
interminable process executions.

Besides the practical considerations described above, there are also a number
of important theoretical aspects that are missing in most existing frameworks:

  * •

hierarchical and multi-level algorithms may produce various numbers of output
levels (resolutions), whose fair evaluation is not straightforward since an
algorithm with a larger number of output levels is more likely to score high
on effectiveness metrics on one of its levels;

  * •

very few extrinsic quality measures are applicable to overlapping clusters,
which causes some frameworks to apply improper measures (e.g. ARI is used for
overlaps in [1]) or let end-users apply improper measures;

  * •

most of the quality measures for overlapping clusters are not comparable to
similar measures for non-overlapping clusters (e.g. standard NMI [2] or
modularity [3] VS some overlapping NMI [4] or overlapping modularity [5, 6, 7]
implementations), which prevents direct comparison of the respective
clustering algorithms.

Finally, besides comparing to the state of the art, a benchmarking framework
could be extremely useful for the online and iterative development of new
clustering algorithms given interactive profiling capabilities. To the best of
our knowledge Clubmark is the first benchmarking framework that addresses all
of the aforementioned issues and provides a unified and fully automatic
solution for the comprehensive benchmarking and profiling of diverse
clustering algorithms on a wide variety of synthetic and real-world networks.

##  II Related Work

_WebOCD_ [8] is an open-source RESTful web framework for the development,
evaluation and analysis of _overlapping_ community detection (clustering)
algorithms. It comprises several baseline algorithms, evaluation metrics and
input data pre-processing utilities for the fast development of new clustering
algorithms inside the framework. However, WebOCD being implemented in pure
Java, is designed to execute and evaluate algorithms implemented solely in
Java with specific interfaces tightly integrated into the framework. Moreover,
the existent implementations of evaluation metrics can not be easily
integrated into WebOCD without being reimplemented in Java, which is not
always possible without a significant performance drop and time loss.

_CoDAR_ [9] is a framework for community detection algorithm evaluation and
recommendation providing a user-friendly interface and visualizations. The
framework monitors the real-time structural changes of the network during the
clustering process, adopts multiple metrics and builds a rating model for
algorithm performance evaluation. Based on this framework, the authors also
introduced a study of _non-overlapping_ community detection algorithms on
_unweighed undirected_ networks [10]. The evaluated algorithms are
reimplemented in a common code base inside the framework, which is convenient
for the uniform evaluation but limits the applicability of the framework to
the existing algorithms. Unfortunately, the framework URL provided in the
paper refers to a forbidden page, i.e. the implementation is not available to
the public anymore.

_LDBC Graphalytics_ [11] is a benchmark for large-scale graph analysis
platforms such as Giraph and GraphX. It comprises several parallel algorithms,
standard datasets, synthetic dataset generators, reference output and
evaluation of various metrics to quantify multiple kinds of system scalability
and performance variability. This benchmark provides comprehensive evaluations
of graph analysis platforms on various algorithms and datasets rather than an
evaluation of the algorithms themselves (i.e., evaluating the accuracy of the
algorithms themselves is outside the scope of this platform).

Several frameworks and toolkits have been presented to measure the quality of
the clustering, which can not be qualified as full-fledged benchmarking
frameworks but are related to benchmarking. _Circulo_ [12] is a framework for
community detection algorithms evaluation. It executes the algorithms on
preliminary uploaded input networks and then evaluates the results with
multiple intrinsic and a few extrinsic measures. The framework executes the
algorithms on the input datasets in parallel; however, the execution is
performed without any isolation and no measures are taken to prevent mutual
impact of the running processes. For example, if one of the processes consumes
most of the available physical memory, others will be swapped by the operating
system affecting the execution time. Multi-treaded processes in Circulo also
affect the execution time of the remaining running algorithms by occupying the
shared computational resources, which is unacceptable for a fair benchmarking.
A _toolkit for the parallel measurement_ of quality in non-overlapping
clusters on both distributed and shared memory machines is presented in [13].
This toolkit performs exclusively the evaluation of several intrinsic and
extrinsic quality measures without executing the clustering algorithms
themselves. The evaluation of multiple algorithms using various measures is
performed in several surveys and studies on clustering algorithms [14, 15,
16]. However, the corresponding evaluation frameworks have not been publicly
shared.

##  III System Description

Clubmark 111https://github.com/eXascaleInfolab/clubmark is an industrial-grade
benchmarking framework for parallel isolation benchmarking of clustering
algorithms. It can be applied on a wide variety of real-world and synthetic
networks, and evaluates both the efficiency and the effectiveness of the
algorithms. This framework is implemented in Python to be cross-platform and
easily extensible, and is available as a free and open source package.
Clubmark has a modular architecture with pluggable external clustering
algorithms and utilities for the evaluation and data pre/post-processing.
Additionally, we provide a ready-to-use, containerized execution
environment222https://hub.docker.com/r/luaxi/clubmark-env/ for benchmarking
with pre-installed dependencies for all algorithms and utilities since most of
them are implemented in compilable languages (C++ and C) with dependencies on
external libraries (Boost, Intel TBB, etc.). The containerization is performed
on Docker for Linux Ubuntu 16.04 LTS x64. The overall Clubmark architecture is
depicted in Fig. 2.

Figure 1: Clubmark architecture.

Figure 2: Top utility listing the executing processes during benchmarking.

###  III-A Framework Core

The framework is based on the
PyExPool333https://github.com/eXascaleInfolab/PyExPool multi process execution
pool with a constraint-aware load balancer, which isolates each executing
process. PyExPool provides a number of primitives like Job, Task and ExecPool.
Each application (clustering algorithms, evaluation utilities, etc.) is
scheduled for execution as a _Job_ instance and is transparently started under
an external tiny profiler, exectime444https://bitbucket.org/lumais/exectime/,
to trace resource consumption (execution time, processing time, peak RAM
consumption) and return code. A Job instance includes the execution arguments,
a descriptor of the executing process, a symbolic name, an optional timeout,
and provides the optional capability to restart the process on timeout. Jobs
can be wrapped into a hierarchy of _Tasks_ for the intuitive management of
related jobs. For example, a task for executing a clustering algorithm on a
specific type of synthetic networks may include subtasks with several
instances of this network type, where each instance may include jobs with
network shuffles (randomly reordered nodes and links) of the instance. Each
Task and Job provide callbacks for the start and finish events, which can be
used for the pre/post-processing activities such as notification of external
services about a process crash.

All jobs are scheduled and executed by the _ExecPool_. The execution pool
performs load balancing to adjust the number of workers (executing processes,
i.e. running jobs) in a way as to maximize the utilization of CPU and memory
resources as much as possible within the specified constrains. ExecPool
optionally provides isolation of the executing processes on the processing
units according to the specified policy. Portable Hardware Locality utility
(hwloc)555https://www.open-mpi.org/projects/hwloc/ is used to identify the
hierarchical topology of the underlying NUMA system architecture to provide
several policies for the maximization of the dedicated CPU L1/L2/L3 cache
(process execution on the physical CPU core / node) vs parallelization
(execution on a logical CPU, i.e. hardware thread). By default,  a) each
clustering algorithm is executed on the dedicated physical CPU core to
maximize CPU L1 cache usage and to provide equal computational resources for
all algorithms  b) each single-threaded evaluation utility is executed on the
dedicated logical CPU to maximize parallelization  c) each instance of the
multi-threaded evaluation utility (gecmi) is executed on the dedicated CPU
node to maximize L1/L2/L3 cache usage and thread parallelization.  The number
of worker processes in the pool is defined dynamically to satisfy  a) the
isolation policy and  b) considering the available hardware resources to
prevent system swapping while executing the processes.  For example, if the
isolation policy allows $n$ worker processes but $k<=n$ workers consume more
than the automatically defined low memory condition666The low memory condition
is defined to be a bit larger than the amount triggering a system swap,
vm.swappiness is set to 5 by default.. Then, the shortest running task among
the heaviest workers (in terms of memory consumption) is killed and postponed
(if $k>=2$) as shown in Fig. 2. The execution pool also takes care of cleaning
tables for the terminating processes to avoid zombies and catches, logs and
handles all exceptions occurred during the execution (including system
signals), handles global timeouts and feeds the WebUI component.

###  III-B Input Data

Clubmark includes the LFR benchmark [17] for undirected weighted synthetic
networks generation with ground-truth overlapping clusters and a script to
download real-world networks with ground-truth communities from
SNAP777https://snap.stanford.edu/data/#communities. Clubmark includes default
parameters to generate a wide range of diverse synthetic networks with varying
numbers of nodes, density of links and mixing parameters for nodes membership
in overlapping clusters. The input datasets are represented in a widely used
ncol format. Additionally, an accessory
PyNetConvert888https://github.com/eXascaleInfolab/PyNetConvert utility is
included to convert custom input networks from pajek and metis into the
nsl999https://github.com/eXascaleInfolab/clubmark/blob/master/formats format
(generalization of ncol). A user may include any additional un/weighed,
un/directed networks with/out ground-truth for the benchmarking from any
custom location by simply specifying them in the arguments on the benchmark
execution. Optionally, the specified number of shuffles is produced from each
input network by reordering nodes and links to avoid bias of the algorithms
toward the input order of the data.

###  III-C Clustering Algorithms

TABLE I: Clustering algorithms included in Clubmark.

Features \Algs | DaocA | Daoc | SCP | Louvain | Oslom2 | GANXiS | pSCAN | CGGC_RG | CGGCi_RG | SCD | Randcommuns
---|---|---|---|---|---|---|---|---|---|---|---
Hierarchical | + | + |  | + | + |  |  |  |  |  |
Multi-scale | + | + | + | + | + | + |  |  |  |  |
Deterministic | + | + | + |  |  |  | + |  |  |  |
Overlapping clusters | + | + | + |  | + | + | + |  |  |  |
Weighted links | + | + | + | + | + | + |  |  |  |  | +
Parameter-free | +! | +! |  | + | * | * |  | * | * | * | +
Consensus/Ensemble | + | + |  |  | + |  |  | + | + |  |

_Deterministic_ means here that the algorithm is deterministic and input-order
invariant;
+! the feature is available and does not require any tuning, still the ability
to force a manual value is provided;
* the feature is parameterized and the default value is available, however a tuning might be required to obtain good results for the given network.

Clustering algorithms can be classified by their input data type, i.e.
operating on  a) attributed graphs or  b) networks (graphs) specified by
pairwise relations.  These two types of inputs cannot be unambiguously
converted into each other. Thus, the respective two types of clustering
algorithms cannot be executed on the same input data and, hence, are not
(directly) comparable. Clubmark includes a dozen of diverse clustering
algorithms processing networks specified by pairwise relations. The included
algorithms are listed in Table I:
SCP101010http://www.lce.hut.fi/research/mm/complex/software/ [18],
Louvain111111http://igraph.org/c/doc/igraph-
Community.html%#igraph_community_multilevel [19],
Oslom2121212http://www.oslom.org/software.htm [20],
GANXiS131313https://sites.google.com/site/communitydetectionslpa/ (also known
as SLPA) [21], pSCAN141414https://github.com/eXascaleInfolab/pSCAN [22],
CGGC[i]_RG151515https://github.com/eXascaleInfolab/CGGC [23] and
SCD161616https://github.com/eXascaleInfolab/SCD [24]. We also included the
_Randcommuns_
171717https://github.com/eXascaleInfolab/clubmark/blob/master/algorithms/%randcommuns.py
algorithm, which takes a number of clusters and their sizes from the ground-
truth and randomly fills each formed template with connected nodes fetched
from the input network. Each node is fetched only once, so some templates
might end up empty and become omitted if the ground-truth clusters contain
overlaps. Clusters formed by the Randcommuns represent a useful baseline for
all algorithms providing interpretable and intuitive values of each evaluating
measure. Additional algorithms can be added just by wrapping the call of the
respective application into the execAlgName Python function located in the
benchapps.py module.

###  III-D Web Interface

Clubmark comprises a RESTful web interface (_WebUI_) for the interactive
profiling of the clustering algorithms and monitoring of the system resources.
The WebUI provides three endpoints, each of them showing a common summary on
the system resources and execution state, and also provides the following
endpoint-specific information:  a) /failureslists hierarchies of the failed
tasks with their jobs  b) /jobslists all executing and scheduled jobs  c)
/taskslists hierarchies of the executing and scheduled tasks with their jobs.
Each endpoint has an API for queries described at /apinfo and provides
features such as  a) queries filtering tasks and jobs using multiple fields
and supporting range and optional values  b) snapshots and live continuous
listing of the execution state  c) adjustment of the displayed columns for
tasks and jobs  d) selection of the outpout format (html or json for
integration with other services).  The WebUI is built using pure HTML/CSS
without any JavaScript to provide identical appearance and functionality for
both the graphical and the terminal web browsers as shown in Fig. 4-4.

Figure 3: WebUI quired from the Firefox browser as http://host/tasks.

Figure 4: WebUI quired from the w3m console browser using a simple filtering
query: $ w3m http://host/jobs?flt=tstart.

###  III-E Evaluation Measures

Clubmark evaluates both the efficiency and the effectiveness of the clustering
algorithms. The following _efficiency measures_ are evaluated for each
algorithm:  a) peak consumption of resident memory (RAM)  b) execution time
c) processing time (total amount of time spent by the algorithm on each
processing unit).  The _effectiveness measures_ comprise most common intrinsic
and extrinsic clustering quality measures. We include only the _unified_
measures suitable for both overlapping and non-overlapping clusters evaluation
and having a reasonably low complexity for large datasets evaluation, that is:
a) having at most near linear complexity on the number of links and  b) having
at most square complexity on the number of nodes.  Providing unified measures
only prevents the improper use of measures by the end-user, facilitating a
fair and direct comparison of diverse clustering algorithms.

The provided intrinsic measures include conductance [25] and modularity [3].
As the standard modularity measure is not directly applicable to overlaps
evaluation, we extend it to overlapping cases using a method for the virtual
decomposition of overlaps181818The description of the method is out of scope
of this paper, though the method is described in our open-source package. Our
decomposition technique retains the total weight and structure of the network
yielding values equal to the standard modularity when the overlap is not
present. The latter provides a fair comparison of both overlapping and non-
overlapping clusters even if the non-overlapping clusters are evaluated with
the standard modularity being reported in other papers. The provided extrinsic
measures include all known extrinsic quality measures for overlaps (fuzzy
partitions) [26] satisfying our complexity requirements. In particular, Omega
Index191919https://github.com/eXascaleInfolab/xmeasures [27] (which is a fuzzy
version of the Adjusted Rand Index [28] and is identical to the Fuzzy Rand
Index [29]), an NMI version for overlaps [30] compatible with standard NMI for
disjoint clustering and harmonic mean of F1-Score (F1h)ftn:xmeasures. The
average of F1-Score (F1a) is a commonly used evaluation measure of clustering
accuracy [31, 32] but the resulting values lower than $0.5$ are non-indicative
since the artificial clusters formed from all permutations of the input nodes
yield $F1a\rightarrow 0.5$. To make all resulting values indicative we present
F1hftn:outofs. Also, we extended the original implementation of NMI for
overlaps202020https://github.com/eXascaleInfolab/GenConvNMI with adaptive
sampling and specific optimizations to speed up its execution, in order to
apply it on large datasets. Additional quality measures can be added by
wrapping the call of the respective application into the execMeasureName
Python function located in the benchevals.py module.

###  III-F Evaluation & Results

The uniform evaluation and fair comparison of the resulting clusterings
requires some post-processing to unify their structures. In particular, multi-
level and hierarchical algorithms returing multiple levels of clusters. The
more levels the algorithm produces, the more likely it is to have a higher
evaluation. Therefore, we unify the expected number of output levels to a
fixed parameter $L$ (10 by default). If the produced number of levels is
larger than $L$, then the original results are moved to another repository
(-orig/) and symbolic links are created to the $L$ output levels sampled
uniformly from those results. Algorithms producing a single output level
typically have a resolution parameter (density, clique rank, etc.), which can
optionally be leveraged to produce $L$ output clusterings.

Thus, each clustering algorithm produces up to $L$ clusterings for each
shuffle of each network instance of each network type forming the following
structure of output directories: ` <algname>/ <nettype>[^<instance>]/
<shuffle>/ ` with up to $L$ clusterings in the <shuffle>/. The ground-truth is
specified per network instance. The quality evaluation of the resulting
clusterings is performed by the measures specified by the user and saved into
an HDF5 hierarchical structure. Afterwards, the aggregated final results are
computed for each measure:  1) the average value and variance are calculated
for all shuffles of each instance and  2) these results are averaged for all
instances of each network type.  The efficiency evaluations reported by the
exectime for each clustering algorithm execution on each shuffle are
aggregated similarly to the quality evaluations.

##  IV Demonstration Objectives

Clubmark benchmarking framework is open sources and is available for free for
both non-commercial and commercial purposes from
https://github.com/eXascaleInfolab/clubmark. The objective of our
demonstration is to let the audience experience the deployment, execution and
extension of our proposed benchmarking framework, as well as the online
profiling of a clustering algorithms via the provided web interface. The
resulting experience should let the user understand how Clubmark helps in  a)
facilitating comprehensive evaluations of emerging clustering algorithms, and
b) speeding up their development thanks to fast and convenient profiling tools
on diverse input networks.

Clubmark Deployment. We will demonstrate the deployment of Clubmark on cloud-
hosted servers in two scenarios:  a) directly on the host and  b) using a
containerized environment from the Docker hub.

Benchmarking Execution. We will demonstrate a typical execution of the
benchmarking cycle for the clustering algorithms selected by the user on both
synthetic and a predifined set of real-world networks. The synthetic networks
will be generated using default framework configurations. We plan to discuss
and demonstrate all essential aspects of our framework. The participants will
hence experience:  a) how to apply optional pre-processing steps (i.e.
synthetic networks generation and shuffling)  b) how to specify execution
constraints for the benchmarking  c) how a uniform input is created from
distinct datasets, considering the availability of distinct instances and
shuffles for each network  d) what kind of clusterings are generated by the
diverse clustering algorithms  e) how results of the diverse clustering
algorithms are unified for the subsequent evaluation  f) how the parallel
evaluation is performed considering both single and multi-threaded
applications  g) how the evaluation results are aggregated and finally stored.

We will also demonstrate several built-in utilities to illustrate  a) the load
of the server during execution  b) the structure of the input and intermediate
results  c) the structure of the generating logs  d) the structure of the
efficiency results produced by an external application (exectime)  e) the
structure of the final results in the HDF5 storage.

Algorithms Profiling. We will demonstrate the available endpoints of the Web
interface and encourage users to perform various queries to  a) experience the
REST WebAPI and its capabilities  b) perform a simple profiling of the
algorithms being executed  c) understand how load-balancing and isolation work
for clustering algorithms executed in parallel  d) monitor for potential
issues and failed tasks when executing clustering algorithms.

Framework Extensions. Finally, we plan to demonstrate how to seamlessly extend
Clubmark with  a) new clustering algorithms,  b) multiple versions of a single
clustering algorithm (which is a useful feature when designing a new
clustering algorithm) and  c) new evaluation measures  implemented as external
applications and in various languages.

This overall demonstration will make users aware of the latest methodologies
and common pitfalls in clustering evaluation, and present an extensive
overview of our Clubmark platform for performance evaluation and profiling.

## References

  * [1] V. Melnykov and R. Maitra, “Carp: Software for fishing out good clustering algorithms,” _J. Mach. Learn. Res._ , vol. 12, pp. 69–73.
  * [2] L. Danon, A. Díaz-Guilera, J. Duch, and A. Arenas, “Comparing community structure identification,” _Journal of Statistical Mechanics: Theory and Experiment_ , vol. 9, p. 8, Sep. 2005.
  * [3] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” _Phys. Rev. E_ , vol. 69, no. 2, p. 026113, 2004.
  * [4] A. F. McDaid, D. Greene, and N. J. Hurley, “Normalized mutual information to evaluate overlapping community finding algorithms,” _CoRR_ , vol. abs/1110.2515, 2011.
  * [5] S. Zhang, R.-S. Wang, and X.-S. Zhang, “Identification of overlapping community structure in complex networks using fuzzy c-means clustering,” _Physica A: Statistical Mechanics and its Applications_ , vol. 374, no. 1, pp. 483–490, 2007.
  * [6] V. Nicosia, G. Mangioni, V. Carchiolo, and M. Malgeri, “Extending the definition of modularity to directed graphs with overlapping communities,” _J Stat Mech._ , vol. 3, p. 24, Mar. 2009.
  * [7] A. Lázár, D. Abel, and T. Vicsek, “Modularity measure of networks with overlapping communities,” _EPL (Europhysics Letters)_ , vol. 90, no. 1, p. 18001, 2010.
  * [8] M. Shahriari, S. Krott, and R. Klamma, “Webocd: A restful web-based overlapping community detection framework,” ser. i-KNOW ’15. ACM.
  * [9] X. Ying, C. Wang, M. Wang, J. X. Yu, and J. Zhang, “Codar: Revealing the generalized procedure & recommending algorithms of community detection,” ser. SIGMOD ’16. ACM, 2016, pp. 2181–2184.
  * [10] M. Wang, C. Wang, J. X. Yu, and J. Zhang, “Community detection in social networks: An in-depth benchmarking study with a procedure-oriented framework,” _Proc. VLDB Endow._ , vol. 8, pp. 998–1009, Jun. 2015.
  * [11] A. Iosup, T. Hegeman, W. L. Ngai, S. Heldens, A. Prat-Pérez, T. Manhardto, H. Chafio, M. Capotă, N. Sundaram, M. Anderson, I. G. Tănase, Y. Xia, L. Nai, and P. Boncz, “Ldbc graphalytics: A benchmark for large-scale graph analysis on parallel and distributed platforms,” _Proc. VLDB Endow._ , vol. 9, pp. 1317–1328, Sep. 2016.
  * [12] P. Mazzuca and Y. T, “Circulo: A Community Detection Evaluation Framework,” Feb. 2015. [Online]. Available: https://www.lab41.org/circulo-a-community-detection-evaluation-framework/
  * [13] M. Chen, S. Liu, and B. K. Szymanski, “Parallel toolkit for measuring the quality of network community structure.” in _ENIC_ , 2014, pp. 22–29.
  * [14] S. Harenberg, G. Bello, L. Gjeltema, S. Ranshous, J. Harlalka, R. Seay, K. Padmanabhan, and N. Samatova, “Community detection in large-scale networks: A survey and empirical evaluation,” _WIREs Comput. Stat._ , vol. 6, pp. 426–439, Nov. 2014.
  * [15] J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground-truth,” _Knowl. Inf. Syst._ , vol. 42, pp. 181–213, Jan. 2015.
  * [16] M. Hascoët and G. Artignan, “Evaluation of Clustering Algorithms: a methodology and a case study,” Tech. Rep. RR-14008, Sep. 2014.
  * [17] A. Lancichinetti and S. Fortunato, “Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities.” _Phys. Rev. E_ , vol. 80 1 Pt 2, p. 016118, 2009.
  * [18] J. M. Kumpula, M. Kivelä, K. Kaski, and J. Saramäki, “Sequential algorithm for fast clique percolation,” _Phys. Rev. E_ , vol. 78, no. 2, p. 026109, 2008.
  * [19] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” _J Stat Mech._ , vol. 2008, no. 10, p. P10008, oct 2008.
  * [20] A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato, “Finding Statistically Significant Communities in Networks,” _PLoS ONE_ , vol. 6, p. 18961, Apr. 2011.
  * [21] J. Xie, B. K. Szymanski, and X. Liu, “Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process,” in _ICDM 2011 Workshop on DMCCI_ , pp. 344–349.
  * [22] L. Chang, W. Li, X. Lin, L. Qin, and W. Zhang, “pscan: Fast and exact structural graph clustering,” in _ICDE’16_ , pp. 253–264.
  * [23] M. Ovelgönne and A. Geyer-Schulz, “An ensemble learning strategy for graph clustering,” in _Graph Partitioning and Graph Clustering - 10th DIMACS Workshop_ , vol. 588, 2013, pp. 187–206.
  * [24] A. Prat-Pérez, D. Dominguez-Sal, and J.-L. Larriba-Pey, “High quality, scalable and parallel community detection for large real graphs,” ser. WWW ’14. ACM, 2014, pp. 225–236.
  * [25] R. Kannan, S. Vempala, and A. Vetta, “On clusterings: Good, bad and spectral,” _J. ACM_ , vol. 51, no. 3, pp. 497–515, May 2004.
  * [26] S. Gregory, “Fuzzy overlapping communities in networks,” _J Stat Mech._ , vol. 2011, no. 02, p. P02017, 2011.
  * [27] L. M. Collins and C. W. Dent, “Omega: A general formulation of the rand index of cluster recovery suitable for non-disjoint solutions,” _Multivariate Behavioral Research_ , vol. 23, no. 2, pp. 231–242, 1988.
  * [28] L. Hubert and P. Arabie, “Comparing partitions,” _Journal of Classification_ , vol. 2, no. 1, pp. 193–218, Dec 1985.
  * [29] E. Hullermeier and M. Rifqi, “A fuzzy variant of the rand index for comparing clustering structures,” ser. IFSA-EUSFLAT 2009.
  * [30] A. V. Esquivel and M. Rosvall, “Comparing network covers using mutual information,” _CoRR_ , vol. abs/1202.0425, 2012.
  * [31] J. Yang and J. Leskovec, “Overlapping community detection at scale: A nonnegative matrix factorization approach,” ser. WSDM ’13. ACM, pp. 587–596.
  * [32] A. Prat-Pérez, D. Dominguez-Sal, and J.-L. Larriba-Pey, “High quality, scalable and parallel community detection for large real graphs,” ser. WWW’14. ACM, pp. 225–236.


# Passage summarization with recurrent models
for Audio – Sheet Music Retrieval

###### Abstract

Many applications of cross-modal music retrieval are related to connecting
sheet music images to audio recordings. A typical and recent approach to this
is to learn, via deep neural networks, a joint embedding space that correlates
short fixed-size snippets of audio and sheet music by means of an appropriate
similarity structure. However, two challenges that arise out of this strategy
are the requirement of strongly aligned data to train the networks, and the
inherent discrepancies of musical content between audio and sheet music
snippets caused by local and global tempo differences. In this paper, we
address these two shortcomings by designing a cross-modal recurrent network
that learns joint embeddings that can summarize longer passages of
corresponding audio and sheet music. The benefits of our method are that it
only requires weakly aligned audio – sheet music pairs, as well as that the
recurrent network handles the non-linearities caused by tempo variations
between audio and sheet music. We conduct a number of experiments on synthetic
and real piano data and scores, showing that our proposed recurrent method
leads to more accurate retrieval in all possible configurations.

##  1 Introduction

The abundance of music-related content in various digital formats, including
studio and live audio recordings, scanned sheet music, and metadata, among
others, calls for efficient technologies for cross-linking between documents
of different modalities. In this work, we explore a cross-modal task referred
to as audio – sheet music passage retrieval. We define it as follows: given an
audio fragment as a query, search within an image database and retrieve the
corresponding sheet music passage; or vice versa, find the appropriate
recording fragment given a query in the form of some snippet of (scanned)
sheet music.

A fundamental step in audio–sheet music retrieval concerns defining a suitable
shared representation that permits the comparison between items of different
modalities in a convenient and effective way. The conventional approaches for
linking audio recordings to their respective printed scores are based on
handcrafted mid-level representations [1, 2]. These are usually pitch-class
profiles, like chroma-based features [3, 4], symbolic fingerprints [5], or the
bootleg score [6, 7], which is a coarse mid-level codification of the main
note-heads in a sheet music image. However extracting such representations
requires a series of pre-processing stages that are prone to errors, for
example optical music recognition on the sheet music side [8, 9, 10], and
automatic music transcription on the audio part [11, 12, 13].

A promising approach [14, 15] has been proposed to eliminate these problematic
pre-processing steps by learning a shared low-dimensional embedding space
directly from audio recordings and printed scores. This is achieved by
optimizing a cross-modal convolutional network (CNN) to project short snippets
of audio and sheet music onto a latent space, in which the cosine distances
between semantically related snippets are minimized, whereas non-related items
of either modality are projected far from each other. Then the retrieval
procedure is reduced to simple nearest-neighbour search in the shared
embedding space, which is a simple and fast algorithm.

Figure 1: Distribution of system durations in around 40,000 examples from the
MSMD. More than 25% of the passages are longer than ten seconds. Figure 2:
Diagram of the proposed network. Two independent pathways are trained to
encode sheet music (a) and audio (b) passages by minimizing a contrastive loss
function (c).

A first limitation of this strategy relates to its supervised nature: it
requires strongly-aligned data in order to generate matching audio–sheet
snippet pairs for training, which means fine-grained mappings between note
onsets and corresponding note positions in the score. Obtaining such
annotations is tedious and time-consuming, and also requires specialized
annotators with musical training. As a result, embedding learning approaches
have been trained with synthetic data, in which recordings, sheet music
images, and their respective alignments are rendered from symbolic scores.
This leads to poor generalization in scenarios with real music data, as shown
in [16].

Moreover, the snippets in both modalities have to be fixed in size, meaning
that the amount of actual musical content in the fragments can vary
considerably depending on note durations and the tempo in which the piece is
played. For example, a sheet excerpt with longer notes played slowly would
correspond to a considerably larger duration in audio than one with short
notes and a faster tempo. This leads to generalization problems caused by
differences between what the model sees during training and test time; [17]
attempted to address this limitation by introducing a soft-attention mechanism
to the network.

In this paper we address the two aforementioned limitations by proposing a
recurrent cross-modal network that learns compact, fixed-size representations
from longer variable-length fragments of audio and sheet music. By removing
the fixed-size fragment constraint, we can adjust the lengths of fragments
during training so that cross-modal pairs can span the same music content,
leading to a more robust representation. Moreover, by operating with longer
music passages, it is possible to rely solely on weakly-annotated data for
training, since we now require only the starting and ending positions of
longer-context music fragments within music documents, in order to extract
audio–sheet passages to prepare a train set. This is a remarkable advantage
compared for example to other approaches based on [14], where fine-detailed
alignments are indispensable to generate short audio–sheet snippet pairs.

The rest of the paper is structured as follows. In Section 2 we describe the
model proposed to learn joint representations from cross-modal passages.
Section 3 presents a series of experiments on artificial and real data and
Section 4 summarizes and concludes the work.

##  2 Audio–sheet passage retrieval

For the purposes of this paper, and in order to be able to use our annotated
corpora for the experiments, we define a "passage" as the musical content
corresponding to one line of sheet music (also known as a "system"). System-
level annotation of scores are much easier to come by than note-precise score-
recording alignments, making it relatively easy to compile large collections
of training data for our approach. Our definition of passages resembles that
of "musical themes", which has been used under a cross-modal retrieval
scenario with symbolic queries in a number of previous works [18, 19]. To
illustrate the temporal discrepancies between passages, we show in Figure 1
the distribution of time duration of the systems from all pieces of the MSMD
dataset [14] (later we will elaborate more on this database). In this dataset,
we observe that systems can cover from less than five to more than 25 seconds
of musical audio.

Audio CNN encoder | Sheet-Image CNN encoder
---|---
input: $92\times 20$ | input: $160\times 180$
2x Conv($3$, pad-1)-$24$ \- BN | 2x Conv($3$, pad-1)-$24$ \- BN
MaxPooling(2) | MaxPooling(2)
2x Conv($3$, pad-1)-$48$ \- BN | 2x Conv($3$, pad-1)-$48$ \- BN
MaxPooling(2) | MaxPooling(2)
2x Conv($3$, pad-1)-$96$ \- BN | 2x Conv($3$, pad-1)-$96$ \- BN
MaxPooling(2) | MaxPooling(2)
2x Conv($3$, pad-1)-$96$ \- BN | 2x Conv($3$, pad-1)-$96$ \- BN
MaxPooling(2) | MaxPooling(2)
Conv($1$, pad-0)-$32$ \- BN | Conv($1$, pad-0)-$32$ \- BN
FC($32$) | FC($32$)

Table 1: Overview of the two convolutinal encoders. Each side is responsible
for their respective modality. Conv($3$, pad-1)-$24$: 3$\times$3 convolution,
24 feature maps and zero-padding of 1. BN: Batch normalization [20]. We use
ELU activation functions [21] after all convolutional and fully-connected
layers.

This important temporal aspect motivates us to propose the network depicted in
Figure 2 to learn a common latent representation from pairs of audio–sheet
passages. The architecture has two independent recurrent-convolutional
pathways, which are responsible for encoding sheet music (Figure 2a) and audio
(Figure 2b) passages. The key component of this approach is the introduction
of two recurrent layers that, inspired by traditional sequence-to-sequence
models [22], are trained to summarize a variable-length sequences into context
vectors, that we conveniently refer to as embedding vectors.

Defining a pair of corresponding passages in the form of image (sheet music)
and log-magnitude spectrogram (audio) as $\mathbf{X}$ and $\mathbf{Y}$,
respectively, two sequences
$(\mathbf{x_{1}},\mathbf{x_{2}},\dots,\mathbf{x_{N}})$ and
$(\mathbf{y_{1}},\mathbf{y_{2}},\dots,\mathbf{y_{M}})$ are generated by
sequentially cutting out short snippets from $\mathbf{X}$ and $\mathbf{Y}$.
The shapes of the short sheet and audio snippets are respectively $160\times
180$ (pixels)111In our approach, all sheet music pages are initially re-scaled
to a $1181\times 835$ resolution and $92\times 20$ (frequency bins $\times$
frames), which corresponds to one second of audio. After that, each individual
snippet is encoded by a VGG-style CNN [23] into a 32-dimensional vector, as
shown in Figure 2, generating two sequences of encoded snippets, one for the
audio passage, and the other for the sheet passage (note that each modality
has its own dedicated CNN encoder). The architecture of the CNN encoders are
detailed in Table 1.

Then each sequence is fed to a recurrent layer in order to learn the spatial
and temporal relations between subsequent snippets, which are inherent in
music. After experimenting with two typical simple recurrent layers, namely
long short-term memory cells (LSTM) [24] and gated recurrent units (GRU) [25],
we observed on average better results with GRUs, and we decided for the latter
for our architecture. Each of the two GRUs is designed with 128 hidden units,
where the hidden state of each GRU after the last step is the context vector
that summarizes the passages. Finally a fully connected layer (FC) is applied
over each context vector, in order to encode the final passage embeddings
$(\mathbf{x}_{\mathrm{emb}},\mathbf{y}_{\mathrm{emb}})$ with the desired
dimension.

During training, a triplet (contrastive) loss function [26] is used to
minimize the distances between embeddings from corresponding passages of audio
and sheet music and maximize the distance between non-corresponding ones.
Defining $\mathrm{d}(\cdot)$ as the cosine distance, the loss function is
given by:

$\mathcal{L}=\sum_{k=1}^{K}\mathrm{max}\Bigl{\\{}0,\alpha+\mathrm{d}\Bigl{(}\mathbf{x}_{\mathrm{emb}},\mathbf{y}_{\mathrm{emb}}\Bigl{)}-\mathrm{d}\Bigl{(}\mathbf{x}_{\mathrm{emb}},\mathbf{y}^{k}_{\mathrm{emb}}\Bigl{)}\Bigl{\\}}\mathrm{,}$
(1)

where $\mathbf{y}^{k}_{\mathrm{emb}}$ for $k\in{1,2,\ldots,K}$ are contrastive
(negative) examples from $K$ non-matching passages in the same training mini-
batch. This contrastive loss is applied to all
$(\mathbf{x}_{\mathrm{emb}},\mathbf{y}_{\mathrm{emb}})$ pairs within each
mini-batch iteration. The margin parameter $\alpha\in\mathbb{R}_{+}$, in
combination with the $\mathrm{max}\left\\{\cdot\right\\}$ function, penalizes
matching snippets that were poorly embedded.

For the sake of simplicity, we leave the remaining details concerning the
design of the networks, such as learning hyper-parameters, to our repository
where our method will be made publicly
available,222https://github.com/luisfvc/lcasr as well as the trained models
derived in this work.

##  3 Experiments

In this section we conduct experiments on different audio–sheet music
scenarios. We first elaborate on the main dataset used for training and
evaluation and define the steps of the passage retrieval task. Then we select
four experiment setups and present the results.

We train our models with the Multi-Modal Sheet Music Dataset (MSMD) [14],
which is a collection of classical piano pieces with multifaceted data,
including score sheets (PDF) engraved via Lilypond333http://www.lilypond.org
and corresponding audio recordings rendered from MIDI with several types of
piano soundfonts. With over 400 pieces from over 50 composers, including Bach,
Beethoven and Schubert, and covering more than 15 hours of audio, the MSMD has
audio–sheet music alignments which allow us to obtain corresponding cross-
modal pairs of musical passages. From the MSMD we were able to derive roughly
5,000 audio–sheet passages for training, which is scaled up to around 40,000
different pairs after data augmentation: audios are re-rendered with different
soundfonts and have their tempo changed between 90% and 110%. Then we generate
a test set of 534 pairs from a separate set of music pieces, that were
rendered with a soundfont that was not seen during training. Later, in 3.2, we
will also consider real scanned scores and real audio recordings.

To perform cross-modal passage retrieval, we first embed all audio–sheet pairs
in the shared space using our trained model depicted in Figure 2. Then the
retrieval is conducted by using the cosine distance and nearest-neighbor
search within the space. For example, in case of using an audio passage as a
query to find the appropriate sheet music fragment, the pairwise cosine
distances between the query embedding and all the sheet music passage
embeddings are computed. Finally, the retrieval results are obtained by means
of a ranked list through sorting the distances in ascending order.

As for evaluation metrics, we look at the Recall@k (R@k), Mean Reciprocal Rank
(MRR) and the Median Rank (MR). The R@k measures the ratio of queries which
were correctly retrieved within the top $k$ results. The MRR is defined as the
average value of the reciprocal rank over all queries. MR is the median
position of the correct match in the ranked list.

###  3.1 Experiment 1: Embedding dimension

In the first round of experiments, we investigate the effect of the final
embedding dimension in the retrieval task. We consider the values in
$\\{16,32,64,128,256,512,1024\\}$ and train the model of Figure 2 with the
same hyperparameters. Then we perform the retrieval task in both search
directions: audio-to-sheet music (A2S) and sheet music-to-audio (S2A).

Figure 3: Mean Reciprocal Rank (MRR) for different embedding dimensions,
evaluated in both search directions. Table 2: Results of audio–sheet music
passage retrieval, performed in both search directions, and evaluated in three
types of data: (I) fully synthetic, (II) partially real and (III) entirely
real. Boldfaced rows represent the best performing model per dataset.

| Audio-to-Score (A2S) | Score-to-Audio (S2A)
---|---|---
| R@1 | R@10 | R@25 | MRR | MR | R@1 | R@10 | R@25 | MRR | MR
I MSMD (Fully synthetic)
BL | 47.56 | 81.68 | 90.80 | 0.592 | 1 | 51.37 | 83.51 | 92.59 | 0.628 | 1
RNN | 51.12 | 84.46 | 92.88 | 0.627 | 1 | 54.30 | 85.95 | 94.94 | 0.670 | 1
RNN-FT | 55.27 | 87.98 | 95.02 | 0.651 | 1 | 56.32 | 87.12 | 96.44 | 0.697 | 1
RNN-FT-CCA | 60.04 | 89.66 | 97.73 | 0.692 | 1 | 62.11 | 91.44 | 98.41 | 0.734 | 1
RNN-FZ | 50.76 | 84.20 | 92.11 | 0.619 | 1 | 52.90 | 85.21 | 94.12 | 0.658 | 1
RNN-FZ-CCA | 52.67 | 86.46 | 92.88 | 0.635 | 1 | 55.67 | 86.30 | 95.34 | 0.682 | 1
II RealScores_Synth (Sheet music scans and synthetic recordings)
BL | 20.19 | 55.47 | 74.99 | 0.343 | 7 | 25.15 | 70.27 | 83.11 | 0.391 | 5
RNN | 25.09 | 61.24 | 78.27 | 0.374 | 5 | 30.15 | 72.47 | 86.89 | 0.439 | 3
RNN-FT | 28.87 | 66.41 | 81.32 | 0.447 | 4 | 33.98 | 75.47 | 88.51 | 0.462 | 2
RNN-FT-CCA | 33.36 | 69.49 | 83.88 | 0.481 | 3 | 37.35 | 79.22 | 89.95 | 0.538 | 1
RNN-FZ | 25.83 | 62.02 | 79.74 | 0.376 | 5 | 31.45 | 74.87 | 87.26 | 0.442 | 3
RNN-FZ-CCA | 26.82 | 63.33 | 80.19 | 0.391 | 5 | 33.55 | 75.71 | 88.79 | 0.467 | 2
III RealScores_Rec (Sheet music scans and real recordings)
BL | 15.67 | 31.46 | 48.12 | 0.226 | 29 | 18.30 | 36.71 | 54.94 | 0.266 | 18
RNN | 19.11 | 35.98 | 53.65 | 0.278 | 21 | 22.76 | 39.95 | 57.47 | 0.303 | 15
RNN-FT | 22.39 | 39.53 | 57.19 | 0.338 | 18 | 26.76 | 42.77 | 59.38 | 0.371 | 7
RNN-FT-CCA | 26.62 | 44.81 | 60.01 | 0.362 | 7 | 29.84 | 46.71 | 60.88 | 0.435 | 4
RNN-FZ | 17.65 | 33.12 | 52.98 | 0.252 | 22 | 19.13 | 37.51 | 55.57 | 0.277 | 17
RNN-FZ-CCA | 18.38 | 35.81 | 54.51 | 0.279 | 21 | 22.30 | 38.95 | 58.82 | 0.285 | 16

Figure 3 presents the MRR of the snippet retrieval results evaluated on the
534 audio–sheet music passage pairs of the MSMD testset. A first and
straightforward observation is that in all cases the S2A direction indicates
better retrieval quality. We observe the performance increasing together with
the embedding dimensionality until it stagnates at 64-D, and the MRR does not
improve on average for higher-dimensional embeddings. For this reason, we
select the model that generates 64-dimensional embeddings as the best one,
which will be evaluated more thoroughly in the next experiments.

###  3.2 Experiment 2: Real data and improved models

In this section, we conduct an extensive series of experiments comparing our
proposed recurrent network and some improved models thereof with baseline
methods, and extend the evaluation to real-world piano data.

Given that our training data are entirely synthetic, we wish to investigate
the generalization of our models from synthetic to real data. To this end, we
evaluate on three datasets: on a (1) fully artificial one, and on datasets
consisting (2) partially and (3) entirely of real data. For (1) we use the
test split of MSMD and for (2) and (3) we combine the Zeilinger and Magaloff
Corpora [27] with a collection of commercial recordings and scanned scores
that we have access to. These data account for more than a thousand pages of
sheet music scans with mappings to both MIDI files and over 20 hours of
classical piano recordings. Then, besides the MSMD (I), we define two
additional evaluation sets: (II) RealScores_Synth: a partially real set, with
scanned (real) scores of around 300 pieces aligned to synthesized MIDI
recordings. And (III) RealScores_Rec: an entirely real set, with scanned
(real) scores of around 200 pieces and their corresponding real audio
recordings.

As a baseline (BL), we implement the method from [14] and adapt their short-
snippet-voting strategy to identify and retrieve entire music recordings and
printed scores so it can operate with passages.444The reasons we did not use
the attention-based method from [17] as a baseline comparison are twofold.
First we intend to compare the exact original snippet embedding architecture
with and without a recurrent encoder, and adding the attention mechanism to a
baseline model would introduce a significant number of additional trainable
parameters, making the comparison unfair. Second, the purpose of the attention
model is to compensate the musical content discrepancy between audio and sheet
snippets, which is not the case for musical passages as defined here: pairs of
audio–sheet music passages comprise the exact musical content (that is the
reason why fragments are not fixed in time). In essence, short snippets are
sequentially cut out from a passage query and embedded, and are compared to
all embedded snippets which were selected from passages in a search dataset of
the counterpart modality, resulting in a ranked list based on the cosine
distance for each passage snippet. Then the individual ranked lists are
combined into a single ranking, in which the passage with most similar
snippets is retrieved as the best match.

Additionally, we investigate whether our models can benefit from pre-trained
cross-modal embeddings. Since both CNN encoders of our proposed network
architecture (see Figure 2) are the same as in [14], we re-designed the
baseline cross-modal network to accommodate our snippet dimensions ($160\times
180$ and $92\times 20$, for sheet and audio, respectively) and trained a
short-snippet embedding model also with the MSMD, as a pre-training step, and
then loaded the two CNN encoders of our recurrent network with their
respective pre-trained weights before training. Our hypothesis is that, by
initializing the CNN encoders with parameters that were optimized to project
short pairs of matching audio–sheet snippets close together onto a common
latent space, models with better embedding capacity can be obtained. After
loading the two CNNs with pre-trained weights, we can either freeze (FZ) them
during training or just fine-tune (FT) on them. Therefore, in our experiments,
we refer to these modifications of our proposed vanilla recurrent network
(RNN) as RNN-FZ and RNN-FT, respectively.

Moreover, an additional CCA (canonical correlation analysis) layer [28] is
used in [14] to increase the correlation of corresponding pairs in the
embedding space. This CCA layer is refined in a post-training step, and we
investigate whether this refinement process is beneficial to our network. In
our experiments we refer to models that were initialized with pre-trained
parameters from networks that had their CCA layer refined as RNN-FZ-CCA and
RNN-FT-CCA.

Table 2 presents the results for all data configurations and models defined
previously. To keep our experiments consistent and the comparison fair, we
randomly select 534 passage pairs from sets (II) and (III) to create the
retrieval scenario for their respective experiments.

An evident observation from the table is the considerable performance drop as
we transition from synthetic to real music data. For all the models, the MRR
drops at least 0.2 points to a partially real test set, and drops more than
0.3 points when moving to the entirely real data. Moreover, as mentioned in
Subsection 3.1, the passage retrieval metrics of the S2A direction are better
than those of A2S for all models and scenarios.

Our recurrent model RNN and its variants outperform the baseline approach in
all retrieval scenarios for all evaluation metrics. In our findings, we did
not see noticeable improvements when the pre-loaded encoders were frozen
during training. In fact, for some configurations (scenarios I and III) the
evaluation metrics were slightly worse than those from the vanilla RNN model.
When the CNN encoders are pre-loaded and enabled for fine-tuning, we observe
the largest improvements over RNN and subsequently over BL. Moreover, the
models initialized with pre-trained weights from CCA-refined networks (RNN-FT-
CCA) achieved the best overall results, for all test datasets and search
directions.

In addition to the overall absolute improvements, we observe that the
performance drop between synthetic and real datasets shrinks with our proposed
models, specially with RNN-FT-CCA. In comparison with the baseline, the I-to-
III MRR gap is reduced by 0.036 and 0.06 points in the directions A2S and S2A,
respectively.

The results we obtained and summarized in Table 2 indicate that introducing a
recurrent layer to learn longer contexts of musical content is beneficial in
our cross-modal retrieval problem. However the real-data generalization
problem is still evident, and in Section 4 we discuss potential solutions to
address such issues.

###  3.3 Experiment 3: Global tempo variations

In this experiment, we investigate the robustness of our system to global
tempo changes. To this end, the pieces of the MSMD test dataset are re-
rendered with different tempo ratios $\rho\in\\{0.5,0.66,1,1.33,2\\}$
($\rho=0.5$ means the tempo was halved and $\rho=2$ stands for doubling the
original tempo). A similar study was conducted in [17] for retrieval of short
audio–sheet snippets.

Table 3 summarizes the MRR values obtained for each tempo re-rendering, where
the baseline method is compared with our proposed recurrent model. We notice
the general trend that the MRR gets worse as the tempo ratio is farther from
$\rho=1$ (original tempo). This behavior is somehow expected because the new
tempo renditions are more extreme than the tempo changes the model has seen
during training.

Besides the better MRR values of the proposed network, an important
improvement concerns the performance drop when changing from $\rho=1$ to
$\rho=0.5$ (slower renditions). The MRR gap between these tempo ratios drops
from 0.12 to 0.1 and from 0.09 to 0.07 points for the A2S and S2A directions,
respectively, when comparing our network with the baseline. This indicates
that the recurrent model is more robust to global tempo variations and can
operate well with longer audio passages.

Model | $\rho=0.5$ | $\rho=0.66$ | $\rho=1$ | $\rho=1.33$ | $\rho=2$
---|---|---|---|---|---
BL | 0.47 | 0.54 | 0.59 | 0.52 | 0.40
RNN | 0.53 | 0.59 | 0.63 | 0.58 | 0.43

(a) A2S search direction.

Model | $\rho=0.5$ | $\rho=0.66$ | $\rho=1$ | $\rho=1.33$ | $\rho=2$
---|---|---|---|---|---
BL | 0.54 | 0.59 | 0.63 | 0.56 | 0.48
RNN | 0.60 | 0.64 | 0.67 | 0.61 | 0.50

(b) S2A search direction.

Table 3: MRR for different tempo renderings of the test pieces of MSMD in both
(a) audio-to-sheet and (b) sheet-to-audio retrieval directions. We evaluate
both baseline and RNN models.

###  3.4 Experiment 4: Qualitative analysis

Figure 4: Cosine distance in the embedding space in relation to the respective
audio passage duration of 534 pairs from the MSMD test set. The cosine
distances were computed with the RNN model.

To get a better understanding of the behavior of our proposed network, in this
last experiment we take a closer look at the shared embedding space
properties. Figure 4 shows the distribution of the pairwise cosine distances
between the passage pairs from the MSMD test set, in relation to the duration
(in seconds) of their respective audio passages. Moreover, we scale the point
sizes in the plot so they are proportional to their individual precision
values (inverse of the rank values), when considering the S2A experimental
setup.

An interesting behavior in this visualization is the size of the points
increasing as the cosine distance decreases. It is expected that passage pairs
with smaller distances between them, meaning that they are closer together in
the embedding space, would be lead to better retrieval ranks.

Another interesting aspect of this distribution concerns the proportion of
larger cosine distances as the audio duration of the passages increases. For
example, between five and ten seconds, there are more large points observed
than smaller ones, while between 20 and 25 seconds, the proportion is roughly
equal. This indicates that, in our test set, embeddings from shorter passages
of audio are still located closer to their sheet counterparts in comparison
with longer audio passages, despite our efforts to design a recurrent networks
that learns from longer temporal contexts.

##  4 Conclusion and future work

We have presented a novel cross-modal recurrent network for learning
correspondences between audio and sheet music passages. Besides requiring only
weakly-aligned music data for training, this approach overcomes the problems
of intrinsic global and local tempo mismatches of previous works that operate
on short and fixed-size fragments. Our proposed models were validated in a
series of experiments under different retrieval scenarios and generated better
results when comparing with baseline methods, for all possible configurations.

On the other hand, a serious generalization gap to real music data was
observed, which points us to the next stages of our research. A natural step
towards making deep-learning-based cross-modal audio–sheet music retrieval
more robust would be to include real and diverse data that can be used for
training models. However such data with suitable annotations are scarce, and
recent advances in end-to-end full-page optical music recognition [29] can be
a possible solution to learn correspondences on the score page level.
Moreover, the powerful transformers [30] are potential architectures to learn
correspondences from even longer audio recordings, accommodating typical
structural differences between audio and sheet music, such as jumps and
repetitions.

##  5 Acknowledgments

This work is supported by the European Research Council (ERC) under the EU’s
Horizon 2020 research and innovation programme, grant agreement No. 101019375
(Whither Music?), and the Federal State of Upper Austria (LIT AI Lab).

## References

  * [1] M. Müller, A. Arzt, S. Balke, M. Dorfer, and G. Widmer, “Cross-modal music retrieval and applications: An overview of key methodologies,” _IEEE Signal Processing Magazine_ , vol. 36, no. 1, pp. 52–62, 2019.
  * [2] Ö. Izmirli and G. Sharma, “Bridging printed music and audio through alignment using a mid-level score representation,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , Porto, Portugal, 2012, pp. 61–66.
  * [3] C. Fremerey, M. Clausen, S. Ewert, and M. Müller, “Sheet music-audio identification,” in _Proceedings of the International Conference on Music Information Retrieval (ISMIR)_ , Kobe, Japan, Oct. 2009, pp. 645–650.
  * [4] F. Kurth, M. Müller, C. Fremerey, Y. ha Chang, and M. Clausen, “Automated synchronization of scanned sheet music with audio recordings,” in _Proceedings of the International Conference on Music Information Retrieval (ISMIR)_ , Vienna, Austria, Sep. 2007, pp. 261–266.
  * [5] A. Arzt, S. Böck, and G. Widmer, “Fast identification of piece and score position via symbolic fingerprinting,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , Porto, Portugal, 2012, pp. 433–438.
  * [6] T. J. Tsai, “Towards linking the Lakh and IMSLP datasets,” in _Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)_ , 2020, pp. 546–550.
  * [7] D. Yang, T. Tanprasert, T. Jenrungrot, M. Shan, and T. J. Tsai, “MIDI passage retrieval using cell phone pictures of sheet music,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2019, pp. 916–923.
  * [8] J. Calvo-Zaragoza, J. H. Jr., and A. Pacha, “Understanding optical music recognition,” _ACM Computing Surveys_ , vol. 53, no. 77, 2021.
  * [9] J. C. López-Gutiérrez, J. J. Valero-Mas, F. J. Castellanos, and J. Calvo-Zaragoza, “Data augmentation for end-to-end optical music recognition,” in _Proceedings of the 14th IAPR International Workshop on Graphics Recognition (GREC)_. Springer, 2021, pp. 59–73.
  * [10] E. van der Wel and K. Ullrich, “Optical music recognition with convolutional sequence-to-sequence models,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , Suzhou, China, 2017, pp. 731–737.
  * [11] S. Böck and M. Schedl, “Polyphonic piano note transcription with recurrent neural networks,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2012, pp. 121–124.
  * [12] C. Hawthorne, E. Elsen, J. Song, A. Roberts, I. Simon, C. Raffel, J. Engel, S. Oore, and D. Eck, “Onsets and frames: Dual-objective piano transcription,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , Paris, France, 2018, pp. 50–57.
  * [13] S. Sigtia, E. Benetos, and S. Dixon, “An end-to-end neural network for polyphonic piano music transcription,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 24, no. 5, pp. 927–939, 2016.
  * [14] M. Dorfer, J. Hajič jr., A. Arzt, H. Frostel, and G. Widmer, “Learning audio–sheet music correspondences for cross-modal retrieval and piece identification,” _Transactions of the International Society for Music Information Retrieval_ , vol. 1, no. 1, 2018.
  * [15] M. Dorfer, A. Arzt, and G. Widmer, “Learning audio-sheet music correspondences for score identification and offline alignment,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , Suzhou, China, 2017, pp. 115–122.
  * [16] L. Carvalho, T. Washüttl, and G. Widmer, “Self-supervised contrastive learning for robust audio–sheet music retrieval systems,” in _Proceedings of the ACM International Conference on Multimedia Systems (ACM-MMSys)_ , Vancouver, Canada, 2023.
  * [17] S. Balke, M. Dorfer, L. Carvalho, A. Arzt, and G. Widmer, “Learning soft-attention models for tempo-invariant audio-sheet music retrieval,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , Delft, Netherlands, 2019, pp. 216–222.
  * [18] F. Zalkow and M. Müller, “Using weakly aligned score–audio pairs to train deep chroma models for cross-modal music retrieval,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , Montréal, Canada, 2020, pp. 184–191.
  * [19] S. Balke, V. Arifi-Müller, L. Lamprecht, and M. Müller, “Retrieving audio recordings using musical themes,” in _Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)_ , Shanghai, China, 2016, pp. 281–285.
  * [20] S. Ioffe and C. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate shift,” in _Proceedings of the 32nd International Conference on International Conference on Machine Learning (ICML)_ , Lille, France, 2015, pp. 448–456.
  * [21] D. Clevert, T. Unterthiner, and S. Hochreiter, “Fast and accurate deep network learning by exponential linear units (ELUs),” in _International Conference on Learning Representations, (ICLR)_ , 2016.
  * [22] I. Sutskever, O. Vinyals, and Q. V. Le, “Sequence to sequence learning with neural networks,” in _Proceedings of the 27th International Conference on Neural Information Processing Systems_ , 2014, pp. 3104–3112.
  * [23] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” in _International Conference on Learning Representations (ICLR)_ , 2015.
  * [24] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural Computation_ , vol. 9, no. 8, pp. 1735–1780, 1997.
  * [25] K. Cho, B. van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio, “Learning phrase representations using RNN encoder–decoder for statistical machine translation,” in _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Doha, Qatar: Association for Computational Linguistics, Oct. 2014, pp. 1724–1734.
  * [26] R. Kiros, R. Salakhutdinov, and R. S. Zemel, “Unifying visual-semantic embeddings with multimodal neural language models,” _arXiv preprint (arXiv:1411.2539)_ , 2014. [Online]. Available: http://arxiv.org/abs/1411.2539
  * [27] C. E. Cancino-Chacón, T. Gadermaier, G. Widmer, and M. Grachten, “An evaluation of linear and non-linear models of expressive dynamics in classical piano and symphonic music,” _Machine Learning_ , vol. 106, no. 6, pp. 887–909, 2017.
  * [28] M. Dorfer, J. Schlüter, A. Vall, F. Korzeniowski, and G. Widmer, “End-to-end cross-modality retrieval with CCA projections and pairwise ranking loss,” _International Journal of Multimedia Information Retrieval_ , vol. 7, no. 2, pp. 117–128, Jun 2018. [Online]. Available: https://doi.org/10.1007/s13735-018-0151-5
  * [29] A. Ríos-Vila, J. M. Iñesta, and J. Calvo-Zaragoza, “End-to-end full-page optical music recognition for mensural notation,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , Bengaluru, India, 2022, pp. 226–232.
  * [30] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in Neural Information Processing Systems_ , vol. 30. Curran Associates, Inc., 2017.