Unsupervised Hierarchy-Agnostic Segmentation: Parsing Semantic Image Structure

Authors: simone  rossetti
fiora  pirri
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:11:45

Abstract: Unsupervised semantic segmentation aims to discover groupings within images, capturing objects' view-invariance without external supervision. This task is inherently ambiguous due to the variable levels of granularity in natural groups. Existing methods often bypass this ambiguity using dataset-specific priors. In our research, we address this ambiguity head-on and provide a universal tool for pixel-level semantic parsing of images guided by the latent representations encoded in self-supervised models. 
We introduce a novel algebraic methodology that recursively identifies latent semantic regions, dynamically estimates the number of components, and ensures smoothness in the partitioning process. 
The innovative approach identifies scene-conditioned primitives within a dataset and creates a hierarchy-agnostic semantic regions tree of the image pixels. 
The model captures fine and coarse semantic details, producing a nuanced and unbiased segmentation. 
We present a new metric for estimating the quality of the semantic segmentation of discovered elements on different levels of the hierarchy. The metric validates the intrinsic nature of the compositional relations among parts, objects, and scenes in a hierarchy-agnostic domain. Our results prove the power of this methodology, uncovering semantic regions without prior definitions and scaling effectively across various datasets. This robust framework for unsupervised image segmentation proves more accurate semantic hierarchical relationships between scene elements than traditional algorithms. The experiments underscore its potential for broad applicability in image analysis tasks, showcasing its ability to deliver a detailed and unbiased segmentation that surpasses existing unsupervised methods.

Main paper: 
 introduction: 
 The advancement of image segmentation has recently taken significant steps forward. On the one hand, the foundation models are trained on increasingly large datasets, such as CLIPseg [57] (CLIP [67] ), SAM [48] , and SEEM [97] , supervised by text and human prompts [92] . On the other hand, there is a rising growth of unsupervised segmentation models. Unsupervised segmentation explores the feature hierarchy by leveraging self-supervised contrastive learning, as in SmooSeg [51] , U2Seg [62] , CUTLer [87] , CuVLER [5] , STEGO [32] , ACSeg [52] , FreeSolo [85] , HSG [44] , Trans-Fgu [90] , DeepCut [3] , and others [77, 58, 96, 86, 33, 17] . Unsupervised models discover and localize image categories with no annotation aid and evaluate the quality of the pseudo-masks they predict on the datasets corpora used for testing, such as COCO-Stuff [10] and Cityscapes [21] . Despite exploring human perception more closely than the foundation models, they still rely on the linguistic and conceptual relations between the images and their annotations.Curated datasets, such as ImageNet [50] , PascalVOC [27] , or MSCOCO [53] , show an extraordinary number of objects with all their components and particulars not annotated either at the image level Figure 1 : Unsupervised hierarchy-agnostic segmentation. Finer image parts are generated via over-clustering, each region colour-coded randomly. Our algorithm recursively partitions these parts, grouping them into coarser regions across multiple levels of granularity. The resulting tree represents an unsupervised hierarchical semantic segmentation. The arrangement of regions in the tree reflects their semantic distance, which is colour-coded in the heat map shown on the right. or densely. Why annotate this and not that? Annotation prejudice creates a bias towards a subset of the scene. Unsupervised learning, in contrast, has the potential to generate richer representations that are not restrained by annotation decisions. Without juggling annotations, unsupervised features (e.g. [64] ) nearly mirror visual perception discovering scene parts and details; indeed, feature cues live in nested context levels and are not necessarily verbalisable [76, 66] , as opposed to the Gestalt holistic view [83] .Following previous research [44, 19, 3, 94] , our key idea is that the natural hierarchical structure of visual scenes is an essential attribute that we can actively pursue in unsupervised segmentation. We approach unsupervised semantic segmentation as an unsupervised pixel-wise feature learning problem, discretising the hierarchical semantic knowledge yielded by self-supervised learning. Our approach makes no assumption about the number of semantic granularity levels and the number of partitions in each level as in [44] . We generate robust hierarchical segmentation for every image across the entire dataset, solely relying on hierarchical clustering in feature space, see Figure 1 . This new method attains unsupervised segmentation by distilling relationships between concepts hidden in the latent space of self-supervised models at multiple levels of semantic granularity.We propose a simple algebraic methodology based on a vast literature [20, 6, 61, 81, 75, 91] , that unsupervisedly segments the scene parts. The method guarantees the construction of natural, scenedependent classes of primitives [55] , which can be easily used in unsupervised segmentation without surrendering to their apriori definitions. Our contributions are:1. We introduce a deep recursive spectral clustering that maximises an unbiased semantic similarity measure at multiple granularity levels. Exposing our method to any generic group of images, we show that it results in hierarchical unsupervised semantic segmentation. 64]. Contrastive learning (CL) [18, 63] is the most prominent method in SSL, maximising feature similarities between an image and its affine transformations while minimising similarity between randomly sampled images. Most unsupervised segmentation methods use learning representations to feed self-supervised features to graphs for clustering [58, 88, 87, 3] . Alternatively, features are used for building distillation strategies [32, 96, 51] , or for designing inductive priors forcing some consistency property [51, 17, 73] . SSL representations implicitly define a distance metric in the latent space, though learning a metric space is not their primary objective.Unsupervised semantic segmentation. Unsupervised semantic segmentation assigns a class to pixels belonging to specific elements in the scene, keeping the same class for all objects of the same semantic kind but without supervision. The main drives for unsupervised semantic segmentation are the strategies that can exploit either (1) grouping of similar patches or pixels, (2) an underlining dense consistency of objects that do not change under transformations, or (3) dense self-distillation. The earlier approaches, such as [41, 47, 17, 86, 77, 33] had not yet available powerful SSL features like [11] , though used CL principles. PiCie [17] used equivariance to transformations; IIC [41] resorted to invariant information clustering, maximising mutual information, to find commonality in objects, and analogously did InfoSeg [33] . CLD [86] integrated local clustering into contrastive learning; [77] used saliency to find the image foreground and guide CL of pixel embedding. The availability of high-level unsupervised features triggered new strategies. DINO self distillation [11] inspired both STEGO [32] and SmooSeg [51] . STEGO trains a segmentation head by distilling the feature correspondences to form compact clusters. SmooSeg uses the smooth prior over semantically coherent regions as a supervision cue to generate semantic maps. However, many methods suffer from the background problem and elaborate on DINO's attention to obtaining foreground objects, such as FreeSolo [85] and [93] . Also, TransFGU [90] focuses on a top-down object-centric approach to generate pixel pseudo labels according to GradCAM [72] . Spectral clustering, as introduced to machine learning by [74] , is considered in [88, 58, 87, 52, 68] . In particular, CutLER [87] applies NCut [74] iteratively to a masked similarity matrix to discover foreground elements of the scene. ACSeg [52] uses the affinity matrix to discover concept similarities. SemPart [68] considers the foreground a single object saliency mask and applies graph regularisation. In [73] , patch-level contrasting learning leverages global hidden positives to learn semantic consistency. As grouping is the common denominator, all the mentioned methods suffer from deciding the correct level of granularity. Some methods resort to an object-centric bias, such as [77, 93] , CAMs [90] , hinting self-attention [96, 79] , fixed-size flat image partitioning [58] . Others, such as [96] , and [46, 73] , resort to a scene-centric prior assumption.Unsupervised parts discovering. Despite hierarchically discovering parts has a long history in computer vision, it has only recently recovered and connected to unsupervised part segmentation. The first input came from [31] , analysing the hierarchical nature of deep learning features. One of the first approaches was SCOPS [39] using dense self-supervised contrastive loss to discover foreground parts of single objects. [94] introduce self-supervised primitive hierarchical grouping. They leverage a boundary strength map (OWT-UCM [4] ) on relatively few images to learn from a large data set. The approach formulates an ultrametric map defining a region hierarchy. Similarly, HSG [44] leverages region boundaries to obtain multi-level segmentation. HSG is unsupervisedly trained from scratch, performing pixel grouping with dense contrastive learning across different granularity levels. In [19] , K fixed parts are discovered via an average part descriptor and by forcing consistency using the equivariance of affine and photometric transformations. Leopart [96] follows DINO self-distillation to classify pixels, obtaining detailed scene parts, further clustered via community detection. Finally, DeepCut [3] approaches unsupervised semantic part segmentation using both spectral clustering with NCut and GNN convolution, constructing a patch-wise correlation [7] matrix from DINO features. 
