# Learning Best Combination for Efficient N:M Sparsity

Yuxin Zhang1 Mingbao Lin2 Zhihang Lin1 Yiting Luo1
Ke Li2 Fei Chao1 Yongjian Wu2 Rongrong Ji1,3,4
1MAC Lab, School of Informatics, Xiamen University, Xiamen, China
2Tencent Youtu Lab, Shanghai, China
3Institute of Artificial Intelligence, Xiamen University, Xiamen China
4Pengcheng Lab, Shenzhen, China Corresponding author<EMAIL_ADDRESS>
###### Abstract

By forcing at most N out of M consecutive weights to be non-zero, the recent
N:M network sparsity has received increasing attention for its two attractive
advantages: 1) Promising performance at a high sparsity. 2) Significant
speedups on NVIDIA A100 GPUs. Recent studies require an expensive pre-training
phase or a heavy dense-gradient computation. In this paper, we show that the
N:M learning can be naturally characterized as a combinatorial problem that
searches for the best combination candidate within a finite collection.
Motivated by this characteristic, we solve N:M sparsity in an efficient
divide-and-conquer manner. First, we divide the weight vector into
$C_{\text{M}}^{\text{N}}$ combination subsets of a fixed size N. Then, we
conquer the combinatorial problem by assigning each combination a learnable
score that is jointly optimized with its associate weights. We prove that the
introduced scoring mechanism can well model the relative importance between
combination subsets. And by gradually removing low-scored subsets, N:M fine-
grained sparsity can be efficiently optimized during the normal training
phase. Comprehensive experiments demonstrate that our learning best
combination (LBC) performs consistently better than off-the-shelf N:M sparsity
methods across various networks. Our project is released at
https://github.com/zyxxmu/LBC.

##  1 Introduction

Recent years have witnessed the popularity of convolutional neural networks
(CNNs) in visual problems such as image classification [34, 12], object
detection [11, 8] and semantic segmentation [9, 3]. However, the remarkable
performance comes at the cost of huge computation burdens and memory
footprint, resulting in great challenges for deploying CNNs in resource-
limited devices. Model compression has received extensive attention from both
academia and industries. By reducing the number of parameters in CNNs, network
sparsity has become one of the most representative techniques to alleviate
storage and computation burdens. According to the sparsity granularity,
traditional methods can be divided into unstructured sparsity [18, 6, 10] and
structured sparsity [20, 29, 27]. As shown in Fig. 1(a), unstructured sparsity
removes arbitrary weights in CNNs. Dozens of earlier studies [23, 17, 7] have
demonstrated its ability to reach negligible performance degradation under a
large compression rate. Unfortunately, unstructured sparsity often results in
an irregular sparse matrix, which causes heavy index storage and very little
acceleration. On the contrary, structured sparsity removes all weights in a
filter as illustrated in Fig. 1 (b). As a result, the sparse weights are still
in a hardware-friendly format, leading to notable speedups. Nevertheless, the
removal of the whole filters also severely damages the accuracy performance.
Thus, future progress is expected to find out a new sparsity pattern to
tradeoff the performance and acceleration.

Figure 1: Mainstream sparsity granularity in the literature. (a) Unstructured
sparsity removes individual weights at arbitrary locations. (b) Structured
sparsity removes entire convolutional filters. (c) N:M sparsity (2:4 case)
requires at most N out of M consecutive weights to be non-zero.

More recently, the N:M fine-grained sparsity has shown a promising power for
the research community. As depicted in Fig. 1 (c), it divides the weights into
several blocks of size M. By preserving at most N out of M weights in each
block, it not only achieves a high sparsity rate but also retains a regular
sparse matrix structure for an effective acceleration supported by the NVIDIA
Ampere Sparse Tensor Core [33]. The pioneering ASP (apex’s automatic sparsity)
[30] preserves two largest-magnitude weights in every four-element block and
then re-trains the sparse network. However, the time-consuming re-training
prohibits the deployment of N:M sparsity in resource-constrained scenarios. To
avert the pre-training burden, Zhou  _et al._ [40] learned N:M sparsity from
scratch by leveraging the straight-through estimator (STE) [1] to approximate
the gradients of removed weights. Although an additional regularization is
proposed to alleviate the weight error accumulation, dense gradients are
required to be computed in each training iteration to update both the removed
and preserved weights. Consequently, a heavy training burden is unavoidable,
barricading the generalization of N:M sparsity to gradient and activation [2].
Thus, how to realize an efficient N:M sparsity remains unexplored.

In this paper, we propose to learn the best combination in order to reach an
efficient N:M sparsity (LBC). Our LBC is motivated by the fact that the N:M
learning can be modeled as a combinatorial problem which consists in finding,
among a finite collection of combinations, one that satisfies all the given
conditions. Considering a single block, the purpose of N:M sparsity is to
select N non-repeated elements as a combination from the M continuous weights.
Thus, N:M sparsity can be simplified as finding the best combination candidate
from a total of $C_{\text{M}}^{\text{N}}$ combinations on condition that the
training loss can be minimized on the observed dataset. Given this analysis,
our LBC solves the N:M sparsity from the perspective of combinatorial problems
in an efficient divide-and conquer manner. We first divide the weight block
into a collection of $C_{\text{M}}^{\text{N}}$ combinations with a fixed size
N. Then, our LBC aims to learn the best combination from this collection. This
is achieved by a learnable score variable, which, as we prove in Sec. 3.4, can
well tell the relative importance between different combinations. As results,
the best combination can be located by gradually removing the low-scored
combinations during a normal training process without the necessity of a
dense-gradient computation.

We perform extensive experiments to demonstrate the efficacy of our LBC. For
instance, our LBC achieves 77.2% top-1 accuracy for training a 2:4 sparse
ResNet-50 on ImageNet, which takes the leading position in comparison with
existing N:M sparsity methods [30, 40]. It is also worth mentioning that our
LBC even surpasses some unstructured state-of-the-art methods that fail to
achieve speedups. For example, under a sparsity rate of around 95%, our LBC
still achieves a top-1 accuracy of 71.8% with a 1:16 sparse pattern,
surpassing the recent competitor STR [17] by 1.2%.

##  2 Related Work

###  2.1 Network Sparsity

Network sparsity has become an active research topic ever since the last
decade [18, 10, 25]. Traditional methods can be roughly categorized into
unstructured sparsity and structured sparsity. The former category removes
individual weights at any position of the network. Prevailing studies remove
unimportant weights using heuristic criteria such as gradient [19], momentum
[6], and magnitude [10]. Recent advances implement unstructured sparsity in a
training adaptive manner. RigL [7] alternately removes and revives weights
according to their magnitudes and dense gradients. Ding  _et al._ [6]
gradually zeroed out the redundant weights by categorizing CNN weights into
two parts at each training iteration and updating them using different rules.
Despite the progress, the irregular sparse weight tensors rarely support
speedups on common hardware unless the sparse rate increases to 95% or even
higher [37, 33]. On the other hand, structured sparsity gains noticeable
speedups thanks to its coarse-grained removal of the entire filters. Two
issues are widely discussed in existing studies including the pruned network
structure and the filter importance measurement. Typical works solve the
former issue by rule-of-thumb designs [13, 5] or layer-wise sparse ratio
searching based on evolutionary algorithms [21, 24]. As for the second issue,
most works resort to devising a certain criterion to estimate the filter
importance including output activation [39], ranks of feature map [20],
geometric median of filters [14], _etc_.

###  2.2 N:M Sparsity

The N:M fine-grained sparsity [30, 40, 35] advocates N-out-of-M non-zero
sparse tensors in the input channel dimension. Supported by the NVIDIA Ampere
Core [33], N:M sparsity leads to attractive storage and computation
efficiency. For example, N:M sparsity can achieve 2$\times$ speedups on the
NVIDIA A100 GPU in the 2:4 case, while unstructured sparsity even decreases
the inference speed under a similar sparse rate. NVIDIA [30] follows a
traditional three-step pipeline to implement N:M sparsity, unfolded as pre-
training, pruning and fine-tuning. Pool  _et al._ [32] further leveraged
channel permutations to maximize the accuracy of N:M sparse networks. Sun  _et
al._ [35] proposed a layerwise fine-grained N:M scheme to achieve higher
accuracy than the uniform N:M sparsity. Recently, there are also efforts in
exploring the training efficiency of N:M fine-grained sparsity. Hubara  _et
al._ [15] devised transposable masks to accelerate the backward phase of N:M
sparsity training. Chmiel  _et al._ [2] further extended N:M sparsity to
activation, which further boosts the training efficiency. Despite the well-
retained performance [30], the expensive pre-training process still hinders
the deployment of N:M sparsity. Sparse-refined straight-through estimator (SR-
STE) [40] learns the N:M sparsity from scratch. Detailedly, the removed
weights are also revived during the backward phase using the straight-through
estimator [1] and a specially-designed sparse penalty item. Therefore, by
choosing N-out-of-M weights with the largest magnitudes in each forward
propagation, the N:M sparsity can be obtained in a dynamic and end-to-end
training manner. However, it requires dense gradients in order to revive the
weights, thus can not be combined with these studies on training efficiency
[15, 2].

##  3 Methodology

###  3.1 Preliminaries

Denoting the parameters of an L-layer convolutional network as
$\mathbf{W}=\\{\mathbf{W}^{0},\mathbf{W}^{1},...,\mathbf{W}^{\text{L}}\\}$
where $\mathbf{W}^{l}$ is a $\text{K}^{l}$-dimension vector111Batch norm
layers and bias items are omitted here for simplicity., N:M fine-grained
sparsity divides parameters in each layer into groups along the input channel
dimension, leading to each group containing M consecutive weights. It saves
computation and retains performance by requiring at most N out of M
consecutive parameters to be non-zero values. To this end, the
$\mathbf{W}^{l}$ is firstly divided into
$\text{G}^{l}=\frac{\text{K}^{l}}{\text{M}}$ groups. For ease of the following
representation, we reorganize $\mathbf{W}^{l}$ as
$\mathbf{W}^{l}\in\mathbb{R}^{\text{G}^{l}\times\text{M}}$. And then, the
optimization of N:M sparsity can be formulated as:

$\min_{\mathbf{W}}\mathcal{L}(\mathbf{W};\;\mathcal{D})\;\;\;\emph{s.t.}\;\;\;{\|\mathbf{W}^{l}_{g,:}\|}_{0}=\text{N},$
(1)

where $l=1,2,...,\text{L}$ and $g=1,2,...,\text{G}^{l}$. The
$\mathcal{L}(\cdot)$ denotes training loss function and $\mathcal{D}$
represents the observed dataset. An illustrative case of 2:4 sparsity is given
in Fig. 1(c).

Previous N:M methods [30, 40] follow the traditional unstructured sparsity
[10] to remove weights in a global manner by looking at the weight magnitude.
However, they all require huge training costs either from a pre-training phase
[30] or dense-gradient calculation [40] to select the most important weights
from the large number of parameters in deep networks. Hence, how to achieve
N:M sparsity in a more efficient manner remains an open issue so far.

###  3.2 Combinatorial Problem in N:M Sparsity

Fortunately, by making full use of the intrinsic particularity in N:M
sparsity, the solution space can be well reduced to pursue an efficient N:M
sparsity. Concretely, given a weight group $\mathbf{W}^{l}_{g,:}$, the target
of N:M sparsity is to select N out of the M weights in
$\mathbf{W}^{l}_{g,:}\in\mathbb{R}^{\text{M}}$ and discard the remaining M$-$N
ones. This leads to a combination collection
$\Theta^{l}_{g}=\\{\Theta_{g,i}^{l}\\}_{i=1}^{C_{\text{M}}^{\text{N}}}$ where
each combination $\Theta^{l}_{g,i}$ is a subset of $\mathbf{W}^{l}_{g,:}$ and
consists of N non-repeated elements from $\mathbf{W}^{l}_{g,:}$. It is
intuitive to derive the collection size
$|\Theta^{l}_{g}|=C_{\text{M}}^{\text{N}}$. As a toy example, we have
$C_{4}^{2}=6$ considering the 2:4 case. Also, we have:

