---
kind: concept
slug: graph-label-propagation
title: Graph label propagation
summary: >-
  Spreads a few trusted values (labels or measured depths) over a neighbourhood graph so that every other node becomes a weighted average of its neighbours. Covers one variant so far: correcting a stereo point cloud with sparse LiDAR anchors, with the trade-off that anchors which disagree with the dense estimate can distort the result.
tags: [graph, sparse-supervision, depth-estimation]
papers: ["1906.06310"]
related: [semi-supervised-learning, graph-neural-network]
status: draft
updated_at: 2026-10-31
---

## Overview

Some nodes of a graph carry trusted values and the rest do not. Propagation
fills in the rest by making each unknown node's value a weighted average of its
neighbours' values, so the trusted values spread outward through the graph. The
invariant shared by the method is that, after propagation, every free node is
still such a weighted average, while the trusted nodes stay at their measured
values [arxiv:1906.06310 §4, eq. 8]. In the one card that uses this concept, the
nodes are 3D points of a stereo-derived point cloud, the trusted values are
depths of a few sparse LiDAR returns, and each point is linked to its ten
nearest neighbours [arxiv:1906.06310 §4, §5.1].

## Variants

Only one card in the wiki lists this concept, so this page covers one variant.
Other label-propagation methods are not described here until a card covers them.

### Graph-based depth correction (GDC)

Sparse LiDAR points are matched to pseudo-LiDAR points and used as fixed anchors.
The remaining depths are solved so that each point is still reconstructed from
its neighbours [arxiv:1906.06310 §4]. Card: [Pseudo-LiDAR++: Accurate Depth for
3D Object Detection in Autonomous Driving](/papers/1906.06310).

The steps are:

1. Build a k-nearest-neighbour graph over the 3D points, with k = 10 [arxiv:1906.06310 §4, §5.1].
2. For each point, compute weights that reconstruct its depth from its neighbours' depths, summing to one and zero outside its neighbourhood [arxiv:1906.06310 §4, eq. 7; app. B].
3. Hold the anchor depths fixed and solve for the remaining depths with a sparse iterative solver (conjugate gradient) [arxiv:1906.06310 §4, eq. 8; app. B, alg. 1].

Author-reported effect on KITTI validation, car, PointRCNN, moderate, IoU 0.7,
AP_BEV: the pseudo-LiDAR baseline reaches 56.0, stereo depth alone 64.0, and
stereo depth with 4-beam anchors and propagation 76.9 [arxiv:1906.06310 tab. 1].
With the same anchors but no propagation, the score is 73.0 [arxiv:1906.06310
tab. 4], so propagation adds about 3.9 points in this setting. The 4-beam input
is simulated by thinning 64-beam scans, not recorded with a 4-beam sensor
[arxiv:1906.06310 §5.1].

## When to use which

| Situation | Use this variant? | Why |
|---|---|---|
| A dense estimate exists and a few trusted measurements are available, with 3D coordinates to build a neighbourhood graph | Yes, as tested | The card's setting; the gain is reported for this combination [arxiv:1906.06310 tab. 1] |
| Anchors alone are the goal and fill-in is not needed | Anchors without propagation may be enough | 73.0 without propagation vs 76.9 with it, same anchors [arxiv:1906.06310 tab. 4] |
| The graph has k ≤ 3 neighbours per node | Expect a non-unique weight solution | The paper takes the minimum-norm solution in this case [arxiv:1906.06310 §4, eq. 7] |
| Tight latency budget on CPU hardware | Measure first | The 90 ms per frame figure comes from a single-GPU run [arxiv:1906.06310 app. D.4]; see [the card's Paper vs code section](/papers/1906.06310) for CPU libraries in the release |
| Anchors are far from the dense estimate at long range | Check the anchor gate | The released code drops anchors that differ by 2 m or more; the paper does not mention this step [see the card](/papers/1906.06310) |

No other evidence in the wiki covers the situations this table leaves out, such
as dense labels, non-geometric graphs, or other anchor sources.

## Implementation sketch

Language-agnostic pseudocode of the common core. Only one variant is covered,
so this is its sketch.

```pseudocode
# Build the graph: each point links to its k nearest neighbours
# [arxiv:1906.06310 §4, §5.1]
neighbors = k_nearest(points, k=10)

# Reconstruction weights: each value is a weighted sum of its neighbours,
# weights sum to one and are zero outside the neighbourhood
# [arxiv:1906.06310 §4, eq. 7; app. B]
W = reconstruction_weights(values, neighbors)

# Hold the anchors at their measured depths and solve the rest so every
# free value is still reconstructed from its neighbours
# [arxiv:1906.06310 §4, eq. 8; app. B, alg. 1]
free = conjugate_gradient_solve(W, anchors, free_indices)

# Anchors keep their measured values in the output
# [arxiv:1906.06310 §4]
corrected = merge(anchors, free)
```

Notes on the sketch:

- The weight solve needs a small regulariser for stability. The paper calls it
  slight and gives no value [arxiv:1906.06310 §4, app. B]. The released code
  uses 1e-5 [see the card](/papers/1906.06310), which is a code value, not a
  paper value.
- The stopping tolerance of the solver is not stated in the paper
  [arxiv:1906.06310 app. B].

## Contradictions

None across papers, since only one card uses this concept. Within that paper,
the main text states the weight step as a least-squares problem [arxiv:1906.06310
§4, eq. 7], while the appendix states a minimum-norm problem with the same
constraints [arxiv:1906.06310 app. B]. The paper does not show that these two
give the same weights.

## Papers

- [Pseudo-LiDAR++: Accurate Depth for 3D Object Detection in Autonomous Driving](/papers/1906.06310): applies graph-based propagation of sparse LiDAR anchors to a stereo point cloud and reports the gain on KITTI.