Thibault Blanc-Beyne

Géraldine Morin

Kathryn Leonard

Stefanie Hahmann

Axel Carlier

A Salience Measure for 3D Shape Decomposition and Sub-parts Classification

Keywords: shape analysis, part hierarchy, medial axis, WEDF, salience measure, 3D shape decomposition

This paper introduces a measure of significance on a curve skeleton of a 3D piecewise linear shape mesh, allowing the computation of both the shape's parts and their saliency. We begin by reformulating three existing pruning measures into a non-linear PCA along the skeleton. From this PCA, we then derive a volume-based salience measure, the 3D WEDF, that determines the relative importance to the global shape of the shape part associated to a point of the skeleton. First, we provide robust algorithms for computing the 3D WEDF on a curve skeleton, independent on the number of skeleton branches. Then, we cluster the WEDF values to partition the curve skeleton, and coherently map the decomposition to the associated surface mesh. Thus, we develop an unsupervised hierarchical decomposition of the mesh faces into visually meaningful shape regions that are ordered according to their degree of perceptual salience. The shape analysis tools introduced in this paper are important for many applications including shape comparison, editing, and compression.

Introduction

a decomposition of the shape), or similarity detection in a 3D shape, as required by [START_REF] Guy | Simselect: Similarity-based selection for 3d surfaces[END_REF].

