Cell-Cell Neighborhood Graphs

Why Represent Cells as a Graph?

A single-cell data set can be represented by a point for each cell in a chosen feature space. A graph provides a different kind of description: it records which pairs of cells are treated as locally related, and optionally how strong each recorded relationship is. This can preserve a useful neighborhood structure without requiring every pairwise distance or every coordinate to be examined directly.

The graph’s links describe a relation defined by the graph-building rule and the chosen representation. They are not, by themselves, declarations of biological identity. In particular, an edge does not guarantee that two cells have the same cell type, share a condition, or have a direct biological interaction. Those claims require evidence and definitions beyond graph structure.

The earlier material on embeddings established that an embedding is a representation of cells whose geometry can be inspected, while its visible geometry has limitations. A cell-cell graph is another representation of relationships. Its meaning depends on how vertices are defined, which pairs receive edges, and what the edge weights mean.

Vertices, Edges, and Weights

In this tutorial, the primary convention is a simple, undirected cell graph with no self-loops: an edge joins two distinct cells, and the edge from cell \(i\) to cell \(j\) is the same as the edge from \(j\) to cell \(i\). Thus the graph represents a symmetric relationship. Directed graphs are possible when the relationship is asymmetric, but direction must then be retained rather than silently interpreted as mutual connection.

An edge records which pairs are included. A weight records an additional property of an included pair. For example, an affinity weight may be larger for a pair considered more similar under the chosen representation and rule. The numerical scale is a modeling convention: weights need not be probabilities, and a weight of 0.8 does not automatically mean an 80% chance that two cells share a type.

For a nonnegative affinity representation, require every included edge to have a strictly positive weight. This convention makes an absent edge distinguishable from a present edge using the weighted adjacency matrix alone. If an application allows a present edge to have weight zero, the weight matrix cannot mark presence unambiguously; an additional binary adjacency matrix is then needed.

The zero on the diagonal follows from the no-self-loop convention, not from a claim that a cell is biologically unrelated to itself. For present edges, an affinity weight summarizes the specified pairwise relationship; it does not reveal every cause of that relationship. A graph is therefore a deliberately selective representation, not a complete account of all possible cell-to-cell relations.

Worked Example: Reading a Small Cell Graph

How the Matrix Encodes Edge Presence

For an undirected graph, the edge set contains unordered pairs. The adjacency matrix stores those same decisions in a square array indexed by cells. The matrix is symmetric because an included pair \(\{i,j\}\) contributes both entries \(A_{ij}\) and \(A_{ji}\), or both \(W_{ij}\) and \(W_{ji}\).

The positive-weight convention gives a direct way to recover edge presence from \(W\). For distinct cells \(i\) and \(j\), an edge is present exactly when \(W_{ij}>0\). If no edge is present, \(W_{ij}=0\). Therefore the binary matrix can be recovered by the indicator rule below.

This rule depends on the assumption that every included edge has a positive weight. If zero is permitted as a weight on a present edge, then \(W_{ij}=0\) has two possible meanings: absent edge or present edge with zero weight. In that setting, the weighted matrix alone is insufficient. Store edge presence separately in \(A\), with the weight recorded as a separate attribute.

An Edge Is Not a Cell-Type Label

Cell type is an annotation of a cell, whereas an edge is a relation between two vertices. A local similarity rule may link cells with different labels, particularly when cell states vary continuously, labels are coarse, or the chosen representation makes two annotated groups close. Conversely, cells assigned the same label need not all be connected in a graph.

This distinction is logical as well as practical. The graph definition says what qualifies as an edge; it does not include a claim about annotations unless the construction explicitly uses labels. Thus an edge between distinct annotated types is not a contradiction of the graph definition. It is evidence that the pair met the specified graph rule, not proof that the labels are wrong or that the cells are biologically identical.

Justification: What Does a Positive Weight Add?

In a binary graph, an included pair has the same recorded status as every other included pair: \(A_{ij}=1\). A weighted graph refines that description by assigning an affinity value \(w_{ij}\) to each included pair. If all positive weights share a meaningful scale, pairs can be ordered by the stated convention. For the first example, \(0.90>0.80>0.60\), so the recorded affinity ordering is \(A\)--\(B\), then \(C\)--\(D\), then \(B\)--\(C\).

The conclusion follows from the numeric comparison and the model convention, not from a universal property of graphs. If weights were defined as distances rather than affinities, the interpretation would reverse: a smaller value would mean a closer pair, and zero could be a valid value for an included edge. In that case, retain edge presence separately rather than using a zero in the weight matrix to mean absence. Never interpret the ordering of weights until the weight definition and scale are stated.

Diagnostics, Alternatives, and Limitations

A graph can be represented as an edge list, a binary adjacency matrix, a weighted adjacency matrix, or a visual diagram. An edge list is often compact when relatively few pairs are included; a matrix makes pairwise presence easy to inspect for a small graph. A diagram can make local structure visible, but the drawing layout may introduce visual impressions that are not properties of the graph. These are alternative representations of the same graph, not different biological findings.

A binary graph is appropriate when the intended information is only whether a pair is included. A weighted graph retains an additional strength or distance value, but only if that quantity is clearly defined. A point embedding instead represents cells with coordinates; it can show geometric structure, while a graph explicitly selects relationships among pairs. Neither representation alone proves cell identity, lineage, interaction, or causality.

Useful checks focus on whether the graph matches its stated definition and whether its interpretation is defensible:

• Confirm that each vertex corresponds to the intended observational unit, usually one cell, and that cell identifiers are not duplicated or mismatched.
• Check that an undirected graph has symmetric adjacency or weight entries and that the diagonal matches the stated self-loop convention.
• Verify how absence is encoded. If zero means no edge, ensure included affinity weights are strictly positive; otherwise keep edge presence separately.
• Inspect the weight definition and range before comparing magnitudes. A value is not a probability unless the method explicitly defines and calibrates it as one.
• Check whether the local relationships change substantially under reasonable choices of representation or edge rule. Strong dependence can make downstream conclusions fragile.
• Consider whether batch, quality, or other technical structure may influence the representation and therefore the selected relationships. A graph records the input structure it receives; it does not automatically remove technical effects.

A graph is selective by design. A missing edge does not establish that two cells are biologically unrelated, and an included edge does not establish shared type. In a large graph, a picture may conceal many pairs, and an apparently prominent edge can depend on the weight scale. Local graphs can also omit longer-range relationships that matter for a different scientific question. Graph structure should therefore be reported together with the representation, edge-selection rule, direction convention, and weight meaning.

Common Mistake

A graph is most useful when its interpretation stays close to its definition. State what the vertices represent, what qualifies as an edge, whether the graph is directed, and how weights are scaled. This prevents a concise structural representation from being mistaken for a complete biological conclusion.