Iordan Iordanov

LORIA, INRIA Nancy -Grand Est, Université de Lorraine, CNRS UMR 7503, France iordan.iordanov@loria.fr Delaunay triangulations and their dual objects, Voronoi diagrams, have been widely studied and have many uses in a vast array of disciplines. In the Euclidean plane, the Delaunay triangulation of a set of points P is the partition of the convex hull of P into triangles whose circumscribing disk does not contain any point of P in its interior. This definition was extended to other settings, including closed Euclidean manifolds [START_REF] Caroli | Delaunay triangulations of closed Euclidean d-orbifolds[END_REF]. We study Delaunay triangulations of a closed orientable hyperbolic surface M g of genus g. The surface M g is defined as the quotient of the hyperbolic plane under the action of the group Γ generated by the hyperbolic translations that identify opposite sides of the regular 4g-gon F g centered at the origin.

The hyperbolic case is more challenging than the Euclidean case, since hyperbolic translations do not commute. For a finite set of points P in the hyperbolic plane, the set ΓP of images of its elements under the action of Γ is infinite, and, therefore, also its Delaunay triangulation; if the projection of this triangulation onto the surface M g is a simplicial complex, then it is the Delaunay triangulation of M g defined by the points in P [START_REF] Bogdanov | Delaunay triangulations on orientable surfaces of low genus[END_REF].

A sufficient validity condition so that this projection is a simplicial complex is that δ P < 1 2 sys(M g ), where δ P is the diameter of the largest disks not containing any point of ΓP , and sys(M g ) is the systole of M g , i.e., the minimal length of a non-contractible loop on M g [START_REF] Bogdanov | Delaunay triangulations on orientable surfaces of low genus[END_REF]. Based on this condition, we generalize the algorithm for closed Euclidean manifolds to the case of the hyperbolic surface M g : (a) construct a triangulation of M g defined by a set of "dummy" points Q g that satisfy the validity condition; (b) insert the points of P into the triangulation; (c) remove from the triangulation every point in Q g whose removal does not violate the validity condition.

We introduce a data structure, relying on the following inclusion property: for a set of points P satisfying the validity condition, a face of the Delaunay triangulation of ΓP with at least one vertex inside F g is contained in the union of F g and its adjacent images under the action of Γ. This property allows us to implement the algorithm. We present several different strategies for the generation of sets of dummy points Q g that satisfy the validity condition. We describe the construction of the Delaunay triangulation of M g defined by Q g , as well as the details of subsequent point insertion and removal. We discuss the algebraic expressions arising from the geometric predicates used by the algorithm, and we report experiments.

This work generalizes previous work tailored to the Bolza surface M 2 , the most symmetric hyperbolic surface of genus 2, for which the Dirichlet region of the origin is a regular octagon [START_REF] Bogdanov | Delaunay triangulations on orientable surfaces of low genus[END_REF][START_REF] Iordanov | Implementing Delaunay triangulations of the Bolza surface[END_REF].

Joint work with: Matthijs Ebbens, Monique Teillaud and Gert Vegter. This talk is complementary to the talk of M. Ebbens [START_REF] Ebbens | Systole of regular hyperbolic surfaces with an application to Delaunay triangulations[END_REF], who treats the mathematical aspects of the algorithm. Among others, he provides an explicit expression for sys(M g ), presents a proof for the inclusion property, and performs an analysis of the cardinality of the dummy point sets Q g in terms of the genus g.

