Connectivity Graphs for Batch-Condition Overlap

Why Look at Connectivity?

A cross-tabulation shows which batch-condition combinations occur. A graph reorganizes the same design information to answer a structural question: can observed combinations link the batches and conditions involved in a comparison? This matters because a condition effect cannot be separated from batch effects merely by fitting a model if the observed design has no paths connecting the relevant levels.

The graph is a diagnostic for identifiability under an additive batch-condition model. It does not measure the strength of evidence, establish that batch effects are truly additive, or show that adjustment will remove a batch effect. Those questions require information beyond the graph.

Constructing the Bipartite Graph

Definition: A bipartite batch-condition graph has one set of vertices for observed batch levels and a separate set for observed condition levels. Draw an edge between batch \(b\) and condition \(c\) if at least one analyzed sample belongs to that batch-condition combination. A connected component is a maximal group of vertices in which every pair can be joined by a path of edges.

Each sample contributes to an observed combination, but repeated samples in the same combination do not create additional edges. For example, 20 cells from batch B1 and condition C1 still correspond to one B1-C1 edge. The number of cells or samples can be recorded as an edge weight for other diagnostics, but connectivity asks only whether the combination is present.

For the graph, include levels represented by at least one analyzed sample. A batch or condition level with no analyzed samples has no edge and no data to estimate its effect; flag it separately rather than treating it as an informative component. The graph is usually built from the sample design, not separately for each gene, provided the same analyzed samples contribute measurements for the genes under study.

Worked Example: Drawing the Graph From a Cross-Tabulation

Suppose a hypothetical single-cell experiment has the following numbers of cells in each batch-condition combination. A zero means no cells were observed in that combination.

	Condition C1	Condition C2	Condition C3
Batch B1	12	8	0
Batch B2	0	15	6
Batch B3	0	0	9

Create batch vertices B1, B2, B3 and condition vertices C1, C2, C3. Draw edges B1-C1, B1-C2, B2-C2, B2-C3, and B3-C3. The counts 12, 8, 15, 6, and 9 do not change which edges exist.

There is one connected component: the path B1-C2-B2-C3-B3 links B1, B2, and B3, while B1 also links to C1. Thus every represented batch and condition level belongs to the same component. Under the additive model described below, this connectedness permits batch-effect contrasts among these batches and condition-effect contrasts among these conditions to be identified from the design. It does not guarantee that those contrasts will be estimated precisely.

Connectivity and the Additive Model

For a single measured outcome, such as a gene's expression on a specified analysis scale, consider the additive model for the expected value in batch \(b\) and condition \(c\):

\eta_{bc}=\beta_b+\gamma_c

Here \(\beta_b\) is the batch contribution and \(\gamma_c\) is the condition contribution. The model assumes that the expected value is a sum of these contributions, with no batch-by-condition interaction. The graph addresses whether these additive contributions can be separated by the observed design; it does not verify the assumption. If there are multiple samples per observed combination, the same graph applies to the design, while replication and the chosen sampling model affect uncertainty.

This parameterization has an inherent location ambiguity: adding a constant to every batch effect and subtracting it from every condition effect leaves all fitted values unchanged. Reference-level or sum-to-zero constraints can choose a representation, but constraints cannot create comparisons absent from the data. With a disconnected graph, there is a separate ambiguity for each component.

Theorem: In the additive model \(\eta_{bc}=\beta_b+\gamma_c\), consider a graph containing only represented batch and condition levels. Within each connected component, batch-effect differences and condition-effect differences are identifiable from the design. Differences of batch effects between components, and differences of condition effects between components, are not separately identifiable without additional assumptions or data connecting those components.

Why Components Determine Identifiability

The result follows by examining changes to model coefficients that leave all observed fitted values unchanged. Let \(u_b\) and \(v_c\) be changes to the batch and condition effects. For every observed edge, an unchanged fitted value requires \(u_b+v_c=0\). In a connected component, this forces all batch changes to equal one constant and all condition changes to equal its negative.

