Zhun-Ga Liu
email: liuzhunga@gmail.com

Jean Dezert
email: jean.dezert@onera.fr

Grégoire Mercier
email: gregoire.mercier@telecom-bretagne.eu

Quan Pan

Change Detections from Heterogeneous Remote Sensing Images based on Multi-dimension Evidential Reasoning

Keywords: evidence theory, belief functions, change detection, multi-temporal satellite images fusion, DST, DSmT

In classical evidential reasoning of Shfer's model, all the sources of evidence over the same frame of discernment are underlying considered referring to the invariable decision target, and the conflicting beliefs produced by the conjunctive combination are redistributed by the combination rules to get a specific result which still lies in the same frame. Nevertheless, the sources of evidence to be combined possibly associate with different real targets in some applications, even if they are defined on the same frame. For example, in the data association in multi-target detection, the evidence from the different sensors may refer to different real-targets, although the evidence are defined in the same frame containing various targets. In such case, the fusion results should take care of the joint information of the different exclusive elements, but it is considered as conflicting beliefs in classical way. Besides, the classical frame, whose elements all refer to the single exclusive target separately, is not sufficient to represent such joint hypothesis. So the multi-dimension evidential reasoning (MDER) approach is proposed in this work. The classical frame is extended to multiple dimension denoted by M-D taking into account of the availability of the joint hypothesis of the exclusive elements called jointelement. M-D frame is composed by the joint-element, whose dimensions is coherent with the number of the independent sources. Belief functions are defined in M-D frame for decision-making. MDER is appropriate for the combination of the sources of evidence which don't necessarily arise from the same invariable decision-target. Two kinds of combination rules working in free model and constrained model are proposed for coping with different cases. Several examples are given to illustrate the use of the proposed approach and the difference between the new approach and DSmT.

I. INTRODUCTION

Change detections from heterogenous multi-temporal remote sensing images is still an important and open problem. The remote sensing images may be acquired form different kinds of sensors, and the parameters of acquisitions may differ from one image to another even when the acquisitions are issued from the same sensor. So the images can be quite different in their modality. That is why, for change detection purpose, the use of the difference image is not an appropriate point of view due to the number of false alarms it induces. Moreover, classification of the change feature is also very important in some applications. Hence the comparison of the classified images seems to be more appropriated. Nevertheless, this yields to deal with uncertain, imprecise and even conflicting information. Evidence theories including Dempster-Shafer Theory (DST) [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], Dezert-Smarandache Theory (DSmT) [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF] and Transferable Belief Model (TBM) [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] are good for dealing with such information, and they have been applied for remote sensing applications.

The classification results of remote sensing images can share a common frame of discernment if the images are obtained by the same kind of sensors, but they may lie in the different frames once the images are acquired from the different kinds of sensors. In the classical evidential reasoning, if the sources of evidence to be combined are defined over a common frame, their fusion results will be considered still in the same invariable frame. So it is suitable for the fusion of the images without change occurrences to get more specific classification results. Nevertheless, both content classifications and change detections are involved in the fusion of the multi-temporal remote sensing images. The classical evidential reasoning doesn't work well in such case, since the hypothesis about change occurrences through different sources can't be represented in the classical frame. In the combination of sources of evidence associated with distinct frames, Cartesian product frame is always used, but in the past works, it mainly focus on the representation of joint information from various aspects referring to the same thing instead of change detections.

In this paper, the multi-dimension evidential reasoning (MDER) is proposed for the change detections through the multitemporal remote sensing images no matter issued from the same or different kinds of sensors. The classification results of each image corresponding the sources of evidence lie in the separate frame, which can be the same or various depending on the properties of images, but their fusion results will work in the multi-dimension frame composed by the Cartesian product of these separate frames. The number of dimensions of the frame depends on the number of multi-temporal images. The multi-dimension elements can well represent the joint state of the fusion of different images, and it provides more refined information than classical evidential reasoning for the combination of sources of evidence in the common frame, since it takes into account of the sequence of sources. If an area remains the same in multi-temporal images, it will be considered as coherent joint state, whereas the change occurrences corresponds to the incoherent joint state. Combination rules working in free model and constrained model are given in MDER for dealing with different cases. In free model, there is no prior information and all the possible joint hypothesis are considered available, whereas some constraints about the impossible joint hypothesis will be given according to the prior knowledge/experience in constrained model. Belief function Bel(.), plausibility function P l(.) and pignistic probability BetP (.) [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF]are defined in MDER similar as in DST for decision-making support. Two experiments with the real data are given to show interests of the proposed approach.

II. A BRIEF REVIEW OF DSMT

We need to introduce briefly DSmT framework [START_REF] Dezert | On the generation of hyper-power sets for DSmT[END_REF], [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF] because the MDER approach developed in the sequel shares some common ideas with DSmT, in particular the necessity to deal with hybrid models of the frames in some applications once parts of the constraints information are known. The purpose of DSmT [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF] is to overcome the limitations of DST [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] mainly by proposing new underlying models for the frames of discernment in order to fit better with the nature of real problems, and proposing new efficient combination and conditioning rules. In DSmT framework, the elements θ i , i = 1, 2, . . . , n of a given frame Θ are not necessarily exclusive, and there is no restriction on θ i but their exhaustivity. The hyper-power set D Θ in DSmT [START_REF] Dezert | On the generation of hyper-power sets for DSmT[END_REF] is defined as the set of all composite propositions built from elements of Θ with operators ∪ and ∩. For instance, if

Θ = {θ 1 , θ 2 }, then D Θ = {∅, θ 1 , θ 2 , θ 1 ∩ θ 2 , θ 1 ∪ θ 2 }.
A (generalized) basic belief assignment (bba for short) is defined as the mapping m : D Θ → [0, 1]. The generalized belief and plausibility functions are defined in almost the same manner as in DST.

Two models1 (the free model and hybrid model) in DSmT can be used to define the bba's to combine. In the free DSm model, the sources of evidence are combined without taking into account integrity constraints. When the free DSm model does not hold because the true nature of the fusion problem under consideration, we can take into account some known integrity constraints and define bba's to combine using the proper hybrid DSm model. All details of DSmT with many examples can be easily found in [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF] available freely on the web.

A. The space of multi-dimension evidential reasoning

The sources of evidence acquired from each piece of images can be defined in separate single-dimension frame, but their fusion results will be considered in multi-dimension frame to well represent the joint state of the multi-temporal images. In the M-D frame, all the elements can be called joint hypothesis, and the subelements in each dimension of joint hypothesis corresponds to different sources of evidence. Let's consider n pieces sources of evidence respectively defined over n singledimension frames as Θ 1 , Θ 2 , . . . , Θ n , which can be the same or distinct. Then their associated M-D frame of their fusion results is given by

Θ n =Θ 1 × Θ 2 × . . . × Θ n = {(x 1 , x 2 , . . . , x n )|x i ∈ Θ i , i = 1, 2, . . . , n}
where Θ i and Θ j , i = j can be same or different. × is the Cartesian product operator. The cardinality of

|Θ n | = |Θ 1 | × |Θ 2 | × . . . × |Θ n |.
The joint hypothesis (x 1 , x 2 , . . . , x n ) can be considered as joint-state through different images with the interpretation that in the same area of n pieces of multi-temporal images, the content classification is

