Disco: Densely-overlapping Cell Instance Segmentation via Adjacency-aware Collaborative Coloring
Authors: Rui Sun
Yiwen Yang
Kaiyu Guo
Chen Jiang
Dongli Xu
Zhaonan Liu
Tan Pan
LIMEI HAN
Xue Jiang
Wu Wei
Yuan Cheng
Venue: ICLR 2026 Poster (2026)
Keywords: Cell Instance Segmentation
Digital Pathology
Graph Coloring
Topological Analysis
Conflict Resolution
Primary area: applications to physical sciences (physics, chemistry, biology, etc.)

Abstract: Accurate cell instance segmentation is foundational for digital pathology analysis. Existing methods based on contour detection and distance mapping still face significant challenges in processing complex and dense cellular regions. Graph coloring-based methods provide a new paradigm for this task, yet the effectiveness of this paradigm in real-world scenarios with dense overlaps and complex topologies has not been verified. Addressing this issue, we release a large-scale dataset GBC-FS 2025, which contains highly complex and dense sub-cellular nuclear arrangements. We conduct the first systematic analysis of the chromatic properties of cell adjacency graphs across four diverse datasets and reveal an important discovery: most real-world cell graphs are non-bipartite, with a high prevalence of odd-length cycles (predominantly triangles). This makes simple 2-coloring theory insufficient for handling complex tissues, while higher-chromaticity models would cause representational redundancy and optimization difficulties. Building on this observation of complex real-world contexts, we propose Disco (Densely-overlapping Cell Instance Segmentation via Adjacency-aware Collaborative Coloring), an adjacency-aware framework based on the “divide and conquer” principle. It uniquely combines a data-driven topological labeling strategy with a constrained deep learning system to resolve complex adjacency conflicts. First, “Explicit Marking” strategy transforms the topological challenge into a learnable classification task by recursively decomposing the cell graph and isolating a “conflict set.” Second, “Implicit Disambiguation” mechanism resolves ambiguities in conflict regions by enforcing feature dissimilarity between different instances, enabling the model to learn separable feature representations. Disco achieves a significant 7.08\% improvement in the PQ metric on the GBC-FS 2025 dataset and an average improvement of 2.72% across all datasets. Furthermore, the predicted “Conflict Map” serves as a novel tool for interpreting topological complexity, offering new potential for data-driven pathology research.

Published as a conference paper at ICLR 2026
DISCO DENSELY-OVERLAPPING CELL INSTANCE SEGMENTATION VIA ADJACENCY-AWARE COLLABO-
RATIVE COLORING
Rui Sun 12.3z Yiwen Yangl.1,5, Kaiyu Guo', Chen Jiang 1.2 Dongli Xu Zhaonan Liu?,
Tan Pan Limei Han 1.2 Xue Jiang", Wu WeiSi, Yuan Cheng
1 Shanghai Academy of Artificial Intelligence for Science, FFudan University
Shanngaii Innovation Institute, "School of Life Sciences and Biotechnology. Shanghai Jiao Tong University 5 Lingangg Laboratory, Renji Hospital, School of Medicine, Shanghai Jiao Tong University
ABSTRACT
Accurate cell instance segmentation is foundational for digital pathology analy- sis. Existing methods based on contour detection and distance mapping still face significant challenges in processing complex and dense cellular regions. Graph coloring-basedd methods provide new paradigm for this task, yet the effectiveness of this paradigm in real-world scenarios with dense overlaps and complex topolo- gies has not been verified. Addressing this issue, we release targe-scale dataset GBC-FS 2025, which contains highly complex and dense sub-cellular nuclear rangements. We conduct the first systematic analysis of the chromatic properties of cell adjacency graphs across four diverse datasets and reveal an important dis- covery: most real-world cell graphs are non-bipartite with a high prevalence of odd-length cycles (predominantly triangles). This makes simple 2-coloring the- ory insufficient for handling complex tissues, while higher- sathher-hromaticity models would cause representational redundancy and optimization difficulties. Building on this observation of complex real-world contexts, we propose Disco (Densely- overlapping Cell Instance Segmentation via Adjacency-aware COIlaborative Col- oring), adjacency-aware framework based on the "divide and conquer" prin- ciple. uniquely combines a data-driven topological labeling strategy with a constrained deep learning system to resolve complex adjacency conflicts. First, "Explicit Marking" strategy transforms the topological challenge into learnable classification task by recursively decomposing the cell graph and isolating "con- flict set." Second, "Implicit Disambiguation" mechanism resolves ambiguities conflict regions by enforcing feature dissimilarity between different instances, en- abling the model to learn separable feature representations. Disco achieves a sig- nificant 7.08% improvement the PQ metric on the GBC-FS 2025 dataset and an average improvement of 2.72% across all datasets. Furthermore, the predicted "Conflict Map" serves as a novel tool for interpreting topological complexity, offering new potential for data-driven pathology research. The code is publicly available https://githubccom//800000//1::
INTRODUCTION
Accurate cell instance segmentation has long been foundational task for cell counting, morpho- logical analysis, spatial histology studies, and even cancer grading Zhang al, (2025a) Zhang al. (2025b). However, due to the intrinsic complexity of biological tissues, cells often exhibit highly dense, severely overlapping, and morphologically diverse characteristics, making the precise dis- ambiguation of each individual instance while maintaining high accuracy formidable challenge. Although mainstream methods based on detection [Ting et al. (2023), contour prediction Chen al.
"These authors contributed equally
1 Corresponning authors: jiangchen sais.org.en, wuwei Luwei@lglah.ac.cn. cheng yuan @ www.afccc..co

---

Published as a conference paper at ICLR 2026
Pridatan
Port
Weth Macked
CaColronkund Mirtee
Ollee Strtee
Figure 1. Visual comparison of mainstream instance segmentation paradigms with our proposed Disco framework. (a) Detection- based methods are constrained by coarse bounding box representa- tions and heuristic non non-maxima suppression (NMS). (b) Contour-based methods are highly sensitive to binarization thresholds. (c) Distance- based methods rely on complex post-pnn poosepronsssing for instance reconstruction. (d) Disco framework reformulates the problem by directly modeling the cell adja- cency graph, ultimately reconstructing instances through topological decoding.
2016), and distance/direction maps He et al. 202 have made significant progress in specific sce- narios, they share a common reliance on local pixelwise or geometric information to infer instance affiliation. As illustrated in Figure 1 (a-c), this strategy reveals its inherent fragility when process- ing complex cell clusters. The common bottleneck of these approaches is their lack of an intrinsic mechanism to explicitly model the global topological constraints among cells, thus their decisions are inherently locally optimal and prone to systematic errors in complex cell clusters.
To overcome these limitations, methods based graph coloring theory [Fritsch al. (1998) have recently emerged, offering a new paradigm with global topological awareness. Among these, 2- coloring, based on bipartite graph theory |sratian et al. (1998), represents the most concise and efficient model. Concurrently, the pioneering work of FCIS Zhang et al.] (2025c) demonstrated the potential of universal 4-coloring model. However, the validity of its core bipartite assump- tion on geal-world cellular topologies has remained a critical and unverified gap. To rigorously investigate this issue, we make two foundational contributions. First, we introduce GBC-FS 2025 (Gallbladder Cancer Frozen Section 2025 Dataset), a new large-scale stress-test dataset compris- ing 2,839 frozen section images of gallbladder cancer with 864,204 annotated sub-cellular nuclei, which exhibits highly complex and dense sub cellular structures. Second, utilizing this dataset and three other public benchmarks, we conduct the first systematic analysis of the chromatic properties of cell adjacency graphs. As shown in Table 1, our analysis reveals striking discovery: real- world cell graphs are fundamentally non-bipartite, characterized by a high prevalence of odd-length cycles (predominantly 3-cycles). This finding suggests that any simple model relying on the ideal bipartite graph assumption may face fundamental limitations when processing complex histopathology im- ages. These findings call for fundamentally new approach that can elegantly handle both bipartite and non- non-bipartite structures.
Table 1: A Cross-Dataset Comparison of Key Topological Properties.
Proportion of Cells Proportion of 3-Cycles
Bipartite
Conflict Node Secondary Conflict
Dataset
with < 3 Neighbors
among Odd Cycles
Node Ratio
Ratio
Node Ratio
PanNuke
100.00%
0.00%
100.00%
0.00%
0.00%
DSB2018
99.66%
97.94%
98.01% %
1.99%
1.84%
CryoNuSeg
99.11%
98.12%
94.36%
5.64%
4.82%
GBC-FS 2025
88.09%
90.51%
69.51% %
30.49%
24.64%
Facing this severe and underestimated challenge, we propose Disco -Densely-overlappingg Cell Instance Segmentation via Adjacency-aware COllaborative Coloring), a conflict-aware and dy- namic 2-coloring framework. Disco is a new method that fundamentally rethinks cell instance segmentation through advanced graph-theoretic coloring. We do not resort to a more general high- chromaticity model, as this would be an unnecessary redundancy for the simple bipartite structures that still dominate the graph. Instead, we propose more refined "divide and conquer" strategy. The core of the Disco framework is comprised of two innovative mechanisms: "Explicit Marking," which transforms topological conflicts into a learnable classification target, and "Implicit Disambiguation," which resolves the intrinsic ambiguities of discrete labels in the continuous feature space. In sum- mary, the contributions of this paper are four-fold:
2

---

Published as a conference paper at ICLR 2026
Groundbreaking Topological Analysis: We conduct the first systematic, quantitative analysis of the chromatic properties of real-world cell adjacency graphs, disruptively revealing their funda- fh mentally non-bipartite nature characterized by dense "conflict clusters." This finding provides foatiiccloouuuttti critical, data-driven theoretical foundation for applying graph coloring paradigms to cell seg- mentation.
A Novel Disco Framework: Based these findings. we propose Disco, conflict-wware frame- work operating on a "divide and conquer" principle. uniquely synergizes two core mecha- nisms: "Explicit Marking," which transforms topological conflicts into a structured, learnable target, and "Implicit Disambiguation; which resolves discrete label ambiguities in the continu- ous feature space via an end-to-end adjacency constraint.
A High High-density Case Study Dataset: We introduce GBC-FS 2025, which contains over 850,000 annotated instances of sub-cellular nuclei data. With its unprecedented cell density and extreme topological complexity. including conffict node ratio exceeding 30%, it provides indispens- able "strexs-test" platform for the development of robust segmentation algorithms.
SOTA Performance and a New Interpretability Paradigm: Disco achieves state-of-the-ar (SOTA) performance across four heterogeneous datasets, with remarkable 7.08% PQ improve- ment on GBC-FS 2025. Furthermore, we pioneer the use of the predicted "Conffict Map" as a novel topological quantification tool, opening new avenues for data-driven pathology research.
FROM LOCAL CUES TO GLOBAL TOPOLOGY
The evolution of cell instance segmentation methods can be understood paradigm shift from approaches reliant on local geometric information to those that embrace global topological structures Chen al. (2024) Petukhov et al. (2022). To provide a comprehensive understanding of existing methods, we conduct a summary analysis herein. At the same time, the Appendix A.2 provides a more extensive review of related works.
2.1 BOTTLENECKS OF LOCAL CUES
Mainstream instance segmentation paradigms Wang et al. (2025), while diverse in their techni- cal implementations, are fundamentally united by their reliance on local, pixel-wise or geometric to infer instance affiliation. Detection retection-based methods, epitomized by Mask R-CNN He et al. (2017), operate on coarse geometric bounding boxes. Their final performance is often dictated by the heuristic nature of non-maxima suppression (NMS) Ren al. (211)), which frequently leads to missed instances in crowded scenes with irregular morphologies or high degrees of overlap (Figure (()).. Contour-based methods Xu al. (2024) are highly sensitive the binarization threshold, often resulting in instance merging
at low thresholds and fragmentation (over- segmentation) high thresholds (Figure 1(b)). Distance/direction based methods, such as StarDist Schmidt et al. (2018) and Hover-Net Graham et al. (2019), attempt to mitigate these issues by learn- ing richer representations, but they in turn depend on complex and error-prone post-processing gorithms to reconstruct instances from the predicted vector fields, making them susceptible to error propagation that can cause erroneous instance splitting (Figure (c)).. The common bottleneck of these methods is their lack of an intrinsic mechanism to comprehend the global topological structure among cells. Their decisions are, by design, locally optimal, which inevitably leads to systematic failures when faced with the global complexity of dense tissues.
2.2 PROMISE OF GLOOBAL TOPOLOGY
To overcome this fundamental limitation, a new perspective that abstracts the instance segmentation problem into graph coloring task has emerged al. (202),, thereby explicitly modeling these global topological constraints. The most concise instantiation within this paradigm is 2-coloring Zhao et al. (2025), based on the elegant theory bipartite graphs. This model is theoretically sufficient for any graph that contains no odd-length cycles. This raises critical, yet unexamined, question: to what extent do real-world cell graphs adhere to this ideal bipartite structure? Concur- rently, the pioneering work of FCIS Zhang al. (202cch demonstrated the potential of universal 4-coloring model based on the Four-Color Theorem. However, this approach risks introducing un- necessary representational redundancy and potential optimization difficulties when the underlying
3

---

Published as a conference paper at ICLR 2026
Confliet Nodes
Adjacnnc Edges
Hipartile Graph
Nea-bipartite
Secondary Confliets Groph
Figure 2. Fundamental topological structures in cell adjacency graphs. (a) Simple, 2-colorable bipartite structures. (b) Non-bipartite structures containing odd-length cycles (e.g.. 3-cycles), which induce coloring conflicts. (c) A complex "conflict cluster" formed by interconnected odd cycles, leading to secondary conflicts between adjacent conflict nodes.
topology is simpler. This presents a "Goldilocks challenge" Hulubei et al. (2003): that of finding coloring model that is neither too simple nor too complex. These considerations necessitate sys- tematic topologiaal analysis to uncover the true nature of cellular graphs, which turn motivates quest for optimally balanced, dynamically adaptive approach.
3 CROSS-DATASET TOPOLOGICAL ANALYSIS
A principled solution necessitates a profound understanding of the problem's intrinsic structure. While graph-based paradigms offer a promising new perspective for instance segmentation, the topo- logical properties of the resulting cell adjacency graphs have remained largely unexplored domain Liu et al. (2022). To this critical gap, we conduct a systematic, quantitative analysis across four datasets of significant heterogeneity to empirically characterize the topological landscape of real- world cellular tissues. This analysis not only provides a solid foundation for our proposed Disco framework but also constitutes one of our scientific contributions.
3.1 GRAPH FORMULATION AND TOPOLOGICAL PRELIMINARIES
We formally model the spatial arrangement of cells as a Cell Adjacency Graph (CAG) Trémeau & Colantoni 2000).
Definition 1. Cell Adjacency Graph, CAG: Given an instance mask / E 7 H comprising a set of instances S {81;-.., 8N its corresponding CAG is undirected graph G (V, F).. where the vertex set V = U1,... UN is in bijective correspondence with S and the edge set is defined as 3 + 0. Aere, denotes the pixel set of instance after a morphological dilation with a x 3 kernel, definition that captures all 8-connected adjacencies.
E (v,, vÿ) 8;, 8j S,i +f j, and (s;)) Naj
The feasibility of resolving instance disambiguation via graph coloring is fundamentally tied to the graph's chromatic number (G), for which bipartiteness is key concept.
Theorem 1. Bipartite Graph Theorem Csóka et al. 2016): A graph G' is 2-colorable (i.e., x(G) S 2) if and only if is bipartite, which is equivalent stating that G contains no odd-length cycles.
This theorem establishes direct link between graph's 's structure- theeereeeeeeeeeeee presence of odd cycles and the minimum number of colors required resolve all adjacency constraints. As illustrated in Figure 2, cellular arrangements can form both simple, 2-colorable bipartite structures and more complex, non-bipartite structures containing odd cycles. The presence single odd cycle necessitates at least three colors, thereby creating coloring conflict for any 2-coloring scheme. In dense tissues, multiple odd cycles may share vertices, forming conflict clusters. In such cases, multiple conflict- inducing nodes themselves be adjacent, situation term secondary conflicts. We now proceed to quantitatively investigate the prevalence of these structures real- real-world data.
3.2 EMPIRICAL ANALYSIS GRAPH PROPERTIES
We analyzed the CAGs derived from four datasets with varying complexities, and the comprehensive results summarized in Figure 3. Our analysis focuses on two key aspects: local connectivity and global topology.
4

