Learning Structured Representations by Embedding Class Hierarchy with Fast Optimal Transport
Authors: Siqi Zeng
Sixian Du
Makoto Yamada
Han Zhao
Venue: ICLR 2025 Poster (2025)
Keywords: hierarchical representation
representation learning
optimal transport
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: To embed structured knowledge within labels into feature representations, prior work (Zeng et al., 2022) proposed to use the Cophenetic Correlation Coefficient (CPCC) as a regularizer during supervised learning. This regularizer calculates pairwise Euclidean distances of class means and aligns them with the corresponding shortest path distances derived from the label hierarchy tree. However, class means may not be good representatives of the class conditional distributions, especially when they are multi-mode in nature. To address this limitation, under the CPCC framework, we propose to use the Earth Mover's Distance (EMD) to measure the pairwise distances among classes in the feature space. We show that our exact EMD method generalizes previous work, and recovers the existing algorithm when class-conditional distributions are Gaussian in the feature space. To further improve the computational efficiency of our method, we introduce the Optimal Transport-CPCC family by exploring four EMD approximation variants. Our most efficient OT-CPCC variant runs in linear time in the size of the dataset, while maintaining competitive performance across datasets and tasks. The code is available at https://github.com/uiuctml/OTCPCC.

Published as a conference paper at ICLR 2025
LEARNING STRUCTURED REPRESENTATIONS BY EM- BEDDING CLASS HIERARCHY WITH FAST OPTIMAL
TRANSPORT
Siqi Zeng' Sixian Du
Makoto Yamada Han Zhao?
1 University of Illinois, Urbana-Champaige 2tanford University
Okinawa Institute of Science and Technology (siqi6, hanzhao @illl1111111 aillinniss... i dusixian@sstanford.ee makoto. yamada@oist. jp
ABSTRACT
To embed structured knowledge within labels into feature representations, prior work (Zeng et al. 2022) proposed use the Cophenetic Correlation Coefficient (CPCC) as a regularizer during supervised learning. This regularizer calculates pairwise Euclidean distances of class means and aligns them with the corresponding shortest path distances derived from the label hierarchy tree. However, class means may not be good representatives of the class conditional distributions. especially when they are multi-mode in nature. To address this limitation, under the CPCC framework, we propose to use the Earth Mover's Distance (EMD) to measure the pairwise distances among classes in the feature space. We show that our exact EMD method generalizes previous work, and recovers the existing algorithm when class- conditioiii distributions are Gaussian. To further improve the computational efficiency of our method, we introduce the Optimal Transport-CPCE family by exploring four EMD approximation variants. Our most efficient OT-CPCC variant, the proposed Fast Flow algorithm, runs in linear time in the size of the dataset, while maintaining competitive performance across datasets and tasks. The code is available at https: /tctps://githan http//gitttu hhu. com/ coon//iuctmm//TCPPP
INTRODUCTION
Supervised classification problems have been a cornerstone in machine learning. While traditional classification methods treat class labels independent entities, there has been growing interest leveraging semantic similarity among classes to improve model performance while following existing label dependency. This is particularly important in fine-graie fine-grained classification tasks where labels are inherently living on a hierarchy, such as the CIFAR (Krizhessky & Hinton 2009) and
IeageNet (Deng al. 2009) datasets. To capture the hierarchical relationship between classes, Zeng ett al. 2022) made a significant contribution by embedding the tree metric of a given class hierarchy into the feature space. They introduced regularizer, the Cophenetic Correlation Coefficient (CPCC), to correlate the tree metric with the Euclidean distance in the class-conditioned representations. This approach of encoding hierarchical relationship in the latent space not only led more interpretable features compared to other hierarchical classification methods (Shen et al. 2023), but also improved some generalization performance across multiple datasets.
Despite the value of this framework for embedding class hicrarchies, it presents a notable limitation. Specifically, ZZng et al. (2022) uses the Ea norm between two class Euclidean centroids, or equiva- lently, maximum mean discrepancy with the linear kernel, as the distance of two class distributions. However, this approach overlooks the difference of samples within the same class, and thus cannot fully capture the global structural information given pairs of class-conditional distributions, especially when they are modal. On the other hand, the use of Optimal Transport (OT) as an alternative to Euclidean centroids has first gained attention in the context of clustering, where Euclidean centroids neglect the intrinsic geometry of data distributions (Cuturi & Doucet 2014). For the same motivation, we propose addressing the limitation of CPCC (Zeng et al. 2022). by integrating the OT distance,

---

Published as a conference paper at ICLR 2025
also known as the Wasserstein distance, and its variants, distance between class distributions in the problem of embedding hierarchical representations.
effective metrie for measuring the
Our contributions family of OT-CPCC algorithm to address the limitation of using la centroids that misrepresents class relationships. We provide a detailed comparative analysis of E2-CPCC versus OT-CPCC about their forward and backward computation. (ii) We propose a novel linear time OT approximation algorithm, FasIFT, and apply it in the CPCC framework learn hierarchical representations that is significantly more efficient than the cubic time exact EMD solution. (iii) We empirically analyze the advantage of OT-CPCC over CPCC across wide range real-world datasets and tasks.
follows: (i) We first generalize the c2CCPC with EMD, and propose
PRELIMINARIES
Notation and Problem Setup Throughout the paper focus the supervised k-claas classi- fication problem. We denote a sample of input x with label y living in the space of X' C R' and y' = [ (1...,,)). The dataset DD consists of N data pairs ((ri, y))
Given the label space y. we have a corresponding label tree T that characterizes the relationship between different subsets of V. In particular, each node of T is associated with subset of y: each leaf node v is associated with a particular class in J/; any internal node corresponds to the subset that the union of its leaf children classes; the root node of T corresponds to the full y. The metric function of y is called tree metric ) x y - R4 which measures the similarity of two class labels u. v based on the shortest path distance of two leaf nodes on T. Intuitively, the tree could be understood as dendrogram of y that characterizes the similarity of different classes.
Let 2 S I be the representation/feauue space. deep network h is the composition of two functions Aw.9 = Iw fo X + As where A₁ is k -1 dimensional probability simplex. The layers until the penultimate layer that, 9n Z + As is linear classifier with weights w. Let g be the one-hot encoding vector of The parameters 0 and w are learned by minimizing combining the cross entropy loss fcE with an optional regularization term R:
feature encoder fo contains
neural network. On top of
k
f(x, yr w. 0)
zs log (x:) + XR(x, 0)
The hyperparameter À is the regularization factor which controls the strength of R. The goal of the problem is to embed the class hierarchical relationship in the feature space. At a high level, the distance of class-conditioned representations should approximate the tree metric of classes in T. This extra constraint can be quantitatively characterized by CPCC as the regularizer term R.
2.1 COPHENETIC CORRELATION COFFFICIENT
The Cophenetic Correlation Coefficient (CPCC) (Sokal Rohli 1962) was introduced regular- ization term in Zeng et al. (2022) to embed the class hierarchy T in the feature space. CPCC has the same formulation as Pearson's 's correlation coefficient that measures the linear dependence between two metrics f and p:
(1(u,)) ()(( v) u<e
cPCC(t,
(Σ -0) ( (plu, v) -))) u<e
u<t
where p is a distance function between u, on feature space 2, and F. p are the average of each metric. Let D., {x] w)) D, {x0] w)in ==
D be datasets with the same class label
When CPCCC is used as regularizer in Eq.
p(u v) =
f(x f(x8)-
Σ
f(a)))
D..
which is the le distance of the mean of the two class-conditional features. We call 2/¹ as the i-th feature vector with label u, when the context clear, we drop the superscript u for convenience. By
2

---

Published as a conference paper at ICLR 2025
Algorithm 1 Greedy Flow Matching
Algorithm 2 Bottom-up Tree Flow Matching
Input: number of features m, weights = (aI,..., am).
Input: m,n, b, flow tree T
1: P = =Array[m x n2]
b (b),..., bn)
2: for height h from 0 to (T) do
2: Array im x n]
1:
3: for each node v at height h do
4: if is a leaf then
3: j = 0
5:
Pass its flow to its parent else
4: while i m and j < do
6:
5: Pii,j] + min min(a]1].
b[1)
7:
(o(v) {z =a(z) > 0}. Co(e) {z
6:
ali
P j
b(2) > 0}, the leaf children of
7:
b[j
- P
j
8:
while 3z. E (v) and E Cb(v) do
8:
if ai
0 then
9:
" = min(((za)))) b(z))
++=1 1
10:
( 2b. += 7) a(2a) - n, b(zb)
9:
if b
0 then
11: Pass non-zero unmatched flows in either a or
j
to its parent
Output: P
Output: P
maximizing CPCC (A < 0), follows the relation in t: classes sharing close common ancestor will be grouped together while classes with a higher common ancestor are pulled away with respect to Euclidean distance.
2.2 EXACT EARTH MOVER'S DISTANCE
Earth Mover's Distance (EMD), or Optimal Transport distances, aims to find the optimal trans- portation plan between two discrete measures. For Du, let (a1...., 4m) E Am which is not necessarily uniform. Let b defined similarly for DD. and 82 is the Dirac delta at z. Define two discrete measures l Σ a,dz,;v V ンラ= bydzy. Then, EMD between probability distributions defined over 2, is the objective value of the following linear program:
min (P, D), s.t. Pl = a, P 1 b. P
In 3 (.))) is the Frobenius inner product, 1 the N-dimensional all ones vector, D is the m pairwise distance matrix where Dij || zy]|, and P called the flow matrix in the computer science literature, or optimal transport plan in the OT literature, the same size with D with nonnegative entries. Intuitively, this is a minimum cost flow problem. Both source and target flow sum to 1, and we want to find the optimal transportation plan P with the minimum cost with respect to ground similarity D. The norm I|-I| depends on the ground metric of D. We use the ||-1|2 norm as the ground metric throughout this paper.
When the dimension of the feature 2024). Instead of solving a linear program in Eg when m = 02 by = 1/n n for all i, the closed form solution for 1d EMD is: (M, v) E. [|=()) - 2'اا |l and z(() is the i-th order statistic of the sequence { 21. ... Zn } after sorting. When m * n, EMD generalizes to solving inverse CDF of p. V/ (Peyré & Cuturi] 2019) which requires approximation. To avoid this approximation, after sorting. we can compute the flow matrix P (Hoffman 1963) efficiently via a greedy algorithm in linear time [ and use the inner product objective of EMD 3q to compute the result. This greedy flow matching algorithm that generates the optimal transport plan can be used for any including the special case when m = n, and any non- non-uniform weights of a, b.
fast computation of the EMD distance exists (Houry et
CPCC WITH OPTIMAL TRANSPORT
3.1 OT-CPCC FAMILY
Despite its simplicity, the use of class centroids l distance as a measure of class distances has two limitations. First, since there is no guarantee of the distribution of class conditional features, the class mean difference may not accurately reflect the average pairwise Euclidean distance between all the pairs of sample. For example, in Fig class v is a non-unimodal (bi-modal in this example) distribution, which is very likely happen when class is abstract concept, such coarse classes like household furniture in CIFAR 100 (Krizhevsky & Hinton 2009) or the collection diverse dog breeds in ImageNet Deng et al.
2009 The blue Eg line can be biased estimation of the average of
3

---

Published as a conference paper at ICLR 2025
red lines. We will see later (c.f. Sec 3.3) that the direction of blue vector plays an important role in the feature geometry in C2CCPC and therefore we misrepresent the class distribution in Eg-CPCC. Second, it is known (Linial et al., 1994) that, for certain trees such basic star graph with three edges, is impossible to embed tree metric into &z exactly, no matter how large feature dimension is. It implies if use the Fuclidean centroids to represent class, CPCC value 1 during training, which always cause some loss of hierarchical information in the learning of structured representation.
never reach the optimal
How to overcome the above limitations? Instead of find- ing one-to-one correspondence of a label and point estimate of a class, we represent a label class with all samples that belong to the class, which leads to EMD- CPCC. We call the set of data-weight pairs containing m class-u conditioned features as μ [(2,, {,));² = and class-v define similarly for the dataset containing conditioned features. The weight a, can be set as uni- form (1/m) by default, non-uniform if external prior knowledge is available. We propose EMD&CPCC by im- plementing p(u, v) := EMD(H, v). In Eq P depends on D derived from each sample in two datasets. Besides, EMD actually a generalization of f2 method:
Class
Class
Meen
Meen
Figure 1: Comparison between EMD (weighted sum of red lines) and the class mean & distance (blue line).
Proposition 3.1 (EMD reduces to l between means of Gaussian with same covariance). EMD(N( E), E),,
E)) = || - -
Although EMD has many appealing properties, the computational cost of EMD is high, where the time complexity of linear programming is cubic time with respect to the data size. Many following work provides approximation methods to reduce the computational cost, such Sinkhorn (Cuturi 2013), Sliced Wasserstein Distance (SWD) (Bonneel et al. 2015), Tree Wasserstein Distance (TWD) (Yamada al., 2022 Le et al. 2019 Takkeawwa al.] 2021) ) and Flow'reee (FT) (Backurs et al. 2020) (detailed discussion of approximation methods in Apple Aj. Similarly, we can replace with all other EMD approximation methods, and we call all of them as the OT-CPCC family. As a side remark, since all approximation methods provide P satisfying constraints in Eq and since EMD is lower bounded by & (see proof of Prop 3.1 in App all OT-CPCC methods are still lower bounded by &z-
3.2
FAST FLOWTREE
2020 is tree-based method where the structure of the tree T is FlowTree (Backurs et al.
learned using QuadTree (Samet) 1984) to approximate the Euclidean space. Once the tree has been built, it firsts compute the optimal flow matrix P. using as the ground metric with linear time bottom-up as shown in Alg 2 (Kalantari & Kalantari, 1995) (see Aip.Fig S in for visualization).
Then, it estimates EMD with (P,, Dez). Given the tree, the time complexity of computing the FT is ((mm + n ad dd log(d))) where & is the maximum Euclidean distance of any two feature vectors.
Our Fast FlowTree The main computational bottleneck of FT is the construction of the tree. However, in our case, we have access to given as prior knowledge, and thus we can skip the tree construction step. To apply tree-based EMD approximation methods, instead of building QuadTreee in FT, we first construct an augmented tree by extending the leaves of the original label tree with samples. Specifically, since each leaf node in T corresponds to a class, we extend each leaf node by adding all samples from the corresponding class, as demonstrated in Fig 2 We set all extended edges to have edge weight 1, and assign the instance weight a; for each data point. The resulting algorithm that applies 2 to the augmented label tree is called Fast Flow Tree (FastFT).
Key Insight that allows FastFT to be more efficient than FT is that the tree metric between any two data samples from different classes is always identical in the augmented tree T. which allows us reduce the computation of P. 1 OT greedy flow matching using Alg T Now we can prove that Alg I and Alg 2 are equivalent given our constructed augmented tree in Fig 2 complexity of FastFT is O(m + n)d), which is optimal among all OT variants.
and the time
Theorem 3.2 (Correctness of Fast FlowTree), For any augmented label tree T, Alg. 4 Mnd Alg. 2 return the same EMD approximation. The Fast FlowTree can be computed in ((m n)d).
4

