Paola Valdivia
email: paola.valdivia@inria.fr.

Paolo Buono
email: paolo.buono@di.uniba.it.

Catherine Plaisant
email: plaisant@cs.umd.edu

Nicole Dufournaud
email: nicole.dufournaud@laposte.net.

Senior Member, IEEE Jean-Daniel Fekete
email: jean-daniel.fekete@inria.fr.

PARALLEL AGGREGATED ORDERED HYPERGRAPH VISUALIZATION 1 Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization

Keywords: dynamic graph, interaction, case study, dynamic hypergraph, digital humanities, usability !

Parallel Aggregated Ordered Hypergraph (PAOH) is a novel technique to visualize dynamic hypergraphs. Hypergraphs are a generalization of graphs where edges can connect several vertices. Hypergraphs can be used to model networks of business partners or co-authorship networks with multiple authors per article. A dynamic hypergraph evolves over discrete time slots. PAOH represents vertices as parallel horizontal bars and hyperedges as vertical lines, using dots to depict the connections to one or more vertices. We describe a prototype implementation of Parallel Aggregated Ordered Hypergraph, report on a usability study with 9 participants analyzing publication data, and summarize the improvements made. Two case studies and several examples are provided. We believe that PAOH is the first technique to provide a highly readable representation of dynamic hypergraphs. It is easy to learn and well suited for medium size dynamic hypergraphs (50-500 vertices) such as those commonly generated by digital humanities projects-our driving application domain.

INTRODUCTION

D YNAMIC networks are used to model the evolution of relations between entities over time. The entities are represented as graph vertices and the relations as graph edges, connecting two vertices. Examples include computer networks where the dynamic relations are defined by packets exchanged over time between computers, co-authorship networks where relations are articles written by two authors, brain activity where relations are high correlations between regions of interest of the brain.

While these kinds of networks are typically modeled as regular graphs, they can more accurately be modeled as hypergraphs where each relation may involve several vertices. For example in historical documents multiple persons can be mentioned together; in coauthorship networks, publications can associate multiple authors to one article; and in brain data, multiple brain regions can be highly active at the same given measurement time.

The design of PAOH was initially driven by Digital Humanities applications. Our team has worked extensively with social science researchers studying social networks and their evolution. Many such projects involve a long data generation process, searching archives, analyzing documents, and generating medium-sized networks (50-500 vertices), followed by careful and detailed analysis of all the relationships.

Let's use the example of a historian studying a collection of historical documents describing business agreements between different people over the years [START_REF] Dufournaud | L'analyse des réseaux, une aide à penser : réflexions sur les stratégies économique et sociale de Marie Boucher, marchande à Nantes au XVIIe siècle[END_REF]. Each contract involves two or more persons, and the historian needs to understand how each person's business relationships change over time. Using classical node-link diagrams to visualize a graph, a contract between three entities is represented as three edges, making it unclear whether they corresponded to a single contract or two or three different contracts. It may be possible to use color or dash pattern on the edges to represent the contract, but if more than half-dozen contracts need to be encoded, the color encoding becomes unusable. Contracts can also be encoded as additional node types using a bipartite network, but this dramatically increases the size and complexity of the graph. So typically, the document identity is lost using classical network visualization techniques that focus on the relations among people (who is in relation with whom). The historian also needs to understand how the network changes over time. None of the existing techniques for visualizing dynamic networks [START_REF] Beck | The State of the Art in Visualizing Dynamic Graphs[END_REF] support hypergraphs, making PAOH unique.

The proposed PAOH visualization is a novel technique (Figure 1) where the time is split into intervals and visualized as consecutive time slots. The vertices are encoded as parallel horizontal tracks, and edges are encoded as parallel vertical lines connecting the vertices. A dot is used to depict and emphasize the connection or vertices with edges. A novel glyph technique (called drips) helps compact the display, while interaction speeds exploration or reveals similar edges. Variations in visual encoding and orderings address specific users needs.

The specific contributions of this article are 1 :

• A detailed description of the PAOH technique implemented in a prototype, with multiple examples and variants.

1. A very early version of the PAOH interface was described in a poster [START_REF] Beck | The State of the Art in Visualizing Dynamic Graphs[END_REF], and an initial case study was described in a workshop paper [START_REF] Valdivia | Using dynamic hypergraphs to reveal the evolution of the business network of a 17th century french woman merchant[END_REF].

Fig. 1: The Parallel Aggregated Ordered Hypergraph visualization of a dataset extracted by historians from 59 legal documents: Time runs from left to right with discrete time slots representing the network at that time. Vertices (here people) are represented by parallel horizontal bars, with all names aligned on the left. Each parallel vertical line is a hyperedge, connecting two or more vertices. A dot marks each connection. In this view, the vertices of degree one (i.e., the people involved in a single document) have been hidden from the list of vertices, and their existence is only hinted with drips, i.e., smaller gray dots at the lower end of hyperedges.

• The report of a usability study which 1) demonstrates that participants could discover how to interpret a PAOH display on their own without training, 2) illustrates how PAOH was used to explore a dataset of publications, and 3) summarizes the changes made to improve the usability of the tool. • Two case studies describing the use of PAOH in digital humanities research projects.

RELATED WORK

PAOH has been inspired by the BioFabric technique proposed by Longabaugh [4] that visualizes large networks, such as those in biological research, by depicting vertices as equally spaced parallel horizontal lines, and edges as vertical lines drawn over the vertices and joining the starting vertex vertical position to the ending vertex position. In addition to BioFabric, PAOH represents hyperedges, visualizes relations over time using time slots, allows vertex reordering, hyperedge packing, and offers multiple interaction techniques to support complex explorations. In the rest of this section, we provide definitions, review the work on the visualization of hypergraphs, dynamic networks, and taxonomies of tasks.

Definitions

A graph is defined as G = (V, E), where V is a set of vertices (or nodes)

{v 1 , • • • , v m } and E a set of relations (or edges) {e 1 , • • • , e p }|e i = (v a , v b ) ∈ V 2 , 1 ≤ i ≤ p.
The focus of this work is on hypergraphs, denoted as G = (V, H)|H is a set of h hyperedges, i.e., edges that can connect any number of vertices. Formally, h ∈ P(V ) where P(V ) is the set of all sets of V (a.k.a power-set of V ).

Several definitions of dynamic graphs exist in the literature. We use the definition from the survey on dynamic graphs [START_REF] Beck | A Taxonomy and Survey of Dynamic Graph Visualization[END_REF], where a dynamic graph is a sequence of graphs

{G 1 , • • • , G n }|G i = (V, E i ), 1 ≤ i ≤ n
sharing the same vertices but with a topology varying over time. Each set of edges E i refers to a given time interval (or time slot). Other authors, such as van den Elzen et al. [START_REF] Van Den Elzen | Dynamic Network Visualization with Extended Massive Sequence Views[END_REF], consider dynamic graphs as G τ = (V, E τ ) where edges E τ have a time-stamp: e τ = (v a , v b , τ) ∈ V 2 × T . These structures are closer to stream graphs [START_REF] Latapy | Stream Graphs and Link Streams for the Modeling of Interactions over Time[END_REF] and are not addressed here.

Visualization of Hypergraphs

Hypergraphs such as co-authorship networks have mostly been visualized as standard networks [START_REF] Newman | The structure of scientific collaboration networks[END_REF], [START_REF] Kang | Netlens: iterative exploration of content-actor network data[END_REF] or bipartite networks [START_REF] Latapy | Basic notions for the analysis of large two-mode networks[END_REF]. Visualizing a hypergraph as a bipartite graph adds vertices to represent hyperedges, and additional edges to connect them to the actual vertices, making the graph more complex to render and interpret, instead of simplifying it as intended by PAOH.

Hyperedges are equivalent to sets since a simple hyperedge is a set of vertices. Various techniques designed for visualizing sets have been surveyed in [START_REF] Alsallakh | The state-of-the-art of set visualization[END_REF]. For example, sets/hyperedges have been represented as Kelp Diagrams [START_REF] Dinkla | Kelp diagrams: Point set membership visualization[END_REF], or variations of node-link diagrams [START_REF] Paquette | Hypergraph visualization and enrichment statistics: how the egan paradigm facilitates organic discovery from big data[END_REF] where the style of an enclosing closed curve or a color encodes the vertices belonging to the same set/hyperedge. Those techniques quickly run out of visual attributes, so they are limited to one or two dozens of hyperedges. Matrix-based approaches [START_REF] Sadana | OnSet: A Visualization Technique for Large-scale Binary Set Data[END_REF], [START_REF] Kim | Visualizing set concordance with permutation matrices and fan diagrams[END_REF], [START_REF] Lex | UpSet: Visualization of Intersecting Sets[END_REF] were also used to represent sets. Within these, the technique proposed by Kim et al. [START_REF] Kim | Visualizing set concordance with permutation matrices and fan diagrams[END_REF] displays elements as columns and set/hyperedges as rows, on a matrix layout. Like PAOH, it also displays information about the set membership and degree of aggregation, for each element, on top of the columns. Although it looks similar to PAOH, it does not deal with time and is meant to support very different tasks.

Matrix-based approaches scale better in the number of vertices and sets than PAOH, but they only support well set operators such as union or intersection between two or more sets. PAOH supports some set operators but is designed for dynamic hypergraphs.

UpSet [START_REF] Lex | UpSet: Visualization of Intersecting Sets[END_REF] is a technique where sets are depicted as columns partitioned as segments of a Venn diagram, and each segment is represented by a configuration of lines (or disks). It is very similar to PAOH graphically, but completely different in meaning. While in PAOH a line depicts a vertex of a hyperedge, UpSet uses a line to depict Venn segments. Links also have a similar visual appearance. In PAOH, a link depicts a hyperedge, while in UpSet, it depicts Venn diagram segments. Furthermore, UpSet does not consider time at all.

