# An Attention-Based Method for the Minimum Vertex Cover Problem on Complex Networks
## 3 Complement Information Based Attention Network
### Iterative Algorithm
To cope with issues 1 and 2, we proposed a methodology that makes use of what we called Attention with Complement Information, i.e., a mechanism of attention which first of all is applied over graphs adjacency matrix to use both local and global information, and then that takes as input not only the matrix itself but also the complement of the matrix, following the intuition, commonly implied also by many state-of-the-art heuristics, that in order to identify candidate nodes to a covering set, it could be useful to know their interaction with other nodes and that the complement of such interaction may provide a better scoring when two nodes have similar interactions. We then use the output of such attention mechanism, properly transformed, as input to an LSTM-based decoder network followed by a SoftMax activation layer to produce the final probability distribution. We showed that our methodology can outperform not only a common 2-factor approximation algorithm for MVC but also a widely used state-of-the-art heuristic known as FastVC both on low-density graphs and on higher-density graphs. Moreover, if our approach is relatively slower with low-density graphs with respect to both the 2-factor approximation algorithm and the FastVC heuristic, it scales much better than FastVC on higher-density graphs. This represents a great advantage, also meaning that for MVC tasks on graphs of comparable size to the ones used to train our neural model, our methodology should be preferred to other state-of-the-art approaches. Finally, we also proved that our attention mechanism with complement information manages to draw a proper representation of the nodes according to the combinatorial nature of the MVC problem. This is extremely important since it demonstrates that our work manages to address the three main issues of the DL-based approach for combinatorial optimization over graphs. As far as we know, this makes our proposal one of the firsts to address these main challenges successfully. Nonetheless, another advantage of our methodology is that we provide a new validated method to build node embeddings in a meaningful way. The embeddings produced, indeed, could be used and tested also for different task-related MVC problems. In this research, we have explained that there is a strong similarity between the iterative algorithm proposed to build the final solution of our method and the iterative algorithm used by FastVC to initialize its solution. However, in FastVC, after initializing the solution, the authors propose to refine the solution by changing the nodes in the covering set according to a cost-effective heuristic called Best from Multiple Selections (BMS). Thus, a possible future direction of this work could be that of understanding how, by applying the BMS heuristic, we could improve the results and in which time. We consider this work as a step towards a new family of solvers for NP-hard problems that leverages and customize DL properly, and, in particular, we will try to extend the results of such work also on the less explored context of temporal networks, where many combinatorial NP-hard problems, like the minimum timeline cover [27; 54], do not have an approximate solution. Conceptualization, G.L., R.D., S.M. and I.Z. ; methodology, G.L. and I.Z. ; software, G.L. ; validation, R.D., S.M. and I.Z. ; formal analysis, G.L. and I.Z. ; investigation, G.L. ; resources, G.L., R.D. and I.Z. ; data curation, G.L. and R.D. ; writing--original draft preparation, G.L. ; writing--review and editing, R.D., S.M. and I.Z. ; supervision, S.M. and I.Z. ; project administration, S.M. and I.Z. All authors have read and agreed to the published version of the manuscript. This research received no external funding. Data Availability StatementData are contained within this article. The authors declare no conflict of interest. ## References

* [PERSON] (2019) [PERSON] A graph theoretical approach for node covering in tree based architectures and its application to bioinformatics. _Netw. Model. Anal. Health Inf. Bioinform._**2019**, \(8\), 12.