Choosing Edge Weights for Cell MSTs

Why Edge Weights Matter

A minimum spanning tree (MST) connects all vertices in a graph using edges with minimum possible total weight, without forming cycles. For a cell MST, the vertices represent cells and the edge weights represent dissimilarities between cell states. The tree is therefore not determined by the cell coordinates alone: it also depends on how dissimilarity is defined.

A change in weights can change which edges are selected, even when the cells and their representation stay fixed. Euclidean distance responds to differences in both direction and magnitude. Cosine dissimilarity compares direction and discounts magnitude. A locally scaled weight adjusts a distance according to neighborhood scales, which can reduce the influence of uneven cell density. These choices encode different geometric priorities; none is automatically appropriate for every trajectory.

The graph may be complete, with a candidate edge for every pair of cells, or it may be a specified sparse candidate graph. In either case, an MST exists only if the candidate graph is connected. If the graph is disconnected, there is no tree spanning all its vertices unless additional edges are introduced. The weights discussed below change edge costs; they do not by themselves determine which pairs are eligible as candidate edges.

Three Choices of Edge Weight

For fixed cell vectors, Euclidean distance is

It is measured in the units of the feature coordinates. A change in a coordinate’s scale can affect the distances, so the representation and any preprocessing must be held fixed when comparing trees. Euclidean distance is a metric: in particular, it satisfies the triangle inequality.

For nonzero vectors, cosine dissimilarity is

It ranges from 0 to 2. It is 0 when two vectors point in the same direction and 2 when they point in opposite directions. Because their lengths do not enter the normalized dot product, multiplying either vector by a positive constant leaves the cosine dissimilarity unchanged. Cosine dissimilarity is not generally a metric, but an MST can still be constructed from its symmetric nonnegative edge weights. It is undefined for a zero vector, which must be handled before using this formula.

A locally scaled weight divides a base distance by a scale associated with each endpoint. One common choice is

where \(d_{ij}\) is a chosen base distance and \(s_i>0\) is a local scale for cell \(i\). For example, \(s_i\) can be the distance from cell \(i\) to its \(k\)th nearest neighbor in the same representation. A large local scale indicates that neighbors are relatively far away; a small one indicates a denser neighborhood. This symmetric definition gives a dimensionless weight when \(s_i\) and \(d_{ij}\) are measured in the same units. Other local-scaling conventions exist, so the formula and scale definition should be reported rather than referred to only as “local scaling.”

When local scales are estimated from the cells, the neighborhood parameter \(k\), the distance used to find neighbors, and the handling of ties or zero scales all matter. A zero scale makes the displayed formula undefined, so implementations need a principled positive-scale rule, such as a stated floor. That adjustment can affect the resulting tree and should not be hidden.

Constructing and Comparing the Trees

For any of the three weights, Kruskal’s algorithm gives a direct way to construct an MST: sort candidate edges from smallest to largest, then add an edge if it joins two components that are not yet connected. Skip an edge if adding it would create a cycle. Stop when \(n-1\) edges have been added. With tied weights, more than one MST may be optimal; a tie-breaking rule can select one tree, but it does not make that tree uniquely determined by the weights.

A useful justification for this procedure is the cut property. A cut divides the vertices into two nonempty sets. If an edge of strictly smallest weight crosses that cut, it belongs to every MST. To see why, consider an MST that omits the edge. Adding it creates a cycle, and that cycle must include another edge crossing the same cut. Replacing that other edge by the strictly lighter crossing edge keeps the graph connected, removes the cycle, and lowers the total weight. This contradicts the claim that the original tree was minimum. Ties weaken the conclusion: a minimum-weight crossing edge is safe to add, but it need not be in every MST.

Interpreting the Choice and Checking for Problems

Euclidean weights are a natural option when distances in the chosen representation are meaningful and differences in magnitude should count. Cosine weights are useful when directional similarity is the intended comparison and vector magnitude should have little or no influence. Locally scaled weights can reduce the dominance of dense regions by adjusting edge costs relative to local neighborhood distances. In exchange, local scaling introduces choices about neighborhood size and can make sparse regions exert a strong influence on normalized weights.

These are geometric choices, not tests of whether a biological trajectory is true. An MST summarizes a weighted graph; by itself it does not establish a temporal ordering, causal progression, or unique biological path. The inferred edges can also depend on the representation supplied to the distance calculation. The geometry chosen for trajectory inference should therefore be considered alongside the edge-weight formula, not treated as a separate afterthought.

Several checks help reveal when an edge-weighting choice is problematic:

• Inspect scale and representation. If a few coordinates dominate Euclidean distances because of their units or ranges, the resulting edges may reflect that scaling rather than the intended cell-state geometry.
• Check cosine inputs. Zero vectors make cosine dissimilarity undefined. Also verify that disregarding magnitude is appropriate for the biological question; a large magnitude difference can be consequential even when directions match.
• Inspect local scales. Very small or very large \(s_i\) values can strongly change normalized edge weights. Check how scales vary, whether ties occur, and whether a few cells are unusually isolated.
• Check connectivity and ties. A disconnected candidate graph cannot yield a spanning tree. Repeated edge weights can permit multiple MSTs, so one displayed tree may conceal ambiguity.
• Compare edge sets under plausible choices. If modest changes to the distance, local neighborhood size, or candidate graph produce very different edges, report that sensitivity. Do not describe one unstable edge as definitively supported.

One practical comparison keeps the cell representation and candidate graph fixed, constructs an MST under each weighting, and tabulates the edges that are shared or changed. For locally scaled weights, repeat the comparison for a small set of scientifically reasonable neighborhood sizes. This comparison diagnoses sensitivity to the weighting choice; it does not identify a universally correct weight or replace biological validation.