---

Published as a conference paper at ICLR 2026
ERA2E1R Bereet
(ot Conpuraaiov Aralyckk Ned Begie Die Berien Acnos Buttoss
Figure 3. A Cross-dataset comparative analysis of cell adjacency graph topologies. (a) Node Degree Distributions: Local connectivity varies significantly, from the highly sparse PanNuke to the densely clustered GBC-FS 2025, (b) Odd-Length Cycle Distributions: The prevalence of 3-cycles confirms that most real-world cell graphs are non-bipane bon-bipartite, with complexity peaking in the GBC-FS 2025 dataset. The y-axis is on logarithmic scale.
Local Connectivity:
The node degree, i.e., the number of its neighbors Chen Su (2023), reflects the local crowdedness of cell. Figure 3(a) illustrates the node degree distributions for each dataset. Although the low average node degrees suggest overall graph sparsity, the long-tailed distributions and the presence of nodes with a maximum degree of up to 8 indicate the existence of highly dense local neighborhoods. As detailed Table 1, in simpler datasets like DSB2018 and CryoNuSeg, over 99% of cells have three fewer neighbors. In more complex in-house GBC-FS 2025 dataset, however, this proportion drops to 88.09%, confirming a significant increase local connectivity.
Global Topology and Von-Bipartiteness: Our most striking finding stems from the analysis of odd cycles. We found that, with the exception of the extremely sparse and entirely bipartite PanNuke dataset, non-bipartite graphs are prevalent feature. Non-bipartite graphs constitute 56.67% of the images in CryoNuSeg and 29.1 19% in GBC-FS 2025. Figure 3(b) displays the length distribution of these odd cycles, revealing strikingly consistent pattern: across all non-bipartite datasets, 3-cycles (triangles) overwhelmingly account for over 90% of all odd cycles. This provides strong, direct evidence for the argument that local structures formed by the direct contact of three more cells are the primary drivers of topological complexity Vazquez et al. (2004).
3.3 THE PERVASIVENESS OF COLORING CONFLICTS
The high prevalence of odd cycles Nikiforov 2008 directly implies that simple 2-coloring models are infeasible. To quantify this, we introduce the concept of conflict nodes.
Definition 2. Conflict Nodes and Conflict Set: For graph G, its conflict set Veen f minimum Veonf]. vertex set such that the subgraph induced by its removal G[V\Voon is bipartite. The nodes in Vomf are termed conflict nodes. The Conflict Node Ratio given by |Voonsl/VV].
As shown in our feasibility analysis in Table 1, this ratio varies dramatically across datasets, from 0% in PanNuke to staggering 30.49% in GBC-FS 2025. This indicates that in complex tissues, nearly a third of all cells are involved in topological conflicts and cannot be resolved by 2-coloring scheme. Furthermore, our analysis reveals deeper shallenge-secondaryy conflicts.
In graph G = (V, E), given its conflict set Vemy, secondary conflict is an edge (u, v) E E such that u E Vconf and v E Veonf.
Definition 3. Secondary Conflict:
Our secondary conflict analysis reveals that these conflict nodes not isolated. Secondary conflicts exist in all datasets that contain non-bipartite graphs. In the challenging GBC-FS 2025 dataset, the secondary conflict node ratio reaches 24.64%.
These quantitative results lead to an unequivocal conclusion: real-world cell adjacency graphs, par- ticularly those from dense histopathology images, fundamentally non-bipartite and are character- ized by dense clusters of interconnected odd cycles. Further details regarding the dataset's 's analytical results and additional visualizations provided in the Appendix A.3
5

---

Published as a conference paper at ICLR 2026
Implict
He lagegedd hargyeed
Teprigged
color
Inetacee Ourpatt
Inpert
Inseace Fasture
Interation
Extraction
Adjencincy Emrning
plice
Flprrtt Buclber Colerieg Coefle Heepe
Tiis Groend Truit
Miic
Expilit Marking
Figure 4. An overview of the training framework for our proposed Disco method. This framework synergistically integrates (1) data-driven topological analysis, which generates Disco ground truth map Y Disco. encoding both bipartite structures and conflict hotspots; (2) a dual-branch segmentation network, which learns to predict a foundational semantic map P Psem= and detailed Disco coloring map Poolor; and (3) decoupled loss system, which provides targeted supervision. Crucially, the Adjacency Constraint Loss (Cad)) leverages the ground truth adjacency graph to enforce feature dissimilarity between all neighboring instances in the continuous probability space, thereby enabling end-to-end constrained optimization.
METHOD
Our topological analysis has revealed a profound characteristic real-world Cell Adjacency Graphs (CAGs): they are simultaneously dominated by simple, local bipartite arrangements yet punctuated by critical, non-bipartinn conflict clusters. To better address this complex and variable reality, we propose Disco, novel framework engineered to be both efficient for simple topologies and robust for complex ones. It eschews monolithic, high-chromaticity solutions in favor of a more elegant "di- vide and conquer" philosophy, which is actualized through cornerstone mechanisms: "Explicit Marking" for label generation and "Implicit Disambiguation" for model optimization. Our frame- work implements complete end-to-end learning process, synergistically integrating topological analysis, predictive modeling, and constrained learning, as illustrated in Figure 4.
4.1 THE "DIVIDE AND CONQUER" PRINCIPLE
The core of the Disco method is "divide and conguer" strategy applied to the graph coloring problem. Instead of treating the CAG as homogencous entity, we first stratify the problem space based on its intrinsic topological structure.
Theoretically, the graph coloring problem is equivalent to partitioning the vertex set V of graph G into a minimum number of disjoint Independent Sets {Vi, 1/2,., Ve). While finding this minimum partition, defined by the chromatic number (G), is an Na-Hard problem, our empirical analysis of the datasets provides a key insight: CAGs are predominantly dominated by massive bipartite subgraph Alon (1996).
This crucial structural property is the foundation of our "divide and conquer" principle. It suggests that a monolithic, high-chromaticity model suboptimal, as applies the same complex machinery to both the simple, vast bipartite regions and the sparse, complex non-bipartite regions. Instead, we propose that an optimal strategy should first efficiently handle the dominant bipartite component and then apply specialized mechanism the isolated, topologically challenging conflict nodes. This principle allows us to design a more targeted and efficient learning framework, which we detail in the following sections.

---