---

Published as a conference paper at ICLR 2025
Method
Time Complexity
#C exact
Use Tree
A-F-B
F
G
& EMD
O((nk + k2)d)
N/A
A-H
A
B
( n² log
Sinkhorn
((n2(d+1)) dn--dT)
E
TWD
SWD
Ö(np(d + n)) (nd log(d
1/5
FT
Figure 2: An example of augmented T. Leaves become samples of each class, and each sample is assigned some weight (ex., uniform) within a class. Whenever call FastFT-CPCC, only subtree rooted at the lowest common ancestor of pair of class label will be used. For example, we use subtree rooted at F to compute optimal flow of samples with label A, B, and subtree rooted at H for samples with label A, C.
FasIFT
((nd)
Table 1: Time complexity comparison of different CPCC methods. Let be the number of iterations for iterative methods, p be the number of projections for SWD, + be the maximum Fuclidean distance of any two feature vectors. We use to represent a factor of k22 For simplicity we assume m = n. In the batch learning setting, d can be much larger than n particularly for the grainge classification problems. See Appl for detailed analysis.
Please refer to App.D for proof details of Theorem 3.2 Note that all OT-CPCC methods inherently need f2(m n)d) because we access each of m + data point once and look at each entry in d-dimensions. Additionally, FastFT can be applied to any label tree with no restriction on structure or edge weights. To control the importance of data points, the flexibility of FastFT can be achieved by tuning a..
Comparison of OT-methods Synthetic Dataset To further understand the behavior of different OT approximation methods, we present experiments on synthetic datasets Fig App more details). We first measured the computation time for different OT methods across datasets of varying sizes. Second, we evaluated the еrror of different OT approximation methods, along with the & distance of the mean of two datasets, in approximating EMD. Two different scenarios either both distributions were Gaussian or non Gaussian. Under Gaussian distribution, the OT methods' results were closely aligned with the &2 method, except for SWD. which supports Prop and implies the similarity in performance between OT and CCCCCC under Gaussian distributions. In non-Gan Con-Gausiian distribution scenario, notable differences emerged between OT methods and lz, where SWD is closer to & measurement. FastFT demonstrated exceptional advantage as an approximation method, outperforming Sinkhorn in both computational speed and precision.
considered,
Caussian Distribution
Non Gaussan Distribttion
2.0
Sknkhom
SWD
FassFT
EVD
Srihhom
1.0
20
SWD FaeFT
0.5
500
1000
1500
2000
2500
3000
3280
1000 1500 2000 2500 2000
2333
dalaved sice.
Figure 3: Efficiency and approximation error comparison of OT methods on synthetic datasets.
3.3 DIFFERENTIABILITY ANALYSIS OF OT-CPCC
Since we use some non-differemtiable algorithms during training (ex., linear programming in EMD, sorting in SWD, tree construction in TWD, greedy algorithm in FT and FastFT), it is unclear how does the backpropagation algorithm work exactly in this problem. Thanks to the Danksin's 's theorem (Danskin) 1966) and the structure of the underlying optimization problem,
still
5

---

Published as a conference paper at ICLR 2025
efficiently compute the gradients of OT-CPCC For simplicity, let consider the case of EMD-CPCC, ie., p = EMD exactly. The other approximate variants can be analyzed in a similar way.
The underlying challenge of the problem is to take derivatives of the optimal value of a minimization problem. We state the differentiability section of Danskin's 's theorem formally and prove a lemma:
Theorem 3.3 Danskin (196)). Let (xz) maxzee f(x, 2), and Zo(z)
( is the set of that achieve the maximum Vf at If R C > continuous and C is compact, then the subgradient of V is the convex hull of set { (0f(2,2) 2 E Zo}. Particularly, if Zo = {z*)
av 0f(z.z))
år
ax
Lemma 3.4. Denote P as the optimal flow of EMD problem, then 2pma
P
8D
80
06
Proof. We rewrite the objective function as maximization problem: PEMD maxpec (P. D). Roughly speaking, Danksin's 's theorem states that the derivative of maximization problems can be evaluated at the optimum. We can get (sub-) Jibbeeriffeettlal of PEMD with respect to f with one step of chain rule:
@PEND
pPEDD
0D
d- O
aD = P OD
00
aD
00
OD
00
where the last term comes from the original flow of backpropagation containing the gradients with
respect to network parameters. The key takeaway is the gradient PEMD w.r.t. the network parameters does not require the gradient from P in the EMD setting, although P depends on A.
Differentiability for Other OT-CPCC Methods The application of Danskin's 's relies on the opti- mality of P". How about the other approximation methods? The differentiability is not a problem in Sinkhorn as the iterative algorithm only involves matrix multiplication. But for the SWD, TWD, FT, the approximate solutions (the flow matrix P) for these methods are not explicitly formulated as solutions to an optimization problem. Following EMD, except for the Sinkhorn variant, our constant for these approximation methods, and stop the
method is to treat flow matrix always gradient through P. For example, in Fast PlowTree, since the tree flow matrix P depends only on the structure of the tree based on external information and not on the model parameters 0, we have
Oprast 86
PFaIIFT 30
To provide more fine-grained understanding of the proposed method, in what follows we analyze the gradients of the proposed CPCC variants and compare them with the C-CCPC
Gradient of CP-CPCC If we want to know the difference between CPCC and EMD-CPCC, assume the same input and the same network parameters, ignoring the cross-entropy loss, the only difference of the gradient starts from the distance calculation between two classes. Assume representations from two classes are Z E Rm Z' E Rnxd
0p12 az
1 1 Z - 11 2')
11ke
az
2T 1 TT
m
Let i-th row of be Z... Each row of Opia is the same,
0%
0pt, 0g 1'' m ||pe M
oz,
Gradient of EMD-CPCC Let D E Roxn be the cost matrix and P is any constant flow matrix:
PEND (P", D(2,2')) = Σ 12. - Z
1.
Let's calculate the derivative by rows Z. We only keep the terms related to Z...
ÖPEMD
à
2, Z
OZ. Oz. Σ P Z, 2,,11 Σ
12, Z
J=1
Note that since P is the optimal solution of a linear program, it is a sparse matrix with at most m + n 1 non-zero entries (Peyré et al.) 2019 Proposition 3.4). As comparison to the gradient of C2CC which assigns equal importance to all data points and only depends on the direction of class centroids, the gradient of EMD-CPP CPC assigns different importance each pair of data points and depends on the pairwise transport probability between data points. From this analysis, we can see that the gradient provided by EMD-CPCC is more fine-grained and informative than that of CPCC.

---

Published as a conference paper at ICLR 2025
4 EXPERIMENTS
For a fair comparison, we closely aligned our implementation with Zeng et al. (2022) to ensure consistency. This section will cover dataset benchmarks, the multi-modality of features, downstream hierarchical classification retrieval, and interpretability analysis. A detailed deseription of training hyperparameters is provided in A along with additional experiments. including the effect of label hierarchy structure, label hierarchy tree weights, optimal transport flow settings (distribution of a in 3) and comparisons with non-CPCC hierarchical methods, in App Throughout this section, the Flat objective is the standard cross entropy loss in Eq with À = 0 without tree information.
Table Datasel Statistics.
Table 3: Preciseness of hierarchical information.
Dataset
train
test
Dataset
Objective
TestCPCC
Dataset
Objective
TesCPCC
CIFARIO
50K
10K
Flat
58.83 (8.80)
Flat
47.63 (1.18)
CIFARI00
50K
10K
&2
99.94 (0.02)
92.30 (0.35)
INAT
500K
100K
LI7
FastFT
91.71 (0.15)
L17
88K
3.4K
CIFARIO
FastFT
99.95 (0.00)
Sinkhom
91.77 (0.44)
N26
132K
5.2K
EMD
99.95 (0.01)
SWD
95.10 (0.51)
E13
334K
13K
Sinkhorn
99.94 (0.01)
E30
307K
12K
SWD
99.98 (0.00)
29.77 (0.53)
Eg
93.03 (0.32)
source
Flat
22.13 (0.84)
FastFT
92.68 (0.21)
lz
83.08 (0.11)
Sinkhorn
93.31 (0.24)
SWD
92.40 (0.05)
CIFARIOO
FastFT
93.85 (0.05)
EMD
89.60 (0.34)
Flat
49.20 (0.86)
train/test
Sinkhorn
93.81 (0.10)
&2
92.02 (0.08)
target
SWD
73.17 (2.66)
E13
FastFT
91.97 (0.20)
Sinkhorn
91.30 (0,57)
Flat
31.97 (0.00)
SWD
88.32 (0.50)
E2
67.01 (0.04)
Flat
$1.33 (0.09)
INAT
FastFT
73.20 (0.03)
93.37 (0.19)
Figure 4: Hierarchical data split. Source and target dataset share the same coarse labels but different fine labels.
EMD
65.80 (0.01)
E30
FastFT
91.81 (0.44)
Sinkhorn
73.20 (0.04)
Sinkhomn
91.89 (0.61)
SWD
50.88 (0.03)
SWD
89.88 (0.68)
4.1 DATASETS
We conducted experiments across 7 diverse datasets, CIFARIO, CIFARI00 (Krizhessky & Hinton 2009), BREEDS benchmarks (Santurkar et al. 2021 including four settings LIVING17 (L.7), ENTITY13 (E13), ENTITY30 (E30), NONLIVIN VING26 (N26), and iNaturalist-min (Van Horn et al. 2018 (INAT) to thoroughly evaluate the efficacy and influence OT-CPCC methods. The dataset statistics is shown in Tab Note that BREEDS and INAT are larger scale datasets with high resolution images. As subsets of ImageNet, BREEDS inherit a more complicated label hierarchy and more realistic, possibly multi-modal class distributions. The major difference from ImageNet is that BREEDS's 's class hierarchy is manually calibrated so that it reflects the visual hicrarchy instead of the WordNet semantic hierarchy in the original ImageNet, which removes ill-defined hierarchical relationships unrelated to vision tasks.
4.2 EXISTENCE OF MULTI-MODE
FEATURE DISTRIBUTION
To verify our hypothesis in Fig I we aim to determine whether conditoond clusters exhibit multi-modal structure in practice. We track the class-conditioned features during training: at each epoch, for each class-conditioned feature cluster, we fit Gaussian Mixture Model (GMM) with the number of components ranging from to 10. We report the optimal number of components based on the lowest Akaike Information Criterion (AIC), averaged across all fine-level class labels. If the best number of Gaussian components exceeds 1, this may indicate the presence of multi-modal structure in the feature distributions, assuming a sufficiently large batch size. From Fig with default training hyperparameters in ApplE] we observe that this phenomenon occurs across most datasets for both CPCC and OT-CPCC training, suggesting that using optimal transport distances in CPCC computation is more appropriate.
7

---

Published as a conference paper at ICLR 2025
Dog. Best Component
BMD
Dataset
Comp.
3.10
CIFARIO
9.90
3.05
CIFAR100
3.07
3.00
INAT
3,48
BREEDS
1.25
2.95
150
109
Epocha
Figure 5: The average best number of components of learned features (left) across training epochs on CIFARI 100 for different CPCC methods (right) for the C2-CPCC final trained features for all datasets.
Figure 6: CIFARI00 Euclidean UMAP for l-- 4-CCPC (left) vs. EMD-CPCC (right). Each cluster represents fine label and we color data sample by coarse labels.
4.3 HIERARCHICAL CLASSIFICATION AND RETRIEVAL
Table 4: Generalization performance on coarse level. The prefix of metric represents the split of test set: source, target. The average number of three seeds reported. See the detailed version including standard deviation in T6b[16]17] and performance on each BREEDS setting is in Tab Due the computation complexity, do report EMD results on training BREEDS from scratch.
Dataset
Objective
SAcc
tAce
sMAP
tMAP
Dataset
SAcc
tAcc
sMAP
tMAP
Flat
99.58
87.30
99.22
89.66
94.63
38.81
70.41
34.00
FastFT
99.61
87.79
99.91
93.04
94.66
39.43
72.90
35.63
CIFARIO
INAT
EMD
99.61
87.45
99.88
93.07
94.64
41.01
73.87
35.58
Sinkhom
99.61
87.41
99.87
92.60
94.30
36.94
68.75
34,92
SWD
99.56
87.63
99.36
90.12
94.52
39.38
75.13
38.11
Flat
86.17
43.09
82.07
42.09
93.85
82.43
74.47
66.50
FastFT
86.96
44.29
91.71
42.20
94.25
82.89
92.84
79.69
CIFARIOO
BREEDS
EMD
86.93
44.03
91.82
42.32
Sinkhorn
86.93
43.99
91.61
42.45
94.42
83.51
91.84
79.33
SWD
86.42
43.35
87.24
42.39
94.41
82.96
83.58
72.38
Table 5: Generalization performance fine level.
Dataset
Objective
sAcc
tAce
sMAP
Dataset
sAce
tÁce
sMAP
E2
96.96
55.71
99.22
88.62
26.78
56.10
FastFT
96.90
55,99
99.24
88.49
27.10
56.21
CIFARIO
INAT
EMD
97.05
56.12
99.24
88.68
26.78
56.83
Sinkhorn
96.95
54.89
99.27
88.08
26.77
51.56
SWD
96.96
59.21
99.45
88.46
26.78
54.19
E
80.98
23.76
77.52
82.66
45.95
62.86
FastFT
81.09
24.71
78.72
82.58
45.75
63.95
CIFARI00
BREEDS
EMD
81.32
23.15
78.88
Sinkhorn
80,99
23.53
78.51
82.99
46.87
61.54
SWD
80.50
26.18
86.82
82.90
46.33
76.24
Hierarchical Dataset Split For downstream classification and retrieval, we split each dataset into source and target subsets, with both further divided into train and test sets, illustrated in Fig The source and target datasets share the same level of coarse labels but differ in fine labels, where the fine level refers to the more granular class labels that are exactly one level below the coarse labels. For example, in CIFAR1O, the source set includes the fine labels (deer, dog, frog, horse) ) and (ship, truck). while the target set includes (bird, cat) and (airplane aut omobi le). Both sets share the same coarse labels: animal and tzansportation We include details of hierarchical construction and splits for other datasets in App
8

