11institutetext: Cognitive Systems, DTU Compute, Technical University of
Denmark, Denmark 22institutetext: EvoMRI Communications, Jena, Germany
33institutetext: Dept of Bioinformatics - BiGCaT, NUTRIM, Maastricht
University, The Netherlands

# Scholia and scientometrics with Wikidata

Finn Årup Nielsen 11 Daniel Mietchen 22 Egon Willighagen 33

###### Abstract

Scholia is a tool to handle scientific bibliographic information through
Wikidata. The Scholia Web service creates on-the-fly scholarly profiles for
researchers, organizations, journals, publishers, individual scholarly works,
and for research topics. To collect the data, it queries the SPARQL-based
Wikidata Query Service. Among several display formats available in Scholia are
lists of publications for individual researchers and organizations,
publications per year, employment timelines, as well as co-author and topic
networks and citation graphs. The Python package implementing the Web service
is also able to format Wikidata bibliographic entries for use in LaTeX/BIBTeX.

††This article is available under the terms of the Creative Commons
Attribution 4.0 License.

##  1 Introduction

Wikipedia contains significant amounts of data relevant for scientometrics,
and it has formed the basis for several scientometric studies [5, 12, 15, 16,
21, 24, 27]. Such studies can use the structured references found in Wikipedia
articles or use the intrawiki hyperlinks, e.g., to compare citations from
Wikipedia to scholarly journals with Thomson Reuters journal citation
statistics as in [15] or to rank universities as in [27].

While many Wikipedia pages have numerous references to scientific articles,
the current Wikipedias have very few entries _about_ specific scientific
articles. This is most evident when browsing the _Academic journal articles_
category on the English
Wikipedia.111https://en.wikipedia.org/wiki/Category:Academic_journal_articles
Among the few items in that category are famed papers such as the 1948 physics
paper _The Origin of Chemical Elements_ [2] – described in the English
Wikipedia article _Alpher–Bethe–Gamow paper_
222https://en.wikipedia.org/wiki/Alpher%E2%80%93Bethe%E2%80%93Gamow_paper – as
well as the 1953 article _Molecular Structure of Nucleic Acids: A Structure
for Deoxyribose Nucleic Acid_ [4] on eight Wikipedias. Another scientific
article is Hillary Putnam’s _Is Semantics Possible?_
[22]333https://et.wikipedia.org/wiki/Is_Semantics_Possible%3F from 1970 on the
Estonian Wikipedia.

References in Wikipedia are often formatted in templates, and it takes some
effort to extract and match information in these fields. For instance, in a
study of journals cited on Wikipedia, a database was built containing journal
name variations to match the many different variations that Wikipedia editors
used when citing scientific articles [15]. The use of standard identifiers –
such as the Digital Object Identifier (DOI) – in citations on Wikipedia can
help to some extent to uniquely identify works and journals.

Several other wikis have been set up to describe scientific articles, such as
WikiPapers, AcaWiki, Wikilit [19] and Brede Wiki
[17].444http://wikipapers.referata.com/, https://acawiki.org/,
http://wikilit.referata.com/ and http://neuro.compute.dtu.dk/wiki/ They are
all examples of MediaWiki-based wikis that primarily describe scientific
articles. Three of them use the Semantic MediaWiki extension [13], while the
fourth uses MediaWiki’s template
functionality555https://www.mediawiki.org/wiki/Help:Templates to structure
bibliographic information.

Since the launch of Wikidata666https://www.wikidata.org [25], the Wikimedia
family includes a platform to better handle structured data such as
bibliographic data and to enforce input validation to a greater degree than
Wikipedia. Wikidata data can be reified to triples [8], and graph-oriented
databases, including SPARQL databases, can represent Wikidata data [9]. The
Wikidata Query Service (WDQS)777https://query.wikidata.org is an extended
SPARQL endpoint that exposes the Wikidata data. Apart from offering a SPARQL
endpoint, it also features an editor and a variety of frontend result display
options. It may render the SPARQL query result as, e.g., bubble charts, line
charts, graphs, timelines, list of images, points on a geographical map, or
just provide the result as a table. These results can also be embedded on
other Web pages via an HTML iframe element. We note that Wikidata is open data
published under CC0, and it is available not only through the SPARQL endpoint,
but also—like any other project of the Wikimedia family—through an API and
dump files.888The API is at https://www.wikidata.org/w/api.php, and the dump
files are available at https://www.wikidata.org/w/api.php.

In the following sections, we describe how Wikidata has been used for
bibliographic information and present Scholia, our website built to expose
such information. We furthermore show how Scholia can be used for bibliography
generation and discuss limitations and advantages with Wikidata and Scholia.

##  2 Bibliographic information on Wikidata

Dimension |  Description
---|---
Domain |  Broad coverage
Size |  $>600,000$ scientific articles
Style of Metadata |  Export via, e.g., Lars Willighagen’s citation.js999https://github.com/larsgw/citation.js
Persistent Inbound Links? |  Yes, with the Q identifiers
Persistent Outbound Links |  Yes, with identifiers like DOI, PMID, PMCID, arXiv
Full Text? |  Via identifiers like DOI or PMCID; dedicated property for ‘full text URL’
Access |  Free access
Table 1: Summary of Wikidata as a digital library. This table is directly
inspired by [10, Table 1].

Wikidata editors have begun to systematically add scientific bibliographic
data to Wikidata across a broad range of scientific domains – see Table 1 for
a summary of Wikidata as a digital library. Individual researchers and
scientific articles not described by their own Wikipedia article in any
language are routinely added to Wikidata, and we have so far experienced very
few deletions of such data in reference to a notability criterion. The current
interest in expanding bibliographic information on Wikidata has been boosted
by the WikiCite project, which aims at collecting bibliographic information in
Wikidata and held its first workshop in 2016 [23].

The bibliographic information collected on Wikidata is about books, articles
(including preprints), authors, organizations, journals, and publishers. These
items (corresponding to _subject_ in Semantic Web parlance) can be interlinked
through Wikidata properties (corresponding to the _predicate_), such as author
(P50),101010The URI for Wikidata property P50 is
http://www.wikidata.org/prop/direct/P50 or with the conventional prefix
wdt:P50. Similarly for any other Wikidata property. published in (P1433),
publisher (P123), series (P179), main theme (P921), educated at (P69),
employer (P108), part of (P361), sponsor (P859, can be used for funding),
cites (P2860) and several other properties.111111A Wikidata table lists
properties that are commonly used in bibliographic contexts:
https://www.wikidata.org/wiki/Template:Bibliographical_properties .

Numerous properties exist on Wikidata for deep linking to external resources,
e.g., for DOI, PMID, PMCID, arXiv, ORCID, Google Scholar, VIAF, Crossref
funder ID, ZooBank and Twitter. With these many identifiers, Wikidata can act
as a hub for scientometrics studies between resources. If no dedicated
Wikidata property exists for a resource, one of the URL properties can work as
a substitute for creating a deep link to a resource. For instance, P1325
(_external data available at_) can point to raw or supplementary data
associated with a paper. We have used this scheme for scientific articles
associated with datasets stored in OpenfMRI [20], an online database with raw
brain measurements, mostly from functional magnetic resonance imaging studies.
Using WDQS, we query the set of OpenfMRI-linked items using the following
query:

⬇

?item wdt:P1325 ?resource .

filter strstarts(str(?resource),

"https://openfmri.org/dataset/")

A similar scheme is used for a few of the scientific articles associated with
data in the neuroinformatics databases Neurosynth [26] and NeuroVault [6].

When bibliographic items exist in Wikidata, they can be used as references to
support claims (corresponding to _triplets_ with extra qualifiers) in other
items of Wikidata, e.g., a biological claim can be linked to the Wikidata item
for a scientific journal.

By using these properties systematically according to an emerging
datamodel,121212https://www.wikidata.org/wiki/Wikidata:WikiProject_Source_MetaData/Bibliographic_metadata_for_scholarly_articles_in_Wikidata
editors have extended the bibliographic information in Wikidata. Particularly
instrumental in this process was a set of tools built by Magnus Manske,
_QuickStatements_ 131313https://tools.wmflabs.org/wikidata-
todo/quick_statements.php and _Source MetaData_
,141414hhttps://tools.wmflabs.org/sourcemd/ including the latter’s associated
_Resolve authors_
tool.151515https://tools.wmflabs.org/sourcemd/new_resolve_authors.php
Information can be extracted from, e.g., PubMed, PubMed Central and arXiv and
added to Wikidata.

How complete is Wikidata in relation to scientific bibliographic information?
Journals and universities are well represented. For instance, 31,895 Wikidata
items are linked with the identifier for the Collections of the National
Library of Medicine (P1055). Far less covered are individual articles,
individual researchers, university departments and citations between
scientific articles. Most of the scientific articles in Wikidata are claimed
to be an _instance of_ (P31) the Wikidata item _scientific article_
(Q13442814). With a WDQS query, we can count the number of Wikidata items
linked to _scientific article_ :

⬇

select (count(?work) as ?count) where {

?work wdt:P31 wd:Q13442814 . }

As of 12 March 2017, the query returned the result 615,182, see also Table 1.
In comparison, arXiv states having 1,240,585 e-prints and ACM Digital Library
states to have 24,110 proceedings.161616As of 9 March 2017 according to
https://arxiv.org/ and https://dl.acm.org/contents_guide.cfm There were 8,617
authors associated with Wikidata items linked through the _author_ property
(P50) to items that are _instance of_ _scientific article_ , and the number of
citations as counted by triples using the P2860 (_cites_) property stood at
2,729,164:

⬇

select (count(?citedwork) as ?count) where {

?work wdt:P2860 ?citedwork . }

The completeness can be fairly uneven. Articles from PLOS journals are much
better represented than articles from the journals of IEEE.

The sponsor property has been used extensively for _National Institute for
Occupational Safety and Health_ (NIOSH) with 52,852 works linking to the
organization, 18,135 of which are _instance of_ _scientific articles_ , but
apart from NIOSH, the use of the property has been very limited for scientific
articles.171717National Institute for Occupational Safety and Health has a
Wikimedian-in-Residence program, through which James Hare has added many of
the NIOSH works.

##  3 Scholia

Figure 1: Overview screenshot of part of the Scholia Web page for an author:
https://tools.wmflabs.org/scholia/author/Q20980928. Figure 2 zooms in on one
panel.

Scholia provides both a Python package and a Web service for presenting and
interacting with scientific information from Wikidata. The code is available
via https://github.com/fnielsen/scholia, and a first release has been archived
in Zenodo [18]. As a Web service, its canonical site runs from the Wikimedia
Foundation-provided service _Wikimedia Tool Labs_ at
https://tools.wmflabs.org/scholia/, but the Scholia package may be downloaded
and run from a local server as well. Scholia uses the Flask Python Web
framework [7]. The current Web service relies entirely on Wikidata for all its
presented data. The frontend consists mostly of HTML iframe elements for
embedding the on-the-fly-generated WDQS results and uses many of the different
output formats from this service: tables, bubble charts, bar charts, line
charts, graphs and image lists.