If a group is an encoded relationship between objects [START_REF] Vehlow | The State of the Art in Visualizing Group Structures in Graphs[END_REF], hyperedges can also be represented as overlapping groups of edges. Vehlow et al. [START_REF] Vehlow | The State of the Art in Visualizing Group Structures in Graphs[END_REF] proposed a state of the art in visualizing group structures in graphs using a taxonomy, composed of two orthogonal concepts: Overlap (disjoint/overlapping) and Structure (flat/hierarchical). The survey mentions colors, pie charts or icons to encode the group or groups a vertex belongs to, and various strategies to show groups of edges (juxtaposed, superimposed, embedded). However, none of the proposed techniques explicitly addresses hyperedges, and most of the solutions consider a small number of groups. In contrast, the domains where PAOH has been used are characterized by the presence of hundreds of hyperedges.

We are interested to visualize non-overlapping group structures (partitions) of vertices over time. Visualizing the evolution of groups over time is challenging. Some researchers visualize the evolution of vertices groups but not the graph topology [START_REF] Falkowski | Mining and visualizing the evolution of subgroups in social networks[END_REF], [START_REF] Rosvall | Mapping change in large networks[END_REF], while others visualize graph topology but not the evolution of groups [START_REF] Wang | AmbiguityVis: Visualization of Ambiguity in Graph Layouts[END_REF], [START_REF] Saket | Comparing nodelink and node-link-group visualizations from an enjoyment perspective[END_REF]. The only attempt to visualize both the evolution of groups and topology that we found proposes a visualization of groups as blocks of vertices connected by curves to show relations between communities [START_REF] Vehlow | Visualizing the evolution of communities in dynamic graphs[END_REF]. They also propose a few patterns that reveal group evolution, such as split, merge, stable, extinct/merge. Hyperedges are not addressed.

In some cases, custom applications were designed to present specific hypergraphs, for example, PaperLens [START_REF] Lee | Understanding research trends in conf.s using paperlens[END_REF] shows a multidimensional and synchronized visualization for the analysis of scientific papers, and helps in exploring the dataset. No graph visualization is used and relationships-such as co-authorship-are reduced to one-to-one relationships. Arafat and Bressan visually identify hyperedges by enclosing vertices in closed curves [START_REF] Arafat | Hypergraph drawing by force-directed placement[END_REF]. To process them, they transform hypergraphs into graphs using several algorithms. This approach produces many crossings that quickly clutter the display, and does not consider dynamic hypergraphs.

Similarly to our proposal, Kerren et al. [START_REF] Kerren | A novel radial visualization approach for undirected hypergraphs[END_REF] address hyperedges as sets of vertices and propose a radial technique where vertices are points disposed regularly around a circle, and hyperedges are circular arcs connecting the vertices. A point depicts the vertex intersecting the hyperedge and its vertex, at the intersection of the radius passing by the vertex and the arc. Their technique is a radial version of PAOH, but is limited in the number of vertices, the number of hyperedges, and cannot encode multiple time-steps.

Storyline [START_REF] Tang | iStoryline: Effective Convergence to Hand-drawn Storylines[END_REF], [START_REF] Tanahashi | An efficient framework for generating storyline visualizations from streaming data[END_REF] is a technique to visualize the interactions between characters in movies and is related to hypergraphs. In a storyline visualization, each character is a curved line displayed in the context of a movie timeline, with only one degree of freedom: it can only move up or down since its horizontal position is constrained by the movie timeline. Lines join when their associated characters are present in the same area during an event of the movie, and get farther apart when the characters are farther away. Particular events can be highlighted with colored patches underlying multiple character lines during an action. These events can be considered as hyperedges. However, the structure of movies constrains the structure of the underlying hypergraph: one character can only appear in one event at a time whereas dynamic hypergraphs can connect the same vertex multiple times at the same time slot, and movie events are usually paced to follow storytelling rules whereas dynamic hyperedges can occur at any pace in a dynamic hypergraph. Therefore, Storyline cannot be used directly to visualize general dynamic hypergraphs.

As we were developing PAOH, we were pleased to find a precursor design published in an archaeology book [START_REF] Arnold | An Archaeology of the Early Anglo-Saxon Kingdoms[END_REF], where Arnold graphically describes a small dataset with 8 territories (see Figure 1 in supplementary materials). Each vertical line is a battle connecting territories. Attacking territories are shown as black dots, and defending ones are white dots. Coalitions are visible when more than two tribes are involved in a battle. Each battle is placed on a continuous timeline, using a stream metaphor instead of a series of discrete time slots as our technique does. The stream metaphor has some benefits but often leads to overlaps, which are avoided in our Parallel Aggregated Ordered Hypergraph design by aggregating hyperedges in specified time slots. No implementation of the design seems to exist.

Because PAOH is also able to display regular dynamic graphs, we continue by reviewing related work on such dynamic graphs.

Visualization of Dynamic Graphs

The state of the art report on dynamic graph visualization published in 2014 by Beck et al. [START_REF] Beck | A Taxonomy and Survey of Dynamic Graph Visualization[END_REF], as well as recent articles, e.g., [START_REF] Zhao | Egocentric Analysis of Dynamic Networks with EgoLines[END_REF], [START_REF] Bach | Small MultiPiles: Piling Time to Explore Temporal Patterns in Dynamic Networks[END_REF], show that node-link diagrams remain the work-horse of network visualization for practitioners [START_REF] Hansen | Analyzing Social Media Networks with NodeXL: Insights from a Connected World[END_REF], [START_REF] Bastian | Gephi: An open source software for exploring and manipulating networks[END_REF]. The evolution of the network has been shown using animation, or by using side by side snapshots. PAOH uses the latter technique.

Dang et al. [START_REF] Dang | TimeArcs: Visualizing Fluctuations in Dynamic Networks[END_REF] propose a network visualization called TimeArcs where vertices (called entities) represent terms of articles, stacked vertically. Edges are correlated terms in the same article, represented as vertical arcs. The time axis is a horizontal timeline. Each vertex has a weight depending on the number of occurrences in the article; line thickness encodes this weight. This technique reduces line crossing but it shows many overlapping arcs in case there are many correlated terms. Following the timeline, users see how term frequencies and relationships evolve.

Van den Elzen et al. [START_REF] Van Den Elzen | Dynamic Network Visualization with Extended Massive Sequence Views[END_REF] added the notion of time to the BioFabric technique in Extended Massive Sequence Views (EMSV); edges flow horizontally over time. EMSV uses color to provide different visual clues, such as edge direction, length, and size. Several ordering methods compact the edge representation and improve readability. Several properties are proposed to identify patterns, such as trends, communities, stars (source or sink vertices). They also propose a circular visualization to highlight two-way communication and correlations between edge occurrences. EMSV highlights the potential value of a grid-like design to represent dynamic graphs, but its continuous time model differs from ours, based on discrete time slots. Labeling and overlaps remain an issue and it does not address hypergraphs at all.

The Parallel Edge Splatting technique from Burch et al. [START_REF] Burch | Parallel Edge Splatting for Scalable Dynamic Graph Visualization[END_REF] visualizes time on the horizontal axis: each time-slot (i.e., network snapshot) is given a width and is visualized as two vertical boundaries. Vertices are distributed vertically using a single default order. Edges are diagonal lines connecting vertices at each time-slot. To address overplotting Parallel Edge Splatting uses a density map that highlights the dense parts of the display but still hides all the detail information. While this technique scales to some very large graphs, line crossings hinder its readability even on some small graphs, including those of our case study partners.

In summary, the review of the literature uncovers a rich and diverse set of related techniques but-to our knowledge-none of the techniques adequately answer to the needs for detailed exploration of medium size hypergraphs that our digital humanities partners have.

Taxonomies of Tasks

PAOH is related to dynamic networks and sets. Three recent taxonomies of tasks for dynamic networks are reported in [START_REF] Bach | GraphDiaries: Animated Transitions andTemporal Navigation for Dynamic Networks[END_REF], [START_REF] Wook Ahn | A Task Taxonomy for Network Evolution Analysis[END_REF], [START_REF] Kerracher | A Task Taxonomy for Temporal Graph Visualisation[END_REF], also summarized in a survey [START_REF] Beck | A Taxonomy and Survey of Dynamic Graph Visualization[END_REF]. For set visualization, Alsallakh et al. presented a taxonomy of tasks in [START_REF] Alsallakh | The state-of-the-art of set visualization[END_REF].

Bach et al. [START_REF] Bach | GraphDiaries: Animated Transitions andTemporal Navigation for Dynamic Networks[END_REF] extended the method introduced by Lee et al. [START_REF] Lee | Task taxonomy for graph visualization[END_REF]: starting from a taxonomy of low-level tasks by Amar et al. [START_REF] Amar | Low-Level Components of Analytic Activity in Information Visualization[END_REF], they combine them using a cross-product with graph entities (vertices, edges, paths, graphs, groups, connected components, clusters), leading to a systematic task space. Bach et al. further extend the cross-product approach by adding the When, Where, What framework of Peuquet [START_REF] Peuquet | Its About Time -a Conceptual-Framework for the Representation of Temporal Dynamics in Geographic Information-Systems[END_REF]. Yet, the approach is only applicable to low-level tasks since higher-level tasks do not always combine; e.g., ensemble perception tasks work in restricted conditions and cannot be combined, or to a limited extent.

Ahn et al. [START_REF] Wook Ahn | A Task Taxonomy for Network Evolution Analysis[END_REF] add more levels to the taxonomy, extending the graph entities to graph structure, taking into account specific temporal features (shape, rate of changes), extending graph properties from structural to domain-dependent. While the crossproduct method could still be applied with these new entities, it generates too many conditions to be explored and understood fully, so they expose their taxonomy through particular examples from 53 temporal network visualization systems from the literature.

