# Physics-Informed Graph Neural Networks for Attack Path Prediction
## Appendix E Complexity Analysis
### Path Prediction Architecture
Combined with the convolution block, the overall complexity of the \(\mathcal{M}_{2}\) architecture is dominated by the quadratic term:

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

```
classAE(torch.nn.Module):... defforward(self,x): encoded=self.encoder(x) decoded=self.decoder(encoded) returndecoded... classEncoderWithClassifier(nn.Module):... defforward(self,x,adj_tensor): batch_size,num_nodes,_=x.shape node_embeddings=self.graphage(x,adj_tensor)... latent_repr=self.encoder(node_embeddings) classification_output=self.classifier(latent_repr)... returnclassification_output
```

## Appendix F Shapley Additive Explanations (SHAP)

The SHAP algorithm [105] is a method from cooperative game theory [109], where the feature (or group of features) value for a data point acts as _players_ in a coalition. The \(j\) feature's value in model \(M\) is computed as follows:

\[g(z^{\prime})=\phi_{0}+\sum_{j=1}^{M}\phi_{j}z^{\prime}_{j} \tag{11}\]

which breaks down to the following: \(z^{\prime}\in\{0,1\}^{M}\) is the coalition vector of maximum size \(M\); this vector indicates which features are included in the coalition. Each entry \(z^{\prime}_{j}\) can either be 0 (feature \(j\) not included) or 1 (feature \(j\) included). The coalition represents a specific configuration of features being evaluated for their contributions to the model's prediction; \(\phi_{0}\) represents the average model output when no features are present. It serves as a reference point against which the contributions of the features are measured; \(\phi_{j}\in\mathbb{R}\) is the feature attribution, which quantifies the impact of each feature \(j\) on the prediction. A positive \(\phi_{j}\) indicates that the feature contributes positively to the predicted output, while a negative value indicates a negative contribution. SHAP values offer four key properties [105]: **additivity**, which allows for independent computation of each feature's contribution to the final prediction; **local accuracy**, such that values equal the difference between the expected and actual model output for a given input, providing accurate local interpretation of the model's predictions; **missingness**, attributingzero values for missing or irrelevant features; and **consistency**, as values remain unchanged unless a feature's contribution is altered, ensuring consistent interpretation across different architectures and parameters. ## References

* (1) [PERSON]; [PERSON] From information to a system. _Behav. Healthc. Tomorrow_**2000**, \(9\), 31-33. [PubMed]
* (2) [PERSON] Conception, architecture et urbanisation des systemes d'information. In _Encyclopaia Universalis_; Encyclopaedia Universalis: Boulogne-Billancour, France, 2010; pp. 1-15. * (3) [PERSON]. In _The Practical Handbook of Internet Computing_; Chapman and Hall/CRC: London, UK, 2004. * (4) [PERSON]; [PERSON]; [PERSON] Cyber risk management: History and future research directions. _Risk Manag. Insur. Rev._**2021**, _24_, 93-125. [CrossRef]
* (5) [PERSON]; [PERSON] Managing the risks associated with end-user computing. _J. Manag. Inf. Syst._**1985**, \(2\), 5-20. [CrossRef]
* (6) [PERSON]; [PERSON]; [PERSON] Risk analysis for information technology. _J. Manag. Inf. Syst._**1991**, \(8\), 129-147. [CrossRef]
* (7) [PERSON]; [PERSON]; [PERSON] A comparative framework for risk analysis methods. _Comput. Secur._**1993**, _12_, 597-603. [CrossRef]
* (8) [PERSON]; [PERSON] _Principles of Information Security_; Thomson Course Technology: Boston, MA, USA, 2009. * (9) [PERSON]; [PERSON]; [PERSON]; [PERSON] Comparing attack models for IT systems: Lockheed Martin's Cyber Kill Chain, MITRE ATT&CK Framework and Diamond Model. In Proceedings of the 2022 IEEE International Symposium on Systems Engineering (ISSE), Vienna, Austria, 24-26 October 2022; pp. 1-7. * (10) [PERSON]; [PERSON]; [PERSON] [PERSON]; [PERSON] Start thinking in graphs: Using graphs to address critical attack paths in a Microsoft cloud tenant. _Int. J. Inf. Secur._**2024**, _23_, 467-485.