This work was partially supported by the grant ANR-17-CE40-0033 of the French National Research Agency ANR (project SoS, https://members.loria.fr/Monique.Teillaud/collab/SoS/), and by the INRIA Associate Team Astonishing (https://members. loria.fr/Monique.Teillaud/collab/Astonishing/).


Systole of regular hyperbolic surfaces with an application to Delaunay triangulations * Matthijs Ebbens Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen, The Netherlands y.m.ebbens@rug.nl

Algorithms for Delaunay triangulations of point sets in Euclidean spaces are widely known. In the literature, the incremental algorithm, which inserts the points one by one, has been extended to periodic point sets. If we consider the Delaunay triangulation of a periodic point set in Euclidean space, and project this triangulation to the space of orbits, the result may be non-simplicial. Namely, if for example both endpoints of an edge project to the same point, then we obtain a loop. This is avoided when the inequality sys(M) > 2δ P is satisfied, where sys(M) denotes the systole of the orbit space M, i.e. the length of the shortest non-contractible curve, and δ P the diameter of the largest disk not containing any points from the input set P in its interior. To make sure that this condition is satisfied, the triangulation can be initialized with a dummy point set that is added to the input set. At the end, the dummy points are removed (if possible).

We will consider periodic Delaunay triangulation in the hyperbolic plane. Hyperbolic translations do not commute, unlike Euclidean translations, which makes the situation more complicated. Furthermore, in general the systole of a hyperbolic surface is unknown. Even though there exists an upper bound of order O(log g), where g denotes the genus, lower bounds exist only for specific families of surfaces, often constructed using algebraic methods; a general lower bound does not exist. The exact value of the systole is known only for a few specific hyperbolic surfaces. This makes checking the condition mentioned above difficult.

One of the hyperbolic surfaces for which the systole is known, is the Bolza surface, the most symmetric hyperbolic surface of genus 2 to consider. Here the regular hyperbolic octagon is a fundamental region for the group of translations, i.e. it represents the space of orbits in a natural way. In [START_REF] Bogdanov | Delaunay triangulations on orientable surfaces of low genus[END_REF] the incremental algorithm is extended to the Bolza surface. In this case, the triangulation is initialized with a dummy point set consisting of 14 points. An implementation is presented in [START_REF] Iordanov | Implementing Delaunay triangulations of the Bolza surface[END_REF].

In this talk, we will look at the surfaces M g of genus g corresponding in a similar way to the regular hyperbolic 4g-gon. We will show that the systole of M g is given by cosh( 12 sys(M g )) = 1 + 2 cos( π 2g ) to be able to verify the inequality given above. The proof relies for the most part on hyperbolic trigonometry. As far as we know, this is the first instance where the exact value of the systole is computed for a family of hyperbolic surfaces. Secondly, we will present several strategies for finding a set of dummy points based on Delaunay refinement. By using Delaunay refinement directly we obtain a point set with cardinality of order Θ(g). Instead, we can use the symmetry of the fundamental region to duplicate points in the dummy point set, which increases the order to Θ(g log g). A third strategy explicitly computes a point set and the corresponding Delaunay triangulation. For all strategies we will prove that the resulting point set satisfies the condition mentioned above.

Joint work with: Iordan Iordanov, Monique Teillaud, Gert Vegter. This talk is closely related to the talk of I. Iordanov [START_REF] Iordanov | Delaunay triangulations of regular hyperbolic surfaces[END_REF], who will discuss the algorithm for computing Delaunay triangulations in more detail.

This work was partially supported by the grant ANR-17-CE40-0033 of the French National Research Agency ANR (project SoS, https://members.loria.fr/Monique.Teillaud/collab/SoS/), and by the INRIA Associate Team Astonishing (https://members. loria.fr/Monique.Teillaud/collab/Astonishing/).


L Jecker
email: loic.jecker@onera.fr

O Vermeersch

H Deniau

E Croner

G Casalis

LAMINAR KINETIC ENERGY MODEL BASED ON THE KLEBANOFF-MODE DYNAMIC TO PREDICT BYPASS TRANSITION ON A TURBINE BLADE

This paper deals with the application of a bypasstransition model developed by Jecker et al. (2017) (JVD), using the laminar kinetic energy (LKE) concept. JVD formulation is written to model the Klebanoff-mode dynamic with an original definition of the LKE and a physics-based associated equation. The application case is the von

Bypass transition scenario

The bypass transition is characterised by the formation of low-frequency, high-velocity streak-shaped disturbances -up to 30% of the mean-flow velocity, [START_REF] Andersson | Optimal disturbances and bypass transition in boundary layers[END_REF] -called Klebanoff modes (K. modes). Theses instabilities are considered by several authors as the key phenomenon of the bypass transition, see for instance [START_REF] Durbin | Perspectives on the Phenomenology and Modeling of Boundary Layer Transition, Flow, Turbulence and Combustion[END_REF].

The bypass-transition scenario is decomposed into five steps, Jacobs et al. (2001). The 1 st step is the receptivity step and describes how the free-stream turbulence (FST) enters the boundary layer. These vortices then interact with the boundary-layer shear to form the streaks (step 2). This is called the lift-up mechanism, identified by [START_REF] Landahl | A note on an algebraic instability of inviscid parallel shear flows[END_REF]. It consists in a mean-flow momentum displacement caused by the wall-normal part of the FST: the higher velocities from the upper part of the boundary layer move towards the wall while the lower velocities rise to the boundary layer edge. When the streak reaches a significant amplitude, it is destabilised (step 3). The 4 th step consists in the formation of turbulent spots by the unstable streaks' breakdown. These spots may grow or disappear and finally occupy the whole boundary layer (step 5).

Development of a new model Klebanoff mode modelling

A bypass-transition model was developed by the authors, [START_REF] Jecker | A New Laminar Kinetic Energy Model for RANS Simulations of Bypass Transition[END_REF], based on the LKE con-cept proposed by [START_REF] Mayle | The Path to Predicting Bypass Transition[END_REF] and popularised by [START_REF] Walters | A Three-Equation Eddy-Viscosity Model for Reynolds-Averaged Navier-Stokes Simulations of Transitional Flow[END_REF] (WC) with their k T -k L -ω formulation. WC formulation uses the Boussinesq hypothesis for both turbulent and laminar velocity fluctuations. They defined two different eddy viscosities based on a separation between the "large" coherent eddies from the small turbulent scales. The authors chose to change the definition of the LKE. They defined the LKE as the streamwise kinetic energy of the K. modes. They wrote a transport equation for the LKE k L from the linearised Navier-Stokes equations, satisfied by the streamwise velocity fluctuation u st of the K. modes. The k L production term P k L is written to model the lift-up phenomenon in the laminar boundary layer, so that it is proportional to P k L ∝ -u st v . The wall-normal velocity fluctuation energy v 2 is considered proportional to the turbulent kinetic energy k T . This leads to :

k L = u 2 st 2 , P k L = α k L k T S. (1)
S is the strain rate tensor magnitude and α = 0.063 is a constant of the model. The transition onset is detected by a criterion, comparing the LKE value to the mean-flow shear, in accordance with Jacobs & Durbin (2001) analysis of streak destabilisation on direct simulations:

k L + 3k T νS > C onset . (2)
C onset = 11 is a constant of the model. The addition of 3k T to k L is done so that the criterion is still verified in the turbulent boundary layer. In the transition region, k L is more than ten times higher than k T , this addition thus does not influence the transition onset position.

Transition onset calculation

Once the transition criterion is verified, the energy transfer from the laminar fluctuations -K. modes (k L ) -to the turbulent spots (k T ) is controlled by a transfer term T k , defined as:

T k = f tr C T k L S.
(3)

C T = 0.015 is a constant of the model. This term will appear both in k L and k T equations with opposite sign.

It involves a transition function f tr , calculated with an additional transport equation:

Dρβ Dt = ρC β f crit (1 -β) S, (4)
where f crit = 1 if the criterion is verified -f crit = 0 otherwise -and C β = 0.013 is a constant of the model. The transition function is thus defined as the maximum of β along the wall-normal direction:

f tr = max d (β) , (5)
with d the distance to the wall. Additionally, a turbulent indicator is used to separate the laminar zone to the transitional and turbulent regions. It is defined as:

β BP = 1 -e -100ftr . (6)
In the laminar boundary layer, β BP = 0; once the criterion is verified, β BP rises abruptly to 1.

Influence of K. modes on the mean flow

As mentioned previously, K. modes can reach large amplitude so that they can deeply influence the mean flow. This impact on the mean flow is accounted for by an anisotropic Reynolds tensor:

u i u j = u i u j + u i u j st , (7)
u i u j st =   2k L -α k L k T 0 -α k L k T 0 0 0 0 0   . (8)
The turbulent tensor u i u j is given by the turbulence modelling.

In the LS89 test case, only the heat transfer was measured. So far JVD model did not contain a heat transfer modelling. As a first approach, it is proposed to model the heat flux vector u i θ with a Simple Gradient Diffusion Hypothesis (SGDH). It is based on a modified turbulent diffusivity α θ taking account of a streak effect:

-u i θ = α θ ∂T ∂x i , α θ = ν t P r t + C θ 2k L SP r t , (9)
with the turbulent Prandtl number P r t = 0.85.

Full formulation

The turbulence modelling rests on the Boussinesq hypothesis:

u i u j = 2 3 k T δ ij -2ν T S ij , (10)
with the following eddy viscosity:

ν T = f ν C µ f 2 W k T ω . ( 11
)
The f ν , C µ and f W functions come from the [START_REF] Walters | A Three-Equation Eddy-Viscosity Model for Reynolds-Averaged Navier-Stokes Simulations of Transitional Flow[END_REF] model:

f ν = 1 -exp - f W √ R T A ν , R T = k T νω , (12)
C µ = 1 A 0 + A S Sω -1 , λ T = √ k T ω , (13)
λ ef f = min (C λ d, λ T ) , f W = λ ef f λ T 2/3 . (14)
The equation for k L , k T and ω are the following:

                   D (ρk L ) Dt = ρP k L -ρT k -2µ ∂ √ k L ∂x j 2 + ∂ ∂x j µ ∂k L ∂x j , D (ρk T ) Dt = ρP k T + ρT k -ρωk T -2µ ∂ √ k T ∂x j 2 + ∂ ∂x j µ + ρα T σ k ∂k T ∂x j , D (ρω) Dt = C ω,1 ρω k T P k T + ρ C ω,R f W -1 ω k T T k -ρC ω,2 f 2 W ω 2 + ∂ ∂x j µ + ρα T σ ω ∂ω ∂x j . ( 15
)
The k L production term is defined as:

P k L = [(1 -β BP ) + β BP f L ] α k L k T S, (16)
with f L a damping function so that P k L disappears in the turbulent region:

f L = max (0, 1 -1.1f tr ) . ( 17
)
The turbulent kinetic energy (TKE) k T production term is written: C µ,std = 0.09 the TKE growth in the transition region:

P k T = (1 -β BP ) k T ω +β BP f tr f ν C µ f 2 p k T ω S 2 . ( 18
C ω,1 = 0.44 C λ = 2.495 C ω,2 = 0.92 A ν = 6.75 C ω,R = 1.5 σ k = 1.0 σ ω = 1.17 A 0 = 4.04 A S = 2.12 α = 0.063 C onset = 11 C T = 1.5 × 10 -2 C β = 1.3 × 10 -2
f p = max f W , 1 -0.7 exp - Re y 37 , Re y = y √ k T ν . ( 19
)
The turbulent viscosity used in the turbulent diffusion is defined as:

α T = f ν C µ,std f 2 W k T ω . ( 20
)
The constants of the model are gathered in Table 1.

The model was validated and its constants were calibrated using the ERCOFTAC T3 -A, B and C1 to C5 -cases, [START_REF] Roach | The influence of a turbulent free-stream on zero pressure gradient transitional boundary layer development. Part I: Test cases T3A and T3B, Numerical simulation of unsteady flows and transition to turbulence[END_REF]. To illustrate the results obtained, the skin friction coefficients measured in three T3 cases is presented in figure 1 3 Application to a turbine blade JVD model was applied to the VKI LS89 turbine blade, [START_REF] Arts | Aero-thermal investigation of a highly loaded transonic linear turbine guide vane cascade, VKI Technical Report Cac[END_REF]. This case is frequently used to investigate turbomachinery transition models. Three configurations were tested: MUR217, MUR235 and MUR237. In these three cases, the elevation of the heat transfer in the pre-transitional zone seems to indicate that strong disturbances may exist in this region. These disturbances could be streaks.

Table 2 presents the inlet total pressure P i 1 , the outlet static pressure P 2 and the inlet turbulence level Tu 0 in the tested cases. The inlet Mach number in the three cases is M = 0.15. The MUR217 and MUR235 have approximately the same inlet total pressure and the same outlet static pressure, but a different turbulence level.

Case

P i 1 (Pa) P 2 (Pa) Tu 0 MUR217 183500 104500 3.9% MUR235 182800 104900 5.3% MUR237 175300 117900 5.3%

Turbulence inlet conditions

Experimentally, the FST is generated by a grid, [START_REF] Arts | Aero-thermal investigation of a highly loaded transonic linear turbine guide vane cascade, VKI Technical Report Cac[END_REF]. In order to have different values of inflow turbulence Tu 0 at 55 mm upstream the leading edge, the grid was moved at different locations. This allowed to obtain four distinct turbulence levels, 5.3%, 3.9%, 3.1% and 2.5%, Fontaneto (2014). The turbulence levels are plotted in figure 2 as functions of the relative grid distance x.

The turbulence inlet parameters, k 0 and ω 0 , are calculated in order to fit the measured turbulence evolution. The knowledge of the turbulence level as a function of the relative grid distance x enables the determination of the turbulence dissipation rate. Far upstream from the model, the equations for k T and ω become:

U 0 ∂k T ∂x = -k T ω, U 0 ∂ω ∂x = -C ω,2 ω 2 .
(21

)
This system has the following solutions:

ω ω 0 = 1 + C ω,2 ω 0 x U 0 -1 , k T k T,0 = ω ω 0 1/Cω,2 . (22)
The inlet condition can be written on Tu and µ t /µ with the following definitions:

Tu = 1 U 2 3 k T , µ t = ρ C µ,std k T ω . ( 23
)
The three configurations have approximately the same inlet velocity of U 0 = 61 m/s. The choice of µ t /µ = 140 for an inlet turbulence level of Tu 0 = 5.3% fits the measurements, as displayed in figure 2. The inlet condition for the MUR217 and MUR235 configurations is consequently Tu 0 = 5.3% and µ t /µ = 140 at a distance of 55 mm upstream the leading edge.

The inlet condition for the MUR217 configuration is Tu 0 = 3.9% and µ t /µ = 132 at the same location.

Streak diffusivity calibration

The coefficient C θ used in equation ( 9) to model the influence of the streaks on the thermal fluxes is not yet determined. Since no academic cases are available in the literature, this constant was determined using one of the LS89 cases. C θ = 300 was chosen so that C θ (2k L /S) is -in the pre-transitional zone -of an order of magnitude comparable to ν t -in the turbulent boundary layer.

Numerical results

Figure 3 represents the heat transfer measured for the three configurations, and calculated with JVD model in elsA software, [START_REF] Cambier | elsA -An efficient object-oriented solution to CFD complexity[END_REF]. First, the simulations underpredict the heat transfer of about 150 W/m2/K in the laminar region. This shift will not be discussed here since it is not caused by the transition model. These results are used qualitatively to analyse the behaviour of JVD model.

Numerically the transition onset is predicted at the same position in the MUR217 and MUR235 cases and corresponds to the shock location -around s ∼ 0.07 m, with s the curvilinear abscissa -as represented by the evaluation of the isentropic Mach number M is in figure 4:

M is = 2 γ -1 p i p γ-1 γ -1 . ( 24
)
The total pressure is written p i , p represents the static pressure and γ = 1.4 the ratio of specific heats. Experimentally, the heat-transfer measurements on the MUR235 configuration have the following features, not reproduced by the simulation: an earlier transition, a pre-transitional region where the heat transfer begins to rise and a wider extent of the transitional region.

In the MUR237 case a pre-transitional region is also observable. It is predicted by the model, although the heat-transfer is sightly underestimated. Contrary to the MUR217 and MUR235 configurations, the transition on MUR237 is not triggered by the shock. The transition is predicted by the model, however too late and the transition extent is too short. On the pressure side, the MUR217, MUR235 and MUR237 configurations show a similar behaviour.

The heat transfer first decreases as the flow accelerates, then increases for |s| > 0.025 m until it reaches a maximum for |s| ∼ 0.055 m and decreases again in the trailing edge region. The heat transfer predicted by the simulation decreases also with the flow acceleration. However, it begins to rise earlier and reaches its maximum earlier. This local maximum happens later in the MUR217 case than in the MUR235 and MUR237 cases. After a second decrease it rises once again.

- (1990).

Discussion

The results of the application of JVD model on the LS89 turbine blade show two discrepancies. First, the model does not accurately predict the heat transfer elevation in the pre-transitional region on the MUR235 and MUR237 configurations. Secondly, the model predicts too late a transition onset and too short a transition region extent on the same configurations.

Pre-transitional region

The cause of the elevation of the heat transfer in the pre-transitional region is not well understood. According to Cac ¸ão Ferreira et al. (2017), these disturbances are associated to turbulent spots. However, another possibility is that streaks are responsible for this heat transfer elevation. There are consequently two questions that need to be resolved. Firstly, could streaks be responsible for this augmentation? Secondly, is the influence of the streaks on the heat transfer well taken into account by the model?

In order to answer the first question, the streak amplitude max U e is displayed in figure 5 for the three tested configurations. The model predicts in the MUR237 case a streak amplitude of a similar order of magnitude than the one calculated in the ERCOFTAC T3C5 case, figure 1. Streaks are thus predicted by the model in the laminar boundary layer. Moreover, a raise of the streak amplitude occurs at the same position than an elevation of the heat transfer is noticed on the experiments, s ∼ 0.027 m. The existence of streaks is thus predicted by the model, with an amplitude comparable to the one observed in academic cases. Streaks can influence the heat transfer through two mechanisms, that will be considered in order to answer the second question. The first one is an indirect mechanism, it consists in the modification of the mean velocity profile due to the streaks. The influence of the streaks on the mean velocity flow is noticeable on the shape factor or on the skin friction coefficient evolution in the laminar boundary layer in bypass transition cases. Since the mean velocity influences the heat transfer, and since the streaks influence the mean velocity flow, the streaks indirectly influence the heat transfer. This mechanism is taken into account by the model through the modified Reynolds tensor, equation (8). The second effect comes from the fact that streaks are streamwise vortices, they may thus increase the mixing in the near wall region and consequently increase the heat transfer. This influence is modelled through the u i θ term, equation ( 9), which has not been calibrated using academic cases in JVD model.

Transition onset and extent

The predicted streak amplitude in the MUR237 case is comparable to the one predicted in the ERCOF-TAC T3C5 case in figure 1. On the contrary, the predicted streak amplitude in the MUR217 case is too low for the criterion to detect a transition. Moreover, the u st /U e value calculated for MUR235 at the transition onset is close to the one observed for MUR237. It is not high enough so that the criterion detects a transition, it is however not far. The streamwise evolution of the skin friction coefficients displayed in figure 1 shows a similar behaviour in the T3A (a) and T3C5 (c) cases, the transition onset is predicted slightly too late and the transition extent is too short. A possible modification of the model could be to lower the criterion threshold value and to slow down the transition dynamic.

Conclusion

JVD model is a RANS bypass-transition model based on the dynamic of Klebanoff modes which is represented by an additional transported variable -the laminar kinetic energy, k L . It has been validated on academic configurations and showed a physically accurate dependence to the turbulence intensity of the external flow, to its turbulent length scale and to the external pressure gradient, [START_REF] Jecker | A New Laminar Kinetic Energy Model for RANS Simulations of Bypass Transition[END_REF]. The model was for the first time applied to a turbine blade test case, three configurations of the LS89 case were simulated. The numerical results showed differences with the heat transfer measurements. The transition onset is predicted too late, the transition extent is too short and the heat transfer elevation in the pretransitional region is not accurately predicted. However, the streak amplification is predicted in the laminar zone. A lower criterion threshold value and a slower transition dynamic could improve the transition prediction. Concerning the heat transfer elevation in the pre-transitional region, the modelling of the streak's direct influence on the temperature is probably responsible for this difference. An improvement could consist in writing an additional transport equation for the u st θ term, as done by [START_REF] Vermeersch | Klebanoff-mode modeling and bypass-transition prediction[END_REF].

  Figure 1: Superior part: evolution of the skin friction coefficient for ERCOFTAC T3 cases, T3A (a) and T3B (b) with a zero pressure gradient (ZPG) and T3C5 (c) exposed to an adverse pressure gradient (APG). Inferior part: evolution of the wall-normal maximum of the velocity fluctuations in the same cases.

  . The T3A (a) and T3B (b) cases have a zero pressure gradient and are subjected to different FST levels. The T3C5 case (c) has an adverse pressure gradient, it is the most representative of the flow around a turbine blade. The measurements are compared to the predictions of JVD model, WC model and to the Abu-Ghannam and Shaw (1980) criterion (AGS). The wall-normal maximum of the longitudinal velocity perturbation measured in the ERCOFTAC T3A, T3B and T3C5 cases is presented in the inferior part of the figure 1. It is compared to the calculated normalised amplitude of the streak u st , of the turbulence u and of the total velocity fluctuation u st + u .

Figure 2 :

 2 Figure 2: Inflow turbulence level Tu0 in the LS89 case as a function of the relative grid distance x, Fontaneto (2014). The calculation is done with Tu0 = 5.3%, U0 = 61 m/s and µt/µ = 140.

Figure 3 :Figure 4 :

 34 Figure 3: Heat transfer for three configurations of the VKI LS89 turbine blade, Arts et al. (1990). The symbols depict the measurements and the lines the calculations.

Figure 5 :

 5 Figure 5: Streak amplitude in the tested LS89 cases.

Table 1 :

 1 The constants for the turbulent region -from Wal-

ters & Cokljat (2008)

-are displayed on the superior table, and the constants for the laminar and transition regions on the inferior table.

Table 2 :

 2 Numerical parameters for the VKI LS89, Arts et al.

	(1990)

Acknowledgments

This work has been founded by SAFRAN group.


Brahim Douar
email: douar@lirmm.fr

Chiraz Latiri
email: chiraz.latiri@gnet.tn

Michel Liquière

Yahya Slimani
email: yahya.slimani@fst.rnu.tn

Michel Liquiere
email: liquiere@lirmm.fr

A Projection Bias in Frequent Subgraph Mining Can Make a Difference

Keywords: Graph mining, Projection operators, Graph classification

The aim of the frequent subgraph mining task is to find frequently occurring subgraphs in a large graph database. However, this task is a thriving challenge, as graph and subgraph isomorphisms play a key role throughout the computations. Since subgraph isomorphism testing is a hard problem, subgraph miners are exponential in runtime. To alleviate the complexity issue, we propose to introduce a bias in the projection operator and instead of using the costly subgraph isomorphism projection, one can use a polynomial projection having a semantically-valid structural interpretation. This paper presents a new projection operator for graphs named AC-projection, which exhibits nice theoretical complexity properties. We study the size of the search space as well as some practical properties of the projection operator. We also introduce a novel breadth-first algorithm for frequent AC-reduced subgraphs mining. Then, we prove experimentally that we can achieve an important performance gain (polynomial complexity projection) without or with non-significant loss of discovered patterns in terms of quality.

Introduction and Motivation

Given an increasing and urgent need to analyze large amount of structured data such as chemical compounds, proteins structures, XML documents, to cite but a few, graph mining has become a compelling issue in the data mining field [START_REF] Cook | Mining Graph Data[END_REF] . Indeed, discovering frequent subgraphs, i.e., discovering subgraphs which occur frequently enough over the entire set of graphs, is a thriving challenge due to their exponential number. Indeed, based on the Apriori principle 1 , a frequent n-edge graph may contain 2 n frequent subgraphs. This raises a serious problem related to the exponential search space as well as the counting of complete sub-patterns while the kernel of frequent subgraph mining is subgraph isomorphism test. The latter has been proved to be NP-complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] . To alleviate the complexity issue, some heuristics based on an incomplete search or some limitations on the class of subgraphs must be introduced.

In this paper, we study an innovative projection operator meant to replace the costly subgraph isomorphism. In the second section, we provide a brief literature review of the subgraph mining field. Then, we present the AC-projection operator initially introduced in [START_REF] Liquiere | Arc consistency projection: A new generalization relation for graphs[END_REF] , as well as its very interesting properties. We propose an efficient graph mining algorithm using the AC-projection operator. Finally, we study the relevance of the AC-reduced patterns for the supervised graph classification.

Notice that, this paper is a wide extension of a previous work we carried out 4 .

Frequent Subgraph Mining

Given a database consisting of small graphs, for example, molecular graphs, the problem of mining frequent subgraphs is to find all subgraphs that are subgraph isomorphic with a large number of example graphs in the database. In this section, we recall some preliminary concepts as well as a brief review of literature dedicated to frequent subgraph mining.

Basic definitions

Definition 2.1. (Labeled Graph) A labeled graph can be represented by a 4-tuple, G = (V, A, L, l), where

• V is a set of vertices, • A ⊆ V × V is a set of edges,
• L is a set of labels,

• l : V ∪ A → L, l is a function assigning labels to the vertices and the edges.

Definition 2.2. (Induced subgraph) A subgraph S of a graph G is said to be induced if, for any pair of vertices x and y of S, (x, y) is an edge of S if and only if (x, y) is an edge of G. In other words, S is an induced subgraph of G if it has all the edges that appear in G over the same vertex set.

For example, we can see in Figure 1 that G2 is an induced subgraph of G1 while G3 is not an induced one.

f : V (G 1 ) → V (G 2 ), such that ∀x ∈ V (G 1 ), l(x) = l(f (x)), and ∀(x, y) ∈ A(G 1 ), (f (x), f (y)) ∈ A(G 2 ) and l(x, y) = l(f (x), f (y)). A subgraph isomorphism from G 1 to G 2 is an isomorphism from G 1 to a subgraph of G 2 .
Definition 2.4. (Graph projection) For two graphs, G 1 (V 1 , A 1 ) and G 2 (V 2 , A 2 ), we call graph projection, the mapping which maps each vertex of G 1 into one or many vertices of G 2 . This defines the generalization order between our graphs.

In this paper, we present a new projection operator (AC-projection) having a polynomial complexity and good properties. It is worth to mention that, given two graphs G 1 and G 2 , if there is no AC-projection between G 1 and G 2 , then there will not be a graph homomorphism between them, then there will also not be a subgraph isomorphism. Definition 2.5. (Frequent Subgraph Mining) Given a graph dataset, GS={G i | i = 0 . . . n}, and a minimal support (minSup), let

ς(g, G) = 1 if there is a projection from g to G 0 otherwise. σ (g, GS) = Gi ∈ GS ς(g, G i ) σ (g, GS)
denotes the occurrence frequency of g in GS, i.e., the support of g in GS. Frequent subgraph mining aims at finding every graph g such that σ (g, GS) is greater than or equal to minSup. We note that the value of the support based on AC-projection is an upper bound of the original graph isomorphism. In fact, if there is no AC-projection between two graphs G 1 and G 2 , then there will be neither graph homomorphism; nor subgraph isomorphism between them.

Known frequent subgraphs miners are based on this definition and deal with the special case where the projection operator is a subgraph isomorphism.

Related Work

Algorithms for frequent subgraph mining are based on two patterns discovery paradigms, namely breadth-first search and depth-first search. Most of these algorithms employ different ways for candidate generation and support counting. An interesting quantitative comparison of the most cited subgraph miners is given in [START_REF] Wörlein | A quantitative comparison of the subgraph miners mofa, gspan, ffsm, and gaston[END_REF] .

Breadth-first Approaches

Algorithms, that follow a breadth-first order to find frequent subgraphs, take advantage of the well-known Apriori 1 levelwise strategy. In the literature, pioneer and most cited approaches are Agm 9 and Fsg 10 .

The particularity of Agm is that it only mines frequent induced subgraphs in the graph database, as well as dealing with graphs having self-loops. During the mining process, the algorithm extends subgraphs by adding one vertex at each level. Experiments, reported in [START_REF] Inokuchi | Complete mining of frequent patterns from graphs: Mining graph data[END_REF] , show that Agm achieves relatively good performances for synthetic dense datasets. Compared to more recent approaches, with the exception of handling self-loops, Agm is an obsolete mining approach with very poor scalability power.

Thus, a more efficient breadth-first approach named Fsg 10 has been introduced. The latter algorithm is also based on the same level-by-level expansion exactly as did Apriori but in the context of labeled graphs. Fsg essentially differs from the Agm approach by adding one edge at a time (instead of one vertex for Agm) allowing to efficiently generate the candidates.

Various optimizations, partially based on labels, vertex degrees and hierarchical structure of the search space, have been proposed for canonical form computation, candidate generation and counting. These optimizations have allowed it to scale to large graphs. The result of the strong dependency of Fsg to labels and vertex degrees etc., makes the performance of Fsg to be relatively worse for graph database with few vertex and edge labels. This is due to the exponential complexity of the subgraph isomorphism test that badly influenced the overall performance.

Besides, if we have sufficiently vertex and edge labels, then Fsg will be able to achieve good performance and to scale linearly with the database size.

In this paper, we are particularly interested in this approach. In fact, we propose a frequent subgraph mining approach based on the Fsg version and using a novel operator for the support counting process as well as an innovative graph reduction algorithm.

A projection bias in frequent subgraph mining can make a difference 5

Depth-first Approaches

Main depth-first approaches are restricted to find connected subgraphs and traverse the search lattice in a vertical way. In this respect, several algorithms were proposed in the literature. We give in the following a brief description of the two most cited ones, namely gSpan [START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF] and Gaston 14 algorithms.

The gSpan algorithm [START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF] is based on a canonical representation for graphs, called dfs-code. A dfs-traversal of a graph defines an order in which the edges are visited. The concatenation of edge representation in that order is the graph's dfs-code. In order to prevent isomorphic subgraphs (duplicates) generation, gSpan computes the canonical (lexicographically smallest) dfs-code from each refinement using a series of permutations. Refinements with non-minimal dfs-code can be pruned. The gSpan stores appearance lists for each subgraphs. Explicit subgraph isomorphism testing has to be done on all graphs in these appearance lists.

Instead of storing appearance lists for each subgraphs, the Gaston algorithm 14 stores all embeddings a to generate only refinements that actually appear and to achieve faster subgraph isomorphism testing. The main idea behind this algorithm is that there are efficient ways to enumerate paths and trees. By looking for subgraphs that are paths or trees first, and by only dealing with general graphs with cycles at the very end, a large fraction of the work can be done efficiently.

Indeed, Gaston will face the NP-completeness of the subgraph isomorphism problem only in the last phase. Duplicate detection is performed in two phases: hashing to pre-sort and an explicit graph isomorphism test for final duplicate detection.

Critical Discussion

Developing algorithms that discover all frequently occurring subgraphs in a large graph database is computationally extensive, since graph and subgraph isomorphisms play a key role throughout the computations. Since subgraph isomorphism testing is a hard problem, fragment miners are exponential in runtime. Many frequent subgraphs miners have tried to avoid the NP-completeness of subgraph isomorphism problem by storing all embeddings in embedding lists which consist of a mapping of the vertices and edges of a fragment to the corresponding vertices and edges in the graph it occurs in. It is clear that with this trick we can avoid excessive subgraph isomorphism tests when counting fragments support and, therefore, avoid exponential runtime. However, these approaches face exponential memory consumption instead. So,we can say that they are only trading time versus storage. This strategy can even cause problem if not enough memory is available or if the memory throughput is not high enough. The authors in [START_REF] Wörlein | A quantitative comparison of the subgraph miners mofa, gspan, ffsm, and gaston[END_REF] , after an extensive experimental study of different subgraph miners, conclude that embedding lists do not a An embedding is a mapping of the nodes and edges of a subgraph to the corresponding nodes and edges in the graph it occurs in.

considerably speed up the search for frequent fragments. Thus, even though gSpan [START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF] does not use them, it is almost as competitive as Gaston 14 and Ffsm 8 , at least with not too big fragments.

To alleviate the complexity issue, we propose to introduce a bias in the projection operator and instead of using the subgraph-isomorphism projection, one can use a polynomial projection having a semantically-valid structural interpretation.

In [START_REF] Liquiere | Arc consistency projection: A new generalization relation for graphs[END_REF] , the author introduced an interesting projection operator named ACprojection which seems to have good properties and ensure polynomial time and memory consumption. The forthcoming sections present this operator with its many interesting properties and show an optimized algorithm for computing it.

The AC-projection Operator

The projection problem (including conceptual graph projection, homomorphism, injective morphism, Θ-subsumption and OI-subsumption) is crucial to the efficiency of relational learning systems. The approach suggested in [START_REF] Liquiere | Arc consistency projection: A new generalization relation for graphs[END_REF] advocates a projection operator based on the arc consistency algorithm. This projection method has the required properties: polynomiality, local validation, parallelization and structural interpretation. We note that the name "AC-projection" comes from the classical AC (arc consistency) used in 2 .

AC-projection And Arc Consistency

We first state the formal definitions related to AC-projection and arc consistency and used in the remainder of the paper. Definition 3.1. (Labeling) Let G 1 and G 2 be two graphs. We call a labeling from

G 1 into G 2 a mapping I : V (G 1 ) → 2 V (G2) |∀x ∈ V (G 1 ), ∀y ∈ I(x), l(x) = l(y).
Thus, for a vertex x ∈ V (G 1 ).I(x) is a set of vertices of G 2 with the same label l(x). We can say that I(x) is the set of "possible images" of the vertex x in G 2 . This first labeling is trivial but can be refined using the neighborhood relations between vertices.

Definition 3.2. (AC-compatible ) Let G be a graph V 1 ⊆ V (G), V 2 ⊆ V (G) V 1 is AC-compatible with V 2 iff (1) ∀x k ∈ V 1 ∃y p ∈ V 2 |(x k , y p ) ∈ A(G) (2) ∀y q ∈ V 2 ∃x m ∈ V 1 |(x m , y q ) ∈ A(G). We denote it V 1 V 2
In the definition above we give a direct relation between two sets of vertices V 1 and V 2 . So, for each vertex x k of V 1 there is at least one vertex y p of V 2 which is a neighbor of x k and, for each vertices y q of V 2 , there is at least one vertex x m of V 1 which is a neighbor of y q . Definition 3.3. (Consistency for one arc) Let G 1 and G 2 be two graphs. We say that a labeling I : V (G 1 ) → 2 V (G2) is consistent with an arc (x, y) ∈ A(G 1 ), iff I(x) I(y).

I : V (G 1 ) → 2 V (G2) is an AC-projection iff ∀ AC-labeling I ′ : V (G 1 ) → 2 V (G2) and ∀x ∈ V (G 1 ), I ′ (x) ⊆ I(x). We denote it G 1 ⇁ G 2 Fig. 2. An AC-projection example (G 1 ⇁ G 2 )
As depicted in Figure 2, considering the labeling I: I(a0) = {a6, a14}, I(a1) = {a6}, I(b2) = {b7}, I(c3) = {c8}, I(d4) = {d9}, I(e5) = {e10}. We verify that I(a0) I(d4), I(d4) I(c3), I(c3) I(b2), I(b2) I(e5), I(e5) I(a1), I(a1) I(d4), I(b2) I(a1). Then I is an AC-projection from G 1 into G 2 , since I is a labeling consistent with all arcs of G 1 and this labeling is maximal.

AC-projection: Improved Algorithm

We introduce an improved AC-projection algorithm for graphs (based on the AC3 algorithm [START_REF] Mackworth | Consistency in networks of relations[END_REF] ). The AC-projection algorithm takes two graphs G 1 and G 2 and tests whether there is an AC-projection from G 1 into G 2 (cf. Algorithm 1). It begins by the creation of a first rough labeling I and reduces, for each vertex x, the given lists I(x) to consistent lists using the function ReviseArc. The consistency check fails if some I(x) becomes empty, otherwise the consistency check succeeds and the algorithm gives the labeling I which is an AC projection G 1 ⇁ G 2 . Like the AC3 algorithm, the actual AC-projection algorithm has a worst-case time complexity of O(e × d 3 ) and space complexity of O(e) where e is the number of arcs and d is the size of the largest domain. In our case, the size of the largest domain is the size of the largest subset of nodes with the same label.

Algorithm 1: AC-projection

Input : Two graphs G 1 and G 2 Output: An AC-projection I from G 1 into G 2 if there is, otherwise an empty set

foreach x ∈ V (G 1 ) do I(x)={y ∈ V (G 2 )|l(x) = l(y)} S ← A(G 1 ); P ← ∅; while S = ∅ do
Choose an arc (x, y) from S;

I ′ :=ReviseArc ((x, y), I, G 2 ); if (I ′ (x) = ∅) or (I ′ (y) = ∅) then return ∅; if I(x) = I ′ (x) then R ← {(x ′ , y ′ ) ∈ P |x ′ = x or y ′ = x}; S ← S ∪ R; P ← P R; if I(y) = I ′ (y) then R ← {(x ′ , y ′ ) ∈ P |x ′ =
Function ReviseArc Input : A graph G 2 , A labeling I from G 1 into G 2 , An arc (x, y) ∈ V (G 1 ) Output: A new labeling I ′ from G 1 into G 2 I ′ ← I; I ′ (x) ← I(x) {x ′ ∈ V (G 2 )|∄ y ′ ∈ I(y) with (x ′ , y ′ ) ∈ A(G 2 )}; I ′ (y) ← I(y) {y ′ ∈ V (G 2 )|∄ x ′ ∈ I(x) with (x ′ , y ′ ) ∈ A(G 2 )}; return I ′ ;

AC-projection And Reduction

The following definition introduces an equivalence relation between graphs w.r.t. AC-projection.

G 2 are AC-equivalent iff both G 1 ⇁ G 2 and G 2 ⇁ G 1 are fulfilled. We denote it G 1 ⇌ G 2 .
For example in Figure 3 we have: We have an equivalence relation between graphs using the AC-projection. In this paragraph we study the properties of this operation and search for a reduced element in an equivalence class of graphs. This element will be the unique representative of this equivalence class, and for which we give then the name of "AC-reduced graph". The Figure 4 shows a set of graphs belonging to the same equivalence class as well as the AC-reduced one in the extreme right.

• G 1 ⇁ G 2 with

Auto AC-projection And AC-reduction

We examine the auto AC-projection operation (G ⇁ G), which we will use to find the minimal graph of an equivalence class of graphs and we will prove in the following that the obtained graph is minimal. Proposition 3.7. Given an AC-projection I : G ⇁ G ′ , x ′ ∈ I(x) iff for each tree T (V T , A T ), (with V T is the set of vertices of T , and A T its set of arcs) and each t ∈ V T we have:

If there is a morphism from T to G which associates t to x then there is a morphism from T to G ′ which associates t to x ′ . [START_REF] Hell | Graphs and homomorphism[END_REF] Proposition 3.8. (Order relation on I)

For an AC-projection

I : G ⇁ G, if x i ∈ I(x) then I(x i ) ⊆ I(x)
Proof. If we have x i ∈ I(x), it means that for all trees T having a morphism in G and which associates t to x, then there is a morphism from t in G which associates t to x i (cf. Proposition 3.7). We call T (x,t) this set of trees.

Let us see now if we can have x j ∈ I(x i ) and x j / ∈ I(x). For x j ∈ I(x i ), according to Proposition 4.3, we see that all trees from T (x,t) associates to t the vertex x i . Since x j ∈ I(x i ), it will be the same for it, so x j ∈ I(x).

We conclude that we can not have x j / ∈ I(x) since x j ∈ I(x i ), so: I(x i ) ⊆ I(x). Proposition 3.9. Given a graph G and an AC-projection I : G ⇁ G and given a vertex x ∈ V (G) with |I(x)| > 1.

If we have x i ∈ I(x), the graph G ′ formed by the merging of x and x i is ACequivalent to G. Proof. To prove that G ⇋ G ′ we have to prove that G ⇁ G ′ and G ′ ⇁ G. Since G ′ ⇁ G by construction we have only to prove that G ⇁ G ′ :

We construct this AC-projection by replacing x with x i in the auto ACprojection G ⇁ G. Since I(x i ) ⊆ I(x), so there is really an AC-projection. We conclude that G ⇁ G ′ . Now, we are interested in finding the smallest element of the equivalence class of graphs. For two AC-equivalent graphs G and G ′ , we will consider that

G < G ′ iff |V (G)| < |V (G ′ )|.

Proposition 3.10. (Minimality)

A graph G is minimal in the equivalence class iff for the AC-projection

I : G ⇁ G, ∀x ∈ V (G), I(x) = {x}.
Proof. According to Proposition 4.3, it is clear that if there was a vertex x such that |I(x)| > 1, then we will be able to do another reduction. Now, the question is: can a graph G ′ = G \ x be AC-equivalent to G ? If this is true, then we must have an AC-projection from G to G ′ . It would say that x in G has another image x ′ in G ′ . So, x ′ must be in I(x) which is contradictory to the initial hypothesis.

A projection bias in frequent subgraph mining can make a difference 11 Algorithm 2: AC-reduce

Input : A graph G Output: G ′ =AC-reduced G 1 G ′ ← G; 2 I ←AC-projection (G, G); 3 Q ← V (G); 4 Sort Q such as x comes before y if |I(x)| < |I(y)|; 5 foreach v in Q do 6 foreach i in I(v) do 7 if (i = v) then 8 N (v) ← N (v) ∪ N (i)
; //if v and i are neighbors, then we would have a reflexive arc

9 Q ← Q i; 10 V (G ′ ) ← V (G ′ ) i;
11 return G ′ ;

AC-reduce Algorithm

The AC-reduce algorithm (cf. Algorithm 2) is based on the properties given on the section above, these properties allow to construct the AC-reduced graph considering any graph G. To do this, we simply have to do an auto AC-projection G ⇁ G and then make the necessary merges. So this algorithm is very simple and have a polynomial complexity, since the AC-projection's complexity is polynomial.

Search space with AC-projection

In this section, we examine the size of the search space using the AC-projection. We present some properties of the AC-projection. While using these properties we can find an upper bound of the search space. We present this result for one labeled graph G and can be easily extended for n graphs (one for each example). In this case, G is the disjoint union of the graphs describing the examples. Notation: For a labeled graph G:(V,E,L) we note P l (V), the power set of vertices, in V, with label l ∈ L.

Definition 4.1. (AC-graph ) For a labeled graph G:(V,E,L) and a set P of element ∈ P l (V) with l ∈ L. We construct a graph G':(V',E',L') with: -a vertex v for each element in P. We note p(v) ∈ P the associated element.

-The label of a vertex v in the label of the element in p(v) fulfill the downward closure property of the support condition, which allows us to effectively prune the lattice of frequent subgraphs. The B FGMAC's particularity is to output only frequent AC-reduced graphs (Algorithm 3, line 11) which is a subset of the whole frequent isomorphic pattern set.

-(V 1 ,V 2 ) ∈ V' iff p(V 1 ) p(V 2 ) G' is
In the following, we present the key steps of the B FGMAC main process.

Candidate Generation

This step is ensured by the fsg-gen function (cf. Algorithm 3, line 5) used in the FSG algorithm. This function uses a precise joining operator (fsg-join), which generates (k + 1)edges subgraphs by joining two frequent kedges subgraphs.

In order to consider two such frequent kedges subgraph as eligible for joining they must contain the same (k -1)edges subgraph named core. The complete description of these functions as well as their detailed algorithms are given in 11 .

Support Computation

The key operator leading this step is the AC-projection previously described. In fact, to check whether a pattern appears in a transaction, B FGMAC computes in polynomial time if there is an AC-projection of the pattern in each one of the transactions. In order to optimize this support computation phase, the algorithm associates to each graph g of size k the set E(g) of transactions such as for each graph G ∈ E(g), g ⇁ G. Having the graph g 1 ∪ g 2 representing the union of the two graphs g 1 and g 2 , the intersection of the two sets E(g

1 ) ∩ E(g 2 ) is then calculated. As E(g 1 ∪ g 2 ) ⊆ E(g 1 ) ∩ E(g 2 )
, it is possible to eliminate the graph g 1 ∪ g 2 if the transaction's count E(g 1 ) ∩ E(g 2 ) is sufficiently low to make g 1 ∪ g 2 infrequent. On the other hand, the existence of a subgraph which has an AC-projection in g 1 ∪ g 2 can be only looked for in transactions E(g 1 ) ∩ E(g 2 ).

Frequents AC-reduction

This step is essential at the end of each iteration of the main loop of the algorithm. It is intended to avoid the extraction of non AC-reduced frequent graphs, which describe representative elements of graphs equivalence classes w.r.t. AC-equivalence. This process is based on the AC-reduce function described previously. We note that this step takes advantage of the polynomial complexity of the AC-reduction algorithm. The set F of frequent subgraphs

HIA PTC-FM

1 F 1 ←detect frequent (1-edge)-subgraphs in D; 2 F 2 ←detect frequent (2-edges)-subgraphs in D; 3 k ← 3; 4 while F k-1 = ∅ do 5 C k ← fsg-gen (F k-1 ) 6 foreach candidate g k ∈ C k do 7 g k .count ← 0; 8 foreach transaction t ∈ D do 9 if g k ⇁ t then 10 g k .count ← g k .count + 1; 11 F k ← {AC-reduce(g k ∈ C k )|g k .count ≥ σ|D|}; 12 k ← k + 1;
13 return F ;

Experiments and Comparative Study

In order to prove the usefulness of the AC-projection for graph mining, we present in the following an experimental study of the B FGMAC algorithm. We insist that the set of frequent AC-reduced graphs found by B FGMAC is not exhaustive w.r.t. isomorphic patterns. In fact, the set of frequent subgraphs found by the means of the AC-projection is a subset of the classical frequent isomorphic subgraphs. In the following, we present a quantitative study of the B FGMAC performance followed by a qualitative evaluation of the AC-reduced patterns which consists in a computation of their discriminative power within a supervised graph classification process.

Datasets

We carried out performance and classification experiments on five biological activity datasets widely cited in the literature. These datasets can be divided in two groups:

• The Predictive Toxicology Challenge (PTC) [START_REF] Helma | The predictive toxicology challenge 20002001[END_REF] that contains a set of chemical compounds classified according to their toxicity in male rats (PTC-MR), female rats (PTC-FR), male mice (PTC-MM), and female mice (PTC-FM). • The Human Intestinal Absorption (HIA) [START_REF] Wessel | Prediction of human intestinal absorption of drug compounds from molecular structure[END_REF] that contains chemical compounds classified by intestinal absorption activity.

Performance Point Of View

In this subsection we present a quantitative study of the computational performance of B FGMAC compared to FSG. Results depicted in Figure 5 clearly show that B FGMAC outperform FSG in the runtime point of view for all minimal supports selected and confirm the theoretical results about the polynomiality of the AC-projection operator compared to the exponential complexity of the subgraph isomorphism adopted by FSG.

In the following, we present a qualitative-oriented study of frequent AC-reduced patterns.

Qualitative Point Of View: Graph Classification

Graph classification is a supervised learning problem in which the goal is to categorize an entire graph as a positive or negative instance of a concept. We are particularly interested by feature mining on graphs as it uses frequent graph patterns in the classification process. Feature mining on graphs is usually performed to find all frequent or informative substructures in the graph instances. These substructures are used for transforming the graph data into data represented as a single table, and then traditional classifiers are used for classifying the instances.

The goal of using graph classification in this paper is the evaluation of the quality and discriminative power of frequent AC-reduced subgraph patterns, and to compare it with isomorphic frequent subgraphs.

We carried out classification experiments on five biological activity datasets, and measured classifier prediction accuracy using the known decision trees classifier named C4.5 [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF] . The classification methods are described in more detail in the following subsections, along with the associated results.

Methods

We evaluated the classification accuracy using two different feature sets. The first set of features (Frequent) consists of all frequent isomorphic subgraphs. Those subgraphs are mined using the Fsg software 10 with different minimal supports. Each chemical compound is represented by a binary vector whose length is equal to the number of mined subgraphs. Each subgraph is mapped to a specific vector index, and if a chemical compound contains a subgraph then the bit at the corresponding index is set to one, otherwise it is set to zero.

The second feature set (Closed) is simply a subset of the first set. In fact, it consists of only closed frequent subgraphs. Those subgraphs are also mined using Fsg with the special parameter (-x) to hold only closed frequent subgraphs.

The third feature set (AC-reduced) contains the B FGMAC's output which consists of only AC-reduced frequent subgraphs. We have represented each chemical compound by a binary vector whose length is equal to the number of AC-reduced mined subgraphs. Each AC-reduced subgraph is mapped to a specific vector index, and if there is an AC-projection from the AC-reduced subgraph to the chemical compound then the bit at the corresponding index is set to one, otherwise it is set to zero. Finally, the fourth feature set (Closed AC-reduced) is similar to the third one, the difference is that we only consider closed AC-reduced frequent subgraphs with a special parameter passed to B FGMAC.

The graph classification preprocessing over an example is depicted by Figure 6. The final matrix (the context) will be used by the C4.5 15 decision tree algorithm.

Results

All classifications have been done with the Weka data-mining software package [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF] , and we have reported results of the prediction accuracy over the 10 cross-validation trials. In the following, we analyze the AC-reduced patterns from quantitative and qualitative points of view. Patterns Count According to results shown in Figure 7, we see that for all datasets we have very few AC-reduced frequent patterns compared to the isomorphic ones. We have on average 35 patterns. This ratio is bigger for lower supports and can reach up to 70 experimental results highlight the fact that the search space for extracting AC-reduced patterns is smaller than the one for classical isomorphic subgraphs. Thus, having an algorithm which looks for all AC-reduced frequent subgraphs would benefit for the polynomiality of the projection operation as well as a smaller search space (i.e. fewer AC-projection tests).

Classification Relevance When we see that the number of frequent subgraph patterns has drastically decreased after the AC-reduction process, we surely wonder about the relevance of these few patterns for supervised graph classification. That's why we have conducted classification's accuracy experiments using AC-reduced and isomorphic patterns to compare them. As shown in Figure 8, we see that for the all datasets and all classifiers average, the percentage of correctly classified (PCC) instances is almost the same for all minimal supports, as well as for the other datasets individually.

Taking a more in-depth look to the results, we see that, for some datasets and minimal support values, we even have better PCC for AC-reduced feature set. This is due to the better generalization power of the AC-reduction process, which helped supervised classifiers avoid over-fitting learning problem.

Conclusions And Future Work

In this paper, we have studied the use of a new polynomial projection operator named AC-Projection initially introduced in [START_REF] Liquiere | Arc consistency projection: A new generalization relation for graphs[END_REF] and based on a key technique of constraint programming namely Arc Consistency (AC). We have shown that using the AC-projection and its properties has permitted us to have less patterns than all frequent or closed subgraphs but with a very comparable quality and discriminative power. AC-projection is intended to replace the use of the exponential subgraph isomorphism, as well as reducing the search space when seeking for frequent subgraphs. Currently, we are studying a depth-first frequent subgraph mining approach based on the AC-projection operator. Given a graph dataset, this novel approach will be able to look for all frequent AC-reduced patterns with a reduced search space.

3 Fig. 1 .

 31 Fig. 1. A set of labeled graphs

Definition 3 . 4 .

 34 (AC-labeling) Let G 1 and G 2 be two graphs. A labeling I from G 1 into G 2 is an AC-labeling iff I is consistent with all the arcs e ∈ A(G 1 ). Definition 3.5. (AC-projection ⇁ ) Let G 1 and G 2 be two graphs. An AC-labeling

  y or y ′ = y}; S ← S ∪ R; P ← P R; S ← S {x, y}; P ← P ∪ {x, y}; I ← I ′ ; return I;

ijait A projection bias in frequent subgraph mining can make a difference 9 Fig. 3 .

 93 Fig. 3. Two AC-equivalent graphs (G 1 ⇌ G 2 )

  the labeling I : I(a0) = {a6, a11, a12}, I(a1) = {a6, a12}, I(b2)={b7, b13}, I(c3) = {c9, c15}, I(d4) = {d16, d10}, I(e5) = {e8, e14} • G 2 ⇁ G 1 with the labeling I ′ : I ′ (a11) = {a0, a1}, I ′ (a6|a12) = {a1}, I ′ (b7|b13) = {b2}, I ′ (c9|c15) = {c3}, I ′ (d16|d10) = {c4}, I ′ (e8|e14) = {e5}

Fig. 4 .

 4 Fig. 4. AC-equivalent graphs and the associated AC-reduced one (extreme right)

Fig. 5 .

 5 Fig. 5. Runtime comparison of B FGMAC versus FSG with the two datasets HIA and PTC-FM

Fig. 6 .

 6 Fig. 6. Graph classification process

HIAFig. 7 .

 7 Fig. 7. Comparison of the number of patterns of different feature set for PTC-FM and HIA datasets

Fig. 8 .

 8 Fig. 8. Comparison of the classification accuracy (PCC) of different feature sets for All datasets(Average), PTC-FM and HIA datasets

B. Douar et al.

B. Douar et al.

B. Douar et al.

B. Douar et al.

B. Douar et al.

So, an AC-graph is built from a list of set of vertices from a graph G. Now, we look at some links between the AC-graph and the AC-projection. Proposition 4.2. For each AC-projection between two graphs G', G there is an associated AC-graph.

Proof. Since an AC-projection I, gives, for each vertex of x of G', a set of vertex of G. The AC-graph built from an AC-projection is the one build from the set of I(x), x ∈ V'. Proof. The labeling I with, for each V ∈ G', I(V) = p(V) is an AC-labeling from G' into G by construction. Now for a graph G we can define a specific AC-graph built from the power set of vertices of G. Definition 4.4. (Max-AC-graph ) For a graph G:(V,E,L) the Max-AC-graph of G is the AC-graph built from the set P of all element ∈ P l (V) with label l ∈ L. We denote this graph Max-AC-graph(G).

All subgraphs of Max-AC-graph(G) have an AC-projection into G. Since the Max-AC-graph is the biggest AC-graph, it will represent the search space. The complexity of the construction of the Max-AC-graph is O(2 n 2 ) where n is the number of vertices in G. This complexity is high but for many structural descriptions (graph with homorphism projection) the size of the search space is bigger by an order of magnitude.

B FGMAC: Breadth-first Frequent subGraph Mining with Arc Consistency

In this section, we present B FGMAC, a modified version of the FSG algorithm 10 based on the AC-projection operator. In fact, in this version we have changed the support counting part. Instead of subgraph isomorphism, the AC-projection is used to verify whether a candidate graph appears in a transaction or not.

The Algorithm

The B FGMAC algorithm initially enumerates all the frequent single and double edge graphs. Then, based on those two sets, it starts the main computational loop.

During each iteration it first generates candidate subgraphs whose size is greater than the previous frequent ones by one edge (cf. Algorithm 3, line 5). Next, it counts the frequency for each of these candidates, and prunes subgraphs that do no satisfy the support constraint (cf. Algorithm 3, lines 6-11). Discovered frequent subgraphs