Published as a conference paper at ICLR 2026
Ripartte Cosppett Edge
Coker
Center
Figure 5. A visual decomposition of the Disco label generation process.
4.2 EXPLICIT MARKING: CONFLICT-AWARY LABEL GENERATION
The "Explicit Marking" strategy transforms the raw instance ground truth into topologically- informed supervisory signal, a process visually decomposed in Figure 5. This strategy operational- izes our "divide and conquer" principle through highly efficient, two-stage decomposition process.
Our algorithm employs a Breadth-First Search (BFS) to efficiently extract the maximal bipartite subgraph identified in our analysis. This partitions the vast majority of "simple" nodes into two large independent sets, V1 and 222 which correspond to our two primary colors.
Theoretically, this process could continue recursively the remaining subgraph, Grem GIV (V]UV)).. However, we make critical, pragmatic design choice based on the Principle of Sufficient Representation. Our analysis shows that the remaining nodes, which consolidate into single conflict set Veon/, are few in number but form dense, topologically complex "conflict clusters". Furthermore, finding minimum vertex set Voon whose removal renders graph bipartite is an NP-Hard problem Yannakakis 1978). Our BFS-based approach serves as an efficient heuristic to approximate this set, which has proven extremely effective in practice. We therefore terminate the decomposition and assign all nodes in Vcons a single, dedicated conflict color (c = t. where t == 3 in our framework). This avoids the computational overhead of full recursive decomposition while still explicitly marking the most challenging regions for our downstream "Implicit Disambiguation" mechanism. The resulting (t 1)-value ground truth map. YDisco E {0. ..., t] H x thus provides supervisory signal that is both efficient and topologically rich. A deeper discussion on the theoretical and empirical bounds of CAG chromaticity is provided Appendix A.4
4.3 IMPLICIT DISAMBIGUATION A DECOUPLED AND CONSTRAINED LOss SYSTEM
While the "Explicit Marking" strategy provides powerful supervisory signal, it has a theoretical limitation in its ambiguity within "secondary conflict" regions. To overcome this, we propose an "Implicit Disambiguation" mechanism, which resolves the inadequacies of discrete labels in the continuous feature space through a novel, end-to-end loss system. The total loss Ltotal is a weighted sum of five synergistic components:
Crotal Leem Lootor
Leone + Leon foadi
The foundational semantic loss (Leem) and the weighted coloring loss (Foolor) supervise the primary semantic segmentation and instance classification tasks. A pair of complementary regularization terms-the consistency loss (Ccona) and the conflict resolution loss (Loonf) mechanism, respectively suppressing the misuse of the conflict color in simple bipartite regions and encouraging its precise prediction in topologically complex regions. Let be the class index for the conflict color, where / = 3 in our framework:
"push-pull"
Lomss EieMar (a (Pentor (1)):)?} Lcom = ExE [(1 (Peostor (1)):)
(2)
Crucially, we designed the Adjacency Constraint Loss (Lndj) as the key mechanism for resolving secondary conflicts. This loss operates on adjacent edges the graph, minimizing the cosine similarity between the mean probability vectors P(s) of neighboring instances, thus maximizing their orthogonality.
P(s)) P(s,) P(( ([l
Lady (P (Pentor: G)
Σ (1IR5))
Conceptually, Cadj can be interpreted as a form supervised contrastive loss. For each instance, other pixels within the same instance constitute the positive set, whose feature cohesion is encour-

---

Published as a conference paper at ICLR 2026
aged by the classification loss Ccolor. Conversely, all its adjacent instances in the graph are treated as explicit negative samples. By minimizing the cosine similarity to these negative samples. Ladj drives the learning of feature manifold where the representations of different instances, especially adjacent ones, are maximally separated angularly. This achieves a powerful dual function: in bipar- tite regions, it drives the model to learn explicit, orthogonal 2-color encodings. In secondary conflict regions, it provides a counteracting gradient to the coloring loss, forcing the model to learn separable representations in the secondary feature dimensions. The effectiveness of this mechanism is signifi- cantly validated in our feature space visualization, as shown in Figure 6. A detailed formulation of each loss component is provided in imppeeddix A.5
Figure 6. Visualization of implicit disambigua- tion and robustness to coloring ambiguity. We project the final 4D probability vector of each cell instance into 3D space via I-SNE, visual- izing the core "Implicit Disambiguation" " mech- anism of the Disco framework and its invariance to the non-uniqueness of coloring.
5 EXPERIMENTS
5.1 DATASETS
To comprehensively evaluate the performance and generalization capability of our Disco method, we conducted experiments on four publicly available and nn-house datasets with significant hetero- geneity. These datasets encompass diverse imaging modalities, cell types, and a wide spectrum of topological complexities. Prior to being processed by our pipeline, all datasets were preprocessed into non-overlapping 256 x 256 pixel patches. Specifically, the datasets used are PanNuke Gamper et al. (020)), DSBco18(Caieedo et al. 2019). CryoNuSeg Mahbod et al. (2021). and GBC-FS 2025.
PanNuke consists of 7,901 256 x 256 images derived from H&E-stained, formalin-fixed paraffin- embedded (FFPE) tissue slides from 19 different human organs. It covers 5 distinct cell types and contains a total of 189, 744 annotated instances. We adhere its official data partitioning strategy, utilizing Fold and Fold 2 for training and validation, and Fold 3 for final testing.
DSB2018 comprises 670 fluorescence microscopy images of varying sizes (from 256 256 to 520 x 696), stained with DAPI and Hoechst. It includes a total of 29,443 annotated instances. We partitioned the dataset into 536 images for training, 67 for validation, and 67 for testing.
CryoNuSeg contains 30 HtE-stained frozen section images of size 512 x 512 from 10 human organs, with a total of 8,178 annotated instances. We cropped these images into 256 x 256 patches and subsequently partitioned them into 96 patches for training, 12 for validation, and 12 for testing.
GBC-ES 2025, first introduced in this study, designed as a high-density case study stress-test algorithmic robustness. Originating from single, deeply annotated WSI of gallbladder cancer frozen section, it provides an unprecedented challenge for handling complex topologies. tains 2,839 256 x 256 H&E-stained images with 864,204 annotated sub-cellular nuclei instances. The dataset was partitioned into 2,271 patches for training, 284 for validation, and 284 for testing. Further details are available in Appendix A.6
con-
5.2 IMPLEMENTATION DETAILS AND EVALUATION METRICS
All our experiments are conducted based on the Py framework and run on a server equipped with eight NVIDIA RTX 4090 GPUs We employ the Adam optimizer, with an initial learning rate set to x 10-4 and a weight decay of x 10-4, A step-wise learning rate decay strategy is adopted, which reduces the learning rate by a factor of 10 at the 70th epoch, supplemented by linear warmup phase over the first 100 iterations to ensure initial training stability. All models are trained for total of 200 epochs. Segmentation performance is evaluated using the Dice Coefficient (Dice) Lei et al. (2023), Aggregated Jaccard Index (AJI) Kumar et al. (2017). Detection Quality (DQ) Kirillov al. (019)) Segmentation Quality (SQ), and Panoptic Quality (PQ) metrics. In all
8

---

Published as a conference paper at ICLR 2026
Original
Ground Truth
llice (eumn)
FUB
Original
Ground Trath
Dises (ours)
(a) Pashhuke Dutasct
(b) USSEEES Dutneet
(o CryuNuale Datant
(4) GBCC-P 1005 Detwel
Figure 7. Qualitative comparison of segmentation results on the four datasets. Each panel displays (from left to right): the input image, the ground truth, the prediction from our Disco method, and the prediction from FCIS.
tables presented throughout this paper, the highest performance scores are highlighted in red bold, and the second-best scores marked in blue bold.
5.3 EVALUATION AND RESULTS
Table The comparison performances on Pan- Nuke dataset.
Table 3: The comparison performances on DSB2018 dataset.
Methods
Source
(FC
(1)
Metrics
(1) SQ PQ
Methods
Source
(TC
Metrics
(QQ (Q
PQ
DCAN
CVPR 2016
0:7285
0.5871
0.6991 0.7316
0.5065
DCAN
CVPR 2016
0.7954
0.6764
0.7435
0.7807
0.6766
Hovereet
MIA 2019
0.7983
0.6463
0,7182
0,7824
0,5953
HoverNet
MIA 2019
0.8983
0.7623
0,8657
0,8775
0,9625
NocleSeegNet
CBM
0.5466
0.457
NudleSeyNet
CBM
0.9045
0.718
0.7845
DoNei
2013
0.7812
0.137
0.6849
0.7506
0.5445
DoNei
CVPR 2013
0.8239
0.162
0.7872
0.8294 0.6733
Net-Net
JERB TIP 2023
0.3145
0.633
0,7115
0,776]
0.5831
CeP-Net
ICEE TIP 2003
0.9167
0.1111
0.8664
0,8793 0,7582
Un-AM
0.295
0.5702
Un-AM
MBA 2025
0:0021
0.526)
CellPose
NAT METHODS 2025
0.7871
0,6262
0,0035
0,7643
0.5918
CellPose
NAT METIODS 2025
0.9232
0.8247
0,8625
0,8715 0.7647
FCIS
ICML 2025
0.5183
0.6394
0.7252
0,8033
0.6129
FCBS
ICML 2025
0.9395
0.8267
0,8805
0,8789 0,7739
0.6211
Quantitative and Qualitative Evaluation. To validate the effectiveness and generalization capa- bility of our Disco method, we conducted a comprehensive quantitative and qualitative compari- son against a diverse set of mainstream instance segmentation methods across four heterogeneous datasets with varying topological complexities. The compared methods include the detection- COeANChen&& Chen
DoNet[Jiang al. (2023); contour prediction rediction-based DCAN
(2016) and NucleiSegNet [Lll et al. (2021); distance mapping-bal based HoverNet Graham et al. (2019). CPP-Net Chen et al. (2023). and CellPose Stringer & Pachitariu (2025); the baseb foundation model Un-SAM Chen et al.
(202);; and the graph-theory based FCIS Zhang et al. (2025c). As demonstrated in Tables 2-5,
Disco method exhibits consistent and superior performance across all four datasets.
Quantitative Comparison. On the PanNuke dataset, which features the simplest topology with 100% bipartite cell adjacency graphs, our method achieves the best results on the key AJI and PQ metrics, with scores of 65.66% and 62.71%, respectively. This proves that even in the sim- plest cases, our dynamic coloring framework can automatically degenerate into a highly efficient 2-coloring model, outperforming the generic 4-color model FCIS which needs to learn a more com- plex representation. As the topological complexity increases, the advantages of Disco become even more pronounced. On the moderately complex DSB2018 and CryoNuSeg datasets, Disco also leads comprchensively in both AJI and PQ. It is worth noting that on DSB2018, although FCIS holds a slight edge in DQ, our method significantly superior in SQ, indicating that our model generates more precise cell contours and ultimately prevails in the overall metrics.
This superiority culminates on the highly challenging GBC-FS 2025 dataset. This dataset, filled with dense "conflict clusters" and "secondary conflicts", poses severe test for all methods. The re- sults in Table 5 clearly show that Disco's, 's performance on this dataset is overwhelming. Our method achieves an AJI of 52.09%, remarkable 6.91% % absolute improvement and a 15.3% relative im- provement over the second-best method, FCIS, Concurrently, Disco achieves a comprehensive lead in both DQ and SQ dimensions. This irrefutably demonstrates that "Explicit Marking Implicit Disambiguation" strategy possesses unparalleled robustness and effectiveness when handling the extreme topological complexities of real-world scenarios.
Visual Comparison. We provide an intuitive visual comparison of the segmentation results in Figure 7. These visualizations showcase Disco's capability to accurately segment cell across the

---

Published as a conference paper at ICLR 2026
Table 4: The comparison performances Cry- oNuSeg dataset.
Table 5: The comparison performances on GBC- FS 2025 dataset.
Methods
Source
(TC
(]
Metrics
IKQ (1) SQ:T] PQ
Methods
Source
DICE())
A]
Metricc
TRU (7) SQ.T PF
DCAN
CVPE 2016
0.3645
0.5273
0.6184
0.7264
0-4663
DCAN
CVPR 2016
0.7144
0.3983
0.5365
0.6572
0.3528
BoverNet
MLA 2019
0.5432
0.5585
0.6469
0.7543
0.4955
HoverNet
MBA 2019
0.7394
0.4058
0,5465
0,6382 0.3699
NecleSegNett
CBM 2021
0.3645
0.5764
0.6673
0.7841 0.5253
NudleSegNet
CBM 2021
0.5419
0.4395
0.5615
0.6647
0.5835
DaNlet
CVPR 2023
0.549
0.7815
0.3147
DoNat
CVPR 2023
0.5409
0.5564
0.3730
CPR-Na
2003
0.5967
0.5379
CPR-Net
2003
MIA
0.5627
0.5671
0.7815
0.5567
SAM
MLA 2025
0.7641
0,4005
0.5782
0,4093
CellPose
NAT METIODS 2025
0.8859
0.5876
0.886]
0,8094
0.5724
CellPoce
NAT METIODS 2025
0.7698
0.4376
0.5983
0.6739
0.4218
PCIS
ICML 2025
0.3977
0 6.5944
0.6929
0,8173
0.5793
FCIS
ICML 2025
0.7785
0.4518
0.5857
0.7068 0.4379
Disco
Dur
0.9152
0.6144
0,7153
0,8120 0.5970
Disce
Ours
0:8133
0.520
0.6795
0,7486
0.5087
four datasets, which vary significantly in staining, cell morphology, and density. In the challenging regions highlighted by white boxes, Disco demonstrates clear advantage over the second-best method FCIS, successfully separating tightly clustered instances. More extensive visual results are presented in the Appendix A.7
5.4 ABLATION STUDIES
To systematically validate the effectiveness of cach core design within the Disco method, we con- ducted a series of exhaustive ablation studies on the most challenging GBC-FS 2025 dataset.
Framework-level Comparison. We first performed framework-level comparison establish the superiority of our dynamic coloring scheme, as shown in Table 6. The results clearly indicate that the pure 2-coloring baseline, which lacks conflict resolution mechanism, performs the worst (37.85% AJI), further corroborating our earlier conclusion on the necessity of handling non-bipartite structures. Compared to the generic 4-coloring scheme of FCIS, our Disco framework achieves a significant 7.08% absolute improvement in the PQ metric. We infer that this advantage stems from our "divide and conquer" strategy, which provides the network with a clearer and more targeted learning objective, thereby avoiding the potential optimization difficulties and representation redun- dancy present in generic high-chromaticity models.
Analysis of Loss Components. We further dissected Disco's loss function system to verify the contribution of each component, as shown Table 7. The experimental results demonstrate that every loss term we designed contributes positively to the final performance. Among them, the Adjacency Constraint Loss (Ludt) shows a decisive influence; adding it alone to the basic Explicit Marking model yields a substantial 6% absolute improvement in PQ (from 42.57% to 48.26%). This result quantitatively and forcefully proves that our proposed Ladj, aimed at resolving "secondary conflicts" through "Implicit Disambiguation", is the key driving force behind the success of the entire framework. When all loss components work in synergy, our final Disco model achieves the optimal performance of 50.87% in PQ, demonstrating that every component we designed both necessary and effective.
Table 6: Ablation study on different coloring frameworks on GBC-FS 2025.
Table Ablation study on the components of our Disco loss system on GBC-FS 2025.
Method
Coloring
Adjacency
Metries
Method
Leans
Loans
kndy
Dice
AJI
PQ
Scheme
Constraint
Dice
AJI
PQ
Explice Marking
x
x
0.753
0.6436
0:4257
Raseline
3-Dwler
None
0.7260
0:3785
0.3876
Explici Marking
0.4583
FCIS
4 4-Color
Lore on features
0.7785
0,4518
0.4379
Explicit Marking
x
0.7914
0,5057
0.4826
Disco
Expicit Marking
busi on probabilities
08137
0,5209
0.5087
Disco
03137
0,5209
0.5087
CONCLUSIONS
Through the first systematic analysis of the chromatic properties of cell adjacency graphs, we veal the profoundly non-bipartite nature of real-world cell adjacency graphs, thereby elucidating the theoretical limitations of simple 2-coloring models in this domain. To address this challenge, we propose Disco, a novel framework operating on a "divide and conquer" principle. Disco employs an "Explicit Marking" strategy, which dynamically and intelligently decomposes the cell graph into a vast bipartite backbone and a sparse conflict set. More importantly, it achieves "Implicit Disam- biguation" through a loss system featuring an end-to-end adjacency constraint. This mechanism resolves the discrete label ambiguities caused by "secondary conflicts" by learning separable rep- resentations in the continuous feature space. Comprehensive experiments demonstrate that Disco achieves state-of-the-art performance and excellent generalization across multiple heterogeneous datasets. Furthermore, we pioneer the use of the predicted "Conflict Map" as a novel interpretability tool. offering new avenue for quantifying topological complexity. In summary, Disco provides a theoretically sound, efficient, and interpretable new paradigm for solving complex cell instance segmentation.
10

---

Published as a conference paper at ICLR 2026
7 ACKNOWLEDGMENTS
This work was supported in part by the Shanghai Municipal Science and Technology Major Project (2023SHZIZZ02 and 2017SHZDZX01 L.J.), and in part by the Lingang Laboratory (Grant No. LGL-5555, LGL-6672 and LGL-8888). The computations in this research were performed using CFFF platform of Fudan University.
REFERENCES
Noga Alon. Bipartite subgraphs. Combinatorica, 16(3):301-311, 1996.
Tuan Tran Anh, Khoa Nguyen- Tuan, Tran Minh Quan, and Won-Ki Ki Jeong. Reinforced coloring for end-to-end instance segmentation. arXiv preprint arXiv:2005.07058 2020.
Armen S Asratian, Tristan MJ Denley, and Roland Häggkvist. Bipartite graphs and their applica- lions, volume 131. Cambridge university press, 1998.
Juan Caicedo, Allen Goodman, Kyle Karhohs, Beth A Cimini, Jeanelle Ackerman, Marzieh Haghighi, CherKeng Heng, Tim Becker, Minh Doan, Claire McQuin, et. Nucleus segmentation across imaging experiments: the 2018 data science bowl. Nature Methods, 164123;124--155,, 2019.
Shivesh Chaudhary, Sol Ah Lee, Yueyi Li, Dhaval Patel, and Hang Lu. Graphical-model frame- work for automated annotation of cell identities in dense cellular images. Elife, 10:e60321, 2021.
Dan Chen and Housheng Su. Identification of influential nodes in complex networks with degree and average neighbor degree. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 13(3):734-743 742, 2023.
Hao Chen, Xiaojuan Qi, Lequan Yu, and Pheng-Ann Heng. Dean: deep contour-aware networks for accurate gland segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2487-2496, 2016.
Jieneng Chen, Jieru Mei, Xianhang Li, Yongyi Lu, Qihang Yu, Qingyue Wei, Xiangde Luo, Yutong Xie, Ehsan Adeli, Yan Wang, al. Transunet: Rethinking the u-net architecture design for med- ical image segmentation through the lens of transformers. Medical Image Analysis, 97:103280, 2024.
Shengcong Chen, Changxing Ding, Minfeng Liu, Jun Cheng, and Dacheng Tao. Cpp-net: Context- aware polygon proposal network for nucleus segmentation. IEEE Transactions on Image Pro- cessing, 32:980-994, 2023.
Zhen Chen, Qing Xu, Xinyu Liu, and Yixuan Yuan. Un-sam: Domain-adaptive self seff-prompt seg- mentation for universal nuclei images. Medical Image Analysis, pp. 103607, 2025.
Endre Csóka, Gábor Lippner, and Oleg Pikhurko. König's 's line coloring and vizing's theorems for graphings. In Forum of Mathematics, Sigma, volume 4, pp. e27. Cambridge University Press, 2016.
Rudolf Fritsch, Rudolf Fritsch, G Fritsch, and Gerda Fritsch. Four-Color Theorem. Springer, 1998.
Jevgenij Gamper, Navid Alemi Koohbanani, Ksenija Benes, Simon Graham, Mostafa Jahanifar, Syed Ali Khurram, Ayesha Azam, Katherine Hewitt, and Nasir Rajpoot. Pannuke dataset exten- sion, insights and baselines. arXiv preprint arXiv:2003.10778 2020.
Fierre-Antoing Ganaye, Michaël Sdika, Bill Triggs, and Hugues Benoit-Cattin Removing segmen- tation inconsistencies with semi-supereised adjaaeeayy constraint. Medical Image Analysis, 58: 101511, 2019.
Georges Gonthier et al. Formal proof the the four-color theorem. Notices of the AMS, 55(11):1382 1393, 2008
11

---

Published as a conference paper at ICLR 2026
Simon Graham, Quoe Dang Vu, Shan E Ahmed Raza, Ayesha Azam, Yee Wah Tsang, Jin Tae Kwak, and Nasir Rajpoot. Hover-net: Simultaneous segmentation and classification of nuclei in mullti-tissue histology images. Medical Image Analysis, 58: 58:101563, 2019.
Hongliang He, Zhongyi Huang, Yao Ding, Guoli Song. Lin Wang, Qian Ren, Pengxu Wei, Zhiqiang Gao, and Jie Chen. Cdnet: Centripetal direction network for nuclear instance segmentation. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp- 4026- 4035, 2021.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In Proceedings of the IEEE International Conference Computer Vision (ICCV), pp- 2961-2969, 2017.
Fabian Hörst, Moritz Rempe, Lukas Heine, Constantin Seibold, Julius Keyl, Giulia Baldini, Selma Ugurel, Jens Siveke, Barbara Grünwald, Jan Egger, al. Cellvit: Vision transformers for precise cell segmentation and classification. Medical Image Analysis, 94:103143, 2024.
Tudor Hulubei, Eugene C Freuder, and Richard Wallace. The goldilocks problem. Al EDAM, 17 (1):3-11, 2003.
Hao Jiang, Rushan Zhang, Yanning Zhou, Yumeng Wang, and Hao Chen. Donet: Deep de- overlapping network for cytology instance segmentation. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition (CVPR), pp. 15641-15650, 2023.
Jeong Han Kim. On brooks' theorem for sparse graphs. Combinatorics, Probability and Computing, 4(2):97-332, 1995.
Alexander Kirillov, Kaiming He, Ross Girshick, Carsten Rother, and Piotr Dollár. Panoptic segmen- tation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9404 9413, 2019.
Victor Kulikov, Victor Yurchenko, and Victor Lempitsky. Instance segmentation by deep coloring. arXiv preprint arXiv: 10007, 2018.
Neeraj Kumar, Ruchika Verma, Sanuj Sharma, Surabhi Bhargava, Abhishek Vahadane, and Amit Sethi. A dataset and technique for generalized nuclear segmentation for computational pathol- ogy. IEEE Transactions on Medical imaging. 36(7):1550-1560, 2017.
Shyam Lal, Devikalyan Das, Kumar Alabhya, Anirudh Kanfade, Aman Kumar, and Jyoti Kini. Nucleisegnet: Robust deep learning architecture for the nuclei segmentation of liver cancer histopathology images. Computers in Biology and Medicine, 128: 104075, 2021.
Tao Lei, Rui Sun, Xiaogang Du, Huazhu Fu, Changqing Zhang, and Asoke K Nandi. Sgu-net: Shape-guided ultralight network for abdominal image segmentation. IEEE Journal of Biomedical and Health Informatics, 27(3):1331-1422 2023.
Xiaoyu Liu, Wei Huang, Yueyi Zhang, and Zhiwei Xiong. Biological instance segmentation with superpixel-guided graph. In IJCAI, pp. 1209-1215, 2022.
Katharina Löffler, Tim Scherr, and Ralf Mikut. A graph-based cell tracking algorithm with few man- ually tunable parameters and automated segmentation error correction. PloS one, 16(9):02292577 2021.
Amirreza Mahbod, Gerald Schaefer, Benjamin Bancher, Christine Löw, Georg Dorffner, Rupert Ecker, and Isabella Ellinger. Cryonuseg: A dataset for nuclei instance segmentation of cryosec- tioned h&e-stained histological images. Computers in Biology and Medicine, 1 132: 104349, 2021.
Sumit K Nath. Kannappan Palaniappan, and Filiz Bunyak. Cell segmentation using coupled level sets and graph-vertex coloring. In International Conference on Medical Image Computing and Computer-Asiistd Intervention (MICCAI), pp. 101-108. Springer, 2006.
Vladimir Nikiforov. A spectral condition for odd cycles in graphs. Linear Algebra and Its Applica- fions, 428(7): 14927) 1498, 2008
12

---

Published as a conference paper at ICLR 2026
Viktor Petukhov, Rosalind Xu, Ruslan A Soldatov, Paolo Cadinu, Konstantin Khodosevich, Jef- frey R Moffitt, and Peter V Kharchenko. Cell segmentation in imaging- based spatial transcrip- tomics. Nature Biotechnology, 4063):345-354, 2022.
Hui Qu, Zhennan Yan, Gregory M Riedlinger, Subhajyoti De, and Dimitris N Metaxas. Improv- ing nuclei/gland instance segmentation in histopathology images by full resolution neural net- work and spatial constrained loss. In International Conference on Medical Image Computing and Computer-Assistr Intervention (MICCAI), pp. 378-3888-888 336.. Springer, 2019.
Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 133--1199 2016.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomed- ical image segmentation. In International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI), pp. 234-241. Springer, 2015.
Uwe Schmidt, Martin Weigert, Coleman Broaddus, and Gene Myers. Cell detection with star-convex polygons. In International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI), pp. 263-273. Springer, 2018.
Carsen Stringer and Marius Pachitariu. Cellpose3: one-click image restoration for improved cellular segmentation. Nature Methods, 22(3):592-599, 2025.
Alain Trémeau and Philippe Colantoni. Regions adjacency graph applied to color image segmenta- tion. IEEE Transactions Image Processing, 9(4):735-744, 2000.
A Vazquez, R Dobrin, D Sergi, J-P Eckmann, Zoltan N Oltvai, and A-L Barabási. The topological relationship between the large-scale attributes and local interaction patterns of complex networks. Proceedings of the National Academy of Sciences, 101452):1940-11994 2004.
Ching- Wei Wang, Wei-Tang Lee, and Ting-Sheng Su. A survey of deep learning methods on cell instance segmentation. Neural Computing and Applications, pp. 1-70, 2025.
Siyuan Xu, Guannan Li, Haofei Song, Jiansheng Wang. Yan Wang, and Qingli Li. Genseg-net: A general segmentation framework for any nucleus immunohistochemistyy images. In Pro- ceedings of the 32nd ACM International Conference Multimedia (ACM MM), pp. 4475-4484, 2024.
Mihalis Yannakakis. Node-and edge-deletion np-complete problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 253-264, 1978.
Jingru Yi, Pengxiang Wu, Qiaoying Huang, Hui Qu, Bo Liu, Daniel Hoeppner, and Dimitris N Metaxas. Multi-scale cell instance segmentation with keypoint graph based bounding boxes. In International Conference on Medical Image Computing and Cosputer-Asistee Intervention (MICCAI), pp. 369-377. Springer, 2019.
Ye Zhang, Linghan Cai, Ziyue Wang, and Yongbing Zhang. Seine: Structure encoding and in- teraction network for nuclei instance segmentation. IEEE Journal of Biomedical and Health Informatics, 2025a.
Ye Zhang, Zijie Fang. Yifeng Wang, Lingbo Zhang, Xianchao Guan, and Yongbing Zhang. Category prompt mamba network for nuclei segmentation and classification. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 39, pp. 10284-10292, 2025b.
Ye Zhang, Yu Zhou, Yifeng Wang, Jun Xiao, Ziyue Wang, Yongbing Zhang, and Jianxu Chen. The four color theorem for cell instance segmentation. arXiv preprint arXiv:2506.09720 09724, 2025c.
Zihua Zhao, Ting Wang, Haonan Xin, Rong Wang, and Feiping Nie. Multi-view clustering via high-order bipartite graph fusion. Information Fusion, 113:102630, 2025.
Yanning Zhou, Omer Fahri Onder, Qi Dou, Efstratios Tsougenis, Hao Chen, and Pheng-Ann Heng. Cia-net: Robust nuclei instance segmentation with contour-aware information aggregation. In International Conference on Information Processing in Medical Imaging (IPMI), pp. 682-693. Springer, 2019.
13