A key observation is the fact that, despite a reputation for instability, a skeleton can provide a reliable basis for shape analysis when it is complemented with measures defined along it. Below, we introduce such a measure, called Weighted Extended Distance Function (WEDF), which is defined on a curve skeleton centered within a 3D shape. WEDF has been introduced recently for 2D shape contours [START_REF] Larsson | Identifying perceptually salient features on 2d shapes[END_REF] and successfully used for defining a salience measure and decomposition of 2D curves [START_REF] Leonard | A 2d shape structure for decomposition and part similarity[END_REF]. Generalizing to the 3D setting takes two steps: first defining WEDF on a 3D skeleton and deducing a partition, second, mapping the measure on the surface mesh. The second step assesses salience of surface mesh parts: it establishes an injective mapping between surface mesh vertices and the skeleton points while ensuring simultaneously that the inverse mapping produces coherent shape parts. In 2D, a straightforward association of boundary points to the WEDF values of the corresponding skeletal points generates a good partition of a shape [START_REF] Leonard | A 2d shape structure for decomposition and part similarity[END_REF], but the 3D setting is more challenging: a direct extension of the 2D approach to 3D generates a poor partition (see Figure 10, where the Many 3D applications make use of 3D shape decompositions in various forms, whether for shape comparison and compression, for editing purposes, or for animation. While much work has studied how to produce meaningful parts, there has been little focus on providing additional information on parts, such as their relative importance. In [START_REF] Bower | Structural units and the redintegrative power of picture fragments[END_REF], the authors show that decomposition into a hierarchy of part and subparts is memorized by user, and such structure is relevant for shape recognition. Such a measure has been formalized by Hoffman and Singh [START_REF] Hoffman | Salience of visual parts[END_REF] and called salience of parts. This measure reveals how important a part is to understand the shape as a whole. In this paper, we propose a shape decomposition method that naturally provides insights about parts salience.

The present work makes a first step towards automatic similarity-based shape decomposition by introducing a new salience measure for 3D shape decomposition and subparts classification. In particular, the proposed decomposition provides an automatic preprocessing for applications such as structuring a 3D shape (e.g. like [START_REF] Léon | Continuous semantic description of 3d meshes[END_REF] whose semantic descriptors relies on legs run into the body of the ant). Accordingly, we propose a robust algorithm for appropriately transferring the salience measure on the skeleton to the surface mesh, enabling a decomposition into a consistent set of subparts that can be clustered according to their salience levels.

Given a WEDF measure coherently transferred to a surface mesh, we use unsupervised methods for decomposing a 3D shape into subparts and for classifying those parts according to their visual salience. This allows us to determine a primary supporting shape and features with decreasing saliency. In contrast to classical shape segmentation algorithms, our method provides a graded salience-based parts decomposition, where each part is labeled with a value characterizing its importance to the overall shape. Figure 1 shows an example: our method not only segments the body parts from the body, but additionally labels each body part with an importance value so that parts with the same importance value belong to the same level in the importance hierarchy. All rose mesh parts belong to the main body, all green parts to the lowest hierarchy level, all yellow parts to a parent hierarchy level, and so on.

Our hierarchy labels inherit the following two features from the relationship to the curve skeleton:

• the connectivity of sub-parts including a parentchild relationship starting from the main shape and decreasing monotonically along parts moving away from the main shape is provided, and

• the partition and salience measure is stable under volume preserving shape deformation (with no topology change).

Both features allow for a straightforward classification of the extracted sub-shapes into visual salience clusters, which then aids any subsequent computations such as correspondences or local symmetries (see Figure 14). After presenting related work and giving background in Section 2, we define WEDF on 1D skeletons embedded in 3D shapes in Section 4, describe its use for skeletal decomposition in Section 5, and introduce the mapping of the WEDF to the surrounding 3D mesh in Section 6. We then demonstrate the applications of the method for 3D shape decomposition and salience-based evaluation of sub-parts.

Related work

3D shape salience

Salience, or saliency, is a concept that has been widely studied in the literature. Borji and Itti, in their important state-of-the-art review [START_REF] Borji | State-of-the-art in visual attention modeling[END_REF] define saliency as a characterization of parts of a scene -which could be objects or regions -that appear to an observer to stand out relative to their neighboring parts. Most of the algorithms that characterize saliency in images use bottomup approaches, determining what stands out using lowlevel cues such as color contrast [START_REF] Itti | A model of saliency-based visual attention for rapid scene analysis[END_REF].

A similar approach has been adopted in studies of 3D objects saliency. In their pioneer work, Lee et al. [START_REF] Lee | Mesh saliency[END_REF] define a mesh saliency measure based on local surface curvature at multiple scales. Many more methods have then be devised following this local approach. Song et al. [START_REF] Song | Mesh saliency via spectral processing[END_REF] exploit the apparent correlation between the logspectrum of 3D mesh geometric Laplacian. They later extended their work, introducing a pooling scheme to introduce a more global saliency [START_REF] Song | Local-to-global mesh saliency[END_REF]. Nouri et al. compute local descriptors on each vertex and then a measure of saliency based on a weighted average at different scales [START_REF] Nouri | Multi-scale mesh saliency with local adaptive patches for viewpoint selection[END_REF]. These methods usually compare their results with outcome of user studies, that either captured eye fixations of users watching 3d objects [START_REF] Kim | A new shape decomposition scheme for graph-based representation[END_REF], or matched manually designated interest points [START_REF] Chen | Schelling points on 3d surface meshes[END_REF].

In our work, we do not aim at computing a local measure of saliency that would characterize the shape at the vertex level, but rather try to define the relative importance of parts of the shape relative to the whole, thus following Hoffman and Singh's footsteps [START_REF] Hoffman | Salience of visual parts[END_REF]. These authors emphasize the need for a measure of the salience of visual parts, especially in the context of object recognition. A part salience is, according to the authors, correlated to how much recognizing this part helps recognizing the object. The authors propose three features to compute parts salience: relative size of the part, degree of protrusion and boundary strength. As a consequence, for the matter of shape understanding, it is important to be able to discriminate a shape into parts and get a sense of the relative importance of those parts. This is a natural outcome of the work we propose in this paper.

3D shape decomposition

3D shape segmentation, or decomposing a shape in sub-parts, is an important research topic offering a wide range of methods emerging from its numerous applications such as compression, reverse engineering, editing, and comparison (see [START_REF] Theologou | A comprehensive overview of methodologies and performance evaluation frameworks in 3d mesh segmentation[END_REF] for a recent survey). Supervised methods are based on user-segmented data and learning methods, offering a perceptually coherent segmentation as in [START_REF] Xie | 3d shape segmentation and labeling via extreme learning machine[END_REF] or [START_REF] Benhabiles | Learning boundary edges for 3d-mesh segmentation[END_REF]. Unsupervised methods make use of other tools, such as clustering methods or region-growing based on various shape characteristics (e.g. [START_REF] Lai | Rapid and effective segmentation of 3d models using random walks[END_REF][START_REF] Bergamasco | A graph-based technique for semi-supervised segmentation of 3d surfaces[END_REF], or see [START_REF] Theologou | A comprehensive overview of methodologies and performance evaluation frameworks in 3d mesh segmentation[END_REF] for a comparison), spectral To each connected part on the skeleton -shown with a different color (c)a connected region of the surface mesh is assigned (d). Then, a salience value according to the hierarchy is assigned to each corresponding surface part (e) -parts of same importance get a similar color.

analysis (e.g. [START_REF] Fang | Heat-mapping: A robust approach toward perceptually consistent mesh segmentation[END_REF]), spatial subdivision methods or explicit boundary extraction (e.g. [START_REF] Kim | A new shape decomposition scheme for graph-based representation[END_REF][START_REF] Au | Mesh segmentation with concavity-aware fields[END_REF]), or probabilistic models [START_REF] Pulla | Improved curvature estimation for watershed segmentation of 3-dimensional meshes[END_REF][START_REF] Koschan | Perception-based 3d triangle mesh segmentation using fast marching watersheds[END_REF]. Other segmentation methods are based on topological information, like Reeb graphs [START_REF] Berretti | 3d mesh decomposition using reeb graphs[END_REF] but depend on the function chosen for defining the graph [START_REF] Biasotti | Reeb graphs for shape analysis and applications[END_REF]. Skeletons have been applied for segmentation on point clouds, where either the resulting skeletons are not connected [START_REF] El-Gaaly | A bayesian approach to perceptual 3d object-part decomposition using skeleton-based representations[END_REF][START_REF] Li | Decomposing polygon meshes for interactive applications[END_REF] or do not provide a consistent segmentation [START_REF] Kustra | Shape segmentation using medial point clouds with applications to dental cast analysis[END_REF], and on surface meshes [START_REF] Feng | Part-based segmentation by skeleton cut space analysis[END_REF], using the skeleton to define a dense set of possible segmentation cuts from which a subset will be chosen based on boundary geometry [START_REF] Tierny | Topology driven 3d mesh hierarchical segmentation[END_REF]. Very few of these segmentation methods explicitly profit from the innate parentchild relation between sub-parts, or measure for the relative saliency over the parts they obtain.

While most of the 3D methods described above do not make use of skeletons, in part because of their perceived instability and difficult to compute, recent methods for 2D shape analysis, decomposition and clustering [START_REF] Liu | Extended grassfire transform on medial axes of 2d shapes[END_REF][START_REF] Larsson | Identifying perceptually salient features on 2d shapes[END_REF][START_REF] Leonard | A 2d shape structure for decomposition and part similarity[END_REF] successfully exploit the geometry of the Blum medial axis for various shape tasks. These methods have shown that the use of the skeletons can be complemented with properly chosen functions that provide robustness and stability. One example of such a function is EDF [START_REF] Liu | Extended grassfire transform on medial axes of 2d shapes[END_REF] (Extended Distance Function) on 2D shapes which is a useful measure for pruning and has already been generalized to 3D, enabling improved 3D skeleton computations [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF]. Another example is WEDF [START_REF] Larsson | Identifying perceptually salient features on 2d shapes[END_REF] (Weighted Extended Distance Function), which defines a measure for 2D sub-parts saliency. It has recently been validated through perceptual studies about cognitively meaningful shape importance [START_REF] Carlier | The 2d shape structure dataset: A user annotated open access database[END_REF] and used for 2D shape decomposition and similarity detection [START_REF] Leonard | A 2d shape structure for decomposition and part similarity[END_REF].

Our work builds on these 2D structures. We generalize WEDF to curve-skeletons on the medial axis of a 3D shape, develop an efficient algorithm and provide a perceptually consistent, graded salience-based shape decomposition based on the variation of the WEDF along the curve-skeleton (see Figure 2).

Depth functions in 3D

In 3D, the medial axis of a surface, which consists of the loci of centers of all enclosed maximal balls of the surface, is no longer simply a curve skeleton but generically includes two-dimensional components called medial surfaces that intersect transversally creating nonmanifold regions. Each point on the medial axis is still associated to a radius function whose value is the shortest distance to the shape boundary, namely the radius of the corresponding medial ball. A direct extension to 3D of a depth function like EDF is not obvious as there is no single medial axis endpoint associated to a medial component. For this reason, it is more convenient to define functions on some kind of medial skeleton rather than on the full medial axis. Dey and Sun [START_REF] Dey | Defining and computing curve-skeletons with medial geodesic function[END_REF] are the first to introduce a mathematical definition and an algorithm to compute a medial curve skeleton based on singularities of a so-called medial geodesic function. Yan et al. [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF] propose another definition and algorithm of a medial curve skeleton for 3D, based on ET and a burning process over the medial axis. They generalize their work in 2D to define the following functions for 3D on piecewise linear medial axes such as those generated by discrete surface meshes: medial burn time (MBT), erosion thickness (ET) and curve burn time (CBT).

In [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF], these functions are meant to aid in pruning the medial axis to obtain a simpler version that is more useful in applications, and to obtain a 1D skeletal shape representation. In contrast, our paper aims to provide a new function on the skeleton, similar to WEDF in 2D, able to measure part saliency. To this end, we build on MBT and CBT and derive an efficient algorithm not only for calculating a 3D WEDF along the skeleton but also for returning the function back to the surface mesh in order to determine a salience-based shape decomposition and to structure the shape hierarchically.

Local analysis of the shape around the axis

Before presenting our algorithms in Section 4, let us briefly recall the existing depth functions relevant for our work and introduce an original interpretation of these three measures as a non-linear PCA.

The first two functions are defined on the full medial axis, and are used to extract a curve skeleton. The third is then defined on the extracted skeleton.

• The medial burn time (MBT) is defined as the geodesic distance of a medial axis point to the shape boundary associated to the closest extremity of the widest medial axis sheet containing this point [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF].

• The erosion thickness ET is defined as the difference between the width and the height: at a point x in a medial axis M, ET (x) = MBT (x) -R(x). ET is used in [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF] to determine the scale at which to extract the curve skeleton.

• The curve burn time (CBT) is defined only for skeletal points, and measures the distance to the closest extremity of the shape on the longest skeleton curve containing the given medial skeleton curve point. CBT thus corresponds to a length computation, and models the direction in which the shape extends the most. Yan et al. [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF] use CBT as a way to prune the medial skeleton to obtain a simplified version.

While these measures were intended for simplification of the medial axis, we show that they can be used as a powerful tool for shape understanding. In particular, the three functions R(x), MBT (x), CBT (x) along a curve skeleton (Fig. 5), when taken together with the paths through the medial axis whose lengths they represent, provide a non-linear version of a PCA decomposition of the shape: at a point x on the curve skeleton, CBT gives length, MBT gives width and R gives height, and the accompanying curves give the principal directions through the shape starting at x. Note that, unlike in PCA, the directions considered are not linear but follow the curvature of the medial axis along each important direction. Moreover, integrating these quantities (width and height) over the principal direction provides our volume-based saliency measure, the 3D WEDF as introduced in the next section.

3D Weighted Extended Distance Function

We now develop a definition for the weighted extended distance function (WEDF) in 3D for piecewiselinear medial surfaces.

The customary challenge in working with discrete medial surfaces is that, in practice, the connectivity of a discrete 3D medial axis is often not consistent with the theory, as noise in the surface mesh propagates to the medial axis sheet by generating regions where the connectivity is rarely manifold even when the underlying continuous model would be smooth. This prevents finding a direct, continuous path to the boundary on a medial axis sheet generated from a surface mesh. Such a path is however essential to define a partial order on the medial axis points. The next section introduces the tools necessary to overcome this difficulty.

Preliminaries

The input of our algorithm is a closed, manifold triangle mesh representing the surface of a 3D object. From the mesh, we can compute a discrete version of the medial axis (e.g. [START_REF] Amenta | A new voronoi-based surface reconstruction algorithm[END_REF][START_REF] Tagliasacchi | 3D Skeletons: A State-of-the-Art Report[END_REF]), and for each medial point x its burn time, MBT (x), as computed in [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF]. Note that each Figure 3: Medial axis (dark gray) and a curve skeleton (yellow) of a 3D shape. The medial axis is obtained using [START_REF] Giesen | The scale axis transform[END_REF] and curve skeleton using [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF]. This curve skeleton preserves the topology of the shape (light gray) and captures its features (ears, head, legs, tail). point x in the medial axis is also the circumcenter of an associated tetrahedron given by a Delaunay tetrahedralization. The set of all tetrahedra associated to all medial axis points provides a partition of the volume within the mesh.

We extract a curve skeleton that is a subset of the medial axis, a connected curve network capturing the structure of the shape. We assume the curve skeleton has the same topology as the shape, and is as centered as possible. In particular, the curve skeleton will be properly contained in the interior of the shape since it lies on the medial axis, see Fig. 3. Our method also works for noncentered skeletons, but the result may be less precise (a comparison is shown in Sect. 7.2). In our implementation, we use the method from [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF] to compute the curveskeleton, but we also consider mean curvature skeletons from [START_REF] Tagliasacchi | Mean curvature skeletons[END_REF][START_REF] Lee | Building skeleton models via 3-d medial surface axis thinning algorithms[END_REF] extracted via mean curvature flow, and curve-skeletons from [START_REF] Livesu | Reconstructing the curveskeletons of 3d shapes using the visual hull[END_REF][START_REF] Livesu | Extracting curve-skeletons from digital shapes using occluding contours[END_REF]. Our methods are consistent for all types of curve-skeletons tested. Note, that we present results for surfaces of genus 0 generating curve skeletons with tree structures. In this case, there exists a single path on a curve skeleton between any of its two points. In other words, the path between an extremity of the curve skeleton and a skeleton point is unique.

Defining 3D WEDF on a curve skeleton

We now define 3D WEDF values on a curve skeleton in order to provide a salience measure of subparts. In the discrete setting, where the shape is a polygonal curve and the medial axis a piecewise linear curve skeleton, WEDF is computed as the areas of the shape parts transversed along the WEDF path from the extremity y to the medial axis point x. An extension to a discrete 3D setting would be to sum up the volume traversing the medial axis from a part extremity until skeleton point. The direction of medial axis traversal is not well defined, however, because of the lack of correspondence between a curve skeleton point and points on a medial sheet (and also on the surface mesh). This prevents us from extending the 2D WEDF definition to 3D directly. We pause to summarize the two main challenges we face and how we propose to solve them, before defining WEDF in more detail:

1. Skeleton traversal. Since the discrete medial axis contains two-dimensional sheets so the medial axis cannot be used for an EDF-like path traversal of the 3D shape. Our solution is to base our computations on a one-dimensional skeleton inside the 3D shape.

The CBT values can then be extended to CBT values for medial points on the manifesting path for the medial burn time (MBT) of the skeletal points. 2. Volumetric shape partition. While in 3D, as in 2D, there is a correspondence between points on the medial axis and the points on the surface mesh, namely those on the circumcircle of the Delaunay tetrahedralisation of the volume, smoothing the non-manifold noise on the medial axis often breaks the correspondence. As is true for the Delaunay triangulation and area in 2D, the theoretical Delaunay tetrahedralisation in 3D partitions the volume of the shape into regions associated to a medial point. In removing the noise from the medial axis, however, the correspondence between medial points and tetrahedra may be broken, and so we must establish a new correspondence between points on the medial axis and tetrahedra. Our so-lution depends on the skeleton traversal described above: we associate tetrahedra for multiple medial points to a single skeletal point so that summing volumes over all skeletal points results in the volume of the entire shape.

Let us explain our solution to these challenges in more detail now. In the following, m denotes a point on the medial axis M and s denotes a skeletal point, a point on the curve skeleton (and also on the medial axis, as the curve skeleton lies on the medial axis). As the curve skeleton is traversed, the WEDF must account for the volume of the entire shape part between a skeletal point and the surface boundary, not just the volume of the shape associated to the tetrahedra of the curve skeletal points. For each skeletal point s, we obtain the medial burn time (MBT), which is the time required for a unit-speed grass-fire lit on the boundary of the medial axis to completely expose a medial point, and consider its burn path b s . See [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF] for a detailed description of the algorithm and rigorous definition in the discrete setting. The burn path is the path of length MBT (s) extending from the point s to a boundary point that represents the path of the fire front that exposed s, see Figure 5. Let T (s) be the volume that is assigned to a skeleton point s: the sum of volumes of the tetrahedra of the medial points along the burn path of s (green tetrahedra in Fig. 4). Then the WEDF-volume assigned to s, WEDF(s) = T (s) + z∈Skeleton path T (z), is the volume T (s) plus the volumes T (z) associated to all preceding skeletal points z that are closer to the skeleton extremity than s along the CBT path to s. Then WEDF(s) can be thought of as the integral along the path along which CBT is computed within the curve skeleton, of the other two PCA-like values: radius and MBT. These volumes form the basis of the 3D WEDF computation. We now formally define WEDF in the piecewise linear case. Let s be a point on a curve skeleton C of the medial axis M associated to a surface mesh S . Then the value of WEDF(s) is given by one of the following:

• If s is a skeleton extremity, WEDF(s) is the volume of the cap between s and the corresponding points on S .

• If s is a junction point where multiple branches of C come together, then WEDF(s) corresponds to the sum of the volumes of all incoming branches, namely those branches that are closer to an skeletal extremity than s, together with the volumes of the tetrahedra assigned to s.

• If s is a generic branch point of a branch b (neither an extremity nor a junction), then WEDF(s) is the sum of the volumes assigned to the neighboring point in b that is closer to an extremity than s, together with the volumes of the tetrahedra assigned to s.

Note that because MBT is not defined in the continuous setting [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF], we cannot provide a continuous definition for WEDF.

Computing WEDF on the 3D curve skeleton

In practice, 3D WEDF is computed for an input surface mesh, on a curve-skeleton consisting of points on the medial axis of the surface mesh. The sampling density of the medial axis or skeleton points may affect the smoothness of the WEDF, but not its actual value. Above, we discuss the volume T (s) assigned to a skeletal point s. More precisely, T (s) is the sum of the volumes of the Delaunay tetrahedra whose circumcenters m ∈ M are closest to s according to the following distance function:

D(m, s) = |MBT (m) -MBT (s)| -d(m, s) (1)
where d is the Euclidean 3D distance and MBT the medial burn time. Note that because MBT is defined only for discrete medial axes, we can define WEDF only in the discrete setting as well. Figure 4 shows the tetrahedra and their circumcenters associated to a skeleton point s. Note that the proposed distance function D ensures that a medial point m is necessarily contributing to a skeleton point s that lies on the same sheet of the medial axis, as illustrated in Figure 6.

The definition of T (s) ensures that points m associated with s are lying along the burn path b s ⊂ M reaching the closest border of the medial axis according to the medial burning time. T (s) therefore measures the volume associated to all points on the burn path of s to the shape boundary, see Figure 4. By construction, each medial point m is associated to a unique skeleton point s. Taking Delaunay tetrahedra across all m ∈ M gives the volume of the entire shape, therefore taking T (s) across all s ∈ C partitions the shape volume into tetrahedra sets associated to each s ∈ C.

To compute WEDF values along the skeleton, we begin at a skeletal extremity and progress inward. During the skeleton traversal, the WEDF value at a point is then computed from the value at the previous point:

WEDF(s) = T (s) + WEDF prev (2)
WEDF prev =                                        0 at extremities; WEDF(y)
if s is a regular point, and y its neighbor with computed WEDF; i≥1 WEDF(y i ) if s is a junction, and all neighbors y i but one y 0 have a WEDF value.

Here in equation ( 2), we define a summed WEDF, since at a junction s of the curve-skeleton the volume WEDF(s) is here the sum of values from all incoming skeleton branches. This differs from the 2D WEDF definition [START_REF] Larsson | Identifying perceptually salient features on 2d shapes[END_REF], where max values at branch junctions are taken. We use the summed WEDF because it is necessary to insure its robustness to surface noise. Indeed, with a 3D max-version of WEDF, small branches of the skeleton originating from noise would capture the volume erroneously around them (by catching tetrahedra volume previously assigned to a main branch) and thus diminish the WEDF on the global shape. An illustration of the change in WEDF due to small branches is given by Figure 8 shows a color-coding of the WEDF function on curve skeletons for 3D objects. When the object and its curve skeleton have some symmetries, the WEDF remains symmetric. The WEDF value is maximum at a point whose value is the total volume within the surface of the object, and then decreases on any path towards curve skeleton extremities. As in 2D, WEDF along a skeleton path between two extremities is unimodal.

Clustering the skeleton into parts according to salience

To demonstrate one avenue for application of our WEDF computation, we use the WEDF values defined on the skeleton to develop a salience measure for each point on the surface mesh. Examples of part salience on some well-known 3D shapes are shown in Section 7.

Partitioning skeleton points into salience levels

We perform unsupervised clustering on the WEDF values in order to identify parts at similar salience levels. The clustering we propose is a two-step process, where the first step determines the main shape of the skeleton and the second step identifies features with decreasing saliency values. For a genus 0 surface mesh, the skeleton has a tree-like connectivity, where the root corresponds to the highest 3D WEDF value. Moving away from the root, the salience values monotonically decreases along the branches of the skeleton.

Identifying the main shape. We select main skeletal points as a subset of the skeletal points in two steps. On the 3D WEDF values, we perform a seeded k-means clustering with two clusters where the seeds are the minimum and the maximum WEDF values of the junction skeletal points being clustered. We then associate all remaining skeleton points to these two clusters based on their WEDF values. All skeletal points belonging to the cluster with the centroid of largest WEDF value are selected as the main shape points.

Identifying features. The other 3D WEDF clusters are determined among those WEDF values of junction points and neighbors which are not in the main shape cluster: we again apply a k-means clustering with k in a given interval (in practice, we take k ∈ {2, 3, ..., 20}). An estimation of the best number of classes k is given by gap analysis [START_REF] Tibshirani | Estimating the number of clusters in a data set via the gap statistic[END_REF]. Each cluster represents a salience level relevant for the shape. The level value L is chosen as the median WEDF value of the cluster: larger 3D WEDF values correspond to higher salience levels, i.e. closest to main shape, while lower values are less significant, corresponding to lower salience levels.

Clustering skeleton points. The curve skeleton is partitioned into clusters according to the clustering of its 3D WEDF values. We thus obtain a partition of the curve-skeleton into salience levels. Note that any path on the curve skeleton going from a point belonging to the main shape to an extremity point will traverse levels of salience in decreasing order, see Figure 9. This partial ordering of points of the curve skeleton, coherent with the tree topology of the medial axis, is the basis for the graded salience-based parts decomposition described in the next section.

This process allows cross-parts comparison of salience for all parts, and is therefore not restricted to those with junctions: for example, the thumb in the hand of Figure 9 is identified as a feature even if there is no junction in the curve skeleton, because its salience level matches the salience level of the other fingers.

Saliency measure for 3D shape surface decomposition and hierarchy

After having decomposed the skeleton into graded skeletal sub-parts (Fig. 1-d), the second step of our method is transfer the parts decomposition to the shape's surface, in order to partition the mesh into graded parts labeled by their salience (Fig. 1-f).

This transfer is a challenging process. A naive method would map the cluster level of curve skeleton points onto medial axis points using the distance function introduced for the computation of WEDF (see Equation (1) in Section 4.3). And, since each medial axis point is the circumcenter of a tetrahedra, assigning the cluster level value to its tetrahedra would directly lead to a partition of the volume of the shape into cluster levels (Figure 4). However, it can be observed that lower level clusters, corresponding to features of We can see that the naive clustering gives a decomposition where sub-parts of lower saliency (like antennae or legs) are indeed entering into the parent shape of higher salience (here head or body).

The naive tetrahedra clustering is therefore not sufficient.

lower salience, carve holes along the branches inside the parent shape: Delaunay tetrahedra whose circumcenters are medial points close to the center of the main shape may be associated to a curve skeleton point belonging to a lower level branch (we see this effect on the left image of Figure 10 where green triangles emerge from inside the main shape near attachment area of legs).

We therefore propose a two-step process to extend transfer salience levels from the skeletal points to the surface, using vertices instead of tetrahedra. We first assign each vertex of the surface a saliency level by considering all medial points whose tetrahedra contain the vertex, and then determine a level value for the triangular faces from the levels of the associated vertices.

Assigning salience levels to mesh vertices

We start with a surface mesh S and a curve skeleton C, where each skeletal point s is attributed a salience level L(s). Each s belongs to a cluster cluster(s), and its associated level L = L(s), the median of the WEDF values within the cluster cluster(s). For each mesh vertex v ∈ S , we compute the skeleton point s, which is the closest to v using the following distance function:

F(v, s) = d(v, s) L(s) (3)
with d(v, s) the Euclidean distance between v and s. This function warps the space to favor clusters of higher value: skeleton points belonging to high-level clusters have an F-distance smaller than the Euclidean distance to the mesh vertices, while skeleton points belonging to clusters with lower value have an F-distance distance greater then the Euclidean distance to the mesh vertices. This way, curve-skeleton points belonging to higher salience-level clusters attract boundary points to the more significant part in terms of salience (body) rather than attaching to a less significant feature. See Fig. 10, where mesh vertices are wrongly attached to the leg using the Euclidean distance (left), but correctly labeled with a salience attached to the body (right).

Assigning salience levels to mesh faces

After this first step of assigning mesh vertices to salience levels of skeleton points, we label the mesh faces using the levels assigned to the three vertices belonging to a face. If all vertices are assigned to the same level, we assign the face to this level, that is, the face salience value is the cluster salience. In salience transition zones, where vertices of a face are assigned to different levels, we subdivide the face (1-4 subdivision) using points linearly interpolated on the three edges according to salience levels of the vertices, and assign levels to subregions accordingly. This generates a smooth transition between parts of the shape belonging to different levels, as shown in the following experiments.

Experiments

Validation

First, Figure 11 shows the partition of different meshes created by considering each cluster on the skeleton as a different part, without grouping by salience value. Note that the decomposition is coherent, and when the shape is close to symmetric, the decomposition preserves this symmetry. Also observe that different parts, like the fingers of the hand, or the arms of the octopus, are well separated (thanks to the topology of the curve medial axis). In Figure 12, we have now grouped parts according to salience, so each part with the same color has been determined to be at the same salience level. Moreover, because the skeleton has a tree structure, the salience levels are monotonically decreasing from the main shape to the extremities of the shape, leading to a graded partition into subparts. We can see in all these results that the core of the shape is well-centered, while shape details are localized at extremities. Also, the shape parts that are similar (legs, fins or antennas) are assigned to the same hierarchy level. The proposed segmentation then gives not only a partition of the shape, but also assigns a level of salience to each feature that is global on the shape, and known to be consistent with perception in 2D [START_REF] Larsson | Identifying perceptually salient features on 2d shapes[END_REF][START_REF] Carlier | The 2d shape structure dataset: A user annotated open access database[END_REF].

Robustness of the graded partition

We also recall that the proposed graded segmentation is robust. First, computing the salience level on the curve skeleton reduces the instability of the medial axis to boundary noise. A curve skeleton may have a lot of small branches, or be simplified. We have seen in Figure 7 that the proposed computation of WEDF (summing the incoming values at junctions) provides stable WEDF values on the main branches, and thus insures a consistent segmentation. We also experiment with different curve skeletons as input. Curve skeletons are not uniquely defined for 3D objects, and the computation of a curve skeleton is not part of our work. Even though our method works successfully for different curve skeleton types, the quality of the curve skeleton plays an important role, see Fig. 13. A good curve skeleton is well-centered and captures all small protrusions with branches associated to each feature (left) whereas a coarser skeleton leads to a coarser graded decomposition (right).

Figure 14 shows that our segmentation is naturally stable under constant volume shape deformation, since the WEDF measure generating the salience levels is volumetric. In other words, the salience levels stay consistent as moving parts articulate. The coloring between the two human figures remains consistent for the legs and arms, with only slight changes on the shoulders. Similarly, in Figure 15 the decomposition is very consistent across the different poses (a) to (d). (c,d). The (a) decomposition uses the skeleton from [START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF], which is better centered and which correctly captures small protrusions (such as ears), while the first decomposition (b), uses the mean curvature skeleton (d) from [START_REF] Tagliasacchi | Mean curvature skeletons[END_REF], and is neither well-centered (see the tail) nor capturing correctly the small protrusions (such as ears). The (a) segmentation gives better results as small protrusions create smaller parts and as parts (legs, tail) are more finely cut, confirming our preference for the skeleton (c).

Discussion and conclusion

We have produced a graded, salience-based parts partition from a importance measure on a curve skeleton of the shape integrating local PCA-like representation of a shape on the skeleton. Our method determines a level of relative importance for each sub-part, and labels features of the same salience level as belonging to a group with the same perceptual importance. Moreover, because the decomposition respects the topology of the skeleton, it produces a parent-child relationship between parts in a given shape. At the highest level, the main shape contains the barycenter of the shape. Moving away from the center, parts decrease in salience as a parent level gives way to a child. For genus 0 shapes, having a skeleton with tree structure, the parent of each part will be unique. As a result, the connectivity produced by the skeleton allows for ordered parts relationships in a way that connectivity induced by cluster adjacency computed directly on the surface does not: for example, the ears of the horse on Fig. 12 have two adjacent regions on the head, themselves neighbors, which would lead to a triangle connection (loop) between the three adjacent regions when using surface connectivity: skeletal connectivity results in two ears each connected to a head. Thus our decomposition is enriched by both a topological relationship between subparts, and an importance value attached to each subpart.

While our decomposition has consistent results on different curve skeletons, it still depends on the quality of the curve skeleton used to capture the shape. Indeed, as shown in Figs. 3 and13, the results may vary depending on the skeleton's geometry and topology. However, for volume preserving deformation, the proposed decomposition is robust and gives a consistent labeling of the shape parts as long as the topology is preserved. As expected, the generalization of WEDF to 3D leads to an analysis of the shape that seems consistent with perception, as shown in 2D in [START_REF] Larsson | Identifying perceptually salient features on 2d shapes[END_REF][START_REF] Carlier | The 2d shape structure dataset: A user annotated open access database[END_REF]. Future work will include a user study to confirm the perceptual coherence.

In future work, we also plan to extend the present work in order to analyze the similarity between segmented parts belonging to the same salience level, by using for example a combination of PCA-like measures on the skeleton. This would enable to produce inputs to recent methods, such as SimSelect [START_REF] Guy | Simselect: Similarity-based selection for 3d surfaces[END_REF] or Pattern-Driven Colorization [START_REF] Leifman | Pattern-driven colorization of 3d surfaces[END_REF], where the user is required to annotate candidate similarities by hand.

Like in the 2D setting [START_REF] Carlier | The 2d shape structure dataset: A user annotated open access database[END_REF], our decomposition and salience could be validated by a user study asking to differentiate the different parts of a 3D object and tag the main shape, and the importance of each different part.

Figure 1 :

 1 Figure 1: Pipeline of our hierarchical decomposition. Starting from a 3D shape and its curve skeleton, we compute a new measure called WEDF on the curve skeleton (a) and, by clustering WEDF values, we decompose the skeleton into hierarchical parts (b).To each connected part on the skeleton -shown with a different color (c)a connected region of the surface mesh is assigned (d). Then, a salience value according to the hierarchy is assigned to each corresponding surface part (e) -parts of same importance get a similar color.

Figure 2 :

 2 Figure 2: Shape center. 3D EDF (a) and 3D WEDF (b) and their associated decomposition (c,d) on a 3D shape. The maximum WEDF value (b, red dot) is centered inside the handle, while the maximum EDF value lies in the tail (a). Our decomposition of the shape into hierarchical salience levels based on each of the two measures given in second row, highlights the fact that considering length, like EDF (c), for measuring salience does not align with perception, whereas considering salience based on WEDF does (d).

Figure 4 :

 4 Figure4: Volume contribution of a skeleton point. The point s is a point on the curve skeleton. In red, the medial axis points (or tetrahedra circumcenters) associated to the point s thanks to the distance D (eq. 1) (a). In green, the tetrahedra whose circumcenter is one of the medial axis points previously marked in red (b). T (s) is the sum of the volume of these green tetrahedra. WEDF(s) is the volume of the subshape whose curve skeleton starts at s and goes towards closest extremities of the curve skeleton, here the volume of the ankle and foot below s (c). The tetrahedra whose volume contributes to WEDF of previous points (WEDF prev in eq. 2) are in light blue.

Figure 5 :

 5 Figure 5: Depth functions at 3D curve skeleton point s: curve burn time CBT (s), medial burn time MBT (s) and radius R(s). Together they provide a global analysis of the shape around s, respectively depth, width and height (R(s) towards us).

Figure 6 :

 6 Figure 6: The distance function D. In gray, two intersecting medial axis sheets belonging to the medial axis M. We distinguish the point m ∈ M and s 1 and s 2 as two points on the skeleton C. The skeleton lies on the medial axis. Despite s 1 being closer to m than s 2 in Euclidean distance, (i.e., d(m, s 1 ) < d(m, s 2 )), m will be associated to s 2 because D(m, s 2 ) < D(m, s 1 ) (since MBT (m) -MBT (s 2 ) ≈ d(m, s 2 ) and MBT (m) -MBT (s 1 ) d(m, s 1 )).

Figure 7 .Figure 7 :

 77 Figure 7: Robustness of the summed WEDF. Two different curve skeletons for the same 3D shape, one with many branches (a,c) and a more filtered version with only main branches (b,d).Top row (a,b): WEDF is computed by taking the max value of incoming branches at intersections[START_REF] Leonard | A 2d shape structure for decomposition and part similarity[END_REF]. we observe a lack of robustness; the distribution of WEDF is different on the main branches of the two skeletons. In particular, the branch containing the greatest WEDF value is not the same. Bottom row (c,d): our proposed summed WEDF computed by summing WEDF values of incoming branches at junctions. The distribution of WEDF remains the same along the main branches of the skeletons since the volume counted on small branches also contributes to the main branch value.

Figure 8 :

 8 Figure 8: WEDF of 3D shapes. Low values are colored in dark blue high values in dark red. We can see that the WEDF grows slowly along branches that are surrounded by a limited volume (such as legs, arms, tail or finger) and grows faster on branches surrounded by an higher volume (belly or palm for instance).

Figure 9 :Figure 10 :

 910 Figure 9:Decomposition of the curve-skeleton into graded salience levels, from main shape (dark red) to less significant parts (dark blue). max WEDF

Figure 11 :

 11 Figure 11: Shape segmentations based on our hierarchical decomposition; here each connected cluster on the curve skeleton generates a different part of the mesh partition.

Figure 12 :

 12 Figure 12: Shape decompositions on several shapes, with saliencybased partial ordering of the extracted sub-parts. The color of a part represents its centroid value. The main shape is often centered in the shape (a,b,c,e,f) or located at the part with greatest volume (d). Details and part of lowest saliency are at the extremities of the shapes (wings, ears, legs, fingers). While (a) and (e) are being decomposed in four levels, (b) is cut in three levels and (c), (d) and (f) only need two levels. Note the capacity of our approach to model shape with a medial axis close to the curve skeleton (e) but also shapes with no tubular parts (f) having a two dimensional medial sheet.

Figure 13 :

 13 Figure 13: Comparison between two segmentations (a,b) using different curve skeletons(c,d). The (a) decomposition uses the skeleton from[START_REF] Yan | Erosion thickness on medial axes of 3d shapes[END_REF], which is better centered and which correctly captures small protrusions (such as ears), while the first decomposition (b), uses the mean curvature skeleton (d) from[START_REF] Tagliasacchi | Mean curvature skeletons[END_REF], and is neither well-centered (see the tail) nor capturing correctly the small protrusions (such as ears). The (a) segmentation gives better results as small protrusions create smaller parts and as parts (legs, tail) are more finely cut, confirming our preference for the skeleton (c).

Figure 14 :

 14 Figure 14: Stability of the segmentation relative to pose variation without change of topology.

Figure 15 :

 15 Figure 15: Several shape decompositions of a bird shape in different positions. The decomposition is stable under deformations. This part decomposition into saliency levels may therefore be used in animation.


Lilian Besson
email: lilian.besson@centralesupelec.fr

SMPyBandits: an Experimental Framework for Single and Multi-Players Multi-Arms Bandits Algorithms in Python

Keywords: sequential learning, multi-armed bandit, reinforcement learning, python

SMPyBandits is a package for numerical simulations on single-player and multi-players Multi-Armed Bandits (MAB) algorithms, written in Python (2 or 3). This library is the most complete open-source implementation of state-of-the-art algorithms tackling various kinds of sequential learning problems referred to as Multi-Armed Bandits. It is extensive, simple to use and maintain, with a clean and well documented codebase. It allows fast prototyping of experiments, with an easy configuration system and command-line options to customize experiments.

Presentation

1.1 Single-Player MAB Multi-Armed Bandit (MAB) problems are well-studied sequential decision making problems in which an agent repeatedly chooses an action (the "arm" of a one-armed bandit) in order to maximize some total reward [START_REF] Robbins | Some Aspects of the Sequential Design of Experiments[END_REF], [START_REF] Lai | Asymptotically Efficient Adaptive Allocation Rules[END_REF]. Initial motivation for their study came from the modeling of clinical trials, as early as 1933 with the seminal work of Thompson [START_REF] William | On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples[END_REF], where arms correspond to different treatments with unknown, random effect. Since then, MAB models have been proved useful for many more applications, that range from cognitive radio [START_REF] Jouini | Multi-Armed Bandit Based Policies for Cognitive Radio's Decision Making Issues[END_REF] to online content optimization like news article recommendation [START_REF] Li | A Contextual-Bandit Approach to Personalized News Article Recommendation[END_REF], online advertising (Chapelle and Li, 2011), A/B Testing [START_REF] Kaufmann | On the Complexity of A/B Testing[END_REF]Yang et al., 2017), or portfolio optimization [START_REF] Sani | Risk-Aversion In Multi-Armed Bandits[END_REF].

More formally, a stochastic MAB is defined by K > 1 distributions ν k (arms), and i.i.d. rewards r k (t) ∼ ν k , ∀t. An agent choose arm A(t) ∈ {1, . . . , K} at time t and observes the reward r A(t) (t) without knowing the other (hidden) rewards. Her goal is to maximize T t=1 r A(t) (t) by sequentially exploring the K arms, and she essentially has to find and exploit the best one as fast as possible. This library tackles one dimensional distributions, and supports Bernoulli, binomial, Poisson, and a generic discrete distributions, as well as exponential, gamma, Gaussian (of known scale or variance) and uniform continuous distributions, which can be truncated to an interval [a, b] or have unbounded support (R).

SMPyBandits is a complete open-source implementation of single-player bandit algorithms, containing over 65 algorithms. It uses a well-designed hierarchical structure and class inheritance scheme to minimize redundancy in the codebase. For example, many existing algorithms are index-based: they compute an index I k (t) ∈ R for each arm k and simply play A(t) = arg max k I k (t) at time t. As such, it is easy to write new index-based algorithms by inheriting from the IndexPolicy class, and simply defining one method computeIndex(k) to compute the index I k (t).

Multi-Players MAB

For Cognitive Radio and other applications, a well-studied extension is to consider M ≥ 2 players, interacting on the same K arms. Whenever two or more players select the same arm at the same time, they all suffer from a collision. Different collision models has been proposed, and the simplest one consists in giving a 0 reward to each colliding players. Without any centralized supervision or coordination between players, they must learn to access the M best resources (i.e., arms with highest means) without collisions. SMPyBandits implements all collision models found in the literature, as well as all the algorithms from the last 10 years (including rhoRand, MEGA, MusicalChair, and our state-of-the-art algorithms RandTopM and MCTopM from [START_REF] Besson | Multi-Player Bandits Revisited[END_REF]). For comparison, realistic or full-knowledge centralized algorithms are also implemented.

Features

With this numerical framework, simulations can run on a single CPU or a single multi-core machine using joblib [START_REF] Varoquaux | Joblib: running Python functions as pipeline jobs[END_REF], and summary plots are automatically saved as high-quality PNG, PDF and EPS, using matplotlib [START_REF] Hunter | Matplotlib: A 2D graphics environment[END_REF] and seaborn [START_REF] Waskom | Seaborn: statistical data visualization[END_REF]. Raw data from each simulation is also saved in a HDF5 ® file using h5py [START_REF] Collette | h5py: HDF5 for Python[END_REF], an efficient and compressed binary format, to allow easy post-mortem exploration of simulation results. Making new simulations is very easy, one only needs to write a configuration script (configuration.py), without needing a complete knowledge of the internal code architecture.

A complete Sphinx documentation, for each algorithm and all parts of the codebase, even including the constants in the different configuration files, is available here: https://SMPyBandits.GitHub.io.

How to run experiments?

We show how to install SMPyBandits, and an example of how to run a simple experiment. This bash snippet 1 shows how to clone the code2 , and install the requirements for Python 3 (once): # 1. get the code in the folder you want $ git clone https://GitHub.com/SMPyBandits/SMPyBandits.git $ cd SMPyBandits.git # 2. install the requirements $ pip install -r requirements.txt Launching simulations is easy, for instance this snippet shows how to start N = 1000 repetitions of a simple non-Bayesian Bernoulli-distributed problem, for K = 9 arms, an horizon of T = 10000 and on 4 CPUs. Such simulation takes about 20 minutes, on a standard 4-cores 64 bits GNU/Linux laptop. Using environment variables (N=1000 etc) in the command line is not required, but it is convenient: # 3. run a single-player simulation $ BAYES=False ARM_TYPE=Bernoulli N=1000 T=10000 K=9 N_JOBS=4 \ MEANS=[0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9] python3 main.py configuration.py

Example of simulation and illustration

A small script configuration.py is used to import the arm classes, the policy classes and define the problems and the experiments. Choosing the algorithms is easy by customizing the configuration["policies"] list in the configuration.py file. For instance, one can compare the standard anytime klUCB algorithm against the non-anytime variant klUCBPlusPlus algorithm, and also UCB (with α = 1) and Thompson (with Beta posterior).

configuration["policies"] = [ {"archtype": klUCB, "params": {"klucb": klucbBern}}, {"archtype": klUCBPlusPlus, "params": {"horizon": HORIZON, "klucb": klucbBern}}, {"archtype": UCBalpha, "params": {"alpha": 1.0}}, {"archtype": Thompson, "params": {"posterior": Beta}} ] Running the simulation as shown above will save figures in a sub-folder, as well as save data (pulls, rewards and regret) in a HDF5 file 3 . Figure 1 below shows the average regret for these 4 algorithms. The regret is the difference between the cumulated rewards of the best fixed-armed strategy (which is the oracle strategy for stationary bandits), and the cumulated rewards of the considered algorithms. They all perform very well: each algorithm is known to be order-optimal (i.e., its regret is proved to match the lower-bound up-to a constant), and each but UCB is known to be optimal (i.e. with the constant matching the lower-bound). For instance, Thomson sampling is very efficient in average (in yellow), and UCB shows a larger variance (in red).

Research papers using SMPyBandits

SMPyBandits was used for the following research articles since 2017:

• For Besson and Kaufmann (2018b), we used SMPyBandits for all the simulations for multi-player bandit algorithms 4 . We designed the two RandTopM and MCTopM algorithms and proved than they enjoy logarithmic regret in the usual setting, and outperform significantly the previous state-of-the-art solutions (i.e., rhoRand, MEGA and MusicalChair).

• In Besson et al. (2018), we used SMPyBandits to illustrate and compare different aggregation algorithms 5 . We designed a variant of the Exp3 algorithm for online aggregation (or boosting)

3. E.g., this simulation produces GitHub.com/SMPyBandits/SMPyBandits/blob/master/plots/paper/example.hdf5. 4. See the page SMPyBandits.GitHub.io/MultiPlayers on the documentation. 5. See the page SMPyBandits.GitHub.io/Aggregation on the documentation.

of experts [START_REF] Bubeck | Regret Analysis of Stochastic and Non-Stochastic Multi-Armed Bandit Problems[END_REF], called Aggregator. Aggregating experts is a well-studied idea in sequential learning and in machine learning in general. We showed that it can be used in practice to select on the run the best bandit algorithm for a certain problem from a fixed pool of experts. This idea and algorithm can have interesting impact for Opportunistic Spectrum Access applications [START_REF] Jouini | Multi-Armed Bandit Based Policies for Cognitive Radio's Decision Making Issues[END_REF] that use multi-armed bandits algorithms for sequential learning and network efficiency optimization.

• In Besson and Kaufmann (2018a), we used SMPyBandits to illustrate and compare different "doubling trick" schemes 6 . In sequential learning, an algorithm is anytime if it does not need to know the horizon T of the experiments. A well-known trick for transforming any non-anytime algorithm to an anytime variant is the "Doubling Trick": start with an horizon T 0 ∈ N * , and when t > T i , use T i+1 = 2T i . We studied two generic sequences of growing horizons (geometric and exponential), and we proved two theorems that generalized previous results.

A geometric sequence suffices to conserve minimax regret bounds (in R T = O( √ T )), with a constant multiplicative loss ≤ 4, but cannot be used to conserve a logarithmic regret bound (in R T = O(log(T ))). And an exponential sequence can be used to conserve logarithmic bounds, with a constant multiplicative loss also ≤ 4 in the usual setting. It is still an open question to know if a well-tuned exponential sequence can conserve minimax bounds, or even "weak" minimax bounds (in R T = O( T log(T ))).

Dependencies

This library is written in Python (Foundation, 2017), for versions 2.7+ or 3.4+, using matplotlib [START_REF] Hunter | Matplotlib: A 2D graphics environment[END_REF] for 2D plotting, numpy (van der [START_REF] Stéfan Van Der Walt | The NumPy Array: A Structure for Efficient Numerical Computation[END_REF] for data storing, random number generations and operations on arrays, scipy [START_REF] Jones | SciPy: Open source scientific tools for Python[END_REF] for statistical and special functions, and seaborn [START_REF] Waskom | Seaborn: statistical data visualization[END_REF] for pretty plotting and colorblind-aware colormaps.

Optional dependencies include joblib [START_REF] Varoquaux | Joblib: running Python functions as pipeline jobs[END_REF] for parallel simulations, numba (Inc. et al., 2017) for automatic speed-up on small functions, sphinx [START_REF] Brandl | Sphinx: Python documentation generator[END_REF] for generating the documentation, and jupyter [START_REF] Kluyver | Jupyter Notebooks -a publishing format for reproducible computational workflows[END_REF] used with ipython [START_REF] Pérez | IPython: a System for Interactive Scientific Computing[END_REF] to experiment with the code.

Figure 1 :

 1 Figure1: Example of a single-player simulation showing the average regret and histogram of regrets of 4 algorithms. They all perform very well: each algorithm is known to be order-optimal (i.e., its regret is proved to match the lower-bound up-to a constant), and each but UCB is known to be optimal (i.e. with the constant matching the lower-bound). For instance, Thomson sampling is very efficient in average (in yellow), and UCB shows a larger variance (in red).

SMPyBandits is also available on Pypi, see pypi.org/project/SMPyBandits. You can install it directly with sudo pip install SMPyBandits, or from a virtualenv.


Thomas Pellissier Tanon

Daria Stepanova
email: dstepano@mpi-inf.mpg.de

Simon Razniewski

Paramita Mirza
email: paramita@mpi-inf.mpg.de

Gerhard Weikum
email: weikum@mpi-inf.mpg.de

Completeness-aware Rule Learning from Knowledge Graphs *

Knowledge graphs (KGs) are huge collections of primarily encyclopedic facts that are widely used in entity recognition, structured search, question answering, and other tasks. Rule mining is commonly applied to discover patterns in KGs. However, unlike in traditional association rule mining, KGs provide a setting with a high degree of incompleteness, which may result in the wrong estimation of the quality of mined rules, leading to erroneous beliefs such as all artists have won an award. In this paper we propose to use (in-)completeness meta-information to better assess the quality of rules learned from incomplete KGs. We introduce completeness-aware scoring functions for relational association rules. Experimental evaluation both on real and synthetic datasets shows that the proposed rule ranking approaches have remarkably higher accuracy than the state-of-the-art methods in uncovering missing facts.

Introduction

Motivation. Advances in information extraction have led to general-purpose knowledge graphs (KGs) containing billions of positive facts about the world (e.g., [START_REF] Carlson | [END_REF][START_REF] Bollacker | [END_REF]Auer et al., 2007;Mahdisoltani et al., 2015]). KGs are widely applied in semantic web search, question answering, web extraction and many other tasks. Unfortunately, due to their wide scope, KGs are generally incomplete. To account for the incompleteness, they typically adopt the Open World Assumption (OWA) under which missing facts are treated as unknown rather than false.

An important task over KGs is rule learning [START_REF] Galarraga | [END_REF]Gad-Elrab et al., 2016;[START_REF] Sazonau | [END_REF]Wang and Li, 2015;Lisi, 2010;[START_REF] Claudia D'amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF], which is relevant for a variety of applications ranging from knowledge graph curation (completion, error detection) [Paulheim, 2017] to data mining and semantic culturonomics [START_REF] Suchanek | [END_REF]. However, since such rules are learned from incomplete data, they might be erroneous and might make incorrect predictions on missing facts. For example, from the KG in Fig. 1 r 1 : hasChild (X , Y ) ← worksAt(X, Z), educatedAt(Y, Z) could be mined, which states that workers of certain institutions often have children among the people educated there, as this is frequently the case for popular scientists. While r 1 is clearly not universal and should be ranked lower than the rule r 2 : hasSibling(X,Z) ← hasFather(X, Y), hasChild(Y, Z), standard rule measures like confidence (i.e., conditional probability of the rule's head given its body) incorrectly favor r 1 over r 2 for the given KG.

