# An Attention-Based Method for the Minimum Vertex Cover Problem on Complex Networks
## 2 Basic Concepts and Problem Definition
### Attention  
The attention mechanism was introduced by [PERSON] et al. [43] to improve the performance of encoder-decoder models for machine translation. Encoder-decoder models work on an input sequence by first building a compact and meaningful representation in a latent space and then using that representation to construct the target output sequence. Before the introduction of attention, such models worked focusing on the entire input sequence, giving equal importance to all its parts. In general, given an input sequence \(x=\{x_{1},x_{2},\ldots,x_{T}\}\), the role of the encoder is to generate an embedded representation \(h_{t}\) for each \(x_{t}\) of the sequence. Given this representation, the role of the decoder is to produce the target output \(s_{t}\) by focusing on \(h_{t}\) and on the previous output \(s_{t-1}\) of the decoder by applying a function \(a(. )\) like a feed-forward neural network, \(s_{t}=a(h_{t},s_{t-1})\). In general, we can think of feed-forward neural networks as stacked parameterized linear models to which a non-linear activation function is applied. Thus, given an input \(x\in\mathbb{R}^{N}\) and a single parameterized linear model \(h\in\mathbb{R}^{D}\), also known as hidden layer, the output \(o\in\mathbb{R}^{M}\) of a feed-forward neural network is:  
\[ \begin{split} h&=g(Wx+b)\\ o&=f(Vh+c)\end{split}  \tag{4}\]  
where \(W\in\mathbb{R}^{N\times D}\) and \(V\in\mathbb{R}^{D\times M}\) are learnable weight matrices for input-to-hidden and hidden-to-output connections, respectively, \(b\in\mathbb{R}^{D}\) and \(c\in\mathbb{R}^{M}\) are learnable bias parameters, \(g\) is a non-linear activation function, like tangent-hyperbolic function used to add non-linearity, and \(f\) is a function, like a SoftMax function for classification problem, used to convert the output of the feed-forward neural network to a conditional probability distribution over the input. In the following, we will refer to the hidden-layer transformation \(h=g(Wx+b)\) also as _dense layer_, and we will mainly use as activation function the ReLU activation function [44]. In the case of the original encoder-decoder model, this function directly uses \(h_{t}\) as it comes out from the encoder without weighing it with respect to a score value that represents the relevance of that part of the input within the sequence. To assign weights to take care of differences within the input sequence, [PERSON] suggests computing a _context vector_ to be fed to the decoder at each timestamp. Equation (5) shows the procedure to compute this context vector \(c_{t}\). \[ \begin{split} e_{t,i}&=a(s_{t-1},h_{i})\\ \alpha_{t,i}&=softmax(e_{t,i})\\ c_{t}&=\sum_{i=1}^{T}\alpha_{t,i}h_{i}\end{split}  \tag{5}\]  
First, it is necessary to calculate an _alignment scores_\(e_{t,i}\), computed applying a function \(a(. )\), like a feed-forward neural network, to each encoded hidden state \(h_{i}\) and to the previous decoder output \(s_{t-1}\), so that the more relevant input of the sequence is in producing the current output (i.e., the more an input is _aligned_ to an output), the higher its value is. The context vector \(c_{t}\) is then computed by a weighted sum of all \(T\) encoder hidden states, where the weights \(\alpha_{t,i}\) are obtained by applying a SoftMax normalization to the alignment score. In this way, instead of passing directly the hidden state \(h_{i}\) together with the previous decoder output state \(s_{t-1}\) to the decoder to compute the output, the decoder is fed with a vector that represents the input but which is scaled according to its importance (expressed by \(\alpha_{t,i}\)) in the input sequence to determine the output. This mechanism has been reformulated into a general form that applies to any sequence-to-sequence task [45], making use of three main components, namely _queries_, _keys_ and _values_, such that query corresponds to the previous decoder output \(s_{t-1}\), while values and keys to the encoded inputs \(h_{i}\).