x i in the image No.i, i = 1, • • • , n.
The space of MDER will be denoted and defined by G Θ n . In this paper, we assume to work in a more simple case where G Θ = 2 Θ , and it will be defined by

2 Θ n = 2 Θ1×Θ2×...×Θn
2 Θ n can be called M-D power-set, which is composed by all the subsets in Θ n with the union operator ∪. The use of the operators ∪ and ∩ in MDER should satisfy the following reasonable conditions:

(C1) Distributivity of ∪ w.r.t. → (A ∪ B, C) = (A, C) ∪ (B, C) (C2) Distributivity of → w.r.t. ∪ (A, B ∪ C) = (A, B) ∪ (A, C) (C3) Associativity of state-transition (A, B) ∩ (C, D) = (A ∩ C, B ∩ D).
Please note that in most cases

(x 1 , . . . , x n ) ∪ (y 1 , . . . , y n ) = (x 1 ∪ y 1 , . . . , x n ∪ y n ) If ∀x i = y i ; x i , y i are singletons, (x 1 , . . . , X n ) ∪ (y 1 , . . . , y n ) indicates only two possible hypothesis, whereas the element (x 1 ∪ y 1 , . . . , x n ∪ y n ) represents 2 × 2 × • • • × 2 = 2 n possible hypothesis. It is obvious that they are quite different, and (x 1 ∪ y 1 , . . . , x n ∪ y n ) is much more imprecise than (x 1 , . . . , x n ) ∪ (y 1 , . . . , y n ). For instance, (x 1 , x 2 ) ∪ (y 1 , y 2 ) = (x 1 ∪ y 1 , x 2 ∪ y 2 ) = (x 1 , x 2 ) ∪ (x 1 , y 2 ) ∪ (y 1 , x 2 ) ∪ (y 1 , y 2 ) following C1 and C2.
As we see, the important and major difference between the classical approaches (DST, TBM, DSmT) and MDER approach is the choice of the fusion space we are working with. With DST, TBM or DSmT, the fusion space we work with is always the same (independent of the number of sources) as soon as the sources are defined with respect to same frame Θ, whereas with MDER approach the fusion space is always increasing with the number of sources. This of course increases the complexity of DER approach, but this is the "price to pay" to acquire the more efficient and interesting information as it will be shown in following sections of this paper.

Example 1: Let's consider 2-dimension frame as Θ2 = Θ × Ω, and Θ = {θ 1 , θ 2 }, Ω = {ω 1 , ω 2 }. Then, the power set of transitions we want to work with for such very simple example will be given by:

Θ 2 ={(θ 1 , ω 1 ), (θ 1 , ω 2 ), (θ 2 , ω 1 ), (θ 2 , ω 2 )} 2 Θ 2 = {(∅, ∅), (∅, ω 1 ), (∅, ω 2 ), (θ 1 , ∅), (θ 2 , ∅), (θ 1 , ω 1 ), (θ 1 , ω 2 ), (θ 2 , ω 1 ), (θ 2 , ω 2 ), (θ 1 , ω 1 ) ∪ (θ 2 , ω 2 ), (θ 1 , ω 2 ) ∪ (θ 2 , ω 1 ), (θ 1 , ω 1 ) ∪ (θ 1 , ω 2 ) = (θ 1 , ω 1 ∪ θ 2 ) = (θ 1 , Ω) (θ 2 , ω 1 ) ∪ (θ 2 , ω 2 ) = (θ 2 , ω 1 ∪ θ 2 ) = (θ 2 , Ω) (θ 1 , ω 1 ) ∪ (θ 2 , ω 1 ) = (θ 1 ∪ θ 2 , ω 1 ) = (Θ, ω 1 ) (θ 1 , ω 2 ) ∪ (θ 2 , ω 2 ) = (θ 1 ∪ θ 2 , ω 2 ) = (Θ, ω 2 ) (θ 1 , ω 1 ) ∪ (θ 1 , ω 2 ) ∪ (θ 2 , ω 1 ) (θ 1 , ω 1 ) ∪ (θ 1 , ω 2 ) ∪ (θ 2 , ω 2 ) (θ 2 , ω 1 ) ∪ (θ 2 , ω 2 ) ∪ (θ 1 , ω 1 ) (θ 2 , ω 1 ) ∪ (θ 2 , ω 2 ) ∪ (θ 1 , ω 2 ) (θ 1 , ω 1 ) ∪ (θ 1 , ω 2 ) ∪ (θ 2 , ω 1 ) ∪ (θ 2 , ω 2 ) = (Θ, Ω)}
These elements involve with ∅ of course can be seen as the same with ∅ in classical way if necessary.

In Example 1, Ω and θ can be equal or not. If Θ and Ω are two distinct frames, it implies the properties of the two pieces of images are total different and their classification results lies in different frames. Then, (θ i , ω j ) can be considered as the content in the same area belongs to θ i and ω j respectively in different images. If Ω is equal to Θ, it indicates the two images possibly issued from the same kind of sensors, and their classification results can be defined in the same frame. (θ i , ω j ) ∆ ( θ i , θ j ) means the content transferred from θ i to θ j during the two images.

We recall that the imprecise elements are derived from application of conditions C1 and C2 and not from the componentwise union of n-uples. The cardinality of 2 Θ n is given as

|2 Θ n | = 2 |Θ n | = 2 |Θ1|×|Θ2|•••×|Θn| (1)
where all the elements involved with ∅ are consider same as empty sets.

III. SOME BASIC DEFINITIONS IN MDER

The belief function Bel(.), or plausibility function P l(.), and pignistic probability BetP (.) 2 [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF], [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] are important and basic functions in evidential reasoning. They can be used to transfer the belief to probability for the convenience of decision-making. These functions can be also used in MDER approach as well.

All the elements in Θ n has a specific and unique meaning, and they are considered the singleton elements. All the focal elements in T Θ n can be decomposed in the disjunctive canonical form using these singleton elements with the operator ∪, and we call it canonical focal element. For example, m((

θ 1 ∪ θ 2 ), θ 3 ) = m((θ 1 , θ 3 ) ∪ (θ 2 , θ 3
)) because of the condition (C1). The belief, plausibility functions and the pignistic transformation are defined in MDER similarly as in DST; that is:

Bel(A) = A,B∈2 Θ n ;B⊂A m(B) (2)
P l(A) = A,B∈2 Θ n ;A∩B =∅ m(B) (3)
The interval [Bel(A), P l(A)] is then interpreted as the lower and upper bounds of imprecise probability for decision-making support [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] and the pignistic probability BetP (A) commonly used to approximate the unknown probability P (A) in [Bel(A), P l(A)] is calculated by:

BetP (A) = A,B∈2 Θ n ,A⊂B |A ∩ B| |B| m(B) (4)
where |X| is the cardinal of the element X. In MDER, the cardinal of A ∈ 2 Θ n is the number of the singleton elements it contains in its canonical form.

For example, if we have a bba's over Θ 2 = Θ × Θ, and

Θ = {θ 1 , θ 2 , θ 3 } as: m(θ 1 , θ 2 ) = 0.5, m(θ 1 , θ 2 ∪ θ 3 ) = 0.2, m(Θ, θ 3 ) = 0.3
The cardinal of the imprecise elements is counted by:

|(θ 1 , θ 2 ∪ θ 3 )| = |(θ 1 , θ 2 ) ∪ (θ 1 , θ 3 )| = 2, (Θ, θ 3 ) = |(θ 1 , θ 3 ) ∪ (θ 2 , θ 3 ) ∪ (θ 3 , θ 3 )| = 3.
Then, one gets

Bel(θ 1 , θ 2 ) = m(θ 1 , θ 2 ) = 0.5, P l(θ 1 , θ 2 ) = m(θ 1 , θ 2 ) + m(θ 1 , θ 2 ∪ θ 3 ) = 0.7, P l(θ 1 , θ 3 ) = m(θ 1 , θ 2 ∪ θ 3 ) + m(Θ, θ 3 ) = 0.5, P l(θ 2 , θ 3 ) = m(Θ, θ 3 ) = 0.3, P l(θ 3 , θ 3 ) = m(Θ, θ 3 ) = 0.3, BetP (θ 1 , θ 2 ) = m(θ 1 , θ 2 ) + m(θ 1 , θ 2 ∪ θ 3 ) 2 = 0.6, BetP (θ 1 , θ 3 ) = m(θ 1 , θ 2 ∪ θ 3 ) 2 + m(Θ, θ 3 ) 3 = 0.2, BetP (θ 2 , θ 3 ) = m(Θ, θ 3 ) 3 = 0.1, BetP (θ 3 , θ 3 ) = m(Θ, θ 3 ) 3 = 0.1.

IV. COMBINATION RULES IN MULTI-DIMENSION EVIDENTIAL REASONING

The combination rules [START_REF] Dubois | On the unicity of Dempster's rule of combination[END_REF], [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], [START_REF] Yager | On the relationships of methods of aggregation of evidence in expert systems[END_REF] in classical frame mainly try to get very specific results by various kinds of redistribution of the conflicting belief. Nevertheless, the conflicting belief may represent interesting information in some applications, and they will be totally or partly kept in M-D frame according to the model. The new combination rules working in free model and constrained model in M-D frame are proposed to get the useful information as much as possible through the fusion of the sources of evidence.

A. Combination rule in free model

In the free model, there is no available prior knowledge in the fusion, and all kinds of hypothesis in 2 Θ n are considered possible to happen.

In the fusion of sources of evidence obtained from multi-temporal images, the bba's associated with each source can be extended to M-D format. For example, m i (A)

∆ = m i (Θ 1 , Θ 2 , . . . , Θ i-1 , A, Θ i+1 , . . . , Θ n ),
and it can be interpreted as the mass of the hypothesis A in source i without knowing anything in the other sources.

Let's assume n sequential sources of information defined over the frames

Θ 1 , • • • , Θ n to be combined as m = m 1 ⊕ m 2 ⊕ . . . m n .
The conjunctive combination rule is given by ∀A,

X i ∈ 2 Θ n m(A) = m 1 (X 1 )m 2 (X 2 ) . . . m n (X n ), X 1 ∩ X 2 ∩ . . . X n = A. (5)
This combination rule of the M-D bba's is associative and commutative.

The single dimension bba's can also be directly combined without the extending to M-D format. The combination rule of n sequential sources of evidence represented by single dimension bba's in M-D frame is defined by ∀x

1 , x 2 , . . . , x n ∈ 2 Θi , A ∈ 2 Θ n m(A) = m 1 (x 1 )m 2 (x 2 ) • • • m n (x n ), A = (x 1 , x 2 , . . . , x n ) (6)
obviously, this combination rule is associative but not commutative. For simplicity, the sequential sources of information can be iteratively combined one by one as

m 1→n (A) = m 1→n-1 (X)m n (x n ), (7)
where

X = (x 1 , x 2 , . . . , x n-1 ) ∈ 2 Θ n-1 , A = (X, x n ) ∈ 2 Θ n
In this free model, the result of the combination is very specific since all kinds of change occurrences are distinguished in the results.

The following example will show the combination of sources of evidence in different frames. Example 2: Let's consider two pieces of images obtained by different sensors, and their classification results are defined in two different frames of discernment Θ = {θ 1 , θ 2 } and Ω = {ω 1 , ω 2 , ω 3 }, and the bba's are given by From the results, we can see the joint state (θ 1 , ω 2 ) is most likely to be true, and it indicates that the associated area belonged to θ 1 in 1 st image, and it was ω 2 in the 2 ed image. if θ 1 and ω 2 are coherent with each other form different aspects, it implies the content of the area is invariable. Otherwise, it was incoherent joint state, and this represents change occurrence.

θ 1 θ 2 Θ m 1 0.6 0.1 0.3 ω 1 ω 2 ω 3 m 2 0.3 0.5 0.2 With MDER free rule (MDERf): m(θ 1 , ω 1 ) = 0.18, m(θ 1 , ω 2 ) = 0.3, m(θ 1 , ω 3 ) = 0.12, m(θ 2 , ω 1 ) = 0.03, m(θ 2 , ω 2 ) = 0.05, m(θ 2 , ω 3 ) = 0.02, m(Θ, ω 1 ) = 0.09, m(Θ, ω 2 ) = 0.15, m(Θ, ω 3 ) = 0.
In the following examples, we will show how MDER works and its difference from the classical methods. With DERf rule:

m(θ 1 , θ 2 ) = m 1 (θ 1 )m 2 (θ 2 ) = 0.045 m(θ 1 , θ 3 ) = m 1 (θ 1 )m 2 (θ 3 ) = 0.2475, m(θ 1 , θ 4 ) = m 1 (θ 1 )m 2 (θ 4 ) = 0.1575, m(θ 3 , θ 2 ) = m 1 (θ 3 )m 2 (θ 2 ) = 0.025, m(θ 3 , θ 3 ) = m 1 (θ 3 )m 2 (θ 3 ) = 0.1375, m(θ 3 , θ 4 ) = m 1 (θ 3 )m 2 (θ 4 ) = 0.0875, m(θ 4 , θ 2 ) = m 1 (θ 4 )m 2 (θ 2 ) = 0.03, m(θ 4 , θ 3 ) = m 1 (θ 4 )m 2 (θ 3 ) = 0.165, m(θ 4 , θ 4 ) = m 1 (θ 4 )m 2 (θ 4 ) = 0.105.
Note that the main difference between DSmC and MDERf lies in the ability of MDERf to refine the partial conflicts into several distinct joint hypothesis. More precisely, the the mass 0.2525 of the partial conflict

θ 3 ∩ θ 4 computed as m(θ 3 ∩ θ 4 ) = m 1 (θ 3 )m 2 (θ 4 ) + m 1 (θ 4 )m 2 (θ 3 ) = 0.
2525 with classical DSm free rule becomes clearly split into two joint hypothesis (θ 3 , θ 4 ) and (θ 4 , θ 3 ) with associated masses 0.0875 and 0.165. One sees that, if DSmC rule is used to detect the change occurrence in some applications, θ 3 ∩ θ 4 gets the biggest mass which indicates that the hypothesis of change occurrences (θ 3 , θ 4 ) or (θ 4 , θ 3 ) is most likely to happen. Nevertheless, the most mass (or credibility) is actually committed to θ 1 in by the source no.1, and to θ 3 by the source no. 2. So the change occurrence from θ 1 to θ 3 is intuitively most likely to occur, which is consistent with the result provided by MDERf rule. Example 4: Let's consider three sources of information in the same frame of discernment Θ = {θ 1 , θ 2 , θ 3 }, and the bba's are given by