Efforts have been put into adding completeness information to databases [START_REF] Levy | [END_REF][START_REF] Etzioni | [END_REF] and recently to knowledge bases [START_REF] Razniewski | [END_REF]Darari et al., 2013]. This could be done by detecting the concrete numbers of facts of certain types that hold in the real world (e.g., "Einstein has 3 children") exploiting Web extraction or crowd-sourcing [START_REF] Prasojo | Managing and consuming completeness information for wikidata using COOL-WD[END_REF][START_REF] Darari | [END_REF][START_REF] Mirza | [END_REF]. Such meta-data provides a lot of hints about the KG's topology, and reveals parts that should be especially targeted by rule learning methods. However, surprisingly, to date, no systematic way of making use of such information in rule learning exists.

In this work we exploit meta-data about the expected number of edges in KGs for better assessment of learned rules.

State of the art and its limitations. In [START_REF] Galarraga | [END_REF] a completeness-aware rule scoring based on the partial completeness assumption (PCA) was introduced. The idea of PCA is that whenever at least one object for a given subject and a predicate is in a KG (e.g., "Eduard is Einstein's child"), then all objects for that subject-predicate pair (Einstein's children) are assumed to be known. This assumption was taken into account in rule scoring, and empirically it turned out to be indeed valid in real-world KGs for some topics. However, PCA inappropriately treats cases, when edges in a graph are randomly missing. Similarly, whether to count absence of contradiction as confirmation for default rules was discussed in [START_REF] Doppa | [END_REF]. In [START_REF] Galárraga | [END_REF] new completeness data was learned from a KG by taking as ground truth completeness data obtained via crowd-sourcing. The acquired statements were used in a post-processing step of rule learning to filter out violating predictions. However, this kind of filtering does not have any impact on the quality of the mined rules and the incorrect predictions for instances about which no completeness information exists.

Contributions. In this shortened version of our work [START_REF] Tanon | [END_REF] we present an approach that accounts for meta-data about the number of edges that should exist for given subject-predicate pairs in the ranking stage of rule learning. The novel rule ranking measures have been evaluated both on real-world and synthetic datasets, showing that they outperform existing ones both with respect to the quality of the mined rules and the predictions they produce.

Preliminaries

Knowledge graphs. Knowledge graphs (KG) represent interlinked collections of factual information, and they are often encoded using the RDF data model [START_REF] Lassila | Resource description framework (RDF) model and syntax specification[END_REF]. The content of KGs is a set of subject predicate object triples, e.g., john hasChild alice . For encyclopedic knowledge graphs on the semantic web, usually the open world assumption (OWA) is employed, i.e., these graphs contain only a subset of the true information.

In the following we write triples using binary predicates, like hasChild (john, A signature of a KG G is Σ G = R, C , where R is the set of binary predicates and C is the set of constants appearing in G. Following [Darari et al., 2013], we define the gap between the available graph G a and the ideal graph G i , which contains all correct facts over R and C that hold in the real world. An incomplete data source is a pair G = (G a , G i ) of two KGs, where G a ⊆ G i and Σ G a = Σ G i . Note that the ideal graph G i is an imaginary construct whose content is generally not known. What is known instead is to which extent the available graph approximates/lacks information wrt. the ideal graph, e.g., "Einstein is missing 2 children and Feynman none"). We formalize this knowledge as cardinality assertions in Sec. 3.

Rule learning. Association rule learning concerns the discovery of frequent patterns in a data set and the subsequent transformation of these patterns into rules. A conjunctive query Q over G is of the form p 1 (x 1 , y 1 ), . . . , p m (x m , y m ), where x i and y i are symbolic variables or constants and

p i ∈ R are binary predicates. The answer of Q on G is the set Q(G) = {(ν(x 1 ), . . . , ν(x m ), ν(y 1 ), . . . , ν(y m )) | ∀i : p i (ν(x i ), ν(y i ))
∈ G} where ν is a function that maps variables and constants to elements of C. The support of Q in G is the number of distinct tuples in the answer of Q on G [START_REF] Dehaspe | Luc Dehaspe and Luc De Raedt. Mining association rules in multiple relations[END_REF]].