Through a JavaScript-based query to the MediaWiki API, an excerpt from the
English Wikipedia is shown on the top of each Scholia page if the
corresponding Wikidata item is associated with an article in the English
Wikipedia. The label for the item is fetched via Wikidata’s MediaWiki API.
While some other information can be fetched this way, Scholia’s many
aggregation queries are better handled through SPARQL.

Aspect | Examples |  Example panels
---|---|---
Author | Scientists |  List of publications, publications per year, co-authors, topics, timelines, map, citations, academic tree.
Work | Papers, books |  Recent citations, citations in the work, statements supported in Wikidata
Organization | Universities, research groups |  Affiliated authors, co-author graph, recent publications, page production, co-author-normalized citations per year
Venue | Journals, proceedings |  Recent publications, topics in the publications, author images, prolific authors, most cited works, most cited authors, most cited venues
Series | Proceedings series |  Items (venues) in the series, published works from venues in the series
Publisher | Commercial publisher |  Journals and other publications published, associated editors, most cited papers, number of citations as a function of number of published works
Sponsor | Foundation |  List of publications funded, sponsored authors, co-sponsors
Topic | Keywords |  Recent publication on the topic, co-occurring topics
Table 2: Aspects in Scholia: Each Wikidata item can be viewed in one or more
aspects. Each aspect displays multiple “panels”, which may be, e.g., a table
of publications or a bar chart of citations per year.

Scholia uses the Wikidata item identifier as its identifier rather than author
name, journal titles, etc. A search field on the front page provides a Scholia
user with the ability to search for a name to retrieve the relevant Wikidata
identifier. To display items, Scholia sets up a number of what we call
“aspects”. The currently implemented aspects are author, work, organization,
venue, series, publisher, sponsor and topic, see Table 2. The present
selection was motivated by the possibilities inherent in the Wikidata items
and properties. We plan to extend this to further aspects, e.g., award or
determination method. A URL scheme distinguishes the different aspects, so the
URL path /scholia/author/Q6365492 will show the author aspect of the
statistician Kanti V. Mardia, while /scholia/topic/Q6365492 will show the
topic aspect of the person, e.g., articles about Mardia. Likewise,
universities can be viewed, for instance, as organizations or as sponsors.
Indeed, any Wikidata item can be viewed in any Scholia aspect, but Scholia can
show no data if the user selects a “wrong” aspect, i.e. one for which no
relevant data is available in Wikidata.

For each aspect, we make multiple WDQS queries based on the Wikidata item for
which the results in the panels are displayed, — technically in embedded
iframes. For the author aspect, Scholia queries WDQS for the list of
publications, showing the result in a table, displaying a bar chart of the
number of publications per year, number of pages per year, venue statistics,
co-author graph, topics of the published works (based on the “main theme”
property), associated images, education and employment history as timelines,
academic tree, map with locations associated with the author, and citation
statistics – see Figure 1 for an example of part of an author aspect page. The
citation statistics displays the most cited work, citations by year and citing
authors. For the academic tree and the citation graph, we make use of
Blazegraph’s graph analytics RDF GAS
API181818https://wiki.blazegraph.com/wiki/index.php/RDF_GAS_API that is
available in WDQS. The embedded WDQS results link back to WDQS where a user
can modify the query. The interactive editor of WDQS allows users not familiar
with SPARQL to make simple modifications without directly editing the SPARQL
code.

Related to their work on quantifying conceptual novelty in the biomedical
literature [14], Shubhanshu Mishra and Vetle Torvik have set up a website
profiling authors in PubMed datasets:
LEGOLAS.191919http://abel.lis.illinois.edu/legolas/ Among other information,
the website shows the number of articles per year, the number of citations per
year, the number of self-citations per year, unique collaborations per year
and NIH grants per year as bar charts that are color-coded according to, e.g.,
author role (first, solo, middle or last author). Scholia uses WDQS for
LEGOLAS-like plots. Figure 2 displays one such example for the number of
published items as a function of year of publication on an author aspect page,
where the components of the bars are color-coded according to author role.

Figure 2: Screenshot of Scholia Web page with the number of papers published
per year for Finn Årup Nielsen:
https://tools.wmflabs.org/scholia/author/Q20980928. Inspired by LEGOLAS.
Colors indicate author role: first, middle, last or solo author. Figure 3:
Scholia screenshot with page production for a research section (Cognitive
Systems at the Technical University of Denmark), where the number of pages per
paper has been normalized by the number of authors. The bars are color-coded
according to author. The plot is heavily biased, as only a very limited subset
of papers from the section is available in Wikidata, and the property for the
number of pages is set for only a subset of these papers. From
%****␣main.tex␣Line␣400␣****https://tools.wmflabs.org/scholia/organization/Q24283660.

For the organization aspect, Scholia uses the employer and affiliated Wikidata
properties to identify associated authors, and combines this with the author
query for works. Scholia formulates SPARQL queries with property paths to
identify suborganizations of the queried organization, such that authors
affiliated with a suborganization are associated with the queried
organization. Figure 3 shows a corresponding bar chart, again inspired by the
LEGOLAS style. Here, the Cognitive Systems section at the Technical University
of Denmark is displayed with the organization aspect. It combines work and
author data. The bar chart uses the P1104 (number of pages) Wikidata property
together with a normalization based on the number of authors on each of the
work items. The bars are color-coded according to individual authors
associated with the organization. In this case, the plot is heavily biased, as
only a very limited subset of publications from the organization is currently
present in Wikidata, and even the available publications may not have the
P1104 property set. Other panels shown in the organization aspect are a co-
author graph, a list of recent publications formatted in a table, a bubble
chart with most cited papers with affiliated first author and a bar chart with
co-author-normalized citations per year. This last panel counts the number of
citations to each work and divides it by the number of authors on the cited
work, then groups the publications according to year and color-codes the bars
according to author.

Figure 4: Screenshot from Scholia’s publisher aspect with number of
publications versus number of citations for works published by BioMed Central.
The upper right point with many citations and many published works is the
journal _Genome Biology_. From
https://tools.wmflabs.org/scholia/publisher/Q463494.

For the publisher aspect, Scholia queries all items where the P123 property
(publisher) has been set. With these items at hand, Scholia can create lists
of venues (journals or proceedings) ordered according to the number of works
(papers) published in each of them, as well as lists of works ordered
according to citations. Figure 4 shows an example of a panel on the publisher
aspect page with a scatter plot detailing journals from _BioMed Central_. The
position of each journal in the plot reveals impact factor-like information.

Listing 1: SPARQL query on the work aspect page for claims supported by a
work, — in this case Q22253877 [1].

⬇

SELECT distinct ?item ?itemLabel ?property ?propertyLabel

?value ?valueLabel WHERE {

?item ?p ?statement .

?property wikibase:claim ?p .

?statement ?a ?value .

?item ?b ?value .

?statement prov:wasDerivedFrom/

<http://www.wikidata.org/prop/reference/P248>

wd:Q22253877 .

SERVICE wikibase:label {

bd:serviceParam wikibase:language "en" }

} ORDER BY ?itemLabel

For the work aspect, Scholia lists citations and produces a partial citation
graph. Figure 5 shows a screenshot of the citation graph panel from the work
aspect for a specific article [3]. For this aspect, we also formulate a
special query to return a table with a list of Wikidata items where the given
work is used as a source for claims. An example query for a specific work is
shown with Listing 1. From the query results, it can be seen, for instance,
that the article _A novel family of mammalian taste receptors_ [1] supports a
claim about _Taste 2 receptor member 16_ (Q7669366) being present in the cell
component (P681) _integral component of membrane_ (Q14327652). For the topic
aspect, Scholia uses a property path SPARQL query to identify subtopics. For a
given item where the aspect is not known in advance, Scholia tries to guess
the relevant aspect by looking at the _instance of_ property. The Scholia Web
service uses that guess for redirecting, so /scholia/Q8219 will redirect to
/scholia/author/Q8219, the author aspect for the psychologist Uta Frith. This
is achieved by first making a server site query to establish that Uta Frith is
a human and then using that information to choose the author aspect as the
most relevant aspect to show information about Uta Frith.

A few redirects for external identifiers are also implemented. For instance,
with Uta Frith’s Twitter name ‘utafrith’, /scholia/twitter/utafrith will
redirect to /scholia/Q8219, which in turn will redirect to
/scholia/author/Q8219. Scholia implements similar functionality for DOI, ORCID
and GitHub user identifier.

Figure 5: Screenshot of part of a Scholia Web page at
https://tools.wmflabs.org/scholia/work/Q21143764 with the partial citation
graph panel of the work aspect for Johan Bollen’s article from 2009 [3].

##  4 Using Wikidata as a bibliographic resource

As a command-line tool, Scholia provides a prototype tool that uses Wikidata
and its bibliographic data in a LaTeX and BibTeX environment. The current
implementation looks up citations in the latex-generated .aux file and queries
Wikidata’s MediaWiki API to get cited Wikidata items. The retrieved items are
formatted and written to a .bib that bibtex can use to format the
bibliographic items for inclusion in the LaTeX document. The workflow for a
LaTeX document with the filename example.tex is

⬇

latex example

python -m scholia.tex write-bib-from-aux example.aux

bibtex example

latex example

latex example

Here, the example document could read

⬇

\documentclass{article}

\usepackage[utf8]{inputenc}

\begin{document}

\cite{Q18507561}

\bibliographystyle{plain}

\bibliography{example}

\end{document}

In this case, the `\cite` command cites Q18507561 (_Wikidata: a free
collaborative knowledgebase_ [25]). A DOI can also be used in the `\cite`
command: instead of writing `\cite{Q18507561}`, one may write
`\cite{10.1145/2629489}` to get the same citation. Scholia matches on the
“10.” DOI prefix and makes a SPARQL query to get the relevant Wikidata item.

The scheme presented above can take advantage of the many available style
files of BibTeX to format the bibliographic items in the various ways
requested by publishers. We have used Scholia for reference management in this
paper.

##  5 Discussion

WDQS and Scholia can provide many different scientometrics views of the data
available in Wikidata. The bibliographic data in Wikidata are still quite
limited, but the number of scientometrically relevant items will likely
continue to grow considerably in the coming months and years.

The continued growth of science data on Wikidata can have negative impact on
Scholia, making the on-the-fly queries too resource demanding. In the current
version, there are already a few queries that run into WDQS’s time out, e.g.,
it happens for the view of co-author-normalized citations per year for Harvard
University. If this becomes a general problem, we will need to redefine the
queries. Indeed, the WDQS time out will be a general problem if we want to
perform large-scale scientometrics studies. An alternative to using live
queries would be using dumps, which are available in several formats on a
weekly basis, with daily increments in
between.202020https://www.wikidata.org/wiki/Wikidata:Database_download The
problem is not a limitation of SPARQL, but a limitation set by the server
resources. Some queries may be optimized, especially around the item labeling.

Working with Scholia has made us aware of several issues. Some of these are
minor limitations in the Wikidata and WDQS systems. The Wikidata label length
is limited to 250 characters, whereas the ‘monolingual text’ datatype used for
the ‘title’ property (P1476) is limited to 400 characters. There are scholarly
articles with titles longer than those limits.