limitations: 
 Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: See Section 5.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
method: 
 We present a flexible, unsupervised method for segmenting natural images, automatically creating data structures that organize pixels by their semantic coherence across multiple levels of detail without relying on predefined hierarchies or labels. This method is designed to segment images from coarse regions to finer parts, providing an intuitive representation of visual content; see Figure 1 .For instance, consider an urban street view. At a high level, it consists of elements such as the sky, a road, buildings, and vehicles. Among the vehicles, there might be a bus or a car, which can be further decomposed into parts like the body shell, wheels, and other visible components.Our approach segments an image I ∈ R 3×M ×N into a hierarchy-agnostic tree T of semantic regions, with each pixel in the image assigned to a leaf node. Our model is a function f : I → T , represented by a deep neural network, which maps an image to its semantic regions. Notably, this is achieved in a fully unsupervised manner; we incorporate mechanisms that guide f to produce a meaningful decomposition of the image, even without labelled examples.Our method discovers semantic parts in an image by recursively partitioning a graph constructed from deep feature representations of the image. The key idea is to treat self-supervised models for image processing as codebooks of a lower-dimensional space, with the extracted feature vectors acting as codes that embed visual semantic concepts.The primary cue for discovering parts is a deep feature extractor ϕ, a neural network pre-trained without supervision on a standard benchmark such as ImageNet. We observe that the alignment of codes leads to semantic similarity across multiple levels of granularity. A higher degree of alignment indicates semantic similarity at finer granularity levels, corresponding to indivisible object parts or primitives. Conversely, a lower degree of alignment reflects semantic similarity at coarser granularity levels. By discretizing the density of these alignments, we can discover scene and object parts at various levels of detail.Let v i = [ϕ (I)] i ∈ R d be the code associated with pixel location i in the image. If pixel j belongs to the same finer part as i, their codes should be similar. Conversely, if they belong to different parts, their codes will diverge. We expect this property to be consistent in each image I and should not be affected by the particular object instances.A straightforward approach might be to cluster these codes using algorithms like K-means or Expectation-Maximization to identify semantic regions. However, a critical flaw that can arise when using these methods in high-dimensional space is the presence of many local minima in the cost function. This would require multiple restarts of the iterative algorithms to find a suitable solution, which is impractical due to high complexity. To overcome these limitations, we propose a novel method that efficiently partitions the image into meaningful semantic regions, avoiding the pitfalls of multiple local minima and the need for iterative restarts.Graph construction. We represent the image I as a weighted undirected graph G = (V, E, w), where V = {v i } n i=1 and n = M • N . The weight assigned to each edge (i, j) ∈ E is defined by a scaled and shifted cosine similarity between feature vectorsw ij = w(v i , v j ) ∈ [0, 1]. These weights form the adjacency matrix W = [w ij ] ∈ [0, 1] n×n , the degree matrix D = diag [d i ] ∈ R n×n , where d i = j w ij and the normalized graph Laplacian L = D -1/2 (D -W ) D -1/2 [59].We interpret the edge weights as indicators of the semantic granularity between nodes. Specifically, if w ij → 1, pixels i and j likely belong to the same fine-grained part (primitive). Conversely, if w ij → 0, these pixels are likely to belong to entirely different parts, indicating minimal semantic similarity even at the coarsest level of granularity.Similarity perturbation. In an ideal scenario, at a specific granularity level, k ′ distinct connected components emerge in G, resulting in a binary adjacency matrix W ′ ∈ {0, 1} n×n with k ′ non-zero diagonal blocks -indicating strong intra-component connectivity and no inter-component connections -and normalized Laplacian L ′ . However, in practice, the observed adjacency matrix is not discrete. Instead, W exhibits tightly connected components alongside others with lower connectivity, resulting in a perturbed normalized graph Laplacian L. We regard the primitives of the model as affected by a small symmetric perturbation H ∈ R n×n incorporating contextual information from coarser levels of semantic granularity, i.e. L = L ′ + H, making the observed adjacency real-valued.Fortunately, the Davis-Kahan symmetric sin θ theorem [23, 91] helps us manage perturbations; see also Appendix A. If the eigenvalues of L exhibit a spectral gap δ, the corresponding eigenspaces of L and L ′ remain close despite the perturbation H. The theorem quantifies this proximity by relating the angle θ between the eigenspaces of L and L ′ , where sin θ is proportional to the norm of H and inversely proportional to δ. By selecting the largest gap, we isolate the part of the spectrum closest to the original graph, guessing the true semantic structure at the specific granularity level.Normalized smoothness measure. We consider a function g : V → R that assigns a value g(v i ) to each node v i ∈ V . Since |V | = n, we identify the function g with a vector in R n . Based on the considerations from [74, 8] (see also Appendix C), we define the normalized smoothness measure of g on the graph G using the functional S G : R n → R + induced by L through the form:EQUATIONWe observe that minimizing the functional yields normalized smoothest functions that assign similar values to tightly connected nodes and different values to weakly connected ones while accounting for their importance in the graph -avoiding trivial solutions for low connectivity nodes. Therefore, if g is both normalized and smooth with respect to G, then g(v i ) is similar to g(v j ) whenever v i is similar to v j , where similarity is quantified by the weight w ij and adjusted by the node degree d i .Given these properties, we can treat any function g as a continuous partition function on our graph G and evaluate its correctness using a criterion based on the semantic density change in the data partition, which measures variations in semantic coherence across different regions of the graph.Recursive partitioning with perturbation stability. We propose a recursive partitioning strategy for discovering semantic parts by progressively dividing the graph, starting from the whole and refining it into tightly connected subgraphs. At each recursion level, we examine the subgraph's granularity, identify perturbations -contextual variations affecting node connections -and derive the unperturbed adjacency matrix to reveal finer semantic components. By capturing relationships at multiple levels of detail, this approach yields more nuanced segmentation than methods that partition the entire graph's nodes into a fixed number k of sets.We aim to find the smoothest normalized functions that best describe the semantic structure of a subgraph G at a specific granularity. 1 We tackle the minimization of Equation ( 1) as a standard eigenvalue problem [74] using the Rayleigh-Ritz quotient form. This yields the orthonormal eigenvectors y i corresponding to the smallest eigenvalues λ i of L, as guaranteed by the Courant-Fischer theorem:EQUATION)The eigenvalues λ i -the values on the right-hand side of the problem above -with0 = λ 0 ≤ λ 1 ≤ • • • ≤ λ n-1 ≤ 2,quantify the normalized smoothness of the functions y i . Since solving the eigenvalue problem has a computational complexity of O(n 3 ), in practice, we limit the computation to the k max smallest eigenvalues for efficiency. We obtain the spectral gaps δ j = λ j -λ j-1 > 0 for 2 ≤ j ≤ k max -1 and seek for the k-th gap giving the tighter sin θ bound, i.e. k = arg max j δ j .We select up to k smoothest normalized functions on G, namely the first k eigenvectors of L, y 1 , . . . , y k-1 -we ignore y 0 since it is constant. These k eigenvectors provide orthogonal graph signals based on semantic coherence, with nodes showing similar values in these functions likely belonging to the same semantic part; thus, each signal points to a distinct connected component.As in [61] , we recover the true semantic structure of the graph considering the matrix Y = [y 1 , y 2 , . . . ,y k-1 ] ∈ R n×k-1 . First, we perform ℓ 2 -normalization of each row in Y , X ij = Y ij /( j Y 2 ij ) 1/2 ∈ R n×k-1-the i-th row of X represents the normalized feature vector for the i-th node, which determines the node's membership in a cluster. Then, we take the best membership for each node -using the K-means algorithm in a lower-dimensional space -finding k disjoint partitions of the nodesV 1 , V 2 , . . . , V k such that k i=1 V i = V and k i=1 V i = ∅.We determine L ′ and estimate the perturbation H = L -L ′ to compute the sin θ upper bound value.Each recursion step splits the graph into tighter subgraphs. This process continues until one of the early stopping criteria is met: (1) if a partition is too small (less than k min ), (2) if the eigenvalues exceed a maximum smoothness threshold λ max , or (3) if the sin θ upper bound value becomes too large (more than p max ), indicating that the current estimate of L ′ is no longer reliable. These stopping conditions ensure we halt when further partitioning does not yield meaningful semantic components, thus identifying the final set of image parts or primitives.Each recursive partitioning adds structure to the tree T , where nodes specify semantic regions at various levels. The final output is T , with each leaf node capturing a distinct part of the image at an appropriate level of granularity; see Figure 2 .The values k min , λ max and p max are found experimentally for the tested dataset; tables are shown in Section 4 and Appendix D. In Appendix B, we discuss the algorithm's properties and the generated T , and present the complete pseudocode of our method.Boosting computation. We introduce a preprocessing strategy that condenses the graph, dramatically reducing the algorithm's time and memory requirements by several orders of magnitude while maintaining comparable accuracy. The condensed graph simplifies the original graph into m nodes by contracting strongly connected components into vertices, where m ≪ n.We assume that the finest semantic content in natural images is inherently limited and cannot exceed the raw pixel statistics. From the input image I we extract m regions [2, 69, 74] leading to an initial undirected condensed graph G c = (V c , E c , w), where V c = {A i } m i=1 , such that m i=1 A i = V c and m i=1 A i = ∅, and the edge weights w(A i , A j ) represent the degree of association between regions, defined as w(A i , A j ) = u∈Ai,v∈Aj w(u, v). We then apply our recursive partitioning algorithm to G c and its corresponding normalized Laplacian matrix L c . As a result, we obtain a region tree T .Ablation studies in Section 4.3 compare performances across various overclustering methods.Boundary Sharpening. Given a predicted region tree T with q leaves, B 1 , B 2 , . . . , B q , each embedding a disjoint segment of V , such that q j=1 B j = V and q j=1 B j = ∅, we compute the prototypes for the image I. Each prototype is defined as the ℓ 2 -normalized average of the feature codes in each leaf u j = |B j | -1 v∈Bj v. For each pixel, we define a conditional probability distribution over the prototypes using the softmax function with smoothing parameter τ , namely,p ij = exp v ⊤ i u j τ -1 / k exp v ⊤ i u k τ -1 .We arrange the matrix P = [p ij ] ∈ [0, 1] (M ×N )×q and sharpen the region boundaries applying a Conditional Random Fields (CRF) [49] , which refine the predicted distribution P by incorporating dependencies between pixel observations I. This improves the accuracy at the boundary, ensuring sharper and more precise segmentation of leaves.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: We refer to theorem which are fully reported and referred.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experiments: 
 We benchmark our algorithm on unsupervised multi-granular segmentation using seven major object-and scene-centric datasets and seven hierarchically structured datasets with varying granularity levels for hierarchy-agnostic segmentation. Our evaluation includes an ablation study to assess the contributions of each algorithm component and comparisons across different self-supervised backbone architectures. We only utilize publicly available datasets, SSL model checkpoints without retraining, and validation set ground-truth annotations. CRF is applied only where specified.Each dataset provides unique characteristics essential for different segmentation challenges. Pas-calVOC2012 [27] offers a broad range of object categories, making it suitable for general object segmentation tasks. With its high-level division into things and stuff, COCO-Stuff [10] extends the MSCOCO [53] and tests the algorithm in complex scenes with multiple objects. Potsdam and Vaihingen [30] datasets, focused on aerial scene parsing, are designed for remote sensing and urban planning applications. Cityscapes [21] is critical for autonomous driving research, providing detailed annotations of urban street scenes. Mapillary Vistats [60] adds diversity with street scenes from various global environments, testing the algorithm's robustness to different conditions. KITTI-STEP [89] and KITTI-SS [1] , similar to Cityscapes, extend the evaluation to dynamic urban scenarios with instance detection and object tracking. For fine-grained part segmentation, Pascal-Part [15] , PartImageNet, and PartImageNet-158 [35] offer detailed part annotations, crucial for tasks requiring precise recognition and segmentation of object parts.These datasets ensure a comprehensive and diverse benchmark for evaluating the performance and robustness of our segmentation algorithm across various contexts, see Figure 2 . Further details about datasets are in Appendix D.1, and more quantitative and qualitative results are in Appendices D.3 and D.4, respectively.To ensure reproducibility, we standardize our experimental setup. Unless otherwise specified, we use the DINOv2-ViT-B14-REG [22] backbone with parameters k min = 1, p max = 20, and λ max = 0.8. We apply the spectral method from Ng et al. [61] with m = 300 for superpixel clustering. The recursive partitioning depth is limited at 10 levels. Depending on each backbone downsampling factor, input images are resized to extract 60 × 60 codes, except for urban street scenes, where we obtain 60 × 120 codes. Further details in Appendix D. Granularity-agnostic. Following [44] , we aim to evaluate the unbiased overlapping of regions between predicted segmentation and ground truth within each image via the Normalized Foreground Covering (NFCovering) metric. However, it is not well-suited for the multi-granular segmentation domain. The metric applies to a single granularity level at a time, failing to account for multiple granularity levels. Furthermore, it disregards the background as a valid semantic instance, leading to an incomplete estimate of segmentation performance.We propose a novel evaluation metric, the Normalized Multigranular Covering (NMCovering), which addresses these limitations evaluating the overlap of regions between the unrolled segments in the region tree T and all the available ground-truth categorical segments in a semantic map S gt . This metric ensures that both foreground and background instances are considered, providing a more comprehensive and granularity-independent assessment of a semantic segmentation model's performance. We adopt a greedy heuristic that maximises the overlap of the full hierarchy with the ground truth segmentation and compute the average overlap ratio of the matching:EQUATIONThe NMCovering metric evaluates the performance of a hierarchical segmentation model considering how many ground truth objects are recognised at any granularity level and how well they are segmented. A high score indicates a high segmentation coherence between human semantic perception and unsupervised machine one.Hierarchy-agnostic. We introduce a second accuracy metric, the Normalized Hierarchical Covering (NHCovering). NHCovering jointly evaluates the segmentation quality and the semantic hierarchical inclusion of the prediction relating to the ground-truth semantic region tree T gt . Hierarchical inclusion is the matching between the nodes of two distinct hierarchies preserving the lineage from the ancestors; this problem is commonly referred to in the literature as the unordered tree inclusion problem [45] .To calculate this metric, we use a greedy heuristic that computes the average overlap ratio of matching regions, weighting each match by the ratio of matched ancestors. The operator π(R) returns the ancestors set of the tree node R, and β(R, T ) returns the nodes set in the predicted tree T that best match the ancestors of node R:EQUATIONwhere β(R, T ) := P ∈π(R)arg maxEQUATIONThe NHCovering metric computes the average weighted overlap of regions between the predicted tree T and the ground-truth tree T gt . The overlap weight measures the proportion of correct ancestorships with respect to the ground truth. Balancing segmentation performance with semantic ancestry consistency provides a granularity-and hierarchy-independent performance assessment. This score quantifies the coherence of segmentation and hierarchical organization of visual concepts between human perception [66] and unsupervised machine one.Refer to Figure 3 for a visual insight into the metrics. A more detailed discussion is in Appendix D.2.Granularity-Agnostic. We adopt the NMCovering metric to benchmark the performance and versatility of our algorithm across different natural image domains. As shown in Tables 1 and 5 , our method achieves excellent results in segmenting object-centric images and foreground discovery. Additionally, Table 1 demonstrates our approach's strong performance on scene-centric datasets, such as remote-sensing images and urban street scenes. Table 3 compares our approach to other supervision strategies. 2 Our approach achieves segmentation quality comparable to supervised methods and surpasses other supervision strategies by a large gap. [12] ResNet-101 77.7 -DeepLab-CRF [12] VGG-16 -43.6 [10] DeepLabV3-JFT [13] ResNet-101 82.7 weakly-supervised ViT-PCM [71] ViT-B16 69.3 45.0 L2G [42] ResNet-38 72.0 44.2 WeakTr [95] DeiT-S 74.0 50.3 un-supervised Melas-Kyriazi et al. [58] ViT-S16 37.2 -Leopart [96] ViT-S16 41.7 49.2 HSG [44] ResNet-50 41.9 -Zhang et al. [94] ResNet-50 43.5 -MaskDistill [79] ResNet-50 Hierarchy-Agnostic. We further benchmark the hierarchical inclusion quality of the algorithm on available datasets having hierarchical structures at a high level, such as MSCOCO, COCO-Stuff and Cityscapes, and at a low level, such as PascalPart and PartImageNet. We show in Table 2 the closeness in performance of NHCovering with respect to the NMCovering, demonstrating the ability of the algorithm to capture hierarchical relations among the parts. The lower performance on PascalPart is due to the lower granularity of part annotations compared to PartImageNet, see [35] .Recent unsupervised semantic segmentation approaches, such as [44, 94] , often employ mutual information maximisation between regions at multiple granularity levels. These methods typically utilise hierarchical clustering that groups low-level coherent regions via boundary potentials, such as the Ultrametric Contour Map (OWT-UCM) [4] , of boundaries derived from low-level features like brightness, colour, and texture gradients, as in Structured Edges (SE) [24] or Pointwise Mutual Information (PMI) [40] . We compare our approach with these methods in Table 4 . The results indicate that low-level processes are inappropriate for the hierarchical grouping of high-level (semantic) features. In contrast, our approach excels in this area, suggesting significant room for improvement in the current state of the art. See some hierarchical grouping results in Figure 4 . Backbone. We evaluate in Table 5 the consistency of our approach according to the latent space induced by different SSL Imagenet pre-trained backbones on the granularity-agnostic task on the PascalVOC2012 val set. The performance gap reflects the representation quality assessed by SSL downstream task benchmarks. Such a result assesses the best model and a complementary downstream task benchmark for SSL. We do not adopt superpixel clustering or CRF but utilise raw patch features as pixel codes.Parameters k min , p max and λ max . In Tables 6a to 6c we validate the optimal parameters of our algorithm. While k min choice affects the granularity at lower levels, the p max and λ max choice affects the granularity at higher levels by controlling the stability of the partition.Overclustering and CRF. We test different over clustering techniques in Table 6a . Results show higher performances for a simultaneous normalised cut on SSL latent space. When applying CRF with τ = 0.1, we obtain an increase in segmentation accuracy as shown in Tables 3 and 4 .Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: As stated in Section 4, to have full reproducibility, we adopt publicly available deep network checkpoints and do not perform any retraining. We evaluate our algorithm on publicly available datasets and use full validation sets. Our algorithm is deeply described in Section 3, and our code is shown in the appendix, Algorithm 1. The used backbone, the superpixel clustering method, the k min , p max and λ max values are the variables needed to reproduce the results. We clearly state their values in Section 4 and table 6 . Implementation details beyond the standard algorithm are reported in Appendix D. 
