1 Introduction↩︎

Alignment is a critical steppingstone behind a wide range of machine learning problems, including but not limit to multi-network analysis [@du2021new; @yan2022dissecting; @slotalign; @wang2023networked; @planetalign; @zeng2023generative; @zeng2024graph; @zeng2024hierarchical; @zeng2025pave], multimodal and cross-domain learning [@yilmaz2019cross; @chen2020graph; @cheng2022cross; @xu2024discrete; @yoo2024ensuring; @ning2025graph4mm], and point cloud registration. [@yu2021cofinet; @yu2023rotation; @haitman2024umeregrobust]. 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 [@parrot; @joena]. 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 [@han2021pre; @gan2022vision; @liang2024foundations; @bartan2025fineamp; @wei2026diffkgw].

Recently, optimal transport (OT) [@gabriel2019computational] 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 [@joena; @planetalign], and have demonstrated remarkable performance across diverse alignment tasks [@chen2020graph; @qin2023geotransformer; @joena]. Despite their success, Figure 1 shows that OT-based alignment approaches are sensitive to the quantity and quality of supervisions [@planetalign], yet obtaining high-quality supervision is costly in practice [@attent; @gan2022vision; @liu2024class; @li2024survey]. 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 [@malmi2017active; @cheng2019deep; @attent]. 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 [@malmi2017active; @cheng2019deep]. Thirdly (Limitation #3), prior efforts on active alignment mainly focus on designing task-specific query strategies [@ren2019meta; @attent], 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).

In this paper, we address these limitations by proposing a principled active alignment framework based on optimal transport, called AvAtar. 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 of AvAtar, 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 that AvAtarconsistently outperform existing active learning approaches under the same query budget. We also show empirically that AvAtarachieves 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 method AvAtarto 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 of AvAtarto establish its correctness, linear time complexity, and linear convergence.

• Evaluation. Extensive experiments across diverse alignment tasks show that AvAtarconsistently improves alignment performance and achieves a good balance between effectiveness and efficiency.

2 Preliminaries↩︎

In this section, we introduce preliminaries on optimal transport in Section 2.1, followed by OT-based alignment problem in Section 2.2. 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., \(k\)). Table 1 summarizes the main symbols used throughout the paper.

2.1 Optimal Transport↩︎

