François-Xavier Dupé
email: francois-xavier.dupe@univ-amu.fr

Rohit Yadav
email: rohit.yadav@univ-amu.fr

Guillaume Auzias
email: guillaume.auzias@univ-amu.fr

Sylvain Takerkart
email: sylvain.takerkart@univ-amu.fr

Emtiyaz Khan

Mehmet Gönen

X Dupé

Kernelized multi-graph matching

Keywords: graph matching, kernel, multi-graph matching, non-convex optimization

published or not. The documents may come

Introduction & Related work

Graph matching is general problem with many applications such as e.g. object recognition and registration, or shape matching to cite a few. Let G 1 and G 2 be two graphs with respectively n 1 and n 2 vertices. The pairwise matching problem is often cast as a quadratic assignment problem (QAP), using the Lawler's formula [START_REF] Lawler | The quadratic assignment problem[END_REF], max X∈Pn 1 ,n 2 vec(X) T K e vec(X) + tr(K v X) ,

(1) with P n 1 ,n 2 the set of permutation matrix of size n 1 × n 2 , K v ∈ R n 1 ×n 2 the vertex affinity matrix and K e ∈ R n 1 n 2 ×n 1 n 2 the edge affinity matrix. These affinity matrices can be built using kernels, then K v and K e are both Gram matrix build using respectively a vertex kernel and an edge kernel [START_REF] Zhang | KerGM: kernelized graph matching[END_REF].

As K e could be a very large matrix, usually the Koopmans-Beckmann's QAP [START_REF] Tjalling | Assignment problems and the location of economic activities[END_REF]

is preferred, max X∈Pn 1 ,n 2 tr(XA 1 XA 2 ) + tr(K v X) , (2)
with A 1 and A 2 respectively the adjacency matrices of G 1 and G 2 . ( 2) is a special case of Lawler's QAP with K e = A 1 ⊗ A 2 (the Kronecker product between the two adjacency matrices).

Recently, [START_REF] Zhang | KerGM: kernelized graph matching[END_REF] showed that by using specific kernels for computing the edge affinity matrix, (1) has a more memory manageable writing. Furthermore, their formulation with kernels allows to match a large diversity of graphs, as kernels can easily manage labels or vectors of attributes. They also propose a regularization scheme combined with a Frank-Wolfe optimization leading to very good performances compared to state of the art methods and good robustness to noise both on attributes and structure.

Multigraph matching is an extension of the graph matching problem, where one aims at matching several graphs at once while enforcing coherence between the vertex assignments. In order to enforce the coherence, the idea is to search for a cycle consistency [START_REF] Pachauri | Solving the multi-way matching problem by permutation synchronization[END_REF] between the permutation matrices, i.e. if X i,j is the permutation matrix between graphs i and j, for a graph k we have X i,j ≈ X i,k X k,j . It is an approximation since the graphs may not have the same number of vertices. [START_REF] Pachauri | Solving the multi-way matching problem by permutation synchronization[END_REF] showed that the cycle consistency property is equivalent to projecting the vertices into a discrete space. A matching between two vertices means that they have the same image in this space. The dimension of this space is directly linked to the diversity of the vertices in the set of graphs. This diversity reflects the attributes and/or labels that are defined on the vertices. Recent methods like MatchALS [START_REF] Zhou | Multi-image matching via fast alternating minimization[END_REF] implicitly use it by minimizing the rank the bulk permutation matrix. Some others such as HiPPI [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF] and GA-MGM (Wang et al., 2020a) directly run the optimization in the universe of vertex. On the other side CAO [START_REF] Yan | Multigraph matching via affinity optimization with graduated consistency regularization[END_REF] and Floyd [START_REF] Jiang | Unifying offline and online multi-graph matching via finding shortest paths on supergraph[END_REF] optimize both affinity and the cycle consistency using a graduated scheme. MLRWM-multi [START_REF] Park | Multi-attributed graph matching with multi-layer random walks[END_REF], a multigraph extension of RRWM [START_REF] Cho | Reweighted random walks for graph matching[END_REF] is based on a multi-layer approach to ensure vertex consistency. Most of these methods relies on non-convex optimization as convex relaxation is not trivial [START_REF] Fogel | Aspremont. Convex relaxations for permutation problems[END_REF][START_REF] Swoboda | A convex relaxation for multi-graph matching[END_REF] and may lead to inappropriate solutions in some cases [START_REF] Aflalo | On convex relaxation of graph isomorphism[END_REF][START_REF] Lyzinski | Graph matching: Relax at your own risk[END_REF]. While there is now many works using deep learning methods [START_REF] Fey | Deep graph matching consensus[END_REF]Wang et al., 2020b;[START_REF] Rolínek | Deep graph matching via blackbox differentiation of combinatorial solvers[END_REF][START_REF] Wang | Neural graph matching network: Learning Lawler's quadratic assignment problem with extension to hypergraph and multiplegraph matching[END_REF]Liu et al., 2021b) for graph matching only a few tackle the multi-graph matching problem.

In this paper we focus on the unsupervised version of the multigraph matching problem that is faced in the many applications where no ground truth labeling is available. We propose an extended version of the framework proposed for KerGM [START_REF] Zhang | KerGM: kernelized graph matching[END_REF] for multigraph matching with an appropriate projection to fulfill the constraints. The induced optimization problem is solved using recent non-convex optimization scheme which guarantees convergence under mild condition. Results on classic data set show promising results compared to other state-of-art unsupervised methods.

Our main contributions are:

• An unsupervised multigraph matching method based on Lawler's QAP which allows kernel over both edge and vertex attributes while keeping a tractable computer memory load.

• A flexible algorithm which allows a set of projection power to find cycle consistent permutation matrices.

• Experiments on real data-sets demonstrating that our approach is competitive with state-of-art results.

Preliminaries about array operations and multi-graph matching

Let {G i } i=1...n be a set of n graphs with ∀i,

G i = {V i , E i ⊆ V i × V i , L v , L e }, i.
e. a graph is defined by a set of vertices, a set of edges and two functions: L v : V → R dv which gives the data vector associated to a vertex and L e : E → R de which gives the data vector associated to an edge. We also define I m as the identity matrix of size m and 1 m the vector of 1 of size m. For a matrix X ∈ R n×n , we denote for i, j ∈ {1, . . . , n} by X[i, j] the scalar at line i and column j, and by X[:, j] we denote the vector form by column j (and reciprocally for lines). First we introduce the notion of array operations in Hilbert space, these tools will be useful to factorize (1) the edge affinity matrices.

Array operations in Hilbert space

We propose a rapid and simplified introduction to H-operations arrays in Hilbert spaces presented in [START_REF] Zhang | KerGM: kernelized graph matching[END_REF]. Let Φ, Ψ ∈ R d×m×m be 3d-arrays (or 3d-matrices). For Φ ∈ R d×m×m , we denote by Φ[l, i, j] ∈ R the scalar at coordinates l, i, j and by Φ[:, i, j] ∈ R d the vector at the coordinates i, j. ∀X ∈ R m×m we define the following operations, 1. Φ T ∈ R d×m×m with ∀i, j, Φ[:, i, j] = Φ[:, j, i] (i.e. the transpose operation along the two last axis).

2. Φ * Ψ ∈ R m×m where ∀i, j,

[Φ * Ψ][i, j] = m k=1 Φ[:, i, k], Ψ[:, k, j] = m k=1 d l=1 Φ[l, i, k]Ψ[l, k, j] . 3. ∀X ∈ R d×m×m , Φ X ∈ R m×m where ∀i, j, [Φ X][i, j] = m k=1 Φ[:, i, k]X[k, j] = m k=1 X[k, j]Φ[:, i, k] .
Similarly, we define X Φ ∈ R m×m where, ∀i, j,