$\displaystyle\Theta^{l}_{g}=$
$\displaystyle\big{\\{}\underbrace{\\{\mathbf{W}^{l}_{g,0},\mathbf{W}^{l}_{g,1}\\}}_{\Theta^{l}_{g,1}},\underbrace{\\{\\{\mathbf{W}^{l}_{g,0},\mathbf{W}^{l}_{g,2}\\}}_{\Theta^{l}_{g,2}},\underbrace{\\{\mathbf{W}^{l}_{g,0},\mathbf{W}^{l}_{g,3}\\}}_{\Theta^{l}_{g,3}},\underbrace{\\{\mathbf{W}^{l}_{g,1},\mathbf{W}^{l}_{g,2}\\}}_{\Theta^{l}_{g,4}},\underbrace{\\{\mathbf{W}^{l}_{g,1},\mathbf{W}^{l}_{g,3}\\}}_{\Theta^{l}_{g,5}},\underbrace{\\{\mathbf{W}^{l}_{g,2},\mathbf{W}^{l}_{g,3}\\}}_{\Theta^{l}_{g,6}}\big{\\}}.$
(2)

According to the above analyses, we realize that the N:M sparsity can be
naturally characterized as a combinatorial problem, which aims to, given a
finite collection of combinations $\Theta^{l}_{g}$, search for the best
candidate within this collection. Herein, we reformulate the realization of
N:M sparsity from the perspective of a combinatorial problem as:

$\mathop{\arg\min}\limits_{\Theta_{g,i}\in\mathbf{W}^{l}_{g,:}}\mathcal{L}(\mathbf{W}^{l}_{g,:};\;\mathcal{D}),\,\,s.t.\,\,|\Theta_{g,i}|=\text{N}$
(3)

where $l=1,2,...,\text{L}$, $g=1,2,...,\text{G}^{l}$ and
$i=1,2,...,C_{\text{M}}^{\text{N}}$.

Discussions. Eq. (1) implements N:M sparsity by globally sparsifying a weight
vector $W^{l}_{g,:}$. In contrast to earlier implementations, our redefined
Eq. (3) solves N:M sparsity in a divide-and-conquer manner. We first divide
the weight vector into $C_{\text{M}}^{\text{N}}$ subsets of a fixed size N.
Then, we conquer the combinatorial problem by scoring each subset and finally
picking up the highest-scored one, details of which are given in the following
contents.

Figure 2: The training process for learning the best combination candidate of
N:M sparsity (2:4 case).

###  3.3 Learning Best Combination

Based on the above analyses, we further propose to learn the best combination
for each weight vector $\mathbf{W}^{l}_{g,:}$. Following [40], we consider
learning the N:M sparsity from scratch to avoid the heavy dependency on an
expensive pre-trained model. A learning example of the 2:4 case is shown in
Fig. 2. Specifically, denoting the input feature map of the $l$-th convolution
layer as $\mathbf{Z}^{l-1}$, the output feature map $\mathbf{Z}^{l}$ is
calculated as:

$\mathbf{Z}^{l}=\mathbf{Z}^{l-1}\otimes\mathbf{W}^{l},$ (4)

where $\otimes$ denotes the convolutional operation. The earlier study [40]
chooses to zero out low-magnitude N weights for every weight vector
$\mathbf{W}^{l}_{g,:}$ in the forward propagation. The straight-through
estimator (STE) is used to dynamically remove and revive weights, which
however leads to error accumulation on the weights. Besides, dense-gradient
computation is of heavy cost since both removed and preserved weights are
required to update. Given the combinatorial property, we are entitled to the
opportunity to reach N:M sparsity by gradually removing the low-scored
candidate subsets in the combination collection $\Theta^{l}_{g}$ during the
training procedure until the one with the smallest loss can be found. The
gradual sparsity is demonstrated to perform better in many traditional network
sparsity [42, 41, 23]. To that effect, we consider the gradual pruning
schedule [42] to remove candidate subsets considered unimportant, and the
remaining collection at the $t$-th training epoch is:

$\displaystyle\Theta^{l}_{g,t}=\Theta^{l}_{g,t-1}-\bar{\Theta}^{l}_{g,t},$ (5)

where $\bar{\Theta}^{l}_{g,t}\in\Theta^{l}_{g,t-1}$ contains unimportant
candidates at the $t$-th training epoch and its size is:

$|\bar{\Theta}^{l}_{g,t}|=\left\\{\begin{array}[]{ll}0,\;\textrm{if $t$ =
$t_{i}$,}\\\
\Big{\lceil}(C_{\text{M}}^{\text{N}}-1)\big{(}1-(1-\frac{t-t_{i}}{t_{f}-t_{i}})^{3}\big{)}\Big{\rceil}-|\bar{\Theta}^{l}_{g,t-1}|,\;\textrm{otherwise,}\end{array}\right.$
(6)

where $t\in[t_{i},t_{f}]$, $t_{i}$ and $t_{f}$ denote the beginning and ending
of the training epochs in the gradual pruning schedule [42]. When $t=t_{f}$,
we remove a total of $C_{\text{M}}^{\text{N}}-1$ candidate subsets. In other
words, only one combination, which is considered to be the best candidate, is
preserved in the end.

To measure the candidate’s importance, we invent a learnable score matrix
$\mathbf{S}^{l}\in\mathbb{R}^{\text{G}^{l}\times C^{\text{N}}_{\text{M}}}$. In
our design, each element $\mathbf{S}^{l}_{g,i}$ reflects relative importance
of candidate ${\Theta}^{l}_{g,i}$ in comparison to others in $\Theta_{g}^{l}$
and we reduce the size of collection $\Theta_{g}^{l}$ by removing the low-
scored candidates. In the forward propagation, an individual weight
$\mathbf{W}^{l}_{g,i}$ often exists in multiple candidate subsets as shown in
Eq. (2). We impose a binary mask
$\mathbf{B}^{l}\in\\{0,1\\}^{\text{G}^{l}\times\text{M}}$ upon the weight
$\mathbf{W}^{l}$ and the output in Eq. (4) becomes:

$\mathbf{Z}^{l}=\mathbf{Z}^{l-1}\otimes(\mathbf{B}^{l}\odot\mathbf{W}^{l}),$
(7)

where $\odot$ represents the element-wise multiplication. The zero elements in
$\mathbf{B}^{l}$ indicate the removal of corresponding weights that contribute
least to the network. The binary mask $\mathbf{B}^{l}$ is derived as:

$\mathbf{B}^{l}_{g,i}=\mathbb{I}\Big{(}\big{(}\sum_{j}\mathbf{S}_{g,j}^{l}\cdot\mathbb{I}(\mathbf{W}^{l}_{g,i}\in\Theta^{l}_{g,j})\big{)}\neq
0\Big{)},$ (8)

where $\mathbb{I}(\cdot)$ returns 1 if its input is true, and 0 otherwise.
That is to say, we choose to preserve weights within any preserved candidate
subset. Note that if $\mathbf{W}^{l}_{g,i}$ does not exist in any preserved
candidate subset, it will be automatically removed since
$\mathbf{B}^{l}_{g,i}=0$ according to Eq. (8).

The use of a binary mask originated from many traditional unstructured
sparsity methods [7, 16]. However, to our best knowledge, it is the first time
to be introduced in N:M sparsity. Moreover, very different from these studies
that directly optimize the binary mask, our mask is obtained according to the
candidate subsets the corresponding weight falls into. Finally, since the
derivative of the $\mathbb{I}(\cdot)$ function is zero almost everywhere, we
adopt the STE [1] to update $\mathbf{S}^{l}_{g,j}$ as:

$\frac{\partial\mathcal{L}}{\partial\mathbf{S}^{l}_{g,j}}=\frac{\partial\mathcal{L}}{\partial\mathbf{B}^{l}_{g,i}}\frac{\partial\mathbf{B}^{l}_{g,i}}{\partial\mathbf{S}^{l}_{g,j}}\;\approx\frac{\partial\mathcal{L}}{\partial\mathbf{B}^{l}_{g,i}}.$
(9)

Consequently, the STE approximation of weight gradient [40] becomes the
approximation of the gradient of the introduced score matrix, avoiding the
error accumulation on the weights. Intuitively, removing $\mathbf{S}$ does not
influence the result of Eq. (8) in the forward propagation. However, our
motive of retaining $\mathbf{S}$ is actually to derive the gradient in the
backward propagation, _i.e._ , Eq. (9) to learn the importance of each
combination. In Sec. 3.4, we formally prove that the learned score
$\mathbf{S}$ can well reflect the relative importance between different
candidate subsets. Further, we conduct experiments in Sec. 4.4 to show that
the learned score $\mathbf{S}$ well outperforms existing pruning criteria [10,
28].

Our learning the best candidate, dubbed as LBC, is outlined in Alg. 1.
Different from traditional methods [39, 26] that conduct network sparsity in a
two-step manner including a mask learning and a weight tuning, LBC enables the
optimization of $\mathbf{W}$ and $\mathbf{S}$ in a joint framework, leading to
a well-optimized N:M sparsity during a normal training phase. It is worthy to
highlight the efficiency of LBC since it casts off the dense gradient
calculation in [40]. Also, LBC can cooperate with techniques that extend N:M
sparsity to gradient and activation to further boost the training efficiency
[2, 15].

Require : Observed data $\mathcal{D}$; Randomly initialized weights
$\mathbf{W}$; Loss function $\mathcal{L}$; Training epochs T; Initial and
final epoch for removing combinations $t_{i},t_{f}$; Candidate collection
$\Theta$.

Output : Trained weights $\mathbf{W}$; Binary mask $\mathbf{B}$.

$\mathbf{S}^{l}_{g,i}$ $\leftarrow$ 1 $\forall l,\forall g,\forall i$; //
Learnable Importance Score

1 for  _$t\in[1,\dots,T]$_ do

2 if  _$|\Theta^{l}_{g,t}|$ $\neq$ $1$_ then

3 Calculate $|\bar{\Theta}^{l}_{g,t}|$ via Eq. (6);

4 for  _$l\in[1,\dots,L]$_ do

5 for  _$g\in[1,\dots,G^{l}]$_ do

6 $\bar{\Theta}^{l}_{g,t}$ = Top-$|\bar{\Theta}^{l}_{g,t}|$ smallest
$\mathbf{S}^{l}_{g}$ in $\Theta^{l}_{g,t-1}$;

$\Theta^{l}_{g,t}$ = $\Theta^{l}_{g,t-1}$ $-$ $\bar{\Theta}^{l}_{g,t}$; //
Remove Unimportant Candidate Subsets

7

8 end for

9

10 end for

11 Get $\mathbf{B}$ via Eq. (8);

12

13 end if

14 Forward via Eq. (7);

15 Update via the SGD optimizer.

16

17 end for

Algorithm 1 Learning Best Candidate (LBC).

###  3.4 Tractability of Optimization

We take the candidate $(\mathbf{W}^{l}_{g,0},\mathbf{W}^{l}_{g,1})$ in 2:4
sparsity of Eq. (2) to show that our introduced mask score can well reflect
the relative importance of each candidate subset. The analysis can be applied
to other N:M patterns as well. The gradient of $\mathbf{\mathbf{S}}^{l}_{g,1}$
is derived using STE [1] as:

$\begin{split}\frac{\partial\mathcal{L}}{\partial\mathbf{S}^{l}_{g,1}}\hskip
2.84526pt=\hskip
2.84526pt&\frac{\partial\mathcal{L}}{\partial\mathbf{B}^{l}_{g,0}}\frac{\partial\mathbf{B}^{l}_{g,0}}{\partial\mathbf{S}^{l}_{g,1}}+\frac{\partial\mathcal{L}}{\partial\mathbf{B}^{l}_{g,1}}\frac{\partial\mathbf{B}^{l}_{g,1}}{\partial\mathbf{S}^{l}_{g,1}}\\\
=\hskip
2.84526pt&\mathbf{W}^{l}_{g,0}\frac{\partial\mathcal{L}}{\partial\mathbf{W}^{l}_{g,0}}\frac{\partial\mathbf{B}^{l}_{g,0}}{\partial\mathbf{S}^{l}_{g,1}}+\mathbf{W}^{l}_{g,1}\frac{\partial\mathcal{L}}{\partial\mathbf{W}^{l}_{g,1}}\frac{\partial\mathbf{B}^{l}_{g,1}}{\partial\mathbf{S}^{l}_{g,1}}\\\
\approx&\mathbf{W}^{l}_{g,0}\frac{\partial\mathcal{L}}{\partial\mathbf{W}^{l}_{g,0}}+\mathbf{W}^{l}_{g,1}\frac{\partial\mathcal{L}}{\partial\mathbf{W}^{l}_{g,1}},\end{split}$
(10)

where
$\mathbf{W}^{l}_{g,0}\frac{\partial\mathcal{L}}{\partial\mathbf{W}^{l}_{g,0}}$
meets the criterion [28] that estimates the loss changes after removing
$\mathbf{W}^{l}_{g,0}$ as:

$\begin{split}\Delta\mathcal{L}(\mathbf{W}^{l}_{g,0})\hskip 2.84526pt&=\hskip
2.84526pt\mathcal{L}(\mathbf{W}^{l}_{g,0}=0)-\mathcal{L}(\mathbf{W}^{l}_{g,0})\\\
&\hskip
2.84526pt\approx\mathcal{L}(\mathbf{W}^{l}_{g,0})-\mathbf{W}^{l}_{g,0}\frac{\partial\mathcal{L}}{\partial(\mathbf{W}^{l}_{g,0}=0)}+R_{1}(\mathbf{W}^{l}_{g,0}=0)-\mathcal{L}(\mathbf{W}^{l}_{g,0})\\\
&\hskip
2.84526pt\approx-\mathbf{W}^{l}_{g,0}\frac{\partial\mathcal{L}}{\mathbf{W}^{l}_{g,0}},\end{split}$
(11)

which leads Eq. (10) to
$\frac{\partial\mathcal{L}}{\partial\mathbf{S}^{l}_{g,1}}=\hskip
2.84526pt-(\Delta\mathcal{L}(\mathbf{W}^{l}_{g,0})+\Delta\mathcal{L}(\mathbf{W}^{l}_{g,1}))$.
The updating rule of $\mathbf{S}^{l}_{g,j}$ using stochastic gradient descent
(SGD) becomes:

$\mathbf{S}^{l}_{g,1}\hskip 2.84526pt=\hskip
2.84526pt\mathbf{S}^{l}_{g,1}+(\Delta\mathcal{L}(\mathbf{W}^{l}_{g,0})+\Delta\mathcal{L}(\mathbf{W}^{l}_{g,1})),$
(12)

where learning rate and momentum are ignored here for simplicity. The
candidate score $\textbf{S}^{l}_{g,1}$ is the accumulation of loss change for
removing weights in the corresponding candidate. A small score denotes less
loss increase thus the corresponding candidate can be safely removed. Thus,
our introduced score matrix can be used to measure the relative importance
between candidate subsets, and preserving the highest-scored combination well
solves the combinatorial problem of Eq. (3).

Table 1: Results of different methods for training the N:M sparse ResNet-18, ResNet-50 and DeiT-small on ImageNet. * implies our reproduced results. Model | Method | N:M | Top-1 | Epochs | FLOPs
---|---|---|---|---|---
|  | Pattern | Accuracy (%) | (Train) | (Train)
ResNet-18 | Baseline | - | 70.9 | 120 |  1$\times$(1.4e18)
ResNet-18 | ASP | 2:4 | 69.9 | 200 |  1.24$\times$
ResNet-18 | SR-STE | 2:4 | 71.2 | 120 |  0.83$\times$
ResNet-18 | LBC | 2:4 | 71.5 | 120 | 0.70$\times$
ResNet-50 | Baseline | - | 77.1 | 120 |  1$\times$(3.2e18)
ResNet-50 | ASP | 2:4 | 76.8 | 200 |  1.24$\times$
ResNet-50 | SR-STE | 2:4 | 77.0 | 120 |  0.83$\times$
ResNet-50 | LBC | 2:4 | 77.2 | 120 | 0.72$\times$
ResNet-50 | SR-STE | 1:4 | 75.3 | 120 |  0.74$\times$
ResNet-50 | LBC | 1:4 | 75.9 | 120 | 0.51$\times$
ResNet-50 | SR-STE | 2:8 | 76.2 | 120 |  0.74$\times$
ResNet-50 | LBC | 2:8 | 76.5 | 120 | 0.53$\times$
ResNet-50 | SR-STE | 1:16 | 71.5 | 120 |  0.69$\times$
ResNet-50 | LBC | 1:16 | 71.8 | 120 | 0.38$\times$
DeiT-small | Baseline | - | 79.8 | 300 |  1$\times$(8.9e18)
DeiT-small | SR-STE* | 2:4 | 79.6 | 300 |  0.83$\times$
DeiT-small | LBC | 2:4 | 80.1 | 300 | 0.71$\times$

##  4 Experiments

###  4.1 Experiment Settings and Implementation Details

Our proposed LBC is evaluated on three computer vision tasks including image
classification, object detection, and instance segmentation. We implement LBC
using the PyTorch [31] upon 2 NVIDIA Tesla A100 GPUs. Following Zhou  _et al._
[40], we train the ResNets for 120 epochs with an initial learning rate of 0,
which is linearly increased to 0.1 during the first 5 epochs and then decayed
to 0 scheduled by the cosine annealing. The SGD is adopted to update
parameters with the weight decay and momentum setting as 0.0005 and 0.9.
Besides, we adopt the Timm framework [38] to train DeiT with 300 epochs. To
implement LBC, we set $t_{i}$ to 0 and $t_{f}$ to 1/2 of the total training
epochs. Top-1 classification accuracy, training epochs and training FLOPs are
reported.

In Sec. 4.2, we compare our LBC with existing N:M sparsity methods including
ASP [33] and SR-STE [40] under different N:M patterns. In Sec. 4.3, we further
show the performance of LBC and traditional unstructured sparsity methods
including RigL [7], GMP [42], and STR [17] under similar total compression
rates. We give performance analyses of LBC _w.r.t._ its components in Sec.
4.4.

###  4.2 Comparison with N:M sparsity methods

Image classification. We first apply our LBC to train N:M sparse ResNet [12]
and DeiT [36] on ImageNet [4]. Tab. 1 shows that the proposed LBC takes the
lead in all N:M patterns with even less training burden for sparsifying ResNet
with depth of 18 and 50. For ResNet-18, LBC outperforms SR-STE [40] at 2:4
pattern at the Top-1 classification accuracy by 0.3% (71.2% for SR-STE and
71.5% for LBC). For ResNet-50, LBC again demonstrates its superiority against
both ASP [30] and SR-STE for all sparse patterns. Specifically, ASP achieves a
Top-1 accuracy of 76.8% for training 2:4 sparse ResNet-50 using 200 training
epochs that contain pre-training and fine-tuning phase, while LBC obtains a
significantly higher accuracy of 77.2% with a fewer epoch of 120. When it
comes to 1:4 sparse case, LBC surpasses SR-STE [40] by a large margin (75.9%
_v.s._ 75.3% in Top-1 accuracy and 0.49$\times$ _v.s._ 0.74$\times$ in
training FLOPs). Although SR-STE also alleviates the pre-training process, the
dense backward propagation greatly decreases its training efficiency in
comparison with LBC. From Fig.6 (a), LBC is still advantageous in all aspects
when compared with SR-STE in the 1:4 case.

Figure 3: (a) Comparison results under different N:M pattern for sparsifying
ResNet-50. (b) Top-1 accuracy _v.s._ training FLOPs for SR-STE and our
proposed LBC at 1:4 case.

Table 2: Results on object detection. Model | Method | N:M Pattern |  mAP.
---|---|---|---
F-RCNN | Baseline | - | 37.4
F-RCNN | SR-STE | 2:4 | 38.2
F-RCNN | LBC | 2:4 | 38.5
F-RCNN | SR-STE | 2:8 | 37.2
F-RCNN | LBC | 2:8 | 37.3

Table 3: Results on instance segmentation. Model | Method | N:M Pattern | Box mAP | Mask mAP
---|---|---|---|---
M-RCNN | Baseline | - | 38.2 | 34.7
M-RCNN | SR-STE | 2:4 | 39.0 | 35.3
M-RCNN | LBC | 2:4 | 39.3 | 35.4
M-RCNN | SR-STE | 2:8 | 37.6 | 33.9
M-RCNN | LBC | 2:8 | 37.8 | 34.0

We further conduct experiments on the recent advanced Vision Transformer (ViT)
model DeiT [36] to validate the efficacy of LBC. Similar to the strategy for
compressing CNNs, we divide all parameters including the multi-head attention
and feed-forward module in DeiT-small and train the N:M sparse networks from
scratch. Tab. 1 shows the results of LBC and our re-produced SR-STE for
training 2:4 sparse DeiT on ImageNet. As can be seen, LBC again surpasses SR-
STE by a noticeable margin of 0.5% (80.1% for LBC and 79.6% for SR-STE) using
fewer training FLOPs (0.71$\times$ for LBC and 0.83$\times$ for SR-STE).
Therefore, the ability of LBC is well validated for compressing ViT models.

Object detection and instance segmentation. Next, we exploit the efficacy of
LBC on object detection and instance segmentation. Tab. 3 and Tab. 3
respectively display the comparison results of LBC against SR-STE [40] for
training 2:4 sparse Faster-RCNN [8] and Mask-RCNN [11] with the backbone of
ResNet-50 on the COCO benchmark [22]. The results further demonstrate the
robustness and superiority of LBC on other computer vision tasks.

###  4.3 Comparison with unstructured sparsity methods

We also compare the performance of LBC with state-of-the-art unstructured
sparsity methods in Tab. 4. By training 1:16 sparse ResNet-50 on ImageNet, LBC
achieves a Top-1 accuracy of 71.8%, with 1.4% and 1.2% improvements over STR
and GMP, respectively. Furthermore, the compressed models generated by
unstructured sparsity remain an irregular format, which brings great
challenges for the real-application deployment. Nevertheless, under a similar
sparse rate, our LBC achieves practical compression and acceleration thanks to
the NVIDIA Ampere Core while still bringing higher accuracy performance, which
validates the advantages of exploring N:M sparsity.

Table 4: Results of the N:M and unstructured sparsity methods for sparsifying ResNet-50. Method | Top-1 | Sparsity | Params | FLOPs | Structured
---|---|---|---|---|---
| Accuracy (%) | (%) | (Test) | (Test) |
Baseline | 77.3 | 0.0 | 25.6M | 4.10G | ✓
DNW | 68.3 | 95 | 1.28M | 0.20G | ✗
RigL | 70.0 | 95 | 1.28M | 0.49G | ✗
GMP | 70.6 | 95 | 1.28M | 0.20G | ✗
STR | 70.4 | 95 | 1.27M | 0.16G | ✗
SR-STE | 71.5 | 94 (1:16) | 3.52M | 0.44G | ✓
LBC | 71.8 | 94 (1:16) | 3.52M | 0.44G | ✓

###  4.4 Performance analyses

Table 5: Experimental results for SR-STE and LBC at the same gradual sparsity schedule.  Method | $t_{i}$ | $t_{f}$ | Top-1 | FLOPs
---|---|---|---|---
|  |  | Accuracy (%) | (Train)
SR-STE | 0 | 0 | 75.3 |  0.74$\times$
LBC | 0 | 0 | 75.2 |  0.48$\times$
SR-STE | 0 | 30 | 75.5 |  0.76$\times$
LBC | 0 | 30 | 75.4 |  0.49$\times$
SR-STE | 0 | 60 | 75.3 |  0.78$\times$
LBC | 0 | 60 | 75.9 |  0.51$\times$
SR-STE | 30 | 60 | 75.6 |  0.87$\times$
LBC | 30 | 60 | 76.0 |  0.54$\times$

Table 6: Experimental results for different criteria to train N:M sparse ResNet-50. Method | N:M | Top-1
---|---|---
| Pattern | Accuracy (%)
Baseline | - | 77.3
Magnitude | 2:4 | 75.8
Gradient | 2:4 | 76.1
$\mathbf{S}$-inverse | 2:4 | 72.9
$\mathbf{S}$ (LBC) | 2:4 | 77.2

Training efficiency. In this part, we investigate the property of LBC for
improving the N:M sparse training efficiency. All the experimental results are
conducted on ImageNet by training 1:4 sparse ResNet-50. We first point out
that the total training FLOPs of LBC are proportional to the initial epoch
$t_{i}$ and final epoch $t_{f}$. To explain, larger $t_{i}$ and $t_{f}$
indicate a more smooth curve for removing combinations and more weights can be
sufficiently trained before the epoch reaches $t_{f}$. For a fair comparison,
we also apply the same gradual sparsity schedule to SR-STE [40]. As
illustrated in Tab. 6, more training FLOPs consistently improve the
performance of LBC as the importance score can be jointly trained with weights
more sufficiently. Fig. 3(b) further shows that our LBC takes the lead in the
trade-off between training cost and Top-1 accuracy performance when compared
with SR-STE [30, 40]. It is worthwhile to note that, by selecting different
$t_{i}$ and $t_{f}$, LBC can provide a satisfying solution between training
expenditure and performance under different resource constraints. Thus, the
efficiency and applicability of LBC are significant.

Combination Score. To investigate our combination score S, we introduce three
other criteria including 1) inversely sorted learned score S, 2) the
magnitude-based criterion [10], and 3) the gradient-based criterion [28] under
the same experiment settings for sparsifying ResNet-50 on ImageNet. Results in
Tab. 6 show that the proposed learnable score significantly outranks other
criteria. Thus, the efficacy of LBC for recommending best weight combinations
is well demonstrated.