---

Published as a conference paper at ICLR 2025
Given the hierarchical splits, we define two evaluation protocols. First, we pretrain the source-train set and evaluate on the source-test set, where the train and test distributions are i..d. Second, we pretrain on the cource-train set and evaluate the target-test set, introducing a subpopulation shift (Santurkar et al. 2021) between the train and test distributions. For each protocol, we conduct classification and retrieval experiments two levels of granularity.
Metries For classification experiments, we measure performance using accuracy (Acc). At the fine level, source accuracy is computed directly using any pretrained model, while coarse source accuracy calculated by summing the fine-level probabilities for predictions that share the same coarse parent label. Since the source and target sets share the same coarse labels, coarse target accuracy can be similarly computed using the model pretrained on the source split. For fine target accuracy, after pretraining the source set, train a linear classifier top of the frozen pretrained encoder for one-shot learning on the target-train set and evaluate it on the target-test set. We include the visualization of all types of classification tasks evaluation in Fig 9 in the Appendix.
For retrieval experiments, we use mean average precision (MAP) as the evaluation metric. Given a model pretrained the source set, compute the fine coarse class prototypes by calculating the Euclidean centroid of the class-conditioned features, Using these class prototypes, we compute the cosine similarity score between the prototypes and test points, and evaluate whether test points most similar to the class prototype with the same label via average precision. Since the source and target sets have different fine labels, we do not include target MAP T
Discussion OT-CPCC outperforms lz- CPCC consistently on fine level tasks: the oracle for the fine level tasks should be Flat, and Zeng al. (2022) reported that &2-CPCC does not perform well for several fine level tasks due to the constraint on coarse level. Tabss that OT-CPCC methods shows better fine-level performance than l,, while maintaining hierarchical information simultancously. Besides, OT-CPCC outperforms the Flat baseline consistently on coarse level tasks as expected in Tab which implies OT-CPCC methods successfully include the additional hierarchical information by optimizing the regularizer. In Fig 6
we visualize the learned hierarchical embeddings
using UMAP (Mcinnes et al., 2018), with Euclidean distance as the similarity metric. We observe that C2-CPCC displays clearer coarse-level grouping pattern, likely due to the direct optimization of CPCC in Euclidean space. However, EMD-CPCC also retains a significant amount of hierarchical information and demonstrates better separation between fine-level classes, which aligns with the results observed in our classification and retrieval tasks.
4.4
INTERPRETABILITY EVALUATION
f EMD
E:225
0.-
Test CPCC
6.900
CPCC
0.935
BMD
FTst
0.0
0.61
6.925-
ft
0.5
EMD
6.900
FastFT
0.4
61128
0.0 025 052 o/s
100 Regularization Facctor
125
130 lls
2:00
0.0
PH14
RM52
VIT-0/16
VT7.11
Backbone Architecture
Figure 7: Test CPCC for various batch size, regularization strength, and architecture, from left to right. FastFT consistently performs the best across all settings.
model more interpretable when its representations accurately capture hierarchical information. CPCC is natural measure of the precision of the hierarchical structure embedded in corresponding metric spaces. Unlike rank-based metrics, where only the relative order distances matters, CPCC not only requires the correct ranking of distances (i.e., fine classes sharing the same coarse class should be closer than fine classes with different coarse parents), but also influenced by the absolute values of the node-to-node distances, because CPCC is affected by the given label tree weights. Therefore, we report CPCC, a stricter metric, on the test set. In Tab[3] we present & CPCC for the Flat and & objectives, and use the corresponding OT distances for the OT-CPCC experiments.

---

