Attention-Grown Multi-Scale Node Sets for Long Video Graphs

Video models that reason over graphs usually decide in advance what a "node" is. Some use one node per frame, some use one node per detected object box, and some use one node per cell of a fixed grid. Each choice fails when the thing that matters changes size. A small, faint structure disappears inside a whole-frame node. A large organ gets shattered across many grid cells. A detector that never fires on a small structure removes it from the graph entirely. We propose to let the model choose its nodes for each frame. A spatial attention module looks at a feature pyramid, meaning the same frame described at several resolutions. It grows a quadtree: a coarse cell is split into four finer cells wherever attention says more detail is needed, until a fixed per-frame node budget is spent. The resulting cells become graph nodes. Temporal edges then connect each node to overlapping nodes in nearby and distant frames, including nodes at a different scale. An entity that grows or shrinks over time therefore stays connected.

The point is scalability without a fixed scale. A fully connected graph over $N$ spatial cells and $T$ frames costs $O(N^2T^2)$. Our graph spends a budget of $K \ll N$ nodes per frame and keeps temporal edges sparse. Where each unit of budget goes is the multi-scale attention's decision. The core claim is testable: at a matched node budget, placing nodes across scales by learned attention beats placing them at one resolution. The claim also predicts that edges crossing scales over time matter specifically when objects change apparent size.

What already exists and what does not

Four lines of prior work come closest. Each fixes the node definition in a different way.

Graph-based Pyramid Global Context Reasoning with a Saliency-aware Projection for COVID-19 Lung Infections Segmentation supplies half our method. It uses spatial and channel attention to project likely-lesion pixels into graph nodes, and it builds separate fully connected graphs at several sampling rates. It is limited to static 2D/2.5D slices, it keeps one independent graph per scale, and it names 3D extension as future work.

Video Instance Segmentation via Multi-Scale Spatio-Temporal Split Attention Transformer motivates cross-scale temporal links. It shows that attention from scale $l$ at frame $t$ to scale $l\pm1$ at frame $t'$ helps with deforming objects. However, it runs on dense feature grids, with no node budget, and its authors state that long sequences remain unsolved.

Encoding Surgical Videos as Latent Spatiotemporal Graphs for Object and Anatomy-Driven Reasoning supplies the multi-horizon temporal edges we reuse, spaced 1, 2, 4 and 8 frames apart, and shows they matter. Removing long-term edges costs 7.2% phase F1 on Cholec80. Its nodes, however, are fixed-scale boxes from a separately trained detector. Its false-positive handling is rule-based graph editing, trained in a separate stage.

EchoGNN: Explainable Ejection Fraction Estimation with Graph Neural Networks shows that a tiny graph model (1.7M parameters) trained only with video-level labels can find the key cardiac phases. Because each frame is one node in a complete $O(T^2)$ graph, it cannot say where in the frame the evidence lies.

Two further works constrain the design. Multiscale Spatio-Temporal Graph Neural Networks for 3D Skeleton-Based Motion Prediction learns pooling over roughly 20 skeletal joints and factorizes space and time. It tells us factorization works, but it never faces the question of which image regions deserve nodes. Preserving Spatial-Temporal Relationship with Adaptive Node Sampling in Hierarchical Dynamic Graph Transformers coarsens dynamic graphs into super-nodes and samples neighbors with a bandit algorithm. It reports that accuracy drops sharply when the super-node count moves away from a tuned optimum of 10. That warning is why we treat the budget $K$ as a swept variable, not a fixed choice.

None of these works chooses, frame by frame, how many nodes a region deserves and at what scale, and then passes messages across scales through time. That combination is the proposal.

Core mechanism

Each frame $t$ passes through a shared convolutional backbone that yields a feature pyramid with levels $l = 1,\dots,L$ (coarse to fine). A lightweight multi-scale attention head, in the style of the parallel-branch spatial/channel gating used in MAFNet, scores every cell $c$ at every level with a split score $s_t(c)$. Node selection starts from the coarsest grid and repeatedly splits the highest-scoring cell into its four children at the next level. It stops when the frame holds $K$ cells. Selected cells tile the frame without overlap, so every pixel belongs to exactly one node. This matters because background is still represented, only coarsely, and nothing is silently dropped. We make the split decisions trainable with a straight-through Gumbel top-$k$ estimator. Each node's feature is its pooled pyramid feature plus a scale-and-position embedding.

Spatial message passing runs within each frame over the $K$ nodes. Temporal message passing runs along sparse edges. Each node at frame $t$ connects to the $k$ nodes with the largest spatial overlap at frames $t\pm h$ for $h \in \{1,2,4,8\}$, whatever their level. The per-clip cost is

$$ C \;=\; O\!\left(T K^2 + T K H k\right), $$

where $T$ is the number of frames, $K$ the node budget per frame, $H=4$ the number of temporal horizons, and $k$ the number of temporal neighbors per horizon. The first term is dense within-frame attention; the second counts the sparse temporal edges. Compared with $O(N^2T^2)$ for a dense grid of $N$ cells, the cost is linear in $T$. This lets us test clips several times longer than dense attention fits in memory.

Research Program

The work has three parts. First, we build the model and verify the memory and speed scaling curve against dense and factorized attention as $T$ grows. Second, we train it under two supervision regimes chosen because they stress different directions. The first regime is EchoNet-Dynamic ejection-fraction regression with only video-level labels, following EchoGNN. Here the left ventricle changes apparent size across the cardiac cycle, and success means sub-frame localization emerges without any spatial labels. The second regime is Critical View of Safety prediction on Endoscapes+ and phase recognition on Cholec80, following Murali et al. Here small anatomical structures (cystic duct, cystic artery) sit next to a large gallbladder, and tools move in depth.