discussion: 
 Broader impact. Supervised learning relies on highly curated datasets that require costly and time-consuming manual annotations, especially for tasks like segmentation or those needing expert knowledge, such as fine-grained recognition. Due to the scarcity and limited size of part segmentation datasets, there's a growing focus on enhancing image understanding with minimal or no supervision. Our approach to discovering semantic object parts can significantly expand the data available for training such models. However, our method is based on self-supervised learning, which, like all data-driven methods, is susceptible to inherent biases in the data, which can influence the learning process and the model's predictions.Limitations. One major drawback of our approach is that the segmentation quality, as well as the execution time of the algorithm, scales with the input size. Indeed, small object parts are hard to discover especially when using overclustering during pre-processing; results prove the statement. However, a trade-off between accuracy and inference time can be obtained experimentally. 
conclusions: 
 We introduce a novel method for unsupervised, hierarchy-agnostic decomposition of natural scenes into primitive components, without requiring prior knowledge of scene granularity. Leveraging deep feature extraction and graph partitioning, our approach identifies scene-conditioned primitives and constructs a semantic tree of scene elements for any dataset. Our core algorithm applies an innovative algebraic approach to deep spectral clustering, addressing blurring from pixel similarity across object parts. Matrix perturbation theory is employed at each level of the semantic tree, ensuring stable smooth partitions. This framework not only advances unsupervised semantic segmentation but also benchmarks deep neural network representations by evaluating segmentation quality at multiple granularity levels and hierarchical consistency among them. We validate our method with new metrics across multiple datasets, measuring overlap with ground-truth components and semantic inclusion across potential image hierarchies. On the right, the perturbed adjacency matrix W introduces off-diagonal entries due to pixel similarity across regions, resulting in the perturbed Laplacian L. Below, a graph with added connections shows these perturbations, with colours matching the highlighted parts in the input image. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification:The paper provides comprehensive statistical information for the experiments. Specifically, we assume Gaussian error (and run time) as stated in Section 4.2, and we report mean and standard deviation values in Table 3 and Tables 6a and 6c . While in Tables 6a and 6c , we report such values to assess the behaviour of the algorithm with respect to its base components, in Section 4.2, we perform 4 experiments to ensure the reproducibility and statistical validity of the experiments with different random seed initialization. However, not all experiments report such statistical information, especially the ones in Tables 1, 2, 4, 5 and 6b, for two main reasons. The first is that typically, in the standard practices in the field of semantic segmentation, it is common to report a single percentage mean value for evaluation metrics such as the mean Intersection over Union (mIoU); it is extremely rare the opposite. The second reason is that our newly introduced metrics typically require more time for evaluation with respect to standard IoU. Indeed, for instance, the NHCovering searches for the leaves matching between two trees; typically, the predicted tree counts many leaves. Hence, multiple restarts make the evaluation process extremely long.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We specified the compute workers and the memory used in Appendix D to run our experiments. The time of execution depends on the parameters used and is discussed in Section 4.3 and Table 6 .Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes]Justification: The research did not involve human participants (but the authors). All datasets used are publicly available. The authors do not envision harmful consequences of the work and no violations in any of the points listed in the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: This is a relevant question. As we have written, in the case of annotations, there is always discrimination due to the annotator's subjective prejudice or the dataset's design. In the case of unsupervised segmentation, in principle, there is no prejudice, but we cannot know if it can lead to some other form of prejudice. However, the most risky factor is the possibility the algorithm discloses of running it over a massive set of raw images (not a curated dataset) and profiting from that. Also, it shares the risk and bias of all SSL models and the unsupervised segmentation models. For example, the enormous amount of energy to run it over hundreds of thousands of raw images. . 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: Assets' owners are explicitly mentioned as reference entries.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: [NA]  
 
 Appendix: From the example in Figure 5 , we observe that perturbation arises from pixel similarity values that inadvertently create connections between regions, which ideally should remain separate. This unintended overlap occurs because similarity values between certain pixel pairs do not perfectly align with the true structure of the components. Perturbation theory [23, 9, 75, 43] studies how small changes, such as these unintended connections, affect a matrix's eigenspaces. Recent research has expanded this analysis from Hermitian matrices to include Laplacian matrices, which capture graph structures, as in [82, 26, 70, 28, 65, 91] .In our method, the two matrices are an ideal Laplacian matrix L ′ and the observed Laplacian matrix L, both symmetric (not necessarily of the same rank), perturbed by a symmetric matrix H induced by higher-order pixel similarity, L = L ′ +H. Given the recursive partitioning described in Section 3, we are looking, for each subgraph, for the best matches between the eigenvectors of L ′ and those of L minimising the functional defined in Equation (1).In the ideal normalized Laplacian L ′ , the graph is disconnected, and the number of connected components is reflected in the multiplicity of the zero eigenvalue of L ′ . Each connected component contributes one zero eigenvalue, and the constant eigenvectors corresponding to these zero eigenvalues represent these isolated components [20, 81] . In a perturbed normalized Laplacian L, the graph is connected and then the minimum of Equation ( 2) is achieved by the eigenvector corresponding to the second smallest eigenvalue of L ′ . This eigenvector, known as the Fiedler vector, is not constant and captures the connectivity structure of the graph, often used for finding the best bipartition.However, in the case of a perturbed graph with weak connections (e.g., low weights or nodes with only a single neighbour), small eigenvalues close to zero may not indicate strongly connected subgraphs. Instead, these small eigenvalues reflect loosely connected regions, where perturbations create weak links between components that ideally should remain separate. This implies that using the smallest eigenvectors directly for graph partitioning is sometimes unreliable, as they may reflect unstable or artificial connections introduced by perturbations. To ensure meaningful segmentation, it is essential to establish a measure that quantifies the stability of the partition under perturbations. Such a measure would indicate when it is safe to apply spectral clustering, ensuring that the identified clusters are robust and well-separated. According to Theorem A.1 (shown below), to achieve this, we seek the set of eigenvectors of the perturbed Laplacian L that are closest to the eigenvectors of the ideal normalized Laplacian L ′ despite the perturbation H:Theorem A.1 ([91]). Let A, A ′ ∈ R n×n be symmetric, with eigenvalues µ 1 ≥ • • • ≥ µ n and µ ′ 1 ≥ • • • ≥ µ ′ n respectively. Fix 1 ≤ r ≤ s ≤ n and assume that min(µ r-1 -µ r , µ s -µ s+1 ) > 0, where µ 0 := ∞ and µ n+1 := -∞. Let u := s -r + 1, and let Z = (z r , z r+1 , . . . , z s ) ∈ R n×u and Z ′ = (z ′ r , z ′ r+1 , . . . , z ′ s ) ∈ R n×u have orthonormal columns satisfying Az j = µ j z j and A ′ z ′ j = µ ′ j z ′ j , for j = r, r + 1, . . . , s. Then:EQUATIONMoreover there exists and orthogonal matrix O ′ in R n×n such that:EQUATIONWith op and F , the spectral and the Frobenius norm, respectively.Corollary A.1 ( [91]). Let A, A ′ ∈ R n×n be symmetric, with eigenvalues µ 1 ≥ • • • ≥ µ n and µ ′ 1 ≥ • • • ≥ µ ′ n respectively. Fix j ∈ {1, .. . , n} and assume that min(µ j-1 -µ j , µ j -µ j+1 ) > 0, where µ 0 := ∞ andEQUATIONMoreover, if z ′⊤ z ≥ 0, then:EQUATIONIn our method, the above symmetric matrix A refers to the perturbed matrix L and the matrix A ′ to the ideal matrix L ′ ; see Section 3. Since we select the k smallest eigenvalues, the interval starts from r = n -k + 1 and ends at s = n, and we have u = k. The denominator in Equation ( 6) simplifies tomin(µ n-k -µ n-k+1 , µ n -µ n+1 ) = µ n-k -µ n-k+1, since by definition µ n+1 := -∞, and, given Z = (z n-k+1 , z n-k+2 , . . . , z n ) ∈ R n×k and Z ′ = (z ′ n-k+1 , z ′ n-k+2 , . . . , z ′ n ) ∈ R n×k , depending on the chosen eigenvalue ordering, we have:EQUATIONor, reversing the indexing -eigenvalues in non-decreasing order -and counting from zero, we set λ i = µ n-i and λ ′ i = µ ′ n-i for i = 0, . . . , n -1 with Y = (y 0 , y 1 , . . . , y k-1 ) ∈ R n×k and Y ′ = (y ′ 0 , y ′ 1 , . . . , y ′ k-1 ) ∈ R n×k the orthonormal columns satisfying Ly j = λ j y j and L ′ y ′ j = λ ′ j y ′ j , for j = 0, 1, . . . , k -1, we have:EQUATIONIndeed, we can apply the substitution and the indexing, given the eigenpairs (λ, y) condition for all the eigenvalues and eigenvectors populating the chosen interval (r, s). Furthermore, given the eigenpair condition, the minimization of Equation ( 1) in Section 3 is guaranteed (see Algorithm 1), and we can just ratify the smoothness by resorting to the Courant-Fisher theorem; see [38] Theorem 4.2.6. Finally, we can use the Corollary A.1 for a more refined choice of the eigenvectors.Note that the theorem of Yu et al. [91] is particularly useful because, differently from Davis-Kahan [23] theorem, it defines an upper bound between two symmetric matrices concerning the angles between a subset of the eigenvectors of the two matrices or their distance (up to a rotation), in terms of the eigenvalues of one of the two matrices. Indeed, this theorem shows that z (an eigenvector of the perturbed Laplacian L) is close to z ′ (an eigenvector of the Laplacian L ′ ), under two main assumptions. First, we assume that L is close to L ′ -often this is straightforward in graph theory, for instance, if L ′ is derived from a theoretical (or "population") graph structure, and L is the Laplacian of a graph constructed from a sample or noisy measurements of this structure. Second, applying Weyl's inequality, we assume that, almost certainly:|µ ′ j-1 -µ j | ≥ (µ j-1 -µ j )/2 and |µ ′ j+1 -µ j | ≥ (µ j -µ j+1 )/2,where µ j and µ ′ j are the j-th eigenvalues of L and L ′ , respectively. Under this eigengap condition, assuming a sufficient separation between the population eigenvalues of L and their neighbouring values, as shown in Yu et al. [91] results, we can conclude that ∥z ′ -z∥ is small, meaning z and z ′ are close in norm. Building on this, the theorem implies that when the eigengap condition holds, the eigenvector z associated with L remains stable under perturbations represented by H = L -L ′ . Specifically, the proximity of z and z ′ allows us to interpret z as a meaningful approximation of z ′ , preserving the structure of the ideal graph encoded by L ′ .Consequently, this alignment of eigenvectors facilitates robust graph-based clustering or segmentation, as it enables us to consistently identify clusters or partitions in perturbed graphs that mirror the structure of the unperturbed graph. Furthermore, this result provides a foundation for using the perturbed eigenvectors for hierarchical clustering by ensuring that the segments or clusters derived from L approximate those of L ′ even under small changes or noise in the graph data. In Section 3 of the main paper, we have presented the recursive partitioning of the graph G, which is simple and intuitive. As noted, we present a Breadth-First Search (BFS) pseudocode in Algorithm 1.The method obtains graph partitions when two or more components are detectable and recur on each partition to find new subgraphs until an early stopping condition is met, see Section 3. We report that the proposed algorithm is defined in two steps for completeness -the first step is meant to speed up the overall algorithm, and hence, it is optional. In the first step, we quantise the graph, creating an over-clustering of semantic parts; in the second step, we recur on the parts, generating coarse to finer semantic groups at multiple granularity levels; see Figure 6 .In the first step, we write the patch-wise features extracted with a deep neural network as the set of nodes V of a weighted undirected graph G = (V, E, w), and we define w as the cosine similarity of points, scaled and shifted in [0, 1].In this step, we follow the approach of Ng et al. [61] to cluster the graph in m components. The clusters define m disjoint segments A 1 , A 2 , . . . , A m (m i=1 A i = V , m i=1 A i = ∅) of Gwith high intra-cluster degree of semantic similarity.In the second step, we adopt a top-down recursive divisive clustering approach, building a hierarchical semantic decomposition of the image. In the recursive call at a certain level l and for a certain subgraph c -notice that here c is an index -of a graph p we define an undirected condensed graph G l,p c = (V l,p c , E l,p c , w), with segments A as nodes in V l,p c( A∈V l,p c A ⊆ V , A∈V l,p c A = ∅)and the edges are weighted by the associativity degree of the components w(A i , A j ) = u∈Ai,v∈Aj w(u, v). Notice that the condensed graph at the root level is indicated as G 0,0 0 = (V 0,0 0 , E 0,0 0 , w) and V 0,0 0 = {A i } m i=1 . At each depth, we obtain a semantic grouping S l = {V l+1,c i } c,i given by all the i-th subgraphs at level l + 1 of each subgraph c at level l.The recursion defines the final hierarchy, namely the output tree T .The semantic grouping algorithm discussed here builds upon conventional spectral clustering methods [74, 61, 6, 81] . l } ℓ l=1 V 0,0 0 = {Ai} m i=1 = spectral_overclustering(V ) {S l } ℓ l=1 = bfs_partitioning({V 0,0 0 }) Function spectral_overclustering(V ): Compute L for graph G = (V, E, w) Y ← arg min Y ∈R |V |×m ,Y ⊤ Y =I Tr(Y ⊤ LY ) Normalize rows Xij = Yij/( j Y 2 ij ) 1/2 Group X rows in m clusters with K-means return m groups {Ai} m i=1 of V Function bfs_partitioning(S l ): S l+1 ← {} foreach segment V l,p c ∈ S l do n ← V l,p c if n < kmin then continue end Get condensed graph G ← G l,p c = (V l,p c , E l,p c , w) Scale W with min-max normalization and compute L Y ← arg min Y ∈R n×kmax ,Y ⊤ Y =I Tr(Y ⊤ LY ) λ ← diag(Y ⊤ LY ) Reorder Y columns and λ in ascending order of λi k ← arg max i {λi -λi-1} kmax-1 i=2 , λi-1 < λmax if ∄ k then continue end Take first k eigenvectors Y ← Y [:,1:k] Normalize rows Xi,j = Yi,j/( j Y 2 i,j ) 1/2 Group X rows in k clusters with K-means and get L ′ Compute perturbation H = L -L ′ if 2 min(k 1/2 ∥H∥op, ∥H∥F )/(λ k -λ k-1 ) > k pmax then continue end Found stable k subgraphs estimate S l+1 c = {V l+1,c i } k i=1 of V l,p c S l+1 ←S l+1 ∪ S l+1 c end return {S l+1 } ∪ bfs_partitioning(S l+1 )Discussion above the algorithm. The algorithm's design integrates several properties that significantly shape semantic components' hierarchical structure and connectivity.One crucial feature is the dynamic estimation of the number of components, k, a parameter closely aligned with insights from perturbation theory. This estimate directly influences segmentation granularity, determining the expected number of distinct semantic regions and hierarchy levels in the final output.The algorithm produces a hierarchy-agnostic, unsupervised semantic region tree T . At each recursion stage, it seeks subgraphs that represent loosely connected regions based on robust algebraic criteria from graph theory, capturing coherent semantic regions at each level of granularity. By isolating each region from the context of previous layers, the algorithm accurately reflects the semantic hierarchy within the image's content. In this framework, the tree's leaves represent regions with high intra-cluster semantic similarity, positioning these clusters as primitives of broader concepts at higher levels. The algorithm naturally embeds semantic inclusion, where finer semantic regions exist within larger semantic contexts, mirroring how complex concepts encompass finer details.Lastly, computing the adjacency matrix only once optimizes efficiency, reducing redundant operations and improving runtime performance, making the approach both scalable and effective for large datasets.Time Complexity. The breadth-first search has a time complexity of O(|V | + |E|) on a general graph. In our case, with n nodes and n -1 edges (assuming a tree graph), BFS has complexityO(n + (n -1)) = O(2n -1) = O(n).The eigendecomposition of a symmetric matrix in the worst case has a complexity of O(n 3 ). Therefore, the combined time complexity is O(n + n 3 ) = O(n 3 ). However, because we only compute the smallest k max ≪ n eigenvectors, the time complexity of the eigendecomposition reduces to O(k max n 2 ). Thus, the overall complexity becomes O(n+kmax n 2 ) = O(k max n 2 ), since k max n 2 dominates n.The recursive partitioning process starts with an eigendecomposition on the full graph, which has a time complexity of O(k max n 2 ) for extracting the smallest k max eigenvectors. This initial computation is the primary contributor to the algorithm's time complexity. As the partitioning proceeds, each recursive call operates on progressively smaller subgraphs. While each subgraph requires an eigendecomposition, the cost decreases significantly as the graph size is reduced at each recursion level. For balanced partitioning, the cumulative cost of these recursive steps remains asymptotically bounded by the initial computation on the full graph. Thus, the overall complexity is effective O(k max n 2 ), ensuring computational feasibility even for large graphs.We recall here the Normalised Cut (NCut) introduced by Shi and Malik [74] for measuring the goodness of a graph partition.Let G = (V, E, w) be a weighted undirected graph, having n nodes, V = {v i } n i=1 , representing points v i ∈ R d . The weight on each edge of the graph w ij = w(v i , v j ) is a function of the similarity between nodes v i and v j and defines an element of the adjacency matrix W = [w ij ] ∈ [0, 1] n×n . The symmetrically normalised Laplacian of the graph [59] is defined as,L = D -1/2 (D-W )D -1/2 , with D = diag [d i ] ∈ R n×n the diagonal degree matrix and d i = j w ij .The normalised cut objective aims to partition the set V into two disjoint sets A ⊂ V and B ⊂ V (A ∪ B = V , A ∩ B = ∅) while minimising the degree of similarity between the two sets and maximising the one within each set, and it is defined as:EQUATIONwhere cut(A, B) = u∈A,v∈B w(u, v) measures the degree of similarity between A and B and is equal to the total weight of edges that the partitioning has removed, assoc(A, V ) = u∈A,t∈V w(u, t) measures the degree of similarity between A and V , and assoc(B, V ) is equivalently defined. The NCut is an unbiased measure of the normalised total similarity of the two sets of points. Indeed, normalisation avoids unnatural bias when partitioning out small sets of points. Minimising exactly Equation ( 12) is NP-complete, according to the proof due to Papadimitriou [74] .However, [74] shows a tractable real-valued solution to the relaxed problem in Equation ( 12) can be obtained by solving the generalized eigenvalue system (D -W )x = λDx , for x ∈ R n and λ ∈ R. The eigenvectors x i span an orthogonal basis for functions on G [81] :EQUATIONwithx 0 = 1 ∈ R n . The eigenvalues λ i , with 0 = λ 0 ≤ λ 1 ≤ • • • ≤ λ n-1, are the values of the right-hand side of the above expression. The eigenvector x 1 corresponding to the second smallest eigenvalue λ 1 of L is the non-trivial solution to the quadratic form in Equation ( 13), called the Fiedler vector [29] . However, this real-valued solution can be transformed into a discrete form to partition the set V in two disjoint sets A and B approximating the solution to the normalised cut problem in Equation ( 12) [74] .The former approach can be expanded to further partition the generated subgraphs, employing the subsequent eigenvectors. Indeed, the eigenvector x 2 linked to the third smallest eigenvalue λ 2 efficiently divides into two parts, A and B. However, the practical application reveals that if higher eigenvectors are used, the gap between real-valued and discrete-valued solutions widens, asking for a global mutual orthogonality constraint for all eigenvectors. Consequently, solutions relying on higher eigenvectors tend to be less dependable. It is often more advantageous to restart the partitioning process for each subgraph separately [74] .The code implementation is in Python 3. We ran experiments on an ASUS ESC8000 server with two AMD EPYC 7413 24-core processors and 256GB RAM. We used the PyTorch 2.3 deep learning framework and 2 NVIDIA A6000 GPUs with 48GB of VRAM to accelerate the feature extraction stage. For all the experiments in the paper, we ran our algorithm with the Python multi-threading library joblib up to 96 workers.PascalVOC2012 [27] is a generic object-centric semantic segmentation dataset of 20 object categories and a background class. It consists of 1, 449 images for validation. We follow [12] to obtain a larger image set with additional annotations [34] , resulting in 10, 582 images. [10] is a complex scene-centric dataset that extends the object-centric MSCOCO [53] dataset, with a high-level hierarchical structure. Concepts are split at the root level into things and stuff, each having outdoor and indoor subsets. There are 12 things and 15 stuff supercategories, and 80 things and 91 stuff categories. Objects appear in complex scenes, with more thing objects per image than PascalVOC2012 (7.3 vs. 2.3). Following [78, 84] , we use val2017 split of 5, 000 images.Potsdam, Vaihingen [30] are scene-centric datasets for aerial scene parsing with 6 categories (roads, cars, vegetation, trees, buildings, clutter). The raw 6000 × 6000 images are divided into 100 RGB 600 × 600 patches. We obtain a total of 3, 800 images for Potsdam and 3, 300 images for Vaihingen.Cityscapes [21] is an urban street scene-centric dataset with a high-level hierarchical structure, having 7 supercategories subdivided into 19 stuff and object categories. Unlike COCO-Stuff and PascalVOC2012, where classes appear in many scene contexts, Cityscapes contains similar street scenes that cover almost all 19 categories. The test split has 500 images.Mapillary Vistats [60] is an urban street scene-centric dataset with a high-level hierarchical structure, having 6 root-level categories subdivided into 37 supercategories and finally 66 categories. Unlike Cityscapes and KITTI-STEP, street scenes are captured from various environments worldwide, including several countries, weather conditions, and seasons. It aims to provide a diverse set of street scenes. The validation split has 2, 000 images. [89] , KITTI-SS [1] are datasets for urban scene understanding, instance detection, and object tracking. They have the same categories as Cityscapes and the same hierarchical structure. There are 2, 981 validation frames of KITTI-STEP, 200 test images of KITTI-SS.Pascal-Part [15] is an extension of the PascalVOC2010 [27] We average the metrics over each image in the dataset, ensuring a comprehensive assessment across varying image contexts. In the hierarchical scenario, the score gives equal importance to all levels, recognising the significance of coarse and fine-grained segmentation. This approach reflects the nuanced structure of hierarchical data, where higher and lower granularity levels provide complementary insights.The maximum overlap heuristics we use do not enforce exclusive matching. We intentionally choose this method to accommodate scenarios where regions in subsequent hierarchical levels overlap. For instance, in an image of human hands, the coarse category person may overlap with the finer category hand. An exclusive matching strategy might misinterpret this overlap, leading to an inaccurate assessment of segmentation performance. Our approach acknowledges such overlaps, providing a more realistic evaluation.Additionally, the granularity of ground-truth annotations is often limited. To address this, our evaluation process disregards predictions that do not best match any annotated object, treating them as neither true positives nor false positives. This avoids penalising the model for predicting more detailed segments than the available annotations. Moreover, this approach permits the evaluation of the model according to standard category micro and macro-averaged segmentation metrics [56] such as the micro pixel Accuracy (pAcc) and the macro mean pixel Accuracy (mAcc), the per-class Intersection over Union (IoU) and the relative macro mean IoU (mIoU), and micro frequency weighted IoU (fIoU). Interestingly, the NMCovering metric can define an upper bound for the NHCovering score with appropriate modifications. Specifically, we find that NHCovering(T → T gt ) ≤ NMCovering(T → T gt ). Equality between these metrics would indicate optimal model performance in terms of hierarchical inclusion, suggesting that the model not only segments accurately but also respects the hierarchical structure of the ground truth. Figures 7 and 8 offers finer insight into the metrics purpose.These metrics provide a robust framework for evaluating hierarchical segmentation models, balancing granularity and hierarchical accuracy while accounting for the inherent complexities in realworld image data.Our hierarchical semantic segmentation algorithm demonstrates strong performance across multiple datasets and hierarchical segmentation tasks, effectively capturing meaningful semantic structures at various levels of granularity.Table 7 showcases the comparative strength of our method, achieving high NMCovering scores against other low-level pixel hierarchical clustering algorithms. With λ max = 0.6, our approach effectively segments the validation set into hierarchical clusters that closely align with ground-truth structures, indicating robustness in preserving semantic hierarchies. Table 8 further illustrate our algorithm's adaptability in aerial scene segmentation, achieving notable NMCovering scores on both train sets. Using DINO-ViT-B8 features with λ max = 0.9, the algorithm accurately segments six primary categories, confirming its applicability to complex geospatial datasets where hierarchical segmentation is critical.Tables 9 and 10 highlight our model's proficiency in urban scene segmentation, achieving high NHCovering and mIoU scores across 19 categories and seven supercategories. Notably, the use of hierarchical labels in Table 9 and detailed category IoUs in Table 10 show the model's capability to distinguish fine-grained features within broader urban contexts. This performance suggests our approach can effectively capture semantic structures across varying levels of granularity, making it well-suited for dynamic urban environments.Table 13 is a challenging benchmark with its extensive hierarchy of 'thing' and 'stuff' categories, totalling 182 classes and 27 supercategories. Our algorithm achieves competitive performance across both high-level supercategories and fine-grained categories, achieving strong IoU scores across each subset. This indicates that the algorithm effectively balances both coarse and fine semantic segmentation layers, enabling nuanced representation across diverse objects and materials.In Table 11 , focused on Conditional Random Field (CRF) post-processing, our method shows that including CRF enhances segmentation accuracy across various datasets, validating its role in refining boundaries for complex regions. Additionally, comparisons with non-hierarchical spectral clustering methods Table 12 underscore our approach's advantage in multi-level segmentation, achieving higher NMCovering scores and consistent performance even without the need for CRF postprocessing.Table 7 : Boundary potential vs. semantic smoothness. Comparison among hierarchical clustering algorithms in terms of NMCovering on PascalVOC2012 val set for λ max = 0.6.Table 8 : Hierarchical semantic segmentation on Potsdam and Vaihingen train sets. We use DINO-ViT-B8 [11] features and λ max = 0.9. The two datasets have six categories. Segmentation performances are computed using NMCovering for ground truth masks exclusive matching. 13 : Hierarchical semantic segmentation on the COCO-Stuff val set. We use DINO-ViT-B8 [11] features and λ max = 0.6. COCO-Stuff dataset has 91 'thing' categories (inherited from MSCOCO), 91 'stuff' categories and 27 supercategories. Segmentation performances are computed using NHCovering for exclusive matching of predictions with ground truth masks. The rows show the hierarchical structure of COCO-Stuff. The first column shows the separation between things/stuff. The second column shows supercategory labels (Coarse Tags), the third column shows the relative supercategory IoU (IoU S ) when considering all supercategories together, and the fourth column considers 12 things supercategories only, and the fifth column considers 15 stuff supercategories only. Sixth column shows leaf labels (Fine Tags), seventh column shows relative category IoU (IoU) when considering all categories, the eighth column considers 91 thing categories only and the ninth column considers 91 stuff categories only. Last row shows mean IoU (mIoU), frequency weighted IoU (fIoU), pixel accuracy (pAcc), and mean accuracy (mAcc) for each experiment. Here, accuracy values are reported in the decimal range [0, 1]. Justification: We introduce and explain the reasons for the new problem setting in Section 3 and our new metric in Section 4.1. The task also defines a new downstream task for SSL, which does not require additional training or prior, and reports some baselines in Table 5 . We introduce our algebraic method for image pixel parsing via semantic regions tree in Section 3.1. In the same section, we define our smoothness criteria for deep features graph partitioning and our method for dynamically establishing connected components. In Tables 1 and 2 , we conduct several experiments to validate the robustness of our algorithm on different datasets. In Tables 5 and 6 , we report ablation experiments to assess the importance of each algorithm component. In Table 3 , we compare our results with different semantic segmentation supervision strategies to benchmark the segmentation quality of our approach; at the same time, we demonstrate that the proposed hierarchical image parsing effectively found visual semantic concepts in the images of a dataset, whether they are object or scene centric, see Table 1 , and whole or part centric, see Tables 2 and 6b . Further experiments in Table 4 demonstrate the effectiveness of the algorithm in capturing semantic hierarchical relationships and an improvement over previous traditional hierarchical models used nowadays in some unsupervised semantic segmentation SOTA to drive the optimization. We hope our findings may improve research in this direction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material.• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).We introduce new metrics for estimating the quality of the semantic segmentation of the elements discovered on the different levels of the hierarchy, called Normalised Multigranular Covering (NMCovering) and Normalised Hierarchical Covering (NHCovering).3. We integrate the method into various self-supervised learning models to enhance its flexibility for benchmarking purposes, making it suitable as a downstream task through unsupervised segmentation by inferring all scene parts in the images of any given dataset.We generalize G and L to denote any subgraph and its Laplacian, rather than just the original image graph.We ran four experiments for each dataset with random seed and assumed normally distributed errors. However, in the segmentation literature, mIoU is typically reported by the single mean value in percentage. 