Published as a conference paper at ICLR 2025
We observe that OT- CPCC preserves more hierarchical information. leading to better interpretabilltyy As shown in T in 5 out of 7 datasets, an OT-CPCC method achieves the best TestCPCC score. For E13 and E30, OT-CPCC methods slightly underperform compared to Eg, likely due to the BREEDS representations being less multi-modal than those of other datasets, as indicated in T
Ablation Study In our experiments with CIFARIOO, 100, shown in Fig 7 we investigated the impact of batch size, the regularization factor X in [ and architecture on Test Given CIFAR 100's large number of fine classes, the average sample size per class is relatively small when applying CPCC with standard batch size of 128. Consequently, there is minimal difference between using the centroid of a few data points, as in E2-CPCC, and using pairwise distances for each data point in OT-CPCC. Therefore, larger batch sizes allow OT-CPCC to better capture class distributions, potentially leading to a more significant advantage in the quality of the learned hicrarchy. We compared TesCCPCC across various settings, including batch sizes of [64, 128, 512, 1024], À values of [0.01, 0.05, 0.1, 0.5, 1, 21, and backbones such as ResNet18, ResNet34, ResNet50 (He et al. (016). ViT-B/16, and ViT-L/16 (Dosovitskiy) 2020), using l2, EMD, FastFT CPCC. Across all comparisons, we observe that FastFT > EMD &2 in terms of the quality of the learned hierarchy, highlighting the advantage of optimal transport-base based methods.
RELATED WORK
Learning Hierarchical Representations We discuss methods that operate on feature represen- tations, thereby directly influencing the geometry of the representation space when hierarchical information is provided. DeViSE (Frome al. 2013) is an early multimodal work to align image and text embedding evaluated on a hierarchical precision metric to reflect semantic knowledge in the representation. [Ge et al. (2018); Zhang et al. (2016) modify triplet loss to capture class similarity for metric learning or image retrieval. [aaz & Denzler (2019); Garg et al. (2022) embed classes on hypersphere based on hierarchical similarity, and similar ideas have been explored in the hyperbolic space (Kim et al. 2023) where tree can be embedded with low distortion. Yang al. (2022) provides a multi-task proxy loss for deep metric learning. Nolasco & Stowell (2022) proposes a ranking loss to make Euclidean distance of feature close to target d-dim sequence determined by the rank of tree metric. We work on the extension of Zeng et al. (2022) which is a special type of hierarchical methods where a regularizer is used. For a broader discussion on various hierarchical methods, direct readers to the summary provided by Bertinetto et al. (2020).
OT Methods and Hierarchical Learning The application of Optimal Transport (OT) in hierar- chical learning contexts is explored in a limited number of studies. Ge et al. (2021). for instance, substitutes the conventional cross-entropy with a novel loss function that optimally transports the predictive distribution to the ground-truth one-hot vector, modifyyng the ground metric tree metric and thus utilizing the hierarchical structure of the classes. Additionally, SEAL (Tan et al., (023) em- ploys the TWD to construct latent hierarchy, enhancing traditional supervised and semi- supervisdd learning methodologies. It can be demonstrated that, given a tree T. the optimization process for TWD aligns with & loss optimization and is upper bounded by the SumLoss baseline introduced by Zeng et al. (2022). Consequently, these methodologies can be categorized as hierarchical loss functions rather than regularization methods discussed in this work.
CONCLUSION
Building upon Zeng et al. (022) using CPCC regularizer learn structured representations, we have identified and targeted the limitations inherent in 4pCCCC. Our proposed OT-CPCC family provides more nuanced measurement of pairwise class distances in feature space, effectively capturing complex distributions theoretically and empirically. Furthermore, our novel linear FastFT algorithm itself is interesting nature for OT communities. FastFT-CPCC can be viewed as a successful application in learning tasks, and we welcome future work to investigate more on the properties of our greedy approach.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
SZ and HZ are partially supported by an NSF IIS grant No. 2416897. HZ would like to thank the support from a Google Research Scholar Award. MY is partly supported by MEXT KAKENHI Grant Number 24K03004 and by JST ASPIRE JPMJAP2302. The views and conclusions expressed in this paper are solely those of the authors and do not necessarily reflect the official policies or positions of the supporting companies and government agencies.
REFERENCES
Arturs Backurs, Yihe Dong, Piotr Indyk. Ily Razenshteyn, and Tal Wagner. Scalable nearest neighbor search for optimal transport. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 497-506. PMLR, 13-18 Jul 2020. URL
m1 mlr. wttpppsssslllllacaeeeeeeee
html
Björn Barz and Joachim Denzler. Hierarchy-basee image embeddings for semantic image retrieval. In 2019 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 638 647, January 2019. doi: 10.1 (09/WACC.2019.000073.. URL http::/aax....rg///aa/p.p arXiv:1809.0992. [es].
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pp. 41 41-48, 2009.
Luca Bertinetto, Romain Mueller, Konstantinos Tertikas, Sina Samangooei, and Nicholas A Lord. Making better mistakes: Leveraging class hierarchies with deep networks. In Proceedings of the IEEE/CVF conference on computer vision and pattem recognition, pp. 12506-1255 12515, 2020.
Kush Bhatia, Himanshu Jain, Purushottam Kar, Manik Varma, and Prateck Jain. Sparse local embeddings for extreme multi-label classification. Advances in neural information processing systems, 28, 2015.
Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and radon wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 1(51):22 45, 2015. doi: 1111007//00851-0014-556666
Rich Caruana. Multitask learning. Machine learning, 28(1):41-75, 1997.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL
mips. http:/ppprrr...ps..cccccpppeeeep wttpf//eeee/ppe//1////////////// 45220007702222211572255333382382
Marco Cuturi and Arnad Doucet. Fast computation of wasserstein barycenters. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 685 693, Bejing, China, 22-24 Jun 2014. PMLR. URL htLlhhtts://patt httpt::::///poceediggs.rttt ml wwt.:mmww...rrre.emmmmmmmme prw.s http:////wwwcutttrteeeee http/euttuuii./e html
John M. Danskin. The theory of max-min, with applications. SIAM Jourmal on Applied Mathematics, 14(4):641-66 1966. ISSN 00361399. URL /ttp::/ttt//tt jstor. http:/staalleeeeee
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009. doi: 10. 1OO/CV9R.2009.5222222 55066488
Alexey Dosovitskiy. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1 1929, 2020.
D.C Dowson and B.V Landau. The fréchet distance between multivariate normal distributions. Journal of Multivariate Analysis, 12(3):450-455 1982. ISSN 0047-259X. doi: https://doi.orr/10
101670477225XX(8))00077
11

---

Published as a conference paper at ICLR 2025
Itay Evron, Edward Moroshko, and Koby Crammer. Efficient loss-based decoding graphs for extreme classification. Advances in Neural Information Processing Systems, 31, 2018.
Andrea Frome, Greg S Corrado, Jon Shlens, Samy Bengio, Jeff Dean, Marc' Aure- lio Ranzato, and Tomas Mikolov. Devise: A deep visual-semantic embedding model. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https: http:s::////appp.speees nips wwtpppppppppeeeeeeeeee 1ca333t966742227777777777777777 -tt.srttttttttttbtaaattt....... Abstract. wwt.ffllsspppp//e/e/ /aaa//ppee//211/aaaha
Ashima Garg, Depanshu Sani, and Saket Anand. Learning hierarchy aware features for reducing mistake severity. In European Conference on Computer Vision, pp. 252-267. Springer, 2022.
Weifeng Ge, Weilin Huang, Dengke Dong, and Matthew R. Scott. Deep Metric Learning with Hierar- chical Triplet Loss, volume 1210 Lecture Notes in Computer Science, pp. 272-288. Springer In- ternational Publishing, Cham, 2018. ISBN 978-3-030-01130-4,
doi: 3 -00-0000--20000 01200113311111
17. BtRphtts:://l0
www.ksspringee wwwpppi...........ppppo.... www.c/ccccc.... 1007/ 978
Yubin Ge, Site Li, Xuyang Li, Fangfang Fan, Wanqing Xie, Jane You, and Xiaofeng Liu. Embedding semantic hierarchy in discrete optimal transport for risk minimization. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2835-2839.
IEEE, 2021.
Vivek Gupta, Rahul Wadbude, Nagarajan Natarajan, Harish Karnick, Prateek Jain, and Piyush Rai. Distributional semantics meets multi-label learning, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3747-3754, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770-778, 2016.
A. J. Hoffman. On simple linear programming problems, volume 7, pp. 317-327. American Mathematical Society, Providence, Rhode Island, 1963. ISBN 978-0-88888 0-82188-407799 doi: 10.1090/ pspum/007/0157778 URL wwww. ams. wwtp 007
Guillaume Houry, Han Bao, Han Zhao, and Makoto Yamada. Fast 1 I-wasserstein distance approxima- tions using greedy strategies. In International Conference on Artificial Intelligence and Statistics, pp. 325-333, PMLR, 2024.
Peiyun Hu, Zachary C. Lipton, Anima Anandkumar, and Deva Ramanan. Active learning with partial feedback, 2018. URL
07427
Ankit Jalan and Purushottam Kar. Accelerating extreme classification via adaptive feature agglomer- ation. arXiv preprint arXiv: /769, 2019.
Bahman Kalantari and Iraj Kalantari. Linear-Time Algorithm for Minimum Cost Flow on Undirected O pp. 217-223, Mathematics and Its Applications. Springer US, Boston, MA, 1995. ISBN 978- 1778-1-4613-355-22 doi: 10.
URL https: org/
Sungyeon Kim, Boseung Jeong, and Suha Kwak. Hier: Metric learning beyond class labels via hierar- chical regularization. In 2023 IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pp. 19903-19912, Vancouver, BC, Canada, June 2023. IEEE. ISBN 9798350301 298. doi: 10.1109/CVPR52299990 011.:729..2231199900 102052737
URL
.etooreeeeeeee. ieee. orq/ ott...o///occmeettttt...e/////.. document/
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
Tam Le. Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. Tree-sliced variants of wasserstein distances. Advances in neural information processing systems, 32, 2019.
N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 577-591, 1994. doi: 1 1109/FFCS 1993.36533..
12

---

Published as a conference paper at ICLR 2025
Yitao Liu, Chenxin An, and Xipeng Qiu. Y-tuning: An efficient tuning paradigm for large-scale pre-trained models via label representation learning. Frontiers of Computer Science, 18(4):184320, 2024.
Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprini arXiv:/802.03420 2018.
George A. Miller. Wordnet: lexical database for english. Commun, ACM, 38(1))33944 nov 1995. ISSN 0001-0782. doi: 10.1144/2997.7.219944. 219717.219741
Quang Nguyen, Hamed Valizadegan, and Milos Hauskrecht. Learning classification models with soft-label information. Journal of the American Medicul Informatics Association, 21(3):001-508, 2014.
Ines Nolasco and Dan Stowell. Rank-based loss for learning hierarchical representations. In ICASSP 2022- 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3623-3627. IEEE, 2022.
Gabriel Peyré, Marco Cuturi, et Computational optimal transport: With applications data science. Foundations and Trends in Machine Learning, 11(5-6)35556077 2019.
Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends in Ma- chine Learning, 11 (5-6):355-602, 2019. URL BtLhhtps::/ /awaiiiiii.../... wwwpvvvvor//aaoo hts///bb/11003 00567
Hanan Samet. The quadtree and related hierarchical data structures. ACM Computing Surveys (CSUR), 16(2):187-260, 1984.
Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. Breeds: Benchmarks for subpopu- lation shift. International Conference on Learning Representations, 2021. URL https
/oopenreview.oo Fodete/oooommdddmmmmamma
Ethan Shen, Ali Farhadi, and Aditya Kusupati. Are" hierarchical" visual representations hicrarchical? arXiv preprint arXiv:2311.0576 2023.
Robert R. Sokal and F. James Rohlf. The comparison of dendrograms by objective methods. Taxon, 11(2)333-00, 1962. ISSN 00400262. URL.http://www/ htt.fftp::/ww...sorrroorrro// http://///..ooooorro////////////
Xu Sun, Bingzhen Wei, Xuancheng Ren, and Shuming Ma. Label embedding network: Learning label representation for soft training of deep networks. arXiv preprint arXiv: 10393, 2017.
Yukihiro Tagami. Annexml: Approximate nearest neighbor search for extreme multi-label classifica- tion. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 455-464, 2017.
Yuki Takezawa, Ryoma Sato, and Makoto Yamada. Supervised wassesssertnin distance. In International Conference on Machine Learning, pp. 10086-10095. PMIR, 2021.
Zhiquan Tan, Zihao Wang, and Yifan Zhang, Seal: Simultaneous label hierarchy exploration and learning. arXiv preprint arXiv:2304. 13374, 2023.
Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie. The inaturalist species classification and detection dataset. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8769-8778. 8778, 2018.
Jason Weston, Samy Bengio, and Nicolas Usunier. Wsabie: Scaling up to large vocabulary image annotation. In Twenty-Second International Joint Conference on Artificial Intelligence. Citeseer, 2011.
Makoto Yamada, Yuki Takezawa, Ryoma Sato, Han Bao, Zomitsa Kozareva, and Sujith Ravi. Approximating I-wasserstein distance with trees. Transactions on Machine Learning Research, 2022. ISSN 2835-8856. URL http:pp:://ageeeeeeeeeeeeeeeeeee
13

---

Published as a conference paper at ICLR 2025
Zhibo Yang, Muhammet Bastan, Xinliang Zhu, Doug Gray, and Dimitris Samaras. Hierarchical proxy-based loss for deep metric learning. In 2022 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV). pp. 449-458, Waikoloa, HI, USA. January 2022. IEEE. ISBN 978-1-665400-11-55. doi: 10. WW1///AACV51155.22220000055 URL
feee.orrg/0cccmmee///776653
-s Yu, Prateek Jain, Purushottam Kar, and Inderjit Dhillon. Large-scale multi-label learning with missing labels. In International conference on machine learning, pp. 593-601. PMLR, 2014.
Siqi Zeng, Remi Tachet des Combes, and Han Zhao. Learning structured representations by em- bedding class hierarchy, In The Eleventh International Conference on Learning Representations. 2022.
Xiaofan Zhang, Feng Zhou, Yuanqing Lin, and Shaoting Zhang. Embedding label structures for fine-grained feature representation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1114-1123, 2016.
14

---

Published as a conference paper at ICLR 2025
APPENDIX
A APPROXIMATION METHODS OF EARTH MOVER'S DISTANCE
Most approximation methods do not rely on any tree structure. Sinkhorn (Cuturi 2013 is a fully differentiable approximation method which leverages the entropic regularization setup of EMD and the convergence of doubly stochastic matrix. Sliced Wasserstein Distance (SWD) (Bonneel et al. 2015) projects data to 1 dimension through random projection matrix and uses EMD1a for fast calculation, but the quality of approximation highly relies on the number of random projections. Tree Wasserstein Distance (TWD) (Yamada et al. 2022: Le et al., 2019; Takezawa et al. 2021) is a tree based approximation algorithm that can be written in the closed matrix form |[diag w Bia b)]l where w contains weights of T and B is 0-1 internal nodes by leaf nodes matrix that represents if node is the ancestor of a leaf node. To make sure TWD a good approximation, an extra step of lasso regression is performed to learn such that the tree metric approximates Euclidean distance between features with iterative gradient based method. In Yamada et al. (2022), requires us to learn the tree distance between all pairs of nodes, which leads to quadratic computational complexity with respect to sample size as shown in Tab
B COMPARISON OF STRUCTURED REPRESENTATION LEARNING AND LEARNING LABEL REPRESENTATIONS
Generally speaking, the problem of structured representation learning and the problem of learning label representations, or learning label embeddings, are two different topics. In label representation learning, each label is mapped to a high-dimensional vector for downstream tasks. For example, in standard multi-class classification, we typically use one-hot vector embeddings. Alternative approaches include using a soft label to assign probability values in (0.1) each class (Nguyen et 2014). or learning label embeddings (Weston et al.) [011]] [unn et al. 2017: Liu et al., 2024). Label representation learning methods have various downstream applications, such as text summarization (Sun et al. 2017). novelty detection (Barz & Denzler 2019), and extreme classification (Jalan & Kar
2019 Tagami 2017
Bhatia et al., 2015 Yu al. 2014]] Evron et al., 2018 Gupta et al. 2019)).
While C2CCCC falls into this category, OT-CPCC methods are not label embedding methods. Instead of representing a class with a Euclidean centroid in f2, OT-CPCC methods intentionally avoid this step by considering more nuanced relationship between labels. OT-CPCC relies pairwise relationships between data points from two classes to include more complex distributional geometry during lcarning. Since these methods depend data point relations, there is one-to-one correspondence between label and a representation.
C EMD-CPCC GENERALIZE: C2-CPCC
We can show EMD-CPCC is a generalization of previous work of CPCC through the following proposition.
Proposition 3.1 (EMD reduces to b between means of Gaussian with same covariance). EMD(N (), E)) ||p- Mz
Proof. Since μl, in EMD definition are probability measures, the definition of EMD can be general- ized to continuous distributions as well. Denote the random variable from μu, Z' from v, and q the coupling between μ and v, then EMD can be also expressed in the following p- D-Wasserstein (W,, form when p 1:
Wp = inf /
|| - 2)11""(21, 2,),,2))222
9 xx
inf (E z 1
9
With this definition, our statement can be proved in two steps. First, we want to show the lower bound of EMD is ||ا- - Pz for any pairs of input random variables. By one step application of Jensen's
15

---

Published as a conference paper at ICLR 2025
inequality, since every norm is convex, we have the following result from the expectation form of Wi in Eq
Wi = inf 1| Z = inf | Z
EZ - EZ = || P2
(5)
Second, we need to show EMD S || - ووy for the given Gaussian constraints. Following the convexity of quadratic function, apply Jensen's again, we have:
W (inf E || 212 < inf [[[ Z 111 W32
(6)
Dowson & Landau 19822 showed the following analytical form of
W || |= Σ. + E. - 2(E.E.,)
This distance metric is also sometimes called Bures- Wasserstein (Bures) distance. The trace term becomes 0 if 2ig D
D DETAILS FOR FAST FLOW TREE CPCC ALGORITHM
In this section, we first present the full pseudocode to compute PastFT-CPCC in Alg Compared to FlowTree (Backurs et al. 2020) which uses helper function in Alg 2 Kalantari Kalantari [995), we replace the greedy fl Flow__a www_matching algorithm with Alg I which aligns with algorithm that computes the dimensional OT transportation plan.
Algorithm 3 Train with Fast flow/Tee CPCC
input epoch batch size B, train data D (:)) dictionary S for iteration 0, 1, E do
1:
2: for batch 0,
|N/B] BB do 3: assume there are k: classes in batch
4: for (a. b) in (=) pairs of classes do
5:
Za -01.....,mm)
6:
26
(b.....,b, b..)
7:
if (m, n) in or (n, m) in S then P + --((,,, n)]
8:
9:
else
10:
P greedy htt.eeyyhgloommmhhhhgghgooo n, a
AAgg]
11:
S[(m, +
12:
idx + P Pnnozerooo p(a, b) =
(store nonzero index tuples of P)
13:
14:
for (i,j) in idx do
15:
p(a, b) += Pli norm(za(i), =[])
Calculate Eq with CPCC as
17:
Update network parameters with backpropagation
Now we prove the correctness of Fast Flow Tree algorithm and its relation dimensional optimal transport distance.
Theorem 3.2 (Correctness of Fast FlowTree). For any augmented label tree T, Alg. 7 and Alg. return the same EMD approximation. The Fast FlowTree can be computed in O(mm + n.d).
Proof Sketch We can observe that the blue code blocks, which contain the update rule of the flow matrix, are almost identical between and Alg According to Kalantari & Kalantari (1995). provides the optimal flow matrix for the optimal transport problem using the tree metric as the ground metric in D. From Fig [ the tree distance between any two samples in the augmented tree is always the same, meaning the order of encountering any vertex within the source or target distribution does not matter. This effectively reduces the Flow Tree problem in Alg to flat 1d EMD problem in Alg The major difference between two algorithms is that, unlike Alg Alg A does not require passing the flow from the leaf to the root node.
16

---

Published as a conference paper at ICLR 2025
Proof. 2 will not start to match leaves until the current node has children from two different distributions, or in our context, from two different fine labels. This is because of the while statement in line 8: based our construction of T in Fig 2 if the current node is either leaf or a fine label node, then all of its children are from either Ca (c) or Ca(v), so we will jump to line 11 to send all flows to e's parent. Therefore, the matching starts at the lowest common ancestor of two label nodes.
Now we have e as the lowest common ancestor of two fine class nodes (ex., F or H in Fig 2 Before entering line 9, we always pass unmatched demands the parent, and we can see the demands are always from one label until we reach the lowest common ancestor. From Fig [ we also know at this point, we have collected all flows from both labels. Therefore, the sum of flow 1 for both fine label nodes when the matching starts.
Both Alg and Alg greedily remove one sample from either distribution. The greedy plan is always feasible and no unmatched flow is left after one scan of all m + features, because we inherently remove the the same amount of flow from both distributions every iteration in the while loop. Thus, on our T, we can skip most steps in Alg 2 bottom up step in line 2, looping through all vertices at height h, the if-else check from line 4-7, and the last step of passing unmatched demands to parents are all unnecessary. Alg terminates immediately once we run through all while loop steps, thus reducing to Alg
_ the flow matrix solution for 1-d EMD problem, can be used when Monge Property or north- west-comer rules (Hoffman )963) hold. It can be shown by induction that this O(m + n) greedy algorithm can be applied whenever the following constraint is satisfied: if ((=),a))) {(2), bU)} are indexed (1d feature, weight) sequences, for indices i < i2 and f1 < j2:
Din. + Dia.ja S Di + Din.i
(8)
If two sequences are ordered (in ascending order) by metric defining D, we have 21, S 2ig and 2j1 Zjz- There are in total six cases for any i2 < f2:
1. If 21
S 2ja
S 24,
S Z1g. then Eq
holds. holds
2. If 2tj I 2i
2jz
Sig. then Eq
8
Zi,
2/1
2/3
2,, 2
because
2i, S Zjz-
3. If Zjz S %/ < 2ig
S Zjz
then Eq
+ Eis T
22g S 36
2/1
+ Zio
holds
because 2i, I Ziz'
4. If 211 S 2j1 I Zja
I 212
then Eq
+ 2j 2
13
24 S 34
+ 212 2ト holds
because 2/1 I 2t2"
5. If 2,, S 2jj < Zia
$ Zjzz
+ 2j. 2,, then Eq
t3
2/ S 34
2h 2ia 2j. holds
because 2j1
< Ziz.
6. If zi S Zia S Zj
2jzz then Eq
35
holds.
Therefore, if two sequences are ordered with respect to some metric, Eq is satisfied.
Recall we need the extra sorting step in the beginning of 1 OT plan to apply the greedy flow matching algorithm. The distance function in Eq 8 is decided by the ground metric of EMD, which does not make any difference for I dimensional features. In Flow Tree, a tree is constructed with QuadTree such that the tree distance of any two features is close to the Eg distance between them. In this case, in EMD computation, we can improve computational efficiency by Flow Tree. With extended label tree T, because all same class sample leaves belong one single parent, we have special case here where the tree distance of any two samples from μu, V are always the same, satisfying Eq[8] vacuously. This statement fails only if we assign different edge weights for each sample during the extension of label tree, and does not depend on the weights of original label tree. To avoid the limitation on the extended edge weights, we can instead assign different weights a; for each sample to adjust the importance of each dat points. Therefore, FastFT is still very flexible.
For the time complexity, Alg requires at most (mm+n) steps from line 4. The most time-consuming aspect is computing the didimensional distance of O(m + n) pairs in D, since there will be at most m + n nonzero values in D after applying the greedy matching algorithm, which makes the final time complexity as O(mm + n)dd.
17

---

Published as a conference paper at ICLR 2025
on M onl 5T1
unmoscced
First skip leaf modes,
For node
Start from vervices on depth I.
Iihel notwerr dosccrdants untrocched.
011
on
(a) Step
(b) Step 2
makitell
1/5
1/5
Greaailyy mutch paine demand eapply.
Maa - 155
updii:
We only posable par: x
fully
(c) Step
(d) Step
3
I0
Repest the steps for
Pass the nonvurno semmining foow the
paremt of leaf todes v.
Step
(I) Step 6
Repest the same steps for v
Repest the same steps for
1/5
1/5
/2
10 16
1
Step
(h) Step 8
3
10
Repeat the some stops for vi
10
Repeat same steps for V
1/10
40
3
10
10
(i) Step 9
(j) Step 10
Go to one level above.
3/
A0
We get the full low matris.
Repear all steps.
1/5
3 10
1/5
v 10
1/10
1/10
(k) Step 11
()) Step 12
Figure 8: Example run of Alg Bottom-up Tree Flow Matching.
18

---

Published as a conference paper at ICLR 2025
E DATASET HIERARCHY CONSTRUCTION
In this section, we discuss the details of dataset hierarchies and how we created the dataset splits. Throughout the main body of this paper, consider two-level hierarchy: coarse and fine. For each coarse node, except for BREEDS, we split the coarse node's fine children into approximately 40% for the target set and 60% for the source set. Following this procedure, the splits are detailed in Tables 6
10 11 and T2| The original class labels for CIFARTU 10 and CIFAR 100 are from www.s:tttss.......... www
7 8
9
//github. com/ / wtt.://ww..oomiiiiiee////./a///a wisapppccc///ntttccooo////e///t/ html for iNauuralist from https and for BREEDS from
WordNet (Miller 1995).
The CIFARIO hierarchy was manually constructed by us, while the CIFAR 100 hierarchy is provided in the original dataset. In INAT, fine and coarse classes correspond the class and phylun um labels from the original annotations. These higher-level labels are particularly suitable for evaluating multi- modal settings, where OT-CPCC methods may have a more significant advantage over &2-CPCC.
In Zeng et al. (2022), fine classes in BREEDS are defined one level deeper than the original labels. However, due the large number of classes and limited samples per class within batch, the distinction between f2CPCC and OT-CPCC can become less apparent. To address this, we employ a three-level hierarchy, using the labels from Santurkar et al. (202T) as fine labels and setting their parent categories mid and coarse labels. Consequently, due to BREEDS setting, the fine classes are the same for both source and target datasets, so there is no source-target split Tables 9 10 and 12 Despite this hierarchical structure, multi-modality. With this design, in Sec 4.3) for classification and retrieval experiments, one-shot fine-tuning is not required for BREEDS on the target split.
in F BREEDS exhibits relatively low
Table 6: CIFAR10 hierarchy and data split.
Coarse
Source
Target
animal
deer, dog, frog ship, truck
bird, cat airplane, automobile
transportation
Table 7: CIFAR100 hierarchy and data split.
Coarse
Source
Target
aquatic mammals
otter, seal, whale ray, shark, trout roses, sunflowers, tulips cans, cups, plates oranges, pears, sweet pepper lamp, telephone, television couch, table, wardrobe butterfly, caterpillar, cockroach lion, tiger, wolf house, road, skyscraper mountain, plain, sea chimpanzec, elephant, kangaroo possum, raccoon, skunk snail, spider, worm girl, man, woman lizard, snake, turtle rabbit, shrew, squirrel palm, pine, willow motorcycle, pickup truck, train streetcar, tank, tractor
beaver, dolphin aquarium fish, flat fish
fish
flowers
orchids, poppies bottles, bowls apples, mushrooms
food containers
fruit and vegetables
household electrical devices
clock, computer keyboard bed, chair bee, beetle bear, leopard bridge, castle cloud, forest camel, cattle fox, porcupine crab, lobster baby, boy crocodile, dinosaur hamster, mouse maple, oak bicycle, bus lawn-mower, rocket
household furniture insects
large carnivores
large man-made outdoor things large natural outdoor scenes large omnivores and herbivores medium-sized mammals
non-insect invertebrates people
reptiles
small mammals
trees
vehicles
vehicles 2
19