Wikidata fields cannot directly handle subscripts and superscripts, which
commonly appear in titles of articles about chemical compounds, elementary
particles or mathematical formulas. Other formatting in titles cannot directly
be handled in Wikidata’s title property,212121By way of an example, consider
the article “A library of 7TM receptor C-terminal tails. Interactions with the
proposed post-endocytic sorting proteins ERM-binding phosphoprotein 50
(EBP50), N-ethylmaleimide-sensitive factor (NSF), sorting nexin 1 (SNX1), and
G protein-coupled receptor-associated sorting protein (GASP)”, an article with
the title “Cerebral 5-HT${}_{\mbox{\small 2A}}$ receptor binding is increased
in patients with Tourette’s syndrome”, where “2A” is subscripted and “User’s
Guide to the amsrefs Package”, where the “amsrefs” is set in monospaced font.
and recording a date such as “Summer 2011” is difficult.

Title and names of items can change. Authors can change names, e.g. due to
marriage, and journals can change titles, e.g. due to a change of scope or
transfer of ownership. For instance, the _Journal of the Association for
Information Science and Technology_ has changed names several times over the
years.222222http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)2330-1643/issues
records these former titles: _Journal of the American Society for Information
Science and Technology_ , _Journal of the American Society for Information
Science_ , and _American Documentation_. Wikidata can handle multiple titles
in a single Wikidata item and with qualifiers describe the dates of changes in
title. For scientometrics, this ability is an advantage in principle, but
multiple titles can make it cumbersome to handle when Wikidata is used as a
bibliographic resource in document preparation, particularly for articles
published near the time when the journal changed its name. One way to
alleviate this problem would be to split the journal’s Wikidata item into
several, but this is not current practice.

In Wikidata, papers are usually not described to be affiliated with
organizations. Scholia’s ability to make statistics on scientific articles
published by organization is facilitated by the fact that items about
scientific articles can link to items about authors, which can link to items
about organizations. It is possible to link scientific articles to
organization by using Wikidata qualifiers in connection with the author
property. However, this scheme is currently in limited use.

This scarcity of direct affiliation annotation on Wikidata items about
articles means that scientometrics on the organizational level are unlikely to
be precise at present. In the current version, Scholia even ignores any
temporal qualifier for the affiliation and employer property, meaning that a
researcher moving between several organization gets his/her articles counted
under multiple organizations.

Data modeling on Wikidata gives rise to reflections on what precisely a
“publisher” and a “work” is. A user can set the _publisher_ Wikidata property
of a work to a corporate group, a subsidiary or possibly an imprint. For
instance, how should we handle _Springer Nature_ , _BioMed Central_ and
_Humana Press_?

_Functional Requirements for Bibliographic Records_ (FRBR) [11] suggests a
scheme for works, expressions, manifestations and “items”. In Wikipedia, most
items are described on the work level as opposed to the manifestation level
(e.g., book edition), while citations should usually go to the manifestation
level. How should one deal with scientific articles that have slightly
different “manifestations”, such as preprint, electronic journal edition,
paper edition and postprint, or editorials that were co-published in multiple
journals with identical texts? An electronic and a paper edition may differ in
their dates of publication, but otherwise have the same bibliographic data,
while a preprint and its journal edition usually have different identifiers
and may also differ in content. From a scientometrics point of view, these
difference in manifestation may not matter in some cases, but could be the
focus of others. Splitting a scientific article as a work (in the FRBR sense)
over multiple Wikidata items seems only to complicate matters.

Feature |  |  Description
---|---|---
Business model | Y |  Community donations and funding from foundations to Wikimedia Foundation and affiliated chapters
Portrait picture | Y |  The P18 property can record Wikimedia Commons images related to a researcher
Alternative names | Y |  Aliases for all items, not just researchers
IDs / profiles in other systems | Y |  Numerous links to external identifiers: ORCID, Scopus, Google Scholar, etc.
Papers and similar | Y |  Papers and books are individual Wikidata items
Uncommon research products | Y |  For instance, software can be associated with a developer
Grants, third party funding | (N) |  Currently no property for grant holders and probably no individual grants in Wikidata. The sponsor property can be used to indicate the funding of a paper
Current institution | Y |  Affiliation and employer can be recorded in Wikidata
Former employers, education | Y |  Education, academic degree can be specified, and former employers can be set by way of qualifiers
Self-assigned keywords | (Y) |  The main theme of a work can be specified, interests or field of work can be set for a person. The values must be items in Wikidata. Users can create items.
Concepts from controlled vocabulary | Y |  See above
Social graph of followers/friends | N |  There are no user accounts on the current version of Scholia.
Social graph of coauthors | Y |
Citation/attention metadata from platform itself | Y |  Citations between scientific articles are recorded with a property that can be used to count citations. Citation/reference between Wikidata items.
Citation/attention metadata from other source | (N) |  Deep links to other citation resources like Google Scholar and Scopus.
Comprehensive search to match/include papers | (N) |  Several tools liks Magnus Manske’s _Source MetaData_ that look up bibliographic metadata based on DOI, PMID or PMCID
Forums, Q&A etc. | N |
Deposit own papers | (Y) |  Appropriately licensed papers can be uploaded to Wikimedia Commons or Wikisource
Research administration tools | N |
Reuse of data from outside of the service | Y |  API, WDQS, XML dump, third-party services
Table 3: Overview of Wikidata and Scholia features in terms of a scholarly
profile. Directly inspired by a blog post by Lambert Heller (see text).

The initial idea for Scholia was to create a researcher profile based on
Wikidata data with list of publications, picture and CV-like information. The
inspiration came from a blog post by Lambert Heller: _What will the scholarly
profile page of the future look like? Provision of metadata is enabling
experimentation._
232323http://blogs.lse.ac.uk/impactofsocialsciences/2015/07/16/scholarly-
profile-of-the-future/ In this blog post, he discussed the different features
of several scholarly Web services: ORCID, ResearchGate, Mendeley, Pure, VIVO,
Google Scholar and ImpactStory. In Table 3, we have set up a table listing
Heller’s features for the Wikidata–Scholia combination. Wikidata–Scholia
performs well in most aspects, but in the current version, Scholia has no
backend for storing user data, and user features such as forum, Q&A and
followers are not available.

Beyond the features listed by Heller, which features set Wikidata–Scholia
apart from other scholarly Web services? The collaborative nature of Wikidata
means that Wikidata users can create items for authors that do not have an
account on Wikidata. In most other systems, the researcher as a user of the
system has control over his/her scholarly profile and other researchers/users
cannot make amendment or corrections. Likewise, when one user changes an
existing item, this change will be reflected in subsequent live queries of
that item, and it may still be in future dumps if not reverted or otherwise
modified before the dump creation.

With WDQS queries, Scholia can combine data from different types of items in
Wikidata in a way that is not usually possible with other scholarly profile
Web services. For instance, Scholia generates lists of publications for an
organization by combining items for works and authors and can show co-author
graphs restricted by affiliation. Similarly, the co-author graph can be
restricted to authors publishing works annotated with a specific main theme.
Authors are typically annotated with gender in Wikidata, so Scholia can show
gender color-coding of co-author graphs. On the topic aspect page, the Scholia
panel that shows the most cited works that are cited from works around the
topic can point to an important paper for a topic – even if the paper has not
been annotated with the topic – by combining the citations data and topic
annotation. References for claims are an important part of Wikidata and also
singles Wikidata out among other scholarly profile Web service, and it acts as
an extra scientometrics dimension. The current version of Scholia has only a
single panel where the query uses references: the “Supports the following
statement(s)” on the work aspect page, but it is possible to extend the use of
this scientometrics dimension.

##  6 Acknowledgements

This work was supported by Innovationsfonden through the DABAI project. The
work on Scholia was spawned by the WikiCite project [23]. We would like to
thank the organizers of the workshop, particular Dario Taraborelli. Finn Årup
Nielsen’s participation in the workshop was sponsored by an award from the
Reinholdt W. Jorck og Hustrus Fund. We would also like to thank Magnus Manske
and James Hare for considerable work with Wikidata tools and data in the
context of WikiCite.

## References

  * [1] Adler, E., Hoon, M.A., Mueller, K.L., Chandrashekar, J., Ryba, N.J., Zuker, C.S.: A novel family of mammalian taste receptors. Cell 100, 693–702 (March 2000)
  * [2] Alpher, R.A., Bethe, H., Gamow, G.: The Origin of Chemical Elements. The Physical review 73, 803–804 (April 1948)
  * [3] Bollen, J., de Sompel, H.V., Hagberg, A., Chute, R.: A principal component analysis of 39 scientific impact measures. PLOS ONE 4, e6022 (December 2009)
  * [4] Crick, F., Watson, J.D.: Molecular Structure of Nucleic Acids: A Structure for Deoxyribose Nucleic Acid. Nature 171, 737–738 (April 1953)
  * [5] Eom, Y.H., Frahm, K.M., Benczúr, A., Shepelyansky, D.L.: Time evolution of Wikipedia network ranking. European Physical Journal B 86 (December 2013)
  * [6] Gorgolewski, K.J., Varoquaux, G., Rivera, G., Schwarz, Y., Ghosh, S.S., Maumet, C., Sochat, V.V., Nichols, T.E., Poldrack, R., Poline, J.B., Yarkoni, T., Margulies, D.S.: NeuroVault.org: A web-based repository for collecting and sharing unthresholded statistical maps of the human brain. Frontiers in Neuroinformatics 9, 8 (April 2015)
  * [7] Grinberg, M.: Flask Web Development (April 2014)
  * [8] Hernández, D., Hogan, A., Krötzsch, M.: Reifying RDF: What Works Well With Wikidata? Proceedings of the 11th International Workshop on Scalable Semantic Web Knowledge Base Systems (September 2015)
  * [9] Hernández, D., Hogan, A., Riveros, C., Rojas, C., Zerega, E.: Querying Wikidata: Comparing SPARQL, Relational and Graph Databases. The Semantic Web – ISWC 2016 pp. 88–103 (September 2016)
  * [10] Hull, D., Pettifer, S.R., Kell, D.B., Kell, D., Pettifer, S.: Defrosting the digital library: bibliographic tools for the next generation web. PLOS Computational Biology 4, e1000204 (October 2008)
  * [11] IFLA Study Group on the Functional Requirements for Bibliographic Records: Functional Requirements for Bibliographic Records (February 2009), http://www.ifla.org/files/assets/cataloguing/frbr/frbr_2008.pdf
  * [12] Kikkawa, J., Takaku, M., Yoshikane, F.: DOI Links on Wikipedia. Digital Libraries: Knowledge, Information, and Data in an Open Access Society pp. 369–380 (November 2016)
  * [13] Krötzsch, M., Vrandečić, D., Völkel, M.: Semantic MediaWiki. The Semantic Web - ISWC 2006 pp. 935–942 (December 2006)
  * [14] Mishra, S., Torvik, V.I.: Quantifying Conceptual Novelty in the Biomedical Literature. D-Lib Magazine 22 (September 2016)
  * [15] Nielsen, F.Å.: Scientific citations in Wikipedia. First Monday 12 (August 2007), http://firstmonday.org/article/view/1997/1872
  * [16] Nielsen, F.Å.: Clustering of scientific citations in Wikipedia (December 2008), http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/5666/pdf/imm5666.pdf
  * [17] Nielsen, F.Å.: Brede Wiki: A neuroinformatics Web service with structured information. Frontiers in Neuroinformatics (December 2009)
  * [18] Nielsen, F.Å., Mietchen, D., Willighagen, E.: Scholia - March 2017 (March 2017)
  * [19] Okoli, C., Mehdi, M., Mesgari, M., Nielsen, F.Å., Lanamäki, A.: The People’s Encyclopedia Under the Gaze of the Sages: A Systematic Review of Scholarly Research on Wikipedia (March 2012), https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2021326
  * [20] Poldrack, R., Barch, D.M., Mitchell, J.P., Wager, T.D., Wagner, A.D., Devlin, J.T., Cumba, C., Koyejo, O., Milham, M.P.: Toward open sharing of task-based fMRI data: the OpenfMRI project. Frontiers in Neuroinformatics 7, 12 (December 2013)
  * [21] Priem, J., Piwowar, H.A., Hemminger, B.M.: Altmetrics in the wild: Using social media to explore scholarly impact (March 2012), https://arxiv.org/html/1203.4745
  * [22] Putnam, H.: Is Semantics Possible? Metaphilosophy 1, 187–201 (July 1970)
  * [23] Taraborelli, D., Dugan, J., Pintscher, L., Mietchen, D., Neylon, C.: WikiCite 2016 Report (November 2016), https://upload.wikimedia.org/wikipedia/commons/2/2b/WikiCite_2016_report.pdf
  * [24] Teplitskiy, M., Lu, G., Duede, E.: Amplifying the impact of open access: Wikipedia and the diffusion of science. Journal of the American Society for Information Science (October 2016)
  * [25] Vrandečić, D., Krötzsch, M.: Wikidata: a free collaborative knowledgebase. Communications of the ACM 57, 78–85 (October 2014), http://cacm.acm.org/magazines/2014/10/178785-wikidata/fulltext
  * [26] Yarkoni, T., Poldrack, R., Nichols, T.E., Essen, D.C.V., Wager, T.D.: Large-scale automated synthesis of human functional neuroimaging data. Nature Methods 8, 665–670 (June 2011)
  * [27] Zhirov, A.O., Zhirov, O.V., Shepelyansky, D.L.: Two-dimensional ranking of Wikipedia articles. European Physical Journal B 77, 523–531 (October 2010)


