SEMIR: Topology-Preserving Graph Minors for Thin-Structure Segmentation

arXiv:2606.24935 · cs.CV · Submitted 2026-06-22 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "SEMIR: Topology-Preserving Graph Minors for Thin-Structure Segmentation".

Jane: The gist The framework replaces pixel-level inference with classification over a compact graph minor,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we're looking at this paper today, "SEMIR: Topology-Preserving Graph Minors for Thin-Structure Segmentation." The big problem they're tackling is segmenting really thin structures like power lines, cracks, or lane markings that are only one to three pixels wide. Standard methods just fail here because they either patch them up or conventional superpixels merge those thin targets into the background before classification.

Jane: That sounds frustrating for anyone working on these kinds of detailed images. So what does this paper propose as a solution? What's the main idea behind SEMIR?

Tom: Well, the thesis is to replace that pixel lattice with something else entirely: a parameterized graph minor. They claim this minor has a contraction map that preserves thin-structure connectivity under a specific criterion, which is key because it keeps those structures connected even when you contract millions of pixels down to a much smaller graph.

Lu: What I find interesting is the mechanism they use for this preservation; they say edge contraction defines a surjective map from the parent graph G to the minor H such that any connected subgraph of G whose edges are all contracted, rather than deleted, maps to a connected subgraph of H <ref:2606.24935#pg2>.

Meng: So if I’m thinking about deployment, what does this mean for the actual model? Does it just make training easier or does it change how we run inference on a real-world feed?

Tom: It changes the inference domain significantly. They say this minor collapses millions of pixels into just tens or hundreds of boundary-aligned supernodes, which means you get full-resolution results without having to patch anything up at scales demonstrated up to twenty-one MP in this paper <ref:2606.24935#pg1,at scales demonstrated up to 21 MP in this paper>.

Jane: That sounds like a huge reduction in computational load for the classification part. But how do we actually know this graph minor is doing what it claims for these thin structures?

Lu: They set the minor parameters—those contraction, deletion, and retention rules—via few-shot boundary-alignment optimization on just five to twenty labeled images. Then they use a lightweight Graph Neural Network to classify that reduced graph.

Lalam: And then they use an exact lifting map to take those node-level predictions and lift them back up to the original pixel resolution without any interpolation <ref:2606.24935#pg2>. That sounds like a very clean pipeline for segmentation.

Paper summary: Meng: It sounds clean on paper, but I’m worried about the setup. How much tuning is actually required before we can even think about putting this on a production server?

Tom: They found that one pipeline—identical architecture, features, loss, and Graph Neural Network hyperparameters across all datasets—matches or exceeds domain-specific baselines on TTPLA for power lines, CrackSeg9k for pavement cracks, and SkyScapes Lane for aerial markings.

Jane: That’s a strong claim since they used the same setup everywhere. What kind of improvement are we actually talking about when they say it reduces mask fragmentation by at least four point six times relative to SLIC at matched inference?

Lu: The controlled ablation study is important here because they replaced the minor with SLIC superpixels at a matched region count and confirmed that the topological advantage originates in the representation, not in the region-level inference alone <ref:2606.24935#pg3>.

Lalam: So they are showing that simply having a better classifier on smaller regions isn't enough; you have to change how you group those regions from the start <ref:2606.24935#pg1>.

Tom: The results are pretty compelling. On TTPLA, SEMIR achieves.eight hundred ninety-four Dice and.eight hundred eight IoU, surpassing PL-UNet at.eight hundred eighty-nine/.eight hundred which was the previous best published result <ref:2606.24935#pg2>.

Jane: And on CrackSeg9k, they hit.nine hundred eleven Dice and.eight hundred thirty-seven IoU, beating BBCNet at.nine hundred nine/.eight hundred thirty-three and CrackScopeNet at.eight hundred ninety-three/.eight hundred twenty-two <ref:2606.24935#pg2>. The numbers are high for thin structures.

Meng: I have to ask, what about the cost of running this? If we're classifying a reduced graph instead of millions of pixels, does that translate into a significant reduction in inference time on our actual hardware?

