Graphs are mathematical objects used to represent items, also called vertices, and relations between them. In the bioinformatics context, they are exploited to express relationships at any biochemical, biological, and medical level. For example, graphs can represent physical molecule structure by expressing chemical bonds among atoms [Tri18]. At the cellular system level, graphs are instead applied to represent biological actors, such as genes, proteins, or RNAs, and their relations, such as physical interactions or causal inference [HPRL08, DL05, BDCC+18]. Di erently, in medical applications, graphs are exploited in decision support systems to connect patient data with disease states and treatments [XWJF19]. For what concerns integration and analysis of multi-omics data, graphs are becoming popular for integrating biomedical information with data regarding multiple omics. In such a model, items compose a heterogeneous set of biological and meta-biological objects. Graphs of genetic interactions are enriched by embedding their relationship with diseases, drugs, anatomic phenotypes, biological functions, or cellular localization. Then, multi-omics data linked to the genetic actors are integrated. The result is a knowledge base that can be exploited for drug repurposing, for prioritizing disease-associated genes, or for patient classification and biomarker identification [HB15, FWY+21, WSH+21].

Among the computational tasks that can be performed on top of such structures, the search of specific topologies within biological graphs is one of the most challenging problems. In particular, the subgraph isomorphism problem is known to be NP-complete [Coo71]. In this context, indexing of labeled graphs is a widely used technique for dealing with such complexity. In fact, it provides a good compromise between precision in filtering unmatching parts of the graphs and time to compute such an operation [LVCF21, GBB+13]. Practically, indexing approaches store topological features, ranging from paths to frequent substructures, in order to provide a fast pruning of the labeled graphs or parts of them that do not contain the queried topology. However, this kind of approaches may lead to relatively large indexes, that can compromise performance.

Recently, Decision Diagrams (DDs) have successfully been applied for reducing the indexing size [LBBG21]. In fact, DDs are particularly e cient for detecting common portions among the paths and storing e ciently them. Their e ciency is known to be strongly a ected by the ordering of variables describing a path: a good ordering can substantially reduce the memory consumption and the execution time to generate and encode the indexing. Unfortunately, discovering the optimal variable ordering is known to be NP-complete [BW96a]. Thus, various heuristics depending on the specific application field for the selection of (sub)optimal orderings were proposed in the literature [FFM93].

Starting from this observation, in this paper, we extend the results presented in [LBBG21] by investigating how the variable ordering may a ect the performance of such an approach in terms of memory consumption. This task was carried out by first proposing a new metric called Sum of Entropies (SOE), which experimentally highlighted a medium-to-strong anti-correlation value with respect to the final size of the DD encoding the indexing. Then, the metric was exploited as starting point to derive a sub-optimal heuristic EntropyHeu that finds a variable order greedily by optimizing the SOE metric.

In detail, Section 2 introduces the concepts of indexing of labeled graphs and DDs. Moreover, the section recalls how DD can be e ciently exploited for encoding graph indexing and we discuss how its e ciency is strongly affected by the choice of a “reasonably good” variable order.

In Section 3, the new metric SOE and the derived new heuristic are formally introduced.

Then, the e ectiveness of the new heuristic is assessed in Section 4 reporting its performance on a set of wellknown biological benchmarks. Finally, Section 5 concludes the paper. 2

In this section, we firstly introduce the concepts of graphs, labeled paths and path-based graph indexing. Then, the Multi-Terminal Multi-way Decision Diagrams (MTMDDs) are introduced as an e cient data structure to encode and manipulate a set of paths with their occurrences. Finally, we describe GRAPES-DD, a tool using MTMDDs for effective searching in graphs. 2.1

In this section, after introducing the GRAPES-DD strategy, we focus on the formal definition of a new suboptimal heuristic inspired to decision tree learning in machine learning [Qui86].

GRAPES-DD exploits an MTMDD with n variables: n 1 variables vi, i = 1; : : : ; n 1 encoding the paths’ ith label; and vn encoding the identifier of the starting node of the labeled path. Note that vn and the vi, 1 i < n, are di erent because they belongs to di erent domain spaces 1Multiset extends the concept of a set allowing for multiple instances for each of its elements. 1: function EntropyHeu 2: O EntropyHeuLabels() 3: minSize 4: for i 5: 6: 7: 8: 9: 10:

1 [1 : : : n] do O0 InsertAt(O; fvn 7! ig) DD0 BuildDD(O0) if SizeDD(DD0) < minS ize then minSize SizeDD(DD0)

O O0 return O 11: function EntropyHeuLabels 12: U fv1 : : : vn 1g 13: O fg 14: for i from 1 to n 1 do 15: null 16: 17: 18: 19: 20: 21: 22: vsel Hsel 1 for v0 2 U do:

U0 U n fv0g H0 Entropy(U0) if H0 > Hsel then vsel v0

Hsel H0

Algorithm 1: Variable ordering selection heuristic (graph vertices and labels, resp.) with largely di erent domain cardinalities. Given a fixed position vn 7! k for the vn variable, we define the stratum k as the subset of variable orders fOgk sharing the fixed position for vn. We shall see that the strata show significant clustering of the results in Section 4.

Each tuple x = hv1 : : : vni has an associated integer multiplicity mult(x). Let X be the multiset of all the encoded tuples x. Given a multiset X, let H(X) be the entropy of X, defined according to the standard definition [Sha01] H(X) =

X p(x) log2 p(x); with: p(x) = x2X (1)

