# Physics-Informed Graph Neural Networks for Attack Path Prediction
## 2 Materials and Methods
### Architecture
#### 2.4.1 Graph Convolution Block  
Graph Convolutional Networks (GCNs) [96] are neural networks designed for learning embeddings in graphs. Graph convolution was introduced in [97] as a way to learn graph structures using neural networks. GraphSAGE [98] is a specific GCN architecture which relies on sample-and-aggregate convolution (SAGEConv) layers to efficiently learn the embeddings on directed graphs. During inference, for each node \(v\in V\), the SAGEConv first aggregates feature representations from its immediate neighbors via a learnable aggregation function. The aggregate is then concatenated with the node's own feature vector. The resulting vector is then processed by a learnable fully connected layer and an element-wise non-linear activation function. The output from the final layer serves as the learned embedding of \(v\). In this paper, we use a slightly different version of the SAGEConv original implementation [98], which employs batch matrix multiplication (BMM) for fast aggregation, detailed in Algorithm 1 and illustrated in Figure 5.  
```
1:Input: Adjacency tensor \(A\in\mathbb{R}^{B\times|V|\times|V|\times d}\)
2:Input: Signal tensor \(F\in\mathbb{R}^{B\times|V|\times p}\)
3: Initialize \(\mathcal{H}^{(0)}\gets F\), \(\quad\mathcal{H}^{\prime}\leftarrow\text{zero matrix}\)
4:for\(i\gets 1\) to \(d\)do
5: Inverse degree matrix: \(D_{i}^{-1}\in\mathbb{R}^{B\times|V|\times|V|}\) for edge type \(A_{i}\)
6: Aggregate: \(\mathcal{H}^{\prime}\leftarrow\mathcal{H}^{\prime}_{i-1}+\left(w_{i}\cdot \left(D_{i}^{-1}A_{i}\cdot\mathcal{H}^{(0)}\right)\right)\)
7:end
8:Concatenate: \(\mathcal{H}^{\prime}\leftarrow\left(\mathcal{H}^{0}\oplus\mathcal{H}^{\prime}/d\right)\)
9:Transform and Activate: \(\mathcal{H}^{(1)}\gets f(W\cdot\mathcal{H}^{\prime})\)
10:Output: Final embeddings \(\mathcal{H}^{(1)}\in\mathbb{R}^{B\times|V|\times H}\)
```  
**Algorithm 1** Inference with BMM SAGEConv layer  
In our path prediction architecture, the first block consists of two BMM SAGEConv layers (see Figure 4). During inference, both \(F\) and \(A\) are input into the first BMM SAGEConv layer. \(F\) is used to retrieve \(h_{v}^{(0)}\), and \(A\) is used to identify the neighbors \(\mathcal{N}(v)\) of \(v\). The trained layer produces the first embedding tensor \(\mathcal{H}^{(1)}\). This tensor is then passed through an activation function, specifically Rectified Linear Unit (ReLU). The Rectified Linear Unit (ReLU) is a standard non-linear function used in deep learning frameworks [64]; the function is defined as \(f(x)=\max(0,x)\). After activation, the signal is passed through the second layer along with \(A\). The second BMM SAGEConv generates the final embedding tensor, \(\mathcal{H}=\mathcal{H}^{(2)}\). During training, each BMM SAGEConv layer is followed by a dropout  
Figure 5: Schematic representation of the BMM SAGEConv; LINEAR blocks are trainable parameters, BMM designates batch matrix multiplication used for aggregation operation, and \(\oplus\) designates the concatenation operation.  
layer to prevent overfitting. The layer randomly zeroes some of the elements of the input tensor with a probability \(p\). For details on the block implementation and to maintain section conciseness, please refer to the replication package. For algorithmic complexity analysis, see Appendix E.  
The BMM SAGEConv layer \(k\), given \(\mathcal{H}^{(0)}=F\), can be written compactly as follows:  
\[\mathcal{H}^{(k)}=f^{(k)}\Bigg{(}\Bigg{(}\mathcal{H}^{(k-1)}\oplus\Bigg{(} \frac{1}{d}\sum_{i=1}^{d}w_{i}^{(k)}\cdot\Big{[}D_{i}^{-1}A_{i}\cdot\mathcal{H }^{(k-1)}\Big{]}\Bigg{)}\Bigg{)}\cdot W^{(k)}\Bigg{)} \tag{1}\]  
where \(\oplus\) designates the concatenation operation, \(f(\cdot)\) designates the ReLU activation function, \(w_{i}^{(k)}\) designates the \(i\)-th type edge learnable weight matrix, and \(W^{(k)}\) designates the learnable weight matrix for the \(k\)-th layer.