9

# Wasserstein distance and metric trees

Maxime MATHEY-PREVOT and Alain VALETTE

###### Abstract

We study the Wasserstein (or earthmover) metric on the space $P(X)$ of
probability measures on a metric space $X$. We show that, if a finite metric
space $X$ embeds stochastically with distortion $D$ in a family of finite
metric trees, then $P(X)$ embeds bi-Lipschitz into $\ell^{1}$ with distortion
$D$. Next, we re-visit the closed formula for the Wasserstein metric on finite
metric trees due to Evans-Matsen [EM12]. We advocate that the right framework
for this formula is real trees, and we give two proofs of extensions of this
formula: one making the link with Lipschitz-free spaces from Banach space
theory, the other one algorithmic (after reduction to finite metric trees).

A la mémoire de Vaughan, ami et bon vivant

##  1 Introduction

Embeddings of metric spaces, especially discrete metric spaces like graphs,
into the Banach spaces $\ell^{1}$ or $L^{1}$, form a well-established part of
metric geometry, with applications ranging from computer science to topology:
we refer to [Na18], part I of [DL97] or Chapter 1 in [Os13]. In this paper we
will be concerned with embeddings of Wasserstein spaces, that we now recall.

Let $(X,d)$ be a metric space and let $P_{1}(X)$ be the space of probability
measures $\mu$ on $X$ with finite first moment, i.e.

$\int_{X}d(x_{0},x)\,d\mu(x)<+\infty$

for some (hence any) base-point $x_{0}\in X$. For compact $X$, the space
$P_{1}(X)$ coincides with the space $P(X)$ of all probability measures on $X$.

The Wasserstein metric is a distance function on $P_{1}(X)$. Intuitively,
given $\mu,\nu\in P_{1}(X)$, the distance $Wa(\mu,\nu)$ represents the amount
of work necessary to transform $\mu$ into $\nu$. More precisely, a probability
measure $\pi\in P(X\times X)$ is a coupling between $\mu$ and $\nu$ if its
marginals are $\mu$ and $\nu$, i.e. $\mu(A)=\pi(A\times X)$ and
$\nu(A)=\pi(X\times A)$ for any Borel subset $A\subset X$. And the Wasserstein
distance $Wa(\mu,\nu)$ is defined as

$Wa(\mu,\nu)=\inf\Big{\\{}\int_{X\times X}d(x,y)\,d\pi(x,y):{\mbox{$\pi$
coupling between $\mu$ and $\nu$}}\Big{\\}}.$

Note that $X$ embeds isometrically in $P_{1}(X)$ by $x\mapsto\delta_{x}$ (the
Dirac mass at $x$). See Chapter 5 in [Sa15] or Chapter 7 in [Vi15] for more on
the Wasserstein distance, also called Kantorovitch-Rubinstein distance or
earthmover distance (EMD) in computer science papers. We denote by $Wa(X)$ the
space $P_{1}(X)$ endowed with the Wasserstein distance, and call it the
Wasserstein space of $X$. For a coupling $\pi$, the cost of $\pi$ is the
quantity $\int_{X\times X}d(x,y)d\pi(x,y)$.

Let $\mathcal{Y}=(Y_{i},d_{i})_{i\in I}$ be a finite family of metric spaces.
We say that a metric space $(X,d)$ embeds stochastically in $\mathcal{Y}$ with
distortion $D\geq 1$ if there exists non-negative numbers $(p_{i})_{i\in I}$
summing up to 1, and maps $f_{i}:X\rightarrow Y_{i}$ (for each $i\in I$) such
that:

  * •

Each $f_{i}$ is non-contracting, i.e. for every $x,y\in X$ we have
$d_{i}(f_{i}(x),f_{i}(y))\geq d(x,y)$.

  * •

For every $x,y\in X$ we have $\sum_{i\in I}p_{i}d_{i}(f_{i}(x),f_{i}(y))\leq
D\cdot d(x,y).$

The first aim of this paper is to prove the following result;

######  Theorem 1.1.

Assume that the finite metric space $(X,d)$ embeds stochastically with
distortion $D$ into a family of finite metric trees. Then $Wa(X)$ embeds bi-
Lipschitz into $\ell^{1}$ with distortion at most $D$.

Here, by a metric tree, we mean a tree $T=(V,E)$ endowed with a positive
weight function $w:E\rightarrow\mathbf{R}_{>0}:e\mapsto w_{e}$. For $x,y\in V$
we denote by $[x,y]$ the set of edges on the unique path from $x$ to $y$ and
we endow $V$ with the distance $d_{T}(x,y)=\sum_{e\in[x,y]}w_{e}$.

We learned Theorem 1.1 from the paper [IT03] by P. Indyk and N. Thaper, who
get a less precise $O(D)$ for the distortion of the embedding into $\ell^{1}$,
and provide a rather frustrating comment that prompted our desire to provide a
direct proof of Theorem 1.1.111We provide the comment for completeness: “The
embedding can be seen as resulting from a combination of the following two
results: 1\. The result of [Ch02], who (implicitely) showed that the
techniques of [KT02] imply the following: if a metric $M$ can be
probabilistically embedded into trees with distortion $c$, then the EMD over
$M$ can be embedded into $\ell^{1}$ with distortion $O(c)$. 2\. The result of
[CC+98] who showed that the Euclidean metric over $\\{1,...,\Delta\\}^{d}$ can
be probabilistically embedded into trees with distortion $O(d\log\Delta)$.
Again that result is implicit in that paper.”

It was shown by J. Fakcharoenphol, S. Rao and K. Talwar [FRT04] that any
finite metric space on $n$ points embeds stochastically with distortion
$O(\log n)$ into a family of finite metric trees (and this bound is optimal).
Using this it was shown by F. Baudier, P. Motakis, G. Schlumprecht and A.
Zs̀ak (Corollary 8 in [BMSZ20]) that, for $X$ a finite metric space on $n$
points, the lamplighter metric space $La(X)$ embeds into $\ell^{1}$ with
distortion $O(\log n)=O(\log\log|La(X)|)$. Using the same result from [FRT04],
our Theorem 1.1 immediately implies:

######  Corollary 1.2.

For any finite metric space $X$ on $n$ points, the Wasserstein space $Wa(X)$
embeds bi-Lipschitz into $\ell^{1}$ with distortion at most $O(\log n)$.
$\blacksquare$

Combining with the isometric embedding $X\rightarrow
Wa(X):x\mapsto\delta_{x}$, we get as corollary a celebrated result by J.
Bourgain [Bo85] 222Of course all the difficulty becomes hidden in [FRT04]!

######  Corollary 1.3.

Any finite metric space on $n$ points, embeds bi-Lipschitz into $\ell^{1}$
with distortion at most $O(\log n)$.

It turns out that on finite metric trees there is a remarkable closed formula
for the Wasserstein distance. It originated in papers in computer science in
2002 and probably earlier: see Charikar [Ch02], for measures supported on the
leaves of the tree333A proof for this special case appears in lemma 3.1 of
[Kl15].. For general probability measures on a finite metric tree, the formula
appears in a paper in biomathematics (see section 2 in S.N. Evans and F.A.
Matsen [EM12]). We believe it deserves to be better known in mathematical
circles. To understand it, let $T=(V,E)$ be a metric tree, fix a base-vertex
$x_{0}\in V$ (so that $T$ appears as a rooted tree). Any edge $e\in E$
separates $T$ into two half-trees, and we denote by $T_{e}$ the set of
vertices of the half-tree NOT containing $x_{0}$: if we view the tree as
hanging from the root, $T_{e}$ is the subtree hanging below the edge $e$.

######  Theorem 1.4.

Let $T=(V,E)$ be a finite, rooted metric tree. Then for $\mu,\nu\in P(V)$:

$Wa(\mu,\nu)=\sum_{e\in E}w_{e}|\mu(T_{e})-\nu(T_{e})|$ (1)

This formula has numerous implications: first, the RHS is independent of the
choice of the root; second, it shows that the Wasserstein metric on $T$ is a
$L^{1}$-metric (see lemma 2.4 below).

Our second aim in this paper is to give two new proofs of Theorem 1.4. The
first one advocates that the right framework for Theorem 1.4 is real trees: by
exploiting a connection with the theory of Lipschitz-free spaces from Banach
space theory, we will extend the result to metric trees with countably many
vertices. The second proof is by double inequality: the inequality
$Wa(\mu,\nu)\geq\sum_{e\in E}w_{e}|\mu(T_{e})-\nu(T_{e})|$ follows by
considering the canonical embedding of the tree into $\ell^{1}$ and its
barycentric extension to $P_{1}(V)$. The converse inequality is proved by
first reducing to finite metric trees and, for those, given $\mu,\nu\in P(V)$,
by providing an algorithmic construction of a coupling $\pi$ with
$\int_{V\times V}d(x,y)\,d\pi(x,y)=\sum_{e\in E}w_{e}|\mu(T_{e})-\nu(T_{e})|$.