Tom: The GINE network performs node classification on H using supernode and edge features. The resulting pipeline is very lightweight when it comes to the classification stage itself <ref:2606.24935#pg1>.

Lu: They describe the features for a supernode as area, mean intensity, per-channel standard deviation, boundary length, compactness, elongation, and dominant axis <ref:2606.24935#pg2>. The edge features encode scale-invariant log-ratios of scalar node features relative displacement and orientation difference between dominant axes <ref:2606.24935#pg1>.

Jane: So the model isn't just looking at intensity anymore, it’s looking at the shape and orientation of those small segments—the elongation and dominant axis—which is what helps it understand that thinness <ref:2606.24935#pg2>.

Paper summary: Lalam: The exact lifting map is crucial because it recovers those predictions to pixel resolution without any interpolation, which keeps the final output sharp <ref:2606.24935#pg1>. That’s a key detail for us.

Meng: It sounds like a lot of complexity is packed into that graph construction and parameterization, but if this works on those benchmarks, it suggests that for very fine details, the representation matters more than just throwing a bigger neural network at the problem <ref:2606.24935#pg3>.

Tom: The paper is clearly focused on proving that changing the representation—the graph minor—is where you get the most gain, rather than just tweaking the classifier for a standard pixel grid <ref:2606.24935#pg1>.

Jane: So to wrap up this part of "SEMIR: Topology-Preserving Graph Minors for Thin-Structure Segmentation," it’s about using graph theory to keep thin structures connected during segmentation, and they achieved strong results across power lines, cracks, and lane markings.

Lu: It suggests that if you are working on any application where things are very thin—whether it's infrastructure or medical scans—moving away from a simple pixel grid representation toward something topologically aware could be a major step forward <ref:2606.24935#pg3>.

Meng: For production, the main hurdle will be getting that minor construction robust enough for novel data, but the efficiency gain from reducing millions of pixels to hundreds of nodes is certainly attractive if it holds up in testing <ref:2606.24935#pg1>.

Tom: So we’ve seen how they build this parameterized graph minor and how a lightweight GNN classifies it, and the results are solid across those three different thin-structure tasks.

Jane: For someone just listening, the core idea is that instead of looking at every single pixel individually, you create a smart map of connected regions first, and then classify those regions to get an accurate picture of things that are only a few pixels wide.

Lu: The implication for the wider field is that we need representations that respect the underlying geometry of the structures we are studying <ref:2606.24935#pg3>.

Meng: We'll keep watching to see if this minor construction holds up when we try to deploy it on our specific, messy data streams, but these initial numbers are very encouraging for what's possible with graph-based reasoning <ref:2606.24935#pg1>.

Tom: That’s all the time we have for this paper on SEMIR: Topology-Preserving Graph Minors for Thin-Structure Segmentation.

Conclusion: Tom: So we’re wrapping up on SEMIR, the paper about Topology-Preserving Graph Minors for Thin-Structure Segmentation. Basically, they took a problem where standard methods just fail on things like power lines or cracks—structures that are only one to three pixels wide—and they replaced the pixel grid with a graph minor.

Jane: That’s right. They used this graph minor to shrink millions of pixels down to just tens or hundreds of boundary-aligned regions while keeping the actual connected structure intact during classification. It sounds like they solved a connectivity problem that standard superpixels completely missed.

Lu: What I find interesting is how they parameterized those contractions and deletions—they set parameters using few-shot optimization on about ten images, and then a Graph Neural Network classifies that smaller graph, which you lift back up to the original pixel resolution. That’s a clean way to do it.

Meng: But for me at the production level, the main thing is that this approach focuses on how you structure your data representation first. They found one pipeline worked across three totally different datasets—power lines, pavement cracks, and aerial markings—without changing anything specific to each one. That’s pretty impressive consistency.

Lalam: I agree with Meng; the fact that the same architecture and hyperparameters performed well across those domains suggests the graph minor method is a really solid representation learning technique for this kind of structure segmentation.