##  5 Limitation

Firstly, LBC still needs relatively dense computation in the early stage of
N:M training as there are still plenty of left candidate subsets. Thus,
despite the advantages over approaches that rely on pre-trained models or
dense-gradient calculation over the entire training phase, there are still
room for improving the efficiency of LBC. Secondly, this paper only explores
N:M sparsity on computer vision tasks. We expect to show more results on other
tasks such as natural language processing (NLP) in our future work. Finally,
we mainly focus on N:M sparsity on weights, while adding N:M sparsity for
gradient [15] and activation [2] in the workflow of LBC remains to be
excavated in the near future.

##  6 Conclusion

N:M fine-grained sparsity is an important technique that allows fast inference
and training on the next-generation hardware and platforms. In this paper, we
have presented LBC towards efficient N:M sparsity from scratch. We first
transfer the N:M learning into a combinatorial problem, which motivates us to
select the best weights combination from $C_{M}^{N}$ candidates. Further, we
propose to assign learnable importance scores for each combination, which is
jointly optimized with the associate weights. We perform an in-depth analysis
that the best combination can be identified by aggressively removing less
important combinations. Extensive experiments have demonstrated the efficacy
of LBC in reducing the N:M training cost, and its superiority over several
SOTAs. Our LBC is characterized by end-to-end implementation, efficient
training, the tractability of optimization, and state-of-the-art performance
in sparsifying modern networks.

## Acknowledgement

This work is supported by the National Science Fund for Distinguished Young
(No.62025603), the National Natural Science Foundation of China (No.62025603,
No. U1705262, No. 62072386, No. 62072387, No. 62072389, No, 62002305,
No.61772443, No. 61802324 and No. 61702136) and Guangdong Basic and Applied
Basic Research Foundation (No.2019B1515120049).