[X Φ][i, j] = m k=1 X[i, k]Φ[:, k, j] .
The last operator can be read as a parallelized matrix product over the first axis. We recap several results from [START_REF] Zhang | KerGM: kernelized graph matching[END_REF] with the following proposition, Proposition 1 [START_REF] Zhang | KerGM: kernelized graph matching[END_REF]) Define the function ., . : R d×m×m × R d×m×m → R such that ∀Φ, Ψ ∈ R d×m×m , Φ, Ψ = tr(Φ T * Ψ). Then ., . is a inner product on R d×m×m and the following equalities are true,

• Let Φ, Ψ ∈ R d×m×m , we have ∀X ∈ R m×m , Φ X, Ψ = Φ, Ψ X T and X Φ, Ψ = Φ, X T Ψ . • ∀X, Y ∈ R m×m , Φ ∈ R d×m×m , we have, Φ X Y = Φ (XY ), and Y (X Φ) = (Y X) Φ . • Let Φ, Ψ ∈ R d×m×m , we have ∀X ∈ R m×m , Φ, Ψ X = Ψ T * Φ, X and Φ, X Ψ = Φ * Ψ T , X .

Building the optimization problem

We assume that the graphs have the same number of vertices m > 0, we add dummy vertices if necessary. We define the constraints on cycle consistency in Definition 2.

Definition 2 (Cycle-consistency [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF])

Let X = {X i,j ∈ P m,m } n i,j=1
be the set of pairwise matchings in a collection of n objects, where each X i,j is an element of the set of partial permutation matrices 1 ,

P m,q = {X ∈ {0, 1} m×q : X1 q ≤ 1 m , X T 1 m ≤ 1 q } . (3)
The set X is said to be cycle-consistent if for all i, j, l ∈ {1, . . . , k} it holds that: (i) X i,i = I m (identity matching), (ii) X i,j = X T j,i (symmetry), and (iii) X i,j X j,l ≤ X i,l (transitivity).

The inequalities in this definition allows graphs of different sizes. From Definition 2, [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF] formalized the links with the universe of vertices with the following lemma, Lemma 3 (Cycle-consistency, universe points [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF])) The set X of pairwise matchings is cycle-consistent, if there exists a collection of rank r {X l ∈ P m,r :

X l 1 r = 1 m } n l=1 , such that for each X i,j ∈ X it holds that X i,j = X i X T j .
Notice that the universe of vertices can be seen as a discrete embedding space for vertices. From Lemma 3 and using matrix factorization, we build our constraint set as follows,

C r = {X ∈ R nm×nm : X i,i = I m , X i,j = X T j,i = X i X T j with X i ∈ P m,r } . (4)
This formulation implies that X ∈ C r is of rank r.

Let K v ∈ R mn×mn be the full vertex affinity matrix built using a kernel on vertices where each block K v i,j ∈ R m×m is the Gram matrix of a vertex kernel applied on the data vectors (through L v ) on vertices of G i and G j . Let K e ∈ R mn 2 ×mn 2 be the full edge affinity matrix built using a kernel on edges. Using the Lawler's QAP, we aim to solve, max X∈Cr vec(X) T K e vec(X) + tr(K v X) .

(5)

1. All inequalities are element-wise.

KMGM

Proposed approach

The limitation with ( 5) is the size of K e which may be very large. In order to address this limitation, we use the framework proposed in Section 2.1 (following the ideas from Zhang et al. ( 2019)) to rewrite K e by factorizing it using a array Φ such that,

vec(X) T K e vec(X) = Φ X, X Φ . ( 6
)
To build Φ, we need to define it for each graph. For graph G k , let Φ d×m×m k be defined as follows,

Φ k [i, j] = L e (v i , v j ) = φ i,j ∈ R d if (v i , v j ) ∈ E k , 0 otherwise . ( 7
)
φ i,j is the data vector on the edge (v i , v j ). There many way to build these vectors, for example Gaussian kernels can be approximated using Random Fourier Features [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF] (see also (Liu et al., 2021a) for other kernel approximations). Then Φ ∈ R d×nm×nm is given by the 3d-array with the Φ k on the diagonal,

Φ =    Φ 1 0 Φ 2 0 . . .    (8)
This formulation has the advantage to be more compact than manipulating the full edge affinity matrix, since the size of Φ is d × nm × nm compare to (nm) 2 × (nm) 2 for K e . Then we reformulate (5) as

max X∈Cr J(X) = Φ X, X Φ + tr(K v X) . (9)
This optimization problem is non-convex because of the two constraints (rank and permutation), we need then a dedicated scheme to solve it.

Optimization scheme

Since ( 9) is a quadratic optimization problem with non-convex constraints, we use a power optimization scheme. This scheme has the advantages to have almost no hyper-parameters and show rather fast convergence rate and the non-convex constraints are deal with a projector which gives an approximate solution. First we need the gradient of the objective function in (9).

Proposition 4 The gradient of J in (9) at X is,

∇J(X) = K v + (Φ X) * Φ T + Φ T * (X Φ) . ( 10
) Proof Let J = J 1 +J 2 with J 1 (X) = Φ X, X Φ and J 2 (X) = tr(K v X)
. By definition of the gradient we have,

∇J 1 (X), E = lim t→0 1 t (J 1 (X + tE) -J 1 (X)) .
Using Proposition 1 we have,

J 1 (X + tE) = Φ (X + tE), (X + tE) Φ , = Φ X + tΦ E, X Φ + tE Φ , = Φ X, X Φ + t Φ E, X Φ + tE Φ , = Φ X, X Φ + t Φ X, E Φ + t Φ E, X Φ + t 2 Φ E, E Φ .
From the gradient definition we yield, E .

∇J 1 (X), E = Φ X, E Φ + Φ E, X Φ , = (Φ X) * Φ T + Φ T * (X Φ),
By identification we have ∇J 1 (X) = (Φ X) * Φ T + Φ T * (X Φ). As the gradient of J 2 (X) = tr(K v X) is ∇J 2 (X) = K v , we produce (10).
With the gradient we can solve (9) using a power method scheme. The full method is described in Algorithm 1. Since the gradient is a proxy for the quadratic operator, this scheme is closely related to HiPPI [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF]. Assuming that we are able to solve the projection step, the scheme converges to a stationary point.

Proposition 5 Algorithm 1 produces a monotone sequence and converges to a stationary point in a finite number of steps.

Proof This proof relies on the same arguments as for HiPPI [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF] for its Proposition 3. Let U = conv(C r ) (the convex hull of the constraint set). We can relax (9) in max

X∈U Φ X, X Φ + tr(K v X) = max X∈U vec(X) T K e vec(X) + tr(K v X), ≡ min X∈R nm×mn ı U (X) -vec(X) T Kvec(X) h(X) , (11)
with ı U the convex indicator function of set U (i.e. it return 0 for element from U and +∞ otherwise) and K the matrix compound of K e with the addition of vec(K v ) on the diagonal. Since ( 11) is a difference of two convex functions we can apply difference of convex (DC) programming updates rules (Le Thi and Pham Dinh, 2018) with an initial step X 0 ,

