Paper deep dive
Understanding Submodular Information Measure Based Objectives for Representation Learning: A Variance and Separation Perspective
Rishabh Iyer, Truong Pham, Anay Majee
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/1/2026, 1:57:49 AM
Summary
This paper provides a unified theoretical framework connecting Submodular Information Measures (SIMs) to classical concepts in representation learning. It demonstrates that Total Information (TI) objectives based on Graph Cut, LogDet, and Facility Location functions recover within-class variance, generalized variance, and imbalance-aware separation, respectively. Similarly, Mutual Information (MI) objectives capture inter-class structures such as centroid separation, covariance-aware separation, and representational overlap. The authors validate these characterizations through synthetic experiments, offering principled guidance for selecting SIM-based objectives.
Entities (12)
Relation Signals (7)
LogDet Mutual Information → captures → Covariance-aware separation
confidence 95% · LogDet MI captures covariance-aware separation through Mahalanobis distance
Facility Location Total Information → induces → Imbalance-aware separation
confidence 95% · Facility Location TI induces imbalance-aware separation that emphasizes rare and confusable classes
Graph Cut Mutual Information → isrelatedto → Centroid separation
confidence 95% · Graph Cut MI is closely related to centroid separation and Fisher-style discrimination
Facility Location Mutual Information → measures → Representational overlap
confidence 95% · Facility Location MI measures nearest-mode representational overlap
Graph Cut Total Information → recovers → Within-class variance
confidence 95% · Graph Cut TI recovers within-class variance
LogDet Total Information → recovers → Generalized variance
confidence 95% · LogDet TI recovers generalized variance and covariance volume
SCORE → uses → Submodular Information Measures
confidence 95% · the SCORE framework demonstrated that SIMs can serve as effective objectives for supervised contrastive learning
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Submodular Information Measures (SIMs) have recently emerged as a powerful framework for representation learning and multimodal learning. In particular, the SCORE framework~\cite{majee2024score} demonstrated that SIMs can serve as effective objectives for supervised contrastive learning. Despite their empirical success, however, the geometric and statistical properties induced by different submodular information measures remain poorly understood. In this work, we develop a unified theoretical framework connecting SIMs to classical concepts in representation learning and statistical pattern recognition. We show that Total Information (TI) objectives characterize intra-class structure: Graph Cut TI recovers within-class variance, LogDet TI recovers generalized variance and covariance volume, and Facility Location TI induces imbalance-aware separation that emphasizes rare and confusable classes. We further show that Mutual Information (MI) objectives capture complementary notions of inter-class structure: Graph Cut MI is closely related to centroid separation and Fisher-style discrimination, LogDet MI captures covariance-aware separation through Mahalanobis distance, and Facility Location MI measures nearest-mode representational overlap. We validate these theoretical characterizations using controlled synthetic experiments that independently vary variance, covariance, class imbalance, class separation, and multimodal overlap. Across all settings, the empirical behavior closely matches the proposed theory. Our results provide the first unified geometric and statistical understanding of submodular information measures and offer principled guidance for selecting and designing SIM-based objectives for representation learning.
Tags
Links
- Source: https://arxiv.org/abs/2607.27660v1
- Canonical: https://arxiv.org/abs/2607.27660v1
Trouble viewing inline? Open PDF directly →
Full Text
92,148 characters extracted from source content.
Expand or collapse full text
Understanding Submodular Information Measure Based Objectives for Representation Learning: A Variance and Separation Perspective Rishabh Iyer The University of Texas at Dallas, Richardson, TX, USA Truong Pham The University of Texas at Dallas, Richardson, TX, USA Anay Majee Adobe, San Jose, CA, USA Abstract Submodular Information Measures (SIMs) based objectives and loss functions have recently emerged as a powerful framework for representation learning and multi-modal learning. In particular, the SCORE framework [23] demonstrated that SIMs can serve as effective objectives for supervised contrastive representation learning, yielding strong performance across balanced and long-tailed recognition settings. Despite these empirical successes, the geometric and statistical properties induced by different submodular information measures remain poorly understood. In particular, it is unclear what notions of compactness, separation, diversity, and coverage are optimized by different SIM formulations. In this work, we develop a unified theoretical framework connecting submodular information measures to classical concepts in representation learning and statistical pattern recognition. We show that Total Information (TI) formulations based on diversity-oriented submodular functions naturally recover measures of intra-class variability. In particular, Graph Cut based TI objectives correspond to classical within-class variance, while LogDet based TI objectives recover generalized variance and covariance volume. We further show that Mutual Information (MI) formulations capture complementary notions of inter-class structure. Graph Cut based MI objectives are closely related to centroid separation and Fisher-style discriminative criteria, while Facility Location based MI objectives quantify representational overlap and modal coverage between classes. LogDet based MI objectives capture covariance-aware separation related to Mahalanobis and generalized discriminant distances. To validate these characterizations, we design a suite of controlled synthetic experiments that independently manipulate variance, covariance structure, class imbalance, class separation, and multimodal overlap. Across all settings, the empirical behavior of the corresponding information measures closely matches the proposed theoretical interpretations. Our analysis reveals that different submodular information measures induce fundamentally different geometric biases, ranging from variance reduction and covariance control to coverage and multimodal representation. These results provide the first unified understanding of SIMs for representation learning and offer principled guidance for selecting and designing future submodular objectives. 1 Introduction Learning effective representations is a central problem in modern machine learning. Deep neural networks trained with cross-entropy objectives have achieved remarkable success across vision, language, and multimodal tasks [27, 8, 30, 18]. More recently, contrastive and metric-learning approaches such as SimCLR [2], MoCo [7], Supervised Contrastive Learning [14], ArcFace [3], CosFace [34], Triplet Loss [29], and Center Loss [36] have demonstrated that explicitly shaping the geometry of the representation space can substantially improve generalization, robustness, and transferability. Despite their diversity, these methods share a common objective: learning embeddings that simultaneously encourage intra-class compactness and inter-class separation. The importance of balancing compactness and separation can be traced back to classical discriminant analysis [4], where the quality of a representation is characterized by the ratio between between-class and within-class scatter. Modern representation learning methods instantiate this principle through a variety of objectives, including pairwise similarity losses [29, 32, 31], angular-margin losses [3, 34], contrastive objectives [14, 2], covariance regularization [1], and neighborhood-preservation criteria [5]. While these objectives differ significantly in their formulation, they all seek to control the geometry of representations through notions of variance, covariance, separation, and diversity. In parallel, a distinct line of work has explored submodular optimization as a principled framework for modeling representation, diversity, coverage, and information [35, 6, 10, 12, 13]. Submodular functions have been widely applied to data subset selection, summarization, active learning, and representation learning [20, 12, 15, 17, 11]. A particularly powerful family of objectives is provided by submodular information measures (SIMs), which generalize classical notions of mutual information through submodular set functions [9]. SIMs have enabled targeted data selection [15, 16], distribution-shift-aware subset selection [11], and more recently representation learning and multi-modal learning [23, 24]. SCORE [23] demonstrated that submodular information measures can serve as effective objectives for supervised representation learning. By constructing positive and negative sets from class labels and maximizing appropriate information measures between them, SCORE achieved competitive performance across multiple representation-learning benchmarks. SMILE [24] extended the formulation of SCORE to few-shot representation learning, and showed that using the submodular mutual information based objectives can enable learning of new classes without forgetting known classes. In [21], the authors proposed a framework called CROWD that used the objectives from SCORE and SMILE for open world learning problems, while [22] proposed a new family of loss functions for hard sample mining. Finally, [26] proposed the Submodular Modality Aligner, a new family of objective functions for multi-modal alignment. However, despite its empirical success, a fundamental question remains unanswered: what geometric properties of the embedding space are induced by different submodular information measures?. In SCORE [23], SMILE [24], SHaSaM [22], and SMA [26], various variants of Total Submodular Information (TI) and Submodular Mutual Information (SMI) variants have been proposed – including Facility Location TI, Log-Det TI, Graph Cut Mutual Information (GCMI), Facility Location Mutual Information (FLQMI), LogDet Mutual Information and their variants [17, 11, 9]. However, there is currently little understanding of the representation-learning biases encoded by these objectives. This lack of understanding creates an important gap between theory and practice. Existing work largely treats different SIMs as interchangeable objective functions, selecting them empirically based on downstream performance [23, 24, 22, 26]. Yet our experiments reveal that different SIMs induce fundamentally different geometric structures. For example, Graph Cut based objectives are closely related to variance-separation criteria and favor global class separation, while Facility Location based objectives emphasize coverage and multimodal representation. LogDet-based objectives, in contrast, explicitly capture covariance structure and generalized variance. These differences become especially pronounced in settings involving multimodal classes, long-tailed distributions, and heterogeneous semantic concepts, where distinct SIMs exhibit markedly different behaviors. In this paper, we develop the first systematic theoretical and empirical study of submodular information measures for representation learning. We establish explicit connections between several widely used SIMs and classical statistical quantities including variance, covariance, generalized variance, class separation, and coverage. We show that Graph Cut based measures recover variance-separation objectives analogous to Fisher-style discriminant criteria, while Facility Location based measures provide coverage-oriented objectives that better capture multimodal class structure. We further characterize the regimes in which these objectives agree and diverge, and derive theoretical results explaining their behavior under class imbalance and multimodal distributions. Our analysis yields both theoretical insights and practical guidance. Through synthetic studies, visualization experiments, and representation-learning benchmarks, we demonstrate that no single SIM is universally optimal. Instead, different information measures encode different inductive biases that make them suitable for different representation-learning regimes. These results provide a principled foundation for selecting and designing submodular information measures for representation learning and establish new connections between submodular optimization, information theory, and modern representation learning. Contributions. Our primary contributions are: 1. A unified geometric theory of Submodular Information Measures. We develop a theoretical framework connecting Submodular Information Measures (SIMs) to classical concepts in statistical pattern recognition and representation learning. Our analysis reveals that different SIMs recover fundamentally different notions of intra-class variability and inter-class separation. 2. Characterization of Total Information objectives. We show that Graph Cut Total Information recovers classical within-class variance, LogDet Total Information recovers generalized variance through covariance volume, and Facility Location Total Information induces imbalance-aware separation margins that naturally emphasize rare and confusable classes. 3. Characterization of Mutual Information objectives. We establish that Graph Cut Mutual Information is intimately connected to aggregate centroid separation and show that the combined GC-TI and GCMI objective exactly recovers the classical aggregate mean-separation criterion. We further show that LogDet Mutual Information recovers Mahalanobis-style covariance-aware separation, while Facility Location Mutual Information captures nearest-mode representational overlap in multimodal settings. 4. A unified view of SCORE objectives. Our results provide the first theoretical explanation of the representation-learning biases induced by the SCORE framework, revealing how different combinations of Total Information and Mutual Information objectives recover distinct classical discriminative criteria. 5. Comprehensive empirical validation. We design a suite of controlled synthetic experiments that independently manipulate variance, covariance structure, class imbalance, centroid separation, and multimodal overlap. Across all settings, the empirical behavior of the corresponding information measures closely matches the proposed theoretical characterizations. 2 Background and Preliminaries In this section, we briefly review representation learning, submodular functions, submodular information measures, and the SCORE framework that motivates our analysis. 2.1 Representation Learning Let =(xi,yi)i=1ND=(x_i,y_i)_i=1^N denote a labeled dataset with K classes, where yi∈1,…,Ky_i∈1,…,K. Given an encoder f∗θf*θ, each sample is mapped to a representation zi=fθ(xi)∈ℝd.z_i=f_θ(x_i) ^d. (1) A central objective in supervised representation learning is to learn embeddings that are both compact within a class and well separated across classes. Classical approaches such as Fisher’s Linear Discriminant Analysis [4] formalize this principle through within-class and between-class scatter matrices, while modern metric-learning and contrastive-learning methods achieve similar goals through pairwise, triplet, or contrastive objectives [29, 36, 2, 14, 3, 34]. For a class CcC_c, let μc=1|Cc|∑i∈Cczi _c= 1|C_c| _i∈ C_cz_i (2) denote the class centroid. Throughout the paper, we will connect submodular information measures to classical notions of: • Intra-class variability, which measures how dispersed samples are within a class. • Inter-class separation, which measures how distinct different classes are from one another. • Coverage and representation, which quantify how well one set of samples represents another. 2.2 Submodular Functions Let V denote a finite ground set. A set function f:2V→ℝf:2^V is submodular if it satisfies the diminishing returns property: f(A∪j)−f(A)≥f(B∪j)−f(B)f(A∪j)-f(A)≥ f(B∪j)-f(B), for all A⊆B⊆VA B V and j∉Bj∉ B. Submodular functions naturally model notions of representation, diversity, and coverage and have been extensively used in subset selection, summarization, active learning, and information maximization [6, 10, 20]. Throughout this work, we focus on four commonly used submodular functions (Graph Cut, Facility Location, and Log Determinant): Graph Cut (GC). Graph Cut captures a tradeoff between representation and diversity and is defined over a similarity matrix S as fGC(A)=λ∑i∈A∑j∈Vsij−∑i,j∈Asij.f_GC(A)=λ _i∈ A _j∈ Vs_ij- _i,j∈ As_ij. (3) Facility Location (FL). Facility Location is a representation-oriented function that measures how well a subset represents the ground set: fFL(A)=∑i∈Vmaxj∈Asij.f_FL(A)= _i∈ V _j∈ As_ij. (4) LogDet (LD). LogDet is a diversity-oriented function based on the determinant of a similarity kernel. It is closely related to determinantal point processes and generalized variance [19]. fLD(A)=logdet(SA).f_LD(A)= (S_A). (5) These functions represent distinct notions of diversity, coverage, and representation, and form the basis of the information measures [9] studied in this paper. 2.3 Submodular Information Measures Submodular Information Measures (SIMs) generalize classical information-theoretic quantities using submodular set functions [9]. Given a submodular function f, the corresponding submodular mutual information between two sets A and B is defined as If(A;B)=f(A)+f(B)−f(A∪B).I_f(A;B)=f(A)+f(B)-f(A∪ B). (6) Different choices of f induce different notions of similarity and dependence. For example, Graph Cut Mutual Information (GCMI), Facility Location Mutual Information (FLQMI), and LogDet Mutual Information (LogDetMI) arise from choosing Graph Cut, Facility Location, and LogDet functions respectively [15, 17, 11]. Complementary to MI is the notion of Total Information (TI), which measures the aggregate dependence among multiple sets: TIf(C1,…,CK)=∑c=1Kf(Cc)TI_f(C_1,…,C_K)= _c=1^Kf(C_c) (7) Throughout this work, we analyze mainly the TI and MI formulations and show that they capture distinct geometric properties of the representation space. 2.4 SCORE: Submodular Combinatorial Representation Learning Recently, Majee et al. [23] proposed SCORE, a supervised representation learning framework based on submodular information measures. SCORE constructs positive and negative sets using class labels and optimizes submodular objectives directly in the embedding space. Given an embedding function fθf_θ, SCORE defines a similarity matrix over representations and computes the Total Information (TI) and Total Correlation (TC) variants. Different choices of the underlying submodular function lead to different learning objectives, including Graph Cut, Facility Location, and LogDet variants. Empirically, SCORE demonstrated that submodular information measures provide effective objectives for supervised representation learning and achieve strong performance across balanced, imbalanced, and long-tailed recognition settings. However, despite these empirical successes, the geometric and statistical properties induced by different information measures remain poorly understood. The goal of this paper is to provide a unified theoretical understanding of these objectives. In particular, we ask: What notions of variability, separation, and coverage are optimized by different submodular information measures? By connecting SIMs to classical statistical quantities such as variance, covariance volume, mean separation, and modal coverage, we develop a principled understanding of the representation-learning biases induced by different submodular objectives. 3 A Unified Geometric View of Submodular Information Measures The central goal of this paper is to understand the geometric biases induced by different submodular information measures. While prior work has demonstrated that Graph Cut, Facility Location, LogDet, and Coverage-based information measures are effective for representation learning [15, 17, 11, 23], there is currently little understanding of the statistical quantities they optimize. In this section, we introduce the key geometric quantities studied throughout the paper, present a generic formulation of SCORE, and summarize the main theoretical results established in subsequent sections. 3.1 Variance, Separation, and Coverage Consider a collection of classes C1,…,CKC_1,…,C_K, where each class CcC_c consists of embedded samples zi∈ℝdz_i ^d. Let 1|Cc|∑i∈Cczi 1|C_c| _i∈ C_cz_i denote the centroid of class CcC_c, and let 1|Cc|∑i∈Cc(zi−μc)(zi−μc)T 1|C_c| _i∈ C_c(z_i- _c)(z_i- _c)^T denote its covariance matrix. A central theme of this paper is that there is no unique notion of either intra-class variability or inter-class separation. Instead, different objectives emphasize different geometric properties of the representation space. We therefore begin by introducing several classical quantities that will later be connected to specific submodular information measures. 3.1.1 Quantifying Intra-Class Structure The most common notion of intra-class variability is the within-class variance: Intra-Class-Var(C1,⋯,Ck)=∑c=1K∑i∈Cc|zi−μc|2=12∑c=1K1|Cc|∑i,j∈Cc|zi−zj|2 -Class-Var(C_1,·s,C_k)= _c=1^K _i∈ C_c|z_i- _c|^2= 12 _c=1^K 1|C_c| _i,j∈ C_c|z_i-z_j|^2 (8) The second equality holds using standard variance identities. Thus, within-class variance may be interpreted either through distances to class centroids or through average pairwise distances within a class. A more general notion of variability is provided by the generalized variance: Intra-Class-GenVar(C1,⋯,Ck)=∑c=1Klogdet(Σc) -Class-GenVar(C_1,·s,C_k)= _c=1^K ( _c) (9) which captures not only the magnitude of variation but also the covariance structure and effective dimensionality of each class. 3.1.2 Quantifying Inter-Class Structure Mean-Based Inter-Class Separation. A classical notion of inter-class separation is the pairwise centroid separation: Mean-SeparationMB(C1,⋯,Ck)=∑i<j|μi−μj|2 -Separation_MB(C_1,·s,C_k)= _i<j| _i- _j|^2 (10) This quantity forms the basis of between-class scatter in Fisher’s discriminant analysis and measures how far apart class centroids are in the embedding space. Covariance-Aware Inter-Class Separation. A second notion of separation accounts for covariance structure through Mahalanobis distances: Cov-Separation(C1,⋯,Ck)=∑i<j(μi−μj)TΣ−1(μi−μj) -Separation(C_1,·s,C_k)= _i<j( _i- _j)^T ^-1( _i- _j) (11) where Σ denotes an appropriate pooled covariance matrix. Unlike centroid separation, this quantity measures separation relative to the variability of the classes and therefore captures discriminability rather than distance alone. Representational Overlap. A third notion of inter-class structure is representational rather than geometric. Instead of asking whether class centroids are far apart, one may ask whether the modes of one class can be represented by another class. If overlap occurs across many modes, the two classes exhibit high representational overlap. If overlap is confined to only a few modes, the classes remain distinguishable despite potentially similar centroid locations. As we show later, Facility Location based mutual information naturally captures this notion of representational overlap. 3.2 A Generic SCORE Objective A central observation underlying SCORE [23] is that effective representation learning requires simultaneously controlling both intra-class variability and inter-class bias. The former determines the compactness and diversity of individual classes, while the latter governs the relationships among different classes. This perspective naturally motivates the use of submodular information measures within a representation learning framework. Let =C1,…,CKC=\C_1,…,C_K\ denote the collection of classes and let If(⋅;⋅)I_f(·;·) denote a submodular mutual information measure induced by a submodular function f. A generic SCORE-style objective can be written as ℒSCORE=λTITIf(C1,…,CK)+λSMI∑i<jIf(Ci;Cj),L_SCORE= _TITI_f(C_1,…,C_K)+ _SMI _i<jI_f(C_i;C_j), (12) where λTI _TI and λSMI _SMI control the relative importance of the two terms. In the original SCORE paper [23], the first term (TI) was proposed while the second term was used for few-shot representation learning in [24]. In this paper, we analyze the combined objective, and we can get back the objective from [23] by setting λSMI _SMI as 0. This decomposition naturally separates representation learning into two components: SCORE=TI⏟Multi-Class Information+SMI⏟Pairwise Class Information.SCORE= TI_Multi-Class Information+ SMI_Pairwise Class Information. (13) A key observation of this paper is that neither TI nor SMI admits a universal geometric interpretation. Rather, the quantities captured by these objectives depend fundamentally on the choice of the underlying submodular function. Broadly speaking, submodular functions used in representation learning can be categorized according to whether they emphasize representation, diversity, or a combination of both. • Representation-oriented functions emphasize how well one set represents another. Examples include Facility Location and Saturated Coverage. • Diversity-oriented functions emphasize dispersion among elements. Examples include LogDet and dispersion-based objectives. • Hybrid functions simultaneously contain representation and diversity components. The most prominent example is Graph Cut, fGC(A)=λ∑i∈A∑j∈Vsij−∑i,j∈Asij,f_GC(A)=λ _i∈ A _j∈ Vs_ij- _i,j∈ As_ij, (14) where the first term is representation-oriented while the second term is diversity-oriented. This distinction is important because the geometric interpretation of TI and SMI depends strongly on the underlying submodular function. For diversity-oriented functions such as Graph Cut and LogDet, the TI formulations will be shown to recover classical notions of intra-class variability, including pairwise variance and generalized variance. In contrast, for representation-oriented functions such as Facility Location and Saturated Coverage, the TI formulations induce quantities that are closely related to inter-class representation and bias. Similarly, different SMI functions induce different notions of inter-class structure. As we show later, Graph Cut Mutual Information is closely related to centroid separation, LogDet Mutual Information captures covariance-aware separation, while Facility Location Mutual Information captures representational overlap between classes. Consequently, the geometric behavior of a SCORE objective is determined jointly by two factors: 1. The information measure being optimized (TI or SMI). 2. The representation-versus-diversity characteristics of the underlying submodular function. The primary goal of this paper is to characterize the notions of intra-class variability and inter-class bias induced by different combinations of these two factors. 3.3 Summary of Main Results The central question studied in this paper is: What notions of intra-class variability and inter-class bias are induced by different submodular information measures? Our analysis reveals that the behavior of a SCORE objective is governed jointly by the information measure being optimized (TI or SMI) and the representation-versus-diversity characteristics of the underlying submodular function. In particular, we establish the following results: • Graph Cut TI and intra-class variance. We show that Graph Cut based Total Information admits a decomposition into inter-class bias and intra-class variance terms. Under suitable parameterizations, the diversity component recovers classical within-class variance and its equivalent pairwise-distance formulation. • LogDet TI and generalized variance. We show that LogDet based Total Information recovers generalized variance and covariance volume, thereby capturing both the magnitude and covariance structure of within-class variability. • Representation-oriented TI objectives and inter-class bias. Unlike diversity-based objectives, representation-oriented functions such as Facility Location and Saturated Coverage induce Total Information formulations that depend explicitly on interactions between classes, yielding notions of inter-class representation and bias rather than classical intra-class variability. • Graph Cut Mutual Information and mean separation. We establish a direct connection between Graph Cut Mutual Information and classical notions of centroid separation and between-class scatter. • LogDet Mutual Information and covariance-aware separation. We show that LogDet Mutual Information captures covariance-aware notions of separation and admits connections to Mahalanobis and Fisher-style discriminative criteria. • Facility Location Mutual Information and representational overlap. We show that Facility Location based mutual information induces a distinct notion of representational overlap, quantifying the extent to which the modes of one class are represented by another. Together, these results provide a unified geometric interpretation of submodular information measures and explain the distinct representation-learning biases induced by different SCORE objectives. Table 1 provides a clean summary of the different objectives (TI and MI) and the respective variance and bias quantities recovered. Table 1: Summary of the geometric biases induced by different Submodular Information Measures. Measure Category Quantity Recovered GC-TI Intra-Class Within-class variance LogDet-TI Intra-Class Generalized variance FL-TI Inter/Intra-Class Rare-class margin expansion GCMI Inter-Class Aggregate overlap / centroid separation GC-TI + GCMI Inter + Intra Class Aggregate mean separation LogDetMI Inter-Class Mahalanobis separation FLQMI Inter-Class Nearest-mode overlap 4 Total Information Objectives In this section, we study Total Information (TI) objectives and characterize the geometric quantities induced by different submodular functions. Recall that for a collection of classes =C1,…,CKC=C_1,…,C_K, the Total Information induced by a submodular function f is given by TIf(C1,…,CK)=∑c=1Kf(Cc).TI_f(C_1,…,C_K)= _c=1^Kf(C_c). (15) Unlike Submodular Mutual Information, which explicitly models interactions between pairs of classes, Total Information aggregates the contribution of each class independently. Nevertheless, as we show below, the resulting objective need not be purely intra-class in nature. Depending on the underlying submodular function, TI objectives can induce both intra-class variability terms and inter-class bias terms. A key observation of this paper is that the behavior of a TI objective depends strongly on whether the underlying submodular function is diversity-oriented, representation-oriented, or a combination of both. Diversity-based functions naturally recover classical notions of intra-class variability, while representation-based functions induce interactions between classes and therefore capture notions of inter-class representation and bias. In the remainder of this section, we analyze four widely-used submodular functions: (i) Graph Cut (GC), (i) LogDet (LD), (i) Facility Location (FL), and (iv) Saturated Coverage (SatCov). For each function, we derive the corresponding Total Information objective and connect it to classical statistical quantities arising in representation learning and pattern recognition. 4.1 Graph Cut Total Information We begin with Graph Cut, which occupies a unique position among submodular functions because it simultaneously contains representation and diversity components. Recall that the Graph Cut function is defined as fGC(A)=λ∑i∈A∑j∈Vsij−∑i,j∈Asij,f_GC(A)=λ _i∈ A _j∈ Vs_ij- _i,j∈ As_ij, (16) where S=[sij]S=[s_ij] denotes a similarity matrix and λ∈[0,1]λ∈[0,1] controls the balance between representation and diversity. Substituting this expression into the Total Information objective yields TIGC=∑c=1KfGC(Cc)=λ∑c=1K∑k∈Cc∑l∈Vskl−∑c=1K∑k,l∈Ccskl. TI_GC= _c=1^Kf_GC(C_c)\ =λ _c=1^K _k∈ C_c _l∈ Vs_kl- _c=1^K _k,l∈ C_cs_kl. (17) Separating the first term into within-class and cross-class contributions gives TIGC TI_GC =λ∑c=1K∑k∈Cc(∑l∈Ccskl+∑l∈V∖Ccskl)−∑c=1K∑k,l∈Ccskl =λ _c=1^K _k∈ C_c ( _l∈ C_cs_kl+ _l∈ V C_cs_kl )- _c=1^K _k,l∈ C_cs_kl (18) =λ∑c=1K∑k∈Cc∑l∈V∖Ccskl−(1−λ)∑c=1K∑k,l∈Ccskl. =λ _c=1^K _k∈ C_c _l∈ V C_cs_kl-(1-λ) _c=1^K _k,l∈ C_cs_kl. (19) Equation (19) reveals an important decomposition. The first term measures interactions between a class and all points outside the class and therefore induces a notion of inter-class bias. The second term depends only on pairwise similarities within each class and therefore captures intra-class variability. This decomposition is particularly interesting because it mirrors the classical representation learning objective of simultaneously maximizing inter-class separation while minimizing intra-class variability. Unlike purely diversity-oriented or purely representation-oriented functions, Graph Cut naturally contains both components within a single objective. In the next subsection, we establish a direct connection between the diversity component of Graph Cut Total Information and classical within-class variance under an appropriate similarity model. 4.1.1 Graph Cut TI and Within-Class Variance We now establish a connection between the diversity component of Graph Cut Total Information and classical within-class variance. Consider the shifted Euclidean similarity sij=M−|zi−zj|2,s_ij=M-|z_i-z_j|^2, (20) where M is a sufficiently large constant ensuring non-negativity of the similarity matrix. Substituting Equation (20) into the diversity component of Equation (19) yields ∑k,l∈Ccskl=∑k,l∈Cc(M−|zk−zl|2)=|Cc|2M−∑k,l∈Cc|zk−zl|2. _k,l∈ C_cs_kl= _k,l∈ C_c (M-|z_k-z_l|^2 )\ =|C_c|^2M- _k,l∈ C_c|z_k-z_l|^2. (21) Thus, up to an additive constant, maximizing the diversity component of Graph Cut TI is equivalent to maximizing the total pairwise distance within each class. The following theorem establishes the precise connection. Theorem 1. Define the similarity kernel as follows: sij=M−|zi−zj|2.s_ij=M-|z_i-z_j|^2. (22) The Graph-Cut Total Information with λ=0λ=0 satisfies: TIGC(C1,⋯,Ck)=−∑c=1K∑k,l∈Ccskl=−2∑c=1K|Cc|∑k∈Cc|zk−μc|2+const,TI_GC(C_1,·s,C_k)=- _c=1^K _k,l∈ C_cs_kl=-2 _c=1^K|C_c| _k∈ C_c|z_k- _c|^2+const, (23) where μc _c denotes the centroid of class CcC_c. Consequently, Graph Cut Total Information recovers classical within-class variance up to a class-dependent scaling factor and an additive constant. Theorem 1 provides a direct connection between Graph Cut based Total Information and one of the most fundamental quantities in statistical pattern recognition. In particular, the diversity component of Graph Cut TI recovers the classical within-class scatter objective used in Fisher’s Linear Discriminant Analysis. An important implication is that minimizing Graph Cut TI encourages compact class representations by reducing within-class variability. Furthermore, because the derivation is based on pairwise distances, the resulting objective remains valid for multimodal classes and does not rely on any explicit centroid computation. In Section 6, we empirically validate this characterization by constructing synthetic datasets with controlled within-class variance and demonstrating that Graph Cut Total Information tracks the resulting variability almost perfectly. 4.2 LogDet Total Information and Generalized Variance We next consider LogDet, a diversity-oriented submodular function that has been widely used in subset selection, determinantal point processes, and diversity maximization. Recall that the LogDet function is defined as fLD(A)=logdet(KA),f_LD(A)= (K_A), (24) where KAK_A denotes the principal kernel matrix corresponding to the subset A. The corresponding Total Information objective is TILD(C1,⋯,Ck)=∑c=1Klogdet(KCc).TI_LD(C_1,·s,C_k)= _c=1^K (K_C_c). (25) Unlike Graph Cut, which decomposes into representation and diversity terms, LogDet is purely diversity-oriented. Consequently, we expect LogDet based Total Information to capture a notion of intra-class variability. To formalize this connection, let Σc=1|Cc|∑i∈Cc(zi−μc)(zi−μc)T _c= 1|C_c| _i∈ C_c(z_i- _c)(z_i- _c)^T (26) denote the covariance matrix of class CcC_c. A classical measure of variability is the generalized variance GV(Cc)=logdet(Σc),GV(C_c)= ( _c), (27) which measures the covariance volume occupied by the class. The following theorem establishes a connection between LogDet Total Information and generalized variance. Theorem 2. Assume that the samples within each class are drawn from a distribution with covariance matrix Σc _c, and let KCcK_C_c denote the corresponding kernel matrix constructed from these samples. Under standard regularity conditions and in the large-sample regime, logdet(KCc)=ac+bclogdet(Σc)+o(1), (K_C_c)=a_c+b_c ( _c)+o(1), (28) where aca_c and bc>0b_c>0 are constants depending on the kernel and embedding dimension. Consequently, TILD=∑c=1Klogdet(KCc)TI_LD= _c=1^K (K_C_c) (29) is a monotone transformation of ∑c=1Klogdet(Σc), _c=1^K ( _c), (30) and therefore recovers the generalized variance of the class distributions. Theorem 2 reveals that LogDet Total Information captures a richer notion of variability than Graph Cut. While Graph Cut is related to within-class variance through pairwise distances, LogDet additionally incorporates covariance structure and effective dimensionality. In particular, two classes may have identical trace variance but very different covariance volumes. Graph Cut treats such classes similarly, whereas LogDet distinguishes them through the determinant of their covariance matrices. Consequently, LogDet TI may be viewed as a covariance-aware generalization of classical within-class variance. In Section 6, we validate this interpretation through synthetic experiments that independently vary covariance volume while controlling other factors. We observe an almost perfect monotonic relationship between LogDet Total Information and generalized variance, supporting the theoretical characterization above. 4.3 Facility Location Total Information and Rare Class Margins We next consider Facility Location, one of the most widely used representation-oriented submodular functions. Recall that the Facility Location function is defined as fFL(A)=∑i∈Vmaxj∈Asij,f_FL(A)= _i∈ V _j∈ As_ij, (31) where V denotes the ground set and S=[sij]S=[s_ij] is a similarity matrix. The corresponding Total Information objective is TIFL=∑c=1KfFL(Cc)=∑c=1K∑i∈Vmaxj∈Ccsij.TI_FL= _c=1^Kf_FL(C_c)= _c=1^K _i∈ V _j∈ C_cs_ij. (32) Unlike Graph Cut and LogDet, Facility Location contains no explicit diversity component. Instead, it measures how well each class represents the points in the ground set through nearest-neighbor similarity. To understand the structure of Equation (32), we separate the contribution of points belonging to the class from those lying outside the class: TIFL=∑c=1K[∑i∈Ccmaxj∈Ccsij+∑i∈V∖Ccmaxj∈Ccsij]. TI_FL= _c=1^K [ _i∈ C_c _j∈ C_cs_ij+ _i∈ V C_c _j∈ C_cs_ij ]. (33) Assuming normalized similarities satisfying sii=1s_i=1, the first term is constant since each point is maximally represented by itself. Consequently, TIFL=N+∑c=1K∑i∈V∖Ccmaxj∈Ccsij,TI_FL=N+ _c=1^K _i∈ V C_c _j∈ C_cs_ij, (34) where N denotes the total number of samples. Equation (34) reveals that Facility Location Total Information is entirely governed by cross-class interactions. Unlike Graph Cut and LogDet, which recover classical notions of intra-class variability, Facility Location TI measures how well each class represents the remainder of the dataset. To make this dependence explicit, define Rc=1N−nc∑i∈V∖Ccmaxj∈Ccsij,R_c= 1N-n_c _i∈ V C_c _j∈ C_cs_ij, (35) where nc=|Cc|n_c=|C_c| denotes the size of class CcC_c. The quantity RcR_c measures the average representational affinity between class CcC_c and all samples outside the class. Substituting Equation (35) into Equation (34) gives TIFL=N+∑c=1K(N−nc)Rc.TI_FL=N+ _c=1^K(N-n_c)R_c. (36) Consequently, the contribution of class CcC_c is weighted by N−ncN-n_c. Classes with fewer samples therefore receive larger relative weight than classes with many samples. As a result, Facility Location Total Information naturally emphasizes rare and underrepresented classes. Theorem 3 (Facility Location TI Induces Larger Margins for Rare Classes). Assume normalized similarities satisfying sii=1s_i=1 and suppose each class CcC_c forms a compact cluster and let δc _c denote the distance between the centroid of class CcC_c and its nearest competing class. Further assume an RBF similarity sij=exp(−‖zi−zj‖22τ2).s_ij= (- \|z_i-z_j\|^22τ^2 ). (37) Then the cross-class contribution of class CcC_c satisfies ∑i∈V∖Ccmaxj∈Ccsij=Θ((N−nc)exp(−δc22τ2)). _i∈ V C_c _j∈ C_cs_ij= \! ((N-n_c) (- _c^22τ^2 ) ). (38) Consequently, the influence of class CcC_c on Facility Location Total Information scales as Influence(Cc)=Θ((N−nc)exp(−δc22τ2)).Influence(C_c)= \! ((N-n_c) (- _c^22τ^2 ) ). (39) Furthermore, if two classes CaC_a and CbC_b contribute equally to the objective, then δa2−δb2=2τ2log(N−naN−nb). _a^2- _b^2=2τ^2 ( N-n_aN-n_b ). (40) In particular, if na<nbn_a<n_b, then δa>δb _a> _b. Thus, for the same effective contribution to the FL-TI objective, smaller classes require larger separation margins. Interpretation. Theorem 3 provides a theoretical explanation for the strong empirical performance of Facility Location based SCORE objectives in long-tailed settings [23]. Unlike variance-based objectives, whose contribution typically scales with the number of samples within a class, Facility Location Total Information penalizes class overlap with a weight proportional to the number of samples outside the class. As a result, tail classes incur a larger penalty when they overlap with neighboring classes. To reduce the objective, the representation must therefore increase the separation of rare classes more aggressively than that of head classes. The induced margin grows approximately as δc2=2τ2log(N−nc)+const. _c^2=2τ^2 (N-n_c)+const. (41) showing that Facility Location naturally allocates larger margins to underrepresented classes. This result provides a principled explanation for the long-tail robustness observed in SCORE-FL [23] and suggests that representation-oriented submodular objectives implicitly perform class-dependent margin adaptation without requiring explicit reweighting or resampling. 5 Submodular Mutual Information Objectives In the previous section, we studied Total Information objectives and showed that different submodular functions induce different notions of intra-class variability and inter-class bias. We now turn our attention to Submodular Mutual Information (SMI) objectives. Recall that for two sets A and B, the submodular mutual information induced by a submodular function f is If(A;B)=f(A)+f(B)−f(A∪B).I_f(A;B)=f(A)+f(B)-f(A∪ B). (42) Unlike Total Information, which aggregates information within classes, SMI explicitly measures interactions between sets. Consequently, SMI objectives are naturally suited for modeling inter-class structure. A generic SCORE objective based on pairwise mutual information takes the form ∑i<jIf(Ci;Cj), _i<jI_f(C_i;C_j), (43) where CiC_i and CjC_j denote different classes. The central question studied in this section is: What notions of inter-class bias and separation are induced by different submodular mutual information measures? We answer this question for Graph Cut, LogDet, and Facility Location based mutual information and establish connections to classical notions of mean separation, covariance-aware discrimination, and representational overlap. 5.1 Graph Cut Mutual Information and Mean Separation We now turn to Graph Cut Mutual Information (GCMI), which provides a complementary perspective to the Graph Cut Total Information objective studied in Section 4.1. While Graph Cut Total Information was shown to recover within-class variance, Graph Cut Mutual Information captures interactions between classes and therefore provides a natural measure of inter-class structure. For two classes CaC_a and CbC_b, Graph Cut Mutual Information takes the form IGC(Ca;Cb)=∑i∈Ca∑j∈Cbsij,I_GC(C_a;C_b)= _i∈ C_a _j∈ C_bs_ij, (44) which measures the aggregate similarity between samples belonging to different classes. Intuitively, if two classes are well separated, cross-class similarities are small and the corresponding Graph Cut Mutual Information is low. Conversely, if two classes overlap substantially, many cross-class similarities become large, leading to a larger GCMI value. We now establish a precise connection between GCMI and classical notions of class separation. Consider two classes CaC_a and CbC_b with centroids μa _a and μb _b. Define the mean separation D(Ca,Cb)=‖μa−μb‖2.D(C_a,C_b)=\| _a- _b\|^2. (45) The following theorem shows that mean separation admits a decomposition into within-class variance terms and a Graph Cut Mutual Information term. Theorem 4 (GC Decomposition of Aggregate Mean Separation). Let sij=M−‖zi−zj‖2,s_ij=M-\|z_i-z_j\|^2, (46) where M is a sufficiently large constant, and let nc=|Cc|n_c=|C_c|. Define the aggregate centroid-separation objective mean=∑a<bnanb‖μa−μb‖2.D_mean= _a<bn_an_b\| _a- _b\|^2. (47) Then minimizing the negative mean-separation objective is equivalent, up to positive scaling and additive constants, to minimizing −mean≡αTITI~GCλ=0+αMI∑a<bIGC(Ca;Cb),-D_mean≡ _TI TI_GC^λ=0+ _MI _a<bI_GC(C_a;C_b), (48) where TI~GCλ=0=∑c=1KN−nc2nc(−∑i,j∈Ccsij) TI_GC^λ=0= _c=1^K N-n_c2n_c (- _i,j∈ C_cs_ij ) (49) is a class-size weighted Graph Cut Total Information term, and αTI,αMI>0 _TI, _MI>0 are constants depending only on normalization. In the balanced-class setting, TI~GCλ=0 TI_GC^λ=0 reduces to a positive scalar multiple of the standard TIGCλ=0TI_GC^λ=0. Thus, in the balanced case, the GC-based SCORE objective consisting of standard Graph Cut Total Information with λ=0λ=0 and pairwise GCMI recovers the classical objective of maximizing aggregate inter-class centroid separation. Interpretation. Theorem 4 shows that the natural multi-class separation objective ∑a<bnanb‖μa−μb‖2 _a<bn_an_b\| _a- _b\|^2 is exactly decomposed into two SCORE components: a TI term over classes and a pairwise SMI term over class pairs. Thus, the combined GC-based SCORE objective recovers the classical discriminative principle of minimizing within-class scatter while maximizing between-class separation. 5.2 LogDet Mutual Information and Mahalanobis Separation While Graph Cut Mutual Information captures centroid separation, it is insensitive to the covariance structure of the underlying classes. In many representation learning settings, classes may exhibit highly anisotropic or correlated distributions, making covariance-aware notions of separation more appropriate. To address this limitation, we consider LogDet Mutual Information (LogDetMI). Recall that ILD(Ca;Cb)=fLD(Ca)+fLD(Cb)−fLD(Ca∪Cb),I_LD(C_a;C_b)=f_LD(C_a)+f_LD(C_b)-f_LD(C_a∪ C_b), (50) where fLD(A)=logdet(KA),f_LD(A)= (K_A), (51) and KAK_A denotes the kernel matrix associated with subset A. Unlike Graph Cut Mutual Information, which depends primarily on cross-class similarities, LogDetMI incorporates the covariance structure of the participating classes through the determinants of the corresponding kernel matrices. The following theorem establishes a connection between LogDetMI and covariance-aware notions of class separation. Theorem 5 (LogDetMI and Mahalanobis Separation). Let classes CaC_a and CbC_b have means μa,μb _a, _b, covariance matrices Σa,Σb _a, _b, and class proportions p=nana+nb,q=nbna+nb.p= n_an_a+n_b, q= n_bn_a+n_b. (52) Define the pooled covariance Σw=pΣa+qΣb _w=p _a+q _b (53) and the Mahalanobis separation ℳab=(μa−μb)TΣw−1(μa−μb).M_ab=( _a- _b)^T _w^-1( _a- _b). (54) Under the covariance LogDet approximation, LogDet Mutual Information satisfies ILD(Ca;Cb)=const−log(1+pqℳab).I_LD(C_a;C_b)=const- (1+pqM_ab ). (55) Consequently, LogDetMI is a monotone decreasing function of Mahalanobis separation. Thus, minimizing LogDetMI is equivalent, up to monotone transformations, to maximizing covariance-normalized class separation. Interpretation. Theorem 5 reveals a fundamental distinction between Graph Cut and LogDet based mutual information. While Graph Cut Mutual Information is primarily governed by centroid separation, LogDetMI depends on the Mahalanobis separation between classes and therefore explicitly accounts for covariance structure and anisotropy. As a result, two pairs of classes with identical Euclidean centroid separation may receive substantially different LogDetMI values if their covariance structures differ. In particular, LogDetMI naturally favors separation along directions of low within-class variance, closely mirroring classical Fisher and Mahalanobis discriminative criteria. Consequently, LogDetMI may be viewed as a covariance-aware generalization of centroid separation, providing a richer notion of inter-class discrimination than Graph Cut Mutual Information. In Section 6, we validate this interpretation by independently varying centroid separation and covariance structure. The resulting experiments demonstrate a strong monotonic relationship between LogDetMI and Mahalanobis separation, supporting the theoretical characterization above. 5.3 Facility Location Mutual Information and Nearest Mode Overlap While Graph Cut and LogDet based mutual information capture different notions of class separation, Facility Location Mutual Information (FLQMI) captures a fundamentally different property: representational overlap. Recall that the Facility Location function is defined as fFL(A)=∑i∈Vmaxj∈Asij.f_FL(A)= _i∈ V _j∈ As_ij. (56) The corresponding Facility Location Mutual Information between two classes CaC_a and CbC_b is: IFL(Ca;Cb)=fFL(Ca)+fFL(Cb)−fFL(Ca∪Cb).I_FL(C_a;C_b)=f_FL(C_a)+f_FL(C_b)-f_FL(C_a∪ C_b). (57) The following theorem shows the connection between FLQMI and nearest-mode overlap. Theorem 6 (FLQMI and Nearest-Mode Overlap). Assume classes CaC_a and CbC_b consist of compact modes with centers νa,rr=1ma\ _a,r\_r=1^m_a and νb,ss=1mb\ _b,s\_s=1^m_b, respectively, and let drs=‖νa,r−νb,s‖d_rs=\| _a,r- _b,s\| (58) denote the distance between mode centers. Further assume an RBF similarity sij=exp(−‖zi−zj‖22τ2).s_ij= (- \|z_i-z_j\|^22τ^2 ). (59) Then Facility Location Mutual Information admits the approximation IFL(Ca;Cb)≈∑r,swrsexp(−drs22τ2),I_FL(C_a;C_b)≈ _r,sw_rs (- d_rs^22τ^2 ), (60) where wrs=na,rs=s∗(r)+nb,sr=r∗(s),w_rs=n_a,r1\s=s^*(r)\+n_b,s1\r=r^*(s)\, (61) and s∗(r)s^*(r) and r∗(s)r^*(s) denote the nearest neighboring modes of mode r and mode s, respectively. Consequently, FLQMI is primarily governed by nearest-mode overlap rather than aggregate overlap across all mode pairs. Interpretation. Theorem 6 reveals a fundamental distinction between Graph Cut and Facility Location based mutual information. While Graph Cut Mutual Information aggregates contributions from all pairs of modes, Facility Location Mutual Information is dominated by nearest-mode interactions. Consequently, GCMI measures aggregate overlap mass between classes, whereas FLQMI measures localized representational overlap. In multimodal settings, FLQMI is therefore more sensitive to rare or poorly separated modes and behaves as a soft nearest-mode separation criterion. This explains why two pairs of classes may exhibit similar aggregate overlap yet receive substantially different FLQMI values depending on how their modes are arranged in the representation space. 6 Experiments In this section, we empirically validate the theoretical characterizations developed in Sections 4 and 5. Our goal is not to benchmark representation-learning performance, but rather to verify that the proposed information measures exhibit the geometric behavior predicted by the theory. To this end, we design a collection of controlled synthetic experiments in which individual geometric properties of the representation space can be manipulated independently. Specifically, we construct datasets that vary: • within-class variance, • covariance structure and anisotropy, • class imbalance, • centroid separation, and • multimodal overlap. For each experiment, we compute the corresponding submodular information measure and compare it against the classical quantity predicted by the theory. A strong monotonic relationship between the two provides empirical support for the theoretical characterization. Unless otherwise specified, all synthetic datasets are generated from Gaussian mixtures in a d-dimensional embedding space. Similarities are computed using either the shifted Euclidean kernel sij=M−|zi−zj|2,s_ij=M-|z_i-z_j|^2, (62) or the Gaussian RBF kernel sij=exp(−|zi−zj|22τ2),s_ij= (- |z_i-z_j|^22τ^2 ), (63) depending on the assumptions of the corresponding theorem. We evaluate the following theoretical predictions: 1. Graph Cut Total Information recovers within-class variance. 2. LogDet Total Information recovers generalized variance. 3. Graph Cut Total Information and Graph Cut Mutual Information jointly recover aggregate mean separation. 4. Facility Location Total Information induces larger margins for rare classes. 5. LogDet Mutual Information recovers Mahalanobis separation. 6. Facility Location Mutual Information recovers nearest-mode overlap. We begin by validating the connection between Graph Cut Total Information and classical within-class variance. 6.1 Experiment 1: Graph Cut Total Information and Within-Class Variance Theorem 1 states that Graph Cut Total Information with λ=0λ=0 recovers the classical within-class variance when the similarity function is chosen as a shifted Euclidean kernel, sij=M−|zi−zj|2s_ij=M-|z_i-z_j|^2. To validate this result, we generate synthetic Gaussian classes while varying the within-class standard deviation σ. For each dataset, we compute: 1. the classical within-class variance, 2. the equivalent pairwise-distance formulation, 3. the quantity recovered by Graph Cut Total Information using the shifted Euclidean kernel, and 4. a Graph Cut objective computed using an RBF kernel. Table 2 summarizes the results. Table 2: Graph Cut Total Information recovers within-class variance exactly under the shifted Euclidean kernel. σ StdVar Pairwise Identity GC Shift GC RBF 0.05 9.85 9.85 9.85 9.82 0.10 40.94 40.94 40.94 40.31 0.20 154.51 154.51 154.51 145.86 0.40 642.86 642.86 642.86 511.20 0.80 2531.28 2531.28 2531.28 1187.79 1.20 5617.50 5617.50 5617.50 1474.99 1.60 9858.35 9858.35 9858.35 1550.94 2.00 15831.65 15831.65 15831.65 1573.80 Several observations follow. First, the classical variance, pairwise-distance identity, and Graph Cut Total Information recovered using the shifted Euclidean kernel are numerically identical across all settings. This provides direct empirical verification of Theorem 1. Second, the RBF version exhibits a strong monotonic relationship with variance but does not recover the variance exactly. This behavior is expected since the RBF kernel introduces a nonlinear transformation of pairwise distances. Nevertheless, larger within-class variance consistently produces larger Graph Cut values, indicating that the variance interpretation extends qualitatively beyond the shifted Euclidean setting. Overall, these results confirm that Graph Cut Total Information recovers classical within-class variance and therefore behaves as a variance-minimization objective in representation learning. 6.2 Experiment 2: LogDet Total Information and Generalized Variance Theorem 2 suggests that LogDet Total Information recovers the generalized variance of the class distributions. Unlike Graph Cut Total Information, which measures classical within-class variance, LogDet Total Information incorporates the full covariance structure of the embeddings through the determinant of the covariance matrix. To validate this result, we generate Gaussian classes while varying the covariance scale parameter σ. For each dataset, we compute: 1. the aggregate covariance log-determinant, ∑clogdet(Σc), _c ( _c), (64) 2. the corresponding LogDet Total Information objective, and 3. the classical centroid variance used in Experiment 6.1. Table 3 summarizes the result thaat LogDet TI closely tracks the generalized variance. The corresponding correlation matrix (between LogDet TI, the generalized variance, and the classical variance) is shown in Table 4. Table 3: LogDet Total Information closely tracks generalized variance. σ CovLogDet LogDet-TI CentroidVar 0.05 -303.21 -2507.71 9.89 0.10 -233.78 -2366.14 39.65 0.20 -164.16 -1954.84 159.08 0.40 -95.29 -1194.24 631.07 0.80 -26.27 -373.00 2521.22 1.20 14.57 -95.03 5697.51 1.60 42.65 -23.05 10016.39 2.00 65.80 -4.94 15847.87 Table 4: Correlation between generalized variance, LogDet Total Information, and classical variance. CovLogDet LogDet-TI CentroidVar CovLogDet 1.000 0.984 0.803 LogDet-TI 0.984 1.000 0.773 CentroidVar 0.803 0.773 1.000 Several observations follow. First, LogDet Total Information exhibits an almost perfect monotonic relationship with the covariance log-determinant, achieving a correlation of 0.9840.984. This provides strong empirical support for Theorem 2. Second, while LogDet-TI remains correlated with classical variance, the relationship is substantially weaker. This is expected since the determinant captures covariance volume rather than merely the sum of marginal variances. Consequently, LogDet-TI incorporates information about anisotropy and covariance structure that is ignored by standard variance measures. Overall, these results confirm that LogDet Total Information behaves as a generalized variance objective and captures richer covariance information than Graph Cut Total Information. 6.3 Experiment 3: Facility Location Total Information Emphasizes Rare and Confusable Classes Theorem 3 predicts that Facility Location Total Information assigns larger weight to classes that are both rare and poorly separated from competing classes. To validate this prediction, we construct a long-tailed dataset consisting of three classes: a head class (n=1000n=1000), a medium class (n=300n=300), and a tail class (n=50n=50). The tail class is positioned near the head class, making it highly confusable, while the medium class is placed farther away. Table 5 reports the per-class contributions of GC-TI, LogDet-TI, and FL-TI. Table 5: Per-class contribution shares on a long-tailed dataset. Class FL-TI GC-TI LogDet-TI Head (n=1000n=1000) 5.5% 91.5% 32.7% Medium (n=300n=300) 1.0% 8.2% 33.4% Tail (n=50n=50) 93.5% 0.2% 33.9% Several observations follow. • First, GC-TI is dominated by the head class, reflecting its connection to within-class variance and class cardinality. • Second, LogDet-TI distributes importance nearly uniformly across classes, since all classes possess similar covariance structure. • In contrast, FL-TI assigns more than 93% of its total contribution to the rare and confusable tail class. This behavior is precisely predicted by Theorem 3, which shows that the influence of a class scales as (N−nc)exp(−δc2/(2τ2))(N-n_c) (- _c^2/(2τ^2)). These results provide a theoretical explanation for the strong performance of Facility Location based SCORE objectives in long-tailed recognition settings. Unlike variance-based objectives, FL-TI naturally prioritizes underrepresented classes without requiring explicit class reweighting. 6.4 Experiment 4: Aggregate Mean Separation and the GC-SCORE Objective Theorem 4 establishes a direct connection between classical discriminative representation learning and Submodular Information Measures. In particular, it shows that the aggregate centroid-separation objective mean=∑a<bnanb|μa−μb|2D_mean= _a<bn_an_b| _a- _b|^2 (65) admits an exact decomposition into a weighted Graph Cut Total Information term and a pairwise Graph Cut Mutual Information term. To validate this result, we generate synthetic datasets with increasing class separation and compute: 1. the aggregate mean-separation objective, 2. the weighted Graph Cut Total Information term, 3. the pairwise Graph Cut Mutual Information term, and 4. their sum predicted by Theorem 4. Table 6 summarizes the results. Table 6: Verification of the exact decomposition of aggregate mean separation into GC-TI and GCMI components. Mean Sep −mean-D_mean GC-TI GCMI GC-TI + GCMI 1 -79,303 -753,619 674,315 -79,303 2 -295,956 -1,299,882 1,003,926 -295,956 4 -1,225,091 -2,676,234 1,451,144 -1,225,091 6 -2,773,310 -5,041,493 2,268,183 -2,773,310 8 -4,906,642 -7,798,381 2,891,739 -4,906,642 10 -7,730,433 -11,006,376 3,275,943 -7,730,433 To quantify the quality of the decomposition, we compare the centered versions of the two objectives. The absolute reconstruction error is shown in Table 7. Table 7: Reconstruction error of the GC-TI + GCMI decomposition. Mean Sep Centered Error 1 0.00.0 2 8.7×10−118.7× 10^-11 4 2.3×10−102.3× 10^-10 6 1.4×10−91.4× 10^-9 8 1.9×10−91.9× 10^-9 10 3.7×10−93.7× 10^-9 The decomposition is exact up to numerical precision, with reconstruction errors on the order of 10−910^-9. Furthermore, the correlation between the theoretical objective −mean-D_mean and the recovered GC-SCORE objective is equal to 1.01.0. These results provide direct empirical verification of Theorem 4. More importantly, they reveal that the GC-based SCORE objective is not merely correlated with classical discriminative objectives but exactly recovers the aggregate centroid-separation criterion. Consequently, Graph Cut Total Information and Graph Cut Mutual Information together admit a precise geometric interpretation as a decomposition of classical mean-separation based representation learning. 6.5 Experiment 5: LogDet Mutual Information and Mahalanobis Separation Theorem 5 predicts that LogDet Mutual Information is a monotone decreasing function of Mahalanobis separation. Unlike Graph Cut Mutual Information, which depends primarily on centroid separation, LogDetMI additionally incorporates covariance structure and anisotropy through the pooled covariance matrix. To validate this characterization, we perform two complementary experiments. Experiment 5A: Varying Centroid Separation. We first generate two Gaussian classes and vary the distance between their centroids while keeping the covariance structure fixed. Here δ=‖μa−μb‖δ=\| _a- _b\|. For each setting, we compute the covariance-based LogDetMI approximation and the corresponding Mahalanobis separation. Table 8 summarizes the results. Table 8: LogDetMI as a function of centroid separation. δ LogDetMI Mahalanobis Separation 0.5 -0.270 0.097 1.0 -0.320 0.307 2.0 -0.491 1.109 3.0 -0.719 2.420 4.0 -0.969 4.241 6.0 -1.457 9.411 8.0 -1.887 16.619 The resulting correlations are corr(LogDetMI,ℳ)=−0.968corr(LogDetMI,M)=-0.968 and corr(δ,LogDetMI)=−0.979corr(δ,LogDetMI)=-0.979. These results confirm the strong monotonic relationship predicted by Theorem 5. Experiment 5B: Varying Covariance Orientation. Next, we fix the centroid separation while varying the relative orientation of the covariance ellipses. This experiment isolates the covariance-dependent component of Mahalanobis separation. Table 9 summarizes the results. Table 9: Effect of covariance orientation on LogDetMI. Angle LogDetMI Mahalanobis Separation 0∘0 -0.673 2.369 15∘15 -1.002 2.818 30∘30 -1.596 3.582 45∘45 -2.072 3.987 60∘60 -2.393 4.178 90∘90 -2.636 4.295 The correlation between LogDetMI and Mahalanobis separation in this setting is corr(LogDetMI,ℳ)=−0.906corr(LogDetMI,M)=-0.906. Notably, substantial changes in LogDetMI occur despite the centroid distance remaining fixed. This behavior cannot be explained by Euclidean separation alone and directly reflects the covariance-aware nature of LogDetMI. Taken together, Experiments 5A and 5B provide strong empirical support for Theorem 5. While Graph Cut Mutual Information captures centroid separation, LogDetMI captures Mahalanobis separation and therefore incorporates covariance structure, anisotropy, and orientation into the representation-learning objective. 6.6 Experiment 6: FLQMI and Multimodal Representational Overlap Theorem 6 predicts that Facility Location Mutual Information is governed by nearest-mode overlap rather than aggregate cross-class similarity. To validate this characterization, we construct a synthetic multimodal dataset in which aggregate overlap is held constant while representational overlap is varied. Class A consists of four equally-sized modes. We consider two configurations of class B: 1. Concentrated Overlap: the overlap between the two classes is concentrated around a single mode of A. 2. Distributed Overlap: the same amount of overlap is distributed across all four modes of A. By construction, the total cross-class similarity is nearly identical between the two settings. However, the distributed configuration provides representatives for a much larger fraction of the modes of class A. Table 10 summarizes the results. Table 10: FLQMI distinguishes distributed and concentrated overlap despite nearly identical aggregate overlap. Setting GCMI FLQMI A→BA\!→\!B Coverage B→AB\!→\!A Coverage Concentrated 3384.78 129.15 79.39 49.76 Distributed 3384.52 439.35 389.58 49.77 Several observations follow. First, GCMI remains essentially unchanged across the two settings, indicating that aggregate overlap mass is nearly identical. Consequently, Graph Cut Mutual Information is unable to distinguish between concentrated and distributed overlap. In contrast, FLQMI increases from 129.15129.15 to 439.35439.35, a factor of approximately 3.4×3.4×. This increase mirrors the dramatic rise in representational coverage from class A to class B, while the reverse coverage remains nearly constant. These results provide strong empirical support for Theorem 6. While GCMI measures aggregate overlap across all mode pairs, FLQMI is sensitive to how that overlap is distributed among the modes. Consequently, FLQMI behaves as a nearest-mode or representational-overlap criterion, making it particularly well-suited for multimodal representation learning. 7 Conclusion Submodular Information Measures have recently emerged as powerful objectives for representation learning, subset selection, and information maximization. Despite their empirical success, the geometric and statistical properties induced by different information measures have remained poorly understood. In this work, we developed a unified theoretical framework connecting Submodular Information Measures to classical notions of variance, covariance, separation, and representational overlap. Our analysis revealed that different information measures induce fundamentally different representation-learning biases. For Total Information objectives, we showed that Graph Cut Total Information recovers classical within-class variance, LogDet Total Information recovers generalized variance through covariance volume, and Facility Location Total Information naturally emphasizes rare and confusable classes by inducing imbalance-aware separation margins. For Mutual Information objectives, we established connections between Graph Cut Mutual Information and aggregate centroid separation, LogDet Mutual Information and Mahalanobis separation, and Facility Location Mutual Information and nearest-mode representational overlap. Perhaps most notably, we showed that the combination of Graph Cut Total Information and Graph Cut Mutual Information admits an exact decomposition of the classical aggregate mean-separation objective. This result provides a direct bridge between Submodular Information Measures and classical discriminative representation learning, revealing that certain SCORE objectives recover well-studied statistical criteria exactly rather than approximately. We further validated these theoretical predictions through a suite of controlled synthetic experiments. Across all settings, the empirical behavior of the corresponding information measures closely matched the proposed theoretical characterizations, providing strong evidence that the geometric interpretations developed in this work accurately describe the behavior of SIM-based objectives. Beyond providing theoretical insight, our results offer practical guidance for selecting information measures in representation learning. Variance-oriented objectives such as Graph Cut are well suited for compactness and class separation, LogDet based objectives provide covariance-aware discrimination, and Facility Location based objectives naturally emphasize multimodal structure, rare classes, and representational coverage. We believe that these insights will facilitate the principled design of future submodular objectives and contribute to a deeper understanding of combinatorial approaches to representation learning. An important direction for future work is extending these analyses beyond supervised representation learning to settings such as self-supervised learning, retrieval-augmented generation, and multimodal foundation models, where Submodular Information Measures have recently demonstrated strong empirical success. More broadly, we hope that the theoretical framework developed in this paper serves as a foundation for understanding and designing the next generation of representation learning, self-supervised learning, and multi-modal learning objectives guided by combinatorial objective functions. References [1] A. Bardes, J. Ponce, and Y. LeCun (2021) Vicreg: variance-invariance-covariance regularization for self-supervised learning. arXiv preprint arXiv:2105.04906. Cited by: §1. [2] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton (2020) A simple framework for contrastive learning of visual representations. Intl. Conf. on Machine Learning (ICML). Cited by: §1, §1, §2.1. [3] J. Deng, J. Guo, N. Xue, and S. Zafeiriou (2019) Arcface: additive angular margin loss for deep face recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, p. 4690–4699. Cited by: §1, §1, §2.1. [4] R. A. Fisher (1936) The use of multiple measurements in taxonomic problems. Annals of Eugenics. Cited by: §1, §2.1. [5] N. Frosst, N. Papernot, and G. E. Hinton (2019) Analyzing and improving representations with the soft nearest neighbor loss. In International Conference on Machine Learning, Cited by: §1. [6] S. Fujishige (2005) Submodular functions and optimization. Elsevier. Cited by: §1, §2.2. [7] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick (2020) Momentum contrast for unsupervised visual representation learning. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Cited by: §1. [8] K. He, X. Zhang, S. Ren, and J. Sun (2016) Deep residual learning for Image Recognition. In IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), Cited by: §1. [9] R. Iyer, N. Khargonkar, J. Bilmes, and H. Asnani (2022) Generalized submodular information measures: theoretical properties, examples, optimization algorithms, and applications. IEEE Transactions on Information Theory 68 (2), p. 752–781. Cited by: §1, §1, §2.2, §2.3. [10] R. K. Iyer (2015) Submodular optimization and machine learning: theoretical results, unifying and scalable algorithms, and applications. Ph.D. Thesis. Cited by: §1, §2.2. [11] A. Karanam, K. Killamsetty, H. Kokel, and R. Iyer (2022) ORIENT: submodular mutual information measures for data subset selection under distribution shift. In Advances in Neural Information Processing Systems, Vol. 35. Cited by: §1, §1, §2.3, §3. [12] V. Kaushal, R. Iyer, K. Doctor, A. Sahoo, P. Dubal, S. Kothawade, R. Mahadev, K. Dargan, and G. Ramakrishnan (2019) Demystifying multi-faceted video summarization: tradeoff between diversity, representation, coverage and importance. In 2019 IEEE Winter Conference on Applications of Computer Vision (WACV), p. 452–461. Cited by: §1. [13] V. Kaushal, R. Iyer, S. Kothawade, R. Mahadev, K. Doctor, and G. Ramakrishnan (2019) Learning from less data: a unified data subset selection and active learning framework for computer vision. In 2019 IEEE Winter Conference on Applications of Computer Vision (WACV), Cited by: §1. [14] P. Khosla, P. Teterwak, C. Wang, A. Sarna, Y. Tian, P. Isola, A. Maschinot, C. Liu, and D. Krishnan (2020) Supervised contrastive learning. In Advances in Neural Information Processing Systems, Cited by: §1, §1, §2.1. [15] S. Kothawade, N. Beck, K. Killamsetty, and R. Iyer (2021) SIMILAR: submodular information measures based active learning in realistic scenarios. Advances in Neural Information Processing Systems 34. Cited by: §1, §2.3, §3. [16] S. Kothawade, S. Ghosh, S. Shekhar, Y. Xiang, and R. K. Iyer (2022) Talisman: targeted active learning for object detection with rare classes and slices using submodular mutual information. In Computer Vision - ECCV 2022 - 17th European Conference, Cited by: §1. [17] S. Kothawade, V. Kaushal, G. Ramakrishnan, J. A. Bilmes, and R. K. Iyer (2022) PRISM: A rich class of parameterized submodular information measures for guided data subset selection. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI, p. 10238–10246. Cited by: §1, §1, §2.3, §3. [18] A. Krizhevsky, I. Sutskever, and G. E. Hinton (2012) ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, Cited by: §1. [19] A. Kulesza (2012) Determinantal point processes for machine learning. Foundations and Trends® in Machine Learning 5 (2–3), p. 123–286. External Links: ISSN 1935-8245 Cited by: §2.2. [20] H. Lin and J. Bilmes (2011) A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Cited by: §1, §2.2. [21] A. Majee, A. Gangrade, and R. Iyer (2026) Looking beyond the known: towards a data discovery guided open-world object detection. Advances in Neural Information Processing Systems 38, p. 25050–25078. Cited by: §1. [22] A. Majee and R. Iyer (2026) SHaSaM: submodular hard sample mining for fair facial attribute recognition. In Proc. WACV. Cited by: §1, §1. [23] A. Majee, S. Kothawade, K. Killamsetty, and R. Iyer (2024) Score: submodular combinatorial representation learning. In ICML. Cited by: §1, §1, §1, §2.4, §3.2, §3.2, §3, §4.3, §4.3. [24] A. Majee, R. Sharp, and R. Iyer (2024) SMILe: leveraging submodular mutual information for robust few-shot object detection. In European Conference on Computer Vision, p. 350–366. Cited by: §1, §1, §1, §3.2. [25] J. Mercer (1909) Functions of positive and negative type, and their connection with the theory of integral equations. Philosophical Transactions of the Royal Society of London. Series A 209, p. 415–446. Cited by: §A.2. [26] T. Pham, A. Majee, and R. Iyer (2026) SMA: submodular modality aligner for data efficient multimodal learning. arXiv preprint arXiv:2605.12872. Cited by: §1, §1. [27] D. E. Rumelhart, G. E. Hinton, and R. J. Williams (1986) Learning representations by back-propagating errors. nature 323 (6088), p. 533–536. Cited by: §1. [28] B. Schölkopf, A. Smola, and K. Müller (1998) Nonlinear component analysis as a kernel eigenvalue problem. In Neural Computation, Vol. 10, p. 1299–1319. Cited by: §A.2. [29] F. Schroff, D. Kalenichenko, and J. Philbin (2015) FaceNet: a unified embedding for face recognition and clustering. In IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), Cited by: §1, §1, §2.1. [30] K. Simonyan and A. Zisserman (2015) Very deep convolutional networks for large-scale image recognition. In Intl. Conf. on Learning Representations, Cited by: §1. [31] K. Sohn (2016) Improved deep metric learning with multi-class n-pair loss objective. In Advances in Neural Inf. Processing Systems, Cited by: §1. [32] H. O. Song, Y. Xiang, S. Jegelka, and S. Savarese (2016) Deep metric learning via lifted structured feature embedding. In Computer Vision and Pattern Recognition (CVPR), Cited by: §1. [33] I. Steinwart and C. Scovel (2012) Mercer’s theorem on general domains: on the interaction between measures, kernels, and rkhss. Constructive Approximation 35, p. 363–417. Cited by: §A.2. [34] H. Wang, Y. Wang, Z. Zhou, X. Ji, D. Gong, J. Zhou, Z. Li, and W. Liu (2018-06) CosFace: large margin cosine loss for deep face recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Cited by: §1, §1, §2.1. [35] K. Wei, R. Iyer, and J. Bilmes (2015) Submodularity in data subset selection and active learning. In ICML, Cited by: §1. [36] Y. Wen, K. Zhang, Z. Li, and Y. Qiao (2016) A discriminative feature learning approach for deep face recognition. In Computer Vision – ECCV 2016, B. Leibe, J. Matas, N. Sebe, and M. Welling (Eds.), p. 499–515. Cited by: §1, §2.1. Appendix A Proofs of Theoretical Results In this appendix, we provide proofs of the theoretical results presented in the main paper. A.1 Proof of Theorem 1 Proof. For λ=0λ=0, the Graph-Cut Total Information is TIGC(C1,…,CK)=−∑c=1K∑k,l∈Ccskl.TI_GC(C_1,…,C_K)=- _c=1^K _k,l∈ C_cs_kl. (66) Substituting skl=M−‖zk−zl‖2s_kl=M-\|z_k-z_l\|^2 gives TIGC(C1,…,CK) _GC(C_1,…,C_K) =−∑c=1K∑k,l∈Cc(M−‖zk−zl‖2) =- _c=1^K _k,l∈ C_c (M-\|z_k-z_l\|^2 ) (67) =−M∑c=1K|Cc|2+∑c=1K∑k,l∈Cc‖zk−zl‖2. =-M _c=1^K|C_c|^2+ _c=1^K _k,l∈ C_c\|z_k-z_l\|^2. (68) The first term is independent of the representations and is therefore an additive constant. Hence, TIGC(C1,…,CK)=∑c=1K∑k,l∈Cc‖zk−zl‖2+const.TI_GC(C_1,…,C_K)= _c=1^K _k,l∈ C_c\|z_k-z_l\|^2+const. (69) Using the standard identity ∑k,l∈Cc‖zk−zl‖2=2|Cc|∑k∈Cc‖zk−μc‖2, _k,l∈ C_c\|z_k-z_l\|^2=2|C_c| _k∈ C_c\|z_k- _c\|^2, (70) we obtain TIGC(C1,…,CK)=2∑c=1K|Cc|∑k∈Cc‖zk−μc‖2+const.TI_GC(C_1,…,C_K)=2 _c=1^K|C_c| _k∈ C_c\|z_k- _c\|^2+const. (71) Thus, Graph-Cut Total Information with λ=0λ=0 recovers the classical within-class variance up to a class-dependent scaling factor and an additive constant. ∎ A.2 Proof of Theorem 2 Proof. We first prove the result for the covariance, or linear, kernel, and then describe the extension to general positive-definite kernels. Let Zc∈ℝnc×dZ_c ^n_c× d denote the centered data matrix for class CcC_c, whose rows are zi−μcz_i- _c. The empirical covariance is Σ^c=1ncZcTZc. _c= 1n_cZ_c^TZ_c. (72) For the linear kernel, KCc=ZcZcT.K_C_c=Z_cZ_c^T. (73) Since ZcZcTZ_cZ_c^T and ZcTZcZ_c^TZ_c have the same nonzero eigenvalues, the nonzero determinant, or pseudo-determinant, satisfies logpdet(KCc) (K_C_c) =logpdet(ZcZcT) = (Z_cZ_c^T) (74) =logdet(ZcTZc) = (Z_c^TZ_c) (75) =logdet(ncΣ^c) = (n_c _c) (76) =dlognc+logdet(Σ^c). =d n_c+ ( _c). (77) Under standard regularity assumptions, the empirical covariance Σ^c _c converges to the population covariance Σc _c as nc→∞n_c→∞. Therefore, logpdet(KCc)=dlognc+logdet(Σc)+o(1). (K_C_c)=d n_c+ ( _c)+o(1). (78) Thus, for the linear kernel, the claim holds with ac=dlognc,bc=1.a_c=d n_c, b_c=1. (79) For more general positive-definite kernels, the kernel matrix KCcK_C_c is an empirical discretization of the kernel covariance or integral operator associated with the class-conditional distribution. Under the usual assumptions for Mercer kernels, the empirical spectrum of KCcK_C_c converges to the spectrum of the corresponding population operator. This is the standard operator-theoretic view underlying kernel PCA and Mercer decompositions [28, 25, 33]. For smooth radial kernels, local changes in the covariance volume of the distribution induce monotone changes in the volume spanned by the corresponding feature embeddings. Hence, in the large-sample regime, the LogDet objective admits the asymptotic form logdet(KCc)=ac+bclogdet(Σc)+o(1), (K_C_c)=a_c+b_c ( _c)+o(1), (80) for constants aca_c and bc>0b_c>0 depending on the kernel, embedding dimension, and sample size. Summing over classes gives TILD TI_LD =∑c=1Klogdet(KCc) = _c=1^K (K_C_c) (81) =∑c=1K(ac+bclogdet(Σc))+o(1). = _c=1^K (a_c+b_c ( _c) )+o(1). (82) Since bc>0b_c>0, LogDet Total Information is a monotone transformation of the aggregate generalized variance ∑c=1Klogdet(Σc). _c=1^K ( _c). (83) This proves the claim. ∎ A.3 Proof of Theorem 3 Proof. Recall that Facility Location Total Information is TIFL=∑c=1K∑i∈Vmaxj∈Ccsij.TI_FL= _c=1^K _i∈ V _j∈ C_cs_ij. (84) Since similarities are normalized so that sii=1s_i=1, for each i∈Cci∈ C_c we have maxj∈Ccsij=1. _j∈ C_cs_ij=1. (85) Therefore, TIFL TI_FL =∑c=1K[∑i∈Ccmaxj∈Ccsij+∑i∈V∖Ccmaxj∈Ccsij] = _c=1^K [ _i∈ C_c _j∈ C_cs_ij+ _i∈ V C_c _j∈ C_cs_ij ] (86) =N+∑c=1K∑i∈V∖Ccmaxj∈Ccsij. =N+ _c=1^K _i∈ V C_c _j∈ C_cs_ij. (87) Thus, the non-constant contribution of class CcC_c is Influence(Cc)=∑i∈V∖Ccmaxj∈Ccsij.Influence(C_c)= _i∈ V C_c _j∈ C_cs_ij. (88) Under the RBF kernel, maxj∈Ccsij=exp(−minj∈Cc‖zi−zj‖22τ2). _j∈ C_cs_ij= (- _j∈ C_c\|z_i-z_j\|^22τ^2 ). (89) Since class CcC_c is assumed to be compact, the nearest point in CcC_c to an external point from its nearest competing class lies at distance comparable to δc _c. Points from classes farther away contribute exponentially less. Therefore, ∑i∈V∖Ccmaxj∈Ccsij=Θ((N−nc)exp(−δc22τ2)). _i∈ V C_c _j∈ C_cs_ij= ((N-n_c) (- _c^22τ^2 ) ). (90) This proves the stated scaling for the influence of class CcC_c. Now suppose two classes CaC_a and CbC_b contribute equally to the FL-TI objective. Then (N−na)exp(−δa22τ2)=(N−nb)exp(−δb22τ2).(N-n_a) (- _a^22τ^2 )=(N-n_b) (- _b^22τ^2 ). (91) Taking logarithms gives log(N−na)−δa22τ2=log(N−nb)−δb22τ2. (N-n_a)- _a^22τ^2= (N-n_b)- _b^22τ^2. (92) Rearranging, δa2−δb2=2τ2log(N−naN−nb). _a^2- _b^2=2τ^2 ( N-n_aN-n_b ). (93) If na<nbn_a<n_b, then N−na>N−nbN-n_a>N-n_b, and hence log(N−naN−nb)>0. ( N-n_aN-n_b )>0. (94) Therefore, δa2>δb2, _a^2> _b^2, (95) which implies δa>δb _a> _b. Thus, for the same effective contribution to the FL-TI objective, smaller classes require larger separation margins. ∎ A.4 Proof of Theorem 4 Proof. For two classes CaC_a and CbC_b, let W(Ca)=∑i,j∈Ca‖zi−zj‖2W(C_a)= _i,j∈ C_a\|z_i-z_j\|^2 (96) denote the pairwise within-class scatter. Using the standard identity ∑i∈Ca∑j∈Cb‖zi−zj‖2=nb∑i∈Ca‖zi−μa‖2+na∑j∈Cb‖zj−μb‖2+nanb‖μa−μb‖2, _i∈ C_a _j∈ C_b\|z_i-z_j\|^2=n_b _i∈ C_a\|z_i- _a\|^2+n_a _j∈ C_b\|z_j- _b\|^2+n_an_b\| _a- _b\|^2, (97) and W(Ca)=2na∑i∈Ca‖zi−μa‖2,W(C_a)=2n_a _i∈ C_a\|z_i- _a\|^2, (98) we obtain nanb‖μa−μb‖2 n_an_b\| _a- _b\|^2 =∑i∈Ca∑j∈Cb‖zi−zj‖2−nb2naW(Ca)−na2nbW(Cb). = _i∈ C_a _j∈ C_b\|z_i-z_j\|^2- n_b2n_aW(C_a)- n_a2n_bW(C_b). (99) Summing over all pairs a<ba<b gives mean _mean =∑a<b∑i∈Ca∑j∈Cb‖zi−zj‖2−∑c=1KN−nc2ncW(Cc). = _a<b _i∈ C_a _j∈ C_b\|z_i-z_j\|^2- _c=1^K N-n_c2n_cW(C_c). (100) Therefore, −mean -D_mean =−∑a<b∑i∈Ca∑j∈Cb‖zi−zj‖2+∑c=1KN−nc2ncW(Cc). =- _a<b _i∈ C_a _j∈ C_b\|z_i-z_j\|^2+ _c=1^K N-n_c2n_cW(C_c). (101) Now substitute the shifted Euclidean similarity sij=M−‖zi−zj‖2.s_ij=M-\|z_i-z_j\|^2. (102) For the cross-class term, −∑a<b∑i∈Ca∑j∈Cb‖zi−zj‖2 - _a<b _i∈ C_a _j∈ C_b\|z_i-z_j\|^2 =∑a<b∑i∈Ca∑j∈Cbsij+const. = _a<b _i∈ C_a _j∈ C_bs_ij+const. (103) This is precisely the pairwise Graph Cut Mutual Information term, up to the convention-dependent constant factor in the definition of IGCI_GC. Similarly, by Theorem 1, for λ=0λ=0, −∑i,j∈Ccsij=W(Cc)+const.- _i,j∈ C_cs_ij=W(C_c)+const. (104) Hence the second term in Equation (101) is a class-size weighted Graph Cut Total Information term: ∑c=1KN−nc2ncW(Cc)=∑c=1KN−nc2nc(−∑i,j∈Ccsij)+const. _c=1^K N-n_c2n_cW(C_c)= _c=1^K N-n_c2n_c (- _i,j∈ C_cs_ij )+const. (105) Combining the two parts, we obtain −mean=αTITI~GCλ=0+αMI∑a<bIGC(Ca;Cb)+const,-D_mean= _TI\, TI_GC^λ=0+ _MI _a<bI_GC(C_a;C_b)+const, (106) where TI~GCλ=0 TI_GC^λ=0 denotes the class-size weighted Graph Cut Total Information term and αTI,αMI>0 _TI, _MI>0 depend only on the normalization convention. In the balanced-class case, where nc=n_c=n for all c, the class-size weights satisfy N−nc2nc=K−12, N-n_c2n_c= K-12, (107) which is constant across classes. Therefore, TI~GCλ=0 TI_GC^λ=0 reduces to a positive scalar multiple of the standard unweighted TIGCλ=0TI_GC^λ=0. Thus, minimizing the negative aggregate mean-separation objective is equivalent, up to positive scaling and additive constants, to minimizing a GC-TI term together with the pairwise GCMI term. This proves the claim. ∎ A.5 Proof of Theorem 5 Proof. Under the covariance LogDet approximation, we replace the LogDet score of a class by the log determinant of its covariance matrix. Thus, ILD(Ca;Cb)=logdet(Σa)+logdet(Σb)−logdet(Σab)+const,I_LD(C_a;C_b)= ( _a)+ ( _b)- ( _ab)+const, (108) where Σab _ab denotes the covariance of the union Ca∪CbC_a∪ C_b. Let Δ=μa−μb. = _a- _b. (109) The covariance of the mixture Ca∪CbC_a∪ C_b is Σab=pΣa+qΣb+pqΔΔT. _ab=p _a+q _b+pq ^T. (110) Using the pooled within-class covariance Σw=pΣa+qΣb, _w=p _a+q _b, (111) we can write Σab=Σw+pqΔΔT. _ab= _w+pq ^T. (112) By the matrix determinant lemma, det(Σw+pqΔΔT)=det(Σw)(1+pqΔTΣw−1Δ). ( _w+pq ^T)= ( _w) (1+pq ^T _w^-1 ). (113) Taking logarithms gives logdet(Σab)=logdet(Σw)+log(1+pqΔTΣw−1Δ). ( _ab)= ( _w)+ (1+pq ^T _w^-1 ). (114) By definition, ℳab=ΔTΣw−1Δ.M_ab= ^T _w^-1 . (115) Therefore, ILD(Ca;Cb) I_LD(C_a;C_b) =logdet(Σa)+logdet(Σb)−logdet(Σw) = ( _a)+ ( _b)- ( _w) (116) −log(1+pqℳab)+const. - (1+pqM_ab )+const. (117) The first three terms depend only on the within-class covariance structure and are independent of the mean separation. Absorbing them into the constant with respect to ℳabM_ab yields ILD(Ca;Cb)=const−log(1+pqℳab).I_LD(C_a;C_b)=const- (1+pqM_ab ). (118) Since the function −log(1+pqx)- (1+pqx) (119) is strictly decreasing in x for p,q>0p,q>0, LogDetMI is a monotone decreasing function of the Mahalanobis separation ℳabM_ab. Therefore, minimizing LogDetMI is equivalent, up to monotone transformations, to maximizing covariance-normalized class separation. ∎ A.6 Proof of Theorem 6 Proof. Let the modes of CaC_a and CbC_b be Ca,rr=1ma\C_a,r\_r=1^m_a and Cb,ss=1mb\C_b,s\_s=1^m_b with corresponding mode centers νa,r\ _a,r\ and νb,s\ _b,s\. Denote the mode cardinalities by na,r=|Ca,r|,nb,s=|Cb,s|.n_a,r=|C_a,r|, n_b,s=|C_b,s|. (120) Assume each mode is ρ-compact, i.e., ‖zi−νa,r‖≤ρ,∀zi∈Ca,r,\|z_i- _a,r\|≤ρ, ∀ z_i∈ C_a,r, (121) and similarly for every mode of CbC_b. Recall that Facility Location Mutual Information is IFL(Ca;Cb)=∑i∈Camaxj∈Cbsij+∑j∈Cbmaxi∈Casij.I_FL(C_a;C_b)= _i∈ C_a _j∈ C_bs_ij+ _j∈ C_b _i∈ C_as_ij. (122) Consider the first term. For any point zi∈Ca,rz_i∈ C_a,r, maxj∈Cbsij _j∈ C_bs_ij =maxj∈Cbexp(−‖zi−zj‖22τ2) = _j∈ C_b \! (- \|z_i-z_j\|^22τ^2 ) (123) =exp(−minj∈Cb‖zi−zj‖22τ2). = \! (- _j∈ C_b\|z_i-z_j\|^22τ^2 ). (124) Let s∗(r)=argminsdrs,s^*(r)= _sd_rs, (125) where drs=‖νa,r−νb,s‖.d_rs=\| _a,r- _b,s\|. (126) Since every mode is compact, dr,s∗(r)−2ρ≤minj∈Cb‖zi−zj‖≤dr,s∗(r)+2ρ.d_r,s^*(r)-2ρ≤ _j∈ C_b\|z_i-z_j\|≤ d_r,s^*(r)+2ρ. (127) Hence, maxj∈Cbsij=exp(−dr,s∗(r)22τ2)(1+o(1)), _j∈ C_bs_ij= \! (- d_r,s^*(r)^22τ^2 ) (1+o(1) ), (128) as ρ/τ→0ρ/τ→ 0. Summing over all points in mode Ca,rC_a,r yields ∑i∈Ca,rmaxj∈Cbsij=na,rexp(−dr,s∗(r)22τ2)+o(1). _i∈ C_a,r _j∈ C_bs_ij=n_a,r \! (- d_r,s^*(r)^22τ^2 )+o(1). (129) Summing over all modes, ∑i∈Camaxj∈Cbsij=∑r=1mana,rexp(−dr,s∗(r)22τ2)+o(1). _i∈ C_a _j∈ C_bs_ij= _r=1^m_an_a,r \! (- d_r,s^*(r)^22τ^2 )+o(1). (130) Applying the same argument in the reverse direction, define r∗(s)=argminrdrs.r^*(s)= _rd_rs. (131) Then, ∑j∈Cbmaxi∈Casij=∑s=1mbnb,sexp(−dr∗(s),s22τ2)+o(1). _j∈ C_b _i∈ C_as_ij= _s=1^m_bn_b,s \! (- d_r^*(s),s^22τ^2 )+o(1). (132) Combining Equations (130) and (132) gives IFL(Ca;Cb) I_FL(C_a;C_b) =∑r=1mana,rexp(−dr,s∗(r)22τ2) = _r=1^m_an_a,r \! (- d_r,s^*(r)^22τ^2 ) (133) +∑s=1mbnb,sexp(−dr∗(s),s22τ2)+o(1). + _s=1^m_bn_b,s \! (- d_r^*(s),s^22τ^2 )+o(1). (134) Finally, regrouping the two sums according to the mode pair (r,s)(r,s) yields IFL(Ca;Cb)=∑r=1ma∑s=1mbwrsexp(−drs22τ2)+o(1),I_FL(C_a;C_b)= _r=1^m_a _s=1^m_bw_rs \! (- d_rs^22τ^2 )+o(1), (135) where wrs=na,rs=s∗(r)+nb,sr=r∗(s).w_rs=n_a,r1\s=s^*(r)\+n_b,s1\r=r^*(s)\. (136) Thus, only nearest neighboring mode pairs receive nonzero weight in the approximation. Consequently, Facility Location Mutual Information is governed by nearest-mode overlap rather than aggregate overlap across all pairs of modes. ∎