## References

  * [1] Yoshua Bengio, Nicholas Léonard, and Aaron Courville.  Estimating or propagating gradients through stochastic neurons for conditional computation.  arXiv preprint arXiv:1308.3432, 2013.
  * [2] Brian Chmiel, Itay Hubara, Ron Banner, and Daniel Soudry.  Optimal fine-grained n: M sparsity for activations and neural gradients.  arXiv preprint arXiv:2203.10991, 2022.
  * [3] Ioana Croitoru, Simion-Vlad Bogolin, and Marius Leordeanu.  Unsupervised learning of foreground object segmentation.  International Journal of Computer Vision (IJCV), 127(9):1279–1302, 2019.
  * [4] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 248–255, 2009.
  * [5] Xiaohan Ding, Guiguang Ding, Yuchen Guo, Jungong Han, and Chenggang Yan.  Approximated oracle filter pruning for destructive cnn width optimization.  In International Conference on Machine Learning (ICML), pages 1607–1616. PMLR, 2019.
  * [6] Xiaohan Ding, Xiangxin Zhou, Yuchen Guo, Jungong Han, Ji Liu, et al.  Global sparse momentum sgd for pruning very deep neural networks.  In Advances in Neural Information Processing Systems (NeurIPS), pages 6382–6394, 2019.
  * [7] Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen.  Rigging the lottery: Making all tickets winners.  In International Conference on Machine Learning (ICML), pages 2943–2952, 2020.
  * [8] Ross Girshick.  Fast r-cnn.  In IEEE International Conference on Computer Vision (ICCV), pages 1440–1448, 2015.
  * [9] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In IEEE International Conference on Computer Vision (ICCV), pages 580–587, 2014.
  * [10] Song Han, Jeff Pool, John Tran, and William Dally.  Learning both weights and connections for efficient neural network.  In Advances in Neural Information Processing Systems (NeurIPS), pages 1135–1143, 2015.
  * [11] Kaiming He, Georgia Gkioxari, Piotr Dollar, and Ross Girshick.  Mask r-cnn.  In IEEE International Conference on Computer Vision (ICCV), 2017\.
  * [12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, 2016.
  * [13] Yang He, Guoliang Kang, Xuanyi Dong, Yanwei Fu, and Yi Yang.  Soft filter pruning for accelerating deep convolutional neural networks.  In International Joint Conference on Artificial Intelligence (IJCAI), pages 2234–2240, 2018.
  * [14] Yang He, Ping Liu, Ziwei Wang, Zhilan Hu, and Yi Yang.  Filter pruning via geometric median for deep convolutional neural networks acceleration.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4340–4349, 2019.
  * [15] Itay Hubara, Brian Chmiel, Moshe Island, Ron Banner, Joseph Naor, and Daniel Soudry.  Accelerated sparse neural training: A provable and efficient method to find n: m transposable masks.  Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
  * [16] Siddhant Jayakumar, Razvan Pascanu, Jack Rae, Simon Osindero, and Erich Elsen.  Top-kast: Top-k always sparse training.  In Advances in Neural Information Processing Systems (NeurIPS), pages 20744–20754, 2020.
  * [17] Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi.  Soft threshold weight reparameterization for learnable sparsity.  In International Conference on Machine Learning (ICML), pages 5544–5555, 2020.
  * [18] Yann LeCun, John Denker, and Sara Solla.  Optimal brain damage.  In Advances in Neural Information Processing Systems (NeurIPS), pages 598–605, 1989.
  * [19] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr.  Snip: Single-shot network pruning based on connection sensitivity.  In International Conference on Learning Representations (ICLR), 2019\.
  * [20] Mingbao Lin, Rongrong Ji, Yan Wang, Yichen Zhang, Baochang Zhang, Yonghong Tian, and Ling Shao.  Hrank: Filter pruning using high-rank feature map.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1529–1538, 2020.
  * [21] Mingbao Lin, Rongrong Ji, Yuxin Zhang, Baochang Zhang, Yongjian Wu, and Yonghong Tian.  Channel pruning via automatic structure search.  In International Joint Conference on Artificial Intelligence (IJCAI), pages 673–679, 2020.
  * [22] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European Conference on Computer Vision (ECCV), pages 740–755, 2014.
  * [23] Shiwei Liu, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Li Shen, Mykola Pechenizkiy, Zhangyang Wang, and Decebal Constantin Mocanu.  Sparse training via boosting pruning plasticity with neuroregeneration.  In Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [24] Zechun Liu, Haoyuan Mu, Xiangyu Zhang, Zichao Guo, Xin Yang, Tim Kwang-Ting Cheng, and Jian Sun.  Metapruning: Meta learning for automatic neural network channel pruning.  In IEEE International Conference on Computer Vision (ICCV), pages 3296–3305, 2019.
  * [25] Christos Louizos, Max Welling, and Diederik P Kingma.  Learning sparse neural networks through $l\\_0$ regularization.  In International Conference on Learning Representations (ICLR), 2017\.
  * [26] Jian-Hao Luo and Jianxin Wu.  Autopruner: An end-to-end trainable filter pruning method for efficient deep model inference.  Pattern Recognition (PR), page 107461, 2020.
  * [27] Jian-Hao Luo, Jianxin Wu, and Weiyao Lin.  Thinet: A filter level pruning method for deep neural network compression.  In IEEE International Conference on Computer Vision (ICCV), pages 5058–5066, 2017.
  * [28] Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz.  Pruning convolutional neural networks for resource efficient inference.  In International Conference on Learning Representations (ICLR), 2017\.
  * [29] Xuefei Ning, Tianchen Zhao, Wenshuo Li, Peng Lei, Yu Wang, and Huazhong Yang.  Dsa: More efficient budgeted pruning via differentiable sparsity allocation.  In European Conference on Computer Vision (ECCV), pages 592–607. Springer, 2020.
  * [30] Nvidia.  Nvidia a100 tensor core gpu architecture.  https://www.nvidia.com/content/dam/en-zz/Solutions/Data-Center/nvidia-ampere-architecture-whitepaper.pdf, 2020.
  * [31] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  In Advances in Neural Information Processing Systems (NeurIPS), pages 8026–8037, 2019.
  * [32] Jeff Pool and Chong Yu.  Channel permutations for n: M sparsity.  Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
  * [33] Olivier Giroux et al. Ronny Krashinsky.  Nvidia ampere sparse tensor core.  https://developer.nvidia.com/blog/nvidia-ampere-architecture-in-depth/, 2020.
  * [34] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In International Conference on Learning Representations (ICLR), 2015\.
  * [35] Wei Sun, Aojun Zhou, Sander Stuijk, Rob Wijnhoven, Andrew O Nelson, Henk Corporaal, et al.  Dominosearch: Find layer-wise fine-grained n: M sparse schemes from dense neural networks.  Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
  * [36] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In International Conference on Machine Learning (ICML), pages 10347–10357, 2021.
  * [37] Ziheng Wang.  Sparsert: Accelerating unstructured sparsity on gpus for deep learning inference.  In Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques (ICPACT), pages 31–42.
  * [38] Ross Wightman.  Pytorch image models.  https://github.com/rwightman/pytorch-image-models, 2019.
  * [39] Yuxin Zhang, Mingbao Lin, Chia-Wen Lin, Jie Chen, Yongjian Wu, Yonghong Tian, and Rongrong Ji.  Carrying out cnn channel pruning in a white box.  IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 2022.
  * [40] Aojun Zhou, Yukun Ma, Junnan Zhu, Jianbo Liu, Zhijie Zhang, Kun Yuan, Wenxiu Sun, and Hongsheng Li.  Learning n: M fine-grained structured sparse neural networks from scratch.  In International Conference on Learning Representations (ICLR), 2021\.
  * [41] Aojun Zhou, Anbang Yao, Yiwen Guo, Lin Xu, and Yurong Chen.  Incremental network quantization: Towards lossless cnns with low-precision weights.  In International Conference on Learning Representations (ICLR), 2017\.
  * [42] Michael Zhu and Suyog Gupta.  To prune, or not to prune: exploring the efficacy of pruning for model compression.  In International Conference on Learning Representations Workshop (ICLRW), 2017.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [N/A]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [N/A]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [N/A]

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]


When $E_{i_{1}}$ has an arrowhead on $X_{i_{1}}$, putting $V_{L}$ into
${\mathbf{C}}$, $X_{i_{1}}$ into ${\mathbf{C}}$ ensures that existed inducing
paths are not damaged (any ancestor of $V_{L}$ still has a descendant
$X_{i_{1}}$ in ${\mathbf{C}}$) and there are inducing paths between $Y$ and
vertices newly added to ${\mathbf{O}}$, _i.e._ , $X_{i_{2}},...,X_{i_{r}}$.
Hence, in both scenarios, 2. (a) holds. In addition, the number of leaves
increases by $r-1$, and $|{\mathbf{O}}|$ increases by at least $r-1$, which
indicates 2. (b) holds.

To conclude, we have proved the claim that any causal graph $G$ whose skeleton
is a tree with $d_{L}$ leaves, and every internal vertex of the tree is a non-
chain vertex, has $N_{G}=\omega(c^{d_{L}})$ for some $1<c<2$. Next, we prove
Claim E.8, _i.e._ , any causal graph $G$ whose skeleton is a tree with $d_{L}$
leaves, has $N_{G}=\omega(c^{d_{L}})$ for some $1<c<2$.

1. Any interval vertex in $G$ is either a trunk vertex or a non-chain vertex. Use Lemma 3 to melt all chunk vertices in $G$ (put a chunk vertex into ${\mathbf{L}}$ if it is a non-collider, into ${\mathbf{C}}$ if otherwise) and call the resulted graph as $\underline{G}$. Because $G$’s skeleton is a tree and there is no cycle in it, $\underline{G}$’s skeleton is also a tree where all interval vertices are non-chain vertices and there are still $d_{L}$ leaves.

2. By Lemma 3, we have $N_{G}>N_{\underline{G}}=\omega(c^{d_{L}})$ and thus $N_{G}=\omega(c^{d_{L}})$ for some $1<c<2$. ∎

######  Lemma E.9 (Maximum leaf spanning tree).

In a connected undirected graph $G$ with $d$ vertices, if every vertex is
either a non-chain vertex or a vertex of deg$=1$, then $G$ has a spanning tree
with $\Theta(d)$ leaves.

###### Proof.

The proof is similar to Lemma 1 in (Young, 2022). We first discuss a property
that any $G$’s spanning tree satisfies, then focus on the number of leaves in
$G$’s maximum leaf spanning tree.

Suppose $T$ is a spanning tree of $G$, denote the number of leaves, chunk
vertices, and non-chain vertices in $T$ as $d_{1},d_{2},d_{>2}$, respectively.
Note that a leaf in $T$ is not necessarily a vertex of deg$=1$ in $G$,
however, a chunk/non-chain vertex in $T$ must be a non-chain vertex in $G$.

Let $G^{\prime}$ be a subgraph of $T$ consisting of: i) all the $d_{2}$ chunk
vertices in $T$, and ii) edges among these chunk vertices in $T$. As a result,
$G^{\prime}$ is a subgraph (maybe not a connected one) of $T$ with maximum
degree $2$.

We claim the number of edges in $G^{\prime}$ is at least $d-4d_{1}-1$. The
proof is as follows. i) Construct a tree $T^{\prime}$ from $T$ by slicing out
all chunk vertices in $T$. Specifically, for each maximal path
$p_{i}:=<X_{i_{1}},X_{i_{2}},...,X_{i_{(l-1)}},X_{i_{l}}>$ in $T$ such that
all the intermediate vertices $X_{i_{2}},...,X_{i_{(l-1)}}$ are chunk vertices
in $T$, remove the edge $X_{i_{j}}-X_{i_{(j+1)}}$ for $j=2,3,...,l-2$ and the
intermediate vertices. Then, replace them with an edge $X_{i_{1}}-X_{i_{l}}$
(which is not necessarily also in $G$). ii) In $T^{\prime}$, every internal
vertex is a non-chain vertex and there are still $d_{1}$ leaves. As a result,
in $T^{\prime}$, the number of edges is at most $2d_{1}$. iii) Now compare
edges in $T^{\prime}$ and $G^{\prime}$. (a) If an edge in $T^{\prime}$ is also
in $T$, then this edge is not in $G^{\prime}$ because it is incident with a
non-chain vertex in $T$ and $G^{\prime}$ does not contain any of such edge.
(b) If an edge in $T^{\prime}$ is constructed by slicing out chunk vertices in
$T$, then there is two edges missing in $G^{\prime}$ compared with $T$. iv) As
a result, for each edge in $T^{\prime}$, $G^{\prime}$ is missing at most two
edges compared with $T$. Hence, $G^{\prime}$ is missing at most $2\cdot
2d_{1}=4d_{1}$ edges compared with $T$. Because there are $d-1$ edges in $T$,
there are at least $d-4d_{1}-1$ edges in $G^{\prime}$.

Because there is at most $d$ vertices in $G^{\prime}$, we know in
$G^{\prime}$, the number of vertices minuses the number of edges $\leq
4d_{1}$. Hence, $G^{\prime}$ contains at most $4d_{1}$ paths666counting each
isolated vertex in $G^{\prime}$ as a path, a path with $l$ vertices has $l-1$
edges.. A path with a single vertex indicates there is a vertex in
$G^{\prime}$ without two neighbors in $G^{\prime}$, a path with $\geq 2$
vertices indicates there are two vertices in $G^{\prime}$ without two
neighbors in $G^{\prime}$. Because $G^{\prime}$ contains at most $4d_{1}$
paths, we know there are at most $8d_{1}$ vertices in $G^{\prime}$ without two
neighbors in $G^{\prime}$.

Because $G^{\prime}$ contains all the $d_{2}$ chunk vertices in $T$, there are
at least $d_{2}-8d_{1}$ vertices in $G^{\prime}$ having two neighbors in
$G^{\prime}$. Back to $T$, we have at least $d_{2}-8d_{1}$ vertices having the
following properties: i) They are chunk vertices in $T$, and ii) both of their
two neighbors are chunk vertices in $T$. Call such vertices pipe vertices.

Now we discuss the number of leaves in $G$’s maximum leaf spanning tree.

Suppose $T$ is a maximum leaf spanning tree. Then, there are at least
$d_{2}-8d_{1}$ pipe vertices in $T$. Let $U$ be a pipe vertex in $T$ and
consider any edge $U*\\!-\\!*V$ from $U$ that is not in $T$. We show $V$ must
be a leaf in $T$. Prove by contradiction. Suppose $V$ is not a leaf in $T$,
then add the edge $U*\\!-\\!*V$ into $T$ and delete one of the other edges
incident to $U$ to break the cycle (so the result is still a spanning tree).
This makes one of $U$’s neighbors in $T$ a leaf, which indicates the number of
leaves increases. Because $T$ is a maximum spanning tree, this is a
contradiction and $V$ is a leaf in $T$. To conclude, for every pipe vertex
$U$, every edge incident to $U$ except the two in $T$ goes to a leaf in $T$.

Each pipe vertex in $T$ is a non-chain vertex in $G$, so we have at least
$d_{2}-8d_{1}$ pipe vertices in $T$ having $\mathrm{deg}\geq 3$ in $G$. As a
result, there are at least $d_{2}-8d_{1}$ edges incident to pipe vertices to
the $d_{1}$ leaves in $T$.

