# Graph construction and spatial schema

This reference targets **PathML 3.0.8 stable**. The stable graph API is based on
graph builders and PyTorch Geometric data objects; it does not contain the
`CellGraph.from_instance_map()` abstraction found in older generated examples.

## Stable public exports

```python
from pathml.graph import (
    ColorMergedSuperpixelExtractor,
    Graph,
    HACTPairData,
    KNNGraphBuilder,
    RAGGraphBuilder,
    build_assignment_matrix,
    get_full_instance_map,
)
```

Other classes documented under `pathml.graph.preprocessing` may be internal or
not re-exported. Prefer the public names above and pin the PathML version.

## Inputs and coordinate contract

A cell/tissue graph starts with:

1. an instance map `(height, width)`, where 0 is background and each object has a
   positive integer label;
2. one feature row per object;
3. optional node annotation rows and a graph target; and
4. explicit coordinate units and image level.

For stable builders, make labels contiguous `1..N`. Both graph topology and
feature alignment assume a deterministic object order. Build and persist a table:

```text
node_index,instance_label,centroid_x,centroid_y,feature_row
0,1,120.5,88.0,0
1,2,175.0,92.5,1
```

PathML computes centroids from `skimage.measure.regionprops` and stores them as
`(x, y)` after integer rounding. This differs from tile `(i, j)` order.

If the instance map comes from level `L`, KNN distances and centroids are in
level-`L` pixels:

```text
x_um = x_L * downsample_L * mpp_x
y_um = y_L * downsample_L * mpp_y
```

Never describe a radius/threshold as biological distance unless it has been
converted to a physical unit.

## Avoid full-slide reconstruction by default

`get_full_instance_map(wsi, patch_size, mask_name="cell")` reconstructs a dense
image and instance map large enough to cover the slide. On a gigapixel WSI this
can exhaust RAM and duplicate tile-overlap objects.

Use it only for a bounded ROI or small image after estimating memory. For large
slides:

- construct graphs per nonoverlapping region;
- reconcile boundary objects with stable global IDs;
- optionally join regional graphs with a documented edge policy; and
- use sparse coordinates/features rather than a dense whole-slide canvas.

Do not use padded zero regions as tissue. Record crop origin so local coordinates
can be mapped to the slide.

## KNN graph

```python
import numpy as np
from pathml.graph import KNNGraphBuilder

# instance_map labels are 0 background, then contiguous 1..N.
n_nodes = int(instance_map.max())
features = np.ones((n_nodes, 1), dtype=np.float32)

builder = KNNGraphBuilder(
    k=5,
    thresh=80,              # selected-level pixels
    add_loc_feats=True,
    return_networkx=False,
)
graph = builder.process(
    instance_map,
    features=features,
    annotation=None,
    target=None,
)
```

Stable behavior:

- `k` nearest neighbors are computed from centroids.
- `thresh=None` keeps all KNN edges; otherwise edges longer than `thresh` are
  removed.
- `k` must be smaller than the available node count.
- adjacency generated by nearest-neighbor queries may be directed; do not assume
  every reverse edge exists.
- `add_loc_feats=True` appends centroids normalized by image width/height.
- `return_networkx` is a **builder constructor** option, not an argument to
  `process()`.

Distinct objects can round to the same centroid; zero-distance adjacency entries
are discarded by the builder, so inspect coincident centroids and missing edges.
For anisotropic MPP, pixel-space nearest neighbors are not physical nearest
neighbors. Convert centroids to micrometres first and use
`builder.process_with_centroids(centroids_xy_um, features=features)` with
`centroids_xy_um` as a CPU Torch tensor and `add_loc_feats=False`; set `thresh`
in micrometres and retain original pixel
coordinates separately. Scaling only the reported distances after building
the graph does not fix a topology constructed in the wrong metric.

In v3.0.8 source, `BaseGraphBuilder.process()` reads `features.shape` before its
nominal `features=None` branch. Pass an explicit `(N, F)` feature array.

## Region adjacency graph

```python
from pathml.graph import RAGGraphBuilder

builder = RAGGraphBuilder(
    kernel_size=3,
    hops=1,
    add_loc_feats=False,
    return_networkx=False,
)
graph = builder.process(instance_map, features=features)
```

`RAGGraphBuilder` dilates each labeled instance and connects labels encountered at
the boundary. `hops>1` expands neighborhoods. Stable implementation assumes
contiguous positive instance IDs; relabel and validate first.

Choose RAG for contact/near-contact topology and KNN for centroid proximity. A
RAG edge is still an image-processing construct, not proof of biological
interaction.

## Tissue superpixels

`ColorMergedSuperpixelExtractor` performs SLIC superpixels followed by
color-based hierarchical merging. Its output depends on image color space,
downsampling, blur, target superpixel size/count, merge threshold, and optional
tissue mask.

Fit/tune these choices on training slides only. Verify:

- every retained superpixel overlaps tissue as intended;
- object labels are contiguous;
- tiny/huge regions and holes are handled;
- downsampled boundaries map correctly to the source level;
- stain normalization did not erase discriminative structure.

The extractor is influenced by histocartography/HACT implementations. Review
license obligations when redistributing derived code or artifacts.

## Output schema

Stable `pathml.graph.Graph` is a PyTorch Geometric `Data` subclass with:

```text
node_centroids   # tensor [N, 2], (x, y)
node_features    # tensor [N, F] or None
edge_index       # tensor [2, E]
edge_features    # tensor/array or None
node_labels      # tensor/array or None
target           # graph target or None
```

It does not automatically expose canonical PyG `x`, `pos`, `edge_attr`, and `y`
aliases. Adapt explicitly:

```python
from torch_geometric.data import Data

pyg_graph = Data(
    x=graph.node_features,
    pos=graph.node_centroids,
    edge_index=graph.edge_index,
    edge_attr=graph.edge_features,
    y=graph.target,
)
```

Validate shapes before training:

```python
assert graph.node_centroids.ndim == 2
assert graph.node_centroids.shape[1] == 2
assert graph.node_features.shape[0] == graph.node_centroids.shape[0]
assert graph.edge_index.shape[0] == 2
assert int(graph.edge_index.min()) >= 0
assert int(graph.edge_index.max()) < graph.node_centroids.shape[0]
```

Handle empty/no-edge graphs before `min()`/`max()`. Check finite values,
self-loops, duplicates, connected components, degree distribution, and edge
direction.

## Exchange schema and validator

For safer exchange, use bounded JSON rather than a pickled `.pt` object:

```json
{
  "schema_version": "1.0",
  "slide_id": "slide-001",
  "coordinate_unit": "um",
  "nodes": [
    {"id": "cell-1", "x": 12.5, "y": 30.0, "features": [0.2, 1.3]},
    {"id": "cell-2", "x": 15.0, "y": 32.0, "features": [0.4, 1.1]}
  ],
  "edges": [
    {"source": "cell-1", "target": "cell-2"}
  ]
}
```

Validate:

```bash
python scripts/validate_spatial_schema.py graph \
  --input derived/graph.json \
  --root . \
  --max-nodes 100000 \
  --max-edges 1000000
```

The validator checks strict JSON, bounded counts, unique node IDs, finite
coordinates/features, explicit units, valid edge endpoints, self-loops, and
duplicate edges. It never imports Torch or loads `.pt`.

## HACT cell-to-tissue graphs

HACT represents:

- a cell graph;
- a tissue/superpixel graph; and
- an assignment from each cell to a tissue node.

Stable helper:

```python
from pathml.graph import build_assignment_matrix

assignment_sparse = build_assignment_matrix(
    low_level_centroids=cell_centroids_xy,
    high_level_map=tissue_instance_map,
    matrix=False,
)
```

Inputs must share the same origin, level, orientation, and units.
`cell_centroids_xy` is `(x, y)`; the helper indexes the image as `[y, x]`.
Tissue labels should be contiguous positive IDs. Cells on background or outside
the map require an explicit policy before calling the helper.

The helper truncates centroid coordinates to integers and subtracts one from the
sampled tissue label. Background label 0 therefore indexes the final tissue
column rather than producing an unassigned cell. Reject/filter background and
out-of-bounds centroids first and retain an explicit unassigned-cell record.

`HACTPairData` stores:

```text
x_cell, edge_index_cell,
x_tissue, edge_index_tissue,
assignment, target
```

PathML's `EntityDataset` can assemble these from `.pt` files, but stable source
uses unrestricted PyTorch object loading. Never use it on untrusted artifacts.

## Graph feature extraction

Node features may include:

- morphology from the instance mask;
- marker intensities from a validated channel manifest;
- learned image embeddings from a trusted local model;
- cell-type probabilities rather than hard labels; and
- normalized position, when scientifically justified.

Keep a schema with feature name, unit, transform, missing policy, and training-only
fit provenance. PathML graph builders do not provide the broad fabricated helper
catalog (`extract_morphology_features`, `extract_intensity_features`,
`analyze_neighborhoods`, and similar) shown in older references. Use
scikit-image/pandas or a reviewed feature package explicitly.

Graph-level topology features can be extracted with
`pathml.graph.preprocessing.GraphFeatureExtractor`, but disconnected graphs may
make diameter/radius undefined and some centrality algorithms may not converge.
Validate topology and handle exceptions rather than dropping graphs silently.

## Boundary and overlap policy

Overlapping tiles can create duplicate cells and duplicated edges. Choose one:

- keep only each tile's central crop;
- reconcile objects by global coordinates and mask overlap;
- run segmentation on a larger context but emit a nonoverlapping center;
- construct per-region graphs and join only verified boundary nodes.

Record:

- context and emission windows;
- global instance ID scheme;
- duplicate matching threshold;
- edge creation across boundaries;
- excluded border-object count; and
- stitching/reconciliation software version.

## Leakage and evaluation

Graph construction must happen after patient/slide splits. Keep all subgraphs from
one slide in one split. Fit feature scalers, dimensionality reduction,
neighborhood thresholds, graph augmentations, and class balancing on training
graphs only.

Report:

- patient and slide counts, not only graph counts;
- node/edge distributions by split;
- site/scanner/stain balance;
- isolated/disconnected graph handling;
- external-slide/site validation where relevant;
- uncertainty and confidence intervals at the patient/slide unit.

Do not treat thousands of correlated nodes or tiles as independent patients.

## Sources and further reading

API baseline reviewed 2026-10-01 using the released wheel/tag; hosted docs may lag.

- Stable graph guide:
  https://pathml.readthedocs.io/en/stable/graphs.html
- Stable graph API:
  https://pathml.readthedocs.io/en/stable/api_graph_reference.html
- Stable graph builder source:
  https://github.com/Dana-Farber-AIOS/pathml/blob/v3.0.8/pathml/graph/preprocessing.py
- Stable graph schema/helpers:
  https://github.com/Dana-Farber-AIOS/pathml/blob/v3.0.8/pathml/graph/utils.py
- Pati et al. (2022), HACT:
  https://doi.org/10.1016/j.media.2021.102264
- Jaume et al. (2021), histocartography:
  https://proceedings.mlr.press/v156/jaume21a.html