The paper is organized as follows. In section 2 we prove Theorem 1.1, taking
Theorem 1.4 for granted. Sections 3 and 4 present our two proofs of Theorem
1.4, suitably generalized to metric trees with countably many vertices (see
Theorem 3.3). Finally the Appendix provides a comparison between various
$\sigma$-algebras of sets on a real tree, that appeared in the literature.

Acknowledgements: We thank Florent Baudier for many insightful discussions,
for providing us with lemma 2.2 and its proof, and for useful comments on an
earlier version of the paper; and Gilles Lancien for pointing out the
connection with Lipschitz-free spaces.

##  2 Stochastic embeddings

We will prove Theorem 1.1 by means of a series of lemmas. The first one is
lemma 3 in [BMSZ20] .

######  Lemma 2.1.

Assume that the metric space $(X,d)$ embeds stochastically in
$\mathcal{Y}=(Y_{i},d_{i})_{i\in I}$, and that for every $i\in I$ the space
$Y_{i}$ embeds bi-Lipschitz into $\ell^{1}$ with distortion $C_{i}\geq 1$.
Then $X$ embeds bi-Lipschitz into $\ell^{1}$ with distortion at most $CD$,
where $C=\max_{i\in I}C_{i}$. $\blacksquare$

The second lemma was suggested to us by F. Baudier.

######  Lemma 2.2.

If the finite metric space $(X,d)$ embeds stochastically into
$\mathcal{Y}=(Y_{i},d_{i})_{i\in I}$ with distortion $D$, then $Wa(X)$ embeds
stochastically into $(Wa(Y_{i}))_{i\in I}$ with distortion $D$.

Proof For $i\in I$, let $p_{i}\geq 0$ and $f_{i}:X\rightarrow Y_{i}$ be
realizing the stochastic embedding with distortion $D$ of $X$ into
$\mathcal{Y}$. Consider then $(f_{i})_{*}:P(X)\rightarrow
P(Y_{i}):\mu\mapsto(f_{i})_{*}(\mu)$. We claim that the stochastic embedding
with distortion $D$ of $Wa(X)$ into the family $(Wa(Y_{i}))_{i\in I}$ is
realized by the $p_{i}$’s and the $(f_{i})_{*}$’s; to see this, we check the
two points in the definition of a stochastic embedding. Fix $\mu,\nu\in
Wa(X)$.

  * •

Fix $i\in I$. Let $\pi_{i}$ be a coupling between $(f_{i})_{*}(\mu)$ and
$(f_{i})_{*}(\mu)$ such that
$Wa((f_{i})_{*}(\mu),(f_{i})_{*}(\nu))=\sum_{y,y^{\prime}\in
Y_{i}}d_{Y_{i}}(y,y^{\prime})\pi_{i}(y,y^{\prime})$. For $y\in Y_{i}\setminus
f_{i}(X)$, we have

$\sum_{y^{\prime}\in
Y_{i}}\pi_{i}(y,y^{\prime})=(f_{i})_{*}(\mu)(y)=\mu(f_{i}^{-1}(y))=0$

hence $\pi_{i}(y,y^{\prime})=0$ for every $y^{\prime}\in Y_{i}$. So $\pi_{i}$
vanishes outside of $f_{i}(X)\times f_{i}(X)$. Hence we may define
$\sigma_{i}\in P(X\times X)$ by
$\sigma_{i}(x,x^{\prime})=\pi_{i}(f_{i}(x),f_{i}(x^{\prime}))$ and
$\sigma_{i}$ is a coupling between $\mu$ and $\nu$. Then

$Wa((f_{i})_{*}(\mu),(f_{i})_{*}(\nu))=\sum_{y,y^{\prime}\in
Y_{i}}d_{Y_{i}}(y,y^{\prime})\pi_{i}(y,y^{\prime})=\sum_{x,x^{\prime}\in
X}d_{Y_{i}}(f_{i}(x),f_{i}(x^{\prime}))\pi_{i}(f_{i}(x),f_{i}(x^{\prime}))$
$=\sum_{x,x^{\prime}\in
X}d_{Y_{i}}(f_{i}(x),f_{i}(x^{\prime}))\sigma_{i}(x,x^{\prime})\geq\sum_{x,x^{\prime}\in
X}d(x,x^{\prime})\sigma(x,x^{\prime})\geq Wa(\mu,\nu),$

where the first inequality follows from the fact that $f_{i}$ is non-
contracting. So $(f_{i})_{*}$ is non-contracting as well.

  * •

Let $\pi\in P(X\times X)$ be a coupling between $\mu$ and $\nu$ such that
$Wa(\mu,\nu)=\sum_{x,x^{\prime}\in X}d(x,y)\pi(x,x^{\prime})$. Set
$\tau_{i}=(f_{i}\times f_{i})_{*}(\pi)\in P(Y_{i}\times Y_{i})$. Then
$\tau_{i}$ is a coupling between $(f_{i})_{*}(\mu)$ and $(f_{i})_{*}(\nu)$ and

$\sum_{i\in I}p_{i}Wa((f_{i})_{*}(\mu),(f_{i})_{*}(\nu))\leq\sum_{i\in
I}p_{i}\sum_{y,y^{\prime}\in Y_{i}}d_{Y_{i}}(y,y)\tau_{i}(y,y^{\prime})$
$=\sum_{i\in I}p_{i}\sum_{x,x^{\prime}\in
X}d_{Y_{i}}(f_{i}(x),f_{i}(x^{\prime}))\tau_{i}(f_{i}(x),f_{i}(x^{\prime}))=\sum_{i\in
I}p_{i}\sum_{x,x^{\prime}\in
X}d_{Y_{i}}(f_{i}(x),f_{i}(x^{\prime}))\pi(x,x^{\prime})$
$=\sum_{x,x^{\prime}\in X}\pi(x,x^{\prime})\sum_{i\in
I}p_{i}d_{Y_{i}}(f_{i}(x),f_{i}(x^{\prime}))\leq D\cdot\sum_{x,x^{\prime}\in
X}\pi(x,x^{\prime})d(x,x^{\prime})=D\cdot Wa(\mu,\nu),$

where the second inequality follows from the fact that the $f_{i}$’s provide a
stochastic embedding. This concludes the proof.

$\blacksquare$

Combining lemmas 2.1 and 2.2 we immediately get:

######  Corollary 2.3.

If the finite metric space $(X,d)$ embeds stochastically into
$\mathcal{Y}=(Y_{i},d_{i})_{i\in I}$ with distortion $D$, and each $Wa(Y_{i})$
embeds bi-Lipschitz in $\ell^{1}$ with distortion $C_{i}$, then $Wa(X)$ embeds
bi-Lipschitz into $\ell^{1}$ with distortion at most $CD$, where $C=\max_{i\in
I}C_{i}$. $\blacksquare$

To prove Theorem 1.1, in view of Corollary 2.3, it is therefore enough to
observe:

######  Lemma 2.4.

If $T=(V,E)$ is any finite metric tree, then $Wa(T)$ embeds isometrically into
$\ell^{1}$.

Proof Fix a root $x_{0}\in V$ and, for any edge $e\in E$, let $T_{e}\subset V$
be defined as in the Introduction. The map

$Wa(T)\rightarrow\ell^{1}(E):\mu\mapsto(e\mapsto w_{e}\mu(T_{e}))$

is an isometric embedding of $Wa(T)$, by Theorem 1.4. $\blacksquare$

This concludes the proof of Theorem 1.1 (taking Theorem 1.4 for granted).

##  3 First proof of Theorem 1.4

###  3.1 Lipschitz-free spaces

For a metric space $(X,d)$ with a base-point $x_{0}\in X$, we denote by
$Lip_{0}(X)$ the Banach space of Lipschitz functions on $X$ vanishing at
$x_{0}$, endowed with the Lipschitz norm. The space $Lip_{0}(X)$ has a
canonical pre-dual, called the Lipschitz-free space of $X$ (see e.g. Chapter 2
in [We99], Chapter 10 in [Os13]) and denoted by $\mathcal{F}(X)$: it is the
closed linear subspace of the dual space $Lip_{0}(X)^{*}$ generated by the
point evaluations $\delta_{x}\;(x\in X\setminus\\{x_{0}\\})$.

For $\mu\in P_{1}(X)$, the linear form $f\mapsto\int_{X}f(x)\,d\mu(x)$ defines
an element of the dual $Lip_{0}(X)^{*}$: this way we get an embedding of
$Wa(X)$ into $Lip_{0}(X)^{*}$. When $X$ is a complete separable metric space,
it can be shown that this is actually an isometric embedding of $Wa(X)$ into
$\mathcal{F}(X)$ (see Theorem 1.13 in [OO19] or section 2 in [NS07]).

###  3.2 Real trees

A real tree $(T,d)$ is a geodesic metric space which is 0-hyperbolic in the
sense of Gromov. For $x,y\in T$, we denote by $[x,y]$ the segment between $x$
and $y$, i.e. the unique arc joining them. A point $x\in T$ is a branching
point if $T\setminus\\{x\\}$ has at least 3 connected components; we denote by
$Branch(T)$ the set of branching points of $T$. Fix a base-point $x_{0}\in T$.
For $x\in T$, we set

$T_{x}=\\{y\in T:x\in[x_{0},y]\\}=\\{y\in T:d(x_{0},y)=d(x_{0},x)+d(x,y)\\};$

so letting $T$ hang from the root $x_{0}$, the set $T_{x}$ is the part of $T$
lying below $x$.

Following A. Godard [Go10]) we say that a subset $A\subset T$ is measurable
if, for every $x,y\in T$, the set $A\cap[x,y]$ is Lebesgue-measurable in
$[x,y]$. On the $\sigma$-algebra $\mathcal{G}$ of measurable subsets, there is
a unique measure $\lambda$ such that $\lambda([x,y])=d(x,y)$: we call
$\lambda$ the length measure 444 See the Appendix below for a comparison of
various $\sigma$-algebras associated with real trees.. It is defined as
follows: for $S$ a segment in $T$, let $\lambda_{S}$ denote Lebesgue measure
on $S$. Then, for $A\in\mathcal{G}$, if $R\subset T$ is a finite disjoint
union of segments, say $R=\cup_{i=1}^{k}S_{i}$, we set
$\lambda_{R}(A)=\sum_{i=1}^{k}\lambda_{S_{i}}(S_{i}\cap A)$. Finally we set

$\lambda(A)=\sup_{R\in\mathcal{R}}\lambda_{R}(A)$ (2)

where $\mathcal{R}$ is the set of subsets of $T$ that can be expressed as
finite disjoint unions of segments.