Let U N be a subset of the problem’s variables. Let x0 = x=U be a new tuple x0 obtained from a tuple x by removing all the variables not in U. Let X=U be the projection of the multiset X over the sole variables U, with mult(x) P mult(x0) x02X mult(x0) = mult(x)

(2)

X x2X; x0=x=U the multiplicity of each tuple x0.

Given a variable order O = fk1 : : : kng, we define the i-th variable subset UO;i as the set of the first i variable indices of O. We define the SOE metric for a variable order O as SOE(O) = n X H X=UO;i i=1 (3) Research question R1: The size of the MTMDD (i.e. the sum of its nodes and edges) correlates with the SOE function. To test this hypothesis, we construct the MTMDD for all the variable orders (which is factorial in the number n of variables), and compute a correlation score between the value (3) and the final MTMDD size.

Unfortunately, finding the optimal MTMDD by constructing all the permutations is not feasible in practice, except for a limited number of encoded variables. Therefore, to make the technique broadly applicable in a real world context, we define a sub-optimal heuristic EntropyHeu that searches a variable order O by applying a greedy optimization the local entropy sum at every projection step i.

The pseudo-code of EntropyHeu is shown in Algorithm 1. The function EntropyHeu first computes the ordering for the fv1 : : : vn 1g label variables. It then tries to insert the identifier variable vn in all the positions, returning the order O that minimizes the final DD size. The function EntropyHeuLabels is the core heuristic algorithm, performing the greedy search. It starts by defining an empty variable order O and by taking into account the full set of label variables U. At each outer iteration (lines 14-23), a variable vsel 2 U is removed and assigned to position i in the order O. The variable vsel is chosen to be the one that maximizes the entropy given by the remaining set of variables U n fvselg, namely: vsel = arg max H(U n v) v2U (4)

We assume that BuildDD(O) generates the MTMDD for the projected variables subset with order O, and Entropy(U) computes (1) on the projected multiset X=U.

We empirically tested our two research questions R1 and R2 using a set of well-known biological benchmarks, described hereafter. The first 5 benchmarks are proteinprotein interaction (PPI) networks of 5 di erent species: Caenorhabditis elegants (CE), Drosophila melanogaster (DROSOFILA), Homo sapiens (HOMO), Mus musculus (MUS) and Saccaromyces cerevisae (YEAST) [SFK+10]. Vertices are proteins and edges are predicted physical interactions between them. For each species, di erent thresholds on the accurateness of the prediction were applied, ranging from 0.4, 0.5, 0.6 to 0.7. The retrieved graphs have from 2k to 10k vertices, and from 2k to 89k edges, with average degrees ranging from 1.3 to 15. PPIs belonging to the same species were then merged into a single benchmark to be indexed. The obtained benchmarks have from 13k to 21k vertices, and from 39k to 260k edges.

We also included in the benchmark the standard database for Antiviral Screen(AIDS) [ci]. It consists of 40k chemical structures representing small molecules. Vertices are atoms and edge are the chemical bounds linking them. Vertex labels represent atomic elements, and there are a total of 62 distinct elements. The average number of vertices per graph is 44.98, and the average degree is 4.17.

We conducted a set of experiments over the graph databases described above. We indexed each database using labeled paths up to length 4, so that each index MTMDD is defined over 5 variables. Then, for each collection, we obtain the size of the index MTMDD for all possible variable orders.

Figure 1 reports the results for the R1 question on the 6 benchmarks. Each dot represents one of the 120 possible variable orders. Dots are colored by their respective stratification induced by the level of the identifier variable. In each stratum, a dashed line represents the trend of the relation between the SOE metric and the final DD size. The number indicates the value Spearman’s correlation coefficient. We can observe that the metric has medium-tostrong anticorrelation values in all stratum except for the one where the identifier is positioned at the bottom, whose sizes are almost insensible to the reordering of the label variables. The figure shows a very positive result, because it shows that a heuristic that maximizes the SOE metric has an high chance of selecting a good order that minimizes the DD size. Moreover, the cross on each stratum identifies the ordering that would be selected by the proposed heuristic EntropyHeu when fixing the position of the identifier variable.

Figure 2 shows the results for the R2 question on the e ectiveness of the EntropyHeu heuristic on the 6 benchmarks. Relative DD sizes are shown on the y-axis, while the x-axis has no meaning (it is only used for visualization purposes to separate the dots). The green cross identifies the relative DD size of the selected order, while the blue bar identifies the average size that would be obtained by taking an order randomly among the possible 120 orders. We can observe that the greedy heuristic that follows the metric SOE is actually capable of selecting almost-optimal orders in all the tested cases, showing the e ectiveness of the proposed information-based strategy. 5

In this paper, we extended the approach proposed in [LBBG21] investigating how the MTMDD variable order may a ect the performance of such an approach in 100 ) 80 % ( s egd 60 e + sed 40 o n D D 20 0 90 85 terms of memory consumption. To achieve this task we first proposed the new metric SOE based on the Shannon entropy which experimentally showed a medium-tostrong anticorrelation with respect to the DD size encoding the graph indexing. Then we developed the suboptimal heuristic EntropyHeu inspired to the information gain which is able to derive a variable order comparable with the theoretical-optimal order derived by the SOE metric. As a future extension, we will apply the EntropyHeu heuristic on a bigger set of benchmarks coming from different research fields and we will evaluate its performance by increasing the length of labeled paths.