An association rule is of the form

Q 1 ⇒ Q 2 , such that Q 1 and Q 2 are both conjunctive queries and Q 1 ⊆ Q 2 , i.e., Q 1 (G ) ⊆ Q 2 (G )
for any possible KG G . We call Q 2 the body of the rule and Q 1 its head. In this work we exploit association rules for reasoning purposes, and thus (with some abuse of notation) treat them as logical rules, i.e., for

Q 1 ⇒ Q 2 we write Q 2 \Q 1 ← Q 1 ,
where Q 2 \Q 1 refers to the set difference between Q 2 and Q 1 seen as sets of atoms.

Classical scoring of association rules is based on rule support, body support and confidence. For a rule r : h(X , Y ) ← B where B is a conjunctive query over the variables Z ⊇ X, Y and/or constants, they are defined in [START_REF] Galarraga | [END_REF] as:

supp(r) := #(x, y) : ∃ Z : B ∧ h(x, y) (1) supp(B) := #(x, y) : ∃ Z : B (2) conf (r) := supp(r) supp(B) (3)
where #γ : Γ denotes the number of γ that fulfill the condition Γ, and conf (r)

∈ [0, 1]. Example 1.
Consider the KG G a in Fig. 1 and the rules r 1 :

hasChild (X , Y ) ← worksAt(X, Z), educatedAt(Y, Z) and r 2 : hasSibling(X , Z ) ← hasFather (X , Y ), hasChild (Y , Z ) mined from it.
The body and rule supports of r 1 over the KG are supp(B ) = 8 and supp(r 1 ) = 2 respectively. Hence, we have conf (r 1 ) = 2 8 . Analogously, conf (r 2 ) = 1 6 . Support and confidence were originally developed for scoring rules over complete data. If data is missing, their interpretation is not straightforward and they can be misleading. In [START_REF] Galarraga | [END_REF], confidence under the partial completeness assumption (PCA) has been proposed as a measure, which guesses negative facts by assuming that data is usually added to KGs in batches, i.e., if at least one child of John is known then most probably all John's children are present in the KG. Formally, the PCA confidence is defined as