u_b+v_c=0\ \text{for every observed edge }(b,c) \quad\Longrightarrow\quad u_b=t,\qquad v_c=-t \ \text{within each connected component.}

To see why, start at any batch vertex in a component and call its change \(t\). Every adjacent condition must have change \(-t\), because their sum on the edge is zero. Every batch adjacent to one of those conditions must then have change \(t\). Repeating this argument along paths gives the stated changes for every vertex in the component. Conversely, assigning those changes leaves every observed edge sum unchanged.

A contrast is identifiable only if it is unchanged by every coefficient change that preserves the observed fitted values. For example, within one component, \(\beta_{b_1}-\beta_{b_2}\) is unchanged because both batch effects shift by \(t\). But a batch-effect difference comparing two components can shift by the difference between their component-specific constants. The same reasoning applies to condition effects.

More generally, for a linear contrast with coefficients \(l_b\) on batch effects and \(m_c\) on condition effects, identifiability requires, in every component, that the sum of its batch coefficients equal the sum of its condition coefficients. This follows because its change under the component shift is \(t(\sum_b l_b-\sum_c m_c)\), which must be zero for each component. This criterion includes contrasts beyond simple differences.

Worked Example: Following a Path to Compare Batch Effects

Use the connected design in the first example. Suppose hypothetical mean expression values, in normalized expression units, for a particular gene are 5 for B1-C2, 8 for B2-C2, 10 for B2-C3, and 11 for B3-C3. Treat these as exact cell-combination means for illustrating identifiability, not as estimates from a real study.

On the shared condition C2, subtracting the two observed means cancels \(\gamma_{C2}\):

\eta_{B1,C2}-\eta_{B2,C2} =(\beta_{B1}+\gamma_{C2})-(\beta_{B2}+\gamma_{C2}) =\beta_{B1}-\beta_{B2} =5-8=-3.

Likewise, the shared condition C3 gives:

\beta_{B2}-\beta_{B3} =\eta_{B2,C3}-\eta_{B3,C3} =10-11=-1.

Add the two differences along the path B1-C2-B2-C3-B3:

\beta_{B1}-\beta_{B3} =(\beta_{B1}-\beta_{B2})+(\beta_{B2}-\beta_{B3}) =-3+(-1)=-4.

Thus the design links the endpoints, and the specified additive model identifies their batch-effect contrast. The calculation is an algebraic illustration, not a claim that raw cell means should always be used for inference; sampling variability and the analysis model determine uncertainty.

Disconnected Components: What Cannot Be Compared

A graph with multiple components provides no observed path linking their effects. Applying a different shift \(t\) to each component preserves every observed fitted value, so cross-component contrasts of batch effects or of condition effects can change without changing the model fit. This is structural non-identifiability, not merely a large standard error.

Worked Example: A Condition Contrast Across Components

Consider a hypothetical design with two disconnected components: B1 is observed with C1 and C2, while B2 is observed with C3 and C4. Suppose the fitted combination means are 4 for B1-C1, 7 for B1-C2, 6 for B2-C3, and 8 for B2-C4, in normalized expression units. Each component is internally connected, but there is no edge linking the components.

Within the first component, the condition contrast is identified by the observed within-batch difference: \(\gamma_{C2}-\gamma_{C1}=7-4=3\) units. Within the second, \(\gamma_{C4}-\gamma_{C3}=8-6=2\) units. However, consider \(\gamma_{C1}-\gamma_{C3}\), which compares conditions in different components.

Shift the batch effects in the first component by \(t\) and its condition effects by \(-t\), leaving the second component unchanged. All four fitted means remain the same. Under this shift, the contrast oriented as \(\gamma_{C1}-\gamma_{C3}\) changes by \(-t\), because \(\gamma_{C1}\) decreases by \(t\) and \(\gamma_{C3}\) does not change. Since \(t\) is arbitrary, the contrast is not identified by these observations. The displayed means do not resolve that ambiguity.