---

Published as a conference paper at ICLR 2025
Table 8: INAT hierarchy and data split.
Coarse
Source
Target
Arthropoda
Diplopoda, Hexanauplia, Insecta,
Arachnida, Chilopoda
Malacostraca, Merostomata
Chordata
Ascidiacea, Aves, Elasmobranchii,
Actinopterygii, Amphibia
Mammalia, Reptilia
Cnidaria
Hydrozoa, Scyphozoa
Anthozoa
Echinodermata
Echinoidea, Holothuroidea, Ophi-
Asteroidea
uroidea Cephalopoda, Gastropoda, Polypla- cophora
Mollusea
Bivalvia
Ascomycota
Lecanoromycetes, Leotiomycetes,
Arthoniomycetes, Dothideomycetes
Pezizomycetes, Sordariomycetes
Basidiomycota
Dacrymycetes, Pucciniomycetes,
Agaricomycetes
Tremellomycetes
Bryophyta
Polytrichopsida. Sphagnopsida
Bryopsida Cycadopsida, Gnetopsida
Tracheophyta
Liliopsida, Lycopodiopsida, Magno- liopsida, Pinopsida, Polypodiopsida
Table 9: LIVING17 dataset hierarchy.
Coarse
Fine
bird
grouse, parrot salamander turtle, lizard, snake, serpent, ophidian spider, crab, beetle, butterfly dog, domestic dog, Canis familiaris, wolf, fox, domestic cat, house cat, Felis domesticus, Felis catus, bear, ape, monkey
amphibian
reptile, reptilian
arthropod
mammal, mammalian
Table 10: NONLIVING26 dataset hierarchy.
Coarse
Fine
structure, place
dwelling, home, domicile, abode, habitation, dwelling house, fence, fencing, mercantile establishment, retail store, sales outlet, outlet, out- building, roof
paraphernalia
ball, bottle, digital computer, keyboard instrument, percussion instru- ment, percussive instrument, pot, stringed instrument, timepiece, time- keeper, horologe, wind instrument, wind squash
food, nutrient apparel, toiletries conveyance, transport
bag. body armor, body armour, suit of armor, suit of armour, coat of mail, cataphract, coat, hat, chapeau, lid, skirt boat. bus, autobus, coach, charabanc, double-decker, jitney, motorbus. motorcoach, omnibus, passenger vehicle, car, auto, automobile, machine, motorcar, ship, truck, motortruck chair
furnishing
F TRAINING HYPERPARAMETERS
We conducted all experiments with NVIDIA RTX A6000. The architectural and training setups for each dataset as follows:
20

---

Published as a conference paper at ICLR 2025
Table 11: IN dataset hierarchy.
Coarse
Fine
living thing, animate thing non-living thing
bird, reptile, reptilian, arthropod, mammal, mammalian garment, accessory, accoutrement, accouterment, craft, equipment, für- niture, piece furniture, article of furniture, instrument, man-made structure, construction, wheeled vehicle, produce, green goods, green groceries, garden truck
Table 12: ENTITY30 dataset hierarchy.
Coarse
Fine
living thing, animate thing
serpentes, passerine, passeriform bird, saurian, arachnid, arachnoid, aquatic bird, crustacean, carnivore, insect, ungulate, hoofed mammal, primate, bony fish
non-living thing
barrier, building, edifice, electronic equipment, footwear, legwear, garment, headdress, headgear, home appliance, household appliance, kitchen utensil. measuring instrument, measuring system, measuring de- vice, motor vehicle, automotive vehicle, musical instrument, instrument, neckwear, sports equipment, tableware, tool, vessel, watercraft, dish, vegetable, veggie, veg, fruit
F.1 CI CIFARI00
We conduct training from scratch using ResNet18, following the ResNet architecture design where the first convolution layer employs 3x3 kernel size, while the pooling layer is omitted. The images are preprocessed by normalizing them according to CIFAR10/CIFARI1 100's mean and standard deviation. We augment the training data by first rero-padding the images by 4 pixels, then cropping them back to their original dimensions, applying a 50% chance of horizontal flipping, and randomly rotating the images between -15 and 15 degrees.
For CIFAR1O, 10, the pretraining process spans 100 epochs with a batch size of 64. The learning rate begins at 0.01 and is decreased by a factor of 10 every 60 steps, with momentum set at 0.9 and weight decay set to 5 x 10 in the SGD optimizer. For CIFAR 100, the pretraining process spans 200 epochs with a batch size of 128. The learning rate begins 0.1 and is decreased by factor of every 60 steps, with momentum set at 0.9 and weight decay set to 5 x 10-4 in the SGD optimizer. Additionally, for both datasets, the fine-level one-shot transfer learning, we train for 100 epochs starting at learning rate of 0.I, which is reduced by factor of 10 every 60 steps. CPCC is applied to coarse, fine level and À in [i is set to The ratio between the distance between two fine classes sharing the same coarse parent and those sharing different parents is 1:2.
F.2 BREEDS
We train ResNet18 model from scratch originally designed for ImageNet, where the first convolution layer uses 7x7 kernel. Adhering to the BREEDS training setup, we use a batch size of 128, an initial learning rate of 0.1, and SGD optimization with a weight decay of 10-4. For the ENTITYI3 and ENTTTY30 datasets, the model is trained for 300 epochs, reducing the learning rate by factor of 10 every 100 steps, while for LIVINGI7 and NONLIVING26, we extend training to 450 epochs, with the learning rate divided by 10 every 150 steps. Data augmentation for the training set includes a RandomResizedCrro to 224x224, horizontal flipping with a 50% probability, and color jittering that adjusts brightness, contrast, and saturation within range of 0.9 to 1.1. The test set, the other hand, is resized to 256x256 and then center-cropped to 224x224.
Since in our experiments with BREEDS, the source and target split share the same set of fine labels, to calculate fine target accuracy, is unnecessary to use one-shot transfer learning. We directly use the source pretrained models for target fine accuracy evaluation.
21

---

Published as a conference paper at ICLR 2025
To apply CPCC methods, backtrack two levels up to find the mid and coarse labels from the original class labels in BREEDS. CPCC applied to mid and coarse level and À in Eq set to 1. The ratio between the distance between two fine classes sharing the same coarse parent and those sharing different parents is 1:2.
F.3 INAT
We fine-tune an ImageNet-pretrained ResNet18 model where checkpoint can be downloaded twt.rrreessttiittttttttstt--/r/e IMAGENET1 K_V1')
in Pytorch
18
models. resnet18 html). The images are preprocessed by normalizing them with mean=[00.466, 0.471, 0.380J and standard deviation= 195, 0.194, 0.192]. We augment the training data by cropping random portion (scale=(0.08,, 1.0), ratio=(0.755 1.33)) of image and resize it to 224x224, and apply a 50% chance of horizontal flipping. We use a batch size of 1024. The learning rate begins at 0.1 and is decreased by factor of 5 every 60 steps, with momentum set 0.9 and weight decay set to 5 x 10-4 in the SGD optimizer. In the downstream one-shot fine-tuning task, we learning
train for 60 epochs starting
of 0.05, which is reduced by factor of 10 every 15 steps, CPCC is applied to coarse, fine level and À in Eq [ is set to 0.1. The ratio between the distance between fine classes sharing the same coarse parent and those sharing different parents 1:3.
Bagar
Figure 9: Visualization of the evaluation of hierarchical classification.
G HIERARCHICAL BASELINE OBJECTIVES
In this section, we introduce the details of hierarchical objectives used in Fig 12
Flat is the naive cross entropy loss only on the fine level, so the expression is:
Cyia (Ir, Yine)
Σ
Fyia (yinne l(xx)).
(DDD))D
We adopt all hierarchical baselines from the comparative study in Zeng et al. (2022). including:
Multi-Task Learning (MTL) (Caruana 1997), where the backbone model is trained with two linear heads-one for coarse classes and one for fine classes-each with a cross-entropy loss. The total loss, CMIL, the sum of these two cross-entropy terms, with a scaling coefficient of for both. Curriculum Learning (Curr) (Bengio et al.) 2009) involves two training phases: first, training coarse head for 50 epochs, followed by training the full network with a fine head for 200 epochs, starting from the coarse-trained features, assuming that coarse classification is an easier task. Sum Loss (Hu et al. 2018) uses only one fine classifier head, where coarse predictions are obtained by summing the fine class probabilities for the same coarse parent and applying a second cross-entropy loss. Hierarchical Cross Entropy (HXE) (Bertinetto et al. 2020) is the sum of weighted cross- entropy losses (a 0.4), where the hierarchical structure is incorporated into the log probabilities. The same paper also introduces Soft Label (Soft), which uses a single softmax loss based on the height of the least common ancestor between label pairs, with hyperparameter 10. Quadruplet
22