Next, we prove $d_{2}-8d_{1}\leq d_{1}$, which indicates
$d_{1}\geq\frac{1}{9}d_{2}$ and together with Lemma E.1 indicates
$d_{1}=\Theta(d)$. Prove by contradiction. Suppose $d_{2}-8d_{1}>d_{1}$. Then
at least one leaf in $T$, say $V$, is connected to two pipe vertices in $T$,
say $U_{1},U_{2}$. Then, add the edges $V*\\!-\\!*U_{1}$, $V*\\!-\\!*U_{2}$ to
$T$ and delete one of the incident edges of $U_{1},U_{2}$ each, we lose one
leaf vertex $V$ in $T$, however, obtain two more (one of $U_{1}$’s neighbors
and one of $U_{2}$’s neighbors), which contradict with $T$ being a maximum
leaf spanning tree. ∎

######  Lemma E.10.

For a connected causal graph $G$, if $d_{>2}=\omega(\mathrm{log}(d))$, then
$N_{G}=\mathrm{NP}(d)$.

###### Proof.

We prove the lemma by showing that any $G$ with $d_{>2}=\omega(\log(d))$ has a
maximum leaf spanning tree with $\omega(d_{>2})$ leaves. In the regard, by
Lemma E.8, the maximum leaf spanning tree has at least
$\omega(2^{\log(d)})=\mathrm{NP}(d)$ equivalence classes. Then, we can delete
the edges in $G$ until $G$ becomes its maximum leaf spanning tree and use
Lemma E.6 to show $N_{G}=\mathrm{NP}(d)$.

We first construct a lower bound graph $\underline{G}$ of $G$ such that
$N_{\underline{G}}\leq N_{G}$, by keeping all vertices of deg$=1$, deg$>2$,
and removing all the chunk vertices which have deg$=2$. Specifically, use
Lemma 3 and iteratively melt the chunk vertex $X_{i}$, whose two neighbors
denoted as $A_{i},B_{i}$, with the following rules: i) If
$\mathrm{deg}(A_{i})=1$, or $\mathrm{deg}(B_{i})=1$, or
$\mathrm{deg}(A_{i})=\mathrm{deg}(B_{i})=2$, or
$\mathrm{deg}(A_{i})=\mathrm{deg}(B_{i})=3$, put $X_{i}$ into ${\mathbf{L}}$
if it is a non-collider, ${\mathbf{C}}$ if otherwise. ii) Otherwise, one of
$\mathrm{deg}(A_{i}),\mathrm{deg}(B_{i})$ is $2$, the other one is $3$.
Without loss of generality, suppose
$\mathrm{deg}(A_{i})=2,\mathrm{deg}(B_{i})=3$. If $A_{i}$ is adjacent to
$B_{i}$ and $A_{i},X_{i},B_{i}$ form a cycle, then delete the edge
$A_{i}*\\!-\\!*X_{i}$. Otherwise, melt the vertex $X_{i}$ (put it into
${\mathbf{L}}$ if it is a non-collider, ${\mathbf{C}}$ if otherwise).

Next, we show that the $\underline{G}$ is a connected graph with at least
$d_{>2}$ vertices, such that every vertex in $\underline{G}$ is either of
deg$=1$ or a non-chain vertex. This is because all vertices of deg$=1$ in $G$
are still of deg$=1$ in $\underline{G}$, all non-chain vertices in $G$ are
still of deg$\geq 3$ in $\underline{G}$.

Hence, $\underline{G}$ has a maximum leaf spanning tree $\underline{T}$ with
at least $\Theta(d_{>2})$ leaves, according to Lemma E.9. By Claim E.8, we
have $N_{\underline{T}}=\omega(c^{d_{>2}})$ for some $1<c<2$. By Lemma 3, we
have $N_{G}>N_{\underline{G}}>N_{\underline{T}}$, which together with
$d_{>2}=\omega(\mathrm{log}(d))$ and Lemma E.3 indicates
$N_{G}=\mathrm{NP}(d)$. ∎

######  Lemma E.11.

Consider two vertex sets $\mathbf{V}^{i},\mathbf{V}^{j}$, and a path $p$
between two vertices $V_{1},V_{l}$. If $p$ can be blocked by $\mathbf{V}^{i}$,
but can not be blocked by $\mathbf{V}^{i}\cup\mathbf{V}^{j}$, then, we have
$V_{1}\not\perp\\!\\!\\!\\!\perp_{G}\mathbf{V}^{j}|\mathbf{V}^{i}$.

###### Proof.

To prove the lemma, we construct a path $p_{1}$ between $V_{1}$ and a vertex
in $\mathbf{V}^{j}$ such that $p_{1}$ can not be blocked by $\mathbf{V}^{i}$.

We first prove the following properties i)-iv):

i) $p$ must contain a collider. Prove by contradiction. Suppose all vertices
on $p$ are non-colliders. Then, since $\mathbf{V}^{i}$ can block $p$, we have
$\mathbf{V}^{j}$ contains at least one non-collider on $p$. Hence, the union
set $\mathbf{V}^{i}\cup\mathbf{V}^{j}$ also contains a non-collider on $p$.
Therefore, $p$ can be blocked by $\mathbf{V}^{i}\cup\mathbf{V}^{j}$, which is
a contradiction.

ii) In a similar way, we can prove that $\mathbf{V}^{i}$ and
$\mathbf{V}^{i}\cup\mathbf{V}^{j}$ do not contain any non-collider on $p$.

iii) Since $p$ can be blocked by $\mathbf{V}^{i}$ and ii), we have:
$\exists\,$ a collider on $p$ such that the collider and its descendants are
all in $\mathbf{V}^{i}$.

iv) For any collider $V_{c}$ on $p$, if $V_{c}$ and any vertex in
$\mathbf{De}(V_{c})$ are all not in $\mathbf{V}^{i}$, then, either $V_{c}$ or
a vertex in $\mathbf{De}(V_{c})$ is in $\mathbf{V}^{j}$. This is because if
otherwise, $V_{i}$ and all vertices in $\mathbf{De}(V_{i})$ are not in
$\mathbf{V}^{i}\cup\mathbf{V}^{j}$. Therefore, the path $p$ can be blocked by
$\mathbf{V}^{i}\cup\mathbf{V}^{j}$, which is a contradiction.

We then construct the path $p_{1}$ in the following way:

Denote those colliders on $p$ such that themselves and their descendants are
all not in $\mathbf{V}^{i}$ as (in the order of their distance to $V_{1}$) as
$\\{V_{c_{1}},V_{c_{2}},...,V_{c_{l}}\\}$.

Now, consider the subpath $p^{\prime}$ of $p$ with
$p^{\prime}:=<V_{1},V_{2},...,V_{c_{1}-1},V_{c_{1}}>$. We have the following
analyses: i) By the definition of $V_{c_{1}}$, among
$V_{1},V_{2},...,V_{c_{1}-1}$, all colliders and their descendants are in
$\mathbf{V}^{i}$. ii) Among $V_{1},V_{2},...,V_{c_{1}-1}$, all non-colliders
are not in $\mathbf{V}^{i}$. iii) Either $V_{c_{1}}$ or a vertex in
$\mathbf{De}(V_{c_{1}})$ is in $\mathbf{V}^{j}$.

If it is $V_{c_{1}}\in\mathbf{V}^{j}$, then we have the path
$p_{1}=<V_{1},V_{2},...,V_{c_{1}}>$ between $V_{1}$ and a vertex in
$\mathbf{V}^{j}$ satisfying that $p_{1}$ can not be blocked by
$\mathbf{V}^{i}$, because of i) and ii); If it is a vertex in
$\mathbf{De}(\mathbf{V}^{j})$ that is in $\mathbf{V}^{j}$, then, we have the
path $p_{1}=<V_{1},V_{2},...,V_{c_{1}}\to\cdots\to V_{j})$ for
$V_{j}\in\mathbf{De}(V_{c_{1}}>$, between $V_{1}$ and a vertex in
$\mathbf{V}^{j}$ satisfying that $p_{1}$ can not be blocked by
$\mathbf{V}^{i}$, because of i), ii), and the definition of $V_{c_{1}}$. ∎

######  Lemma E.12 (Merging property).

For any causal graph $G$ where $Y$ is adjacent to a vertex $X_{0}$, and
vertices in $\mathbf{V}\backslash\\{Y,X_{0}\\}$ are adjacent to at most one
vertex in $\\{Y,X_{0}\\}$, merge777The merging operation means contradicting
the edge $(Y,X_{0})$ and merging $Y,X_{0}$ into a new vertex $\tilde{Y}$.
Edges incident to $\tilde{Y}$ in $\tilde{G}$ are edges incident to either $Y$
or $X_{0}$ in $G$, their orientations on the $\tilde{Y}$ side can be randomly
assigned, and do not influence $N_{\tilde{G}}$, while orientations on the
other side keep the same as in $G$. $Y,X_{0}$ into a new vertex $\tilde{Y}$
and denote the resulted graph as $\tilde{G}$. Then, we have
$N_{\tilde{G}}+1\leq N\leq 2N_{\tilde{G}}$.

###### Proof.

During the proof, we omit the subscript and denote $N_{G}$ as $N$,
$N_{\tilde{G}}$ as $\tilde{N}$, $\mathbf{X}_{S_{i}}$ as $\mathbf{X}^{i}$ for
brevity.

Proof of the right side. We show for any
$\mathbf{T}\subseteq\\{X_{0}\\},\mathbf{X}^{i},\mathbf{X}^{j}\subseteq\mathbf{V}\backslash\\{Y,X_{0}\\}$,
if $\mathbf{X}^{i}\sim_{\tilde{G}}\mathbf{X}^{j}$, then
$\mathbf{X}^{i}\cup\mathbf{T}\sim_{G}\mathbf{X}^{j}\cup\mathbf{T}$. In this
regard, for any subset $\mathbf{T}$, there are at most $\tilde{N}$ equivalent
classes in $G$, thus $N\leq 2^{|\mathbf{T}|}\tilde{N}=2\tilde{N}$.

1. By $\mathbf{X}^{i}\sim_{\tilde{G}}\mathbf{X}^{j}$, we have $\exists\,\mathbf{X}^{ij}\subseteq\mathbf{X}^{i}\cap\mathbf{X}^{j}$ such that $\tilde{Y}\perp\\!\\!\\!\\!\perp_{\tilde{G}}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$. In other word, we have $\\{Y,X_{0}\\}\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$.

2. When $\mathbf{T}=\emptyset$, by 1., we have $Y\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$ and thus $\mathbf{X}^{i}\sim_{G}\mathbf{X}^{j}$ holds.

3. When $\mathbf{T}=\\{X_{0}\\}$, by 1., we have: i) any path in $G$ between $\mathbf{X}^{({ij})^{c}}$ and $Y$ can be blocked by $\mathbf{X}^{ij}$, and ii) any path in $G$ between $\mathbf{X}^{({ij})^{c}}$ and $\mathbf{T}$ can be blocked $\mathbf{X}^{ij}$. Next, we show any path in $G$ between $\mathbf{X}^{({ij})^{c}}$ and $Y$ can also be blocked by $\mathbf{X}^{ij}\cup\mathbf{T}$, which indicates $\mathbf{X}^{i}\cup\mathbf{T}\sim_{G}\mathbf{X}^{j}\cup\mathbf{T}$.

Prove by contradiction. Suppose there is a path between
$\mathbf{X}^{({ij})^{c}}$ and $Y$ that can be blocked by $\mathbf{X}^{ij}$ and
can not be blocked by $\mathbf{X}^{ij}\cup\mathbf{T}$. By Lemma. E.11, we can
construct a path between $\mathbf{X}^{({ij})^{c}}$ and $\mathbf{T}$ such that
it can not be blocked by $\mathbf{X}^{ij}$, which contradicts with 3\. ii).

Proof of the left side. We first prove the in-equation under the case when
$X_{0}$ is a complete collider888$X_{0}$ is called a complete (non-)collider
if it is a (non-)collider on any path $p:=<X_{i},X_{0},Y>$ with
$X_{i}\in\mathbf{Neig}_{G}(X_{0})\backslash\\{Y_{0}\\}$.. With $\\{X_{0}\\}$
as the selection set, the induced MAG is $\tilde{G}$, since there is at least
one equivalent class when not conditioning on $X_{0}$, we have
$\tilde{N}+1\leq N$ by Alg. 2 and Lemma 3.

For the cases when $X_{0}$ is a complete non-collider, or $X_{0}$ is a partial
collider and $\exists\,X_{i}\in\mathbf{De}(X_{0})$ such that $X_{i}$ is
incident to a tail-tail999A tail-tail edge is an edge $*\\!-\\!*$ with
orientations at both sides being tails, _i.e._ , $-$. According to the
definition of a tail-tail edge (Zhang, 2008), a vertex is incident to a tail-
tail edge means it is an ancestor of a member of the selection set. edge, we
can prove $\tilde{N}+1\leq N$ in a similar way.

Next, we discuss the case where $X_{0}$ is a partial collider and $\forall
X_{i}\in\mathbf{De}(X_{0})$, $X_{i}$ is not incident to a tail-tail edge. We
first show the following properties 1. and 2..

1. In $G$, for two vertex sets $\mathbf{X}^{i},\mathbf{X}^{j}$, if $X_{0}\in\mathbf{X}^{i}$ and $X_{0}\not\in\mathbf{X}^{j}$, then $\mathbf{X}^{i}\not\sim_{G}\mathbf{X}^{j}$. This is because $Y$ is adjacent to $X_{0}$ in $G$.