Tom: Exactly, Lalam. The authors are proving that you don't need to train a whole new model for every single type of thin structure; you just need a clever way to shrink the problem down and classify those smaller nodes.

Jane: So what does this mean for the people who actually use these segmentation models? It means they can get much sharper, more accurate results on fine details than before, even when dealing with very narrow features.

Lu: It changes how we think about the representation layer in deep learning for these tasks; it shows that graph theory isn't just a theoretical concept but a practical tool to preserve topology during feature extraction.

Meng: I’m still thinking about the real-world deployment cost, though. If you’re running this on massive satellite imagery, you want to know that collapsing millions of pixels into hundreds of nodes actually makes inference faster, not just more complex setup work.

Tom: The paper shows they do reduce the inference domain drastically—from millions of pixels down to that smaller graph—which is the main win for speed and efficiency at scale.

Jane: So, SEMIR moves us away from patching things up or merging them into noise, toward a method that respects the geometry of thin objects from the very start. Next time we talk about representation learning, we'll look at how these graph-based ideas show up in medical imaging.

University of Missouri-Kansas City

cs.CV

Submitted: 2026-06-22

Updated: 2026-10-14

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 87/100

The gist: The gist The framework replaces pixel-level inference with classification over a compact graph minor, which reduces inference domain from millions of pixels to tens or hundreds of boundary-aligned

Key concepts

Graph Minor: A graph minor is a simplified version of a larger graph created by repeatedly performing operations like edge contraction, node deletion, and edge deletion. SEMIR uses this to reduce the massive pixel grid into a much smaller graph where important structural information is retained.
Edge Contraction: This operation merges two adjacent nodes (pixels) in the original grid into a single new node in the minor graph. In SEMIR, this merging is guided by intensity similarity; pixels with similar colors or intensities are merged if they meet a specific criterion, effectively grouping them into larger structural elements.
Topology-Aware Loss: These are loss functions designed to penalize breaks in the connectivity of thin structures during the segmentation process. While standard methods fail because they destroy continuity, topology-aware losses encourage the model to maintain connected components even when simplifying the representation.

Terminology

Benchmark — 15× in this paper · explained in 2 episodes
Ablation — 8× in this paper · explained in 1 episode
Decoder — 6× in this paper · explained in 2 episodes
Hyperparameters — 6× in this paper · explained in 2 episodes
Transformer — 6× in this paper · explained in 2 episodes
Loss Function — 4× in this paper · explained in 2 episodes
Representation Learning — 4× in this paper · explained in 2 episodes
Semantic Segmentation — 4× in this paper · explained in 2 episodes
European Conference on Computer Vision — 3× in this paper
Graph Construction — 3× in this paper · explained in 3 episodes
International Conference on Machine Learning — 3× in this paper
Ablation Study — 2× in this paper · explained in 3 episodes
Adam — 2× in this paper · explained in 2 episodes
Clustering — 2× in this paper · explained in 2 episodes
Conference on Computer Vision and Pattern Recognition — 2× in this paper
Consistency — 2× in this paper · explained in 3 episodes
Fidelity — 2× in this paper · explained in 2 episodes
Active Learning — 1× in this paper · explained in 6 episodes
CVF International Conference on Computer Vision — 1× in this paper
Coherence — 1× in this paper · explained in 2 episodes
Core — 1× in this paper · explained in 2 episodes
Decode — 1× in this paper · explained in 2 episodes
Diffusion Model — 1× in this paper · explained in 9 episodes
Distillation — 1× in this paper · explained in 2 episodes
Feature Extraction — 1× in this paper · explained in 3 episodes
Gradient Flow — 1× in this paper · explained in 2 episodes
Parameterization — 1× in this paper · explained in 2 episodes
Persistent Homology — 1× in this paper · explained in 4 episodes
Semantic Understanding — 1× in this paper · explained in 2 episodes
Spectral clustering — 1× in this paper · explained in 2 episodes
Transformers — 1× in this paper · explained in 2 episodes

Summary