---

Published as a conference paper at ICLR 2025
Loss (Quad) (hhag et al. 2016) extends triplet loss by defining two types of positive labels based on the hierarchy. For detailed mathematical expressions of these objectives, refer to App.C in Zeng et al. (2022).
We also include several recently published hicrarchical losses:
Soft Hierarchical Consistency (SHC) (Garg al., 2022) is the combination of MTL and Sum Loss. For a two level hierarchy, they jointly train a two-headed network. Define the network as h: X A x Akz with shared feature encoder f X 2 and two classifiers Jceasse 2 . 99ine Z + Aky, with 11 as the number of coarse classes and k2 the number of fine classes. The ground truth coarse probability Peoarse = Scoarse (f()) is the output of coarse head after softmax normalization, and Peuarse is derived from the output of fine head. Let W be k by 1z2 matrix representing the relationships in the label tree: if a fine class belongs a coarse class j. then W is 1, else the entry is set to O. Then Peaorse W gine (f)(),,
the probability of belonging to a given coarse class is the sum the probabilities of its fine class descendants in the tree. Then, the SHC loss is defined as the Jensen-Shaaee -hannon Divergence between these two probability distributions:
Lsnc (1, Yccarse: Yfine) = [SDope (x, Yeourse Il (I, Viine)
(10)
In Garg et al. (2022), Lshc is used in the combination with Flat cross entropy loss. Therefore, we treat it as a counterpart of CPCC losses and use F + X LSHC as the training loss, with À
Geometric Consistency (GC) (Garg et al. 2022) is also computed under the MTL two-head
pipeline. The coarse classifier can be decomposed to a linear layer and softmax function, i.e., let We E Rdxks,
Jecase softmax (.).).)))))............)) and we define W similarly for the linear fine layer.
k1 1 - cos (W; W9).
LGc(I, Mevarses Vine
(1I)
==1
As in SHC, GC aims force the similarity between the predicted coarse weight and the true coarse weight. Here, W is part of the linear classifier corresponds to each coarse class, and the predicted
coarse weight W = (EEchidreen() w / Σ Echildren(s) w is the normalized sum of a part of fine classifiers based on the hierarchical relationship. We combine Lgc with Flat cross entropy during training and set A in Eq as 1.
RankLoss (Rank) (Nolasco & Stowell 2022) proposes ranking loss make Euclidean distance of feature close to the target d--im sequence determined by the rank of tree metric:
Crank (I, Yeearse Yline)
p E -
(12)
In this equation above, Ip is an indicator variable which shows whether the rank of pairwise &g feature distance the same as the rank of pairwise tree metric distance, and TargetRank a function reflecting hierarchical similarity. Since this loss does not focus on discriminative tasks like classification, we combine with Flat cross entropy, setting À in Eq for downstream tasks evaluation.
H ADDITIONAL EXPERIMENTS
H.1 EFFECT OF TREE DEPTH
Although in the main body we focus on depth-3 label hierarchy consisting of a root node, a coarse level, and a fine level, we also test whether our method can be applied to more complex trees. In CIFARI00, beyond the standard fine-coarse levels, introduce mid level by grouping 5 fine classes from the same coarse class into two smaller groups (2 + 3). Additionally, we create a coarser level by grouping two alphabetically neighboring coarse classes into single coarser label. For example, for 10 fine labels, the hierarchical grouping is highlighted by the following color scheme: [[(orchids, poppies) (roses, sunflowers, tulips)] [(bottles, bowls) (cans, cups, plates)]].
In Fig 10 we aligned the axes to sort the fine labels based on the hierarchical structure for embeddings learned using trees of varying depth. We then computed the fine-to-fine class distances using either
23

---

Published as a conference paper at ICLR 2025
depth
depth
depth 5
EMD
depth = 3
depth =4
depth 5
FastFT
Figure 10: CIFAR100 class embedding pairwise distance matrix for different types of label with varying tree depth.
used the standard fine-coarse CIFARI00 label tree, where a clear pattern of twenty 5x5 coarse blocks appears on the diagonal for both optimal transport methods. In the middle of Fig I0 we applied CPCC the fine-mi min-mid-coarse hierarchy, and within each 5x5 coarse block, we observed the expected fine- tne-grained 2x2 + 3x3 patterns. Similarly, on the right of Fig T0 when we included the coarser grouping, we could observe the merging of neighboring 5x5 coarse blocks.
the EMD FastFT metric. On the left of Fig 10
Table 13: EMD and FastFT performance for tree with different depths on the full CIFARI00 dataset.
The batch size is set 128.
Objective
Setup
CPCC
FineAce
CoarseAce
depth 3
88.80
71.91
82.21
EMD
depth 4
85,09
72.59
82.93
depth 5
88.64
72.20
82.50
depth = 3
90.75
72.71
83.31
FastFT
depth 4
87.86
72.45
83.05
depth = 90.27
72.56
83.04
We also include metrics for the preciseness of hierarchical information and hierarchical classification in Tab 13 As observed in Fig 10g the tree information is well-learned, leading us to expect high CPCC scores across all settings in Tab 13 For the hierarchical classification metrics, within the same OT method, the difference between FineAcc and CoarseAce small. is worth noting that, because train on the full CIFAR dataset for visualization purposes, the source-target hierarchical split shown in Fig 4 is not applied here. Both FineAce and CoarseAce are reported on the original CIFAR 100 test set. This suggests that even when the tree used is not identical the label hierarchy associated with the dataset, an approximate tree with a similar structure is sufficient for classification tasks.
In summary, EMD-CPCC a flexible structured representation learning method that adapts well complex hierarchies, while FastFT-CPCC serves good approximation to EMD-CPCC. This
24

---

Published as a conference paper at ICLR 2025
observation is consistent with the results in Tab where optimal transport methods achieve higher Test CPCC values.
H.2
EFFECT OF TREE WEIGITT
1x
2x
4x
EMD
1x
2x
4x
FastFT
Figure 11: CIFAR100 class embedding pairwise distance matrix for different types of label with varying tree weights.
In this section, we demonstrate that all CPCC methods, including OT-CPCC, are influenced by input tree weights. In I1 we begin with the original unweighted CIFAR 100 tree (where all edges have a default weight 1) and modify the edge weights of subtree representing the coarse label aquat ic mammals. which includes five fine labels: beaver, dolphin, otter, seal, and whale. We visualize the learned representation through a distance matrix, as described in Sec H.I From left right in Fig 11 the edge weights of this subtree set to 1, 2, and 4, respectively. Consequently, we observe a color shift the top-left coarse block the matrix, with the block gradually darkening the subtree weights increase. This demonstrates the flexibility of OT-CPCC methods, which can successfully embed weighted trees, and highlights why CPCC a sensitive and effective metric for evaluating the interpretability and quality of the hierarchical information embedded in the learned representation, as discussed in Sec 4.4
Table 14: EMD and FastFT performance for tree with different edge weights within
aquatic i c__ m__maamaa mma classes on the full CIFAR100 dataset. The batch size is set 1024.
Objective
Setup
CPCC
FineAcc
CoarseAcc
weight
89.13
75.76
85,50
EMD
weight 2x
88.85
75.57
85.22
weight 4x
79.86
75.56
85.35
weight 1x
92.12
75.43
85.43
FastFT
weight 2x
92.57
75.38
85.10
weight 4x
84.23
75.57
84.98
We use the same experimental settings as those described in Sec H.I While the classification metrics remain comparable, the most significant trend emerges in the CPCC metric. As shown in
25

---

Published as a conference paper at ICLR 2025
Fig II observe the expected pattern in the top-left block, which changes as the edge weights are multiplied. However, as the injected hierarchy deviates further from the given label hierarchy, becomes increasingly unnatural. The increased weights make the tree embedding more challenging, resulting in drop in CPCC values for larger weights.
H.3 EFFECT OF FLOW WEIGHT
In Eq the flow weight vectors a and are set to uniform by default in all other experiments. However, practice, these vectors can customized by the user if prior information about the data distribution is available, which may significantly influence the learned embeddings. On CIFARIOG we tested three different flow weight settings:
Uniform (umif): default setting where we assume each data point is uniformally sampled from the class distribution, so a (1/m..... 1/m) and (I/n....,
Distance (dist): is an adaptive weighting method where during training, we compute the Euclidean centroid of each class and compute the distance of each sample to the corresponding class centroid. Then we can apply softmax function to normalize the distances into probabilities. Mathematically, if two class representations Z, Z', then for each entry exp(Z,
of flow weight vector, ag = 23-1 exp(2,
by = -n-1 exp(2] P2
exp(2
Inverse-Distance (inv): is similar to dist, yet the only difference is we set the weight to be inversely scaled by the distance to the centroid, so the expressions of the flow weights are exp(nt - Z,) explu, 2z)* b 25m1 expla, 27)*
exp(1__ (-1() 2()
a,
From T3 we observe two key findings: first, tuning the flow weights can lead to improvements generalization metrics for the target set. but this comes the expense of in-distribution source metrics. Second, the most significant differences are seen in the CPCC values, where it is nearly impossible recover hierarchical information the test set when using the Distance flow weight for both EMD and FastFT. The low interpretability scores suggest that not all flow weight settings are suitable for hierarchy learning.
in
Table 15: Comparison of FastFT and EMD methods with different optimal transport flow weighting schemes across fine and coarse metries, with cell colors representing the magnitude of values.
Fine Metrics
Coarse Metries
Objective
Weight
CPCC
SAcc
sMAP
tAcc
SÁcc
SMAP
tAcc
tMAP
unif 93.85
81.32
78.88
23.15
86.96
91.71
44.29
42.20
FastFT
dist 9.30
78.90
67.33
25.28
85.18
91.47
45.00
43.78
inv 66.52
79.73
68.31
25.45
85.81
92.03
43.70
43.70
unif 89.60
80.99
78.51
23.53
86.93
91.82
44.03
42.32
EMD
dist 19.87
79.23
73.79
26.05
85.91
91.30
43.55
42.53
inv 98.13
79.51
75.84
26.80
86.05
91.22
44.15
42.13
I ANALYSIS FOR THE TIME COMPLEXITY OF OT APPROXIMATION METHODS
In this section, we provide the details and references for the reported time complexities in Tab
In the following time complexity analysis, denote b as batch size. We assume each class- consiconddt cluster has the same size n, which implies b = nk, where & is the number of classes.
For lz. given one batch of batch size b, computing Euclidean centroids for all classes requires scanning through all d-dimensional data points once, which requires ((bd) O(nkd). We have at most classes in one batch, so computing the pairwise distances between class centroids will cost (k) The total cost for fg is O(nnk k2)d).
26

---

Published as a conference paper at ICLR 2025
Table 16:
Detailed generalization performance on fine level. Each value is the mean (std) of three seeds of experiments. Flat directly optimizes on the fine level classes, so we treat it as the upper bound of fine metries and colored in grey. The bold values have the largest mean for column metric within a dataset, ignoring the upper bound.
Dataset
Objective
SAce
tAcc
sMAP
Dataset
SAcc
tAcc
sMAP
Flat
96.92 (4)
54.23 (6.92)
99.43 (0.02)
88.70 (0.01)
26.77 (0.04)
63.97 (0.04)
fg
96.96 (0.16)
55.71 (7.38)
99.22 (0.06)
88.62 (0.01)
26.78 (0.04)
56.10 (0.05)
CIFARIO
FastFT
96.90 (0.13)
55.99 (8.19)
99.24 (0.02)
INAT
88.49 (0.01)
27.10 (0.04)
56.21 (0.05)
EMD
97.05 (0.18)
56.12 (7.63)
99. (0.02)
88.68 (0.00)
26.78 (0.04)
56.83 (0.00)
Sinkhorn
96.95 (0.08)
54,89 (8.59)
99.27 (0.03)
88.08 (0.00)
26.77 (0.04)
51.56 (0.04)
SWD
96.96 (0.05)
59.21 (4.42)
99.45 (0.03)
88,46 (0.00)
26.78 (0.04)
54.19 (0.03)
Flat
80.53 (0.31)
28.44 (1.89)
86.47 (0.21)
82.08 (0.26)
45.19 (0.38)
73.74 (0.46)
&2
80.98 (0.17)
23.76 (1.01)
77.52 (0.12)
82.66 (0.41)
45.95 (0.40)
62.86 (0.38)
CIFARIOO
FastFT
81.09 (0.18)
24.71 (0:90)
78.72 (0.19)
BREEDS
82.58 (0.34)
45.75 (0:45)
63.95 (0.36)
EMD
81.32 (0.19)
23,15 (0.40)
78.88 (8.18)
Sinkhorm
80.99 (0.12)
23.53 (0:48)
78.51 (0.20)
82,99 (0.31)
46.87 (0.40)
61.54 (0.55)
SWD
80.50 (0.33)
26.18 (1.04)
86.82 (0.22)
82.90 (0.30)
46.33 (0.16)
76.24 (0.39)
Table 17: Detailed generalization performance on coarse level. Each value is the mean (std) of three seeds of experiments. & directly optimizes on the coarse level classes, so treat it as the upper bound of coarse metrics and colored in grey.
Datave
Objective
sAce
LAce
sMAP
IMAP
Dataset
sAcc
LAce
sMAP
IMAP
99 6il (0:01)
87.5 51 (0.97)
99 SS, (0:11)
92 07.84 (8.63)
94:52 (0.00)
41186 (0.01)
74, 74.34((0.05)
57 (0.01)
Flat
99.58 (0.07)
87.30 (0.59)
99.22 (0.05)
89.66 (0.38)
94.63 (0.00)
38.81 (0.01)
70.41 (0.04)
34 (0.13)
CIRARIO
FaaFT
99.61 (0.05)
87.79
99.91
93.04
INAT
94.66
39.45
72:90
35.63 (0.01)
EMD
(0.03)
87.45 (0.00)
(0:03)
(0.63)
(0.00)
41.01 (0.01)
73.87
(0.01)
Sinkhorn
99.61 (0.05)
87:4 (0.53)
99.87 (0.03)
92.60 (0.13)
94.30 (0.00)
36.94 (0.07)
68.75 (0.02)
34.92 (0.00)
SWD
99.56 (0.04)
87.63 (0.62)
99 36 (0.09)
90.12 (0.43)
94.52 (0.00)
39.38 (0.01)
75.13 (0.03)
38.11 (0.01)
N7.00 (0:
24 55 (0 39)
92: (0.23)
43.03 (0.55)
94.24 (0) 50)
83.15 (0.23)
95.00 (0: 75)
73 (0.37)
Flat
86.17 (0.26)
43.09 (0.55)
82.07
42.09 (0.26)
93.85 (0.20)
82,45 (0.27)
74.47 (0.52)
66.50
CIRAR100
FastET
86.96 (0.13)
44.29 (0.33)
BREEDS
(0.27)
(0.31)
92.84 (0.27)
79.69 (0.34)
EMD
86.93 (0.28)
44.03 (0.31)
91.82 (0.14)
42.32 (0.31)
Sinkhorn
86.93 (0. 10)
43.99 (0.37)
91 (0.31)
42.45 (0.19)
94.42 (0.21)
83.51 (0.30)
91 84 (0 42)
79 (0.38)
SWD
86.42 (0.26)
$3.35(00.7))
87.24 (0.29)
42.39 (0.30)
94.41 (0.25)
82.96 (0.17)
83.58 (0.60)
72.38 (0.43)
For OT methods, we have l class-conditioned clusters, resulting in O(k2) pairs of matrices as input for all OT methods. For each pair, the computation time of OT methods can range from linear to cubic with respect to For instance, each FastFT computation takes ((nd) as shown in Theorem 3.2, so the total computation time becomes O(k2nd). In general, the computation time for all OT methods can be expressed as O OT-time). Next, we elaborate on the "OT-time" term.
For EMD, the complexity is typically On log n) in the past literature (Cuturi 2013). which primarily focuses the influence of the number of samples However, in our setting, because d >> aim to emphasize the effect of d. In the time complexity expression for EMD, the Onn log n)) term arises from solving the linear programming problem, while the ((n)) term accounts for computing the objective function (P, D). Due to the sparse nature of the linear programming solution, there are only (n) non-zero values in P. Consequently, we compute O(n) d-dimensional pairwise distances in D. making the dot product computation require ((nd) in total. Therefore, the overall complexity of EMD is (nl(d= n² log.).
To get the approximated flow matrix, Sinkhorn CCuturi 2013) mainly depends on the iterative matrix scaling algorithm. For each I iteration, we normalize the row and column of a matrix of size O(n?). so the complexity for running this iterative algorithm is O(n² I). Unlike in EMD, the approximated flow matrix derived from Sinkhorn is not sparse. Therefore, the dot product of the objective function will now take O(ndd) in total. The total complexity of Sinkhorn is ( I)).
To obtain the approximated flow matrix, Sinkhorn (Cuturi 2013) relies on the iterative matrix scaling algorithm. During each of the / iterations, we normalize the rows and columns of matrix of size Onn²), resulting in a complexity of O for the iterative algorithm. Unlike EMD, the approximated flow matrix P derived from Sinkhorn is not sparse. Consequently, computing the dot product for the objective function requires O(n²d) d) in total. Therefore, the overall complexity of Sinkhorn is On (d + T)).
27