Further, we show for two vertex sets $\mathbf{X}^{i},\mathbf{X}^{j}$, if
$\mathbf{X}^{i}\cap\mathbf{De}(X_{0})\neq\emptyset$ and
$\mathbf{X}^{j}\cap\mathbf{De}(X_{0})=\emptyset$, then
$\mathbf{X}^{i}\not\sim_{G}\mathbf{X}^{j}$. This is proved as follows. For
$X_{i}\in\mathbf{X}^{i}\cap\mathbf{De}(X_{0})$, there is a path $p:=<Y*\\!\to
X_{0}\to\cdots\to X_{i}>$ from $Y$ to $X_{i}$. Since
$\mathbf{X}^{j}\cap\mathbf{De}(X_{0})=\emptyset$,
$\forall\,\mathbf{X}^{ij}\subseteq\mathbf{X}^{i}\cap\mathbf{X}^{j}$, we have
$\mathbf{X}^{ij}\cap\mathbf{De}(X_{0})=\emptyset$ and
$X_{i}\in\mathbf{X}^{({ij})^{c}}$. As a result,
$\forall\,\mathbf{X}^{ij}\subseteq\mathbf{X}^{i}\cap\mathbf{X}^{j}$, there is
a path $p$ between $Y$ and $\mathbf{X}^{({ij})^{c}}$ such that $p$ can not be
blocked by $\mathbf{X}^{ij}$, _i.e._ ,
$\mathbf{X}^{i}\not\sim_{G}\mathbf{X}^{j}$.

In $\tilde{G}$, similarly, for two vertex sets
$\mathbf{X}^{i},\mathbf{X}^{j}$, if
$\mathbf{X}^{i}\cap\mathbf{De}(X_{0})\neq\emptyset$ and
$\mathbf{V}_{j}\cap\mathbf{De}(X_{0})=\emptyset$, then
$\mathrm{X}_{i}\not\sim_{\tilde{G}}\mathbf{X}^{j}$.

2. In $G$, by 1., divide subsets of $\mathbf{X}$ into those that contain $X_{0}$ and those that do not contain $X_{0}$. Denote the number of equivalent classes in them as $N_{1},N_{2}$, respectively, we have $N=N_{1}+N_{2}$. Further, divide those subsets that do not contain $X_{0}$ into those that have an intersection with $\mathbf{De}(X_{0})$ and those that have no intersection with $\mathbf{De}(X_{0})$. Denote the number of equivalent classes in them as $N_{3},N_{4}$, respectively. We have $N_{2}=N_{3}+N_{4}$ and thus $N=N_{1}+N_{3}+N_{4}$.

Similarly, in $\tilde{G}$, divide subsets of $\mathbf{X}\backslash\\{X_{0}\\}$
into those that have an intersection with $\mathbf{De}(X_{0})$ and those that
have no intersection with $\mathbf{De}(X_{0})$. Denote the number of
equivalent classes in them as $\tilde{N}_{1},\tilde{N}_{2}$, respectively. We
have $\tilde{N}=\tilde{N}_{1}+\tilde{N}_{2}$.

It is straightforward to have $N_{4}\geq 1$. In the following, we will show
$N_{1}\geq\tilde{N}_{2},N_{3}=\tilde{N}_{1}$ and thus $N\geq\tilde{N}+1$.

Claim. 1. For two subsets of vertex $\mathbf{X}^{i},\mathbf{X}^{j}$ such that
$\mathbf{X}^{i}\cap(X_{0}\cup\mathbf{De}(X_{0}))=\emptyset$ and
$\mathbf{X}^{j}\cap(X_{0}\cup\mathbf{De}(X_{0}))=\emptyset$, then
$\mathbf{X}^{i}\sim_{\tilde{G}}\mathbf{X}^{j}\Leftrightarrow\mathbf{X}^{i}\cup
X_{0}\sim_{G}\mathbf{X}^{j}\cup X_{0}$, which indicates
$N_{1}\geq\tilde{N}_{2}$.

Proof of Claim. 1. $\Rightarrow$ can be proved similarly as the proof of the
right side.

$\Leftarrow$ Suppose $\mathbf{X}^{i}\cup X_{0}\sim_{G}\mathbf{X}^{j}\cup
X_{0}$, we will show $\mathbf{X}^{i}\sim_{\tilde{G}}\mathbf{X}^{j}$, given the
fact that $\mathbf{X}^{i},\mathbf{X}^{j}$ do not contain $X_{0}$ nor its
descendants, and any member of $\\{X_{0}\\}\cup\mathbf{De}(X_{0})$ is not
incident to a tail-tail edge.

1. For $X_{i}\in\mathbf{De}(X_{0})$ and $X_{j}\not\in\mathbf{De}(X_{0})$, since $X_{i}-X_{j}$ and $X_{i}\to X_{j}$ is not allowed, it must be $X_{i}\leftarrow\\!*X_{j}$. Similarly, we have $X_{0}\to X_{i}$ and $X_{0}\leftarrow\\!*X_{j}$.

2. By $\mathbf{X}^{i}\cup X_{0}\sim_{G}\mathbf{X}^{j}\cup X_{0}$, we have $\exists\,\mathbf{X}^{ij}\subseteq(\mathbf{X}^{i}\cup X_{0})\cap(\mathbf{X}^{j}\cup X_{0})$ such that $Y\perp\\!\\!\\!\\!\perp_{G}(\mathbf{X}^{i}\cup\mathbf{X}^{j}\cup X_{0})\backslash\mathbf{X}^{ij}|\mathbf{X}^{ij}$. Since $Y$ is adjacent to $X_{0}$, $\mathbf{X}^{ij}$ must contain $X_{0}$. That is, $\exists\,\mathbf{X}^{ij}\subseteq\mathbf{X}^{i}\cap\mathbf{X}^{j}$ such that $Y\perp\\!\\!\\!\\!\perp_{G}(\mathbf{X}^{i}\cup\mathbf{X}^{j}\cup X_{0})\backslash(\mathbf{X}^{ij}\cup X_{0})|\mathbf{X}^{ij}\cup X_{0}$, which is equivalent to $Y\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}\cup X_{0}$.

3. We first show $Y\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$, which is equivalent to showing any path between $Y$ and $\mathbf{X}^{({ij})^{c}}$ can be blocked by $\mathbf{X}^{ij}$. Prove by contradiction. Suppose there is a path $p_{0}:=<X_{k_{1}},X_{k_{2}},...,Y>$ between $Y$ and $\mathbf{X}^{({ij})^{c}}$ that can be blocked by $\mathbf{X}^{ij}\cup X_{0}$, and can not be blocked by $\mathbf{X}^{ij}$. By Lemma. D.1, the set $\\{X_{0}\\}$ contains a non-collider on $p_{0}$, which means $X_{0}$ is a non-collider on $p_{0}$.

Then, $X_{0}$ is incident to at least one tail on $p_{0}$, since
$X_{0}\leftarrow\\!*X_{j}$ for $X_{j}\not\in\mathbf{De}(X_{0})$, $p_{0}$ must
contain a member of $\mathbf{De}(X_{0})$ and
$p_{0}=<X_{k_{1}},X_{k_{2}},...,X_{0}\to X_{i},...,Y>$ for
$X_{i}\in\mathbf{De}(X_{0})$. Since $Y$ is not a member of
$\mathbf{De}(X_{0})$, there is $X_{0}\to\cdots\to X_{i}\leftarrow\\!*X_{j}$
for $X_{i}\in\mathbf{De}(X_{0})$ and $X_{j}\not\in\mathbf{De}(X_{0})$ on
$p_{0}$. As a result, $p_{0}$ contains a collider that itself nor its
descendants are in $\mathbf{X}^{ij}$. This means $p_{0}$ can be blocked by
$\mathbf{X}^{ij}$ and thus a contradiction.

4. We then show $X_{0}\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$, which together with 3. means $\\{Y,X_{0}\\}\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$ and thus $\mathbf{X}^{i}\sim_{\tilde{G}}\mathbf{X}^{j}$. We show this by proving any path between $\mathbf{X}^{({ij})^{c}}$ and $X_{0}$ can be blocked by $\mathbf{X}^{ij}$. Prove by contradiction. Suppose there is a path $p_{1}:=<X_{k_{1}},X_{k_{2}},...,X_{k_{l}},X_{0}>$ that can not be blocked by $\mathbf{X}^{ij}$.

Then, if $X_{k_{l}}\not\in\mathbf{De}(X_{0})$, we have a path
$p_{2}:=<X_{k_{1}},...,X_{k_{l}}*\\!\to X_{0}\leftarrow*Y>$ such that $p_{2}$
can not be blocked by $\mathbf{X}^{ij}\cup X_{0}$, which contradicts with
$Y\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}\cup
X_{0}$. Otherwise $X_{k_{l}}\in\mathbf{De}(X_{0})$, then we have a path
$p_{2}:=<X_{k_{1}},...,X_{k_{l}}\leftarrow X_{0}\leftarrow\\!*Y>$. Since
$X_{k_{1}}\in\mathbf{X}^{({ij})^{c}}$ and thus
$X_{k_{1}}\not\in\mathbf{De}(X_{0})$, there is $X_{j}\to
X_{i}\leftarrow\cdots\leftarrow X_{0}$, with $X_{j}\not\in\mathbf{De}(X_{0})$,
$X_{i}\in\mathbf{De}(X_{0})$, between $X_{k_{1}}$ and $X_{0}$. Hence, we have
$X_{i}$ is a collider on $p_{1}$, itself nor its descendants are in
$\mathbf{X}^{ij}$, which means $p_{1}$ can be blocked by $\mathbf{X}^{ij}$ and
thus a contradiction.

To conclude, 3. and 4. mean $\Leftarrow$ is true.

Claim. 2. Two subsets of vertices $\mathbf{X}^{i},\mathbf{X}^{j}$ such that
$\mathbf{X}^{i},\mathbf{X}^{j}$ do not contain $X_{0}$,
$\mathbf{X}^{i}\cap\mathbf{De}(X_{0})\neq\emptyset$, and
$\mathbf{X}^{j}\cap\mathbf{De}(X_{0})\neq\emptyset$, then,
$\mathbf{X}^{i}\sim_{\tilde{G}}\mathbf{X}^{j}\Leftrightarrow\mathbf{X}^{i}\sim_{G}\mathbf{X}^{j}$,
which indicates $N_{3}=\tilde{N}_{1}$.

Proof of Claim. 2. $\Rightarrow$ can be proved similarly as the proof of the
right side.

$\Leftarrow$ 1. By $\mathbf{X}^{i}\sim_{G}\mathbf{X}^{j}$, we have
$\exists\,\mathbf{X}^{ij}\subseteq\mathbf{X}^{i}\cap\mathbf{X}^{j}$ such that
$Y\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$.

We show that $\mathbf{X}^{ij}$ must contain a member of $\mathbf{De}(X_{0})$.
Prove by contradiction. Suppose
$\mathbf{X}^{ij}\cap\mathbf{De}(X_{0})=\emptyset$, which means
$\mathbf{X}^{ij}$ does not contain $X_{0}$ nor its descendants. Since
$\mathbf{X}^{i}\cap\mathbf{De}(X_{0})\neq\emptyset$ and
$\mathbf{X}^{j}\cap\mathbf{De}(X_{0})\neq\emptyset$,
$(\mathbf{X}^{i}\cup\mathbf{X}^{j})\backslash(\mathbf{X}^{ij}\cap\mathbf{De}(X_{0}))\neq\emptyset$.
As a result, there is a path $p_{0}:=<Y*\\!\to X_{0}\to\cdots\to X_{i}>$, for
$X_{i}\in\mathbf{De}(X_{0})$, between $Y$ and $\mathbf{X}^{({ij})^{c}}$ that
can not be blocked by $\mathbf{X}^{ij}$, which contradicts with
$Y\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$. As a
result, $\mathbf{X}^{ij}$ must contain a member of $\mathbf{De}(X_{0})$.

2. Next, we show $X_{0}\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$, which together with 1. indicates $\\{Y,X_{0}\\}\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$ and thus $\mathbf{X}^{i}\sim_{\tilde{G}}\mathbf{X}^{j}$. We prove this by showing any path between $\mathbf{X}^{({ij})^{c}}$ and $X_{0}$ can be blocked by $\mathbf{X}^{ij}$.

Prove by contradiction. Suppose there is a path
$p_{1}:=<X_{k_{1}},X_{k_{2}},...,X_{k_{l}},X_{0}>$ that can not be blocked
$\mathbf{X}^{ij}$. Consider the path
$p_{2}:=<X_{k_{1}},X_{k_{2}},...,X_{k_{l}},X_{0}\leftarrow\\!*Y>$ constructed
from $p_{1}$. If $X_{0}$ is a non-collider, since $\mathbf{X}^{ij}$ does not
contain $X_{0}$, $p_{2}$ can not be blocked by $\mathbf{X}^{ij}$. Otherwise
$X_{0}$ is a collider, since $\mathbf{X}^{ij}$ contains a member of
$\mathbf{De}(X_{0})$, $p_{2}$ can not be blocked by $\mathbf{X}^{ij}$ neither.
These results contradict with
$Y\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$. Hence,
we have
$X_{0}\perp\\!\\!\\!\\!\perp_{G}\mathbf{X}^{({ij})^{c}}|\mathbf{X}^{ij}$.

To conclude, 1. and 2. mean $\Leftarrow$ is true. Claim.1 indicates
$N_{1}\geq\tilde{N}_{2}$, Claim.2 indicates $N_{3}=\tilde{N}_{1}$, and thus
$N\geq\tilde{N}+1$. ∎

######  Corollary E.13 (Merging property for multiple vertices).

For any causal graph $G$ where $Y$ is adjacent to a connected vertex sets
$\mathbf{X}_{0}$, and vertices in $\mathbf{V}\backslash(\mathbf{X}_{0}\cup Y)$
is adjacent to at most one vertex in $\mathbf{X}_{0}\cup Y$. Merge
$Y,\mathbf{X}_{0}$ into a new vertex $\tilde{Y}$ and call the resulted graph
$\tilde{G}$. Then, $\tilde{N}+|\mathbf{X}_{0}|\leq N\leq
2^{|\mathbf{X}_{0}|}\tilde{N}$.

