# Graph construction and spatial schema

This reference targets **PathML 3.0.5 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()`.

In v3.0.5 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.

`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, accessed 2026-07-23

- 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.5/pathml/graph/preprocessing.py
- Stable graph schema/helpers:
  https://github.com/Dana-Farber-AIOS/pathml/blob/v3.0.5/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