# An Attention-Based Method for the Minimum Vertex Cover Problem on Complex Networks
## 3 Complement Information Based Attention Network
### Iterative Algorithm
It is important to note that our methodology only fits for graphs with no more than 2000 nodes. This is not a strong limit for many real-world applications like network design, sensor network, resource allocation, or text tasks [2; 4; 5]. To test the methodology with larger graphs, it would be necessary to retrain the neural model by modifying the maximum

\begin{table}
\begin{tabular}{l l l l l l l l l} \hline \hline
**Graph** & \(|N|\) & \(|E|\) & \begin{tabular}{l} **2-Factor** \\ **Cover** \\ \end{tabular}  & \begin{tabular}{l} **2-Factor** \\ **Time** \\ \end{tabular}  & \begin{tabular}{l} **ACI** \\ **Cover** \\ \end{tabular}  & \begin{tabular}{l} **ACI** \\ **Time** \\ \end{tabular}  & \ \begin{tabular}{l} **FastVC** \\ **Cover** \\ \end{tabular}  & \begin{tabular}{l} **FastVC** \\ **Time** \\ \end{tabular}  \\ \hline C2000-5 & 2000 & 999,836 & 1997 & 0.18 & 1989 & 0.6 & 1993 & 2.80 \\ C250-9 & 250 & 27,984 & 248 & 0.00 & 246 & 0.22 & 24 & 0.20 \\ C500-9 & 500 & 112,332 & 499 & 0.02 & 496 & 0.26 & 498 & 0.32 \\ C125-9 & 125 & 6963 & 124 & 0.00 & 122 & 0.20 & 121 & 0.05 \\ MANN-a27 & 378 & 70,551 & 375 & 0.01 & 375 & 0.24 & 376 & 0.22 \\ MANN-a45 & 1035 & 533,115 & 1033 & 0.10 & 1032 & 0.44 & 1033 & 1.44 \\ MANN-a9 & 45 & 918 & 43 & 0.00 & 43 & 0.20 & 43 & 0.03 \\ brock800-1 & 800 & 207,505 & 798 & 0.04 & 794 & 0.29 & 793 & 0.55 \\ c-fat200-1 & 200 & 1534 & 199 & 0.00 & 182 & 0.20 & 182 & 0.04 \\ c-fat200-5 & 200 & 8473 & 199 & 0.00 & 197 & 0.20 & 197 & 0.06 \\ gen400-p-9-55 & 400 & 71,820 & 399 & 0.01 & 396 & 0.24 & 397 & 0.22 \\ gen400-p-9-65 & 400 & 71,820 & 399 & 0.01 & 396 & 0.24 & 396 & 0.23 \\ hamming10-2 & 1024 & 518,656 & 1022 & 0.10 & 1022 & 0.43 & 1022 & 1.40 \\ hamming8-4 & 256 & 20,864 & 248 & 0.00 & 240 & 0.21 & 248 & 0.10 \\ hamming6-2 & 64 & 1824 & 62 & 0.00 & 62 & 0.20 & 62 & 0.04 \\ hamming6-4 & 64 & 704 & 56 & 0.00 & 52 & 0.20 & 56 & 0.03 \\ johnson8-2-4 & 28 & 210 & 25 & 0.00 & 21 & 0.20 & 25 & 0.03 \\ johnson8-4-4 & 70 & 1855 & 67 & 0.00 & 65 & 0.20 & 65 & 0.04 \\ keller4 & 171 & 9435 & 167 & 0.00 & 156 & 0.21 & 163 & 0.06 \\ keller5 & 776 & 225,990 & 772 & 0.04 & 760 & 0.30 & 766 & 0.61 \\



size of the graph to be expected as input. However, we did not explore this aspect of the research further. ### Nodes Representation

Another important aspect of our approach concerns the capability of the network, particularly of the ACI-based method, to produce a good representation of the nodes with respect to the optimization target defined by the MVC problem. To understand whether the network can perform a proper mapping of the embedded input nodes into a d-dimensional space, we plot some points considering the representation of the nodes as obtained from the output of the ACI layer of the network, namely the context vector \(U\). Since the network has been trained to produce an encoding embedding in a 32-dimensional space, we only visualize a scatterplot of the nodes by taking two of the 32 components at a time. We only visualize the results with respect to the first four components since the behavior is similar for the others as well. In Figure 4, we can see the representation of the nodes of a graph with 25 nodes and 50 edges. The orange points are the points associated with covering nodes according to the exact solution, while the blue ones are those that do not correspond to covering nodes. In general, we can see that the network is able to map the points in a space where covering nodes and non-covering nodes belong to different regions (almost linearly separable) and with a clear ordering. This representation is built considering node features so that similar nodes are closer in this representation space. Figure 5 shows an example of this. In the picture, we can see

Figure 4: Example of nodes representations of a graph \(G=(25,50)\) as produced by the ACI layer with respect to the first four components taken in pairs.