Decision: This paper proposes unsupervised semantic segmentation by recursive spectral clustering.

It has received 2x weak accepts, 1x borderline accept, and 1x accept.  Authors have an extensive rebuttal with additional clarification and results.  Reviewers like the unsupervised algebraic approach, new metrics for estimating the quality of the semantic segmentation at different levels of the discovered hierarchy, and performance gains.  They also point out the limitations on frozen features, reliance on superpixels, minor technical innovation, unfair comparisons with stronger backbone features, hyper-parameter sensitivity, and convoluted writing.

The AC recommends acceptance based on the consensus.   Please take all the comments and rebuttal into account to improve the final version.

~~~~~~~~~~~~~~~~~~~~~~~~
Here are some extra comments from SAC. 
(1) The authors are suggested to pay much effort in the layout and font size of tables, where some results can be put into appendix. 
(2) Abstract, introduction, and related work can be trimmed. If necessary, the extensive discussion on related work can be also moved into appendix.

Reviews: review: paper_summary: paper_summary: The submission presents a way to get hierarchical segmentations from the features extracted by an unsupervised semantic segmentation model. It builds a graph representation from the features or "codes" from the network. Spectral clustering is computed on this graph, followed by recursively partitioning the clusters until certain stopping conditions are met (for which the partition won't be further subdivided). It also proposes new evaluation metrics for evaluating a hierarchical segmentation against ground-truth pixel labels.
strength_weakness: strength_weakness: iv) Features are frozen.

