# GRAph ALigner (GRAAL)

GRAaph ALigner (GRAAL) is an algorithm for global network alignment that is based solely on network topology. It aligns two networks $G$ and $H$ by producing an alignment that consists of a set of ordered pairs $(x,y)$ , where $x$ is a node in $G$ and $y$ is a node in $H$ . GRAAL matches pairs of nodes originating in different networks based on their graphlet degree signature similarities, where a higher similarity between two nodes corresponds to a higher topological similarity between their extended neighborhoods (out to distance 4). GRAAL produces global alignments, i.e., it aligns each node in the smaller network to exactly one node in the larger network. The matching proceeds using a technique analogous to the "seed and extend" approach of the popular BLAST algorithm for sequence alignment: it first chooses a single "seed" pair of nodes (one node from each network) with high graphlet degree signature similarity. It then expands the alignment radially outward around the seed as far as practical using a greedy algorithm (see [Kuchaiev et al., 2010] for details).
When aligning two graphs $G(V,E)\!$ and $H(U,F)$ , GRAAL first computes costs of aligning each node $v$ in G with each node $u$ in $H$ . The cost of aligning two nodes takes into account the graphlet degree signature similarity between them, modified to reduce the cost as the degrees of both nodes increase, since higher degree nodes with similar signatures provide a tighter constraint than correspondingly similar low degree nodes. In this way, GRAAL align the densest parts of the networks first. Let $deg(v)$ be the degree of a node $v$ in network $G$ , let $max_{deg(G)}$ be the maximum degree of nodes in $G$ , let $S(v,u)$ be the graphlet degree signature similarity of nodes $v$ and $u$ , and let $\alpha$ be a parameter in [0, 1] that controls the contribution of the node signature similarity to the cost function (that is, $1-\alpha$ is the parameter that controls the contribution of node degrees to the cost function), then the cost of aligning nodes $v$ and $u$ is computed as:
$C(v,u)=2-((1-\alpha )\times {\frac {deg(v)+deg(u)}{max\_deg(G)+max\_deg(H)}}+\alpha \times S(v,u))$ .
A cost of $0$ corresponds to a pair of topologically identical nodes $v$ and $u$ , while a cost close to $2$ corresponds to a pair of topologically different nodes.