Kerracher et al. [START_REF] Kerracher | A Task Taxonomy for Temporal Graph Visualisation[END_REF] extend the full task framework of Andrienko&Andrienko [START_REF] Andrienko | Exploratory Analysis of Spatial and Temporal Data: A Systematic Approach[END_REF] to adapt it to dynamic networks. The original framework consists of a data model (ADM) and a task framework (ATF). ADM divides a data structure into referential components (time, space, and objects) and characteristics (what data is being measured, e.g., publications count, author affiliation). According to ATF, at the lowest level, tasks are divided into Lookup, Comparison, and Relation seeking. Lookup tasks consist in finding a characteristic given a reference or vice versa. The comparison focuses on retrieving relations among references and/or characteristics. Relation seeking is focused on finding components associated with a given relation. At a higher level, tasks are divided into elementary and synoptic tasks.

Kerracher et al. extend the Andrienko&Andrienko framework, which mostly describes attribute-based tasks, by adding graph structural tasks related to the graph topology and entities. Using a parallel structure with the attribute-based tasks, they split the structural tasks into elementary and synoptic tasks related to the structure(s). Between the attribute-based and structural tasks lie connection tasks, that involve relational behaviors between multiple parts (attributes or structural entities).

The tasks supported by PAOH were mainly driven by our interviews with practitioners who were interested, for example, in tracking the temporal connectivity patterns, relate connections between vertices with group attributes, analyze in detail connections and when those connections were happening. In other words, PAOH is meant to facilitate the connection tasks involving both attribute values, such as groups, and graph structure over the same timeranges. Existing taxonomies are not clear about how many entities can be involved in the connection tasks. The existing taxonomies should be extended and specialized to characterize our dynamic hypergraph data structure. Particularly, having hyperedges instead of edges as the reference for performing tasks adds a level of complexity that needs to be further studied, and PAOH is a good starting point for this study.

Alsallakh et al. [START_REF] Alsallakh | The state-of-the-art of set visualization[END_REF] introduced a taxonomy of tasks for set visualization based on the task focus: elements, sets, relations, and element attributes. Since there is an equivalence between sets and hyperedges, PAOH supports or partially supports, several of these tasks. However, some tasks, like some set operations and set creation do not directly relate to hyperedges, since hyperedges usually represent relations such as contracts or papers. Also, the time aspect is missing on this taxonomy and would be too complex to extend using the cross product mechanism used in [START_REF] Bach | GraphDiaries: Animated Transitions andTemporal Navigation for Dynamic Networks[END_REF]. Therefore, PAOH is currently difficult to relate to existing task taxonomies; it would be weak on typical set tasks, but supports a large number of additional tasks not expressible by traditional set visualizations, e.g., related to time and graph topology that are essential for our partners.

PARALLEL AGGREGATED ORDERED HYPER-

GRAPH

We now describe the Parallel Aggregated Ordered Hypergraph technique in details. In a PAOH visualization, time flows from left to right as a series of time slots separated by small white gaps (Figure 2). Each time slot corresponds to an interval of time. Vertices are mapped to parallel horizontal bars. Their labels are placed on the left side of the display, fully visible and left aligned to make the list easy to scan. Hyperedges are parallel vertical lines connecting the vertices. The connections are emphasized usually with a dot, or alternatively using a symbol representing the role of the vertex in the hyperedge.

To further describe the technique we use a fictitious small dynamic hypergraph of business contracts in the 19 th century (Figure 2). It includes thirteen vertices (people); four time slots (four years from 1801-1804), and twenty-seven hyperedges corresponding to business contracts signed by those people during the specified time period. Specific symbols at the intersection of the vertex and hyperedge can be used to depict the role of the person in the contact. For example, in Figure 2 a star marks the first person mentioned in each contract.

The names in Figure 2 have been sorted vertically by appearance over time and, when appearing at the same time-slot, by their overall degree, providing a strong cue regarding the evolution of the network. Elise's business network starts small with only two contracts, each with a single partner. In the second time slot, Elise's network expands with four contracts, but still, all contracts are one-to-one business relationships. The third time slot sees a significant expansion. More business partners for Elise and several contracts are now between multiple persons. Some are former partners appearing in the upper part of the list of names, and some are new people appearing lower down. John is a major partner appearing in three contracts. We can see that, early on, he had his own separate contracts, and that when he joins Elise in 1803, they signed larger multi-person contracts. In the final year more people are included overall but we see a rupture: Elise has ended all business with John and works only with new people, but she remains very active with multiple business partners-such as Claude, who remains in contact with John. John keeps working with his previous partners but also some of Elise's earlier partners. One might wonder if John had a conflict with Elise, leading them not to work together anymore. PAOH facilitates this type of detailed and precise analysis of a dynamic hypergraph, which is crucial to many historical studies. The labels are readable and can be scanned easily, and there is no overlap, a perennial problem with graph visualization.

To illustrate another benefit of modeling and visualizing hyperedges, Figure 3 compares the representation of the 3 rd time slot modeled as a regular graph with edges (left) to the same data represented with hyperedges (right). The orange arrows point to six edges (clique) replaced by a single hyperedge. Again, using a regular graph visualization, it is impossible to know that multiple people are linked by a single contract.

Like other visualizations, the technique benefits from specialized interactions (section 3.6) but the readability of the display makes it usable even without interaction; it can even be printed for a systematic detailed analysis or for publication-which is critical for our driving application in the digital humanities.

Drips for Hypergraph Simplification

A common approach for simplifying graphs is to filter out vertices with low degrees [START_REF] Dunne | Motif simplification: improving network visualization readability with fan, connector, and clique glyphs[END_REF], e.g., hiding all the vertices that appear only in one single edge. In our prototype, a control allows users to set the minimum degree, and the existence and number of missing vertices are easily shown with a novel glyph that we call drips: tightly spaced smaller dots appended below the hyperedge line, Fig. 4: A subset of Marie Boucher's network. The vertices of people who signed only one contract have been filtered out. The fact that some people are missing is hinted at the lower end of the hyperedges by a drip line of smaller gray dots. On the right, we see how the tooltip reveals all the names-using smaller font size for the names of people that have been filtered out.

their number matching the number of missing vertices. Hovering over the hyperedge reveals all vertex labels in a consistent and readable manner (Figure 4). Drips dramatically reduce the overall size of the PAOH display but remain easy to understand and allows quickly revealing the hidden labels. Users are, most of the time, less interested in those one-time (or few times) vertices, but drips still remind them of the existence of the relationship instead of filtering them out totally.

Time slots

