## 2 Materials and Methods
### Tree-Extensions
#### 2.3.2. MILPs for Rank-2 Chemical Graphs
In the scheme graph \((K,\mathcal{E})\), denote the edges in \(E_{1}\cup E_{2}\cup E_{3}\) by \(E_{1}=\{a_{1},a_{2},\ldots,a_{|E_{1}|}\}\), \(E_{2}=\{a_{|E_{1}|+1},\ldots,a_{c^{*}}\}\) and \(E_{3}=\{a_{c^{*}+1},\ldots,a_{m}\}\) (where \(c^{*}=|E_{1}\cup E_{2}|\)), and regard each edge \(a_{i}=u_{s,1}u_{s^{\prime},1}\in E_{1}\cup E_{2}\cup E_{3}\) as a directed edge from one end-vertex \(u_{s,1}\) to the other end-vertex \(u_{s^{\prime},1}\) with \(s<s^{\prime}\). Let \(a(i)\) be a binary variable for each edge \(a_{i}\), \(i\in[1,m]\). 2. In each tree \(S_{s}\) (resp., \(T_{i}\)) in the tree-extension, we regard each edge \(e^{\prime}_{s,i^{\prime}}\), \(i\geq 2\) in the rooted tree \(S_{s}\), \(s\in[1,s^{*}]\) (resp., \(e_{t,i}\), \(i\geq 2\) in the rooted tree \(T_{t}\), \(t\in[1,t^{*}]\)) as a directed edge from vertex \(u_{s,\mathrm{prt}(i)}\) to vertex \(u_{s,i}\) (resp., from vertex \(v_{t,\mathrm{prt}(i)}\) to vertex \(v_{t,i}\)). Let \(u(s,i)\) (resp., \(v(t,i)\)) be a binary variable for vertex \(u_{s,i}\), \(s\in[1,s^{*}]\) (resp., \(t\in[1,t^{*}]\)) and \(i\in[1,u_{\mathrm{tree}}]\);
3. In the path \(P_{t^{*}}\) consisting of the roots of trees \(T_{t}\), \([t\in 1,t^{*}]\), we regard each edge \(e_{t}\), \(t\in[2,t^{*}]\) as a directed edge from vertex \(v_{t-1,1}\) to vertex \(v_{t,1}\); and
4. We regard each edge \(u_{s,1}v_{t,1}\) for \(s\in[1,s^{*}]\) and \(t\in[1,t^{*}]\) as two directed edges, one directed from vertex \(u_{s,1}\) to vertex \(v_{t,1}\) and the other directed oppositely. Let \(e(s,t)\) (resp., \(e(t,s)\)) be a binary variable of directed edge \((u_{s,1},v_{t,1})\) (resp., \((v_{t,1},u_{s,1})\)). Based on these, we include constraints with some more additional variables so that a selected subgraph \(H\) is a connected rank-2 graph. See constraints Equations (A10) to (A42) in Appendix A for the details. In the constraints of 2, we prepare an integer variable \(\widetilde{\alpha}(u)\) for each vertex \(u\) in the tree-extension that represents the chemical element \(\alpha(u)\in\Lambda\) if \(u\) is in a selected graph \(H\) (or \(\widetilde{\alpha}(u)=0\) otherwise) and an integer variable \(\widetilde{\beta}(e)\in[0,3]\) (resp., \(\widehat{\beta}(e)\in[0,3]\)) for each edge \(e\) (resp., \(e=e(s,t)\) or \(e(t,s),s\in[1,s^{*}]\), \(t\in[1,t^{*}]\)) in the tree-extension that represents the multiplicity \(\beta(e)\in[1,3]\) if \(e\) is in a selected graph \(H\) (or \(\widehat{\beta}(e)\) or \(\widehat{\beta}(e)\) takes 0 otherwise). This determines a chemical graph \(G=(H,\alpha,\beta)\). Also we include constraints for a selected chemical graph \(G\) to satisfy the valence condition \((\alpha(u),\alpha(v),\beta(uv))\in\Gamma\) for each edge \(uv\in E\). See constraints Equations (A43) to (A61) in Appendix A for the details. In the constraints of 3, we introduce a variable for each descriptor and constraints with some more variables to compute the value of each descriptor in \(f(G)\) for a selected chemical graph \(G\). See constraints Equations (A62) to (A113) in Appendix A for the details. With constraints 1 to 3, our MILP formulation already represents a rank-2 chemical graph \(G\) and a feature vector \(x\in\mathbb{R}^{k}\) so that \(x=f(G)\) holds. In the constraints of 4, we include some additional constraints so that the search space required for an MILP solver to solve an instance of our MILP problem is reduced. For this, we consider a graph-isomorphism of rooted subtrees of each tree \(S_{s}\) or \(T_{s}\) and define a canonical form among subtrees that are isomorphic to each other. We try to eliminate a chemical graph \(G\) that has a subtree in \(S_{s}\) or \(T_{s}\) that is not a canonical form. See constraints Equations (A114) to (A119) in Appendix A for the details.