Arnaud Lods Learn&go
email: arnaud.lods@learn-and-go.com

Éric Anquetil
email: eric.anquetil@irisa.fr

Sébastien Macé Learn&go
email: sebastien.mace@learn-and-go.com

Graph Edit Distance for the analysis of children's on-line handwritten arithmetical operations

Keywords: arithmetical operation analysis, graph matching, sub-graph isomorphism, graph edit distance

This paper is based on a research project aiming at improving learning arithmetic operations at school using penbased tablets. Given an arithmetic operation instruction, the goal is to analyze a child's handwritten answer. This comes down to find if any mistakes are made and their nature. An adapted representation and similarity search are needed for this analysis. In this paper, we propose to use a valued graph representation for handwritten arithmetical operations. To produce the analysis, we compute a similarity search with the corresponding expected answer using Graph Edit Distance (GED). To make up for the uncertainty of the noisy handwritten input recognition, we produce several segmented graph hypotheses for a single answer. Using the GED, we are able to correlate each hypothesis to the instruction graph. It enables to highlight multiple kinds of mistakes a child can make. The GED computation being a NPcomplete problem, we propose to use sub-graph isomorphism: we partially match the instruction on each hypothesis in polynomial time to cut part of the tree search. Experiments were conducted on an in-house dataset composed of 400 handwritten arithmetical additions written by children on pen-based tablet. The time required for the GED computation is evaluated. We are able to match the complete operation in reasonable time on larger graphs while finding most of the time the best corresponding hypothesis.

I. INTRODUCTION

In the intelligent tutoring domain, several systems were proposed to provide an analysis of a student's answer for programming exercise [START_REF] Marin | Automated personalized feedback in introductory java programming moocs[END_REF] or for mathematics using keyboard interfaces [START_REF] Xin | An intelligent tutor-assisted mathematics intervention program for students with learning difficulties[END_REF], [START_REF] Huang | Intelligent tutoring systems work as a math gap reducer in 6th grade after-school program[END_REF]. With the recent improvement of pen-tablet devices, such system can be enhanced to transfer solving mathematical problems from the devices to paper back and forth. The input process displayed in Figure 1 is straightforward: a child is given an operation instruction, and he is expected to solve it using a pen and a tablet as he would do it on paper. The resulting on-line handwritten input is a set of sequences of points in the 2D space. The answer expected from the child can be deduced from the instruction. The goal of the analysis system is to produce adapted feedback for the child. The feedback will depend on the nature of their mistakes. It is necessary to both recognize what was written and find any dissimilarities between the child's answer and the expected answer. Given the learning context, mistakes can be either misaligned symbols, a wrong instruction recopy, a forgetting of operators, calculus mistakes, unneeded symbols, Fig. 1: Input of our system. An operation instruction is given to the child who wrote his answer on a pen-tablet device. An expected answer is generated based on the operation instruction. The dissimilarities we are looking for are circled. an excess of carry over ... Other dissimilarities that will hinder the recognition are noisy input from the device and the malleability of handwriting.

We use a graph-based representation commonly used to represent mathematical expression [START_REF] Mahdavi | Icdar 2019 crohme + tfd: Competition on recognition of handwritten mathematical expressions and typeset formula detection[END_REF]. By using such representation for both the input and the expected answer, it is possible to compute the Graph Edit Distance. It is a popular and general graph similarity computation [START_REF] Blumenthal | On the exact computation of the graph edit distance[END_REF] that searches the best vertices and edges correspondence between a pair of graphs. Two contributions are presented in this paper. We propose a way to compute and match several graph segmentation hypotheses to an instruction graph to select the most promising hypothesis. We propose a partial matching based on sub-graph isomorphism for our context of application to compute a better approximate matching and accelerate the complete Graph Edit Distance computation.

