# Cost-constrained Minimal Steiner Tree Enumeration by Binary Decision Diagram

Yuya Sasaki Osaka university<EMAIL_ADDRESS>
###### Abstract

The Steiner tree enumeration problem is a well known problem that asks for
enumerating Steiner trees. Numerous theoretical works proposed algorithms for
the problem and analyzed their complexity, but there are no practical
algorithms and experimental studies. In this paper, we study the Steiner tree
enumeration problem practically. We define a problem cost-constrained minimal
Steiner tree enumeration problem, which enumerates minimal Steiner trees with
costs not larger than a given threshold. To solve the problem, we propose a
binary decision diagram (BDD)-based algorithm. The BDD-based algorithm
constructs a BDD that compactly represents the set of minimal Steiner trees
and then traverses the BDD for enumeration. We develop a novel frontier-based
algorithm to efficiently construct BDDs. Our BDD traverse algorithm prunes
Steiner trees with costs larger than the threshold. We also extend our
algorithm by preprocessing the given graph and controlling the number of
generated Steiner trees in order to reduce the memory and computation costs.
The extension makes our algorithm scalable by generating a subset of the
minimal Steiner trees. We validate that our algorithm can enumerate Steiner
trees in real-world graphs more efficiently than existing methods.

##  1 Introduction

The Steiner tree problem is one of the most classic and fundamental problems
for graph analysis Dreyfus and Wagner (1971). The problem asks for the
minimum-cost Steiner tree which is a subtree that connects an arbitrary subset
of vertices (called terminals) in a given graph. The Steiner tree problem
emerges in numerous applications such as a design of VLSI, network routing,
road network construction, and wire length estimation Hwang and Richards
(1992) though it is known as NP-hard problem Garey and Johnson (1979).

The minimum-cost Steiner tree may not be the best solution in real-world
applications because the applications implicitly may have constraints that
Steiner trees should have. It is possible to add such constraints to objective
functions but it is often difficult to formalize them. For example, let us
consider a road network construction. Road networks are modeled by graphs
whose vertices represent intersections/facilities and edges represent road
segments. For robustness to disasters such as earthquakes and flooding, users
often want to know Steiner trees such that roads are “not very close” to each
other Tsompanakis et al. (2008). However, it is difficult to set an
appropriate distance threshold and/or formalize distances between edges.

The Steiner tree enumeration problem is a problem that asks for enumerating
Steiner trees in a given graph Dourado et al. (2014); Kimelfeld and Sagiv
(2008). We can find a suitable Steiner tree from enumerated Steiner trees. The
problem is theoretically studied well in terms of time and memory complexity.
However, to the best of our knowledge, there do not exist practical algorithms
and experimental studies. To practically solve the Steiner tree enumeration
problem, we can use (approximate or exact) algorithms for the Steiner tree
problem. In more concretely, a straightforward method for enumerating Steiner
trees is that iteratively (1) runs algorithms to generate Steiner trees and
(2) modify a given graph to avoid obtaining the same Steiner tree, until
enumerating all Steiner trees. The straightforward method has two issues; (1)
how to modify the graph for enumerating Steiner trees and (2) when the method
can be terminated. We need a practical problem definition and efficient
methods.

In this paper, we initiate a new problem for enumerating Steiner trees, which
we call cost-constrained minimal Steiner tree enumeration problem. The problem
asks for enumerating minimal Steiner trees with costs not larger than a given
threshold. We theoretically show the problem is $\\#$P-hard problem. For
efficient enumeration, we propose a novel algorithm that enumerates Steiner
trees by using binary decision diagram (BDD for short). BDD is a well-known
data structure for effective enumeration of discrete data including graphs.
Our BDD-based algorithm has two steps; constructing a BDD and traversing the
constructed BDD. For the first step, we develop a novel frontier-based
algorithm to efficiently construct BDDs that compactly represent the set of
minimal Steiner trees. The frontier-based algorithm effectively reduces the
size of BDDs by using functions tailored for the Steiner tree enumeration
problem. After constructing a BDD, we traverse the BDD to obtain the set of
Steiner trees while pruning the Steinter trees with larger costs than the
threshold.

It is generally difficult to construct BDDs for large-scale graphs due to time
and space complexity. Recent works for enumerating subgraphs showed that
computational costs and memory usage become significantly large even for
graphs with few hundred edges Maehara et al. (2017); Sasaki et al. (2019).
Thus, we restrict the number of generated Steiner trees by applying
preprocessing techniques and extending the traverse algorithm. The
preprocessing technique reduces the size of graph by using existing algorithms
for the Steiner tree problem. The traverse algorithm enumerates the Steiner
trees with the $k$ smallest costs among Steiner trees on preprocessed graphs,
where $k$ is a user-specified parameter. The extension makes our algorithm
scalable by generating a subset of the minimal Steiner trees.

We conduct computational experiments to evaluate our BDD-based algorithm by
using nine real graphs. We show that our algorithm efficiently enumerates
Steiner trees compared with graph traversal-based and solver-based methods.
Furthermore, the enumerated Steiner trees have costs close to the optimal
cost.

##  2 Preliminaries

We describe the notations and definitions used in this paper.

###  2.1 Definitions and Notations

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be an undirected, weighted, and
connected graph, where $\mathcal{V}$ and
$\mathcal{E}=\mathcal{V}\times\mathcal{V}$ are sets of vertices and edges,
respectively. Each edge $e$ has a non-negative weights $c(e)$. Each vertex has
an unique integer $v$ as its identifier.

######  Definition 1 (Steiner Tree).

A subset of edges $\mathcal{S}\subseteq\mathcal{E}$ spanning a given set of
terminals $\mathcal{T}\subseteq\mathcal{V}$ without cycles is called a Steiner
tree, and the cost of $\mathcal{S}$ is
$c(\mathcal{S})=\sum_{e\in\mathcal{S}}c(e)$.

Given Steiner tree $\mathcal{S}$, a subgraph $\mathcal{S}\cup e$ could be a
Steiner tree. However, the subgraph is meaningless if we know $\mathcal{S}$
already. We define minimal Steiner tree as follows:

######  Definition 2 (Minimal Steiner tree).

Given Steiner tree $\mathcal{S}$, $\mathcal{S}$ is a minimal Steiner tree if
and only if there are no $e$ in $\mathcal{S}$ such that $\mathcal{S}\backslash
e$ is a Steiner tree.

We here note that Steiner trees whose all leaves are terminals are minimal.

######  Definition 3 (Steiner tree problem).

Giving a graph and a set of terminals, the Steiner tree problem asks for the
Steiner tree with the minimum cost.

###  2.2 Binary Decision Diagram

To maintain exponentially numerous subgraphs, we can use the binary decision
diagram (BDD), which is a data structure to represent a Boolean function
compactly.

A BDD $\mathcal{D}=(\mathcal{N},\mathcal{A})$ is a directed acyclic graph with
sets of nodes $\mathcal{N}$ and arcs $\mathcal{A}$111To avoid confusion, we
use the terms “vertex” and “edge” to refer to a vertex and an edge in a graph,
respectively, and “node” and “arc” to refer to a vertex and an edge in a BDD,
respectively.. It has two nodes that have no outgoing arcs, called sink nodes.
The sink nodes are of two types, called 1-sink and 0-sink. Additionally, it
has a single node that has no incoming arcs, called the root node. Each node
(except for sink nodes) has two outgoing arcs, called the 0-arc and 1-arc.
Each node is assigned a variable, and 0-arc and 1-arc indicate that the
variable of the node is false and true, respectively. We call the set of
descendent nodes through $x$-arc from node $n$ as $x$-descendants of $n$.

Paths from the root node to the 1-sink and 0-sink represent variable
assignments that a given Boolean function is true and false, respectively. In
the contexts of graph enumeration, each variable represents an edge. A path
from the root node to the 1-sink represents a constrained subgraph that is
represented by a Boolean function.

The size of the BDD is defined by the number of nodes in the BDD Hardy et al.
(2007). Generally, it exponentially increases as edges in the graphs increase.
As the sizes of graphs increase, both of the computation cost and the memory
usage exponentially increase. Thus, it is difficult to construct BDD on large-
scale graphs.

##  3 Proposal

We aim at enumerating minimal Steiner trees instead of finding the optimal
Steiner tree. We define a new problem that we solve in this paper as follows:

Problem definition (Cost-constrained Minimal Steiner Tree Enumeration Problem)
Given a weighted undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, a
subset of its vertices $\mathcal{T}\subseteq\mathcal{V}$, and a positive
threshold $\theta$, the cost-constrained minimal Steiner enumeration problem
asks for enumerating minimal Steiner trees whose costs are not larger than
$\theta$.

The Steiner tree problem is known as NP-hard problem. While, the minimal
Steiner tree enumeration problem is $\\#P$-hard problem as follows:

######  Theorem 1.

The minimal Steiner tree enumeration problem is $\\#P$-hard problem.

Proof sketch: We reduce the enumeration of $s$-$t$ simple pats Valiant (1979)
which is $\\#P$-hard problem to the minimal Steiner tree enumeration problem.
The minimal Steiner tree enumeration problem can formulate the enumeration of
$s$-$t$ simple paths. Given two vertices as terminals, the minimal Steiner
tree enumeration problem is equivalent to the enumeration of $s$-$t$ simple
paths. Therefore, the minimal Steiner tree enumeration problem is $\\#$P-hard
problem. $\square$

In the following, we show an overall idea of our algorithm. Then, we present
our techniques; BDD construction, BDD traversal, and preprocessing methods.

###  3.1 Overall Idea

For thoroughly enumerating minimal Steiner trees, we need to search for the
minimum-cost Steiner trees on all possible graphs, which are subgraphs of a
given original graph. This is equivalent to find all variable assignments for
which the Boolean function representing minimal Steiner trees is true. Since
the BDD can efficiently and compactly represent the Boolean function, it is
suitable for enumerating minimal Steiner trees. There are no studies on BDDs
for enumerating minimal Steiner trees, and thus we design a novel algorithm
for constructing the BDD.

After constructing BDDs, we traverse the constructed BDDs to enumerate the
minimal Steiner trees. Since BDDs may include minimal Steiner trees with costs
larger than the threshold, our traversal algorithm prunes such Steiner trees
on demand.

###  3.2 BDD Construction Method

Our BDD construction method is a type of frontier-based search, which is a
general construction algorithm for enumerating all constrained subgraphs
Kawahara et al. (2017); Maehara et al. (2017). The frontier-based search is
applied to many types of subgraphs such as trees, connected graphs, and paths,
but not for minimal Steiner trees. The pseudo-code of BDD construction method
is in appendix.

We extend the frontier-based search for enumerating minimal Steiner trees. The
non-trivial challenge is how to design functions and frontier information of
the frontier-based algorithm to reduce the size of BDD with keeping accurate
Steiner tree enumeration. We first describe the framework of the frontier-
based search and then each function.

Frontier-based search: The frontier-based search generates nodes of BDDs one
by one. We fix ordering of edges ($e_{1},\ldots,e_{|\mathcal{E}|}$) before
constructing BDD and process the edges following the order. The processed and
unprocessed edges at the end of $i$-th step are denoted by $E^{\leq
i}:=\\{e_{1},\ldots,e_{i}\\}$ and
$E^{>i}:=\\{e_{i+1},\ldots,e_{|\mathcal{E}|}\\}$, respectively. The set of
vertices that have both processed and unprocessed edges is called the frontier
(at the $i$-th step) and denoted by $\mathcal{F}_{i}$.

We consider all minimal Steiner trees $\mathcal{M}$. The set of nodes at
$i$-th step $\mathcal{N}_{i}$ represents all subsets of $E^{\leq i}$ that can
possibly belong to $\mathcal{M}$. $\mathcal{M}(n)$ denotes the set of edges
that can possibly belong to $\mathcal{M}$ represented by node $n$. A path from
the root node to $n$ represents a subgraph in which edges are present if the
path descends the 1-arc of nodes associated with edges.