conf pca (r) := supp(r) #(x, y) : ∃ Z : B ∧ ∃y : h(x, y ) ∈ G a (4)
Example 2. We obtain conf pca (r 1 ) = 2 4 . Indeed, since carol and dave are not known to have any children in the KG, four existing body substitutions are not counted in the denominator. Meanwhile, we have conf pca (r 2 ) = 1 6 , since all people that are predicted to have siblings by r 2 already have siblings in the available graph.

Given a rule r and a KG G the application of r on G results in a rule-based graph completion. More formally, Definition 1 (Rule-based KG completion). Let G be a KG over the signature

Σ G = R, C and let r : h(X , Y ) ← B be a rule mined from G, i.e. a rule over Σ G . Then the completion of G is a graph G r := G ∪ {h(x, y) | ∃ Z : B}. Example 3. We have G a r1 = G a ∪ { hasChild(john, dave
), hasChild(carol, mary), hasChild(dave, dave), hasChild(carol, carol), hasChild(dave, bob), hasChild(mary, dave) }.

Note that G i is the perfect completion of G a , i.e., it is supposed to contain all correct facts with entities and relations from Σ G a that hold in the current state of the world. The goal of rule-based KG completion is to extract from G a a set of rules R such that ∪ r∈R G a r is as close to G i as possible.