The paper is structured as follows. In Section II, we discuss the current state-of-the art on graph matching. We then define our graph representation and construction in Section III. In this, we present the transformation from raw input to a set of hypothesis graphs then we describe the process of matching multiple hypotheses with the expected answer graph. The results on an in-house Handwritten Arithmetical Operation (HAO) dataset are detailed in Section IV. We discuss future improvements in Section V. Fig. 2: Overview of our system. From the input, segmented hypothesis graphs are produced as well as an expected answer graph. The latter is matched to all hypothesis to find the best hypothesis to compute the GED. One result vertex is detected as missing and two result vertices have an incorrect label.

II. PROBLEM CONTEXT

Handwritten mathematical expression (HME) recognition has been a widely researched subject [START_REF] Mahdavi | Icdar 2019 crohme + tfd: Competition on recognition of handwritten mathematical expressions and typeset formula detection[END_REF] using end-to-end neural network or sequential solutions to transform the handwritten input into a valid mathematical expression. The recognized HME is usually represented by a graph with each vertex corresponding to a symbol and each edges representing a mathematical relationship. Figure 2 presents the workflow of our analysis system. The online handwritten strokes are transformed to a set of fuzzy visibility graphs [START_REF] Lods | Fuzzy visibility graph for structural analysis of online handwritten mathematical expressions[END_REF] corresponding each to a different segmentation hypothesis. An adapted similarity search is necessary to select the most promising hypothesis and put into correspondence the expected answer. For this purpose we provide a quick lookup on methods tackling the task of Graph Edit Distance (GED) computation.

The popular GED computation used in the literature is mainly based on a tree search. A vertex in the tree corresponds to a partial edition of the graph and a leaf corresponds to a complete edit path transforming a graph G 1 into a graph G 2 . The A* algorithm was the first used to complete this task but as a best-first search it is both computationally and memory expansive, and thus unusable on large graphs.

Systems for the inexact computation of the GED can often be computed faster by limiting the number of partial solutions [START_REF] Neuhaus | Fast suboptimal algorithms for the computation of graph edit distance[END_REF], by using heuristic for efficient computation [START_REF] Fischer | A hausdorff heuristic for efficient computation of graph edit distance[END_REF] or by using deep learning to learn an embedding function to map graph to vector for specific similarity measures [START_REF] Bai | Simgnn: A neural network approach to fast graph similarity computation[END_REF]. They are efficient and useful for indexing or classification in large databases, but an approximation of the matching could result in an incorrect matching and provide wrong feedback to the child.

A comparison of several algorithms on the exact computation of the GED is proposed in [START_REF] Blumenthal | On the exact computation of the graph edit distance[END_REF]. The standard A* Best-First Search is evaluated as well as the Depth-First Search (DF-GED) algorithm, presented in [START_REF] Abu-Aisheh | An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems[END_REF]. They also compare an improvement using sub-graph isomorphism (CSI-GED) generalised for non-uniform edit costs [START_REF] Blumenthal | Exact computation of graph edit distance for uniform and non-uniform metric edit costs[END_REF]. Another compared method uses Binary Linear Programming [START_REF] Lerouge | New binary linear programming formulation to compute the graph edit distance[END_REF] and the CPLEX mathematical solver. A lower bound can be computed either with Hungarian algorithm [START_REF] Riesen | Speeding up graph edit distance computation with a bipartite heuristic[END_REF] or by solving a Quadratic Assignment Problem [START_REF] Bougleux | Graph edit distance as a quadratic assignment problem[END_REF]. The paper comparing these algorithms concludes that it is now possible to compute the GED up to 16 vertices in reasonable time before frequently reaching time out. More recently a Beam-Stack Search was proposed in [START_REF] Chen | An efficient algorithm for graph edit distance computation[END_REF] but it only works for uniform edit costs which provide less expressiveness for graphs.

Given these methods, we propose to tackle our problem by using the DF-GED. The algorithm works for non-uniform edit costs which are adapted for arithmetical graphs as we can attribute more refined costs for edges with different mathematical relationships.

III. ANALYSIS OF ARITHMETICAL OPERATION

In this section we present our contribution. We first specify the graph representation and segmentation. Then we present the proposed hypothesis selection through pre-matching and approximate matching before computing the GED on the most promising hypothesis.

