Minsu Cho

Jian Sun

Olivier Duchenne

Jean Ponce

A major challenge in real-world feature matching problems is to tolerate the numerous outliers arising in typical visual tasks. Variations in object appearance, shape, and structure within the same object class make it harder to distinguish inliers from outliers due to clutters. In this paper, we propose a max-pooling approach to graph matching, which is not only resilient to deformations but also remarkably tolerant to outliers. The proposed algorithm evaluates each candidate match using its most promising neighbors, and gradually propagates the corresponding scores to update the neighbors. As final output, it assigns a reliable score to each match together with its supporting neighbors, thus providing contextual information for further verification. We demonstrate the robustness and utility of our method with synthetic and real image experiments.

Introduction

Feature matching lies at the heart of computer vision research, and most vision problems involve correspondence tasks in different forms [START_REF] Forsyth | Computer vision: A modern approach[END_REF]. A major challenge in realworld matching problems is to tolerate the numerous outliers arising in typical situations. In images and videos, objects of interest often appear small against dominant backgrounds, and also involve variations in appearance, shape, and structure. These variations in cluttered scenes make it harder to distinguish inlier features from outliers. To tackle real-world vision tasks, thus, feature matching should be robust to a large number of outlier features while effectively using mutual relations among features.

This paper addresses the issues with a max-pooling approach to graph matching [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. Let us suppose we have a large set of candidate matches from the features that make up a target object with numerous false candidates. In evaluating a candidate match, the nearby matches are useful con- We address the issue with a max-pooling approach to graph matching. The proposed method is not only resilient to deformations but also remarkably tolerant to outliers. Each node on the left image corresponds to one with the same color on the right image, where bigger nodes represent more similar nodes. (best viewed in color.) textual information, and graph matching provides a powerful framework for exploiting these relational similarities. We propose to adopt a feature-pooling perspective [START_REF] Bourdev | Describing people: a poselet-based approach to attribute classification[END_REF] into this graph matching framework. The proposed method computes the score of each candidate match using maximal support from nearby matches, which corresponds to max-pooling of nearby features. As both the max-pooled matches and the scores improve each other in our optimization process, the method efficiently avoids the adverse effect of false matches or outliers. Our experiments demonstrate its robustness to outliers, and significant improvement over recent state of the art methods.

Related work

Graph matching is widely used in computer vision problems such as finding feature correspondences [START_REF] Cho | Progressive graph matching: Making a move of graphs via probabilistic voting[END_REF][START_REF] Duchenne | A tensorbased algorithm for high-order graph matching[END_REF][START_REF] Torresani | Feature correspondence via graph matching: Models and global optimization[END_REF], shape matching [START_REF] Sharma | Topologicallyrobust 3d shape matching based on diffusion geometry and seed growing[END_REF][START_REF] Zaslavskiy | A path following algorithm for the graph matching problem[END_REF], object recognition [START_REF] Berg | Shape matching and object recognition using low distortion correspondences[END_REF][START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF], and video analysis [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF]. Since graph matching is mathematically expressed as a quadratic assignment problem [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF], which is NP-hard, most research has long focused on developing accurate and efficient approximate algorithms [START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF][START_REF] Umeyama | An eigen decomposition approach to weighted graph matching problems[END_REF]. In feature matching and object recognition, both a reference and a test scene are represented as graphs using visual features, and graph matching finds correspondences by minimizing the structural distortions between the two graphs. Contrary to rigid geometric constraints used in popular methods such as RANSAC and the Hough transform, e.g., planar assumptions or epipolar geometry [START_REF] Forsyth | Computer vision: A modern approach[END_REF], graph matching allows non-rigid deformations and provides greater robustness in matching and recognition [START_REF] Berg | Shape matching and object recognition using low distortion correspondences[END_REF][START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF][START_REF] Leordeanu | Beyond local appearance: category recognition from pairwise interactions of simple features[END_REF]. As observed in recent evaluations [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF][START_REF] Zhou | Deformable graph matching[END_REF], however, current methods are still vulnerable to the large amount of outliers, that typically arise in highly cluttered scenes. Our approach tackles this issue based on a max-pooling scheme, and improves outlier-tolerance over the current state of the arts.

Feature pooling aims to transform feature representation into a more compact one that preserves important information while discarding irrelevant details [START_REF] Bourdev | Describing people: a poselet-based approach to attribute classification[END_REF]. The pooling operation typically performs a max, average, or sum over the feature responses in a local or global spatial region. Many recent recognition methods adopt it to compute local or global bags of features, e.g., vector-quantizing feature descriptors, computing the codeword frequencies over local or global areas [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF][START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF], and learning the invariant image features in convolutional neural networks [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] Lee | Convolutional deep belief networks for scalable unsupervised learning of hierarchical representations[END_REF]. As witnessed by the success of the spatial pyramid model [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF] and deep learning methods [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] Lee | Convolutional deep belief networks for scalable unsupervised learning of hierarchical representations[END_REF], appropriate pooling strategies achieve invariance to image variations, more compact representations, and better robustness to noise. Our approach will show how these advantages can also be achieved in a graph matching framework.

Graph matching and max-pooling

In this section we revisit the standard formulation of graph matching, and describe our novel max-pooling formulation and its optimization in the graph matching framework.

Standard formulation

We are given two attributed graphs G = (V, E) and G ′ = (V ′ , E ′ ), where V represents a set of nodes and E represents a set of edges. Here, the graph G represents a target object model with its features as nodes and their relations as edges, and graph G ′ represents a scene. A solution of matching is defined as a subset of possible correspon-dences X ⊂ V × V ′ , represented by a binary assignment matrix X ∈ {0, 1} n×n ′

, where n and n ′ denote the number of nodes in G and G ′ , respectively. If v i ∈ V matches v ′ a ∈ V ′ , then X ia = 1, and X ia = 0 otherwise. We denote by x ∈ {0, 1} nn ′ , a column-wise vectorized replica of X.

The objective function f (x) measures the mutual similarity of graph attributes, and is typically decomposed into a unary similarity function s V (v i , v ′ a ) for a node pair of v i in V and v ′ a in V ′ , and a pairwise similarity function s E (e ij , e ′ ab ) for an edge pair of e ij in E and e ′ ab in E ′ . The similarity functions are usually represented by a symmetric affinity matrix A, where non-diagonal elements are assigned as A ia;jb = s E (e ij , e ′ ab ), and diagonal terms as

A ia;ia = s V (v i , v ′ a ).
In general, the standard objective function of graph matching is defined as:

f (x) = xia=1 x jb =1 s E (e ij , e ′ ab ) + xia=1 s V (v i , v ′ a ) = x ⊺ Ax. (1)
Finally, the graph matching problem can be expressed as finding the assignment vector x * that maximizes the objective function f (x) as follows:

x * = arg max

x x ⊺ Ax (2a) s.t. x ∈ {0, 1} nn ′ n i=1 x ia ≤ 1, n ′ a=1 x ia ≤ 1, (2b)
where Eq. (2b) induces the matching constraints, thus making x an assignment vector [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Cour | Balanced graph matching[END_REF][START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF][START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF]. In essence, the objective function accumulates all the affinity values relevant to the assignment. The formulation in Eq. ( 2) is an integer quadratic programming (IQP) problem. More precisely, it is the quadratic assignment problem, which is known to be NP-hard. Due to its generality and flexibility, this formulation and its extensions has been favored in recent graph matching research [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Cho | Progressive graph matching: Making a move of graphs via probabilistic voting[END_REF][START_REF] Duchenne | A tensorbased algorithm for high-order graph matching[END_REF][START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF][START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF][START_REF] Suh | Graph matching via sequential monte carlo[END_REF][START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF][START_REF] Zhou | Deformable graph matching[END_REF].

Max-pooling for matching

The goal of feature pooling is to transform a joint feature representation into a more compact one that preserves important information while discarding irrelevant details [START_REF] Bourdev | Describing people: a poselet-based approach to attribute classification[END_REF][START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF][START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF]. Here we introduce a feature pooling perspective in the graph matching framework. Previous algorithms modify the original problem of Eq. (2), usually by relaxing the constraints of Eq.(2b) on the solution, in order to alleviate the NP-hard property in the original problem. A common approach is to relax the integer and matching constraints of Eq.(2b) from the standard objective, and aim at maximizing the quadratic function f (x) = x ⊺ Ax in a continuous domain. The function can be approximated by the first order Taylor expansion around the current solution x k :

f (x) ≈ f (x k ) + (x -x k ) ⊺ Ax k . (3)
In the iterative first-order optimization framework, maximizing the second term x ⊺ Ax k with a unit l 2 -norm constraint boils down to the following update at each iteration:

x k+1 ← 1 Ax k 2 Ax k , (4)
which is equivalent to the power method of spectral matching [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF]. Methods of [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Duchenne | A tensorbased algorithm for high-order graph matching[END_REF][START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF][START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF] combine an additional projection step with this to guide the solution closer to a feasible region consistent with matching constraints. All these iterative optimization methods, however, share the similar form of Eq.( 4) at their heart. In the context of graph matching, given two graphs G and G ′ , each element x ia represents the assignment confidence associated with a candidate match (v i , v ′ a ). The confidence x ia is updated by Eq.( 4) in which Ax can be written as:

(Ax) ia = x ia A ia;ia + j∈Ni b∈Na x jb A ia;jb (5) = x ia s V (v i , v ′ a ) + j∈Ni b∈Na
x jb s E (e ij , e ′ ab ).

The second term can be seen as accumulating scores from N i , each of which is the sum of weighted pairwise affinities: b∈Na A ia;jb x jb . Figure 2(a) shows how this works, i.e., it sums over all the affinities, no matter whether they really match to node a. In this perspective, the product Ax used in the standard formulation of Eq.(2a) can be viewed as performing sum-pooling or average-pooling [START_REF] Bourdev | Describing people: a poselet-based approach to attribute classification[END_REF], which accumulates all the weighted affinities respect to each match to measure the confidence of how compatible the match is with the others. A problem of sum-pooling, commonly used in other matching methods, is that it is strongly influenced by uninformative or irrelevant elements, often resulting in bad local minimum.

To address this issue, we instead take the following maxpooling product: [START_REF] Cho | Reweighted random walks for graph matching[END_REF] which collects the best pairwise affinity from each neighbor. Unlike the sum-pooled confidence of Ax, which sums up all weighted affinities of candidate matches for each feature, the max-pooled confidence of A ⊛ x corresponds to the maximum possible matching score for each feature. Each neighborhood can be seen as a spatial bin for pooling [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF].

(A ⊛ x) ia = x ia A ia;ia + j∈Ni max b∈Na x jb A ia;jb
There are two clear advantages in using A ⊛ x: (i) While Ax in the relaxed continuous domain inevitably contains a large amount of noisy scores from outliers, max-pooling selection in A⊛x effectively suppresses the noisy scores from numerous outlier features by ignoring most of them. This effect is similar to that of median filtering [START_REF] Arce | Nonlinear signal processing: a statistical approach[END_REF][START_REF] Wang | Progressive switching median filter for the removal of impulse noise from highly corrupted images[END_REF] in signal processing, which removes noise by taking the median 6), a candidate match (j, b) with the highest weighted affinity x ia;jb sE(eij, e ′ ab ) is selected among all possible matches as a support of j for (i, a). (c) In max-pooling, each candidate match has its own max-pooled support from all neighbors and a maxpooled score as a sum of their weighted affinities. A ⊛ x of Eq.( 6) computes such max-pooled confidences for all candidate matches. (Best viewed in color.) value of neighboring signals rather than the average value. (ii) Max pooling in A ⊛ x is very likely to provide higher scores only on true matches because the highest affinities from them are always selected and accidental high affinities occur rarely with outliers. These advantages are critical in practice because we usually need to collect a large number of candidate matches to avoid losing true matches among them, which leads to facing numerous outlier matches.

Proposed algorithm

Using the max-pooling product, we propose to address graph matching as follows. From the first-order approximation of Eq.( 3), we take the max-pooling product A ⊛ x, Algorithm 1: Max-pooling matching (MPM)

Input: affinity matrix A Output: soft-assignment x Initialize the starting assignment x as uniform; repeat for each candidate match (i, a) do x ia ← x ia A ia;ia + j∈Ni max b∈Na x jb A ia;jb ;

x ← 1

x 2

x; until x converges; Discretize the solution x if needed; instead of the sum-pooling product Ax. Then, we have the local objective at each iteration: x k+1 = arg max x x ⊺ (A⊛ x k ) under the unit l 2 -norm of x. Finally, we obtain the following iteration:

x k+1 = arg max ||x||2=1 x ⊺ (A ⊛ x k ) = 1 A ⊛ x k 2 A ⊛ x k . (7)
This method, dubbed max-pooling matching (MPM), is described in Algorithm 1. Since 1 , the proposed algorithm only maximizes a lower bound of the first-order approximation of Eq.( 3) at each iteration. In this algorithm, max-pooling implicitly involves surjective constraints, where each candidate correspondence is assigned the best supporting matches as shown in Fig. 2(b). These are "soft" constraints (e.g., as opposed to ones in [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF][START_REF] Suh | Graph matching via sequential monte carlo[END_REF]), the consistent elements of x being driven toward a solution satisfying these constraints (e.g., as similar to ones in [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Duchenne | A tensorbased algorithm for high-order graph matching[END_REF][START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF]). MPM itself does not prevent one-to-many nor many-to-one matches if they are well supported by maxpooled neighboring matches. It is the final discretization step that enforces any matching constraints explicitly.

x ⊺ Ax k ≥ x ⊺ (A ⊛ x k )
In general, MPM iterations do not monotonically increase the objective function of Eq.(2a). As can be seen in the experiments of Sec. 3.1, however, MPM turns out to be remarkably robust to outliers, and effectively optimizes the objective function after the final discretization, compared to recent state of the arts [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Cour | Balanced graph matching[END_REF][START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF][START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF]. In all our experiments, convergence has been obtained in 10 to 50 steps, but we do not have theoretical guarantees in general yet. A theoretical understanding of the convergence of our approach is clearly desirable, but left for future work.

Complexity. The computational complexity of MPM is O(nmkk ′ ) per iteration, where n and m represent the number of nodes in G and the number of candidate matches 1 Elements in A, x k , x are all non-negative, and the elements summed in A ⊛ x k correspond to a max-pooled subset of elements summed in Ax k . Therefore, it is obvious that

x ⊺ Ax k ≥ x ⊺ (A ⊛ x k ).
for each node, and k and k ′ denotes the size of neighborhood in G and G ′ , respectively. In practice, this is comparable or faster in speed than the recent state-of-the-art algorithms [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF][START_REF] Torresani | Feature correspondence via graph matching: Models and global optimization[END_REF][START_REF] Zhou | Deformable graph matching[END_REF]. Restricting the neighbors N i of node v i boils down to different kinds of spatial max-pooling centered on each feature i, and further reduces computational complexity.

Relation with other algorithms. MPM can be compared with other graph matching algorithms, which adopt a similar iterative optimization strategy [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Cour | Balanced graph matching[END_REF][START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF][START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF]. The iterative update in MPM resembles a gradient descent step in GA [START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF], a power method in SM [START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF], and a random walk step in RRWM [START_REF] Cho | Reweighted random walks for graph matching[END_REF]. Unlike those, however, the update step of MPM performs pooling of best features instead of using all observations, which make it robust to outliers. In the view of random walks for graph matching [START_REF] Cho | Reweighted random walks for graph matching[END_REF], this corresponds to a constrained random walking, which takes a random walk to one of max-pooled matches at each step.

Practical advantages in vision problems

The proposed method is adequate for practical matching problems in computer vision where the following critical issues frequently arise in many applications.

Clutter and deformations. In real-world images, target objects appear as small regions whereas clutters dominate larger regions. Even object regions also generate distracting features as feature detections are not perfectly stable nor repeatable [START_REF] Tuytelaars | Local invariant feature detectors: a survey[END_REF]. These numerous outliers become unsurmountable obstacles to matching. Furthermore, variations in appearance and shape make it harder to discern true matches from outliers. MPM provides strong robustness against outliers using adaptive max pooling, and addresses object deformations by minimizing distortion in both shape and appearance.

Contextual support. MPM provides reliable softassignments x by gradually updating max-pooled neighbor matches. In the end, each candidate match (i, a) is assigned not only a score x ia but also its max-pooled neighbor matches P(i, a) = {(j, b) | ∃j ∈ N i , b * = arg max b∈Na x jb A ia;jb }. These max-pooled neighbors are useful for further tasks. For example, they function as contextual information for verifying the presence of the match they support. They also reveal explicit relations between each match and its neighbors, providing better evidence for its correctness than relative scores of the soft-assignment x. Such better verified matches also could lead to more accurate localization of objects [START_REF] Endres | Learning collections of part models for object recognition[END_REF].

Structural flexibility. Despite surjective constraints used in max pooling, MPM itself does not necessarily force the result to be one-to-one correspondence. Any candidate match with strong max-pooled supports keeps a high score in x. In other words, MPM does not prevent one-to-many nor many-to-one matches if they are well supported by maxpooled neighboring matches. This enables to address structural flexibility in matching, which is important for many generic objects [START_REF] Maji | Part discovery from partial correspondence[END_REF]. For example, a clover may have three or four leaves, and an airplane may have four, two or no visible engines. The number of windows in a house are highly variable. There are also many kinds of repetitive patterns in nature as well as man-made objects. MPM is particularly adequate for dealing with such flexible structures without strict matching constraints.

Experimental evaluation

We evaluate the proposed algorithms on standard synthetic benchmarks and real image datasets. For comparison to the state of the art, reweighted random-walk matching (RRWM) [START_REF] Cho | Reweighted random walks for graph matching[END_REF], integer projected fixed-point matching (IPFP) [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF], and spectral matching with affine constraint (SMAC) [START_REF] Cour | Balanced graph matching[END_REF] are evaluated in the same setting2 . To bet-ter measure the effect of max-pooling, spectral matching (SM) [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] is also compared as a baseline, since it uses a comparable optimization strategy with sum pooling (Ax) instead of the max pooling (A ⊛ x).

Synthetic point set matching

This section presents comparative evaluations on the task of random point set matching, which is widely used as a benchmark test for graph matching [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Cour | Balanced graph matching[END_REF][START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF]. Synthetic point sets P and P ′ are built as follows. For the point set P , n in inlier points are randomly generated on R 2 using Gaussian distribution N (0, 1). Each point in P is then copied to the point set P ′ with additional Gaussian noise N (0, σ 2 ). Further outlier noise is created in P ′ by adding n out random points using N (0, 1). In this setup, we consider the point sets P and P ′ as the graphs G and G ′ , and test all the methods on them to quantitatively evaluate the matching accuracy. The number of inliers is fixed as n in = 10 or 20. For the pairwise similarity, the difference between the 4. Comparative matching examples on the object class dataset. Given an input image, features of each learned object model are matched and localized as circles, where bigger circles represent more similar features. Correctly matched features are connected by red lines, and otherwise by black lines. See Table 1 for the quantitative result on the entire dataset. (Best viewed in color.)

Euclidean distances of two point pairs is employed:

s E (e ij , e ′ ab ) = exp(-( p i -p j -p ′ a -p ′ b ) 2 /σ 2 s ). (8
) where σ 2 s = 0.5 in this experiment. No unary similarity is used: s V (v i , v ′ a ) = 0. This distance-based measure has been used in other papers [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Cour | Balanced graph matching[END_REF][START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF]. For all the methods, the same linear assignment of the Hungarian algorithm is performed on the resultant assignment vector as a postprocessing scheme enforcing one-to-one constraints.

The experimental results are shown in Fig. 3. The proposed method shows remarkable tolerance to the number of outliers, while all the other methods drop shapely with the number of outliers increases. Note that our experiment uses a large number of outliers (up to 20 times more than inliers) compared to the experiments in [START_REF] Cho | Reweighted random walks for graph matching[END_REF][START_REF] Cour | Balanced graph matching[END_REF][START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF][START_REF] Zhou | Deformable graph matching[END_REF]. In the case without deformation, as shown in Fig. 3(a), the proposed method performs perfectly without being distracted by outliers, because our max-pooling provides accurate neighboring supports when there is no deformation. Under deformation only, IPFP, RRWM, and our method perform comparable each other. For high deformation levels, MPM's robustness to deformation becomes slightly worse than IPFP and RRWM. In a more realistic situation with both of deformations and outliers, shown in Fig. 3(c), our method clearly outperforms the current state of the art. In the presence of both much larger deformations and more outliers together, the performance gap between MPM and other methods becomes modest as the problem itself starts making less and less sense. In practice, however, MPM strongly benefits from its robustness to outliers as shown in the following real image experiments.

Object class learning and matching

We experimented on real object class images in this section. In order to test the proposed method in the context of learning, we adopted the recent method of [START_REF] Cho | Learning graphs to match[END_REF] to learn a graph model for matching, and perform a quantitative comparison. This learning framework is particularly useful for evaluation because any graph matching algorithm can be used as a graph matching module. For the experiment, we use the publicly available dataset used in [START_REF] Cho | Learning graphs to match[END_REF], which includes annotated images on 5 object classes 3 . These dataset consists of images from Caltech-256 and PASCAL VOC2007. For each image, 10 distinctive features are annotated for the target object. We split the image set for each object class into two partitions, and report accuracy and error of matching, averaged over the 10 random splits. The scaleinvariant Hessian detector is used to detect local regions as nodes. As unary and pairwise affinity functions, we adopt the histogram-based affinity measures used in [START_REF] Cho | Learning graphs to match[END_REF].

To observe the robustness to outliers, we use a larger set of candidate matches than that of [START_REF] Cho | Learning graphs to match[END_REF]. Given a test image, we select 200 nearest neighbor features for each node of the model graph, which is four time more than that used in the original experiment. In this setting, both learning and matching become more challenging due to a larger number of distracting outliers. We compare the proposed method with SM, IPFP, and RRWM in the framework. Matching performance is evaluated without learning as well as with learning. The results for all the methods are summarized in Table 1, and some comparative examples are shown in Fig. 4. This experiment demonstrates that our approach successfully handles a large number of outliers in practical learning and matching. Interestingly, without learning, we can see significantly better performance of MPM on Face, which is relatively more rigid than other classes. In the other classes, MPM is comparable to IPFP and RRWM. With learning, however, MPM clearly outperforms others in most classes. It means that the proposed method provides better performance given an adequate graph model. Figure 5 presents a comparative example where MPM outperform the others with increasing outliers in the Face class.

Building landmark matching

The datasets used in the previous experiments deal with deformable but isomorphic objects, where one-to-one correspondences usually hold between matching features. In this experiment we evaluate flexible matching performance using the partial correspondence dataset [START_REF] Maji | Part discovery from partial correspondence[END_REF]. The dataset contains correspondence annotations for 1000 image pairs among 288 images of church buildings downloaded from Flickr. Those annotations were obtained on Amazon Mechanical Turk by asking subjects to click on pairs of matching landmark points in two instances of the category. The annotated pairs, a few examples of which are shown in Fig. 6(a), contain a variety of semantic matches on identical structural elements of buildings, and allows one-tomany or many-to-one relations among them. Finding these correspondences, which have high variability in both appearance and structure, is a challenging problem. We run each method on this dataset, and evaluate a matching performance by measuring the average recall ratio of the top k percentage matches with increasing k. Those top matches are chosen based on the confidence score obtained by each method. We use the soft-assignment value, which is not discretized, of each method as the confidence score. MPM is compared to RRWM and SM. As a baseline, we add a simple appearance-based method, dubbed UM, which only uses the similarity of SIFT descriptors without any pairwise affinity. The results are reported in Fig. 6(c). While the two other graph matching methods, RRWM and SM, show better performance than the appearance-based method, MPM outperforms all of them in recall, taking more true matches to the top ranks. As mentioned earlier, it implies that our method is robust to structural flexibility because any match with strong max-pooled support keeps a high score.

Conclusion

We proposed a novel matching method based on a maxpooling strategy within the graph matching framework. The proposed method is well suited for practical matching problems in computer vision where numerous outlier features occur from clutter. In our synthetic and real image experiments, we demonstrated its robustness to outliers and its utility in real applications. We believe the feature-pooling perspective introduced in this paper is worth further research. More theoretical understandings of our algorithm are also left for future work.

Figure 1 .

 1 Figure 1. Feature matching in the presence of outliers. (a) In real-world scenes, background clutter often produces numerous outlier features, making it hard to find correspondences. (b)We address the issue with a max-pooling approach to graph matching. The proposed method is not only resilient to deformations but also remarkably tolerant to outliers. Each node on the left image corresponds to one with the same color on the right image, where bigger nodes represent more similar nodes. (best viewed in color.)

Figure 2 .

 2 Figure 2. Feature-pooling perspective for a match (i, a). Features of a target object are shown as nodes on the left domain, and features of candidate matches, represented by nodes in the same color, are detected on the right domain. (a) Sum-pooling in Eq.(5) collects the weighted affinities of all possible matches (denoted by yellow nodes) from each neighbor j. (b) Max-pooling in Eq.(6), a candidate match (j, b) with the highest weighted affinity x ia;jb sE(eij, e ′ ab ) is selected among all possible matches as a support of j for (i, a). (c) In max-pooling, each candidate match has its own max-pooled support from all neighbors and a maxpooled score as a sum of their weighted affinities. A ⊛ x of Eq.(6) computes such max-pooled confidences for all candidate matches. (Best viewed in color.)

Figure 3 .

 3 Figure3. Comparative experiments on synthetic point sets varying the amount of outliers and deformation. To better show the effects of max-pooling, our algorithm (MPM) is compared to other recent algorithms, RRWM[START_REF] Cho | Reweighted random walks for graph matching[END_REF], IPFP[START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF], SMAC[START_REF] Cour | Balanced graph matching[END_REF], and SM[START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF]. The top row presents accuracy while the first and the second plots in the bottom row show the objective score. The third plot in the bottom represents the average computation time with increasing outliers. (a) The number of outliers nout was varied from 0 to 200 by intervals of 10 without deformation. (b) The deformation noise σ was varied from 0 to 0.2 by intervals of 0.01 without any outliers. (c) The number of outliers nout was varied with deformation σ = 0.03. Our method shows remarkable tolerance to outliers. In the aspect of deformation, our method is comparable to the best methods, IPFP and RRWM. In a realistic situation with both of deformations and outliers, shown in (c), our algorithm significantly outperforms all the other state of the arts. (Best viewed in color.)

  (a) MPM with 500, 1000, and 2000 candidate matches. (b) SM with 500, 1000, and 2000 candidate matches. (c) RRWM with 500, 1000, and 2000 candidate matches.

Figure 5 .

 5 Image matching varying the amount of outliers. For each feature on the reference image (leftmost), the best k candidate matches are selected on the input image according to the SIFT distance. From the second to the fourth column, k = 50, 100, 200 are used, respectively. More candidates involve more outliers, making the problem harder. (Best viewed in color.)

  (a) Landmark annotation examples from the dataset of [21] Ground truth MPM SM RRWM (b) Comparative matching results of different algorithms (c) Recall of true matches among top-k percentage matches.

Figure 6 .

 6 Figure 6. Matching performance on the partial correspondence dataset [21]. (a) Landmark annotations include a variety of semantic matches between flexible structures allowing one-to-many or many-to-one relations, such as windows, spires, corners, and gables. (b) Comparative results are shown for an example, where only true matches are visualized. (c) Matching performance is measured as the ratio of true matches among the top k percentage of matches. While increasing k, we compare ours to RRWM [6], SM [18], and a simple appearance-based matching (UM) as a baseline. (Best viewed in color.)

Table 1 .

 1 Performance on the object class dataset[START_REF] Cho | Learning graphs to match[END_REF]. (learn ×: results without learning; learn •: results with learning.)

		Face		Motorbike	Car		Duck	Wine bottle
	Method	learn ×	learn •	learn ×	learn •	learn ×	learn •	learn ×	learn •	learn ×	learn •
	SM [18]	20.3	35.0	28.7	51.3	30.0	46.3	31.3	46.3	54.4	65.2
	IPFP [20]	33.7	83.3	39.5	56.0	40.8	55.2	42.1	59.2	72.7	85.3
	RRWM [6]	47.1	84.1	40.7	63.7	40.3	54.8	44.7	59.3	70.8	84.4
	MPM (ours)	68.9	92.2	41.7	61.3	36.7	61.7	46.0	65.2	68.6	87.8
	Input		MPM		Input	MPM		Input		MPM
	SM	RRWM		SM	RRWM		SM	RRWM
	Figure

For the algorithms, the original implementations from the author's websites were used in all our experiments.

For the detailed information, refer to the project site: http://www. di.ens.fr/willow/research/graphlearning/

Acknowledgments. The authors would like to thank Francis Bach for helpful discussions, and Subhransu Maji for providing his data. This work was supported in part by the ERC grant VideoWorld and the Institut Universitaire de France.


Julie Rozenberg

Céline Guivarch

Robert Lempert

Stéphane Hallegatte

Nebojsa Nakicenovic

Anthony 10 Janetos

Building SSPs for climate policy analysis: a scenario elicitation methodology to map the space of possible future challenges to mitigation and adaptation

Building SSPs for climate policy analysis: a scenario elicitation methodology to map the space of possible future challenges to mitigation and adaptation

A new generation of scenarios

Most published analyses of climate change mitigation policy, and many investigating climate change impacts and adaptations, are based on long-term socioeconomic scenarios. Up to now, most analyses have used the Special Report on Emissions Scenarios (SRES, see IPCC, 2000), that describe possible world evolutions in demographic, social, economic, and technological terms, up to 2100.They assume that there are no climate change impacts and no mitigation policies, and thus have been used as "baselines" to assess the performance of adaptation and mitigation policies, and to investigate residual impacts from climate change. For instance, the costs and benefits of climate mitigation policies can be estimated by comparing the change in global mean temperature in a SRES scenario and in the same scenario in which specific climate policies are implemented (see a review in IPCC, 2007). Also, the potential impacts of climate change can be assessed by comparing a SRES scenario with the same scenario in which climate impacts are included (e.g., [START_REF] Arnell | Climate change and global water resources: SRES emissions and socio-economic scenarios[END_REF].

The scientific community is now developing a new set of scenarios (Shared Socioeconomic Pathways or SSPs) to replace the SRES [START_REF] Moss | The next generation of scenarios for climate change research and assessment[END_REF]van Vuuren et al., 2010;[START_REF] Kriegler | Socio-economic Scenario Development for Climate Change Analysis[END_REF]Arnell et al.,2011;[START_REF] O'neill | Meeting Report of the Workshop on The Nature and Use of New Socioeconomic Pathways for Climate Change Research[END_REF]. As with the earlier SRES scenarios, the new SSPs will describe different socioeconomic characteristics, different vulnerabilities, and different GHG emissions. To assist with the exploration of both adaptation and mitigation questions with the same scenarios, Arnell et al. (2011) propose to develop SSPs that are contrasted along two axes: socio-economic challenges to adaptation and socio-economic challenges to mitigation.

Using "story and simulation" methods [Garb et al., 2008], similar to those used for SRES, groups of experts would build the SSPs working collaboratively to choose a common set of qualitative storylines, informed by experts' intuition regarding the most important driving forces leading to different vulnerabilities to climate change and different abilities to mitigate (see O'Neill, 2012 for an illustration with the SSP process). Analysts would then use computer simulation models to develop quantitative projections based on these storylines.

But this process may fail to yield storylines that focus on the most important driving forces for each SSP, and avoid focusing on the less important drivers. For some driving forces, the direction of the influence can be ambiguous a priori. For instance, it is likely that climate change vulnerabilities in an urban world are different from those in a rural world; but it is difficult to guess whether one is more or less vulnerable than the other. Cities are vulnerable to floods, air pollution and heat waves while rural zones are vulnerable to drought (falling yields), famines and migration. There is an obvious difference in the nature of vulnerability but not in the magnitude of the vulnerability. Moreover, some mechanisms (feedbacks, rebound effects, etc.) might appear negligible a priori but reveal themselves to be crucial in a more careful analysis. This is why an a priori selection of the likely drivers of the capacity to mitigate and adapt appears insufficient to us, and could be completed by an analysis that validates the most important drivers a posteriori.

Furthermore, since future socioeconomic and environmental changes are highly uncertain, policies need to be tested against a variety of scenarios that cover a large range of possible futures [START_REF] Lempert | Technology Interactions Among Low-Carbon Energy Technologies: What Can We Learn From a Large Number of Scenarios?[END_REF][START_REF] Hallegatte | Strategies to adapt to an uncertain climate change[END_REF]. It would indeed be dangerous to implement a climate policy that performs well in one given scenario but completely fails in another, for instance if the population is larger or technological change slower than expected. Although the "story and simulation" process creates coherent scenarios through the storylines, it does not guarantee that the scenario outcome in terms of GDP or GHG emissions for instance will cover the uncertainty spectrum expected by users.

To address these challenges, we suggest here developing SSPs using a "backwards" approach. Our methodology is based on (i) an identification of potential drivers of challenges to mitigation and adaptation, (ii) a modeling exercise to explore the uncertainty space and select scenarios, and (iii) an a posteriori confirmation of which drivers matter and of the sign of their influence on adaptation and mitigation challenges, using statistical cluster-finding algorithms.

In recent years, several research groups have employed similar approaches, in which cluster-finding algorithms applied to databases of multiple simulation model runs are used to suggest scenarios relevant for specific policy questions with less potential ambiguity than can arise from story and simulation methods [Gerst et al., 2013;[START_REF] Groves | A New Analytic Method for Finding Policy-Relevant Scenarios[END_REF]Haasnoot et al., 2013;Hamarat et al., 2013;[START_REF] Kasprzyk | Many-Objective Robust Decision Making for Complex Environmental Systems Undergoing Change[END_REF]Robert J. Lempert et al., 2006;[START_REF] Mcjeon | Technology Interactions Among Low-Carbon Energy Technologies: What Can We Learn From a Large Number of Scenarios?[END_REF]. For example, one such "scenario discovery" analysis focused on mitigation strategies, evaluating the costs and benefits of a Renewable Energy Portfolio standard in the U.S. It found that the availability of low-cost biomass feedstock and low-cost sites for wind energy were the most important drivers for whether or not the policy produced high cost outcomes [START_REF] Schweizer | Systematic construction of global socioeconomic pathways using internally consistent element combinations[END_REF]. The concept of "backwards" analysis is similar to the "tolerable window" approach [START_REF] Petschel-Held | The Tolerable Windows Approach: Theoretical and Methodological Foundations[END_REF]) that identified policies consistent with defined guardrails for climate evolution, though the current approach can be used with any forward-running model [Lempert et. al. 2006]. The concept of defining scenarios relevant to specific decision-relevant criteria is also consistent with the Global Business Network's "strategic scenarios" approach, although we do not start with a specific decision but with the broader issue of defining scenarios that are contrasted in terms of future challenges to adaptation and mitigation, similarly to recent work on defining scenarios for climate adaptation studies [START_REF] Birkmann | Scenarios for Vulnerability, Climate Change[END_REF]. While the structural form of our model limits the results described in this paper, our approach could usefully be generalized to employ multi-model analyses [START_REF] Arnel | A framework for a new generation of socioeconomic scenarios for climate change impact, adaptation, vulnerability, and mitigation research[END_REF][START_REF] Barker | The costs of greenhouse gas mitigation with induced technological change : A meta-analysis of estimates in the literature. 4CMR[END_REF][START_REF] Peace | Insights not numbers : the appropriate use of economic models[END_REF].

To build a database of many cases in this study, we first identify potential drivers of future challenges to adaptation and mitigation and translate some of our potential drivers into different model parameters (e.g., the amount of ultimately recoverable oil resources). Other drivers cannot be accommodated in the model and are considered part of a narrative, accompanying model parameters and results (e.g. quality of governance). Combining the different states of these drivers (e.g., the amount of oil is low or large), we build a database of model runs (as in [START_REF] Rozenberg | Climate policies as a hedge against the uncertainty on future oil supply[END_REF]. We then obtain several hundreds of scenarios1 by combining the model outputs with additional external drivers that cannot be included in the model, but that are essential for an analysis on future challenges to adaptation and mitigation.

Once we have constructed the database, we distinguish the scenarios using criteria measuring future challenges to adaptation (e.g., the share of people living below the poverty line) and mitigation (e.g., baseline CO 2 emissions). The scenario discovery algorithms then identify the common characteristics (e.g., the demographic changes, the extent of globalization) that best predict the scenarios where the challenges to adaptation or mitigation are high or low. They help us select a few SSPs that are contrasted along these criteria.

For SSPs, the selected scenarios have to be sufficiently general, since they need to be applicable to a large set of research questions and decisions. Therefore, instead of starting from a specific decision, we look to find contrasted scenarios in terms of adaptation and mitigation challenges. But this "scenario elicitation" methodology can be used to build different sets of scenarios, each decision maker choosing the drivers relevant to a particular policy issue and selecting his or her own scenarios from a common database.

To summarize, we propose the following approach for developing SSPs:

(i)
We first identify a priori the main driving forces of the world future challenges to mitigation and adaptation to climate change, based on existing literature (Section 2).

(ii)

We then translate these driving forces into model parameters for a global energy-economic model, and we combine these parameters to build a large number of model runs. We also combine model outputs with external drivers (that are not included in the model) to create a large set of scenarios (Section 3).2

(iii)

We analyze the resulting database using indicators measuring future challenges to mitigation and adaptation, and we identify a posteriori the main driving forces of these future challenges. Then we select five contrasting combinations of drivers to cover the range of possible challenges to adaptation and mitigation (Section 4).

The last section discusses how this could define a new approach to the use of scenarios by the climate community. Noting that the most relevant scenarios are often crafted explicitly for specific communities facing specific climate-related decisions (European Environment Agency, 2009;[START_REF] Parson | Global-Change Scenarios: Their Development and Use, Synthesis and Assessment Product 2.1b[END_REF], this new concept envisions providing data and tools that would allow each user to construct his or her own scenarios as needed, while ensuring broad consistency among users with the underlying base of scientific knowledge. et al. (2011) propose three dimensions to explore climate change vulnerability and adaptation challenges, that are described in details in Section I of the supplementary material: (i) Globalization: a "converging" world vs. a "fragmented" world; (ii) Equity: inclusive development vs. "growth and poverty" development; and (iii) Environmental stress: an "environment-oriented" world vs. an "environmentally-stressed" world. As described in the Supplementary material, these dimensions, along with dependency on fossil fuel, also appear highly relevant to challenges to mitigation.

The a priori drivers of challenges to adaptation and mitigation

Hallegatte

The resulting four dimensions are shown in Figure 1, giving an idea of which parameters can be included in each dimension. The figure suggests that some of these parameters can be included in different dimensions (e.g., urbanization can be included in the environmental/lifestyle dimension or in the convergence dimension), showing that there will always be some flexibility and subjectivity in how our approach is applied. Note also that the literature is not the only place to look for a priori drivers of future adaptation and mitigation challenges. Other sources such as expert elicitation surveys (Schweizer and O'Neill, this issue) could also prove valuable. Nonetheless, the drivers considered here should prove more than sufficient for the illustrative purposes of this paper.

Figure 1: Identified drivers of the challenges to mitigation and adaptation, in the four main dimensions.

How to build scenarios

There are good reasons to think that these factors represent the major drivers of challenges to adaptation and to mitigation, but this is only an informed guess. Complex mechanisms, interactions, and feedbacks can act on these drivers, and a more sophisticated analysis is possible. To test whether these drivers are well chosen, we translated some of them into model parameters.

To do so, we used the IMACLIM-R model [START_REF] Rozenberg | Climate policies as a hedge against the uncertainty on future oil supply[END_REF][START_REF] Waisman | The Imaclim-R Model: Infrastructures, Technical Inertia and the Costs of Low Carbon Futures under Imperfect Foresight[END_REF] and Section II in the supplementary material), which projects the long-term evolution of the world economy and allows us to explore the uncertainty that arises from unknown exogenous trends (e.g., future population) and parameter values that are debated.

For a given model, not all drivers can be translated into input parameters. Indeed, some of the drivers are direct inputs of the IMACLIM-R model (e.g., population), some are the result of upstream hypotheses (e.g., the availability of fossil energy is the result of hypotheses on oil resources and inertia in the development of production capacities), and some are model outputs (e.g., economic structure). Note that some potential technological breakthrough such as hyper efficient micro grids or black swans like epidemics are not modelled here.

For this exercise, we selected the following drivers to be translated into input parameters of the IMACLIM-R model and consider several alternative values for these parameters to reflect uncertainty on future challenges to adaptation and mitigation:

Dimension1: Globalization

Population. We use the three UN scenarios (low, median, and high). In a next step, population data defined specifically for the SSPs could be used.

Economic structure. Even though this driver is an output of the IMACLIM-R model, we influence it by introducing three assumptions on the speed of labor productivity convergence (see III.1 in the supplementary material). This parameter influences economic growth in each region, but note that GDP growth is endogenous in IMACLIM-R.

Capital markets.

The IMACLIM-R model treats capital balances as exogenous, so we consider two assumptions about global financial imbalances reduction: In the first assumption financial imbalances are phased out exponentially in two decades, whereas in the second assumption they remain constant for the whole simulation period.

Dimension2: Environmental stress

Energy sobriety. We make two assumptions (i.e. two groups of hypotheses affecting many different variables) regarding energy sobriety:

-Development patterns: We introduce two assumptions on the evolution of households' preferences (environmentally-inclined or energy-intensive) in transportation and housing (evolution of the number of cars per capita, maximum dwelling surface per capita in developing countries) as well as on the saturation level of households' industrial goods consumption (see III.2 in the supplementary material). -Production choices: We introduce two alternatives on the freight content of economic growth through alternative evolutions of the input-output coefficient representing the transportation requirement per unit of good produced (see III.2 in the supplementary material). -Induced energy efficiency: Even though energy efficiency is driven by energy prices, we introduce two alternatives for the parameters describing its maximum annual improvement in the leading country and the catch-up speed of the others (see III.2 in the supplementary material).

Dimension3: Carbon supply

Availability of fossil energy. We introduce two assumptions about oil resources (parameters include the amount of ultimately recoverable resources, inertia in the deployment of non conventional oil, the maximum growth rate of Middle-East production capacities), the gas price indexation on the oil price, and the elasticities of coal price growth to demand changes (see III.3 in the supplementary material). Each of these variables can take two different values depending on the assumption.

Availability of low-carbon technologies.

We build two assumptions for parameters describing the market penetration of nuclear energy, renewable resources, carbon capture and storage, and electric vehicles. These parameters include learning rates and maximum market shares throughout the simulation period. (More details are given for each technology in III.3 in the supplementary material.)

Dimension4: Equity

Dimension 4 has to be treated differently, because IMACLIM-R in its current form cannot include its drivers (inequality within countries). Since the model is based on a representative consumer-worker, it cannot take into account income distribution among consumers-workers. Considering the importance of this driver, it cannot be disregarded. We thus introduce it through an external driver, i.e. that is not included in the model and does not modify the model outputs, but adds numerical information to the model results to build a scenario.

In the current case, therefore, we add to the model outputs quantitative information on "equity." Some of the scenarios are built assuming a global reduction of within-country inequality (an "inclusive growth" set of scenarios), in which the share of income of the 20% poorest in countries increases by 33% by 2090 (e.g., in a country where the 20% poorest receive an income corresponding to 6% of total GDP in 2010, this share increases to 8% in 2090). Others are built assuming a global increase in within-country inequality, with a share of income of the 20% poorest that decreases by 33% by 2090.

To the model outputs, therefore, we add an additional variable, namely the income of the 20% poorest, which is built from model outputs (GDP per capita in less developed countries) and from this external driver.

The result is a set of 286 scenarios3 (see Figure 2 below and Figure 1 in the supplementary material), each being the combination of (1) a set of model parameters describing the drivers, (2) a model run with these parameters, and (3) additional quantitative and qualitative information that cannot be accommodated in the model but are relevant for challenges to adaptation and mitigation (e.g., in our case, inequalities within countries).

Figure 2: GDP per capita of the 20% poorest in a selection of developing countries in 286 scenarios resulting from 143 model runs with IMACLIM-R and two hypotheses on the share of income of the 20% poorest

How to select relevant scenarios

To select scenarios that cover challenges to mitigation and adaptation, the first step is to define indicators for these challenges. This is a very important and difficult endeavor. Much work has been devoted to this task, but there is little agreement on how to proceed. Taking the example of the challenges to adaptation, [START_REF] Füssel | Review and quantitative analysis of indices of climate change exposure, adaptive capacity, sensitivity, and impacts[END_REF] reviews the many indicators that have been proposed and shows that they lead to very different prescriptions and vulnerability hot spots. Also, he shows that vulnerability and adaptive capacity cannot be identified in isolation from political considerations and value and ethical judgments. Our analysis is thus developed and illustrated using very simple indicators (two for mitigation and two for adaptation), taking into account the fact that more work on this issue needs to be done, and that the methodology needs to be able to accommodate a fairly large set of indicators.

For mitigation, we chose baseline CO 2 emissions as an indicator. We are well aware that this measure does not include all components of the challenges to mitigation. For instance, good governance and reduced inequalities are likely to make it easier to implement mitigation policies, regardless of CO 2 emissions. But as a first-step analysis, we use this indicator. In a second step, we use the GDP losses from a mitigation policy implemented to stabilize radiative forcing at a given level.

For adaptation, no natural indicator is available. Still well aware of the limits, we decided to use the income of the 20% poorest in a selection of developing countries (African countries, India, South America [except Brazil] and South East Asia). Of course, this is a very partial indicator, and it is well known that challenges to adaptation will depend on many other factors, such as governance and technologies (see the review in the supplementary material and in [START_REF] Hallegatte | Building world narratives for climate change impact, adaptation and vulnerability analyses[END_REF]. In the current analysis, we use this simple indicator only to illustrate our methodology and make a first proposal for SSPs. In a second step, we use the share of jobs in agriculture in developing countries. We next normalize our two indicators (the sum of global emissions over the 2011-2090 period for challenges to mitigation and the discounted income of the 20% poorest in developing countries, over the same period, for challenges to adaptation) and map our 286 scenarios over the resulting space. As shown in Figure 3, the scenarios span most combinations of challenges to mitigation and adaptation as defined by these indicators. We then define five regions in this space that correspond to the five SSPs.

In the selection of SSP spaces, we emphasize contrast, i.e., on having scenarios with different challenges to mitigation and adaptation. We do not focus on the "probability" of these scenarios. The "plausibility" is supposed to be ensured in the first phase of this analysis, when the determinants have been chosen and transformed into model parameters. We do not want to focus on probabilities because the ability to assess them appears out of reach and because focusing on the most likely scenarios would lead to disregarding low-probability high-impact scenarios, which might be the most relevant in a risk-management approach. Since we think that the analysis of climate policies is an analysis of climate risks more than anything else, the inclusion of low-probability scenarios in SSPs appears essential.

To select the five SSP boxes, we choose numerical thresholds for the challenges to mitigation and adaptation indicators that characterize each SSP. Here we choose the two thresholds so that one-third of the scenarios lie below the first and one-third lie above the second (see Figure 3). This choice results in a significant number of scenarios in each SSP region. One could, however, set thresholds independently of the scenarios distribution, for instance by requiring that all SSP regions have the same area. As described below, we find that in this particular example our results are relatively insensitive to the choice of thresholds. More generally, the choice of threshold might usefully be assisted by approaches such as the hierarchical cluster methods used by Gerst et. al. [2013].

Having chosen thresholds to define the SSP regions, we can then use a "scenario discovery" cluster analysis to identify the main drivers of each scenario group. "Scenario discovery," often used to support robust decision making (Robert [START_REF] Lempert | Managing Climate Risks in Developing Countries with Robust Decision MakingRep[END_REF][START_REF] Lempert | Shaping the Next One Hundred Years : New Methods for Quantitative, Long-term Policy Analysis[END_REF], provides a computer-assisted method of scenario development that applies statistical or data-mining algorithms to databases of simulation model results to characterize the combinations of uncertain inputs parameter values most predictive of specified classes of results. Importantly, scenario discovery also suggests which uncertain input parameters have less influence. We apply a modified version of the PRIM (Patient Rule Induction Method) [START_REF] Friedman | Bump Hunting in High-Dimensional Data[END_REF] to the 286 scenarios spanning the range of adaptation and mitigation indicators shown in Figure 3. A variety of classification algorithms have been used for scenario discovery. PRIM often proves useful in this context because it facilitates users' ability to trade between the accuracy of the scenario descriptions and their interpretability, that is, the ease with which decision makers can understand the information contained in the scenarios (see for example, the comparison between PRIM and the Classification and Regression Tree (CART) algorithm in Bryant, Lempert, and Bankes [2008]).

An SSP is defined by a range of values for the adaptation and mitigation indicators. PRIM seeks a set of drivers that maximize the matching between those drivers and the model scenarios that have the indicator values associated with each SSP. For instance, for SSP5, we want to find the drivers such that a scenario with these drivers has a high likelihood of being in the upper-left-hand corner of Fig 5

and such that a scenario is in the upper-left-hand corner has a high likelihood of having these drivers.

To measure this match, we use three criteria (see [START_REF] Bryant | Thinking inside the box: A Participatory, computer-assisted approach to scenario discovery[END_REF]. Coverage is the fraction of scenarios consistent with the indicators (e.g. that lie in the SSP5 corner of Fig 5) that are also consistent with the drivers. Density is the fraction of all scenarios consistent with the drivers that are also consistent with the indicators. 4 Interpretability represents that ability of decision makers to understand the information by the combinations of drivers and is measured by having a small number of drivers.

Since these three measures are generally in tension with one another, PRIM provides the user a set of options representing different tradeoffs among density, coverage, and interpretability.

Table 1 shows our results. Each row shows an SSP and the middle eight columns list its potential drivers. A cell filled with black text indicates that a driver plays a significant role in that SSP whereas grey italics text indicates that the driver plays a partial role. We distinguish the former from the latter using the resampling test described in [START_REF] Bryant | Thinking inside the box: A Participatory, computer-assisted approach to scenario discovery[END_REF]. This test runs PRIM on multiple subsamples of the original dataset and notes the fraction of subsamples for which each parameter emerges as an important driver of the scenario definition. We consider a driver that scores greater than 50% in the test as significant and less significant otherwise.

The final column shows the explanatory power of these combinations of drivers, as measured by their coverage and density (rounded at 5%). For instance, the SSP4 row shows that low equity, slow convergence, and high energy sobriety contribute most significantly to SSP4 while medium or low population plays a partial role. The last column says that ninety percent of the cases in the region of Figure 3 noted as SSP4 meet these conditions (coverage) and ninety percent of the cases that meet these conditions are SSP4 (density).

Some drivers, such as equity, contribute strongly to all the SSPs. Indeed, this driver has a direct impact on the challenges to adaptation axis, since it was used to calculate the indicator (see Section 4); this driver splits the income of the 20% poorest into two groups, with a compression to the right as GDP per capita decreases. In the same way, the "energy sobriety" driver has a strong impact on challenges to mitigation, since it directly influences CO 2 emissions in the baseline. It also influences the challenges to adaptation because energy sobriety leads to higher GDP, i.e. to less poverty.5

The impact of population on the indicators is ambiguous and not always significant. Although one might think that a higher population would reduce GDP per capita in a world with finite resources, a higher population growth rate implies higher potential economic growth in the model, so that challenges to adaptation might decrease. Moreover, higher economic growth accelerates capital turnover and increases the share of low-carbon technologies, thus decreasing challenges to mitigation.

The results show, however, that a high population is inconsistent with SSP1 and that a low population is inconsistent with SSP3.

Other drivers, such as fossil fuel availability and capital markets, contribute to few if any SSPs. The non-significant impact of fossil fuel availability is due to two contradictory effects: on the one hand, a constrained oil supply induces substitution toward coal, which emits more CO 2 for the same energy service. On the other hand, it also induces higher energy prices, which trigger faster energy efficiency.

In the same way, low-carbon technologies contribute to only one SSP because they tend to slow down energy efficiency through lower energy prices, which lessens their effect on carbon emissions.

An interesting result of this analysis is the difficulty in finding scenarios corresponding to SSP5 (i.e., scenarios with both high baseline emissions and high GDP growth). Indeed, to include one-third of all scenarios above the first threshold for adaptation challenges, we had to define it at a high value, around 0.6 (see Figure 3). As already mentioned, GDP growth is affected by energy consumption and sobriety. If energy consumption is too high -and energy efficiency too low -energy prices are so high than GDP growth is significantly reduced, especially in developing countries. This explains why there are few scenarios with high economic growth and high baseline emissions. This result however depends on the indicator considered, and taking a different indicator for challenges to mitigation helps finding SSP5 scenarios (see section III in the supplementary material).

Another conclusion of the analysis is the difficulty to define a unique SSP 2. Indeed, coverage only reaches 45%, which means that 55% of the scenarios identified as potential SSP2 in Figure 3 corresponds to other drivers than those identified in Table 1. In other terms, there are other sets of drivers that could lead to scenarios with medium challenges to adaptation and mitigation. This quantitative result is consistent with discussions in the Boulder meeting in November 2011 [START_REF] O'neill | Meeting Report of the Workshop on The Nature and Use of New Socioeconomic Pathways for Climate Change Research[END_REF] and the proposition to have several versions of SSP2.

Table 1: Combinations of future challenges to adaptation and mitigation in our five SSP spaces as identified by the scenario discovery analysis described in the text. Black/grey italics text indicates more/less important drivers. Coverage and density (rounded) measure the explanatory power of the drivers for each SSP.

Eventually, this representation allows testing the ex-post relevance of our drivers on our indicators.

The hypotheses that we made about financial markets and the future reduction of imbalances are not a posteriori main drivers of the world challenges to adaptation and mitigation, except for SSP5. These results must be moderated, however, because they depend significantly on the choice of indicators and on the delimitation of the SSP spaces.

As an illustration, we repeat the analysis using a different set of indicators. As an indicator of future challenges to mitigation, we calculate the GDP losses from a mitigation policy reducing emissions to stabilize radiative forcing at a given level (we retain a target at 3.7 Wm -2 ). For adaptation challenges, we use the share of jobs in agriculture in developing countries.

The results of this second analysis share some similarities with those of the first one (see Table SP4 in the supplementary material); for example, convergence is slow for SSP4 and fast for SSP5; energy sobriety is high for SSP1 and low for SSPs 3 and 5. But significant differences can also be noted. For instance, low-carbon technologies become significant in SSPs 1, 3, 4 and 5. This is due to the mitigation challenges indicator (i.e., the cost of a mitigation policy): low-carbon technologies help meet the climate objective at a lower cost without slowing down energy efficiency, which is triggered by the carbon tax in all scenarios. In this second analysis, capital markets are significant in three SSPs because they have an impact on the adaptation challenges indicator: a reduction of financial imbalances (as in SSP1 for instance) induces developing countries to invest more locally. This accelerates structural change and reduces the share of jobs in agriculture.

The similarities and differences in these two analyses, with different criteria for challenges to mitigation and adaptation, constitute a first indication of the robust results for SSPs development. To go further, we consider only scenarios that are in the same SSP domain for both sets of indicators. For each SSP domain, only about ten scenarios are stable to a change of indicators, and they have a few drivers in common: -SSP1 (11 scenarios): these scenarios are characterized by a high availability of low-carbon technologies, energy-sober behaviors and a reduction in financial imbalances. -SSP2 (5 scenarios): there is no common characteristic to those scenarios. -SSP3 (7 scenarios): these scenarios are the exact opposite of the SSP1 scenarios, and are characterized by a low availability of low-carbon technologies, energy-intensive behaviors and maintained financial imbalances. -SSP4 (11 scenarios): these scenarios are characterized by low equity, low convergence and maintained financial imbalances. -SSP5 (10 scenarios): these scenarios all have a high convergence, nine of them have a low availability of low carbon technologies and nine of them have reduced financial imbalances.

These results confirm that it is difficult to find a unique set of drivers defining SSP2; this intermediate scenario can be represented by very different futures. They also show that the relevant set of drivers depend on which SSP is considered. Interestingly, SSP1 and SSP3 are defined by the same set of drivers -but with opposite values -that mainly describes the energy system (technologies and energy intensity). Conversely, SSP4 and SSP5 are characterized by assumptions on socio-economic aspects, and particularly equity and economic convergence.

To test sensitivity to the choice of threshold for the SSP regions, we repeated the analysis a third time using same-sized SSP domains with a diamond-shaped domain corresponding to SSP26 (Fig. SP4 and Table SP5 in Supplementary Material). As the new domains include all scenarios, the number of explanatory drivers is lower than in the first analysis, and since the domains are moved to the left compared to the distribution, the equity driver is no longer significant for SSP3 and SSP4. The results however share similarities with those of the first one, in particular for SSP1 and SSP5 that have three constant drivers. The only contradictory result is for SSP2: improved equity was a significant driver in the first analysis while worsen equity is now significant. Note that here again, coverage is bad (45%) for SSP2, which confirms that it is very difficult finding a storyline for this SSP.

This analysis remains preliminary and the robustness of its results would be increased by the inclusion of additional driver values, additional drivers, alternative selection criteria, and more models. In particular, combining different models with different designs would be key to improve our confidence in the SSP determinants, because it would help assess the uncertainties surrounding the model structures. Indeed, the coherence that we find for a certain set of drivers depends on modelling choices and might be called into question by other models.

Conclusion and further challenges

A central goal of scenario exercises is to inform the development of robust strategies, that is, strategies that perform better than the alternatives over a wide range of plausible future states of the world. When this process is successful, it can be surprising that uncertain factors do not affect the relative performance of a robust strategy.

Such context dependence of the most important scenarios for decision making presents both an opportunity and a challenge for the choice of socioeconomic scenarios. The opportunity is that it provides a clear definition of the most policy-relevant scenarios -those that most directly inform the tradeoffs among strategies. But it also suggests the need for different sets of scenarios for different decisions.

But as a first step, we propose in this paper an illustration of how this methodology could be applied to define a first set of SSPs, appropriate for a broad range of decisions concerning climate policies, including mitigation and adaptation. We show that this approach allows for the development of five baseline SSPs that have very different challenges to adaptation and mitigation (at least according to the very simple indicators we used in this study).

Most importantly, the development of SSPs will not be a one-shot exercise. Instead, it will be a continuous process of refinement. The methodology that is proposed here could be applied to an increasingly large set of scenarios produced using different methods and models. The methodology would indeed be particularly relevant if a large number of diversified models are used to construct the scenario database in which SSPs are selected. Also, it would be particularly useful to develop a large set of selection criteria, which could be used to select SSPs that are particularly adapted to a specific problem.

Over the long term, one can imagine a large multi-model scenario database and a diversity of selection criteria that can be used to identify which scenarios are most relevant for a given category of decisions.

A web-based tool could then be proposed to allow decision makers to select the few scenarios that they need to consider in their decision making process. Such a tool would benefit from the multiplicity of models available in the literature. It would also avoid the difficult selection of a few marker scenarios, which will inevitably oversimplify the reality and result in the discarding of a lot of useful information.

Figure 3 :

 3 Figure 3: Capacities to adapt and to mitigate that define the five SSP spaces and the results of our 286 model runs arrayed in this space.

Note that there is no consensus of the terminology used in scenario analysis. Here, we label each of our model runs a "scenario." The Robust Decision-Making tradition (e.g.,Lempert and Groves,

2010) labels these runs "cases" and considers a "scenario" as a set of "case" particularly relevant to the analysis of a given decision.

The scenario discovery literature generally refers to the entries in the database of model results as cases. Here we use the term scenarios because we have added to the database entries information associated with narratives in addition to the results of model runs.

Combining all assumptions creates 288 model runs, but one baseline did not run until the end of the simulation period. Thus, two scenarios are excluded from the database (derived from this model run and the two hypotheses on equity).

Coverage is analogous to "sensitivity" or "recall" in the classification and information retrieval literatures. Density is analogous to "precision" or "positive predictive value" in those literatures.

The "energy sobriety" driver contains hypotheses on behaviors, localization choices, and the potential for energy efficiency (energy efficiency is endogenous and driven by energy prices). In scenarios with high energy sobriety, energy prices are lower, accelerating GDP growth. This result warns against the use of exogenous GDP scenarios, developed independently from natural resources and energy modeling.

We credit the idea for a diamond-shaped domain corresponding to SSP2 to Jae Edmonds of the GCAM modelling group at the Joint Global Change Research Institute.