From what I can tell, the hierarchy found by this method doesn't, and isn't meant to, play a role in the training of the feature extractor. This therefore seems likely to have a more limited impact than some related work, such as [42, 88]. Since the feature extractor could also be used as a foundation for other segmentation or vision tasks.

v) Reliance on superpixel pre-processing. This is a practical choice, but it would likely limit the method at the finest levels of the hierarchy.
questions: questions: 1. Is there some property of the proposed method that limits it to using features/codes from the self-supervised and unsupervised models described in section 2, such as DINO, STEGO and Smooseg? Or could it also be applied to codes from any arbitrary model that extracts dense image segmentation features?
2. What's the motivation for the specifics of stopping criterion #3? As in, it seems quite intuitive to look at the eigenvalues and the "smoothness" of the labelling, but why a fixed threshold? Is there any relationship to the use of the eigengap as a measure of the number of clusters?
3. Was ablating the CRF boundary sharpening also looked at for other datasets, such as Cityscapes and Mapillary Vistas?
limitations: limitations: Limitations seem clear from the authors' own description. One limitation that might follow from (iii) is that the method couldn't discover sub-parts not learned by the original feature extractor training: for example if the pixel features/codes don't differentiate a given part from its surrounding object.
paper_summary: paper_summary: The paper proposes a spectral-clustering approach to hierarchically segment an image, in an unsupervised fashion. The method starts from self-supervised features assigned to each pixel. Then, a recursive partitioning is obtained by minimizing a quadratic form for a given level of the hierarchy, and repeating the process until a stopping criterion is met. For faster computation, it is possible to start from superpixels. A Conditional Random Field can be applied on the boundaries to refine the prediction. 