OT has emerged as a powerful mathematical tool for aligning two distributions [@santambrogio2015optimal]. Let \(\boldsymbol{\mu}=\sum_{i=1}^{n}\mu_i\delta_{x_i}\) and \(\boldsymbol{\nu}=\sum_{j=1}^{m}\nu_i\delta_{y_j}\) be two discrete probability distributions where \(\delta\) denotes the Dirac measure. The discrete optimal transport problem seeks an optimal transport plan \(\mathbf{T}\) that minimizes the total transport cost as follows: \[\label{eq:w-dist} \min_{\mathbf{T}\in\Pi(\boldsymbol{\mu}, \boldsymbol{\nu})}\left<\mathbf{C}, \mathbf{T}\right>\tag{1}\] where \(\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\}\), \(\mathbf{C}\in\mathbb{R}^{n\times m}_{\geq 0}\) is the cost matrix where \(\mathbf{C}_{i,j}\) measures the cost of transporting mass from the support point \(x_i\) of \(\boldsymbol{\mu}\) to point \(y_j\) of \(\boldsymbol{\nu}\). The optimal value of Eq. 1 defines the Wasserstein distance between \(\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 induces a linear programming problem of cubic complexity which is infeasible for large-scale applications, [@gabriel2019computational] introduces entropic regularization into Eq. 1 to approximate the original OT formulation: \[\label{eq:ent-ot} \min_{\mathbf{T}\in\Pi(\boldsymbol{\mu}, \boldsymbol{\nu})}\left<\mathbf{C}, \mathbf{T}\right>-\epsilon\,\text{Ent}(\mathbf{T})\tag{2}\]

where \(\text{Ent}(\mathbf{T}):=-\sum_{i,j}\mathbf{T}_{i,j}\left(\log\mathbf{T}_{i,j}-1\right)\) and \(\epsilon>0\) denotes the entropic regularization weight. Eq. 2 yields an \(\epsilon\)-strongly convex optimization problem that can be solved more efficiently with a quadratic complexity via the Sinkhorn algorithm [@nemirovski1999complexity].

2.2 OT-based Alignment↩︎

A generalized definition for alignment problems based on OT can be summarized as follows [@parrot; @joena; @chen2020graph]:

Eq. 3 follows the common practice [@parrot; @joena] of integrating supervisions into OT-based alignment by penalizing the cost entries of aligned pairs. \(\beta\) in Eq. 3 denotes the penalizing factor. Under unsupervised settings, \(\mathbf{H}\) becomes a zero matrix, making Eq. 3 equivalent to Eq. 1 .

3 Problem 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 [@attent]:

Given an object \(x_s\) from the source set \(\mathcal{X}\), which target object \(y_t\in\mathcal{Y}\) is the correct alignment of \(x_s\)?

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

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.

Definition 2 is general and applicable to a wide range of alignment problems. Specifically, for NA, \(\mathcal{X}\) and \(\mathcal{Y}\) correspond to the node sets in the source and target networks; for CDA, \(\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.

4 Methodology↩︎

In this section, we present the proposed active OT-based alignment framework AvAtar. We first introduce a quantitative gradient-based method for evaluating the informativeness of querying a source object, in Section 4.1. Then, we introduce the proposed AvAtarwhich leverages this gradient-based method for solving the active OT-based alignment problem, in Section 4.2. Finally, we provide theoretical analysis regarding the complexity and convergence of AvAtar, in Section 4.3.

4.1 Gradient-based Query Impact↩︎

A fundamental principle in active learning is to query the most informative objects for the learning task [@attent; @li2024survey; @qiu2024gradient], oftentimes via gradient-based impact estimation [@he2024on; @chen2024wapiti; @chen2026influence]. 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 [@attent]. 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 function \(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 the global quality of the alignment.

In this paper, we adopt two general-purpose utility functions for all alignment tasks, \(f_{L_2}\) and \(f_\text{entropy}\), and design an additional utility function \(f_\text{consist}\) for the NA tasks. Definitions of different utility functions are listed in Table 2. We differentiate AvAtarof different utility functions by suffixes, e.g., AvAtar-\(L_2\).

The intuition of \(f_{L_2}\) and \(f_\text{entropy}\) is straightforward: both functions encourage querying source objects whose true alignment leads to a more deterministic result \(\mathbf{T}\) that approximates a permutation matrix when \(n\approx m\) [@gabriel2019computational; @joena]. For the NA-specific function \(f_\text{consist}\), it encourage the consistency principles widely adopted in NA [@final; @parrot]. Specifically, the first term \(\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 \(\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.1 Pairwise Objects Query Impact↩︎

The calculation of \(\mathcal{I}(p_{ij})\) for OT-based alignment method can be decomposed by the chain rule as follows \[\label{eq:pair-impact} \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\tag{4}\]

The second term \(\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 , \(\nabla_{\mathbf{H}_{i,j}}\tilde{\mathbf{C}}\) can be computed easily as \(\nabla_{\mathbf{H}_{i,j}}\tilde{\mathbf{C}}=-\beta\mathbf{C}_{i,j}\mathbf{E}\) where \(\mathbf{E}_{i,j}=1\) and 0 otherwise.

The main computation falls into the first term \(\nabla_{\tilde{\mathbf{C}}}f\), which quantifies the impact of changing the supervised cost matrix \(\tilde{\mathbf{C}}\) on the utility function \(f(\mathbf{T})\). Computing \(\nabla_{\tilde{\mathbf{C}}}f\) requires 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., \(\frac{\mathrm{d}\mathbf{T}}{\mathrm{d}\tilde{\mathbf{C}}}\), requires explicitly forming and inverting a Jacobian matrix of size \((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 \(\nabla_{\tilde{\mathbf{C}}}f\) to solving an adjoint linear system of size \((n+m)\).

The detailed proof of Lemma 1 can be found in Appendix 8.1. The core idea is to implicitly differentiate the constrained optimality conditions of OT by the adjoint-state method, which reformulates the computation of \(\nabla_{\tilde{\mathbf{C}}}f\) to solving a linear system [@sadr2024data] without explicitly inverting a large Jacobian.

To solve the linear system, we show in Appendix 8.2 that the coefficient matrix \(\mathbf{A}\) of Eq. 6 is singular, making it impossible to directly solve Eq. 6 by matrix inversion. To address this issue, we resort to conjugate gradient (CG) method, which is summarized in the following lemma 2.

The detailed proof of Lemma 2 can be found in Appendix 2. In general, Eq. 6 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  [@kaasschieter1988preconditioned; @hayami2018convergence]. 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 in Section 4.3, which shows that Eq. 6 can be solved with (1) a linear time complexity w.r.t. the number of objects in \(\mathcal{X}\) and \(\mathcal{Y}\), and (2) guaranteed convergence with a linear convergence rate. Combining Eq. 4 6 gives the final formulation of \(\mathcal{I}(p_{ij})\), which quantifies the impact of querying a possible pairwise alignment \((x_i,y_j)\): \[\label{eq:pair-impact-full} \begin{align} \mathcal{I}(p_{ij})&=-\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}\\ \text{s.t.}& \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} \end{align}\tag{7}\]

4.1.2 Posterior Object Query Impact↩︎

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, \(\mathbf{T}_{i,j}\) encodes the posterior alignment probability between two objects \(x_i\in\mathcal{X}\) and \(y_j\in\mathcal{Y}\) conditioned on the observed data and supervision. Aggregating pairwise objects query impact weighted by \(\mathbf{T}_{i,:}\) thus computes the expected impact of querying a source object \(x_i\).

4.2 AvAtar↩︎

Based on Definition 3 and Definition 4, we propose a generic query algorithm for OT-based alignment as described in Algorithm 2, which allows customized utility function \(f\) that quantifies the global alignment quality for different tasks. The key idea of AvAtaris to iteratively (1) select candidate objects with the largest posterior impact by Eq. 8 (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, \(\mathbf{H}_{i,j}\) is set to 1 if object \(x_i\) and \(y_j\) are known to be aligned, and 0 otherwise; for unsupervised alignment tasks, \(\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.

4.3 Theoretical Analysis↩︎

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

The detailed proof of Theorem 1 can be found in Appendix 8.4. In general, we reduce the complexity of AvAtar-\(L_2\)/entropy/consist to linear by utilizing the sparsity of the transport plan \(\mathbf{T}\) of OT-based method, as visualized in Figure 6. Note that while the total complexity of AvAtarmay depend on the selected utility function \(f\), the coefficient martix \(\mathbf{A}\) in Eq. 6 is agnostic to \(f\) thus the CG method can always leverage the sparsity of \(\mathbf{T}\) for OT-based alignment to approximate a linear time complexity of \(\mathcal{O}(K(n+m))\) w.r.t. the number of objects in \(\mathcal{X}\) and \(\mathcal{Y}\).

The detailed proof of Theorem 2 can be found in Appendix 8.5. This linear convergence rate guarantees fast and stable convergence of the CG method, making the gradient computation in AvAtarefficient and scalable.

5 Experiments↩︎

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

• Q1. How effective is the proposed AvAtaracross different alignment problems?

• Q2. How efficient and scalable is AvAtar?

• Q3. How is the empirical convergence of AvAtar?

• Q4. How sensitive is the proposed AvAtarto different parameters and design choices?

5.1 Experimental Setup↩︎

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

5.1.0.1 Network Alignment.

NA aims to find node-level correspondence across different networks. For datasets, we adopt 4 real-world datasets Phone-Email [@zhang2017ineat], ACM-DBLP-P [@tang2008arnetminer], Douban [@final], and ACM-DBLP-A [@tang2008arnetminer], covering both plain and attributed networks. For baseline OT-based NA methods, we adopt PARROT [@parrot] and JOENA [@joena]. For baseline query strategies, we adopt Random, Entropy, Margin [@li2024survey], Betweenness [@macskassy2009using], Contrastive, GibbsMatchings [@malmi2017active], and TopMatchings [@malmi2017active]. We report the mean reciprocal rank (MRR) as the benchmarking metric for NA.

5.1.0.2 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. For datasets, we adopt 2 widely used datasets CIFAR-10-C and ImageNet-C [@hendrycks2019benchmarking]. For baseline OT-based CDA methods, we adopt the Wasserstein (W) and Fused Gromov-Wasserstein (FGW) variants of GOT [@chen2020graph]. For baseline query strategies, we adopt Random, Entropy, Margin, Least confident, Density, and Diversity [@li2024survey]. We report the Recall@1 as the benchmarking metric for image-text retrieval.

5.1.0.3 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 [@li2022grounded]. For datasets, we adopt 2 widely used datasets COCO [@lin2014microsoft] and Flickr30K Entities [@plummer2015flickr30k]. 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 9.

5.2 Benchmarking Results↩︎

5.2.1 Network Alignment↩︎

For NA tasks, we adopt the task-agonistic AvAtar-\(L_2\), and AvAtar-consist which 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 ¿tbl:tab:exp95bench95na?. We observe that (1) AvAtar-\(L_2\)/consist achieve state-of-the-art performance across all datasets. They consistently outperform all baselines by up to 2.8% in MRR, demonstrating the effectiveness of AvAtaron both plain and attributed NA tasks. (2) Existing active NA methods becomes less effective on OT-based algorithms. We notice that GibbsMatchings and TopMatchings designed 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 for GibbsMatchings and TopMatchings to 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-consist designed specifically for NA tasks typically outperforms AvAtar-\(L_2\) with up to 0.6% improvement in MRR, indicating that consistency principles are particularly useful when attribute information is missing. In contrast, AvAtar-\(L_2\) generally achieves better performance than AvAtar-consist on attributed networks (Douban, ACM-DBLP-A), suggesting that deterministic alignment results given by \(f_{L_2}\), as mentioned in Section 4, 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 10.1.

5.2.2 Cross-Domain Alignment↩︎

We include two tasks for benchmarking AvAtaron CDA: image-text retrieval and image-text grounding. For both CDA tasks, we compare AvAtar-\(L_2\)/entropy with 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 ¿tbl:tab:exp95bench95itr? and ¿tbl:tab:exp95bench95itg?, respectively. We observe that (1) AvAtar-entropy/\(L_2\) consistently achieve state-of-the-art performance on both CDA tasks, demonstrating the effectiveness of AvAtaron OT-based alignment methods for CDA. (2) AvAtar-entropy aligns well with the objective of entropic OT. AvAtar-entropy typically outperforms AvAtar-\(L_2\) under most settings except for the image-text grounding task by GOT-FGW, which implies that \(f_\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-entropy consistently outperforms Entropy by 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.3 Efficiency Results↩︎

We study the effectiveness-efficiency trade-off of proposed AvAtar-\(L_2\)/consist compared with other baseline query methods on phone-email and Douban datasets using PARROT [@parrot]. The MRR vs. query time trade-off results are shown in Figure 3. We can see that AvAtar-\(L_2\)/consist achieve a good balance between the alignment performance and query time. Specifically, AvAtarachieves up to \(25\times\) speed-up compared to TopMatchings, and up to 8.1% improvement in MRR compared to GibbsMatchings, demonstrating both the effectiveness and efficiency of AvAtarover existing active NA methods. While most other baselines are slightly faster, they are consistently less effective in improving the alignment performance than AvAtar. More results on scalability are included in Appendix 10.2.

5.4 Convergence Results↩︎

We evaluate the convergence of the the conjugate gradient (CG) method for solving Eq. 6 and that of the Sinkhorn (SH) algorithm used for solving OT-based alignment, in terms of the difference between two consecutive solutions \(\Delta\mathbf{s}^{(t)}=\|\mathbf{s}^{(t)}-\mathbf{s}^{(t-1)}\|_1\), on Phone-Email. For CG, \(\mathbf{s}=\mathbf{y}\) in Eq. 6 ; for SH, \(\mathbf{s}=\text{vec}(\mathbf{T})\). Results are normalized to ensure a fair comparison. The corresponding convergence result of AvAtar-\(L_2\) and AvAtar-consist, are shown in Figure 4. We observe that (1) CG converges empirically when applied to Eq. 6 , which validates the convergence of AvAtar. (2) The convergence of SH is more sensitive to \(\epsilon\) than CG. As the entropic regularization weight \(\epsilon\) decreases, 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, incurs negligible overhead compared to the Sinkhorn algorithm for solving OT.

5.5 Further Studies↩︎

5.5.1 Hyperparameter Analysis↩︎

5.5.1.1 Query Budget \(k\).

The impact of the query budget \(k\) is presented in Tables ¿tbl:tab:exp95bench95na?-¿tbl:tab:exp95bench95itg? and Appendix 10.1, which shows that the alignment performance of AvAtarimproves monotonically as the query budget \(k\) increases.

5.5.1.2 Query Batch Size \(n_b\).

We perform a sensitivity study on the query batch size \(n_b\) in Figure 5. We adopt AvAtar-\(L_2\) and test the performance of PARROT on two datasets as the query batch size \(n_b\) changes under different query budget \(k\). We can see in Figure 5 that the performance of AvAtar-\(L_2\) remains stable under different choices of \(n_b\), with only slight performance improvement when \(n_b\) is smaller on Douban.

5.5.2 Ablation Study↩︎

5.5.2.1 Sparse vs. Dense Matrix Operation in CG.

As mentioned in Section 4.3, AvAtarleverages the sparsity of the transport plan \(\mathbf{T}\) to achieve linear time complexity. To verify the effectiveness and efficiency of sparse matrix operations in AvAtar, we compare the alignment performance of AvAtarwith AvAtar(Dense), which computes Eq. 7 and Eq. 8 by dense matrix operations. Specifically, we compare AvAtar-\(L_2\) with AvAtar-\(L_2\) (Dense), and AvAtar-consist with AvAtar-consist (Dense). The results on two datasets are shown in Table ¿tbl:tab:exp95ablate95sparse?. We observe that (1) Sparse matrix operations do not harm the empirical performance of AvAtar, as we can see that the alignment performance of AvAtarand AvAtar(Dense) remains close across different datasets. (2) Sparse matrix operation significantly improves the efficiency of AvAtar. AvAtarruns significantly faster than AvAtar(Dense) with up to \(1010/118\approx8.6\) times speed-up, demonstrating the efficiency of sparse matrix operations on AvAtar.

5.5.2.2 Posterior vs. Uniform Aggregation.

We verify the necessity of using transport plan \(\mathbf{T}\) as a posterior in Eq. 8 by comparing the performance of AvAtarwith AvAtar(Uniform), which aggregated pairwise objects query impact in Eq. 4 uniformly for computing the object-level query impact, i.e., \(\mathcal{I}(p_i)=\sum_{j=1}^m\mathcal{I}(p_{ij})\). As shown in Table ¿tbl:tab:exp95ablate95pos?, AvAtarconsistently outperforms AvAtar(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.

5.6 Visualizations↩︎

5.6.0.1 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 6. The results show that the \(\mathbf{T}\) returned by different OT-based methods are empirically sparse across different alignment tasks, with over 99% entries close to zero, suggesting that OT-based methods typically choose a small entropic regularization weight \(\epsilon\) to approximate deterministic, one-to-one alignment, making it possible for AvAtarto achieve linear time complexity by leveraging the sparsity of \(\mathbf{T}\).

5.6.0.2 Drifts of Transport Plans.

To improve interpretability regarding the corrective benefit of the oracle, we include an additional study on the drift of \(\mathbf{T}^{(i)}\) from \(\mathbf{T}^{(0)}\) in the \(i\)-th query round, measured by the Frobenius norm of their difference (i.e., \(\|\mathbf{T}^{(i)}-\mathbf{T}^{(0)}\|_{\text{F}}\). The results are shown in Figure 12, which shows that (1) \(\mathbf{T}^{(i)}\) gradually drifts from \(\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.

6 Related Work↩︎

6.1 Optimal 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 [@parrot] proposes a regularized OT-based algorithm and integrates consistency principles for effective cost design. JOENA [@joena] further unifies embedding learning and OT optimization, enabling end-to-end training of an effective and robust NA model. For CDA, GOT [@chen2020graph] combines both Wasserstein and Gromov-Wasserstein distance and proposes a principled framework for regularizing cross-domain alignment. DCOT [@wang2024dual] 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.2 Active 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 [@ren2021survey; @li2024survey]. The sparse literature on active alignment mainly focus on network data. [@malmi2017active] proposes two active NA methods that samples the most uncertain nodes via bipartite matching. Utilizing inter-network meta diagram and link selection, ActiveIter [@ren2019meta] introduces an active NA methods specifically for social networks. Attent [@attent] 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 [@gan2022vision; @liang2024foundations; @wei2024robust; @zeng2025interformer; @zeng2026harnessing; @zeng2025hierarchical; @zeng2026subspace].

7 Conclusion↩︎

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 framework AvAtarfor OT-based alignment applicable to diverse alignment tasks. Extensive experiments across three different alignment tasks demonstrate the effectiveness and scalability of AvAtaron 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, 2433309, 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.

8 Proof↩︎

8.1 Proof of Lemma 1↩︎

8.2 Proof of Singularity of \(\mathbf{A}\) in Eq. 6↩︎

8.3 Proof of Lemma 2↩︎

8.4 Proof of Theorem 1↩︎

8.5 Proof of Theorem 2↩︎

9 Detailed Experimental Pipeline↩︎

9.1 Datasets Descriptions↩︎

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

9.1.0.1 Phone-Email [@zhang2017ineat].

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.

9.1.0.2 ACM-DBLP-P(A) [@tang2008arnetminer].

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.

9.1.0.3 Douban [@final].

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.

9.1.0.4 CIFAR-10-C [@hendrycks2019benchmarking].

CIFAR-10-C consist of the original CIFAR-10 [@krizhevsky2009learning] 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.

9.1.0.5 ImageNet-C [@hendrycks2019benchmarking].

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.

9.1.0.6 COCO [@lin2014microsoft].

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.

9.1.0.7 Flickr30K Entities [@plummer2015flickr30k].

Flickr30K Entities is a standard benchmark for sentence-based image description, constructed by augmenting around 158,000 captions from the Flickr30k [@young2014image] 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.

9.2 Introduction of Baseline Query Strategies↩︎

9.2.0.1 Random.

Selects candidate object from \(\mathcal{X}\) randomly.

9.2.0.2 Entropy [@ren2021survey].

Select candidate object from \(\mathcal{X}\) whose Shannon entropy of its alignment results, i.e., \(\sum_j^m-\mathbf{T}_{i,j}\log\mathbf{T}_{i,j}\) for \(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.

9.2.0.3 Margin [@ren2021survey].

Select candidate objects from \(\mathcal{X}\) whose differences between the two most probable labels reflected by \(\mathbf{T}\), i.e., \(\mathbf{T}_{i,j_1}-\mathbf{T}_{i,j_2}\) where \(\mathbf{T}_{i,j_1}:=\arg\max_j\mathbf{T}_{i,j}\) and \(\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.

9.2.0.4 Least Confident [@attent].

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

9.2.0.5 Betweenness [@attent].

Select candidate nodes of NA from \(\mathcal{X}\) that has the largest betweenness centrality scores. [@freeman1977set].

9.2.0.6 Density [@li2024survey].

Select candidate nodes from \(\mathcal{X}\) that can represent all unlabeled source objects. The density score of a candidate object \(x\) is defined as \(\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 \(\mathcal{N}(x_i,k)\) denotes the \(k\) nearest neighbors of \(x_i\) in \(\mathcal{X}\). We adopt \(k=20\) [@kim2022defense]. Candidate objects with the highest density score are selected for query.

9.2.0.7 Diversity [@li2024survey].

Select candidate nodes from \(\mathcal{X}\) that are different from labeled source objects. The density score of a candidate object \(x\) is defined as \(\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, and \(\text{KL}(\cdot,\cdot)\) denotes the KL divergence.

9.2.0.8 GibbsMatchings & TopMatchings [@malmi2017active].

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.

9.3 Detailed Experimental Setup↩︎

9.3.0.1 Metrics.

We adopt MRR and Recall@1 as the benchmarking metrics. For mean 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\(=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\text{rank}_i}\), where \(n\) is the size of source object set, and rank\(_i\) is the rank of the correct alignment for the \(i\)-th object in the source set; for Recall@1, it is defined as the proportion of source object whose correct alignment is ranked 1st by an alignment method, i.e., Recall@1\(=\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\{\text{rank}_i=1\}\), where \(\mathbb{I}\{\cdot\}\) denotes the indicator function. For the total query time, it is defined as the accumulated runtime of different active alignment methods under a fixed query budget \(k\) and query batch size \(n_b\). Formally, \(t^{(k, n_b)}=\sum_{i=1}^{N}t_i^{(k, n_b)}\), where \(t_i^{(k, n_b)}\) is time required to select query candidates at the i-th round, after the completion of the alignment algorithm. \(N\) denotes the total number of query rounds.

9.3.0.2 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 at https://github.com/yq-leo/AvAtar-ICML26.

9.3.0.3 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.

10 Additional Experimental Results↩︎

10.1 Detailed Effectiveness Results↩︎

10.2 Scalability Results↩︎

10.3 Comparision with Non-OT Baselines↩︎

To further demonstrate the power of OT-based alignment algorithm, e.g., PARROT [@parrot], equipped with OT-specific active learning approach, i.e., AvAtar, we compare its performance with a consistency-based alignment algorithm FINAL [@final] with an active learning approach Attent [@attent] tailored for consistency-based methods. The results are shown in Table 13, 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 of AvAtarin boosting the performance of OT-based alignment methods.

10.4 Study on External Hyperparameters↩︎

We further validates the robustness of AvAtaragainst external hyperparameters of specific OT-based alignment algorithms, i.e., the penalizing factor \(\beta\) and the entropic regularization parameter \(\epsilon\), we conduct an additional set of hyperparameter study on Phone-Email with PARROT [@parrot], and report results in Table ¿tbl:tab:exp95ext95param?.

11 Limitations & Future Works↩︎

In this section, we discuss some of the potential limitations of the proposed AvAtar. 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 [@qin2023geotransformer; @qiu2024tucket]. Secondly, while AvAtarcan be easily extended to some OT variants, e.g., unbalanced OT [@gabriel2019computational], and Gromov-Wasserstein distance [@peyre2016gromov], with entropic regularization, its extension to neural OT [@korotin2022neural] remains an interesting future work.

---

1. Without loss of generality, we assume \(\mathcal{O}(e)\approx \mathcal{O}(e_1)\approx \mathcal{O}(e_2)\) where \(e_i\) denotes the number of edges in the \(i\)-th networks [@parrot; @joena].↩︎

2. Without loss of generality, we assume \(\mathcal{O}(e)\approx \mathcal{O}(e_1)\approx \mathcal{O}(e_2)\) where \(e_i\) denotes the number of edges in the \(i\)-th networks [@parrot; @joena].↩︎