At the $i$-th step, the algorithm generates $\mathcal{N}_{i}$ from
$\mathcal{N}_{i-1}$. For each node $n\in\mathcal{N}_{i-1}$, the frontier-based
search generates two children for which $e_{i}$ is excluded or included in the
sets in $\mathcal{M}$ by generateNode function. Generated nodes in
$\mathcal{N}_{i}$ can be merged if the descendants of the nodes go to the same
sinks for any patterns of $E^{>i}$ by mergeNode function. In addition, the
frontier-based algorithm has two functions isZeroSink and isOneSink to
determine $x$-descendants of $n$ do not satisfy and do satisfy minimal Steiner
trees, respectively, which output either true or false according to $x$ and
information of $n$.

In the following, we present an extension of the frontier-based algorithm for
minimal Steiner trees. We first explain information held at each node, and
then explain four functions; generateNode, mergeNode, isZeroSink, and
isOneSink.

Frontier information: Our BDD captures the characteristics of minimal Steiner
trees for efficient enumeation. Minimal Steiner trees are subgraphs that (1)
connect all terminals (i.e. connectivity), (2) do not have cycles (i.e.,
tree), and (3) do not have edges that the subgraphs without the edges satisfy
both (1) and (2) (i.e., minimality). Additionally, we aim to enumerate Steiner
trees with costs not larger than $\theta$. Based on the above constraints, we
design the information at node $n\in\mathcal{N}_{i}$ as follows:

  * •

Identifier $id_{n}(f)$ for all $f\in\mathcal{F}_{i}$: If frontiers $f$ and
$f^{\prime}$ are connected by processed edges, $id_{n}(f)$ and
$id_{n}(f^{\prime})$ share the same identifier.

  * •

Unprocessed edge $u_{n}(f)$ for all $f\in\mathcal{F}_{i}$: The sum of the
numbers of unprocessed edges connected to the frontiers such that
$\\{f\in\mathcal{F}_{i}|id_{n}(f)=id_{n}(f^{\prime})\\}$.

  * •

Terminal $t_{n}(f)$ for all $f\in\mathcal{F}_{i}$: The number of terminals
that are connected to $f$ by processed edges.

  * •

Degree $d_{n}(f)$ for all $f\in\mathcal{F}_{i}$: The number of present edges
that are connected to $f$.

  * •

Cost $c_{n}$: The cost of the subgraph corresponding to $n$.

We here note that if $id_{n}(f)=id_{n}(f^{\prime})$, we hold that
$u_{n}(f)=u_{n}(f^{\prime})$ and $t_{n}(f)=t_{n}(f^{\prime})$ because $f$ and
$f^{\prime}$ are connected by processed edges. The information fulfills to
check whether subgraphs represented by $n$ satisfy the conditions of minimal
Steiner trees or never satisfy the conditions even after processing $E^{>i}$.
We extend generateNode, mergeNode, isZeroSink, and isOneSink functions based
on the information. In the following, let us assume that we process edge
$e_{i}$ that connects to $v$ and $v^{\prime}$.

generateNode function: The generateNode function is to generate new nodes at
$i$-th step and compute the information of the new nodes. The information of
new node $n^{\prime}$ is first copied from its parent nodes $n$ and then
updates according to that $e_{i}$ is either included or excluded.

We describe the detailed procedures in each case that $e_{i}$ is included and
excluded. As a common procedure, we add (resp. delete) the information for new
(resp. old) frontier if a vertex is added to (resp. deleted from) frontiers.
The information on the new frontier is derived from the graph. In the
following, we assume that both $v$ and $v^{\prime}$ are frontiers. If they are
not frontiers, we can just ignore the updating of information related to them.
When we exclude $e_{i}$, we decrease $u_{n}(v)$ and $u_{n}(v^{\prime})$ by
one. When we include $e_{i}$, we update the information as follows:
$id_{n^{\prime}}(v)=min(v,v^{\prime})$,
$u_{n^{\prime}}(v)=u_{n}(v)+u_{n}(v^{\prime})-2$,
$d_{n^{\prime}}(v)=d_{n}(v)+1$, and $c_{n^{\prime}}=c_{n}+c(e_{i})$.
Similarly, we update the information related to $v^{\prime}$.

mergeNode function: The mergeNode function computes whether two nodes can be
merged or not. Descendants of merged nodes go to the same 0-sink and 1-sink
for any patterns of $E^{>i}$. If two nodes $n$ and $n^{\prime}$ in
$\mathcal{N}_{i}$ have the following information, we merge $n$ and
$n^{\prime}$.

######  Lemma 1.

Two nodes $n$ and $n^{\prime}$ in $\mathcal{N}_{i}$ are merged if they have
the following information: for all $f\in\mathcal{F}_{i}$,
$id_{n}(f)=id_{n^{\prime}}(f)$, ($t_{n}(f)>0$ and $t_{n^{\prime}}(f)>0$) or
($t_{n}(f)=0$ and $t_{n^{\prime}}(f)=0$), and $d_{n}(f)=d_{n^{\prime}}(f)$.

Proof: We prove the theorem by each condition. First, if
$id_{n}(f)=id_{n^{\prime}}(f)$, sets of connected frontiers on $n$ and
$n^{\prime}$ are same. Descendants of $n$ and $n^{\prime}$ are similarly
connected all frontiers after $i$-th step. Second, if ($t_{n}(f)>0$ and
$t_{n^{\prime}}(f)>0$) or ($t_{n}(f)=0$ and $t_{n^{\prime}}(f)=0$), frontiers
that must be connected are the same in order to connect all terminals. Third,
if $d_{n}(f)=d_{n^{\prime}}(f)$, both descendants of $n$ and $n^{\prime}$
become either minimal or not minimal after $i$-th step. If $n$ and
$n^{\prime}$ satisfy three conditions, these descendants go to the same sinks
for any patterns of $E^{>i}$. Therefore, we can merge two nodes without
missing any minimal Steiner trees. $\square$

If two nodes are merged, we use frontier information at either node $n$ or
$n^{\prime}$. While, $c_{n}$ is updated to the smaller ones of $c_{n}$ and
$c_{n}^{\prime}$ to avoid false-negative of $\mathcal{M}$. That is, if $c_{n}$
is updated to the larger one, some Steiner trees may be discarded due to
overestimating the costs of Steiner trees. On the other hand, our update may
include false-positive due to underestimating costs, but we can remove such
Steiner trees during traversing BDDs.

isZeroSink and isOneSink functions: If subgraphs represented by nodes satisfy
the conditions of minimal Steiner tree, the nodes should point at 1-sink.
Similarly, if subgraphs represented by nodes do not satisfy the conditions of
minimal Steiner tree ever, they should point at 0-sink. We design isOneSink
and isZeroSink functions to determine whether child nodes of $n$ are 1- and
0-sinks, or not. We explain ${\sf isOneSink}(n,e_{i},x)$ and ${\sf
isZeroSink}(n,e_{i},x)$ such that $x$-arc from node $n$ that is assigned
$e_{i}$ point at whether 1-sink and 0-sink or not, respectively.

First, the isOneSink function is designed as follows:

${\sf isOneSink}(n,e_{i},1)=\left\\{\begin{array}[]{ll}true&\exists
f\in\mathcal{F}_{i}~{}~{}t_{n}(f)=|\mathcal{T}|\\\
false&otherwise\end{array}\right.$

${\sf isOneSink}(n,e_{i},0)$ is always false because if $e_{i}$ is excluded,
all terminals are not connected on $n$ at $i$-th step. Intuitively, isOneSink
function checks whether the all terminals are connected

There are several conditions of the isZeroSink function, so we list the case
that isZeroSink is true;

${\sf isZeroSink}(n,e_{i},1)$ becomes true if one of the followings satisfies;

  * •

$id_{n}(v)=id_{n}(v^{\prime})$,

  * •

$v\notin\mathcal{F}_{i}$, $d_{n}(v)=0$ and $v\notin\mathcal{T}$ (similarly,
for $v^{\prime}$), and

  * •

$c_{n}+c(e_{i})>\theta$.

${\sf isZeroSink}(n,e_{i},0)$ becomes true if one of the followings satisfies;

  * •

$v\not\in\mathcal{F}_{i}\cup\mathcal{F}_{i-1}$ and $v\in\mathcal{T}$
(similarly, for $v^{\prime}$),

  * •

$t_{n}(v)>0$ and $u_{n}(v)=1$ (similarly, for $v^{\prime}$), and

  * •

$v\notin\mathcal{F}_{i}$, $d_{n}(v)=1$ and $v\notin\mathcal{T}$ (similarly,
for $v^{\prime}$).

Intuitively, isZeroSink function checks whether (1) terminals are
disconnected, (2) subgraphs have cycle, and (3) subgraphs are not minimal.
isOneSink and isZeroSink functions help to reduce the number of nodes in the
BDD. We here note that both functions are true at the same time.

######  Lemma 2.

${\sf isOneSink}(n,e_{i},x)$ and ${\sf isZeroSink}(n,e_{i},x)$ functions are
true if $x$-arc from node $n$ that is assigned $e_{i}$ satisfies and does not
satisfy conditions of minimal Steiner trees, respectively.

Proof: Remind that we obtain subgraphs by traversing from the root node to
$n$. If $x$ is 1, we add edge $e_{i}$ to the subgraphs and if $x$ is 0, we
delete $e_{i}$ from the subgraphs. If the subgraphs are minimal Steiner trees,
they satisfy conditions that (1) connect all terminals (i.e., connectivity),
(2) do not have cycles (i.e., tree), and (3) do not have edges that if the
edges are deleted, subgraphs satisfy both (1) and (2) (i.e., minimality).

We consider the four cases; (a) ${\sf isOneSink}(n,e_{i},0)$, (b) ${\sf
isOneSink}(n,e_{i},1)$, (c) ${\sf isZeroSink}(n,e_{i},0)$, and (d) ${\sf
isZeroSink}(n,e_{i},1)$. We assume that $e_{i}=(v,v^{\prime})$ and $g$ are
subgraphs represented by $n$ with/without $e_{i}$. We prove each case if we
add $e_{i}=(v,v^{\prime})$.

  * •

${\sf isOneSink}(n,e_{i},1)$: If the number of terminals connected to $f$, the
connectivity satisfies. Here, $g$ satisfies both the tree and minimality
conditions; if $g$ has cycles due to $e_{i}$, new terminals are not connected
to $f$ additionally, and $g$ is minimal because $g$ is not Steiner trees
without $e_{i}$.

  * •

${\sf isOneSink}(n,e_{i},0)$: ${\sf isOneSink}(n,e_{i},0)$ is always false
because $g$ does not satisfy the connectivity condition.

  * •

${\sf isZeroSink}(n,e_{i},1)$:

    * –

If $id_{n}(v)=id_{n}(v^{\prime})$, $g$ has cycle because $v$ and $v^{\prime}$
are already connected by different paths on the graph. Thus, $g$ does not
satisfy the tree condition.

    * –

If $v\notin\mathcal{F}_{i}$ and $d_{n}(v)=0$, $v$ becomes a leaf vertex of $g$
after adding $e_{i}$. If $v$ is not terminals, $g$ could be Steiner tree
without $e_{i}$. Thus, $g$ does not satisfy the minimality condition.

    * –

If $c_{n}+c(e_{i})>\theta$, $g$ does not satisfy cost-constraint.

  * •

${\sf isZeroSink}(n,e_{i},0)$:

    * –

If $v\not\in\mathcal{F}_{i}\cup\mathcal{F}_{i-1}$, $v$ has a single edge
because $v$ does not become frontiers after and before processing $e_{i}$.
Thus, if $v$ is terminals and $e_{i}$ is deleted, $g$ does not satisfy the
connectivity condition.

    * –

If $t_{n}(v)>0$ and $u_{n}(v)=1$, $v$ is not connected to other vertices ever.
Thus, $g$ does not satisfy the connectivity condition.

    * –

If $v\notin\mathcal{F}_{i}$ and $d_{n}(v)=1$, $v$ becomes a leaf vertex of $g$
after deleting $e_{i}$. If $v$ is not terminals, $g$ could be Steiner tree
without $e_{i}$. Thus, $g$ does not satisfy the minimality condition.

$\square$

Pseudo code for BDD construction method: Algorithm 1 shows pseudo code for the
BDD consruction method presented in Section 4.2. The algorithm constructs the
BDD by generating nodes from $\mathcal{N}_{1}$ to
$\mathcal{N}_{|\mathcal{E}|}$ (line 4). For each node in $\mathcal{N}_{i-1}$,
it generates two nodes (lines 5–6). If nodes satisfy isOneSink and isZeroSink,
node $\alpha$ points at 1- and 0-sinks, respectively (lines 7–10). Otherwise,
it generates $\alpha_{x}$ by generateNode (line 12). If $\alpha_{x}^{\prime}$
is included in $\mathcal{N}_{i}$, it merges $\alpha_{x}$ and
$\alpha_{x}^{\prime}$ by mergeNode (lines 13-14). We here note that we use
hash functions for efficiently checking whether there is $\alpha_{x}^{\prime}$
that satisfy lemma 1. Finally, we add nodes and arcs to $\mathcal{N}_{i}$ and
$\mathcal{A}$, respectively (lines 16–17).

Input : Graph $\mathcal{G}$, threshold $\theta$

Output : BDD $\mathcal{D}=(\mathcal{N},\mathcal{A})$

1 procedure Construction Algorithm

2 order edges;

3 $\mathcal{N}_{0}\leftarrow$ $\\{root\\}$, $\mathcal{N}_{i}\leftarrow$ $\phi$
for $i=1,2,\ldots,|\mathcal{E}|$;

4 for  _$i=1,2,\ldots,|\mathcal{E}|$_ do

5 foreach  _$\alpha\in\mathcal{N}_{i-1}$_ do

6 foreach  _$x\in\\{0,1\\}$_ do

7 if  _${\sf isOneSink}(n,e_{i},x)$_ then

8 $\alpha_{x}\leftarrow$ 1-sink;

9 else if  _${\sf isZeroSink}(n,e_{i},x)$_ then

10 $\alpha_{x}\leftarrow$ 0-sink;

11 else

12 $\alpha_{x}\leftarrow{\sf generateNode}(\alpha,e_{i},x)$;

13 if  _$\alpha_{x}$ and $\alpha_{x}^{\prime}\in\mathcal{N}_{i}$ satisfy lemma
1_ then

14 mergeNode($\alpha_{x},\alpha_{x}^{\prime}$);

15

16 else

17 $\mathcal{N}_{i}\leftarrow\mathcal{N}_{i}\cup\alpha_{x}$;

18

19

20 $\mathcal{A}\leftarrow\mathcal{A}\cup(\alpha,\alpha_{x},x)$;

21

22

23

24return $\mathcal{D}$;

end procedure

Algorithm 1 Construction Algorithm

###  3.3 BDD Traversal Method

After constructing BDDs, we traverse the BDD to enumerate Steiner trees whose
costs are not larger than a given threshold. We first reduce the constructed
BDD and then traverse the BDD to obtain the set of Steiner trees.

BDD reduction: Any decedents of nodes at $i$-th step may not go to 1-sinks
even for any patterns of $E^{>i}$. We can delete these nodes because they are
irrelevant to enumerating Steiner trees. To delete such nodes, we traverse BDD
from the 0-sink to the root node. If both 0-arc and 1-arc of nodes point to
the 0-sink, we delete the nodes. Similarly, if both arcs point to the 0-sink
or deleted nodes, we also delete the nodes. This process reduces the size of
BDD without sacrificing the accuracy and accelerates the enumeration of
Steiner trees.

Enumerating Steiner trees: We enumerate Steiner trees via traversing the
constructed BDDs. When we traverse the BDD, our algorithm needs to keep costs
from the root node to nodes in order to eliminate the Steiner trees with costs
larger than $\theta$. We traverse the BDD in a breath first search (BFS)
manner. In the BFS, we can remove costs at $\mathcal{N}_{i}$ after computing
costs at $\mathcal{N}_{i+1}$. Thus, we can reduce the memory costs to keep the
costs on nodes.

##  4 Scalable extension

Since the minimal Steiner tree enumeration problem is $\\#P$-hard, approximate
algorithms are practical in real-world applications as well as the Steiner
tree problem.

We need to improve the scalability to large-scale graphs for applying the
minimal Steiner tree enumeration problem to the real-world applications. We
use two ideas; (1) restricting the candidates of vertices and edges that can
be used for enumerating Steiner trees and (2) enumerating the Top-$k$ Steiner
trees (i.e., Steiner trees with $k$ smallest costs) among the set of generated
Steiner trees represented by the constructed BDDs. These two ideas support to
enumerate the cost-constrained minimal Steiner trees on large-scale graphs.

###  4.1 Preprocessing

We preprocess graphs before constructing BDD to reduce the size of graphs
based on two approaches; seed trees selection and graph simplification. These
two techniques effectively reduce the computation cost for constructing BDDs.

Seed tree selection: The seed trees are Steiner trees computed by existing
algorithms of the Steiner tree problem. We construct the BDD by the union of
seed trees instead of the original graph. The benefits of using seed trees are
(1) mitigating the computation time and memory usage to construct BDDs and (2)
controlling generated Steiner trees by changing the algorithm for selecting
seed trees.

Graph simplification: We reduce the size of graphs by simplifying the graphs
without any information loss. We simplify graphs based on the idea of series-
parallel graphs Borie et al. (2009). We delete and add the following edges and
vertices without sacrificing the number of enumerated Steiner trees as
follows: For sequential edges
($e=(v,v^{\prime}),e^{\prime}=(v,v^{\prime\prime})$), we delete $v$, $e$ and
$e^{\prime}$, and add a new edge with weights $c(e)+c(e^{\prime})$ between
$v^{\prime}$ and $v^{\prime\prime}$, provided that $v$ is not a terminal and
its degree is two. For the loop, we delete the loop because loops are not
included in Steiner trees. We iteratively repeat this process until the graph
does not change.

###  4.2 Enumerating Top-k Steiner trees

In the traversal algorithm, we keep the costs from the root to nodes. The
number of paths from the root is significantly large even when BDDs are not
very large. Thus, we limit the number of costs kept on each node to $k$. Our
algorithm keeps the $k$ smallest costs on each node during traversal, and thus
we can guarantee that we obtain the top-$k$ Steiner trees among Steiner trees
represented by the constructed BDD. Our algorithm can control memory usage and
computation cost by adjusting $k$.

We describe the time and space complexity of the BDD traversal algorithm.

######  Theorem 2.

The time complexity of the BDD traversal algorithm is $O(k|\mathcal{N}|\log
k)$.

Proof: The BDD traversal algorithm conducts BFS from the root node. The time
complexity of BFS is $O(|\mathcal{N}|)$ because each node has just two arcs.
To obtain the Steiner trees with $k$ smallest costs, the algorithm sorts costs
for each node, which takes $O(k\log k)$. Therefore, the time complexity of the
BDD traversal algorithm is $O(k|\mathcal{N}|\log k)$. $\square$

######  Theorem 3.

The space complexity of the BDD traversal algorithm is
$O(k|\mathcal{N}_{m}|)$, where $|\mathcal{N}_{m}|$ denotes the maximum size of
$\mathcal{N}_{i}$ for $i=1,\ldots,|\mathcal{E}|$.

Proof: The BDD traversal algorithm keeps $k$ costs for each node. Since the
algorithm conducts BFS, it removes $k$ costs at $\mathcal{N}_{i}$ after
computing costs at $\mathcal{N}_{i+1}$. It stores at most
$k\cdot|\mathcal{N}_{m}|$ costs during the traversal. Thus, the space
complexity of the BDD traversal algorithm is $O(k|\mathcal{N}_{m}|)$.
$\square$

We here note that our algorithm enumerates top-k $k$ Steiner trees and in
addition, it possibly enumerates other Steiner trees whose costs are not
larger than the threshold.

##  5 Experimental Study

We conduct experimental studies to evaluate our scalable method. Our goal in
the experiments is to answer the following questions: Efficiency. Does our
algorithm efficiently enumerate Steiner trees? Accuracy. Does our algorithm
find Steiner trees with small costs? and Scalability. Does our algorithm
handle large-scale graphs? We here note that our algorithm without scalable
extensions did not work for large-scale graphs.

Our algorithms were implemented in C++. Experiments were performed on a Linux
server with 512GB of memory and an Intel(R) Xeon(R) CPU E5-2699v3 @ 2.30GHz
processor. All algorithms are single-threaded.

###  5.1 Experimental Setting

We provide an overview of our experimental setup, including datasets,
comparisons, and parameters.

Table 1: Datasets Name | $|\mathcal{V}|$ | $|\mathcal{E}|$ | $|\mathcal{T}|$ | Min cost
---|---|---|---|---
PUCNcc3-5n | 125 | 750 | 13 | 20
PUCNcc5-3n | 243 | 1,215 | 27 | 42
PUCNcc6-3n | 729 | 4,368 | 76 | 100
ALUE2087 | 1,244 | 1,971 | 34 | 1,049
ALUE2105 | 1,220 | 1,858 | 34 | 1,032
ALUE3146 | 3,636 | 5,869 | 64 | 2,240
G101 | 67,966 | 82,485 | 100 | 3,492,405
G105 | 79,244 | 101,189 | 550 | 12,507,877
G301 | 80,736 | 98,750 | 191 | 4,797,441
Table 2: Efficiency and accuracy. DNF indicates that the tests did not finish over 24 hours. | Our algorithm | ToSP | Scip-jack
---|---|---|---
Data | Time | Avg cost | Min cost | Time | Avg cost | Min cost | Time | Avg cost | Min cost
PUCNcc3-5n | 1.23 s | 23.6 | 20 | 290.7 s | 22.0 | 20 | DNF | — | —
PUCNcc5-3n | 7.49 s | 50.9 | 48 | 80.1 s | 49.2 | 47 | DNF | — | —
PUCNcc6-3n | 1,623.4 s | 101.0 | 101 | 8315.1 s | 119.8 | 116 | 1,218.3 | 108.4 | 102
ALUE2087 | 0.07 ms | 1,070.7 | 1,049 | 0.02 s | 1,142.8 | 1,104 | 0.85 s | 1,059.3 | 1,049
ALUE2105 | 0.16 ms | 1,080.9 | 1,032 | 0.25 s | 1,129.0 | 1,097 | 18.6 s | 1,049.7 | 1,032
ALUE3146 | 34.5 s | 2,267.9 | 2,240 | 990.1 s | 2,599.7 | 2,438 | DNF | — | —
G101 | 0.03 s | 3,812,251 | 3,801,188 | 9.5 s | 3,859,434 | 3,726,148 | 423.1 s | 3,583,357.0 | 3,515,778
G105 | 347.6 s | 13,149,050 | 13,146,451 | 2,382.1 s | 13,358,044 | 13,134,651 | 85,971.3 s | 12,731,646.7 | 12,596,785
G301 | 730.7 s | 5,113,457 | 5,110,959 | 1,220.3 s | 5,270,464 | 5,145,846 | 37,619.0 s | 201,715.4 | 4,847,830

(a) Graph size (b) BDD size

(c) Construction Time

Figure 1: Scalability: varying the number of seed trees. Missing plots are due
to out of memory.

Datasets: We use three types of datasets; code
covering222http://steinlib.zib.de/showset.php?PUC,
VLSI333http://steinlib.zib.de/showset.php?ALUT, telecommunication
networks444https://homepage.univie.ac.at/ivana.ljubic/research/STP/. The
datasets include graphs, terminals, and the minimum cost of the Steiner tree
for the given graphs and terminals. We use PUCNcc3-5n, PUCNcc5-3n, PUCN6-3n
from code covering, ALUE2087, ALUE2105, and ALUE3146 from VLSI dataset, and
G101, G105, and G301 from telecommunication networks. Table 1 shows statistics
of the graphs.

Comparisons: We compare our scalable method with algorithms by using the tree-
of-shortest-path (ToSP for short) approximation Cormen et al. (2001); Keyder
and Geffner (2009) and SCIP-Jack solver Gamrath et al.
(2017)555https://github.com/dRehfeldt/scipjack, respectively. The ToSP
approximation computes a Steiner tree by computing the shortest paths from a
terminal to other all terminals, which is efficient without guaranteeing
accuracy of approximation. SCIP-Jack can compute Steiner trees accurately more
than the ToSP algorithm, but it takes a more cost. To enumerate Steiner trees,
we repeat (1) temporally deleting $x\%$ edges randomly from the given original
graph, (2) running the algorithms on the graph, and (3) checking whether
duplicate trees are already generated, until obtaining the specified number of
Steiner trees with costs not larger than the given threshold. We specify the
number of Steiner trees to the number of Steiner trees that our algorithm
obtains. We here note that we can use other approximate algorithms and
solvers.

Parameters: We set parameters to our algorithms; threshold $\theta$, the
number of seed trees, and the rank $k$. Threshold $\theta$ is 1.2 times the
cost of optimal Steiner trees. We set the number of seed trees is three as
default, and we compute the seed trees by using the comparisons. We decide $k$
from [1,000, 10,000, 100,000, and 1,000,000] to enumerate Steiner trees as
much as possible without out of memory, based on our preliminary experiments.
To order edges for constructing BDDs, we use a BFS from the terminal with the
smallest degree. For the comparisons, we decide $x$ from [1, 5, 10, 20] in
each test, and we report the results with the smallest computation time.

###  5.2 Result

We first show the efficiency and accuracy of our algorithm and comparisons.
Table 2 shows the enumeration time, the average cost of enumerated Steiner
trees, and the minimum cost among enumerated Steiner trees on each method.

Our algorithm finds Steiner trees more efficiently than the ToSP and Scip-
Jack, except for PUCNcc6-3n. Since our BDDs compactly represent the set of
Steiner trees, we can find Steiner trees without duplication checks. The
comparisons are inefficient because they often find duplicate Steiner trees
and generate trees whose costs larger than the threshold. The enumeration time
on our algorithm is related to the size of BDD. If the BDD is small, the
traverse of BDDs is quickly terminated. Otherwise, it takes a large time such
as PUCNcc6-3n.

We can see that the accuracy of our algorithm is better than that of ToSP in
most datasets. This is because our algorithm guarantees enumerating the
Steiner trees with the $k$ smallest costs among them represented by the BDD.
The Scip-Jack is more accurately than our algorithm except for PUCNcc6-3n.
Scip-Jack finds sub optimal Steiner trees for the given graph, but it takes a
large time to enumerate Steiner trees. In PUCNcc6-3n, the BDD represents
numerous Steiner trees, so it can enumerate Steiner trees with very small
costs.

Finally, we show the scalability of our algorithm. The scalability of our
algorithm is related to the number of seed trees. Therefore, we evaluate the
impacts on the number of seed trees. Figure 1 shows the size of graphs, the
size of BDD, and construction time, with varying the number of seed trees.

The size of graphs slightly increases as the number of seed trees increases.
The size does not increase much because seed trees have many overlapped edges.
Though, the BDD size and construction time significantly increase. From these
results, we can know that it is necessary to control computation costs and
memory usage. Since our algorithm can control them by changing the number of
seed trees, it is applicable to large-scale graphs.

From these results, we confirm that our algorithm efficiently enumerates
minimal Steiner trees whose costs are close to the optimal costs, with high
scalability.

##  6 Related Work

We here describe existing works related to the Steiner tree enumeration
problem and binary decision diagram.

Steiner Tree Enumeration Problem: There are several known results on
algorithms related to Steiner tree enumeration and its variants Kimelfeld and
Sagiv (2006); Khachiyan et al. (2005); Dourado et al. (2014); Conte et al.
(2019); Kimelfeld and Sagiv (2008).

Dourado et al. Dourado et al. (2014) and Khachyan et al. Khachiyan et al.
(2005) theoretically studied minimum Steiner tree enumeration problem and
Steiner forest, respectively. In Kobayashi et al. (2020); Kimelfeld and Sagiv
(2006, 2008), they proposed algorithms for enumerating minimal Steiner trees
and analyzed computational complexity of their algorithms. Their algorithms
interatively remove/add edges from/to the given graph to enumerate minimal
Steiner trees. Unfortunately, the algorithms obviously do not work if graphs
are large scale and the number of terminals is large, so they are not
practical. For example, Kimelfeld and Sagiv Kimelfeld and Sagiv (2006)
proposed an algorithm for enumerating minimal Steiner trees with rankded
order, which takes $O(4^{|T|}|V|+3^{|T|}e\log|V|)$ for generating a single
Steiner tree, where $|T|$ and $|V|$ are the numbers of terminals and vertices,
respectively. All existing works have not shown that their algorithms are
empirically applicable to real-world graphs.

Subgraph Enumeration by Binary Decision Diagram: Binary decision diagram (BDD)
Bergman et al. (2016) as well as its variants such as ZDD Minato (1993) and
SDD Choi and Darwiche (2013) are effective to enumerate discrete data
structures.

One of the main research challenges in the BDD is efficient construction of
BDDs tailored for specific problems. For example, Bergman et al. Bergman et
al. (2011) and Maehara et al. Maehara et al. (2017) proposed construction
algorithms for the set covering and influence spread problems, respectively.
The BDD is often used to enumerate constrained subgraphs, such as paths,
spanning trees, and connected graphs Yan et al. (2015); Hardy et al. (2005);
Sasaki et al. (2019); Maehara et al. (2017). However, to the best of our
knowledge, BDDs for enumerating minimal Steiner trees are not studied, and
existing methods are not easily applied to the minimal Steiner tree
enumeration problem. In addition, these methods are not scalable to the size
of graphs. Thus, our method is the first scalable method for enumerating the
minimal Steiner trees.

Enumerating the cost-constrained subgraphs could have many applications.
However, to the best of our knowledge, there are no BDD construction methods
for enumerating the cost-constrained subgraphs. Our approach can be used for
other problem definitions.

Our approach with scalable extension is different from existing works (e.g.,
Bergman et al. (2011)). We aim to constructs BDDs not including subgraphs that
are not Steiner trees. Our approach resizes the given graphs and enumerates
the top-k Steiner trees. Existing approximate BDD construction methods
construct BDDs that possibly include subgraphs that are not targeted ones
because they approximately merge/delete nodes of BDDs. Therefore, our approach
is novel compared with other BDD methods.

##  7 Conclusion

We initiated a new problem, the cost-constrained minimal Steiner tree
enumeration problem. For addressing the problem, we proposed a novel algorithm
based on the binary decision diagram. We showed that our algorithm is
efficient, accurate, and scalable through experimental studies using real-
world datasets.

## References

  * Bergman et al. [2011] David Bergman, Willem-Jan Van Hoeve, and John N Hooker.  Manipulating mdd relaxations for combinatorial optimization.  In International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems, pages 20–35, 2011.
  * Bergman et al. [2016] David Bergman, Andre A Cire, Willem-Jan van Hoeve, and John Hooker.  Decision diagrams for optimization.  Springer, 2016.
  * Borie et al. [2009] Richard B Borie, R Gary Parker, and Craig A Tovey.  Solving problems on recursively constructed graphs.  ACM Computing Surveys, 41(1):1–51, 2009.
  * Choi and Darwiche [2013] Arthur Choi and Adnan Darwiche.  Dynamic minimization of sentential decision diagrams.  In AAAI, pages 187–194, 2013.
  * Conte et al. [2019] Alessio Conte, Roberto Grossi, Mamadou Kanté, Andrea Marino, Takeaki Uno, and Kunihiro Wasa.  Listing induced steiner subgraphs as a compact way to discover steiner trees in graphs.  2019\.
  * Cormen et al. [2001] Thomas H.. Cormen, Charles Eric Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms, volume 5.  MIT press Cambridge, 2001.
  * Dourado et al. [2014] Mitre C Dourado, Rodolfo A Oliveira, and Fábio Protti.  Algorithmic aspects of steiner convexity and enumeration of steiner trees.  Annals of Operations Research, 223(1):155–171, 2014.
  * Dreyfus and Wagner [1971] Stuart E Dreyfus and Robert A Wagner.  The steiner problem in graphs.  Networks, 1(3):195–207, 1971.
  * Gamrath et al. [2017] Gerald Gamrath, Thorsten Koch, Stephen J Maher, Daniel Rehfeldt, and Yuji Shinano.  Scip-jack—a solver for stp and variants with parallelization extensions.  Mathematical Programming Computation, 9(2):231–296, 2017.
  * Garey and Johnson [1979] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * Hardy et al. [2005] Gary Hardy, Corinne Lucet, and Nikolaos Limnios.  Computing all-terminal reliability of stochastic networks with binary decision diagrams.  In Applied Stochastic Models, pages 1469–74, 2005.
  * Hardy et al. [2007] Gary Hardy, Corinne Lucet, and Nikolaos Limnios.  K-terminal network reliability measures with binary decision diagrams.  IEEE Transactions on Reliability, 56(3):506–515, 2007.
  * Hwang and Richards [1992] Frank K Hwang and Dana S Richards.  Steiner tree problems.  Networks, 22(1):55–89, 1992.
  * Kawahara et al. [2017] Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shinichi Minato.  Frontier-based search for enumerating all constrained subgraphs with compressed representation.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 100(9):1773–1784, 2017.
  * Keyder and Geffner [2009] Emil Keyder and Héctor Geffner.  Trees of shortest paths vs. steiner trees: Understanding and improving delete relaxation heuristics.  In IJCAI, pages 1734–1739, 2009.
  * Khachiyan et al. [2005] Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino.  On the complexity of some enumeration problems for matroids.  SIAM Journal on Discrete Mathematics, 19(4):966–984, 2005.
  * Kimelfeld and Sagiv [2006] Benny Kimelfeld and Yehoshua Sagiv.  Finding and approximating top-k answers in keyword proximity search.  In Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 173–182, 2006.
  * Kimelfeld and Sagiv [2008] Benny Kimelfeld and Yehoshua Sagiv.  Efficiently enumerating results of keyword search over data graphs.  Information Systems, 33(4-5):335–359, 2008.
  * Kobayashi et al. [2020] Yasuaki Kobayashi, Kazuhiro Kurita, and Kunihiro Wasa.  Polynomial delay enumeration for minimal steiner problems.  arXiv preprint arXiv:2010.11462, 2020.
  * Maehara et al. [2017] Takanori Maehara, Hirofumi Suzuki, and Masakazu Ishihata.  Exact computation of influence spread by binary decision diagrams.  In WWW, pages 947–956, 2017.
  * Minato [1993] Shin-ichi Minato.  Zero-suppressed bdds for set manipulation in combinatorial problems.  In DAC, pages 272–277, 1993.
  * Sasaki et al. [2019] Yuya Sasaki, Yasuhiro Fujiwara, and Makoto Onizuka.  Efficient network reliability computation in uncertain graphs.  In EDBT, pages 337–348, 2019.
  * Tsompanakis et al. [2008] Yannis Tsompanakis, Nikos D Lagaros, and Manolis Papadrakakis.  Structural Design Optimization Considering Uncertaintie.  CRC Press, 2008.
  * Valiant [1979] Leslie G Valiant.  The complexity of enumeration and reliability problems.  SIAM Journal on Computing, 8(3):410–421, 1979.
  * Yan et al. [2015] Zongshuai Yan, Chenhua Nie, Rongsheng Dong, Xi Gao, and Jianming Liu.  A novel obdd-based reliability evaluation algorithm for wireless sensor networks on the multicast model.  Mathematical Problems in Engineering, 2015, 2015.


11institutetext: Beihang University, Beijing, China, 22institutetext: Hangzhou
Innovation Institute, Hangzhou, China

# Multi-Grained Cross-modal Alignment for Learning Open-vocabulary Semantic
Segmentation from Text Supervision

Yajie Liu 11 Pu Ge 22 Qingjie Liu 11 Di Huang 11

###### Abstract

Recently, learning open-vocabulary semantic segmentation from text supervision
has achieved promising downstream performance. Nevertheless, current
approaches encounter an alignment granularity gap owing to the absence of
dense annotations, wherein they learn coarse image/region-text alignment
during training yet perform group/pixel-level predictions at inference. Such
discrepancy leads to suboptimal learning efficiency and inferior zero-shot
segmentation results. In this paper, we introduce a Multi-Grained Cross-modal
Alignment (MGCA) framework, which explicitly learns pixel-level alignment
along with object- and region-level alignment to bridge the granularity gap
without any dense annotations. Specifically, MGCA ingeniously constructs
pseudo multi-granular semantic correspondences upon image-text pairs and
collaborates with hard sampling strategies to facilitate fine-grained cross-
modal contrastive learning. Further, we point out the defects of existing
group and pixel prediction units in downstream segmentation and develop an
adaptive semantic unit which effectively mitigates their dilemmas including
under- and over-segmentation. Training solely on CC3M, our method achieves
significant advancements over state-of-the-art methods, demonstrating its
effectiveness and efficiency.

###### Keywords:

Open-vocabulary Semantic Segmentation Text-supervision

##  1 Introduction

Open-vocabulary semantic segmentation (OVSS) aims to segment the visual
elements of arbitrary categories. In contrast to conventional semantic
segmentation [38, 6] that segments targets in a fixed set of categories, OVSS
is more practical for real-world applications where infinite visual concepts
exist. However, the expensive pixel-level annotations and restricted label
categories impede the learning of arbitrary categories. Motivated by the
remarkable success of visual-language pre-training (VLP) [25, 15], recent
studies [31, 22, 4, 30, 26, 24, 20, 33] propose to learn OVSS from massive
web-crawled image-text paired data, which obviates the need for expensive
manual pixel-level annotations. Despite the impressive progress, there remain
critical unresolved challenges that hinder the efficient learning of dense
cross-modal alignment.

Figure 1: Conceptual comparison between previous methods and ours. Group-based
methods encounter an image-group alignment gap while pixel-wise methods
confront a region-pixel alignment gap. In contrast, our method bridges the
train-test alignment gap and introduces adaptive prediction that mitigates
under-/over-segmentation issues.

The primary challenge lies in the alignment granularity gap, as the task
learns from coarse image-level supervision yet necessitates precise
predictions for dense pixels. To learn segmentation with text supervision, the
mainstream works adopt two typical pipelines. The first is group-based methods
[31, 26, 22], which explicitly cluster an image into several group tokens.
Groups are averaged to align with image-level supervision, but at inference,
segmentation masks are generated by independently matching each group with
texts. The image-group alignment gap between training and inference (see Fig.
1) leads to limited performance in complex scenes despite extensive training
on large-scale data (_e.g_., 8.7 mIoU on ADE20K [38] with 29 million image-
text pairs in [31]). The other we refer to pixel-wise methods [4, 24] that
strive to achieve fine-grained alignment without the need for pixel
reorganization. More specifically, TCL [4] incorporates a text grounder into
CLIP [25] to learn region-level alignment, yet performs pixel-wise
classification at inference. PACL [24] establishes alignment between texts and
attention weighted global visual embeddings but conducts pixel-level
predictions. Even with the rich knowledge of CLIP, pixel-wise methods require
heavily fine-tuning on massive paired data (15 million in [4]) to achieve
promising results due to the train-test region-pixel alignment gap as depicted
in Fig. 1.

Another critical issue is rarely explored regarding the semantic unit in
downstream segmentation inference. Semantic units refer to the basic visual
elements processed by the recognition module, which means that pixels within a
unit share the same category. However, our observation reveals that existing
units impose limitations on segmentation performance. Group-based methods
recognize each group unit, which is an object-level representation formed with
limited global initial centroids and without explicit group-level supervision.
As a result, the group unit suffers from imprecise grouping and under-
segmentation at zero-shot inference as shown in Fig. 1. In contrast, pixel-
wise methods classify each pixel independently and disregard the semantic-
level visual coherence. However, without sufficient pixel-level supervision,
individual pixel embedding may not capture adequate semantics and be
susceptible to noise, resulting in over-segmentation, _i.e_., inconsistent
semantics appear within an object as illustrated in Fig. 1.

To bridge the alignment gap, we propose a Multi-Grained Cross-modal Alignment
(MGCA) framework that innovatively constructs multi-granular pseudo semantic
correspondence for fine-grained alignment. As illustrated by the provided
examples in the right of Fig. 2, the text captions demonstrate a stronger
correspondence with the specific objects/regions/pixels in paired images
compared to those in unpaired. Current methods are constrained to the
object/region-level alignment, failing to capture the most critical pixel-
level correspondence that aligns with the semantic granularity required for
segmentation tasks. In contrast, MGCA establishes the informative
object/region/pixel-level positive and negative pairs based on the pixel-to-
text similarity matrix and subsequently conducts multi-grained cross-modal
contrastive learning, explicitly resolving the alignment granularity gap and
enhancing the recognition capabilities at various granularity. Moreover, to
tackle the redundant matching candidates present in region/pixel-level
alignment, MGCA introduces efficient hard mining strategies which facilitate
better and faster learning with zero computational overhead.

To alleviate the under- and over-segmentation problems at inference, we
construct an adaptive semantic unit which cleverly harnesses the advantages of
existing group and pixel unit. The core idea is to finely aggregate the
semantically relevant pixels centered on adequate local sampling points to
form valid part-level representations. The aggregation dynamically exploits
the generalizable visual coherence [24] to enforce more consistent predictions
and effectively suppress the adverse impact of inconsistent noise.
Furthermore, our semantic unit adaptively harnesses the learned multi-granular
alignment capabilities for dense predictions. Our main contributions can be
summarized as follows:

  * •

We propose an efficient Multi-Grained Cross-modal Alignment (MGCA) framework
for text-supervised open-vocabulary semantic segmentation. It bridges the
train-test alignment gap and enables adaptive predictions.

  * •

We innovatively establish pseudo semantic correspondence at object-, region-
and pixel-level for fine-grained alignment without any dense annotations.

  * •

We develop an adaptive semantic unit for downstream segmentation, which
mitigates the under-/over-segmentation issues arising from group/pixel units.

  * •

Training solely on CC3M datasets [27] with mere 4.72M learnable parameters, we
achieve new state-of-the-art zero-shot performance on 8 segmentation
benchmarks with large margins compared to previous methods.

##  2 Related Work

Open-vocabulary semantic segmentation with text supervision. Motivated by the
remarkable success of VLP [25, 15], recent studies [31, 22, 4, 30, 26, 24, 35]
propose to learn open-vocabulary semantic segmentation (OVSS) from web-crawled
image-text paired data. These works can be categorized into two groups based
on segmentation pipelines. Group-based methods, represented by GroupViT [31],
cluster an image into distinct group tokens, which are averaged to align with
text during training and independently matched to text at inference. SegCLIP
[22] arms CLIP [25] by a plugged group module and introduces additional
supervision including a reconstruction loss [13] and a superpixel-based KL
loss [12]. PGSeg [36] leverages the prototypical knowledge extracted from both
images and text to regularize group tokens. However, the image-group alignment
gap between training and inference, compounded by under-segmentation issues
arising from group unit, results in subpar zero-shot segmentation performance.

Another category, which we term pixel-wise methods [4, 24, 39], delves into
learning fine-grained alignment upon spatial image embeddings and performs
pixel-wise classification at inference. Rather than training from scratch,
most works leverage the rich knowledge in large-scale visual-language pre-
training [25, 15] and transfer the image-level alignment to finer alignment.
MaskCLIP [39] introduces modifications to the last attention layer to obtain
dense embeddings for segmentation. TCL [4] incorporates a text grounding
procedure to enhance the quality of region-text alignment. PACL [24] proposes
a modified compatibility function to implicitly learn the patch-level
alignment. Nevertheless, the train-test region-pixel alignment gap, along with
the over-segmentation issues caused by pixel unit hampers the zero-shot
segmentation performance. In this study, we introduce an innovative framework
designed to bridge the train-test alignment gap while enabling adaptive
prediction for downstream segmentation.

Open-vocabulary semantic segmentation. In addition to image-text pairs, [18,
37, 34, 32, 40] also incorporates dense annotations during training to learn
OVSS. They acquire segmentation capability from dense annotations and extend
vocabulary through image-text supervision. Despite the impressive results, the
reliance on dense annotations imposes limitations on the scalability and
generalization of the methods. Therefore, our work focuses on learning OVSS
using cheap and abundant web-crawled image-text pairs without dense
annotations.

##  3 Method

In this section, we introduce the Multi-Grained Cross-modal Alignment (MGCA)
framework for text-supervised open-vocabulary semantic segmentation. We first
present the problem definition and target objective in Sec. 3.1. To achieve
the objective, we ingeniously construct pseudo multi-grained semantic
correspondence upon image-text pairs to facilitate the fine-grained alignment
in Sec. 3.2. Lastly, we develop an adaptive and transferable semantic unit for
downstream semantic segmentation tasks in Sec. 3.3.

Figure 2: The architecture and overall pipeline of our method. $E_{v}$ and
$E_{t}$ are initialized with CLIP and frozen. We train the decoder $D_{v}$
only. As illustrated by the provided examples, Multi-Grained Cross-modal
Alignment (MGCA) innovatively constructs object/region/pixel-level semantic
correspondence, which enables the model to learn fine-grained alignment
without dense annotations. During inference, we discard MGCA and aggregate
pixel embeddings into adaptive semantic units for predictions.

###  3.1 Problem Definition

We aim to learn fine-grained visual representations capable of generalizing to
various downstream semantic segmentation tasks in a zero-shot manner purely
with web-crawled image-text pairs. An overview of the proposed method is
presented in Fig. 2. The architecture of our method consists of three modules:
image encoder $E_{v}$, text encoder $E_{t}$, and a lightweight decoder
$D_{v}$. $E_{v}$ and $E_{t}$ are initialized with the pre-trained CLIP [25]
weights and are both frozen to preserve and exploit the rich knowledge of the
large-scale visual-language pre-training instead of training from scratch. We
only train the lightweight decoder which converts visual features to dense
pixel embeddings for fine-grained alignment. Assume an input batch of image-
text pairs $\\{(x_{i}^{I},x_{i}^{T})\\}_{i=1}^{B}$, where $x_{i}^{I}$ and
$x_{i}^{T}$ denote an image and its paired caption, respectively. For an image
$x_{i}^{I}$, we first pass it through $E_{v}$ to extract the spatial image
features, which exclude the global $[\text{CLS}]$ embedding. Then the spatial
features are fed into the decoder $D_{v}$ to obtain the pixel embeddings
$V_{i}$, which are employed to align with text features
$T_{i}\in\mathbb{R}^{C}$ extracted from the text encoder $E_{t}$. We summarize
the simple process as follows:

$V_{i}=D_{v}(E_{v}(x_{i}^{I})),\qquad T_{i}=E_{t}(x_{i}^{T})$ (1)

where $V_{i}=\\{V_{i}^{p},p=1,...,L\\}\in\mathbb{R}^{L\times C}$ represents
the sequence of the final pixel embeddings. $L$ and $C$ indicate the number of
pixels and the embedding dimension size. Formally, the similarity between
$p$th pixel embeddings of $i$th image $V_{i}^{p}$ and any text embeddings
$T_{j}$ can be computed as the following dot production:

$S_{ij}^{p}=V_{i}^{p}\cdot T_{j}$ (2)

The pixel-to-text similarity matrix $S_{ij}$ reflects the degree of semantic
correlation between dense visual representations and text embeddings. The
objective of open-vocabulary semantic segmentation is to learn fine-grained
cross-modal alignment. In this context, the fine-grained alignment asks to
improve the similarity $S_{ij}^{p}$ when $i$ equals $j$ and the $pth$ pixel
falls into the text-described region otherwise decrease the similarity.
However, the absence of matching between pixels and texts makes learning fine-
grained alignment challenging.

Figure 3: Illustration of the proposed Multi-Grained Cross-modal Alignment
(MGCA). Based on the pixel-to-text similarity matrix $S_{ij}$, we identify
informative positive and negative pairs for object-, region- and pixel-level
contrastive learning.

###  3.2 Multi-Grained Cross-Modal Alignment

Digging into web-crawled data, we ingeniously construct pseudo semantic
correspondence at object-, region- and pixel-level to bridge the granularity
gap and enhance the fine-grained alignment. The pipeline of MGCA is presented
in Fig. 3.

Align at object-level. The most straightforward way to perform fine-grained
alignment is to transfer image-level supervision to object-level, _i.e_.,
locate the text-described object in each image and align it with text in the
latent space. Given the similarity matrix ${S_{ii}}\in\mathbb{R}^{L}$ of
paired image-text, we first calculate the probability of each pixel falling
into the text-described object by applying the softmax function across pixels:
${\mathit{Prob}_{ii}}=\text{softmax}(S_{ii})\in\mathbb{R}^{L}$. Then, pixels
with top-$k$ similarity within the image are considered to form the target
object, and its mask can be computed as follows:

$M_{ii}^{p}=\begin{cases}1,&\mathit{Prob}_{ii}^{p}\geq\text{top-}k(\mathit{Prob}_{ii})\\\
0,&\mathit{Prob}_{ii}^{p}\textless\text{top-}k(\mathit{Prob}_{ii})\\\
\end{cases}\qquad p=0,1,...,L$ (3)

where $k$ represents the maximum area of the object. To further attend to the
reliable pixels and suppress the adverse impact of ambiguous pixels with low
similarity within the target, we weight the pixel embeddings with
${\mathit{Prob}_{ii}}$ to get the object-level representation as follows:

$V_{ii}^{r}=(V_{i})^{\top}({\mathit{Prob}_{ii}}\odot M_{ii})$ (4)

where ${V_{ii}^{r}}\in\mathbb{R}^{C}$ and $\odot$ denotes element-wise
multiplication. The objective of object-level cross-modal alignment can be
formulated as follows:

$\mathcal{L}^{obj}=-\dfrac{1}{B}\sum\limits_{i=1}^{B}(\text{log}\dfrac{\text{exp}(s(V_{ii}^{r},{T_{i}})/\tau)}{\sum_{j=1}^{B}\text{exp}(s(V_{ii}^{r},{T_{j}})/\tau)}+\text{log}\dfrac{\text{exp}(s({T_{i}},V_{ii}^{r})/\tau)}{\sum_{j=1}^{B}\text{exp}(s({T_{i}},V_{jj}^{r})/\tau)})$
(5)

where $s(x,y)=\dfrac{x\cdot y}{\|x\|_{2}\|y\|_{2}}$ is the cosine similarity.
$B$ is the batch size and $\tau$ is the temperature hyperparameter.

Align at region-level. The object-level alignment is insufficient to establish
semantic correspondence between non-object regions and texts. Therefore, we
further integrate the region-level alignment, which encourages the model to
map the positive region-text pairs nearby while mapping all negative pairs far
apart in the latent space.

The object-text pairs above naturally provide proper positive region
correspondences. Any region in an image with its unpaired text forms a
negative region-text pair. However, redundant negatives impede the
computational efficiency and the learning of discriminative representations.
In this respect, we propose to boost region-level alignment with an efficient
hard negative mining strategy. Concretely, we establish negatives by selecting
the most relevant region in an image to the unpaired text using Eq. 4. Recall
that $i$, $j$ in $S_{ij}$ denote the sequence order of image and text in a
batch, respectively. Hence, $V_{ij}^{r}$ seamlessly represents the embedding
of the hard negative region $M_{ij}$ when $i\neq j$. We delineate the
objective of region-level cross-modal alignment as follows:

$\mathcal{L}^{reg}=-\dfrac{1}{B}\sum\limits_{i=1}^{B}(\text{log}\dfrac{\text{exp}(s(V_{ii}^{r},{T_{i}})/\tau)}{\sum_{j=1}^{B}\text{exp}(s(V_{ij}^{r},{T_{j}})/\tau)}+\text{log}\dfrac{\text{exp}(s({T_{i}},V_{ii}^{r})/\tau)}{\sum_{j=1}^{B}\text{exp}(s({T_{i}},V_{ji}^{r})/\tau)})$
(6)

Align at pixel-level. Pixel-level cross-modal alignment serves as a critical
bridge to tackle the alignment granularity gap and achieve high-quality
segmentation masks, as it fulfills the granularity demands of segmentation.
The objective of pixel-level alignment is to enhance the similarity between
positive pixel-level correspondence and reduce the similarity between
unmatched pairs.

Positive pixel-text pairs lie within the text-described objects, _i.e_., $i=j$
and $M_{ij}^{p}=1$. The remaining pairs are regarded as negatives. However,
the pixel-level pairs present in a batch, especially the negatives, are
severely redundant. Training with all candidates incurs high computational
cost and the redundant easy ones would undermine the informative gradient
information from hard negatives, hindering the learning of discriminative
representations. Additionally, the hardest positive pixel within the text-
described object may be negative indeed due to the lack of groundtruth masks,
which would harm the performance.

To this end, we propose to collect hard negatives and semi-hard positives to
facilitate pixel-level contrastive learning. Selection of negative
correspondence can be done by simply picking the pixel with the highest
similarity in an image to its unpaired text. To establish the hardness-
trustworthiness trade-off positive correspondence, pixels with the
top-$k_{pix}$th similarity in the objects are selected as semi-hard positives.
We maximize the similarity of positive pixel-text pairs versus negatives via
contrastive learning as follows:

$\displaystyle\mathcal{L}^{pix}=-\dfrac{1}{B}\sum\limits_{i=1}^{B}$
$\displaystyle(\text{log}\dfrac{\text{exp}(S_{ii}^{+}/\tau)}{\text{exp}(\dfrac{S_{ii}^{+}}{\tau})+\sum\limits_{j\neq
i}^{B}\text{exp}(\dfrac{{S_{ij}^{-}}}{\tau})}+\text{log}\dfrac{\text{exp}({S_{ii}^{+}}/\tau)}{\text{exp}(\dfrac{{S_{ii}^{+}}}{\tau})+\sum\limits_{j\neq
i}^{B}\text{exp}(\dfrac{{S_{ji}^{-}}}{\tau})})$ (7) $\displaystyle S_{ii}^{+}$
$\displaystyle=\text{top-}k_{pix}\text{th}(S_{ii}/f),\qquad
S_{ij}^{-}=\max(S_{ij}/f)~{}s.t.~{}j\neq i$

where $S_{ii}^{+}$, $S_{ij}^{-}$ represent the similarity of semi-hard
positives and hard negatives, respectively. In practice, we directly extract
the selected pixel-to-text similarity from $S_{ij}$ in Eq. 2 instead of
recalculating their cosine similarity, and a scale factor $f$ is employed here
to ensure the numerical stability of exponential.

Overall objective. We train the model by jointly optimizing object-, region-
and pixel-level cross-modal alignment. The overall objective can be
represented as follows:

$\mathcal{L}=\mathcal{L}^{obj}+\mathcal{L}^{reg}+\mathcal{L}^{pix}$ (8)

###  3.3 Adaptive semantic unit

To generalize to various downstream segmentation tasks, it is critical to
employ an adaptive and transferable semantic unit at inference. The semantic
unit refers to the basic visual element processed by the recognition module,
which means that pixels within a unit share the same category. However, it’s
noteworthy that existing units impose limitations on the segmentation
performance.

Group-based methods recognize each group unit, which is formed by hierarchical
grouping of visual tokens and results in coarse object-level representations.
However, owing to the limited initial global cluster centers and the absence
of explicit group-level supervision, group unit suffers from imprecise
grouping and under-segmentation when applied to downstream tasks as shown in
Fig. 8. In contrast, pixel-wise methods identify each pixel independently and
disregard the semantic-level visual coherence. Due to the lack of sufficient
pixel-level supervision, individual pixel embedding may not carry adequate
semantics and be susceptible to noise. As a result, inconsistent predictions
appear among the pixels within regions with the same semantics, leading to
over-segmentation as depicted in Fig. 8.

Based on above analysis, rather than utilizing existing units directly, we
develop an adaptive semantic unit that cleverly harnesses their advantages.
The core idea is to finely aggregate pixels with relevant semantics in the
final visual embeddings based on pixel affinity. Firstly, we conduct uniform
sampling on the dense pixel embeddings to acquire a collection of meta-points
$\mathcal{P}$. Secondly, we assign each pixel to its most similar meta-point
in $\mathcal{P}$, thus obtaining a set of pixels for each meta-point. Lastly,
each set of pixels is averaged to compute its semantic embedding, which is
employed to calculate the most similar text as the prediction result.

Figure 4: Examples of our semantic units. Pixels with the same color belong to
the same unit. Our semantic units align with part-level representations, such
as the wheel hub in the first image and the hat and shoes in the second image.

The proposed semantic unit dynamically exploits the generalizable visual
coherence and finely aggregates semantically relevant pixels, forming valid
part-level representations as illustrated in Fig. 4. Unlike group-based
methods rely on limited group tokens and global initial centers, our part-
level unit benefits from adequate local sampling meta-points, ensuring a fine
and precise aggregation of pixels. Moreover, the average aggregation
effectively enhances the joint features across pixels and mitigates the
adverse impact of inconstant noise with minimal computational overhead. The
adaptive unit enables the feasible utilization of the learned multi-grained
alignment capabilities and alleviates the under- and over-segmentation
problems.

##  4 Experiments

###  4.1 Implementation details

Architecture We adopt the visual encoder and text encoder from CLIP [25]
ViT-B/16 [10]. The input image size is 224 $\times$ 224 and the patch size is
16 $\times$ 16 during the training stage. We extract spatial visual features
from the image encoder following [39, 4] that modifies the last attention
layer. The learnable decoder, with a total of 4.72M parameters, consists of an
upsampling interpolation with a scale factor of 2 and two gated convolution
blocks from [4].

Training We train our models purely on CC3M [27]. Discounting expired links, a
total of 2.56 million image-text pairs are actually downloaded. To enrich
positive correspondence, we extract nouns from each caption and use CLIP
prompts to generate captions with these nouns as GroupViT [31]. When forming a
batch, we randomly select one of the captions for each image from either its
original caption or the generated captions. The models are trained on 4 RTX
3090 GPUs with a global batch size of 1024. The learning rate is 1e-4 and
decayed via the cosine annealing schedule [21]. We train the models for 15
epochs, with a linear warmup for the first 2 epochs. Adam optimizer [16] with
a weight decay of 0.05 is used. Following the practice in contrastive learning
[14], the temperature hyperparameter $\tau$ is 0.07. And inspired by [29], we
set the scale factor in Eq. 7 as $f=5\times\sqrt{C}$, $C$ is the embedding
dimension size.

Hyperparameters The area $k\in[0,1]$ in Eq. 3 for the positive object is 0.4,
which corresponds to the average area of text-described regions in CC3M [27].
For negative region-level pairs, we denote the area as $k_{n}$ and set it to
0.05. The $k_{pix}\in[0,1]$ in Eq. 7 for semi-hard positives is 0.06.

Inference Following previous works [31, 4], we resize the input image to have
a shorter size of 448 and adopt a sliding window strategy during inference.
Pixel embeddings from the decoder are aggregated into 36 semantic units per
image, that is, the number of meta-points is 36. Within each unit, the pixel
embeddings are averaged to calculate their corresponding semantic embedding,
which is then utilized to calculate the most similar text as the prediction
result.

Table 1: Zero-shot segmentation performance comparison on datasets with a
background class. All methods are reported without post-processing. mIoU (%)
metric is used in every experiment. Abbreviations of benchmarks, from left to
right: Pascal VOC, Pascal Context, COCO-Object. Results above the dotted line
are taken from papers that may not adhere to the unified evaluation protocol.
* represents the results are trained on the downloaded CC3M. We highlight the
best and second-best results.

Method | Pretrain Data | VOC | Context | COCO | Avg.
---|---|---|---|---|---
ViL-Seg [CVPR23] [20] | CC12M [5] | 37.3 | 18.9 | 18.1 | 24.8
ViewCo [ICLR23] [26] | CC12M+YFCC14M [28] | 52.4 | 23.0 | 23.5 | 33.0
MixReorg [ICCV23] [3] | CC12M | 47.9 | 23.9 | 21.3 | 31.0
CoCu [NeurIPS23] [30] | CC3M&12M+YFCC14M | 49.7 | 22.8 | 22.0 | 31.5
1-6[1pt/1pt] GroupViT [CVPR22] [31] | CC3M&12M+YFCC14M | 52.3 | 22.4 | 24.3 | 33.0
GroupViT [CVPR22] [31] | CC3M&12M+RedCaps12M [9] | 50.8 | 23.7 | 27.5 | 34.0
PGSeg [NeurIPS23] [36] | CC12M + RedCaps12M | 53.2 | 23.8 | 28.7 | 35.2
SegCLIP [ICML23] [22] | CC3M+COCO Caption [19] | 52.6 | 24.7 | 26.5 | 34.6
MaskCLIP [ECCV22] [39] | - | 38.8 | 23.6 | 20.6 | 27.7
$\text{TCL}^{*}$ [CVPR23] [4] | CC3M | 51.4 | 25.1 | 28.8 | 35.1
TCL [CVPR23] [4] | CC3M&12M | 51.2 | 24.3 | 30.4 | 35.3
MGCA (Ours) | CC3M | 53.1 | 31.3 | 31.9 | 38.8

Table 2: Zero-shot segmentation performance comparison on datasets without
background class. Abbreviations of benchmarks, from left to right: Pascal
VOC20, Pascal Context59, COCO-Stuff, Cityscapes, Ade20k.

Method | Pretrain Data | VOC20 | C59 | STUFF | CITY | ADE | Avg.
---|---|---|---|---|---|---|---
CoCu [NeurIPS23] [30] | CC3M&12M+YFCC14M | - | - | 14.9 | 21.9 | 12.0 | -
1-8[1pt/1pt] GroupViT [CVPR22] [31] | CC3M&12M+YFCC14M | 74.1 | 20.8 | 12.6 | 6.9 | 8.7 | 24.6
GroupViT [CVPR22] [31] | CC3M&12M+RedCaps12M | 79.7 | 23.4 | 15.3 | 11.1 | 9.2 | 27.7
PGSeg [NeurIPS23] [36] | CC12M + RedCaps12M | 79.6 | 23.4 | 15.3 | 12.5 | 9.1 | 28.0
SegCLIP [ICML23] [22] | CC3M+COCO Caption | 76.8 | 25.6 | 16.5 | 11.0 | 8.7 | 27.7
MaskCLIP [ECCV22] [39] | - | 74.9 | 26.4 | 16.4 | 12.6 | 9.8 | 28.0
$\text{TCL}^{*}$ [CVPR23] [4] | CC3M | 76.8 | 28.4 | 18.7 | 20.1 | 14.3 | 31.7
TCL [CVPR23] [4] | CC3M&12M | 77.5 | 30.3 | 19.6 | 23.1 | 14.9 | 33.1
MGCA (Ours) | CC3M | 81.4 | 33.7 | 22.0 | 24.0 | 16.4 | 35.5

###  4.2 Zero-shot Transfer to Semantic Segmentation

Evaluation protocol We follow the unified evaluation protocol in TCL [4] to
evaluate our method on widely used 8 benchmark datasets, categorized into two
groups: $(i)$ with a background class including Pascal VOC (21 classes) [11],
Pascal Context (60 classes) [23], COCO-Object (81 classes) [2], $(ii)$ without
background class including Pascal VOC20 (20 classes) [11], Pascal Context59
(59 classes) [23], COCO-Stuff (171 classes) [2], ADE20k (150 classes) [38] and
City-scapes (19 classes) [8]. For the first category, we evaluate the
foreground classes by thresholding the softmax-normalized-similarity between
the pixel embeddings and text features following [31]. For the other datasets,
we evaluate both object and stuff classes. The unified class names from
MMSegmentation [7] is used without class name based tricks. We employ the text
prompts following TCL [4] without any test-time augmentation. The post-
processing methods such as dense CRF [17] and PAMR [1] are not used for a fair
comparison.

Comparison with the state-of-the-art We quantitatively compare our method with
the state-of-the-art methods on the two groups of benchmarks. We summarize the
performance reported in the papers (which may not adhere to the unified
evaluation protocol) for methods that have not released the pretrained
weights. And most group-based methods are compared only in Tab. 1 such as ViL-
Seg [20], ViewCo [26] and MixReorg [3] since they tend to focus on evaluating
and presenting the performance on object-oriented datasets, _i.e_., the
datasets with a background class. For the methods that have released their
pretrained weights including GroupViT [31], PGSeg [36], SegCLIP [22], MaskCLIP
[39] and TCL [4], we evaluate and present their performance across all
benchmarks following the unified protocol. In addition, we train the current
best-performing method TCL [4] on the downloaded CC3M using their official
code to provide a fair comparison.

Tab. 1 illustrates the comparison results on the object-oriented datasets. Our
MGCA achieves substantial advancements over preceding state-of-the-art methods
while utilizing a reduced amount of training data. Concretely, we exceed the
current best-performing method TCL [4] by an average of 3.5% mIoU. Tab. 2
summarizes the performance comparison results on the datasets that compromise
both object and stuff classes. It further demonstrates MGCA attains noticeable
improvements across various downstream tasks with diverse scenes and
categories. Compared to high-performing TCL [4] which involves a total of 15M
training samples, MGCA exhibits superior performance with a 2.4% increase in
average mIoU, despite utilizing only 3M training samples. More quantitative
comparison results are provided in Appendix.

Figure 5: Visualization of the impact of each module. The baseline corresponds
to the first row in Tab. 3 which directly employs CLIP for dense prediction.
We progressively integrate object-, region- and pixel-level alignment modules,
along with the proposed unit, into the model to qualitatively demonstrate the
impact of each module.

Notably, our method achieves these results without using any dense
annotations, and without introducing any additional supervision (_e.g_.,
superpixel), any regularization or any post-processing techniques. We will
release the code with the pretrained checkpoint upon acceptance. Limitations
and future works are discussed in the Appendix.

Table 3: Ablation studies of alignment granularity. Pixel units are employed
to clearly illustrate the impact of fine-grained alignment. We present the
absolute improvement in mIoU (%) for each setting relative to the baseline.
Settings in our method are highlighted in blue.

object | region | pixel | with background class | without background class
---|---|---|---|---
level | level | level | VOC | Context | COCO | Avg. | VOC20 | C59 | STUFF | CITY | ADE | Avg.
✗ | ✗ | ✗ | 25.9 | 17.1 | 20.0 | 21.0 | 40.1 | 18.3 | 10.0 | 17.2 | 8.2 | 18.8
1-13[1pt/1pt] ✓ | ✗ | ✗ | 42.6 | 27.8 | 24.3 | 31.6 (10.6 $\uparrow$) | 66.5 | 28.7 | 17.5 | 23.7 | 12.6 | 29.8 (11.0 $\uparrow$)
✗ | ✓ | ✗ | 41.6 | 22.8 | 24.6 | 29.7 ( 8.7 $\uparrow$) | 63.0 | 24.6 | 15.1 | 22.1 | 11.6 | 27.3 ( 8.5 $\uparrow$)
✗ | ✗ | ✓ | 50.4 | 29.2 | 29.3 | 36.3 (15.3 $\uparrow$) | 78.2 | 31.1 | 20.1 | 20.9 | 15.3 | 33.1 (14.3 $\uparrow$)
1-13[1pt/1pt] ✓ | ✗ | ✗ | 42.6 | 27.8 | 24.3 | 31.6 (10.6 $\uparrow$) | 66.5 | 28.7 | 17.5 | 23.7 | 12.6 | 29.8 (11.0 $\uparrow$)
✓ | ✓ | ✗ | 44.1 | 28.9 | 26.2 | 33.1 (12.1 $\uparrow$) | 71.6 | 30.2 | 19.2 | 24.9 | 14.5 | 32.1 (13.3 $\uparrow$)
✓ | ✓ | ✓ | 51.1 | 30.0 | 30.3 | 37.1 (16.1 $\uparrow$) | 77.5 | 31.8 | 20.5 | 23.2 | 15.6 | 33.7 (14.9 $\uparrow$)

Figure 6: Impact of $k_{n}$. $k_{n}$ decides the area of regions for negative
region-level correspondence. We present the performance on datasets without
background class.

Figure 7: Impact of $k_{pix}$. $k_{pix}$ controls the hardness-trustworthiness
trade-off for positive pairs in pixel-level alignment.

###  4.3 Ablation Studies

In this section, we conduct ablation studies to evaluate the effects of core
components of the proposed method.

Impact of alignment granularity. Tab. 3 presents the ablation studies on the
alignment granularity. To better understand and assess the impact of fine-
grained alignment on the segmentation performance, we adopt pixel as semantic
unit here in accordance with previous pixel-wise methods. The first row serves
as the baseline that directly calculates the most similar text to each spatial
embedding from the CLIP image encoder as the prediction. The quantitative
results demonstrate: (1) Each alignment granularity is proven to be beneficial
for dense prediction, _e.g_., the object-level alignment enhances the baseline
by 10.6% mIoU on object-oriented datasets and region-level alignment delivers
an 8.5% improvement on the datasets compromise both object and stuff classes.
(2) The finest pixel-level alignment brings the most significant improvements.
In particular, pixel-level alignment alone achieves remarkable improvements of
15.3% and 14.3% on the two groups of benchmarks, respectively. (3) Combining
the three-level granularity alignment yields the best performance, resulting
in an average improvement of 16.1% and 14.9% mIoU compared to the baseline.

We qualitatively explore the effect of alignment granularity by incrementally
incorporating object-, region- and pixel-level alignment into the baseline. As
illustrated in Fig. 5, object- and region-level alignment effectively enhance
the identification of salient regions and mitigates the occurrence of false
cross-modal correspondences, _e.g_., the noisy patches in the background. And
incorporating the pixel-level alignment significantly improves the
completeness and accuracy of segmentation masks.

Table 4: Ablation studies of semantic unit and the number of meta-points. The
first line employs the pixel unit, where the number of units is equal to the
total number of pixel embeddings.

semantic | # meta- | with background class | without background class
---|---|---|---
unit | points | VOC | Context | COCO | Avg. | VOC20 | C59 | STUFF | CITY | ADE | Avg.
pixel | 3136 | 51.1 | 30.0 | 30.3 | 37.1 | 77.5 | 31.8 | 20.5 | 23.2 | 15.6 | 33.7
1-12[1pt/1pt] Ours | 121 | 52.3 | 30.9 | 31.3 | 38.2 | 80.0 | 33.1 | 21.5 | 23.9 | 16.3 | 35.0
81 | 52.5 | 31.1 | 31.5 | 38.4 | 80.4 | 33.3 | 21.7 | 23.9 | 16.4 | 35.1
64 | 52.7 | 31.1 | 31.6 | 38.5 | 80.6 | 33.5 | 21.8 | 24.0 | 16.4 | 35.3
49 | 52.8 | 31.2 | 31.8 | 38.6 | 81.0 | 33.6 | 22.0 | 23.9 | 16.4 | 35.4
36 | 53.1 | 31.3 | 31.9 | 38.8 | 81.4 | 33.7 | 22.0 | 24.0 | 16.4 | 35.5
25 | 53.3 | 31.3 | 31.9 | 38.8 | 81.9 | 33.8 | 22.2 | 23.3↓ | 16.2↓ | 35.5
16 | 53.7 | 31.1 | 31.7 | 38.8 | 82.2 | 33.8 | 22.1 | 22.6 | 15.9 | 35.3

Impact of $k_{n}$. Recall that we calculate the mask of hard negative region
by selecting pixels with top-$k_{n}$ similarity to the unpaired text. Fig. 7
explores the influence of the area $k_{n}$ for negative region-level
correspondence on datasets without background class. We observe that
alterations in ${k_{n}}$ exert little effect on model performance. Therefore
we also present the results excluding pixel-level alignment to clearly access
the impact of ${k_{n}}$. As expected, smaller $k_{n}$ compels the model to
distinguish more challenging regions and promotes finer alignment which
benefits the dense predictions as shown in Fig. 7.

Impact of $k_{pix}$. Fig. 7 quantifies the effect of $k_{pix}$ which controls
the hardness and trustworthiness of positive pixel-text pairs. During
training, an image is assumed to contain $k\times L$ positive pixels, where
$k=0.4$ as mentioned above, and $L$ is the total number of pixel embeddings.
Bigger $k_{pix}$ signifies harder positives which may result in false positive
predictions, whereas smaller $k_{pix}$ is likely to cause false negative
predictions. The results presented in Fig. 7 demonstrate the superiority of
semi-hard positives $k_{pix}=0.06$ compared to the hardest positives
$k_{pix}=1.0$ and the most trustworthy positives $k_{pix}=0$. The impact of
hard mining strategy for negative pixel-level correspondence is provided in
Appendix.

Impact of the semantic unit and the number of meta-points. Tab. 4 reports the
performance on all benchmarks with regard to the semantic units. The first row
serves as the baseline, aligning with pixel-wise methods [4, 24], where the
number of meta-point is equal to the total number of final pixel embeddings. A
smaller number signifies a reduced number of final semantic units per image,
contributing to more consistent segmentation results. As demonstrated in Tab.
4, reducing the number of meta-point consistently enhances the segmentation
performance. However, decreasing the number below 36 yields marginal returns
in performance, and even leads to a drop in some benchmarks (_e.g_.,
Cityscapes and ADE20k). Therefore we set the meta-point number as 36 in the
aggregation for semantic units. As shown in the penultimate column in Fig. 5,
the proposed unit achieves more consistent segmentation masks within identical
semantic regions, _e.g_., a more complete mask for the motorbike depicted in
the first row.

###  4.4 Visualization

We qualitatively compare our method with previous state-of-the-art methods in
Fig. 8. Specially, we select the group-based GroupViT [31] and pixel-wise
method TCL [4] to further illustrate the characteristics of different semantic
units. GroupViT encounters inaccurate grouping and under-segmentation
problems, while TCL suffers from over-segmentation, particularly with stuff
categories. Our method consistently achieves more accurate and high-quality
segmentation masks. More qualitative results are provided in Appendix.

Figure 8: Qualitative comparison results on PASCAL Context59. Post-processing
techniques are not used in all methods. We circle the coarse-clustering and
under-segmentation results for GroupViT. Pixel-wise methods like TCL suffer
from over-segmentation where a single object is segmented into multiple
categories. Our method achieves more accurate and high-quality segmentation
masks. The official palette for PASCAL Context59 from MMSegmentation is
utilized.

##  5 Conclusion

In this paper, we propose an efficient multi-grained cross-modal alignment
framework to learn open-vocabulary semantic segmentation without any manual
dense annotations. Digging into image-text pairs, we innovatively construct
multi-grained pseudo semantic correspondence and accomplish object-, region-
and pixel-level alignment, explicitly resolving the train-test alignment
granularity gap. Besides, an adaptive and transferable semantic unit is
introduced which cleverly harnesses the advantages of group and pixel units
and alleviates their under- and over-segmentation problems in zero-shot
predictions. With a reduced amount of training data, our method achieves
state-of-the-art performance on 8 downstream datasets, highlighting its
effectiveness and efficiency.

## References

  * [1] Araslanov, N., Roth, S.: Single-stage semantic segmentation from image labels. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 4253–4262 (2020)
  * [2] Caesar, H., Uijlings, J., Ferrari, V.: Coco-stuff: Thing and stuff classes in context. In: CVPR. pp. 1209–1218 (2018)
  * [3] Cai, K., Ren, P., Zhu, Y., Xu, H., Liu, J., Li, C., Wang, G., Liang, X.: Mixreorg: Cross-modal mixed patch reorganization is a good mask learner for open-world semantic segmentation. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 1196–1205 (2023)
  * [4] Cha, J., Mun, J., Roh, B.: Learning to generate text-grounded mask for open-world semantic segmentation from only image-text pairs. In: CVPR. pp. 11165–11174 (2023)
  * [5] Changpinyo, S., Sharma, P., Ding, N., Soricut, R.: Conceptual 12m: Pushing web-scale image-text pre-training to recognize long-tail visual concepts. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 3558–3568 (2021)
  * [6] Chen, L.C., Zhu, Y., Papandreou, G., Schroff, F., Adam, H.: Encoder-decoder with atrous separable convolution for semantic image segmentation. In: ECCV. pp. 801–818 (2018)
  * [7] Contributors, M.: Mmsegmentation: Openmmlab semantic segmentation toolbox and benchmark (2020)
  * [8] Cordts, M., Omran, M., Ramos, S., Rehfeld, T., Enzweiler, M., Benenson, R., Franke, U., Roth, S., Schiele, B.: The cityscapes dataset for semantic urban scene understanding. In: CVPR. pp. 3213–3223 (2016)
  * [9] Desai, K., Kaul, G., Aysola, Z.T., Johnson, J.: Redcaps: Web-curated image-text data created by the people, for the people. In: Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1) (2021)
  * [10] Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al.: An image is worth 16x16 words: Transformers for image recognition at scale. In: International Conference on Learning Representations (2020)
  * [11] Everingham, M., van Gool, L., Williams, C.K., Winn, J., Zisserman, A.: The pascal visual object classes (voc) challenge. International Journal of Computer Vision 88(2), 303–338 (2010)
  * [12] FELZENSZWALB, P.F., HUTTENLOCHER, D.P.: Efficient graph-based image segmentation. International Journal of Computer Vision 59(2), 167–181 (2004)
  * [13] He, K., Chen, X., Xie, S., Li, Y., Dollár, P., Girshick, R.: Masked autoencoders are scalable vision learners. In: CVPR. pp. 16000–16009 (2022)
  * [14] He, K., Fan, H., Wu, Y., Xie, S., Girshick, R.: Momentum contrast for unsupervised visual representation learning. In: CVPR. pp. 9729–9738 (2020)
  * [15] Jia, C., Yang, Y., Xia, Y., Chen, Y.T., Parekh, Z., Pham, H., Le, Q., Sung, Y.H., Li, Z., Duerig, T.: Scaling up visual and vision-language representation learning with noisy text supervision. In: ICML. pp. 4904–4916. PMLR (2021)
  * [16] Kinga, D., Adam, J.B., et al.: A method for stochastic optimization. In: ICLR. vol. 5, p. 6. San Diego, California; (2015)
  * [17] Krähenbühl, P., Koltun, V.: Efficient inference in fully connected crfs with gaussian edge potentials. In: Proceedings of the 24th International Conference on Neural Information Processing Systems. pp. 109–117 (2011)
  * [18] Liang, F., Wu, B., Dai, X., Li, K., Zhao, Y., Zhang, H., Zhang, P., Vajda, P., Marculescu, D.: Open-vocabulary semantic segmentation with mask-adapted clip. In: CVPR. pp. 7061–7070 (2023)
  * [19] Lin, T.Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P., Zitnick, C.L.: Microsoft coco: Common objects in context. In: ECCV. pp. 740–755. Springer (2014)
  * [20] Liu, Q., Wen, Y., Han, J., Xu, C., Xu, H., Liang, X.: Open-world semantic segmentation via contrasting and clustering vision-language embedding. In: European Conference on Computer Vision. pp. 275–292. Springer (2022)
  * [21] Loshchilov, I., Hutter, F.: Stochastic gradient descent with warm restarts. In: Proceedings of the 5th Int. Conf. Learning Representations. pp. 1–16
  * [22] Luo, H., Bao, J., Wu, Y., He, X., Li, T.: Segclip: Patch aggregation with learnable centers for open-vocabulary semantic segmentation. In: ICML. pp. 23033–23044. PMLR (2023)
  * [23] Mottaghi, R., Chen, X., Liu, X., Cho, N.G., Lee, S.W., Fidler, S., Urtasun, R., Yuille, A.: The role of context for object detection and semantic segmentation in the wild. In: CVPR. pp. 891–898 (2014)
  * [24] Mukhoti, J., Lin, T.Y., Poursaeed, O., Wang, R., Shah, A., Torr, P.H., Lim, S.N.: Open vocabulary semantic segmentation with patch aligned contrastive learning. In: CVPR. pp. 19413–19423 (2023)
  * [25] Radford, A., Kim, J.W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al.: Learning transferable visual models from natural language supervision. In: International conference on machine learning. pp. 8748–8763. PMLR (2021)
  * [26] Ren, P., Li, C., Xu, H., Zhu, Y., Wang, G., Liu, J., Chang, X., Liang, X.: Viewco: Discovering text-supervised segmentation masks via multi-view semantic consistency. In: The Eleventh International Conference on Learning Representations (2022)
  * [27] Sharma, P., Ding, N., Goodman, S., Soricut, R.: Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning. In: Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 2556–2565 (2018)
  * [28] Thomee, B., Shamma, D.A., Friedland, G., Elizalde, B., Ni, K., Poland, D., Borth, D., Li, L.J.: Yfcc100m: The new data in multimedia research. Communications of the ACM 59(2), 64–73 (2016)
  * [29] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. pp. 6000–6010 (2017)
  * [30] Xing, Y., Kang, J., Xiao, A., Nie, J., Shao, L., Lu, S.: Rewrite caption semantics: Bridging semantic gaps for language-supervised semantic segmentation. In: Thirty-seventh Conference on Neural Information Processing Systems (2023)
  * [31] Xu, J., De Mello, S., Liu, S., Byeon, W., Breuel, T., Kautz, J., Wang, X.: Groupvit: Semantic segmentation emerges from text supervision. In: CVPR. pp. 18134–18144 (2022)
  * [32] Xu, J., Liu, S., Vahdat, A., Byeon, W., Wang, X., De Mello, S.: Open-vocabulary panoptic segmentation with text-to-image diffusion models. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 2955–2966 (2023)
  * [33] Xu, J., Hou, J., Zhang, Y., Feng, R., Wang, Y., Qiao, Y., Xie, W.: Learning open-vocabulary semantic segmentation models from natural language supervision. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 2935–2944 (2023)
  * [34] Xu, M., Zhang, Z., Wei, F., Hu, H., Bai, X.: Side adapter network for open-vocabulary semantic segmentation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 2945–2954 (2023)
  * [35] Yi, M., Cui, Q., Wu, H., Yang, C., Yoshie, O., Lu, H.: A simple framework for text-supervised semantic segmentation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 7071–7080 (2023)
  * [36] Zhang, F., Zhou, T., Li, B., He, H., Ma, C., Zhang, T., Yao, J., Zhang, Y., Wang, Y.: Uncovering prototypical knowledge for weakly open-vocabulary semantic segmentation. In: Thirty-seventh Conference on Neural Information Processing Systems (2023)
  * [37] Zhang, H., Li, F., Zou, X., Liu, S., Li, C., Yang, J., Zhang, L.: A simple framework for open-vocabulary segmentation and detection. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 1020–1031 (2023)
  * [38] Zhou, B., Zhao, H., Puig, X., Xiao, T., Fidler, S., Barriuso, A., Torralba, A.: Semantic understanding of scenes through the ade20k dataset. International Journal of Computer Vision 127(3), 302–321 (2019)
  * [39] Zhou, C., Loy, C.C., Dai, B.: Extract free dense labels from clip. In: European Conference on Computer Vision. pp. 696–712. Springer (2022)
  * [40] Zou, X., Dou, Z.Y., Yang, J., Gan, Z., Li, L., Li, C., Dai, X., Behl, H., Wang, J., Yuan, L., et al.: Generalized decoding for pixel, image, and language. In: CVPR. pp. 15116–15127 (2023)