The core of the approach is the definition of a smoothness of function labelling on a graph, the minimization of which leads to a given level of the hierarchy. 

Experiments show that the method achieves state-of-the-art results on several datasets.
strength_weakness: strength_weakness: - The writing of the paper could have been simpler, and more to the point. I find that many sentences are convoluted, which makes it difficult to understand the description of the method. For example, I did not understand the method until I read the first paragraph of Appendix A. 
- At a high-level, the difference of this paper with papers like [56] is only the spectral clustering method used in the process. There are other differences, but they are minor in theory.
questions: questions: - I do not understand why the Normalized cuts (or any other spectral method) would not lead to the same kind of results. Specifically, I would like an ablation experiment in which another spectral method is used, as in [56] for example, but with the same superpixels, same network, and similar other details. The question is then: is the minimization of the smooth function-labelling the important idea here, or some other component of the approach? I believe the difference should not be as high as it appears in the paper.
limitations: limitations: The authors state that their approach can be slow, but no timing is reported.
paper_summary: paper_summary: This paper addresses the problem of unsupervised hierarchy-agnostic segmentation by treating it as a graph partitioning problem. Specifically, each node in the graph represents a part, while the weighted edges, measured by similarity scores, reflect the connections between parts. The graph is recursively partitioned until a stopping criterion is met. To facilitate the graph partitioning, superpixel segmentation is initially performed to construct the graph, and boundary sharpening is applied post-partitioning as a technique to improve segmentation results.
The paper also introduces two new metrics: Normalized Multigranular Covering and Normalized Hierarchical Covering, which ensure that both foreground and background instances, as well as hierarchical inclusion, are considered. Experiments conducted on popular benchmarks demonstrate the strong capability of the proposed method as an unsupervised segmentation approach.
strength_weakness: strength_weakness: - The pre-trained DINOv2-ViT-B14-REG backbone is a very strong backbone and also a strong requirement when compared to other unsupervised segmentation model, which harms the fair comparison.
- The newly introduced metrics would be more clear if they could come with an example to illustrate the computation process step by step.
questions: questions: Please refer to the weaknesses.
limitations: limitations: Limitations and broader impact of the proposed method are discusses in the paper. No other discussions are must needed.
paper_summary: paper_summary: The paper presents a novel approach to unsupervised semantic image segmentation.  The authors introduce a novel algebraic methodology that constructs a hierarchy-agnostic semantic region tree, which dynamically identifies scene-conditioned primitives and creates a nuanced and unbiased segmentation of image pixels.
Key contributions of the paper include:
- A deep recursive spectral clustering method that maximizes an unbiased measure of total semantic similarity across multiple levels of semantic granularity.
- The integration of this method with diverse self-supervised learning models to enhance flexibility and applicability in unsupervised segmentation tasks.
- The introduction of new metrics, namely Normalized Multigranular Covering (NMCovering) and Normalized Hierarchical Covering (NHCovering), for estimating the quality of semantic segmentation at different levels of hierarchy.
strength_weakness: strength_weakness: - The proposed approach has a few critical hyperparameters (the minimum number of points in a partition $k_{min}$, a threshold $p_{max}$,   a maximum eigenvalue $\lambda_{max}$) which if not properly set can degrade the performance.
questions: questions: no
limitations: limitations: see weakness

Comments: comment: Thanks for the detailed answer. 

As I have some concerns regarding the writing of the paper (I find the paper somehow difficult to read), I maintain my previous score of weak accept.