Introduction
Background Among various application areas of bioinformatics and machine learning, drug design is gathering interest [1 , 2 ] . Accordingly, extensive studies have been done on computational analysis of chemical structures. There are two major topics in such studies: prediction of the chemical property of a given chemical structure, and design of a chemical structure having a desired chemical property. These topics have also been extensively studied in the field of cheminformatics, where the former one is referred to as quantitative structure activity relationship (QSAR) [3 ] and the latter as inverse quantitative structure activity relationship (inverse QSAR) [4 , 5 , 6 ] .
For the prediction task, statistical methods and machine learning methods have been extensively utilized [3 ] . In most of such studies, there are two phases: learning phase and prediction phase. In the learning phase, a prediction function is derived from training data consisting of pairs of chemical structures and their activities (or properties), where each chemical structure is given as an undirected graph (called a chemical graph) and then is transformed into a vector of real numbers called features or descriptors . In the prediction phase, the prediction function derived as above is simply applied to the feature vector obtained from a given chemical graph. To derive a prediction function, regression-based methods have been utilized in traditional QSAR studies [3 ] , where machine learning-based methods, including artificial neural network (ANN)-based methods [7 , 8 ] , have recently been extensively utilized. It is to be noted that when using graph convolutional networks (GCNs) [9 ] , chemical graphs can be directly handled and thus transformation to feature vectors is not necessarily required.
For the design task, prediction functions are also utilized and are usually derived from existing data as in the above. Then, chemical structures are inferred from given chemical activities through a prediction function [4 , 5 , 6 ] where additional constraints may be imposed to restrict the possible structures. In the traditional approach, this inference task consists of two phases, (i) derivation of feature vectors from given chemical activities using the inverse of the prediction function, and (ii) reconstruction of chemical structures from given feature vectors, where these two phases are often mixed. For (i), some optimization methods and/or sampling methods are usually employed. For (ii), some enumeration methods are often applied. However, both are inverse problems and are computationally difficult. For example, it is known that the number of possible chemical graphs is huge [10 ] and inference of a chemical graph from a given feature vector is NP-hard in general [11 ] . Therefore, most existing methods employ heuristic methods for both (i) and (ii), and thus do not guarantee optimal or exact solutions.
Recently, different approaches have been proposed for the design task using ANNs. One of the attractive points of ANNs is that generative models are available, which include autoencoders and generative adversarial networks. Furthermore, as mentioned before, chemical structures can be directly handled by using GCNs [9 ] . By combining these techniques, it might be possible to design novel chemical structures without solving the inverse problems [12 ] . Indeed, extensive studies have recently been done using various ANN models, which include variational autoencoders [13 ] , grammar variational autoencoders [14 ] , generative adversarial networks [15 ] , recurrent neural networks [16 , 17 ] , and invertible flow models [18 , 19 ] . However, these are heuristic methods (although based on some statistical models) and thus do not guarantee optimality or exactness of the solutions.
Framework A novel framework for inferring chemical graphs has been developed [20 , 21 , 22 , 23 ] based on an idea of formulating as a mixed integer linear programming (MILP), the computation process of a prediction function constructed by a machine learning method. The unique point of this framework is that once a prediction function is formulated, the inverse problem can be solved exactly by applying an MILP solver. It consists of two main phases: the first phase constructs a prediction function η \eta η for a chemical property and the second phase infers a chemical graph with a target value of the property based on the function η \eta η . For a chemical property π \pi π , let C π C_{\pi} C π be a data set of chemical graphs such that the observed value a ( C ) a(C) a ( C ) of property π \pi π for every chemical graph C ∈ C π C \in C_{\pi} C ∈ C π is available. In the first phase, we introduce a feature function f : G → R K f:\mathcal{G} \to\mathbb{R}^{K} f : G → R K for a positive integer K K K , where the descriptors of a chemical graph are defined based on local graph structures in a special way called a two-layered model . We then construct a prediction function
η \eta η by a machine learning method such as linear regression, decision tree and an ANN so that the output y = η ( x ) ∈ R y=\eta(x)\in\mathbb{R} y = η ( x ) ∈ R of the feature vector x = f ( C ) ∈ R K x=f(\mathcal{C})\in\mathbb{R}^{K} x = f ( C ) ∈ R K for each C ∈ C π \mathcal{C}\in\mathcal{C}_{\pi} C ∈ C π serves as a predicted value to the real value a ( C ) a(\mathcal{C}) a ( C ) . In the second phase of inferring a desired chemical graph, we specify not only a target chemical value for property π \pi π but also an abstract structure for a chemical graph to be inferred. The latter is described by a set of rules based on the two-layered model called a topological specification σ \sigma σ , and denote by G σ \mathcal{G}_{\sigma} G σ the set of all chemical graphs that satisfy the rules in σ \sigma σ . The users select topological specification σ \sigma σ and two reals y ‾ ∗ \underline{y}^{*} y ∗ and y ‾ ∗ \overline{y}^{*} y ∗ as an interval for a target chemical value. The task of the second phase is to infer chemical graphs C ∗ ∈ G σ \mathcal{C}^{*}\in\mathcal{G}_{\sigma} C ∗ ∈ G σ such that y ‾ ∗ ≤ η ( f ( C ∗ ) ) ≤ y ‾ ∗ \underline{y}^{*}\leq\eta(f(\mathcal{C}^{*}))\leq\overline{y}^{*} y ∗ ≤ η ( f ( C ∗ )) ≤ y ∗ (see Figure 1 for an illustration). For this, we formulate an MILP M f , η , σ \mathcal{M}_{f,\eta,\sigma} M f , η , σ that represents (i) the computation process of x : = f ( C ) x:=f(\mathcal{C}) x := f ( C ) from a chemical graph C \mathcal{C} C in the feature function f f f ; (ii) the computation process of y : = η ( x ) y:=\eta(x) y := η ( x ) from a vector x ∈ R K x\in\mathbb{R}^{K} x ∈ R K in the prediction function η \eta η ; and (iii) the constraint for C ∈ G σ \mathcal{C}\in\mathcal{G}_{\sigma} C ∈ G σ . Given an interval with y ‾ ∗ , y ‾ ∗ ∈ R \underline{y}^{*},\overline{y}^{*}\in\mathbb{R} y ∗ , y ∗ ∈ R , we solve the MILP M f , η , σ \mathcal{M}_{f,\eta,\sigma} M f , η , σ to find a feature vector x ∗ ∈ R K x^{*}\in\mathbb{R}^{K} x ∗ ∈ R K and a chemical graph C † ∈ G σ \mathcal{C}^{\dagger}\in\mathcal{G}_{\sigma} C † ∈ G σ such that f ( C † ) = x ∗ f(\mathcal{C}^{\dagger})=x^{*} f ( C † ) = x ∗ and y ‾ ∗ ≤ η ( x ∗ ) ≤ y ‾ ∗ \underline{y}^{*}\leq\eta(x^{*})\leq\overline{y}^{*} y ∗ ≤ η ( x ∗ ) ≤ y ∗ (where if the MILP instance is infeasible then this suggests that G σ \mathcal{G}_{\sigma} G σ does not contain such a desired chemical graph). In the second phase, we next generate some other desired chemical graphs based on the solution C † \mathcal{C}^{\dagger} C † . For this, the following two methods have been designed.
Figure 1. An illustration of inferring desired chemical graphs C ∈ G σ \mathcal{C} \in\mathcal{G}_{\sigma} C ∈ G σ with y ‾ ∗ ≤ η ( f ( C ) ) ≤ y ‾ ∗ \underline{y}^{*} \leq\eta(f(\mathcal{C})) \leq\overline{y}^{*} y ∗ ≤ η ( f ( C )) ≤ y ∗ .
The first method constructs isomers of C † \mathcal{C}^{\dagger} C † without solving any new MILP. In this method, we first decompose the chemical graph C † \mathcal{C}^{\dagger} C † into a set of chemical acyclic graphs T 1 † , T 2 † , … , T q † T_{1}^{\dagger},T_{2}^{\dagger},\ldots,T_{q}^{\dagger} T 1 † , T 2 † , … , T q † , and next construct a set T i \mathcal{T}_{i} T i of isomers T i ∗ T_{i}^{*} T i ∗ of each tree T i † T_{i}^{\dagger} T i † such that f ( T i ∗ ) = f ( T i † ) f(T_{i}^{*})=f(T_{i}^{\dagger}) f ( T i ∗ ) = f ( T i † ) by a dynamic programming algorithm due to Azam et al. [24 ] . Finally we choose an isomer T i ∗ ∈ T i T_{i}^{*}\in\mathcal{T}_{i} T i ∗ ∈ T i for each i = 1 , 2 , … , q i=1,2,\ldots,q i = 1 , 2 , … , q and assemble them into an isomer C ∗ ∈ G σ \mathcal{C}^{*}\in\mathcal{G}_{\sigma} C ∗ ∈ G σ of C † \mathcal{C}^{\dagger} C † such that f ( C ∗ ) = x ∗ = f ( C † ) f(\mathcal{C}^{*})=x^{*}=f(\mathcal{C}^{\dagger}) f ( C ∗ ) = x ∗ = f ( C † ) . The first method generates such isomers C 1 ∗ , C 2 ∗ , … \mathcal{C}_{1}^{*},\mathcal{C}_{2}^{*},\ldots C 1 ∗ , C 2 ∗ , … which we call recombination solutions of C † \mathcal{C}^{\dagger} C † .
The second method constructs new solutions by solving the MILP M f , η , σ \mathcal{M}_{f,\eta,\sigma} M f , η , σ with an additional set Θ \Theta Θ of new linear constraints [23 ] . We first prepare arbitrary p d i m p_{\mathrm{dim}} p dim linear functions θ j : R K → R , j = 1 , 2 , … , p d i m \theta_{j}:\mathbb{R}^{K}\to\mathbb{R},j=1,2,\ldots,p_{\mathrm{dim}} θ j : R K → R , j = 1 , 2 , … , p dim and consider a neighbor of C † \mathcal{C}^{\dagger} C † defined by a set of chemical graphs C ∗ \mathcal{C}^{*} C ∗ that satisfy linear constraints ( k − 0.5 ) δ ≤ ∣ θ j ( f ( C ∗ ) ) − θ j ( f ( C † ) ) ∣ ≤ ( k + 0.5 ) δ , j = 1 , 2 , … , p d i m (k-0.5)\delta\leq\left|\theta_{j}(f(\mathcal{C}^{*}))-\theta_{j}(f(\mathcal{C}^{\dagger}))\right|\leq(k+0.5)\delta,j=1,2,\ldots,p_{\mathrm{dim}} ( k − 0.5 ) δ ≤ θ j ( f ( C ∗ )) − θ j ( f ( C † )) ≤ ( k + 0.5 ) δ , j = 1 , 2 , … , p dim for a small real δ > 0 \delta> 0 δ > 0 and an integer k ≥ 1 k \ge1 k ≥ 1 . By changing the integer k k k systematically, we can search for new solutions C 1 † , C 2 † , … ∈ G σ \mathrm{C}^{\dagger}_{1},\mathrm{C}^{\dagger}_{2},\ldots\in\mathcal{G}_{\sigma} C 1 † , C 2 † , … ∈ G σ of MILP M f , η , σ \mathcal{M}_{f,\eta,\sigma} M f , η , σ with constraint Θ \Theta Θ such that the feature vectors x ∗ = f ( C 1 † ) , x 1 ∗ = f ( C 1 † ) , x 2 ∗ = f ( C 2 † ) , … \boldsymbol{x}^{*}=f(\mathrm{C}^{\dagger}_{1}),\boldsymbol{x}^{*}_{1}=f(\mathrm{C}^{\dagger}_{1}),\boldsymbol{x}^{*}_{2}=f(\mathrm{C}^{\dagger}_{2}),\ldots x ∗ = f ( C 1 † ) , x 1 ∗ = f ( C 1 † ) , x 2 ∗ = f ( C 2 † ) , … are all slightly different. We call these chemical graphs C 1 † , C 2 † , … \mathrm{C}^{\dagger}_{1},\mathrm{C}^{\dagger}_{2},\ldots C 1 † , C 2 † , … neighbor solutions of C 1 † \mathrm{C}^{\dagger}_{1} C 1 † .
The main reason why the framework can infer a chemical compound with 50 non-hydrogen atoms is that the descriptors of a chemical graph are defined on local graph structures in the two-layered model and thereby an MILP necessary to represent a chemical graph can be formulated as a considerably compact form that is efficiently solvable by a standard solver.
Contribution The descriptors in the framework mainly consists of the frequencies of local graph structures based on the two-layered model by which a chemical graph C \mathrm{C} C is regarded as a pair of interior and exterior structures (see § 3 for details). To derive a compact MILP formulation to infer a chemical graph, it is important to use the current definition of descriptors. However, there are some chemical properties for which the performance of a prediction function constructed with the feature function f f f remains rather low. To improve the learning performance of prediction functions with the same two-layered model, we propose a method of splitting a given data set with a hyperplane in the feature space into two subsets, where we construct a prediction function to each of the subsets independently before a prediction function η \eta η to the original set is obtained by combining these prediction functions (see § 5 for details). Based on the same MILP M f , η , σ \mathcal{M}_{f,\eta,\sigma} M f , η , σ formulation proposed by Zhu et al. [21 ] , we implemented the framework to treat the newly proposed type of prediction. From the results of our computational experiments on over some chemical properties such as odor threshold [30 ] , we observe that our new method of splitting data sets and combining prediction functions improved the performance of a prediction function for these chemical properties. It is to be noted that extensive studies have been done on prediction problems using hyperplanes since the development of support vector machines [25 ] . However, existing methods can only be applied to prediction problems. The novel and unique point of our study is that an efficient MILP formulation for chemical graphs is developed, which makes the inverse problem (i.e., design problem) tractable.
The paper is organized as follows. Section 2 introduces some notions on graphs and a modeling of chemical compounds. Section 3 reviews the two-layered model and descriptors defined by the model. Section 4 reviews prediction functions constructed by linear regression. Section 5 proposes a method of splitting a data set by a hyperplane and a linear programming formulation for finding such a hyperplane. Section 6 reports the results on computational experiments conducted for 22 chemical properties such as autoignition temperature, flammable limits and odor threshold. Section 7 makes some concluding remarks. Some technical details are given in Appendices: Appendix A for all descriptors in our feature function; Appendix B for a full description of a topological specification; and Appendix C for the detail of test instances used in our computational experiment.
Preliminary
This section introduces some notions and terminologies on graphs, modeling of chemical compounds and our choice of descriptors.
Let R \mathbb{R} R , R + \mathbb{R}_{+} R + , Z \mathbb{Z} Z and Z + \mathbb{Z}_{+} Z + denote the sets of reals, non-negative reals, integers and non-negative integers, respectively. For two integers a a a and b b b , let [ a , b ] [a,b] [ a , b ] denote the set of integers i i i with a ≤ i ≤ b a \le i \le b a ≤ i ≤ b . For a vector x ∈ R p x \in\mathbb{R}^{p} x ∈ R p , the j j j -th entry of x x x is denoted by x ( j ) x(j) x ( j ) .
Graph Given a graph G G G , let V ( G ) V(G) V ( G ) and E ( G ) E(G) E ( G ) denote the sets of vertices and edges, respectively. For a subset V ′ ⊆ V ( G ) V^{\prime} \subseteq V(G) V ′ ⊆ V ( G ) (resp., E ′ ⊆ E ( G ) E^{\prime} \subseteq E(G) E ′ ⊆ E ( G ) ) of a graph G G G , let G − V ′ G - V^{\prime} G − V ′ (resp., G − E ′ G - E^{\prime} G − E ′ ) denote the graph obtained from G G G by removing the vertices in V ′ V^{\prime} V ′ (resp., the edges in E ′ E^{\prime} E ′ ), where we remove all edges incident to a vertex in V ′ V^{\prime} V ′ to obtain G − V ′ G - V^{\prime} G − V ′ . A path with two end-vertices u u u and v v v is called a u , v u,v u , v -path.
We define a rooted graph to be a graph with a designated vertex, called a root . For a graph G G G possibly with a root, a leaf-vertex is defined to be a non-root vertex with degree 1. Call the edge u v uv uv incident to a leaf vertex v v v a leaf-edge , and denote by V l e a f ( G ) V_{\mathrm{leaf}}(G) V leaf ( G ) and E l e a f ( G ) E_{\mathrm{leaf}}(G) E leaf ( G ) the sets of leaf-vertices and leaf-edges in G G G , respectively. For a graph or a rooted graph G G G , we define graphs G i G_i G i , i ∈ Z + i \in\mathbb{Z}_{+} i ∈ Z + obtained from G G G by removing the set of leaf-vertices i i i times so that
G 0 : = G ; G i + 1 : = G i − V l e a f ( G i ) , G_0 := G;\quad G_{i+1} := G_i - V_{\mathrm{leaf}}(G_i), G 0 := G ; G i + 1 := G i − V leaf ( G i ) ,
where we call a vertex v v v a tree vertex if v ∈ V l e a f ( G i ) v \in V_{\mathrm{leaf}}(G_i) v ∈ V leaf ( G i ) for some i ≥ 0 i \ge0 i ≥ 0 . Define the height ht ( v ) \operatorname{ht}(v) ht ( v ) of each tree vertex v ∈ V l e a f ( G i ) v \in V_{\mathrm{leaf}}(G_i) v ∈ V leaf ( G i ) to be i i i ; and ht ( v ) \operatorname{ht}(v) ht ( v ) of each non-tree vertex v v v adjacent to a tree vertex to be ht ( u ) + 1 \operatorname{ht}(u) + 1 ht ( u ) + 1 for the maximum ht ( u ) \operatorname{ht}(u) ht ( u ) of a tree vertex u u u adjacent to v v v , where we do not define height of any non-tree vertex not adjacent to any tree vertex. We call a vertex v v v with ht ( v ) = k \operatorname{ht}(v) = k ht ( v ) = k a *leaf k k k -branch. The height ht ( T ) \operatorname{ht}(T) ht ( T ) of a rooted tree T T T is defined to be the maximum of ht ( v ) \operatorname{ht}(v) ht ( v ) of a vertex v ∈ V ( T ) v \in V(T) v ∈ V ( T ) .
Modeling of Chemical Compounds
We review a modeling of chemical compounds introduced by Zhu et al. [21 ] .
To represent a chemical compound, we introduce a set of chemical elements such as H (hydrogen), C (carbon), O (oxygen), N (nitrogen) and so on. To distinguish a chemical element a with multiple valences such as S (sulfur), we denote a chemical element a with a valence i i i by a ( i ) a_{(i)} a ( i ) , where we do not use such a suffix ( i ) (i) ( i ) for a chemical element a with a unique valence. Let Λ \Lambda Λ be a set of chemical elements a ( i ) a_{(i)} a ( i ) . For example, Λ = { H , C , O , N , P , S ( 2 ) , S ( 4 ) , S ( 6 ) } \Lambda= \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}, \mathrm{P}, \mathrm{S}_{(2)}, \mathrm{S}_{(4)}, \mathrm{S}_{(6)}\} Λ = { H , C , O , N , P , S ( 2 ) , S ( 4 ) , S ( 6 ) } . Let val : Λ → [ 1 , 6 ] \operatorname{val} : \Lambda\to[1,6] val : Λ → [ 1 , 6 ] be a valence function. For example, val ( H ) = 1 \operatorname{val}(\mathrm{H}) = 1 val ( H ) = 1 , val ( C ) = 4 \operatorname{val}(\mathrm{C}) = 4 val ( C ) = 4 , val ( O ) = 2 \operatorname{val}(\mathrm{O}) = 2 val ( O ) = 2 , val ( P ) = 5 \operatorname{val}(\mathrm{P}) = 5 val ( P ) = 5 , val ( S ( 2 ) ) = 2 \operatorname{val}(\mathrm{S}_{(2)}) = 2 val ( S ( 2 ) ) = 2 , val ( S ( 4 ) ) = 4 \operatorname{val}(\mathrm{S}_{(4)}) = 4 val ( S ( 4 ) ) = 4 and val ( S ( 6 ) ) = 6 \operatorname{val}(\mathrm{S}_{(6)}) = 6 val ( S ( 6 ) ) = 6 . For each chemical element a ∈ Λ a \in\Lambda a ∈ Λ , let mass ( a ) \operatorname{mass}(a) mass ( a ) denote the mass of a a a .
A chemical compound is represented by a chemical graph defined to be a tuple C = ( H , α , β ) \mathcal{C} = (H,\alpha,\beta) C = ( H , α , β ) of a simple, connected undirected graph H H H and functions α : V ( H ) → Λ \alpha: V(H) \to\Lambda α : V ( H ) → Λ and β : E ( H ) → [ 1 , 3 ] \beta: E(H) \to[1,3] β : E ( H ) → [ 1 , 3 ] . The set of atoms and the set of bonds in the compound are represented by the vertex set V ( H ) V(H) V ( H ) and the edge set E ( H ) E(H) E ( H ) , respectively. The chemical element assigned to a vertex v ∈ V ( H ) v \in V(H) v ∈ V ( H ) is represented by α ( v ) \alpha(v) α ( v ) and the bond-multiplicity between two adjacent vertices u , v ∈ V ( H ) u,v \in V(H) u , v ∈ V ( H ) is represented by β ( e ) \beta(e) β ( e ) of the edge e = u v ∈ E ( H ) e = uv \in E(H) e = uv ∈ E ( H ) . We say that two tuples ( H i , α i , β i ) (H_i,\alpha_i,\beta_i) ( H i , α i , β i ) , i = 1 , 2 i = 1,2 i = 1 , 2 are isomorphic if they admit an isomorphism ϕ \phi ϕ , i.e., a bijection ϕ : V ( H 1 ) → V ( H 2 ) \phi: V(H_1) \to V(H_2) ϕ : V ( H 1 ) → V ( H 2 ) such that u v ∈ E ( H 1 ) , α 1 ( u ) = a , α 1 ( v ) = b , β 1 ( u v ) = m ⇔ ϕ ( u ) ϕ ( v ) ∈ E ( H 2 ) , α 2 ( ϕ ( u ) ) = a , α 2 ( ϕ ( v ) ) = b , uv \in E(H_1), \alpha_1(u) = a, \alpha_1(v) = b, \beta_1(uv) = m \Leftrightarrow\phi(u)\phi(v) \in E(H_2), \alpha_2(\phi(u)) = a, \alpha_2(\phi(v)) = b, uv ∈ E ( H 1 ) , α 1 ( u ) = a , α 1 ( v ) = b , β 1 ( uv ) = m ⇔ ϕ ( u ) ϕ ( v ) ∈ E ( H 2 ) , α 2 ( ϕ ( u )) = a , α 2 ( ϕ ( v )) = b , \beta_2(\phi(u)\phi(v)) = m. W h e n . When . W h e n H_i is rooted at a vertex r i r_i r i , i = 1 , 2 i = 1, 2 i = 1 , 2 , these chemical graphs ( H i , α i , β i ) (H_i,\alpha_i,\beta_i) ( H i , α i , β i ) , i = 1 , 2 i = 1, 2 i = 1 , 2 are rooted-isomorphic (r-isomorphic) if they admit an isomorphism ϕ \phi ϕ such that ϕ ( r 1 ) = r 2 \phi(r_1) = r_2 ϕ ( r 1 ) = r 2 .
For a notational convenience, we use a function β C : V ( H ) → [ 0 , 12 ] \beta_{\mathrm{C}}: V(H) \to[0,12] β C : V ( H ) → [ 0 , 12 ] for a chemical graph C = ( H , α , β ) \mathrm{C} = (H,\alpha,\beta) C = ( H , α , β ) such that β C ( u ) \beta_{\mathrm{C}}(u) β C ( u ) means the sum of bond-multiplicities of edges incident to a vertex u u u ; i.e.,
β C ( u ) = △ ∑ u v ∈ E ( H ) β ( u v ) \beta_{\mathrm{C}}(u) \mathrel{\overset{\triangle}{=}} \sum_{uv \in E(H)} \beta(uv) β C ( u ) = △ uv ∈ E ( H ) ∑ β ( uv )
for each vertex u ∈ V ( H ) u \in V(H) u ∈ V ( H ) .
For each vertex u ∈ V ( H ) u \in V(H) u ∈ V ( H ) , define the electron-degree eledeg C ( u ) \operatorname{eledeg}_{\mathrm{C}}(u) eledeg C ( u ) to be
eledeg C ( u ) = △ β C ( u ) − val ( α ( u ) ) . \operatorname{eledeg}_{\mathrm{C}}(u) \mathrel{\overset{\triangle}{=}} \beta_{\mathrm{C}}(u) - \operatorname{val}(\alpha(u)). eledeg C ( u ) = △ β C ( u ) − val ( α ( u )) .
For each vertex u ∈ V ( H ) u \in V(H) u ∈ V ( H ) , let deg C ( v ) \operatorname{deg}_{\mathrm{C}}(v) deg C ( v ) denote the number of vertices adjacent to u u u in C \mathrm{C} C .
For a chemical graph C = ( H , α , β ) \mathrm{C} = (H,\alpha,\beta) C = ( H , α , β ) , let V a ( C ) V_a(\mathrm{C}) V a ( C ) , a ∈ Λ a \in\Lambda a ∈ Λ denote the set of vertices v ∈ V ( H ) v \in V(H) v ∈ V ( H ) such that α ( v ) = a \alpha(v) = a α ( v ) = a in C \mathrm{C} C and define the hydrogen-suppressed chemical graph ⟨ C ⟩ \langle\mathrm{C}\rangle ⟨ C ⟩ to be the graph obtained from H H H by removing all the vertices v ∈ V H ( C ) v \in V_{\mathrm{H}}(\mathrm{C}) v ∈ V H ( C ) .
Two-layered Model
This section reviews the two-layered model introduced by Shi et al. [20 ] .
Let C = ( H , α , β ) \mathrm{C} = (H,\alpha,\beta) C = ( H , α , β ) be a chemical graph and ρ ≥ 1 \rho\ge1 ρ ≥ 1 be an integer, which we call a branch-parameter .
A two-layered model of C \mathrm{C} C is a partition of the hydrogen-suppressed chemical graph ⟨ C ⟩ \langle\mathrm{C}\rangle ⟨ C ⟩ into an “interior” and an “exterior” in the following way. We call a vertex v ∈ V ( ⟨ C ⟩ ) v \in V(\langle\mathrm{C}\rangle) v ∈ V (⟨ C ⟩) (resp., an edge e ∈ E ( ⟨ C ⟩ ) e \in E(\langle\mathrm{C}\rangle) e ∈ E (⟨ C ⟩) ) of C \mathrm{C} C an exterior-vertex (resp., exterior-edge ) if ht ( v ) < ρ \operatorname{ht}(v) < \rho ht ( v ) < ρ (resp., e e e is incident to an exterior-vertex) and denote the sets of exterior-vertices and exterior-edges by V e x ( C ) V^{\mathrm{ex}}(\mathrm{C}) V ex ( C ) and E e x ( C ) E^{\mathrm{ex}}(\mathrm{C}) E ex ( C ) , respectively and denote V i n t ( C ) = V ( ⟨ C ⟩ ) ∖ V e x ( C ) V^{\mathrm{int}}(\mathcal{C}) = V(\langle\mathcal{C}\rangle) \setminus V^{\mathrm{ex}}(\mathcal{C}) V int ( C ) = V (⟨ C ⟩) ∖ V ex ( C ) and E i n t ( C ) = E ( ⟨ C ⟩ ) ∖ E e x ( C ) E^{\mathrm{int}}(\mathcal{C}) = E(\langle\mathcal{C}\rangle) \setminus E^{\mathrm{ex}}(\mathcal{C}) E int ( C ) = E (⟨ C ⟩) ∖ E ex ( C ) , respectively. We call a vertex in V i n t ( C ) V^{\mathrm{int}}(\mathcal{C}) V int ( C ) (resp., an edge in E i n t ( C ) E^{\mathrm{int}}(\mathcal{C}) E int ( C ) ) an interior-vertex (resp., interior-edge ). The set E e x ( C ) E^{\mathrm{ex}}(\mathcal{C}) E ex ( C ) of exterior-edges forms a collection of connected graphs each of which is regarded as a rooted tree T T T rooted at the vertex v ∈ V ( T ) v \in V(T) v ∈ V ( T ) with the maximum ht ( v ) \operatorname{ht}(v) ht ( v ) . Let T e x ( ⟨ C ⟩ ) \mathcal{T}^{\mathrm{ex}}(\langle\mathcal{C}\rangle) T ex (⟨ C ⟩) denote the set of these chemical rooted trees in ⟨ C ⟩ \langle\mathcal{C}\rangle ⟨ C ⟩ . The interior C i n t \mathcal{C}^{\mathrm{int}} C int of C \mathcal{C} C is defined to be the subgraph ( V i n t ( C ) , E i n t ( C ) ) (V^{\mathrm{int}}(\mathcal{C}), E^{\mathrm{int}}(\mathcal{C})) ( V int ( C ) , E int ( C )) of ⟨ C ⟩ \langle\mathcal{C}\rangle ⟨ C ⟩ .
Figure 2 illustrates an example of a hydrogen-suppressed chemical graph ⟨ C ⟩ \langle\mathcal{C}\rangle ⟨ C ⟩ . For a branch-parameter ρ = 2 \rho= 2 ρ = 2 , the interior of the chemical graph ⟨ C ⟩ \langle\mathcal{C}\rangle ⟨ C ⟩ in Figure 2 is obtained by removing the set of vertices with degree 1 1 1 ρ = 2 \rho= 2 ρ = 2 times; i.e., first remove the set V 1 = { w 1 , w 2 , … , w 14 } V_1 = \{w_1, w_2, \ldots, w_{14}\} V 1 = { w 1 , w 2 , … , w 14 } of vertices of degree 1 in ⟨ C ⟩ \langle\mathcal{C}\rangle ⟨ C ⟩ and then remove the set V 2 = { w 15 , w 16 , … , w 19 } V_2 = \{w_{15}, w_{16}, \ldots, w_{19}\} V 2 = { w 15 , w 16 , … , w 19 } of vertices of degree 1 in ⟨ C ⟩ − V 1 \langle\mathcal{C}\rangle- V_1 ⟨ C ⟩ − V 1 , where the removed vertices become the exterior-vertices of ⟨ C ⟩ \langle\mathcal{C}\rangle ⟨ C ⟩ .
For each interior-vertex u ∈ V i n t ( C ) u \in V^{\mathrm{int}}(\mathcal{C}) u ∈ V int ( C ) , let T u ∈ T e x ( ⟨ C ⟩ ) T_u \in\mathcal{T}^{\mathrm{ex}}(\langle\mathcal{C}\rangle) T u ∈ T ex (⟨ C ⟩) denote the chemical tree rooted at u u u (where possibly T u T_u T u consists of vertex u u u ) and define the ρ \rho ρ -fringe-tree C [ u ] \mathcal{C}[u] C [ u ] to be the chemical rooted tree obtained from T u T_u T u by putting back the hydrogens originally attached with T u T_u T u in C \mathcal{C} C . Let T ( C ) \mathcal{T}(\mathcal{C}) T ( C ) denote the set of ρ \rho ρ -fringe-trees C [ u ] \mathcal{C}[u] C [ u ] , u ∈ V i n t ( C ) u \in V^{\mathrm{int}}(\mathcal{C}) u ∈ V int ( C ) . Figure 3 illustrates the set T ( C ) = { C [ u i ] ∣ i ∈ [ 1 , 28 ] } \mathcal{T}(\mathcal{C}) = \{\mathcal{C}[u_i] \mid i \in[1, 28]\} T ( C ) = { C [ u i ] ∣ i ∈ [ 1 , 28 ]} of the 2 2 2 -fringe-trees of the example C \mathcal{C} C in Figure 2.
Feature Function The feature of an interior-edge e = u v ∈ E i n t ( C ) e = uv \in E^{\mathrm{int}}(\mathcal{C}) e = uv ∈ E int ( C ) such that α ( u ) = a \alpha(u) = a α ( u ) = a , deg ⟨ C ⟩ ( u ) = d \deg_{\langle\mathcal{C}\rangle}(u) = d deg ⟨ C ⟩ ( u ) = d , α ( v ) = b \alpha(v) = b α ( v ) = b , deg ⟨ C ⟩ ( v ) = d ′ \deg_{\langle\mathcal{C}\rangle}(v) = d^{\prime} deg ⟨ C ⟩ ( v ) = d ′ and β ( e ) = m \beta(e) = m β ( e ) = m is represented by a tuple ( a d , b d ′ , m ) (ad, bd^{\prime}, m) ( a d , b d ′ , m ) , which is called the edge-configuration of the edge e e e , where we call the tuple ( a , b , m ) (a, b, m) ( a , b , m ) the adjacency-configuration of the edge e e e .
In the framework with the two-layered model, the feature vector f f f mainly consists of the frequency of edge-configurations of the interior-edges and the frequency of chemical rooted trees among the set of chemical rooted trees C [ u ] \mathcal{C}[u] C [ u ] over all interior-vertices u u u . See Appendix A for all these descriptors x ( 1 ) , x ( 2 ) , … , x ( K 1 ) x(1), x(2), \ldots, x(K_1) x ( 1 ) , x ( 2 ) , … , x ( K 1 ) , which are called linear descriptors . We denote by D π ( 1 ) : = { x ( k ) ∣ k ∈ [ 1 , K 1 ] } D_{\pi}^{(1)} := \{x(k) \mid k \in[1, K_1]\} D π ( 1 ) := { x ( k ) ∣ k ∈ [ 1 , K 1 ]} the set of descriptors constructed over a data set for a property π \pi π . Zhu et al. [28 ] introduced a quadratic term x ( i ) x ( j ) x^{(i)}x^{(j)} x ( i ) x ( j ) (or x ( i ) ( 1 − x ( j ) ) x^{(i)}(1-x^{(j)}) x ( i ) ( 1 − x ( j ) ) ), 1 ≤ i ≤ j ≤ K 1 1 \le i \le j \le K_1 1 ≤ i ≤ j ≤ K 1 as a new descriptor, where it is assumed that each x ( i ) x^{(i)} x ( i ) is normalized between 0 and 1. This term x ( i ) x ( j ) x^{(i)}x^{(j)} x ( i ) x ( j ) , 1 ≤ i ≤ j ≤ K 1 1 \le i \le j \le K_1 1 ≤ i ≤ j ≤ K 1 (or x ( i ) ( 1 − x ( j ) ) x^{(i)}(1-x^{(j)}) x ( i ) ( 1 − x ( j ) ) , i , j ∈ [ 1 , K 1 ] i,j \in[1,K_1] i , j ∈ [ 1 , K 1 ] ) is called a quadratic descriptor and is denoted by D π ( 2 ) : = { x ( i ) x ( j ) ∣ 1 ≤ i ≤ j ≤ K 1 } ∪ { x ( i ) ( 1 − x ( j ) ) ∣ i , j ∈ [ 1 , K 1 ] } D_{\pi}^{(2)} := \{x^{(i)}x^{(j)} \mid1 \le i \le j \le K_1\} \cup\{x^{(i)}(1-x^{(j)}) \mid i,j \in[1,K_1]\} D π ( 2 ) := { x ( i ) x ( j ) ∣ 1 ≤ i ≤ j ≤ K 1 } ∪ { x ( i ) ( 1 − x ( j ) ) ∣ i , j ∈ [ 1 , K 1 ]} the set of quadratic descriptors.
To construct a prediction function, we use the union D π ( 1 ) ∪ D π ( 2 ) D_{\pi}^{(1)} \cup D_{\pi}^{(2)} D π ( 1 ) ∪ D π ( 2 ) . This set of descriptors is usually excessive in constructing a prediction function, and we reduce it to a smaller set of descriptors to construct a feature function f : R K → R f : \mathbb{R}^{K} \to\mathbb{R} f : R K → R , where K K K is the number of resulting descriptors. We call R K \mathbb{R}^{K} R K the feature space . To reduce descriptors, we use the methods proposed by Zhu et al. [28 ] .
Topological Specification A topological specification σ \sigma σ is described as a set of the following rules:
(i) a seed graph G C G_{\mathrm{C}} G C as an abstract form of a target chemical graph C;
(ii) a set F \mathcal{F} F of chemical rooted trees as candidates for a tree C[ u ] [u] [ u ] rooted at each exterior-vertex u u u in C; and
(iii) lower and upper bounds on the number of components in a target chemical graph such as chemical elements, double/triple bonds and the interior-vertices in C.
Figures 4(a) and (b) illustrate examples of a seed graph G C G_{\mathrm{C}} G C and a set F \mathcal{F} F of chemical rooted trees, respectively. Given a seed graph G C G_{\mathrm{C}} G C , the interior of a target chemical graph C is constructed from G C G_{\mathrm{C}} G C by replacing some edges a = u v a=uv a = uv with paths P a P_a P a between the end-vertices u u u and v v v and by attaching new paths Q v Q_v Q v to some vertices v v v . For example, a chemical graph C \mathcal{C} C in Figure 2 is constructed from the seed graph G C G_{\mathcal{C}} G C in Figure 4 (a) as follows.
Figure 2. An illustration of a hydrogen-suppressed chemical graph ⟨ C ⟩ \langle\mathrm{C}\rangle ⟨ C ⟩ obtained from a chemical graph C \mathrm{C} C by removing all the hydrogens, where for ρ = 2 \rho= 2 ρ = 2 , V e x ( C ) = { w i ∣ i ∈ [ 1 , 19 ] } V^{\mathrm{ex}}(\mathrm{C}) = \{w_i \mid i \in[1,19]\} V ex ( C ) = { w i ∣ i ∈ [ 1 , 19 ]} and V i n t ( C ) = { u i ∣ i ∈ [ 1 , 28 ] } V^{\mathrm{int}}(\mathrm{C}) = \{u_i \mid i \in[1,28]\} V int ( C ) = { u i ∣ i ∈ [ 1 , 28 ]} .
Figure 4. (a) An illustration of a seed graph G C G_{\mathrm{C}} G C , where the vertices in V C V_{\mathrm{C}} V C are depicted with gray circles, the edges in E ( ≥ 2 ) E_{(\ge2)} E ( ≥ 2 ) are depicted with dotted lines, the edges in E ( ≥ 1 ) E_{(\ge1)} E ( ≥ 1 ) are depicted with dashed lines, the edges in E ( 0 / 1 ) E_{(0/1)} E ( 0/1 ) are depicted with gray bold lines and the edges in E ( = 1 ) E_{(=1)} E ( = 1 ) are depicted with black solid lines; (b) A set F = { ψ 1 , ψ 2 , … , ψ 30 } ⊆ F ( C π ) \mathcal{F} = \{\psi_1,\psi_2,\ldots,\psi_{30}\} \subseteq\mathcal{F}(C_{\pi}) F = { ψ 1 , ψ 2 , … , ψ 30 } ⊆ F ( C π ) of 30 chemical rooted trees ψ i \psi_i ψ i , i ∈ [ 1 , 30 ] i \in[1,30] i ∈ [ 1 , 30 ] , where the root of each tree is depicted with a gray circle. The hydrogens attached to non-root vertices are omitted in the figure.
First replace five edges a 1 = u 1 u 2 a_1=u_1u_2 a 1 = u 1 u 2 , a 2 = u 1 u 3 a_2=u_1u_3 a 2 = u 1 u 3 , a 3 = u 4 u 7 a_3=u_4u_7 a 3 = u 4 u 7 , a 4 = u 10 u 11 a_4=u_{10}u_{11} a 4 = u 10 u 11 and a 5 = u 11 u 12 a_5=u_{11}u_{12} a 5 = u 11 u 12 in G C G_{\mathcal{C}} G C with new paths P a 1 = ( u 1 , u 13 , u 2 ) P_{a_1}=(u_1,u_{13},u_2) P a 1 = ( u 1 , u 13 , u 2 ) , P a 2 = ( u 1 , u 14 , u 3 ) P_{a_2}=(u_1,u_{14},u_3) P a 2 = ( u 1 , u 14 , u 3 ) , P a 3 = ( u 4 , u 15 , u 16 , u 7 ) P_{a_3}=(u_4,u_{15},u_{16},u_7) P a 3 = ( u 4 , u 15 , u 16 , u 7 ) , P a 4 = ( u 10 , u 17 , u 18 , u 19 , u 11 ) P_{a_4}=(u_{10},u_{17},u_{18},u_{19},u_{11}) P a 4 = ( u 10 , u 17 , u 18 , u 19 , u 11 ) and P a 5 = ( u 11 , u 20 , u 21 , u 22 , u 12 ) P_{a_5}=(u_{11},u_{20},u_{21},u_{22},u_{12}) P a 5 = ( u 11 , u 20 , u 21 , u 22 , u 12 ) , respectively to obtain a subgraph G 1 G_1 G 1 of ⟨ C ⟩ \langle\mathcal{C}\rangle ⟨ C ⟩ .
Next attach to this graph G 1 G_1 G 1 three new paths Q u 5 = ( u 5 , u 24 ) Q_{u_5}=(u_5,u_{24}) Q u 5 = ( u 5 , u 24 ) , Q u 18 = ( u 18 , u 25 , u 26 , u 27 ) Q_{u_{18}}=(u_{18},u_{25},u_{26},u_{27}) Q u 18 = ( u 18 , u 25 , u 26 , u 27 ) and Q u 22 = ( u 22 , u 28 ) Q_{u_{22}}=(u_{22},u_{28}) Q u 22 = ( u 22 , u 28 ) to obtain the interior of ⟨ C ⟩ \langle\mathcal{C}\rangle ⟨ C ⟩ in Figure 2 .
Finally attach to the interior 28 trees selected from the set F \mathcal{F} F and assign chemical elements and bond-multiplicities in the interior to obtain a chemical graph C \mathcal{C} C in Figure 2 . In Figure 3 , ψ 1 ∈ F \psi_1\in\mathcal{F} ψ 1 ∈ F is selected for C [ u i ] \mathcal{C}[u_i] C [ u i ] , i ∈ { 6 , 7 , 11 } i\in\{6,7,11\} i ∈ { 6 , 7 , 11 } . Similarly ψ 2 \psi_2 ψ 2 for C [ u 9 ] \mathcal{C}[u_9] C [ u 9 ] , ψ 4 \psi_4 ψ 4 for C [ u 1 ] \mathcal{C}[u_1] C [ u 1 ] , ψ 6 \psi_6 ψ 6 for C [ u i ] \mathcal{C}[u_i] C [ u i ] , i ∈ { 3 , 4 , 5 , 10 , 19 , 22 , 25 , 26 } i\in\{3,4,5,10,19,22,25,26\} i ∈ { 3 , 4 , 5 , 10 , 19 , 22 , 25 , 26 } , ψ 8 \psi_8 ψ 8 for C [ u 8 ] \mathcal{C}[u_8] C [ u 8 ] , ψ 11 \psi_{11} ψ 11 for C [ u i ] \mathcal{C}[u_i] C [ u i ] , i ∈ { 2 , 13 , 16 , 17 , 20 } i\in\{2,13,16,17,20\} i ∈ { 2 , 13 , 16 , 17 , 20 } , ψ 15 \psi_{15} ψ 15 for C [ u 12 ] \mathcal{C}[u_{12}] C [ u 12 ] , ψ 19 \psi_{19} ψ 19 for C [ u 15 ] \mathcal{C}[u_{15}] C [ u 15 ] , ψ 23 \psi_{23} ψ 23 for C [ u 21 ] \mathcal{C}[u_{21}] C [ u 21 ] , ψ 24 \psi_{24} ψ 24 for C [ u 24 ] \mathcal{C}[u_{24}] C [ u 24 ] , ψ 25 \psi_{25} ψ 25 for C [ u 27 ] \mathcal{C}[u_{27}] C [ u 27 ] , ψ 26 \psi_{26} ψ 26 for C [ u 23 ] \mathcal{C}[u_{23}] C [ u 23 ] , ψ 27 \psi_{27} ψ 27 for C [ u 14 ] \mathcal{C}[u_{14}] C [ u 14 ] and ψ 30 \psi_{30} ψ 30 for C [ u 28 ] \mathcal{C}[u_{28}] C [ u 28 ] .
Figure 3. The set T ( C ) \mathcal{T}(\mathcal{C}) T ( C ) of 2-fringe-trees C [ u i ] \mathcal{C}[u_i] C [ u i ] , i ∈ [ 1 , 28 ] i \in[1, 28] i ∈ [ 1 , 28 ] of the example C \mathcal{C} C in Figure 2, where the root of each tree is depicted with a gray circle and the hydrogens attached to non-root vertices are omitted in the figure.
See Appendix § 11 for a full description of topological specification.
Prediction Functions
Let C \mathcal{C} C be a data set of chemical graphs C \mathcal{C} C with an observed value a ( C ) ∈ R a(\mathcal{C})\in\mathbb{R} a ( C ) ∈ R . Let D D D be a set of descriptors with K = ∣ D ∣ K=|D| K = ∣ D ∣ and f f f be a feature function that maps a chemical graph C \mathcal{C} C to a vector f ( C ) ∈ R K f(\mathcal{C})\in\mathbb{R}^{K} f ( C ) ∈ R K , where x ( d ) x(d) x ( d ) denotes the value of descriptor d ∈ D d\in D d ∈ D . For a notational simplicity, we denote a i = a ( C i ) a_i=a(\mathcal{C}_i) a i = a ( C i ) and x i = f ( C i ) x_i=f(\mathcal{C}_i) x i = f ( C i ) for an indexed graph C i ∈ C \mathcal{C}_i\in\mathcal{C} C i ∈ C .
Evaluation
For a prediction function η : R K → R \eta:\mathbb{R}^{K}\to\mathbb{R} η : R K → R , define an error function
Err ( η ; C ) ≔ ∑ C i ∈ C ( a i − η ( f ( C i ) ) ) 2 = ∑ C i ∈ C ( a i − η ( x i ) ) 2 , \operatorname{Err}(\eta;\mathcal{C})\coloneqq\sum_{\mathcal{C}_i\in\mathcal{C}}(a_i-\eta(f(\mathcal{C}_i)))^2=\sum_{\mathcal{C}_i\in\mathcal{C}}(a_i-\eta(x_i))^2, Err ( η ; C ) : = C i ∈ C ∑ ( a i − η ( f ( C i )) ) 2 = C i ∈ C ∑ ( a i − η ( x i ) ) 2 ,
and define the coefficient of determination R 2 ( η , C ) \mathrm{R}^2(\eta,\mathcal{C}) R 2 ( η , C ) to be
R 2 ( η , C ) ≔ 1 − Err ( η ; C ) ∑ C i ∈ C ( a i − a ~ ) 2 for a ~ = 1 ∣ C ∣ ∑ C ∈ C a ( C ) . \mathrm{R}^2(\eta,\mathcal{C})\coloneqq1-\frac{\operatorname{Err}(\eta;\mathcal{C})}{\sum_{\mathcal{C}_i\in\mathcal{C}}(a_i-\widetilde{a})^2}
\quad\text{for}\quad
\widetilde{a}=\frac{1}{|\mathcal{C}|}\sum_{\mathcal{C}\in\mathcal{C}}a(\mathcal{C}). R 2 ( η , C ) : = 1 − ∑ C i ∈ C ( a i − a ) 2 Err ( η ; C ) for a = ∣ C ∣ 1 C ∈ C ∑ a ( C ) .
We evaluate a method of constructing a prediction function over a set D D D of descriptors by 5-fold cross-validation as follows. A single run r r r of 5-fold cross-validation executes the following: Partition a data set C \mathcal{C} C randomly into five subsets C ( k ) \mathcal{C}^{(k)} C ( k ) , k ∈ [ 1 , 5 ] k\in[1,5] k ∈ [ 1 , 5 ] so that the difference between ∣ C ( i ) ∣ |\mathcal{C}^{(i)}| ∣ C ( i ) ∣ and ∣ C ( j ) ∣ |\mathcal{C}^{(j)}| ∣ C ( j ) ∣ is at most 1. For each k ∈ [ 1 , 5 ] k\in[1,5] k ∈ [ 1 , 5 ] , let C t r a i n ≔ C ∖ C ( k ) \mathcal{C}_{\mathrm{train}}\coloneqq\mathcal{C}\setminus\mathcal{C}^{(k)} C train : = C ∖ C ( k ) , C t e s t ≔ C ( k ) \mathcal{C}_{\mathrm{test}}\coloneqq\mathcal{C}^{(k)} C test : = C ( k ) and execute the method to construct a prediction function η ( k ) : R ∣ D ∣ → R \eta^{(k)}:\mathbb{R}^{|D|}\to\mathbb{R} η ( k ) : R ∣ D ∣ → R over a training set C t r a i n \mathcal{C}_{\mathrm{train}} C train and compute g r ( k ) ≔ R 2 ( η ( k ) , C t e s t ) g_r^{(k)}\coloneqq\mathrm{R}^2(\eta^{(k)},\mathcal{C}_{\mathrm{test}}) g r ( k ) : = R 2 ( η ( k ) , C test ) . Let R C V 2 ( C , D , p ) \mathrm{R}^2_{\mathrm{CV}}(\mathcal{C},D,p) R CV 2 ( C , D , p ) denote the median of { g r i ( k ) ∣ k ∈ [ 1 , 5 ] , i ∈ [ 1 , p ] } \{g_{r_i}^{(k)}\mid k\in[1,5],i\in[1,p]\} { g r i ( k ) ∣ k ∈ [ 1 , 5 ] , i ∈ [ 1 , p ]} of p p p runs r 1 , r 2 , … , r p r_1,r_2,\ldots,r_p r 1 , r 2 , … , r p of 5-fold cross-validation.
Linear Regressions
For a set D D D of descriptors, a hyperplane is defined to be a pair ( w , b ) (w,b) ( w , b ) of a vector w ∈ R K w \in\mathbb{R}^{K} w ∈ R K and a real b ∈ R b \in\mathbb{R} b ∈ R . Given a hyperplane ( w , b ) (w,b) ( w , b ) , a prediction function η w , b : R K → R \eta_{w,b} : \mathbb{R}^{K} \to\mathbb{R} η w , b : R K → R is defined by setting
η w , b ( x ) ≜ w ⋅ x + b = ∑ d ∈ D w ( d ) x ( d ) + b . \eta_{w,b}(x) \triangleq w \cdot x + b = \sum_{d \in D} w(d)x(d) + b. η w , b ( x ) ≜ w ⋅ x + b = d ∈ D ∑ w ( d ) x ( d ) + b .
Multidimensional Linear Regression (MLR) Given a data set C C C and a set D D D of descriptors, multidimensional linear regression MLR ( C , D ) \operatorname{MLR}(C,D) MLR ( C , D ) returns a hyperplane ( w , b ) (w,b) ( w , b ) with w ∈ R K w \in\mathbb{R}^{K} w ∈ R K that minimizes Err ( η w , b ; C ) \operatorname{Err}(\eta_{w,b};C) Err ( η w , b ; C ) . However, such a hyperplane ( w , b ) (w,b) ( w , b ) may contain unnecessarily many non-zero reals w ( d ) w(d) w ( d ) . To avoid this, a minimization with an additional penalty term τ \tau τ to the error function has been proposed. Among them, a Lasso function [26 ] is defined to be
1 2 ∣ C ∣ Err ( η w , b ; C ) + λ τ , τ = ∑ d ∈ D ∣ w ( d ) ∣ + ∣ b ∣ , \frac{1}{2|C|}\operatorname{Err}(\eta_{w,b};C) + \lambda\tau,\qquad\tau= \sum_{d \in D}|w(d)| + |b|, 2∣ C ∣ 1 Err ( η w , b ; C ) + λ τ , τ = d ∈ D ∑ ∣ w ( d ) ∣ + ∣ b ∣ ,
where λ ∈ R + \lambda\in\mathbb{R}_{+} λ ∈ R + is a given nonnegative number.
Adjustive Linear Regression (ALR) We review a recent learning method, called adjustive linear regression , that is effectively equivalent to an ANN with no hidden layers by a linear regression such that each input node may have a non-linear activation function (see [27 ] for the details of the idea). Let C = { C 1 , C 2 , … , C m } C = \{C_1,C_2,\ldots,C_m\} C = { C 1 , C 2 , … , C m } , A = { a i = f ( C i ) ∣ i ∈ [ 1 , m ] } A = \{a_i = f(C_i) \mid i \in[1,m]\} A = { a i = f ( C i ) ∣ i ∈ [ 1 , m ]} and X = { x i = f ( C i ) ∈ R K ∣ i ∈ [ 1 , m ] } X = \{x_i = f(C_i) \in\mathbb{R}^{K} \mid i \in[1,m]\} X = { x i = f ( C i ) ∈ R K ∣ i ∈ [ 1 , m ]} . Let D + D^{+} D + (resp., D − D^{-} D − ) denote the set of descriptor d ∈ D d \in D d ∈ D such that the correlation coefficient σ ( X [ d ] , A ) \sigma(X[d],A) σ ( X [ d ] , A ) between X [ d ] = { x i ( d ) ∣ i ∈ [ 1 , m ] } X[d] = \{x_i(d) \mid i \in[1,m]\} X [ d ] = { x i ( d ) ∣ i ∈ [ 1 , m ]} and A A A is nonnegative (resp., negative). We first solve the following linear program with a constant λ ≥ 0 \lambda\ge0 λ ≥ 0 , a real variable b b b and nonnegative real variables c q ( 0 ) c_q(0) c q ( 0 ) , q ∈ [ 0 , 2 ] q \in[0,2] q ∈ [ 0 , 2 ] , w q ( d ) w_q(d) w q ( d ) , q ∈ [ 0 , 2 ] q \in[0,2] q ∈ [ 0 , 2 ] , d ∈ D d \in D d ∈ D .
Linear Program
Minimize: 1 2 m ∑ i ∈ [ 1 , m ] [ c 0 ( 0 ) a i + c 1 ( 0 ) a i 2 + c 2 ( 0 ) ( 1 − ( a i − 1 ) 2 ) ] − ∑ d ∈ D + [ w 0 ( d ) x i ( d ) + w 1 ( d ) x i ( d ) 2 + w 2 ( d ) ( 1 − ( x i ( d ) − 1 ) 2 ) ] + ∑ d ∈ D − [ w 0 ( d ) x i ( d ) + w 1 ( d ) x i ( d ) 2 + w 2 ( d ) ( 1 − ( x i ( d ) − 1 ) 2 ) ] − b ∣ + λ τ \begin{aligned}
\text{Minimize:}\quad& \frac{1}{2m}\sum_{i \in[1,m]}[c_0(0)a_i+c_1(0)a_i^2+c_2(0)(1-(a_i-1)^2)]\\
&-\sum_{d \in D^{+}}[w_0(d)x_i(d)+w_1(d)x_i(d)^2+w_2(d)(1-(x_i(d)-1)^2)]\\
&+\sum_{d \in D^{-}}[w_0(d)x_i(d)+w_1(d)x_i(d)^2+w_2(d)(1-(x_i(d)-1)^2)]-b|+\lambda\tau
\end{aligned} Minimize: 2 m 1 i ∈ [ 1 , m ] ∑ [ c 0 ( 0 ) a i + c 1 ( 0 ) a i 2 + c 2 ( 0 ) ( 1 − ( a i − 1 ) 2 )] − d ∈ D + ∑ [ w 0 ( d ) x i ( d ) + w 1 ( d ) x i ( d ) 2 + w 2 ( d ) ( 1 − ( x i ( d ) − 1 ) 2 )] + d ∈ D − ∑ [ w 0 ( d ) x i ( d ) + w 1 ( d ) x i ( d ) 2 + w 2 ( d ) ( 1 − ( x i ( d ) − 1 ) 2 )] − b ∣ + λ τ
subject to
τ = ∑ d ∈ D w 0 ( d ) + ∣ b ∣ , c 0 ( 0 ) + c 1 ( 0 ) + c 2 ( 0 ) = 1. (1) \tau=\sum_{d \in D}w_0(d)+|b|,\qquad c_0(0)+c_1(0)+c_2(0)=1. \tag*{(1)} τ = d ∈ D ∑ w 0 ( d ) + ∣ b ∣ , c 0 ( 0 ) + c 1 ( 0 ) + c 2 ( 0 ) = 1. (1)
An optimal solution to this minimization can be found by solving a linear program with O ( m + ∣ D ∣ ) O(m+|D|) O ( m + ∣ D ∣ ) variables and constraints. From an optimal solution, we next compute the following hyperplane ( w ∗ , b ∗ ) (w^{*},b^{*}) ( w ∗ , b ∗ ) to obtain a linear prediction function η w ∗ , b ∗ \eta_{w^{*},b^{*}} η w ∗ , b ∗ . Let c q ∗ ( 0 ) c_q^{*}(0) c q ∗ ( 0 ) , q ∈ [ 0 , 2 ] q \in[0,2] q ∈ [ 0 , 2 ] , w q ∗ ( d ) w_q^{*}(d) w q ∗ ( d ) , q ∈ [ 0 , 2 ] q \in[0,2] q ∈ [ 0 , 2 ] , d ∈ D d \in D d ∈ D and b ∗ b^{*} b ∗ denote the values of variables c q ( 0 ) c_q(0) c q ( 0 ) , q ∈ [ 0 , 2 ] q \in[0,2] q ∈ [ 0 , 2 ] , w q ( d ) w_q(d) w q ( d ) , q ∈ [ 0 , 2 ] q \in[0,2] q ∈ [ 0 , 2 ] , d ∈ D d \in D d ∈ D and b b b in an optimal solution, respectively. Let D † D^{\dagger} D † denote the set of descriptors d ∈ D d \in D d ∈ D with w 0 ∗ ( d ) > 0 w_0^{*}(d)>0 w 0 ∗ ( d ) > 0 . Then we set w ∗ ( d ) : = 0 w^{*}(d):=0 w ∗ ( d ) := 0 for d ∈ D d \in D d ∈ D with w 0 ∗ ( d ) = 0 w_0^{*}(d)=0 w 0 ∗ ( d ) = 0 ,
w ∗ ( d ) : = w 0 ∗ ( d ) w 0 ∗ ( d ) + w 1 ∗ ( d ) + w 2 ∗ ( d ) for d ∈ D + ∩ D † , w ∗ ( d ) : = − w 0 ∗ ( d ) w 0 ∗ ( d ) + w 1 ∗ ( d ) + w 2 ∗ ( d ) for d ∈ D − ∩ D † and w ∗ : = ( w 0 ∗ ( 1 ) , w 0 ∗ ( 2 ) , … , w 0 ∗ ( ∣ D ∣ ) ) ∈ R K . \begin{aligned}
w^{*}(d) &:= \frac{w_{0}^{*}(d)}{w_{0}^{*}(d)+w_{1}^{*}(d)+w_{2}^{*}(d)} && \text{for } d \in D^{+}\cap D^{\dagger},\\
w^{*}(d) &:= -\frac{w_{0}^{*}(d)}{w_{0}^{*}(d)+w_{1}^{*}(d)+w_{2}^{*}(d)} && \text{for } d \in D^{-}\cap D^{\dagger}\text{ and}\\
w^{*} &:= \left(w_{0}^{*}(1),w_{0}^{*}(2),\ldots,w_{0}^{*}(|D|)\right)\in\mathbb{R}^{K}.
\end{aligned} w ∗ ( d ) w ∗ ( d ) w ∗ := w 0 ∗ ( d ) + w 1 ∗ ( d ) + w 2 ∗ ( d ) w 0 ∗ ( d ) := − w 0 ∗ ( d ) + w 1 ∗ ( d ) + w 2 ∗ ( d ) w 0 ∗ ( d ) := ( w 0 ∗ ( 1 ) , w 0 ∗ ( 2 ) , … , w 0 ∗ ( ∣ D ∣ ) ) ∈ R K . for d ∈ D + ∩ D † , for d ∈ D − ∩ D † and
Reduction of Descriptors and Linear Regression (RLR) We finally review a learning method recently proposed by Zhu et al. [28 ] to improve the learning performance with the two-layered model. Given a set of descriptors x ( 1 ) , x ( 2 ) , … , x ( K ) x(1),x(2),\ldots,x(K) x ( 1 ) , x ( 2 ) , … , x ( K ) , the method first adds to the original set of linear descriptors a quadratic descriptor x ( i ) x ( j ) x(i)x(j) x ( i ) x ( j ) (or x ( i ) ( 1 − x ( j ) ) x(i)(1-x(j)) x ( i ) ( 1 − x ( j )) of each two descriptors. This drastically increases the number of descriptors, which would take extra running time in learning or cause over-fitting to the data set. Next the method reduces the set of linear and quadratic descriptors into a smaller set that delivers a prediction function with a higher performance (see [28 ] for the details on the reduction procedure). Finally the method constructs a prediction function by using MLR on the set of selected descriptors. We call this method based on reduction and linear regression RLR in this paper.
Splitting Data Sets via Hyperplanes
This section proposes a method of splitting a given data set into two subsets with a hyperplane in the feature space so that most of the compounds C \mathcal{C} C in the first (resp., second) subsets have observed values a ( C ) a(\mathcal{C}) a ( C ) smaller (resp., larger) than a threshold θ \theta θ .
For a property π \pi π , let C = { C 1 , C 2 , … , C n } \mathcal{C}=\{\mathrm{C}_1,\mathrm{C}_2,\ldots,\mathrm{C}_n\} C = { C 1 , C 2 , … , C n } be a set of chemical graphs. Assume that all entries and observed values are normalized, where min { a i ∣ C i ∈ C } = 0 \min\{a_i\mid\mathrm{C}_i\in\mathcal{C}\}=0 min { a i ∣ C i ∈ C } = 0 and max { a i ∣ C i ∈ C } = 1 \max\{a_i\mid\mathrm{C}_i\in\mathcal{C}\}=1 max { a i ∣ C i ∈ C } = 1 and min { x i ( d ) ∣ C i ∈ C } = 0 \min\{x_i(d)\mid\mathrm{C}_i\in\mathcal{C}\}=0 min { x i ( d ) ∣ C i ∈ C } = 0 and max { x i ( d ) ∣ C i ∈ C } = 1 \max\{x_i(d)\mid\mathrm{C}_i\in\mathcal{C}\}=1 max { x i ( d ) ∣ C i ∈ C } = 1 for each d ∈ D d\in D d ∈ D .
For a threshold θ \theta θ with 0 < θ < 1 0<\theta<1 0 < θ < 1 , we find a hyperplane ( w , b ) (w,b) ( w , b ) with w ∈ R K w\in\mathbb{R}^{K} w ∈ R K and b ∈ R b\in\mathbb{R} b ∈ R that splits the set C \mathcal{C} C into subsets
C ( 1 ) : = { C i ∈ C ∣ w x i − b ≤ 0 } and C ( 2 ) : = { C i ∈ C ∣ w x i − b > 0 } \mathcal{C}^{(1)}:=\{\mathrm{C}_i\in\mathcal{C}\mid wx_i-b\leq0\}\text{ and }\mathcal{C}^{(2)}:=\{\mathrm{C}_i\in\mathcal{C}\mid wx_i-b>0\} C ( 1 ) := { C i ∈ C ∣ w x i − b ≤ 0 } and C ( 2 ) := { C i ∈ C ∣ w x i − b > 0 }
so that C ( 1 ) \mathcal{C}^{(1)} C ( 1 ) (resp., C ( 2 ) \mathcal{C}^{(2)} C ( 2 ) ) contains compounds C i ∈ C \mathrm{C}_i\in\mathcal{C} C i ∈ C with a i ≤ θ a_i\leq\theta a i ≤ θ (resp., a i > θ a_i>\theta a i > θ ) as many as possible. Then we treat each of the subsets C ( j ) \mathcal{C}^{(j)} C ( j ) , j = 1 , 2 j=1,2 j = 1 , 2 as a new data set and construct a prediction function ψ j \psi_j ψ j before we obtain a prediction function to the original set C \mathcal{C} C by combining functions ψ 1 \psi_1 ψ 1 and ψ 2 \psi_2 ψ 2 .
A Linear Program Formulation to Find a Hyperplane To find a hyperplane to split a given data set, we formulate a linear program in a similar manner of the idea by Freed and Glover [29 ] for separating a classification data. Define sets C ≤ θ : = { C i ∈ C ∣ a i ≤ θ } \mathcal{C}_{\leq\theta}:=\{\mathrm{C}_i\in\mathcal{C}\mid a_i\leq\theta\} C ≤ θ := { C i ∈ C ∣ a i ≤ θ } and C > θ : = { C i ∈ C ∣ a i > θ } \mathcal{C}_{>\theta}:=\{\mathrm{C}_i\in\mathcal{C}\mid a_i>\theta\} C > θ := { C i ∈ C ∣ a i > θ } , and choose compounds C s ∈ C ≤ θ \mathrm{C}_s\in\mathcal{C}_{\leq\theta} C s ∈ C ≤ θ with a s = 0 a_s=0 a s = 0 and C t ∈ C > θ \mathrm{C}_t\in\mathcal{C}_{>\theta} C t ∈ C > θ with a t = 1 a_t=1 a t = 1 , so that C s ∈ C ( 1 ) \mathrm{C}_s\in\mathcal{C}^{(1)} C s ∈ C ( 1 ) , C t ∈ C ( 2 ) \mathrm{C}_t\in\mathcal{C}^{(2)} C t ∈ C ( 2 ) .
A linear program is formulated as follows, where a hyperplane ( w , b ) (w,b) ( w , b ) with w ∈ R K w\in\mathbb{R}^{K} w ∈ R K and b ∈ R b\in\mathbb{R} b ∈ R is obtained as an optimal solution to this linear program:
LP(θ \theta θ )
constants: a i ∈ R a_i\in\mathbb{R} a i ∈ R , x i ∈ R K x_i\in\mathbb{R}^{K} x i ∈ R K , ∀ C i ∈ C \forall\mathrm{C}_i\in\mathcal{C} ∀ C i ∈ C ; indices s s s and t t t such that a s = 0 a_s=0 a s = 0 and a t = 1 a_t=1 a t = 1 ; θ ∈ R \theta\in\mathbb{R} θ ∈ R ; variables: w ∈ R K w \in\mathbb{R}^{K} w ∈ R K , b ∈ R b \in\mathbb{R} b ∈ R , nonnegative variables δ i ≥ 0 \delta_i \ge0 δ i ≥ 0 , ∀ C i ∈ C \forall C_i \in\mathcal{C} ∀ C i ∈ C ; constraints:
w x s − b ≤ 0 , w x t − b ≥ 0 , δ i ≥ w x i − b + ( a i − θ ) 2 , ∀ C i ∈ C ≤ θ , δ i ≥ − ( w x i − b ) + ( a i − θ ) 2 , ∀ C i ∈ C > θ . \begin{aligned}
wx_s-b &\le0,\\
wx_t-b &\ge0,\\
\delta_i &\ge wx_i-b+(a_i-\theta)^2,\quad\forall C_i \in\mathcal{C}_{\le\theta},\\
\delta_i &\ge-(wx_i-b)+(a_i-\theta)^2,\quad\forall C_i \in\mathcal{C}_{>\theta}.
\end{aligned} w x s − b w x t − b δ i δ i ≤ 0 , ≥ 0 , ≥ w x i − b + ( a i − θ ) 2 , ∀ C i ∈ C ≤ θ , ≥ − ( w x i − b ) + ( a i − θ ) 2 , ∀ C i ∈ C > θ .
objective function:
minimize ∑ C i ∈ C δ i . \operatorname{minimize}\ \sum_{C_i\in\mathcal{C}}\delta_i. minimize C i ∈ C ∑ δ i .
The above linear program consists of O ( ∣ D ∣ + ∣ C ∣ ) O(|D|+|\mathcal{C}|) O ( ∣ D ∣ + ∣ C ∣ ) variables and O ( ∣ C ∣ ) O(|\mathcal{C}|) O ( ∣ C ∣ ) constraints. We solve the linear program to obtain an optimal solution ( w , b ) (w,b) ( w , b ) and compute C ( 1 ) = { C i ∈ C ∣ w x i − b ≤ 0 } \mathcal{C}^{(1)}=\{C_i\in\mathcal{C}\mid wx_i-b\le0\} C ( 1 ) = { C i ∈ C ∣ w x i − b ≤ 0 } and C ( 2 ) = { C i ∈ C ∣ w x i − b > 0 } \mathcal{C}^{(2)}=\{C_i\in\mathcal{C}\mid wx_i-b>0\} C ( 2 ) = { C i ∈ C ∣ w x i − b > 0 } . Denote
a min ( j ) : = min { a i ∣ C i ∈ C ( j ) } and a max ( j ) : = max { a i ∣ C i ∈ C ( j ) } , j = 1 , 2 , a_{\min}^{(j)}:=\min\{a_i\mid C_i\in\mathcal{C}^{(j)}\}\quad\text{and}\quad a_{\max}^{(j)}:=\max\{a_i\mid C_i\in\mathcal{C}^{(j)}\},\quad j=1,2, a m i n ( j ) := min { a i ∣ C i ∈ C ( j ) } and a m a x ( j ) := max { a i ∣ C i ∈ C ( j ) } , j = 1 , 2 ,
where a min ( 1 ) = 0 a_{\min}^{(1)}=0 a m i n ( 1 ) = 0 and a max ( 2 ) = 1 a_{\max}^{(2)}=1 a m a x ( 2 ) = 1 . When C ( 1 ) = C ≤ θ \mathcal{C}^{(1)}=\mathcal{C}_{\le\theta} C ( 1 ) = C ≤ θ and C ( 2 ) = C > θ \mathcal{C}^{(2)}=\mathcal{C}_{>\theta} C ( 2 ) = C > θ hold, the ranges [ a min ( 1 ) = 0 , a max ( 1 ) ] [a_{\min}^{(1)}=0,a_{\max}^{(1)}] [ a m i n ( 1 ) = 0 , a m a x ( 1 ) ] and [ a min ( 2 ) , a max ( 2 ) = 1 ] [a_{\min}^{(2)},a_{\max}^{(2)}=1] [ a m i n ( 2 ) , a m a x ( 2 ) = 1 ] have no overlap (i.e., a max ( 1 ) ≤ θ < a min ( 2 ) a_{\max}^{(1)}\le\theta<a_{\min}^{(2)} a m a x ( 1 ) ≤ θ < a m i n ( 2 ) ). Otherwise a min ( 2 ) ≤ a max ( 1 ) a_{\min}^{(2)}\le a_{\max}^{(1)} a m i n ( 2 ) ≤ a m a x ( 1 ) holds, where even for this case, the two subsets C ( 1 ) \mathcal{C}^{(1)} C ( 1 ) and C ( 2 ) \mathcal{C}^{(2)} C ( 2 ) are well-separated if a min ( 2 ) a_{\min}^{(2)} a m i n ( 2 ) and a max ( 1 ) a_{\max}^{(1)} a m a x ( 1 ) are very close. We select a threshold θ \theta θ from a set of candidates so that a max ( 1 ) − a min ( 2 ) a_{\max}^{(1)}-a_{\min}^{(2)} a m a x ( 1 ) − a m i n ( 2 ) is minimized subject to the condition that each of ∣ C ( 1 ) ∣ |\mathcal{C}^{(1)}| ∣ C ( 1 ) ∣ and ∣ C ( 2 ) ∣ |\mathcal{C}^{(2)}| ∣ C ( 2 ) ∣ becomes nearly half of the original size ∣ C ∣ |\mathcal{C}| ∣ C ∣ .
Implementation in the First Phase of the Framework In the first phase of the framework, we construct a prediction function ψ \psi ψ to a data set C \mathcal{C} C for a property π \pi π and a descriptor set D D D of a feature function f : C → R K f:\mathcal{C}\to\mathbb{R}^{K} f : C → R K as follows. For a selected threshold θ \theta θ , we find a hyperplane ( w , b ) (w,b) ( w , b ) , w ∈ R K w\in\mathbb{R}^{K} w ∈ R K , b ∈ R b\in\mathbb{R} b ∈ R as an optimal solution to the above linear program LP ( θ ) \operatorname{LP}(\theta) LP ( θ ) based on which we split C \mathcal{C} C into subsets C ( j ) \mathcal{C}^{(j)} C ( j ) , j = 1 , 2 j=1,2 j = 1 , 2 . For each j = 1 , 2 j=1,2 j = 1 , 2 , choose a set D ~ j \widetilde{D}_j D j of descriptors and construct a prediction function ψ j : R ∣ D ~ j ∣ → R \psi_j:\mathbb{R}^{|\widetilde{D}_j|}\to\mathbb{R} ψ j : R ∣ D j ∣ → R for the data set C ( j ) \mathcal{C}^{(j)} C ( j ) with the descriptor set D ~ j \widetilde{D}_j D j . In our computational experiments, we use LLR, ANN, ALR and RLR to construct prediction functions to C ( j ) \mathcal{C}^{(j)} C ( j ) , j = 1 , 2 j=1,2 j = 1 , 2 and choose as ψ j \psi_j ψ j one of them with the best learning performance (where D ~ j \widetilde{D}_j D j is a subset of the linear descriptor set D D D when we use LLR, ANN or ALR; and D ~ j \widetilde{D}_j D j consists of some linear and quadratic descriptors of D D D when RLR is used to construct ψ j \psi_j ψ j ). Given a feature vector x ∈ R K x\in\mathbb{R}^{K} x ∈ R K , use the prediction function ψ 1 \psi_1 ψ 1 if w x − b ≤ 0 wx-b\le0 w x − b ≤ 0 ; and use the prediction function ψ 2 \psi_2 ψ 2 otherwise. Thus the prediction function ψ \psi ψ is given by
ψ ( x ) : = { ψ 1 ( x ) if w x − b ≤ 0 , ψ 2 ( x ) otherwise , \psi(x):=
\begin{cases}
\psi_1(x) & \text{if } wx-b\le0,\\
\psi_2(x) & \text{otherwise},
\end{cases} ψ ( x ) := { ψ 1 ( x ) ψ 2 ( x ) if w x − b ≤ 0 , otherwise ,
where the hyperplane ( w , b ) (w,b) ( w , b ) is a part of the prediction function ψ \psi ψ .
Implementation in the Second Phase of the Framework In the second phase of the framework, we need an MILP formulation that simulates the computing process of a prediction function ψ \psi ψ . Such a formulation for a prediction function constructed with LLR, ANN, ALR or RLR has been known [21 , 27 , 28 ] . For the data set C \mathcal{C} C for property π \pi π in the first phase, let ( w , b ) (w,b) ( w , b ) denote the hyperplane that splits C \mathcal{C} C into subsets C ( j ) \mathcal{C}^{(j)} C ( j ) , j = 1 , 2 j=1,2 j = 1 , 2 and ψ j \psi_j ψ j be a prediction function constructed for C ( j ) \mathcal{C}^{(j)} C ( j ) . Assume that, for the feature function f f f , a topological specification σ \sigma σ and each prediction function ψ j \psi_j ψ j , j = 1 , 2 j=1,2 j = 1 , 2 , we have an MILP formulation M f , η j , σ \mathcal{M}_{f,\eta_j,\sigma} M f , η j , σ for inferring a chemical graph that satisfies σ \sigma σ in the second phase.
Let y ‾ ∗ \underline{y}^{*} y ∗ and y ‾ ∗ \overline{y}^{*} y ∗ be lower and upper limits for a target value to property π \pi π . Recall that the observed value a ( C ) a(\mathcal{C}) a ( C ) of a chemical compound C ∈ C \mathcal{C}\in\mathcal{C} C ∈ C is normalized to a value ν ( a ( C ) ) \nu(a(\mathcal{C})) ν ( a ( C )) between 0 and 1. Let ν ( y ‾ ∗ ) \nu(\underline{y}^{*}) ν ( y ∗ ) and ν ( y ‾ ∗ ) \nu(\overline{y}^{*}) ν ( y ∗ ) denote the normalized values of y ‾ ∗ \underline{y}^{*} y ∗ and y ‾ ∗ \overline{y}^{*} y ∗ , respectively, where we assume that either ν ( y ‾ ∗ ) ≤ max { a max ( 1 ) , θ } \nu(\underline{y}^{*})\leq\max\{a_{\max}^{(1)},\theta\} ν ( y ∗ ) ≤ max { a m a x ( 1 ) , θ } or min { a min ( 2 ) , θ } ≤ ν ( y ‾ ∗ ) \min\{a_{\min}^{(2)},\theta\}\leq\nu(\overline{y}^{*}) min { a m i n ( 2 ) , θ } ≤ ν ( y ∗ ) (otherwise we consider two target instances [ ν ( y ‾ ∗ ) , max { a max ( 1 ) , θ } ] [\nu(\underline{y}^{*}),\max\{a_{\max}^{(1)},\theta\}] [ ν ( y ∗ ) , max { a m a x ( 1 ) , θ }] and [ min { a min ( 2 ) , θ } , ν ( y ‾ ∗ ) ] [\min\{a_{\min}^{(2)},\theta\},\nu(\overline{y}^{*})] [ min { a m i n ( 2 ) , θ } , ν ( y ∗ )] ). In the former (resp., the latter), we solve the MILP M f , η 1 , σ \mathcal{M}_{f,\eta_1,\sigma} M f , η 1 , σ plus an additional constraint of w x i − b ≤ 0 wx_i-b\leq0 w x i − b ≤ 0 (resp., MILP M f , η 2 , σ \mathcal{M}_{f,\eta_2,\sigma} M f , η 2 , σ plus an additional constraint of w x i − b ≥ 0 wx_i-b\geq0 w x i − b ≥ 0 ) to infer a desired chemical graph C † \mathcal{C}^{\dagger} C † .
Results
With our new method of splitting a data set and formulating an MILP to treat quadratic descriptors in the two-layered model, we implemented the framework for inferring chemical graphs and conducted experiments to evaluate the computational efficiency. We executed the experiments on a PC with Processor: Core i7-9700 (3.0GHz; 4.7 GHz at the maximum) and Memory: 16 GB RAM DDR4. To construct a prediction function by MLR (multidimensional linear regression), or ANN (artificial neural network), we used scikit-learn version 1.0.2 with Python 3.8.12, MLPRegressor for MLR, and ReLU activation function for ANN.
Results on the First Phase of the Framework
Chemical Properties We implemented the first phase for the following 22 chemical properties of monomers:
autoignition temperature (At), biological half life (BHL), critical pressure (Cp), critical temperature (Ct), dissociation constants (Dc), flammable limits lower (FlmL), flammable limits upper (FlmU), flash point in closed cup (Fp), melting point (Mp), refractive index of trees (RfIdT), odor threshold lower (OdrL), odor threshold upper (OdrU) and vapor pressure (Vp) provided by HSDB from PubChem [30 ] ;
solubility (SL) by ESOL [31 ] ;
autoignition temperature for organic compounds (AtO) by A. Dashti et al. [32 ] ;
flammable limits upper for organic compounds (FlmUO) by S. Yuan et al. [33 ] ;
flammable limits lower for gas (FlmL G) and flammable limits upper for gas (FlmUG) by S. Kondo et al. [34 ] ; and energy of highest occupied molecular orbital (HOMO), energy of lowest unoccupied molecular orbital (LUMO), the energy difference between HOMO and LUMO (GAP) and electric dipole moment (MU) provided by MoleculeNet [35 ] , where all these from HOMO to MU are based on a common data set QM9.
The data set QM9 contains more than 130,000 compounds. In our experiment, we use a set of 1,000 compounds randomly selected from the data set. We do not exclude any polymer from the original data set as outliers for these properties.
Setting Data Sets For each property π \pi π , we first select a set Λ \Lambda Λ of chemical elements and then collect a data set C π C_{\pi} C π on chemical graphs over the set Λ \Lambda Λ of chemical elements. To construct the data set C π C_{\pi} C π , we eliminated chemical compounds that do not satisfy one of the following: the graph is connected, the number of carbon atoms is at least four, and the number of non-hydrogen neighbors of each atom is at most 4.
We set a branch-parameter ρ \rho ρ to be 2, introduce linear descriptors defined by the two-layered graph in the chemical model without suppressing hydrogen and use the sets D π ( 1 ) D_{\pi}^{(1)} D π ( 1 ) and D π ( 2 ) D_{\pi}^{(2)} D π ( 2 ) of linear and quadratic descriptors (see Appendix § 10 for the details).
For properties π ∈ { B H L , F l m L , F l m L G , F l m U , F l m U O , F l m U G , O d r L , O d r U , V p } \pi\in\{\mathrm{BHL}, \mathrm{FlmL}, \mathrm{FlmLG}, \mathrm{FlmU}, \mathrm{FlmUO}, \mathrm{FlmUG}, \mathrm{OdrL}, \mathrm{OdrU}, \mathrm{Vp}\} π ∈ { BHL , FlmL , FlmLG , FlmU , FlmUO , FlmUG , OdrL , OdrU , Vp } , we take the logarithmic measurement of observed values a ( C ) a(C) a ( C ) , C ∈ D π C \in D_{\pi} C ∈ D π , where log ( a ( C ) + c ) \log(a(C)+c) log ( a ( C ) + c ) (c = 10 − 8 c=10^{-8} c = 1 0 − 8 if π = V p \pi=\mathrm{Vp} π = Vp and c = 0 c=0 c = 0 otherwise) is used as the observed value in our experiments.
We normalize the range of each linear descriptor and the range of observed values a ( C ) a(C) a ( C ) , C ∈ C π C \in C_{\pi} C ∈ C π .
We conducted an experiment of comparing the following five methods of constructing a prediction function.
LLR: use Lasso linear regression on the set D π ( 1 ) D_{\pi}^{(1)} D π ( 1 ) of linear descriptors (see [21 ] for the detail of the implementation);
ANN: use ANN on the set D π ( 1 ) D_{\pi}^{(1)} D π ( 1 ) of linear descriptors (see [21 ] for the detail of the implementation);
ALR: use adjustive linear regression on the set D π ( 1 ) D_{\pi}^{(1)} D π ( 1 ) of linear descriptors (see [27 ] for the detail of the implementation);
RLR: the learning method proposed by Zhu et al. [28 ] that chooses a set of descriptors from the set D π ( 1 ) ∪ D π ( 2 ) D_{\pi}^{(1)} \cup D_{\pi}^{(2)} D π ( 1 ) ∪ D π ( 2 ) of linear and quadratic descriptors and then constructs a prediction function by applying MLR (multidimensional linear regression) to the resulting set of descriptors; and
HPS: our method of computing a hyperplane to split a given data set into two subsets and constructing a prediction function to each subset independently. By conducting a preliminary experiment, we predetermine a threshold θ \theta θ and a hyperplane ( w , b ) (w,b) ( w , b ) , w ∈ R ∣ D π ( 1 ) ∣ w \in\mathbb{R}^{|D_{\pi}^{(1)}|} w ∈ R ∣ D π ( 1 ) ∣ and b ∈ R b \in\mathbb{R} b ∈ R in the feature space of linear descriptors. In a cross-validation, we split a training data set C ^ π ⊆ C π \widehat{C}_{\pi} \subseteq C_{\pi} C π ⊆ C π into two subsets C ^ π ( j ) \widehat{C}_{\pi}^{(j)} C π ( j ) , j = 1 , 2 j=1,2 j = 1 , 2 and construct a prediction function ψ j \psi_j ψ j to each subset C ^ π ( j ) \widehat{C}_{\pi}^{(j)} C π ( j ) by applying one of the above four methods (i)–(iv).
Table 1 shows the size and range of data sets that we prepared for each chemical property to construct a prediction function, where we denote the following:
Table 1. Results of setting data sets.
Λ \Lambda Λ : a set of selected elements used in the data set C π C_{\pi} C π ; Λ \Lambda Λ is one of the following eight sets: Λ 1 = { H , C , O , N } \Lambda_{1} = \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}\} Λ 1 = { H , C , O , N } ; Λ 2 = { H , C , O , N , F } \Lambda_{2} = \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}, \mathrm{F}\} Λ 2 = { H , C , O , N , F } ; Λ 3 = { H , C , O , N , C l , S ( 2 ) , S ( 6 ) } \Lambda_{3} = \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}, \mathrm{Cl}, \mathrm{S}_{(2)}, \mathrm{S}_{(6)}\} Λ 3 = { H , C , O , N , Cl , S ( 2 ) , S ( 6 ) } ; Λ 4 = { H , C , O , N , C l , P b } \Lambda_{4} = \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}, \mathrm{Cl}, \mathrm{Pb}\} Λ 4 = { H , C , O , N , Cl , Pb } ; Λ 5 = { H , C , O , N , S ( 2 ) , S ( 4 ) , S ( 6 ) , C l , B r , F } \Lambda_{5} = \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}, \mathrm{S}_{(2)}, \mathrm{S}_{(4)}, \mathrm{S}_{(6)}, \mathrm{Cl}, \mathrm{Br}, \mathrm{F}\} Λ 5 = { H , C , O , N , S ( 2 ) , S ( 4 ) , S ( 6 ) , Cl , Br , F } ; Λ 6 = { H , C , O , N , C l , P ( 2 ) , P ( 5 ) } \Lambda_{6} = \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}, \mathrm{Cl}, \mathrm{P}_{(2)}, \mathrm{P}_{(5)}\} Λ 6 = { H , C , O , N , Cl , P ( 2 ) , P ( 5 ) } ; Λ 7 = { H , C , O , N , C l , B r } \Lambda_{7} = \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}, \mathrm{Cl}, \mathrm{Br}\} Λ 7 = { H , C , O , N , Cl , Br } ; Λ 8 = { H , C , O , N , C l , B r , F } \Lambda_{8} = \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}, \mathrm{Cl}, \mathrm{Br}, \mathrm{F}\} Λ 8 = { H , C , O , N , Cl , Br , F } , where a ( i ) a_{(i)} a ( i ) for a chemical element a and an integer i ≥ 1 i \ge1 i ≥ 1 means that
a chemical element a a a with valence i i i .
∣ C π ∣ |C_{\pi}| ∣ C π ∣ : the size of data set C π C_{\pi} C π over the element set Λ \Lambda Λ for the property π \pi π .
n ‾ \underline{n} n , n ‾ \overline{n} n : the minimum and maximum values of the number n ( C ) n(C) n ( C ) of non-hydrogen atoms in the compounds C C C in C π C_{\pi} C π .
a ‾ \underline{a} a , a ‾ \overline{a} a : the minimum and maximum values of a ( C ) a(C) a ( C ) (or the logarithm of the original observed values) for π \pi π over the compounds C C C in C π C_{\pi} C π before we normalize them between 0 and 1.
∣ Γ ∣ |\Gamma| ∣Γ∣ : the number of different edge-configurations of interior-edges over the compounds in C π C_{\pi} C π .
∣ F ∣ |\mathcal{F}| ∣ F ∣ : the number of non-isomorphic chemical rooted trees in the set of all 2-fringe-trees in the compounds in C π C_{\pi} C π .
K 1 K_{1} K 1 : the size ∣ D π ( 1 ) ∣ |D_{\pi}^{(1)}| ∣ D π ( 1 ) ∣ of a set D π ( 1 ) D_{\pi}^{(1)} D π ( 1 ) of linear descriptors, where ∣ D π ( 2 ) ∣ = ( 3 K 1 2 + K 1 ) / 2 |D_{\pi}^{(2)}|=(3K_{1}^{2}+K_{1})/2 ∣ D π ( 2 ) ∣ = ( 3 K 1 2 + K 1 ) /2 holds.
Constructing Prediction Functions For each chemical property π \pi π , we construct a prediction function by one of the four methods (i)-(iv).
For methods (i)-(iv), we used the same implementation due to Zhu et al. [21 , 27 , 28 ] and omit the details.
Tables 2 shows the results on constructing prediction functions, where we denote the following:
π , Λ \pi,\Lambda π , Λ : an instance with a chemical property π \pi π and a set Λ \Lambda Λ of chemical elements selected from the data set C π C_{\pi} C π .
LLR: the median of test R 2 \mathrm{R}^{2} R 2 in ten 5-fold cross-validations for prediction functions constructed by the method (i).
ANN: the median of test R 2 \mathrm{R}^{2} R 2 in ten 5-fold cross-validations for prediction functions constructed by the method (ii).
ALR: the median of test R 2 \mathrm{R}^{2} R 2 in ten 5-fold cross-validations for prediction functions constructed by the method (iii).
RLR: the median of test R 2 \mathrm{R}^{2} R 2 in ten 5-fold cross-validations for prediction functions constructed by the method (iv).
HPS: the median of test R 2 \mathrm{R}^{2} R 2 in ten 5-fold cross-validations for the prediction function obtained by HPS, where a prediction function is obtained by combining the prediction functions constructed for the first and second subsets.
the score of LLR, ANN, ALR, RLR or HPS marked with “*” indicates the best performance among the five methods for the property π \pi π ;
θ \theta θ : the threshold used in HPS to split the data set C π C_{\pi} C π .
a max ( 1 ) a_{\max}^{(1)} a m a x ( 1 ) , a min ( 2 ) a_{\min}^{(2)} a m i n ( 2 ) : the maximum observed value a ( C ) a(C) a ( C ) of a compound C ∈ C ( 1 ) C \in C^{(1)} C ∈ C ( 1 ) and the minimum observed value a ( C ) a(C) a ( C ) of a compound C ∈ C ( 2 ) C \in C^{(2)} C ∈ C ( 2 ) in HPS;
∣ C ( 1 ) ∣ |C^{(1)}| ∣ C ( 1 ) ∣ , ∣ C ( 2 ) ∣ |C^{(2)}| ∣ C ( 2 ) ∣ : the sizes of the first subset C ( 1 ) C^{(1)} C ( 1 ) and the second subset C ( 2 ) C^{(2)} C ( 2 ) in HPS.
C ( 1 ) C^{(1)} C ( 1 ) -R2 ^{2} 2 : the name of the method (one of (i)-(iv)) used to construct a prediction function to the first subset in HPS and the median of test R 2 \mathrm{R}^{2} R 2 in ten 5-fold cross-validations for the prediction function over the first subset.
C ( 2 ) C^{(2)} C ( 2 ) -R2 ^{2} 2 : the name of the method (one of (i)-(iv)) used to construct a prediction function to the second subset in HPS and the median of test R 2 \mathrm{R}^{2} R 2 in ten 5-fold cross-validations for the prediction function over the second subset.
The running time of constructing two prediction functions for subsets C ( 1 ) C^{(1)} C ( 1 ) and C ( 2 ) C^{(2)} C ( 2 ) in HPS was at most around 13 seconds. To execute RLR, selecting a subset of linear and quadratic descriptors is the most time consuming part, which took from 1162 to 44356 seconds.
In Table 2, HPS attains the best score of the median test R2 ^{2} 2 among the five methods in most cases. Especially the improvement over the methods (i)-(iv) is significant for properties AT _{\mathrm{T}} T , Fl m _{\mathrm{lm}} lm L, Fl m _{\mathrm{lm}} lm U, Fl m _{\mathrm{lm}} lm UO, Fl m _{\mathrm{lm}} lm UG, OdrL and OdrU.
From the values a max ( 1 ) , a min ( 2 ) a_{\max}^{(1)},a_{\min}^{(2)} a m a x ( 1 ) , a m i n ( 2 ) in Table 2 , we see how the original set C π \mathcal{C}_{\pi} C π is split with a hyperplane into two subsets C ( j ) \mathcal{C}^{(j)} C ( j ) , j = 1 , 2 j=1,2 j = 1 , 2 for each property π \pi π . For property AT _{\mathrm{T}} T with λ 1 \lambda_{1} λ 1 , it holds that a max ( 1 ) = 0.505 > a min ( 2 ) = 0.293 a_{\max}^{(1)} = 0.505 > a_{\min}^{(2)} = 0.293 a m a x ( 1 ) = 0.505 > a m i n ( 2 ) = 0.293 , which implies that no hyperplane separates C < θ = { C i ∈ C π ∣ a i ≤ θ } \mathcal{C}_{<\theta} = \{\mathcal{C}_{i} \in\mathcal{C}_{\pi} \mid a_{i} \leq\theta\} C < θ = { C i ∈ C π ∣ a i ≤ θ } and C > θ = { C i ∈ C π ∣ a i > θ } \mathcal{C}_{>\theta} = \{\mathcal{C}_{i} \in\mathcal{C}_{\pi} \mid a_{i} > \theta\} C > θ = { C i ∈ C π ∣ a i > θ } for θ = 0.40 \theta= 0.40 θ = 0.40 . On the other hand, for property AT _{\mathrm{T}} T O, it holds that a max ( 1 ) = 0.447 < θ = 0.45 < a min ( 2 ) = 0.451 a_{\max}^{(1)} = 0.447 < \theta= 0.45 < a_{\min}^{(2)} = 0.451 a m a x ( 1 ) = 0.447 < θ = 0.45 < a m i n ( 2 ) = 0.451 , which implies that C π \mathcal{C}_{\pi} C π is split with a hyperplane into C ( 1 ) = C ≤ θ \mathcal{C}^{(1)} = \mathcal{C}_{\leq\theta} C ( 1 ) = C ≤ θ and C ( 2 ) = C > θ \mathcal{C}^{(2)} = \mathcal{C}_{>\theta} C ( 2 ) = C > θ .
Table 2. Results of constructing prediction functions for monomers.
For some properties such as A T \mathrm{A_T} A T with λ 1 \lambda_1 λ 1 , the median R 2 \mathrm{R}^2 R 2 of HPS is considerably larger than the median R 2 \mathrm{R}^2 R 2 of C ( 1 ) \mathcal{C}^{(1)} C ( 1 ) -R 2 \mathrm{R}^2 R 2 and C ( 2 ) \mathcal{C}^{(2)} C ( 2 ) -R 2 \mathrm{R}^2 R 2 . For property π = A T \pi= \mathrm{A_T} π = A T with λ 1 \lambda_1 λ 1 , the median R 2 \mathrm{R}^2 R 2 of HPS is 0.808 whereas that of C ( 1 ) \mathcal{C}^{(1)} C ( 1 ) (resp., C ( 2 ) \mathcal{C}^{(2)} C ( 2 ) ) is 0.220 (resp., 0.521). This can happen because the range [ a min ( 1 ) = 0 , a max ( 1 ) = 0.505 ] [a_{\min}^{(1)} = 0, a_{\max}^{(1)} = 0.505] [ a m i n ( 1 ) = 0 , a m a x ( 1 ) = 0.505 ] (resp., [ a min ( 2 ) = 0.293 , a max ( 2 ) = 1 ] [a_{\min}^{(2)} = 0.293, a_{\max}^{(2)} = 1] [ a m i n ( 2 ) = 0.293 , a m a x ( 2 ) = 1 ] ) of observed values for C ( 1 ) \mathcal{C}^{(1)} C ( 1 ) (resp., C ( 2 ) ) \mathcal{C}^{(2)}) C ( 2 ) ) is again normalized to [ 0 , 1 ] [0,1] [ 0 , 1 ] on which a prediction function ψ 1 \psi_1 ψ 1 (resp., ψ 2 \psi_2 ψ 2 ) is constructed and its learning performance C ( 1 ) \mathcal{C}^{(1)} C ( 1 ) -R 2 \mathrm{R}^2 R 2 (resp., C ( 2 ) \mathcal{C}^{(2)} C ( 2 ) -R 2 \mathrm{R}^2 R 2 ) is evaluated. However, in the evaluation of ψ \psi ψ for the median R 2 \mathrm{R}^2 R 2 of HPS, the error caused by each of the prediction functions ψ j \psi_j ψ j , j = 1 , 2 j = 1, 2 j = 1 , 2 is measured as a relatively smaller value over the original wider range of observed values to C π \mathcal{C}_{\pi} C π .
Results on the Second Phase of the Framework
To execute the second phase, we used a set of seven instances I a I_a I a , I b i I_b^i I b i , i ∈ [ 1 , 4 ] i \in[1,4] i ∈ [ 1 , 4 ] , I c I_c I c and I d I_d I d based on the seed graphs prepared by Zhu et al. [21 ] . The instances I a I_a I a and I c I_c I c have restricted seed graphs, the instances I b i I_b^i I b i have abstract seed graphs and instances I c I_c I c and I d I_d I d have restricted set of fringe-trees. We here present their seed graphs G C G_C G C (see Appendix § 11 for the details of I a I_a I a and Appendix § 13 for the details of I b i I_b^i I b i , i ∈ [ 1 , 4 ] i \in[1,4] i ∈ [ 1 , 4 ] , I c I_c I c and I d I_d I d ).
The seed graph G C G_C G C of I a I_a I a is given by the graph in Figure 4 (a). The seed graph G C 1 G_C^1 G C 1 of I b 1 I_b^1 I b 1 (resp., G C i G_C^i G C i , i = 2 , 3 , 4 i = 2,3,4 i = 2 , 3 , 4 of I b i I_b^i I b i , i = 2 , 3 , 4 i = 2,3,4 i = 2 , 3 , 4 ) is illustrated in Figure 5 .
Figure 5. (i) Seed graph G C 1 G_C^1 G C 1 for I b 1 I_b^1 I b 1 and I d I_d I d ; (ii) Seed graph G C 2 G_C^2 G C 2 for I b 2 I_b^2 I b 2 ; (iii) Seed graph G C 3 G_C^3 G C 3 for I b 3 I_b^3 I b 3 ; (iv) Seed graph G C 4 G_C^4 G C 4 for I b 4 I_b^4 I b 4 .
Instance I c I_c I c has been introduced in order to infer a chemical graph C † \mathcal{C}^{\dagger} C † such that
a core part of C † \mathcal{C}^{\dagger} C † is equal to that of chemical graph C A \mathcal{C}_A C A : CID 24822711 in Figure 6 (a) (where the seed graph G C G_C G C of I c I_c I c is indicated by the shaded area in Figure 6 (a)).
the frequency of each edge-configuration in the non-core of C † \mathcal{C}^{\dagger} C † is equal to that of chemical graph C B \mathcal{C}_B C B : CID 59170444 in Figure 6 (b).
Figure 6. An illustration of chemical compounds for instances I c I_c I c and I d I_d I d : (a) C A C_A C A : CID 24822711; (b) C B C_B C B : CID 59170444; (c) C A C_A C A : CID 10076784; (d) C B C_B C B : CID 44340250, where hydrogens are omitted.
Instance I d I_d I d has been introduced in order to infer a chemical graph C † \mathcal{C}^{\dagger} C † such that
C † \mathcal{C}^{\dagger} C † is monocyclic (where the seed graph of I d I_d I d is given by G C 1 G_C^1 G C 1 in Figure 5 (i)); and
the frequency vector of edge-configurations in C † \mathcal{C}^{\dagger} C † is a vector obtained by merging those of chemical graphs C A \mathcal{C}_A C A : CID 10076784 and C B \mathcal{C}_B C B : CID 44340250 in Figure 6 (c) and (d), respectively.
Solving an MILP for the Inverse Problem We executed the stage of solving an MILP to infer a chemical graph for two properties π ∈ { A T , F L M L } \pi\in\{\mathrm{A_T}, \mathrm{F_LM_L}\} π ∈ { A T , F L M L } .
For the MILP formulation M f , n , σ \mathcal{M}_{f,n,\sigma} M f , n , σ , we use the prediction function η \eta η for each A T \mathrm{A_T} A T with Λ 3 \Lambda_3 Λ 3 and F L M L \mathrm{F_LM_L} F L M L with Λ 6 \Lambda_6 Λ 6 constructed by method (v), HPS that attained the median test R 2 \mathrm{R}^2 R 2 in Table 2 .
To solve an MILP with the formulation, we used CPLEX version 12.10. Table 3 and Table 4 show the computational results of the experiment in this stage for the two properties, where we denote the following:
Table 3. Results of inferring a chemical graph C† and generating recombination solutions for AΓ with Λ₃.
Table 4. Results of inferring a chemical graph C† and generating recombination solutions for FₗₘL with Λ₆.
n L B n_{\mathrm{LB}} n LB : a lower bound on the number of non-hydrogen atoms in a chemical graph C to be inferred;
y ‾ ∗ \underline{y}^{*} y ∗ , y ‾ ∗ \overline{y}^{*} y ∗ : lower and upper bounds y ‾ ∗ , y ‾ ∗ ∈ R \underline{y}^{*},\overline{y}^{*} \in\mathbb{R} y ∗ , y ∗ ∈ R on the value a ( C ) a(\mathrm{C}) a ( C ) of a chemical graph C to be inferred; For At, we use range of the original values a ( C ) a(\mathrm{C}) a ( C ) before normalization. For FlmL, we use the logarithmic scale log a ( C ) \log a(\mathrm{C}) log a ( C ) as the range of target values.
# v \#\mathrm{v} # v (resp., # c \#\mathrm{c} # c ): the number of variables (resp., constraints) in the MILP;
I-time: the time (sec.) to solve the MILP;
n n n : the number n ( C † ) n(\mathrm{C}^{\dagger}) n ( C † ) of non-hydrogen atoms in the chemical graph C † \mathrm{C}^{\dagger} C † inferred by solving the MILP;
n i n t n^{\mathrm{int}} n int : the number n i n t ( C † ) n^{\mathrm{int}}(\mathrm{C}^{\dagger}) n int ( C † ) of interior-vertices in the inferred chemical graph C † \mathrm{C}^{\dagger} C † ; and
η \eta η : the predicted property value η ( f ( C † ) ) \eta(f(\mathrm{C}^{\dagger})) η ( f ( C † )) of the inferred chemical graph C † \mathrm{C}^{\dagger} C † .
Figure 7 (a) illustrates the chemical graph C † \mathrm{C}^{\dagger} C † inferred from I c I_c I c with ( y ‾ ∗ , y ‾ ∗ ) = ( 360 , 370 ) (\underline{y}^{*},\overline{y}^{*})=(360,370) ( y ∗ , y ∗ ) = ( 360 , 370 ) of At in Table 3.
Figure 7.
Figure 7(b) (resp., Figure 7(c)) illustrates the chemical graph C† inferred from I a I_a I a with ( y ∗ , y ˉ ∗ ) = ( − 0.55 , − 0.5 ) (y^{*},\bar{y}^{*}) = (-0.55,-0.5) ( y ∗ , y ˉ ∗ ) = ( − 0.55 , − 0.5 ) (resp., I d I_d I d with ( y ∗ , y ˉ ∗ ) = ( 0.2 , 0.25 ) (y^{*},\bar{y}^{*}) = (0.2,0.25) ( y ∗ , y ˉ ∗ ) = ( 0.2 , 0.25 ) ) of FₗₘL in Table 4.
From Tables 3 and 4, we observe that an instance with a large number of variables and constraints takes more running time than those with a smaller size in general. All instances in this experiment are solved in a few seconds to around 30 seconds with our MILP formulation.
Generating Recombination Solutions
Let C † \mathrm{C}^{\dagger} C † be a chemical graph obtained by solving the MILP M f , η , σ \mathcal{M}_{f,\eta,\sigma} M f , η , σ for the inverse problem. We here execute a stage of generating recombination solutions C ∗ ∈ G σ \mathrm{C}^{*} \in\mathcal{G}_{\sigma} C ∗ ∈ G σ of C † \mathrm{C}^{\dagger} C † such that f ( C ∗ ) = x ∗ = f ( C † ) f(\mathrm{C}^{*}) = x^{*} = f(\mathrm{C}^{\dagger}) f ( C ∗ ) = x ∗ = f ( C † ) .
We execute an algorithm for generating chemical isomers of C † \mathrm{C}^{\dagger} C † up to 100 when the number of all chemical isomers exceeds 100. For this, we use a dynamic programming algorithm [21 ] . The algorithm first decomposes C † \mathrm{C}^{\dagger} C † into a set of acyclic chemical graphs, next replaces each acyclic chemical graph T T T with another acyclic chemical graph T ′ T' T ′ that admits the same feature vector as that of T T T and finally assembles the resulting acyclic chemical graphs into a chemical isomer C ∗ \mathrm{C}^{*} C ∗ of C † \mathrm{C}^{\dagger} C † . The algorithm can compute a lower bound on the total number of all chemical isomers C † \mathrm{C}^{\dagger} C † without generating all of them.
Tables 3 and 4 show the computational results of the experiment in this stage for the two properties π ∈ { A T , F L m L } \pi\in\{\mathrm{A}_{T}, \mathrm{F}_{\mathrm{LmL}}\} π ∈ { A T , F LmL } , where we denote the following:
D-time: the running time (sec.) to execute the dynamic programming algorithm to compute a lower bound on the number of all chemical isomers C ∗ \mathrm{C}^{*} C ∗ of C † \mathrm{C}^{\dagger} C † and generate all (or up to 100) chemical isomers C ∗ \mathrm{C}^{*} C ∗ ;
C-LB: a lower bound on the number of all chemical isomers C ∗ \mathrm{C}^{*} C ∗ of C † \mathrm{C}^{\dagger} C † ; and
#C: the number of all (or up to 100) chemical isomers C ∗ \mathrm{C}^{*} C ∗ of C † \mathrm{C}^{\dagger} C † generated in this stage.
From Tables 3 and 4, we observe the running time and the number of generated recombination solutions in this stage.
For the tested properties, the chemical graph C † \mathrm{C}^{\dagger} C † in I b 2 I_{b}^{2} I b 2 , I b 3 I_{b}^{3} I b 3 and I d I_{d} I d admits a large number of chemical isomers C ∗ \mathrm{C}^{*} C ∗ , where a lower bound C-LB on the number of chemical isomers is derived without generating all of them. The running time for computing the lower bound and generating up to 100 target chemical graphs is at most 18 second. For some chemical graphs C † \mathrm{C}^{\dagger} C † , the number of chemical isomers found by our algorithm was small. This is because some of acyclic chemical graphs in the decomposition of C † \mathrm{C}^{\dagger} C † has no alternative acyclic chemical graph other than the original one.
Generating Neighbor Solutions
Let C † \mathrm{C}^{\dagger} C † be a chemical graph obtained by solving the MILP M f , η , σ \mathcal{M}_{f,\eta,\sigma} M f , η , σ for the inverse problem. We executed a stage of generating neighbor solutions of C † \mathrm{C}^{\dagger} C † .
We select an MILP for the inverse problem with a prediction function η \eta η such that a solution C † \mathrm{C}^{\dagger} C † of the MILP admits only two isomers C ∗ \mathrm{C}^{*} C ∗ in the stage of generating recombination solutions; i.e., instance I c I_{c} I c for property AT with Λ 3 \Lambda_{3} Λ 3 and instances I a I_{a} I a , I b 4 I_{b}^{4} I b 4 and I c I_{c} I c for property FLmL with Λ 6 \Lambda_{6} Λ 6 .
In this experiment, we add to the MILP M f , η , σ \mathcal{M}_{f,\eta,\sigma} M f , η , σ an additional set Θ \Theta Θ of two linear constraints on linear and quadratic descriptors as follows. For the two constraints, we use the prediction functions η π \eta_{\pi} η π constructed by RLR for properties π ∈ { M P , S L } \pi\in\{\mathrm{M}_{P}, \mathrm{S}_{L}\} π ∈ { M P , S L } with Λ 3 \Lambda_{3} Λ 3 in Table 2.
We regard each of η M P \eta_{\mathrm{MP}} η MP and η S L \eta_{\mathrm{SL}} η SL as a function from R ∣ D π u n i o n ∣ \mathbb{R}^{|D_{\pi}^{\mathrm{union}}|} R ∣ D π union ∣ to R \mathbb{R} R for π ∈ { A T , F L m L } \pi\in\{\mathrm{AT}, \mathrm{FLmL}\} π ∈ { AT , FLmL } . We set p d i m : = 2 p_{\mathrm{dim}} := 2 p dim := 2 and let Θ \Theta Θ consist of two linear constraints θ 1 : = η M P \theta_{1} := \eta_{\mathrm{MP}} θ 1 := η MP and θ 2 : = η S L \theta_{2} := \eta_{\mathrm{SL}} θ 2 := η SL . We select δ ∈ { 0.01 , 0.05 , 0.1 , 0.15 } \delta\in\{0.01, 0.05, 0.1, 0.15\} δ ∈ { 0.01 , 0.05 , 0.1 , 0.15 } which defines a two-dimensional grid space where C † \mathrm{C}^{\dagger} C † is mapped to the origin (see [23 ] for the detail on the neighbors). We choose a set N 0 N_{0} N 0 of 48 neighbors of the origin C † \mathrm{C}^{\dagger} C † in the grid search space. For each instance, we check the feasibility of neighbors in N 0 N_{0} N 0 in a non-decreasing order of the distance between the neighbor and the origin. For each feasible neighbor z ∈ N 0 z \in N_0 z ∈ N 0 , output a feasible solution C z † C_z^\dagger C z † of the augmented MILP instance. We set a time limit for checking the feasibility of a neighbor to be 300 seconds, and we skip a neighbor when the corresponding MILP is not solved within the time limit. We also ignore any neighbor z ∈ N 0 z \in N_0 z ∈ N 0 without testing the feasibility of z z z if we find an infeasible neighbor z ′ ∈ N 0 z' \in N_0 z ′ ∈ N 0 such that z ′ z' z ′ is closer to the origin than z z z is.
Table 5 shows the computational results of the experiment for the three instances, where we denote the following:
( i n s t . , π ) (\mathrm{inst.}, \pi) ( inst. , π ) : topological specification I I I and property π \pi π ;
n n n : the number of non-hydrogen atoms in the tested instance;
δ \delta δ : the size of a sub-region in the grid search space;
#sol: the number of new chemical graphs obtained from the neighbor set N 0 N_0 N 0 ;
#infs: the number of neighbors in N 0 N_0 N 0 that are found to be infeasible during the search procedure;
#ign: the number of neighbors in N 0 N_0 N 0 that are ignored during the search procedure;
#TO: the number of neighbors in N 0 N_0 N 0 such that the time for feasibility check exceeds the time limit of 300 seconds during the search procedure.
Table 5. Results of generating neighbor solutions of C † C^\dagger C † .
In many solvers such as CPLEX, an MILP is solved by an algorithm based on the branch-and-bound method, which sometimes takes an extremely large execution time for the same size of instances. We introduce a time limit to bound a running time of testing the feasibility of neighbors in N 0 N_0 N 0 to skip such instances. From Table 5, we observe that some number of neighbor solutions of C † C^\dagger C † could be successfully generated for each of the four instances.
Concluding Remarks
In the framework of inferring chemical graphs, the descriptors of a prediction function were mainly defined to be the frequencies of local graph structures in the two-layered model and defining descriptors in such a way is important to derive a compact MILP formulation in the second phase of the framework. To improve the performance of prediction functions based on the same definition of descriptors, this paper proposed a method of splitting a given data set into two subsets by a hyperplane in the feature space so that the first and second subsets mainly consist of compounds with observed values lower and higher than a threshold, respectively. A prediction function is obtained by combining prediction functions for the first and second subsets constructed independently, where the hyperplane is used to decide which of the two prediction functions is applied for a given feature vector. Our experimental results show that the proposed method improved the learning performance of chemical properties such as flammable limits and odor threshold and that the MILP in the second phase is solvable for instances of inferring a chemical graph with around 50 non-hydrogen atoms. It is left as a future work to extend our new method of splitting a data set so that a given data set is repeatedly split into smaller subsets with a narrower range of observed values when the size of the data set is large enough.
References
Appendix
A Full Description of Descriptors
Associated with the two functions α \alpha α and β \beta β in a chemical graph C = ( H , α , β ) \mathrm{C} = (H,\alpha,\beta) C = ( H , α , β ) , we introduce functions ac : V ( E ) → ( Λ ∖ { H } ) × ( Λ ∖ { H } ) × [ 1 , 3 ] \operatorname{ac}: V(E) \to(\Lambda\setminus\{H\}) \times(\Lambda\setminus\{H\}) \times[1,3] ac : V ( E ) → ( Λ ∖ { H }) × ( Λ ∖ { H }) × [ 1 , 3 ] , cs : V ( E ) → ( Λ ∖ { H } ) × [ 1 , 6 ] \operatorname{cs}: V(E) \to(\Lambda\setminus\{H\}) \times[1,6] cs : V ( E ) → ( Λ ∖ { H }) × [ 1 , 6 ] and ec : V ( E ) → ( ( Λ ∖ { H } ) × [ 1 , 6 ] ) × ( ( Λ ∖ { H } ) × [ 1 , 6 ] ) × [ 1 , 3 ] \operatorname{ec}: V(E) \to((\Lambda\setminus\{H\}) \times[1,6]) \times((\Lambda\setminus\{H\}) \times[1,6]) \times[1,3] ec : V ( E ) → (( Λ ∖ { H }) × [ 1 , 6 ]) × (( Λ ∖ { H }) × [ 1 , 6 ]) × [ 1 , 3 ] in the following.
To represent a feature of the exterior of C \mathrm{C} C , a chemical rooted tree in T ( C ) \mathcal{T}(\mathrm{C}) T ( C ) is called a fringe-configuration of C \mathrm{C} C .
We also represent leaf-edges in the exterior of C \mathrm{C} C . For a leaf-edge u v ∈ E ( ⟨ C ⟩ ) uv \in E(\langle\mathrm{C}\rangle) uv ∈ E (⟨ C ⟩) with deg ⟨ C ⟩ ( u ) = 1 \deg_{\langle\mathrm{C}\rangle}(u) = 1 deg ⟨ C ⟩ ( u ) = 1 , we define the adjacency-configuration of e e e to be an ordered tuple ( α ( u ) , α ( v ) , β ( u v ) ) (\alpha(u),\alpha(v),\beta(uv)) ( α ( u ) , α ( v ) , β ( uv )) . Define
Γ ac leaves ≜ { ( a , b , m ) ∣ a , b ∈ Λ , m ∈ [ 1 , min { val ( a ) , val ( b ) } ] } \Gamma_{\operatorname{ac}}^{\operatorname{leaves}} \mathrel{\triangleq} \{(a,b,m) \mid a,b \in\Lambda, m \in[1,\min\{\operatorname{val}(a),\operatorname{val}(b)\}]\} Γ ac leaves ≜ {( a , b , m ) ∣ a , b ∈ Λ , m ∈ [ 1 , min { val ( a ) , val ( b )}]}
as a set of possible adjacency-configurations for leaf-edges.
To represent a feature of an interior-vertex v ∈ V int ( C ) v \in V^{\operatorname{int}}(\mathrm{C}) v ∈ V int ( C ) such that α ( v ) = a \alpha(v) = a α ( v ) = a and deg ⟨ C ⟩ ( v ) = d \deg_{\langle\mathrm{C}\rangle}(v) = d deg ⟨ C ⟩ ( v ) = d (i.e., the number of non-hydrogen atoms adjacent to v v v is d d d ) in a chemical graph C = ( H , α , β ) \mathrm{C} = (H,\alpha,\beta) C = ( H , α , β ) , we use a pair ( a , d ) ∈ ( Λ ∖ { H } ) × [ 1 , 4 ] (a,d) \in(\Lambda\setminus\{H\}) \times[1,4] ( a , d ) ∈ ( Λ ∖ { H }) × [ 1 , 4 ] , which we call the chemical symbol cs ( v ) \operatorname{cs}(v) cs ( v ) of the vertex v v v . We treat ( a , d ) (a,d) ( a , d ) as a single symbol a d ad a d , and define Λ dg \Lambda_{\operatorname{dg}} Λ dg to be the set of all chemical symbols μ = a d ∈ ( Λ ∖ { H } ) × [ 1 , 4 ] \mu= ad \in(\Lambda\setminus\{H\}) \times[1,4] μ = a d ∈ ( Λ ∖ { H }) × [ 1 , 4 ] .
We define a method for featuring interior-edges as follows. Let e = u v ∈ E int ( C ) e = uv \in E^{\operatorname{int}}(\mathrm{C}) e = uv ∈ E int ( C ) be an interior-edge e = u v ∈ E int ( C ) e = uv \in E^{\operatorname{int}}(\mathrm{C}) e = uv ∈ E int ( C ) such that α ( u ) = a \alpha(u) = a α ( u ) = a , α ( v ) = b \alpha(v) = b α ( v ) = b and β ( e ) = m \beta(e) = m β ( e ) = m in a chemical graph C = ( H , α , β ) \mathrm{C} = (H,\alpha,\beta) C = ( H , α , β ) . To feature this edge e e e , we use a tuple ( a , b , m ) ∈ ( Λ ∖ { H } ) × ( Λ ∖ { H } ) × [ 1 , 3 ] (a,b,m) \in(\Lambda\setminus\{H\}) \times(\Lambda\setminus\{H\}) \times[1,3] ( a , b , m ) ∈ ( Λ ∖ { H }) × ( Λ ∖ { H }) × [ 1 , 3 ] , which we call the adjacency-configuration ac ( e ) \operatorname{ac}(e) ac ( e ) of the edge e e e . We introduce a total order < < < over the elements in Λ \Lambda Λ to distinguish between ( a , b , m ) (a,b,m) ( a , b , m ) and ( b , a , m ) (b,a,m) ( b , a , m ) (a ≠ b a \ne b a = b ) notationally. For a tuple ν = ( a , b , m ) \nu= (a,b,m) ν = ( a , b , m ) , let ν ˉ \bar{\nu} ν ˉ denote the tuple ( b , a , m ) (b,a,m) ( b , a , m ) .
Let e = u v ∈ E int ( C ) e = uv \in E^{\operatorname{int}}(\mathrm{C}) e = uv ∈ E int ( C ) be an interior-edge e = u v ∈ E int ( C ) e = uv \in E^{\operatorname{int}}(\mathrm{C}) e = uv ∈ E int ( C ) such that cs ( u ) = μ \operatorname{cs}(u) = \mu cs ( u ) = μ , cs ( v ) = μ ′ \operatorname{cs}(v) = \mu' cs ( v ) = μ ′ and β ( e ) = m \beta(e) = m β ( e ) = m in a chemical graph C = ( H , α , β ) \mathrm{C} = (H,\alpha,\beta) C = ( H , α , β ) . To feature this edge e e e , we use a tuple ( μ , μ ′ , m ) ∈ Λ dg × Λ dg × [ 1 , 3 ] (\mu,\mu',m) \in\Lambda_{\operatorname{dg}} \times\Lambda_{\operatorname{dg}} \times[1,3] ( μ , μ ′ , m ) ∈ Λ dg × Λ dg × [ 1 , 3 ] , which we call the edge-configuration ec ( e ) \operatorname{ec}(e) ec ( e ) of the edge e e e . We introduce a total order < < < over the elements in Λ dg \Lambda_{\operatorname{dg}} Λ dg to distinguish between ( μ , μ ′ , m ) (\mu,\mu',m) ( μ , μ ′ , m ) and ( μ ′ , μ , m ) (\mu',\mu,m) ( μ ′ , μ , m ) (μ ≠ μ ′ \mu\ne\mu' μ = μ ′ ) notationally. For a tuple γ = ( μ , μ ′ , m ) \gamma= (\mu,\mu',m) γ = ( μ , μ ′ , m ) , let γ ˉ \bar{\gamma} γ ˉ denote the tuple ( μ ′ , μ , m ) (\mu',\mu,m) ( μ ′ , μ , m ) .
Let π \pi π be a chemical property for which we will construct a prediction function η \eta η from a feature vector f ( C ) f(\mathrm{C}) f ( C ) of a chemical graph C \mathrm{C} C to a predicted value y ∈ R y \in\mathbb{R} y ∈ R for the chemical property of C \mathrm{C} C .
We first choose a set Λ \Lambda Λ of chemical elements and then collect a data set C π \mathcal{C}_{\pi} C π of chemical compounds C C C whose chemical elements belong to Λ \Lambda Λ , where we regard C π \mathcal{C}_{\pi} C π as a set of chemical graphs C \mathrm{C} C that represent the chemical compounds C C C in C π \mathcal{C}_{\pi} C π . To define the interior/exterior of chemical graphs C ∈ C π \mathrm{C} \in\mathcal{C}_{\pi} C ∈ C π , we next choose a branch-parameter ρ \rho ρ , where we recommend ρ = 2 \rho= 2 ρ = 2 .
Let Λ int ( C π ) ⊆ Λ \Lambda^{\operatorname{int}}(\mathcal{C}_{\pi}) \subseteq\Lambda Λ int ( C π ) ⊆ Λ (resp., Λ ex ( C π ) ⊆ Λ \Lambda^{\operatorname{ex}}(\mathcal{C}_{\pi}) \subseteq\Lambda Λ ex ( C π ) ⊆ Λ ) denote the set of chemical elements used in the set V int ( C ) V^{\operatorname{int}}(\mathrm{C}) V int ( C ) of interior-vertices (resp., the set V ex ( C ) V^{\operatorname{ex}}(\mathrm{C}) V ex ( C ) of exterior-vertices) of C \mathrm{C} C over all chemical graphs C ∈ C π \mathrm{C} \in\mathcal{C}_{\pi} C ∈ C π , and Γ int ( C π ) \Gamma^{\operatorname{int}}(\mathcal{C}_{\pi}) Γ int ( C π ) denote the set of edge-configurations used in the set E int ( C ) E^{\operatorname{int}}(\mathrm{C}) E int ( C ) of interior-edges in C \mathrm{C} C over all chemical graphs C ∈ C π \mathrm{C} \in\mathcal{C}_{\pi} C ∈ C π . Let F ( C π ) \mathcal{F}(\mathcal{C}_{\pi}) F ( C π ) denote the set of chemical rooted trees ψ \psi ψ isomorphic to a chemical rooted tree in T ( C ) \mathcal{T}(\mathrm{C}) T ( C ) over all chemical graphs C ∈ C π \mathrm{C} \in\mathcal{C}_{\pi} C ∈ C π , where possibly a chemical rooted tree ψ ∈ F ( C π ) \psi\in\mathcal{F}(\mathcal{C}_{\pi}) ψ ∈ F ( C π ) consists of a single chemical element a ∈ Λ ∖ { H } a \in\Lambda\setminus\{H\} a ∈ Λ ∖ { H } .
We define an integer encoding of a finite set A A A of elements to be a bijection σ : A → [ 1 , ∣ A ∣ ] \sigma: A \to[1, |A|] σ : A → [ 1 , ∣ A ∣ ] , where we denote by [ A ] [A] [ A ] the set [ 1 , ∣ A ∣ ] [1, |A|] [ 1 , ∣ A ∣ ] of integers. Introduce an integer coding of each of the sets Λ i n t ( C π ) \Lambda^{\mathrm{int}}(\mathcal{C}_{\pi}) Λ int ( C π ) , Λ e x ( C π ) \Lambda^{\mathrm{ex}}(\mathcal{C}_{\pi}) Λ ex ( C π ) , Γ i n t ( C π ) \Gamma^{\mathrm{int}}(\mathcal{C}_{\pi}) Γ int ( C π ) and F ( C π ) \mathcal{F}(\mathcal{C}_{\pi}) F ( C π ) . Let [ a ] i n t [a]^{\mathrm{int}} [ a ] int (resp., [ a ] e x [a]^{\mathrm{ex}} [ a ] ex ) denote the coded integer of an element a ∈ Λ i n t ( C π ) a \in\Lambda^{\mathrm{int}}(\mathcal{C}_{\pi}) a ∈ Λ int ( C π ) (resp., a ∈ Λ e x ( C π ) a \in\Lambda^{\mathrm{ex}}(\mathcal{C}_{\pi}) a ∈ Λ ex ( C π ) ), [ γ ] [\gamma] [ γ ] denote the coded integer of an element γ \gamma γ in Γ i n t ( C π ) \Gamma^{\mathrm{int}}(\mathcal{C}_{\pi}) Γ int ( C π ) and [ ψ ] [\psi] [ ψ ] denote an element ψ \psi ψ in F ( C π ) \mathcal{F}(\mathcal{C}_{\pi}) F ( C π ) .
Over 99% of chemical compounds C \mathrm{C} C with up to 100 non-hydrogen atoms in PubChem have degree at most 4 in the hydrogen-suppressed graph ⟨ C ⟩ \langle\mathrm{C}\rangle ⟨ C ⟩ [24 ] . We assume that a chemical graph C \mathrm{C} C treated in this paper satisfies deg ⟨ C ⟩ ( v ) ≤ 4 \deg_{\langle\mathrm{C}\rangle}(v) \le4 deg ⟨ C ⟩ ( v ) ≤ 4 in the hydrogen-suppressed graph ⟨ C ⟩ \langle\mathrm{C}\rangle ⟨ C ⟩ .
In our model, we use an integer mass ∗ ( a ) = ⌊ 10 ⋅ mass ( a ) ⌋ \operatorname{mass}^{*}(a) = \lfloor10 \cdot\operatorname{mass}(a) \rfloor mass ∗ ( a ) = ⌊ 10 ⋅ mass ( a )⌋ , for each a ∈ Λ a \in\Lambda a ∈ Λ .
For a chemical property π \pi π , we define a set D π ( 1 ) D_{\pi}^{(1)} D π ( 1 ) of descriptors of a chemical graph C = ( H , α , β ) ∈ C π \mathrm{C} = (H, \alpha, \beta) \in\mathcal{C}_{\pi} C = ( H , α , β ) ∈ C π to be the following non-negative integers dcp i ( C ) \operatorname{dcp}_{i}(\mathrm{C}) dcp i ( C ) , i ∈ [ 1 , K 1 ] i \in[1, K_{1}] i ∈ [ 1 , K 1 ] , where K 1 = 14 + ∣ Λ i n t ( C π ) ∣ + ∣ Λ e x ( C π ) ∣ + ∣ Γ i n t ( C π ) ∣ + ∣ F ( C π ) ∣ + ∣ Γ a c l f ∣ K_{1} = 14 + |\Lambda^{\mathrm{int}}(\mathcal{C}_{\pi})| + |\Lambda^{\mathrm{ex}}(\mathcal{C}_{\pi})| + |\Gamma^{\mathrm{int}}(\mathcal{C}_{\pi})| + |\mathcal{F}(\mathcal{C}_{\pi})| + |\Gamma_{\mathrm{ac}}^{\mathrm{lf}}| K 1 = 14 + ∣ Λ int ( C π ) ∣ + ∣ Λ ex ( C π ) ∣ + ∣ Γ int ( C π ) ∣ + ∣ F ( C π ) ∣ + ∣ Γ ac lf ∣ .
dcp 1 ( C ) \operatorname{dcp}_{1}(\mathrm{C}) dcp 1 ( C ) : the number ∣ V ( H ) ∣ − ∣ V H ∣ |V(H)| - |V_{\mathrm{H}}| ∣ V ( H ) ∣ − ∣ V H ∣ of non-hydrogen atoms in C \mathrm{C} C .
dcp 2 ( C ) \operatorname{dcp}_{2}(\mathrm{C}) dcp 2 ( C ) : the rank of C \mathrm{C} C (i.e., the minimum number of edges to be removed to make the graph acyclic).
dcp 3 ( C ) \operatorname{dcp}_{3}(\mathrm{C}) dcp 3 ( C ) : the number ∣ V i n t ( C ) ∣ |V^{\mathrm{int}}(\mathrm{C})| ∣ V int ( C ) ∣ of interior-vertices in C \mathrm{C} C .
dcp 4 ( C ) \operatorname{dcp}_{4}(\mathrm{C}) dcp 4 ( C ) : the average m s ‾ ( C ) \overline{\mathrm{ms}}(\mathrm{C}) ms ( C ) of mass ∗ \operatorname{mass}^{*} mass ∗ over all atoms in C \mathrm{C} C ; i.e., m s ‾ ( C ) ≜ 1 ∣ V ( H ) ∣ ∑ v ∈ V ( H ) mass ∗ ( α ( v ) ) \overline{\mathrm{ms}}(\mathrm{C}) \triangleq\frac{1}{|V(H)|} \sum_{v \in V(H)} \operatorname{mass}^{*}(\alpha(v)) ms ( C ) ≜ ∣ V ( H ) ∣ 1 ∑ v ∈ V ( H ) mass ∗ ( α ( v )) .
dcp i ( C ) \operatorname{dcp}_{i}(\mathrm{C}) dcp i ( C ) , i = 4 + d i = 4 + d i = 4 + d , d ∈ [ 1 , 4 ] d \in[1, 4] d ∈ [ 1 , 4 ] : the number dg d H ‾ ( C ) \operatorname{dg}^{\overline{\mathrm{H}}}_{d}(\mathrm{C}) dg d H ( C ) of non-hydrogen vertices v ∈ V ( H ) ∖ V H v \in V(H) \setminus V_{\mathrm{H}} v ∈ V ( H ) ∖ V H of degree deg ⟨ C ⟩ ( v ) = d \deg_{\langle\mathrm{C}\rangle}(v) = d deg ⟨ C ⟩ ( v ) = d in the hydrogen-suppressed chemical graph ⟨ C ⟩ \langle\mathrm{C}\rangle ⟨ C ⟩ .
dcp i ( C ) \operatorname{dcp}_{i}(\mathrm{C}) dcp i ( C ) , i = 8 + d i = 8 + d i = 8 + d , d ∈ [ 1 , 4 ] d \in[1, 4] d ∈ [ 1 , 4 ] : the number dg d i n t ( C ) \operatorname{dg}^{\mathrm{int}}_{d}(\mathrm{C}) dg d int ( C ) of interior-vertices of interior-degree deg C i n t ( v ) = d \deg_{\mathrm{C}^{\mathrm{int}}}(v) = d deg C int ( v ) = d in the interior C i n t = ( V i n t ( C ) , E i n t ( C ) ) \mathrm{C}^{\mathrm{int}} = (V^{\mathrm{int}}(\mathrm{C}), E^{\mathrm{int}}(\mathrm{C})) C int = ( V int ( C ) , E int ( C )) of C \mathrm{C} C .
dcp i ( C ) \operatorname{dcp}_{i}(\mathrm{C}) dcp i ( C ) , i = 12 + m i = 12 + m i = 12 + m , m ∈ [ 2 , 3 ] m \in[2, 3] m ∈ [ 2 , 3 ] : the number bd m i n t ( C ) \operatorname{bd}^{\mathrm{int}}_{m}(\mathrm{C}) bd m int ( C ) of interior-edges with bond multiplicity m m m in C \mathrm{C} C ; i.e., bd m i n t ( C ) ≜ ∣ { e ∈ E i n t ( C ) ∣ β ( e ) = m } ∣ \operatorname{bd}^{\mathrm{int}}_{m}(\mathrm{C}) \triangleq|\{e \in E^{\mathrm{int}}(\mathrm{C}) \mid\beta(e) = m\}| bd m int ( C ) ≜ ∣ { e ∈ E int ( C ) ∣ β ( e ) = m } ∣ .
dcp i ( C ) \operatorname{dcp}_{i}(\mathrm{C}) dcp i ( C ) , i = 14 + [ a ] i n t i = 14 + [a]^{\mathrm{int}} i = 14 + [ a ] int , a ∈ Λ i n t ( C π ) a \in\Lambda^{\mathrm{int}}(\mathcal{C}_{\pi}) a ∈ Λ int ( C π ) : the frequency na a i n t ( C ) = ∣ V a ( C ) ∩ V i n t ( C ) ∣ \operatorname{na}^{\mathrm{int}}_{a}(\mathrm{C}) = |V_{a}(\mathrm{C}) \cap V^{\mathrm{int}}(\mathrm{C})| na a int ( C ) = ∣ V a ( C ) ∩ V int ( C ) ∣ of chemical element a a a in the set V i n t ( C ) V^{\mathrm{int}}(\mathrm{C}) V int ( C ) of interior-vertices in C \mathrm{C} C .
dcp i ( C ) \operatorname{dcp}_{i}(\mathrm{C}) dcp i ( C ) , i = 14 + ∣ Λ i n t ( C π ) ∣ + [ a ] e x i = 14 + |\Lambda^{\mathrm{int}}(\mathcal{C}_{\pi})| + [a]^{\mathrm{ex}} i = 14 + ∣ Λ int ( C π ) ∣ + [ a ] ex , a ∈ Λ e x ( C π ) a \in\Lambda^{\mathrm{ex}}(\mathcal{C}_{\pi}) a ∈ Λ ex ( C π ) : the frequency na a e x ( C ) = ∣ V a ( C ) ∩ V e x ( C ) ∣ \operatorname{na}^{\mathrm{ex}}_{a}(\mathrm{C}) = |V_{a}(\mathrm{C}) \cap V^{\mathrm{ex}}(\mathrm{C})| na a ex ( C ) = ∣ V a ( C ) ∩ V ex ( C ) ∣ of chemical element a a a in the set V e x ( C ) V^{\mathrm{ex}}(\mathrm{C}) V ex ( C ) of exterior-vertices in C \mathrm{C} C .
dcp i ( C ) \operatorname{dcp}_{i}(\mathrm{C}) dcp i ( C ) , i = 14 + ∣ Λ i n t ( C π ) ∣ + ∣ Λ e x ( C π ) ∣ + [ γ ] i = 14 + |\Lambda^{\mathrm{int}}(\mathcal{C}_{\pi})| + |\Lambda^{\mathrm{ex}}(\mathcal{C}_{\pi})| + [\gamma] i = 14 + ∣ Λ int ( C π ) ∣ + ∣ Λ ex ( C π ) ∣ + [ γ ] , γ ∈ Γ i n t ( C π ) \gamma\in\Gamma^{\mathrm{int}}(\mathcal{C}_{\pi}) γ ∈ Γ int ( C π ) : the frequency ec γ ( C ) \operatorname{ec}_{\gamma}(\mathrm{C}) ec γ ( C ) of edge-configuration γ \gamma γ in the set E i n t ( C ) E^{\mathrm{int}}(\mathrm{C}) E int ( C ) of interior-edges in C \mathrm{C} C .
dcp i ( C ) \operatorname{dcp}_{i}(\mathrm{C}) dcp i ( C ) , i = 14 + ∣ Λ i n t ( C π ) ∣ + ∣ Λ e x ( C π ) ∣ + ∣ Γ i n t ( C π ) ∣ + [ ψ ] i = 14 + |\Lambda^{\mathrm{int}}(\mathcal{C}_{\pi})| + |\Lambda^{\mathrm{ex}}(\mathcal{C}_{\pi})| + |\Gamma^{\mathrm{int}}(\mathcal{C}_{\pi})| + [\psi] i = 14 + ∣ Λ int ( C π ) ∣ + ∣ Λ ex ( C π ) ∣ + ∣ Γ int ( C π ) ∣ + [ ψ ] , ψ ∈ F ( C π ) \psi\in\mathcal{F}(\mathcal{C}_{\pi}) ψ ∈ F ( C π ) : the frequency fc ψ ( C ) \operatorname{fc}_{\psi}(\mathrm{C}) fc ψ ( C ) of fringe-configuration ψ \psi ψ in the set of ρ \rho ρ -fringe-trees in C \mathrm{C} C .
dcp i ( C ) \operatorname{dcp}_{i}(\mathrm{C}) dcp i ( C ) , i = 14 + ∣ Λ i n t ( C π ) ∣ + ∣ Λ e x ( C π ) ∣ + ∣ Γ i n t ( C π ) ∣ + ∣ F ( C π ) ∣ + [ ν ] i = 14 + |\Lambda^{\mathrm{int}}(\mathcal{C}_{\pi})| + |\Lambda^{\mathrm{ex}}(\mathcal{C}_{\pi})| + |\Gamma^{\mathrm{int}}(\mathcal{C}_{\pi})| + |\mathcal{F}(\mathcal{C}_{\pi})| + [\nu] i = 14 + ∣ Λ int ( C π ) ∣ + ∣ Λ ex ( C π ) ∣ + ∣ Γ int ( C π ) ∣ + ∣ F ( C π ) ∣ + [ ν ] , ν ∈ Γ a c l f \nu\in\Gamma_{\mathrm{ac}}^{\mathrm{lf}} ν ∈ Γ ac lf : the frequency ac ν l f ( C ) \operatorname{ac}^{\mathrm{lf}}_{\nu}(\mathrm{C}) ac ν lf ( C ) of adjacency-configuration ν \nu ν in the set of leaf-edges in ⟨ C ⟩ \langle\mathrm{C}\rangle ⟨ C ⟩ .
In this paper, we also use a method of generating quadratic descriptors. For this, we first normalize each descriptor d c p i ( C ) \mathrm{dcp}_i(\mathrm{C}) dcp i ( C ) , i ∈ [ 1 , K 1 ] i \in[1,K_1] i ∈ [ 1 , K 1 ] to a value x ( i ) x(i) x ( i ) between 0 and 1 by scaling the minimum and maximum values to 0 and 1, respectively. Then construct a set D π ( 2 ) : = { x ( i ) x ( j ) ∣ 1 ≤ i ≤ j ≤ K 1 } ∪ { x ( i ) ( 1 − x ( j ) ) ∣ i , j ∈ [ 1 , K 1 ] } D_{\pi}^{(2)} := \{x(i)x(j) \mid1 \le i \le j \le K_1\} \cup\{x(i)(1-x(j)) \mid i,j \in[1,K_1]\} D π ( 2 ) := { x ( i ) x ( j ) ∣ 1 ≤ i ≤ j ≤ K 1 } ∪ { x ( i ) ( 1 − x ( j )) ∣ i , j ∈ [ 1 , K 1 ]} of ( 3 K 1 2 + K 1 ) / 2 (3K_1^2+K_1)/2 ( 3 K 1 2 + K 1 ) /2 quadratic descriptors. Then we reduce the union D π ( 1 ) ∪ D π ( 2 ) D_{\pi}^{(1)} \cup D_{\pi}^{(2)} D π ( 1 ) ∪ D π ( 2 ) to a subset to construct a prediction function by a procedure proposed by Zhu et al. [28 ] .
Specifying Target Chemical Graphs
Given a prediction function η \eta η and a target value y ∗ ∈ R y^* \in\mathbb{R} y ∗ ∈ R , we call a chemical graph C ∗ \mathrm{C}^* C ∗ such that η ( x ∗ ) = y ∗ \eta(x^*) = y^* η ( x ∗ ) = y ∗ for the feature vector x ∗ = f ( C ∗ ) x^* = f(\mathrm{C}^*) x ∗ = f ( C ∗ ) a target chemical graph . This section presents a set of rules for specifying topological substructure of a target chemical graph in a flexible way in the second phase of the framework.
We first describe how to reduce a chemical graph C = ( H , α , β ) \mathrm{C} = (H,\alpha,\beta) C = ( H , α , β ) into an abstract form based on which our specification rules will be defined. To illustrate the reduction process, we use the chemical graph C = ( H , α , β ) \mathrm{C} = (H,\alpha,\beta) C = ( H , α , β ) such that ⟨ C ⟩ \langle\mathrm{C} \rangle ⟨ C ⟩ is given in Figure 2 .
R1 Removal of all ρ \rho ρ -fringe-trees: The interior H i n t = ( V i n t ( C ) , E i n t ( C ) ) H^{\mathrm{int}} = (V^{\mathrm{int}}(\mathrm{C}), E^{\mathrm{int}}(\mathrm{C})) H int = ( V int ( C ) , E int ( C )) of C \mathrm{C} C is obtained by removing the non-root vertices of each ρ \rho ρ -fringe-trees C [ u ] ∈ T ( C ) \mathrm{C}[u] \in\mathcal{T}(\mathrm{C}) C [ u ] ∈ T ( C ) , u ∈ V i n t ( C ) u \in V^{\mathrm{int}}(\mathrm{C}) u ∈ V int ( C ) . Figure 8 illustrates the interior H i n t H^{\mathrm{int}} H int of chemical graph C \mathrm{C} C with ρ = 2 \rho= 2 ρ = 2 in Figure 2 .
Figure 8. The interior H i n t H^{\mathrm{int}} H int of chemical graph C \mathcal{C} C with ⟨ C ⟩ \langle\mathcal{C}\rangle ⟨ C ⟩ in Figure 2 for ρ = 2 \rho= 2 ρ = 2 .
R2 Removal of some leaf paths: We call a u , v u,v u , v -path Q Q Q in H i n t H^{\mathrm{int}} H int a leaf path if vertex v v v is a leaf-vertex of H i n t H^{\mathrm{int}} H int and the degree of each internal vertex of Q Q Q in H i n t H^{\mathrm{int}} H int is 2, where we regard that Q Q Q is rooted at vertex u u u . A connected subgraph S S S of the interior H i n t H^{\mathrm{int}} H int of C \mathrm{C} C is called a cyclical-base if S S S is obtained from H H H by removing the vertices in V ( Q u ) ∖ { u } V(Q_u) \setminus\{u\} V ( Q u ) ∖ { u } , u ∈ X u \in X u ∈ X for a subset X X X of interior-vertices and a set { Q u ∣ u ∈ X } \{Q_u \mid u \in X\} { Q u ∣ u ∈ X } of leaf u , v u,v u , v -paths Q u Q_u Q u such that no two paths Q u Q_u Q u and Q u ′ Q_{u'} Q u ′ share a vertex. Figure 9 (a) illustrates a cyclical-base S = H i n t − ⋃ u ∈ X ( V ( Q u ) ∖ { u } ) S = H^{\mathrm{int}} - \bigcup_{u \in X}(V(Q_u) \setminus\{u\}) S = H int − ⋃ u ∈ X ( V ( Q u ) ∖ { u }) of the interior H i n t H^{\mathrm{int}} H int for a set { Q u 5 = ( u 5 , u 24 ) , Q u 18 = ( u 18 , u 25 , u 26 , u 27 ) , Q u 22 = ( u 22 , u 28 ) } \{Q_{u_5} = (u_5,u_{24}), Q_{u_{18}} = (u_{18},u_{25},u_{26},u_{27}), Q_{u_{22}} = (u_{22},u_{28})\} { Q u 5 = ( u 5 , u 24 ) , Q u 18 = ( u 18 , u 25 , u 26 , u 27 ) , Q u 22 = ( u 22 , u 28 )} of leaf paths in Figure 8 .
Figure 9. (a) A cyclical-base S = H i n t − ⋃ u ∈ { u 5 , u 18 , u 22 } ( V ( Q u ) ∖ { u } ) S = H^{\mathrm{int}} - \bigcup_{u\in\{u_5,u_{18},u_{22}\}}(V(Q_u)\setminus\{u\}) S = H int − ⋃ u ∈ { u 5 , u 18 , u 22 } ( V ( Q u ) ∖ { u }) of the interior H i n t H^{\mathrm{int}} H int in Figure 8 ; (b) A contraction S ′ S' S ′ of S S S for a pure path set P = { P a 1 , P a 2 , … , P a 5 } P = \{P_{a_1},P_{a_2},\ldots,P_{a_5}\} P = { P a 1 , P a 2 , … , P a 5 } in (a), where a new edge obtained by contracting a pure path is depicted with a thick line.
R3 Contraction of some pure paths: A path in S S S is called pure if each internal vertex of the path is of degree 2. Choose a set P P P of several pure paths in S S S so that no two paths share vertices except for their end-vertices. A graph S ′ S' S ′ is called a contraction of a graph S S S (with respect to P P P ) if S ′ S' S ′ is obtained from S S S by replacing each pure u , v u,v u , v -path with a single edge a = u v a = uv a = uv , where S ′ S' S ′ may contain multiple edges between the same pair of adjacent vertices. Figure 9 (b) illustrates a contraction S ′ S' S ′ obtained from the chemical graph S S S by contracting each u v uv uv -path P a ∈ P P_a \in P P a ∈ P into a new edge a = u v a = uv a = uv , where a 1 = u 1 u 2 a_1 = u_1u_2 a 1 = u 1 u 2 , a 2 = u 1 u 3 a_2 = u_1u_3 a 2 = u 1 u 3 , a 3 = u 4 u 7 a_3 = u_4u_7 a 3 = u 4 u 7 , a 4 = u 10 u 11 a_4 = u_{10}u_{11} a 4 = u 10 u 11 and a 5 = u 11 u 12 a_5 = u_{11}u_{12} a 5 = u 11 u 12 and P = { P a 1 = ( u 1 , u 13 , u 2 ) , P a 2 = ( u 1 , u 14 , u 3 ) , P a 3 = ( u 4 , u 15 , u 16 , u 7 ) , P a 4 = ( u 10 , u 17 , u 18 , u 19 , u 11 ) , P a 5 = ( u 11 , u 20 , u 21 , u 22 , u 12 ) } P = \{P_{a_1} = (u_1,u_{13},u_2), P_{a_2} = (u_1,u_{14},u_3), P_{a_3} = (u_4,u_{15},u_{16},u_7), P_{a_4} = (u_{10},u_{17},u_{18},u_{19},u_{11}), P_{a_5} = (u_{11},u_{20},u_{21},u_{22},u_{12})\} P = { P a 1 = ( u 1 , u 13 , u 2 ) , P a 2 = ( u 1 , u 14 , u 3 ) , P a 3 = ( u 4 , u 15 , u 16 , u 7 ) , P a 4 = ( u 10 , u 17 , u 18 , u 19 , u 11 ) , P a 5 = ( u 11 , u 20 , u 21 , u 22 , u 12 )} of pure paths in Figure 9 (a).
We will define a set of rules so that a chemical graph can be obtained from a graph (called a seed graph in the next section) by applying processes R3 to R1 in a reverse way. We specify topological substructures of a target chemical graph with a tuple ( G C , σ i n t , σ c e ) (G_C,\sigma_{\mathrm{int}},\sigma_{\mathrm{ce}}) ( G C , σ int , σ ce ) called a target specification defined under the set of the following rules.
Seed Graph
A seed graph G C = ( V C , E C ) G_C=(V_C,E_C) G C = ( V C , E C ) is defined to be a graph (possibly with multiple edges) such that the edge set E C E_C E C consists of four sets E ( ≥ 2 ) E_{(\ge2)} E ( ≥ 2 ) , E ( ≥ 1 ) E_{(\ge1)} E ( ≥ 1 ) , E ( 0 / 1 ) E_{(0/1)} E ( 0/1 ) and E ( = 1 ) E_{(=1)} E ( = 1 ) , where each of them can be empty.
A seed graph plays a role of the most abstract form S ′ S' S ′ in R3. Figure 4 (a) illustrates an example of a seed graph G C G_C G C , where V C = { u 1 , u 2 , … , u 12 , u 23 } V_C=\{u_1,u_2,\ldots,u_{12},u_{23}\} V C = { u 1 , u 2 , … , u 12 , u 23 } , E ( ≥ 2 ) = { a 1 , a 2 , … , a 5 } E_{(\ge2)}=\{a_1,a_2,\ldots,a_5\} E ( ≥ 2 ) = { a 1 , a 2 , … , a 5 } , E ( ≥ 1 ) = { a 6 } E_{(\ge1)}=\{a_6\} E ( ≥ 1 ) = { a 6 } , E ( 0 / 1 ) = { a 7 } E_{(0/1)}=\{a_7\} E ( 0/1 ) = { a 7 } and E ( = 1 ) = { a 8 , a 9 , … , a 16 } E_{(=1)}=\{a_8,a_9,\ldots,a_{16}\} E ( = 1 ) = { a 8 , a 9 , … , a 16 } .
A subdivision S S S of G C G_C G C is a graph constructed from a seed graph G C G_C G C according to the following rules:
Each edge e = u w ∈ E ≥ 2 e=uw \in E_{\geq2} e = u w ∈ E ≥ 2 is replaced with a u , w u,w u , w -path P e P_e P e of length at least 2;
Each edge e = u w ∈ E ≥ 1 e=uw \in E_{\geq1} e = u w ∈ E ≥ 1 is replaced with a u , w u,w u , w -path P e P_e P e of length at least 1 (equivalently e e e is directly used or replaced with a u , w u,w u , w -path P e P_e P e of length at least 2);
We allow a possible elimination of edges in E ( 0 / 1 ) E_{(0/1)} E ( 0/1 ) as an optional rule in constructing a target chemical graph from a seed graph, even though such an operation has not been included in the process R3. A subdivision S S S plays a role of a cyclical-base in R2. A target chemical graph C = ( H , α , β ) (H,\alpha,\beta) ( H , α , β ) will contain S S S as a subgraph of the interior H i n t H^{\mathrm{int}} H int of C.
Interior-specification
A graph H ∗ H^* H ∗ that serves as the interior H i n t H^{\mathrm{int}} H int of a target chemical graph C will be constructed as follows. First construct a subdivision S S S of a seed graph G C G_C G C by replacing each edge e = u u ′ e=uu' e = u u ′ ∈ E ≥ 2 ∪ E ≥ 1 \in E_{\geq2} \cup E_{\geq1} ∈ E ≥ 2 ∪ E ≥ 1 with a pure u , u ′ u,u' u , u ′ -path P e P_e P e . Next construct a supergraph H ∗ H^* H ∗ of S S S by attaching a leaf path Q v Q_v Q v at each vertex v ∈ V C v \in V_C v ∈ V C or at an internal vertex v ∈ V ( P e ) ∖ { u , u ′ } v \in V(P_e) \setminus\{u,u'\} v ∈ V ( P e ) ∖ { u , u ′ } of each pure u , u ′ u,u' u , u ′ -path P e P_e P e for some edge e = u u ′ ∈ E ≥ 2 ∪ E ≥ 1 e=uu' \in E_{\geq2} \cup E_{\geq1} e = u u ′ ∈ E ≥ 2 ∪ E ≥ 1 , where possibly Q v = ( v ) Q_v=(v) Q v = ( v ) , E ( Q v ) = ∅ E(Q_v)=\varnothing E ( Q v ) = ∅ (i.e., we do not attach any new edges to v v v ). We introduce the following rules for specifying the size of H ∗ H^* H ∗ , the length ∣ E ( P e ) ∣ |E(P_e)| ∣ E ( P e ) ∣ of a pure path P e P_e P e , the length ∣ E ( Q v ) ∣ |E(Q_v)| ∣ E ( Q v ) ∣ of a leaf path Q v Q_v Q v , the number of leaf paths Q v Q_v Q v and a bond-multiplicity of each interior-edge, where we call the set of prescribed constants an interior-specification σ i n t \sigma_{\mathrm{int}} σ int :
Lower and upper bounds n L B i n t , n U B i n t ∈ Z + n^{\mathrm{int}}_{\mathrm{LB}}, n^{\mathrm{int}}_{\mathrm{UB}} \in\mathbb{Z}_+ n LB int , n UB int ∈ Z + on the number of interior-vertices of a target chemical graph C.
For each edge e = u u ′ ∈ E ≥ 2 ∪ E ≥ 1 e=uu' \in E_{\geq2} \cup E_{\geq1} e = u u ′ ∈ E ≥ 2 ∪ E ≥ 1 ,
a lower bound ℓ L B ( e ) \ell_{\mathrm{LB}}(e) ℓ LB ( e ) and an upper bound ℓ U B ( e ) \ell_{\mathrm{UB}}(e) ℓ UB ( e ) on the length ∣ E ( P e ) ∣ |E(P_e)| ∣ E ( P e ) ∣ of a pure u , u ′ u,u' u , u ′ -path P e P_e P e . (For a notational convenience, set ℓ L B ( e ) : = 0 \ell_{\mathrm{LB}}(e):=0 ℓ LB ( e ) := 0 , ℓ U B ( e ) : = 1 \ell_{\mathrm{UB}}(e):=1 ℓ UB ( e ) := 1 , e ∈ E ( 0 / 1 ) e \in E_{(0/1)} e ∈ E ( 0/1 ) and ℓ L B ( e ) : = 1 \ell_{\mathrm{LB}}(e):=1 ℓ LB ( e ) := 1 , ℓ U B ( e ) : = 1 \ell_{\mathrm{UB}}(e):=1 ℓ UB ( e ) := 1 , e ∈ E ( = 1 ) e \in E_{(=1)} e ∈ E ( = 1 ) .)
a lower bound b l L B ( e ) \mathrm{bl}_{\mathrm{LB}}(e) bl LB ( e ) and an upper bound b l U B ( e ) \mathrm{bl}_{\mathrm{UB}}(e) bl UB ( e ) on the number of leaf paths Q v Q_v Q v attached at internal vertices v v v of a pure u , u ′ u,u' u , u ′ -path P e P_e P e .
a lower bound c h L B ( e ) \mathrm{ch}_{\mathrm{LB}}(e) ch LB ( e ) and an upper bound c h U B ( e ) \mathrm{ch}_{\mathrm{UB}}(e) ch UB ( e ) on the maximum length ∣ E ( Q v ) ∣ |E(Q_v)| ∣ E ( Q v ) ∣ of a leaf path Q v Q_v Q v attached at an internal vertex v ∈ V ( P e ) ∖ { u , u ′ } v \in V(P_e) \setminus\{u,u'\} v ∈ V ( P e ) ∖ { u , u ′ } of a pure u , u ′ u,u' u , u ′ -path P e P_e P e .
For each vertex v ∈ V C v \in V_C v ∈ V C ,
a lower bound b l L B ( v ) \mathrm{bl}_{\mathrm{LB}}(v) bl LB ( v ) and an upper bound b l U B ( v ) \mathrm{bl}_{\mathrm{UB}}(v) bl UB ( v ) on the number of leaf paths Q v Q_v Q v attached to v v v , where 0 ≤ b l L B ( v ) ≤ b l U B ( v ) ≤ 1 0 \leq\mathrm{bl}_{\mathrm{LB}}(v) \leq\mathrm{bl}_{\mathrm{UB}}(v) \leq1 0 ≤ bl LB ( v ) ≤ bl UB ( v ) ≤ 1 .
a lower bound c h L B ( v ) \mathrm{ch}_{\mathrm{LB}}(v) ch LB ( v ) and an upper bound c h U B ( v ) \mathrm{ch}_{\mathrm{UB}}(v) ch UB ( v ) on the length ∣ E ( Q v ) ∣ |E(Q_v)| ∣ E ( Q v ) ∣ of a leaf path Q v Q_v Q v attached to v v v .
For each edge e = u u ′ ∈ E C e = uu' \in E_C e = u u ′ ∈ E C , a lower bound b d m , L B ( e ) \mathrm{bd}_{m,\mathrm{LB}}(e) bd m , LB ( e ) and an upper bound b d m , U B ( e ) \mathrm{bd}_{m,\mathrm{UB}}(e) bd m , UB ( e ) on the number of edges with bond-multiplicity m ∈ [ 2 , 3 ] m \in[2,3] m ∈ [ 2 , 3 ] in u , u ′ u,u' u , u ′ -path P e P_e P e , where we regard P e P_e P e , e ∈ E ( 0 / 1 ) ∪ E ( = 1 ) e \in E_{(0/1)} \cup E_{(=1)} e ∈ E ( 0/1 ) ∪ E ( = 1 ) as single edge e e e .
We call a graph H ∗ H^* H ∗ that satisfies an interior-specification σ i n t \sigma_{\mathrm{int}} σ int a σ i n t \sigma_{\mathrm{int}} σ int -extension of G C G_C G C , where the bond-multiplicity of each edge has been determined. Table 6 shows an example of an interior-specification σ i n t \sigma_{\mathrm{int}} σ int to the seed graph G C G_C G C in Figure 4 .
Table 6. Example 1 of an interior-specification σ i n t \sigma_{\mathrm{int}} σ int .
Figure 10 illustrates an example of an σ i n t \sigma_{\mathrm{int}} σ int -extension H ∗ H^* H ∗ of seed graph G C G_C G C in Figure 4 under the interior-specification σ i n t \sigma_{\mathrm{int}} σ int in Table 6 .
Figure 10. An illustration of a graph H ∗ H^* H ∗ that is obtained from the seed graph G C G_{\mathrm C} G C in Figure 4 under the interior-specification σ i n t \sigma_{\mathrm{int}} σ int in Table 6 .
Chemical-specification
Let H ∗ H^* H ∗ be a graph that serves as the interior H i n t H^{\mathrm{int}} H int of a target chemical graph C C C , where the bond-multiplicity of each edge in H ∗ H^* H ∗ has been determined. Finally we introduce a set of rules for constructing a target chemical graph C C C from H ∗ H^* H ∗ by choosing a chemical element a ∈ Λ a \in\Lambda a ∈ Λ and assigning a ρ \rho ρ -fringe-tree ψ \psi ψ to each interior-vertex v ∈ V i n t v \in V^{\mathrm{int}} v ∈ V int . We introduce the following rules for specifying the size of C C C , a set of chemical rooted trees that are allowed to use as ρ \rho ρ -fringe-trees and lower and upper bounds on the frequency of a chemical element, a chemical symbol, and an edge-configuration, where we call the set of prescribed constants a chemical specification σ c e \sigma_{\mathrm{ce}} σ ce :
Lower and upper bounds n L B , n ∗ ∈ Z + n_{\mathrm{LB}}, n^* \in\mathbb{Z}_+ n LB , n ∗ ∈ Z + on the number of vertices, where n L B i n t ≤ n L B ≤ n ∗ n^{\mathrm{int}}_{\mathrm{LB}} \le n_{\mathrm{LB}} \le n^* n LB int ≤ n LB ≤ n ∗ .
Subsets F ( v ) ⊆ F ( D π ) \mathcal{F}(v) \subseteq\mathcal{F}(D_\pi) F ( v ) ⊆ F ( D π ) , v ∈ V C v \in V_{\mathrm C} v ∈ V C and F E ⊆ F ( D π ) \mathcal{F}_{\mathrm E} \subseteq\mathcal{F}(D_\pi) F E ⊆ F ( D π ) of chemical rooted trees ψ \psi ψ with ht ( ⟨ ψ ⟩ ) ≤ ρ \operatorname{ht}(\langle\psi\rangle) \le\rho ht (⟨ ψ ⟩) ≤ ρ , where we require that every ρ \rho ρ -fringe-tree C [ v ] \mathcal{C}[v] C [ v ] rooted at a vertex v ∈ V C v \in V_{\mathrm C} v ∈ V C (resp., at an internal vertex v v v not in V C V_{\mathrm C} V C ) in C \mathcal{C} C belongs to F ( v ) \mathcal{F}(v) F ( v ) (resp., F E \mathcal{F}_{\mathrm E} F E ). Let F ∗ : = F E ∪ ⋃ v ∈ V C F ( v ) \mathcal{F}^* := \mathcal{F}_{\mathrm E} \cup\bigcup_{v \in V_{\mathrm C}}\mathcal{F}(v) F ∗ := F E ∪ ⋃ v ∈ V C F ( v ) and Λ e x \Lambda^{\mathrm{ex}} Λ ex denote the set of chemical elements assigned to non-root vertices over all chemical rooted trees in F ∗ \mathcal{F}^* F ∗ .
A subset Λ i n t ⊆ Λ i n t ( D π ) \Lambda^{\mathrm{int}} \subseteq\Lambda^{\mathrm{int}}(D_\pi) Λ int ⊆ Λ int ( D π ) , where we require that every chemical element α ( v ) \alpha(v) α ( v ) assigned to an interior-vertex v v v in C \mathcal{C} C belongs to Λ i n t \Lambda^{\mathrm{int}} Λ int . Let Λ : = Λ i n t ∪ Λ e x \Lambda:= \Lambda^{\mathrm{int}} \cup\Lambda^{\mathrm{ex}} Λ := Λ int ∪ Λ ex and na a ( C ) \operatorname{na}_a(\mathcal{C}) na a ( C ) (resp., na a i n t ( C ) \operatorname{na}^{\mathrm{int}}_a(\mathcal{C}) na a int ( C ) and na a e x ( C ) \operatorname{na}^{\mathrm{ex}}_a(\mathcal{C}) na a ex ( C ) ) denote the number of vertices (resp., interior-vertices and exterior-vertices) v v v such that α ( v ) = a \alpha(v) = a α ( v ) = a in C \mathcal{C} C .
A set Λ d g i n t ⊆ Λ × [ 1 , 4 ] \Lambda^{\mathrm{int}}_{\mathrm{dg}} \subseteq\Lambda\times[1,4] Λ dg int ⊆ Λ × [ 1 , 4 ] of chemical symbols and a set Γ i n t ⊆ Γ i n t ( D π ) \Gamma^{\mathrm{int}} \subseteq\Gamma^{\mathrm{int}}(D_\pi) Γ int ⊆ Γ int ( D π ) of edge-configurations ( μ , μ ′ , m ) (\mu,\mu',m) ( μ , μ ′ , m ) with μ ≤ μ ′ \mu\le\mu' μ ≤ μ ′ , where we require that the edge-configuration ec ( e ) \operatorname{ec}(e) ec ( e ) of an interior-edge e e e in C \mathcal{C} C belongs to Γ i n t \Gamma^{\mathrm{int}} Γ int . We do not distinguish ( μ , μ ′ , m ) (\mu,\mu',m) ( μ , μ ′ , m ) and ( μ ′ , μ , m ) (\mu',\mu,m) ( μ ′ , μ , m ) .
Define Γ a c i n t \Gamma^{\mathrm{int}}_{\mathrm{ac}} Γ ac int to be the set of adjacency-configurations such that Γ a c i n t : = { ( a , b , m ) ∣ ( a d , b d ′ , m ) ∈ Γ i n t } \Gamma^{\mathrm{int}}_{\mathrm{ac}} := \{(a,b,m) \mid(a d,b d',m) \in\Gamma^{\mathrm{int}}\} Γ ac int := {( a , b , m ) ∣ ( a d , b d ′ , m ) ∈ Γ int } . Let ac ν i n t ( C ) \operatorname{ac}^{\mathrm{int}}_\nu(\mathcal{C}) ac ν int ( C ) , ν ∈ Γ a c i n t \nu\in\Gamma^{\mathrm{int}}_{\mathrm{ac}} ν ∈ Γ ac int denote the number of interior-edges e e e such that ac ( e ) = ν \operatorname{ac}(e) = \nu ac ( e ) = ν in C \mathcal{C} C .
Subsets Λ ∗ ( v ) ⊆ { a ∈ Λ i n t ∣ val ( a ) ≥ 2 } \Lambda^*(v) \subseteq\{a \in\Lambda^{\mathrm{int}} \mid\operatorname{val}(a) \ge2\} Λ ∗ ( v ) ⊆ { a ∈ Λ int ∣ val ( a ) ≥ 2 } , v ∈ V C v \in V_{\mathrm C} v ∈ V C , we require that every chemical element α ( v ) \alpha(v) α ( v ) assigned to a vertex v ∈ V C v \in V_{\mathrm C} v ∈ V C in the seed graph belongs to Λ ∗ ( v ) \Lambda^*(v) Λ ∗ ( v ) .
Lower and upper bound functions na L B , na U B : Λ → [ 1 , n ∗ ] \operatorname{na}_{\mathrm{LB}}, \operatorname{na}_{\mathrm{UB}} : \Lambda\to[1,n^*] na LB , na UB : Λ → [ 1 , n ∗ ] and na L B i n t , na U B i n t : Λ i n t → [ 1 , n ∗ ] \operatorname{na}^{\mathrm{int}}_{\mathrm{LB}}, \operatorname{na}^{\mathrm{int}}_{\mathrm{UB}} : \Lambda^{\mathrm{int}} \to[1,n^*] na LB int , na UB int : Λ int → [ 1 , n ∗ ] on the number of interior-vertices v v v such that α ( v ) = a \alpha(v) = a α ( v ) = a in C \mathcal{C} C .
Lower and upper bound functions ns L B i n t , ns U B i n t : Λ d g i n t → [ 1 , n ∗ ] \operatorname{ns}^{\mathrm{int}}_{\mathrm{LB}}, \operatorname{ns}^{\mathrm{int}}_{\mathrm{UB}} : \Lambda^{\mathrm{int}}_{\mathrm{dg}} \to[1,n^*] ns LB int , ns UB int : Λ dg int → [ 1 , n ∗ ] on the number of interior-vertices v v v such that cs ( v ) = μ \operatorname{cs}(v) = \mu cs ( v ) = μ in C \mathcal{C} C .
Lower and upper bound functions ac L B i n t , ac U B i n t : Γ a c i n t → Z + \operatorname{ac}^{\mathrm{int}}_{\mathrm{LB}}, \operatorname{ac}^{\mathrm{int}}_{\mathrm{UB}} : \Gamma^{\mathrm{int}}_{\mathrm{ac}} \to\mathbb{Z}_+ ac LB int , ac UB int : Γ ac int → Z + on the number of interior-edges e e e such that ac ( e ) = ν \operatorname{ac}(e) = \nu ac ( e ) = ν in C \mathcal{C} C .
Lower and upper bound functions e c L B i n t , e c U B i n t : Γ i n t → Z + \mathrm{ec}^{\mathrm{int}}_{\mathrm{LB}}, \mathrm{ec}^{\mathrm{int}}_{\mathrm{UB}} : \Gamma^{\mathrm{int}} \to\mathbb{Z}_{+} ec LB int , ec UB int : Γ int → Z + on the number of interior-edges e e e such that e c ( e ) = γ \mathrm{ec}(e) = \gamma ec ( e ) = γ in C \mathrm{C} C .
Lower and upper bound functions f c L B , f c U B : F ∗ → [ 0 , n ∗ ] \mathrm{fc}_{\mathrm{LB}}, \mathrm{fc}_{\mathrm{UB}} : \mathcal{F}^{*} \to[0,n^{*}] fc LB , fc UB : F ∗ → [ 0 , n ∗ ] on the number of interior-vertices v v v such that C [ v ] \mathrm{C}[v] C [ v ] is r-isomorphic to ψ ∈ F ∗ \psi\in\mathcal{F}^{*} ψ ∈ F ∗ in C \mathrm{C} C .
Lower and upper bound functions a c L B l f , a c U B l f : Γ a c l f → [ 0 , n ∗ ] \mathrm{ac}^{\mathrm{lf}}_{\mathrm{LB}}, \mathrm{ac}^{\mathrm{lf}}_{\mathrm{UB}} : \Gamma^{\mathrm{lf}}_{\mathrm{ac}} \to[0,n^{*}] ac LB lf , ac UB lf : Γ ac lf → [ 0 , n ∗ ] on the number of leaf-edges u v uv uv in a c C \mathrm{ac}_{\mathrm{C}} ac C with adjacency-configuration ν \nu ν .
We call a chemical graph C \mathrm{C} C that satisfies a chemical specification σ c e \sigma_{\mathrm{ce}} σ ce a ( σ i n t , σ c e ) (\sigma_{\mathrm{int}},\sigma_{\mathrm{ce}}) ( σ int , σ ce ) -extension of G C G_{\mathrm{C}} G C , and denote by G ( G C , σ i n t , σ c e ) \mathcal{G}(G_{\mathrm{C}},\sigma_{\mathrm{int}},\sigma_{\mathrm{ce}}) G ( G C , σ int , σ ce ) the set of all ( σ i n t , σ c e ) (\sigma_{\mathrm{int}},\sigma_{\mathrm{ce}}) ( σ int , σ ce ) -extensions of G C G_{\mathrm{C}} G C .
Table 7 shows an example of a chemical-specification σ c e \sigma_{\mathrm{ce}} σ ce to the seed graph G C G_{\mathrm{C}} G C in Figure 4 .
Figure 2 illustrates an example C \mathrm{C} C of a ( σ i n t , σ c e ) (\sigma_{\mathrm{int}},\sigma_{\mathrm{ce}}) ( σ int , σ ce ) -extension of G C G_{\mathrm{C}} G C obtained from the σ i n t \sigma_{\mathrm{int}} σ int -extension H ∗ H^{*} H ∗ in Figure 10 under the chemical-specification σ c e \sigma_{\mathrm{ce}} σ ce in Table 7.
Test Instances for Inferring Chemical Graphs
We prepared the following instances (a)-(d) for conducting experiments of the second phase of the framework.
In the second phase of inferring chemical graphs, we use two properties π ∈ { A t , F l m L } \pi\in\{\mathrm{At}, \mathrm{FlmL}\} π ∈ { At , FlmL } and define a set Λ ( π ) \Lambda(\pi) Λ ( π ) of chemical elements as follows: Λ ( A t ) = Λ 3 = { H , C , O , N , C l , S ( 2 ) , S ( 6 ) } \Lambda(\mathrm{At}) = \Lambda_{3} = \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}, \mathrm{Cl}, \mathrm{S}_{(2)}, \mathrm{S}_{(6)}\} Λ ( At ) = Λ 3 = { H , C , O , N , Cl , S ( 2 ) , S ( 6 ) } and Λ ( F l m L ) = Λ 6 = { H , C , O , N , C l , P ( 2 ) , P ( 5 ) } \Lambda(\mathrm{FlmL}) = \Lambda_{6} = \{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}, \mathrm{Cl}, \mathrm{P}_{(2)}, \mathrm{P}_{(5)}\} Λ ( FlmL ) = Λ 6 = { H , C , O , N , Cl , P ( 2 ) , P ( 5 ) } .
(a) I a = ( G C , σ i n t , σ c e ) I_{a} = (G_{\mathrm{C}},\sigma_{\mathrm{int}},\sigma_{\mathrm{ce}}) I a = ( G C , σ int , σ ce ) : The instance introduced in Section B to explain the target specification. For each property π \pi π , we replace Λ = { H , C , O , N , S ( 2 ) , S ( 6 ) , P ( 5 ) } \Lambda= \{\mathrm{H},\mathrm{C},\mathrm{O},\mathrm{N},\mathrm{S}_{(2)},\mathrm{S}_{(6)},\mathrm{P}_{(5)}\} Λ = { H , C , O , N , S ( 2 ) , S ( 6 ) , P ( 5 ) } in Table 7 with Λ ( π ) ∩ { H , C , O , N , S ( 2 ) , S ( 6 ) , P ( 5 ) } \Lambda(\pi) \cap\{\mathrm{H},\mathrm{C},\mathrm{O},\mathrm{N},\mathrm{S}_{(2)},\mathrm{S}_{(6)},\mathrm{P}_{(5)}\} Λ ( π ) ∩ { H , C , O , N , S ( 2 ) , S ( 6 ) , P ( 5 ) } and remove from the σ c e \sigma_{\mathrm{ce}} σ ce all chemical symbols, edge-configurations and fringe-configurations that cannot be constructed from the replaced element set (i.e., those containing a chemical element P ( 5 ) \mathrm{P}_{(5)} P ( 5 ) ).
(b) I b i = ( G C i , σ i n t i , σ c e i ) I_{b}^{i} = (G_{\mathrm{C}}^{i},\sigma_{\mathrm{int}}^{i},\sigma_{\mathrm{ce}}^{i}) I b i = ( G C i , σ int i , σ ce i ) , i = 1 , 2 , 3 , 4 i = 1,2,3,4 i = 1 , 2 , 3 , 4 : An instance for inferring chemical graphs with rank at most 2. In the four instances I b i I_{b}^{i} I b i , i = 1 , 2 , 3 , 4 i = 1,2,3,4 i = 1 , 2 , 3 , 4 , the following specifications in ( σ i n t , σ c e ) (\sigma_{\mathrm{int}},\sigma_{\mathrm{ce}}) ( σ int , σ ce ) are common.
Set Λ : = Λ ( π ) \Lambda:= \Lambda(\pi) Λ := Λ ( π ) for a given property π ∈ { A t , F l m L } \pi\in\{\mathrm{At},\mathrm{FlmL}\} π ∈ { At , FlmL } , set Λ d g i n t \Lambda_{\mathrm{dg}}^{\mathrm{int}} Λ dg int to be the set of all possible symbols in Λ × [ 1 , 4 ] \Lambda\times[1,4] Λ × [ 1 , 4 ] that appear in the data set C π \mathcal{C}_{\pi} C π and set Γ i n t \Gamma^{\mathrm{int}} Γ int to be the set of all edge-configurations that appear in the data set C π \mathcal{C}_{\pi} C π . Set Λ ∗ ( v ) : = Λ \Lambda^{*}(v) := \Lambda Λ ∗ ( v ) := Λ , v ∈ V C v \in V_{\mathrm{C}} v ∈ V C .
The lower bounds ℓ L B \ell_{\mathrm{LB}} ℓ LB , b l L B \mathrm{bl}_{\mathrm{LB}} bl LB , c h L B \mathrm{ch}_{\mathrm{LB}} ch LB , b d 2 , L B \mathrm{bd}_{2,\mathrm{LB}} bd 2 , LB , b d 3 , L B \mathrm{bd}_{3,\mathrm{LB}} bd 3 , LB , n a L B \mathrm{na}_{\mathrm{LB}} na LB , n a L B i n t \mathrm{na}^{\mathrm{int}}_{\mathrm{LB}} na LB int , n s L B i n t \mathrm{ns}^{\mathrm{int}}_{\mathrm{LB}} ns LB int , a c L B i n t \mathrm{ac}^{\mathrm{int}}_{\mathrm{LB}} ac LB int , e c L B i n t \mathrm{ec}^{\mathrm{int}}_{\mathrm{LB}} ec LB int and a c L B l f \mathrm{ac}^{\mathrm{lf}}_{\mathrm{LB}} ac LB lf are all set to be 0.
Set upper bounds n a U B ( a ) : = n ∗ \mathrm{na}_{\mathrm{UB}}(a) := n^{*} na UB ( a ) := n ∗ , n a ∈ { H , C } \mathrm{na} \in\{\mathrm{H},\mathrm{C}\} na ∈ { H , C } , n a U B ( a ) : = 5 \mathrm{na}_{\mathrm{UB}}(a) := 5 na UB ( a ) := 5 , n a ∈ { O , N } \mathrm{na} \in\{\mathrm{O},\mathrm{N}\} na ∈ { O , N } , n a U B ( a ) : = 2 \mathrm{na}_{\mathrm{UB}}(a) := 2 na UB ( a ) := 2 , n a ∈ Λ ∖ { H , C , O , N } \mathrm{na} \in\Lambda\setminus\{\mathrm{H},\mathrm{C},\mathrm{O},\mathrm{N}\} na ∈ Λ ∖ { H , C , O , N } . The other upper bounds ℓ U B \ell_{\mathrm{UB}} ℓ UB , b l U B \mathrm{bl}_{\mathrm{UB}} bl UB , c h U B \mathrm{ch}_{\mathrm{UB}} ch UB , b d 2 , U B \mathrm{bd}_{2,\mathrm{UB}} bd 2 , UB , b d 3 , U B \mathrm{bd}_{3,\mathrm{UB}} bd 3 , UB , n a U B i n t \mathrm{na}^{\mathrm{int}}_{\mathrm{UB}} na UB int , n s U B i n t \mathrm{ns}^{\mathrm{int}}_{\mathrm{UB}} ns UB int , a c U B i n t \mathrm{ac}^{\mathrm{int}}_{\mathrm{UB}} ac UB int , e c U B i n t \mathrm{ec}^{\mathrm{int}}_{\mathrm{UB}} ec UB int and a c U B l f \mathrm{ac}^{\mathrm{lf}}_{\mathrm{UB}} ac UB lf are all set to be an upper bound n ∗ n^{*} n ∗ on n ( G ∗ ) n(G^{*}) n ( G ∗ ) .
We specify n L B n_{\mathrm{LB}} n LB as a parameter and set n ∗ : = n L B + 10 n^{*} := n_{\mathrm{LB}} + 10 n ∗ := n LB + 10 , n L B i n t : = ⌊ ( 1 / 4 ) n L B ⌋ n_{\mathrm{LB}}^{\mathrm{int}} := \lfloor(1/4)n_{\mathrm{LB}} \rfloor n LB int := ⌊( 1/4 ) n LB ⌋ and n U B i n t : = ⌈ ( 3 / 4 ) n L B ⌉ n_{\mathrm{UB}}^{\mathrm{int}} := \lceil(3/4)n_{\mathrm{LB}} \rceil n UB int := ⌈( 3/4 ) n LB ⌉ .
Table 7. Example 2 of a chemical-specification σ c e \sigma_{\mathrm{ce}} σ ce .
Table 8.
Table 9.
Table 10.
Table 11.
Table 12.
Table 13.
Table 14.
For each property π \pi π , let F ( C π ) \mathcal{F}(\mathcal{C}_{\pi}) F ( C π ) denote the set of 2-fringe-trees in the compounds in C π \mathcal{C}_{\pi} C π , and select a subset F π i ⊆ F ( C π ) \mathcal{F}^{i}_{\pi}\subseteq\mathcal{F}(\mathcal{C}_{\pi}) F π i ⊆ F ( C π ) with ∣ F π i ∣ = 45 − 5 i |\mathcal{F}^{i}_{\pi}|=45-5i ∣ F π i ∣ = 45 − 5 i , i ∈ [ 1 , 5 ] i\in[1,5] i ∈ [ 1 , 5 ] . For each instance I b i I^{i}_{b} I b i , set F E : = F ( v ) : = F π i \mathcal{F}_{\mathrm{E}}:=\mathcal{F}(v):=\mathcal{F}^{i}_{\pi} F E := F ( v ) := F π i , v ∈ V C v\in V_{\mathrm{C}} v ∈ V C and f c L B ( ψ ) : = 0 fc_{\mathrm{LB}}(\psi):=0 f c LB ( ψ ) := 0 , f c U B ( ψ ) : = 10 fc_{\mathrm{UB}}(\psi):=10 f c UB ( ψ ) := 10 , ψ ∈ F π i \psi\in\mathcal{F}^{i}_{\pi} ψ ∈ F π i .
Instance I b 1 I^{1}_{b} I b 1 is given by the rank-1 seed graph G C 1 G^{1}_{\mathrm{C}} G C 1 in Figure 5 (i) and Instances I b i I^{i}_{b} I b i , i = 2 , 3 , 4 i=2,3,4 i = 2 , 3 , 4 are given by the rank-2 seed graph G C i G^{i}_{\mathrm{C}} G C i , i = 2 , 3 , 4 i=2,3,4 i = 2 , 3 , 4 in Figure 5 (ii)-(iv).
For instance I b 1 I^{1}_{b} I b 1 , select as a seed graph the monocyclic graph G C 1 = ( V C , E C = E ( ≥ 2 ) ∪ E ( ≥ 1 ) ) G^{1}_{\mathrm{C}}=(V_{\mathrm{C}},E_{\mathrm{C}}=E_{(\geq2)}\cup E_{(\geq1)}) G C 1 = ( V C , E C = E ( ≥ 2 ) ∪ E ( ≥ 1 ) ) in Figure 5 (i), where V C = { u 1 , u 2 } V_{\mathrm{C}}=\{u_1,u_2\} V C = { u 1 , u 2 } , E ( ≥ 2 ) = { a 1 } E_{(\geq2)}=\{a_1\} E ( ≥ 2 ) = { a 1 } and E ( ≥ 1 ) = { a 2 } E_{(\geq1)}=\{a_2\} E ( ≥ 1 ) = { a 2 } . We include a linear constraint ℓ ( a 1 ) ≤ ℓ ( a 2 ) \ell(a_1)\leq\ell(a_2) ℓ ( a 1 ) ≤ ℓ ( a 2 ) and 5 ≤ ℓ ( a 1 ) + ℓ ( a 2 ) ≤ 15 5\leq\ell(a_1)+\ell(a_2)\leq15 5 ≤ ℓ ( a 1 ) + ℓ ( a 2 ) ≤ 15 as part of the side constraint.
(ii) For instance I b 2 I_b^2 I b 2 , select as a seed graph the graph G C 2 = ( V C , E C = E ( ≥ 2 ) ∪ E ( ≥ 1 ) ∪ E ( = 1 ) ) G_C^2 = (V_C, E_C = E_{(\geq2)} \cup E_{(\geq1)} \cup E_{(=1)}) G C 2 = ( V C , E C = E ( ≥ 2 ) ∪ E ( ≥ 1 ) ∪ E ( = 1 ) ) in Figure 5 (ii), where V C = { u 1 , u 2 , u 3 , u 4 } V_C = \{u_1, u_2, u_3, u_4\} V C = { u 1 , u 2 , u 3 , u 4 } , E ( ≥ 2 ) = { a 1 , a 2 } E_{(\geq2)} = \{a_1, a_2\} E ( ≥ 2 ) = { a 1 , a 2 } , E ( ≥ 1 ) = { a 3 } E_{(\geq1)} = \{a_3\} E ( ≥ 1 ) = { a 3 } and E ( = 1 ) = { a 4 , a 5 } E_{(=1)} = \{a_4, a_5\} E ( = 1 ) = { a 4 , a 5 } . We include a linear constraint ℓ ( a 1 ) ≤ ℓ ( a 2 ) \ell(a_1) \leq\ell(a_2) ℓ ( a 1 ) ≤ ℓ ( a 2 ) and ℓ ( a 1 ) + ℓ ( a 2 ) + ℓ ( a 3 ) ≤ 15 \ell(a_1) + \ell(a_2) + \ell(a_3) \leq15 ℓ ( a 1 ) + ℓ ( a 2 ) + ℓ ( a 3 ) ≤ 15 .
(iii) For instance I b 3 I_b^3 I b 3 , select as a seed graph the graph G C 3 = ( V C , E C = E ( ≥ 2 ) ∪ E ( ≥ 1 ) ∪ E ( = 1 ) ) G_C^3 = (V_C, E_C = E_{(\geq2)} \cup E_{(\geq1)} \cup E_{(=1)}) G C 3 = ( V C , E C = E ( ≥ 2 ) ∪ E ( ≥ 1 ) ∪ E ( = 1 ) ) in Figure 5 (iii), where V C = { u 1 , u 2 , u 3 , u 4 } V_C = \{u_1, u_2, u_3, u_4\} V C = { u 1 , u 2 , u 3 , u 4 } , E ( ≥ 2 ) = { a 1 } E_{(\geq2)} = \{a_1\} E ( ≥ 2 ) = { a 1 } , E ( ≥ 1 ) = { a 2 , a 3 } E_{(\geq1)} = \{a_2, a_3\} E ( ≥ 1 ) = { a 2 , a 3 } and E ( = 1 ) = { a 4 , a 5 } E_{(=1)} = \{a_4, a_5\} E ( = 1 ) = { a 4 , a 5 } . We include linear constraints ℓ ( a 1 ) ≤ ℓ ( a 2 ) + ℓ ( a 3 ) \ell(a_1) \leq\ell(a_2) + \ell(a_3) ℓ ( a 1 ) ≤ ℓ ( a 2 ) + ℓ ( a 3 ) , ℓ ( a 2 ) ≤ ℓ ( a 3 ) \ell(a_2) \leq\ell(a_3) ℓ ( a 2 ) ≤ ℓ ( a 3 ) and ℓ ( a 1 ) + ℓ ( a 2 ) + ℓ ( a 3 ) ≤ 15 \ell(a_1) + \ell(a_2) + \ell(a_3) \leq15 ℓ ( a 1 ) + ℓ ( a 2 ) + ℓ ( a 3 ) ≤ 15 .
(iv) For instance I b 4 I_b^4 I b 4 , select as a seed graph the graph G C 4 = ( V C , E C = E ( ≥ 2 ) ∪ E ( ≥ 1 ) ∪ E ( = 1 ) ) G_C^4 = (V_C, E_C = E_{(\geq2)} \cup E_{(\geq1)} \cup E_{(=1)}) G C 4 = ( V C , E C = E ( ≥ 2 ) ∪ E ( ≥ 1 ) ∪ E ( = 1 ) ) in Figure 5 (iv), where V C = { u 1 , u 2 , u 3 , u 4 } V_C = \{u_1, u_2, u_3, u_4\} V C = { u 1 , u 2 , u 3 , u 4 } , E ( ≥ 1 ) = { a 1 , a 2 , a 3 } E_{(\geq1)} = \{a_1, a_2, a_3\} E ( ≥ 1 ) = { a 1 , a 2 , a 3 } and E ( = 1 ) = { a 4 , a 5 } E_{(=1)} = \{a_4, a_5\} E ( = 1 ) = { a 4 , a 5 } . We include linear constraints ℓ ( a 2 ) ≤ ℓ ( a 1 ) + 1 \ell(a_2) \leq\ell(a_1) + 1 ℓ ( a 2 ) ≤ ℓ ( a 1 ) + 1 , ℓ ( a 2 ) ≤ ℓ ( a 3 ) + 1 \ell(a_2) \leq\ell(a_3) + 1 ℓ ( a 2 ) ≤ ℓ ( a 3 ) + 1 , ℓ ( a 1 ) ≤ ℓ ( a 3 ) \ell(a_1) \leq\ell(a_3) ℓ ( a 1 ) ≤ ℓ ( a 3 ) and ℓ ( a 1 ) + ℓ ( a 2 ) + ℓ ( a 3 ) ≤ 15 \ell(a_1) + \ell(a_2) + \ell(a_3) \leq15 ℓ ( a 1 ) + ℓ ( a 2 ) + ℓ ( a 3 ) ≤ 15 .
We define instances in (c) and (d) in order to find chemical graphs that have an intermediate structure of given two chemical cyclic graphs G A = ( H A = ( V A , E A ) , α A , β A ) G_A = (H_A = (V_A, E_A), \alpha_A, \beta_A) G A = ( H A = ( V A , E A ) , α A , β A ) and G B = ( H B = ( V B , E B ) , α B , β B ) G_B = (H_B = (V_B, E_B), \alpha_B, \beta_B) G B = ( H B = ( V B , E B ) , α B , β B ) . Let Λ A i n t \Lambda_A^{\mathrm{int}} Λ A int and Λ d g , A i n t \Lambda_{\mathrm{dg},A}^{\mathrm{int}} Λ dg , A int denote the sets of chemical elements and chemical symbols of the interior-vertices in G A G_A G A , Γ A i n t \Gamma_A^{\mathrm{int}} Γ A int denote the sets of edge-configurations of the interior-edges in G A G_A G A , and F A F_A F A denote the set of 2-fringe-trees in G A G_A G A . Analogously define sets Λ B i n t \Lambda_B^{\mathrm{int}} Λ B int , Λ d g , B i n t \Lambda_{\mathrm{dg},B}^{\mathrm{int}} Λ dg , B int , Γ B i n t \Gamma_B^{\mathrm{int}} Γ B int and F B F_B F B in G B G_B G B .
(c) I c = ( G C , σ i n t , σ c e ) I_c = (G_C, \sigma_{\mathrm{int}}, \sigma_{\mathrm{ce}}) I c = ( G C , σ int , σ ce ) : An instance aimed to infer a chemical graph G † G^\dagger G † such that the core of G † G^\dagger G † is equal to the core of G A G_A G A and the frequency of each edge-configuration in the non-core of G † G^\dagger G † is equal to that of G B G_B G B . We use chemical compounds CID 24822711 and CID 59170444 in Figure 6 (a) and (b) for G A G_A G A and G B G_B G B , respectively.
Set a seed graph G C = ( V C , E C = E ( = 1 ) ) G_C = (V_C, E_C = E_{(=1)}) G C = ( V C , E C = E ( = 1 ) ) to be the core of G A G_A G A .
Set Λ : = { H , C , N , O } \Lambda:= \{\mathrm{H}, \mathrm{C}, \mathrm{N}, \mathrm{O}\} Λ := { H , C , N , O } , and set Λ d g i n t \Lambda_{\mathrm{dg}}^{\mathrm{int}} Λ dg int to be the set of all possible chemical symbols in Λ × [ 1 , 4 ] \Lambda\times[1,4] Λ × [ 1 , 4 ] .
Set Γ i n t : = Γ A i n t ∪ Γ B i n t \Gamma^{\mathrm{int}} := \Gamma_A^{\mathrm{int}} \cup\Gamma_B^{\mathrm{int}} Γ int := Γ A int ∪ Γ B int and Λ ∗ ( v ) : = { α A ( v ) } \Lambda^*(v) := \{\alpha_A(v)\} Λ ∗ ( v ) := { α A ( v )} , v ∈ V C v \in V_C v ∈ V C .
Set n L B i n t : = min { n i n t ( G A ) , n i n t ( G B ) } n_{\mathrm{LB}}^{\mathrm{int}} := \min\{n^{\mathrm{int}}(G_A), n^{\mathrm{int}}(G_B)\} n LB int := min { n int ( G A ) , n int ( G B )} , n U B i n t : = max { n i n t ( G A ) , n i n t ( G B ) } n_{\mathrm{UB}}^{\mathrm{int}} := \max\{n^{\mathrm{int}}(G_A), n^{\mathrm{int}}(G_B)\} n UB int := max { n int ( G A ) , n int ( G B )} ,
n L B : = min { n ( G A ) , n ( G B ) } − 10 = 40 n_{\mathrm{LB}} := \min\{n(G_A), n(G_B)\} - 10 = 40 n LB := min { n ( G A ) , n ( G B )} − 10 = 40 and n ∗ : = max { n ( G A ) , n ( G B ) } + 5 n^* := \max\{n(G_A), n(G_B)\} + 5 n ∗ := max { n ( G A ) , n ( G B )} + 5 .
Set lower bounds ℓ L B \ell_{\mathrm{LB}} ℓ LB , b l L B \mathrm{bl}_{\mathrm{LB}} bl LB , c h L B \mathrm{ch}_{\mathrm{LB}} ch LB , b d 2 , L B \mathrm{bd}_{2,\mathrm{LB}} bd 2 , LB , b d 3 , L B \mathrm{bd}_{3,\mathrm{LB}} bd 3 , LB , n a L B \mathrm{na}_{\mathrm{LB}} na LB , n a L B i n t \mathrm{na}_{\mathrm{LB}}^{\mathrm{int}} na LB int , n s L B i n t \mathrm{ns}_{\mathrm{LB}}^{\mathrm{int}} ns LB int , a c L B i n t \mathrm{ac}_{\mathrm{LB}}^{\mathrm{int}} ac LB int and a c l f L B \mathrm{aclf}_{\mathrm{LB}} aclf LB to be 0.
Set upper bounds n a U B ( a ) : = n ∗ \mathrm{na}_{\mathrm{UB}}(a) := n^* na UB ( a ) := n ∗ , a ∈ { H , C } a \in\{\mathrm{H}, \mathrm{C}\} a ∈ { H , C } , n a U B ( a ) : = 5 \mathrm{na}_{\mathrm{UB}}(a) := 5 na UB ( a ) := 5 , a ∈ { O , N } a \in\{\mathrm{O}, \mathrm{N}\} a ∈ { O , N } , n a U B ( a ) : = 2 \mathrm{na}_{\mathrm{UB}}(a) := 2 na UB ( a ) := 2 , a ∈ Λ ∖ { H , C , O , N } a \in\Lambda\setminus\{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}\} a ∈ Λ ∖ { H , C , O , N } and set the other upper bounds ℓ U B \ell_{\mathrm{UB}} ℓ UB , b l U B \mathrm{bl}_{\mathrm{UB}} bl UB , c h U B \mathrm{ch}_{\mathrm{UB}} ch UB , b d 2 , U B \mathrm{bd}_{2,\mathrm{UB}} bd 2 , UB , b d 3 , U B \mathrm{bd}_{3,\mathrm{UB}} bd 3 , UB , n a U B i n t \mathrm{na}_{\mathrm{UB}}^{\mathrm{int}} na UB int , n s U B i n t \mathrm{ns}_{\mathrm{UB}}^{\mathrm{int}} ns UB int , a c U B i n t \mathrm{ac}_{\mathrm{UB}}^{\mathrm{int}} ac UB int and a c l f U B \mathrm{aclf}_{\mathrm{UB}} aclf UB to be n ∗ n^* n ∗ .
Set e c L B i n t ( γ ) \mathrm{ec}_{\mathrm{LB}}^{\mathrm{int}}(\gamma) ec LB int ( γ ) to be the number of core-edges in G A G_A G A with γ ∈ Γ i n t \gamma\in\Gamma^{\mathrm{int}} γ ∈ Γ int and e c U B i n t ( γ ) \mathrm{ec}_{\mathrm{UB}}^{\mathrm{int}}(\gamma) ec UB int ( γ ) to be the number interior-edges in G A G_A G A and G B G_B G B with edge-configuration γ \gamma γ .
Let F B p F_B^p F B p , p ∈ [ 1 , 2 ] p \in[1,2] p ∈ [ 1 , 2 ] denote the set of chemical rooted trees r-isomorphic p p p -fringe-trees in G B G_B G B ; Set F E : = F ( v ) : = F B ( 1 ) ∪ F B ( 2 ) F_E := F(v) := F_B^{(1)} \cup F_B^{(2)} F E := F ( v ) := F B ( 1 ) ∪ F B ( 2 ) , v ∈ V C v \in V_C v ∈ V C and f c L B ( ψ ) : = 0 \mathrm{fc}_{\mathrm{LB}}(\psi) := 0 fc LB ( ψ ) := 0 , f c U B ( ψ ) : = 10 \mathrm{fc}_{\mathrm{UB}}(\psi) := 10 fc UB ( ψ ) := 10 , ψ ∈ F B ( 1 ) ∪ F B ( 2 ) \psi\in F_B^{(1)} \cup F_B^{(2)} ψ ∈ F B ( 1 ) ∪ F B ( 2 ) .
(d) I d = ( G C 1 , σ i n t , σ c e ) I_d = (G_C^1, \sigma_{\mathrm{int}}, \sigma_{\mathrm{ce}}) I d = ( G C 1 , σ int , σ ce ) : An instance aimed to infer a chemical monocyclic graph G † G^\dagger G † such that the frequency vector of edge-configurations in G † G^\dagger G † is a vector obtained by merging those of G A G_A G A and G B G_B G B . We use chemical monocyclic compounds CID 10076784 and CID 44340250 in Figure 6 (c) and (d) for G A G_A G A and G B G_B G B , respectively. Set a seed graph to be the monocyclic seed graph G C 1 = ( V C , E C = E ( ≥ 2 ) ∪ E ( ≥ 1 ) ) G_C^1 = (V_C, E_C = E_{(\geq2)} \cup E_{(\geq1)}) G C 1 = ( V C , E C = E ( ≥ 2 ) ∪ E ( ≥ 1 ) ) with V C = { u 1 , u 2 } V_C = \{u_1, u_2\} V C = { u 1 , u 2 } , E ( ≥ 2 ) = { a 1 } E_{(\geq2)} = \{a_1\} E ( ≥ 2 ) = { a 1 } and E ( ≥ 1 ) = { a 2 } E_{(\geq1)} = \{a_2\} E ( ≥ 1 ) = { a 2 } in Figure 5 (i).
Set Λ : = { H , C , N , O } \Lambda:= \{\mathrm{H}, \mathrm{C}, \mathrm{N}, \mathrm{O}\} Λ := { H , C , N , O } , Λ d g i n t : = Λ d g , A i n t ∪ Λ d g , B i n t \Lambda^{\mathrm{int}}_{\mathrm{dg}} := \Lambda^{\mathrm{int}}_{\mathrm{dg},A} \cup\Lambda^{\mathrm{int}}_{\mathrm{dg},B} Λ dg int := Λ dg , A int ∪ Λ dg , B int and Γ i n t : = Γ A i n t ∪ Γ B i n t \Gamma^{\mathrm{int}} := \Gamma^{\mathrm{int}}_{A} \cup\Gamma^{\mathrm{int}}_{B} Γ int := Γ A int ∪ Γ B int .
Set n L B i n t : = min { n i n t ( G A ) , n i n t ( G B ) } n^{\mathrm{int}}_{\mathrm{LB}} := \min\{n^{\mathrm{int}}(G_A), n^{\mathrm{int}}(G_B)\} n LB int := min { n int ( G A ) , n int ( G B )} , n U B i n t : = max { n i n t ( G A ) , n i n t ( G B ) } n^{\mathrm{int}}_{\mathrm{UB}} := \max\{n^{\mathrm{int}}(G_A), n^{\mathrm{int}}(G_B)\} n UB int := max { n int ( G A ) , n int ( G B )} , n L B : = min { n ( G A ) , n ( G B ) } = 40 n_{\mathrm{LB}} := \min\{n(G_A), n(G_B)\} = 40 n LB := min { n ( G A ) , n ( G B )} = 40 and n ∗ : = max { n ( G A ) , n ( G B ) } n^{*} := \max\{n(G_A), n(G_B)\} n ∗ := max { n ( G A ) , n ( G B )} .
Set lower bounds ℓ L B \ell_{\mathrm{LB}} ℓ LB , b l L B \mathrm{bl}_{\mathrm{LB}} bl LB , c h L B \mathrm{ch}_{\mathrm{LB}} ch LB , b d 2 , L B \mathrm{bd}_{2,\mathrm{LB}} bd 2 , LB , b d 3 , L B \mathrm{bd}_{3,\mathrm{LB}} bd 3 , LB , n a L B \mathrm{na}_{\mathrm{LB}} na LB , n a L B i n t \mathrm{na}^{\mathrm{int}}_{\mathrm{LB}} na LB int , n s L B i n t \mathrm{ns}^{\mathrm{int}}_{\mathrm{LB}} ns LB int , a c L B i n t \mathrm{ac}^{\mathrm{int}}_{\mathrm{LB}} ac LB int and a c L B l f \mathrm{ac}^{\mathrm{lf}}_{\mathrm{LB}} ac LB lf to be 0.
Set upper bounds n a U B ( a ) : = n ∗ \mathrm{na}_{\mathrm{UB}}(a) := n^{*} na UB ( a ) := n ∗ , n a ∈ { H , C } \mathrm{na} \in\{\mathrm{H}, \mathrm{C}\} na ∈ { H , C } , n a U B ( a ) : = 5 \mathrm{na}_{\mathrm{UB}}(a) := 5 na UB ( a ) := 5 , n a ∈ { O , N } \mathrm{na} \in\{\mathrm{O}, \mathrm{N}\} na ∈ { O , N } , n a U B ( a ) : = 2 \mathrm{na}_{\mathrm{UB}}(a) := 2 na UB ( a ) := 2 , n a ∈ Λ ∖ { H , C , O , N } \mathrm{na} \in\Lambda\setminus\{\mathrm{H}, \mathrm{C}, \mathrm{O}, \mathrm{N}\} na ∈ Λ ∖ { H , C , O , N } and set the other upper bounds ℓ U B \ell_{\mathrm{UB}} ℓ UB , b l U B \mathrm{bl}_{\mathrm{UB}} bl UB , c h U B \mathrm{ch}_{\mathrm{UB}} ch UB , b d 2 , U B \mathrm{bd}_{2,\mathrm{UB}} bd 2 , UB , b d 3 , U B \mathrm{bd}_{3,\mathrm{UB}} bd 3 , UB , n a U B i n t \mathrm{na}^{\mathrm{int}}_{\mathrm{UB}} na UB int , n s U B i n t \mathrm{ns}^{\mathrm{int}}_{\mathrm{UB}} ns UB int , a c U B i n t \mathrm{ac}^{\mathrm{int}}_{\mathrm{UB}} ac UB int and a c U B l f \mathrm{ac}^{\mathrm{lf}}_{\mathrm{UB}} ac UB lf to be n ∗ n^{*} n ∗ .
For each edge-configuration γ ∈ Γ i n t \gamma\in\Gamma^{\mathrm{int}} γ ∈ Γ int , let x A ∗ ( γ i n t ) x^{*}_{A}(\gamma^{\mathrm{int}}) x A ∗ ( γ int ) (resp., x B ∗ ( γ i n t ) x^{*}_{B}(\gamma^{\mathrm{int}}) x B ∗ ( γ int ) ) denote the number of interior-edges with γ \gamma γ in G A G_A G A (resp., G B G_B G B ), γ ∈ Γ i n t \gamma\in\Gamma^{\mathrm{int}} γ ∈ Γ int and set x min ∗ ( γ ) : = min { x A ∗ ( γ ) , x B ∗ ( γ ) } x^{*}_{\min}(\gamma) := \min\{x^{*}_{A}(\gamma), x^{*}_{B}(\gamma)\} x m i n ∗ ( γ ) := min { x A ∗ ( γ ) , x B ∗ ( γ )} , x max ∗ ( γ ) : = max { x A ∗ ( γ ) , x B ∗ ( γ ) } x^{*}_{\max}(\gamma) := \max\{x^{*}_{A}(\gamma), x^{*}_{B}(\gamma)\} x m a x ∗ ( γ ) := max { x A ∗ ( γ ) , x B ∗ ( γ )} , e c L B i n t ( γ ) : = ⌊ ( 3 / 4 ) x min ∗ ( γ ) + ( 1 / 4 ) x max ∗ ( γ ) ⌋ \mathrm{ec}^{\mathrm{int}}_{\mathrm{LB}}(\gamma) := \lfloor(3/4)x^{*}_{\min}(\gamma) + (1/4)x^{*}_{\max}(\gamma)\rfloor ec LB int ( γ ) := ⌊( 3/4 ) x m i n ∗ ( γ ) + ( 1/4 ) x m a x ∗ ( γ )⌋ and e c U B i n t ( γ ) : = ⌈ ( 1 / 4 ) x min ∗ ( γ ) + ( 3 / 4 ) x max ∗ ( γ ) ⌉ \mathrm{ec}^{\mathrm{int}}_{\mathrm{UB}}(\gamma) := \lceil(1/4)x^{*}_{\min}(\gamma) + (3/4)x^{*}_{\max}(\gamma)\rceil ec UB int ( γ ) := ⌈( 1/4 ) x m i n ∗ ( γ ) + ( 3/4 ) x m a x ∗ ( γ )⌉ .
Set F E : = F ( v ) : = F A ∪ F B \mathcal{F}_{E} := \mathcal{F}(v) := \mathcal{F}_{A} \cup\mathcal{F}_{B} F E := F ( v ) := F A ∪ F B , v ∈ V C v \in V_{C} v ∈ V C and f c L B ( ψ ) : = 0 \mathrm{fc}_{\mathrm{LB}}(\psi) := 0 fc LB ( ψ ) := 0 , f c U B ( ψ ) : = 10 \mathrm{fc}_{\mathrm{UB}}(\psi) := 10 fc UB ( ψ ) := 10 , ψ ∈ F A ∪ F B \psi\in\mathcal{F}_{A} \cup\mathcal{F}_{B} ψ ∈ F A ∪ F B .
We include a linear constraint ℓ ( a 1 ) ≤ ℓ ( a 2 ) \ell(a_{1}) \leq\ell(a_{2}) ℓ ( a 1 ) ≤ ℓ ( a 2 ) and 5 ≤ ℓ ( a 1 ) + ℓ ( a 2 ) ≤ 15 5 \leq\ell(a_{1}) + \ell(a_{2}) \leq15 5 ≤ ℓ ( a 1 ) + ℓ ( a 2 ) ≤ 15 as part of the side constraint.