A. Hypothesis graphs segmentation Definition 1. An attributed handwritten operation graph is a tuple G = (V, E, µ, ξ) where V is the set of vertices and E is the set of edges such that ∀e = (i, j) ∈ E, i ∈ V and j ∈ V . µ : V → L v is the vertex labeling function that associates the label µ(v) to v ∈ V and where L v = [0..9, +, -] is the set of possible labels for the vertices. ξ : E → L e is the edge labeling function that associates a label ξ(e) to e ∈ E where L e = [Right, Lef t, Above, Below] is the set of labels for the edges.

The graph is sequentially constructed using three different classifiers namely for the strokes segmentation into symbols, the symbols classification and the classification of relationships between symbols. We propose to generate several segmentation hypotheses to not induce early segmentation mistakes. A threshold τ is defined to induce several segmentation hypotheses using the probabilities output of the segmentation classifier. The segmentation classifier is similar to the one used in [START_REF] Hu | Line-of-sight stroke graphs and parzen shape context features for handwritten math formula representation and symbol segmentation[END_REF]; the Random Forest classifier output is a segmentation rate for each pair of strokes. Using the threshold τ , we produce two different graphs if the segmentation probability is in between [0.5-τ ; 0.5+τ ]. The impact of τ on the segmentation will be evaluated in Section IV.

The relationship classifier presented in our previous work is also a Random Forest classifier using features computed from fuzzy landscapes [START_REF] Lods | Fuzzy visibility graph for structural analysis of online handwritten mathematical expressions[END_REF]. For the symbol classification, we use a more general deep neural network inspired by VGG [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF]. An iterative construction of the set of hypothesis graphs is straightforward and proposed in Algorithm 1.

Algorithm 1 Construction of the set of hypothesis graphs G

INPUT: S (set of strokes) V = {}, E = {}, G = {} for all s 1 , s 2 ∈ S do merge = SEGMENTATION(s 1 , s 2 ) [16] if (0.5 -τ ≤ merge ≤ 0.5 + τ ) then V += (s 1 , s 2 ) + (s 1 ) + (s 2 ) else if merge > 0.5 + τ then V += (s 1 , s 2 ) else V += (s 1 ) + (s 2 ) end if // create above a new vertex if stroke is not found, else merge with corresponding vertex end for for all v ∈ V do L v = µ(v) end for for all v 1 , v 2 ∈ V do E+ = ξ(v 1 , v 2 ) [6]
end for // for all unique set of vertices V' which covers all strokes, make a graph for all unique set of vertices V do G += (V , E V ) end for return G

B. Partial and complete matching

Given the operation instruction, we can generate an expected answer graph G EA . This graph is computed using the algorithmic rules for each type of arithmetic operation. Given the set of hypothesis graphs G and the expected answer graph G EA , we can compute the Graph Edit Distance to select the most promising hypothesis and find dissimilarities.

Definition 2. The Graph Edit Distance (GED) is a measure of similarity between two graphs G 1 = (V 1 , E 1 , µ 1 , ξ 1 ) and G 2 = (V 2 , E 2 , µ 2 , ξ 2
). An objective function is used to select the best edit-path, which is a set of operation o i applied on G 1 to transform the graph into G 2 . An operation o i is either a vertex or edge substitution, deletion or insertion. The objective function to minimize f is:

f (G 1 , G 2 ) = min (o1...o k )∈T (G1,G2) i=1 k c(o i ) where T (G 1 , G 2 ) is the set of all edit paths o = (o 1 , ..., o k ) that enables transforming G 1 to G 2 . c(.
) is a cost associated to each edit operation o i .

Cost function and matrix Using fuzzy landscapes representing each mathematical relationship, we are able to evaluate relative positioning of pairs of symbols. We compute a membership to each fuzzy landscapes for a given edge e (i,j) . The label L e is a set of tuples (D, V D ) where D ∈ [Right, Lef t, Above, Below] is an evaluated direction and V D is its associated value. Given this relative positioning, we can compute the differences between a pair of edges with the equation:

R(e (i1,j1) , e (i2,j2) ) = d∈D ||V 1 d -V 2 d || * 100 (1)
where e (i1,j1) and e (i2,j2) are respectively edges from graphs G 1 and G 2 .

Using our Eq. 1 to compute the differences between a pair of valued edges, it is possible to compute a single cost-matrix which takes into account both labels on vertices and their edges. This cost matrix dimensions are (n+m) X (m+n) where n is the number of vertices of a graph G 1 and m is the number of vertices of a graph G 2 . The matrix is constructed as follows:

c 1,1 .. c 1,m c 1→ ∞ ∞ .. .. .. ∞ .. ∞ c n,1 .. c n,m ∞ ∞ c n→ c 1← ∞ ∞ 0 0 0 ∞ .. ∞ 0 0 0 ∞ ∞ c m← 0 0 0
where c i,j is a substitution, c i← is a deletion and c i→ is an insertion. The cost is computed so that both the vertices labels, the edges values and the adjacent vertices labels are taken into account to improve the accuracy of the lower-bound computation, with:

c vi,vj = d(v i , v j )+min t∈T e (i,i ) ,e (j,j ) ∈t R(e (i,i ) , e (j,j ) )+d(v i , v j ) (2)
d(v i , v j ) =    if µ i ∈ [-, +] and µ j / ∈ [-, +] 50 else if µ i ! = µ j 10 else 0 (3)
d is a function evaluating the cost transformation of a vertex label to another. T is the set of all combinations of edges from vertices v i and v j and t is the corresponding list of pair of edges e(i, i ), e(j, j ). Depth First-GED (DF-GED) [START_REF] Abu-Aisheh | An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems[END_REF] is an efficient computation of the GED which uses upper and lower bounds with the Hungarian Algorithm and vertices sorting during the tree search. However it becomes computationally expensive on large graphs due to many backtracks in search for a better edit-path. Moreover with distant pairs of graphs such as bad segmentation hypotheses it is harder to prune large parts of the tree search due to a lower bound too inaccurate. To face this, we propose to do a quick partial matching by searching a sub-graph isomorphism to match parts of the excepted graph answer. This way it provides a more accurate lower bound estimation for hypothesis selection and speeds-up the DF-GED search by applying it on a reduced tree search.

Definition 3. Given the graph G 1 = (V, E, µ, ξ), a sub-graph G 1 is a tuple G 1 = (V 1 , E 1 , µ 1 , ξ 1 ) where V 1 ⊆ V and E 1 ⊆ E where ∀e i,j ∈ E 1 , i ∈ V 1 and j ∈ V 1 . The sub-graph G 1 is isomorphic to a graph G 2 if there exists a sub-graph G 2 such that d(G 1 , G 2 ) = 0.
In Figure 3 we display several ways to split the expected answer graph into smaller sub-graphs representing significant parts of the initial graph. The idea is to identify patterns in graphs that are more likely to be present in both graphs. Such pattern for arithmetical operations is the instruction recopy part; it is more likely to be found in the child's answer. Moreover, finding sub-graphs where most of the vertices have directed edges to other parts of the operation will make later pruning easier.

The task of searching for sub-graph isomorphism is NPcomplete. However, by using the Hungarian algorithm, we can find the best approximate matching between a sub-graph G EAi and the graph G. By applying this algorithm, if the edit path between G EAi and a sub-graph of G yield an edit-cost of 0, then an isomorphism is found. This edit path is saved for the complete graphs. Then the DF-GED can be computed on the set of vertices between G EA and G that are yet to be matched. Using this partial matching on each hypothesis graph, we can complete the partial edit-path using the Hungarian algorithm on each pair of graphs. The hypothesis with the lowest approximate matching cost is then selected to compute the DF-GED given the previous edit-path found.