The gist The framework replaces pixel-level inference with classification over a compact graph minor, which reduces inference domain from millions of pixels to tens or hundreds of boundary-aligned regions while preserving connected-component topology of thin foreground structures<ref:2606.24935#pg2>

How it works

SEMIR constructs a parameterized graph minor from the pixel lattice via edge contraction, node deletion, and edge deletion, replacing the grid with a compact, boundary-aligned graph on which a GNN performs node-level classification<ref:2606.24935#pg5> The critical property is graph-theoretic: edge contraction defines a surjective map from the parent graph G to the minor H such that any connected subgraph of G whose edges are all contracted—rather than deleted—maps to a connected subgraph of H<ref:2606.24935#pg2> For thin structures, this means any foreground region whose pixels are intensity-homogeneous under ψ is preserved as a connected supernode chain in H regardless of width or orientation<ref:2606.24935#pg2> Minor parameters are set via few-shot boundary-alignment optimization on 5–20 labeled images; a GINE classifier operates on the reduced graph; and an exact lifting map recovers pixel-level predictions without interpolation<ref:2606.24935#pg2>

Methodology

The pipeline comprises four stages: (i) construction of a pixel-adjacency graph G from I; (ii) derivation of a graph minor H ⪯ G via parameterized edge contraction, node deletion, and edge deletion; (iii) node-level classification on H by a graph neural network; and (iv) exact lifting of supernode predictions to pixel resolution<ref:2606.24935#pg2>

Pixel Graph Construction: The image I is encoded as an 8-connected grid graph G = (V (G), E(G)) with one node per pixel and edges between all horizontally, vertically, and diagonally<ref:2606.24935#pg2> Rather than maintaining explicit coordinate lists or adjacency structures for G—which would require O(V (G) + E(G)) storage, roughly 9HW entries for an 8-connected grid—we represent the graph via an expanded binary tensor T in (2H−1)×(2W−1) that interleaves node and edge states<ref:2606.24935#pg2> This representation costs (2H−1)(2W−1) bits, a fraction of the memory required by a sparse adjacency list, while encoding the full graph topology in a structure that supports O(E(G) − E(H)) flood-fill construction of the minor via simple array writes<ref:2606.24935#pg2>
Graph Minor Construction: A graph minor H ⪯ G is obtained from G by a sequence of edge contractions, node deletions, and edge deletions [10, 24]<ref:2606.24935#pg2> SEMIR parameterizes these operations by a compact parameter set Θ = ψ, α, β and executes them in a fixed order during a coprime traversal of V (G)<ref:2606.24935#pg2> The order in which pixels are visited during contraction affects the resulting minor: a raster-scan traversal preferentially merges rightward and downward, producing elongated supernodes aligned with the scan direction<ref:2606.24935#pg2> Connectivity guarantee: Edge contraction defines a surjective homomorphism ϕ: G → H such that for any connected subgraph S ⊆ G whose edges are all contracted (rather than deleted), ϕ(S) is a connected subgraph of H [10, 24]<ref:2606.24935#pg2> Edge contraction: Two adjacent supernodes vi, vk ∈ V (H) are merged if their canonical intensity vectors satisfy I vi - I vkn ≤ ψ (3)<ref:2606.24935#pg2> Node deletion: Supernodes violating retention criteria are removed: V del:= v ∈ V(H): a v βmax or I v not in [mmin, mmax]<ref:2606.24935#pg2> Edge deletion: Edges across strong intensity gradients are severed: E del:= (vi, vj) ∈ E(H): I vi - I vjn > α (5)<ref:2606.24935#pg2>

Optimization and Classification

Minor parameters Θ = ψ, α, β are set once per dataset through few-shot black-box optimization on 5–20 labeled images<ref:2606.24935#pg2> A GINE network performs node classification on H using supernode and edge features<ref:2606.24935#pg2> Each supernode u ∈ V (H) aggregates statistics including area au, mean intensity ¯Iu, per-channel standard deviation σu, boundary length bu, compactness cu, elongation eu, and dominant axis du<ref:2606.24935#pg2> Edge features for (u, v) ∈ E(H) encode scale-invariant log-ratios of scalar node features relative displacement and orientation difference between dominant axes<ref:2606.24935#pg2> A three-layer GINE network with relational edge features performs node classification on H, producing supernode predictions YˆH ∈ 0, · · ·, k V (H)<ref:2606.24935#pg2> The final pixel-level segmentation is obtained by lifting: hat Y(j,k) = hat Y H(u) for all (j,k) ∈ P u<ref:2606.24935#pg2>