3 Completeness-aware Rule Scoring

Scoring and ranking rules are core steps in association rule learning. A variety of measures for ranking rules have been proposed, with prominent ones being confidence, conviction and lift. The existing (in-)completeness-aware rule measure in the KG context (the PCA confidence (4) [START_REF] Galarraga | [END_REF]) has two apparent shortcomings: First, it only counts as counterexamples those pairs (x, y) for which at least one h(x, y ) is in G a for some y and a rule's head predicate h. Hence, it may incorrectly give high scores to rules predicting facts for very incomplete relations, e.g., place of baptism. Second, it is not suited for data in non-functional relations that is not added in batches, such as awards, where the important ones are added instantly, while others much slower or never. Thus, in this work we focus on the improvements of rule scoring functions by making use of the extra (in-)completeness meta-data. Before dwelling into the details of our approach we discuss the formal representation of such meta-data.

Cardinality

Statements. We represent the (in)completeness meta-data using cardinality statements by reporting (the numerical restriction on) the absolute number of facts over a certain relation in the ideal graph G i . More specifically, we define the partial function num that takes as input a predicate p and a constant s and outputs a natural number corresponding to the number of facts in G i over p with s as the first argument:

num(p, s) := #o : p(s, o) ∈ G i (5)
These cardinality statements can be obtained using web extraction techniques [START_REF] Mirza | [END_REF]. With such statements, it is also possible to encode cardinalities on the number of subjects for given predicates and objects, provided that inverse relations can be expressed in a KG. Naturally, the number of missing facts for a given p and s can be obtained as

