# A Generalized Framework for the Estimation of Edge Infection Probabilities
## 4 Evaluation
### Acyclic Examples
#### 4.2.2 Trees and Directed Acyclic Graphs (DAGs)  
We first evaluate the performance of the GIIM with arborescences. In these graphs, the infection spreads from the root, which is infected with probability of 1. Reference edge values were drawn from a uniform distribution between 0 and 1. We consider both binary and real vertex infection values for three binary trees with heights of 4, 8 and 11 and two DAGs with 42 and 420 edges. Figure 1: Example of underdetermination. There is only one edge weight that explains the infection event on (**a**), while (**b**) is underdetermined. First, consider the task where we only have two observations on the infection process, one at the beginning \(t_{0}=i_{0}\) and one at the end \(t_{1}=t_{max}=i_{max}\) of the process. The accuracy of the estimations are presented in Table 1. The differences between infection models was minimal; therefore, results are only shown for the IC infection model. When the observations are provided as binary flags, the optimization algorithm is always able to find an optimal solution with RMSE = 0 and AUC = 1 much faster than with the real-valued solution. The reason for this is due to the underdetermination. If the observations are vectors of ones and zeros, the best way to explain the observations is to assign the edge values to be ones and zeros. To further illustrate this concept, consider the example shown in Figure 2. A leaf node in the tree has an observed infection value of one if all the edges leading to the leaf from the root have an edge infection value of one. If a leaf node has a value of zero, at least one edge connecting it to the root must have a zero value. This constrains the search to binary values as opposed to the continuous values of the real-valued case. Even if the behavior of the infection process is more complicated in DAGs, i.e., there are more explanations, this makes the binary inverse infection task much easier. Table 1 shows that in the two-observation real-valued case, the second DAG with 420 edges is more challenging than the similarly sized tree with 511 edges. This is because \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Class** & **Edges** & **Binary** & **Binary** & **Real-Valued** \\  & & **ROC AUC** & **RMSE** & **RMSE** \\ \hline Tree & 31 & 1 & 0 & 0.0171 \\ Tree & 511 & 1 & 0 & 0.0269 \\ Tree & 2047 & 1 & 0 & 0.08 \\ DAG & 42 & 1 & 0 & 0.0262 \\ DAG & 420 & 1 & 0 & 0.0562 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Average error of the optimization method on trees and directed lattices of various sizes for the two-observation case. The graph class, the number of edges and the accuracy of the results (error at the end of the optimization process) can be seen. Both binary and real-valued observations were tested, with AUC and RMSE provided for the former and only RMSE for the latter. Results are provided for the IC infection model. Figure 2: Example of underdetermination. A leaf node has an observed infection value of one if and only if all the edges leading to it have edge infection values of one. A leaf node has an observed infection value of zero if at least one edge connecting the root to it has a value of zero. in the trees, there is only one path from the source of the infection to each node, so there is only one way to explain the process, while in the DAGs, multiple paths are present, meaning that there are multiple optima. The first problem is therefore easier than the second, hence the difference in the real-valued RMSE results in Table 1.  
If the infection process is fully observed, i.e., if the infection status at all time steps is available, the error on all nodes for each individual time step can be computed separately; therefore, it is possible to measure the performance of the optimization method in each iteration of the infection process. Figure 3 shows the results for the fully observed case for the second tree and the second DAG.