###### Proof.

Proof of the right side is the same as Lemma. 7.

Proof of the left side. Since $\mathbf{X}_{0}$ is a connected set and $Y$ is
adjacent to $\mathbf{X}_{0}$, we can delete edges among $\mathbf{X}_{0}\cup Y$
until the subgraph over $\mathbf{X}_{0}\cup Y$ becomes a spanning tree over
$\mathbf{X}_{0}\cup Y$ with $Y$ as the root vertex. Then, iteratively merge
vertices and use Lemma. 7, Lemma E.6, we have
$N\geq\tilde{N}+|\mathbf{X}_{0}|$. ∎

###  E.3 Details of Prop. 5.5: Complexity

In this section, we discuss the complexity of searching $N_{G}$ equivalence
classes. We show that compared to the exponential cost $O(2^{d_{S}})$ of
exhaustive search, our search strategy enjoys a polynomial cost
$\mathrm{P}(d_{S})$ when $G_{S}$ is mainly composited of chain vertices. Our
analysis mainly uses the results in Lemma E.10 and Lemma 7. The idea is
briefed as follows:

Lemma E.10 shows that any $G_{S}$ with $d_{>2}=\omega(\log(d))$ has
$N_{G}=\mathrm{NP}(d_{S})$. Hence, we need to look at cases when
$d_{>2}=O(\log(d))$. For these cases, Lemma 7 shows that the non-chain
vertices in $G_{S}$ do not influence the rank of $N_{G}$. This is because we
can iteratively merge the non-chain vertices into $Y$ and have $N_{G}$ being
squeezed within $N_{\tilde{G}}\sim 2^{d_{>2}}N_{\tilde{G}}$. Since
$2^{d_{>2}}=\mathrm{P}(d_{S})$, we have $N_{G}=\mathrm{P}(d_{S})$ if and only
if $N_{\tilde{G}}=\mathrm{P}(d_{S})$. Therefore, the rank of $N_{G}$ when
$d_{>2}=O(\log(d_{S}))$ is decided by $N_{\tilde{G}}$, in other words, by the
chain vertices with deg$\leq 2$ in $G_{S}$.

Intuitively, when the chain vertices compose different chains that do not
intersect each other, by Claim E.4, the $N_{\tilde{G}}$ is the product of the
chains’ lengths. Hence, the more “intensive” the chain vertices distribute,
the smaller $N_{\tilde{G}}$ and thus $N_{G}$ will be. In the following, we
will provide a formal metric $F_{G}$ to measure the intensity of chain
vertices.

We first define the following structures on $G_{S}$. For brevity, we omit the
subscript and denote $G_{S}$ as $G$, $d_{S}$ as $d$, respectively.

  1. 1.

A path is a sequence of distinct vertices $<V_{1},V_{2},...,V_{l}>$ where
$V_{i},V_{i+1}(i=1,2,...,l-1)$ are adjacent in $G$. The length of the path is
$l$. Define the distance between a vertex and $Y$ and the length of the
shortest path between them.

  2. 2.

A chain is a path where every vertex on it has $\mathrm{deg}\leq 2$ in $G$.
The head of a chain is the vertex in it that is closest to $Y$. A maximal
chain is a chain that can not be made longer by adding new vertices.

  3. 3.

For a maximal chain $c$, let $c\in\mathbf{Ch}^{\prime}(Y)$ if there is no
other maximal chain in the shortest path between the head of $c$ and $Y$. For
two maximal chains $c_{1},c_{2}$, let $c_{2}\in\mathbf{De}^{\prime}(c_{1})$ if
there is a path between a vertex in $c_{2}$ and $Y$ that contains $c_{1}$.

  4. 4.

For a maximal chain $c\in\mathbf{Ch}^{\prime}(Y)$, define a set of operations
$\mathrm{opt}_{c}(G)$ on $G$. Specifically, if
$\mathbf{De}^{\prime}(c)=\emptyset$, define
$\mathrm{opt}_{c}(G):=\\{\text{remove}\,c\\}$; Otherwise, define
$\mathrm{opt}_{c}(G):=\\{\text{remove}\,\mathbf{X}_{c}^{1:i}|i=1,2,...,l\\}\cup\\{\text{replace}\,c\,\text{with
an edge}\\}$, with $l$ the number of vertices on $c$, $X^{i}_{c}$ the $i$-th
one (in the order of the distance to $Y$), and
$\mathbf{X}^{1:i}_{c}:=\\{X_{c}^{1},X_{c}^{2},...,X_{c}^{i}\\}$.

  5. 5.

For a maximal chain with $l$ vertices, define $\mathrm{cost}(c):=l+1$ if $c$
has one head vertex, $(l^{2}+l+2)/2$ if $c$ has two head vertices (that is
both sides of $c$ have equal distance to $Y$).

Proposition 5.5 (Complexity). Let $F_{G}$ be an recursive metric defined over
maximal chains in $G$:

$F_{G}:=\prod_{\begin{subarray}{c}c\in\mathbf{Ch}^{\prime}_{G}(Y)\\\
\mathbf{De}^{\prime}(c)=\emptyset\end{subarray}}\mathrm{cost}(c)\sum_{\mathrm{opt}\in\prod_{c\in\mathbf{Ch}^{\prime}_{G}(Y)}\mathrm{opt}_{c}}F_{\mathrm{opt}(G)}.$

Then, $N_{G}=\mathrm{P}(d)$ if and only if $d_{>2}=O(\mathrm{log}(d))$ and
$F_{G}=\mathrm{P}(d)$.

###### Proof.

To prove the proposition, we will show i) if $d_{>2}=\omega(\mathrm{log}(d))$,
then $N_{G}=\mathrm{NP}(d)$; ii) if $d_{>2}=O(\mathrm{log}(d))$, then
$N_{G}=\mathrm{P}(d)\Leftrightarrow F_{G}=\mathrm{P}(d)$.

Specifically, ii) means if $d_{>2}=O(\mathrm{log}(d))$ and
$F_{G}=\mathrm{P}(d)$, then $N_{G}=\mathrm{P}(d)$, which shows $\Leftarrow$ of
the proposition. i) means if $N_{G}=\mathrm{P}(d)$, then
$d_{>2}=O(\mathrm{log}(d))$, together with ii), it means if
$N_{G}=\mathrm{P}(d)$, then $d_{>2}=O(\mathrm{log}(d))$ and
$F_{G}=\mathrm{P}(d)$, which shows $\Rightarrow$ of the proposition.

The proof of i) is at Lemma. E.10. The proof of ii) is as follows:

Claim. 1. $F_{G}\leq N_{G}\leq 2^{d_{>2}}F_{G}$.

Proof of Claim. 1. Modify Alg. 2 in the following way:

i) Add before line-2: if $\mathbf{Neig}(Y)$ contains non-chain vertices, then
merge them into $Y$ until $\mathbf{Neig}(Y)$ only contains non-chain vertices.
Call the resulting graph as $\tilde{G}$. ii) Replace the $G$ with $\tilde{G}$,
$G^{\prime}$ with $\tilde{G}^{\prime}$, and $N_{G}$ with $N_{\tilde{G}}$, in
lines 4-12. Call the modified algorithm as
$N_{\tilde{G}}=\mathrm{count}^{\prime}(G)$.

Next, we first show $F_{G}=N_{\tilde{G}}$, then prove Claim. 1 via the
$\mathrm{count}^{\prime}(G)$ algorithm.

After merging non-chain vertices around $Y$, in $\tilde{G}$, $Y$’s neighbors
are the head vertices of the maximal chains in $\mathbf{Ch}^{\prime}(Y)$.
Recursively conduct the $\mathrm{count}^{\prime}$ algorithm on $\tilde{G}$ and
its induced MAGs $\tilde{M}_{G}$, until all vertices in all maximal chains in
$\mathbf{Ch}^{\prime}(Y)$ have been traversed.

For maximal chains without descendants, since they are disjoint with the other
maximal chains, we have
$N_{\tilde{G}}=(\prod_{c\in\mathbf{Ch}^{\prime}_{\tilde{G}}(Y),\mathbf{De}^{\prime}_{\tilde{G}}(c)=\emptyset}\mathrm{cost}(c))N_{\mathrm{opt}_{1}(\tilde{G})}$,
where $\mathrm{cost}(c)=l+1$ if $c$ has one head vertex (see Claim E.4) and
$(l^{2}+l+2)/2$ if $c$ has two head vertices (see Claim E.5), and
$\mathrm{opt}_{1}:=\prod_{c\in\mathbf{Ch}^{\prime}_{\tilde{G}}(Y),\mathbf{De}^{\prime}_{\tilde{G}}(c)=\emptyset}\mathrm{cost}(c)\mathrm{opt}_{c}$,
and $\mathrm{opt}_{1}(\tilde{G})$ is the causal graph after removing all
maximal chains without descendants.

In $\mathrm{opt}_{1}(\tilde{G})$, denote the remained maximal chains in
$\mathbf{Ch}^{\prime}(Y)$ as $\\{c_{i}\\}_{i=1:r}$ and the vertices on them as
$\\{X^{i}_{1},...,X^{i}_{l_{i}}\\}_{i=1:r}$. To obtain
$N_{\mathrm{opt}_{1}(\tilde{G})}$, for each $c_{i}$, similarly as the analysis
of the Claim E.4, we need to consider the following $l_{i}+1$ situations:
$X^{i}_{1}$ is blocked101010A vertex of deg=2 is blocked if it is a non-
collider and is put in the selection set, or it is a collider and is put in
the latent set. A vertex is open if it is not blocked; $X^{i}_{1}$ is open,
$X^{i}_{2}$ is blocked; …; $X^{i}_{1},...,X^{i}_{l_{i}-1}$ are blocked,
$X^{i}_{l_{i}}$ is open; and $X^{i}_{1},...,X^{i}_{t_{i}}$ are open. Because
vertices in the $r$ maximal chains are disjoint, we in total need to consider
$\prod_{i=1}^{r}l_{i}+1$ situations, and
$N_{\mathrm{opt}_{1}(\tilde{G})}=\sum_{j=1}^{\prod_{i=1}^{r}l_{i}+1}N_{\mathrm{opt}_{1}(\tilde{G})^{\prime}_{j}}$,
where $\mathrm{opt}_{1}(\tilde{G})^{\prime}_{j}$ denotes the induced subgraph
from $\mathrm{opt}_{1}(\tilde{G})$ in the $j$-th situation.

Note that each subgraph $\mathrm{opt}_{1}(\tilde{G})^{\prime}_{j}$ corresponds
to an operation in
$\prod_{c\in\mathbf{Ch}^{\prime}_{\tilde{G}}(Y)}\mathrm{opt}_{c}$ on
$\tilde{G}$, we have
$N_{\mathrm{opt}_{1}(\tilde{G})}=\sum_{\mathrm{opt}\in\prod_{c\in\mathbf{Ch}^{\prime}_{\tilde{G}}(Y)}\mathrm{opt}_{c}}N_{\mathrm{opt}(\tilde{G})}$.
Hence,
$N_{\tilde{G}}=\prod_{c\in\mathbf{Ch}^{\prime}_{\tilde{G}}(Y),\mathbf{De}^{\prime}_{\tilde{G}}(c)=\emptyset}\mathrm{cost}(c)\sum_{\mathrm{opt}\in\prod_{c\in\mathbf{Ch}^{\prime}_{\tilde{G}}(Y)}\mathrm{opt}_{c}}N_{\mathrm{opt}(\tilde{G})}$
and $N_{\tilde{G}}=F_{G}$.

During the recursive execution of the $\mathrm{count}^{\prime}(G)$ to obtain
$N_{\tilde{G}}$, there are at most $d_{>2}$ non-chain vertices merged into
$Y$. As a result, by Lemma. 7, we have $N_{G}\leq 2^{d_{>2}}N_{\tilde{G}}$.
The number of non-chain vertices merged into $Y$ is at least $0$, so we also
have $N_{\tilde{G}}\leq N_{G}$.

To conclude, we have $F_{G}\leq N_{G}\leq 2^{d_{>2}}F_{G}$, which means Claim.
1. and hence the proposition is true. ∎

######  Remark E.14.

If the skeleton of $G$ is a tree, for two maximal chains $c_{1},c_{2}$, define
$c_{2}\in\mathbf{Ch}^{\prime}(c_{1})$ if $c_{1}$ contains the first non-chain
vertex in the path from the head of $c_{2}$ to $Y$. The $F_{G}$ degenerates
to:

$F_{G}=\prod_{\tilde{c}\in\mathbf{Ch}^{\prime}(Y)}f(\tilde{c}),$

with
$f(c):=\mathrm{cost}(c)+\prod_{\tilde{c}\in\mathbf{Ch}^{\prime}(c)}f(\tilde{c})$,
$\mathrm{cost}(c)=\mathrm{len}(c)+\mathbbm{1}(\mathbf{Ch}^{\prime}(c)=\emptyset)$.

##  Appendix F Experiment

###  F.1 Implementation details

All codes are implemented with PyTorch 1.10 and run on an Intel Xeon E5-2699A
<EMAIL_ADDRESS>CPU.

Baselines.

  1. 1.

Vanilla. $\mathbb{E}[Y|\boldsymbol{x}]$ is implemented by the same neural
network as $f_{S^{\prime}}$.

  2. 2.