Third, we analyze where the budget goes. We check whether splits concentrate on anatomy and tool tips, how the per-frame depth distribution tracks apparent object size over time, and how sensitive accuracy is to $K$. We add the bounded lesion-size reweighting of Optimizing Operating Points for High Performance Lesion Detection and Segmentation Using Lesion Size Reweighting only where pixel-level loss is used. That paper shows naive inverse-size weighting is unstable, so we do not use it.

Baselines

The naive reference points are the no-graph and single-frame variants. On Endoscapes+, Murali et al. report 67.3% CVS mAP for their single-frame model and 63.8% for a video model without entity graphs. We rerun both with our backbone so that any gain from the node mechanism is not confused with a better feature extractor.

On surgical video, the strongest graph competitor is the latent spatio-temporal graph of Murali et al.. It reports 69.7% CVS mAP on Endoscapes+ and 81.4 phase F1 on Cholec80. Their nodes come from a detector trained with box labels, while ours are detector-free, so the comparison favors them in supervision. We therefore report two versions. One is fully detector-free. In the other, their detected entities are added to our node set as extra nodes. Our method beats Murali et al. if either version exceeds 69.7 mAP at equal backbone and equal training epochs. It is also a useful result if the detector-free version matches 69.7 while using no box labels.

For Cholec80, LoViT, a long-video transformer with sparse attention, reports 91.50±6.10% video accuracy and 74.15% phase Jaccard. We report these metrics too, as the strongest non-graph reference.

On EchoNet-Dynamic the strongest competitor is EchoGNN, at MAE 4.45, $R^2$ 0.76, and F1 0.78 for EF below 40%. Beating it means lower MAE at a comparable parameter count. Localization maps are a bonus that EchoGNN cannot produce.

The most important baseline is an internal one, the dense factorized-attention model. It uses divided space-then-time attention over the full finest grid, which is the MS-STS VIS design without its segmentation decoder, run at whatever $T$ fits in memory. We give it the same backbone, the same hyperparameter search budget (the same number of trials over learning rate and depth), and the same GPU memory cap.

Three ablations isolate the key ingredients. The first spends the same $K$ nodes at one fixed resolution, choosing them by top-$K$ attention. The second grows the quadtree with random or uniform splits. The third restricts temporal edges to same-level nodes only. For each baseline we tune independently and report mean and spread over three seeds.

Why not just…?

Why not just prune tokens at a single resolution with top-$K$ attention? This is the most serious threat. It is simpler, and methods such as ST-SimDiff show that token pruning by similarity and difference already works for long videos. Our claim fails if single-scale top-$K$ at the same budget matches us. The matched-budget ablation settles it directly. We expect the gap to be largest at small $K$. There, a single fine resolution cannot cover large structures, and a single coarse resolution cannot resolve small ones. If the gap vanishes at every $K$, we will report that multi-scale selection is unnecessary.

Why not just run dense factorized spatio-temporal attention over the full grid? At short clip lengths it may well match us. MS-STS VIS reaches 50.1% mask AP on YouTube-VIS 2019 with a ResNet-50 backbone using dense grid attention. Our argument is about the regime where the dense grid no longer fits, since MS-STS's own authors flag long sequences as open. The test is a matched-memory curve of accuracy against clip length. We win only if, at the memory cap, our longer clips beat dense attention's shorter ones. At short lengths, a tie at lower memory is an acceptable result.

Why not just use one node per frame with a stronger backbone, as EchoGNN does? For weakly supervised regression this may be enough for accuracy alone. EchoGNN already reaches MAE 4.45 with 1.7M parameters. It cannot localize, however, and its complete graph grows quadratically in $T$. We compare MAE at matched parameters. We also measure whether our attention maps fall on the ventricle, using held-out frames with left-ventricle outlines where the data provide them. If MAE does not improve and localization is poor, the frame-as-node design wins on simplicity.

Why not just reweight the loss toward small structures? Nichyporuk et al. show that inverse-size weighting destabilizes training. Their bounded reweighting fixes the loss but leaves the representation unchanged. A small structure that pooling has already destroyed cannot be recovered by weighting its gradient. We include their bounded reweighting applied to the single-scale baseline, so any remaining gap is attributable to node allocation.

Decisive checks

Two experiments decide whether the idea holds.

The first is a controlled zoom test. We take held-out Endoscapes+ and EchoNet-Dynamic clips and apply a progressive synthetic zoom (in or out by up to a factor of four across the clip). The full model should degrade much less than the same-level-edges ablation. It should also degrade less than dense attention, whose temporal attention is tied to fixed grid scales. If cross-scale edges give no robustness to zoom, the second half of the claim is false.

The second is a budget sweep of $K$ from 16 to 256 nodes per frame. We plot accuracy, peak memory, and throughput against clip length up to the longest that dense attention can process. The proposal succeeds if two things hold. First, the multi-scale model sits above single-scale top-$K$ across the sweep. Second, its accuracy curve is flatter in $K$ than the sharp optimum that Hierarchical Dynamic Graph Transformers reports for fixed super-node counts. Together these would show that letting attention choose scale per region is what makes a small, cheap node budget sufficient.