## 2 Preliminaries  
Given two simple graphs \(G_{1}=(V_{1},E_{1})\) and \(G_{2}=(V_{2},E_{2})\), an alignment \(a:V_{1}\to V_{2}\) is a partial injective function from \(V_{1}\) to \(V_{2}\). As such, we have that an alignment relates every node in \(V_{1}\) to at most one node in \(V_{2}\) and that conversely every node in \(V_{2}\) has at most one counterpart in \(V_{1}\). An alignment is assigned a real-valued score using an additive scoring function \(s\) defined as follows:  
\[s(a)=\sum_{v\in V_{1}}c(v,a(v))+\sum_{\begin{subarray}{c}v,w\in V_{1}\\ v<w\end{subarray}}w(v,a(v),w,a(w)) \tag{1}\]  
where \(c:V_{1}\times V_{2}\rightarrow\mathbb{R}\) is the score of aligning a pair of nodes in \(V_{1}\) and \(V_{2}\) respectively. On the other hand, \(w:V_{1}\times V_{2}\times V_{1}\times V_{2}\rightarrow\mathbb{R}\) allows for scoring topological similarity. The problem of global pairwise network alignment (GNA) is to find the highest scoring alignment \(a^{*}=\arg\max s(a)\). Figure 1 shows an example:  
NP-hardness of GNA follows from a simple reduction from the decision problem Clique, which asks whether there is a clique of cardinality at least \(k\) in a given simple graph \(G=(V,E)\)[20]. The corresponding GNA instance concerns the alignment of the complete graph of \(k\) vertices \(K_{k}=(V_{k},E_{k})\) with \(G\) using the scoring function \(s(a)=|\{(v,w)\in E_{k}\mid(a(v),a(w))\in E\}|\). Since an alignment is injective, there is a clique of cardinality at least \(k\) if and only if the cost of the optimal alignment is \(\binom{k}{2}\). The close relationship of GNA with the quadratic assignment problem is more easily observed when formulating GNA as a mathematical program. Throughout the remainder of the text, we use variables \(i,j\in\{1,\ldots,|V_{1}|\}\) and \(k,l\in\{1,\ldots,|V_{2}|\}\) to denote nodes in \(V_{1}\) and \(V_{2}\), respectively. Let \(C\) be a \(|V_{1}|\times|V_{2}|\) matrix such that \(c_{ik}=c(i,k)\) and let \(W\) be a \(|V_{1}|\times|V_{2}|\times|V_{1}|\times|V_{2}|\) matrix whose entries \(w_{ikjl}\) correspond to interaction scores \(w(i,k,j,l)\). Now, we can formulate GNA as  
\[\max_{x} \sum_{i,k}c_{ik}x_{ik}+\sum_{\begin{subarray}{c}i,j\\ i<j\end{subarray}}\sum_{\begin{subarray}{c}k,l\\ k\
eq l\end{subarray}}w_{ikjl}x_{ik}x_{jl}\] (IQP) s.t. \[\sum_{l}x_{jl}\leq 1 \forall j \tag{2}\] \[\sum_{j}x_{jl}\leq 1 \forall l\] (3) \[x_{ik}\in\{0,1\} \forall i,k \tag{4}\]  
Figure 1: Example of a network alignment. With the given scoring function, the alignment has a score of \(4+40=44\).  
where the decision variable \(x_{ik}\) indicates whether the \(i\)-th node in \(V_{1}\) is aligned with the \(k\)-th node in \(V_{2}\). The above formulation shares many similarities with [PERSON]'s formulation [21] of the QAP. However, instead of finding an assignment we are interested in finding a matching, which is reflected in Constraints (2) and (3) being inequalities rather than equalities. As can be seen in Equation (1), we only consider the upper triangle of \(W\) rather than the entire matrix. An analogous way of looking at this is to consider \(W\) to be symmetric. This is usually not the case for QAP instances. In addition, due to the fact that biological input graphs are typically sparse and the restriction of possible matchings to a few candidates per node on average, we have that \(W\) is sparse as well. These differences allow us to come up with an effective method of solving the problem as we will see in the following.