Several applications call to align the nodes of two graphs in a way that minimizes a distance function.In practicality, the graphs to be aligned often have unequal orders (i.e., numbers of vertices) and no auxiliary labels or attributes; we refer to this problem as partial unlabeled graph alignment.Some proposals to address this problem add dummy nodes to the smaller graph to even the orders and align the ensuing graphs or employ embeddings such as GNNs, which yield ad hoc node representations.Unfortunately, as we show, an optimal solution to equal-order graph alignment using dummy nodes does not imply an optimal solution to partial graph alignment.To address this deficiency, in this paper, we propose Alpine, a Partial Unlabeled Graph Alignment algorithm that solely peruses the graphs' adjacency matrices, guided by a tailored objective function inspired by best-of-breed shape matching techniques and a state-ofthe-art optimization method.Extensive experiments demonstrate that Alpine consistently surpasses state-of-the-art graph alignment methods in solution quality across all benchmark datasets.

The Voter model is a well-studied stochastic process that models the invasion of a novel trait A (e.g., a new opinion, social meme, genetic mutation, magnetic spin) in a network of individuals (agents, people, genes, particles) carrying an existing resident trait B. Individuals change traits by occasionally sampling the trait of a neighbor, while an invasion bias δ ≥ 0 expresses the stochastic preference to adopt the novel trait A over the resident trait B. The strength of an invasion is measured by the probability that eventually the whole population adopts trait A, i.e., the fixation probability. In more realistic settings, however, the invasion bias is not ubiquitous, but rather manifested only in parts of the network. For instance, when modeling the spread of a social trait, the invasion bias represents localized incentives. In this paper, we generalize the standard biased Voter model to the positional Voter model, in which the invasion bias is effectuated only on an arbitrary subset of the network nodes, called biased nodes. We study the ensuing optimization problem, which is, given a budget k, to choose k biased nodes so as to maximize the fixation probability of a randomly occurring invasion. We show that the problem is NP-hard both for finite δ and when δ → ∞ (strong bias), while the objective function is not submodular in either setting, indicating strong computational hardness. On the other hand, we show that, when δ → 0 (weak bias), we can obtain a tight approximation in O(n^2ω ) time, where ω is the matrix-multiplication exponent. We complement our theoretical results with an experimental evaluation of some proposed heuristics.