# An Attention-Based Method for the Minimum Vertex Cover Problem on Complex Networks
## 3 Complement Information Based Attention Network
### Attention with Complement Information  
The implementation of the attention mechanism follows the schema represented in Figure 3. To implement Equation (6) as described in [45], we directly use the adjacency matrix \(A\) to compute \(Q\) and \(V\) by first learning \(H\), as the sum of a non-linear transformation of \(A\) (which produces an embedded representation of \(A\)) and the positional encoding of the input nodes, and then by learning the weights of another linear transformation separately for \(Q\) and \(V\). To produce the \(K\) matrix, instead, we apply the same procedure to \(H^{\prime}\) obtained from the complement of the adjacency matrix \(\overline{A}=J_{n,n}-A\), where \(J_{n,n}\) is a \(n\times n\) matrix with all entries equal to 1. The size of the matrices is kept unchanged so that each row can be referenced to a representation of the node in that position. Equation (10) better describes how matrices \(Q\), \(K\), and \(V\) are computed by integrating the complement of the adjacency matrix.  
\[\begin{split}& H=ReLu(W_{d}A+b_{d})+(W_{p}A+b_{p})\\ & H^{\prime}=ReLu(W_{d^{\prime}}\overline{A}+b_{d^{\prime}})+(W_{ p^{\prime}}\overline{A}+b_{p^{\prime}})\\ & V=W_{v}H+b_{v}\\ & Q=W_{q}H+b_{q}\\ & K=W_{k}H^{\prime}+b_{k}\end{split} \tag{10}\]  
In Equation (10), we can see that each transformation (linear or non-linear) has its own matrix of weights and biases, defined by the subscripts, which, thus, is learned separately.  
In this way, following the intuition described in Section 3.1, we expect that when computing the alignment score \(e_{q,k_{i}}=\frac{QK^{T}}{\sqrt{d_{k}}}\) by applying the element-wise product, for each pair of nodes \(i,j\) we compute a similarity score between node \(i\) and \(j\) which is much higher the fewer number of nodes the neighborhood sets of \(i\) and \(j\) have in common. In this way, the general DL mechanism is customized to reflect the behavior of common heuristics to build the MVC.  
Over the alignment score, a SoftMax function is computed to normalize it (\(\alpha_{q,k_{i}}=softmax(e_{q,k_{i}})\)) and, finally, to produce a weighted representation, they are multiplied by the \(V\) matrix as in Equation (6).  
The output is a matrix of attention weights for each element of each feature vector (one per node) of the input matrices \(H\) and \(H^{\prime}\). This matrix is composed of attention coefficients that indicate which node must be assigned more energy for the final computation. Finally, a context vector \(u_{i}\) for each node \(i\) is produced by summing all the attention coefficients of each node representation (\(u_{i}=\sum_{i}\alpha_{q,k_{i}}v_{k_{i}}\)).  
Thus, given a \(n\times n\) adjacency matrix \(A\), where each row represents a node of the input graph, the matrix of context vectors \(U=softmax(\frac{Q\kappa^{T}}{\sqrt{d_{k}}})V\) is a \(n\times m\) matrix, where each row represent an m-dimensional embedding \(u_{i},\ i\in(1,\dots,n)\) of the corresponding input node, built considering not only its local features but also its importance with respect to the other nodes in building the MVC.  
This vector is then passed to a dense layer (Figure 2), composed of a stack of three non-linear transformations as in Equation (4), with ReLu activation function that produces as output an embedding \(P_{i},\ i\in(1,\dots,n)\) of the corresponding input node.