---

Published as a conference paper at ICLR 2025
Table 18: Fine level generalization performance for each BREEDS setting.
Dataset
Objective
sAcc
tAcc
sMAP
Flat
85.15 (0.30)
46.31 (0.31)
85,94 (0.18)
lz
85.74 (0.69)
47.50 (0.73)
74.07 (0.61)
L17
FastFT
85.21 (0.38)
46.47 (0.75)
74.46 (0.16)
Sinkhorn
85,80 (0.49)
48.37 (0.69)
70.50 (0.53)
SWD
85.88 (0.26)
47.50 (0.09)
86.65 (0.51)
Flat
79.76 (0.27)
36.06 (0.37)
70.75 (1.14)
&
80.58 (0.54)
37.08 (0.26)
55.51 (0.50)
N26
FastFT
80.78 (0.52)
36.69 (0.19)
58.87 (0.42)
Sinkhorn
81.74 (0.26)
38.16 (0.14)
57.54 (0.92)
SWD
81.79 (0.25)
37.71 (0.09)
76.03 (0.05)
Flat
84.37 (0.24)
56.04 (0.27)
74.04 (0.34)
l2
84.77 (0.18)
55.69 (0.37)
66.92 (0.16)
E13
FastFT
85.04 (0.15)
56.66 (0.44)
67.96 (0.64)
Sinkhorn
85.00 (0.15)
57.14 (0.40)
64.47 (0.20)
SWD
84.49 (0.18)
56.82 (0.12)
75.39 (0.54)
Flat
79.05 (0.23)
42.35 (0.57)
64.23 (0. 17)
79.54 (0.21)
43.51 (0.23)
54.92 (0.23)
E30
FastFT
79.29 (0.32)
43.16 (0.42)
54.49 (0.23)
Sinkhorn
79.40 (0.33)
43.82 (0.38)
53.66 (0.53)
SWD
79.42 (0.52)
43.28 (0.34)
66.87 (0.45)
Table 19: Coarse level generalization performance for each BREEDS setting.
Dataset
Objective
sAce
tAcc
SMAP
tMAP
f2 Flat
93.13 (0.62)
79.03 (0.29)
93.93 (0.54)
69.13 (0.42)
92.68 (0.39)
78.35 (0.37)
76.66 (0.26)
56.13 (0.36)
LJ7
FastFT
93.33 (0.26)
78.37 (0.47)
92.11 (0.23)
65.44 (0.24)
Sinkhorn
93.11 (0.20)
79.50 (0.43)
89.14 (0.36)
63.88 (0.32)
SWD
92.96 (0.41)
78.66 (0.26)
83.92 (0.38)
59.66 (0.21)
Eg
88.94 (0.42)
70.24 (0.50)
89.59 (0.26)
68.40 (0.52)
Flat
88.44 (0.12)
68.98 (0.41)
61.20 (1.01)
50.86 (0.16)
N26
FastFT
88.83 (0.75)
69.43 (0.42)
83.89 (0.40)
65.22 (0.75)
Sinkhorn
89.94 (0.35)
70.70 (0.41)
83.14 (0.78)
66.07 (0.85)
SWD
89.88 (0.34)
69.93 (0.04)
74.06 (0.57)
58.50 (0.48)
fg Flat
97.80 (0.04)
91.51 (0.01)
98.25 (0.04)
94.15 (0.09)
97.53 (0.12)
91.30 (0.16)
83.89 (0.13)
82.37 (0.31)
E13
FastFT
97.80 (0.01)
91.78 (0.13)
97.69 (0.13)
93.21 (0.10)
Sinkhorn
97.63 (0.02)
91.97 (0.14)
97.53 (0.23)
92.77 (0.18)
SWD
97.67 (0.13)
91.69 (0.06)
91.43 (0.72)
87.71 (0.16)
Eg
97.07 (0.10)
91.74 (0.10)
98.24 (0.14)
95.28 (0.24)
Flat
96.75 (0.18)
91.10 (0.15)
76.12 (0.66)
76.65 (0.74)
E30
FastFT
97.02 (0.07)
91.98 (0.23)
97.65 (0.32)
94.90 (0.26)
Sinkhorn
96.99 (0.25)
91.87 (0.22)
97.54 (0.31)
94.59 (0. 18)
SWD
97.12 (0.13)
91.55 (0.31)
84.89 (0.74)
83.66 (0.88)
For FT (Backurs et al, 2020). the most computationally expensive step is the tree construction
using the QuadTTee algorithm. Backurs et al. (2020) demonstrate that this tree can be built in
28

---