V t = ∇ X h(X) = 2 unvec( Kvec(X t )) , X t+1 = argmin X∈R nm×nm ı U (X) -h(X t ) -X -X t , V t , = argmin X∈U -X, V t ,
where unvec is the inverse of vec. U is linked with the Birkhoff polytope with the permutation matrix as extreme points [START_REF] Maciel | A global solution to sparse correspondence problems[END_REF][START_REF] Birdal | Probabilistic permutation synchronization using the Riemannian structure of the Birkhoff polytope[END_REF]. Since the maximum of the linear objective over a compact set is attained at its extreme points, we get,

X t+1 = argmin X∈U -X, V t , = argmin X∈U V t -X 2 F = proj Cr (V t ) ,
where X, X = nm since X is formed from permutation matrices. Then we get from DC programming property that the sequence {X t } T t=0 is a increasing sequence for J in (9). Since C r is a finite set, J is bounded above for any X ∈ C r . Furthermore as ∀t > 0, X t ∈ C r , the increasing sequence {X t } T t=0 converges to a stationary point.

Algorithm 1: Power method for solving (9) Input : Affinity vertices matrix K v , edges' data 3d-array Φ, tolerance τ , maximal number of iterations T , rank r. Output : X T the bulk permutation matrix.

X 0 ← 0; for t ← 1 to T do Xt ← ∇J(X t ); // Using Proposition 4 X t+1 ← proj Cr ( Xt ); if X t+1 -X t < τ then break; end t ← t + 1; end
Complexity of Algorithm 1: The computational complexity of the algorithm mainly depends on both the computation of the gradient and the projection onto the set of permutations. Since we are dealing with 3d-arrays of size d × m × n the complexity of both * and operations is O(d(nm) 2 ). The complexity of the permutation depends on the selected approach to solve the optimization. We discuss this point in the next section.

Initialization: As many non-convex methods our method is sensitive to the initialization. For example methods like HiPPI [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF] or GA-MGM (Wang et al., 2020a) cannot start with an uniformly valued matrix. Since they are working in the universe of vertices, the initialization impacts the projection step and a method like the Hungarian method will just put the vertex in order (i.e. the vertex 1 will match other vertex 1 and so on). The algorithm ends-up being stuck in a solution where the permutation matrices are simply the identity. To avoid such an issue, GA-MGM for example, uses a random initialization, leading to a non deterministic optimization method. For our method such initialization is less a problem. If we initialize with the null matrix, the algorithm will only use the vertex affinity matrix to recover the permutations. Such initialization is relevant if the affinity is correctly tuned and it makes our method deterministic.

Comparison with closely related methods: While our method is not the first multi-graph method to include edge attributes, it is the first to propose a tractable way of dealing with real-world data. For example, methods like Floyd [START_REF] Jiang | Unifying offline and online multi-graph matching via finding shortest paths on supergraph[END_REF] or deep learning methods like NGM [START_REF] Wang | Neural graph matching network: Learning Lawler's quadratic assignment problem with extension to hypergraph and multiplegraph matching[END_REF] directly work with Lawler's QAP (1). This leads to manipulate matrices whose size are quadratic in the number of vertices, so they only consider pairwise matching for most set of graphs. In comparison, with the arrays, we are able to manipulate matrices whose sizes linearly depends on the number of vertices. The cycle consistency constraints can then consider the full set of graphs.

Projection over the set of constraints

Optimizing on C r is a NP-Hard problem. Furthermore as mentioned in several publications [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF][START_REF] Shi | Robust multi-object matching via iterative reweighting of the graph connection Laplacian[END_REF], most of the approximation methods are very sensitive to the initialization and some require to provide a reference graph (mSync [START_REF] Pachauri | Solving the multi-way matching problem by permutation synchronization[END_REF] for example). Recent methods include: mSync [START_REF] Pachauri | Solving the multi-way matching problem by permutation synchronization[END_REF] uses an eigen decomposition and a reference graph (the first graph in the algorithm presented in the paper) combined with the Hungarian method to recover the permutations.

MatchEIG [START_REF] Maset | Practical and efficient multi-view matching[END_REF] is an alternative to mSync with no reference graph but still combines eigen decomposition with the Hungarian method. As noticed in [START_REF] Bernard | Sparse quadratic optimisation over the Stiefel manifold with application to permutation synchronisation[END_REF], the cycle consistency is not guaranteed.

Birkhoff-RLMC [START_REF] Birdal | Probabilistic permutation synchronization using the Riemannian structure of the Birkhoff polytope[END_REF] uses a probabilistic method to estimate the permutation matrix from a noisy observation. This method relies on an optimization onto Riemannian manifold.

IRGCL [START_REF] Shi | Robust multi-object matching via iterative reweighting of the graph connection Laplacian[END_REF] combines several methods to estimate the permutations from a noisy permutation matrix. This method requires a reference graph for cycle consistency. They also estimate the projection of each vertex in the universe of vertices.

SQAP [START_REF] Bernard | Sparse quadratic optimisation over the Stiefel manifold with application to permutation synchronisation[END_REF] is based on QR decomposition and a power method to recover the permutations from a noisy permutation matrix. As in IRGCL, they estimate the projection of each vertex in the universe of vertices and guarantee the cycle consistency.

Generalized power method [START_REF] Ling | Improved performance guarantees for orthogonal group synchronization via generalized power method[END_REF][START_REF] Ling | Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods[END_REF] can be seen as an iterative extension of MatchEIG where the result is refined through a power method scheme. As for MatchEIG the cycle consistency is not guaranteed.

In this paper, we propose to use three methods: MatchEIG in the version presented in Algorithm 2, the iterative version of MatchEIG (Algorithm 3) which is a generalized power method and we expect it to produce better results [START_REF] Ling | Improved performance guarantees for orthogonal group synchronization via generalized power method[END_REF] and IRGCL [START_REF] Shi | Robust multi-object matching via iterative reweighting of the graph connection Laplacian[END_REF]. To avoid the need of a reference graph, we propose to apply IRGCL combined with SQAP for solving the inner problem of permutation estimation. We apply it on the permutation matrix estimated by MatchEIG. While IRGCL is more accurate than MatchEIG, its complexity may limit its scalability to large data-sets. Notice that all these methods require to have a estimation of the rank r, some are more sensitive to a bad value than others [START_REF] Maset | Practical and efficient multi-view matching[END_REF] and finding easily a good guess or the optimal value remains an open question.

Algorithm 2: MatchEIG [START_REF] Maset | Practical and efficient multi-view matching[END_REF] for computing an approximation of the permutation matrix where EIG(X) is function which computes the eigen decomposition of X and Hungarian(Z) is the Hungarian method for estimating the permutations from Z.

Input

: Perturbed bulk permutation matrix X, rank r. Output : X an estimation of the bulk permutation matrix.

U ΣU T ← EIG(X); U ← U √ Σ; for i ← 1 to n do for j ← 1 to n do Z ← U [im : (i + 1)m, 1 : r]U T [jm : (j + 1)m, 1 : r];
Xi,j ← Hungarian(Z); end end Algorithm 3: GPow: an adaptation of the generalized power method [START_REF] Ling | Improved performance guarantees for orthogonal group synchronization via generalized power method[END_REF][START_REF] Ling | Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods[END_REF] for the bulk permutation matrix estimation.

Input

: Perturbed bulk permutation matrix X, rank r, tolerance τ , maximal number of iterations T . Output : X an estimation of the bulk permutation matrix. Z 0 ← MatchEIG(X, r);

