# Progressive Multiple Alignment of Graphs
## 3 Algorithmic Considerations  
### Construction of the Guide Tree Based on Graph Kernels  
Every binary tree \(\mathfrak{T}\) with leaves that are in a one-to-one correspondence with the input graphs may serve as guide tree for a progressive alignment. It is well known for multiple alignments of sequences, however, that the guide tree influences the quality of the alignment [28; 29]. In the case of graph alignments, the computational effort for computing MCIS, and thus for the pairwise alignment problems, also depends on the similarity of the input graphs. It is desirable, therefore, to use a guide tree along which for each inner node, the two children correspond to graphs that are as similar as possible. The most useful guide trees thus correspond to a parsimonious hierarchical clustering of the input graphs [16]. In the case alignments of homologous genetic sequences, a good approximation of the correct phylogeny is ideal. In practice, good guide trees are obtained by hierarchical clustering of the input objects.  
The progressive computation of the multiple alignment requires \(\mathcal{O}(N)\) pairwise alignments. In contrast, all \(\mathcal{O}(N^{2})\) pairwise comparisons are required for hierarchical clustering to estimate the guide tree. However, pairwise alignments can be used to compute the distances or similarities of all pairs of input objects. It is therefore desirable to replace the alignment-based similarities by a computationally less expensive approximation for the computation of the guide tree. Comparisons of two graphs based on MCIS [30], i.e., \(d_{\text{MCIS}}(G,H)\coloneqq|V(G)|+|V(H)|-2|\text{MCIS}(G,H)|\), as well as other forms of graph editing distance [31] are NP-complete.  
Among the heuristic alternatives are distance measures based on semi-definite graph kernels [32], i.e., bilinear functions \(\kappa:\mathfrak{G}\times\mathfrak{G}\to\mathbb{R}\) on a non-empty set \(\mathfrak{G}\) satisfying \(\sum_{i=1}^{n}\sum_{j=1}^{n}c_{i}\kappa(G_{i},G_{j})\geq 0\) for all \(G_{1},\ldots,G_{n}\in\mathfrak{G}\) and any \(c_{1},\ldots,c_{n}\in\mathbb{R}\). The kernel function \(\kappa\) in essence provides a similarity measure between graphs.  
Furthermore, as shown in [33; 34], due to its relation with inner products in vector spaces, the similarities \(\kappa(G_{i},G_{j})\) can be transformed into a distance measure \(d(G_{i},G_{j})\) by taking the square root of the value \(\kappa(G_{i},G_{i})+\kappa(G_{j},G_{j})-2\kappa(G_{i},G_{j})\). Both the similarities and its associated distances can be used as inputs for a simple agglomerative hierarchical clustering procedure, here simply WPGMA [22], to infer a guide tree \(\mathfrak{T}\).  
Originally conceived in cheminformatics, a wide array of graph kernels has been studied depending on different properties and features of graphs, including paths, walks, cycles, spanning trees, matchings, local subgraphs, etc.; see [35] for a survey. Implementations of kernel functions for graphs (including labeled, weighted, and directed graphs) are available as widely used software packages such as graphkit-learn [36]. Here, we made use of the Structural_Shortest_Path kernel implementation of the graphkit-learn library in order to produce our kernel-based guide trees. As shown in Appendix A.1, the kernel-based distance and the MCIS-based distance are well correlated.