Published as a conference paper at ICLR 2025
(nd (og(d))), Once the tree is constructed, shown in Lemma 3.1 of Backurs al. (2020) FT requires ((n(d + (gg()))) to run the bottom-up algorithm and compute the objective function, which is less expensive than the tree construction. Thus, the total complexity of FT is (nd log(d)))
For Fast FlowTree, please refer to the proof of Thm.
For TWD, follow Algorithm in Yamada et al. (022). The first step is to construct tree. To save computation, instead of using Quad we leverage the same technique as in FastFT to use our augmented tree, making this step O(1). For each of the I iterations in supervised learning, need to compute all entries in the pairwise distance matrix D, which requires On)dd). Thus, even when the tree structure is known, the total complexity of TWD is (n?2dT).
Finally, we want to highlight that Fig evaluated with = 2, where we vary the number of samples in one source and one target distribution. In this scenario, although the theoretical computational complexities for lg and Fast FlowTrer are both ( we observe that & scales better in practice. This due to the effect of standard vectorization optimizations in common matrix operation packages, which leverage parallelism along the dimension of n.
1.1 COMPARISON TO OTHER HIERARCHICAL BASELINES
Fig 12 we compared OT-CPCC methods with other hierarchical objectives described in See G and report the Fine/Coarse Metric Avg., which averages all source/target classification and retrivval metrics. Based on CPCC, fine, and coarse metrics, we observe that OT-CPCC methods behave similarly to CCCCC exhibiting higher CPCC values and stronger performance on but lower fine metrics (though OT methods still outperform & on fine metrics, as shown in Tab In contrast, all other hierarchical baseline objectives perform more like flat cross-entropy methods, with the opposite trend-lower CPCC and coarse metrics but relatively higher fine metries. Additionally, we excluded Rank loss from the correlation plot on the right side of Fig 12, as Tab 20 Tab220ssugees suggests that Rank loss is not suitable for any of the downstream tasks used in our evaluation, making it an outlier compared to the other objectives.
metries,
R² 0.69
Objective
CPCC
Metrics Avg.
EMD Sinkhorn
X Soft
l
83.08
66-
FastFT
93.85
65
HXE
MTL
SWD
EMD
89.60
Quad
Sinkhorn
93.81
64
Flat
X
SWD
73.17
63
Sum
X GK X SHC
Flat
22.13
20
30
40
50
60
70
80
90
MTL
37.07
R = 0.43
Curr
22.70
HXE
SumLoss
27.48
Fine Metrics Avg.
Fat Quad MTL
Sumlass
Soft
HXE
22.65
Soft
50.90
Quad
24.01
SHC
30.68
GC
X
w/o CPCC
w/ CPCC
Fast
GC 21.88
Sindhorn
Rank 24.75
50
60
70
80
90
Test CPCC
Figure Left: Comparison of CPCC for hierarchical baselines on CIFAR100. Right: CPCC against coarse and fine metrics average. Rank is an outlier, so its value is removed from the visualization.
J IMPLEMENTATION DETAILS FOR SYNTHETIC DATASETS EXPERIMENTS
Computational Efficiency We measured the computation time for different OT methods across datasets varying sizes. This involved generating two random 228-dimensional datasets identical shape and recording the wall-clock time for single distance computation. This process repeated
29

---

Published as a conference paper at ICLR 2025
Table 20: Comparison of fine and coarse metries for Flat Rank Loss.
Fine Metries
Coarse Metries
Objective
SAce
tAce
sMAP
SÂcc
tAcc
sMAP
tMAP
Flat
80.53
28.44
86.47
86.17
43.09
82.07
42.09
Rank
77.89
20.48
74.39
83.41
39.25
46.60
24.31
10 times, and the average time was reported. For illustrative purposes, we fixed the number of projections at 10 for SWD, and the regularization parameter at 10 for Sinkhorn, the same in our experiment setting in T5
Approximation Error We evaluated the error of different OT approximation methods, along with the lg distance of the mean of two datasets, in approximating EMD. Two different distribution scenarios were considered:
Gaussian Distribution: Here, both distributions were created as Gaussian distributions with different means and 4, respectively) and the same standard deviation of
Gaussans Distribution: For this scenario, generated the dataset from Gaussian mixtures. One dataset combined Gaussian distributions with means of ( and 5, while the other merged Gaussian distributions with means of and 3, all of them with standard deviation of 1.
Other experiment settings were consistent with those detailed in the Computational Efficiency paragraph above.
K COMPARISON OF RUNTIME OF OT-CPCC ON REAL-WORLD DATASETS
Table 21: Comparison of the wall clock runtime of OT-methods on real datasets for training one epoch. The results averaged for three random seeds.
Dataset
Objective
Per Epoch (s)
Dataset
Objective
Per Epoch (s)
Flat
85.88 (3.69)
Flat
147.67 (4.54)
l FastFT
83.78 (9,80)
&
149.39 (1.24)
CIPARIO
85.21 (4.26)
INAT (b=1024)
FastFT
132.01 (3.24)
(b=128)
EMD
87.70 (2.43)
EMD
234.68 (4.40)
Sinkhorn
85.65 (4.15)
Sinkhorn
165.69 (4.60)
SWD
92.90 (4.65)
SWD
152.52 (8.90)
We include the wall clock times for training different CPCC methods using two distinct settings: CIFAR10 with batch size of 128 and model training from scratch, and INAT with a batch size of 1024 and model fine-tuning from an ImageNet checkpoint. Despite the differences in settings, we observe that FastFT consistently runs significantly faster than exact EMD computation and outperforms the other two approximation methods, SWD and Sinkhorn. This aligns with our theoretical analysis in Tab and observations on synthetic data in Fig. When comparing FastFT f,, we find that FastFT is not much slower, and in the case of INAT, iS even faster than &z. Thus, we can confidently conclude that our proposed method, especially FastFT, is scalable.
epoch in Tab 21
and
Similar to fg, one could argue for using another closed-form Wasserstein expression, the Bures- Wasserstein distance (as defined in Eq 7. in CPCC optimization. However, Bures depends on the covariance term of the source and target distributions, which requires at least O(nd²) computation. As shown in Tab I in fz, calculating the mean of class-conditionee cluster only requires ((dd), and other OT methods have a linear term in their time complexity. large batch size of 1024, is approximately 1024/100 v 10, assuming all classes of equal size. Using ResNet18 as the backbone, d 512, which is typically much larger than n. Therefore, the d? factor from computing the covariance matrix in Bures make it prohibitively expensive in our case.
CIFAR100, even with a
30

---

Published as a conference paper at ICLR 2025
Table 22: Comparison of the wall clock runtime of Bures-CPCC vs, OT-CPCC on real datasets for training one batch. The results are averaged for three random seeds.
Dataset
Objective
Per Batch (s)
l EMD
0.35 (0.18)
CIFAR100
1.94 (0. 12)
Bures
33.77 (4.73)
To verify this, we computed the running time for CIFAR100 (batch size = 128) for different methods in 22 considering one batch update. The results averaged three random seeds.
As observed in Tab 22 Bures- Wassersessn significantly slower than both f and EMD due to its quadratie dependence on d. Therefore, for scalability concerns, covariance-based Wasserstein metrics are not well-suited to our problem setup.
31


Reviews:
[{"review_id": "BRGaRlttHH", "reviewer": "Reviewer_1XYv", "summary": "The paper aims to improve classification by incorporating similarities among classes. These semantic relationships between labels are introduced into the original problem as a regularizer. The paper assumes a hierarchical structure in the labels. Building on the work of Zeng et al. (2022), the authors replace Euclidean distances between class means with optimal transport (OT) distances between label distributions. To reduce the computational burden of OT distance, they use a modified version of a tree-based method called FlowTree, which relies on a predefined tree structure. The paper also introduces a differentiable method for training with their tree-based OT distance. Experimental results for the classification problem using the OT-based regularization method show improvements compared to the method in Zeng et al. (2022). However, the proposed FastFT regularization falls behind the performance of some other OT-based methods.", "questions": "See  the Weakness section.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper employs optimal transport (OT) distance to measure the distributions of labels rather than relying solely on the distance between class means. By capturing distributional differences, this approach aims to provide a more nuanced measure of class similarity.\n\n- To address the high computational complexity typically associated with OT distance, the authors implement a tree-based approximation method. This approach enables more efficient computation while maintaining the benefits of OT-based similarity measures.\n\n- Experimental results demonstrate that accounting for the distributional nature of labels enhances performance in tasks such as classification and class representation learning. This distribution-based approach proves beneficial in capturing class relationships more effectively than mean-based methods.", "weaknesses": "- Theorem 3.2 appears to be a key contribution, as it establishes that Algorithms 1 and 2 can approximate the Earth Mover's Distance (EMD). However, the proof is vague and leaves several critical points open to interpretation. I found it challenging to follow the complete argument leading to the stated approximation result. Including a detailed proof sketch could greatly enhance clarity and strengthen the manuscript.\n\n- Similarly, while Lemma 3.4 provides the derivative of the EMD, the result itself is relatively straightforward. More importantly, it is unclear whether the same derivative result directly applies to FastTree. A formal proof confirming that this result holds for FastTree would significantly enhance the paper's contribution and rigor.\n\n- Another issue arises with the reliance on an assumed ground-truth tree structure. In most cases, this ideal tree is unknown or impractical to obtain, even if the underlying assumptions hold. As a result, multiple approximated trees may be used instead. The paper does not adequately address how gradient computations would handle these varied approximations, which is an important practical consideration.\n\n- Finally, a literature review on learning label representations, accompanied by illustrative examples, would provide valuable context and motivation for the study. This would help readers appreciate the importance of this approach within the broader scope of label representation learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qWWWQS5127", "reviewer": "Reviewer_rpnu", "summary": "The paper extends the work (Zeng et al. 2022) for learning structured representation by introducing the Earth Mover's Distance (EMD) to measure the pairwise distances among classes in embeddings. Moreover, a so-called Fast FlowTree algorithm is proposed to improve the computation efficiency, which is linear in the size of the dataset. Experiments show promising results.", "questions": "1. While different approximation methods can be used, it is not clear about the computation cost, compared to the baseline methods. \n \n2. In Table 3, the preciseness of hierachical information listed show that in most cases, the presented FastFT based method cannot beat the $\\ell_2$ norm based method. How to interprete the results in Table 3? \n\n3. Using AIC to estimate the number of modality of the classes sounds interesting.  Is there any more intuitive evidence to support the existence of multi-mode in feature distribution? Or,  whether the identified multi-mode classes could be visualized by e.g., t-SNE or UMAP?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ It extends the $\\ell_2$ norm based Cophenetic Correlation Coefficient (CPCC) (Zeng et al. 2022) to OT-CPCC by introducing EMD, which is essentially equivalent to assign different importance to each pair of data points when computing the gradients.\n+ It presents a linear time approximation algorithm to solve the OP problem for learning the hierachical representation.\n+ Extensive experiments are provided.", "weaknesses": "1.  To replace the $\\ell_2$ distance between two class-centroids, the EMD is introduced based on representing class label by all samples in the class. If the number of samples in each class is large, then solving a single EMD is expensive in time cost. Notice that the distances are computed for pairwise classes, thus the times to compute EMD is quadratic to the number of classes. If the number of classes is large, then it is extremely expensive to compute the EMD based hierarchy information among embeddings.  While different approximation methods can be used, it is not clear about the computation cost, compared to the baseline methods. \n \n2. In Table 3, the preciseness of hierachical information listed show that in most cases, the presented FastFT based method cannot beat the $\\ell_2$ norm based method. How to interprete the results in Table 3?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K3PfpVD0b7", "reviewer": "Reviewer_LYtZ", "summary": "This paper presents a method for learning structured representations by embedding class hierarchies using Optimal Transport (OT) in the Cophenetic Correlation Coefficient (CPCC) framework. Traditional methods use Euclidean distances between class means to represent hierarchical information, which can be inaccurate for multi-modal distributions. The authors propose using Earth Mover’s Distance (EMD) to address this limitation and introduce Fast FlowTree (FastFT), a computationally efficient OT approximation algorithm for CPCC that operates in linear time.", "questions": "see Weaknesses", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed algorithms are novel and scalable. The proposed method leads to performance improvements across multiple datasets. The work is impactful for applications needing hierarchical class embedding.", "weaknesses": "1. I feel section 3.3 can be simplified by moving some derivations and technical discussion to the appendix. \n2. Label embedding methods have been employed in extreme classification (see datasets: http://manikvarma.org/downloads/XC/XMLRepository.html). The authors may want to experiment on those datasets to verify scalability and compare to existing embedding methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hiz9zsO4Iq", "reviewer": "Reviewer_BGq8", "summary": "The paper addresses the challenge of embedding hierarchical structures in feature representations for supervised classification tasks. It builds upon existing work that uses the Cophenetic Correlation Coefficient (CPCC) to enforce hierarchical structure alignment but innovates by employing the Earth Mover’s Distance (EMD) within this framework. The authors also propose a new, efficient algorithm, Fast FlowTree (FastFT), to approximate EMD in linear time, making it feasible to apply OT-based regularization to large datasets.", "questions": "While the paper proposes FastFT for computational efficiency, can the authors provide a clear comparison of computation time on empirical datasets?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to follow.\n2. The paper makes a theoretical extension by generalizing CPCC with EMD, allowing the model to handle more complex, non-unimodal distributions that Euclidean-based methods struggle with. This extension is theoretically sound and shows how OT can capture nuanced hierarchical structures in data.", "weaknesses": "1. The improvement of FastFT and EMD, which appears to be the paper’s key contribution, is modest on empirical datasets, showing less than a 1% gain on average across three random seeds.\n2. The computation time for empirical datasets is not reported.\n3. The paper is a follow-up to the CPCC work by Zeng et al. (2022), with the addition of EMD. The novelty of introducing Fast FlowTree is somewhat limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WMpZfBRGHQ", "reviewer": "Reviewer_Tr4V", "summary": "This paper tackles the problem of structured knowledge embedding in supervised learning, i.e., how to enforce that representations encode structures in the label space. An example of structure in label space is when labels are hierarchical (e.g., dog -> husky, bulldog, etc). Previous work has considered comparing class-conditional distributions through the Euclidean distance of the mean of their samples. However, as the authors remark, this choice is restrictive as it does not really capture all the information of a distribution (e.g., multi-modality, covariances, etc). The authors propose using the EMD to compare these class-conditionals, improving the learning of representations.\n\n---\n\n__Post-Rebuttal__\n\nThe authors did a good job on the rebuttal, and addressed all of my concerns. I also praise the initiative of running further experiments with the Bures-Wasserstein metric, which proved to be too computationally heavy for the task at hand (since $d \\gg n$).\n\nOverall, this is a strong submission, so I decided to increase my score from __6. Marginally above the acceptance threshold__ to __8. Accept, good paper__.", "questions": "# Suggestions\n\n- In Sec. 2.2, I suggest the authors to comment more specifically on the complexity of OT and its variants. I get that this is somewhat done in Table 1, but I did not find any references to this table. I think a clear discussion on the text would be beneficial (and, of course, a reference to the table).\n\n- For better uniformity and clarity, the authors might want to change references to the EMD as a distance in favor of $2-$Wasserstein distance, which is what is actually used in the paper. For instance, in most tables the authors use EMD and terms involving the Wasserstein distance (TWD or SWD).\n\n- In section 3.3, when authors are comparing the gradients of $\\ell_{2}-$CPCC and OT-CPCC, I think the authors can make 2 further links, if they agree with the following discussion. First, the comparison of distributions' centroids can be understood as computing the MMD, with a linear kernel, between those distributions. This can further make the link with other probability metrics, and arguably, OT yields a richer geometry than this simplistic choice. Second, if one chooses to approximate OT through the Sinkhorn algorithm, letting the entropic regularization penalty $\\epsilon \\rightarrow +\\infty$ leads to the trivial coupling $P_{ij} = 1/nm$. In this case, OT-CPCC boils down to the $\\ell_{2}-$CPCC algorithm, modulo a scaling factor on the gradients. The authors can also cite (Feydy et al, 2019) which discusses these relations in depth.\n\n# Questions\n\nI have only one question, which I detail below.\n\nProposition 3.1 left me wondering if it would not be possible to run OT-CPCC with a parametric approximation of the classes through Gaussian measures. This way, instead of calculating EMD between classes, one would use the Bures-Wasserstein metric,\n\n$\\mathcal{W}_{2}(P,Q)^{2}  = \\lVert \\mu\\_{P} - \\mu\\_{Q} \\rVert\\_{2}^{2}  +  Tr(\\Sigma\\_{P} + \\Sigma\\_{Q} - 2(\\Sigma\\_{P}^{1/2}\\Sigma\\_{Q}\\Sigma\\_{P}^{1/2})^{1/2}).$\n\nWith this approach, you could trade the complexity with respect the number of samples to a complexity with respect number of dimensions, which may be desirable depending on the problem at hand. Some authors have used this in other contexts (e.g., (Alvarez-Melis and Fusi, 2020)).\n\nFurthermore, stressing the idea that class-conditionals are multi-modal, GMMs could be fit on these conditionals, then compute Mixture-Wasserstein (Delon and Desolneux, 2020) distances between the class-conditionals.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The ideia is good. OT makes a good contribution to the considered problem, especially concerning how distributions are compared and embedded in the tree structure.\n\n- The authors present a solid analysis of how to extend the $\\ell_{2}$-CPCC framework to OT, especially concerning differentiating through linear programming.\n\n- The authors' experiments show a solid improvement over previous framework under a variety of ways of computing Wasserstein distances.", "weaknesses": "- In Table 1 (Sec 2.2), I do not think that these complexities are straightforward to derive. Can the authors point to the reasoning to their derivation? For instance, EMD's complexity is tipically $\\mathcal{O}(n^{3}\\log n)$ instead of $\\mathcal{O}(n(d+n^{2}\\log n))$\n\n- While I got what the authors are trying to express with prop. 3.1, and the result is true if stated correctly, I think the authors could rephrase it for better clarity. First, \"$\\ell_{2}$ for Gaussians\" is not mathematically correct, since the $\\ell_{2}$ norm or distance is defined for vectors. The closest term to this expression would be an $L_{2}$ norm or distance between probability distributions, but it is not equivalent to the $\\ell_{2}$ distance between the means. I propose that the authors change the statement to \"EMD reduces to $\\ell_{2}$ distance between the means\". Other ways of rephrasing this are possible, see my suggestions and questions below. Likewise, an appropriate reference to (Takatsu, 2011) would be interesting.\n\n- In table 4, the objective \"Flat\" is not explained. From the overall context, I guess this corresponds to learning with no structure tree, but this is not clear to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)