AvAtar: Learning to Align via Active Optimal Transport

# AvAtar: Learning to Align via Active Optimal Transport
Source: [https://arxiv.org/html/2605.24395](https://arxiv.org/html/2605.24395)
###### Abstract

Alignment plays a fundamental role in many machine learning problems, such as multi\-network analysis, multimodal learning, and point cloud registration\. Recent works increasingly leverage optimal transport \(OT\) for distributional alignment, whose effectiveness largely depends on sparse supervision that is hard or costly to obtain in practice\. Existing works, however, largely overlook how to actively acquire high\-quality supervision to improve their alignment performance under OT frameworks\. In this paper, we propose a principledactivealignment framework for optimal transport alignment calledAvAtar\. We quantify the informativeness of a candidate by measuring its gradient\-based impact on the global alignment result, computed as the gradient propagation from the global alignment result to all possible supervisions of the candidate through the entropy\-regularized OT formulation\. While differentiating through OT is challenging given its constrained nature, we leverage the adjoint\-state method to reformulate the computation to a linear system solvable by the conjugate gradient method with linear complexity and guaranteed convergence\. By encoding the global alignment result via effective utility functions,AvAtaris applicable to general alignment problems under the OT framework\. Extensive experiments on three representative alignment tasks demonstrate the effectiveness, scalability, and generalizability of the proposedAvAtar\.

Machine Learning, ICML

## 1Introduction

Alignment is a critical steppingstone behind a wide range of machine learning problems, including but not limit to multi\-network analysis\(Duet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib19); Yanet al\.,[2022](https://arxiv.org/html/2605.24395#bib.bib10); Tanget al\.,[2023](https://arxiv.org/html/2605.24395#bib.bib7); Wanget al\.,[2023](https://arxiv.org/html/2605.24395#bib.bib68); Yuet al\.,[2025a](https://arxiv.org/html/2605.24395#bib.bib5); Zenget al\.,[2023b](https://arxiv.org/html/2605.24395#bib.bib111),[2024b](https://arxiv.org/html/2605.24395#bib.bib57),[2024a](https://arxiv.org/html/2605.24395#bib.bib109),[2025c](https://arxiv.org/html/2605.24395#bib.bib24)\), multimodal and cross\-domain learning\(Yilmazet al\.,[2019](https://arxiv.org/html/2605.24395#bib.bib20); Chenet al\.,[2020](https://arxiv.org/html/2605.24395#bib.bib11); Chenget al\.,[2022](https://arxiv.org/html/2605.24395#bib.bib107); Xuet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib52); Yooet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib72); Ninget al\.,[2025](https://arxiv.org/html/2605.24395#bib.bib21)\), and point cloud registration\.\(Yuet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib15),[2023](https://arxiv.org/html/2605.24395#bib.bib17); Haitmanet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib18)\)\. The general goal of these problems is to identify meaningful correspondence between two sets of data points, which facilitate various downstream machine learning tasks\. For example, aligning nodes from different networks enables personalized recommendation across social platforms and helps fraud detection across transaction networks\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1); Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2)\)\. Aligning entities from different data modalities, e\.g\., image\-text matching, enables automatic labeling of cross\-modal data used for large\-scale pre\-training of multimodal foundation models\(Hanet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib106); Ganet al\.,[2022](https://arxiv.org/html/2605.24395#bib.bib96); Lianget al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib97); Bartanet al\.,[2025](https://arxiv.org/html/2605.24395#bib.bib80); Weiet al\.,[2026](https://arxiv.org/html/2605.24395#bib.bib76)\)\.

Recently, optimal transport \(OT\)\(Gabriel and Marco,[2019](https://arxiv.org/html/2605.24395#bib.bib22)\)has been increasingly adopted as an effective tool for solving alignment problems in general\. By associating two sets of objects to be aligned \(e\.g\., nodes from two networks\) with two discrete probability distributions serving as the marginal constraints, OT\-based alignment methods infer object\-level alignment from the solved transport plan under carefully crafted cost function for specific tasks\. Empowered by informative cost function and constrained optimization, OT\-based methods naturally learn robust and deterministic alignment from a global view\(Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2),[a](https://arxiv.org/html/2605.24395#bib.bib5)\), and have demonstrated remarkable performance across diverse alignment tasks\(Chenet al\.,[2020](https://arxiv.org/html/2605.24395#bib.bib11); Qinet al\.,[2023](https://arxiv.org/html/2605.24395#bib.bib16); Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2)\)\. Despite their success, Figure[1](https://arxiv.org/html/2605.24395#S1.F1)shows that OT\-based alignment approaches are sensitive to the quantity and quality of supervisions\(Yuet al\.,[2025a](https://arxiv.org/html/2605.24395#bib.bib5)\), yet obtaining high\-quality supervision is costly in practice\(Zhouet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib8); Ganet al\.,[2022](https://arxiv.org/html/2605.24395#bib.bib96); Liuet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib58); Liet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib39)\)\. To date, few works have investigated how to actively acquire high\-quality supervision in weakly supervised or unsupervised settings to effectively improve the performance of OT\-based methods\.

Although there exists sparse literature on active alignment, they bear the following three key limitations for OT\-based methods\. Firstly \(Limitation \#1\), existing active alignment methods are not tailored to OT thus fail to utilize key components behind OT\-based alignment, such as the cost function and marginal constraints, which directly affect the alignment performance\(Malmiet al\.,[2017](https://arxiv.org/html/2605.24395#bib.bib9); Chenget al\.,[2019](https://arxiv.org/html/2605.24395#bib.bib23); Zhouet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib8)\)\. Secondly \(Limitation \#2\), there lacks a principled method to quantify how newly acquired supervision would propagate through the OT formulation, making it difficult to assess the direct impact of a query on the alignment results\(Malmiet al\.,[2017](https://arxiv.org/html/2605.24395#bib.bib9); Chenget al\.,[2019](https://arxiv.org/html/2605.24395#bib.bib23)\)\. Thirdly \(Limitation \#3\), prior efforts on active alignment mainly focus on designing task\-specific query strategies\(Renet al\.,[2019](https://arxiv.org/html/2605.24395#bib.bib95); Zhouet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib8)\), such as active consistency\-based network alignment methods, which are not readily generalizable to other alignment methods \(e\.g\., OT\-based methods\) or alignment tasks \(e\.g\., cross\-domain alignment\)\.

![Refer to caption](https://arxiv.org/html/2605.24395v1/x1.png)\(a\)Network Alignment
![Refer to caption](https://arxiv.org/html/2605.24395v1/x2.png)\(b\)Image\-Text Grounding

Figure 1:Sensitivity of active OT\-based alignment methods w\.r\.t\. the quality and quantity of supervision on network alignment and image\-text grounding\. Observations:\(1\. Quantity\)The performance of OT\-based methods improve significantly by up to15%15\\%with increased supervision level\.\(2\. Quality\)Under the same number of supervision, the performance of OT\-based methods can differ significantly \(up to 7%\) by different query strategies, e\.g\., the proposedAvAtar\-L2L\_\{2\}\(red\) vs\. Random \(blue\)\.In this paper, we address these limitations by proposing a principled active alignment framework based on optimal transport, calledAvAtar\.AvAtaris designed intrinsically for OT\-based alignment, which evaluates the informativeness of candidates by their posterior query impact on the global alignment results of OT, comprehensively utilizing key elements of OT to select the best candidates to query \(Limitation \#1\)\. To quantify the posterior query impact of a candidate,AvAtarcomputes the gradient propagation from the global alignment result to all possible supervision signals of the candidate through the entropy\-regularized OT formulation, capturing exactly how a new label would affect OT\-based alignment through gradients \(Limitation \#2\)\. However, a major challenge lies in differentiating through the OT formulation, since the transport plan is defined implicitly as the solution of a large\-scale constrained optimization problem\. To tackle this, we leverage the adjoint\-state method to reformulate the computation of gradient\-based impact to a linear system which can be solved efficiently via the conjugate gradient method with linear complexity and guaranteed convergence\. By encoding the global alignment results via effective utility functions defined over the transport plan of OT,AvAtaris applicable to OT\-based alignment methods across diverse alignment tasks with minimal modification \(Limitation \#3\)\.

To validate the effectiveness ofAvAtar, we conduct comprehensive experiments across three representative alignment tasks, including network alignment \(NA\) and two cross\-domain alignment \(CDA\) tasks: image\-text retrieval and image\-text grounding\. Extensive experiments covering 8 datasets, 4 OT\-based alignment algorithms, and 9 baseline active learning methods demonstrate thatAvAtarconsistently outperform existing active learning approaches under the same query budget\. We also show empirically thatAvAtarachieves a good balance between alignment performance and efficiency, making it applicable to large\-scale alignment problems\.

Our main contributions are summarized as follows:

- •Problem\.To our best knowledge, we are the first to formalize the timely and important problem of active learning for OT\-based alignment\.
- •Method\.We propose a novel methodAvAtarto quantify the informativeness of candidates by their impact on the alignment results, measured by gradient propagation through the OT formulation\.
- •Analysis\.We provide extensive theoretical analysis ofAvAtarto establish its correctness, linear time complexity, and linear convergence\.
- •Evaluation\.Extensive experiments across diverse alignment tasks show thatAvAtarconsistently improves alignment performance and achieves a good balance between effectiveness and efficiency\.

## 2Preliminaries

In this section, we introduce preliminaries on optimal transport in Section[2\.1](https://arxiv.org/html/2605.24395#S2.SS1), followed by OT\-based alignment problem in Section[2\.2](https://arxiv.org/html/2605.24395#S2.SS2)\. In this paper, we use bold uppercase letters for matrices \(e\.g\.,𝐓\\mathbf\{T\}\), bold lowercase letters for vectors \(e\.g\.,𝝁\\boldsymbol\{\\mu\}\), calligraphic uppercase letters for sets \(e\.g\.,𝒳\\mathcal\{X\}\) and lowercase letters for scalars \(e\.g\.,kk\)\. Table[1](https://arxiv.org/html/2605.24395#S2.T1)summarizes the main symbols used throughout the paper\.

### 2\.1Optimal Transport

OT has emerged as a powerful mathematical tool for aligning two distributions\(Santambrogio,[2015](https://arxiv.org/html/2605.24395#bib.bib105)\)\. Let𝝁=∑i=1nμi​δxi\\boldsymbol\{\\mu\}=\\sum\_\{i=1\}^\{n\}\\mu\_\{i\}\\delta\_\{x\_\{i\}\}and𝝂=∑j=1mνi​δyj\\boldsymbol\{\\nu\}=\\sum\_\{j=1\}^\{m\}\\nu\_\{i\}\\delta\_\{y\_\{j\}\}be two discrete probability distributions whereδ\\deltadenotes the Dirac measure\. The discrete optimal transport problem seeks an optimal transport plan𝐓\\mathbf\{T\}that minimizes the total transport cost as follows:

min𝐓∈Π​\(𝝁,𝝂\)⁡⟨𝐂,𝐓⟩\\min\_\{\\mathbf\{T\}\\in\\Pi\(\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}\)\}\\left<\\mathbf\{C\},\\mathbf\{T\}\\right\>\(1\)whereΠ​\(𝝁,𝝂\):=\{𝐓∈ℝ\+n×m\|𝐓𝟏m=𝝁,𝐓⊤​𝟏n=𝝂\}\\Pi\(\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}\):=\\left\\\{\\mathbf\{T\}\\in\\mathbb\{R\}^\{n\\times m\}\_\{\+\}\|\\mathbf\{T\}\\mathbf\{1\}\_\{m\}=\\boldsymbol\{\\mu\},\\mathbf\{T\}^\{\\top\}\\mathbf\{1\}\_\{n\}=\\boldsymbol\{\\nu\}\\right\\\},𝐂∈ℝ≥0n×m\\mathbf\{C\}\\in\\mathbb\{R\}^\{n\\times m\}\_\{\\geq 0\}is the cost matrix where𝐂i,j\\mathbf\{C\}\_\{i,j\}measures the cost of transporting mass from the support pointxix\_\{i\}of𝝁\\boldsymbol\{\\mu\}to pointyjy\_\{j\}of𝝂\\boldsymbol\{\\nu\}\. The optimal value of Eq\. \([1](https://arxiv.org/html/2605.24395#S2.E1)\) defines theWasserstein distancebetween𝝁\\boldsymbol\{\\mu\}and𝝂\\boldsymbol\{\\nu\}under the cost matrix𝐂\\mathbf\{C\}, and the resulting transport plan encodes the soft correspondence between points from the two distributions\.

While Eq\. \([1](https://arxiv.org/html/2605.24395#S2.E1)\) induces a linear programming problem of cubic complexity which is infeasible for large\-scale applications,\(Gabriel and Marco,[2019](https://arxiv.org/html/2605.24395#bib.bib22)\)introduces entropic regularization into Eq\. \([1](https://arxiv.org/html/2605.24395#S2.E1)\) to approximate the original OT formulation:

min𝐓∈Π​\(𝝁,𝝂\)⁡⟨𝐂,𝐓⟩−ϵ​Ent​\(𝐓\)\\min\_\{\\mathbf\{T\}\\in\\Pi\(\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}\)\}\\left<\\mathbf\{C\},\\mathbf\{T\}\\right\>\-\\epsilon\\,\\text\{Ent\}\(\\mathbf\{T\}\)\(2\)
whereEnt​\(𝐓\):=−∑i,j𝐓i,j​\(log⁡𝐓i,j−1\)\\text\{Ent\}\(\\mathbf\{T\}\):=\-\\sum\_\{i,j\}\\mathbf\{T\}\_\{i,j\}\\left\(\\log\\mathbf\{T\}\_\{i,j\}\-1\\right\)andϵ\>0\\epsilon\>0denotes the entropic regularization weight\. Eq\. \([2](https://arxiv.org/html/2605.24395#S2.E2)\) yields anϵ\\epsilon\-strongly convex optimization problem that can be solved more efficiently with a quadratic complexity via the Sinkhorn algorithm\(Nemirovski and Rothblum,[1999](https://arxiv.org/html/2605.24395#bib.bib26)\)\.

### 2\.2OT\-based Alignment

A generalized definition for alignment problems based on OT can be summarized as follows\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1); Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2); Chenet al\.,[2020](https://arxiv.org/html/2605.24395#bib.bib11)\):

###### Definition 2\.1\.

OT\-based Alignment Given:\(1\) two sets of objects𝒳=\{xi\}i=1n\\mathcal\{X\}=\\\{x\_\{i\}\\\}^\{n\}\_\{i=1\}and𝒴=\{yj\}j=1m\\mathcal\{Y\}=\\\{y\_\{j\}\\\}^\{m\}\_\{j=1\}to be aligned, and their associated marginal distributions𝝁,𝝂\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}, \(2\) a cost function𝐂∈ℝn×m\\mathbf\{C\}\\in\\mathbb\{R\}^\{n\\times m\}, \(3\) an alignment supervision matrix𝐇∈\{0,1\}n×m\\mathbf\{H\}\\in\\\{0,1\\\}^\{n\\times m\}with𝐇i,j=1\\mathbf\{H\}\_\{i,j\}=1indicating prior alignment betweenxix\_\{i\}andyjy\_\{j\}\. Output:an optimal transport plan𝐓∗∈Π​\(𝝁,𝝂\)\\mathbf\{T\}^\{\*\}\\in\\Pi\(\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}\)indicating the soft correspondence between𝒳\\mathcal\{X\}and𝒴\\mathcal\{Y\}:

𝐓∗=arg⁡min𝐓∈Π​\(𝝁,𝝂\)⟨𝐂~,𝐓⟩,𝐂~=\(𝟏n×m−β​𝐇\)⊙𝐂\\mathbf\{T\}^\{\*\}=\\mathop\{\\arg\\min\}\\limits\_\{\\mathbf\{T\}\\in\\Pi\(\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}\)\}\\langle\\tilde\{\\mathbf\{C\}\},~\\mathbf\{T\}\\rangle,\\tilde\{\\mathbf\{C\}\}=\\left\(\\mathbf\{1\}\_\{n\\times m\}\-\\beta\\mathbf\{H\}\\right\)\\odot\\mathbf\{C\}\(3\)

Eq\. \([3](https://arxiv.org/html/2605.24395#S2.E3)\) follows the common practice\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1); Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2)\)of integrating supervisions into OT\-based alignment by penalizing the cost entries of aligned pairs\.β\\betain Eq\. \([3](https://arxiv.org/html/2605.24395#S2.E3)\) denotes the penalizing factor\. Under unsupervised settings,𝐇\\mathbf\{H\}becomes a zero matrix, making Eq\. \([3](https://arxiv.org/html/2605.24395#S2.E3)\) equivalent to Eq\. \([1](https://arxiv.org/html/2605.24395#S2.E1)\)\.

Table 1:Symbols and Notations\.

## 3Problem Definition

We study the problem of active alignment based on optimal transport, whose goal is to maximally increase the performance of OT\-based alignment methods by selectively acquiring a fixed amount of supervision from an oracle \(e\.g\., a human annotator\)\. We assume that the oracle can answer queries of the following form\(Zhouet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib8)\):

Given an objectxsx\_\{s\}from the source set𝒳\\mathcal\{X\}, which target objectyt∈𝒴y\_\{t\}\\in\\mathcal\{Y\}is the correct alignment ofxsx\_\{s\}?

Based on this, we formally define the active OT\-based alignment problem as follows:

###### Definition 3\.1\.

Active OT\-based Alignment Given:\(1\) two sets of objects𝒳=\{xi\}i=1n\\mathcal\{X\}=\\\{x\_\{i\}\\\}^\{n\}\_\{i=1\}and𝒴=\{yj\}j=1m\\mathcal\{Y\}=\\\{y\_\{j\}\\\}^\{m\}\_\{j=1\}to be aligned, \(2\) an OT\-based alignment method with marginal distributions𝝁,𝝂\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}, cost function𝐂\\mathbf\{C\}, and solved transport plan𝐓\\mathbf\{T\}, \(3\) an alignment supervision matrix𝐇\\mathbf\{H\}that encodes supervision signals, \(4\) a fixed query budgetkk, and \(5\) an oracle\. Output:a set ofkkobjects in𝒳\\mathcal\{X\}for the oracle to label the correct alignment in𝒴\\mathcal\{Y\}, which maximally improves the alignment performance for the unlabeled objects in𝒳\\mathcal\{X\}\.

While the true alignment performance over unlabeled objects are typically unknown without access to test data, we quantify the quality of alignment results by effective utility functions introduced in Section[4\.1](https://arxiv.org/html/2605.24395#S4.SS1)\.

Definition[3\.1](https://arxiv.org/html/2605.24395#S3.Thmtheorem1)is general and applicable to a wide range of alignment problems\. Specifically, forNA,𝒳\\mathcal\{X\}and𝒴\\mathcal\{Y\}correspond to the node sets in the source and target networks; forCDA,𝒳\\mathcal\{X\}and𝒴\\mathcal\{Y\}denote instances from two different domains or modalities, e\.g\. image and text\. This unified problem formulation allows us to define a task\-agnostic active learning template for OT\-based alignment methods applicable to diverse alignment tasks\.

## 4Methodology

In this section, we present the proposed active OT\-based alignment frameworkAvAtar\. We first introduce a quantitative gradient\-based method for evaluating the informativeness of querying a source object, in Section[4\.1](https://arxiv.org/html/2605.24395#S4.SS1)\. Then, we introduce the proposedAvAtarwhich leverages this gradient\-based method for solving the active OT\-based alignment problem, in Section[4\.2](https://arxiv.org/html/2605.24395#S4.SS2)\. Finally, we provide theoretical analysis regarding the complexity and convergence ofAvAtar, in Section[4\.3](https://arxiv.org/html/2605.24395#S4.SS3)\.

### 4\.1Gradient\-based Query Impact

A fundamental principle in active learning is to query the mostinformativeobjects for the learning task\(Zhouet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib8); Liet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib39); Qiu and Tong,[2024](https://arxiv.org/html/2605.24395#bib.bib56)\), oftentimes via gradient\-based impact estimation\(Heet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib73); Chenet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib90),[2026](https://arxiv.org/html/2605.24395#bib.bib46)\)\. In the context of alignment, it is thus desirable to quantify the informativeness of querying a candidate object through its potential impact on the overall alignment results\(Zhouet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib8)\)\. Accordingly, we propose to evaluate the informativeness of querying a source object by its posterior impact on the global alignment results, encoded by an effective utility functionf​\(𝐓\):ℝn×m→ℝf\(\\mathbf\{T\}\):\\mathbb\{R\}^\{n\\times m\}\\rightarrow\\mathbb\{R\}defined over the transport plan𝐓\\mathbf\{T\}\. The utility function is designed to turn matrix𝐓\\mathbf\{T\}that indicates pairwise alignment into a scalar, quantifying theglobal qualityof the alignment\.

In this paper, we adopt two general\-purpose utility functions for all alignment tasks,fL2f\_\{L\_\{2\}\}andfentropyf\_\{\\text\{entropy\}\}, and design an additional utility functionfconsistf\_\{\\text\{consist\}\}for the NA tasks\. Definitions of different utility functions are listed in Table[2](https://arxiv.org/html/2605.24395#S4.T2)\. We differentiateAvAtarof different utility functions by suffixes, e\.g\.,AvAtar\-L2L\_\{2\}\.

Table 2:Adopted utility functionsf​\(𝐓\)f\(\\mathbf\{T\}\)and their gradient w\.r\.t\. the transport map𝐓\\mathbf\{T\}\.log⁡\(⋅\)\\log\(\\cdot\)denotes the element\-wise logarithmic function,∥⋅∥1\\\|\\cdot\\\|\_\{1\}is L1 norm, tr\(⋅\)\(\\cdot\)denotes the trace of a matrix, and𝐌1,𝐌2\\mathbf\{M\}\_\{1\},\\mathbf\{M\}\_\{2\}are the graph Laplacian matrices of the two networks\.The intuition offL2f\_\{L\_\{2\}\}andfentropyf\_\{\\text\{entropy\}\}is straightforward: both functions encourage querying source objects whose true alignment leads to a moredeterministicresult𝐓\\mathbf\{T\}that approximates a permutation matrix whenn≈mn\\approx m\(Gabriel and Marco,[2019](https://arxiv.org/html/2605.24395#bib.bib22); Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2)\)\. For the NA\-specific functionfconsistf\_\{\\text\{consist\}\}, it encourage the consistency principles widely adopted in NA\(Zhang and Tong,[2016](https://arxiv.org/html/2605.24395#bib.bib6); Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1)\)\. Specifically, the first termtr​\(𝐓⊤​𝐌1​𝐓\)=12​∑i,j𝐀i,j\(1\)​‖𝐓i,:−𝐓j,:‖22\\text\{tr\}\(\\mathbf\{T\}^\{\\top\}\\mathbf\{M\}\_\{1\}\\mathbf\{T\}\)=\\frac\{1\}\{2\}\\sum\_\{i,j\}\\mathbf\{A\}^\{\(1\)\}\_\{i,j\}\\\|\\mathbf\{T\}\_\{i,:\}\-\\mathbf\{T\}\_\{j,:\}\\\|^\{2\}\_\{2\}with𝐀\(1\)\\mathbf\{A\}^\{\(1\)\}denoting the graph adjacency matrix of the first network\. It encourages alignment from the source to target network that contributes most to the consistency principle: the 1\-hop neighbors of aligned nodes across different networks should share similar alignment results \(i\.e\. corresponding rows in𝐓\\mathbf\{T\}\)\. Similarly, the second term encourages consistency when the alignment direction is reversed\.

For the rest of this subsection, we first define the impact of a pairwise objects query on an utility function and introduce how to calculate this gradient\-based impact\. Then, we formally define the posterior impact of an individual object query on the utility function\.

#### 4\.1\.1Pairwise Objects Query Impact

###### Definition 4\.1\.

Pairwise Objects Query Impact Given a query of a pair of objects denoted aspi​j=\(xi,yj\)p\_\{ij\}=\(x\_\{i\},y\_\{j\}\)wherexi∈𝒳,yj∈𝒴x\_\{i\}\\in\\mathcal\{X\},y\_\{j\}\\in\\mathcal\{Y\}, and an utility functionf​\(𝐓\)f\(\\mathbf\{T\}\)defined over the transport plan𝐓\\mathbf\{T\}, the query impact ofpi​jp\_\{ij\}is defined as thegradientoff​\(𝐓\)f\(\\mathbf\{T\}\)w\.r\.t\. the alignment supervision signal of this pair of objects, i\.e\.,𝐇i,j\\mathbf\{H\}\_\{i,j\}\. Formally, the pairwise objects query impact is defined asℐ​\(pi​j\)=∇𝐇i,jf\\mathcal\{I\}\(p\_\{ij\}\)=\\nabla\_\{\\mathbf\{H\}\_\{i,j\}\}f\.

The calculation ofℐ​\(pi​j\)\\mathcal\{I\}\(p\_\{ij\}\)for OT\-based alignment method can be decomposed by the chain rule as follows

ℐ​\(pi​j\)=∇𝐇i,jf=⟨∇𝐂~f,∇𝐇i,j𝐂~⟩\\mathcal\{I\}\(p\_\{ij\}\)=\\nabla\_\{\\mathbf\{H\}\_\{i,j\}\}f=\\langle\\nabla\_\{\\tilde\{\\mathbf\{C\}\}\}f,\\nabla\_\{\\mathbf\{H\}\_\{i,j\}\}\\mathbf\{\\tilde\{C\}\}\\rangle\(4\)
The second term∇𝐇i,j𝐂~\\nabla\_\{\\mathbf\{H\}\_\{i,j\}\}\\tilde\{\\mathbf\{C\}\}quantifies the impact of an added supervision to the supervised cost matrix𝐂~\\tilde\{\\mathbf\{C\}\}\. Following Eq\. \([3](https://arxiv.org/html/2605.24395#S2.E3)\),∇𝐇i,j𝐂~\\nabla\_\{\\mathbf\{H\}\_\{i,j\}\}\\tilde\{\\mathbf\{C\}\}can be computed easily as∇𝐇i,j𝐂~=−β​𝐂i,j​𝐄\\nabla\_\{\\mathbf\{H\}\_\{i,j\}\}\\tilde\{\\mathbf\{C\}\}=\-\\beta\\mathbf\{C\}\_\{i,j\}\\mathbf\{E\}where𝐄i,j=1\\mathbf\{E\}\_\{i,j\}=1and 0 otherwise\.

The main computation falls into the first term∇𝐂~f\\nabla\_\{\\tilde\{\\mathbf\{C\}\}\}f, which quantifies the impact of changing the supervised cost matrix𝐂~\\tilde\{\\mathbf\{C\}\}on the utility functionf​\(𝐓\)f\(\\mathbf\{T\}\)\. Computing∇𝐂~f\\nabla\_\{\\tilde\{\\mathbf\{C\}\}\}frequires differentiating through the OT formulation, which is highly challenging for the following reason: as𝐓\\mathbf\{T\}is an implicit function w\.r\.t\.𝐂~\\tilde\{\\mathbf\{C\}\}due to existence of marginal constraints, differentiating𝐓\\mathbf\{T\}w\.r\.t\.𝐂~\\tilde\{\\mathbf\{C\}\}, i\.e\.,d​𝐓d​𝐂~\\frac\{\\mathrm\{d\}\\mathbf\{T\}\}\{\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\}, requires explicitly forming and inverting a Jacobian matrix of size\(n​m\)2\(nm\)^\{2\}, which would be computationally intractable at scale\.

To tackle this computational challenge, we leverage the adjoint\-state method to reformulate the computation of∇𝐂~f\\nabla\_\{\\tilde\{\\mathbf\{C\}\}\}fto solving an adjoint linear system of size\(n\+m\)\(n\+m\)\.

###### Lemma 4\.2\.

The gradient of a utility functionf​\(𝐓\)f\(\\mathbf\{T\}\)w\.r\.t\. the cost function𝐂~\\tilde\{\\mathbf\{C\}\}under the entropy\-regularized OT formulation can be computed by solving a linear system with respect to adjoint vectors𝐲α∈ℝn,𝐲β∈ℝm\\mathbf\{y\}\_\{\\alpha\}\\in\\mathbb\{R\}^\{n\},\\mathbf\{y\}\_\{\\beta\}\\in\\mathbb\{R\}^\{m\}as follows,

∇𝐂~f=1ϵ​𝐓⊙\(𝐲α​𝟏m⊤\+𝟏n​𝐲β⊤−∇𝐓f\)\\nabla\_\{\\tilde\{\\mathbf\{C\}\}\}f=\\frac\{1\}\{\\epsilon\}\\mathbf\{T\}\\odot\\left\(\\mathbf\{y\}\_\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\+\\mathbf\{1\}\_\{n\}\\mathbf\{y\}\_\{\\beta\}^\{\\top\}\-\\nabla\_\{\\mathbf\{T\}\}f\\right\)\(5\)s\.t\.

\[diag​\(𝝁\)𝐓𝐓⊤diag​\(𝝂\)\]⏟𝐀​\[𝐲α𝐲β\]⏟𝐲=\[\(𝐓⊙∇𝐓f\)​𝟏m\(𝐓⊙∇𝐓f\)⊤​𝟏n\]⏟𝐛\\underbrace\{\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)&\\mathbf\{T\}\\\\ \\mathbf\{T\}^\{\\top\}&\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\end\{bmatrix\}\}\_\{\\mathbf\{A\}\}\\underbrace\{\\begin\{bmatrix\}\\mathbf\{y\}\_\{\\alpha\}\\\\ \\mathbf\{y\}\_\{\\beta\}\\end\{bmatrix\}\}\_\{\\mathbf\{y\}\}=\\underbrace\{\\begin\{bmatrix\}\\left\(\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\\right\)\\mathbf\{1\}\_\{m\}\\\\ \\left\(\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\}\}\_\{\\mathbf\{b\}\}\(6\)whereϵ\\epsilonis the entropic regularization weight,𝛍,𝛎\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}are marginal distributions of OT, anddiag​\(⋅\)\\text\{diag\}\(\\cdot\)creates a diagonal matrix from a vector\.

The detailed proof of Lemma[4\.2](https://arxiv.org/html/2605.24395#S4.Thmtheorem2)can be found in Appendix[A\.1](https://arxiv.org/html/2605.24395#A1.SS1)\. The core idea is to implicitly differentiate the constrained optimality conditions of OT by the adjoint\-state method, which reformulates the computation of∇𝐂~f\\nabla\_\{\\tilde\{\\mathbf\{C\}\}\}fto solving a linear system\(Sadret al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib99)\)without explicitly inverting a large Jacobian\.

To solve the linear system, we show in Appendix[A\.2](https://arxiv.org/html/2605.24395#A1.SS2)that the coefficient matrix𝐀\\mathbf\{A\}of Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) is singular, making it impossible to directly solve Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) by matrix inversion\. To address this issue, we resort to conjugate gradient \(CG\) method, which is summarized in the following lemma[4\.3](https://arxiv.org/html/2605.24395#S4.Thmtheorem3)\.

###### Lemma 4\.3\.

Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) can be solved via the conjugate gradient method with guaranteed convergence to global optimum\.

The detailed proof of Lemma[4\.3](https://arxiv.org/html/2605.24395#S4.Thmtheorem3)can be found in Appendix[4\.3](https://arxiv.org/html/2605.24395#S4.Thmtheorem3)\. In general, Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) renders a singular linear system solvable by the CG method, given that𝐀\\mathbf\{A\}is positive\-semidefinite and𝐛\\mathbf\{b\}lies in the range of𝐀\\mathbf\{A\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\)\(Kaasschieter,[1988](https://arxiv.org/html/2605.24395#bib.bib28); Hayami,[2018](https://arxiv.org/html/2605.24395#bib.bib29)\)\. This linear system corresponding to a convex quadratic optimization problem, therefore CG is guaranteed to converge to the global optimum\.

We present detailed analysis of the complexity and convergence rate of the CG method for Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) in Section[4\.3](https://arxiv.org/html/2605.24395#S4.SS3), which shows that Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) can be solved with \(1\) alineartime complexity w\.r\.t\. the number of objects in𝒳\\mathcal\{X\}and𝒴\\mathcal\{Y\}, and \(2\) guaranteed convergence with alinearconvergence rate\. Combining Eq\. \([4](https://arxiv.org/html/2605.24395#S4.E4)\)\-\([6](https://arxiv.org/html/2605.24395#S4.E6)\) gives the final formulation ofℐ​\(pi​j\)\\mathcal\{I\}\(p\_\{ij\}\), which quantifies the impact of querying a possible pairwise alignment\(xi,yj\)\(x\_\{i\},y\_\{j\}\):

ℐ​\(pi​j\)\\displaystyle\\mathcal\{I\}\(p\_\{ij\}\)=−βϵ​𝐂i,j​𝐓i,j​\(𝐲α​𝟏m⊤\+𝟏n​𝐲β⊤−∇𝐓f\)i​j\\displaystyle=\-\\frac\{\\beta\}\{\\epsilon\}\\mathbf\{C\}\_\{i,j\}\\mathbf\{T\}\_\{i,j\}\\left\(\\mathbf\{y\}\_\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\+\\mathbf\{1\}\_\{n\}\\mathbf\{y\}\_\{\\beta\}^\{\\top\}\-\\nabla\_\{\\mathbf\{T\}\}f\\right\)\_\{ij\}\(7\)s\.t\.\[diag​\(𝝁\)𝐓𝐓⊤diag​\(𝝂\)\]​\[𝐲α𝐲β\]=\[\(𝐓⊙∇𝐓f\)​𝟏m\(𝐓⊙∇𝐓f\)⊤​𝟏n\]\\displaystyle\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)&\\mathbf\{T\}\\\\ \\mathbf\{T\}^\{\\top\}&\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\end\{bmatrix\}\\begin\{bmatrix\}\\mathbf\{y\}\_\{\\alpha\}\\\\ \\mathbf\{y\}\_\{\\beta\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\left\(\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\\right\)\\mathbf\{1\}\_\{m\}\\\\ \\left\(\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\}

#### 4\.1\.2Posterior Object Query Impact

###### Definition 4\.4\.

Posterior Object Query Impact For an object query denoted aspi=\(xi,⋅\)p\_\{i\}=\(x\_\{i\},\\cdot\)wherexi∈𝒳x\_\{i\}\\in\\mathcal\{X\}, the posterior query impact ofpip\_\{i\}on the utility functionffis defined as the aggregation of the pairwise objects query impact between objectxi∈𝒳x\_\{i\}\\in\\mathcal\{X\}and all objectsyyin the target set𝒴\\mathcal\{Y\}, weighted by the corresponding rows of the transport plan𝐓i,:\\mathbf\{T\}\_\{i,:\}as a posterior\. Formally, the posterior object query impact is defined as

ℐ​\(pi\)=∑j=1m𝐓i,j​ℐ​\(pi​j\)\\mathcal\{I\}\(p\_\{i\}\)=\\sum\_\{j=1\}^\{m\}\\mathbf\{T\}\_\{i,j\}\\mathcal\{I\}\(p\_\{ij\}\)\(8\)

The intuition of using the transport plan𝐓\\mathbf\{T\}as posterior weights is straightforward: while it is unknown which target object will be the true alignment for a source object before the query,𝐓i,j\\mathbf\{T\}\_\{i,j\}encodes the posterior alignment probability between two objectsxi∈𝒳x\_\{i\}\\in\\mathcal\{X\}andyj∈𝒴y\_\{j\}\\in\\mathcal\{Y\}conditioned on the observed data and supervision\. Aggregating pairwise objects query impact weighted by𝐓i,:\\mathbf\{T\}\_\{i,:\}thus computes theexpected impactof querying a source objectxix\_\{i\}\.

### 4\.2AvAtar

Based on Definition[4\.1](https://arxiv.org/html/2605.24395#S4.Thmtheorem1)and Definition[4\.4](https://arxiv.org/html/2605.24395#S4.Thmtheorem4), we propose a generic query algorithm for OT\-based alignment as described in Algorithm[1](https://arxiv.org/html/2605.24395#alg1), which allows customized utility functionffthat quantifies the global alignment quality for different tasks\. The key idea ofAvAtaris to iteratively\(1\)select candidate objects with the largest posterior impact by Eq\. \([8](https://arxiv.org/html/2605.24395#S4.E8)\) \(Steps 7 and 10\);\(2\)query the oracle for their true alignment \(Step 13\);\(3\)update the alignment supervision matrix𝐇\\mathbf\{H\}accordingly \(Step 14\); and\(4\)re\-compute the alignment results by an OT\-based method \(Step 15\)\.

AvAtaroperates under both weakly supervised and unsupervised settings by different initializations of the alignment supervision matrix𝐇\\mathbf\{H\}\. For weakly supervised alignment tasks where partial ground\-truth alignment is pre\-known,𝐇i,j\\mathbf\{H\}\_\{i,j\}is set to 1 if objectxix\_\{i\}andyjy\_\{j\}are known to be aligned, and 0 otherwise; for unsupervised alignment tasks,𝐇i,j\\mathbf\{H\}\_\{i,j\}is set to be a zero matrix\. Similarly, when updating𝐇\\mathbf\{H\}during the query process, we set the corresponding entries of queried alignment pairs in𝐇\\mathbf\{H\}to 1\. While we adopt a binary supervision matrix𝐇\\mathbf\{H\},AvAtarcan be naturally extended to a soft supervision matrix𝐇\\mathbf\{H\}with continuous values\.

Algorithm 1AvAtar1:Input:\(1\) two sets of objects

𝒳\\mathcal\{X\}and

𝒴\\mathcal\{Y\}, \(2\) an OT\-based alignment method with marginal distributions

𝝁,𝝂\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}and cost function

𝐂\\mathbf\{C\}, \(3\) an alignment supervision matrix

𝐇\\mathbf\{H\}, \(4\) a total query budget

kk, \(5\) query batch size

nbn\_\{b\}, \(6\) a query pool

𝒫⊆𝒳\\mathcal\{P\}\\subseteq\\mathcal\{X\}, \(7\) an oracle, \(8\) an utility function

fffor encoding the alignment result\.

2:Output:\(1\) a set of

kkobjects

𝒬⊆𝒳\\mathcal\{Q\}\\subseteq\\mathcal\{X\}for query, \(2\) the alignment matrix

𝐓\\mathbf\{T\}between

𝒳\\mathcal\{X\}and

𝒴\\mathcal\{Y\}\.

3:Initialize the query set

𝒬=∅\\mathcal\{Q\}=\\emptyset;

4:Remove source objects whose alignment are known from the query pool, i\.e\.,

𝒫←𝒫\\\{xi∈𝒳\|∑j𝐇i,j\>0\}\\mathcal\{P\}\\leftarrow\\mathcal\{P\}\\backslash\\left\\\{x\_\{i\}\\in\\mathcal\{X\}\|\\sum\_\{j\}\\mathbf\{H\}\_\{i,j\}\>0\\right\\\};

5:Compute the current alignment matrix

𝐓\\mathbf\{T\}by the input OT\-based method via entropy\-regularized OT solver;

6:while

\|𝒬\|<k\|\\mathcal\{Q\}\|<kdo

7:Compute the posterior query impact of all source objects

ℐ\\mathcal\{I\}using Eq\. \([8](https://arxiv.org/html/2605.24395#S4.E8)\);

8:Initialize batch query set

𝒬b=∅\\mathcal\{Q\}\_\{b\}=\\emptyset;

9:while

\|𝒬b\|<nb\|\\mathcal\{Q\}\_\{b\}\|<n\_\{b\}do

10:Update

𝒬b←𝒬b∪\{x∗=arg⁡maxxi∈𝒫⁡ℐ​\(pi\)\}\\mathcal\{Q\}\_\{b\}\\leftarrow\\mathcal\{Q\}\_\{b\}\\cup\\\{x^\{\*\}=\\arg\\max\_\{x\_\{i\}\\in\\mathcal\{P\}\}\\mathcal\{I\}\(p\_\{i\}\)\\\};

11:Update

𝒫←𝒫\\\{x∗\}\\mathcal\{P\}\\leftarrow\\mathcal\{P\}\\backslash\\\{x^\{\*\}\\\};

12:endwhile

13:Query for the correct alignment of objects in

𝒬b\\mathcal\{Q\}\_\{b\};

14:Update the alignment supervision matrix

𝐇\\mathbf\{H\};

15:Re\-compute

𝐓\\mathbf\{T\}by the OT\-based alignment method;

16:Update

𝒬=𝒬∪𝒬b\\mathcal\{Q\}=\\mathcal\{Q\}\\cup\\mathcal\{Q\}\_\{b\};

17:endwhile

18:return

𝒬\\mathcal\{Q\}and

𝐓\\mathbf\{T\};

### 4\.3Theoretical Analysis

In this subsection, we provide theoretical analysis regarding the complexity and convergence rate of proposedAvAtar\.

###### Theorem 4\.5\.

\(Time & Space Complexity ofAvAtar\-L2L\_\{2\}/entropy/consist\) The time complexity is𝒪​\(knb​K​\(n\+m\)\)\\mathcal\{O\}\\left\(\\frac\{k\}\{n\_\{b\}\}K\(n\+m\)\\right\)forAvAtar\-L2L\_\{2\}/entropy, and𝒪​\(knb​\(K​\(n\+m\)\+e\)\)\\mathcal\{O\}\\left\(\\frac\{k\}\{n\_\{b\}\}\(K\(n\+m\)\+e\)\\right\)forAvAtar\-consist, whereeedenotes the number of edges in the networks111Without loss of generality, we assume𝒪​\(e\)≈𝒪​\(e1\)≈𝒪​\(e2\)\\mathcal\{O\}\(e\)\\approx\\mathcal\{O\}\(e\_\{1\}\)\\approx\\mathcal\{O\}\(e\_\{2\}\)whereeie\_\{i\}denotes the number of edges in theii\-th networks\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1); Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2)\)\.\. The space complexity ofAvAtar\-L2L\_\{2\}/entropy/consistis𝒪​\(n​m\)\\mathcal\{O\}\(nm\)\.kkis the total query budget,nbn\_\{b\}is the batch query size,KKis the number of iterations of the CG method, andn,mn,mare number of objects in the source and target sets, respectively\.

The detailed proof of Theorem[4\.5](https://arxiv.org/html/2605.24395#S4.Thmtheorem5)can be found in Appendix[A\.4](https://arxiv.org/html/2605.24395#A1.SS4)\. In general, we reduce the complexity ofAvAtar\-L2L\_\{2\}/entropy/consistto linear by utilizing thesparsityof the transport plan𝐓\\mathbf\{T\}of OT\-based method, as visualized in Figure[5](https://arxiv.org/html/2605.24395#S5.F5)\. Note that while the total complexity ofAvAtarmay depend on the selected utility functionff, the coefficient martix𝐀\\mathbf\{A\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) is agnostic toffthus the CG method can always leverage the sparsity of𝐓\\mathbf\{T\}for OT\-based alignment to approximate a linear time complexity of𝒪​\(K​\(n\+m\)\)\\mathcal\{O\}\(K\(n\+m\)\)w\.r\.t\. the number of objects in𝒳\\mathcal\{X\}and𝒴\\mathcal\{Y\}\.

###### Theorem 4\.6\.

\(Convergence Rate ofAvAtar\) The conjugate gradient method applied to the linear system of Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) converges at a linear convergence rate ofλ1/λr−1λ1/λr\+1\\frac\{\\sqrt\{\\lambda\_\{1\}/\\lambda\_\{r\}\}\-1\}\{\\sqrt\{\\lambda\_\{1\}/\\lambda\_\{r\}\}\+1\}, whereλ1,λr\\lambda\_\{1\},\\lambda\_\{r\}denotes the largest/smallest nonzero eigenvalues of𝐀\\mathbf\{A\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\)\.

The detailed proof of Theorem[4\.6](https://arxiv.org/html/2605.24395#S4.Thmtheorem6)can be found in Appendix[A\.5](https://arxiv.org/html/2605.24395#A1.SS5)\. This linear convergence rate guarantees fast and stable convergence of the CG method, making the gradient computation inAvAtarefficient and scalable\.

## 5Experiments

In this section, we carry out comprehensive experiments and analyses to evaluate the proposedAvAtarfrom the following aspects:

- •Q1\.How effective is the proposedAvAtaracross different alignment problems?
- •Q2\.How efficient and scalable isAvAtar?
- •Q3\.How is the empirical convergence ofAvAtar?
- •Q4\.How sensitive is the proposedAvAtarto different parameters and design choices?

### 5\.1Experimental Setup

We benchmark the proposedAvAtaron three different alignment tasks, including network alignment \(NA\), image\-text retrieval, and image\-text grounding\.

##### Network Alignment\.

NA aims to find node\-level correspondence across different networks\. Fordatasets, we adopt 4 real\-world datasets Phone\-Email\(Zhanget al\.,[2017](https://arxiv.org/html/2605.24395#bib.bib31)\), ACM\-DBLP\-P\(Tanget al\.,[2008](https://arxiv.org/html/2605.24395#bib.bib32)\), Douban\(Zhang and Tong,[2016](https://arxiv.org/html/2605.24395#bib.bib6)\), and ACM\-DBLP\-A\(Tanget al\.,[2008](https://arxiv.org/html/2605.24395#bib.bib32)\), covering both plain and attributed networks\. Forbaseline OT\-based NA methods, we adopt PARROT\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1)\)and JOENA\(Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2)\)\. Forbaseline query strategies, we adoptRandom,Entropy,Margin\(Liet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib39)\),Betweenness\(Macskassy,[2009](https://arxiv.org/html/2605.24395#bib.bib38)\),Contrastive,GibbsMatchings\(Malmiet al\.,[2017](https://arxiv.org/html/2605.24395#bib.bib9)\), andTopMatchings\(Malmiet al\.,[2017](https://arxiv.org/html/2605.24395#bib.bib9)\)\. We report the mean reciprocal rank \(MRR\) as the benchmarking metric for NA\.

##### Image\-Text Retrieval\.

Image\-text retrieval aims to retrieve the most relevant text given an image query, or vice versa\. In this paper, we focus on the former setting\. Fordatasets, we adopt 2 widely used datasets CIFAR\-10\-C and ImageNet\-C\(Hendrycks and Dietterich,[2019](https://arxiv.org/html/2605.24395#bib.bib33)\)\. Forbaseline OT\-based CDA methods, we adopt the Wasserstein \(W\) and Fused Gromov\-Wasserstein \(FGW\) variants of GOT\(Chenet al\.,[2020](https://arxiv.org/html/2605.24395#bib.bib11)\)\. Forbaseline query strategies, we adoptRandom,Entropy,Margin,Least confident,Density, andDiversity\(Liet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib39)\)\. We report the Recall@1 as the benchmarking metric for image\-text retrieval\.

##### Image\-Text Grounding\.

Image\-text grounding aims to identify the fine\-grained correspondence between phrases in a sentence and objects \(or regions\) in an image\(Liet al\.,[2022](https://arxiv.org/html/2605.24395#bib.bib34)\)\. Fordatasets, we adopt 2 widely used datasets COCO\(Linet al\.,[2014](https://arxiv.org/html/2605.24395#bib.bib36)\)and Flickr30K Entities\(Plummeret al\.,[2015](https://arxiv.org/html/2605.24395#bib.bib35)\)\. We adopt the same baseline OT\-based alignment methods, query strategies, and evaluation metric as that of image\-text retrieval\.

Detailed experimental settings, as well as descriptions of datasets and introduction for different query strategies, are included in Appendix[B](https://arxiv.org/html/2605.24395#A2)\.

### 5\.2Benchmarking Results

#### 5\.2\.1Network Alignment

Table 3:Benchmarking results on network alignment in MRR\. The1st/2ndbest results are highlighted inboldandunderline, respectively\.For NA tasks, we adopt the task\-agonisticAvAtar\-L2L\_\{2\}, andAvAtar\-consistwhich is designed specifically for NA\. We compare these two versions of the proposed method with other baseline query methods in alignment performance measured by MRR\. The results are summarized in Table[3](https://arxiv.org/html/2605.24395#S5.T3)\. We observe that\(1\)AvAtar\-L2L\_\{2\}/consistachieve state\-of\-the\-art performance across all datasets\.They consistently outperform all baselines by up to 2\.8% in MRR, demonstrating the effectiveness ofAvAtaron both plain and attributed NA tasks\.\(2\) Existing active NA methods becomes less effective on OT\-based algorithms\.We notice thatGibbsMatchingsandTopMatchingsdesigned specifically for active NA are consistently outperformed by general\-purpose active query strategies, e\.g\.,Entropy, when applied to OT\-based methods\. This is because the deterministic transport plan gives consistent sampling results, making it difficult forGibbsMatchingsandTopMatchingsto characterize the uncertainty of a candidate\.\(3\)AvAtarbenefits from effective utility functions tailored for specific alignment tasks\.On plain networks \(Phone\-Email and ACM\-DBLP\-P\),AvAtar\-consistdesigned specifically for NA tasks typically outperformsAvAtar\-L2L\_\{2\}with up to 0\.6% improvement in MRR, indicating that consistency principles are particularly useful when attribute information is missing\. In contrast,AvAtar\-L2L\_\{2\}generally achieves better performance thanAvAtar\-consiston attributed networks \(Douban, ACM\-DBLP\-A\), suggesting that deterministic alignment results given byfL2f\_\{L\_\{2\}\}, as mentioned in Section[4](https://arxiv.org/html/2605.24395#S4), are more helpful when informative attributes are available\. Complete results that shows MRR vs\. query round for all baselines across three different alignment tasks can be found in Appendix[C\.1](https://arxiv.org/html/2605.24395#A3.SS1)\.

#### 5\.2\.2Cross\-Domain Alignment

Table 4:Benchmarking results on image\-text retrieval in Recall@1\. The1st/2ndbest results are highlighted inboldandunderline, respectively\.Table 5:Benchmarking results on image\-text grounding in Recall@1\. The1st/2ndbest results are highlighted inboldandunderline, respectively\.We include two tasks for benchmarkingAvAtaron CDA:image\-text retrievalandimage\-text grounding\. For both CDA tasks, we compareAvAtar\-L2L\_\{2\}/entropywith other baseline query methods in alignment performance by Recall@1\. The results of image\-text retrieval and image\-text grounding can be found in Tables[4](https://arxiv.org/html/2605.24395#S5.T4)and[5](https://arxiv.org/html/2605.24395#S5.T5), respectively\. We observe that\(1\)AvAtar\-entropy/L2L\_\{2\}consistently achieve state\-of\-the\-art performance on both CDA tasks, demonstrating the effectiveness ofAvAtaron OT\-based alignment methods for CDA\.\(2\)AvAtar\-entropyaligns well with the objective of entropic OT\.AvAtar\-entropytypically outperformsAvAtar\-L2L\_\{2\}under most settings except for the image\-text grounding task by GOT\-FGW, which implies thatfentropyf\_\{\\text\{entropy\}\}generally aligns better with the objective of entropic OT alignment\.\(3\) Gradients characterize the informativeness of a candidate better than the plain transport plan𝐓\\mathbf\{T\}\.AvAtar\-entropyconsistently outperformsEntropyby up to 2\.6% in Recall@1, suggesting that the gradients propagated through OT provide more accurate measures of the informativeness of candidates than directly applying the same utility function on𝐓\\mathbf\{T\}\.

### 5\.3Efficiency Results

![Refer to caption](https://arxiv.org/html/2605.24395v1/x3.png)Figure 2:MRR vs\. total query time ofAvAtarand baselines, showing thatAvAtarachieves up to25×\\timesspeed\-up and 8\.1% improvement in MRRcompared to existing active NA methods\.We study the effectiveness\-efficiency trade\-off of proposedAvAtar\-L2L\_\{2\}/consistcompared with other baseline query methods on phone\-email and Douban datasets using PARROT\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1)\)\. The MRR vs\. query time trade\-off results are shown in Figure[2](https://arxiv.org/html/2605.24395#S5.F2)\. We can see thatAvAtar\-L2L\_\{2\}/consistachieve a good balance between the alignment performance and query time\. Specifically,AvAtarachieves up to25×25\\timesspeed\-up compared toTopMatchings, and up to 8\.1% improvement in MRR compared toGibbsMatchings, demonstrating both the effectiveness and efficiency ofAvAtarover existing active NA methods\. While most other baselines are slightly faster, they are consistently less effective in improving the alignment performance thanAvAtar\. More results on scalability are included in Appendix[C\.2](https://arxiv.org/html/2605.24395#A3.SS2)\.

### 5\.4Convergence Results

We evaluate the convergence of the the conjugate gradient \(CG\) method for solving Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) and that of the Sinkhorn \(SH\) algorithm used for solving OT\-based alignment, in terms of the difference between two consecutive solutionsΔ​𝐬\(t\)=‖𝐬\(t\)−𝐬\(t−1\)‖1\\Delta\\mathbf\{s\}^\{\(t\)\}=\\\|\\mathbf\{s\}^\{\(t\)\}\-\\mathbf\{s\}^\{\(t\-1\)\}\\\|\_\{1\}, on Phone\-Email\. For CG,𝐬=𝐲\\mathbf\{s\}=\\mathbf\{y\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\); for SH,𝐬=vec​\(𝐓\)\\mathbf\{s\}=\\text\{vec\}\(\\mathbf\{T\}\)\. Results are normalized to ensure a fair comparison\. The corresponding convergence result ofAvAtar\-L2L\_\{2\}andAvAtar\-consist, are shown in Figure[3](https://arxiv.org/html/2605.24395#S5.F3)\. We observe that\(1\) CG converges empiricallywhen applied to Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\), which validates the convergence ofAvAtar\.\(2\) The convergence of SH is more sensitive toϵ\\epsilonthan CG\.As the entropic regularization weightϵ\\epsilondecreases, SH becomes increasingly ill\-conditioned and harder to converge, while the convergence rate of CG remains relatively stable\.\(3\) CG converges faster than SH under the sameϵ\\epsilon, suggesting that the CG method, with a linear time complexity per iteration, incursnegligible overheadcompared to the Sinkhorn algorithm for solving OT\.

![Refer to caption](https://arxiv.org/html/2605.24395v1/x4.png)\(a\)AvAtar\-L2L\_\{2\}
![Refer to caption](https://arxiv.org/html/2605.24395v1/x5.png)\(b\)AvAtar\-consist

Figure 3:Convergence analysis of the conjugate gradient \(CG\) and the Sinkhorn \(SH\) algorithm inAvAtarunder different entropic regularization weightϵ\\epsilon\.
### 5\.5Further Studies

#### 5\.5\.1Hyperparameter Analysis

##### Query Budgetkk\.

The impact of the query budgetkkis presented in Tables[3](https://arxiv.org/html/2605.24395#S5.T3)\-[5](https://arxiv.org/html/2605.24395#S5.T5)and Appendix[C\.1](https://arxiv.org/html/2605.24395#A3.SS1), which shows that the alignment performance ofAvAtarimproves monotonically as the query budgetkkincreases\.

##### Query Batch Sizenbn\_\{b\}\.

We perform a sensitivity study on the query batch sizenbn\_\{b\}in Figure[4](https://arxiv.org/html/2605.24395#S5.F4)\. We adoptAvAtar\-L2L\_\{2\}and test the performance of PARROT on two datasets as the query batch sizenbn\_\{b\}changes under different query budgetkk\. We can see in Figure[4](https://arxiv.org/html/2605.24395#S5.F4)that the performance ofAvAtar\-L2L\_\{2\}remains stable under different choices ofnbn\_\{b\}, with only slight performance improvement whennbn\_\{b\}is smaller on Douban\.

![Refer to caption](https://arxiv.org/html/2605.24395v1/x6.png)Figure 4:Parameter study for query batch sizenbn\_\{b\}onAvAtar\-L2L\_\{2\}\.

#### 5\.5\.2Ablation Study

##### Sparse vs\. Dense Matrix Operation in CG\.

As mentioned in Section[4\.3](https://arxiv.org/html/2605.24395#S4.SS3),AvAtarleverages the sparsity of the transport plan𝐓\\mathbf\{T\}to achieve linear time complexity\. To verify the effectiveness and efficiency of sparse matrix operations inAvAtar, we compare the alignment performance ofAvAtarwithAvAtar\(Dense\), which computes Eq\. \([7](https://arxiv.org/html/2605.24395#S4.E7)\) and Eq\. \([8](https://arxiv.org/html/2605.24395#S4.E8)\) by dense matrix operations\. Specifically, we compareAvAtar\-L2L\_\{2\}withAvAtar\-L2L\_\{2\}\(Dense\), andAvAtar\-consistwithAvAtar\-consist\(Dense\)\. The results on two datasets are shown in Table[6](https://arxiv.org/html/2605.24395#S5.T6)\. We observe that \(1\)Sparse matrix operations do not harm the empirical performance ofAvAtar, as we can see that the alignment performance ofAvAtarandAvAtar\(Dense\) remains close across different datasets\.\(2\) Sparse matrix operation significantly improves the efficiency ofAvAtar\.AvAtarruns significantly faster thanAvAtar\(Dense\) with up to1010/118≈8\.61010/118\\approx 8\.6times speed\-up, demonstrating the efficiency of sparse matrix operations onAvAtar\.

Table 6:Ablation study on sparse matrix operations adopted byAvAtar\.
##### Posterior vs\. Uniform Aggregation\.

We verify the necessity of using transport plan𝐓\\mathbf\{T\}as a posterior in Eq\. \([8](https://arxiv.org/html/2605.24395#S4.E8)\) by comparing the performance ofAvAtarwithAvAtar\(Uniform\), which aggregated pairwise objects query impact in Eq\. \([4](https://arxiv.org/html/2605.24395#S4.E4)\) uniformly for computing the object\-level query impact, i\.e\.,ℐ​\(pi\)=∑j=1mℐ​\(pi​j\)\\mathcal\{I\}\(p\_\{i\}\)=\\sum\_\{j=1\}^\{m\}\\mathcal\{I\}\(p\_\{ij\}\)\. As shown in Table[7](https://arxiv.org/html/2605.24395#S5.T7),AvAtarconsistently outperformsAvAtar\(Uniform\) on both Douban and ACM\-DBLP\-A under different choices of utility functions, demonstrating the informativeness of the transport plan𝐓\\mathbf\{T\}as a posterior\.

![Refer to caption](https://arxiv.org/html/2605.24395v1/x7.png)\(a\)PARROT on Phone\-Email
![Refer to caption](https://arxiv.org/html/2605.24395v1/x8.png)\(b\)JOENA on Phone\-Email
![Refer to caption](https://arxiv.org/html/2605.24395v1/x9.png)\(c\)GOT\-W on ImageNet\-C
![Refer to caption](https://arxiv.org/html/2605.24395v1/x10.png)\(d\)GOT\-W on COCO

Figure 5:Visualization of transport plans𝐓\\mathbf\{T\}of different OT\-based methods on different datasets under default hyperparameter settings in their original papers\. Lighter pixels denotes higher value\. Ground\-truth alignment are moved to diagonals for better visualization\.Table 7:Ablation study on posterior aggregation of pairwise objects query impact inAvAtar\.

### 5\.6Visualizations

##### Sparsity of Transport Plans

To verify the sparsity of the output transport plan𝐓\\mathbf\{T\}, we visualize randomly sampled𝐓\\mathbf\{T\}\(300x300\) of different OT\-based alignment methods under their default hyperparameter settings in Figure[5](https://arxiv.org/html/2605.24395#S5.F5)\. The results show thatthe𝐓\\mathbf\{T\}returned by different OT\-based methods are empirically sparseacross different alignment tasks,with over 99% entries close to zero, suggesting that OT\-based methods typically choose a small entropic regularization weightϵ\\epsilonto approximate deterministic, one\-to\-one alignment, making it possible forAvAtarto achieve linear time complexity by leveraging the sparsity of𝐓\\mathbf\{T\}\.

##### Drifts of Transport Plans\.

To improve interpretability regarding the corrective benefit of the oracle, we include an additional study on the drift of𝐓\(i\)\\mathbf\{T\}^\{\(i\)\}from𝐓\(0\)\\mathbf\{T\}^\{\(0\)\}in theii\-th query round, measured by the Frobenius norm of their difference \(i\.e\.,‖𝐓\(i\)−𝐓\(0\)‖F\\\|\\mathbf\{T\}^\{\(i\)\}\-\\mathbf\{T\}^\{\(0\)\}\\\|\_\{\\text\{F\}\}\. The results are shown in Figure[11](https://arxiv.org/html/2605.24395#A3.F11), which shows that\(1\)𝐓\(i\)\\mathbf\{T\}^\{\(i\)\}gradually drifts from𝐓\(0\)\\mathbf\{T\}^\{\(0\)\}with increasing level of supervision along query rounds, and\(2\) the drift of𝐓\\mathbf\{T\}positively correlates with the performance improvement of OT\-based alignment methods, suggesting that the acquired supervision from the oracle gradually corrects𝐓\\mathbf\{T\}to infer accurate alignment\.

## 6Related Work

### 6\.1Optimal Transport

OT has recently attracted increasing attention in alignment problems for its effectiveness in aligning distributional structures and its efficiency enabled by entropic regularization\. For NA, PARROT\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1)\)proposes a regularized OT\-based algorithm and integrates consistency principles for effective cost design\. JOENA\(Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2)\)further unifies embedding learning and OT optimization, enabling end\-to\-end training of an effective and robust NA model\. For CDA, GOT\(Chenet al\.,[2020](https://arxiv.org/html/2605.24395#bib.bib11)\)combines both Wasserstein and Gromov\-Wasserstein distance and proposes a principled framework for regularizing cross\-domain alignment\. DCOT\(Wanget al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib93)\)designs a dual\-view OT framework for cross\-modality retrieval\. While OT has been used extensively for alignment, few works have studied OT\-based alignment methods under active learning settings\.

### 6\.2Active Alignment

Active alignment falls into the broad category of active learning, which studies how to maximally improve the performance of a machine learning model by querying as few supervision as possible from an oracle\(Renet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib94); Liet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib39)\)\. The sparse literature on active alignment mainly focus on network data\.\(Malmiet al\.,[2017](https://arxiv.org/html/2605.24395#bib.bib9)\)proposes two active NA methods that samples the most uncertain nodes via bipartite matching\. Utilizing inter\-network meta diagram and link selection, ActiveIter\(Renet al\.,[2019](https://arxiv.org/html/2605.24395#bib.bib95)\)introduces an active NA methods specifically for social networks\. Attent\(Zhouet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib8)\)proposes an active learning method for attributed consistency\-based NA\. While promising for specific NA tasks, they rely on network data and are not readily applicable to other alignment tasks such as cross\-domain alignment, which are critical stepping stones for cross\-domain and multi\-modal machine learning\(Ganet al\.,[2022](https://arxiv.org/html/2605.24395#bib.bib96); Lianget al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib97); Weiet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib81); Zenget al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib110),[2026b](https://arxiv.org/html/2605.24395#bib.bib63),[a](https://arxiv.org/html/2605.24395#bib.bib89),[2026a](https://arxiv.org/html/2605.24395#bib.bib86)\)\.

## 7Conclusion

In this paper, we study the active alignment problem based on optimal transport\. We select the most informative candidates to query based on their impact on the global alignment results encoded by effective utility functions, computed by gradient propagation through the entropy\-regularized OT formulation\. To differentiate through OT, we leverage the adjoint\-state method to reformulate the computation to solving a linear system, which is solvable via the conjugate gradient method with linear complexity and guaranteed convergence\. Based on these, we propose a generic active learning frameworkAvAtarfor OT\-based alignment applicable to diverse alignment tasks\. Extensive experiments across three different alignment tasks demonstrate the effectiveness and scalability ofAvAtaron real\-world datasets\.

## Impact Statement

This paper presents work whose goal is to advance the field of Active Machine Learning and Optimal Transport\. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here\.

## Acknowledgment

This work is supported by NSF \(2433308, 2416606\) and AFOSR \(FA9550\-24\-1\-0002\)\. The content of the information in this document does not necessarily reflect the position or the policy of the Government, and no official endorsement should be inferred\. The U\.S\. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on\.

## References

- B\. Bartan, R\. Qiu, R\. Esteves, Y\. Ren, W\. W\. Zeng, and A\. Chen \(2025\)FineAMP: optimization\-based automatic mixed precision quantization for efficient diffusion model inference\.The 17th International OPT Workshop on Optimization for Machine Learning\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- S\. Boyd and L\. Vandenberghe \(2004\)Convex optimization\.Cambridge university press\.Cited by:[§A\.3](https://arxiv.org/html/2605.24395#A1.SS3.4.p4.3),[§A\.3](https://arxiv.org/html/2605.24395#A1.SS3.4.p4.8)\.
- L\. Chen, R\. Qiu, S\. Yuan, Z\. Liu, T\. Wei, H\. Yoo, Z\. Zeng, and D\. Yang \(2024\)WAPITI: a watermark for finetuned open\-source LLMs\.arXiv preprint\.Cited by:[§4\.1](https://arxiv.org/html/2605.24395#S4.SS1.p1.3)\.
- L\. Chen, Z\. Gan, Y\. Cheng, L\. Li, L\. Carin, and J\. Liu \(2020\)Graph optimal transport for cross\-domain alignment\.InInternational Conference on Machine Learning,pp\. 1542–1553\.Cited by:[§A\.4](https://arxiv.org/html/2605.24395#A1.SS4.1.p1.17),[Figure 8](https://arxiv.org/html/2605.24395#A3.F8),[Figure 8](https://arxiv.org/html/2605.24395#A3.F8.3.2),[Figure 9](https://arxiv.org/html/2605.24395#A3.F9),[Figure 9](https://arxiv.org/html/2605.24395#A3.F9.3.2),[§1](https://arxiv.org/html/2605.24395#S1.p1.1),[§1](https://arxiv.org/html/2605.24395#S1.p2.1),[§2\.2](https://arxiv.org/html/2605.24395#S2.SS2.p1.1),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px2.p1.1),[Table 4](https://arxiv.org/html/2605.24395#S5.T4.1.1.2.1.2),[Table 4](https://arxiv.org/html/2605.24395#S5.T4.1.1.2.1.3),[Table 5](https://arxiv.org/html/2605.24395#S5.T5.1.1.2.1.2),[Table 5](https://arxiv.org/html/2605.24395#S5.T5.1.1.2.1.3),[§6\.1](https://arxiv.org/html/2605.24395#S6.SS1.p1.1)\.
- S\. Chen, Y\. Qi, M\. Ai, Y\. Sun, R\. Qiu, J\. Zou, and J\. He \(2026\)Influence\-preserving proxies for gradient\-based data selection in LLM finetuning\.InThe Fourteenth International Conference on Learning Representations,Cited by:[§4\.1](https://arxiv.org/html/2605.24395#S4.SS1.p1.3)\.
- A\. Cheng, C\. Zhou, H\. Yang, J\. Wu, L\. Li, J\. Tan, and L\. Guo \(2019\)Deep active learning for anchor user prediction\.arXiv preprint arXiv:1906\.07318\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p3.1)\.
- Y\. Cheng, X\. Zhu, J\. Qian, F\. Wen, and P\. Liu \(2022\)Cross\-modal graph matching network for image\-text retrieval\.ACM Transactions on Multimedia Computing, Communications, and Applications \(TOMM\)18\(4\),pp\. 1–23\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- B\. Du, S\. Zhang, Y\. Yan, and H\. Tong \(2021\)New frontiers of multi\-network mining: recent developments and future trend\.InProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining,pp\. 4038–4039\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- L\. C\. Freeman \(1977\)A set of measures of centrality based on betweenness\.Sociometry,pp\. 35–41\.Cited by:[§B\.2](https://arxiv.org/html/2605.24395#A2.SS2.SSS0.Px5.p1.1)\.
- P\. Gabriel and C\. Marco \(2019\)Computational optimal transport with applications to data sciences\.Foundations and Trends® in Machine Learning11\(5\-6\),pp\. 355–607\.Cited by:[Appendix D](https://arxiv.org/html/2605.24395#A4.p1.1),[§1](https://arxiv.org/html/2605.24395#S1.p2.1),[§2\.1](https://arxiv.org/html/2605.24395#S2.SS1.p2.1),[§4\.1](https://arxiv.org/html/2605.24395#S4.SS1.p3.8)\.
- Z\. Gan, L\. Li, C\. Li, L\. Wang, Z\. Liu, J\. Gao,et al\.\(2022\)Vision\-language pre\-training: basics, recent advances, and future trends\.Foundations and Trends® in Computer Graphics and Vision14\(3–4\),pp\. 163–352\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1),[§1](https://arxiv.org/html/2605.24395#S1.p2.1),[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- Y\. Haitman, A\. Efraim, and J\. M\. Francos \(2024\)UMERegRobust\-universal manifold embedding compatible features for robust point cloud registration\.InEuropean Conference on Computer Vision,pp\. 358–374\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- X\. Han, Z\. Zhang, N\. Ding, Y\. Gu, X\. Liu, Y\. Huo, J\. Qiu, Y\. Yao, A\. Zhang, L\. Zhang,et al\.\(2021\)Pre\-trained models: past, present and future\.Ai Open2,pp\. 225–250\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- K\. Hayami \(2018\)Convergence of the conjugate gradient method on singular systems\.arXiv preprint arXiv:1809\.00793\.Cited by:[§A\.3](https://arxiv.org/html/2605.24395#A1.SS3.1.p1.5),[§A\.5](https://arxiv.org/html/2605.24395#A1.SS5.1.p1.1),[§4\.1\.1](https://arxiv.org/html/2605.24395#S4.SS1.SSS1.p7.3)\.
- X\. He, J\. Kang, R\. Qiu, F\. Wang, J\. Sepulveda, and H\. Tong \(2024\)On the sensitivity of individual fairness: Measures and robust algorithms\.InProceedings of the 33rd ACM International Conference on Information and Knowledge Management,Cited by:[§4\.1](https://arxiv.org/html/2605.24395#S4.SS1.p1.3)\.
- D\. Hendrycks and T\. Dietterich \(2019\)Benchmarking neural network robustness to common corruptions and perturbations\.arXiv preprint arXiv:1903\.12261\.Cited by:[§B\.1](https://arxiv.org/html/2605.24395#A2.SS1.SSS0.Px4),[§B\.1](https://arxiv.org/html/2605.24395#A2.SS1.SSS0.Px5),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px2.p1.1)\.
- E\. F\. Kaasschieter \(1988\)Preconditioned conjugate gradients for solving singular systems\.Journal of Computational and Applied mathematics24\(1\-2\),pp\. 265–275\.Cited by:[§A\.3](https://arxiv.org/html/2605.24395#A1.SS3.1.p1.5),[§A\.4](https://arxiv.org/html/2605.24395#A1.SS4.1.p1.17),[§A\.5](https://arxiv.org/html/2605.24395#A1.SS5.1.p1.13),[§4\.1\.1](https://arxiv.org/html/2605.24395#S4.SS1.SSS1.p7.3)\.
- Y\. Kim and B\. Shin \(2022\)In defense of core\-set: a density\-aware core\-set selection for active learning\.InProceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining,pp\. 804–812\.Cited by:[§B\.2](https://arxiv.org/html/2605.24395#A2.SS2.SSS0.Px6.p1.9)\.
- A\. Korotin, D\. Selikhanovych, and E\. Burnaev \(2022\)Neural optimal transport\.arXiv preprint arXiv:2201\.12220\.Cited by:[Appendix D](https://arxiv.org/html/2605.24395#A4.p1.1)\.
- A\. Krizhevsky, G\. Hinton,et al\.\(2009\)Learning multiple layers of features from tiny images\.Cited by:[§B\.1](https://arxiv.org/html/2605.24395#A2.SS1.SSS0.Px4.p1.1)\.
- D\. Li, Z\. Wang, Y\. Chen, R\. Jiang, W\. Ding, and M\. Okumura \(2024\)A survey on deep active learning: recent advances and new frontiers\.IEEE Transactions on Neural Networks and Learning Systems36\(4\),pp\. 5879–5899\.Cited by:[§B\.2](https://arxiv.org/html/2605.24395#A2.SS2.SSS0.Px6),[§B\.2](https://arxiv.org/html/2605.24395#A2.SS2.SSS0.Px7),[§1](https://arxiv.org/html/2605.24395#S1.p2.1),[§4\.1](https://arxiv.org/html/2605.24395#S4.SS1.p1.3),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px2.p1.1),[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- L\. H\. Li, P\. Zhang, H\. Zhang, J\. Yang, C\. Li, Y\. Zhong, L\. Wang, L\. Yuan, L\. Zhang, J\. Hwang,et al\.\(2022\)Grounded language\-image pre\-training\.InProceedings of the IEEE/CVF conference on computer vision and pattern recognition,pp\. 10965–10975\.Cited by:[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px3.p1.1)\.
- P\. P\. Liang, A\. Zadeh, and L\. Morency \(2024\)Foundations & trends in multimodal machine learning: principles, challenges, and open questions\.ACM Computing Surveys56\(10\),pp\. 1–42\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1),[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- T\. Lin, M\. Maire, S\. Belongie, J\. Hays, P\. Perona, D\. Ramanan, P\. Dollár, and C\. L\. Zitnick \(2014\)Microsoft coco: common objects in context\.InEuropean conference on computer vision,pp\. 740–755\.Cited by:[§B\.1](https://arxiv.org/html/2605.24395#A2.SS1.SSS0.Px6),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px3.p1.1)\.
- Z\. Liu, R\. Qiu, Z\. Zeng, H\. Yoo, D\. Zhou, Z\. Xu, Y\. Zhu, K\. Weldemariam, J\. He, and H\. Tong \(2024\)Class\-imbalanced graph learning without class rebalancing\.InProceedings of the 41st International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p2.1)\.
- S\. A\. Macskassy \(2009\)Using graph\-based metrics with empirical risk minimization to speed up active learning on networked data\.InProceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining,pp\. 597–606\.Cited by:[§A\.4](https://arxiv.org/html/2605.24395#A1.SS4.1.p1.17),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px1.p1.1)\.
- E\. Malmi, A\. Gionis, and E\. Terzi \(2017\)Active network alignment: a matching\-based approach\.InProceedings of the 2017 ACM on Conference on Information and Knowledge Management,pp\. 1687–1696\.Cited by:[§B\.2](https://arxiv.org/html/2605.24395#A2.SS2.SSS0.Px8),[§1](https://arxiv.org/html/2605.24395#S1.p3.1),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px1.p1.1),[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- A\. Nemirovski and U\. Rothblum \(1999\)On complexity of matrix scaling\.Linear Algebra and its Applications302,pp\. 435–460\.Cited by:[§2\.1](https://arxiv.org/html/2605.24395#S2.SS1.p3.3)\.
- X\. Ning, D\. Fu, T\. Wei, W\. Xu, and J\. He \(2025\)Graph4MM: weaving multimodal learning with structural information\.arXiv preprint arXiv:2510\.16990\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- G\. Peyré, M\. Cuturi, and J\. Solomon \(2016\)Gromov\-wasserstein averaging of kernel and distance matrices\.InInternational conference on machine learning,pp\. 2664–2672\.Cited by:[Appendix D](https://arxiv.org/html/2605.24395#A4.p1.1)\.
- B\. A\. Plummer, L\. Wang, C\. M\. Cervantes, J\. C\. Caicedo, J\. Hockenmaier, and S\. Lazebnik \(2015\)Flickr30k entities: collecting region\-to\-phrase correspondences for richer image\-to\-sentence models\.InProceedings of the IEEE international conference on computer vision,pp\. 2641–2649\.Cited by:[§B\.1](https://arxiv.org/html/2605.24395#A2.SS1.SSS0.Px7),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px3.p1.1)\.
- Z\. Qin, H\. Yu, C\. Wang, Y\. Guo, Y\. Peng, S\. Ilic, D\. Hu, and K\. Xu \(2023\)Geotransformer: fast and robust point cloud registration with geometric transformer\.IEEE Transactions on Pattern Analysis and Machine Intelligence45\(8\),pp\. 9806–9821\.Cited by:[Appendix D](https://arxiv.org/html/2605.24395#A4.p1.1),[§1](https://arxiv.org/html/2605.24395#S1.p2.1)\.
- R\. Qiu, J\. Jang, X\. Lin, L\. Liu, and H\. Tong \(2024\)TUCKET: a tensor time series data structure for efficient and accurate factor analysis over time ranges\.InProceedings of the VLDB Endowment 17,Cited by:[Appendix D](https://arxiv.org/html/2605.24395#A4.p1.1)\.
- R\. Qiu and H\. Tong \(2024\)Gradient compressed sensing: A query\-efficient gradient estimator for high\-dimensional zeroth\-order optimization\.InProceedings of the 41st International Conference on Machine Learning,Cited by:[§4\.1](https://arxiv.org/html/2605.24395#S4.SS1.p1.3)\.
- P\. Ren, Y\. Xiao, X\. Chang, P\. Huang, Z\. Li, B\. B\. Gupta, X\. Chen, and X\. Wang \(2021\)A survey of deep active learning\.ACM computing surveys \(CSUR\)54\(9\),pp\. 1–40\.Cited by:[§B\.2](https://arxiv.org/html/2605.24395#A2.SS2.SSS0.Px2),[§B\.2](https://arxiv.org/html/2605.24395#A2.SS2.SSS0.Px3),[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- Y\. Ren, C\. C\. Aggarwal, and J\. Zhang \(2019\)Meta diagram based active social networks alignment\.In2019 IEEE 35th International Conference on Data Engineering \(ICDE\),pp\. 1690–1693\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p3.1),[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- M\. Sadr, T\. Tohme, and K\. Youcef\-Toumi \(2024\)Data\-driven discovery of pdes via the adjoint method\.arXiv preprint arXiv:2401\.17177\.Cited by:[§4\.1\.1](https://arxiv.org/html/2605.24395#S4.SS1.SSS1.p5.1)\.
- F\. Santambrogio \(2015\)Optimal transport for applied mathematicians\.Cited by:[§2\.1](https://arxiv.org/html/2605.24395#S2.SS1.p1.4)\.
- G\. Strang \(2022\)Introduction to linear algebra\.SIAM\.Cited by:[§A\.3](https://arxiv.org/html/2605.24395#A1.SS3.3.p3.13)\.
- J\. Tang, W\. Zhang, J\. Li, K\. Zhao, F\. Tsung, and J\. Li \(2023\)Robust attributed graph alignment via joint structure learning and optimal transport\.In2023 IEEE 39th International Conference on Data Engineering \(ICDE\),pp\. 1638–1651\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- J\. Tang, J\. Zhang, L\. Yao, J\. Li, L\. Zhang, and Z\. Su \(2008\)Arnetminer: extraction and mining of academic social networks\.InProceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining,pp\. 990–998\.Cited by:[§B\.1](https://arxiv.org/html/2605.24395#A2.SS1.SSS0.Px2),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px1.p1.1)\.
- D\. Wang, Y\. Yan, R\. Qiu, Y\. Zhu, K\. Guan, A\. J\. Margenot, and H\. Tong \(2023\)Networked time series imputation via position\-aware graph enhanced variational autoencoders\.InProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- Y\. Wang, S\. Wang, H\. Luo, J\. Dong, F\. Wang, M\. Han, X\. Wang, and M\. Wang \(2024\)Dual\-view curricular optimal transport for cross\-lingual cross\-modal retrieval\.IEEE Transactions on Image Processing33,pp\. 1522–1533\.Cited by:[§6\.1](https://arxiv.org/html/2605.24395#S6.SS1.p1.1)\.
- T\. Wei, R\. Qiu, Y\. Chen, Y\. Qi, J\. Lin, W\. Xu, S\. Nag, R\. Li, H\. Lu, Z\. Wang,et al\.\(2024\)Robust watermarking for diffusion models: a unified multi\-dimensional recipe, 2024b\.URL https://openreview\. net/pdf\.Cited by:[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- T\. Wei, R\. Qiu, Y\. Chen, Y\. Qi, J\. Lin, W\. Bao, W\. Xu, S\. Nag, R\. Li, H\. Lu, Z\. Wang, C\. Luo, H\. Liu, S\. Wang, J\. He, Q\. He, and X\. Tang \(2026\)DiffKGW: stealthy and robust diffusion model watermarking\.Transactions on Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- Z\. Xu, R\. Qiu, Y\. Chen, H\. Chen, X\. Fan, M\. Pan, Z\. Zeng, M\. Das, and H\. Tong \(2024\)Discrete\-state continuous\-time diffusion for graph generation\.InAdvances in Neural Information Processing Systems 37,Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- Y\. Yan, Q\. Zhou, J\. Li, T\. Abdelzaher, and H\. Tong \(2022\)Dissecting cross\-layer dependency inference on multi\-layered inter\-dependent networks\.InProceedings of the 31st ACM International Conference on Information & Knowledge Management,pp\. 2341–2351\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- Z\. A\. Yilmaz, W\. Yang, H\. Zhang, and J\. Lin \(2019\)Cross\-domain modeling of sentence\-level evidence for document retrieval\.InProceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing \(EMNLP\-IJCNLP\),pp\. 3490–3496\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- H\. Yoo, Z\. Zeng, J\. Kang, R\. Qiu, D\. Zhou, Z\. Liu, F\. Wang, C\. Xu, E\. Chan, and H\. Tong \(2024\)Ensuring user\-side fairness in dynamic recommender systems\.InProceedings of the ACM Web Conference 2024,Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- P\. Young, A\. Lai, M\. Hodosh, and J\. Hockenmaier \(2014\)From image descriptions to visual denotations: new similarity metrics for semantic inference over event descriptions\.Transactions of the association for computational linguistics2,pp\. 67–78\.Cited by:[§B\.1](https://arxiv.org/html/2605.24395#A2.SS1.SSS0.Px7.p1.1)\.
- H\. Yu, F\. Li, M\. Saleh, B\. Busam, and S\. Ilic \(2021\)Cofinet: reliable coarse\-to\-fine correspondences for robust pointcloud registration\.Advances in Neural Information Processing Systems34,pp\. 23872–23884\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- H\. Yu, Z\. Qin, J\. Hou, M\. Saleh, D\. Li, B\. Busam, and S\. Ilic \(2023\)Rotation\-invariant transformer for point cloud matching\.InProceedings of the IEEE/CVF conference on computer vision and pattern recognition,pp\. 5384–5393\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- Q\. Yu, Z\. Zeng, Y\. Yan, Z\. Liu, B\. Jing, R\. Qiu, A\. Azad, and H\. Tong \(2025a\)PLANETALIGN: a comprehensive python library for benchmarking network alignment\.arXiv preprint arXiv:2505\.21366\.Cited by:[§A\.4](https://arxiv.org/html/2605.24395#A1.SS4.1.p1.17),[§1](https://arxiv.org/html/2605.24395#S1.p1.1),[§1](https://arxiv.org/html/2605.24395#S1.p2.1)\.
- Q\. Yu, Z\. Zeng, Y\. Yan, L\. Ying, R\. Srikant, and H\. Tong \(2025b\)Joint optimal transport and embedding for network alignment\.InProceedings of the ACM on Web Conference 2025,pp\. 2064–2075\.Cited by:[Figure 7](https://arxiv.org/html/2605.24395#A3.F7),[Figure 7](https://arxiv.org/html/2605.24395#A3.F7.3.2),[§1](https://arxiv.org/html/2605.24395#S1.p1.1),[§1](https://arxiv.org/html/2605.24395#S1.p2.1),[§2\.2](https://arxiv.org/html/2605.24395#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2605.24395#S2.SS2.p2.2),[§4\.1](https://arxiv.org/html/2605.24395#S4.SS1.p3.8),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px1.p1.1),[Table 3](https://arxiv.org/html/2605.24395#S5.T3.2.2.14.9.1),[§6\.1](https://arxiv.org/html/2605.24395#S6.SS1.p1.1),[footnote 1](https://arxiv.org/html/2605.24395#footnote1),[footnote 2](https://arxiv.org/html/2605.24395#footnote2)\.
- Z\. Zeng, W\. Bao, X\. Lin, R\. Qiu, T\. Wei, X\. Ning, Y\. Yan, C\. Luo, M\. X\. Cheng, J\. He, and H\. Tong \(2026a\)Subspace alignment for vision\-language model test\-time adaptation\.arXiv preprint\.Cited by:[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- Z\. Zeng, B\. Du, S\. Zhang, Y\. Xia, Z\. Liu, and H\. Tong \(2024a\)Hierarchical multi\-marginal optimal transport for network alignment\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 16660–16668\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- Z\. Zeng, M\. Hang, X\. Liu, X\. Liu, X\. Lin, R\. Qiu, T\. Wei, Z\. Liu, S\. Yuan, C\. Yang, Y\. Liu, H\. Yin, J\. Yang, and H\. Tong \(2025a\)Hierarchical LoRA MoE for efficient CTR model scaling\.arXiv preprint\.Cited by:[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- Z\. Zeng, X\. Liu, M\. Hang, X\. Liu, Q\. Zhou, C\. Yang, Y\. Liu, Y\. Ruan, L\. Chen, Y\. Chen,et al\.\(2025b\)InterFormer: effective heterogeneous interaction learning for click\-through rate prediction\.InProceedings of the 34th ACM International Conference on Information and Knowledge Management,pp\. 6225–6233\.Cited by:[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- Z\. Zeng, R\. Qiu, W\. Bao, T\. Wei, X\. Lin, Y\. Yan, T\. F\. Abdelzaher, J\. Han, and H\. Tong \(2025c\)Pave your own path: graph gradual domain adaptation on fused gromov\-wasserstein geodesics\.arXiv preprint arXiv:2505\.12709\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- Z\. Zeng, R\. Qiu, Z\. Xu, Z\. Liu, Y\. Yan, T\. Wei, L\. Ying, J\. He, and H\. Tong \(2024b\)Graph mixup on approximate Gromov–Wasserstein geodesics\.InProceedings of the 41st International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- Z\. Zeng, Q\. Yu, X\. Lin, R\. Qiu, X\. Ning, T\. Wei, Y\. Yan, J\. He, and H\. Tong \(2026b\)Harnessing consistency for robust test\-time LLM ensemble\.Findings of the Association for Computational Linguistics: EACL 2026\.Cited by:[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.
- Z\. Zeng, S\. Zhang, Y\. Xia, and H\. Tong \(2023a\)Parrot: position\-aware regularized optimal transport for network alignment\.InProceedings of the ACM web conference 2023,pp\. 372–382\.Cited by:[§A\.4](https://arxiv.org/html/2605.24395#A1.SS4.1.p1.17),[Figure 11](https://arxiv.org/html/2605.24395#A3.F11),[Figure 11](https://arxiv.org/html/2605.24395#A3.F11.4.2),[Figure 6](https://arxiv.org/html/2605.24395#A3.F6),[Figure 6](https://arxiv.org/html/2605.24395#A3.F6.3.2),[§C\.3](https://arxiv.org/html/2605.24395#A3.SS3.p1.1),[§C\.4](https://arxiv.org/html/2605.24395#A3.SS4.p1.2),[§1](https://arxiv.org/html/2605.24395#S1.p1.1),[§2\.2](https://arxiv.org/html/2605.24395#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2605.24395#S2.SS2.p2.2),[§4\.1](https://arxiv.org/html/2605.24395#S4.SS1.p3.8),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px1.p1.1),[§5\.3](https://arxiv.org/html/2605.24395#S5.SS3.p1.3),[Table 3](https://arxiv.org/html/2605.24395#S5.T3.2.2.5.3.1),[§6\.1](https://arxiv.org/html/2605.24395#S6.SS1.p1.1),[footnote 1](https://arxiv.org/html/2605.24395#footnote1),[footnote 2](https://arxiv.org/html/2605.24395#footnote2)\.
- Z\. Zeng, R\. Zhu, Y\. Xia, H\. Zeng, and H\. Tong \(2023b\)Generative graph dictionary learning\.InInternational Conference on Machine Learning,pp\. 40749–40769\.Cited by:[§1](https://arxiv.org/html/2605.24395#S1.p1.1)\.
- S\. Zhang, H\. Tong, J\. Tang, J\. Xu, and W\. Fan \(2017\)Ineat: incomplete network alignment\.In2017 IEEE International Conference on Data Mining \(ICDM\),pp\. 1189–1194\.Cited by:[§B\.1](https://arxiv.org/html/2605.24395#A2.SS1.SSS0.Px1),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px1.p1.1)\.
- S\. Zhang and H\. Tong \(2016\)Final: fast attributed network alignment\.InProceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining,pp\. 1345–1354\.Cited by:[§B\.1](https://arxiv.org/html/2605.24395#A2.SS1.SSS0.Px3),[§C\.3](https://arxiv.org/html/2605.24395#A3.SS3.p1.1),[§4\.1](https://arxiv.org/html/2605.24395#S4.SS1.p3.8),[§5\.1](https://arxiv.org/html/2605.24395#S5.SS1.SSS0.Px1.p1.1)\.
- Q\. Zhou, L\. Li, X\. Wu, N\. Cao, L\. Ying, and H\. Tong \(2021\)Attent: active attributed network alignment\.InProceedings of the Web Conference 2021,pp\. 3896–3906\.Cited by:[§B\.2](https://arxiv.org/html/2605.24395#A2.SS2.SSS0.Px4),[§B\.2](https://arxiv.org/html/2605.24395#A2.SS2.SSS0.Px5),[§C\.3](https://arxiv.org/html/2605.24395#A3.SS3.p1.1),[§1](https://arxiv.org/html/2605.24395#S1.p2.1),[§1](https://arxiv.org/html/2605.24395#S1.p3.1),[§3](https://arxiv.org/html/2605.24395#S3.p1.1),[§4\.1](https://arxiv.org/html/2605.24395#S4.SS1.p1.3),[§6\.2](https://arxiv.org/html/2605.24395#S6.SS2.p1.1)\.

## Appendix AProof

### A\.1Proof of Lemma[4\.2](https://arxiv.org/html/2605.24395#S4.Thmtheorem2)

###### Lemma\.

The gradient of a utility functionf​\(𝐓\)f\(\\mathbf\{T\}\)w\.r\.t\. the cost function𝐂~\\tilde\{\\mathbf\{C\}\}under the entropy\-regularized OT formulation can be computed by solving a linear system with respect to adjoint vectors𝐲α∈ℝn,𝐲β∈ℝm\\mathbf\{y\}\_\{\\alpha\}\\in\\mathbb\{R\}^\{n\},\\mathbf\{y\}\_\{\\beta\}\\in\\mathbb\{R\}^\{m\}as follows,

∇𝐂~f=1ϵ​𝐓⊙\(𝐲α​𝟏m⊤\+𝟏n​𝐲β⊤−∇𝐓f\)\\nabla\_\{\\tilde\{\\mathbf\{C\}\}\}f=\\frac\{1\}\{\\epsilon\}\\mathbf\{T\}\\odot\\left\(\\mathbf\{y\}\_\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\+\\mathbf\{1\}\_\{n\}\\mathbf\{y\}\_\{\\beta\}^\{\\top\}\-\\nabla\_\{\\mathbf\{T\}\}f\\right\)\(9\)s\.t\.

\[diag​\(𝝁\)𝐓𝐓⊤diag​\(𝝂\)\]⏟𝐀​\[𝐲α𝐲β\]⏟𝐲=\[\(𝐓⊙∇𝐓f\)​𝟏m\(𝐓⊙∇𝐓f\)⊤​𝟏n\]⏟𝐛\\underbrace\{\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)&\\mathbf\{T\}\\\\ \\mathbf\{T\}^\{\\top\}&\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\end\{bmatrix\}\}\_\{\\mathbf\{A\}\}\\underbrace\{\\begin\{bmatrix\}\\mathbf\{y\}\_\{\\alpha\}\\\\ \\mathbf\{y\}\_\{\\beta\}\\end\{bmatrix\}\}\_\{\\mathbf\{y\}\}=\\underbrace\{\\begin\{bmatrix\}\\left\(\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\\right\)\\mathbf\{1\}\_\{m\}\\\\ \\left\(\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\}\}\_\{\\mathbf\{b\}\}\(10\)whereϵ\\epsilonis the entropic regularization weight,𝛍,𝛎\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}are marginal distributions of OT, anddiag​\(⋅\)\\text\{diag\}\(\\cdot\)creates a diagonal matrix from a vector\.

###### Proof\.

Consider the entropy\-regularized OT formulation in Eq\. \([2](https://arxiv.org/html/2605.24395#S2.E2)\)\. We introduce two dual variables𝜶∈ℝn,𝜷∈ℝm\\boldsymbol\{\\alpha\}\\in\\mathbb\{R\}^\{n\},\\boldsymbol\{\\beta\}\\in\\mathbb\{R\}^\{m\}for the marginal constraints of OT, and gives the Lagrangian of Eq\. \([2](https://arxiv.org/html/2605.24395#S2.E2)\) as

ℒ​\(𝐓,𝜶,𝜷\)=⟨𝐂~,𝐓⟩\+ϵ​∑i,j𝐓i,j​\(log⁡𝐓i,j−1\)\+𝜶⊤​\(𝝁−𝐓𝟏m\)\+𝜷⊤​\(𝝂−𝐓⊤​𝟏n\)\\mathcal\{L\}\(\\mathbf\{T\},\\boldsymbol\{\\alpha\},\\boldsymbol\{\\beta\}\)=\\langle\\tilde\{\\mathbf\{C\}\},\\mathbf\{T\}\\rangle\+\\epsilon\\sum\_\{i,j\}\\mathbf\{T\}\_\{i,j\}\\left\(\\log\\mathbf\{T\}\_\{i,j\}\-1\\right\)\+\\boldsymbol\{\\alpha\}^\{\\top\}\(\\boldsymbol\{\\mu\}\-\\mathbf\{T\}\\mathbf\{1\}\_\{m\}\)\+\\boldsymbol\{\\beta\}^\{\\top\}\(\\boldsymbol\{\\nu\}\-\\mathbf\{T\}^\{\\top\}\\mathbf\{1\}\_\{n\}\)\(11\)The first order condition gives

∂ℒ​\(𝐓,𝜶,𝜷\)∂𝐓i,j=𝐂~i,j\+ϵ​log⁡𝐓i,j−𝜶i−𝜷j=0\\frac\{\\partial\\mathcal\{L\}\(\\mathbf\{T\},\\boldsymbol\{\\alpha\},\\boldsymbol\{\\beta\}\)\}\{\\partial\\mathbf\{T\}\_\{i,j\}\}=\\tilde\{\\mathbf\{C\}\}\_\{i,j\}\+\\epsilon\\log\\mathbf\{T\}\_\{i,j\}\-\\boldsymbol\{\\alpha\}\_\{i\}\-\\boldsymbol\{\\beta\}\_\{j\}=0\(12\)which yields

𝐓i,j=exp⁡\(𝜶i\+𝜷j−𝐂~i,jϵ\)\\mathbf\{T\}\_\{i,j\}=\\exp\\left\(\\frac\{\\boldsymbol\{\\alpha\}\_\{i\}\+\\boldsymbol\{\\beta\}\_\{j\}\-\\tilde\{\\mathbf\{C\}\}\_\{i,j\}\}\{\\epsilon\}\\right\)\(13\)for an optimal transport map𝐓\\mathbf\{T\}to the entropy\-regularized OT problem\. We take the differential of Eq\. \([13](https://arxiv.org/html/2605.24395#A1.E13)\) as follows

d​𝐂~i,j\+ϵ​d​\(log⁡𝐓i,j\)−d​𝜶i−d​𝜷j=0\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\_\{i,j\}\+\\epsilon\\mathrm\{d\}\\left\(\\log\\mathbf\{T\}\_\{i,j\}\\right\)\-\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}\_\{i\}\-\\mathrm\{d\}\\boldsymbol\{\\beta\}\_\{j\}=0\(14\)which can be reformulated in matrix form as follows

d​𝐓=1ϵ​𝐓⊙\(d​𝜶​𝟏m⊤\+𝟏n​d​𝜷⊤−d​𝐂~\)\\mathrm\{d\}\\mathbf\{T\}=\\frac\{1\}\{\\epsilon\}\\mathbf\{T\}\\odot\\left\(\\mathrm\{d\}\\boldsymbol\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\+\\mathbf\{1\}\_\{n\}\\mathrm\{d\}\\boldsymbol\{\\beta\}^\{\\top\}\-\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)\(15\)Next, we impose the marginal constraints to derive a linear system of equations\. Since the marginal constraints of OT are always satisfied, their differentials must be zero, i\.e\.,

d​𝐓𝟏m=0\\mathrm\{d\}\\mathbf\{T\}\\mathbf\{1\}\_\{m\}=0\(16\)\(d​𝐓\)⊤​𝟏n=0\\left\(\\mathrm\{d\}\\mathbf\{T\}\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}=0\(17\)Firstly, we plug Eq\. \([15](https://arxiv.org/html/2605.24395#A1.E15)\) into Eq\. \([16](https://arxiv.org/html/2605.24395#A1.E16)\), which gives

1ϵ​\(\(𝐓⊙\(d​𝜶​𝟏m⊤\)\)​𝟏m\+\(𝐓⊙\(𝟏n​d​𝜷⊤\)\)​𝟏m−\(𝐓⊙d​𝐂~\)​𝟏m\)=0\\frac\{1\}\{\\epsilon\}\\left\(\\left\(\\mathbf\{T\}\\odot\\left\(\\mathrm\{d\}\\boldsymbol\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\\right\)\\right\)\\mathbf\{1\}\_\{m\}\+\\left\(\\mathbf\{T\}\\odot\\left\(\\mathbf\{1\}\_\{n\}\\mathrm\{d\}\\boldsymbol\{\\beta\}^\{\\top\}\\right\)\\right\)\\mathbf\{1\}\_\{m\}\-\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)\\mathbf\{1\}\_\{m\}\\right\)=0\(18\)where

\{\(𝐓⊙\(d​𝜶​𝟏m⊤\)\)​𝟏m=\(𝐓𝟏m\)⊙d​𝜶=diag​\(𝝁\)​d​𝜶\(𝐓⊙\(𝟏n​d​𝜷⊤\)\)​𝟏m=𝐓​d​𝜷\\left\\\{\\begin\{aligned\} &\\left\(\\mathbf\{T\}\\odot\\left\(\\mathrm\{d\}\\boldsymbol\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\\right\)\\right\)\\mathbf\{1\}\_\{m\}=\\left\(\\mathbf\{T\}\\mathbf\{1\}\_\{m\}\\right\)\\odot\\mathrm\{d\}\\boldsymbol\{\\alpha\}=\\text\{diag\}\(\\boldsymbol\{\\mu\}\)\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}\\\\ &\\left\(\\mathbf\{T\}\\odot\\left\(\\mathbf\{1\}\_\{n\}\\mathrm\{d\}\\boldsymbol\{\\beta\}^\{\\top\}\\right\)\\right\)\\mathbf\{1\}\_\{m\}=\\mathbf\{T\}\\mathrm\{d\}\\boldsymbol\{\\beta\}\\end\{aligned\}\\right\.\(19\)Therefore, Eq \([18](https://arxiv.org/html/2605.24395#A1.E18)\) gives the first part of the linear system as follows

diag​\(𝝁\)​d​𝜶\+𝐓​d​𝜷=\(𝐓⊙d​𝐂~\)​𝟏m\\text\{diag\}\(\\boldsymbol\{\\mu\}\)\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}\+\\mathbf\{T\}\\mathrm\{d\}\\boldsymbol\{\\beta\}=\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)\\mathbf\{1\}\_\{m\}\(20\)Secondly, we plug Eq\. \([15](https://arxiv.org/html/2605.24395#A1.E15)\) into Eq\. \([17](https://arxiv.org/html/2605.24395#A1.E17)\), which gives

1ϵ​\(\(𝐓⊙\(d​𝜶​𝟏m⊤\)\)⊤​𝟏n\+\(𝐓⊙\(𝟏n​d​𝜷⊤\)\)⊤​𝟏n−\(𝐓⊙d​𝐂~\)⊤​𝟏n\)=0\\frac\{1\}\{\\epsilon\}\\left\(\\left\(\\mathbf\{T\}\\odot\\left\(\\mathrm\{d\}\\boldsymbol\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\\right\)\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\+\\left\(\\mathbf\{T\}\\odot\\left\(\\mathbf\{1\}\_\{n\}\\mathrm\{d\}\\boldsymbol\{\\beta\}^\{\\top\}\\right\)\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\-\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\right\)=0\(21\)where

\{\(𝐓⊙\(d​𝜶​𝟏m⊤\)\)⊤​𝟏n=𝐓⊤​d​𝜶\(𝐓⊙\(𝟏n​d​𝜷⊤\)\)⊤​𝟏n=\(𝐓⊤​𝟏n\)⊙d​𝜷=diag​\(𝝂\)​d​𝜷\\left\\\{\\begin\{aligned\} &\\left\(\\mathbf\{T\}\\odot\\left\(\\mathrm\{d\}\\boldsymbol\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\\right\)\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}=\\mathbf\{T\}^\{\\top\}\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}\\\\ &\\left\(\\mathbf\{T\}\\odot\\left\(\\mathbf\{1\}\_\{n\}\\mathrm\{d\}\\boldsymbol\{\\beta\}^\{\\top\}\\right\)\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}=\\left\(\\mathbf\{T\}^\{\\top\}\\mathbf\{1\}\_\{n\}\\right\)\\odot\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\beta\}\}=\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\mathrm\{d\}\\boldsymbol\{\\beta\}\\end\{aligned\}\\right\.\(22\)Therefore, Eq \([21](https://arxiv.org/html/2605.24395#A1.E21)\) gives the second part of the linear system as follows

𝐓⊤​d​𝜶\+diag​\(𝝂\)​d​𝜷=\(𝐓⊙d​𝐂~\)⊤​𝟏n\\mathbf\{T\}^\{\\top\}\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}\+\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\mathrm\{d\}\\boldsymbol\{\\beta\}=\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\(23\)Combining Eq\. \([20](https://arxiv.org/html/2605.24395#A1.E20)\) and \([23](https://arxiv.org/html/2605.24395#A1.E23)\) gives a block linear system as follows

\[diag​\(𝝁\)𝐓𝐓⊤diag​\(𝝂\)\]​\[d​𝜶d​𝜷\]=\[\(𝐓⊙d​𝐂~\)​𝟏m\(𝐓⊙d​𝐂~\)⊤​𝟏n\]\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)&\\mathbf\{T\}\\\\ \\mathbf\{T\}^\{\\top\}&\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\end\{bmatrix\}\\begin\{bmatrix\}\\mathrm\{d\}\\boldsymbol\{\\alpha\}\\\\ \\mathrm\{d\}\\boldsymbol\{\\beta\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)\\mathbf\{1\}\_\{m\}\\\\ \\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\}\(24\)Now, we derive the differential of utility functionf​\(𝐓\):ℝn×m→ℝf\(\\mathbf\{T\}\):\\mathbb\{R\}^\{n\\times m\}\\rightarrow\\mathbb\{R\}\. By definition,d​f=⟨∇𝐓f,d​𝐓⟩\\mathrm\{d\}f=\\langle\\nabla\_\{\\mathbf\{T\}\}f,\\mathrm\{d\}\\mathbf\{T\}\\rangle\. We plug this equation into Eq\. \([15](https://arxiv.org/html/2605.24395#A1.E15)\), which gives

d​f=1ϵ​\(⟨𝐆𝟏m,d​𝜶⟩\+⟨𝐆⊤​𝟏n,d​𝜷⟩⏟Ω−⟨𝐆,d​𝐂~⟩\)\\mathrm\{d\}f=\\frac\{1\}\{\\epsilon\}\\left\(\\underbrace\{\\langle\\mathbf\{G\}\\mathbf\{1\}\_\{m\},\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}\\rangle\+\\langle\\mathbf\{G\}^\{\\top\}\\mathbf\{1\}\_\{n\},\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\beta\}\}\\rangle\}\_\{\\Omega\}\-\\langle\\mathbf\{G\},\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\rangle\\right\)\(25\)where𝐆\\mathbf\{G\}is defined as

𝐆:=𝐓⊙∇𝐓f\\mathbf\{G\}:=\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\(26\)At this point, bothd​𝜶\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}andd​𝜷\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\beta\}\}are implicitly defined by Eq\. \([24](https://arxiv.org/html/2605.24395#A1.E24)\)\. To eliminated​𝜶,d​𝜷\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\},\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\beta\}\}, we introduce an adjoint vector𝐲∈ℝn\+m\\mathbf\{y\}\\in\\mathbb\{R\}^\{n\+m\}and define the following linear system in Eq\. \([27](https://arxiv.org/html/2605.24395#A1.E27)\)\. For readability, We write𝐲=\[𝐲α𝐲β\]\\mathbf\{y\}=\\begin\{bmatrix\}\\mathbf\{y\}\_\{\\alpha\}\\\\ \\mathbf\{y\}\_\{\\beta\}\\end\{bmatrix\}where𝐲α∈ℝn,𝐲β∈ℝm\\mathbf\{y\}\_\{\\alpha\}\\in\\mathbb\{R\}^\{n\},\\mathbf\{y\}\_\{\\beta\}\\in\\mathbb\{R\}^\{m\}\.

\[diag​\(𝝁\)𝐓𝐓⊤diag​\(𝝂\)\]​\[𝐲α𝐲β\]=\[𝐆𝟏m𝐆⊤​𝟏n\]\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)&\\mathbf\{T\}\\\\ \\mathbf\{T\}^\{\\top\}&\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\end\{bmatrix\}\\begin\{bmatrix\}\\mathbf\{y\}\_\{\\alpha\}\\\\ \\mathbf\{y\}\_\{\\beta\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\mathbf\{G\}\\mathbf\{1\}\_\{m\}\\\\ \\mathbf\{G\}^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\}\(27\)Let

𝐀=\[diag​\(𝝁\)𝐓𝐓⊤diag​\(𝝂\)\]\\mathbf\{A\}=\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)&\\mathbf\{T\}\\\\ \\mathbf\{T\}^\{\\top\}&\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\end\{bmatrix\}\(28\)For Eq\. \([24](https://arxiv.org/html/2605.24395#A1.E24)\) and \([27](https://arxiv.org/html/2605.24395#A1.E27)\), we have

𝐀​\[d​𝜶d​𝜷\]=\[\(𝐓⊙d​𝐂~\)​𝟏m\(𝐓⊙d​𝐂~\)⊤​𝟏n\],𝐀​\[𝐲α𝐲β\]=\[𝐆𝟏m𝐆⊤​𝟏n\]\\mathbf\{A\}\\begin\{bmatrix\}\\mathrm\{d\}\\boldsymbol\{\\alpha\}\\\\ \\mathrm\{d\}\\boldsymbol\{\\beta\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)\\mathbf\{1\}\_\{m\}\\\\ \\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\},~~~\\mathbf\{A\}\\begin\{bmatrix\}\\mathbf\{y\}\_\{\\alpha\}\\\\ \\mathbf\{y\}\_\{\\beta\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\mathbf\{G\}\\mathbf\{1\}\_\{m\}\\\\ \\mathbf\{G\}^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\}\(29\)Now, we can reformulate theΩ\\Omegaterm in Eq \([25](https://arxiv.org/html/2605.24395#A1.E25)\) as follows

Ω\\displaystyle\\Omega=⟨𝐆𝟏m,d​𝜶⟩\+⟨𝐆⊤​𝟏n,d​𝜷⟩=⟨\[𝐆𝟏m𝐆⊤​𝟏n\],\[d​𝜶d​𝜷\]⟩\\displaystyle=\\langle\\mathbf\{G\}\\mathbf\{1\}\_\{m\},\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}\\rangle\+\\langle\\mathbf\{G\}^\{\\top\}\\mathbf\{1\}\_\{n\},\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\beta\}\}\\rangle=\\left\\langle\\begin\{bmatrix\}\\mathbf\{G\}\\mathbf\{1\}\_\{m\}\\\\ \\mathbf\{G\}^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\},\\begin\{bmatrix\}\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}\\\\ \\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\beta\}\}\\end\{bmatrix\}\\right\\rangle\(30\)=⟨𝐀​\[𝐲α𝐲β\],\[d​𝜶d​𝜷\]⟩=⟨\[𝐲α𝐲β\],𝐀​\[d​𝜶d​𝜷\]⟩⏟given that​𝐀=𝐀⊤\\displaystyle=\\underbrace\{\\left\\langle\\mathbf\{A\}\\begin\{bmatrix\}\\mathbf\{y\}\_\{\\alpha\}\\\\ \\mathbf\{y\}\_\{\\beta\}\\end\{bmatrix\},\\begin\{bmatrix\}\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}\\\\ \\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\beta\}\}\\end\{bmatrix\}\\right\\rangle=\\left\\langle\\begin\{bmatrix\}\\mathbf\{y\}\_\{\\alpha\}\\\\ \\mathbf\{y\}\_\{\\beta\}\\end\{bmatrix\},\\mathbf\{A\}\\begin\{bmatrix\}\\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\alpha\}\}\\\\ \\mathrm\{d\}\\boldsymbol\{\\mathbf\{\\beta\}\}\\end\{bmatrix\}\\right\\rangle\}\_\{\\text\{given that \}\\mathbf\{A\}=\\mathbf\{A\}^\{\\top\}\}=⟨\[𝐲α𝐲β\],\[\(𝐓⊙d​𝐂~\)​𝟏m\(𝐓⊙d​𝐂~\)⊤​𝟏n\]⟩=⟨𝐲α,\(𝐓⊙d​𝐂~\)​𝟏m⟩\+⟨𝐲β,\(𝐓⊙d​𝐂~\)⊤​𝟏n⟩\\displaystyle=\\left\\langle\\begin\{bmatrix\}\\mathbf\{y\}\_\{\\alpha\}\\\\ \\mathbf\{y\}\_\{\\beta\}\\end\{bmatrix\},\\begin\{bmatrix\}\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)\\mathbf\{1\}\_\{m\}\\\\ \\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\}\\right\\rangle=\\langle\\mathbf\{y\}\_\{\\alpha\},\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)\\mathbf\{1\}\_\{m\}\\rangle\+\\langle\\mathbf\{y\}\_\{\\beta\},\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\rangleTherefore, we reformulate Eq \([25](https://arxiv.org/html/2605.24395#A1.E25)\) as follows

d​f\\displaystyle\\mathrm\{d\}f=1ϵ​\(⟨𝐲α,\(𝐓⊙d​𝐂~\)​𝟏m⟩\+⟨𝐲β,\(𝐓⊙d​𝐂~\)⊤​𝟏n⟩−⟨𝐆,d​𝐂~⟩\)\\displaystyle=\\frac\{1\}\{\\epsilon\}\\left\(\\langle\\mathbf\{y\}\_\{\\alpha\},\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)\\mathbf\{1\}\_\{m\}\\rangle\+\\langle\\mathbf\{y\}\_\{\\beta\},\\left\(\\mathbf\{T\}\\odot\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\rangle\-\\langle\\mathbf\{G\},\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\rangle\\right\)\(31\)=1ϵ​\(⟨𝐓⊙\(𝐲α​𝟏m⊤\),d​𝐂~⟩\+⟨𝐓⊙\(𝟏n​𝐲β⊤\),d​𝐂~⟩−⟨𝐆,d​𝐂~⟩\)\\displaystyle=\\frac\{1\}\{\\epsilon\}\\left\(\\langle\\mathbf\{T\}\\odot\\left\(\\mathbf\{y\}\_\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\\right\),\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\rangle\+\\langle\\mathbf\{T\}\\odot\\left\(\\mathbf\{1\}\_\{n\}\\mathbf\{y\}\_\{\\beta\}^\{\\top\}\\right\),\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\rangle\-\\langle\\mathbf\{G\},\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\rangle\\right\)=⟨1ϵ​𝐓⊙\(𝐲α​𝟏m⊤\+𝟏n​𝐲β⊤−∇𝐓f\),d​𝐂~⟩\\displaystyle=\\left\\langle\\frac\{1\}\{\\epsilon\}\\mathbf\{T\}\\odot\\left\(\\mathbf\{y\}\_\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\+\\mathbf\{1\}\_\{n\}\\mathbf\{y\}\_\{\\beta\}^\{\\top\}\-\\nabla\_\{\\mathbf\{T\}\}f\\right\),\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\\right\\rangleIn this way, we have the final formulation of∇𝐂~f\\nabla\_\{\\tilde\{\\mathbf\{C\}\}\}fas follows

∇𝐂~f=d​fd​𝐂~=1ϵ​𝐓⊙\(𝐲α​𝟏m⊤\+𝟏n​𝐲β⊤−∇𝐓f\)\\nabla\_\{\\tilde\{\\mathbf\{C\}\}\}f=\\frac\{\\mathrm\{d\}f\}\{\\mathrm\{d\}\\tilde\{\\mathbf\{C\}\}\}=\\frac\{1\}\{\\epsilon\}\\mathbf\{T\}\\odot\\left\(\\mathbf\{y\}\_\{\\alpha\}\\mathbf\{1\}\_\{m\}^\{\\top\}\+\\mathbf\{1\}\_\{n\}\\mathbf\{y\}\_\{\\beta\}^\{\\top\}\-\\nabla\_\{\\mathbf\{T\}\}f\\right\)\(32\)s\.t\.

\[diag​\(𝝁\)𝐓𝐓⊤diag​\(𝝂\)\]​\[𝐲α𝐲β\]=\[𝐆𝟏m𝐆⊤​𝟏n\]=\[\(𝐓⊙∇𝐓f\)​𝟏m\(𝐓⊙∇𝐓f\)⊤​𝟏n\]\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)&\\mathbf\{T\}\\\\ \\mathbf\{T\}^\{\\top\}&\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\end\{bmatrix\}\\begin\{bmatrix\}\\mathbf\{y\}\_\{\\alpha\}\\\\ \\mathbf\{y\}\_\{\\beta\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\mathbf\{G\}\\mathbf\{1\}\_\{m\}\\\\ \\mathbf\{G\}^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\left\(\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\\right\)\\mathbf\{1\}\_\{m\}\\\\ \\left\(\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\}\(33\)∎

### A\.2Proof of Singularity of𝐀\\mathbf\{A\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\)

###### Proof\.

By Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\), we have

𝐀=\[diag​\(𝝁\)𝐓𝐓⊤diag​\(𝝂\)\]\\mathbf\{A\}=\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)&\\mathbf\{T\}\\\\ \\mathbf\{T\}^\{\\top\}&\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\end\{bmatrix\}\(34\)where𝝁,𝝂\\boldsymbol\{\\mu\},\\boldsymbol\{\\nu\}are marginal distributions of OT, and𝐓\\mathbf\{T\}is the solved transport map\. As𝐓\\mathbf\{T\}satisfy the marginal constraints of OT, i\.e\.,𝐓𝟏m=𝝁\\mathbf\{T\}\\mathbf\{1\}\_\{m\}=\\boldsymbol\{\\mu\},𝐓⊤​𝟏n=𝝂\\mathbf\{T\}^\{\\top\}\\mathbf\{1\}\_\{n\}=\\boldsymbol\{\\nu\}, we can find a nonzero vector\[𝟏n−𝟏m\]\\begin\{bmatrix\}\\mathbf\{1\}\_\{n\}\\\\ \-\\mathbf\{1\}\_\{m\}\\end\{bmatrix\}in the null space of𝐀\\mathbf\{A\}, i\.e\.,

𝐀𝐳=\[diag​\(𝝁\)𝐓𝐓⊤diag​\(𝝂\)\]​\[𝟏n−𝟏m\]=\[diag​\(𝝁\)​𝟏n−𝐓𝟏m𝐓⊤​𝟏n−diag​\(𝝂\)​𝟏m\]=\[𝝁−𝐓𝟏m𝐓⊤​𝟏n−𝝂\]=𝟎n\+m\\mathbf\{A\}\\mathbf\{z\}=\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)&\\mathbf\{T\}\\\\ \\mathbf\{T\}^\{\\top\}&\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\end\{bmatrix\}\\begin\{bmatrix\}\\mathbf\{1\}\_\{n\}\\\\ \-\\mathbf\{1\}\_\{m\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)\\mathbf\{1\}\_\{n\}\-\\mathbf\{T\}\\mathbf\{1\}\_\{m\}\\\\ \\mathbf\{T\}^\{\\top\}\\mathbf\{1\}\_\{n\}\-\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\mathbf\{1\}\_\{m\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\boldsymbol\{\\mu\}\-\\mathbf\{T\}\\mathbf\{1\}\_\{m\}\\\\ \\mathbf\{T\}^\{\\top\}\\mathbf\{1\}\_\{n\}\-\\boldsymbol\{\\nu\}\\end\{bmatrix\}=\\mathbf\{0\}\_\{n\+m\}\(35\)Therefore,𝐀\\mathbf\{A\}is a singular matrix\.

∎

### A\.3Proof of Lemma[4\.3](https://arxiv.org/html/2605.24395#S4.Thmtheorem3)

###### Lemma\.

Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) can be solved via conjugate gradient method with guaranteed convergence to global optimum\.

###### Proof\.

First, we prove that Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) can be solved via conjugate gradient method with guaranteed convergence\. While the classical CG method requires the coefficient matrix𝐀\\mathbf\{A\}to be strictly positive definite,\(Kaasschieter,[1988](https://arxiv.org/html/2605.24395#bib.bib28); Hayami,[2018](https://arxiv.org/html/2605.24395#bib.bib29)\)show that CG method can be applied directly to singular systems with guaranteed convergence when \(1\)𝐀\\mathbf\{A\}is positive\-semidefinite, and \(2\) vector𝐛\\mathbf\{b\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) lies in the rangeR​\(𝐀\)R\(\\mathbf\{A\}\)of𝐀\\mathbf\{A\}\.

We begin by proving that matrix𝐀\\mathbf\{A\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) is positive\-semidefinite\. Firstly,𝐀∈ℝ\(n\+m\)×\(n\+m\)\\mathbf\{A\}\\in\\mathbb\{R\}^\{\(n\+m\)\\times\(n\+m\)\}is symmetric as𝐀=𝐀⊤\\mathbf\{A\}=\\mathbf\{A\}^\{\\top\}\. Secondly, for any vectors𝐬∈ℝn,𝐭∈ℝm\\mathbf\{s\}\\in\\mathbb\{R\}^\{n\},\\mathbf\{t\}\\in\\mathbb\{R\}^\{m\}, we have

\[𝐬𝐭\]⊤​𝐀​\[𝐬𝐭\]=\[𝐬𝐭\]⊤​\[diag​\(𝝁\)𝐓𝐓⊤diag​\(𝝂\)\]​\[𝐬𝐭\]=𝐬⊤​diag​\(𝝁\)​𝐬\+2​𝐬⊤​𝐓𝐭\+𝐭⊤​diag​\(𝝂\)​𝐭\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}^\{\\top\}\\mathbf\{A\}\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}^\{\\top\}\\begin\{bmatrix\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)&\\mathbf\{T\}\\\\ \\mathbf\{T\}^\{\\top\}&\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\end\{bmatrix\}\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}=\\mathbf\{s\}^\{\\top\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)\\mathbf\{s\}\+2\\mathbf\{s\}^\{\\top\}\\mathbf\{T\}\\mathbf\{t\}\+\\mathbf\{t\}^\{\\top\}\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\mathbf\{t\}\(36\)As𝐓\\mathbf\{T\}satisfy the marginal constraints of OT, i\.e\.,∑j=1m𝐓i,j=𝝁i\\sum\_\{j=1\}^\{m\}\\mathbf\{T\}\_\{i,j\}=\\boldsymbol\{\\mu\}\_\{i\},∑i=1n𝐓i,j=𝝂j\\sum\_\{i=1\}^\{n\}\\mathbf\{T\}\_\{i,j\}=\\boldsymbol\{\\nu\}\_\{j\}, we have

𝐬⊤​diag​\(𝝁\)​𝐬=∑i=1n𝐬i2​𝝁i=∑i=1n𝐬i2​∑j=1m𝐓i,j\\mathbf\{s\}^\{\\top\}\\text\{diag\}\(\\boldsymbol\{\\mu\}\)\\mathbf\{s\}=\\sum\_\{i=1\}^\{n\}\\mathbf\{s\}\_\{i\}^\{2\}\\boldsymbol\{\\mu\}\_\{i\}=\\sum\_\{i=1\}^\{n\}\\mathbf\{s\}\_\{i\}^\{2\}\\sum\_\{j=1\}^\{m\}\\mathbf\{T\}\_\{i,j\}\(37\)2​𝐬⊤​𝐓𝐭=2​∑i=1n∑j=1m𝐬i​𝐭j​𝐓i,j2\\mathbf\{s\}^\{\\top\}\\mathbf\{T\}\\mathbf\{t\}=2\\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{m\}\\mathbf\{s\}\_\{i\}\\mathbf\{t\}\_\{j\}\\mathbf\{T\}\_\{i,j\}\(38\)𝐭⊤​diag​\(𝝂\)​𝐭=∑j=1m𝐭j2​𝝂j=∑j=1m𝐭j2​∑i=1n𝐓i,j\\mathbf\{t\}^\{\\top\}\\text\{diag\}\(\\boldsymbol\{\\nu\}\)\\mathbf\{t\}=\\sum\_\{j=1\}^\{m\}\\mathbf\{t\}\_\{j\}^\{2\}\\boldsymbol\{\\nu\}\_\{j\}=\\sum\_\{j=1\}^\{m\}\\mathbf\{t\}\_\{j\}^\{2\}\\sum\_\{i=1\}^\{n\}\\mathbf\{T\}\_\{i,j\}\(39\)Therefore, Eq\. \([36](https://arxiv.org/html/2605.24395#A1.E36)\) can be reformulated to

\[𝐬𝐭\]⊤​𝐀​\[𝐬𝐭\]=∑i=1n∑j=1m𝐓i,j​\(𝐬i2\+2​𝐬i​𝐭j\+𝐭j2\)=∑i=1n∑j=1m𝐓i,j​\(𝐬i\+𝐭j\)2≥0\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}^\{\\top\}\\mathbf\{A\}\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}=\\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{m\}\\mathbf\{T\}\_\{i,j\}\\left\(\\mathbf\{s\}\_\{i\}^\{2\}\+2\\mathbf\{s\}\_\{i\}\\mathbf\{t\}\_\{j\}\+\\mathbf\{t\}\_\{j\}^\{2\}\\right\)=\\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{m\}\\mathbf\{T\}\_\{i,j\}\\left\(\\mathbf\{s\}\_\{i\}\+\\mathbf\{t\}\_\{j\}\\right\)^\{2\}\\geq 0\(40\)In this case, we have proven that𝐀\\mathbf\{A\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) is positive\-semidefinite\.

Then, we prove that vector𝐛\\mathbf\{b\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) lies in the rangeR​\(𝐀\)R\(\\mathbf\{A\}\)of𝐀\\mathbf\{A\}by showing that𝐛\\mathbf\{b\}is orthogonal to the null space of𝐀\\mathbf\{A\}, i\.e\.,𝐳⊤​𝐛=0,∀𝐳∈Null​\(𝐀\)\\mathbf\{z\}^\{\\top\}\\mathbf\{b\}=0,~\\forall\\mathbf\{z\}\\in\\text\{Null\}\(\\mathbf\{A\}\)\(Strang,[2022](https://arxiv.org/html/2605.24395#bib.bib30)\)\. For a vector\[𝐬∈ℝn𝐭∈ℝm\]\\begin\{bmatrix\}\\mathbf\{s\}\\in\\mathbb\{R\}^\{n\}\\\\ \\mathbf\{t\}\\in\\mathbb\{R\}^\{m\}\\end\{bmatrix\}in the null space of𝐀\\mathbf\{A\}, we have𝐀​\[𝐬𝐭\]=𝟎n\+m\\mathbf\{A\}\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}=\\mathbf\{0\}\_\{n\+m\}, which means that\[𝐬𝐭\]⊤​𝐀​\[𝐬𝐭\]=0\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}^\{\\top\}\\mathbf\{A\}\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}=0\. As we shown in Appendix[A\.3](https://arxiv.org/html/2605.24395#A1.SS3), for any vector\[𝐬𝐭\]\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}, we have\[𝐬𝐭\]⊤​𝐀​\[𝐬𝐭\]=∑i=1n∑j=1m𝐓i,j​\(𝐬i\+𝐭j\)2≥0\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}^\{\\top\}\\mathbf\{A\}\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}=\\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{m\}\\mathbf\{T\}\_\{i,j\}\\left\(\\mathbf\{s\}\_\{i\}\+\\mathbf\{t\}\_\{j\}\\right\)^\{2\}\\geq 0, therefore the null space of𝐀\\mathbf\{A\}is

Null​\(𝐀\)=\{\[𝐬𝐭\]:𝐬i\+𝐭j=0\}=span​\{\[𝟏n−𝟏m\]\}\\text\{Null\}\(\\mathbf\{A\}\)=\\left\\\{\\begin\{bmatrix\}\\mathbf\{s\}\\\\ \\mathbf\{t\}\\end\{bmatrix\}:\\mathbf\{s\}\_\{i\}\+\\mathbf\{t\}\_\{j\}=0\\right\\\}=\\text\{span\}\\left\\\{\\begin\{bmatrix\}\\mathbf\{1\}\_\{n\}\\\\ \\mathbf\{\-1\}\_\{m\}\\end\{bmatrix\}\\right\\\}\(41\)Since

\[𝟏n−𝟏m\]⊤​𝐛=\[𝟏n−𝟏m\]⊤​\[\(𝐓⊙∇𝐓f\)​𝟏m\(𝐓⊙∇𝐓f\)⊤​𝟏n\]=0\\begin\{bmatrix\}\\mathbf\{1\}\_\{n\}\\\\ \-\\mathbf\{1\}\_\{m\}\\end\{bmatrix\}^\{\\top\}\\mathbf\{b\}=\\begin\{bmatrix\}\\mathbf\{1\}\_\{n\}\\\\ \-\\mathbf\{1\}\_\{m\}\\end\{bmatrix\}^\{\\top\}\\begin\{bmatrix\}\\left\(\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\\right\)\\mathbf\{1\}\_\{m\}\\\\ \\left\(\\mathbf\{T\}\\odot\\nabla\_\{\\mathbf\{T\}\}f\\right\)^\{\\top\}\\mathbf\{1\}\_\{n\}\\end\{bmatrix\}=0\(42\)then𝐛\\mathbf\{b\}lies in the rangeR​\(𝐀\)R\(\\mathbf\{A\}\)of𝐀\\mathbf\{A\}\. In this way, we have proven that CG solves Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) with guaranteed convergence\.

Then, we prove that CG converges to the global optimum of Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\)\. As𝐀\\mathbf\{A\}is symmetric, solving the linear system𝐀𝐲=𝐛\\mathbf\{A\}\\mathbf\{y\}=\\mathbf\{b\}is equivalent to minimizing a quadratic functionggas follows\(Boyd and Vandenberghe,[2004](https://arxiv.org/html/2605.24395#bib.bib104)\)

g​\(𝐲\)=12​𝐲⊤​𝐀𝐲−𝐛⊤​𝐲g\(\\mathbf\{y\}\)=\\frac\{1\}\{2\}\\mathbf\{y\}^\{\\top\}\\mathbf\{A\}\\mathbf\{y\}\-\\mathbf\{b\}^\{\\top\}\\mathbf\{y\}\(43\)We can see that the Hessian ofggis𝐀\\mathbf\{A\}, which is positive\-semidefinite as proven above\. Therefore,ggis a convex quadratic function w\.r\.t\.𝐲\\mathbf\{y\}\(Boyd and Vandenberghe,[2004](https://arxiv.org/html/2605.24395#bib.bib104)\)\. Since Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) corresponds to the first\-order optimality condition∇𝐲g​\(𝐲\)=0\\nabla\_\{\\mathbf\{y\}\}g\(\\mathbf\{y\}\)=0, any solution of the linear system is a global optimum\(Boyd and Vandenberghe,[2004](https://arxiv.org/html/2605.24395#bib.bib104)\)\. Since the CG method converges to a solution of Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) as proven above, the solution must be the global optimum\. ∎

### A\.4Proof of Theorem[4\.5](https://arxiv.org/html/2605.24395#S4.Thmtheorem5)

###### Theorem\.

\(Time & Space Complexity ofAvAtar\-L2L\_\{2\}/entropy/consist\)

The time complexity is𝒪​\(kb​K​\(n\+m\)\)\\mathcal\{O\}\\left\(\\frac\{k\}\{b\}K\(n\+m\)\\right\)forAvAtar\-L2L\_\{2\}/entropy, and𝒪​\(kb​\(K​\(n\+m\)\+e\)\)\\mathcal\{O\}\\left\(\\frac\{k\}\{b\}\(K\(n\+m\)\+e\)\\right\)forAvAtar\-consist, whereeedenotes the number of edges in the networks to be aligned222Without loss of generality, we assume𝒪​\(e\)≈𝒪​\(e1\)≈𝒪​\(e2\)\\mathcal\{O\}\(e\)\\approx\\mathcal\{O\}\(e\_\{1\}\)\\approx\\mathcal\{O\}\(e\_\{2\}\)whereeie\_\{i\}denotes the number of edges in theii\-th networks\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1); Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2)\)\.\. The space complexity ofAvAtar\-L2L\_\{2\}/entropy/consistis𝒪​\(n​m\)\\mathcal\{O\}\(nm\)\.kkis the total query budget,bbis the batch query size,KKis the number of iterations of CG, andn,mn,mare number of objects in the source and target sets, respectively\.

###### Proof\.

The computation ofAvAtarconsist of two main steps: 1\) compute the pairwise object query impact by Eq\. \([7](https://arxiv.org/html/2605.24395#S4.E7)\) 2\) compute the posterior object query impact by Eq\. \([8](https://arxiv.org/html/2605.24395#S4.E8)\)\. Note that the transport map𝐓\\mathbf\{T\}at the end of each query round is typically a deterministic andsparsematrix with𝒪​\(n\+m\)\\mathcal\{O\}\(n\+m\)non\-zero entries for alignment problems\(Chenet al\.,[2020](https://arxiv.org/html/2605.24395#bib.bib11); Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1); Yuet al\.,[2025a](https://arxiv.org/html/2605.24395#bib.bib5)\), as shown empirically in Figure[11](https://arxiv.org/html/2605.24395#A3.F11), making𝐀\\mathbf\{A\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) sparse as well\. We denote the number of non\-zero entries in𝐓\\mathbf\{T\}by nnz\(𝐓\)\(\\mathbf\{T\}\)\. For the first step, we need to compute the vector𝐛\\mathbf\{b\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) first in𝒪​\(nnz​\(𝐓\)\)\\mathcal\{O\}\(\\text\{nnz\}\(\\mathbf\{T\}\)\)forAvAtar\-L2L\_\{2\}/entropy, and𝒪​\(nnz​\(𝐓\)\+n\+m\+e\)\\mathcal\{O\}\(\\text\{nnz\}\(\\mathbf\{T\}\)\+n\+m\+e\)forAvAtar\-consist\(Macskassy,[2009](https://arxiv.org/html/2605.24395#bib.bib38)\)\. Then, we solve the linear system in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) via the CG method with a time complexity of𝒪​\(K​nnz​\(𝐓\)\)\\mathcal\{O\}\(K\\text\{nnz\}\(\\mathbf\{T\}\)\), whereKKis the total number of CG iterations\(Kaasschieter,[1988](https://arxiv.org/html/2605.24395#bib.bib28)\)\. For the second step, Eq\. \([8](https://arxiv.org/html/2605.24395#S4.E8)\) aggregates pairwise query impact in𝒪​\(nnz​\(𝐓\)\)\\mathcal\{O\}\(\\text\{nnz\}\(\\mathbf\{T\}\)\)\. Therefore, forAvAtar\-L2L\_\{2\}/entropy, the time complexity for one query batch is𝒪​\(nnz​\(𝐓\)\)\+𝒪​\(K​nnz​\(𝐓\)\)\+𝒪​\(nnz​\(𝐓\)\)=𝒪​\(K​nnz​\(𝐓\)\)≈𝒪​\(K​\(n\+m\)\)\\mathcal\{O\}\(\\text\{nnz\}\(\\mathbf\{T\}\)\)\+\\mathcal\{O\}\(K\\text\{nnz\}\(\\mathbf\{T\}\)\)\+\\mathcal\{O\}\(\\text\{nnz\}\(\\mathbf\{T\}\)\)=\\mathcal\{O\}\(K\\text\{nnz\}\(\\mathbf\{T\}\)\)\\approx\\mathcal\{O\}\(K\(n\+m\)\), making the total time complexity𝒪​\(kb​K​\(n\+m\)\)\\mathcal\{O\}\(\\frac\{k\}\{b\}K\(n\+m\)\); forAvAtar\-consist, the time complexity for one query batch is𝒪​\(nnz​\(𝐓\)\+n\+m\+e\)\+𝒪​\(K​nnz​\(𝐓\)\)\+𝒪​\(nnz​\(𝐓\)\)=𝒪​\(K​nnz​\(𝐓\)\+n\+m\+e\)≈𝒪​\(K​\(n\+m\)\+e\)\\mathcal\{O\}\(\\text\{nnz\}\(\\mathbf\{T\}\)\+n\+m\+e\)\+\\mathcal\{O\}\(K\\text\{nnz\}\(\\mathbf\{T\}\)\)\+\\mathcal\{O\}\(\\text\{nnz\}\(\\mathbf\{T\}\)\)=\\mathcal\{O\}\(K\\text\{nnz\}\(\\mathbf\{T\}\)\+n\+m\+e\)\\approx\\mathcal\{O\}\(K\(n\+m\)\+e\), making the total time complexity𝒪​\(kb​\(K​\(n\+m\)\+e\)\)\\mathcal\{O\}\\left\(\\frac\{k\}\{b\}\(K\(n\+m\)\+e\)\\right\)

While the transport map𝐓\\mathbf\{T\}is typically sparse forAvAtar, Eq\. \([7](https://arxiv.org/html/2605.24395#S4.E7)\) requires explicit storage of the dense transport cost matrix𝐂\\mathbf\{C\}\. Therefore, the space complexity ofAvAtar\-L2L\_\{2\}is𝒪​\(n​m\)\\mathcal\{O\}\(nm\)\. ∎

### A\.5Proof of Theorem[4\.6](https://arxiv.org/html/2605.24395#S4.Thmtheorem6)

###### Theorem A\.1\.

\(Convergence ofAvAtar\) The conjugate gradient method applied to the linear system of Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) converges at a linear convergence rate ofλ1/λr−1λ1/λr\+1\\frac\{\\sqrt\{\\lambda\_\{1\}/\\lambda\_\{r\}\}\-1\}\{\\sqrt\{\\lambda\_\{1\}/\\lambda\_\{r\}\}\+1\}, whereλ1,λr\\lambda\_\{1\},\\lambda\_\{r\}denotes the largest/smallest nonzero eigenvalues of𝐀\\mathbf\{A\}in Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\)\.

###### Proof\.

\(Hayami,[2018](https://arxiv.org/html/2605.24395#bib.bib29)\)shows that the error bound of CG method on a singular system𝐀𝐲=𝐛\\mathbf\{A\}\\mathbf\{y\}=\\mathbf\{b\}is

‖𝐲\(k\)−𝐲∗‖𝚲r≤2​\{κ​\(𝚲r\)−1κ​\(𝚲r\)\+1\}k​‖𝐲\(0\)−𝐲∗‖𝚲r\\\|\\mathbf\{y\}^\{\(k\)\}\-\\mathbf\{y\}^\{\*\}\\\|\_\{\\boldsymbol\{\\Lambda\}\_\{r\}\}\\leq 2\\left\\\{\\frac\{\\sqrt\{\\kappa\(\\boldsymbol\{\\Lambda\}\_\{r\}\)\}\-1\}\{\\sqrt\{\\kappa\(\\boldsymbol\{\\Lambda\}\_\{r\}\)\}\+1\}\\right\\\}^\{k\}\\\|\\mathbf\{y\}^\{\(0\)\}\-\\mathbf\{y\}^\{\*\}\\\|\_\{\\boldsymbol\{\\Lambda\}\_\{r\}\}\(44\)where𝐲\(k\)\\mathbf\{y\}^\{\(k\)\}denotes𝐲\\mathbf\{y\}in thekk\-th round of CG method, and𝐲∗\\mathbf\{y\}^\{\*\}denotes the optimal solution\.‖𝐱‖𝚲r=𝐱⊤​𝚲r​𝐱\\\|\\mathbf\{x\}\\\|\_\{\\boldsymbol\{\\Lambda\}\_\{r\}\}=\\mathbf\{x\}^\{\\top\}\\boldsymbol\{\\Lambda\}\_\{r\}\\mathbf\{x\}, where𝚲r\\boldsymbol\{\\Lambda\}\_\{r\}is a diagonal matrix of the nonzero eigenvalues of𝐀\\mathbf\{A\}, i\.e\.,

𝚲r=\[λ1⋱λr\],λ1≥λ2≥…≥λr\>0\\boldsymbol\{\\Lambda\}\_\{r\}=\\begin\{bmatrix\}\\lambda\_\{1\}&&\\\\ &\\ddots&\\\\ &&\\lambda\_\{r\}\\\\ \\end\{bmatrix\},~\\lambda\_\{1\}\\geq\\lambda\_\{2\}\\geq\\ldots\\geq\\lambda\_\{r\}\>0\(45\)wherer=rank​\(𝐀\)r=\\text\{rank\}\(\\mathbf\{A\}\),λi\\lambda\_\{i\}are the nonzero eigenvalues of𝐀\\mathbf\{A\}\.κ​\(𝚲𝒓\)=λ1λr≥1\\kappa\(\\boldsymbol\{\\Lambda\_\{r\}\}\)=\\frac\{\\lambda\_\{1\}\}\{\\lambda\_\{r\}\}\\geq 1\. Sinceρ=κ​\(𝚲r\)−1κ​\(𝚲r\)\+1∈\[0,1\)\\rho=\\frac\{\\sqrt\{\\kappa\(\\boldsymbol\{\\Lambda\}\_\{r\}\)\}\-1\}\{\\sqrt\{\\kappa\(\\boldsymbol\{\\Lambda\}\_\{r\}\)\}\+1\}\\in\[0,1\)in this case, Eq\. \([6](https://arxiv.org/html/2605.24395#S4.E6)\) converges linearly to a solution by CG method\(Kaasschieter,[1988](https://arxiv.org/html/2605.24395#bib.bib28)\)\. ∎

## Appendix BDetailed Experimental Pipeline

### B\.1Datasets Descriptions

Detailed descriptions of datasets adopted in this paper are given as follows\.

##### Phone\-Email\(Zhanget al\.,[2017](https://arxiv.org/html/2605.24395#bib.bib31)\)\.

A pair of communication networks with nodes representing people and edges representing documented communication between them via phone or email\. The phone network contains 1,000 nodes and 41,191 edges, and the Email network contains 1,003 nodes and 4,627 edges\. No attribute information is available for both networks\. There are 1,000 common people across two networks as ground\-truth alignment\.

##### ACM\-DBLP\-P\(A\)\(Tanget al\.,[2008](https://arxiv.org/html/2605.24395#bib.bib32)\)\.

A pair of undirected co\-authorship networks with nodes representing authors and edges representing co\-authorship between two authors\. The ACM network contains 9,872 nodes and 39,561 edges, and the DBLP network contains 9,916 nodes and 44,808 edges\. ACM\-DBLP\-A contains node attribute information while ACM\-DBLP\-P are plain networks\. There are 6,325 common authors across two networks as ground\-truth alignment\.

##### Douban\(Zhang and Tong,[2016](https://arxiv.org/html/2605.24395#bib.bib6)\)\.

A pair of online\-offline social networks collected from Douban, with nodes representing users and edges representing user interactions on the website\. The online network of Douban contains 3,906 nodes and 8,164 edges, and the offline network of Douban contains 1,118 nodes and 1,511 edges\. Node attribute are constructed from the the location of a user, and edge attributes from the contact/friend relationship on the social platform\. There are 1,118 common user across the two networks\.

##### CIFAR\-10\-C\(Hendrycks and Dietterich,[2019](https://arxiv.org/html/2605.24395#bib.bib33)\)\.

CIFAR\-10\-C consist of the original CIFAR\-10\(Krizhevskyet al\.,[2009](https://arxiv.org/html/2605.24395#bib.bib100)\)test set images transformed by different types of corruptions at five levels of severity\. In this paper, we adopt the gaussian perturbation version of CIFAR\-10\-C with level 5 severity\. For image\-text retrieval on CIFAR\-10\-C, we construct image\-text pairs by associating each images with the corresponding textual description based on its class label, and treat retrieval as matching images to their corresponding text embeddings\.

##### ImageNet\-C\(Hendrycks and Dietterich,[2019](https://arxiv.org/html/2605.24395#bib.bib33)\)\.

ImageNet\-C consist of the original images from ImageNet transformed by different types of corruptions at five levels of severity\. we adopt the gaussian perturbation version level 5 severity\. Image\-text retrieval on ImageNet\-C follows the same paradigm as CIFAR10\-C\.

##### COCO\(Linet al\.,[2014](https://arxiv.org/html/2605.24395#bib.bib36)\)\.

COCO is a large\-scale dataset for object detection, segmentation, and captioning\. It contains photos of 91 objects types and around 2,500,000 labeled instances in 328,000 images\. For image\-text grounding on COCO, which contains explicit fine\-grained correspondence between phrases in a sentence and objects \(or regions\) in an image, we treat grounding as an matching problem between phrases and objects for an image\.

##### Flickr30K Entities\(Plummeret al\.,[2015](https://arxiv.org/html/2605.24395#bib.bib35)\)\.

Flickr30K Entities is a standard benchmark for sentence\-based image description, constructed by augmenting around 158,000 captions from the Flickr30k\(Younget al\.,[2014](https://arxiv.org/html/2605.24395#bib.bib101)\)dataset\. Flickr30K Entities links the same entities across different captions for the same image, and associating them with manually annotated bounding boxes in Flickr30K\. Image\-text grounding on Flickr30K Entities follows the same paradigm as COCO\.

### B\.2Introduction of Baseline Query Strategies

##### Random\.

Selects candidate object from𝒳\\mathcal\{X\}randomly\.

##### Entropy\(Renet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib94)\)\.

Select candidate object from𝒳\\mathcal\{X\}whose Shannon entropy of its alignment results, i\.e\.,∑jm−𝐓i,j​log⁡𝐓i,j\\sum\_\{j\}^\{m\}\-\\mathbf\{T\}\_\{i,j\}\\log\\mathbf\{T\}\_\{i,j\}forxi∈𝒳x\_\{i\}\\in\\mathcal\{X\}, is the largest\. The intuition is to select the most uncertain object to query, measured by entropy of its alignment results\.

##### Margin\(Renet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib94)\)\.

Select candidate objects from𝒳\\mathcal\{X\}whose differences between the two most probable labels reflected by𝐓\\mathbf\{T\}, i\.e\.,𝐓i,j1−𝐓i,j2\\mathbf\{T\}\_\{i,j\_\{1\}\}\-\\mathbf\{T\}\_\{i,j\_\{2\}\}where𝐓i,j1:=arg⁡maxj⁡𝐓i,j\\mathbf\{T\}\_\{i,j\_\{1\}\}:=\\arg\\max\_\{j\}\\mathbf\{T\}\_\{i,j\}and𝐓i,j2:=arg⁡maxj≠j1⁡𝐓i,j\\mathbf\{T\}\_\{i,j\_\{2\}\}:=\\arg\\max\_\{j\\neq j\_\{1\}\}\\mathbf\{T\}\_\{i,j\}, is the smallest\. The intuition is to select the most uncertain object to query, measured by such differences\.

##### Least Confident\(Zhouet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib8)\)\.

Select candidate objects from𝒳\\mathcal\{X\}whose confidence of alignment measured by the corresponding probability in𝐓\\mathbf\{T\}, i\.e\.,maxj⁡𝐓i,j\\max\_\{j\}\\mathbf\{T\}\_\{i,j\}, is the smallest\. The intuition is to select the least confident object to query\.

##### Betweenness\(Zhouet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib8)\)\.

Select candidate nodes of NA from𝒳\\mathcal\{X\}that has the largest betweenness centrality scores\.\(Freeman,[1977](https://arxiv.org/html/2605.24395#bib.bib102)\)\.

##### Density\(Liet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib39)\)\.

Select candidate nodes from𝒳\\mathcal\{X\}that can represent all unlabeled source objects\. The density score of a candidate objectxxis defined asDensity​\(xi\)=∑xj∈𝒰∪𝒩​\(xi,k\)k‖𝐓i,:−𝐓j,:‖22\\text\{Density\}\(x\_\{i\}\)=\\sum\_\{x\_\{j\}\\in\\mathcal\{U\}\\cup\\mathcal\{N\}\(x\_\{i\},k\)\}^\{k\}\\\|\\mathbf\{T\}\_\{i,:\}\-\\mathbf\{T\}\_\{j,:\}\\\|^\{2\}\_\{2\}, where𝒰\\mathcal\{U\}denotes the set of unlabeled source objects, and𝒩​\(xi,k\)\\mathcal\{N\}\(x\_\{i\},k\)denotes thekknearest neighbors ofxix\_\{i\}in𝒳\\mathcal\{X\}\. We adoptk=20k=20\(Kim and Shin,[2022](https://arxiv.org/html/2605.24395#bib.bib103)\)\. Candidate objects with the highest density score are selected for query\.

##### Diversity\(Liet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib39)\)\.

Select candidate nodes from𝒳\\mathcal\{X\}that are different from labeled source objects\. The density score of a candidate objectxxis defined asDensity​\(xi\)=∑xj∈ℒKL​\(𝐓i,:,𝐓j,:\)\\text\{Density\}\(x\_\{i\}\)=\\sum\_\{x\_\{j\}\\in\\mathcal\{L\}\}\\text\{KL\}\(\\mathbf\{T\}\_\{i,:\},\\mathbf\{T\}\_\{j,:\}\), whereℒ⊂𝒳\\mathcal\{L\}\\subset\\mathcal\{X\}denotes the set of labeled source objects, andKL​\(⋅,⋅\)\\text\{KL\}\(\\cdot,\\cdot\)denotes the KL divergence\.

##### GibbsMatchings & TopMatchings\(Malmiet al\.,[2017](https://arxiv.org/html/2605.24395#bib.bib9)\)\.

Two matching\-based query strategies for active NA that select uncertain candidate nodes from𝒳\\mathcal\{X\}whose sampled matchings aligns to different target nodes during different samples\.

### B\.3Detailed Experimental Setup

##### Metrics\.

We adopt MRR and Recall@1 as the benchmarking metrics\. Formean reciprocal rank \(MRR\), it is defined as the average reciprocal of the rank at which the correct alignment appears in the candidate list, i\.e\., MRR=1n​∑i=1n1ranki=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\frac\{1\}\{\\text\{rank\}\_\{i\}\}, wherennis the size of source object set, and rankiis the rank of the correct alignment for theii\-th object in the source set; forRecall@1, it is defined as the proportion of source object whose correct alignment is ranked 1st by an alignment method, i\.e\., Recall@1=1n​∑i=1n𝕀​\{ranki=1\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbb\{I\}\\\{\\text\{rank\}\_\{i\}=1\\\}, where𝕀​\{⋅\}\\mathbb\{I\}\\\{\\cdot\\\}denotes the indicator function\. For thetotal query time, it is defined as the accumulated runtime of different active alignment methods under a fixed query budgetkkand query batch sizenbn\_\{b\}\. Formally,t\(k,nb\)=∑i=1Nti\(k,nb\)t^\{\(k,n\_\{b\}\)\}=\\sum\_\{i=1\}^\{N\}t\_\{i\}^\{\(k,n\_\{b\}\)\}, whereti\(k,nb\)t\_\{i\}^\{\(k,n\_\{b\}\)\}is time required to select query candidates at the i\-th round, after the completion of the alignment algorithm\.NNdenotes the total number of query rounds\.

##### Reproducibility\.

For all experiments, the reported results are averaged against 5 different runs which randomly selects 20% ground\-truth alignment as prior supervision for each run\. To ensure a fair comparison, all baselines are given the same total query budget of 20% ground\-truth, averaged against 10 query rounds \(batches\)\. Hyperparameters of all baselines alignment methods are set as default in their official implementations\. Code and datasets are available athttps://github\.com/yq\-leo/AvAtar\-ICML26\.

##### Machine\.

All experiments are conducted on a server with dual Intel® Xeon® Gold 6240R CPUs and 4 NVIDIA Tesla V100\-SXM2 GPUs of 32GB memory\.

## Appendix CAdditional Experimental Results

### C\.1Detailed Effectiveness Results

![Refer to caption](https://arxiv.org/html/2605.24395v1/x11.png)Figure 6:MRR vs\. query round on four NA datasets using the PARROT\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1)\)algorithm![Refer to caption](https://arxiv.org/html/2605.24395v1/x12.png)Figure 7:MRR vs\. query round on four NA datasets using the JOENA\(Yuet al\.,[2025b](https://arxiv.org/html/2605.24395#bib.bib2)\)algorithm![Refer to caption](https://arxiv.org/html/2605.24395v1/x13.png)Figure 8:MRR vs\. query round on two image\-text retrieval datasets using the GOT\(Chenet al\.,[2020](https://arxiv.org/html/2605.24395#bib.bib11)\)algorithm![Refer to caption](https://arxiv.org/html/2605.24395v1/x14.png)Figure 9:MRR vs\. query round on two image\-text grounding datasets using the GOT\(Chenet al\.,[2020](https://arxiv.org/html/2605.24395#bib.bib11)\)algorithm
### C\.2Scalability Results

![Refer to caption](https://arxiv.org/html/2605.24395v1/x15.png)Figure 10:Scalability results \(under10310^\{3\}runtime limit\) on synthetic graphs generated by the Erdős–Rényi \(ER\) model with an average node degree of 10\.Thex\-axisshows the number of nodes in the ER graphs \(in10310^\{3\}\), and they\-axisof shows the runtime of query methods\. The results confirm confirms that bothAvAtar\-L2L\_\{2\}andAvAtar\-consistscales linearly w\.r\.t\. the number of nodes in networks, making it scalable to large\-scale alignment problems\.![[Uncaptioned image]](https://arxiv.org/html/2605.24395v1/x16.png)

Figure 11:Drift of transport plan𝐓\\mathbf\{T\}and alignment performance improvement across query rounds, on Phone\-Email dataset using the PARROT\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1)\)algorithm andAvAtar\-L2L\_\{2\}
Table 8:Comparison of OT\-based alignment algorithm \(PARROT\) \+ OT\-specific active learning methods \(AvAtar\-L2L\_\{2\}\) with non\-OT aligment algorithm \(FINAL\) \+ non\-OT active learning methods \(Attent\) on NA tasks, in MRR\.

### C\.3Comparision with Non\-OT Baselines

To further demonstrate the power of OT\-based alignment algorithm, e\.g\., PARROT\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1)\), equipped with OT\-specific active learning approach, i\.e\.,AvAtar, we compare its performance with a consistency\-based alignment algorithm FINAL\(Zhang and Tong,[2016](https://arxiv.org/html/2605.24395#bib.bib6)\)with an active learning approach Attent\(Zhouet al\.,[2021](https://arxiv.org/html/2605.24395#bib.bib8)\)tailored for consistency\-based methods\. The results are shown in Table[8](https://arxiv.org/html/2605.24395#A3.T8), which shows that\(1\) PARROT \+AvAtarconsistently outperforms FINAL \+ Attent, demonstrating the power of OT\-based alignment\.\(2\) The performance gap increases as the query round \(budget\) increases, showing the superiority ofAvAtarin boosting the performance of OT\-based alignment methods\.

### C\.4Study on External Hyperparameters

We further validates the robustness ofAvAtaragainst external hyperparameters of specific OT\-based alignment algorithms, i\.e\., the penalizing factorβ\\betaand the entropic regularization parameterϵ\\epsilon, we conduct an additional set of hyperparameter study on Phone\-Email with PARROT\(Zenget al\.,[2023a](https://arxiv.org/html/2605.24395#bib.bib1)\), and report results in Table[9](https://arxiv.org/html/2605.24395#A3.T9)\.

Table 9:Study on external hyperparametersβ\\betaandϵ\\epsilonon Phone\-Email with PARROT\. The best results are highlighted inbold\.

## Appendix DLimitations & Future Works

In this section, we discuss some of the potential limitations of the proposedAvAtar\. Firstly, the benefit of AvAtar may be partially reduced in some geometric matching tasks, e\.g\., point cloud registration \(PCR\), where the cost functions are relatively robust due to rich geometric information\. However, this does not not render AvAtar inapplicable to PCR, especially under imperfect cost design due to outlier points and noisy features\(Qinet al\.,[2023](https://arxiv.org/html/2605.24395#bib.bib16); Qiuet al\.,[2024](https://arxiv.org/html/2605.24395#bib.bib59)\)\. Secondly, whileAvAtarcan be easily extended to some OT variants, e\.g\., unbalanced OT\(Gabriel and Marco,[2019](https://arxiv.org/html/2605.24395#bib.bib22)\), and Gromov\-Wasserstein distance\(Peyréet al\.,[2016](https://arxiv.org/html/2605.24395#bib.bib25)\), with entropic regularization, its extension to neural OT\(Korotinet al\.,[2022](https://arxiv.org/html/2605.24395#bib.bib108)\)remains an interesting future work\.