Evaluation and Results

SEMIR was evaluated on three benchmarks spanning distinct thin-structure domains: TTPLA [1] (power lines), CrackSeg9k [17] (pavement cracks), and SkyScapes Lane (aerial markings)<ref:2606.24935#pg2> The largest standard deviation across all reported metrics was ±.008; per-run breakdowns are provided in the supplementary material but omitted here for space<ref:2606.24935#pg2> On TTPLA, SEMIR achieves.894 Dice and.808 IoU, surpassing PL-UNet (.889/.800), the previous best published result<ref:2606.24935#pg2> On CrackSeg9k, SEMIR attains.911 Dice and.837 IoU, exceeding BBCNet (.909/.833) and CrackScopeNet (.893/.822)<ref:2606.24935#pg2> Across all four benchmarks, SEMIR achieves the best or second-best result using an identical pipeline—same GINE architecture, same few-shot SMBO tuning, same feature set—with no dataset-specific modifications<ref:2606.24935#pg2> The controlled ablation against SLIC confirms that these gains originate in the representation, not in region-level inference alone<ref:2606.24935#pg2> The minor achieves a component fragmentation of 5.1, meaning its predictions differ from the ground truth by roughly five connected components per image on average<ref:2606.24935#pg2>

Limitations and Future Work

SEMIR’s region-level representation trades spatial context breadth for boundary precision; on tasks dominated by large-area classes, such as SkyScapes Dense, pixel-level encoders that aggregate features over wide receptive fields retain an advantage<ref:2606.24935#pg2> The minor contraction process also introduces a dependency on the quality of the initial oversegmentation: if early contraction steps merge a thin structure with its background, no downstream classification can recover it<ref:2606.24935#pg2> Finally, the current framework treats topology preservation purely at the representation level; combining the minor with loss functions that explicitly penalise topological errors—such as clDice [27] or skeleton-recall loss—could yield complementary gains<ref:2606.24935#pg2> The authors leave this combination, along with extension to 3D volumetric structures, as future work<ref:2606.24935#pg2>

Conclusion

SEMIR presents a segmentation framework that replaces pixel-level inference with classification over a compact graph minor<ref:2606.24935#pg2> By contracting homogeneous image regions into supernodes whose boundaries align with structural edges, SEMIR reduces the inference domain from millions of pixels to tens or hundreds of boundary-aligned regions while preserving the connected-component topology of thin foreground structures<ref:2606.24935#pg2> A lightweight GINE classifier on the resulting region-adjacency graph, tuned via few-shot optimization on as few as ten images, achieves state-of-the-art results on TTPLA, CrackSeg9k, and SkyScapes Lane using an identical pipeline with no dataset-specific modifications to the GNN model<ref:2606.

Improvements for AI systems

Improved AI system can perform full-resolution inference on thin structures up to 21 MP scale without patching, as noted in the abstract, by replacing pixel-level inference with classification over a compact graph minor.
The system can achieve superior topological accuracy by utilizing a parameterized graph minor whose contraction map preserves thin-structure connectivity under the contraction criterion, which is independent of task-specific losses.
The system can be deployed across diverse domains (power lines, cracks, lane markings) using a single pipeline—identical architecture, features, loss, and GNN hyperparameters across all datasets without modification.
The system can utilize a lightweight GINE classifier that operates on the reduced graph to classify supernodes, followed by an exact lifting map to recover pixel-level predictions without interpolation.
The system can be optimized for the specific thin structure by setting minor parameters via few-shot boundary-alignment optimization on 5–20 labeled images, effectively finding parameters that define a family of boundary-aligned partitions adapted to the target structure.