For $A$ a closed subset of $T$ containing $x_{0}$, still following [Go10] we
define a function $L_{A}:A\rightarrow\mathbf{R}^{+}$ by
$L_{A}(a)=\inf\\{d(a,x):x\in A\cap[x_{0},a[\\}$. So $L_{A}(a)>0$ if and only
if $a$ is isolated in $A\cap[x_{0},a]$. We then define a measure $\mu_{A}$ on
$A$ by $\mu_{A}=\lambda|_{A}+\sum_{a\in A}L_{A}(a)\delta_{a}$. In Theorem 3.2
in [Go10], it is proved that, if $A$ is a closed subset of $T$ containing
$Branch(T)$, then $\mathcal{F}(A)$ is isometrically isometric to
$L^{1}(A,\mu_{A})$.

Assume from now on that the real tree $T$ is complete and separable. Then by
the previous sub-section, for $A$ a closed subset of $T$ containing
$Branch(T)$, the space $Wa(A)$ isometrically embeds into $L^{1}(A,\mu_{A})$.
This embedding is not written explicitly in [Go10]; by making it explicit we
get a closed formula for the Wasserstein distance on closed subsets of real
trees.

######  Proposition 3.1.

Let $(T,d)$ be a complete, separable real tree and let $A$ be a closed subset
of $T$ containing $Branch(T)$. For $\mu,\nu\in Wa(A)$ we have:

$Wa(\mu,\nu)=\int_{A}|\mu(T_{x}\cap A)-\nu(T_{x}\cap A)|\,d\mu_{A}(x).$ (3)

Proof By the proof of Theorem 3.2 in [Go10], the map

$\Phi:L^{\infty}(A,\mu_{A})\rightarrow
Lip_{0}(A):g\mapsto\Big{(}a\mapsto\int_{[x_{0},a]\cap
A}g(x)\,d\mu_{A}(x)\Big{)}$

is an isometric isomorphism which is weak∗-weak∗ continuous, so its transpose
$\Phi^{*}$ realizes the desired isometric isomorphism
$\mathcal{F}(A)\rightarrow L^{1}(A,\mu_{A})$. Denoting by $\chi_{[x,y]}$ the
characteristic function of the interval $[x,y]$, the previous formula may be
re-written:

$(\Phi(g))(a)=\int_{A}\chi_{[x_{0},a]}(x)g(x)\,d\mu_{A}(x).$

For $\nu\in Wa(A)$, we compute $\Phi^{*}(\nu)$. For $g\in
L^{\infty}(A,\mu_{A})$, we have

$(\Phi^{*}(\nu),g)=(\nu,\Phi(g))=\int_{A}(\Phi(g))(a)\,d\nu(a)=\int_{A}\Big{(}\int_{A}\chi_{[x_{0},a]}(x)g(x)\,d\mu_{A}(x)\Big{)}\,d\nu(a).$

As the measure $\mu_{A}$ is $\sigma$-finite (here we use that the tree $T$ is
separable), we may appeal to Fubini:

$(\Phi^{*}(\nu),g)=\int_{A}g(x)\Big{(}\int_{A}\chi_{[x_{0},a]}(x)\,d\nu(a)\Big{)}\,d\mu_{A}(x)=\int_{A}g(x)\nu(T_{x}\cap
A)\,d\mu_{A}(x).$

Since this holds for every $g\in L^{\infty}(A,\mu_{A})$ we deduce that, for
almost every $x\in A$:

$(\Phi^{*}(\nu))(x)=\nu(T_{x}\cap A).$

Equation (3) follows. $\blacksquare$

######  Remark 3.2.

When $A=T$, Proposition 3.1 becomes, for $T$ a complete separable real tree
and $\mu,\nu\in Wa(T)$:

$Wa(\mu,\nu)=\int_{T}|\mu(T_{x})-\nu(T_{x})|\,d\lambda(x).$ (4)

When $T$ is the geometric realization of a finite metric tree, equation (4)
appears as equation (5) in [EM12]; the proof is different.

######  Theorem 3.3.

Let $T=(V,E)$ be a rooted metric tree with countably many vertices. Then for
$\mu,\nu\in P_{1}(V)$:

$Wa(\mu,\nu)=\sum_{e\in E}w_{e}|\mu(T_{e})-\nu(T_{e})|$

Proof Fix $\mu,\nu\in P_{1}(V)$. For an edge $e$, let $e^{+},e^{-}$ be the
vertices of $e$, chosen so that $d(x_{0},e^{+})<d(x_{0},e^{-})$. Then on the
arc $[e^{+},e^{-}]$ the function $x\mapsto|\mu(T_{x})-\nu(T_{x})|$ is
constant, equal to $|\mu(T_{e})-\nu(T_{e})|$. So by formula (4):

$Wa(\mu,\nu)=\sum_{e\in
E}\int_{[e^{+},e^{-}]}|\mu(T_{x})-\nu(T_{x})|\,d\lambda(x)=\sum_{e\in
E}w_{e}|\mu(T_{e})-\nu(T_{e})|.$

$\blacksquare$

##  4 Second proof of Theorem 1.4

###  4.1 Lipschitz maps to Banach spaces

######  Proposition 4.1.

Let $(X,d)$ be a metric space, and let $E$ be a Banach space. Any
$C$-Lipschitz map $\beta:X\rightarrow E$ extends canonically to a
$C$-Lipschitz map $\tilde{\beta}:Wa(X)\rightarrow
E:\mu\mapsto\tilde{\beta}(\mu)$ defined as the barycenter of $\beta(X)$ with
respect to $\mu$, i.e.

$\tilde{\beta}(\mu)=\int_{X}\beta(x)\,d\mu(x).$

Proof Let $x_{0}$ be a base-point in $X$. Composing $\beta$ with a translation
in $E$, we may assume that $\beta(x_{0})=0$. Then, as
$\|\beta(x)-\beta(y)\|\leq C\cdot d(x,y)$ for any $x,y\in X$, we get
$\|\beta(x)\|\leq C\cdot d(x_{0},x)$, hence
$\|\tilde{\beta}(\mu)\|\leq\int_{X}\|\beta(x)\|\,d\mu(x)\leq
C\int_{X}d(x_{0},x)\,d\mu(x)<+\infty$. So $\tilde{\beta}$ is well-defined.

To check that $\tilde{\beta}$ is $C$-Lipschitz, observe that for $\mu,\nu\in
P_{1}(X)$ and $\pi$ a coupling between $\mu$ and $\nu$, we have:

$\|\tilde{\beta}(\mu)-\tilde{\beta}(\nu)\|=\Big{\|}\int_{X}\beta(x)\,d\mu(x)-\int_{X}\beta(y)\,d\nu(y)\Big{\|}=\Big{\|}\int_{X\times
X}\beta(x)\,d\pi(x,y)-\int_{X\times X}\beta(y)\,d\pi(x,y)\Big{\|}$
$\leq\int_{X\times X}\|\beta(x)-\beta(y)\|\,d\pi(x,y)\leq C\int_{X\times
X}d(x,y)\,d\pi(x,y).$

The result follows by taking the infimum over all couplings $\pi$.
$\blacksquare$

######  Remark 4.2.

Observe that, if $\beta$ in Proposition 4.1 is bi-Lipschitz, in general its
extension $\tilde{\beta}$ is not. Indeed take $E=\mathbf{R}$, and let
$X\subset\mathbf{R}$ be any subset with at least 3 elements, the inclusion
$\beta:X\rightarrow\mathbf{R}$ is isometric, but $\tilde{\beta}$ is not even
injective.

Let $T=(V,E)$ be a metric tree; we denote by $\chi_{[x,y]}$ the characteristic
function of the set of edges in $[x,y]$. There is a well-known isometric
embedding $\beta:V\rightarrow\ell^{1}(E,w):x\mapsto\chi_{[x_{0},x]}$ (it is
hard to locate the first appearance of this embedding in the literature: we
learned it from [Ha79]). By Proposition 4.1, we extend it to a 1-Lipschitz map
$\tilde{\beta}:P_{1}(V)\rightarrow\ell^{1}(E,w)$. Ultimately we will see that
$\tilde{\beta}$ is isometric. For the moment we prove:

######  Proposition 4.3.

Let $T=(V,E)$ be a metric tree. For $\mu,\nu\in P_{1}(V)$:

$\|\tilde{\beta}(\mu)-\tilde{\beta}(\nu)\|_{1}=\sum_{e\in
E}w_{e}|\mu(T_{e})-\nu(T_{e})|\leq Wa(\mu,\nu).$

Proof The inequality follows from Proposition 4.1, we focus on the equality.
But

$\|\tilde{\beta}(\mu)-\tilde{\beta}(\nu)\|_{1}=\sum_{e\in
E}w_{e}|\tilde{\beta}(\mu)(e)-\tilde{\beta}(\nu)(e)|.$

So it it enough to prove that $\tilde{\beta}(\mu)(e)=\mu(T_{e})$. So we
compute:

$\tilde{\beta}(\mu)(e)=\sum_{x\in V}\beta(x)(e)\mu(x)=\sum_{x\in
V}\chi_{[x_{0},x]}(e)\mu(x)=\sum_{x\in T_{e}}\mu(x)=\mu(T_{e})$

as $\chi_{[x_{0},x]}(e)=1$ if and only if $x\in T_{e}$. $\blacksquare$

Our aim now is to prove that the inequality in Proposition 4.3 is actually an
equality, i.e for metric trees $T=(V,E)$ with countably many vertices we wish
to prove the reverse inequality

$\sum_{e\in E}w_{e}|\mu(T_{e})-\nu(T_{e})|\geq Wa(\mu,\nu).$ (5)

Theorem 1.13 of [OO19] implies that the set of finitely supported probability
measures is dense in $(P_{1}(V),Wa)$. Of course
$Wa(\cdot,\cdot):P_{1}(V)\times P_{1}(V)\to\mathbf{R}$ is continuous, and

$P_{1}(V)\times P_{1}(V)\to\mathbf{R}:(\mu,\nu)\mapsto\sum_{e\in
E}w_{e}|\mu(T_{e})-\nu(T_{e})|$

is continuous too, as an immediate consequence of Proposition 4.3. So to show
(5) we may restrict for finitely supported measures i.e. we may restrict to
finite metric trees.

###  4.2 An algorithm for finite metric trees

Let $T=(V,E)$ be a finite metric tree. Recall from the proof of theorem 3.3
that if $e\in E$ is an edge, we write $e^{+}$ and $e^{-}$ its two extremities
chosen so $d(x_{0},e^{+})<d(x_{0},e^{-})$, moreover if $v,w\in V$, we say that
$w$ is a descendant of $v$ if $v\in[x_{0},w]$ (notice that a vertex is its own
descendant) and we say that $w$ is a child of $v$ \- and that $v$ is the
parent of $w$ \- if $w$ is a descendent of $v$ and $[v,w]=\\{w,v\\}$. If $v\in
V$ we write $T_{v}$ the half tree with set of vertices the set of all
descendants of $v$, hence $T_{x_{0}}=T$ and if $e\in E$ then
$T_{e}=T_{e^{-}}$.

To show that

$\displaystyle Wa(\mu,\nu)\leq\sum_{e\in E}w_{e}\mid\mu(T_{e})-\nu(T_{e})\mid$

we provide an algorithm which transforms a probability measure $\mu^{\prime}$,
initially set to $\mu$ into $\nu$. In parallel, this algorithm keeps track of
a variable (here a matrix) $\pi^{\prime}=(\pi^{\prime}(x,y))_{x,y\in
V}:=(\pi^{\prime}_{x,y})_{x,y\in V}$ that, all the way through the running of
the algorithm, provides a coupling between $\mu$ and $\mu^{\prime}$. When the
algorithm stops we will have $\mu^{\prime}=\nu$ and the cost of the coupling
$\pi^{\prime}$ will be $\sum_{e\in E}w_{e}\mid\mu(T_{e})-\nu(T_{e})\mid$. This
algorithm runs in two phases; intuitively speaking the first phase brings up
(towards the root) the excess of mass from those subtrees $T_{e}$ with
$\mu(T_{e})>\nu(T_{e})$, and the second phase let that mass fall (towards the
leaves) in the subtrees $T_{e}$ with $\mu(T_{e})<\nu(T_{e})$. Still
intuitively, for every vertex $x$, $\pi^{\prime}_{x,y}$ is the mass attributed
by $\mu^{\prime}$ to $x$ coming from $y$; the coupling remembers where the
mass comes from. We consider that the vertices of $T$ are numbered with
$1,2,...,n:=|V|$ (e.g. in such a way that given two vertices that are at
distinct depths in the tree, the deeper one is associate to a lower number
than the other). The algorithm is such that it moves first the mass coming
from vertices with a low number.

#### Algorithm.

% Initialization:
$\mu^{\prime}\leftarrow\mu$.
for all $v$

  1. $\pi_{v}^{\prime}\leftarrow\vec{0}$

  2. $\pi_{v,v}^{\prime}\leftarrow\mu(v)$

end for
$M\leftarrow 0$ % This variable is used just for the proof
% Phase (1):
for $N$ depth level, from the deeper up to 1:

  1. for all $T_{e}$ subtree whose root $e^{-}$ is at depth $N$: % Loop (*)

    1. if $\mu^{\prime}(T_{e})>\nu(T_{e})$ then

      1. % ”we bring $(\mu^{\prime}(T_{e})-\nu(T_{e}))$ up one level”:
$x\leftarrow(\mu^{\prime}(T_{e})-\nu(T_{e}))$
$\mu^{\prime}(e^{-})\leftarrow\mu^{\prime}(e^{-})-x$ % and simultaneously
$\mu^{\prime}(e^{+})\leftarrow\mu^{\prime}(e^{+})+x$.
$j\leftarrow\min\\{k:\sum_{i=1}^{k}\pi_{e^{-},i}^{\prime}\geq x\\}$
for $i<j$

        1. $\pi_{e^{+},i}^{\prime}\leftarrow\pi_{e^{+},i}^{\prime}+\pi_{e^{-},i}^{\prime}$

end for
$\pi_{e^{+},j}^{\prime}\leftarrow\pi_{e^{+},j}^{\prime}+(x-\sum_{n=1}^{j-1}\pi_{e^{-},n})$
$\pi_{e^{-},j}^{\prime}\leftarrow\pi_{e^{+},j}^{\prime}-(x-\sum_{n=1}^{j-1}\pi_{e^{-},n})$
for all $i<j$

        1. $\pi_{e^{-},i}\leftarrow 0$

end for

end if

$M\leftarrow M+1$
end for

end for
% Phase (2):
for $N$ depth level from $0$ to the deepest level in the tree$-1$:

  1. for all $T$ subtree whose root $r$ is at depth $N$:

    1. let $s_{1},...,s_{n}$ be the sons of $r$

    2. if $\mu^{\prime}(r)>\nu(r)$:

      1. for $i=1...n$ % Loop (**):

        1. if $\nu(T_{s_{i}})>\mu^{\prime}(T_{s_{i}})$:

          1. % ”We let $(\nu(T_{s_{i}})-\mu^{\prime}(T_{s_{i}}))$ fall one level”:
$x\leftarrow(\nu(T_{s_{i}})-\mu^{\prime}(T_{s_{i}}))$
$\mu^{\prime}(s_{i})\leftarrow\mu^{\prime}(s_{i})+x$ % and simultaneously
$\mu^{\prime}(r)\leftarrow\mu^{\prime}(r)-x$.
$j\leftarrow\min\\{k:\sum_{n=1}^{k}\pi_{r,n}\geq x\\}$
for  $k<j$

            1. $\pi_{s_{i},k}\leftarrow\pi_{s_{i},k}+\pi_{r,k}$

end for
$\pi_{s_{i},j}\leftarrow\pi_{s_{i},j}+(x-\sum_{n=1}^{j-1}\pi_{r,n})$
$\pi_{r,j}\leftarrow\pi_{s_{i},j}-(x-\sum_{n=1}^{j-1}\pi_{r,n})$
for $k<j$

            1. $\pi_{r,k}\leftarrow 0$

end for

end if
$M\leftarrow M+1$

end for

end if

end for

end for

We must now prove that the algorithm works as intended, that is $\pi^{\prime}$
is always a coupling between $\mu$ and $\mu^{\prime}$, and when the algorithm
terminates we have $\mu^{\prime}=\nu$ and the cost of $\pi^{\prime}$ is
$\sum_{e\in E}w_{e}\mid\mu(T_{e})-\nu(T_{e})\mid$.

Proof A probability measure on a tree $T$ is determined by the measure
attributed to all subtrees $T_{e}$. To see that $\mu^{\prime}=\nu$ when the
algorithm terminates, we thus show that $\mu^{\prime}(T_{e})=\nu(T_{e})$ for
all subtree $T_{e}$:

  * •

If $\mu(T_{e})=\nu(T_{e})$ then neither phase (1) nor (2) modifies
$\mu^{\prime}(T_{e})=\mu(T_{e})=\nu(T_{e})$ (even though the distribution may
vary).

  * •

If $\mu(T_{e})>\nu(T_{e})$ then phase (1) removes the adequate quantity of
mass from $\mu^{\prime}(T_{e})$ so that once phase (1) is over we have
$\mu^{\prime}(T_{e})=\nu(T_{e})$. Then phase (2) does not change the quantity
$\mu^{\prime}(T_{e})=\nu(T_{e})$ (even though it could change the distribution
on that subtree).

  * •

If $\mu(T_{e})<\nu(T_{e})$ phase (1) does not change the quantity
$\mu^{\prime}(T_{e})=\mu(T_{e})$ (even though it could change the distribution
on that subtree). We write $\mu^{N}$ for the measure $\mu^{\prime}$ after all
subtrees whose root is at depth $N$ have been treated by phase (2) ($N$ going
from $0$ to the deepest level in the tree $-1$). Then we proceed by induction
on $N$, assuming $e^{+}$ is at depth $N$. The initial step consists in seeing
that $\mu^{N=0}$, the measure $\mu^{\prime}$ just after phase (1), is a
probability measure on $T$; $\nu$ being one too it follows
$\mu^{N=0}(T)=\nu(T)=1$. For the induction step, we write
$e^{-}=v_{1},...,v_{m}$ the children of $e^{+}$ and assume that (induction
hypothesis) for all $i=1,...,m$:

$\displaystyle\mu^{N}(T_{e^{+}})=\nu(T_{e^{+}})$
$\displaystyle=\mu^{N}(e^{+})+\sum_{i=1}^{m}\mu^{N}(T_{v_{i}})$
$\displaystyle=\nu(e^{+})+\sum_{i=1}^{m}\nu(T_{v_{i}}).$

Since phase (1) is over $\mu^{N}(T_{v_{i}})\leq\nu(T_{v_{i}})$, hence
$\mu^{N}(e^{+})\geq\nu(e^{+})$. Then, phase (2) of the algorithm modifies:

$\mu^{N+1}(v_{i})=\mu^{N}(v_{i})+(\nu(T_{v_{i}})-\mu^{N}(T_{v_{i}})).$

And:

$\displaystyle\mu^{N+1}(T_{v_{i}})$
$\displaystyle=\mu^{N}(T_{v_{i}})-\mu^{N}(v_{i})+\mu^{N+1}(v_{i})$
$\displaystyle=\mu^{N}(T_{v_{i}})-\mu^{N}(v_{i})+\mu^{N}(v_{i})+(\nu(T_{v_{i}})-\mu^{N}(T_{v_{i}}))$
$\displaystyle=\nu(T_{v_{i}}).$

Then we have the desired fact for $i=1$.

Eventually when the algorithm stops $\mu^{\prime}=\nu$.

$\mu^{\prime}$ and $\pi^{\prime}$ are modified only during loops (*) and (**),
we write $\mu^{M}$ and $\pi^{M}$ for the values of $\mu^{\prime}$ and
$\pi^{\prime}$ after $M$ rounds through loops (*) or (**). Then
$\pi^{M}=(\pi^{M}(x,y))_{x,y\in V}:=(\pi^{M}_{x,y})_{x,y\in V}$ is a coupling
between $\mu$ and $\mu^{M}$: just after initialization it is clear that
$\pi^{\prime}=\pi^{0}$ is a coupling between $\mu$ and $\mu^{0}=\mu$, if
follows by induction that $\pi^{M}$ is a coupling between $\mu$ and $\mu^{M}$
(treating separately the case where moving from $M$ to $M+1$ is done during
phase (1) and the case where this move is done during phase (2)). About the
cost of the coupling, if moving from $M$ to $M+1$ is done during phase (1), in
loop (*) we have:

$\displaystyle\sum_{x,i}d(x,i)\pi^{M+1}_{x,i}$
$\displaystyle=\sum_{x}\sum_{i}d(x,i)\pi^{M+1}_{x,i}$
$\displaystyle=\sum_{i}d(s,i)\pi^{M+1}_{s,i}+\sum_{i}d(r,i)\pi^{M+1}_{r,i}+\sum_{x\neq
r,s}\sum_{i}d(x,i)\pi^{M}_{x,i}$
$\displaystyle=\sum_{i<j}d(s,i)(\pi_{s,i}^{M}+\pi_{r,i}^{M})+d(s,j)\bigg{(}\pi_{s,j}^{M}+\bigg{(}x-\sum_{n=1}^{j-1}\pi_{r,n}^{M}\bigg{)}\bigg{)}+\sum_{i>j}d(s,i)\pi_{s,i}^{M}$
$\displaystyle\ +\sum_{i<j}d(r,i)\cdot
0+d(r,j)\bigg{(}\pi_{r,j}^{M}-\bigg{(}x-\sum_{n=1}^{j-1}\pi_{r,n}^{M}\bigg{)}\bigg{)}+\sum_{i>j}d(r,i)\pi_{s,i}^{M}$
$\displaystyle\ +\sum_{x\neq r,s}\sum_{i}d(x,i)\pi^{M}_{x,i}$
$\displaystyle=\sum_{x,i}d(x,i)\pi_{x,i}^{M}+(d(s,j)-d(r,j))\bigg{(}x-\sum_{n=1}^{j-1}\pi_{r,n}^{M}\bigg{)}+\sum_{i<j}(d(s,i)-d(r,i))\pi_{r,i}^{M}$
$\displaystyle=\sum_{x,i}d(x,i)\pi_{x,i}^{M}+x\cdot(d(s,j)-d(r,j))$
$\displaystyle=\sum_{x,i}d(x,i)\pi_{x,i}^{M}+x\cdot d(s,r).$

Where we used that $d(s,j)-d(r,j)=d(s,r)$ and that every $i$ such that
$\pi_{r,i}^{M}$ contributes to the sum
$\sum_{i<j}(d(s,j)-d(r,j))\pi_{r,i}^{M}$ is such that
$d(s,i)-d(r,i)=d(s,j)-d(r,j)=d(s,r)\geq 0$: Each vertex $i$ such that
$\pi_{r,i}^{M}\neq 0$ is (non strictly) below $r$ in the rooted-tree (since
$\pi_{r,i}^{M}$ is the mass $\mu^{M}$ in $r$ coming from $i$; we let the
reader check it formally). Then those vertices $i$ such that $\pi_{r,i}^{M}$
contributes to the sum $\sum_{i<j}(d(s,i)-d(r,i))\pi_{r,i}^{M}$ are (non
strictly) below $r$ and for those we have $d(s,i)\geq d(r,i)$ and then
$d(s,i)-d(r,i)=d(s,r)$ since $s$ is the father of $r$. By definition of $j$,
$\pi_{r,j}^{M}\neq 0$ and thus $j$ is (non strictly) below $r$, hence
$d(s,j)-d(r,j)=d(s,r)\geq 0$. If moving from $M$ to $M+1$ is done during phase
(2), in loop (**), we conclude similarly that the cost of the coupling is
increased by $x\cdot d(s_{i},r)$. During phase (1) excess measure is always
brought up one level at the time, in the loop (*) we thus always have
$x=\mu^{\prime}(T)-\nu(T)=\mu(T)-\nu(T)$. And phase (1) brings up excess
measure exactly from those subtrees $T_{e}$ with $\mu(T_{e})>\nu(T_{e})$.
During phase (2) measure is always brought down one level at the time, in the
loop (**) we thus always have
$x=\mu^{\prime}(T_{i})-\nu(T_{i})=\mu(T_{i})-\nu(T_{i})$. And phase (2) brings
down adequate quantity of measure exactly in those subtrees $T_{e}$ with
$\mu(T_{e})<\nu(T_{e})$. Since just after initialization $\pi^{\prime}$ has
null cost, the cost of it at the end of the algorithm is thus $\sum_{e\in
E}w_{e}|\mu(T_{e})-\nu(T_{e})|$. $\blacksquare$

######  Remark 4.4.

Let $(X,d)$ be a Polish metric space. For $\mu,\nu\in P_{1}(X)$, we have from
the Kantorovich-Rubinstein duality:

$Wa(\mu,\nu)=\sup\Big{\\{}\int_{X}f(x)\,d\mu(x)-\int_{X}f(x)\,d\nu(x)\Big{\\}},$

where the supremum is taken over all 1-Lipschitz functions $f$: see Theorem
1.3 in [Vi15]; see also [Ed10] for a short proof. We observe that, for a
finite metric tree, our second proof of Theorem 1.4 does not appeal to
Kantorovich-Rubinstein duality (in contrast e.g. with the proof in [EM12]).

##  5 Appendix: $\sigma$-algebras on real trees

Let $(T,d)$ be a real tree. Apart from Godard’s construction from [Go10] of
the $\sigma$-algebra $\mathcal{G}$ recalled above, we are aware of other
constructions of $\sigma$-algebras on $T$ and of corresponding length
measures:

  * •

The $\sigma$-algebra $\mathcal{S}$ generated by segments, see [Va90].

  * •

The Borel $\sigma$-algebra $\mathcal{B}$ generated by open subsets, see
[EPW06] for compact real trees, then for locally compact real trees in
[AEW13].

All these constructions have in common that the length measure of a segment
$[x,y]$ is exactly $d(x,y)$. In order to clarify the relation between
$\mathcal{S},\mathcal{B}$ and $\mathcal{G}$, we also introduce the
$\sigma$-algebras $\mathcal{B}_{0}$ generated by open balls (so that
$\mathcal{B}_{0}\subset\mathcal{B}$) and $\overline{\mathcal{S}}$ obtained by
completing $\mathcal{S}$ with respect to $\lambda$-negligible subsets.

The following proposition explains our choice to work with Godard’s
$\sigma$-algebra $\mathcal{G}$.

######  Proposition 5.1.

Let $T$ be a real tree.

  1. 1.

We have $\mathcal{S}\subset\mathcal{B}_{0}\subset\mathcal{G}$ and
$\overline{\mathcal{S}}\subset\mathcal{G}$.

  2. 2.

If $T$ is separable then $\mathcal{B}_{0}=\mathcal{B}$ and
$\overline{\mathcal{S}}=\mathcal{G}$

Proof

  1. 1.

To show that $\mathcal{S}\subset\mathcal{B}_{0}$, fix $x,y\in T$ and let
$(z_{n})_{n>0}$ be a dense sequence in $[x,y]$. Then the equality

$[x,y]=\bigcap_{m\geq 1}\Big{(}\bigcup_{n>0}B(z_{n},1/m)\Big{)}$

shows that $[x,y]\in\mathcal{B}_{0}$. Now, let $B$ be an open ball in $T$. For
any $x,y\in T$, the intersection $B\cap[x,y]$ is convex in $[x,y]$, so it is a
sub-interval in $[x,y]$. In particular $B\cap[x,y]$ is Lebesgue-measurable in
$[x,y]$, so $B\in\mathcal{G}$.

The inclusion $\overline{\mathcal{S}}\subset\mathcal{G}$ follows from the fact
that $\mathcal{G}$ is complete, as can be seen from the definitions.

  2. 2.

The equality $\mathcal{B}_{0}=\mathcal{B}$ holds in every separable metric
space (any open set being then a countable union of open balls).

To prove the inclusion $\mathcal{G}\subset\overline{\mathcal{S}}$, we consider
the subset $T^{0}=:\cup_{x,y\in T}]x,y[$ and its complement $L=T\setminus
T^{0}$: the latter is the set of leaves of $T$. For every segment $[x,y]$ we
have $L\cap[x,y]\subset\\{x,y\\}$, so that $L\in\mathcal{G}$; moreover
$\lambda(L)=0$ by equation (2).

Then we take $A\in\mathcal{G}$. To show $A\in\overline{\mathcal{S}}$ we use
separability: let $D$ be a countable subset of $T$. It is easy to see that
$T^{\circ}=\cup_{x,y\in D}]x,y[$ which implies that $T^{\circ}$ is
$\overline{\mathcal{S}}$-measurable, as well as its complement $L$. On the one
hand $A\cap L\subset L$ and $\lambda(L)=0$, then $A\cap L$ is
$\lambda$-negligible and thus $\overline{\mathcal{S}}$-measurable. On the
other hand $A\cap T^{\circ}\in\overline{\mathcal{S}}$ since
$A\cap]x,y[\in\overline{\mathcal{S}}$ for all $x,y\in T$ because the
$\sigma$-algebra of Lebesgue-measurable subsets is the completion of the
$\sigma$-algebra generated by sub-intervals i.e.
$A\cap]x,y[\in\overline{\mathcal{S}}$. This concludes the proof.

$\blacksquare$

## References

  * [AEW13] S. Athreya, M. Eckhoff and A. Winter,  Brownian motion on $\mathbf{R}$-trees,  Transactions of the American Mathematical Society 365 (2013), 3115-3150.
  * [BMSZ20] F. Baudier, P. Motakis, G. Schlumprecht and A. Zsak,  Stochastic approximation of lamplighter metrics,  Preprint, arXiv:2003.06093
  * [Bo85] J. Bourgain,  On Lipschitz embedding of finite metric spaces in Hilbert space,  Israel Journal of Mathematics, 52, 46-52, 1985.
  * [CC+98] M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin,  Approximating a finite metric by a small number of tree metrics,  Proc. Symposium Foundations of Computer Science, 1998.
  * [Ch02] M.S. Charikar,  Similarity estimation techniques from rounding algorithms STOC ’02: Proceedings of the thirty-fourth annual ACM symposium on Theory of computing, May 2002, 380-388.
  * [DL97] M.M. Deza and M. Laurent,  Geometry of cuts and metrics,  Springer, Algorithms and combinatorics 15, 1997.
  * [Ed10] D.A. Edwards,  A simple proof in Monge-Kantorovich duality theory,  Studia Math. 200 (2010), 67-77.
  * [EPW06] S.N. Evans, J. Pitman and A. Winter,  Rayleigh processes, real trees, and root growth with re-grafting,  Probab. Theory Relat. Fields 134 (2006), 81-126.
  * [EM12] S.N. Evans and F.A. Matsen The phylogenetic Kantorovich-Rubinstein metric for environmental sequence samples,  J. R. Stat. Soc. Series B Stat. Methodol. 74(3) (2012), 569-592.
  * [FRT04] J. Fakcharoenphol, S. Rao and K. Talwar,  A tight bound on approximating arbitrary metrics by tree metrics,  Journal of Computer and System Sciences 69 (2004) 485-497.
  * [Go10] A. Godard.  Tree metrics and their Lipschitz-free spaces Proc. Amer. Math. Soc. 138 (2010), 4311-4320.
  * [Ha79] U. Haagerup,  An example of a nonnuclear $C^{*}$-algebra, which has the metric approximation property,  Invent. Math. 50 (1978/79), 279-293.
  * [IT03] P. Indyk and N. Thaper.  Fast image retrieval via embeddings.  In 3rd International Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003.
  * [KT02] J. Kleinberg and E. Tardos,  Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields,  Journal of the ACM 49 (2002), 616-639.
  * [Kl15] B.R. Kloeckner,  A geometric study of Wasserstein spaces: ultrametrics,  Mathematika 61 (2015), 162-178.
  * [Na18] A. Naor Metric dimension reduction: a snapshot of the Ribe program.  Proceedings of the ICM-Rio de Janeiro 2018. Vol. I. Plenary lectures, 759-837, World Sci. Publ., Hackensack, NJ, 2018.
  * [NS07] A. Naor and G. Schechtman,  Planar earthmover is not in $L^{1}$.  SIAM J. Comput. 37 (2007), 804-826.
  * [OO19] S. Ostrovska and M.I. Ostrovskii,  Generalized transportation cost spaces , Preprint, arXiv:1902.10334
  * [Os13] M.I. Ostrovskii,  Metric embeddings - bilipschitz and coarse embeddings into Banach spaces,  De Gruyter, Studies in Math. 49, 2013.
  * [Sa15] F Santambrogio,  Optimal Transport for Applied Mathematicians,  Birkhäuser, Progress in Nonlinear Differential Equations and Their Applications, 2015.
  * [Va90] A. Valette,  Les représentations uniformément bornées associées Ã un arbre réel,  Bull. Soc. Math. Belg. Sér. A 42 (1990), 747-760.
  * [Vi15] C. Villani,  Topics in Optimal Transportation,  AMS, Graduate Studies in Mathematics Vol. 58, 2003.
  * [We99] N. Weaver,  Lipschitz algebras.  World Scientific Publishing Co., Inc., River Edge, NJ, 1999. xiv+223 pp.

Authors’ address:
Institut de Mathématiques
Université de Neuchâtel
Unimail
11 Rue Emile Argand
CH-2000 Neuchâtel - SWITZERLAND

<EMAIL_ADDRESS>
<EMAIL_ADDRESS>