---

Published as a conference paper at ICLR 2026
Yanning Zhou, Hao Chen, Huangjing Lin, and Pheng-Amn Heng. Deep semi- supi-uupe knowl- edge distillation for overlapping cervical cell instance segmentation. In International Confer- on Medical Image Computing and Computer-Assisted Intervention (MICCAI), pp. 521-531. Springer, 2020.
Zongwei Zhou, Md Mahfuzur Rahman Siddiquee, Nima Tajbakhsh, and Jianming Liang. Unet++: A nested u-net architecture for medical image segmentation. In International Workshop on Deep Learning Medical Image Analysis, pp. 3-11. Springer, 2018.
A APPENDIX
A.I LLM USAGE STATEMENT
In the preparation of this manuscript, we have strictly utilized the ChatGPT large language model (LLM) solely as general auxiliary tool to support and enhance the writing process. All core scien- tific contributions, including the research concept, the design of all algorithms and experiments, and the final analysis of results, were exclusively developed by the human authors. LLMs were primarily employed to refine sentence structures for improved clarity and fluency, and to ensure terminology consistency. Additionally, an --se- image generation tool was used to create the logo graphic present in the paper's 's title. They made no contribution to any of the core research ideas or scientific conclusions presented in this paper.
A.2 RELATED WORK
A.2.1 DETECTION -AASDD INSTANCE SEGMENTATION
The "detecttthen--semee"" paradigm, introduced by pioneering works like Faster R-CN Ren al. 2016), was extended to instance segmentation by Mask R-CNN He et al. (2017). This two-stage method first generates bounding box Yi al. (2099) proposals for individual instances and then performs segmentation within these localized regions. Its inherent capability for instance separation has made it a widely adopted framework, especially in semi-supervised cell segmentation tasks) Zhou et al. (2020). However, the performance of this paradigm is fundamentally constrained by its reliance on axis- axis-aligned bounding boxes, which provide coarse representation for cells with complex or irregular morphologies. Furthermore, the final instance set is often dictated by the heuristic nature of non-maxima suppression (NMS), which frequently leads to the erroneous suppression of valid detections in dense, overlapping cell clusters, critical failure mode visualize in Figure I(a).
A.2.2 CONTOUR AND DISTANCE- BASED SEGMENTATION
To circumvent the limitations of bounding boxes, a second major class of methods focuses on learn- ing dense, pixel-wise representations that encode instance identity.
Contour-based based methods aim to explicitly predict the boundaries between cells. The seminal U- Net |Ronneberger al. (2015) facilitated boundary learning by weighting cell edges in the loss function, with instances subsequently delineated via post-processisng techniques like watershed. This
architecture has profoundly influenced the field. Subsequent advancements focused on enhancing boundary prediction, for example, DCAN Chen et al. (2016) introduced dedicated boundary-class channels. Architectural optimizations such nested skip connections in UNet++ Zhou et al. (2018) and multi-scale context aggregation in FullNet Qu et al. (2019) and CIA-Net Zhou et al. (2019) further improved boundary delineation. Despite these advances, contour-based methods remain highly sensitive to the binarization threshold of the predicted boundary map, leading to trade-off between instance merging and fragmentation, as shown in Figure 1(b).
Distance-based methods achieve more robust separation by learning richer spatial relationships. StarDist [Schmidt et al. (2018) and CellPose Stringer & Pachitariu (2025) learn to predict vectors from pixels to the cell's boundary or center, respectively. Hover-Net Graham al. (2019) extended this concept by simultaneously predicting horizontal and vertical distance maps. Although these methods demonstrate SOTA performance, they typically rely complex and error-prone post- processingLLöffer et (202)) to reconstruct instances. This makes them susceptible to error prop- agation Chaudhary al. (2021), where minute inaccuracies in the predicted vector fields can be
14

---

Published as a conference paper at ICLR 2026
amplified into significant instance splitting errors, as illustrated in Figure I(c). While recent models, from CPP-Net| Chen et al. (2023) to Vision Transformer based architectures like CelIViT Hörst et al. 2024), continue to advance this paradigm, they still share fundamental dependence on decoding local geometric cues.
A.2.3 GRAPH-THEORETH APPROACHES IN SEGMENTATION
A common theoretical bottleneck across all aforementioned paradigms is their lack of an intrinsic mechanism to model the global topological constraints among cells. To address this, a new perspec- tive that abstracts the problem into graph coloring task has emerged.
Graph coloring is a fundamental problem in graph theory with deep connections to scheduling and resource allocation. A k-coloring of graph G = (V, E) is a function C V (1.....) k) such that for any edge (u, v) E F., C(u) * C(r). The minimum k for which such coloring exists is the graph's 's chromatic number, XG).
Early works in computer vision used graph coloring Nath et al. (2006) as a post-processing step for region merging. However, its integration into end-to-end learning recent innovation. In- spired by the Four-Color Theorem Gonthier et al. (2008), which states that any planar graph satisfies X() I 4, FCIS Zhang et al. (2025c) was the first to propose training network directly predict a 4-coloring of the cell graph. This pioneering work demonstrated the immense potential of refor- mulating instance segmentation as a multi-class classification problem constrained by topological rules.
more fundamental concept than the Four-Color Theorem is 2-coloring, which, according to König's Theorem, is sufficient for any bipartite graph. This introduces critical "Goldilocks" problem: what is the minimal, yet sufficient, number of colors required Kulikov et al. (2018) for real-world cellular topologies? Is the elegant simplicity of 2-coloring model sufficient, or is the universal robustness of 4-coloring model necessary?
Our work is dedicated to answering this question and, based on the answer, proposing an optimal solution. We do not treat the cell graph as a passive object to which existing theories are applied; rather, we view it
unique, unexplored structure. First, through systematic topological analysis, we are the first to provide an empirical answer to this question, revealing the complex reality of "near-bipartite but with dense conflict clusters." Second, based on this finding, we design novel, non-iterative mechanism that injects strong topological priors into a deep network via graph- aware loss system. Therefore, our work not only resolves the "Goldilocks" problem but also offers a new perspective on how to integrate profound graph- theoretcc principles with deep representation learning to solve structured prediction tasks.
A.3 SUPPLEMENTARY ANALYSIS AND VISUALIZATIONS
To provide a more holistic and intuitive understanding of our core motivations and the efficacy of our proposed coloring strategy, we present in Figure A. comprehensive, side-by-side visual comparison across the full spectrum of dataset complexities. This figure visually decomposes our entire analysis pipeline, from the raw input the final coloring outcomes, providing direct evidence for the key arguments made throughout this paper.
Column (a) the input image, and Column (b) is the instance ground truth. These two columns establish the problem context, showcasing the significant heterogeneity in imaging modality (H&E, fluorescence), cell density, and morphology across the different benchmarks. The randomly colored instance map in (b) represents the ideal segmentation target.
Column (c) is the Cell Adjacency Graph (CAG) with odd-cycle detection. This column visual- izes the core of our topological analysis. The instance map is abstracted into its underlying graph structure, where nodes represent cell centroids and edges represent adjacency. A critical diagnos- tic is performed red, while those of simple bipartite components remain gray. This visualization starkly reveals the "topological complexity spectrum". the graph for the PanNuke dataset is entirely gray, confirming its perfect bipartite nature. DSB2018 and CryoNuSeg, red edges begin to appear, indicating the presence of isolated or small clusters of odd cycles. The graph for the GBC-FS 2025 dataset, in
each graph: edges belonging to non-bipartite components are highlighted in
15

