# An Attention-Based Method for the Minimum Vertex Cover Problem on Complex Networks
## 2 Basic Concepts and Problem Definition
On the left-hand graph, the optimal solution is composed of nodes 1 and 4; on the right-hand of nodes 1 and 3. The difference in the result is determined by the different way edges are ordered and picked to compute the final solution. In general, iterative algorithms (either approximated or exact) do not pick edges or nodes completely at random, but they order them according to some heuristic or criterion as in [37; 39; 40]. However, it is clear that, according to these approaches, the order according to which edges are picked from the initial set highly influences the final result since the fact that a node is already part of the final solution has an impact on the fact that another node should be part of it. In our example in Figure 1, the fact that node 3 is already part of the solution implies that node 4 should not be part of it and vice versa. Informally, this means that, given an ordered sequence of nodes, the probability that a node is part of the final solution depends on the probability that the previous nodes in the sequence are already part of the solution. Thus, given a sequence of nodes, \(\{x_{1},\ldots,x_{n}\}\), we want to model the probability of the event \"\(x_{i}\) is part of the covering set\" for each \(i\in n\), assuming that this event is conditioned to each event \"\(x_{j}\) is part of the covering set\" for each \(j<i\in n\). Supposing that each event can be described as a random variable \(x_{i}\), what we want to model, according to probability theory, is the joint probability distribution of all the random variables \(p(x_{1},\ldots,x_{n})=p(x_{1}\cap\ldots\cap x_{n})\), which according to the chain rule, can be modeled as \(p(x_{1}\cap\ldots\cap x_{n})=p(x_{1})p(x_{2}|x_{1})p(x_{3}|x_{2}\cap x_{1}) \ldots p(x_{n}|x_{1}\cap x_{2}\cap\ldots\cap x_{n-1})\). Moreover, we can consider that the probability distribution of the covering nodes can be represented as a sequence of nodes ordered according to their probability of belonging to the covering set. Let us call this sequence \(\mathcal{C}^{\mathcal{P}}\). The probability of belonging to the covering set is, of course, determined by the representation of nodes itself. Let us call it \(\mathcal{P}\). Indeed, we assume that each node \(x_{i}\), with index \(i\), can be represented as a vector \(P_{i}\) according to a parametric function that maps each input node to a latent representation \(g(x_{i};\theta)=P_{i}\). According to this, the previous conditioned probability distribution is evaluated on a sequence of nodes conditioned by their representation \(\mathcal{P}\). We can now formally define the problem that we want to solve. **Problem 1** (Minimum Vertex Cover Biased Nodes Embedding). : _Given a graph \(G=(N,E)\), with \(|N|=n\) and a training pair \((\mathcal{P},\mathcal{C}^{\mathcal{P}})\), where \(\mathcal{P}=(P_{1},\ldots,P_{n})\) is a sequence of node embeddings, representing the latent representation of nodes, and \(\mathcal{C}^{\mathcal{P}}=(C_{1},\ldots,C_{m(\mathcal{P})})\) is a sequence of \(m(\mathcal{P})\) nodes, we want to model the conditional probability \(p(\mathcal{C}^{\mathcal{P}}|\mathcal{P};\theta)\) using a parametric model to estimate the terms of the probability chain rule_  
\[p(\mathcal{C}^{\mathcal{P}}|\mathcal{P};\theta)=\prod_{i=1}^{m(\mathcal{P})}p _{\theta}(C_{i}|C_{1},\ldots,C_{i-1},\mathcal{P};\theta) \tag{2}\]  
_learning the parameter of the model by maximizing the conditional probabilities for the training set_  
\[\theta^{*}=\operatorname*{argmax}_{\theta}\sum_{\mathcal{P},\mathcal{C}^{ \mathcal{P}}}\log p(\mathcal{C}^{\mathcal{P}}|\mathcal{P};\theta) \tag{3}\]  
In this way, we reduce the MVC problem to a binary classification problem, i.e., given a graph as input, we want to assign to each node of the graph a probability term such that the node is assigned to the covering set if and only if the value of the probability term is higher than a given threshold value (e.g., 0.5).