Finding an isomorphism for large sub-graphs using the Hungarian algorithm output, even with refined cost, is unlikely. Instead it is possible to iterate this process over increasingly larger sub-graphs. A first sub-graph representing the instruction numbers (see Figure 3) is selected, then extended by adding the operators in a second step, and the carryovers in a third step. Two sub-graphs matching are evaluated in Section IV.

The complete matching is then processed using DF-GED given the partial matching found previously. This enables for both a direct tree search reduction on the number of vertices as well as a more precise lower-bound estimation thanks to edges directed on already matched vertices. The Algorithm 2 describes the process of the hypothesis selection before applying DF-GED.

IV. EXPERIMENTAL RESULTS

Our dataset of handwritten arithmetical operation (HAO) is composed exclusively of arithmetical additions. Samples from this dataset are displayed in Figure 4. An operation is considered incorrect when an expected symbol is missing Fig. 3: Example of different sub-graphs for the expected answer graph. We can quickly find a perfect isomorphism for the small sub-graph G EA1 with the graph hypothesis G. This sub-graph can be matched on the complete graph. It is possible iterate over larger sub-graphs to quickly find larger corresponding sub-graph isomorphism before computing the GED on the complete partially matched graph.

Algorithm 2 Hypothesis selection through partial matching

INPUT: G (set of hypothesis graphs), G EA (expected answer graph), G EA (set of selected sub-graphs), EP (edit path, initially empty) best cost = inf, best hyp = φ for G ∈ G do best path = {} for G EAi ∈ G EA do // for each selected sub-graph, we look for a perfect match using the Hungarian algorithm Generate matrix C with best path path = Hungarian(G,

G EAi , C) if cost(G, G EA , path) == 0 then best path = path end if end for approx cost = cost(G, G EA , best path) + Hungarian(G, G EA , C) if (approx cost<best cost) then
best cost = approx cost EP = best path best hyp = G end if end for // the DF-GED is computed on the remaining vertices given the edit path found for the best hypothesis return DF-GED(best hyp, G EA , EP) (number, operator or carry over), when an expected symbol is matched with an incorrect label or when symbols are in excess. Strokes in excess due to the noisy input devices are not counted as mistakes.

The training set of 200 operations was indiscriminately input by both adults and children and was used to train the segmentation and relation [START_REF] Lods | Fuzzy visibility graph for structural analysis of online handwritten mathematical expressions[END_REF] classifiers presented earlier. For the symbol classifier, a much larger training set from the CROHME 2019 competition [START_REF] Mahdavi | Icdar 2019 crohme + tfd: Competition on recognition of handwritten mathematical expressions and typeset formula detection[END_REF] was used. The test set of 200 operations is exclusively composed of handwritten operation written by primary school children (age 7 to 9). 110 out of 200 Evaluations are conducted on a machine with an Intel i5-8250U processor with 8GB of RAM. Running time are presented on log-scale and a time-out of 100 seconds was set for the computation on each operation. We have conducted two experiments. The first evaluates the contribution of the partial matching over the running time while the second evaluates both the impact of the segmentation threshold τ on the set of hypothesis graphs as well as the hypothesis selection running time.

We compare the running time of the standard DF-GED algorithm on the complete graphs to three different partial matching. We use the small sub-graph instruction (see Figure 3), a larger sub-graph with all vertices above the horizontal bar and then both sub-graphs. The DF-GED is then applied on the partially matched graphs. We evaluate the computation time for an increasing number of vertices. Figure 5 shows the consistent time improvement between the standard DF-GED and the reduced tree search of DF-GED thanks to the partial matching. In practice the DF-GED algorithm goes beyond the hour computation very fast, while the partial matching has still difficulties on larger graphs when no sub-graph isomorphism is found. In this case the system still reaches time-out on large arithmetical operations. On the set of 200 test operations, using only the DF-GED 20 operations are matched in less than 5 seconds (considered as reasonable for our use case) against 134 operations using both sub-graphs for partial matching. For the remaining operations, when no isomorphism is found, we could search for a partial matching with an edit-cost lesser than a fixed low threshold to avoid a time out on the complete GED.