---

Published as a conference paper at ICLR 2026
PanNuke
DSB2018
CryoNnSeg
GBC-FS 2025
(u) Image
(b) Ground Truth
(c) Adjucency Graph
(d) Four Color
(c) Disco
Figure A.1. A comprehensive, cross-dataset visualization of cell graph topologies and coloring strategies. Each row corresponds to a specific dataset, with topological complexity increasing from top bottom.
contrast, exhibits massive, interconnected network of red conflict edges, visually demonstrating prevalence of dense "conflict clusters" and "secondary conflicts".
Column (d) is the generic greedy 4-coloring. This column displays the results of applying generic greedy coloring algorithm. crucial empirical finding is revealed here: across all four datasets, including the highly complex GBC-FS 2025, palette of three colors is empirically sufficient to resolve all adjacency constraints. This evidence strongly suggests that the true chromatic number of real-world cell graphs is typically XG) = 3. Consequently, any framework based on the Four-Color Theorem, which prepares for a worst-case chromaticity of four, introduces unnecessary representa- tional redundancy and potential optimization challenges.
Column (e) is the Disco coloring scheme. This final column showcases the adaptability and targeted efficiency of our proposed Disco framework. On the perfectly bipartite PanNuke dataset, our algo- rithm automatically degenerates into an optimal 2-coloring scheme, avoiding color waste. On the moderately complex DSB2018 and CryoNuSeg datasets, Disco effectively utilizes its conflict-aware 2-coloring strategy. It efficiently colors the vast bipartite backbones with two primary colors (blue and purple) and uses a dedicated conflict color (yellow) to precisely and sparsely mark the few topo- logical conflicts identified in (c). On the extremely complex GBC-FS 2025, Disco robustly applies the same structured, conflict-aware coloring scheme. This provides a clear, topologically-infore supervisory signal that explicitly pinpoints the numerous conflict hotspots, laying the foundation for our "Implicit Disambiguation' mechanism to resolve the remaining ambiguities in the feature space.
In summary, this comprehensive visualization provides powerful, side-by-side validation of our core thesis: Disco not merely a coloring method, but a principled, data-driven framework that tailor-made for the observed topological properties of real-world cell images. It avoids both the theoretical insufficiency of pure 2-coloring and the practical redundancy of 4-coloring, offering a solution that strikes optimal balance between efficiency, robustness, and interpretability.
16

---

Published as a conference paper at ICLR 2026
A.4 THEORETICAL AND EMPIRICAL BOUNDS ON THE CHROMATICITY OF CELL GRAPHS
In Section 4.2, justified pragmatic choice terminate the graph decomposition. This section provides deeper theoretical and empirical discussion of the chromatic number (x(G)) of Cell Adjacency Graphs (CAGs), which further substantiates our design philosophy.
A.4.1 THEORETICAL REMARK THE UPPER BOUND CIROMATICITY
A well-established result in graph theory provides upper bound on the chromatic number based on the graph's s maximum degree Åg.
Proposition 1: For any graph G with maximum degree Ag. its chromatic number is bounded by (G) & Ag
Proof. This proposition can be proven constructively using simple greedy coloring algorithm. The algorithm proceeds as follows:
1. Order the vertices of the graph G arbitrarily UI, U2, "2...... Un-
Provide palette of Âg available colors.
3. Iterate through the vertices from 11 to t/ For each vertex 14 assign it the smallest available color that has not been used by any its already-colored neighbors in {ui,..., 1.-1)
This algorithm is guaranteed to succeed. When coloring any vertex vs, it has at most Ag neighbors. Therefore, at most AG colors could have been used by its neighbors. Since our palette contains Ag + 1 distinct colors, there will always be at least color available for v As this holds for all vertices, the entire graph can be colored with at most Ag + 1 colors, thus establishing the bound XG) < Ag 1. This bound is related the more powerful Brooks" Theorem Kim (1995). which provides a tighter bound of (G) & A for most graphs.
Our data analysis (Table 1) shows that for datasets, Ag S 8, implying worst-case theoretical bound of 9 colors based on this proposition. This loose upper bound highlights significant gap between worst-case graph theory and the specifie reality of our problem domain.
A.4.2 EMPIRICAL FINDINGS: THE "3-COLOR PHENOMENON"
Our most striking empirical finding, illustrated in the qualitative results (e.g., Figure A.1 in Ap- pendix A.2), is that palette of three colors consistently sufficient to resolve all adjacency con- straints across all four diverse datasets, including the topologically complex GBC-FS 2025. This suggests that the true chromatic number of real-world cell graphs almost always X(G) = if they non-bipartite, and X otherwise. This "3-Color Phenomenon" stands in stark contrast to the theoretical upper bound of 9.
A.4.3 A HYPOTHESIS ON THE STRUCTURAL ORIGINS OF Low CHROMATICITY IN CELL GRAPHS
The consistent observation of low chromaticity motivates deeper question: why are cell graphs so structurally constrained? We hypothesize that this is not coincidence, but consequence of fundamental physical and biological principles governing tissue organization.
Graph theory tells us that a high chromatic number (x(G) 2 requires the graph to contain K₃ minor-thor is, subgraph that can be contracted to form complete graph of 4 vertices (K4). A K4 subgraph represents a scenario where four distinct cell instances are all mutually adjacent to each other, as shown in Figure A.2.
We argue that such a configuration is biophysically improbable quasi-2D tissue slice. Due to constraints of cell volume, membrane tension, and optimal packing principles (analogous to circle packing problems), is extremely difficult for four distinct, roughly convex objects to all achieve simultaneous, pairwise physical contact. While three-war way contact (forming 3-cycle or triangle) common at intercellular junctions, a four-way mutual contact topologically unstable and energetically unfavorable state.
17

---

Published as a conference paper at ICLR 2026
A
D
Bipartite Nodes
Bipartite Nodes
Conflict Nodes
B
Adjacency Edges
Figure A.2. A schematic a complete graph on four vertices (K²) and its biophysical interpretation in cell segmentation. A Ka subgraph represents topological configuration where four distinet cell instances (A, B, C. D) are mutually adjacent. We hypothesize that forming such a structure in a quasi-2D tissue slice is biophysically improbable due the physical constraints of cell volume and membrane tension. The absence of such high-order conflict structures like K₂ minors in real-world cell graphs provides theoretical underpinning for the empirically observed "3-Color Phenomenon".
Conclusion and Justification for Disco: This hypothesis provides theoretical underpinning for our empirical "3-Color Phenomenon". It suggests that the underlying biophysics of cellular ar- rangements naturally precludes the formation of high-order conflict structures (like K₁ minors) that would necessitate 4 more colors. This finding the ultimate justification for our Disco frame- work. Instead of preparing for high-chromaticity worst case that is biophysically unrealistic (like 4-coloring scheme), 2+1 approach is perfectly tailored to the observed reality: it efficiently handles the dominant bipartite structures with two colors and reserves single, sufficient conflict color resolve the common, but low-order (predominantly 3-cycle), topological confticts.
A.5 DETAILED FORMULATION OF THE LOss SYSTEM
The end-to-end optimization of our Disco framework is driven by decoupled and constrained loss system. The total loss, as introduced in Equation (1), is a weighted sum of five components. Here, we provide detailed formulation and rationale for each component.
Notation:
Let Prem E R Bx2xxxx be the semantic logits and Pcolor E XXW be the coloring logits produced by the network for a batch of B images. Let Y Ysem 10 be the binary semantic ground truth, and Y Dismo E {0...., B x be our Disco ground truth map, with I = 3 in case. Let ar-)) be the channel-wise Softmax function. Let Ω denote the set of all pixel coordinates in an image.
Foundational Losses Csem and Lootor
These two losses provide the primary supervisory signal for the network's 's dual heads.
The Semantic Loss fiem supervises the basic foreground/background segmentation. It is linear combination of pixel-wise Cross-Entropy loss LCE and a region-based Dice loss L
L Ssem (Psem; Y Ysem) CCr(Psem. Ysem) L (Psemy Y Ysem)
(4)
This ensures the network learns to accurately identify the spatial support of all cellular regions.
The Coloring Loss Lestor supervises the multi-class Disco labeling task. is composed of Weighted Cross-Entropy LwOE and Dice loss:
Cector(Pootor Discoo) = LWCE(Pooll Disoo) + L (Potoor Disco)
(5)
The LWEF is defined for pixel i as:
18