ICP (https://github.com/juangamella/icp). The level of the test procedure is
set to $0.05$. The estimator is implemented by the same neural network as
$f_{S^{\prime}}$.

  3. 3.

IC (https://github.com/mrojascarulla/causal_transfer_learning). The level of
the test procedure is set to $0.05$. Levene test is used. The estimator is
implemented by the same neural network as $f_{S^{\prime}}$.

  4. 4.

DRO (https://github.com/duchi-lab/certifiable-distributional-robustness). The
$\gamma$ is set to $2$. The estimator is implemented by the same neural
network as $f_{S^{\prime}}$.

  5. 5.

Surgery estimator. Since there is no official implementation available, we
implement it based on our method. Specifically, we pick $2\sim 3$ validation
environments from $\mathcal{E}_{\text{tr}}$ and use the validation loss to
select $S^{*}$.

  6. 6.

IRM (https://github.com/facebookresearch/InvariantRiskMinimization). The best
$\phi$ is chosen by comparing the validation loss of
$\mathrm{reg}=0,10^{-5},10^{-4},10^{-3},10^{-2},10^{-1}$.

  7. 7.

HRM (https://github.com/LhSthu/HRM). The cluster number is set to the number
of deployment environments. $\sigma$ and $\lambda$ are both set to $0.1$. The
overall threshold for subset selection is set to $0.25$.

  8. 8.

IB-IRM (https://github.com/ahujak/IB-IRM). The $\lambda_{\text{ib}}$ is set to
$0.1$, the $\lambda_{\text{irm}}$ is set to $0.75$. The estimator is
implemented by the same neural network as $f_{S^{\prime}}$.

  9. 9.

Anchor regression (https://github.com/rothenhaeusler/anchor-regression). The
$\gamma$ is set to $1.5$.

Synthetic study. The neural networks to implement $f_{S^{\prime}}$ and
$h_{\theta}$ are two-layers MLPs. We use a sigmoid activation function in the
hidden layer to add non-linearity. We use the Adam optimizer. The learning
rate is set to $0.02$, and epochs are set to $10000$ with an early stop.

Alzheimer’s disease diagnosis. The neural networks to implement
$f_{S^{\prime}}$ and $h_{\theta}$ are the same as the synthetic study. We use
the SGD optimizer. For the estimation of $f_{S^{\prime}}$, the epochs are set
to $5000$, the learning rate is set to $0.25$ in the first $4000$ epochs, and
decreased to $0.1$ in the last $1000$ epochs. For the estimation of
$\mathcal{L}$, the epochs are set to $12000$ with an early stop, the learning
rate is set to $0.4$.

Gene function prediction. The neural networks to implement $f_{S^{\prime}}$
and $h_{\theta}$ are the same as the synthetic study. We use the SGD
optimizer. The epochs are set to $10000$. For the estimation of
$f_{S^{\prime}}$, the learning rate is set to $0.01$. For the estimation of
$\mathcal{L}$, the learning rate is set to $0.05$.

Figure 8: The synthetic causal graphs for complexity analysis. Stable and mutable variables are respectively marked blue and red. We have $d_{>2}=1,2,5,6$ in (a), (b), (c), (d), respectively. The sparse graphs (a), (b) are generated by deleting edges from Fig. 4 (a). The dense graphs (c), (d) are generated by adding edges to Fig. 4 (a). Table 4: Indices for brain region partition. Abbreviation | Brain region | AAL index (Tzourio-Mazoyer et al., 2002)
---|---|---
FSL | Frontal superior lobe | 2101,2102,2111,2112,2601,2602
FML | Frontal middle lobe | 2201,2202,2211,2212,2611,2612
FIL | Frontal inferior lobe | 2301,2302,2311,2312,2321,2322
TSL | Temporal superior lobe | 8111,8112
TML | Temporal medial lobe | 8201,8202
TIL | Temporal inferior lobe | 8301,8302
TP | Temporal pole | 8121,8122,8211,8212
PSL | Parietal superior lobe | 6101,6102
PIL | Parietal inferior lobe | 6201,6202
OSL | Occipital superior lobe | 5101,5102
OML | Occipital middle lobe | 5201,5202
OIL | Occipital inferior lobe | 5301,5302
CA | Cingulum anterior | 4001,4002
CM | Cingulum middle | 4011,4012
CP | Cingulum posterior | 4021,4022
INS | Insula | 3001,3002
AMY | Amygdala | 4201,4202
CAU | Caudate | 7001,7002
HP | Hippocampus | 4101,4102
PAL | Pallidum | 7021,7022
PUT | Putamen | 7011,7012
THA | Thalamus | 7101,7102

###  F.2 Extra results

Table 5: Max. MSE evaluation on synthetic and IMPC datasets. The first column
notes the methods we compare. The second column represents the max. MSE over
deployment environments. Data for Syn-a,b,c,d are respectively generated by
the causal graphs (a) ,(b), (c), and (d) shown in Fig. 8. The best results are
boldfaced.

Method | max. MSE ($\downarrow$)
---|---
Syn-a | Syn-b | Syn-c | Syn-d | IMPC
Vanilla | $15.946_{\pm 2.7}$ | $3.033_{\pm 2.7}$ | $5.613_{\pm 3.5}$ | $1.814_{\pm 0.4}$ | $1.227_{\pm 0.1}$
ICP (Peters et al., 2016) | $1.777_{\pm 0.6}$ | $1.629_{\pm 0.6}$ | $1.631_{\pm 0.6}$ | $1.097_{\pm 0.1}$ | $1.291_{\pm 0.3}$
IC (Rojas-Carulla et al., 2018) | $5.580_{\pm 0.3}$ | $1.631_{\pm 0.4}$ | $2.322_{\pm 0.7}$ | $1.665_{\pm 0.3}$ | $1.253_{\pm 0.2}$
DRO (Sinha et al., 2018) | $4.511_{\pm 1.8}$ | $1.628_{\pm 0.4}$ | $2.311_{\pm 0.7}$ | $1.827_{\pm 0.4}$ | $1.196_{\pm 0.1}$
Surgery (Subbaswamy et al., 2019) | $1.325_{\pm 0.0}$ | $1.086_{\pm 0.0}$ | $1.005_{\pm 0.1}$ | $1.190_{\pm 0.2}$ | $1.071_{\pm 0.1}$
IRM (Arjovsky et al., 2019) | $6.328_{\pm 2.3}$ | $1.439_{\pm 0.2}$ | $3.067_{\pm 0.9}$ | $1.601_{\pm 0.5}$ | $1.296_{\pm 0.1}$
HRM (Liu et al., 2021) | $4.511_{\pm 1.8}$ | $1.537_{\pm 0.4}$ | $1.019_{\pm 0.0}$ | $1.427_{\pm 0.3}$ | $1.205_{\pm 0.1}$
IB-IRM (Ahuja et al., 2021) | $1.194_{\pm 0.0}$ | $1.177_{\pm 0.0}$ | $1.111_{\pm 0.1}$ | $1.108_{\pm 0.0}$ | $1.288_{\pm 0.1}$
AncReg (Rothenhäusler et al., 2021) | $1.482_{\pm 0.4}$ | $\mathbf{1.032_{\pm 0.0}}$ | $1.117_{\pm 0.7}$ | $1.631_{\pm 0.5}$ | $1.127_{\pm 0.1}$
Ours (Alg. 1) | $\mathbf{1.037_{\pm 0.0}}$ | $1.046_{\pm 0.0}$ | $\mathbf{0.689_{\pm 0.0}}$ | $\mathbf{1.067_{\pm 0.0}}$ | $\mathbf{0.952_{\pm 0.0}}$

Table 6: Std. MSE evaluation on synthetic and IMPC datasets. The first column
notes the methods we compare. The second column represents the max. MSE over
deployment environments. Data for Syn-a,b,c,d are respectively generated by
the causal graphs (a) ,(b), (c), and (d) shown in Fig. 8. The best results are
boldfaced.

Method | std. MSE ($\downarrow$)
---|---
Syn-a | Syn-b | Syn-c | Syn-d | IMPC
Vanilla | $3.184_{\pm 1.2}$ | $0.552_{\pm 0.5}$ | $1.543_{\pm 1.0}$ | $0.463_{\pm 0.3}$ | $0.257_{\pm 0.0}$
ICP (Peters et al., 2016) | $0.132_{\pm 0.1}$ | $0.145_{\pm 0.0}$ | $0.219_{\pm 0.1}$ | $0.055_{\pm 0.0}$ | $0.289_{\pm 0.1}$
IC (Rojas-Carulla et al., 2018) | $0.421_{\pm 0.0}$ | $0.324_{\pm 0.2}$ | $0.635_{\pm 0.4}$ | $0.376_{\pm 0.1}$ | $0.302_{\pm 0.1}$
DRO (Sinha et al., 2018) | $0.329_{\pm 0.1}$ | $0.321_{\pm 0.2}$ | $0.633_{\pm 0.4}$ | $0.474_{\pm 0.3}$ | $0.266_{\pm 0.0}$
Surgery (Subbaswamy et al., 2019) | $0.367_{\pm 0.0}$ | $0.071_{\pm 0.0}$ | $0.147_{\pm 0.0}$ | $0.101_{\pm 0.1}$ | $0.237_{\pm 0.0}$
IRM (Arjovsky et al., 2019) | $1.560_{\pm 0.7}$ | $0.205_{\pm 0.1}$ | $0.803_{\pm 0.4}$ | $0.369_{\pm 0.3}$ | $0.319_{\pm 0.1}$
HRM (Liu et al., 2021) | $0.328_{\pm 0.1}$ | $0.280_{\pm 0.2}$ | $\mathbf{0.011_{\pm 0.0}}$ | $0.195_{\pm 0.1}$ | $0.278_{\pm 0.0}$
IB-IRM (Ahuja et al., 2021) | $0.104_{\pm 0.0}$ | $0.063_{\pm 0.0}$ | $0.082_{\pm 0.0}$ | $\mathbf{0.055_{\pm 0.0}}$ | $0.259_{\pm 0.0}$
AncReg (Rothenhäusler et al., 2021) | $0.210_{\pm 0.1}$ | $\mathbf{0.030_{\pm 0.0}}$ | $0.285_{\pm 0.3}$ | $0.410_{\pm 0.3}$ | $0.275_{\pm 0.0}$
Ours (Alg. 1) | $\mathbf{0.034_{\pm 0.0}}$ | $0.043_{\pm 0.0}$ | $0.073_{\pm 0.0}$ | $0.062_{\pm 0.0}$ | $\mathbf{0.017_{\pm 0.0}}$

Table 7: Std. over equivalent subsets on synthetic and IMPC datasets. Data for
Syn-a,b,c,d are respectively generated by the causal graphs (a) ,(b), (c), and
(d) shown in Fig. 8.

Metric | Dataset
---|---
Syn-a | Syn-b | Syn-c | Syn-d | IMPC
Inter-class std. | 0.118 | 1.178 | 0.697 | 1.668 | 0.288
Intra-class std. | 0.005 | 0.017 | 0.001 | 0.015 | 0.023

Figure 9: Detailed results for Fig. 5. (a) and (b) respectively show the max.
MSE of all the 256 subsets for Fig. 5 (a) and (b). Figure 10: Results on
synthetic data. (a), (b), (c), and (d) respectively show the max. MSE of the
first 100 subsets ranked respectively according to our method and the
validation‘s loss, with data generated by the causal graphs in Fig. 8 (a),
(b), (c), and (d). Detailed results of all the 256 subsets are shown in (a.1),
(b.1), (c.1), and (d.1), respectively.

####  F.2.1 Gene function prediction

In this section, we evaluate our method on gene function prediction, which can
potentially help better understand the human-disease progress (Muñoz-Fuentes
et al., 2018).

Figure 11: Gene function prediction. (a) The learned causal graph, where
$\leftrightarrow$ denotes undirected edges. (b) Comparison of max. MSE over
deployed environments. (c) Max. MSE of subsets that are ranked respectively
according to the estimated worst-case risk of our method and the validation’s
loss.

Dataset. We consider the International Mouse Phenotyping Consortium (IMPC)
dataset111111http://www.crm.umontreal.ca/2016/Genetics16/competition_e.php
that was originally published in a causal inference challenge and later used
as a benchmark for domain generalization (Magliacane et al., 2018). The IMPC
contains the hematology phenotypes of both wild-type mice and mutant mice with
$13$ kinds of single-gene knockout. To predict the gene function, we knock out
this gene and assess the cell counts of monocyte (MON), with cell counts of
neutrophil (NEU), lymphocyte (LYM), eosinophil (EO), basophil (BA), and large
unstained cell (LUC) as covariates. We use the kind of knocked-out gene to
divide environments. The training environments contain wild-type mice and five
randomly picked gene knockouts. The deployed environments contain the rest
nine kinds of gene knockouts. This random train-test split is repeated $45$
times.

Causal discovery and $\mathrm{Pow}(S)/\\!\sim_{G}$ recovery. The learned
causal graph is shown in Fig. 11 (a). As we can see, we have
$\text{LUC}\to\text{LYM}$ and $\text{LYM}\to\text{BA}$, which respectively
echo the existing studies that monocyte can activate the lymphocyte (Carr et
al., 1994) and increase the number of LUC (Lee et al., 2021), and that the
lymphocyte participates in activating basophil (Goetzl et al., 1984). Since
MON is mutable and $\text{LYM}\in\mathbf{De}(\text{MON})$ is pointed by LUC,
the condition in Thm. 4.1 is violated. We need to compare the equivalence
classes to find the optimal subset. Applying Alg. 2, we find that there are
$12$ equivalence classes out the $2^{4}$ subsets ($d_{S}|=4$ as shown in Fig.
11 (a)).

Results. Fig. 11 (b) and Tab. 5, 6 respectively report the max. MSE and std.
MSE of our method and baselines. As we can see, our method can outperform the
others by a significant margin. Besides, Fig. 11 (c) shows that our
$\mathcal{L}$ can well reflect the worst-case risk.

Analysis of $\sim_{G}$ equivalence. We compute the intra-class std. versus the
inter-class std. The results are shown in Tab. 7 (IMPC), which show that
equivalence subsets have comparable max. MSE.