# Physics-Informed Graph Neural Networks for Attack Path Prediction
## Appendix E Complexity Analysis
### Path Prediction Architecture
In that case, the lower bound \(d\leq|E|\) is no longer valid, and the total time complexity must include \(d\):  
\[T(\mathcal{M}_{\text{conv}};G)=\mathcal{O}(d\times|V|^{2}) \tag{15}\]```
classBMMSageConvLayer(nn.Module):... defmessage_passing(self,x:torch.Tensor,adj_tensor:torch.Tensor): batch_size,num_nodes,_=x.shape aggregated_neigh_embeds=[] fori inrange(adj_tensor.shape[3]): adj_matrix=adj_tensor[:,:,:,i] neigh_embeds_i=torch.bm(adj_matrix,x) neigh_embeds_i=self.lin_neighbors[i](neigh_embeds_i) aggregated_neigh_embeds.append(neigh_embeds_i) neigh_embeds=sum(aggregated_neigh_embeds) returnneigh_embeds defforward(self,x:torch.Tensor,adj_tensor:torch.Tensor): neigh_embeds=self.message_passing(x,adj_tensor) x_self=self.lin_self(x) out=neigh_embeds+x_self returnself.act(out) classDNN(nn.Module):... defforward(self,x): x=F.relu(self.fc1(x))... x=torch.sigmoid(self.fc5(x)) returnx
```

**Listing 1**\(\mathcal{M}_{1}\) implementation. Overall, Equation (A15) is the generalization of the time complexity of the graph convolution block, while Equation (A14) applies to cases where the architecture fits perfectly the dataset dimensions (which is the case in this paper). To complete the architecture \(\mathcal{M}_{1}\), we have to add the complexity of the prediction block. The block comprises \(k=4\) fully connected hidden layers, each containing 512 neurons with ReLU activations. The computational cost of a single fully connected layer mapping \(m\) input neurons to \(n\) output neurons is \(\mathcal{O}(|V|mn)\), where \(m\) and \(n\) are architecture-dependent. The last hidden layer maps \(n\) to an output of size \(|V|\), contributing an additional \(\mathcal{O}(|V|^{2})\). As this term dominates the overall computation, the total complexity of the MLP can be approximated as \(\mathcal{O}(|V|^{2})\). The logistic normalization function is applied element-wise and does not significantly impact the asymptotic complexity. Thus, the second block exhibits a quadratic complexity with respect to the number of nodes \(|V|\). As both blocks' time-complexity is dominated by the quadratic term \(|V|^{2}\), overall, this gives us a generalized time-complexity for the \(\mathcal{M}_{1}\) architecture as follows:

\[T(\mathcal{M}_{1};G)=\mathcal{O}(d\times|V|^{2})\] (A16)

### Node Classification Architecture

The second architecture, denoted by \(\mathcal{M}_{2}\), is composed of the same graph convolution block \(\mathcal{M}_{\text{conv}}\), with a different second block. We previously determined that the time complexity of the convolution block is \(\mathcal{O}(d\times|V|^{2})\). The time complexity of the node classification block, which does not vary depending on whether we are predicting start/end, is determined by the encoder and the classification MLP. This block's implementation is illustrated in Listing 2. The encoder compresses the input embeddings \(\mathcal{H}\) into a lower-dimensional representation \(z\in\mathbb{R}^{|V|\times\mathcal{Z}}\) through \(k=4\) fully connected layers with ReLU activations, progressively reducing the feature size from \(128\to 64\to 36\to 18\to z\). The computational cost of a fully connected layer mapping \(m\) input neurons to \(n\) output neurons is \(\mathcal{O}(|V|mn)\), where \(H,m,n,z\) are all architecture -dependent parameters. Summing across all layers, the total complexity of the encoder is approximately \(\mathcal{O}(|V|(128\times 64+64\times 36+36\times 18+18\times z))\), which can be reduced to \(\mathcal{O}(|V|)\). The classifier processes the compressed representation \(z\in\mathcal{Z}\) through two fully connected layers, with the first mapping \(z\to 64\) followed by a ReLU activation and the second mapping \(64\to|V|\) with a point-wise normalization step. This results in an additional complexity of \(\mathcal{O}(|V|\times z+|V|^{2})\). As the quadratic term \(\mathcal{O}(|V|^{2})\) dominates for large graphs, the overall complexity of the start/end node classification block is approximated as \(\mathcal{O}(|V|^{2}+|V|)\).