Why Reciprocity Matters
When two batches are represented in the same feature space, a cell in one batch may be close to cells in the other. A one-way nearest-neighbor relationship is a useful candidate for correspondence, but it is not reciprocal automatically: cell \(x\) may select \(y\) as its closest cross-batch neighbor even though \(y\) is closer to a different cell. Mutual nearest neighbors (MNNs) require both selections to agree. This reciprocal rule gives a precise way to identify candidate cross-batch pairs without asserting that paired cells are literally the same cell or have identical measured profiles.
The earlier material on shared-state assumptions motivates the interpretation: an MNN can be evidence that two batches contain cells in comparable states, provided the representation and distance are meaningful for the biological comparison. The definition itself is geometric. It does not, by itself, establish that a pair is biologically equivalent or that a batch effect has been removed.
Definition in a Common Feature Space
Suppose batch A contains points \(x_1,\ldots,x_m\), and batch B contains points \(y_1,\ldots,y_n\). These may represent cells using a chosen set of coordinates. Assume that both batches use the same coordinate system and that a distance \(d(\cdot,\cdot)\) has been specified. For the basic definition, suppose there are no distance ties.
Only cross-batch distances enter this definition. A point’s closest point within its own batch is irrelevant to whether it forms an MNN. The distance function and coordinates must be fixed before identifying the pairs: changing the representation, scaling, or metric can change which points are nearest.
The definition can be extended from one nearest neighbor to \(k\) nearest neighbors. The rank of \(y_j\) among the points in B, ordered by distance from \(x_i\), is its cross-batch rank for \(x_i\); define the reverse rank of \(x_i\) from \(y_j\) in the same way. A pair is a \(k\)-nearest-neighbor mutual pair if both ranks are at most \(k\). Thus, ordinary MNNs are the \(k=1\) case. For \(k>1\), a point may participate in several pairs, so the result need not be a one-to-one matching.
If distances tie at the neighbor boundary, the rule needs an explicit convention. One option is to include every tied point, which can yield more than one nearest neighbor even when \(k=1\). Another is to use a deterministic tie-breaking rule. The convention should be stated because it can change the reported pair set. The examples below have no ties.
Why the Rank Rule Is Equivalent
The distance definition and the rank definition express the same reciprocal requirement. For a fixed candidate pair \((x_i,y_j)\), count how many points in B are strictly closer to \(x_i\) than \(y_j\), and how many points in A are strictly closer to \(y_j\) than \(x_i\). With no ties, these counts determine the two ranks.
For \(k=1\), the first rank is one exactly when no point in B is closer to \(x_i\) than \(y_j\); this is the statement that \(y_j\) is \(x_i\)'s nearest point in B. The second rank is one exactly when no point in A is closer to \(y_j\) than \(x_i\). Both conditions hold precisely when the pair is mutual. Replacing “rank is one” with “rank is at most \(k\)” gives the \(k\)-nearest-neighbor extension.
Worked Example: Finding Reciprocal Pairs on a Line
Consider hypothetical one-dimensional coordinates in a common feature space: batch A has \(a_1=0\) and \(a_2=4\); batch B has \(b_1=1\) and \(b_2=6\). Use ordinary absolute distance.
The cross-batch distances are \(d(a_1,b_1)=|0-1|=1\), \(d(a_1,b_2)=|0-6|=6\), \(d(a_2,b_1)=|4-1|=3\), and \(d(a_2,b_2)=|4-6|=2\).
For \(a_1\), the nearer B point is \(b_1\), since \(1<6\). From \(b_1\), \(a_1\) is nearer than \(a_2\), since \(1<3\). Therefore, \((a_1,b_1)\) is an MNN pair. For \(a_2\), the nearer B point is \(b_2\), since \(2<3\). From \(b_2\), \(a_2\) is nearer than \(a_1\), since \(2<6\). Therefore, \((a_2,b_2)\) is also an MNN pair. The complete set is \(\{(a_1,b_1),(a_2,b_2)\}\).
A One-Way Neighbor Is Not Necessarily Mutual
Checking just one direction can create candidate pairs that fail the reciprocal rule. The following example shows why both rankings must be examined.
Worked Example: Rejecting a One-Way Match
Take hypothetical two-dimensional coordinates with Euclidean distance. Let batch A contain \(a_1=(0,0)\), \(a_2=(4,0)\), and \(a_3=(0,3)\). Let batch B contain \(b_1=(1,0)\) and \(b_2=(5,2)\).
From \(a_1\), the distances to \(b_1\) and \(b_2\) are \(1\) and \(\sqrt{29}\approx5.385\), respectively, so \(b_1\) is the nearest B point. From \(b_1\), the distances to \(a_1,a_2,a_3\) are \(1,3,\sqrt{10}\approx3.162\). Thus, \(a_1\) is also nearest to \(b_1\), and \((a_1,b_1)\) is mutual.
From \(a_2\), the distances to \(b_1,b_2\) are \(3\) and \(\sqrt{5}\approx2.236\), so \(b_2\) is nearest. From \(b_2\), the distances to \(a_1,a_2,a_3\) are \(\sqrt{29}\approx5.385\), \(\sqrt{5}\approx2.236\), and \(\sqrt{26}\approx5.099\). Therefore, \(a_2\) is nearest to \(b_2\), making \((a_2,b_2)\) mutual.
Finally, \(a_3\)'s distances to \(b_1,b_2\) are \(\sqrt{10}\approx3.162\) and \(\sqrt{26}\approx5.099\). Its one-way nearest neighbor is \(b_1\). But \(b_1\)'s nearest point is \(a_1\), not \(a_3\), because \(1<\sqrt{10}\). So \((a_3,b_1)\) is not an MNN pair. The MNN set contains two pairs, not three.
What Changes When \(k\) Increases?
Using more than one neighbor can retain reciprocal pairs that are not each point’s single closest cross-batch partner. It also makes the pair set less restrictive and can allow a point to appear in multiple pairs. The next example calculates the ranks to show exactly how this happens.
Worked Example: Comparing One- and Two-Nearest-Neighbor Pairs
Let hypothetical one-dimensional batch A coordinates be \(a_1=0,a_2=4,a_3=8\), and batch B coordinates be \(b_1=1,b_2=5,b_3=9\). The distance rows below give the distances from each A point to \(b_1,b_2,b_3\), in that order.
For \(a_1\), the row is \((1,5,9)\); for \(a_2\), it is \((3,1,5)\); and for \(a_3\), it is \((7,3,1)\). Their neighbor orders are therefore \(b_1,b_2,b_3\); \(b_2,b_1,b_3\); and \(b_3,b_2,b_1\), respectively. In the reverse direction, the distances from \(b_1\) to \((a_1,a_2,a_3)\) are \((1,3,7)\); from \(b_2\), they are \((5,1,3)\); and from \(b_3\), they are \((9,5,1)\).
With \(k=1\), the reciprocal nearest pairs are \((a_1,b_1)\), \((a_2,b_2)\), and \((a_3,b_3)\). With \(k=2\), \((a_2,b_1)\) is also included: \(b_1\) has rank 2 from \(a_2\), and \(a_2\) has rank 2 from \(b_1\). Similarly, \((a_3,b_2)\) is included because both ranks are 2. The \(k=2\) pair set is thus \(\{(a_1,b_1),(a_2,b_1),(a_2,b_2),(a_3,b_2),(a_3,b_3)\}\). For example, \((a_1,b_2)\) is not included: \(b_2\) has rank 2 from \(a_1\), but \(a_1\) has rank 3 from \(b_2\). Reciprocity is still required in both directions.
Assumptions, Interpretation, and Alternatives
Identifying MNNs is a deterministic operation once the points, representation, metric, neighbor rule, and tie convention are fixed. Interpreting those pairs as evidence about shared cell states requires more. In particular, both batches must be represented on comparable coordinates, and the chosen distance must reflect meaningful similarity for the comparison. The shared-state assumption matters: if the batches contain no comparable states in a region, proximity there does not create a genuine biological correspondence.
An MNN is a candidate pair of observations, not a statistical test, a probability that two cells are equivalent, or proof that a shared state exists. Nor does it show that a difference between batches is purely technical. Earlier material on confounding emphasizes why observational data may not distinguish technical shifts from biological differences without suitable design and assumptions.
| Approach | Pair rule | What it provides | Main caution |
|---|---|---|---|
| One-way nearest neighbor | Keep a point’s closest point in the other batch, in only one direction | A directed candidate relationship | The selected point may prefer a different partner in the reverse direction |
| Mutual nearest neighbors | Keep a pair only if each point is the other’s nearest cross-batch point | A reciprocal, locally closest pair under the chosen metric | May omit plausible correspondences that are not each other’s single closest point |
| Mutual \(k\)-nearest neighbors | Keep a pair if each point ranks within the other’s first \(k\) neighbors | A less restrictive reciprocal relation | Can yield many-to-many pairs and depends on the choice of \(k\) |
| Fixed one-to-one assignment | Choose a set of pairs subject to a global matching rule | A constrained assignment across the batches | Requires an assignment objective and constraints; it is not the same as local reciprocity |
Several basic checks help prevent mistakes. Confirm that cross-batch distances use the intended common coordinates and the same metric in both directions. Verify that a proposed pair is in fact within the specified neighbor rank for each point. Inspect ties and state their handling. If the selected pairs change substantially under a reasonable change in scaling or distance, that is a warning that the result depends on the geometric choices rather than an invariant property of the cells. These checks do not establish pair quality; they check whether the stated MNN rule has been applied and interpreted consistently.
Common Pitfalls and Limits
- Checking only one direction. “\(y_j\) is closest to \(x_i\)” does not imply “\(x_i\) is closest to \(y_j\).” Check both rankings.
- Mixing within-batch and cross-batch neighbors. MNNs are defined by searching the opposite batch for each point, not by pooling both batches or using within-batch neighbors.
- Assuming pairs must be one-to-one for every \(k\). The \(k=1\) relation is one-to-one when distances are unique; for \(k>1\), points can participate in several reciprocal pairs.
- Treating a pair as proof of biological identity. Mutual proximity is conditional on the representation, metric, and shared-state assumptions. It is evidence for a candidate correspondence, not proof.
MNNs are useful because reciprocity removes some one-sided neighbor relationships and yields an explicit set of cross-batch candidate pairs. Their limitation is equally important: “nearest” is relative to a chosen geometry, and local proximity cannot repair an unsuitable representation or overcome a lack of shared biological states. The definition identifies pairs; deciding how to use them for integration is a separate question.
Check Your Understanding
Answer each question, then compare with the solutions below.
- In one sentence, state both conditions required for \((x_i,y_j)\) to be an MNN.
- If \(y_j\) is the nearest B point to \(x_i\), but \(x_i\) is the second-nearest A point to \(y_j\), is the pair an MNN for \(k=1\)? What about \(k=2\)?
- Why can a change in coordinate scaling alter the MNN set even when the cell observations have not changed?
- Does identifying an MNN pair prove that its two cells have the same biological state? Explain briefly.
Solutions. (1) Each point must be the other’s nearest point in the opposite batch under the specified distance. (2) It is not an MNN for \(k=1\), because the reverse rank is 2; it is a mutual \(k\)-nearest pair for \(k=2\), provided the forward rank is also at most 2. (3) Scaling changes distances and can change their ordering, so a different point may become nearest. (4) No. The pair is a geometric candidate conditional on the representation, metric, and shared-state assumptions; proximity alone does not prove biological equivalence.