miss(p, s) := num(p, s) -#o : p(s, o) ∈ G a (6)
Example 4. Consider the KG in Fig. 1. and the following cardinality statements for it:

• num(hasChild , john) = num(hasChild , mary) = 3; num(hasChild , alice) = 1; num(hasChild , carol ) = num(hasChild , dave) = 0; • num(hasSibling, bob) = 3; num(hasSibling, alice) = num(hasSibling, carol ) = num(hasSibling, dave) = 2. We then have:

• miss(hasChild , mary) = miss(hasChild , john) = miss(hasChild , alice) = 1; miss(hasChild , carol ) = miss(hasChild , dave) = 0; • miss(hasSibling, bob) = miss(hasSibling, carol ) = 2; miss(hasSibling,alice) = miss(hasSibling,dave)= 1.

We are now ready to define the completeness-aware rule scoring problem. Given a KG and a set of cardinality statements, completeness-aware rule scoring aims to score rules not only by their predictive power on the known KG, but also wrt. the number of wrongly predicted facts in complete areas and newly predicted facts in known incomplete areas.

In the following we discuss and compare two novel approaches for completeness-aware rule scoring. These are (i) the completeness confidence, and (ii) directional metric. Henceforth, all examples consider the KG in Fig. 1, rules from Ex. 1, and cardinality statements described in Ex. 4.