for i ← 1 to T do Z t ← MatchEIG(XZ t-1 , r); if Z t-1 -Z t < τ then break; end end X ← Z T ;
Complexity: We report here only the complexity of three methods that will be used in Section 4. As the version of MatchEIG presented by Algorithm 2 is based on an eigen decomposition and the Hungarian method the complexity is at least O(n 2 m 3 ). SQAP is mostly based on QR decomposition and GPow iterate MatchEIG-like methods. These methods have a complexity of O(T n 2 m 3 ) with T the maximal number of iterations. IRGCL is at least as complex because it relies on methods like mSync at each iteration. Thus, while MatchEIG may be the fastest method, the others may lead to better results that fully respect the cycle consistency.

Experiments

We extensively benchmark our method on four data-sets. In addition to a synthetic set of graphs, we consider two multi-image data-sets that are commonly used for graph matching comparison: Willow, PascalVOC 2 . We compare our method against several state-of-art unsupervised methods: HiPPI [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF], MatchEIG [START_REF] Maset | Practical and efficient multi-view matching[END_REF] (without the thresholding step), GA-MGM (Wang et al., 2020a) and Floyd [START_REF] Jiang | Unifying offline and online multi-graph matching via finding shortest paths on supergraph[END_REF]. We also compare the performances of our method against three state-of-art supervised methods for pairwise graph matching: DGMC [START_REF] Fey | Deep graph matching consensus[END_REF], NGM [START_REF] Wang | Neural graph matching network: Learning Lawler's quadratic assignment problem with extension to hypergraph and multiplegraph matching[END_REF] and SIGMA (Liu et al., 2021b). Both methods are based on deep learning to learn the best representation for matching.

Data-set management: All the computer vision data-sets are provided by pytorchgeometric 3 . We directly use the keypoint and their attributes (descriptor and position). For the construction of the graphs from the keypoints, we follow the procedure from [START_REF] Fey | Deep graph matching consensus[END_REF] where the graphs are built using a Delaunay tessellation with an isotropic distance. For Willow and PascalVOC, the descriptors are taken for each keypoint from the concatenated output of relu4 2 and relu5 1 on a VGG16 network trained on ImageNet [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF].

Kernel setting: For the synthetic graphs experiments we only use linear kernels to avoid hyper-parameter setting. For Willow and PascalVOC, we use the Gaussian kernel for computing the vertices weight as in [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF]. We follow also the same protocol as in [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF] to compute the weights on the edges. The weights are computed using a Gaussian kernel applied to the distance between the vertices and the variance is given by the median of the minimal distances. As kernel on the edges, we use the Random Fourier Features (RFF) [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF] as proposed for KerGM [START_REF] Zhang | KerGM: kernelized graph matching[END_REF]. For all experiments we take a dimension of 100 for the random features.

Initialization: For all our experiments, we initialize our method using the null matrix, which is equivalent to an initialization using the projection method on the vertex affinity matrix.

Dummy vertices: For all experiments we add dummy vertices when the size of the graphs varies. In practice, we add unconnected vertices with attribute values far from the legitimates ones (the same for all dummy vertices). These vertices are removed before computing the score, the vertices that are matched to a dummy vertex are then considered as unmatched. We thus take such configuration into account when defining the score.

Convergence setting: For Algorithm 1 we set the maximal number of iterations to 100 and the tolerance to 10 -2 . The algorithm stops when one of the conditions is met. For IRGCL we use the same setting and parameters as proposed in [START_REF] Shi | Robust multi-object matching via iterative reweighting of the graph connection Laplacian[END_REF]. For Algorithm 3 we set the maximal number of iterations at 100 with a tolerance of 10 -3 .

Similarity scores: We compute the precision and recall directly from the ground truth bulk permutation matrix X truth . Let X be the current estimated bulk permutation matrix, the score are then computed as follows:

precision = X truth -I, X -I X -I 2 F , recall = X truth -I, X -I X truth -I 2 F F1 -score = 2 * precision * recall precision + recall (12)
2. Some statistics on these sets can be found in [START_REF] Fey | Deep graph matching consensus[END_REF]

Synthetic data-set

We use a synthetic data-set to assess the robustness of our method to different perturbations.

In this purpose we adapt the protocol from [START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF]; [START_REF] Zhang | KerGM: kernelized graph matching[END_REF] where the graphs are generated from an Erdős-Rényi model. For this experiment, we generate graphs with 50 vertices and a probability of edges of 0.05 (also named connectivity density in [START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF]). For each test, we report the mean value across 20 graphs. For each graph, the attributes of the vertices and the edges are random vectors built from the uniform distribution U(0, 1). The dimension of these vectors is set to 10. First, we assess the sensitivity of our method with respect to noise on the attributes. For each graph in the set we compute nine shuffled versions to make a total of 10 graphs. We add the same additive Gaussian noise on the attributes of the vertices and edges, with different variances. We set the rank to 50, the number of vertices. We compare our method against MatchEIG [START_REF] Maset | Practical and efficient multi-view matching[END_REF] where only the vertices are taken into account. Figure 1(left) shows the evolution of the F1-score as a function of the variance of the noise. We show only our results with MatchEIG as projector, we also test with IRGCL and GPow but they yield similar results, so for visualization purpose we selected only one method. Our method is more robust to noise since it uses both edges and vertices. It is interesting to see that it is robust to small and mild noise values while the performance severely degrades with higher noise levels. Compared to MatchEIG, the robustness likely comes from taking the edges into account, as long as the attributes on edges are reliable.

Secondly, we assess the robustness of our method against vertex removal. For this, we remove vertices at random until a maximal number is reached. This means that for a given set of graphs, the number of vertices removed is not the same for all the graphs but cannot exceed the specified maximum. The removed vertices are disconnected from the other vertices and transformed into dummy in order to preserve an equal number of vertices. We also add different levels of noise on the attributes (same variance for edge and vertex data vectors). The results are presented by Figure 1(right). In absence of noise, MatchEIG shows a better robustness to vertex removal. But when we add the noise, our Method/Class Car Duck Face Motorbike Winebottle MatchEIG [START_REF] Maset | Practical and efficient multi-view matching[END_REF] 23.4 36.1 47.6 19.4 21.1 HiPPI [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF] 74.0 88.0 100 84.0 95.0 GA-MGM (Wang et al., 2020a) 74.6 90.0 99.7 89.2 93.7 Floyd-c [START_REF] Jiang | Unifying offline and online multi-graph matching via finding shortest paths on supergraph[END_REF] 85.0 79.3 100 84.3 93.1 DGMC [START_REF] Fey | Deep graph matching consensus[END_REF] 95.53 93.0 100 99.4 99.39 NGM-v2 [START_REF] Wang | Neural graph matching network: Learning Lawler's quadratic assignment problem with extension to hypergraph and multiplegraph matching[END_REF] 97 method performs better. Note that the matching quality degrades severely with increased maximal number of removed vertices. This is expected since removing vertices leads to changes in the edges and but also in the topology of the graphs.

Willow data-set

Willow is an image data-set composed of 5 classes of objects. For each class we have a minimum of 40 graphs with exactly 10 vertices. Here we use the same edge attributes as in [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF] where the weights are computed using the median distance between vertices.

In order to find an appropriate set of hyper-parameters we run a grid-search on the variance for the Gaussian kernel on the vertices and the parameter of the RFF. The tested values range from 10 to 100 for an additive step of 10 for the vertices and from 10 -6 to 1 with a multiplicative step of 0.1 for the edges. For each set of values, we take at random 10 graphs from the car class and apply our method to estimate the F1-score. We repeat the process 10 times and report the mean of the scores. We use the set with the best mean score (80 for vertices and 10 -5 for edges).

