# Physics-Informed Graph Neural Networks for Attack Path Prediction
## Appendix E Complexity Analysis
### Path Prediction Architecture  
\(\mathcal{M}_{1}\) and \(\mathcal{M}_{2}\) both operate on the same data inputs, i.e., a directed multigraph \(G=(V,E)\) with self-loops. \(d\) is the maximum number of parallel edges between any pair of nodes, \(p\) is the maximum number of labels per node, \(|E|\) is the set of edges, and \(|V|\) is the set of nodes. Since \(|V|,|E|,p,d\) are used to build \(F\), the signal tensor, and \(A\), the adjacency tensor, we can state the following:  
\[ \begin{split} T(\mathcal{M}_{1};G)&=\mathcal{O}(f( |V|,|E|,p,d))\\ T(\mathcal{M}_{2};G)&=\mathcal{O}(f(|V|,|E|,p,d)) \end{split}  \tag{15}\]Now, we assume the following inequalities: \(d\leq|E|\)--meaning that the number of edge types does not exceed the total number of edges in the graph. In other words, \(d\) does not include edge types that do not have at least one edge in the \(G\). Later in this section, we drop this assumption to observe the effect on time complexity. We also assume that \(1\leq|V|\leq|E|\) and \(p\leq d\), which is consistent with the data augmentation strategy we proposed, i.e., the graph structure is tracked by edges rather than nodes. We can state the following:  
\[ \begin{split} 1&\leq p\leq d\\ 1&\leq|V|\leq|E|\\ d&\leq|E|\leq d\times|V|^{2}\end{split}  \tag{12}\]  
The first block of \(\mathcal{M}_{1}\) is the graph convolution block, denoted by \(\mathcal{M}_{\text{conv}}\). The computational complexity of Algorithm 1 is primarily determined by the aggregation step within the loop over edge types. Initializing the node feature tensor \(\mathcal{H}^{(0)}\) and the auxiliary matrix \(\mathcal{H}^{\prime}\) requires \(\mathcal{O}(1)\). The main computational cost arises in the aggregation step, where, for each edge type, the algorithm computes the inverse degree matrix \(D_{i}^{-1}\) and performs a matrix multiplication \(D_{i}^{-1}A_{i}\cdot\mathcal{H}^{(0)}\). This results in a complexity of \(\mathcal{O}(|V|^{2}\times p)\) per iteration. Since this operation is repeated for each of the \(d\) edge types, the total cost of the loop is \(\mathcal{O}(d\times|V|^{2}\times p)\). The final transformation step, involving a matrix multiplication and activation function, contributes an additional \(\mathcal{O}(|V|\times p\times H)\). In practice, this operation is optimized using the torch.bmm() API. See the implementation in Listing A1, where the message_passing() function is responsible for the aggregation step, while the forward() function is responsible for concatenation and activation. The message-passing algorithm performs batch matrix multiplication to efficiently multiply the signal tensor \(F\) with each of the \(d\) adjacency matrices composing the adjacency tensor \(A\). Each of the \(d\) matrices is then transformed through a linear layer (\(w_{i}\) in Algorithm 1) and summed. When the forward() function calls the message-passing algorithm, the sum is transformed through a linear layer and then passed through an activation function. The forward function returns the \(K\)-th layer embedding. In the overall implementation, this function pair is called \(K\) times. The overall complexity of the algorithm can be approximated as \(\mathcal{O}(K\times d\times|V|^{2}\times p)\). As \(K\) and \(H\) are architecture-dependent, we can state the following:  
\[T(\mathcal{M}_{\text{conv}};G)=\mathcal{O}(d\times|V|^{2}\times p) \tag{13}\]  
Now, considering the inequalities in Equation (12), \(\mathcal{O}(p)\) is at most \(\mathcal{O}(d)\Rightarrow\mathcal{O}(|E|)\Rightarrow\mathcal{O}(d\times|V|^{2})\). We can express the worst-case time complexity of the convolution block in terms of \(|V|^{2}\) only as follows:  
\[T(\mathcal{M}_{\text{conv}};G)=\mathcal{O}(|V|^{2}) \tag{14}\]  
Now, we update the inequalities presented in Equation (12) and no longer assume \(d\leq|E|\)--meaning that there can be more edge types than actual edges in the graph. Practically speaking, this results in the adjacency tensor \(A\) containing null matrices for certain edge types.