For the second experiment we generate multiple segmentation hypotheses (Algorithm 1). To evaluate the impact of the segmentation threshold τ , we report in Table I for increasing values of τ the average and maximum number of hypothesis as well as the recall and precision. Our recall represents the presence of the ground-truth segmented hypothesis in the set of all generated hypotheses. Our precision corresponds Fig. 5: Average time execution for different complete matching for increasing graphs length.

to how often the selected hypothesis, using the best cost of approximate matching, was the ground-truth hypothesis.

The handwriting from children is complex and the same feedback could be produced from different segmented graphs. In the Figure 4, the top operation has a horizontal bar split into two strokes. Both strokes can be segmented either as a single symbol or as two separate symbols. In both cases, using the resulting edit-path we would find no mistakes in the operation (no symbols missing or wrong labels). However, to be more fair in our experiments, only one segmentation is considered correct for each operation (both strokes merged as a single horizontal bar in this example). As expected, with an increasing number of hypotheses, our recall is increased because the correct segmentation missed with τ = 0 is generated with a larger segmentation threshold τ . The precision also increases as we are able to select the correct segmented hypothesis out of the set of generated hypotheses. However we are not able to reach a perfect segmentation and selection, as incorrect segmentation hypotheses might induce the same edit cost (see Figure 4). Finally we evaluated the hypothesis selection over the increasing value of τ for different sizes of graphs. Figure 6 shows the computation time needed to achieve the hypothesis selection and the complete matching on the selected hypothesis. Using both partial and approximate matching we can quickly select the best hypothesis. With a larger value of τ the average running time is decreasing: when τ = 0 a more distant Fig. 6: Execution time for hypotheses selection and GED computation on the selected hypothesis for different sizes of graphs with a variable segmentation threshold τ . hypothesis might be selected and induce a costlier DF-GED. With multiple hypotheses a better suited graph is selected with a better partial matching and a cheaper computation for the DF-GED on the remaining graph. However, for operations with a lot of overlapping strokes, too many hypotheses might be generated, in which case the system will run out of time. The solution to avoid an exponential number of hypotheses would be to have a dynamic τ depending on the number of generated hypotheses.

V. CONCLUSION AND FUTURE WORKS

We tackle the problematic of the analysis of on-line handwritten arithmetical operations in the context of children mathematics teaching. We propose the use of an adapted valued graph representation and a corresponding expected answer graph transformation to put into correspondence both graphs. We produce several graphs hypotheses to cover up for the uncertainty of the recognition results. We use subgraph isomorphism to partially match as much as possible the instruction to reduce the complexity of the Graph Edit Distance computation. This partial matching enables us to both select the best hypothesis with the lowest approximated matching cost and prune large parts of the depth-first search tree for the complete matching.

The experiments on an in-house dataset of 400 arithmetical additions show that from multiple hypotheses, the best one is selected most of the time in reasonable time. We are able to compute the matching on large graphs and much faster. However, the increasing number of hypotheses is a problem that could be solved either by using a better segmentation classifier or by adapting the segmentation threshold at the cost of a lower recall. Given the nature of our process, an incremental partial matching stroke by stroke while the child is writing could reduce the number of promising segmentation hypotheses. This would enable us to compute the Graph Edit Distance for future experiments on larger operations such as multiplications and divisions.

Fig. 4 :

 4 Fig. 4: Samples from the HAO dataset and their respective generated segmentation hypothesis.

TABLE I :

 I Evolution of the number of hypotheses given an increasing segmentation threshold τ , and the corresponding recall and precision.

	τ	# of hypotheses Recall Precision
		mean	max
	0	1	1	0.825	0.825
	0.05	1.16	4	0.860	0.850
	0.10	1.7	32	0.870	0.860
	0.15	3.04	272	0.885	0.865
	0.20 17.42	2880	0.935	0.900

ACKNOWLEDGMENT

With the support from the LabCom ScriptAndLabs founded by the ANR ANR-16-LVC2-0008-01. With the support from the ANRT.