θ 1 θ 2 θ 3 θ 1 ∪ θ 3 Θ m 1 0.8 0 0.1 0 0.1 m 2 0 1 0 0 0 m 3 0.6 0 0 0.4 0 With DSmC rule : m(θ 1 ∩ θ 2 ) = 0.84, m(θ 2 ∩ θ 3 ) = 0.04, m(θ 1 ∩ θ 2 ∩ θ 3 ) = 0.06, m(θ 2 ∩ (θ 1 ∪ θ 3 )) = 0.06.
With MDERf rule:

m(θ 1 , θ 2 , θ 1 ) = 0.48, m(θ 3 , θ 2 , θ 1 ) = 0.06, m(Θ, θ 2 , θ 1 ) = 0.04, m(θ 1 , θ 2 , θ 1 ∪ θ 3 ) = 0.32, m(θ 3 , θ 2 , θ 1 ∪ θ 3 ) = 0.04, m(Θ, θ 2 , θ 1 ∪ θ 3 ) = 0.06.
For the singleton elements, based on MDERf, one gets: Bel(.) BetP (.) P l(.) (θ 1 , θ One can see that most belief is committed to the joint hypothesis (θ 1 , θ 2 , θ 1 ) according to the results of MDERf. It can be interpreted in the application of data association as m 1 and m 3 are associated with the same target θ 1 , whereas m 2 refers to θ 2 . If it is used in the change detection of multi-temporal satellite images, it can be considered as the content transfers from θ 1 to θ 2 , and then back to θ 1 in one area of the images. Nevertheless, the elements in DSmC are all single dimension, and they can't provide the joint or transition information.

B. Combination rule in constrained model

In some applications, part of joint hypothesis in 2 Θ n is known impossible to happen as the prior information, and these hypothesis can be considered as empty sets. The set ∅ {∅ M , ∅} can be defined in introducing some integrity constraints as done in the hybrid model of DSmT. ∅ M includes all the hypothesis in 2 Θ n , which have been forced to be empty because of the chosen integrity constraints in the model M, and ∅ is the classical empty set. The mass of the empty sets arising from integrity constraints can be distributed to the other focal elements.

The notation (x 1 , x 2 , . . . , x n ) M = X, means that the hypothesis (x 1 , x 2 , . . . , x n ) is equivalent to X in the underlying model M given the integrity constraints.

• DER DS rule of combination:

The mass of empty sets can be distributed by a lot of ways like Dempster's rule [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], Yager's rule [START_REF] Yager | On the relationships of methods of aggregation of evidence in expert systems[END_REF], etc. For simplicity, it is proportionally distributed to the other focal elements similarly to Dempster-Shafer's rule denoted by MDER DS in this work. All the single dimension bba's are extended to M-D at first. Then, the combination rule of n sequential sources of evidence is mathematically defined as follows:

∀A, X, Y ∈ 2 Θ n m(A) = X∩Y M = A m 1 (X)m 2 (Y ) 1 -K (8)
where the factor 1 1-K is used for the normalization of the results, and K represents the mass of belief committed to the empty sets (i.e. the degree of conflict) which is given by

K = X∩Y ∈∅ m 1 (X)m 2 (Y ) (9)
Please note that this combination rule seems similar to Dempster's rule, but it works in a quite different frame. It is associative and communicative, and it can be used to combine the n sources of evidence one by one.

When considering the direct combination of n sequential single dimension bba's altogether, one has ∀A ∈ 2 Θ n , and

x i ∈ 2 Θi , i = 1, 2, . . . , n m(A) = (x1,x2,...,xn) M = A m 1 (x 1 ) • • • m n (x n ) 1 -K (10)
where

K = (x1,x2,...,xn)∈∅ m 1 (x 1 ) • • • m n (x n ) (11)
Remark: The summation introduced in ( 8) and [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] allows to take into account the integrity constraints of the model of the space of transitions as shown in the next example. Example 4:(Continued) Let's continue Example 4. Once some constraints about the impossible joint hypothesis are available as

∅ M = {(Θ, θ 2 , θ 3 ), (θ 3 , Θ, Θ)},
MDER DS can be used in the constrained model. The constraints mean that θ 2 and θ 3 can't be in the last two dimensions at same time whatever the elements are in the 1 st dimension, and θ 3 will never be in the 1 st dimension whatever the last two dimensions are.

Therefore, these beliefs of the joint hypothesis (θ 3 , θ 2 , θ 1 ) and (θ 3 , θ 2 , θ 1 ∪ θ 2 ) in free model take part in the conflict. Thus, the mass of belief committed to the total conflict is therefore given by:

K = m f (θ 3 , θ 2 , θ 1 ) + m f (θ 3 , θ 2 , θ 1 ∪ θ 2 ) = 0.1
Due to the integrity constraints (Θ, θ 2 , θ 3 ), (θ 3 , Θ, Θ) ∈ ∅ and the conditions given by C1 and C2, one has

(θ 1 , θ 2 , θ 1 ∪ θ 3 ) = (θ 1 , θ 2 , θ 1 ) ∪ (θ 1 , θ 2 , θ 3 ) M = (θ 1 , θ 2 , θ 1 ) ∪ ∅ = (θ 1 , θ 2 , θ 1 ); (Θ, θ 2 , θ 1 ) = (θ 3 , θ 2 , θ 1 ) ∪ (θ 1 ∪ θ 2 , θ 2 , θ 1 ) M = ∅ ∪ (θ 1 ∪ θ 2 , θ 2 , θ 1 ) = (θ 1 ∪ θ 2 , θ 2 , θ 1 ); (Θ, θ 2 , θ 1 ∪ θ 3 ) = (θ 3 , θ 2 , θ 1 ∪ θ 3 ) ∪ (θ 1 ∪ θ 2 , θ 2 , θ 1 ) ∪ (θ 1 ∪ θ 2 , θ 2 , θ 3 ) M = ∅ ∪ (θ 1 ∪ θ 2 , θ 2 , θ 1 ) ∪ ∅ = (θ 1 ∪ θ 2 , θ 2 , θ 1 ).
Therefore, the mass of m f (θ 1 , θ 2 , θ 1 ∪ θ 3 ) must be transferred to m(θ 1 , θ 2 , θ 1 ), and m f (Θ, θ 2 , θ 1 ) and m f (Θ, θ 2 , θ 1 ∪ θ 3 ) must be transferred to m(θ 1 ∪ θ 2 , θ 2 , θ 1 ).

Finally, the result given by DER DS rule is

m(θ 1 , θ 2 , θ 1 ) = m f (θ 1 , θ 2 , θ 1 ) + m f (θ 1 , θ 2 , θ 1 ∪ θ 3 ) 1 -K = 0.9, m(θ 1 ∪ θ 2 , θ 2 , θ 1 ) = m f (Θ, θ 2 , θ 1 ) + m f (Θ, θ 2 , θ 1 ∪ θ 3 ) 1 -K = 0.1.
In this constrained model, MDER DS gets more specific results than in the free model because of the use of the constraints.

In the constrained model, if all transitions among the exclusive elements are not allowed, it will becomes Shafer's model, and the MDER DS combination rule reduces to classical Dempster-Shafer's rule of combination.

V. APPLICATION ON REAL REMOTE SENSING IMAGES

VI. CHANGE DETECTIONS WITH A PAIR OF SPOT XS-ERS AND SPOT IMAGES

In this experiment, we want to show how MDER works for the change detections between a pair of heterogenous images form different sensors. Quartile regression has been applied on this pair of images: SPOT Xs-ERS images and SPOT images corresponding to a flood over Gloucester, U.K. from October and November 2000. The ERS bef ore image reflecting the roughness of the ground was acquired on 10/21/1999, and the multi-spectral SPOT HRV af ter image was obtained on 10/21/2000 during a flood that occurs in October 2000, as shown on Fig. 1 and2.

At first, the bba's associated with the mass of belief of classes in each image are determined based on the image classification. In this level, many supervised/unsupoervised methods can be applied for the image classification. In this work, the unsupervised clustering method ECM (Evidential C-Means), which is adapted to the classification of uncertain data in belief functions framework, is applied for the images classification using the pixel value, and it resultscan be directly used as bba's. The ERS image is gray image, and it is not so clear and specific as the colorful SP OT image. The number of clusters for ERS bef ore image is given by k E = 3, and its classification results are defined in the frame as The other tuning parameters are defined by: Maximum number of iterations T = 10, Termination threshold ε = 3, Termination measureE = 1. The normalized membership is used as the mass functions (bba's). As to decision making, we take the criteria that true hypothesis gets the maximum of pignistic probability.

In the fusion process, the constrained model is selected, since we can have some prior knowledge that the change occurrence mainly happened about the flood. It is not necessary to consider all kinds of joint hypothesis, since some incoherent joint states are impossible and they can be forced to be empty set. We can find some links between the two frames that θ 1 mainly corresponding to ω 1 or ω 2 , θ 2 mainly corresponding to ω 4 , and θ 3 mainly corresponding to ω 3 . So we only consider such joint sates are available including the coherent joint states as (θ 1 , ω 1 ), (θ 1 , ω 2 ), (θ 2 , ω 4 ), (θ 3 , ω 3 ), and the incoherent joint state (θ 1 , ω 3 ) which is considered as change occurrences.

The fusion results by the combination rules DER DS are shown as As we can see, the fusion results not only present the change occurrences but also give some indication of the content classification, which can be helpful in some applications. Nevertheless, there are still some miss detections and false alarms. Some parts along the river is gray or even white color before flood, and they are green after the flood. As our above analysis, gray and white are mainly coherent with green between the two images. So they are not considered as change occurrences, and it mainly leads to the miss detections. The reason of the false alarms mainly lies that the changing of pixels in some small areas similarly to the changing in the flood area during the images. As we know, the flood mainly happened along the river. So if some more prior information about location of the river is known, false alarms would be reduced using the prior probability about change occurrences.

VII. CONCLUSIONS

Multi-dimension evidential reasoning (MDER) is proposed in this work, and it is shown how to use MDER in data association in multi-target detection. MDER is appropriate to combine the sources of evidence which are not necessarily refers to the same thing by introducing the multi-dimension (M-D) frame of belief functions. The joint hypothesis in M-D frame can well represent the joint information from the different sources of evidence. The belief functions bel(.), plausibility function P l(.) and pignistic probability BetP (.) in M-D frame are defined similarly as in DST for the convenience of decision-making. The free model of MDER is designed for the combination of sources of evidence in case that no prior knowledge about the joint hypothesis is available. If some constraints on the impossible joint hypothesis are acquired, the constrained model will be adopted to get better fusion results with less computational complexity. MDER DS rule is given in the constrained model as the direct extensions of Dempster-Shafer's rule in M-D frame. Several simple numerical examples were given to show how to use MDER and to show its difference with classical fusion approaches. Finally, the application of MDER for data association in multi-target detection is introduced by a simple example, and it is compared with the method using conflicting beliefs. The comparison indicates that MDER is more appropriate in this application, especially in case of the similar bba's.

Example 3 :

 3 Let's consider two sources of information in the same frame of discernment Θ = {θ 1 , θ 2 , θ 3 , θ 4 }, and the bba'classic/conjunctive rule (DSmC):m(θ 1 ∩ θ 2 ) = 0.045, m(θ 1 ∩ θ 3 ) = 0.2475, m(θ 1 ∩ θ 4 ) = 0.1575, m(θ 2 ∩ θ 3 ) = 0.025, m(θ 2 ∩ θ 4 ) = 0.03, m(θ 3 ∩ θ 4 ) = 0.2525, m(θ 3 ) = 0.1375, m(θ 4 ) = 0.105.

Θ = {θ 1 ∆= Dark area, θ 2 ∆= Gray area, θ 3 ∆={ω 1 ∆= 2 ∆= 3 ∆= 4 ∆=

 1231234 White area}, whereas SPOT af ter image can be clustered k S = 4 groups as as Ω = Red area, ω Dark-red area, ω Green area, ω Dark-green area}.

  Fig.[], and the comparison results between the change occurrences extracted from Fig.[] and the ground truth are shown in Fig.[].

Figure 1 .Figure 4 .

 14 Figure 1. before image: 11/16/1999

  06,

	For the n-d singleton elements, one gets
		Bel(.) BetP (.) P l(.)
	(θ 1 , ω 1 )	0.18	0.225	0.27
	(θ 1 , ω 2 )	0.3	0.375	0.45
	(θ 1 , ω 3 )	0.12	0.15	0.18
	(θ 2 , ω 1 )	0.03	0.075	0.12
	(θ 2 , ω 2 )	0.05	0.125	0.2
	(θ 2 , ω 3 )	0.02	0.05	0.08

Actually, Shafer's model, considering all elements of the frame as truly exclusive, can be viewed as a special case of hybrid model.

DSmP (.) transformation proposed in[START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion[END_REF] (Vol.2) which provides of better probabilistic informational content than BetP (.) can also be chosen instead. But DSmP (.) is more complicated to implement than BetP (.) and it has not been tested in our application for now.


Évariste Daller

Sébastien Bougleux

Luc Brun

Olivier Lézoray
email: olivier.lezoray@unicaen.frluc.brun@ensicaen.fr

Local Patterns and Supergraph for Chemical Graph Classification with Convolutional Networks

Keywords: Graph-CNNs, graph classification, graph edit distance

Convolutional neural networks (CNN) have deeply impacted the field of machine learning. These networks, designed to process objects with a fixed topology, can readily be applied to images, videos and sounds but cannot be easily extended to structures with an arbitrary topology such as graphs. Examples of applications of machine learning to graphs include the prediction of the properties molecular graphs, or the classification of 3D meshes. Within the chemical graphs framework, we propose a method to extend networks based on a fixed topology to input graphs with an arbitrary topology. We also propose an enriched feature vector attached to each node of a chemical graph and a new layer interfacing graphs with arbitrary topologies with a full connected layer.

Introduction

Convolutional neural networks(CNN) [START_REF] Lecun | The handbook of brain theory and neural networks. chap[END_REF] have deeply impacted machine learning and related fields such as computer vision. These large breakthrough encouraged many researchers [START_REF] Bruna | Spectral networks and deep locally connected networks on graphs[END_REF][START_REF] Duvenaud | Convolutional networks on graphs for learning molecular fingerprints[END_REF][START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF][START_REF] Bronstein | Geometric deep learning: Going beyond euclidean data[END_REF] to extend the CNN framework to unstructured data such as graphs, point clouds or manifolds. The main motivation for this new trend consists in extending the initial successes obtained in computer vision to other fields such as indexing of textual documents, genomics, computer chemistry or indexing of 3D models.

The initial convolution operation defined within CNN, uses explicitly the fact that objects (e.g. pixels) are embedded within a plane and on a regular grid. These hypothesis do not hold when dealing with convolution on graphs. A first approach related to the graph signal processing framework uses the link between convolution and Fourier transform as well as the strong similarities between the Fourier transform and the spectral decomposition of a graph. Fig. 1: Illustration of our propositions on a graph convolutional network example, Bruna et al. [START_REF] Bruna | Spectral networks and deep locally connected networks on graphs[END_REF] define the convolution operation from the Laplacian spectrum of the graph encoding the first layer of the neural network. However this approach requires a costly decomposition into singular Laplacian values during the creation of the convolution network as well as costly matrices multiplications during the test phase. These limitations are partially solved by Defferard et al. [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF] who propose a fast implementation of the convolution based on Chebyshev polynomials (CGCNN). This implementation allows a recursive and efficient definition of the filtering operation while avoiding the explicit computation of the Laplacian. However, both methods are based on a fixed graph structure. Such networks can process different signals superimposed onto a fixed input layer but are unable to predict properties of graphs with variable topologies.

Another family of methods is based on a spatial definition of the graph convolution operation. Kipf and Welling [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF] proposed a model (CGN) which approximates the local spectral filters from [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF]. Using this formulation, filters are no longer based on the Laplacian but on a weight associated to each component of the vertices' features for each filter. The learning process of such weights is independent of the graph topology. Therefore graph neural networks based on this convolution scheme can predict properties of graphs with various topologies. The model proposed by Duvenaud et al. [START_REF] Duvenaud | Convolutional networks on graphs for learning molecular fingerprints[END_REF] for fingerprint extraction is similar to [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF], but considers a set of filters for each possible degree of vertices. These last two methods both weight each components of the vertices' feature vectors. Verma et al. [START_REF] Verma | FeaStNet: Feature-Steered Graph Convolutions for 3D Shape Analysis[END_REF] propose to attach a weight to edges through the learning of a parametric similarity measure between the features of adjacent vertices. Similarly, Simonovsky and Komodakis [START_REF] Simonovsky | Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs[END_REF] learn a weight associated to each edge label. Finally, Atwood and Towsley [START_REF] Atwood | Diffusion-convolutional neural networks[END_REF] (with DCNN) remove the limitation of the convolution to the direct neighborhood of each vertex by considering powers of a transition matrix defined as a normalization of the adjacency matrix by vertices' degrees. A main drawback of this non-spectral approach is that there exist intrinsically no best way to match the learned convolution weights with the elements of the receptive field, hence this variety of recent models.

In this paper, we propose to unify both spatial and spectral approaches by using as input layer a super-graph deduced from a graph train set. In addition, we propose an enriched feature vector within the framework of chemical graphs. Finally, we propose a new bottleneck layer at the end of our neural network which

HO C O OH Pattern C O C O C O O C O O O C O O Frequency 2 1 1 2 1
Fig. 2: Frequency of patterns associated to the central node (C).

is able to cope with the variable size of the previous layer. These contributions are described in Section 2 and evaluated in Section 3 through several experiments.

Contributions

2.1 From symbolic to feature graphs for convolution

Convolution cannot be directly applied to symbolic graphs. So symbols are usually transformed into unit vectors of {0, 1} |L| , where L is a set of symbols, as done in [START_REF] Atwood | Diffusion-convolutional neural networks[END_REF][START_REF] Duvenaud | Convolutional networks on graphs for learning molecular fingerprints[END_REF][START_REF] Simonovsky | Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs[END_REF] to encode atom's type in chemical graphs. This encoding has a main drawback, the size of convolution kernels is usually much smaller than |L|. Combined with the sparsity of vectors, this produces meaningless means for dimensionality reduction. Moreover, information attached to edges is usually unused.

Let us consider a graph G = (V, E, σ, φ), where V is a set of nodes, E ⊆ V ×V a set of edges, and σ and φ functions labeling respectively G's nodes and edges. To avoid these drawbacks, we consider for each node u of V a vector representing the distribution of small subgraphs covering this node. Let N u denotes its 1-hop neighbors. For any subset S ⊆ N u , the subgraph M S u = ({u} ∪ S, E ∩ ({u} ∪ S) × ({u} ∪ S), σ, φ) is connected (through u) and defines a local pattern of u. The enumerations of all subsets of N u provides all local patterns of u that can be organized as a feature vector counting the number of occurrences of each local pattern. Figure 2 illustrates the computation of such a feature vector. Note that the node's degree of chemical graphs is bounded and usually smaller than 4.

During the training phase, the patterns found for the nodes of the training graphs determine a dictionary as well as the dimension of the feature vector attached to each node. During the testing phase, we compute for each node of an input graph, the number of occurrences of its local patterns also present in the dictionary. A local pattern of the test set not present in the train set is thus discarded. In order to further enforce the compactness of our feature space, we apply a PCA on the whole set of feature vectors and project each vector onto a subspace containing 95% (fixed threshold) of the initial information.

Supergraph as input layer

As mentioned in section 1, methods based on spectral analysis [START_REF] Bruna | Spectral networks and deep locally connected networks on graphs[END_REF][START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF] require a fixed input layer. Hence, these methods can only process functions defined on a fixed graph topology (e.g. node's classification or regression tasks) and cannot be used to predict global properties of topologically variable graphs. We propose to remove this restriction by using as an input layer a supergraph deduced from graphs of a training set.

A common supergraph of two graphs G 1 and G 2 is a graph S so that both G 1 and G 2 are isomorphic to a subgraph of S. More generally, a common supergraph of a set of graphs

G = {G k = (V k , E k , σ k , φ k )} k=n k=1 is a graph S = (V S , E S , σ S , φ S ) so that any graph of G is isomorphic to a subgraph of S. So, given any two complementary subsets G 1 , G 2 ⊆ G, with G 1 ∪ G 2 = G, it
holds that a supergraph of a supergraph of G 1 and a supergraph of G 2 is a supergraph of G. The latter can thus be defined by applying this property recursively on the subsets. This describes a tree hierarchy of supergraphs, rooted at a supergraph of G, with the graphs of G as leaves. We present a method to construct hierarchically a supergraph so that it is formed of a minimum number of elements.

A common supergraph S of two graphs, or more generally of G, is a minimum common supergraph (MCS) if there is no other supergraph S of G with

|V S | < |V S | or (|V S | = |V S |)∧(|E S | < |E S |).
Constructing such a supergraph is difficult and can be linked to the following notion. A maximum common subgraph (mcs) of two graphs G k and G l is a graph G k,l that is isomorphic to a subgraph Ĝk of G k and to a subgraph Ĝl of G l , and so that there is no other common

subgraph G of both G k and G l with |V G | > |V G k,l | or (|V G | = |V G k,l |) ∧ (|E G | > |E G k,l |).
Then, given a maximum common subgraph G k,l , the graph S obtained from G k,l by adding the elements of G k not in Ĝk and the elements of G l not in Ĝl is a minimum common supergraph of G k and G l . This property shows that a minimum common supergraph can thus be constructed from a maximum common subgraph. These notions are both related to the notion of error-correcting graph matching and graph edit distance [START_REF] Bunke | On the minimum common supergraph of two graphs[END_REF].

The graph edit distance (GED) captures the minimal amount of distortion needed to transform an attributed graph G k into an attributed graph G l by iteratively editing both the structure and the attributes of G k , until G l is ob-tained. The resulting sequence of edit operations γ, called edit path, transforms G k into G l . Its cost (the strength of the global distortion) is measured by L c (γ) = o∈γ c(o), where c(o) is the cost of the edit operation o. Among all edit paths from G k to G l , denoted by the set Γ (G k , G l ), a minimal-cost edit path is a path having a minimal cost. The GED from G k to G l is defined as the cost of a minimal-cost edit path:

d(G k , G l ) = min γ∈Γ (G k ,G l ) L c (γ).
Under mild constraints on the costs [START_REF] Bougleux | Graph edit distance as a quadratic assignment problem[END_REF], an edit path can be organized into a succession of removals, followed by a sequence of substitutions and ended by a sequence of insertions. This reordered sequence allows to consider the subgraphs Ĝk of G k and Ĝl of G l . The subgraph Ĝk is deduced from G k by a sequence of node and edge removals, and the subgraph Ĝl is deduced from Ĝk by a sequence of substitutions (Figure 3a). By construction, Ĝk and Ĝl are structurally isomorphic, and an error-correcting graph matching (ECGM) between G k and G l is a bijective function f : Vk → Vl matching the nodes of Ĝk onto the ones of Ĝl (correspondences between edges are induced by f ).

Then ECGM, mcs and MCS are related as follows. For specific edit cost values [START_REF] Bunke | On the minimum common supergraph of two graphs[END_REF] (not detailed here), if f corresponds to an optimal edit sequence, then Ĝk and Ĝl are mcs of G k and G l . Moreover, adding to a mcs of G k and G l the missing elements from G k and G l leads to an MCS of these two graphs. We use this property to build the global supergraph of a set of graphs.

Supergraph construction

The proposed hierarchical construction of a common supergraph of a set of graphs G = {G i } i is illustrated by Fig. 3b. Each level k of the hierarchy contains N k graphs. They are merged by pairs to produce N k /2 supergraphs. In order to restrain the size of the final supergraph, a natural heuristic consists in merging close graphs according to the graph edit distance. This can be formalized as the computation of a maximum matching M , in the complete graph over the graphs of G, minimizing:

M = arg min M (gi,gj )∈M d(g i , g j ) (1)
where d(•, •) denotes the graph edit distance. An advantage of this kind of construction is that it is highly parallelizable. Nevertheless, computing the graph edit distance is NP-hard. Algorithms that solve the exact problem cannot be reasonably used here. So we considered a bipartite approximation of the GED [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] to compute d(•, •) and solve (1), while supergraphs are computed using a more precise but more computationally expansive algorithm [START_REF] Daller | Approximate Graph Edit Distance by Several Local Searches in Parallel[END_REF].

Projections as input data

The supergraph computed in the previous section can be used as an input layer of a graph convolutional neural network based on spectral graph theory [START_REF] Bruna | Spectral networks and deep locally connected networks on graphs[END_REF][START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF] (Section 1). Indeed, the fixed input layer allows to consider convolution operations based on the Laplacian of the input layer. However, each input graph for which a property has to be predicted, must be transformed into a signal on the supergraph. This last operation is allowed by the notion of projection, a side notion of the graph edit distance.

Definition 1 (Projection). Let f be an ECGM between two graphs G and S and let ( VS , ÊS ) be the subgraph of S defined by f (Fig. 3). A projection of G = (V, E, σ, φ) onto S = (V S , E S , σ S , φ S ) is a graph P f S (G) = (V S , E S , σ P , φ P ) where σ P (u) = (σ • f -1 )(u) for any u ∈ VS and 0 otherwise. Similarly, φ P ({u, v}) = φ({f -1 (u), f -1 (v)}) for any {u, v} in ÊS and 0 otherwise.

Let {G 1 , . . . , G n } be a graph training set and S its the associated supergraph. The projection P f S (G i ) of a graph G i induces a signal on S associated to a value to be predicted. For each node of S belonging to the projection of G i , this signal is equal to the feature vector of this node in G i . This signal is null outside the projection of G i . Moreover, if the edit distance between G i and S can be computed through several edit paths with a same cost (i.e., several ECGM f 1 , . . . , f m ), the graph G i will be associated to these projections P f1 S (G i ), . . . , P fm S (G i ). Remark that a graph belonging to a test dataset may also have several projections. In this case, it is mapped onto the majority class among its projections. A natural data augmentation can thus be obtained by learning m equivalent representations of a same graph on the supergraph, associated to the same value to be predicted. Note that this data augmentation can also be increased by considering µm nonminimal ECGM, where µ is a parameter. To this end, we use [START_REF] Daller | Approximate Graph Edit Distance by Several Local Searches in Parallel[END_REF] to compute a set of non-minimal ECGM between an input graph G i and the supergraph S and we sort this set increasingly according to the cost of the associated edit paths.

Bottleneck layer with variable input size

A multilayer perceptron (MLP), commonly used in the last part of multilayer networks, requires that the previous layer has a fixed size and topology. Without the notion of supergraph, this last condition is usually not satisfied. Indeed, the size and topology of intermediate layers are determined by those of the input graphs, which generally vary. Most of graph neural networks avoid this drawback by performing a global pooling step through a bottleneck layer. This usually consists in averaging the components of the feature vectors across the nodes of the current graph, the so-called global average pooling (GAP). If for each node v ∈ V of the previous layer, the feature vector h(v) ∈ R D has a dimension D, GAP produces a mean vector ( 1|V | v∈V h c (v)) c=1,...,D describing the graph globally in the feature space.

We propose to improve the pooling step by considering the distribution of feature activations across the graph. A simple histogram can not be used here, due to its non-differentiability, differentiability being necessary for backpropagation. To guarantee this property holds, we propose to interpolate the histogram by using averages of Gaussian activations. For each component c of a given a feature vector h(v), the height of a bin k of this pseudo-histogram is computed as follows:

b ck (h) = 1 |V | v∈V exp -(h c (v) -µ ck ) 2 σ 2 ck ( 2
)
The size of the layer is equal to D × K, where K is the number of bins defined for each component. In this work, the parameters µ ck and σ ck are fixed and not learned by the network. To choose them properly, the model is trained with a GAP layer for few iterations (10 in our experiments), then it is replaced by the proposed layer. The weights of the network are preserved, and the parameters µ ck are uniformly spread between the minimum and the maximum values of h c (v). The parameters σ ck are fixed to σ ck = δ µ /3 with δ µ = µ ci+1 -µ ci , ∀1 ≤ i < K, to ensure an overlap of the Gaussian activations.

Since this layer has no learnable parameters, the weights α c (i) of the previous layer h are adjusted during the backpropagation for every node i ∈ V , according to the partial derivatives of the loss function

L: ∂L ∂αc(i) = ∂L ∂b ck (h) ∂b ck (h) ∂hc(i) ∂hc(i)
∂αc(i) . The derivative of the bottleneck layer w.r.t. its input is given by:

∀i ∈ V, ∂b ck (h) ∂h c (i) = -2(h c (i) -µ ck ) |V |σ 2 ck exp -(h c (i) -µ ck ) 2 σ 2 ck . (3)
It lies between -

√ 2
|V |σ ck e -1/2 and √ 2

|V |σ ck e -1/2 .

Experiments

We compared the behavior of several graph convolutional networks, with and without the layers presented in the previous section, for the classification of chemical data encoded by graphs. The following datasets were used: NCI1, MU-TAG, ENZYMES, PTC, and PAH. Table 1 summarizes their main characteristics. NCI1 [START_REF] Wale | Comparison of descriptor spaces for chemical compound retrieval and classification[END_REF] contains 4110 chemical compounds, labeled according to their capacity to inhibit the growth of certain cancerous cells. MUTAG [START_REF] Debnath | Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity[END_REF] contains 188 aromatic and heteroaromatic nitrocompounds, the mutagenicity of which has to be predicted. ENZYMES [START_REF] Borgwardt | Protein function prediction via graph kernels[END_REF] contains 600 proteins divided into 6 classes of enzymes (100 per class). PTC [START_REF] Toivonen | Statistical evaluation of the predictive toxicology challenge 2000-2001[END_REF] contains 344 compounds labeled as carcinogenic or not for rats and mice. PAH3 contains non-labeled cyclic carcinogenic and non-carcinogenic molecules.

Baseline for classification

We considered three kinds of graph convolutional networks. They differ by the definition of their convolutional layer. CGCNN [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF] is a deep network based on a pyramid of reduced graphs. Each reduced graph corresponds to a layer of the network. The convolution is realized by spectral analysis and requires the computation of the Laplacian of each reduced graph. The last reduced graph is followed by a fully connected layer. GCN [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF] and DCNN [START_REF] Atwood | Diffusion-convolutional neural networks[END_REF] networks do not use spectral analysis and are referred to as spatial networks. GCN can be seen as an approximation of [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF]. Each convolutional layer is based on F filtering operations associating a weight to each component of the feature vectors attached to nodes. These weighted vectors are then combined through a local averaging. DCNN [START_REF] Atwood | Diffusion-convolutional neural networks[END_REF] is a nonlocal model in which a weight on each feature is associated to a hop h < H and hence to a distance to a central node (H is thus the radius of a ball centered on this central node). The averaging of the weighted feature vectors is then performed on several hops for each node.

To measure the effects of our contributions when added to the two spatial networks (DCNN and GCN), we considered several versions obtained as follows (Table 2). We used two types of characteristics attached to the nodes of the graphs (input layer): characteristics based on the canonical vectors of {0, 1} |L| as in [START_REF] Atwood | Diffusion-convolutional neural networks[END_REF][START_REF] Duvenaud | Convolutional networks on graphs for learning molecular fingerprints[END_REF][START_REF] Simonovsky | Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs[END_REF], and those based on the patterns proposed in Section 1. Note that PAH has few different patterns (Table 1), PCA was therefore not applied to this data to reduce the size of features. Since spatial networks can handle arbitrary topology graphs, the use of a supergraph is not necessary. However, since some nodes have a null feature in a supergraph (Definition 1), a convolution performed on a graph gives results different from those obtained by a similar convolution performed on the projection of the graph on a supergraph. We hence decided to test spatial networks with a supergraph. For the other network (CGCNN), we used the features based on patterns and a supergraph.

For the architecture of spatial networks, we followed the one proposed by [START_REF] Atwood | Diffusion-convolutional neural networks[END_REF], with a single convolutional layer. For CGCNN we used two convolutional layers to take advantage of the coarsening as it is part of this method. For DCNN, H = 4. For CGCNN and GCN, F = 32 filters were used. The optimization was achieved by Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF], with at most 500 epochs and early stopping. The experiments were done in 10 fold cross-validation which required to compute the supergraphs of all training graphs. Datasets were augmented by 20% of nonminimal cost projections with the method described in Section 2.3.

Discussion

As illustrated in Table 2, the features proposed in Section 2.1 improve the classification rate in most cases. For some datasets, the gain is higher than 10 per- centage points. The behavior of the two spatial models (DCNN and GCN) is also improved, for every dataset, by replacing global average pooling by the histogram bottleneck layer described in Section 2.4. These observations point out the importance of the global pooling step for these kind of networks Using a supergraph as an input layer (column s-g) opens the field of action of spectral graph convolutional networks to graphs with different topologies, which is an interesting result in itself. Results are comparable to the ones obtained with the other methods (improve the baseline models with no histogram layer), but this is a first result for these networks for the classification of graphs. The sizes of supergraphs reported in Table 1 remain reasonable regarding the number of graphs and the maximum size in each dataset. Nevertheless, this strategy only enlarge each data up to the supergraph size.

Conclusions

We proposed features based on patterns to improve the performances of graph neural networks on chemical graphs. We also proposed to use a supergraph as input layer in order to extend graph neural networks based on spectral theory to the prediction of graph properties for arbitrary topology graphs. The supergraph can be combined with any graph neural network, and for some datasets the performances of graph neural networks not based on spectral theory were improved. Finally, we proposed an alternative to the global average pooling commonly used as bottleneck layer in the final part of these networks.

  For

Fig. 3 :

 3 Fig. 3: Construction of a supergraph (b) using common subgraphs induced by the Graph Edit Distance (a).

Table 1 :

 1 Characteristics of datasets. V and E denotes resp. nodes and edges sets of the datasets' graphs, while V S and E S denotes nodes and edges sets of the datasets' supergraphs

		NCI1	MUTAG ENZYMES	PTC	PAH
	#graphs	4110	188	600	344	94
	mean |V |, mean |E|	(29.9, 32.3) (17.9, 19.8) (32.6, 62.1) (14.3, 14.7) (20.7, 24,4)
	mean |VS|	192.8	42.6	177.1	102.6	26.8
	mean |ES|	4665	146	1404	377	79
	#labels, #patterns	(37, 424)	(7, 84)	(3, 240)	(19, 269)	(1, 4)
	#classes	2	2	6	2	2
	#positive, #negative (2057, 2053) (125, 63)	-	(152, 192)	(59, 35)

Table 2 :

 2 Mean accuracy (10-fold cross validation) of graph classification by three networks (GConv), with the features proposed in Section 2.1 (feat.) and the supergraph (s-g). Global pooling (gpool) is done using global average pooling (GAP) or with histogram bottleneck layer (hist).

	GConv feat. s-g gpool	NCI1 MUTAG ENZYMES PTC PAH
	-	-GAP	62.61	66.98	18.10	56.60 57.18
	DCNN	-GAP -hist	67.81 71.47	81.74 82.22	31.25 38.55	59.04 54.70 60.43 66.90
		hist	73.95 83.57	40.83	56.04 71.35
	-	-GAP	55.44	70.79	16.60	52.17 63.12
	GCN	-GAP -hist	66.39 74.76 82.86 82.22	32.36 37.90	58.43 57.80 62.78 72.80
		hist	73.02	80.44	46.23	61.60 71.50
	CGCNN	-	68.36	75.87	33.27	60.78 63.73

PAH is available at: https://iapr-tc15.greyc.fr/links.html