Each time slot T i corresponds to a time interval [t i-1 ,t i [. The set of edges E i , composed by all connections having a time stamp τ ∈ T i , is associated with the time slot T i . All the connections occurring in a particular time slot are visible inside the horizontal bounds allocated to that time slot; this means that the width of the time slot adapts to fit all its hyperedges so the width of a slot is proportional to the number of hyperedges in this slot. Given the width w of a vertical edge, the width W i of a time slot T i , composed of m edges, is given by W i = m × (w + e T i ) + e T i , where e T i is the edge padding selected for the time slot T i . This parameter can be modified by the user to change the width of time slots.

When multiple occurrences of the same hyperedge occur within a time slot (e.g., multiple contracts between the exact same persons), they all appear individually by default. An option allows users to collapse them into a single hyperedge that appears slightly thicker until it reaches a maximum edge width (Figure 7). This decreases the width of the time slot by (w + e T i ) × (n -1), where n is the number of repeated occurrences.

Ordering

We developed several vertex and edge ordering strategies which modify the layout and address different needs.

Vertex ordering. Vertex position remains constant in all the time slots and determines the length of the hyperedges, but different orderings help perform different tasks, e.g., bringing together highly connected vertices may reveal similarities. It may also reveal communities and outliers [START_REF] Behrisch | Matrix Reordering Methods for Table and Network Visualization[END_REF]. In our prototype users have the following ordering options:

• Original: vertices are ordered by ID. This order is useful in application domains that have a canonical vertex order that practitioners are trained to use. • Chronological: vertices are sorted by chronological appearance (default, see Figure 2). It moves the names involved in the early contracts to the top, and the names appearing later are down below. If two vertices have their first edge in the same time-slot, the one with the higher degree appears on top. • Alphabetical: useful to find vertices by name in long lists, which is critical for static or printed displays without search capability.

• Degree: vertices with a higher degree (higher number of connections through all the time slots) appear on top. • Group: the vertices are first ordered according to the "group" attribute. This attribute may have been computed by a clustering algorithm or can be intrinsic to the dataset (e.g., person affiliation). Within each group, vertices are sorted chronologically. Sorting by group helps differentiate withingroup versus between-group connections [START_REF] Rodrigues | Group-in-a-box layout for multi-faceted analysis of commu[END_REF] (Figure 5). • Reverse Cuthill McKee: this ordering tends to reduce the length of the edges [45]. • Spectral: tries to move vertices belonging to the same cluster close-by [START_REF] Behrisch | Matrix Reordering Methods for Table and Network Visualization[END_REF]. • Barycenter: similar to Spectral but uses a fast heuristics [START_REF] Mäkinen | The barycenter heuristic and the reorderable matrix[END_REF]. Van den Elzen et al. [START_REF] Van Den Elzen | Dynamic Network Visualization with Extended Massive Sequence Views[END_REF] also introduced an ordering method to move similar vertices far-away from each other and favor long edges. In PAOH, long edges are detrimental to hyperedge packing and to readability so we chose not to include that ordering method.

Edge ordering. Time slots are always displayed by their natural chronological order, but within each time slot, the ordering of the edges can be changed. By default, the edges are sorted according to the order provided by the first vertex of the hyperedge. The edges can also be ordered by line length (recommended when packing is needed-see section 3.6 and Figure 5).

Visual Attributes

To address specific needs, visual attributes can be configured using control panels.

Visual attributes of vertices. The basic layout was designed to remain monochrome to allow the use of color for specific needs. For example, it can be used to color the vertex background (Figure 5left) or the dots (Figure 5-right) according to the vertex group attribute. Figure 5 shows two examples using a sample dataset with two time slots (from the synthetic dataset used by [START_REF] Bach | GraphDiaries: Animated Transitions andTemporal Navigation for Dynamic Networks[END_REF]). The left example uses background color; it clearly highlights groups but also how some vertices are absent in the first or the second time slot. It also shows cases where vertices group change over time. This encoding is most effective when the group changes remain limited, otherwise the evolution of connections between groups become difficult to perceive.

Coloring the dots produces a more subtle encoding but highlights the topology of the network better, such as inter-group relationships. In the example of Figure 5-right, the blue group has just one connection with the purple group in the first time slot, while in the second time slot, the number of connections between the groups increases.

Visual attributes of hyperedges. If color is not used to show the group attribute, consecutive hyperedges can be shown using alternate colors in the hope of facilitating the visual tracking of long lines. By default, we use green and purple. This may help the eye following long lines involving multiple visual saccades, and be useful for large printed hypergraphs. This option is turned off by default. Its effectiveness needs to be tested, but the participants of the usability test found it confusing. We have also experimented with providing multiple options such as dashed lines or varying line widths, but our participants also found them distracting or confusing so we ended-up not providing them by default.

Visual attributes at the intersection. The role of a vertex of a hyperedge can be marked with a symbol that can depict, e.g., the first author on a publication. The use of symbols for representing roles was implemented after a suggestion of one of the practitioners who worked with us in one of the case studies (section 5.2). She was interested in knowing the role of the persons who appeared in contracts, as either primary contractor, secondary, or witness. Currently, we only support one vertex to have a different role in each hyperedge, but we will support more roles in the future.

Numerical Summaries

The grid-like design of PAOH lends itself naturally to the inclusion of summaries on the side of the display. In our prototype, bars are placed on the left of vertices labels. They can indicate the number of hyperedges or the number of time slots where a vertex is present. Similarly, at the top of the time slot labels, bars indicate for each time slot either: the number of hyperedges, the number of nodes, or the average number of nodes per hyperedge. Other metrics could easily be added if asked by our partners.

Interaction

We now describe the interaction methods, from simple to advanced.

Highlighting relationships. Hovering on a vertex label (e.g., John) highlights in bold all the hyperedges and all the vertices it is connected to (e.g., Figure 6-left). Hovering over the area at the intersection of John's vertical line and a time slot highlights all his contracts in that particular period. Finally, hovering over the label of a time slot highlights all the contracts and all the people active in this time slot. Highlighting also updates the numerical summaries according to the selected items (Figure 6).

Revealing similar edges. Hovering over a hyperedge (e.g., a contract) highlights all the vertices it connects to and also highlights similar hyperedges. By default it highlights all the other hyperedges that have the same vertices and more, using a thicker line (Figure 6right). A tooltip option can be enabled to display additional details of a highlighted item (details on demand). It reveals exact dates and all the information related to the highlighted item (vertex or hyperedge). Finally, the arrow keys of the keyboard can be used to help users systematically review all vertices or hyperedges, browsing through the items one by one.

Selection. Selection has a similar behavior as hovering but the highlighting is persistent. Multiple selections reveal the union of all the edges (in bold), their intersection (bolder), and the dots corresponding to the selected nodes in the intersection are filled with black to make them easier to spot.

Filtering. A quick way to reduce the size of the dataset is to filter by one or more vertices. A double click on a vertex or searching a vertex name in the search box filters out all the vertices that are not connected to it (Figure 10). Hyperedges between remaining vertices that do not involve the selected vertex can either be removed entirely, or be grayed out (default). Grayed-out dots reveal that visible vertices have relations with other vertices that have been filtered out.

Zooming and Scrolling. Before scrolling becomes needed, users can reduce the vertices height and the time slot width. They can also choose to temporarily fit all the data in the available horizontal and/or vertical space to get an overview, even at the cost of reducing the readability of labels. When items that should be highlighted fall outside the visible portion of the display, colored hints are shown in the scroll bars. Small green bars for highlights, orange bars for selections, so that users know that scrolling is needed to see all the highlighted items. Fig. 7: Packing (orange arrows) and collapsing multiple occurrences of the same hyperedge (blue) reduces horizontal space. On the left is a view before packing, and the right is after packing.

Packing. Packing optimizes the horizontal space and limits scrolling by reorganizing hyperedges in each time slot independently. It reuses the same horizontal position for hyperedges that do not overlap vertically. Optimizing packing is an NP-hard problem, but we use the first fit bin packing approximation algorithm [START_REF] Coffman | Approximation Algorithms for Bin Packing: A Survey[END_REF] that inserts each edge in turn, from left to right, where they can fit without overlap. This heuristic offers an excellent trade-off between speed and effectiveness. The orange arrows in Figure 7 highlight how packing changes the order of edges. In particular, the rightmost edges in the first time slot, labeled with "1803", are shifted to the first three positions, because there is room to accommodate the edges. This shift saves the horizontal space of three edges. The resulting layout will depend on the vertex and edge ordering, and on the dataset but packing is always detrimental to readability. If the hypergraph associated with time slot (T i ) is sparse, then the packing will have a great impact in reducing the horizontal space needed to render it (see Figure 2 in supplementary materials).

Implementation

Our prototype is available at https://aviz.fr/paohvis. It is implemented in about 5000 lines of Dart [START_REF] Bracha | The Dart Programming Language[END_REF], a language compiled to JavaScript to run inside web browsers. It uses the Canvas API for fast drawing; our implementation can visualize hundreds of vertices (limited by vertical scrolling) and thousands of hyperedges (limited by horizontal scrolling). The orderings are computed using the reorder.js library [START_REF] Fekete | Reorder.js: A JavaScript Library to Reorder Tables and Networks[END_REF].

FORMATIVE USABILITY STUDY

To identify usability problems, gather feedback, and improve the prototype, we have performed a formative user study. A secondary goal was to verify that users could interpret the PAOH visualization, and perform complex tasks by combining multiple features and functionalities of PAOH without training. Before the study, we conducted a pilot with 2 participants to test the procedure. As we conducted the study, we fixed bugs and improved the prototype to address the problems encountered by participants or their suggestions. Examples of improvements include placement of labels, the addition of summary charts, highlighting similar edges, depicting vertices roles, and choosing better default values for options.

Procedure

Nine participants were recruited from our local research community (students or more senior researchers) and told that they were going to be looking at co-authorship networks. The participants used a desktop computer with an ordinary keyboard and mouse, and were encouraged to think-aloud at all time. The study was organized in 2 main phases and every participant followed the same procedure. Each session lasted for about 20 minutes.

In the first phase (Discovery): participants were shown a small publication dataset using the PAOH visualization. Participants were initially asked to describe what they were seeing in the visualization without receiving any training. Then they were encouraged to explore and interact with the toolbar and the visualization on their own and discover how the tool works. If participants needed help, the observer answered their questions and noted the difficulty participants had encountered.

In the second phase (Task): participants were asked to perform a list of tasks, as reported in Section 4.2. At the end of each session, participants were asked to provide feedback.

To provide a meaningful situation and encourage participants to explore the data, we used two datasets of publications from two local research labs. Participants were familiar with those labs and many current members-but not all, and had not looked at the history of publications. During the Discovery phase, the coauthorship network of people from the smallest lab was used, with 57 authors and 36 publications over 6 semesters, from 2015 to 2017 (Figure 8). The whole dataset fits in the screen, so no scrolling was required. A larger dataset was used for the Tasks phase, with the publications of both labs, i.e., 371 authors and 312 publications over a time span of 20 semesters, from 2008 to 2017 (Figure 9). Users had to zoom or scroll to see the entire dataset.

We selected realistic tasks, from simple to complex, that someone interested in analyzing co-authorship networks would have in real life. The complexity of tasks is discussed in Ahn et al. [START_REF] Wook Ahn | A Task Taxonomy for Network Evolution Analysis[END_REF], and relates to "analysts [who] . . . often combine tasks into compound tasks in order to explore more complex questions". We focused on tasks that used the hypergraph nature of the data. In order to provide answers, tasks required the combination of multiple elements and features of the design, so we could observe what strategies users would use.

Results

Discovering how to interpret a PAOH visualization. At the start (i.e., without any interaction), all participants guessed correctly that authors were arranged in rows and publications in columns. They guessed that a dot on a line meant that the author associated with the row was a co-author of the publication. No one seemed confused by the varying width of the semester time slots. Three participants immediately guessed that drips meant filtered-out people, and all participants understood it after they interacted with the system.

Once they were able to interact with the system, participants understood the color coding. However, there was some confusion about special cases where an author had left a team but remained co-author on later papers; no background color was interpreted as a bug by some participants-the observer had to clarify the meaning.

In the early pilot, the (default) use of alternate colors for the edges was confusing participants. Seven participants commented that alternating colors might help to differentiate neighboring lines.

Two said that it would not be useful anyway. Only two kept the alternate colors, so we turned it off by default.

There was no issue with the barcharts on the sides and the scrollbars. The four participants who noticed the hints on the scrollbars found them useful. At first, zooming was challenging, so we improved the controls and added two buttons to fit the display to the screen size, horizontally and vertically.

At first, the interface used the technical terms of vertex, hyperedge, time slot, and group. Several participants were not familiar with those terms so we included the definition of domain dependent terms-author, publication, semester, and team-in the dataset to customize the interface. This eliminated the confusion.

Filtering was more challenging to understand. We added a simple animation to reveal how the display changed when filtering, which was helpful. The presence of grayed out edges, i.e., edges one hop away from selected vertices, was confusing to some participants, so we added an option to hide them to simplify the results. They are now hidden by default. Finally, some participants did not understand how filtering an author affected the drips and we still need to improve the feedback of filtering. We plan to modify the drip labeling and to group authors visible as drips according to the reason they were filtered out, i.e., either because of filtering by degree or by one or more specific vertices.

Tasks. In the following, we review each task one by one. T1. Find all the papers Petra Isenberg and Danyel Fisher wrote together.

All participants were able to answer correctly. Many strategies were used to solve this task; one participant even listed 4 strategies, but all of them were trivial to perform. They usually searched for one of the authors (either with the search function or by sorting the authors alphabetically), then visually answered the task or by watching the barcharts while using highlighting on the second author. Multiple selection also helped. T2. Find the 3 people Petra Isenberg has written papers with the most often.

The first part of the task was trivial to perform: all participants immediately selected and filtered on Petra. For the second part, the first two participants attempted the task visually by looking at rows with many dots, and carefully counted the dots. The other participants all used the barcharts, which were changed to update when highlighting or selecting to simplify this seemingly generic task, and got the correct answer. T3. Looking at Petra's network, are there papers with the exact same co-authors in different semesters? Tell me the names.

We had selected this task to be difficult, in the sense of Ahn et al. [START_REF] Wook Ahn | A Task Taxonomy for Network Evolution Analysis[END_REF]. To perform this tasks, users had to split the high-level task into simpler sub-tasks, and there were multiple ways of performing this decomposition, none of them being trivial. We were surprised that 5 participants were able to answer it correctly. Indeed all participants reported it to be challenging. Most participants did not have access to the highlighting of similar edges (which was just added recently). One early participant abandoned without trying, the others devised a valid strategy but did not always complete the task when it was tedious. One strategy used to give the correct answer by three participants was to first look for lines of the same length and then check if they had the same dots, either visually or by highlighting the names of the co-authors associated with the edge. One participant reordered the names by one of the heuristics that reduce line length, guessing that shorter edges would have more chances to share the same coauthors. An effective strategy (used correctly by two participants who had access to the feature) Fig. 9: Co-authorship network from the two labs combined publications-used in the Tasks phase of the usability study. Coauthors with only one or two papers were moved to the drips. was to use the highlighting of similar edges. They would hover over an edge-which highlighted other edges with at least the same authors-and then repeated for all edges one by one. After locating the edges, they used the tooltip to get the name of the publication.

Of course tools designed specifically for co-authorship networks may provide a custom function for this complex task, but our usability study suggests that users are able to combine basic PAOH functionalities to answer very complex task. T4. Anything else you can say about Petra's publications and how her co-authorship evolved?

To solve this open-ended question all participants filtered on Petra. They correctly commented that Petra was quite active, and published regularly except on the second semesters of 2011 or 2012, proposing hypotheses as to why. They remarked that Petra's long term collaborations involved mainly senior researchers. They noticed that no publication had Petra as a single author. Several participants commented that they would prefer to remove all grayed out publications entirely since it made it harder to focus only on Petra's network. This option was introduced for the last participant, who used it while answering several tasks. T5. Can you tell if over time papers have more co-authors than before, less, or about the same? T5 was quite difficult as well; it is described as an Inferential Compound Tasks in Ahn et al. [START_REF] Wook Ahn | A Task Taxonomy for Network Evolution Analysis[END_REF]. All the information is visible to answer but users need to carefully count and average the dots. Early participants only "guess-estimated", so after the third participant, we introduced the option "average # of authors per publications" to the time slot summary charts. The bars-and the menu to change to the appropriate metric-were successfully used by 4 out of the 6 participants who had access to them. The remaining two participants did not think of using the summary bars.

T6. What can you tell me about the collaboration between teams?

This was also an open question. All participants tried one of the color by group options (background or dots) and then used the author ordering by group (team). Participants reported that some authors changed team; that the smallest team was created on 2015; that there was more collaboration within teams than collaborations between teams, and that one author from the smallest team (who had belonged to the largest team in the past), was mainly responsible for the collaboration.

After completing the tasks, participants could explore further and comment on the overall experience. Many participants expressed that they liked the filtering because it reduced the amount of information displayed. Participants who had access to the highlighting of similar edges said that this was very helpful; one of them pointed out that it could be helpful in other contexts. Some participants suggested improvements to the control panel layout and the layout was improved, even though we aim at continuously improving the UI.

In summary, while most participants were able to interpret all basic features of the PAOH visualization without any training, some interactive features were more challenging and should be the focus of a training video to be accessible to all. Many participants were able to complete even the most challenging tasks, and most devised adequate strategies that would lead to the correct answer. Some participants were clearly not motivated enough to complete complex tasks.

In addition to structured formative usability study, we also collected feedback from about fifty additional users during demonstrations, labs, and exploration of possible case studies, which generally confirmed the study results and provided suggestions for improvements. Examples are the use of different icons of the dots in order to identify the role of the vertex in the hyperedge (e.g. a star for the lead author), or aggregating vertices according to an attribute, in order to scale further. As is always the case, users wish to be able to access the source documents directly from the visualization, and possibly correct mistakes in the coded data.

During labs, they understood the benefit of the simplicity of PAOH, and that external tools such as spreadsheets were appropriate and effective for cleaning-up and transforming their data, instead of bloating PAOH with data manipulation functions. In the future, we hope that PAOH can be integrated into visualization suites such as the Vistorian [START_REF] Bach | Small MultiPiles: Piling Time to Explore Temporal Patterns in Dynamic Networks[END_REF], allowing users to analyze their data from complementary visual representations and perspectives.

USE CASES

Simple graphs can be found in abundance in open data repositories, but dynamic hypergraphs data are less common. To motivate and showcase the PAOH representation, we describe two use cases: a trade network in the 17 th century, a study on the circulation of entrepreneurs in Piedmont during the 18 th century.

Trade Network in the 17 th Century

We worked with a professional historian studying the role and power of a non-married woman, Marie Boucher, a merchant living in the 17 th century in Nantes, France. Dufournaud et al. [START_REF] Dufournaud | L'analyse des réseaux, une aide à penser : réflexions sur les stratégies économique et sociale de Marie Boucher, marchande à Nantes au XVIIe siècle[END_REF] analyzed the trade relations among people linked to her from contracts (called Actes in the visualization) found in multiple archives. An important part of the work was to understand-and present-the changing relationships that Boucher had with other merchants over time.

This case study is representative of a large category of studies in social history in which people are connected through dated documents where they are mentioned, such as contracts, but also diaries, and justice decisions. Such datasets are then carefully curated and studied in great depth and details by humanists, over long periods of time as the research progresses. The acquisition and curation process is very tedious: documents may have to be discovered in archives, transcribed, and annotated manually (because transcription and entity extraction algorithms do not work with old French or old English manuscripts). As a result, many studies generate moderately large datasets with twenty to a hundred person, and hyperedges connecting two to a dozen people. The Boucher dataset is representative of this large category of studies. It is composed of 59 contracts mentioning 90 persons overall. Each contract can be modeled as a hyperedge linking several persons. Each contract has a signature date (no duration). Modeling the same data as a standard graph, these 59 hyperedges would become 488 edges, one for each relation between a pair of persons. Modeling the hypergraph as a bipartite graph would generate an additional 59 nodes and 322 edges.

Our case study partner had already studied the dataset at length (see work [START_REF] Dufournaud | L'analyse des réseaux, une aide à penser : réflexions sur les stratégies économique et sociale de Marie Boucher, marchande à Nantes au XVIIe siècle[END_REF]). The relationships had been visualized using two separate representations: node-link diagrams and TimeArcs [START_REF] Dang | TimeArcs: Visualizing Fluctuations in Dynamic Networks[END_REF], shown in the supplementary material. The TimeArcs visualization shows the dynamic graph that revealed the connections between persons over time, but not showing the documents. The initial analysis had been done using these two representations only.

Our collaborator found the PAOH representation clear and was able to understand it after a very brief description. She quickly commented that the same analysis required only one visualization and could be done more accurately. Some new findings were identified. For example in 1667, Marie Boucher had two contracts with Jean Boucher (line 3) and two others with Julien Gérard Seigneur de Nays (line 9)-while Dufournaud et al. had assumed that two persons connected during the same year appeared in only one contract. Using the highlighting of similar hyperedges, she noted surprising repetitions over the years. Our collaborator also explained that three main phases had been identified after the lengthy prior analysis and inspection of original documents: an initial phase from 1660 to 64 with mostly French trading, a second phase with cross Atlantic trade from 1666 to 68, and a third expansion phase until 1675, after which Marie disappears from the records until a 1689 mention of her being deceased. She stated that those phases were clearly apparent in the PAOH visualization that represents time and connections simultaneously. She commented that it provided good narrative support, and would be useful to communicate the findings during talks and in print. In addition, the color coding was found useful to represent the strong-and changing-family connections.

Circulation of Entrepreneurs in Piedmont During the 18 th Century

We worked with two professional historians analyzing the evolution of a network of entrepreneurs in Piedmont (a region of Italy) in the 18 th century [START_REF] Cristofoli | Temporalités à l'oeuvre dans les chantiers du bâtiment[END_REF]. The aim of the study was to understand the ties between building contractors and their mobility through contracts established by cities. Cristofoli and Rolla analyzed 330 archived contracts, extracting the contractors involved and their professions, roles, cities of origin, as well as the city and location of the projects during the 1711-1742 period. It included 594 different individuals.

To make sense of their data, the authors had originally used several visualizations such as Figure 10-left, using a bipartite network clustered by work location and linking to the construction sites. They thought they knew their dataset well.

Using PAOH, the historians were able to make new observations. For example, construction appears clearly as a seasonal activity with breaks in winter (Figure 10-right), where September to December is almost empty except in 1713. The original analysis missed both the seasonal pattern and the 1713 exception deserving further investigation. The visualization also revealed that the collaborations included people from more diverse origins over time. This insight was unexpected as it goes against dominant beliefs in history according to [START_REF] Cristofoli | Temporalités à l'oeuvre dans les chantiers du bâtiment[END_REF].

Coloring by the profession of contractors, the historians saw that only a few professions, usually two, were present in each contract. In addition, they saw that some contractors reported different professions over time so our collaborators are now researching whether this is tied to an underlying strategy used to win contracts or a simple inconsistency in reporting professions. In a few sessions, PAOH was able to deeply engage the researchers and generate new insights. The rich data they gathered suggested many improvements to PAOH, such as the possibility to encode more than one role per hyperedge, and to dynamically choose the attribute that should be visualized as group using colors. Initially, we chose to represent the region of origin, but it could be mapped to other attributes, such as the current region or the stated profession.

CONCLUSION

In this article, we introduced Parallel Aggregated Ordered Hypergraph, a technique to visualize dynamic hypergraphs. We described the technique as well as its visual encodings, interactions, layout and simplification operations, with examples using real data from two application domains. A usability study with 9 participants demonstrates that the technique is easy to learn, and can be used to answer complex questions. Finally, two case studies with historians suggest that PAOH provides a new and effective way to analyze the medium size hypergraphs commonly produced Fig. 10: On the left, the static bipartite node-link diagram originally published by [START_REF] Cristofoli | Temporalités à l'oeuvre dans les chantiers du bâtiment[END_REF] connecting the contractors and contracts in which they are mentioned, clustered by region of origin, and also linked to their construction site visualized as large round points. On the right, a selection of the network showing the contracts signed by at least one member of the "Menafoglio" family, visualized using Paohvis with monthly time slots, colored by region of origin of the contractors. by digital humanities projects and that modeling relationships as dynamic hypergraphs can lead to more accurate analyses.

Future work include all the improvements asked by our partners related to roles, managing multiple groups, and integration with the suite of visualizations of the Vistorian. Longer term plans include working on scalability. One good property of hypergraphs is that, when aggregating multiple vertices, they remain hypergraphs. Dynamic hypergraph visualization is still in its infancy but we hope that PAOH will stimulate additional innovation in this area.

Fig. 2 :

 2 Fig. 2: PAOH visualization of a small fictitious dynamic hypergraph of 18 th century business relationships evolving over 4 years among thirteen people.

Fig. 3 :

 3 Fig. 3: Comparison of the representation of the same time slot using regular edges (on the left) versus hyperedges (on the right)

Fig. 5 :

 5 Fig. 5: Two visualizations of the same dataset with two time slots, sorted and colored by the group attribute. Values of the group are associated with colors that fill the background (left) or the dots (right). Both reveal 7 groups, and 5 vertices not belonging to any group.

Fig. 6 :

 6 Fig. 6: Highlighting in PAOH. Left: Hovering over John highlights all his contracts and the names of the people involved. Right: Hovering over a contract between John and Joseph reveals contracts including at least John and Joseph, also in other time slots).

Fig. 8 :

 8 Fig. 8: Co-authorship network of the small lab's publications-used in the Discovery phase of the usability study. Co-authors with only one paper are filtered out.

Paola

  Valdivia is a Postdoc researcher at IN-RIA Project Team AVIZ. She obtained her PhD from the Mathematical and Computer Sciences Institute of University of S ão Paulo -S ão Carlos, Brazil. Her research interests are in Network Visualizations, Information Visualization and Visual Analytics. Paolo Buono is assistant professor at the Department of Computer Science of the University of Bari, Italy. He is the coordinator for Information Visualization and Visual Analytics at the IVU Lab. He holds a PhD in Computer Science on Visual Data Analysis. His current research interests include Visual Analytics, Information Visualization, HCI, Mobile Applications, Time Series. Catherine Plaisant is a research scientist at the University of Maryland, College Park and assistant director of research of the University of Maryland Human-Computer Interaction Lab. She is also an INRIA International Chair. Her research focuses on human-computer interaction and visualization. Nicole Dufournaud is an associate researcher in the LaD éHiS and Gender History research groups. She has a PhD in Modern History at EHESS. Her research focuses on women's roles and powers in the 16th century in western France". Jean-Daniel Fekete is the Scientific Leader of the INRIA Project Team AVIZ that he founded in 2007. He received his PhD in Computer Science in 1996 from University of Paris Sud, France. His main research areas are Visual Analytics, Information Visualization and Human Computer Interaction. He is a Senior Member of IEEE.

ACKNOWLEDGMENTS

We thank our collaborators Pascal Cristofoli and Nicoletta Rolla for providing the motivation for this work and for helping us validate our design. We also thank our colleagues from the University of Maryland HCIL, from Inria, Aviz and Ilda, and the students from the University of Bari IVU lab for their feedback.


Robin Algayres
email: robin.algayres@inria.fr

Mohamed Salah Zaiem
email: mohamed.zaiem@inria.fr

Benoît Sagot
email: benoit.sagot@inria.fr

Emmanuel Dupoux
email: emmanuel.dupoux@inria.fr

Evaluating the reliability of acoustic speech embeddings

Keywords: unsupervised speech processing, speech embeddings, frequency estimation, evaluation metrics, representation learning, k-nearest neighbours

Speech embeddings are fixed-size acoustic representations of variable-length speech sequences. They are increasingly used for a variety of tasks ranging from information retrieval to unsupervised term discovery and speech segmentation. However, there is currently no clear methodology to compare or optimize the quality of these embeddings in a task-neutral way. Here, we systematically compare two popular metrics, ABX discrimination and Mean Average Precision (MAP), on 5 languages across 17 embedding methods, ranging from supervised to fully unsupervised, and using different loss functions (autoencoders, correspondance autoencoders, siamese). Then we use the ABX and MAP to predict performances on a new downstream task: the unsupervised estimation of the frequencies of speech segments in a given corpus. We find that overall, ABX and MAP correlate with one another and with frequency estimation. However, substantial discrepancies appear in the fine-grained distinctions across languages and/or embedding methods. This makes it unrealistic at present to propose a task-independent silver bullet method for computing the intrinsic quality of speech embeddings. There is a need for more detailed analysis of the metrics currently used to evaluate such embeddings.

Introduction

Unsupervised representation learning is the area of research that aims to extract units from unlabelled speech that are consistent with the phonemic transcription [START_REF] Jansen | A summary of the 2012 jhu clsp workshop on zero resource speech technologies and models of early language acquisition[END_REF][START_REF] Versteegh | The zero resource speech challenge 2015[END_REF][START_REF] Dunbar | The zero resource speech challenge 2017[END_REF][START_REF] Dunbar | The zero resource speech challenge 2019[END_REF]. As opposed to text, speech is subject to large variability. Two speech sequences with the same transcription can have significantly different raw speech signals. In order to work on speech sequences in an unsupervised way, there is a need for robust acoustic representations. To address that challenge, recent methods use speech embeddings, i.e. fixed-size representations of variable-length speech sequences [START_REF] Kamper | Truly unsupervised acoustic word embeddings using weak top-down constraints in encoder-decoder models[END_REF][START_REF] Holzenberger | Learning word embeddings: Unsupervised methods for fixedsize representations of variable-length speech segments[END_REF][START_REF] Riad | Sampling strategies in siamese networks for unsupervised speech representation learning[END_REF][START_REF] Maas | Word-level acoustic modeling with convolutional vector regression[END_REF][START_REF] Levin | Fixeddimensional acoustic embeddings of variable-length segments in low-resource settings[END_REF][START_REF] Chung | Audio word2vec: Unsupervised learning of audio segment representations using sequence-to-sequence autoencoder[END_REF][START_REF] Chung | Unsupervised cross-modal alignment of speech and text embedding spaces[END_REF][START_REF] Renshaw | A comparison of neural network methods for unsupervised representation learning on the zero resource speech challenge[END_REF]. 1 Speech embeddings can be used in many applications, such as key-word spotting [START_REF] Hazen | Query-by-example spoken term detection using phonetic posteriorgram templates[END_REF][START_REF] Levin | Segmental acoustic indexing for zero resource keyword search[END_REF][START_REF] Wang | Segmental audio word2vec: Representing utterances as sequences of vectors with applications in spoken term detection[END_REF], spoken term discovery [START_REF] Park | Unsupervised pattern discovery in speech[END_REF][START_REF] Lee | Unsupervised lexicon discovery from acoustic input[END_REF][START_REF] Räsänen | Unsupervised word discovery from speech using automatic segmentation into syllable-like units[END_REF], and segmentation of speech into words [START_REF] Goldwater | A bayesian framework for word segmentation: Exploring the effects of context[END_REF][START_REF] Kamper | A segmental framework for fully-unsupervised large-vocabulary speech recognition[END_REF][START_REF] Kawakami | Unsupervised word discovery with segmental neural language models[END_REF]. It is convenient to evaluate the reliability of speech embeddings without being tied to a particular downstream task. One way to do that is to compute the intrinsic quality of speech embeddings. The basic idea is that a reliable speech embedding should maximize the information relevant to its type and minimize irrelevant tokenspecific information. Two popular metrics have been used: the mean average precision (MAP) [START_REF] Carlin | Rapid evaluation of speech representations for spoken term discovery[END_REF] and the ABX discrimination score [START_REF] Schatz | Evaluating speech features with the minimal-pair abx task: Analysis of the classical mfc/plp pipeline[END_REF]. 1 A speech sequence is a non-silent part of the speech signal (not necessarily a word). It can be transcribed into a phoneme n-gram.

ABX and MAP are mathematically distinct yet they are expected to correlate well with each other as they both evaluate the discriminability of speech embeddings in terms of their transcription. However, [START_REF] Holzenberger | Learning word embeddings: Unsupervised methods for fixedsize representations of variable-length speech segments[END_REF] revealed a surprising result: the best model according to the ABX, is also the worst one according to the MAP. Following [START_REF] Holzenberger | Learning word embeddings: Unsupervised methods for fixedsize representations of variable-length speech segments[END_REF]'s results, we observed that this kind of discrepancies is much more common than we had expected. If a model performs well according to the MAP and bad according to the ABX, which metric should be trusted? For research in this field to go forward, there is a need to quantify the correlation of these two metrics.

In this paper, we wanted to go further and check that MAP and ABX can also predict performances on a downstream task. Such tasks are numerous, but one of them has not yet received enough interest: the unsupervised frequency estimation. We define the frequency of a speech sequence as the number of times the phonetic transcription of this sequence appears in the corpus. When dealing with text corpora, frequencies can be computed exactly with a lookup table and are used in many NLP applications. In the absence of labels, deriving the frequency of a speech sequence becomes a problem of density estimation. Estimated frequencies can be useful in representation learning by enabling efficient sampling of tokens in a speech database [START_REF] Riad | Sampling strategies in siamese networks for unsupervised speech representation learning[END_REF]. Also, frequencies could be used for the unsupervised word segmentation using algorithms similar to those used in text [START_REF] Goldwater | A bayesian framework for word segmentation: Exploring the effects of context[END_REF].

In Section 2, we present the range of embedding models that can be grouped in five categories of increasing expected reliability: hand-crafted, unsupervised, self-supervised, supervised plus a top-line embedding. In Section 3, we present the MAP and ABX metrics and introduce our frequency estimation task. In Section 4, we present results on the five speech datasets from the ZeroSpeech Challenge [START_REF] Versteegh | The zero resource speech challenge 2015[END_REF][START_REF] Dunbar | The zero resource speech challenge 2017[END_REF][START_REF] Dunbar | The zero resource speech challenge 2019[END_REF]. From these results, we draw guidelines for future improvements in the field of acoustic speech embeddings.

Embedding Methods

Acoustic features

Neural networks learn representations on top of input features. Therefore we used two types of acoustic features known as the log-MEL filterbanks (Mel-F) [START_REF] Davis | Comparison of parametric representations for monosyllabic word recognition in continuously spoken sentences[END_REF] and the Perceptual Linear Prediction (PLP) [START_REF] Hermansky | Perceptual linear predictive (plp) analysis of speech[END_REF]. These two features can be considered as two levels of phonetic abstraction: a high-level one (PLP) and a low-level one (Mel-F). Formally, let us define a speech sequence st by x1,x2,...,xT , where xi ∈ R n is called a frame of the acoustic features. T is the number frames in the sequence st. In our setting, these frames are spaced out every 10 ms each representing a 25 ms span of the raw signal.

Hand-crafted model: Gaussian downsampling

Holzenberger and al. [START_REF] Holzenberger | Learning word embeddings: Unsupervised methods for fixedsize representations of variable-length speech segments[END_REF] described a method to create fixedsize embedding vectors that requires no training of neural net-works: the Gaussian down-sampling (GD). Given a sequence st, l equidistant frames are sampled and a Gaussian average is computed around each sample. It returns an embedding vector et of size l × n for any size T of input sequences. Therefore, given our two acoustic features, two baselines model are derived: the Gaussian-down-sampling-PLP (GD-PLP) and the Gaussian-down-sampling-Mel-F (GD-Mel-F).

Similarly, we derived a simple top-line model. Instead of using hand-crafted features, we can use the transcription of a given random segment. Each frame xi in a sequence st will be assigned a 1-hot vector referring directly to the phoneme being said. This model goes through the same Gaussian averaging process to form the Gaussian-down-sampling-1hot (GD-1hot) model. This model is almost the true labels notwithstanding the information loss due to compression.

Unsupervised model: RNNAE

A more elaborate way to create speech embeddings is to learn them on top of acoustic features using neural networks. Specifically, recurrent neural networks (RNN) can be trained with back-propagation in an auto-encoding (AE) objective: the RN-NAE [START_REF] Holzenberger | Learning word embeddings: Unsupervised methods for fixedsize representations of variable-length speech segments[END_REF][START_REF] Chung | Audio word2vec: Unsupervised learning of audio segment representations using sequence-to-sequence autoencoder[END_REF]. Formally, the model is composed of an encoder network, a decoder network and a speaker encoder network. The encoder maps st to et, a fixed-size vector. The speaker encoder maps the speaker identity to a fixed size vector spkt. Then, the decoder concatenate et and spkt and maps them to ŝt, a reconstruction of st. The three networks are trained jointly to minimize the Mean Square Error between ŝt and st.

2.4. Self-supervised and supervised models: CAE, Siamese and CAE-Siamese

Advanced training objectives

We consider two popular embedding models. They are also encoder-decoders but they use additional side information. One is trained according to the Siamese objective [START_REF] Riad | Sampling strategies in siamese networks for unsupervised speech representation learning[END_REF][START_REF] Thiollière | A hybrid dynamic time warping-deep neural network architecture for unsupervised acoustic modeling[END_REF] the other is a correspondence auto-encoder (CAE) objective [START_REF] Renshaw | A comparison of neural network methods for unsupervised representation learning on the zero resource speech challenge[END_REF]. Both models assume a set of pairs of sequences from the training corpus. Positive pair are assumed to have the same transcription, negative pairs, different transcriptions. Let pt = (st, s t , y) where (st, s t ) is a pair of sequences of lengths T and T . A binary value y indicates the positive or negative nature of the pair. We will see how to find such pairs in the next sub-section.

The CAE objective uses only positive pairs. The autoencoder is asked to encode st into et and decode it into ŝt. The speaker encoder network is used similarly as for the RNNAE. To satisfy the CAE objective, ŝt has to minimise the Mean Square Error between ŝt and s t . It forces the auto-encoder to learn a common representation for st and s t .

The Siamese objective does not need the decoder network. It encodes both st and s t and forces the encoder to learn a similar or different representation depending on whether the pair is positive or negative.

Ls(et, e t , y) = y cos(et, e t ) -(1-y) max(0, cos(et, e t )-γ)
where cos is the cosine similarity and γ is a margin. This latter accounts for negative pairs whose transcriptions have phonemes in common. These pairs should not have embeddings 'too' far away from each other. The CAE and Siamese objective can also be combined into a CAE-Siamese loss by a weighted sum of their respective loss function [START_REF] Last | Unsupervised feature learning for speech using correspondence and siamese networks[END_REF].

Finding and choosing pairs of speech embeddings

Finding positive pairs of speech sequences is an area of research called unsupervised term discovery (UTD) [START_REF] Park | Unsupervised pattern discovery in speech[END_REF][START_REF] Lee | Unsupervised lexicon discovery from acoustic input[END_REF][START_REF] Räsänen | Unsupervised word discovery from speech using automatic segmentation into syllable-like units[END_REF][START_REF] Thual | A k-nearest neighbours approach to unsupervised spoken term discovery[END_REF]. Such UTD systems can be DTW alignment based [START_REF] Park | Unsupervised pattern discovery in speech[END_REF] or involve a k-Nearest-Neighbours search [START_REF] Thual | A k-nearest neighbours approach to unsupervised spoken term discovery[END_REF]. We opted for the latter, as it is both scalable and among the state-of-the-art methods. It encodes exhaustively all possible speech sequences with an embedding model, and used optimized K-NN search [START_REF] Johnson | Billion-scale similarity search with gpus[END_REF] to retrieve acoustically similar pairs of speech sequences (see the details in [START_REF] Thual | A k-nearest neighbours approach to unsupervised spoken term discovery[END_REF]). In our experiments, we used the pairs retrieved by k-NN on GD-PLP encoded sequences to train our self-supervised models (CAE,Siamese, CAE-Siamese).

As a supervised alternative, it is possible to sample 'gold' pairs, i.e pairs of elements that have the exact same transcription. These 'gold' pairs are given to the CAE, Siamese and CAE-Siamese to train supervised models. These supervised models indicate how good these self-supervised models could be if we enhanced the UTD system.

Evaluation metrics and frequency estimation 3.1. Intrinsic quality metrics: ABX and MAP

The intrinsic quality of an acoustic speech embedding can be measured using two types of discrimination tasks: the MAP (also called same-different) [START_REF] Carlin | Rapid evaluation of speech representations for spoken term discovery[END_REF] and ABX tasks [START_REF] Schatz | Evaluating speech features with the minimal-pair abx task: Analysis of the classical mfc/plp pipeline[END_REF].

Let us consider a set of n acoustic speech embeddings: The error rate on this classification task is the ABX score. It is first averaged by type of contrast (all triplets having the same ta and t b ) then average over all contrasts.

((e1 ,
The MAP task forms a list of all possible pairs of embeddings (ea,ex). The model is asked to predict 1 or 0 to indicate if ex and ea have the same type, i.e the same transcription, or not. Formally for a given pair, the model predicts:

y(ea, ex, θ) = 1 d(ea,ex)≤θ
The precision and recall on this classification task are computed for various values of θ. The final score or the MAP task is obtained by integrating over the precision-recall curve.

3.2. Downstream task: unsupervised frequency estimation

3.2.1. The R 2 metric
Here, we introduce the novel task of frequency estimation as the assignment, for each speech sequence, of a positive real value that correlate with how frequent the transcription of this sequence is in a given reference corpus2 . To evaluate the quality of frequency estimates, we use the correlation determinant R 2 between estimation and true frequencies. We compute this number in log space, to take into account the power-law distribution of frequencies in natural languages [START_REF] Zipf | The psycho-biology of language[END_REF]. This coefficient is between 0 and 1 and tells what percentage of variance in the true frequencies can be explained by the estimated frequencies.

k-NN and density estimation

We propose to estimate frequencies using density estimation, also called the Parzen-Rosenblatt window method [START_REF] Parzen | On estimation of a probability density function and mode[END_REF]. Let N be the number of speech sequence embeddings. First, these N embeddings are indexed into a k-NN graph, noted G, where all distances between embeddings are computed. Then, for each embedding, we search for the k closest embeddings in G. Formally, given an embedding et from the k-NN graph G, we compute its k distances to its k closest neighbours (dn 1 ,...dn k ). The frequency estimation is a density estimation function κ of the k-NN graph G that has three parameter: a Gaussian kernel β, the number of neighbours k and the embedding et.

κG(et, β, k) = k i=1 exp -βd 2 n i
This density estimation yields a real number in [1, k], which we take as our frequency estimation. We set k to 2000, the maximal frequency that should be predicted using the transcription of our training corpus (the Buckeye). Then, we must tune β, the dilation of the space of a given embedding model. For each model, we choose β such that it maximises the variance of the estimated log frequencies, thereby covering the whole spectrum of possible log frequencies, in our case [0, log(k)], which is beneficial for power-law types of distribution. Note that the β kernel cannot be too large (resp. small), as it would predict only high (resp. low) values. We compared density estimation with an alternative method: the clustering of speech embeddings. Jansen et al. [START_REF] Kamper | Unsupervised lexical clustering of speech segments using fixed-dimensional acoustic embeddings[END_REF] did a thorough benchmark of clustering methods on the task of clustering speech embeddings. Across all their metrics, the model that performs best is Hierarchical-K-means (HC-K-means), an improved version of K-means for a higher computational cost. HC-K-means is not scalable to our data sets, so we extracted 1% of the Buckeye corpus in order to compare it with our method. A similar size of corpus is used by Jansen et al. [START_REF] Kamper | Unsupervised lexical clustering of speech segments using fixed-dimensional acoustic embeddings[END_REF]. We applied k-NN, K-means and HC-K-means from the python library scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] on three of our models on this subset. For K-means and HC-K-means, we used the hyperparameters that gave the best scores in [START_REF] Kamper | Unsupervised lexical clustering of speech segments using fixed-dimensional acoustic embeddings[END_REF], namely k-means++ initialisation and average linkage function for HC-K-means. On our subset, the ground truth number of clusters is K = 33000. Yet, we did a grid-search on the value of k that maximises the R 2 score for frequency estimation. We found that K-means and HC-K-means perform better for K = 20000. It shows these algorithms are not tuned to handle data distributed according to the Zipf's law. Indeed K-means is subject the so-called 'uniform effect' and tends to find clusters of uniform sizes [START_REF] Wu | The Uniform Effect of K-means Clustering[END_REF].

Density estimation versus clustering

Models

Table 1 shows that even by optimizing the number of clusters K, the k-NN method outperforms K-means and HC-K-means.

Experiments

Data sets

Five data sets at our disposal from the ZeroSpeech challenge: Conversational English (a sample of the Buckeye [START_REF] Pitt | The buckeye corpus of conversational speech: Labeling conventions and a test of transcriber reliability[END_REF] corpus), English, French, Xitsonga and Mandarin [START_REF] Versteegh | The zero resource speech challenge 2015[END_REF][START_REF] Dunbar | The zero resource speech challenge 2017[END_REF]. These are multispeaker non-overlapping (i.e one speaker per file) recordings of speech. All silences were removed using voice activity detection and corrected manually.

Each corpus was split into all possible segmentations to produce random speech sequences as described in [START_REF] Thual | A k-nearest neighbours approach to unsupervised spoken term discovery[END_REF]. Random speech sequences span from 70ms to 1s. Shorter than 70ms sequences may contain less than one phoneme or be illpronounced phonemes. Therefore we removed very short sequences to avoid issues that are out of scope of this study.

The Buckeye sample corpus contains 12 speakers and 5 hours of speech. The French and English corpora being much larger, we reduced their number of speech sequences and speakers to the size of the Buckeye. Mandarin and Xitsonga are smaller data sets and were left untouched.

Training and hyperparameters

Our encoder-decoder network is a specific use of a three-layers bi-directional LSTM as described by Holzenberger et al. [START_REF] Holzenberger | Learning word embeddings: Unsupervised methods for fixedsize representations of variable-length speech segments[END_REF] with hyper-paremeters selected to minimize the ABX error on the Buckeye corpus. The speaker embedding network is a single fully connected layer with fifteen neurons. Our UTD system [START_REF] Thual | A k-nearest neighbours approach to unsupervised spoken term discovery[END_REF] uses the embeddings of the GD-PLP model. A set of speech pairs is returned, sorted by cosine similarity. We selected the pairs that have a cosine similarity above 0.85 as it seemed to be optimal on the Buckeye corpus according to the ABX metric. In comparison, we trained our supervised models with 'gold' pairs, i.e pairs with the exact same transcription.

Each corpus was randomly split into train (90%), dev(5%) and test (5%). Neural networks were trained on the train set, early stopping was done using the dev set and metrics computed on the test set. Specifically, we trained each model on the five training sets using the Buckeye's hyper-parameters.

MAP was ABX were computed on the test sets. Frequency estimation was computed by indexing the five training sets and building k-NN graphs. For each element of a given test set, we searched neighbours and estimated frequencies using the k-NN graphs. We used the FAISS [START_REF] Johnson | Billion-scale similarity search with gpus[END_REF] library that provides an optimised k-NN implementation.

Results

Across models

The results of the two metrics and downstream task are shown in Figure 1 and the following broad trends can be observed.

• Supervised models yield substantially lower performance than the ground truth 1-hot encodings, on all metric and all languages. These supervised models have a margin for improvement as they do not learn optimal embeddings despite having access to ground truth labels.

• Supervised models outperform their corresponding selfsupervised model, in almost all metrics and for all languages. It means that self-supervision has also a margin for improvement given better pairs from the UTD systems. • Among self-supervised and supervised models, the CAE-Siamese Mel-F takes the pole position. This model seems to be able to combine the advantages of both training objectives. A result already claimed by [START_REF] Last | Unsupervised feature learning for speech using correspondence and siamese networks[END_REF].

• (self) supervised neural neural networks trained on low-level acoustic features (Mel-F) performs better or equally well as high-level acoustic features (PLP). This shows that neural networks can learn their own high-level acoustic features from low-level information.

• Self-supervised models are expected to outperform unsupervised models because they use side information. Yet many configurations do not show this consistently. Only the Buckeye data set seems consistent, but this dataset is the one on which pairs were selected through a grid-search to minimise the ABX error. This may be due to the variable quality of the pairs found by UTD; better UTD is therefore needed to help self-supervised models.

• Unsupervised models are supposed to be better than handcrafted models because they can adjust by learning from the dataset. Yet, this is not consistently found. Hand crafted models are worse than unsupervised models for ABX and frequency estimation but not for MAP.

• In detail, which model is best in a particular language depends on the metric.

Across metrics and frequency estimation

subsubsectionInterpretation of results across metrics and frequency estimation We quantified the possibility to observe the discrepancies that we have just discussed in Table 2. We computed the correlation R 2 across the three 'average' columns. Cross correlation scores range from R 2 = 0.33 to 0.53; the top-line model is not included when computing these scores. R These correlations are low enough to permit sizeable discrepancies across metrics and the downstream task. One of our model, the RNNAE Mel-F, epitomises the problem. This model is comparatively bad according to the MAP but good according to ABX and the frequency estimation. It means that MAP and ABX reveal different aspect of the reliability of embedding models. Therefore, only large progress according to one metric assures a progress according to an other metric. It shows the limit of intrinsic evaluation of speech embeddings. Moderate variations on a intrinsic metric cannot guarantee a progress on a given downstream task.

ABX and MAP scores are averages over multiple phonetic contrasts. These contrasts could be clustered based on their phonetic frequencies, average lengths or number of phonemes in common. Such fined-grained analyses can sometimes understanding divergences across metrics. However, we have been unable to find a categorisation of results that make sense of Figure 1 as a whole. There are currently no fully reliable metrics to assess the intrinsic quality of speech embeddings.

Conclusion

We quantified the correlation across two intrinsic metrics (MAP and ABX) and a novel downstream task: frequency estimation. Although MAP and ABX agree on general categories (like supervised versus unsupervised embeddings), we also found large discrepancies when it comes to select a particular model highlighting the limits of these intrinsic quality metrics. However convenient intrinsic metrics may be, they only show partial views of the overall reliability of a model. We showed using frequency estimation that variations on intrinsic quality metrics should not be accounted for certain progress on downstream tasks. More attention should be brought on downstream tasks that have the credit to answer practical problems.

  t1), (e2, t2), ...(en, tn)) where ei are the embeddings and ti the transcriptions. The ABX task creates all possible triplets (ea,e b ,ex) such that: ta = tx and t b = tx. The model is asked to predict 1 or 0 to indicate if ex is of type ta or t b . Such triplets are instances of the phonetic contrast between ta and t b . Formally for a given a triplet, the task is to predict: y(ex, ea, e b ) = 1 d(ea,ex)≤d(e b ,ex)

Figure 1 :

 1 Figure 1: Value of metrics and the downstream task across models, corpora. The average column is the average score over all corpora

Table 1 :

 1 Frequency estimations using K-means, HC-K-means and k-NN density estimation on a subset of the Buckeye corpus

	/methods	K-means HC-K-means k-NN
	GD-1hot	0.67	0.73	0.74
	RNNAE Mel-F	0.30	0.35	0.41
	CAE Siamese Mel-F	0.26	0.37	0.43

Table 2 :

 2 Correlation R 2 across the 'average' column of MAP, ABX and frequency estimation

	2	Frequency est. MAP ABX
	Frequency est.	1.0	0.34	0.53
	MAP	0.34	1.0	0.45
	ABX	0.53	0.45	1.0

This estimation could be up to a scaling coefficient; the task of finding exact count estimates is a harder task, not tackled in this paper.

Acknowledgements

We thanks Matthijs Douze for useful comments on density estimation. This work was funded in part by the Agence Nationale pour la Recherche (ANR-17-EURE-0017 Frontcog, ANR-10-IDEX-0001-02 PSL*, ANR-19-P3IA-0001 PRAIRIE 3IA Institute), CIFAR, and a research gift by Facebook.