We present the results in Table 1. Here we use three methods for the projection onto permutations set: MatchEIG, GPow and IRGCL (with SQAD for the inner optimization step). For all methods expect MatchEIG we report the score from the articles. For MatchEIG we used our own implementation. The results show that we are competitive compared to other state-of-art methods. On the projection side, IRGCL leads to better results on motorbike while GPow is better on winebottle. Between the three methods, MatchEIG gives the best average results and is a little better than unsupervised state-of-art methods like Floyd-c [START_REF] Jiang | Unifying offline and online multi-graph matching via finding shortest paths on supergraph[END_REF].

PascalVOC data-set

PascalVOC is an image data-set composed of 20 classes of objects with key points on each image. This database is challenging since the number of vertices vary greatly inside a For the hyper-parameters estimations we use the same protocol as for Willow (Section 4.2) but using the horse class. The optimal parameter were 60 for vertices and 0.01 for edges. We report the results in Table 2. Except MatchEIG where we use our own implementation, the results of the other methods are taken from the articles. Notice that we also report the results from NGM-v2 using an unsupervised setting with the same VGG16 data of the vertices. While supervised methods clearly perform better on this set, we are competitive with the two unsupervised methods. For computational reasons we did not apply IRGCL or GPow for the projection step. Interestingly while our method generally outperform MatchEIG, there are some classes where it is the reverse (e.g. tables). This could be explained by the way the edges are built (Delaunay tessellation). For some classes we are even better than the unsupervised version of NGM-v2 (bottle and plant).

These results are in line with our experiment on the robustness in Section 4.1. Since PascalVOC graphs are affected by noise and vertex suppression, our method performs badly on the most degraded category. Furthermore some categories are only composed by few graphs, for the test set. The cycle consistency is then insufficient to recover the good matches.

Conclusion and future work

We propose a generalization of the KerGM approach [START_REF] Zhang | KerGM: kernelized graph matching[END_REF] for multi-graph matching. Our approach allows for more flexibility than previous methods for dealing attributes on edges. While others methods directly deals with Lawler's QAP, our approach relies on more efficient matrices and arrays and can be applied to larger and more complex data-sets. Contrary to other methods [START_REF] Bernard | HiPPI: Higherorder projected power iterations for scalable multi-matching[END_REF]Wang et al., 2020a), we do not optimize in the universe of vertices, but directly manage the projection onto the permutation sets. This avoids some common limitations induced by the definition of the universe of vertices. In addition, our approach benefits from recently published methods to estimate the projection in reasonable computational times.

The kernel framework is very flexible and allows for specific definitions of the affinity on vertices and edges. For the edges we only use the classical Random Fourier Feature, but one can use more adapted features [START_REF] Li | Towards a unified analysis of random fourier features[END_REF] while keeping a tractable memory load. As an unsupervised method, the matching relies essentially on the constraints and the experiments show it is sufficient to deal with mild level of noise and almost homogeneous, in term of number of vertices, sets of graphs. Managing more complex sets requires either supervised learning or additional constraints.

Potential improvements include building a stochastic version of the method in order to be able to handle very large sets of graphs, for example by adapting stochastic DC methods [START_REF] Xu | Stochastic optimization for dc functions and non-smooth non-convex regularizers with non-asymptotic convergence[END_REF]. We also seek to improve the projection step while keeping an acceptable computational burden.

Figure 1 :

 1 Figure 1: (left) The robustness of our method compare to MatchEIG following the variance of the noise. (right) The robustness of our method compare to MatchEIG following the maximal number of removed vertices and the variance of the noise.

Table 1 :

 1 F1-score of the different approaches on the Willow data-set. DGMC and NGM-v2 are supervised method where the vertices attributes are learned using deep learning framework. The others methods are unsupervised. We remind that the IRGCL method is combined with SQAD and initialized with MatchEIG result.

	.4	93.4	100	98.6	98.3

Table 2 :

 2 F1-score of the different approaches on the PascalVOC data-set. class and there are also outliers. The number of vertices for a graph can vary from 1 to 16. For this data-set with follow the protocol from Fey et al. (2020) (it differs from the protocol of Wang et al. (2021) as they have different limits for the number of vertices). For comparison purpose we only use the test sets of each category.

	KMGM

Acknowledgments

This work received support from the French government under the France 2030 investment plan, as part of the Initiative d'Excellence d'Aix-Marseille Université -A*MIDEX.


Elvira Nikalayevich
email: elvira.nikalayevich@college-de-france.fr

Katja Wassmann
email: katja.wassmann@ijm.fr

Protocol to measure cleavage efficiency of the meiotic cohesin subunit Rec8 by separase in mouse oocytes using a biosensor

Here we describe a biosensor to assess meiotic cohesin cleavage by live imaging in mouse oocytes. The biosensor is targeted to chromosomes and consists of two fluorophores flanking a fragment of Rec8 containing Separase cleavage sites. Cleavage of Rec8 leads to dissociation of one of the fluorophores from chromosomes which is used to estimate cleavage efficiency. We detail the use of this biosensor in mouse oocytes completing the first meiotic division in presence or absence of AuroraB/C inhibitor.

.

Before you begin

 where a Key resources table REAGENT or RESOURCE SOURCE IDENTIFIER Chemicals, peptides, and recombinant proteins M2 medium Merck Millipore Cat# MR-015P EmbryoMax® Penicillin/Streptomicin, solution 100X Merck Millipore Cat# TMS-AB2-C N6,2ʹ-O-Dibutyryladenosine 3ʹ,5ʹcyclic monophosphate sodium salt (dbcAmp)

biosensor containing a fragment of the mitotic cohesin subunit Scc1 was used to detect Separase activity.

1. Make sure to have the necessary permission and training to euthanize mice. 2. Oocyte culture conditions during timelapse imaging should be optimal to let oocytes go through anaphase without delay. See Problem 1 in the Troubleshooting section.

3. Verify the design of the biosensor, making sure it contains Separase cleavage sites (ExxR/D) only where you intend them to be.

Note: Artificial cleavage sites can be introduced inadvertently during the cloning process, please check the peptide sequence of any linkers between the functional parts of the biosensor.

4. Prepare capped mRNA following the instructions of the kit's manufacturer. Aliquot the final elution (30-40 μl) in 5 μl aliquots, store at -20°C for up to 1 month (or at -80°C for longer periods).

CRITICAL: Use gloves, work in a clean and nuclease-free environment (preferentially with

RNAse inhibitors) and use nuclease-free water when preparing mRNA.

Note:

The level of biosensor expression depends on the quality of the microinjected mRNA.

The mRNA should form two sharp bands on the agarose gel after electrophoresis, appearance of a smear signifies RNA degradation. If the biosensor sequence is rather long (above 2500 bps), additional polyadenylation and increasing the concentration of GTP in the in vitro transcription reaction such as suggested by the manufacturer can help with increasing mRNA yield and stability, leading to higher protein expression in oocytes. The culture medium (M2 medium) is supplemented with penicillin (final concentration 1.678 mM) and streptomycin (final concentration 0.689 mM). To keep the oocytes in prophase I arrest, the medium is additionally supplemented with 100mg/mL dibutyryl cyclic AMP (dbcAMP).

Oocyte collection and manipulation is done under a Nikon stereomicroscope SMZ1000 equipped with a compatible Tokai Hit thermoplate. The light source should be below the stage, and the light temperature should be warm (i.e. the color of the light should be slightly yellow) for better visualization of the oocytes.

