  Network alignment is the problem of matching the nodes of two graphs,
maximizing the similarity of the matched nodes and the edges between them. This
problem is encountered in a wide array of applications-from biological networks
to social networks to ontologies-where multiple networked data sources need to
be integrated. Due to the difficulty of the task, an accurate alignment can
rarely be found without human assistance. Thus, it is of great practical
importance to develop network alignment algorithms that can optimally leverage
experts who are able to provide the correct alignment for a small number of
nodes. Yet, only a handful of existing works address this active network
alignment setting.
  The majority of the existing active methods focus on absolute queries ("are
nodes $a$ and $b$ the same or not?"), whereas we argue that it is generally
easier for a human expert to answer relative queries ("which node in the set
$\{b_1, \ldots, b_n\}$ is the most similar to node $a$?"). This paper
introduces two novel relative-query strategies, TopMatchings and
GibbsMatchings, which can be applied on top of any network alignment method
that constructs and solves a bipartite matching problem. Our methods identify
the most informative nodes to query by sampling the matchings of the bipartite
graph associated to the network-alignment instance.
  We compare the proposed approaches to several commonly-used query strategies
and perform experiments on both synthetic and real-world datasets. Our
sampling-based strategies yield the highest overall performance, outperforming
all the baseline methods by more than 15 percentage points in some cases. In
terms of accuracy, TopMatchings and GibbsMatchings perform comparably. However,
GibbsMatchings is significantly more scalable, but it also requires
hyperparameter tuning for a temperature parameter.