---

Published as a conference paper at ICLR 2026
Swee(Pootan (ootor(()) (i), Disco Wyccc Log(a((Pntoon (1)) (
(6)
where W. is the weight for class We set the weight for the conflict class w; significantly higher than for the bipartite colors (w; > WeE(L....t11) to compel the model to prioritize learning these critical topological features.
2. Decoupled Regularization Losses Lcons and Leon
To enforce the specific logic of "divide and conquer" scheme, introduce pair of comple- mentary regularization losses that act as a "push-pull" mechanism.
The Bipartite Consistency Loss Leons of the conflict color within the topologically simple bipartite regions, Maip = {i E Ω Y Disco E
the "pull" force. penalizes the erroneous prediction
{I...., 1}}. Its objective ensure the sparsity and targeted use the conflict class.
Leons Econs(Pootor (Pootor, Mbip) = ((o (Pootor (1))
(7)
Conversely, the Conflic Resolution Loss L acts as the "push" force. It rewards high-confidence predictions for the conflict class within the regions of topological conflict, Meonf {i E Q Disco ensuring these crucial signals are not suppressed.
Lcon (Poooor Moong) Mog [[1 (Peotor (1)))
(8)
3. Adjacency Constraint Loss Ludj for Implicit Disambiguation
This is the cornerstone of our "Implicit Disambiguation" mechanism. designed to resolve the the- oretical limitations discrete labels in secondary conflict regions. It operates on the continuous feature manifold of the network's 'ss output, transforming an ill- ill-posed discrete problem into a well- posed feature separation problem.
Let 8ę denote the set of pixel coordinates for instance k. We first define the mean probability vector for this instance, P(s)) E IR++1 as the average of the softmax probability vectors over all its pixels:
P(sx) Epes. (P (p))]
This vector represents the instance's average feature embedding in the probability space.
The Adjacency Constraint Loss (Ladj) then defined as a global potential function over all edges E in the Cell Adjacency Graph G. aims maximize the angular separation between the feature representations of adjacent instances by minimizing their cosine similarity.
P(s.) P(xj) P((s)) l (1((())
Ludj (P Peotorr: G)
Σ
(10)
E
(OL,))EE
where ||- ||2 denotes the L2 norm (Euclidean norm) of a vector, and is a small constant 10-6 for numerical stability.
This loss provides powerful counteracting gradient the primary classification objective. In sec- ondary conflict regions, where Lector drives two adjacent instances towards the same discrete class t, Lodj forces their continuous representations apart by compelling the network to learn different ac- tivation patterns in the secondary channels (c E {1, ..., 1}). Conceptually, this can be interpreted as a form of supervised contrastive loss, where the graph adjacency defines negative pairs that must be repelled in the feature space. This mechanism ensures that even instances with ambiguous dis- crete labels become separable on the learned feature manifold, which critical for accurate instance reconstruction in topologically complex regions.
19

---

Published as a conference paper at ICLR 2026
A.6 THE GBC-FS 2025 HIGH-DENSITY CASE STUDY DATASET
This section provides a comprehensive description of the GBC-FS 2025 (GallBladder Cancer Frozen Section 2025) dataset, which was constructed and first introduced in this study. We detail the clinical motivation, data curation process, key characteristics, and its potential impact on the field.
A.6.1 THE CRITICAL GAP IN HIGH-DENCE PATHOLOGY SEGMENTATION
Gallbladder cancer (GBC) is the most common biliary tract malignancy, accounting for 80-95% of cases, and ranks among the major digestive system cancers. Due to its insidious onset and lack of specific early symptoms, most patients are diagnosed at an advanced stage, resulting in extremely poor prognosis: the 5-year survival rate for metastatic disease is below 5%, with a median survival often under 6 months. This reality highlights the urgent need for high-quality, cell- and subcellular- level quantitative analysis to enable breakthroughs in early pathological feature identification, im- mune infiltration analysis, and spatial heterogeneity characterization.
However, the histological features of GBC pose formidable challenges. Tumor cells often form com- pact nests with ambiguous boundaries, while immune responses induce dense lymphocyte clusters and tertiary lymphoid structures (TLS) at the tumor periphery, creating regions of extreme density and overlap. these areas, conventional cell segmentation approaches frequently fail, leading to downstream biases such as distorted immune infiltration assessment and unreliable biomarker dis- covery.
Existing public datasets (e.g., MoNuSeg, PanNuke, Lizard/CoNIC), though valuable, centered on more common cancers and lack sub-nuclear granularity. As result, mainstream models gener- alize poorly to highly dense and complex tissues like GBC. The GBC-FS 2025 dataset was created to explicitly fill this gap, providing the first large-scale, sub-nuclear annotated benchmark on frozen sections of gallbladder cancer.
A.6.2 DATASET CURATION AND SUB-CELLULAR ANNOTATION
(1) Data Source: The 2,839 256 256 images in the GBC-FS 2025 dataset originate from a single whole-slide image (WSI) of gallbladder cancer frozen section, obtained from 71-year-old female with Stage IVB adenocarcinoma. Frozen sections inherently exhibit uneven staining, ice-crystal ar- tifacts, tissue distortion, and blurred or incomplete nuclear membranes, making reliable cell-level nuclear annotation infeasible. Therefore, instead annotating individual cells, which cannot be consistently identified under such conditions, focus annotating the chromatin -ikttin--ikke dense sub- cellular aggregates that remain visually stable and reproducible. The complete WSI data of the remaining patients will also be released later.
(2) Annotation Methodology: All instances were manually delineated by four annotators with ba- sic morphological training using QuPath (v0.5.1) software, and were reviewed by a Ph.D. with pathology background. For regions with significant ambiguity, a pathologist was consulted for lim- ited sample verification confirm that the overall annotation direction was consistent with the basic morphological features of frozen sections. Additionally, our annotation target was "chromatin like dense sub-cellular structures" as visual primitives, as these structures are more consistently identi- fiable in noisy frozen sections than complete nuclei. This was a deliberate choice aimed at creating a benchmark that reflects the true visual challenges of this data modality, rather than approximating cleaner, FFPE-style annotations.
Given the inherent ambiguity of boundaries in frozen sections, we adopted a multi-round expert review process, which is more suitable for this scenario than traditional IoU/Dice metrics. Annotations were completed by junior annotators and then reviewed by a Ph.D. with a pathology background. Any uncertain regions were marked and then adjudicated by senior team members, with a few difficult cases submitted to a pathologist for sample inspection.
(3) Quality Control:
(4) Tissue Composition: A pathologist-guidd regional assessment indicates that the dataset is com- posed of approximately 89.69% cancer cell regions, 6.1 111% 1% fibroblast regions, and 4.20% immune cell regions.
The dataset carries practical significance on three fronts. Biologically, it facilitates exploration of di- viding nuclei and nuclear fragmentation, enabling quantification of heterogeneity and multipolarity
20

---

Published as a conference paper at ICLR 2026
Table 8: Overview of the datasets used in our experiments. FFPE denotes formalin-fixed paraflin- embedded, while FS denotes frozen section.
Total Annotated
Avg. Cells
Dataset
Imaging Modality
Tissue Processing
Total Patches
Instances
per Patch
PanNuke
H&E, Bright-field
FFPE
7901
189,744
20.92
DSB2018
Fluorescence
FFPE
670
29,443
43.94
CryoNuSeg
H&E, Bright-field
FS
120
8,178
68.15
GBC-FS 2025
H&F, Bright-field
FS
2839
864,204
304.44
that inform tumor aggressiveness and prognosis. Algorithmically, sub-nuclear annotations provide finer-grained supervisory signals than traditional cell-level labels, enhancing robustness in dense, overlapping, and morphologically complex regions, and serving as an ideal dataset for stress-testing segmentation models. Clinically, sub-nuclear delineations not only benchmark nucleus segmenta- tion but also inform cell-segmentation preprocessing, as aggregating nuclear units can approximate whole-cell boundaries, thereby supporting immune infiltration analysis, tumor grading, and progno- sis assessment.
A.6.3 KEY CHARACTERISTICS AND COMPARISON WITH EXISTING DATASETS
GBC-FS 2025 is distinguished from existing datasets not only by its focus on a rare and challenging cancer type but, more importantly, by its unprecedented topological complexity and sub-nucleat annotation granularity. To contextualize its unique properties, we provide a direct comparison with the other datasets used in this study in Table 8.
As the table clearly illustrates, GBC-FS 2025 sits at the extreme end of the "topological complex- ity spectrum." It exhibits by far the highest average instance density, with 304.44 instances per patch-mon more than four times that of the next densest dataset, CryoNuSeg. This extreme density is the primary driver of its complex graph structures, which we analyzed in the main paper (Section 3). A staggering 30.49% of its cell nodes are classified as conflict nodes, and 24.64% are involved in secondary conflicts, figures that are an order of magnitude higher than those of other public bench- marks.
This unique combination of massive scale (over 860k instances) and extreme topological complexity makes GBC-FS 2025 an indispensable resource for the field. It serves crucial complement to existing datasets by providing a much-needed benchmark for the most challenging. high-density segmentation scenarios, enabling the development and rigorous stress- stress-testing of robust, topology- aware algorithms like our proposed Disco.
A.7 SUPPLEMENTARY QUALITATIVE RESULTS
To provide of our Disco framework, we present in Figure A.3 an extensive gallery of qualitative segmentation results across the four datasets. This figure showcases Disco's performance in wide variety of chal- lenging scenarios, highlighting its consistent accuracy across different imaging modalities, staining techniques, cell morphologies. and densities.
comprehensive visual testament to the robustness and generalization capability
These visualizations demonstrate Disco's remarkable ability to adapt to vastly different visual do- mains, performing equally well bright-field H& images and fluorescence mieroscopy images. Furthermore, it successfully handles the entire spectrum of cell densities, from sparse ar- rangements extremely dense and cluttered environments. In highly challenging regions, Disco consistently generates instance masks that are highly concordant with the ground truth, accurately delineating irregular shapes and separating tightly clustered cells.
A particularly noteworthy observation is showcased in cases with known incomplete annotations. Our Disco method, trained only on the available labels, exhibits a powerful generalization capabil- ity: it successfully identifies and segments numerous sub-cellular nuclei that were entirely absent from the ground truth annotation. This can be clearly observed by comparing the Disco (ours) row with the Ground Truth row in the corresponding panels, where our method correctly delineates many additional, valid instances. This "gap- "gap-filling" ability underscores the robustness of the learned topological priors and highlights Disco's future potential in sepi-super or weakly-supervised
21

---

Published as a conference paper at ICLR 2026
Table Computational cost comparison. Params denotes model parameters. FLOPs are calculated for 256 x 256 input. FPS denotes frames per second during inference.
Method
Backbone
Source
Paras
FLOPs
FPS
HoverNet
ResNet-50
MIA 2019
49.70M
192.70G
12.4
FCIS
Swin-Unet
ICML 2025
48.23M
66.37G
28.5
Disco
Swin-Unet
Ours
46.84M
65.21G
29.2
learning scenarios, significantly enhancing its practical utility in real-world applications where ex- haustive annotation is often infeasible.
A.8 COMPARISON OF COMPUTATIONAL EFFICIENCY
Our analysis confirms that the graph-based components of our method (CAG construction, BFS labeling) are one-time, offine preprocessing steps and introduce additional overhead during in- ference. The inference speed is therefore determined solely by the neural network's ' architecture and post-processing.
To ensure a fair comparison of inference efficiency, we benchmarked all models on a single NVIDIA RTX 4090 GPU with 256 256 inputs. The results are summarized in Table 9.
The results clearly demonstrate the high efficiency of our Disco framework. Disco achieves an inference speed of 29.2 FPS, which is not only highly competitive but also slightly faster than the strong graph-based baseline, FCIS (28.5 FPS). Furthermore, it is more than twice as fast as methods like HoverNet that rely on computationally intensive post-proue prospprcc..sng.
Notably, even with its sophisticated dual-branch head and decoupled loss system, our Disco model more parameter-efficien than FCIS (46.84M vs. 48.23M) and has lower computational load (65.21G vs. 66.37G FLOPs). These results irrefutably demonstrate that Disco achieves its state-of- the-art accuracy not by adding significant computational complexity, but through more efficient and targeted learning strategy. Our method successfully improves performance without sacrificing, and in some cases even improving upon, practical computational efficiency. A.9 COMPARISON BETWEEN Xadj AND NONADILOSS
While NonAdjLoss Ganaye et al. (2019) and our 'adj share a conceptual similarity-bote leverage predefined adjacency graph to penalize undesired relationships in the network's 's output output-their their ob- jectives, mechanisms, and application domains are fundamentally different, which in turn highlights the uniqueness of our method.
(1) Fundamentally Different Objectives. The objective of NonAdjLoss is semantic-level cor- rectness, aimed enforcing anatomical consistency by preventing impossible adjacencies between different semantic classes. It is loss that promotes regional purity and semantic correctness. In contrast, the objective of Audj is instance-level discriminability, aimed enforcing feature dis- similarity between different instances within the same semantic class. The former promotes regional purity, while the latter promotes instance separability.
(2) Different Operational Mechanisms. NonAdjLoss operates at the pixel level, penalizing the simultaneous occurrence of forbidden class probabilities within a local neighborhood. Our Aadj- however, is form of supervised contrastive loss that operates at the instance level. It first abstracts each instance into a mean feature vector, then treats the edges the adjacency graph as defining "negative pairs," and directly minimizes the feature similarity of these pairs This mechanism of enforcing the separation of the feature manifold at the instance level, based on contrastive learning, not present in NonAdjLoss.
(3) Distinct Application Domains and Problems Solved. NonAdjLoss addresses the problem of "topologically incorrect semantic layouts." Our Xadj addresses the problem of "ambiguous instance identity dense clusters," particularly the "secondary conflict" challenge, which is a unique issue in graph-coloring- baased instance segmentation.
In summary, although both methods use an adjacency graph, they are applied to solve problems of two entirely different dimensions and employ fundamentally distinct mechanisms. NonAdjLoss
22

---

Published as a conference paper at ICLR 2026
Original Image
Disco Ground Truth
Original Image
Ground Truth
Disco
Original Image
Ground Truth
Disco (ours)
Figure A.3. A gallery of qualitative segmentation results from our Disco method on the four datasets. For each dataset block, the top row displays the original input images, the middle row shows the corresponding ground truth instance masks, and the bottom row presents our Disco's 's final segmentation predictions, For clarity, all instance masks are visualized with random colors.
23

---

Published as a conference paper at ICLR 2026
Table 10: Fair comparison of different coloring strategies GBC-FS 2025.
Method
DICE
AJI
DQ
SQ
PQ
Greedy 3-Coloring
0.7528
0,4594
0,5838
0.6971
0.4122
FCIS
0.7785
0.4518
0.5857
0.7068
0.4379
Disco
0.8137
0.5209
0.6795
0.7486
0.5087
ensures that different classes do not touch when they should not, whereas our Aadj ensures that different instances of the same class have separable features when they do touch.
A.10 FAIR COMPARISON OF DIFFERENT COLORING STRATEGIES
Our (2+1) scheme, while seemingly creating intermediate ambiguity, constitutes superior, more efficient, and more "dynamically adaptive" learning paradigm compared to a static, greedy 3-coloring that always uses three colors. Our rationale is twofold.
(1) is a dynamically adaptive and more efficient labeling strategy. A standard greedy 3- coloring algorithm will always attempt to three colors, regardless of whether the input graph is simple or complex. In contrast, our "Explicit Marking" algorithm is dynamically adaptive. When faced with simple, bipartite cell graph (such in the PanNuke dataset), cally degenerates into an optimal 2-coloring scheme, using only two colors and completely avoiding the introduction of third. It only "activates" and introduces the dedicated conflict color when detects an unavoidable topological conflict in the graph. This "on-deman allocation" strategy is not only more elegant in theory but also provides the network with more concise supervisory sig- nal that adheres to the "Occam's razor" principle, avoiding representational redundancy in simple scenarios.
algorithm automati-
(2) It drives more robust feature learning. The "label ambiguity" is a deliberate design choice that, when coupled with our Xadj, creates a constructive tension that drives the learning of a more robust feature manifold. A clean 3-coloring supervision would only require the network to learn to mimic discrete labels. Our (2+1) scheme, however, compels the model to resolve the conflict between the coloring loss and the adjacency loss by utilizing secondary feature dimensions, thereby learning truly separable, topologically-awve aawaee feature representation.
To empirically validate this argument, conducted relevant ablation study. We performed an experimental validation on the GBC-FS 2025 dataset, comparing our Disco method with a standard greedy 3-coloring method and the FCIS method. The results, shown in Table 10, demonstrate that our Disco framework, with its "Explicit Marking + Implicit Disambiguation" strategy. significantly outperforms the models trained clean, unambiguous 3-color and 4-color labels. This substantial performance gap provides strong empirical evidence that our seemingly "roundabout" design is, in fact, more effective learning strategy that guides the model more robust and precise solution.
24


Reviews:
[{"review_id": "Gi7sRPO8oz", "reviewer": "Reviewer_LVtp", "summary": "In this work, the authors deal with dense cell instance segmentation in histopathology images. They introduce a new dataset, analyze bipartite nature of 4 datasets, and propose DISCO, a divide and conquer approach for the segmentation task.", "questions": "Please see the weakness section. I am willing to increase the score after seeing authors' rebuttal and discussing with other reviewers.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This is the first study revealing that non-bipartite is actually more prevalent in cell datasets, and hence the need for more sophisticated methods aside from 2-coloring or 4-coloring approaches. The authors provide statistics on percentage of bipartite nodes, conflict nodes, and that 3-cycles are more prevalent among the odd-length cycles.\n- The authors perform adequate experiments, in terms of 4 datasets, several recent and relevant baselines and ablation studies. Their method is usually either the best or second-best in performance.", "weaknesses": "- The actual method doesn't seem very novel, as BFS exists in literature, and forcing adjacent nodes to have different feature representation is common\n- The authors do not provide standard deviation in the results. The mean numbers seem very close to baselines. t-test needs to be done to determine if the results are statistically significant or not.\n- Authors need to provide inference run-times. Because constructing the graph and performing BFS can be time-consuming.\n- Hyperparameter tuning: Authors need to provide results of different hyperparameter values (such as loss weights) to understand sensitivity of each term.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "S6fdoptFm1", "reviewer": "Reviewer_cFuN", "summary": "This paper addresses cell instance segmentation in dense, overlapping regions by reformulating the problem through graph coloring theory. The authors present three main contributions:\n\nDataset: GBC-FS 2025 (Gallbladder Cancer Frozen Section), comprising 2,839 H&E-stained frozen section images with 864,204 manually annotated sub-cellular nuclei instances. This represents a 40× scale increase over CryoNuSeg, and addresses a critical gap for intraoperative diagnosis algorithms.\n\nTopological Analysis: A systematic cross-dataset study of cell adjacency graph (CAG) properties across four benchmarks is presented. The authors construct CAGs where nodes represent cell instances and edges represent 8-connected spatial adjacency. Key findings include: (1) PanNuke is 100% bipartite while DSB2018 (1.99%), CryoNuSeg (5.64%), and GBC-FS 2025 (30.49%) contain increasing proportions of conflict nodes that violate bipartite structure; (2) Among non-bipartite components, 90.51-98.12% of odd-length cycles are 3-cycles (triangles), with GBC-FS 2025 showing 24.64% secondary conflict nodes (adjacent conflict nodes). \n\nMethod: DISCO employs a \"divide and conquer\" strategy with two core mechanisms. \"Explicit Marking\" uses BFS-based graph decomposition to extract the maximal bipartite subgraph, partitioning cells into two primary colors (V₁, V₂) and consolidating remaining non-bipartite nodes into a conflict set (Vconf) assigned a third color. This generates a (t+1)-value ground truth map where t=3. \"Implicit Disambiguation\" introduces an adjacency constraint loss (L_adj) that minimizes cosine similarity between mean probability vectors of adjacent instances, forcing the model to learn angularly separated representations in probability space. The total loss combines semantic segmentation (L_sem), weighted coloring (L_color), bipartite consistency (L_cons), conflict resolution (L_conf), and adjacency constraints (L_adj). At inference, instances are reconstructed by grouping connected components with identical color predictions.\n\nResults: DISCO achieves PQ of 62.71% on PanNuke (+1.62% vs FCIS), 77.81% on DSB2018 (+0.42%), 59.70% on CryoNuSeg (+1.77%), and 50.87% on GBC-FS 2025 (+7.08%), representing an average 2.72% improvement across benchmarks. Ablations demonstrate the adjacency constraint loss contributes ~6% absolute PQ improvement (42.57% → 48.26%) on GBC-FS 2025.", "questions": "See weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Compelling topology evidence. Cross‑dataset analysis shows frequent odd cycles with >90% of odd cycles being triangles in non‑bipartite graphs; conflict/secondary‑conflict ratios quantify difficulty (Table 1, p. 2; Fig. 3b, p. 5).\n\nClean “2 + 1” design. Explicit Marking extracts a large bipartite backbone and pools the rest into a conflict set; Implicit Disambiguation resolves label ambiguity via 𝐿_adj over CAG edges (Sec. 4.2–4.3; Eqs. 1–3, pp. 6–7).\n\nGraph‑aware loss that works. Ablations show 𝐿_adj alone adds ~+6 PQ on GBC‑FS 2025; the full system achieves PQ = 0.5087 (Table 7; Table 5, p. 9).\n\nState‑of‑the‑art on dense regime. Disco surpasses FCIS by +7.08 PQ on GBC‑FS 2025 and improves AJI/DQ/SQ concurrently (Table 5, p. 9); visuals highlight separation in dense clusters (Fig. 7, p. 8).\n\nHigh‑value dataset. GBC‑FS 2025: 2,839 patches, ~304 instances/patch on average, 864k+ sub‑nuclear instances; orders‑of‑magnitude denser than public sets (Sec. 5.1; App. A.6; Table 8, p. 20).\n\nReproducibility intent. Code and dataset release promised (Reproducibility Statement, p. 10).", "weaknesses": "1. Is there a formal definition of \"dense\" and \"complex\" cells for segmentation analysis? If no, can the authors quantify this aspect of the data to define \"highly dense\" cell segmentation?\n\n2. \"First Topological Analysis\" claim is overstated: The repeated assertion of conducting the \"first systematic topological analysis\" of cell adjacency graphs appears throughout the paper: This claim is incorrect given extensive prior work: Topological Tumor Graphs (Failmezger et al., Cancer Research 2020), Ceograph (Wang et al., Nature Communications 2023), HistoCartography (Pati et al., Medical Image Analysis 2021), CellSpatialGraph (Chen et al., 2022, Software Impacts Journal), SpaGCN (Hu et al., Nature Methods 2021), GraphST (Long et al., Nature Communications 2023), etc. Thus, there are several  graph-based topological analysis papers on cell spatial arrangements.\n\t\nHowever, the proposed specific analysis of chromatic numbers, bipartite versus non-bipartite classification, odd-cycle length distributions, conflict node ratios, and secondary conflict prevalence seem novel to this manuscript..Thus, the contribution seems \"first systematic analysis of chromatic properties and graph coloring characteristics in cell adjacency graphs\" not \"first topological analysis.\"\n\nThe authors should consider adding a new paragraph in Introduction acknowledging: \"While graph-based analysis of cell spatial arrangements is well-established in computational pathology [cite TTG, Ceograph, HistoCartography] and spatial transcriptomics [cite SpaGCN, GraphST], prior work has focused on node centrality, clustering, and GNN-based prediction rather than graph coloring characteristics. To our knowledge, this is the first systematic study of chromatic properties…”. Also, the abstract calls the predicted “Conflict Map” an “unsupervised tool”, though conflict labels for training are produced from GT via Explicit Marking; wording may mislead (Abstract, p. 1).\n\n3.  Missing Critical Citation: The adjacency constraint loss (Section 4.3, Equation 3, L_adj) has very close conceptual precedent that must be cited and differentiated: NonAdjLoss (Ganaye et al., \"Removing segmentation inconsistencies with semi-supervised non-adjacency constraint\", in Medical Image Analysis 2019). Both NonAdjLoss and the proposed method use adjacency graphs to penalize unwanted relationships. The paper should provide explicit technical comparison, with NonAdjLoss, discussing this conceptual similarity and explaining how instance disambiguation loss differs from anatomical consistency loss beyond just the application domain.\n\n4. Insufficient Comparison with FCIS (ICML 2025): FCIS (Zhang et al., \"The Four Color Theorem for Cell Instance Segmentation,\" ICML 2025, arXiv:2506.09724) is the most directly comparable concurrent work and requires deep technical comparison.\n\nWhy is divide-and-conquer superior to direct 4-color prediction? The paper shows DISCO outperforms FCIS on GBC-FS 2025 (+6.91% AJI) but provides no explanation of why the proposed divide-and-conquer is superior to direct 4-color prediction in FCIS?\n\nComputational efficiency comparison is missing. FCIS claims efficiency advantages by reducing to semantic segmentation. Does DISCO maintain or sacrifice efficiency for accuracy? Need: training time, inference speed (FPS), memory requirements, FLOPs comparison.\n\nWould FCIS-style encoding work on GBC-FS 2025? A critical ablation would be testing uniform 4-color prediction (FCIS approach) with DISCO's backbone and training procedure on GBC-FS 2025. This would isolate whether improvements come from divide-and-conquer versus other factors (architecture choices, training hyperparameters, etc.).\n\n5. Incomplete Dataset Documentation: GBC-FS 2025 is a strong contribution but lacks essential documentation that limits its utility.\n\nTissue Composition: What proportions are:\n* Tumor tissue (epithelial cancer cells)?\n* Stroma (fibroblasts, extracellular matrix)?\n* Inflammatory infiltrate (lymphocytes, macrophages)?\n* Necrotic regions?\n* Normal tissue?\n\nThis matters because algorithm performance varies dramatically across tissue types. Methods optimized for dense tumor nests may fail on sparse inflammatory regions.\n\nSource Data:\n* How many whole slide images (WSIs) produced the 2,839 patches?\n* How many patients?\n* What is patient-level diversity (age range, disease stage, tumor grade)?\nAnnotation Methodology:\n* Manual pixel-wise annotation by pathologists? How many pathologists?\n* Crowdsourcing platform (like NuCLS using novel protocols for 220K+ annotations)?\n* Semi-automated pipeline (like SNOW using HoVer-Net on StyleGAN2-ADA synthetic images)?\n* What annotation tools/software?\n* What is annotation time per image?\nQuality Control:\n* Inter-annotator agreement metrics (Dice scores, IoU between multiple annotators)?\n* How was consensus achieved for disagreements?\n* What validation ensured correct capture of sub-cellular nuclei versus artifacts?\n* What percentage of annotations required adjudication?\nQuantitative Density Metrics:\n* Cells per mm² (accounting for magnification)?\n* Percentage of overlapping/touching cells?\n* Distribution of neighbor counts quantitatively?\n* Comparison to other datasets' density metrics?\nThe paper reports 304.44 cells per 256×256 patch but doesn't translate to physical density or overlap percentage.\n\n6. No Computational Cost Analysis Prevents Efficiency Assessment, the paper reports no computational metrics:\n* Training time (hours to convergence)?\n* Inference speed (FPS, seconds per image)?\n* Memory requirements (peak GPU memory during training/inference)?\n* Model size (number of parameters)?\n* FLOPs per forward pass?\n\n7. Missing Biological Interpretation of Triangle Dominance Finding: The 90.51-98.12% triangle dominance in odd cycles is potentially the most interesting finding but lacks biological grounding. Why would cell packing favour triangles? Why not hexagonal packing for epithelial cells? Are these findings consistent across FFPE and frozen sections?\n\n8. Limited Baseline Coverage Missing Recent Methods: The baseline selection is good but misses most recent methods representing 2024-2025 state-of-the-art such as CellSAM (Israel et al., bioRxiv 2023.11.17.567630), Cell-TRACTR (O'Connor & Dunlop, PLOS Computational Biology 2025, 21(5), e1013071), and SwinCell (Zhang et al., Communications Biology 2025, 8, 962).\n\n9. Missing Statistical Analysis: No error bars, confidence intervals, or standard deviations and no significance testing (t-tests, Wilcoxon tests across images) reported.\n\n10. Missing Failure Case Analysis: Are there cases where graph colouring fails? May be for FFPE → frozen section transfer? H&E → fluorescence transfer? Trained on one organ, tested on another? Different scanners/staining protocols?\n\n11. Decoding unspecified: “Topological decoding” is mentioned but not detailed: how per‑pixel colors are converted into final instances (connectivity, merging/splitting, conflict assignment) is unclear (Fig. 1d, p. 2)\n\n12. Explicit Marking under‑specified: The BFS‑based conflict labeling heuristic lacks tie‑breaking rules for overlapping odd cycles and complexity bounds, though supervision hinges on it (Sec. 4.2, p. 6; Fig. 5).\n\n13. Adjacency sensitivity: CAG edges rely on 3×3 dilation (8‑connectivity) (Def. 1, p. 3); there’s no ablation for kernel size/shape or alternative proximity rules, which can alter odd‑cycle counts and conflict sets.\n\n14. Figure 4 captions is very abstract and does not provide an overview of the proposed method. Could that be revised?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BORpKxuOuH", "reviewer": "Reviewer_72eb", "summary": "This paper addresses the instance segmentation of dense, overlapping cells in pathology images. The authors present three main contributions: 1) A systematic, quantitative topological analysis of Cell Adjacency Graphs (CAGs) across four datasets, finding that real-world cell graphs are non-bipartite, dominated by 3-cycles, and empirically have a chromatic number $\\chi(G)$ that is almost always 3. 2) The release of a new, large-scale, high-density dataset, GBC-FS 2025, which features unique \"sub-nuclear\" level annotations. 3) A proposed segmentation framework, Disco, which uses a \"divide and conquer\" (2+1) coloring strategy (\"Explicit Marking\") and an \"Implicit Disambiguation\" mechanism ($\\mathcal{L}_{adj}$ loss) to handle topological conflicts.", "questions": "1. Given your own empirical evidence (Appendix A.4.2) that $\\chi(G)=3$ is almost always sufficient, why did you opt for the (2+1) \"Explicit Marking\" strategy, which creates label ambiguity, instead of using a standard, unambiguous greedy 3-coloring algorithm (as shown in your Appendix A.1(d)) as the supervisory signal?\n\n2. How can you decouple the performance gains on GBC-FS 2025 from the unique \"sub-nuclear\" task definition to prove that Disco's advantage truly stems from its topological handling capabilities? Did you consider an ablation study where you merge the \"sub-nuclear\" annotations into standard \"nucleus\" annotations to conduct a fair comparison?\n\n3. The ablation study (Table 7) shows that $\\mathcal{L}_{adj}$ provides a massive ~6% PQ boost. In light of \"Weakness 1,\" does this not simply prove that $\\mathcal{L}_{adj}$ is highly effective at resolving the specific label ambiguity you introduced, rather than proving it is a generally superior mechanism for handling topological conflicts compared to a clean 3-color supervision?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper provides the first systematic quantitative topological analysis of CAGs. Its key finding (that real-world cell graphs are non-bipartite, 3-cycle dominant, and empirically have $\\chi(G)=3$) provides a solid empirical foundation for the graph-coloring paradigm in this field. This analysis moves beyond simple theoretical assumptions (e.g., bipartiteness or the 4-color theorem) and points toward designing more efficient, targeted models.\n\n2. The release of the GBC-FS 2025 dataset is a contribution. Its extremely high instance density (avg. 304.44/patch) and unique \"sub-nuclear\" annotation granularity provide a novel, highly challenging benchmark for the community, filling a gap left by existing datasets in extremely dense scenarios.", "weaknesses": "1. The (2+1) \"Explicit Marking\" strategy of Disco is logically flawed. The authors' own analysis (Appendix A.4.2) clearly states that an empirical chromatic number of $\\chi(G)=3$ is almost always sufficient. However, instead of generating an unambiguous 3-color label (as shown in Appendix A.1(d)), the authors' strategy lumps all conflicting nodes—regardless of adjacency—into the same conflict class ($c=t=3$). This artificially creates \"secondary conflicts\" at the label level (i.e., two adjacent conflict nodes are assigned the same ground-truth label). Consequently, the \"Implicit Disambiguation\" mechanism (especially the $\\mathcal{L}_{adj}$ loss) appears to be a complex solution to an avoidable problem introduced by the labeling strategy itself. This is an unnecessarily convoluted design.\n\n2. The method's most significant performance gain (a 7.08% PQ improvement) is reported on the authors' own GBC-FS 2025 dataset. However, as described in Appendix A.6.2, this dataset uses \"sub-nuclear instances\" for annotation. This is a fundamentally different task from the \"nucleus segmentation\" task in benchmarks like PanNuke and DSB2018. This \"apples-to-oranges\" comparison invalidates the claim of superior performance. Is Disco's superiority on GBC-FS 2025 attributable to its superior handling of complex topology, or is it simply better at learning this specific and unusual \"sub-nuclear segmentation\" task? This ambiguity in task definition severely weakens the paper's central claims about its topological robustness.\n\n3. The abstract claims that the effectiveness of the graph coloring paradigm \"has not been verified\" in real-world scenarios. This is inaccurate and contradicts Section 2.2, which acknowledges the \"pioneering work of FCIS (2025c)\" demonstrating the \"potential of a universal 4-coloring model.\" The paper's topological contribution is the quantification of 3-cycle prevalence, not the novel discovery of non-bipartite structures (which is already implied by FCIS's 4-coloring). This framing exaggerates the paper's novelty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k3rl362Y72", "reviewer": "Reviewer_SvPT", "summary": "This paper presents DISCO, an effective framework for dense cell instance segmentation with detailed theoretically analysis. The authors identify the lack of global topological awareness in existing methods, and provide solution by graph coloring theory. \nThrough the introduction of a new GBC-FS 2025 dataset and a systematic cross-dataset topological analysis, the authors show that cell adjacency graphs are predominantly non-bipartite with a high density of odd-length cycles.  DISCO addresses the challenge by the proposed explicit marking and implicit disambiguation mechanism.\nComprehensive experiments across four datasets demonstrate consistent and significant gains, with qualitative visualizations and detailed ablations further verify Disco's effectiveness.", "questions": "1. Could the authors provide quantitative evidence (e.g., runtime, GPU memory usage) to support the claim that DISCO is more efficient than FCIS, particularly given its additional loss terms and graph computations?\n\n2. Do the authors plan to fully open-source the GBC-FS dataset and the complete DISCO implementation after the review phase? \n\n3. Can the authors offer theoretical insights or proofs regarding the efficiency or convergence of DISCO?\n\n4. Have the authors considered comparing DISCO to GNN-based instance segmentation or relational reasoning methods?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1.The authors construct a large-scale GBC-FS 2025 benchmark which contains highly complex and dense sub cellular structures. The also report the comparisons of recent models on the benchmark. \n\n2.The paper conduct systematic, quantitative analysis of the complex topology of cell adjacency graphs and reveal their inherent non-bipartite nature. They also establish a clear conceptual shift from local geometric modeling to global topological reasoning for instance segmentation.\n\n3.The “divide and conquer” strategy handles bipartite regions efficiently while explicitly modeling non-bipartite conflict clusters. The integration of “Explicit Marking” and “Implicit Disambiguation” aligns well align with the theoretical analysis.", "weaknesses": "1. The method introduces multiple loss components and graph-based computations. Although training settings are reported, there is limited discussion or empirical evidence regarding runtime and memory overhead compared to baselines such as FCIS or HoverNet. This omission is particularly notable since the paper highlights DISCO’s efficiency advantage over FCIS.\n\n2. While the topological observations are empirically sound, the paper stops short of providing formal theoretical bounds or proofs. Incorporating theoretical justification such as convergence analysis or expected bounds would enhance the rigor and clarity of the claims.\n\n3. It would be beneficial to discuss or empirically compare against recent GNN-based segmentation or relational reasoning approaches. This would help contextualize the novelty and positioning of the proposed framework within the broader landscape of graph-based learning methods.\n\n4. Although the paper provides an anonymous repository, the released materials currently lack full access to the proposed GBC-FS dataset and the complete implementation of DISCO. This incomplete release raises concerns about reproducibility. It would be helpful to clarify whether the dataset and code will be fully released upon publication, as stated in the reproducibility section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)