Silicone tubing for mouth pipetting consists of a mouth piece attached to a thin (4.8 mm inner diameter) silicon tube of about 1 m. On the other side, a 1 ml plastic pipette tip is introduced and fixed with the help of Parafilm M (Sigma Aldrich, ref. #P7543). A thick (1mm inner diameter), around 5 cm long silicon tube is torn over the larger end of the 1 ml tip and used to attach the thicker end of a glass Pasteur pipette, again sealed with parafilm.

The mouth piece is taken from the "Aspirator tube assemblies for calibrated microcapillary pipettes" product (Sigma-Aldrich ref. #A5177-5EA). Alternatively, the mouth piece can be replaced with a 200 μl plastic pipette tip, with its tapered end inserted into the silicon tube. The silicon tubing is Fisherbrand™ Translucent Platinum-Cured Silicone Tubing (Fisher Scientific ref. #11748118 and #11758148).

We use 230 mm Pasteur pipettes with a closed tip made from soda-lime glass (CEB ref. #PP230S)., to generate very thin glass pipette tips for oocyte aspiration. The thin part of the pipette (around 1-2 cm away from the part where the pipette gets wide) should be heated up over a flame until it is red and glowing. Holding both ends of the pasteur pipette, the molded glass should be extended with a swift motion outside the flame. The very end of the extended glass pipette should be broken off manually to produce a 5-10 cm long thin ending with an opening large enough to aspirate oocytes. For oocyte collection, the inner diameter of the opening should be large enough to aspirate oocytes with attached cumulus cells (around 200 μm). For subsequent cleaning of oocytes, the inner diameter of the pipette should be very close to the diameter of the oocytes (70-80 μm). The correct size of the pipette tip has to be checked under the microscope and by mouth-pipetting oocytes up and down. Step-by-step method details

Oocyte collection

Timing: 1-2 hours Mouse prophase-arrested oocytes are collected and prepared for microinjection.

1. Prepare a 60 mm polystyrene tissue culture dish with 5-6 droplets (around 30 μl each) of prewarmed medium containing dbcAMP. Cover the drops completely with a layer of mineral oil. Prepare another dish/cover/container with a large drop of medium (800-1000 μl) containing dbcAMP and without oil for dissection of ovaries. 2. Sacrifice a female mouse through cervical dislocation or in a CO2 chamber, dissect the abdomen and collect the ovaries. Make sure to carefully tear off fatty tissue with forceps and place the ovaries in the medium containing dbcAMP, without oil.

Note:

We use mice that have not been hormonally stimulated, to work with naturally competent oocytes. Optimal age of a OF1 (Swiss) mouse for oocyte collection is 8-12 weeks. The quantity of oocytes obtained per mouse depends on the strain, the age and estrus cycle of the mouse. On average, an unstimulated OF1 mouse yields 40-70 oocytes, C57BL6 mice yield around 30 oocytes each.

3. Working under the binocular microscope equipped with a heated glass plate, macerate the ovaries with the sharp tip of a needle, opening up all the large follicles. With a glass pipette (torn-out Pasteur pipettes, prepared as described above) collect all fully-grown oocytes that were released from the dissected follicles and transfer themto the dish with smaller medium droplets covered with mineral oil.

Note:

The end of the pasteur pipette may be broken off manually to create a straight tip, to avoid hurting the oocytes upon pipetting. Oocytes should enter the glass pipette without extra sucking force applied and should not be deformed upon entering and exiting the glass pipette. The inner diameter should not be too large either, to avoid pipetting more volume than necessary at each step, which can make it hard to control the flow and leads to damage on the oocytes.

Note:

In this and all following steps keep the oocytes at 37°C. This is important even when harvesting and manipulating oocytes. Medium should be prewarmed, and microscopes equipped with heated plates. Alternatively, oocytes can be put in an incubator between the different steps to avoid cooling down of the medium; however, in our experience proceeding like this is suboptimal and delays in meiotic maturation may occur.

4. Clean the collected oocytes. This means detaching all the remaining follicular cells (denudation) by passing the oocytes several times through the opening of a glass pipette with an inner diameter only slightly larger than the diameter of an oocyte (80-100 μm). Transfer the follicle-free oocytes into another medium drop in the same dish. 5. Select fully-grown competent oocytes that are arrested in prophase I, and discard the rest.

Note: Competent prophase I oocytes have reached their full size (70-80 μm in diameter), with the germinal vesicle (GV) in the center and with a smooth-looking Zona Pellucida (ZP). Oocytes covered with follicle cells that cannot be removed and the GV not in the center are not fully competent and should be discarded. See Figure 1C for an example of a competent oocyte arrested in prophase I.

Microinjection

Timing: 15-60 min (without centrifugation step) mRNA to express the biosensor is microinjected into prophase-arrested oocytes.

6. Defrost and centrifuge one mRNA aliquot in an Eppendorf centrifuge at maximum speed at 4°C for 15-45 min. Keep on ice. 7. Prepare the microinjection needle and load it with 0.5-1.5 μl of mRNA solution.

Note: We use home-made microinjection needles made from glass capillaries (outer diameter 1 mm, inner diameter 0.75 mm, length 100 mm, purchased from Harvard apparatus) with the help of a Narishige PN-30 puller (currently discontinued, possible alternative is Narishige PC-100). The puller settings have to be determined experimentally as identical settings on identical machines do not result in the same needle configuration.

Note: Load the needle with 0.5-1.5 μl of mRNA solution with the help of microloader tips (Eppendorf).

8. Place a 10-15 μl drop of the culture medium with dbcAMP in the center of a glass slide with a shallow depression and cover with a small amount of mineral oil. Transfer the oocytes into this drop.

Note: Make sure that the mineral oil covers the drop of the culture medium completely. This prevents the medium from evaporating which would change the osmotic pressure and affect the oocyte quality. Glass slides with a shallow depression ("depression glass slides" or "cavity glass slides 9. Place the glass slide with oocytes under the microinjection microscope, lower the holding pipette and the loaded microinjection needle to the oocyte level. Switch the microinjection pump to constant flow setting (Figure 1A,B).

Note:

We use Eppendorf FemtoJet Microinjector with constant flow setting as it is the best way to ensure oocyte microinjection success. It does not deliver an exact, predetermined volume of RNA into the oocyte. However, the amount of protein expression after microinjection has to be measured by other means anyway, as protein expression does not only depend on the amount of mRNA injected, but also on its quality and ternary structures it may form.

10. Capture one oocyte with the holding pipette and insert the tip of the microinjection needle in the oocyte, avoiding the nucleus (Figure 1C). Quickly take the needle out after injection.

Release the oocyte from the holding pipette. Repeat the procedure to microinject all the oocytes.

Note: For holding pipettes, we use VacuTip microcapillaries, inner diameter 15 μm, outer diameter 100 μm, angle 35°. The pipette is connected to an Eppendorf CellTram Oil manual microinjector. For an example of a microinjection setup, see Figure 1.

Note: Successful injection is indicated by a short burst in the cytoplasm, the size of the burst depends on the pressure supplied to the microinjection needle. Increase or reduce the pressure setting of the Microinjector to change the injection force. Ideally the size of the burst should be comparable or smaller than the oocyte nucleus.

Note: After injection, retrieve the needle quickly but carefully, keeping the same angle so not to tear the plasma membrane and kill the oocyte.

Note:

We arrange oocytes under the microscope in a way that not injected oocytes are "above" and injected oocytes are "below" the microinjection needle. With the holding pipette, one oocyte after the other is taken from "above", moved in front of the microinjection needle, injected, and moved to the "lower" pool of injected oocytes.

Note: Depending on the microinjection skills of the user and the amount of injected mRNA, 30-80% oocytes will survive, others will lyse within 15-30 min after injection.

11. Transfer the injected oocytes from the glass slide into an unused drop of medium in the original culture dish. Incubate at 37°C for 1-4h to ensure that there is sufficient time for protein expression.

Note: Depending on mRNA concentration, the length of the mRNA to be translated and efficiency of protein expression, the incubation time can be shortened or extended. However, too long incubation may interfere with efficient prophase I exit after dbcAMP washout.

Release from cell cycle arrest and timelapse imaging

Timing: 10-12h

The injected oocytes are released from prophase I arrest and prepared for timelapse imaging in presence or absence of Aurora B/C inhibitors. Oocytes are filmed to capture metaphase I to anaphase I transition.

12. Prepare a culture dish with 5-6 drops (around 30 μl each) of culture medium without dbcAMP and cover with mineral oil. Pre-warm the dish at 37°C.

13. Place the injected oocytes into several successive drops of culture medium, thus removing trace amounts of dbcAMP to allow cell cycle resumption. 14. Incubate the oocytes at 37°C for 50-70 min until they start undergoing germinal vesicle breakdown (GVBD). Ten to fifteen minutes after the first oocytes undergo GVBD, discard all oocytes still in prophase. Incubate the synchronized batch of oocytes at 37°C for 4-6h.

Optional: Prepare a dish with 3-4 drops (around 30 μl each) of medium containing Aurora B/C (or Aurora A) inhibitor (ZM447439 or AZD1152 for Aurora B/C and MLN 8237 for Aurora A), cover with mineral oil, and prewarm the dish at 37°C. Transfer the required number of injected oocytes that underwent GVBD on time through subsequent pipetting into 2-3 drops of medium with inhibitors, leaving them to incubate in the last drop.

Note: GVBD marks oocyte exit from prophase and resumption of meiosis. The most competent and healthy oocytes undergo GVBD approximately 1h after release from dbcAmp-containing medium, which maintains them arrested. It is possible to use the oocytes that undergo GVBD after the first batch, but these oocytes are more likely to have no or delayed anaphase I onset. We never use oocytes that undergo GVBD more than 90 minutes after release.

Note: Aurora B/C is required for the so-called error correction pathway, to detach wrongly attached microtubule fibers. It is functional during early meiosis, when mictroubules attach and detach continiously. The error correction pathway signals to the spindle assembly checkpoint (SAC) which imposes a cell cycle delay. As a consequence, inhibition of Aurora B/C results in accelerated cell cycle progression. Under normal conditions, mouse oocytes of the strain backgrounds we use undergo anaphase I around 7-9 hours after GVBD, and 4.5-5h after GVBD if the SAC is inactivated. Thus, adjust timelapse imaging setup to account for accelerated anaphase timing in presence of Aurora B/C inhibitors.

Note:

The concentration of AuroraB/C inhibitors should be determined experimentally as we found that depending on the manufacturer and production batch the quality may differ. Too strong AuroraB/C inhibition affects chromosome condensation, making them appear as a uniform mass. It is impossible to correctly measure the cleavage efficiency of the sensor in this case. Also, too high concentration may lead to unspecific inhibition of Aurora A, preventing anaphase I onset.

The aliquots of the inhibitors should be prepared according to the manufacturer's instructions and diluted in the culture medium to obtain the desired concentration just before use.

Note: AuroraB/C is required for cytokinesis, i.e. polar body (PB) extrusion. Anaphase I onset is detectable through rapid chromosome movements, or an attempt to extrude a PB which is then retracted.

15. Prepare a microscopic chamber such as suggested by the microscope manufacturer with multiple drops of 2 μl medium and cover with mineral oil. Prewarm at 37°C. Place 1-2 injected oocytes in each drop.

Note: If using Aurora kinase inhibitors, use medium containing inhibitors when preparing the chamber.

Note: Oocytes are very sensitive to laser irradiation, such as used in confocal imaging systems. To reduce laser exposure, it is best to place individual oocytes apart from each other. The number of medium drops in the chamber should accommodate the number of oocytes in the experiment. The maximum number of oocytes depends on the conditions and is best determined experimentally.

16. At 4-6 h after GVBD, start timelapse imaging: use the transmitted light, the 491nm and 561nm channels, acquire a z-stack of the region around the chromosomes (30-45 μm with a step-size of 3 μm), with acquisitions every 15-20 min.

Note: Duration of timelapse imaging should start in metaphase I and cover anaphase I, which normally occurs 7-9 h after GVBD. It may be slightly delayed (<30 min) due to the imaging conditions, compared to the oocytes kept in the incubator. A more significant delay indicates that culture conditions are suboptimal.

Note: Start of the movie has to be adapted to accelerated cell cycle progression in Aurora B/C inhibitor-treated oocytes. 17. After timelapse imaging check that the oocytes have survived and control oocytes have extruded a polar body, indicative of exit from meiosis I.

Cleavage efficiency quantification

Timing: 2h

The movies are analysed and biosensor cleavage efficiency is quantified.

18.

Using ImageJ, open image sequences (as stacks and hyperstack) for TRANS, 491nm and 561nm channels for one oocyte. 19. For measuring, select the oocytes with their chromosomes fully visible during several timepoints before, during and after anaphase I.

Note:

The chromosomes may migrate out of focus during anaphase if the metaphase plate is not parallel to the plane of imaging. The signal from only partially visible chromosomes should be discarded, as it will introduce errors in quantifications.

Identify the timepoint of anaphase I (marked by chromosome segregation and beginning of polar body extrusion).

Note: If Aurora B/C kinases are inhibited, chromosome segregation is often problematic as endogenous Rec8 cleavage depends on the activity of these kinases. In this case, anaphase can also be spotted through the attempt of the oocyte to extrude a polar body (which will most likely retract) in the transmitted light channel, or a sudden movement of the chromosomes towards the oocyte cortex (in the 561nm channel). Consider the timepoint where either of these events occur as anaphase, and keep in mind that oocytes devoid of functional Aurora B/C undergo anaphase I onset several hours earlier compared to untreated oocytes, due to absence of error correction signaling to the SAC.

21. Starting from 3-4 timepoints before anaphase and until 3-4 timepoints after anaphase, measure mean fluorescence on Z-projection (maximum intensity) in 491nm and 561nm channels in a box that includes all chromosomes ("Chromosomes") and in another box placed in the cytoplasm away from the chromosomes ("Cytoplasm"). See Figure 2A.

Note:

The area measured must be the same in size and position between the two channels. As the chromosomes will change position during anaphase, make sure to follow the chromosomes with the area that is being measured.

Note: During anaphase, chromosomes are separated with half of them being extruded into the PB.

When the area measured cannot cover both halves anymore, shift the area to cover only one half of the now segregated chromosome masses, preferably the one remaining in the oocyte, but keep in mind that the signal has now been divided by two (Figure 2).

22. Import the measurements into MS Excel, subtract the "Cytoplasm" from the "Chromosomes" signal for each channel and for each timepoint. Normalize the result for each channel separately to the timepoint right before anaphase (Figure 2B).

Note:

If the value at the timepoint right before or at onset of chromosome segregation is significantly lower than the value at the timepoint just before, take the higher value for normalization. (Separase cleavage may have started already before segregation of chromosomes is visible)

23. Calculate the ratio between the values obtained for the 491nm and 561nm channels (divide the normalized value of the 491nm channel by the normalized value of the 561nm channel for each timepoint). Find the lowest post-anaphase value (within 0-30 min after anaphase), and subtract it from the highest pre-anaphase value. This value represents the portion of the sensor that was cleaved during anaphase, i.e. cleavage efficiency of the sensor.

Note: Cleavage efficiency is notoriously variable between oocytes, especially if biosensor expression levels are low. Hence, it is important to quantify sensor cleavage in a high number of oocytes to obtain statistically significant results.

Expected outcomes

Cleavage efficiency of a sensor is a numerical value representing how many molecules of the biosensor were cleaved in a separase-dependent manner at anaphase I onset. The values should present a statistically significant difference when compared to the values measured from the negative control (a sensor without a separase cleavage consensus sequence). It is expected that the cleavage efficiency is different between oocytes based on the level of biosensor expression and noise-to-signal ratio in a given oocyte.

It is expected that inhibition of Aurora B/C but not Aurora A activity reduces or completely inhibits cleavage of the Rec8-containing biosensor.

In absence of separase or separase activation, no cleavage should be observed.

Limitations

The method for measuring Rec8 cleavage efficiency we describe here is best suited for mouse oocytes and not in other experimental systems, such as cultured somatic cells. The use of kinase inhibitors such as described here for Aurora kinases can be challenging due to possible side effects perturbing chromosome structure, chromosome segregation, or cell cycle progression. It is essential to confirm the conditions for this protocol with positive and negative controls, like Scc1-containing biosensor (positive control) or non-cleavable biosensor (negative control).

Troubleshooting

Problem 1:

Oocytes don't go through anaphase during timelapse imaging (step 17).

Potential solutions:

• Oocytes are very sensitive to the temperature, quality of culture medium and the quality of the mineral oil that is used to cover the medium droplets. Test whether the oocytes complete the first meiotic division normally in the incubator at 37°C. If the oocytes survive and extrude a polar body at the correct time in the incubator but not under the microscope, the temperature should be checked first, preferably right before and right after the imaging session. To check the temperature of the imaging setup, we use a thermometer with a long wire sensor placed exactly where the oocytes are supposed to be (middle of the fluorodish, right above the microscope objective).

In our experience, the temperature is less stable in the heated chamber of the microscope than in the tissue culture incubator, likely due to insulation problems or temperature changes in the area surrounding the microscope. Often the actual temperature of the culture medium droplet in the imaging chamber is different from the temperature settings of the microscope heating system. Adjust the temperature settings and make sure the actual temperature in the medium droplet is 37°C. • During timelapse imaging, too much exposure to laser radiation can damage oocytes resulting in the failure to complete cell division. To check whether the laser irradiation is excessive, make a test run of the experiment without 491nm and 561nm channels, imaging with transmitted light only. If the oocytes complete anaphase I with exposure to transmitted light but not when the lasers are used, limit exposure to laser damage by reducing either laser power, exposition time, number of timepoints or number of stage positions. These settings can vary a lot from microscope to microscope. Imaging not more than 10 oocytes with timepoints every 20 min, 15 z-slices with 3 μm distance between z-slices should be a good starting point. Laser power and exposure times should be as low as possible, but sufficient enough to clearly visualize all chromosomes. Start imaging not earlier than 1h before anaphase I is expected, to avoid unnecessary exposure before the crucial time point you are interested in.

• Check that oocyte collection and handling techniques applied are not damaging the oocytes.

Oocytes are also sensitive to the quality of mineral oil used to cover medium droplets. The oil can be additionally purified by vortexing an aliquot of oil together with milliQ water and then letting the phases separate. Other factors may include quality of the culture medium or the material of the imaging chamber. • Certain inhibitors will block cell cycle progression. Depending on the mechanism, it is possible to override the arrest. For example, SAC-dependent arrest can be lifted with the Mps1 inhibitor Reversine.

Problem 2:

Oocytes do not survive microinjection (step 10).

Potential solutions:

• Proper microinjection technique is required to achieve good survival rate. Practice microinjection with water and limit the injected volume. Adjust the length and shape of the microinjection needle tip by changing the settings of the needle puller. See Figure 1C for an example of the needle shape. • Dirt on the microinjection needle tip might damage the oocyte membrane during injection.

The needle tip can be cleaned by tapping or sliding it against the holding pipette tip. • If the RNA solution is too viscous and causes needle clogging, you can dilute the solution with nuclease-free water (however, this may also reduce biosensor expression) and microcentrifuge the sample again. Make sure the RNA sample is purified.

Problem 3:

Insufficient sensor expression, chromosomes are not visible (step 16).

Potential solutions:

• Check that the oocytes are injected by comparing background fluorescence in 491nm or 561nm channels of injected and not injected oocytes. • Synthetize a fresh aliquot of mRNA, make sure not to introduce nucleases (from dust, skin) until injection. • Increase RNA concentration, increase RNA quality by adding extra capping solution, GTP or extra polyadenylation, according to the manufacturer's instructions. • Prolong incubation time after injection.

• Verify mRNA quality of the aliquot that has been used for injection, to be sure the mRNA remained stable throughout the microinjection procedure.

Problem 4:

Aurora B/C inhibition produces unexpected results (step 14).

Potential solutions:

• Make sure to add the inhibitors within the first 15 min after GVBD.

• Try inhibitors from different suppliers, always use single-use aliquots.

• Verify that the inhibitor works (by staining for the Aurora B/C substrate pH3S10, and checking that anaphase I onset is accelerated). • If the chromosomes are decondensed and stuck together before anaphase I, try reducing the concentration of the inhibitor or changing suppliers.

Resource availability

Lead contact

Further information and requests for resources and reagents should be directed and will be fulfilled by the lead contact, Katja Wassmann (katja.wassmann@ijm.fr).

Figure 1 .

 1 Figure 1. Microinjection setup. A) A bright-field microscope with attached pipette holders that are operated by micromanipulators. Pressure is supplied by the manual microinjector to the left and the automatic microinjector to the right. The microscope is equipped with a heating plate and a temperature controller. B) A heating plate containing a depression glass slide. A holding pipette and a microinjection needle are connected to the pipette holders. C) Mouse oocyte ready for microinjection.

Figure 2 .

 2 Figure 2. Measuring biosensor cleavage efficiency from timelapse images. A) A montage of timelapse images of a mouse oocyte undergoing anaphase I (marked as 0 min). Rectangles of colored dashed lines mark the areas where the mean fluorescence signal should be measured. B) Calculations based on the measurements from (A), colored blocks correspond to measurements from the rectangles of colored dashed lines.

  ", for example Globe Scientific ref. #1341-72 or VWR ref. # 470235-728) are perfect for this purpose. If the medium drop is not covered with the mineral oil completely you can also reduce the volume of the drop.

Acknowledgments

We thank the members of the MOM team for discussion and helpful suggestions, Marie-Emilie Terret and Marie-Hélène Verlhac for allowing to take the pictures of the microinjection setup. E.N. was supported by a postdoctoral fellowship by the FRM (Fondation de la Recherche Médicale SPF20150934093) and EMBO (short-term fellowship ASTF 426 -2015). The K.W. lab obtained funding for this project from ANR (ANR-16-CE92-0007-01 and ANR-19-CE13-0015) and FRM (Equipe FRM DEQ 20160334921, Equipe FRM DEQ 202103012574), and core funding from the CNRS and Sorbonne Université.

Sigma-Aldrich

Cat# D0260-25MG CAS

Materials availability

All unique reagents generated in this study are available from the lead contact without restriction. The study did not generate new mouse lines.

Author contributions

EN and KW designed the concept, EN did experimental work and troubleshooting, EN wrote the manuscript with input from KW.

Declaration of interests

The authors declare no competing interests.