Adding a Connecting Combination

A new observed batch-condition combination can join components if its edge links a batch vertex in one component to a condition vertex in another. This can remove a structural barrier to comparing effects under the additive model. It does not, by itself, ensure a useful estimate: a very small number of samples on the linking combination may provide little precision, and the model's additive assumption still needs substantive justification.

Worked Example: A Bridge Joins Two Components

Suppose the disconnected design above is supplemented by one hypothetical sample in batch B1 under condition C3. Before adding it, there are two components: B1-C1-C2 and B2-C3-C4. The new B1-C3 edge joins them into one component along the path C2-B1-C3-B2-C4.

Under the additive model, the within-component condition contrasts can now be connected algebraically. For instance, \(\gamma_{C2}-\gamma_{C3}\) is identified using their shared batch B1, and \(\gamma_{C3}-\gamma_{C4}\) is identified using their shared batch B2. Therefore:

\gamma_{C2}-\gamma_{C4} =(\gamma_{C2}-\gamma_{C3})+(\gamma_{C3}-\gamma_{C4}).

The graph therefore changes the structural answer: the condition contrast across the former components is now identifiable in the additive model. But one sample on the bridge may yield a noisy estimate, and a batch-by-condition interaction could make a single shared edge insufficient as a scientifically credible basis for pooling. Connectivity is necessary for the relevant additive comparison, not a guarantee of precision or validity.

Diagnostics, Alternatives, and Limitations

A practical connectivity audit starts from the cross-tabulation and checks both the number of components and the levels in each component. Recheck the sample inclusion rules and labels if an unexpected split appears. In particular, confirm that condition names and batch identifiers were harmonized correctly; a mislabeled level can create an artificial separation or connection.

Connectivity complements, rather than replaces, other diagnostics. Cross-tabulations make the actual counts and imbalance visible. A design-matrix audit expresses the same model in algebraic form and can test particular contrasts. A graph is often the clearest way to see paths and disconnected groups, but it discards edge counts and therefore cannot diagnose whether a connected design has enough replication or severe imbalance. Numerical near-aliasing and variance inflation require additional analysis beyond this structural graph.

Do not confuse connectedness with balance. One path can connect all vertices even if most combinations are absent or have very few samples.
Do not infer a biological or technical effect from an edge. An edge records that a combination was observed, not that batch or condition caused an expression difference.
Do not treat a disconnected design as repaired by a correction algorithm. A transformation or constraint cannot supply the missing comparison; it can only impose additional choices or assumptions.
Do not overlook interactions. The graph theorem concerns the additive model. If condition effects vary by batch, a connected additive design does not establish that a single shared condition contrast is appropriate.

Key takeaway: In an additive batch-condition model, connected components describe the boundaries of structural comparison. Contrasts within a component can be identified; separate batch or condition effects across components cannot be disentangled from the component-specific shifts without additional linking data or assumptions.

Check Your Understanding

Answer each question, then compare with the brief solutions.

A batch has 30 cells in condition C1 and 5 cells in condition C2. How many graph edges do these observations create, and what does the difference in counts tell you about connectivity?
Two batches share one condition and belong to the same component. Under the additive model, which batch contrast is identified by their shared condition?
In one component, batch effects shift by \(t\) and condition effects by \(-t\). What happens to observed fitted means on its edges?
Why does a connected graph not show that the estimated condition contrast will have small standard error?
What is the structural consequence of adding an observed combination that links two previously disconnected components?

Solutions. (1) There are two edges, one for each observed combination; the counts do not alter connectivity, although they may matter for precision. (2) The difference in their batch effects is identified because subtracting the two shared-condition fitted means cancels that condition effect. (3) No observed fitted mean changes: each edge sum changes by \(t+(-t)=0\). (4) Connectivity ignores sample counts and other sources of uncertainty, so it does not establish adequate replication or precision. (5) The components become connected, making additional contrasts structurally identifiable under the additive model, although their estimates may still be imprecise or the model inappropriate.