Completeness Confidence

In this work we propose to explicitly rely on incompleteness information in determining whether to consider an instance as a counterexample for a rule at hand or not.

To do that, we first define two indicators for a given rule r : h(X , Y ) ← B, reflecting the number of new predictions made by r in incomplete (npi (r )) and, respectively, complete (npc(r )) KG parts:

npi (r) := x min(#y: h(x, y) ∈ G a r \G a , miss(h, x)) (7) npc(r) := x max(#y: h(x, y) ∈ G a r \G a -miss(h, x), 0) (8
) Note that summation is done exactly over those entities for which miss is defined. Exploiting these additional indicators for r : h(X, Y ) ← B we obtain the following completenessaware confidence:

conf comp (r) := supp(r) supp( B) -npi (r) (9)
Example 5. The rule r 2 matches more the real world than r 1 and, so, should be preferred over it. For our novel completeness confidence, we get conf comp (r 1 ) = 2 6 and conf comp (r 2 ) = 1 2 , resulting in the desired rule ordering, not achieved by existing measures (see Ex. 1 and 2).

Under the closed world assumption conf comp (r) = conf (r) because ∀x : miss(h, x) = 0. Similarly, under the partial completeness assumption conf comp (r) = conf pca (r). Thus, our completeness confidence is a more general measure than both the standard and the PCA confidence.

Directional Bias

If rule mining does make use of completeness information, and both do not exhibit any statistical bias, then intuitively the rule predictions and the (in)complete areas should be statistically independent. On the other hand, correlation between the two indicates that the rule-mining is (in)completeness-aware. Example 6. Suppose in total a given KG stores 1 million humans, and we know that 10,000 (1%) of these are missing some children (incompleteness information), while we also know that 1000 of the persons are definitely complete for children (0.1%). Let the set of rules mined from a KG predict 50,000 new facts for the hasChild relation. Assuming independence between predictions and (in)completeness statements, we would expect 1% out of 50,000, i.e., 500 facts to be predicted in the incomplete areas and 0.1%, i.e., 50 in the complete KG parts. If instead we find 1000 children predicted for people that are missing correspondingly many children, and 10 for people that are not missing these, the former deviates from the expected value by a factor of 2, and the latter by a factor of 5.

Following the intuition from the above example, we propose to look at the extent of the non-independence of completeness information and rule mining to quantify the (in)completenessawareness of rule mining. Let us consider predictions made by rules in a given KG, and denote by enpi(r) and enpc(r) the expected numbers of facts added by the rule r in the incomplete and complete areas respectively. Then for α ∈ [0, 1] being the weight given to completeness versus incompleteness, the directional coefficient of r is defined as follows:

direct coef (r) := α • enpc(r) npc(r) + (1 -α) • npi (r) enpi (r) (10)
Unlike the other measures that range from 0 to 1, the directional coefficient takes values between 0 and infinity, where 1 is the default. The higher the directional coefficient is, the more "completeness-aware" the rules are.

In practice, expected values might be difficult to compute, and statistical independence is a strong assumption. An alternative that does not require knowledge about expected values is to directly measure the proportion between predictions in complete and incomplete parts. We call this the directional metric, which is computed as

direct metric(r) := npi (r) -npc(r) 2 • (npi (r) + npc(r)) + 0.5 (11)
The metric is similar to the directional coefficient, but does not require knowledge about the expected number of predictions in complete/incomplete KG parts. It is designed to range between 0 and 1 again, thus allowing convenient weighting with other [0, 1] measures. The directional metric of a rule that predicts the same number of facts in incomplete as in complete parts is 0.5, a rule that predicts twice as many facts in incomplete parts has a value of 0.66, and so on.

We propose to consider the combination of a weighted existing association rule measure, e.g., confidence or lift and the directional metric, with the weighting factor β = 0..1. Using confidence, we obtain

wdm(r)=β•conf (r)+(1-β)•direct metric(r) (12)
Example 7. It holds that direct metric(r 1 ) ≈ 0.33 and direct metric(r 2 ) = 0.8. Moreover, for confidence we get wdm(r 1 ) ≈ 0.29 and wdm(r 2 ) ≈ 0.48 with β = 0.5.

Evaluation

We have implemented our completeness-aware rule learning approach in a C++ system prototype CARL 1 , following a standard relational learning algorithm implementation such as [START_REF] Goethals | Relational association rules: Getting WARMeR[END_REF].

We restrict the search space by mining rules of the form r(X, Z) ← p(X, Y ), q(Y, Z)

We aim to compare the predictive quality of the top k rules mined by our completeness-aware approach with the ones learned by standard rule learning methods: (1) AMIE [START_REF] Galarraga | [END_REF] (PCA confidence) and ( 2) WarmeR [START_REF] Goethals | Relational association rules: Getting WARMeR[END_REF] (standard confidence).

1 The source code and all the data are available at https: //github.com/Tpt/CARL. Dataset. We used two datasets for the evaluation: (i) Wiki-dataPeople, which is a dataset we have created from the Wikidata knowledge graph, containing 2.4M facts over 9 predicates about biographical information and family relationships of people; and (ii) LUBM, which is a synthetic dataset describing the structure of a university [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF].

For the WikidataPeople dataset, the approximation of the ideal KG (G i ) is obtained by applying solid rules from the family domain. We acquired cardinality statements using data from Freebase [Pellissier Tanon et al., 2016] and hand-crafted rules relying on the PCA [START_REF] Galarraga | [END_REF] assumption. This resulted in 10M cardinality statements.

LUBM G i , with 1.2M facts, was constructed by running the LUBM data generator. 464K cardinality statements were obtained by assuming the PCA on the whole dataset.

Experimental Setup. To assess the effect of our proposed measures, we first construct versions of the available KG (G a ) by removing parts of the data from G i and introducing a synthetic bias in the data (i.e., leaving many facts in G a for some relations and few for others). The synthetic bias is needed to simulate our scenario of interest, where some parts of G a are very incomplete, while others are fairly complete, which is indeed the case in real world KGs. In Wikidata, for instance, 2.7% of all humans have an assertion about their father, yet only 0.8% have an assertion about their mother.

We proceed in two steps: First, we define a global ratio, which determines a uniform percentage of data retained in the available graph. To further refine this, we then factor a predicate ratio individually for each predicate.

For a given predicate, the final ratio of facts in G a retained from those in G i is then computed as min(1, 2

• k • n),
where k is the predicate ratio and n is the global ratio.

The assessment of the rules learned from different versions of the available KG is performed by comparing rule predictions with the approximation of G i . More specifically, every learned rule is assigned a quality score, defined as:

quality score(r) = |G a r ∩ G i \ G a | |G a r \ G a | (14)
This scoring naturally allows us to control the percentage of rule predictions that hit our approximation of G i , similar to standard precision estimation in machine learning.

Results. From every version of the available KG we have mined rules of the form (13) and kept only rules r with conf (r) ≥ 0.001 and supp(r) ≥ 10, whose head coverage (ratio of the number of predicted facts that are in G a over the number of facts matching the rule head) is greater than 0.001. Evaluation results for WikidataPeople and LUBM datasets are in Figure 2. The horizontal axis displays the global ratio used for generating G a . The Pearson correlation factor (vertical axis) between each ranking measure and the rules quality score ( 14) is used to evaluate the measures' effectiveness.

For the WikidataPeople KG, directional metric, weighted directional metric and completeness confidence show the best results. For the LUBM KG, the completeness confidence outperforms the rest of the measures, followed by the standard confidence and the weighted directional metric.

Conclusion

We have defined the problem of learning rules from incomplete KGs enriched with the exact numbers of missing edges of certain types, and proposed several novel rule ranking measures that effectively make use of the meta-knowledge about complete and incomplete KG parts: completeness confidence and the (weighted) directional metric. Our measures have been injected in the rule learning prototype CARL and evaluated on real-world and synthetic KGs, demonstrating significant improvements both with respect to the quality of mined rules and predictions they produce.

  Figure 1: Example KG

  Evaluation results for WikidataPeople and LUBM datasets