#  ${}_{\\!\\!\\!\\!\\!}$LogicSeg:${}_{\\!}$ Parsing${}_{\\!}$ Visual
Semantics with Neural Logic Learning and
Reasoning${}_{\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!}$

Liulei Li1, 2, Wenguan Wang1111Corresponding author: Wenguan Wang., Yi Yang1
1 ReLER, CCAI, Zhejiang University 2 ReLER, AAII, University of Technology
Sydney
https://github.com/lingorX/LogicSeg/

###### Abstract

Current high-performance semantic segmentation models are${}_{\\!}$
purely${}_{\\!}$ data-driven${}_{\\!}$ sub-symbolic${}_{\\!}$
approaches${}_{\\!}$ and${}_{\\!}$ blind${}_{\\!}$ to${}_{\\!}$ the${}_{\\!}$
structured${}_{\\!}$ nature${}_{\\!}$ of${}_{\\!}$ the${}_{\\!}$
visual${}_{\\!}$ world.${}_{\\!}$ This${}_{\\!}$ is in${}_{\\!}$
stark${}_{\\!}$ contrast${}_{\\!}$ to${}_{\\!}$ human${}_{\\!}$
cognition${}_{\\!}$ which${}_{\\!}$ abstracts${}_{\\!}$ visual${}_{\\!}$
percep- tions${}_{\\!}$ at${}_{\\!}$ multiple${}_{\\!}$ levels${}_{\\!}$
and${}_{\\!}$ conducts${}_{\\!}$ symbolic${}_{\\!}$ reasoning${}_{\\!}$ with
such structured abstraction. To fill these fundamental gaps, we devise
LogicSeg, a holistic visual semantic parser that integrates${}_{\\!}$
neural${}_{\\!}$ inductive${}_{\\!}$ learning${}_{\\!}$ and${}_{\\!}$
logic${}_{\\!}$ reasoning${}_{\\!}$ with both${}_{\\!}$ rich${}_{\\!}$
data${}_{\\!}$ and${}_{\\!}$ symbolic${}_{\\!}$ knowledge.${}_{\\!}$
In${}_{\\!}$ particular, the semantic concepts of interest are structured as a
hierarchy,${}_{\\!}$ from${}_{\\!}$ which${}_{\\!}$ a${}_{\\!}$ set${}_{\\!}$
of${}_{\\!}$ constraints${}_{\\!}$ are${}_{\\!}$ derived for describing the
symbolic relations and formalized as first-order logic rules. After fuzzy
logic-based continuous relaxation, logical formulae are grounded onto data and
neural computational graphs, hence enabling logic-induced network training.
During inference, logical constraints are packaged into an iterative process
and injected into the network in a form of several matrix multiplications, so
as to achieve hierarchy-coherent prediction${}_{\\!}$ with${}_{\\!}$
logic${}_{\\!}$ reasoning.${}_{\\!}$ These${}_{\\!}$ designs${}_{\\!}$
together${}_{\\!}$ make LogicSeg a general and compact neural-logic machine
that is readily integrated into existing segmentation models.
Extensive experiments over four datasets with various segmentation models and
backbones verify the effectiveness and generality${}_{\\!}$ of${}_{\\!}$
LogicSeg.${}_{\\!\\!}$ We${}_{\\!}$ believe${}_{\\!}$ this${}_{\\!}$
study${}_{\\!}$ opens${}_{\\!}$ a${}_{\\!}$ new avenue${}_{\\!}$ for${}_{\\!}$
visual${}_{\\!}$ semantic${}_{\\!}$ parsing.

##  1 Introduction

Interpreting${}_{\\!}$ high-level${}_{\\!}$ semantic${}_{\\!}$ concepts of
visual stimuli is an integral aspect of human perception and cognition, and
has been a subject of interest in computer vision for nearly as${}_{\\!}$
long${}_{\\!}$ as${}_{\\!}$ this${}_{\\!}$ discipline${}_{\\!}$ has${}_{\\!}$
existed.${}_{\\!}$ As${}_{\\!}$ an${}_{\\!}$ exemplar${}_{\\!}$ task${}_{\\!}$
of${}_{\\!}$ vi- sual semantic interpretation, semantic segmentation aims to
group pixels into different semantic units. Progress in this field has been
notable since the seminal work of fully convolution networks (FCNs) [1] and
been further advanced by the recent launch of fully attention networks
(Transformer) [2].

Figure 1: (a) We humans abstract our perception in a structured manner, and
conduct reasoning through symbol manipulation over such multi-level
abstraction. (b) We aim to holistically interpret visual semantics, through
the integration of both data-driven sub-symbolic learning and symbolic
knowledge-based logic reasoning.

Despite these technological strides, we still observe current prevalent
segmentation systems lack in-depth reflection on some intrinsic nature of
human cognition. First, standard segmentation systems simply assume the
semantic concepts in the set of interest have no underlying relation and
predict all these concepts exclusively.${}_{\\!}$ By contrast, humans
interpret a scene by components. For example in Fig. 1, we can effortlessly
recognize many pieces of furniture, such as chairs and tables, and identify
various utensils, _e.g_., bottles, and plates. Such capacity of structured
understanding of visual semantics is an innate aspect of human perception [3],
complies with our way of the organization of knowledge [4, 5], and has a close
relation to many meta-cognitive skills including compositional generalization
(_i.e_., making infinite use of finite means) [6], systematicity (_i.e_.,
cognitive capacity comes in groups of related behaviours) [7], and
interpretability (_i.e_., interpreting complex concepts with simpler ones) [8,
9]. Despite its significance and ubiquity, surprisingly little has been done
on the computational modeling of structured visual perception in the
segmentation literature.${}_{\\!}$ Though${}_{\\!}$ exceptions${}_{\\!}$
exist${}_{\\!}$ [10, 11, 12, 13, 14],${}_{\\!}$ in${}_{\\!}$ general${}_{\\!}$
they are scattered, lacking systematic study. Second, the latest semantic
segmentation systems, label structure aware or not, have developed a pure sub-
symbolic learning approach.${}_{\\!}$ They enjoy the advantages of robust
distributed representation of concept entities, but struggle with explicit
reasoning with the relations among entities by discrete symbolic
representations [15]. Nevertheless, studies in cognition suggest that our
perception works at multiple levels of semantic abstraction [16], intertwined
with logical reasoning through manipulation of symbolic knowledge/concepts
[17]. For example, after recognizing many utensils from Fig. 1, we know the
scene is more likely a kitchen, rather than a bathroom or gym. This judgement
comes as a result of reasoning with some abstract knowledge, such as “utensils
typically appear
in the kitchen” and “utensils are seldom seen in the bathroom,” which are
generalized from our daily experience. The judgement of the scene type may
become a belief and in turn cause reallocation of our visual attention [18],
hence driving us to find out more relevant details, such as small forks.

Filling the gaps identified above calls for a fundamental paradigm shift: i)
moving away from pixel-wise ‘flat’ classification towards semantic structure-
aware parsing; and ii) moving away from the extreme of pure distributed
representation learning towards an ambitious hybrid which combines both
powerful sub-symbolic learning and principled symbolic reasoning. To embrace
this change, we develop LogicSeg, a structured visual parser which exploits
neural computing and symbolic logic in a neural-symbolic framework for
holistic${}_{\\!}$ visual semantic learning and reasoning.${}_{\\!}$ In
particular, given${}_{\\!}$ a${}_{\\!}$ set${}_{\\!}$ of${}_{\\!}$
hierarchically-organized${}_{\\!}$ semantic${}_{\\!}$ concepts as background
knowledge and parsing target, we first use first-order logic, a powerful
declarative language, to comprehensively specify relations among semantic
classes. After fuzzy logic based relaxation, the logical formulae of hi-
erarchy${}_{\\!}$ constraints${}_{\\!}$ can${}_{\\!}$ be${}_{\\!}$
grounded${}_{\\!}$ on${}_{\\!}$ data.${}_{\\!}$ During${}_{\\!}$ training,
each logical constraint is converted into a differentiable loss
function${}_{\\!}$ for${}_{\\!}$ gradient${}_{\\!}$ descent${}_{\\!}$
optimization.${}_{\\!}$ During${}_{\\!}$ inference,${}_{\\!}$
the${}_{\\!}$ logical${}_{\\!}$ constraints${}_{\\!}$ are${}_{\\!}$
involved${}_{\\!}$ into${}_{\\!}$ an${}_{\\!}$ iterative${}_{\\!}$
process,${}_{\\!}$ and${}_{\\!}$ calculated${}_{\\!}$ in${}_{\\!}$
matrix${}_{\\!}$ form.${}_{\\!}$ This${}_{\\!}$ not only${}_{\\!}$
ensures${}_{\\!}$ the${}_{\\!}$ obser- vance${}_{\\!}$ of${}_{\\!}$
the${}_{\\!}$ compositional${}_{\\!}$ semantic${}_{\\!}$ structure${}_{\\!}$
but${}_{\\!}$ also${}_{\\!}$ binds logic reasoning into network${}_{\\!}$
feed-forward${}_{\\!}$ prediction.

By accommodating logic-based symbolic rules into network training and
inference, our LogicSeg i) blends statistical learning with symbolic
reasoning, ii) obtains better performance, and iii) guarantees its parsing
behavior compliant with the logically specified symbolic knowledge. We also
remark that our study is relevant to a field of research called neural-
symbolic computing (NSC)${}_{\\!}$ [19, 20, 21]. With the promise of
integrating two critical cognitive abilities [22]: inductive learning (_i.e_.,
the ability to learn general principles from experience) and deductive
reasoning (_i.e_., the ability to draw logical conclusions from what has been
learned), NSC has long been a multi-disciplinary research focus and shown
superiority in certain application scenarios, such as program generation [23,
24, 25], and question answering [26, 27]. This work unlocks the potential of
NSC in visual semantic parsing – a fundamental, challenging, and large-scale
vision task.

LogicSeg${}_{\\!}$ is${}_{\\!}$ a${}_{\\!}$ principled${}_{\\!}$
framework.${}_{\\!}$ It${}_{\\!}$ is${}_{\\!}$ fully${}_{\\!}$ compatible with
existing segmentation network architectures, with only minor modification to
the classification head and a plug-and-play${}_{\\!}$ logic-induced${}_{\\!}$
inference${}_{\\!}$ module.${}_{\\!}$ We${}_{\\!}$ perform${}_{\\!}$ experi-
ments${}_{\\!}$ on${}_{\\!}$ four${}_{\\!}$ datasets${}_{\\!}$
covering${}_{\\!}$ wide${}_{\\!}$ application${}_{\\!}$ scenarios,
including${}_{\\!}$ automated-driving${}_{\\!}$ (Mapillary${}_{\\!\\!}$
Vistas${}_{\\!}$ 2.0${}_{\\!}$ [28],${}_{\\!}$ City- scapes${}_{\\!}$
[29]),${}_{\\!}$ object-centric${}_{\\!}$ (Pascal-Part [30]),${}_{\\!}$
and${}_{\\!}$ daily${}_{\\!}$ (ADE-20K [31])${}_{\\!}$ scenes.${}_{\\!}$
Experimental${}_{\\!}$ results${}_{\\!}$ show${}_{\\!}$ that,${}_{\\!}$
on${}_{\\!}$ the${}_{\\!}$ top${}_{\\!}$ of various${}_{\\!}$
segmentation${}_{\\!}$ models${}_{\\!}$ (_i.e_.,${}_{\\!}$
DeepLabV3+${}_{\\!}$ [32],${}_{\\!}$ Mask- 2Former${}_{\\!}$ [33]) and
backbones (_i.e_., ResNet-101${}_{\\!}$ [34], Swin-T${}_{\\!}$ [35]), LogicSeg
yields solid performance gains (1.12%-3.29%${}_{\\!}$ mIoU)${}_{\\!}$
and${}_{\\!}$ suppresses${}_{\\!}$ prior${}_{\\!}$ structured${}_{\\!}$
alternatives.${}_{\\!}$ The strong generalization and promising performance of
LogicSeg evidence the great potential of integrating symbolic reasoning and
sub-symbolic learning in machine perception.

##  2 Related Work

Semantic Segmentation. Since the proposal of fully convolutional networks
(FCNs) [1], research studies in pixel-level semantic interpretation have
witnessed a phenomenal growth.${}_{\\!}$ Tremendous${}_{\\!}$
progress${}_{\\!}$ has${}_{\\!}$ been${}_{\\!}$ achieved${}_{\\!}$
by,${}_{\\!}$ for${}_{\\!}$ exam- ple,${}_{\\!}$ polishing${}_{\\!}$
context${}_{\\!}$ cues${}_{\\!}$ [36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46,
47, 48, 49, 50, 51, 52], investigating boundary information${}_{\\!}$ [53, 54,
55, 56, 57], incorporating${}_{\\!}$ neural${}_{\\!}$ attention [58, 59, 60,
61, 62, 63, 64, 65, 66, 67, 68, 69, 70], adopting data structure-aware
learning${}_{\\!}$ [71, 72, 73, 74, 75], and automating network
engineering${}_{\\!}$ [76, 77, 78, 79]. More recently, the engage- ment of
advanced Transformer [2] architecture, which spe- cializes${}_{\\!}$
in${}_{\\!}$ long-range${}_{\\!}$ dependency${}_{\\!}$ modeling,${}_{\\!}$
is${}_{\\!}$ widely${}_{\\!}$ viewed${}_{\\!}$ as a promising route for
further development${}_{\\!}$ [80, 81, 82, 83, 33, 84, 85].

Though impressive, existing segmentation solutions are mainly aware of
straightforward prediction for flatten labels. They are largely blind to the
rich structures among semantic concepts and lack an explicit mechanism for
symbol manipulation/logical calculus, which is what distinguishes humans from
other animals [86, 87, 88]. This work represents a small yet solid step
towards addressing these fundamental limitations through an integrated neural-
logic machine, and inspects semantic segmentation from a brand-new standpoint.

(Eq. 9)(Eq. 11)(Eq.
13)$\mathcal{T}$$\mathcal{V}_{1}$$\mathcal{V}_{2}$$\mathcal{V}_{3}$

Figure 2: Illustration of the (a) class hierarchy $\mathcal{T}$, and (b-d)
abstract relational knowledge specified by first-order logic formulae (§3.1).

Label Structure-aware Semantic Segmentation. Till now, only a rather small
number of deep learning based segmentation models${}_{\\!}$ [10, 89, 90, 91,
13] are built with structured label taxonomies. The origin of this line of
research can be traced back to the task of image parsing${}_{\\!}$ [89, 90,
92, 93, 94, 95, 96] raised in the pre-deep learning era. Basically, image
parsing seeks for a holistic explanation of visual observation:${}_{\\!}$
scenes${}_{\\!}$ can${}_{\\!}$ be understood as a sum of novel objects, and
the objects can be further broken down into fine-grained parts. In the deep
learning era, the majority of structured segmentation models are dedicated to
human parsing${}_{\\!}$ [97, 89, 90, 98], which is customized to human-part
relation understanding. As for the case of general-purpose segmentation, there
are far rare lite- rature${}_{\\!}$ [10, 11, 12, 91, 13], and many of them
incorporate label taxonomies into the network topology, losing
generality${}_{\\!}$ [10, 11, 12]. As a notable exception, [13] converts the
task as pixel-wise multi-label classification and exploits the class hierarchy
for training regularization, with only trivial architectural change.

In a nutshell, previous efforts highlight the limits of standard segmentation
models for semantic structures. However, they typically i) resolve to stand on
the side of sub-symbolic learning,${}_{\\!}$ ii)${}_{\\!}$ make${}_{\\!}$
usage${}_{\\!}$ of${}_{\\!}$ only${}_{\\!}$ fragments${}_{\\!}$ of${}_{\\!}$
structured${}_{\\!}$ relations (for instance, the exclusion relation is
neglected by [13]), iii) lack structure-ware inference, and/or iv) rely on
sophisticated and specialized neural structures. By contrast, we formulate the
structured task into a neural-symbolic framework. We derive a comprehensive
set of symbolic relational knowledge in the form of first-order logic and
deeply embed logical constraints into network training and inference. Our
algorithm is a general framework that is applicable to existing standard
hierarchy-agnostic segmentation architectures.

Neuro-Symbolic Computing. There has been a line of research, called neural-
symbolic computing (NSC), that pursues the integration of the symbolic and
statistical paradigms of cognition [19, 20, 21]. NSC has a long history,
dating back to McCulloch and Pitts 1943 paper${}_{\\!}$ [99], even before AI
was recognized${}_{\\!}$ as${}_{\\!}$ a${}_{\\!}$ new${}_{\\!}$
scientific${}_{\\!}$ field.${}_{\\!}$ During 2000s, NSC${}_{\\!}$ received
systematic${}_{\\!}$ study [100, 101, 102, 103].${}_{\\!}$ Early NSC systems
were meticulously designed for hard logic reasoning, but they are
far${}_{\\!}$ less${}_{\\!}$ trainable,${}_{\\!}$ and${}_{\\!}$
fall${}_{\\!}~{}$short${}_{\\!}~{}$when${}_{\\!}~{}$solving${}_{\\!}~{}$real-
world${}_{\\!}$ pro-
blems. NSC${}_{\\!}$ has${}_{\\!}$ recently${}_{\\!}$ ushered in its
renaissance, since it shows promise of reconciling statistical learning of
neural networks and logic reasoning of abstract knowledge – which is viewed as
a key enable to the next generation of AI${}_{\\!}$ [104, 105].${}_{\\!}$
Specifically,${}_{\\!}$ recent${}_{\\!}$ NSC${}_{\\!}$ systems${}_{\\!}$ [106,
107]${}_{\\!}$ show the possibility for modern neural networks to manipulate
abstract knowledge with diverse forms of symbolic representation, including
knowledge graph [108, 109, 110], propositional logic [111, 112, 113], and
first-order${}_{\\!}$ logic [114, 115, 116].${}_{\\!}$ They${}_{\\!}$
also${}_{\\!}$ demonstrate successful application in several domains and
disciplines, _e.g_., scientific discovery [117, 118], program generation
[23, 24, 25], (visual) question-answering [26, 27], robot planning [119,
120, 121], and mathematical reasoning [122, 123, 124].

To date, none of NSC systems reports advanced performance in large-scale
vision, to our best knowledge. In this work, we take the lead to promote and
implement the idea of conciliating the methodologies of symbolic and neural
paradigms,${}_{\\!}$ in${}_{\\!}$ visual${}_{\\!}$ semantic${}_{\\!}$
interpretation.${}_{\\!}$ Moreover,${}_{\\!}$ many previous NSC
systems${}_{\\!}$ only${}_{\\!}$ exploit${}_{\\!}$ logical${}_{\\!}$
constraints during network training${}_{\\!}$ [113, 125, 126, 127, 116, 128],
while our solution is more favored as logic rules are involved throughout
network training${}_{\\!}$ and${}_{\\!}$ inference.${}_{\\!}$ As${}_{\\!}$
a${}_{\\!}$ result,${}_{\\!}$ impressive${}_{\\!}$ performances across diverse
challenging datasets are delivered, and in turn, provide solid empirical
evidence for the power of NSC.

##  3 Methodology

Task${}_{\\!}$ Setup${}_{\\!}$ and${}_{\\!}$ Notations.${}_{\\!}$ In${}_{\\!}$
this${}_{\\!}$ work${}_{\\!}$ we${}_{\\!}$ are${}_{\\!}$ interested${}_{\\!}$
in structured${}_{\\!}$ visual${}_{\\!}$ parsing${}_{\\!}$ [13]${}_{\\!}$
–${}_{\\!}$ a${}_{\\!}$ more${}_{\\!}$ challenging${}_{\\!}$ yet${}_{\\!}$
realis- tic${}_{\\!}$ setting${}_{\\!}$ for${}_{\\!}$ semantic${}_{\\!}$
segmentation${}_{\\!}$ –${}_{\\!}$ where${}_{\\!}$ both${}_{\\!}$ semantic
concepts and their relations are considered in a form of a tree-
shaped${}_{\\!}$ class${}_{\\!}$ hierarchy${}_{\\!}$
$\mathcal{T}\\!=\\!\langle\mathcal{V},\mathcal{E}\rangle$${}_{\\!}$.${}_{\\!}$
The${}_{\\!}$ node${}_{\\!}$ set${}_{\\!}$
$\mathcal{V}\\!=\\!\cup^{L}_{l=1\\!}\mathcal{V}_{l}$ represents the
classes/concepts at $L$ abstraction levels. For instance in Fig.${}_{\\!}$
2(a), the leaf nodes $\mathcal{V}_{1}$ are the finest classes (_e.g_., chair,
pot), while the internal nodes are higher-level concepts (_e.g_.,
furniture,${}_{\\!}$ utensil),${}_{\\!}$ and${}_{\\!}$ the${}_{\\!}$
roots${}_{\\!}$ $\mathcal{V}_{L\\!}$ are${}_{\\!}$ the${}_{\\!}$
most${}_{\\!}$ abstract${}_{\\!}$ ones${}_{\\!}$ (_e.g_.,${}_{\\!}$
object).${}_{\\!}$ The${}_{\\!}$ edge${}_{\\!}$ set${}_{\\!}$
$\mathcal{E}_{\\!}$ encodes${}_{\\!}$ relational knowledge${}_{\\!}$
among${}_{\\!}$ classes.${}_{\\!}$ For${}_{\\!}$ example,${}_{\\!}$ a
directed${}_{\\!}$ edge${}_{\\!}$
$u_{\\!\\!}\rightarrow_{\\!\\!}v\\!\in\\!\mathcal{E}$${}_{\\!}$ denotes a
part-of relation between classes $u,v\\!\in\\!\mathcal{V}$ in adjacent levels
(_e.g_.,${}_{\\!}$ utensil$\rightarrow$pot).

Given $\mathcal{T}$, the${}_{\\!}$ target${}_{\\!}$ goal${}_{\\!}$
is${}_{\\!}$ to${}_{\\!}$ assign${}_{\\!}$ each${}_{\\!}$ pixel a valid root-
to-leaf path in $\mathcal{T}$. For instance, associating a pixel with
object$\rightarrow$utensil$\rightarrow$pot is valid, yet with
object$\rightarrow$
furniture$\rightarrow$pot is invalid. Thus standard semantic segmentation can
be viewed as a specific case of such structured setting — only assigning
pixels with one single class label from the leaf nodes $\mathcal{V}_{1}$
without considering the hierarchy.

Figure 3: Illustration of our logic-induced network training (§3.2). For
clarity, the pixel-wise binary cross-entropy loss is omitted.

Algorithmic${}_{\\!}$ Overview.${}_{\\!}$ LogicSeg${}_{\\!}$ is${}_{\\!}$
a${}_{\\!}$ unified,${}_{\\!}$ neural-logic learning and reasoning model for
visual parsing, supported by${}_{\\!}$ large-scale${}_{\\!}$ data${}_{\\!}$
and${}_{\\!}$ the${}_{\\!}$ structured${}_{\\!}$ symbolic${}_{\\!}$
knowledge${}_{\\!}$ $\mathcal{T}$.

  * •

From the neural aspect, LogicSeg is model-agnostic. After dense feature
extraction, its classification head outputs a total of $|\mathcal{V}|$
sigmoid-normalized scores, _i.e_., $\bm{s}\\!\in\\![0,1]^{|\mathcal{V}|}$,
over${}_{\\!}$ all${}_{\\!}$ the${}_{\\!}$ classes${}_{\\!}$ $\mathcal{V}$
for${}_{\\!}$ each${}_{\\!}$ pixel,${}_{\\!}$ like${}_{\\!}$ [13].${}_{\\!}$
Here${}_{\\!}$ $|_{\\!}\cdot_{\\!}|_{\\!}$ counts its${}_{\\!}$
elements.${}_{\\!}$ A${}_{\\!}$ set${}_{\\!}$ of${}_{\\!}$ logic${}_{\\!}$
rules,${}_{\\!}$ derived${}_{\\!}$ from${}_{\\!}$ $\mathcal{T}$, are injected
into network training and inference.

  * •

From the logic aspect, LogicSeg uses first-order logic to express the complex
and abstract relational knowledge in${}_{\\!}$ $\mathcal{T}$.${}_{\\!}$
The${}_{\\!}$ network${}_{\\!}$ is${}_{\\!}$ learnt${}_{\\!}$ as${}_{\\!}$
approximation${}_{\\!}$ of${}_{\\!}$ logic${}_{\\!}$ predi- cates by following
the logical specifications. Once trained, it conducts iterative reasoning on
the basis of logic rules.

After introducing our logic based visual relational knowledge representation
(§3.1), we will elaborate on our logic-induced network training (§3.2) and
inference (§3.3) strategies.

###  3.1 Parsing Visual Semantics with Logic Rules

We formalize our target task — learning and reasoning vi- sual${}_{\\!}$
semantics${}_{\\!}$ with${}_{\\!}$ logic${}_{\\!}$ —${}_{\\!}$ as${}_{\\!}$
a${}_{\\!}$ triple${}_{\\!}$
$\langle\mathcal{T},_{\\!}\mathcal{X},_{\\!}\Pi\rangle$.${}_{\\!}$
$\mathcal{X}$${}_{\\!}$ is${}_{\\!}$ a${}_{\\!}$ data collection,${}_{\\!}$
_i.e_.,${}_{\\!}$
$\mathcal{X}\\!=\\!\\{(x_{k},\bm{y}_{k})\\}_{k=1}^{K}$,${}_{\\!}$
where${}_{\\!}$ $x_{k\\!}$ is${}_{\\!}$ a${}_{\\!}$ pixel${}_{\\!}$ data
point,${}_{\\!}$ and${}_{\\!}$
$\bm{y}_{k\\!}\\!\in_{\\!}\\!\\{0,1\\}^{|\mathcal{V}|\\!}$ is${}_{\\!}$
its${}_{\\!}$ groundtruth${}_{\\!}$ symbolic${}_{\\!}$ descrip- tion${}_{\\!}$
in${}_{\\!}$ terms${}_{\\!}$ of${}_{\\!}$ the${}_{\\!}$ semantic${}_{\\!}$
hierarchy${}_{\\!}$ $\mathcal{T}$.${}_{\\!}$ $\Pi_{\\!}$ is${}_{\\!}$
a${}_{\\!}$ set${}_{\\!}$ of${}_{\\!}$ hierar- chy${}_{\\!}$ rules${}_{\\!}$
declaratively${}_{\\!}$ expressed${}_{\\!}$ by${}_{\\!}$ first-order${}_{\\!}$
logic,${}_{\\!}$ contain- ing${}_{\\!}$ i)${}_{\\!}$ constants,${}_{\\!}$
_e.g_.,${}_{\\!}$ pixel samples${}_{\\!}$ $x_{1},x_{2},\cdots$;${}_{\\!}$
ii)${}_{\\!}$ variables${}_{\\!}$ ranging${}_{\\!}$ over${}_{\\!}$
constants,${}_{\\!}$ _e.g_.,${}_{\\!}$ $x$; and iii) unary predicates, one for
each class $v\\!\in\\!\mathcal{V}$, denote the semantics of variables and
return true and false, _e.g_., $\texttt{bed}(x)\\!=\\!\textit{true}$ states
the fact that pixel${}_{\\!}$ $x_{\\!}$ belongs${}_{\\!}$ to${}_{\\!}$
a${}_{\\!}$ bed.${}_{\\!}$ A${}_{\\!}$ logic${}_{\\!}$ rule/formula${}_{\\!}$
is${}_{\\!}$ a${}_{\\!}$ sequence${}_{\\!}$ of${}_{\\!}$ finite${}_{\\!}$
predicates${}_{\\!}$ with${}_{\\!}$ connectives${}_{\\!}$ (_i.e_.,${}_{\\!}$
$\land$,${}_{\\!}$ $\lor$,${}_{\\!}$ $\neg$,${}_{\\!}$
$\Rightarrow$)${}_{\\!}$ and${}_{\\!}$ quan- tifiers (_i.e_., $\forall$,
$\exists$), and organized in prenex form in our case.

Concretely, $\Pi$ is composed of three types of rules, _i.e_., composition,
decomposition, and exclusion, for comprehensively describing the structured
symbolic knowledge $\mathcal{T}$.

$\bullet$ _Composition Rule_ (C-rule) expresses our knowledge about the
composition relations between semantic concepts, such as${}_{\\!}$
“bed${}_{\\!}$ and${}_{\\!}$ chair${}_{\\!}$ are${}_{\\!}$
(subclasses${}_{\\!}$ of)${}_{\\!}$ furniture,”${}_{\\!}$ in${}_{\\!}$
a${}_{\\!}$ form${}_{\\!}$ of:

$\displaystyle\small\small\forall x(\texttt{bed}(x){}$
$\displaystyle\Rightarrow\texttt{furniture}(x)),$ (1)
$\displaystyle\small\forall x(\texttt{chair}(x)$
$\displaystyle\Rightarrow\texttt{furniture}(x)),$

where bed, chair, furniture are predicates, and ‘$\phi\Rightarrow\varphi$’
indicates $\varphi$ is a logical consequence of antecedence $\phi$.

######  Definition 3.1.1 (C-rule).

If one class is labeled true, its superclass should be labeled true
(Fig.${}_{\\!}$ 2(b)):

$\displaystyle\small\forall x(v(x)\Rightarrow p_{v}(x)),$ (2)

where${}_{\\!}$ $p_{v\\!}$ is${}_{\\!}$ the${}_{\\!}$ parent${}_{\\!}$
node${}_{\\!}$ of${}_{\\!}$ $v_{\\!}$ in${}_{\\!}$ $\mathcal{T}$,${}_{\\!}$
_i.e_.,${}_{\\!}$ $p_{v\\!}\\!\rightarrow\\!v\\!\in\\!\mathcal{E}_{\\!}$
(the${}_{\\!}$ tree structure${}_{\\!}$ of${}_{\\!}$ $\mathcal{T}_{\\!}$
restricts${}_{\\!}$ each${}_{\\!}$ class${}_{\\!}$ to${}_{\\!}$
possess${}_{\\!}$ only${}_{\\!}$ one${}_{\\!}$ super- class).${}_{\\!}$
C-rule${}_{\\!}$ generalizes${}_{\\!}$ the${}_{\\!}$ famous${}_{\\!}$ tree-
property [129, 130].

$\bullet$${}_{\\!}$ _Decomposition ${}_{\\!}$ Rule${}_{\\!}$_
(D-rule)${}_{\\!}$ states${}_{\\!}$ our${}_{\\!}$ knowledge${}_{\\!}$ about
the${}_{\\!}$ decomposition${}_{\\!}$ relations among${}_{\\!}$
semantic${}_{\\!}$ concepts,${}_{\\!}$ such as${}_{\\!}$ “furniture${}_{\\!}$
is${}_{\\!}$ the${}_{\\!}$ superclass${}_{\\!}$ of${}_{\\!}$ bed,${}_{\\!}$
chair,${}_{\\!}$ $\cdots$,${}_{\\!}$ table,”${}_{\\!}$ via:

$\displaystyle\small\forall x(\texttt{furniture}(x)\Rightarrow$
$\displaystyle\texttt{bed}(x)\lor\texttt{chair}(x)_{\\!}~{}\lor$ (3)
$\displaystyle\cdots\lor\texttt{tabel}(x)).$

######  Definition 3.1.2 (D-rule).

${}_{\\!\\!}$If${}_{\\!}$ one${}_{\\!}$ class${}_{\\!}$ is${}_{\\!}$
labeled${}_{\\!}$ true,${}_{\\!}$ at${}_{\\!}$ least${}_{\\!}$ one of its
subclasses should be labeled true (Fig.${}_{\\!}$ 2(c)):

$\displaystyle\small\forall x(v(x)\Rightarrow c^{1}_{v}(x)\lor
c^{2}_{v}(x)\lor\cdots\lor c^{N}_{v}(x)),$ (4)

where${}_{\\!}$ $c^{n}_{v}\\!\in\\!\mathcal{C}_{v{\\!}}$ are${}_{\\!}$
all${}_{\\!}$ the${}_{\\!}$ child${}_{\\!}$ nodes${}_{\\!}$ of${}_{\\!}$
$v_{\\!}$ in${}_{\\!}$ $\mathcal{T}$,${}_{\\!}$ _i.e_.,${}_{\\!}$
$v\\!\rightarrow\\!c^{n}_{v}\\!\in\\!\mathcal{E}$. C-rule and D-rule are not
equivalent. For instance in Eq. 1, $\texttt{bed}(x)$ is sufficient but not
necessary for $\texttt{furniture}(x)$: given${}_{\\!}$ the${}_{\\!}$
fact${}_{\\!}$ “$x_{\\!}$ is${}_{\\!}$ furniture”,${}_{\\!}$ we${}_{\\!}$
cannot${}_{\\!}$ conclude${}_{\\!}$ “$x_{\\!}$ is${}_{\\!}$ bed”.

$\bullet$ Exclusion Rule (E-rule) specifies our knowledge about mutual
exclusion relations between sibling concepts, such as “a bed cannot be at the
same time a chair,” in a form of:

$\displaystyle\small\forall
x(\texttt{bed}(x)\Rightarrow\neg\texttt{chair}(x)).$ (5)

######  Definition 3.1.3 (E-rule).

If one class is labeled true, all its sibling classes should be labeled false
(Fig.${}_{\\!}$ 2(d)):

$\displaystyle\small\forall x(v(x)\Rightarrow\neg a^{1}_{v}(x)\land\neg
a^{2}_{v}(x)\land\cdots\land\neg a^{M}_{v}(x)),$ (6)

where${}_{\\!}$ $a^{m\\!}_{v\\!}\\!\in\\!\mathcal{A}_{v\\!}$ are${}_{\\!}$
all${}_{\\!}$ the${}_{\\!}$ peer${}_{\\!}$ nodes${}_{\\!}$ of${}_{\\!}$
$v_{\\!}$ in${}_{\\!}$ $\mathcal{T}$${}_{\\!}$.${}_{\\!}$ Note${}_{\\!}$
that${}_{\\!}$ E-rule is${}_{\\!}$ ignored${}_{\\!}$ by${}_{\\!}$
many${}_{\\!}$ hierarchy-aware${}_{\\!}$ algorithms [13, 131, 132].

###  3.2 Logic-Induced Training

So${}_{\\!}$ far,${}_{\\!}$ we${}_{\\!}$ shown${}_{\\!}$ the${}_{\\!}$
logic${}_{\\!}$ rules${}_{\\!}$ $\Pi$${}_{\\!}$ provide${}_{\\!}$ LogicSeg
a${}_{\\!}$ flexible${}_{\\!}$ language${}_{\\!}$ for${}_{\\!}$
comprehensively${}_{\\!}$ expressing${}_{\\!}$ the${}_{\\!}$ complex meronymy
and exclusion relations among symbolic concepts in the hierarchy
$\mathcal{T}$. Unfortunately, these${}_{\\!}$ rules${}_{\\!}$ are${}_{\\!}$
logic${}_{\\!}$ formulae${}_{\\!}$ working${}_{\\!}$ with${}_{\\!}$
variables${}_{\\!}$ (assuming a boolean value), and non-differentiable logic
symbols (_e.g_., $\forall$, $\Rightarrow$). This prevents the integration with
end-to-end network learning.

(Eq. 16)(Eq. 17)(Eq. 18)

Figure 4: Illustration of our logic-induced inference (§3.3). (a-b) Iterative
reasoning is made by exchanging and absorbing messages between nodes,
following the logic rules $\Pi$. For clarity, we only show the message
creation (Eq. 16) and aggregation (Eq. 17) stages for one single node. (c)
Structured parsing (Eq. 18) is conducted by selecting the top-scoring path
$\mathcal{P}^{*\\!}$ (highlighted in red) after logic-guided iterative
reasoning. (d) With logic-induced inference, LogicSeg is able to generate more
accurate and hierarchy-compliant predictions.

Inspired by [133, 128], a fuzzy logic based grounding process${}_{\\!}$
is${}_{\\!}$ adopted${}_{\\!}$ to${}_{\\!}$ interpret${}_{\\!}$
logic${}_{\\!}$ formulae${}_{\\!}$ as${}_{\\!}$ differentiable fuzzy${}_{\\!}$
relations${}_{\\!}$ on${}_{\\!}$ real${}_{\\!}$ numbers${}_{\\!}$
for${}_{\\!}$ neural${}_{\\!}$ computing${}_{\\!}$ (Fig.${}_{\\!}$ 3).

Fuzzy relaxation. Fuzzy logic is a form of soft probabilistic logic. It deals
with reasoning that is approximate instead of fixed and exact; variables have
a truth degree that ranges in $[0,1]$: zero and one meaning that the variable
is false and true with certainty, respectively [134]. Hence we can ground
predicates onto segmentation network outputs. For instance, given a pixel
sample $x$, corresponding network prediction score w.r.t. class bed is a
grounded predicate w.r.t. $\texttt{bed}(x)$. Logical connectives, _i.e_.,
$\land,\lor,\neg,\Rightarrow$ are approximated with fuzzy operators, _i.e_.,
t-norm, t-conorm, fuzzy negation, and fuzzy implication. As suggested
by${}_{\\!}$ [133], we adopt the operators in Goguen fuzzy logic [135] and
Gödel fuzzy logic [136]:

$\displaystyle\small\phi\land\varphi$ $\displaystyle=\phi\cdot\varphi,\ \ \ \
~{}~{}\phi\lor\varphi=\texttt{max}(\phi,\varphi),$ (7) $\displaystyle\neg\phi$
$\displaystyle=1-\phi,\ \ \ \ \phi\Rightarrow\varphi=1-\phi+\phi\cdot\varphi.$

The existential quantifier $\exists$ and universal quantifier $\forall$ are

approximated in a form of generalized mean:

$\displaystyle\small\exists x\phi(x)={}$
$\displaystyle\textstyle(\frac{1}{K}\\!\textstyle\sum\nolimits_{k=1}^{K}\phi(x_{k})^{q})^{\frac{1}{q}},$
(8) $\displaystyle\forall x\phi(x)={}$ $\displaystyle
1\\!-\\!\textstyle(\frac{1}{K}\\!\textstyle\sum\nolimits_{k=1}^{K}(1\\!-\\!\phi(x_{k}))^{q})^{\frac{1}{q}},$

where $q\\!\in\\!\mathbb{Z}$. Please refer to${}_{\\!}$ [133, 128] for
detailed discussion regarding${}_{\\!}$ the${}_{\\!}$ rationale${}_{\\!}$
behind${}_{\\!}$ such${}_{\\!}$ approximation${}_{\\!}$ of${}_{\\!}$
$\exists_{\\!}$ and${}_{\\!}$ $\forall$.

Logic Loss. With fuzzy relaxation, we are ready to convert our first-order
logic rules $\Pi$ into loss functions.

$\bullet$ _C-rule Loss._ For a non-root node
$v\\!\in\\!\mathcal{V}/\mathcal{V}_{L}$, its corres- ponding C-rule${}_{\\!}$
(cf.${}_{\\!}$ Eq.${}_{\\!\\!}$ 2) is grounded as:

$\displaystyle\small\mathcal{G}_{C}(v)\\!=1\\!-\\!\textstyle\Big{(}\frac{1}{K}\\!\sum_{k=1}^{K}(\bm{s}_{k}[v]\\!-\\!\bm{s}_{k}[v]\cdot\bm{s}_{k}[p_{v}])^{q}\Big{)}^{\\!\frac{1}{q}},$
(9)

where $\bm{s}_{k}[v]\\!\in\\![0,1]$ refers to the score (confidence) of
$x_{k}$ for class $v$. Then the C-rule based training objective is given as:

$\displaystyle\small\mathcal{L}_{C}\\!=\\!\textstyle\frac{1}{|\mathcal{V}|-|\mathcal{V}_{L}|}\\!\\!\textstyle\sum_{v\in\mathcal{V}/\mathcal{V}_{L}}\\!1-\mathcal{G}_{C}(v).$
(10)

$\bullet$ _D-rule Loss._ For a non-leaf node
$v\\!\in\\!\mathcal{V}/\mathcal{V}_{1}$, its corres- ponding D-rule${}_{\\!}$
(cf.${}_{\\!}$ Eq.${}_{\\!\\!}$ 4) is grounded as:

$\displaystyle\small\\!\\!\\!\\!\\!\\!\\!\\!\mathcal{G}_{D}(v)\\!=\\!1\\!-\\!\textstyle\Big{(}\\!\frac{1}{K}\\!\\!\textstyle\sum\limits_{k=1}^{K}\\!\\!\big{(}\bm{s}_{k}[v]\\!-\\!\bm{s}_{k}[v]\\!\cdot\\!\texttt{max}(\\{\bm{s}_{k}[c^{n}_{v}]\\}_{n})\big{)}^{\\!q}\Big{)}^{\\!\frac{1}{q}}.$
(11)

Similarly, our D-rule loss is given as:

$\displaystyle\small\mathcal{L}_{D}\\!=\\!\textstyle\frac{1}{|\mathcal{V}|-|\mathcal{V}_{1}|}\\!\\!\textstyle\sum\nolimits_{v\in\mathcal{V}/\mathcal{V}_{1}}\\!1-\mathcal{G}_{D}(v).$
(12)

$\bullet$ _E-rule Loss._ During the grounding of E-rule${}_{\\!}$
(cf.${}_{\\!}$ Eq.${}_{\\!\\!}$ 6), we first translate such one-vs-all
exclusion statement to a semantically equivalent expression, _i.e_., the
aggregation of multiple one-vs-one exclusion
($\\{(v(x)_{\\!}\Rightarrow_{\\!}\neg
a^{1}_{v}(x)),\cdots\\!,\\{(v(x)_{\\!}\Rightarrow_{\\!}\neg
a^{M}_{v}(x))\\}$). Adopting such translation is to avoid the sorites paradox,
_i.e_., a long chain of only slightly unreliable deductions can be very
unreliable [137] (_e.g_., $0.9^{10}\\!\approx\\!0.34$), happened during
approximating a series of $\land$. Then, for each node
$v\\!\in\\!\mathcal{V}$, its corresponding E-rule${}_{\\!}$ is grounded as:

$\displaystyle\small\\!\\!\\!\\!\\!\\!\\!\\!\mathcal{G}_{E}(v)\\!=\\!1\\!-\\!\textstyle\frac{1}{M}\\!\\!\textstyle\sum_{m=1}^{M}\\!\\!\Big{(}\\!\frac{1}{K}\\!\\!\textstyle\sum_{k=1}^{K}\\!\\!\big{(}\bm{s}_{k}[v]\\!\cdot\\!\bm{s}_{k}[a^{m}_{v}]\big{)}^{\\!q}\Big{)}^{\\!\frac{1}{q}}.$
(13)

Similarly, our E-rule loss is given as:

$\displaystyle\small\mathcal{L}_{E}\\!=\\!\textstyle\frac{1}{|\mathcal{V}|}\\!\\!\sum\nolimits_{v\in\mathcal{V}}1-\mathcal{G}_{E}(v).$
(14)

In this way, it is possible to backpropagate the gradient from

the logic loss into the network. The network is essentially learned as neural
predicates obeying the logical constraints. It is worth mentioning that, due
to large-scale training, it is infeasible to compute the full semantics of
$\forall$; batch-training can be viewed as sampling based approximation [133].

Our overall training target is organized as:

$\displaystyle\small\mathcal{L}\\!=\\!\alpha(\mathcal{L}_{C}\\!+\\!\mathcal{L}_{D}\\!+\\!\mathcal{L}_{E})\\!+\\!\textstyle\frac{1}{K}\\!\\!\textstyle\sum\nolimits_{k=1\\!}^{K}\mathcal{L}_{\text{BCE}}(\bm{s}_{k},\bm{y}_{k}).$
(15)

Here${}_{\\!}$ $\bm{y}\\!\in\\!\\{0,_{\\!}1\\}^{|\mathcal{V}|\\!}$
is${}_{\\!}$ the${}_{\\!}$ groundtruth,${}_{\\!}$
$\mathcal{L}_{\text{BCE}\\!}$ is${}_{\\!}$ the${}_{\\!}$ binary${}_{\\!}$
cross- entropy${}_{\\!}$ loss,${}_{\\!}$ and${}_{\\!}$ the${}_{\\!}$
coefficient${}_{\\!}$ is${}_{\\!}$ empirically${}_{\\!}$ set${}_{\\!}$
as${}_{\\!}$ $\alpha\\!=\\!0.2$.

###  3.3 Logic-Induced Inference

We just showed that LogicSeg can approximate the pre- dicates by integrating
symbolic logic constraints into large-scale network training. However, during
inference, there is no explicit way to ensure the alignment between the class
hierarchy $\mathcal{T}$ and network prediction, neither sound reasoning with
the logic rules $\Pi$. We thus put forward logic-induced${}_{\\!}$
reasoning${}_{\\!}$ (Fig.${}_{\\!}$ 4),${}_{\\!}$ where${}_{\\!}$
the${}_{\\!}$ logic${}_{\\!}$ rules${}_{\\!}$ $\Pi_{\\!}$ are${}_{\\!}$
encapsulated into an iterative optimization process. Such process is non-
learnable, based on only matrix operations and thus can be seamlessly embedded
into network feed-forward inference, yielding an elegant yet compact neural-
logic visual parser.

Our solution is built upon the classic message passing algorithm which is to
estimate the marginal likelihood for a given tree structure by iteratively
exchanging messages between nodes.${}_{\\!}$ Specifically,${}_{\\!}$
at${}_{\\!}$ each${}_{\\!}$ iteration,${}_{\\!}$ for${}_{\\!}$ each${}_{\\!}$
pixel sample $x_{k}$, node $v\\!\in\\!\mathcal{V}$ sends different types of
messages to different neighboring nodes, according to the logic rules $\Pi$:

$\displaystyle\small\\!\\!\\!\\!\\!\\!\text{{C}-message}\\!:\\!~{}h^{C}_{v,p_{v}\\!}$
$\displaystyle\\!=\\!v(x_{k})\Rightarrow p_{v}(x_{k})$
$\displaystyle\\!=\\!1\\!-\\!\bm{s}_{k}[v]\\!+\\!\bm{s}_{k}[v]\\!\cdot_{\\!}\bm{s}_{k}[p_{v}],~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\small\\!\\!\\!\\!\\!\\!\text{{D}-message}\\!:\\!~{}h^{D}_{v,c^{n}_{v}\\!}$
$\displaystyle\\!=\\!v(x_{k})\\!\Rightarrow\\!c^{1}_{v}(x_{k})\\!\lor\\!\cdots\\!\lor\\!c^{N}_{v}(x_{k})$
(16)
$\displaystyle\\!=\\!1\\!-\\!\bm{s}_{k}[v]\\!+\\!\bm{s}_{k}[v]\\!\cdot\\!\texttt{max}(\\{\bm{s}_{k}[c^{n}_{v}]\\}_{n}),$
$\displaystyle\small\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\text{{E}-message}\\!:_{\\!}\\!~{}h^{E}_{v,a^{m}_{v}\\!}$
$\displaystyle\\!=\\!-1{\\!}\cdot{\\!}\big{(}v(x_{k})\\!\Rightarrow{\\!}\neg
a^{1}_{v}(x_{k})\\!\land\\!\cdots\\!\land\\!\neg
a^{M\\!}_{v}(x_{k})\big{)}\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\\!=\\!-_{\\!}~{}(1\\!-\\!\textstyle\frac{1}{M}_{\\!}\\!\sum_{m=1}^{M}\\!\bm{s}_{k}[v]_{\\!}\cdot_{\\!}\bm{s}_{k}[a_{v}^{m}]).\\!\\!\\!\\!$

Node $v$ is updated by aggregating the received messages:

$\displaystyle\small\\!\\!\\!\\!\\!\\!\bm{s}_{k}[v]\\!\leftarrow\\!\bm{s}_{k}[v]$
$\displaystyle\\!+\\!\textstyle\frac{1}{N}\\!\\!\sum\nolimits_{c^{n}_{v}\in\mathcal{C}_{v}\\!\\!}\bm{s}_{k}[c^{n}_{v}]\\!\cdot\\!h^{C}_{c^{n}_{v},v}\\!+\\!\bm{s}_{k}[p_{v}]\\!\cdot\\!h^{D}_{p_{v},v}\\!\\!\\!$
(17)
$\displaystyle\\!+\\!\textstyle\frac{1}{M}\\!\\!\sum\nolimits_{a^{m}_{v}\in\mathcal{A}_{v}\\!\\!}\bm{s}_{k}[a^{m}_{v}]\\!\cdot\\!h^{E}_{a^{m}_{v},v}.$

Each message (cf.${}_{\\!}$ Eq.${}_{\\!}$ 16) accounts for the certainty
degree that $v$ satisfies the corresponding logic rule (cf.${}_{\\!}$ §3.1)
when being${}_{\\!}$ grounded${}_{\\!}$ on${}_{\\!}$ pixel${}_{\\!}$
data${}_{\\!}$ point${}_{\\!}$ $x_{k}$,${}_{\\!}$ with${}_{\\!}$
fuzzy${}_{\\!}$ logic${}_{\\!}$ based approximation${}_{\\!}$ (cf.
§3.2).${}_{\\!}$ Intuitively,${}_{\\!}$ the${}_{\\!}$ more${}_{\\!}$
certainty${}_{\\!}$ a${}_{\\!}$ node meets the logic rules, the more message
it can propagate to other nodes. Note that, $v$ creates a negative message
$h^{E}_{v,a^{m}_{v}\\!}$ to “suppress” other peer nodes due to their exclusion
relations. In Eq.${}_{\\!}$ 17, the received messages are weighted by the
confi- dence of the source nodes themselves – the grounded predi-
cates,${}_{\\!}$ _i.e_.,${}_{\\!}$ $\bm{s}_{k}[c^{n}_{v}]$,${}_{\\!}$
$\bm{s}_{k}[p_{v}]$,${}_{\\!}$ and${}_{\\!}$
$\bm{s}_{k}[a^{m}_{v}]$.${}_{\\!}$ After${}_{\\!}$ each${}_{\\!}$ iteration,
the score vector $\bm{s}_{k}$ is softmax-normalized per hierarchy level.

Finally, each pixel $x_{k}$ is associated with the top-scoring root-to-leaf
path in the hierarchy $\mathcal{T}$ (red path in Fig. 4(c)):

$\displaystyle\small\mathcal{P}^{*}=\\{v^{*}_{1},\cdots,v^{*}_{L}\\}=\\!\operatorname*{argmax}_{\mathcal{P}\subset\mathcal{T}}\textstyle\sum\nolimits_{v^{\mathcal{P}}\in\mathcal{P}}\bm{s}_{k}[v^{\mathcal{P}}],$
(18)

where
$\mathcal{P}_{\\!}\\!=\\!\\{v^{\mathcal{P}}_{1},\cdots_{\\!},v^{\mathcal{P}}_{L}\\}\\!\subset\\!\mathcal{T}$
indicates a feasible root-to-leaf path in $\mathcal{T}$, _i.e_., $\forall
v^{\mathcal{P}\\!}_{l},v^{\mathcal{P}}_{l-1\\!}\in\\!\mathcal{\mathcal{P}}\\!\Rightarrow\\!v^{\mathcal{P}\\!\\!}_{l\\!}\\!\rightarrow\\!v^{P}_{l-1\\!}\in\\!\mathcal{E}$.

It is easy to find that all the logic-induced inference steps (cf.${}_{\\!}$
Eq.${}_{\\!}$ 16-18) can be formulated in matrix form with only a couple of
matrix multiplications (see corresponding pseudo-code in the supplementary).
Hence it is efficient on GPU and can be straightforward injected into the
network, making LogicSeg a fully-integrated neural-logic machine. In practice,
$2$-iteration message passing is enough for robust prediction. Through logic-
induced reasoning (cf.${}_{\\!}$ Eq.${}_{\\!}$ 17) and hierarchy-aware parsing
(cf.${}_{\\!}$ Eq.${}_{\\!}$ 18), LogicSeg is able to i) obtain improved
performance, and ii) guarantee the parsing results to respect the hierarchy
$\mathcal{T}$, with iii) only negligible speed delay (about 3.8%). See §4.4
for related experiments.

##  4 Experiment

###  4.1 Experimental Setup

Datasets.${}_{\\!}$ We${}_{\\!}$ conduct${}_{\\!}$ extensive${}_{\\!}$
experiments${}_{\\!}$ on${}_{\\!}$ four${}_{\\!}$ datasets, _i.e_.,
Mapillary${}_{\\!}$ Vistas${}_{\\!}$ 2.0 [28], Cityscapes [29], Pascal-
Part-108 [30], and ADE20K${}_{\\!}$ [31]. The four datasets are selected to
cover the rich application scenarios of semantic segmentation, including urban
street segmentation for automated driving (_i.e_., [28, 29]), object part
parsing (_i.e_., [30]), and fine-grained understanding of daily scenes
(_i.e_., [31]), so as to comprehensively examine the utility of our algorithm.

  * •

Mapillary${}_{\\!}$ Vistas${}_{\\!}$ 2.0 is a large-scale urban scene dataset.
It contains $18,000$/$2,000/5,000$ images for train/val/ test. A three-level
semantic hierarchy, covering $4/16/$ $124$ concepts, is officially provided
for dense annotation.

  * •

Cityscapes has $2,975$/$500$/$1,524$ finely annotated, urban street images for
train/val/test. The label hierarchy consists of $19$ fine-gained concepts and
$6$ superclasses.

  * •

Pascal-Part-108 is the largest object part parsing dataset. It consists of
$4,998$/$5,105$ images for train/test. To establish the class hierarchy, we
group $108$ part-level labels into $20$ object-level categories, as in [138,
139, 140, 141].

  * •

ADE20K is a large-scale generic scene parsing dataset. It is divided into
$20,210$/$2,000$/$3,000$ images for train/ val/test. It provides pixel-wise
annotations for $150$ fine-grained semantic classes, from which a three-layer
label hierarchy (with $3$/$14$/$150$ concepts) can be derived.

Evaluation Metric. We adopt the standard metric, mean intersection-over-union
(mIoU), for evaluation. For detailed performance analysis, the score is
reported for each hierarchy level $l$ (denoted as mIoUl), as suggested by [89,
13].

Base Models and Competitors. To demonstrate our wide benefit, we approach our
algorithm on two famous segmentation architectures, _i.e_., DeepLabV3+ [32]
and Mask2For- mer [33], with ResNet-101 [34] and Swin-T [35] backbones. For
performance comparison, we involve several hierarchy-aware segmentation
models [13, 138, 141], and view Hssn [13] as our major rival as it is a
general framework that reports strong results over several datasets, instead
of the others that are dedicated to specific dataset(s) or task setup(s). For
comprehensive evaluations, we include a group of previous hierarchy-agnostic
segmentation algorithms [44, 38, 10, 82, 81, 80], whose segmentation results
on coarse-grained semantics are obtained by merging the predictions of the
corresponding subclasses.

Training. For the sake of fairness, we follow the standard training setup in
[142, 44, 83, 143, 73]. In particular, we train $240$K/$80$K iterations for
Mapillary Vistas 2.0/Cityscapes, with batch size $8$ and crop size
$512$$\times$$1024$; $60$K/$160$K iterations for Pascal-Part-108/ADE20K, with
batch size $16$ and crop size $512$$\times$$512$. For data augmentation, the
images are horizontally flipped and scaled with a ratio between 0.5${}_{\\!}$
and${}_{\\!}$ 2.0${}_{\\!}$ at${}_{\\!}$ random.${}_{\\!}$ For${}_{\\!}$
network${}_{\\!}$ optimization,${}_{\\!}$ SGD (with initial learning rate
1e-2, momentum 0.9, and weight decay 1e-4) and Adam (with initial learning
rate 6e-5 and weight decay 0.01) are respectively used for CNN-based and
neural attention-based models, where the learning rate is scheduled by the
polynomial annealing rule. For network initialization, ImageNet [144] pre-
trained weights are pre-loaded.

Testing.${}_{\\!}$ For${}_{\\!}$ Mapillary${}_{\\!}$ Vistas${}_{\\!}$
2.0${}_{\\!}$ and${}_{\\!}$ Cityscapes,${}_{\\!}$ we${}_{\\!}$ keep${}_{\\!}$
the original${}_{\\!}$ image${}_{\\!}$ aspect${}_{\\!}$ ratio${}_{\\!}$
but${}_{\\!}$ resize${}_{\\!}$ the${}_{\\!}$ short${}_{\\!}$ edge${}_{\\!}$
to${}_{\\!}$ 1024\. Sliding window inference with the identical
window${}_{\\!}$ shape${}_{\\!}$ as${}_{\\!}$ the${}_{\\!}$ training${}_{\\!}$
size${}_{\\!}$ is${}_{\\!}$ adopted${}_{\\!}$ to${}_{\\!}$ save${}_{\\!}$
memory.${}_{\\!}$ For${}_{\\!}$ ADE20K${}_{\\!}$ and

Pascal-Part-108,${}_{\\!}$ the${}_{\\!}$ short${}_{\\!}$ edge${}_{\\!}$
is${}_{\\!}$ resized${}_{\\!}$ to${}_{\\!}$ 512${}_{\\!}$ so${}_{\\!}$
as${}_{\\!}$ to${}_{\\!}$ enable one-time${}_{\\!}$ inference${}_{\\!}$
for${}_{\\!}$ the${}_{\\!}$ whole${}_{\\!}$ image.${}_{\\!}$ As${}_{\\!}$
in${}_{\\!}$ [66, 83, 44, 98], performance of all the models is reported at
multiple scales ($\\{0.5,0.75,1.0,1.25,$ $1.5,1.75\\}_{\\!}$) with horizontal
flipping.

Hyperparameters. We set $\alpha\\!=\\!0.2$ for the loss coefficient (cf. Eq.
15), and $q\\!=\\!5$ for logic quantifier approximation (cf. Eq. 8), as
suggested by [128]. For network inference, we find 2 iterations of message
passing are enough.

Method | Backbone |  $\text{mIoU}^{3}$$\uparrow$ |  $\text{mIoU}^{2}$$\uparrow$ |  $\text{mIoU}^{1}$$\uparrow$
---|---|---|---|---
Seamless [145] | ResNet-101 | 84.23 | 70.24 | 38.82
OCRNet [44] | HRNet-W48 | 84.19 | 69.82 | 38.26
HMSANet [90] | HRNet-W48 | 84.63 | 70.71 | 39.53
Mask2Former [33] | Swin-S | 88.81 | 74.98 | 43.49
Hssn [13] | ResNet-101 | 85.27 | 71.40 | 40.16
Hssn [13] | Swin-S | 90.02 | 75.81 | 43.97
DeepLabV3+ [32] |  | 81.86 | 68.17 | 37.43
\+ LogicSeg | ResNet-101 |  85.51 $\uparrow$3.65 |  71.69 $\uparrow$3.42 |  40.72 $\uparrow$3.29
MaskFormer [83] |  | 87.93 | 73.88 | 42.16
\+ LogicSeg | Swin-S |  90.35 $\uparrow$2.42 |  76.61 $\uparrow$2.73 |  45.12 $\uparrow$2.96

Table 1: ${}_{\\!}$Urban${}_{\\!}$ scene${}_{\\!}$ parsing${}_{\\!}$
results${}_{\\!}$ (§4.2)${}_{\\!}$ on${}_{\\!}$ Mapillary${}_{\\!\\!}$
Vistas${}_{\\!}$ $2.0_{\\!}$ [28] val with a three-level label hierarchy of
$4$/$16$/$124$ concepts.

Method | Backbone |  $\text{mIoU}^{2}$$\uparrow$ |  $\text{mIoU}^{1}$$\uparrow$
---|---|---|---
PSPNet [146] | ResNet-101 | 91.67 | 80.91
DANet [65] | ResNet-101 | 91.83 | 81.52
CCNet [66] | ResNet-101 | 91.70 | 81.08
OCRNet [44] | HRNet-W48 | 92.57 | 82.33
SETR [82] | ViT-L | 92.86 | 82.75
SegMentor [81] | ViT-L | 91.79 | 81.30
UperNet [10] | Swin-S | 91.92 | 81.79
Mask2Former [33] | Swin-S | 93.68 | 83.62
SegFormer [80] | MiT-B4 | 93.81 | 83.90
Hssn [13] | ResNet-101 | 93.31 | 83.02
Hssn [13] | Swin-S | 94.39 | 83.74
DeepLabV3+ [32] |  | 92.16 | 82.08
\+ LogicSeg | ResNet-101 |  93.37 $\uparrow$1.21 |  83.20 $\uparrow$1.12
MaskFormer [83] |  | 92.96 | 82.57
\+ LogicSeg | Swin-S |  94.31 $\uparrow$1.35 |  83.85 $\uparrow$1.28

Table 2: ${}_{\\!}$Urban${}_{\\!}$ scene${}_{\\!}$ parsing${}_{\\!}$
results${}_{\\!}$ (§4.2)${}_{\\!}$ on${}_{\\!}$ Cityscapes${}_{\\!}$ [29] val
with a two-level label hierarchy of $6$/$19$ concepts.

###  4.2 Quantitative Comparison Result

Mapillary${}_{\\!\\!}$ Vistas${}_{\\!}$ 2.0${}_{\\!}$ [28]${}_{\\!}$
val.${}_{\\!}$ From${}_{\\!}$ Table${}_{\\!}$ 1${}_{\\!}$ we${}_{\\!}$
can${}_{\\!}$ observe that our approach provides notable performance gains
over the baselines. For example, our algorithm promotes classic
DeepLabV3+${}_{\\!}$ [32] by 3.65%/3.42%/3.29% over the three semantic levels.
On top of MaskFormer${}_{\\!}$ [83], our algorithm further lifts the scores by
2.42%/2.73%/2.96%, suppressing previous hierarchy-agnostic models, as well as
Hssn [13] – a newly proposed hierarchy-aware segmentation model.

Cityscapes${}_{\\!}$ [29] val. Table 2 confirms again our compelling
performance in challenging urban street scenes and wide benefits for different
segmentation models, _i.e_., 1.21%/1.12% over DeepLabV3+, and 1.35%/1.28% over
MaskFormer. Though both encoding concept structures into segmentation, our
algorithm greatly outperforms Hssn, suggesting the superiority of our logic
reasoning framework.

Pascal-Part-108${}_{\\!}$ [30] test. As illustrated by Table 3, our algorithms
yields remarkable performance on explaining the compositionality of object-
centric semantic structures. Specifically, our algorithm not only consistently
boosts the performance of base segmentation models${}_{\\!}$ [32, 33], but
also defeats two outstanding hierarchy-agnostic competitors [38, 141] as well
as three structured alternatives [138, 141, 13].

Method | Backbone |  $\text{mIoU}^{2}$$\uparrow$ |  $\text{mIoU}^{1}$$\uparrow$
---|---|---|---
SegNet [38] | ResNet-101 | 59.81 | 36.42
FCN-8s [1] | ResNet-101 | 62.26 | 38.62
BSANet [140] | ResNet-101 | 69.37 | 47.36
GMNet [138] | ResNet-101 | 69.28 | 47.21
FLOAT [141] | ResNet-101 | 70.03 | 48.08
Hssn [13] | ResNet-101 | 72.91 | 48.32
Hssn [13] | Swin-S | 77.01 | 54.79
DeepLabV3+ [32] |  | 70.86 | 46.54
\+ LogicSeg | ResNet-101 |  73.68 $\uparrow$2.82 |  49.13 $\uparrow$2.69
MaskFormer [83] |  | 75.78 | 53.07
\+ LogicSeg | Swin-S |  77.92 $\uparrow$2.14 |  55.53 $\uparrow$2.46

Table 3: Object part parsing results (§4.2) on PASCAL-Part-108${}_{\\!}$ [30]
test with a two-level label hierarchy of $20$/$108$ concepts.

Method | Backbone |  $\text{mIoU}^{3}$$\uparrow$ |  $\text{mIoU}^{2}$$\uparrow$ |  $\text{mIoU}^{1}$$\uparrow$
---|---|---|---|---
OCRNet [44] | HRNet-W48 | 76.33 | 55.76 | 44.92
SETR [82] | ViT-L | 78.92 | 59.03 | 49.41
UperNet [10] | Swin-S | 78.90 | 59.17 | 49.47
SegMentor [81] | ViT-S | 77.32 | 57.18 | 46.82
K-Net [147] | Swin-S | 79.11 | 59.38 | 49.95
SegFormer [80] | MiT-B4 | 79.85 | 60.24 | 51.08
GMMSeg [73] | MiT-B5 | 80.13 | 60.91 | 52.12
Mask2Former [33] | Swin-S | 80.46 | 61.15 | 52.43
Hssn [13] | ResNet-101 | 79.23 | 58.52 | 47.69
Hssn [13] | Swin-S | 82.59 | 62.56 | 52.37
DeepLabV3+ [32] |  | 77.24 | 56.87 | 46.43
\+ LogicSeg | ResNet-101 |  79.60 $\uparrow$2.36 |  59.04 $\uparrow$2.17 |  48.46 $\uparrow$2.03
MaskFormer [83] |  | 79.89 | 60.32 | 51.04
\+ LogicSeg | Swin-S |  82.45 $\uparrow$2.56 |  62.44 $\uparrow$2.12 |  52.82 $\uparrow$1.78

Table 4: Generic scene parsing results (§4.2) on ADE20K${}_{\\!}$ [31] val
with a three-level label hierarchy of $3$/$14$/$150$ concepts.

ADE20K [31] val. Table${}_{\\!}$ 4 presents our parsing results in general
scenes. With a relatively conservative baseline, _i.e_., DeepLabV3+${}_{\\!}$
[32], our algorithm earn 79.60%, 59.04%, and 48.46%, in terms of mIoU1, mIoU2,
and mIoU3 respectively. It delivers a solid overtaking against
Mask2Former${}_{\\!}$ [33], which is${}_{\\!}$ built${}_{\\!}$ upon${}_{\\!}$
a${}_{\\!}$ more${}_{\\!}$ advanced${}_{\\!}$ architecture.${}_{\\!}$
When${}_{\\!}$ applied to MaskFormer${}_{\\!}$ [83], our algorithm achieves
82.45%/ 62.44%/52.82%, pushing forward the state-of-the-art.

DeepLabV3+

Mask2Former

LogicSeg

LogicSeg

Figure 5: Visual results (§4.3) on${}_{\\!}$ Mapillary${}_{\\!}$
Vistas${}_{\\!}$ 2.0${}_{\\!}$ [28]. Left: DeepLabV3+${}_{\\!}$ [32] vs
LogicSeg; Right: Mask2Former ${}_{\\!}$[33] vs LogicSeg.

$\mathcal{L}_{C}$ | $\mathcal{L}_{D}$ | $\mathcal{L}_{E}$ | $\text{mIoU}^{3}$$\uparrow$ | $\text{mIoU}^{2}$$\uparrow$ | $\text{mIoU}^{1}$$\uparrow$ | Training Speed
---|---|---|---|---|---|---
Eq. 9 | Eq. 11 | Eq. 13 | (multi scale) | (min/epoch)
|  |  | 81.86 | 68.17 | 37.43 | 45.62
✓ |  |  | 83.56 | 69.74 | 38.71 | 46.35 +1.60%
| ✓ |  | 84.08 | 69.97 | 38.98 | 46.13 +1.12%
|  | ✓ | 83.42 | 69.60 | 38.43 | 46.72 +2.41%
✓ | ✓ | ✓ | 85.51 | 71.69 | 40.72 | 47.67 +4.51%

(a) logic loss (§3.2)

$\\#$ |  $\text{mIoU}^{3}$$\uparrow$ |  $\text{mIoU}^{2}$$\uparrow$ |  $\text{mIoU}^{1}$$\uparrow$ | Inference Speed
---|---|---|---|---
Iter. | (multi scale) | (fps)
0 | 84.62 | 70.95 | 40.18 | 3.44
1 | 85.23 | 71.46 | 40.56 | 3.37 -2.03%
2 | 85.51 | 71.69 | 40.72 | 3.31 -3.78%
3 | 84.84 | 71.12 | 40.29 | 3.25 -5.52%
4 | 84.49 | 70.84 | 40.03 | 3.20 -6.98%

(b) iteration of message passing (§3.3)

$q$ |  $\text{mIoU}^{3}$$\uparrow$ |  $\text{mIoU}^{2}$$\uparrow$ |  $\text{mIoU}^{1}$$\uparrow$
---|---|---|---
(multi scale)
1 | 83.83 | 70.22 | 38.77
3 | 84.65 | 71.15 | 40.09
5 | 85.51 | 71.69 | 40.72
8 | 84.47 | 71.03 | 39.74
10 | 83.52 | 69.88 | 38.25

(c) aggregation coefficient for $\forall$ (Eq.${}_{\\!\\!}$ 8)

Table 5: Ablative${}_{\\!}$ studies${}_{\\!}$ on${}_{\\!}$ Mapillary${}_{\\!}$
Vistas${}_{\\!}$ 2.0${}_{\\!}$ [28]${}_{\\!}$ val${}_{\\!}$ (§4.4).${}_{\\!}$
All${}_{\\!}$ variants${}_{\\!}$ are${}_{\\!}$ based${}_{\\!}$ on${}_{\\!}$
DeepLabV3+${}_{\\!}$ [32]${}_{\\!}$ with${}_{\\!}$ ResNet-101${}_{\\!}$
[34]${}_{\\!}$ backbone.

Taking together, our extensive benchmarking results provide solid evidence
that our algorithm successfully unlocks the power of logic reasoning in large-
scale visual parsing, and owns broad applicability across various task
scenarios, segmentation architectures, and backbone networks.

###  4.3 Qualitative Comparison Result

Fig. 5 visualizes qualitative comparisons of LogicSeg against DeepLabV3+
[32] (left) and Mask2Former [33] (right) on Mapillary Vistas 2.0 dataset
[28]. As seen, with the help of symbolic reasoning, LogicSeg can generate
higher-quality predictions even in challenging scenarios.

###  4.4 Diagnostic Experiment

For thorough evaluation, we perform a series of ablative studies on Mapillary
Vistas 2.0${}_{\\!}$ [28] val. All variants are based on DeepLabV3+${}_{\\!}$
[32] with ResNet-101 [34] backbone.

Logic-Induced Training. We first study the effectiveness of our logic-induced
training strategy (§3.2) in Table 5a. 1st row reports the results of our
baseline model – DeepLabV3+. 2nd, 3rd, and 4th rows respectively list the
scores obtained by individually adding our C-rule${}_{\\!}$ loss
$\mathcal{L}_{C}$ (cf.${}_{\\!}$ Eq.${}_{\\!\\!}$ 10), D-rule${}_{\\!}$ loss
$\mathcal{L}_{D}$ (cf.${}_{\\!}$ Eq.${}_{\\!\\!}$ 12), and E-rule${}_{\\!}$
loss $\mathcal{L}_{E}$ (cf.${}_{\\!}$ Eq.${}_{\\!\\!}$ 14). The last row gives
the performance of our full loss $\mathcal{L}$ (cf.${}_{\\!}$ Eq.${}_{\\!\\!}$
15). We can find that: i) Taking each of our logic losses into consideration
can provide consistent performance gains. This demonstrates that different
logic rules can describe different properties of semantic structure and verify
that the segmentation model can indeed benefit from our proposed logic losses.
ii) Combing all three logic losses together results in the best performance.
This suggests that our logic rules provide a comprehensive description of the
relational knowledge in the semantic hierarchy $\mathcal{T}$, and supports our
core idea that exploiting symbolic knowledge is crucial for visual semantic
interpretation and can boost sub-symbolic learning.

Training${}_{\\!}$ Speed.${}_{\\!}$ As${}_{\\!}$ shown${}_{\\!}$ in${}_{\\!}$
the${}_{\\!}$ last${}_{\\!}$ column${}_{\\!}$ of${}_{\\!}$ Table${}_{\\!}$ 5a,
our logic-induced${}_{\\!}$ training${}_{\\!}$ regime${}_{\\!}$
causes${}_{\\!}$ a trivial${}_{\\!}$ delay${}_{\\!}$ ($\sim$5.0%).

Logic-Induced Inference. We next investigate the impact of our logic-induced
inference strategy (§3.3) in Table 5b. 1${}^{\text{st}}$ row reports the
results of network feed-forward output. The rest rows give the scores obtained
with different iterations of message passing (cf.${}_{\\!}$ Eq.${}_{\\!}$ 17).
These results demonstrate the efficacy of our strategy and the necessity of
incorporating logic reasoning into network inference. We accordingly set
2-iteration as the default to pursue the best performance.

Inference${}_{\\!}$ Speed.${}_{\\!}$ We also report inference speed (fps) in
Table 5b. As seen, our logic-induced inference strategy only slows the speed
slightly during model deployment ($\sim$3.8%).

Aggregation Coefficient. For the approximation of $\forall$ quantifier
(cf.${}_{\\!}$ Eq.${}_{\\!\\!}$ 8), we adopt the generalized mean for stable
training,${}_{\\!}$ as${}_{\\!}$ suggested${}_{\\!}$ by${}_{\\!}$
[128].${}_{\\!}$ Basically,${}_{\\!}$ a${}_{\\!}$ higher${}_{\\!}$
coefficient${}_{\\!}$ $q$ renders $\forall$ a stronger focus on outliers. For
completeness, the results with different values of $q$ are reported in Table
5c.

##  5 Conclusion and Discussion

The creation of intelligent systems that integrate the fundamental cognitive
abilities of reasoning and learning has long been viewed as a core challenge
for AI [22]. While the community recently witnessed great advances in high-
level perception tasks such as visual semantic interpretation, top-leading
solutions are purely driven by sub-symbolic learning, far from such effective
integration. The present study repre- sents${}_{\\!}$ an${}_{\\!}$
innovative${}_{\\!}$ and${}_{\\!}$ solid${}_{\\!}$ attempt${}_{\\!}$
towards${}_{\\!}$ closing${}_{\\!}$ this${}_{\\!}$ gap. By embedding symbolic
logic into both network training and inference, a structured and powerful
visual semantic parser is delivered. We hope this work can stimulate our
community to rethink current de facto, sub-symbolic paradigm and inves- tigate
new methodologies,${}_{\\!}$ from the perspective of achieving a better
understanding of human and machine intelligence.

Acknowledgements This work was supported in part by the Australian Research
Council (ARC) under Grant DP200100938.

## References

  * [1] Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In CVPR, 2015.
  * [2] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In NeurIPS, 2017.
  * [3] Johannes Bill, Hrag Pailian, Samuel J Gershman, and Jan Drugowitsch.  Hierarchical structure is employed by humans during visual motion perception.  Proceedings of the National Academy of Sciences, 117(39):24581–24589, 2020.
  * [4] Steven M Frankland and Joshua D Greene.  Concepts and compositionality: in search of the brain’s language of thought.  Annual Review of Psychology, 71:273–303, 2020.
  * [5] Yi Yang, Yueting Zhuang, and Yunhe Pan.  Multiple knowledge representation for big data artificial intelligence: framework, applications, and case studies.  Frontiers of Information Technology & Electronic Engineering, pages 1551–1558, 2021.
  * [6] Theo MV Janssen et al.  Compositionality: Its historic context.  The Oxford handbook of compositionality, pages 19–46, 2012.
  * [7] Jerry A Fodor and Zenon W Pylyshyn.  Connectionism and cognitive architecture: A critical analysis.  Cognition, 28(1-2):3–71, 1988.
  * [8] Peter Pagin and Dag Westerståhl.  Compositionality i: Definitions and variants.  Philosophy Compass, 5(3):250–264, 2010.
  * [9] Paul Smolensky, R Thomas McCoy, Roland Fernandez, Matthew Goldrick, and Jianfeng Gao.  Neurocompositional computing in human and machine intelligence: A tutorial.  Microsoft Technical Report MSR-TR-2022, 2022.
  * [10] Tete Xiao, Yingcheng Liu, Bolei Zhou, Yuning Jiang, and Jian Sun.  Unified perceptual parsing for scene understanding.  In ECCV, 2018.
  * [11] Xiaodan Liang, Hongfei Zhou, and Eric Xing.  Dynamic-structured semantic propagation network.  In CVPR, 2018.
  * [12] Zhiheng Li, Wenxuan Bao, Jiayang Zheng, and Chenliang Xu.  Deep grouping model for unified perceptual parsing.  In CVPR, 2020.
  * [13] Liulei Li, Tianfei Zhou, Wenguan Wang, Jianwu Li, and Yi Yang.  Deep hierarchical semantic segmentation.  In CVPR, 2022.
  * [14] Wenguan Wang, Tianfei Zhou, Siyuan Qi, Jianbing Shen, and Song-Chun Zhu.  Hierarchical human semantic parsing with comprehensive part-relation modeling.  IEEE TPAMI, 44(7):3508–3522, 2021.
  * [15] Jing Zhang, Bo Chen, Lingxi Zhang, Xirui Ke, and Haipeng Ding.  Neural, symbolic and neural-symbolic reasoning on knowledge graphs.  AI Open, 2:14–35, 2021.
  * [16] Stephen K Reed.  A taxonomic analysis of abstraction.  Perspectives on Psychological Science, 11(6):817–837, 2016.
  * [17] Daniel Kahneman.  Thinking, fast and slow.  Macmillan, 2011.
  * [18] Fumi Katsuki and Christos Constantinidis.  Bottom-up and top-down attention: different processes and overlapping neural systems.  The Neuroscientist, 20(5):509–521, 2014.
  * [19] A Garcez, M Gori, LC Lamb, L Serafini, M Spranger, and SN Tran.  Neural-symbolic computing: An effective methodology for principled integration of machine learning and reasoning.  Journal of Applied Logics, 6(4):611–632, 2019.
  * [20] Henry Kautz.  The third AI summer: AAAI robert s. engelmore memorial lecture.  AI Magazine, 43(1):93–104, 2022.
  * [21] Wenguan Wang and Yi Yang.  Towards data-and knowledge-driven artificial intelligence: A survey on neuro-symbolic computing.  arXiv preprint arXiv:2210.15889, 2022.
  * [22] Leslie G Valiant.  Three problems in computer science.  Journal of the ACM, 50(1):96–99, 2003.
  * [23] Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri.  Houdini: Lifelong learning as program synthesis.  In NeurIPS, 2018.
  * [24] Maxwell Nye, Armando Solar-Lezama, Josh Tenenbaum, and Brenden M Lake.  Learning compositional rules via neural program synthesis.  In NeurIPS, 2020.
  * [25] Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli.  Neuro-symbolic program synthesis.  In ICLR, 2017.
  * [26] Ramakrishna Vedantam, Karan Desai, Stefan Lee, Marcus Rohrbach, Dhruv Batra, and Devi Parikh.  Probabilistic neural symbolic models for interpretable visual question answering.  In ICLR, 2019.
  * [27] Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum.  Neural-symbolic vqa: Disentangling reasoning from vision and language understanding.  In NeurIPS, 2018.
  * [28] Gerhard Neuhold, Tobias Ollmann, Samuel Rota Bulo, and Peter Kontschieder.  The mapillary vistas dataset for semantic understanding of street scenes.  In ICCV, 2017.
  * [29] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In CVPR, 2016.
  * [30] Xianjie Chen, Roozbeh Mottaghi, Xiaobai Liu, Sanja Fidler, Raquel Urtasun, and Alan Yuille.  Detect what you can: Detecting and representing objects using holistic models and body parts.  In CVPR, 2014.
  * [31] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba.  Scene parsing through ade20k dataset.  In CVPR, 2017.
  * [32] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In ECCV, 2018.
  * [33] Bowen Cheng, Ishan Misra, Alexander G Schwing, Alexander Kirillov, and Rohit Girdhar.  Masked-attention mask transformer for universal image segmentation.  In CVPR, 2022.
  * [34] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [35] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In ICCV, 2021.
  * [36] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In MICCAI, 2015.
  * [37] Fisher Yu and Vladlen Koltun.  Multi-scale context aggregation by dilated convolutions.  In ICLR, 2016.
  * [38] Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla.  Segnet: A deep convolutional encoder-decoder architecture for image segmentation.  IEEE TPAMI, 39(12):2481–2495, 2017.
  * [39] Ziwei Liu, Xiaoxiao Li, Ping Luo, Chen Change Loy, and Xiaoou Tang.  Deep learning markov random field for semantic segmentation.  IEEE TPAMI, 40(8):1814–1828, 2017.
  * [40] Guosheng Lin, Anton Milan, Chunhua Shen, and Ian Reid.  Refinenet: Multi-path refinement networks for high-resolution semantic segmentation.  In CVPR, 2017.
  * [41] Hang Zhang, Kristin Dana, Jianping Shi, Zhongyue Zhang, Xiaogang Wang, Ambrish Tyagi, and Amit Agrawal.  Context encoding for semantic segmentation.  In CVPR, 2018.
  * [42] Junjun He, Zhongying Deng, Lei Zhou, Yali Wang, and Yu Qiao.  Adaptive pyramid context network for semantic segmentation.  In CVPR, 2019.
  * [43] Hanzhe Hu, Deyi Ji, Weihao Gan, Shuai Bai, Wei Wu, and Junjie Yan.  Class-wise dynamic graph convolution for semantic segmentation.  In ECCV, 2020.
  * [44] Yuhui Yuan, Xilin Chen, and Jingdong Wang.  Object-contextual representations for semantic segmentation.  In ECCV, 2020.
  * [45] Changqian Yu, Jingbo Wang, Changxin Gao, Gang Yu, Chunhua Shen, and Nong Sang.  Context prior for scene segmentation.  In CVPR, 2020.
  * [46] Mingyuan Liu, Dan Schonfeld, and Wei Tang.  Exploit visual dependency relations for semantic segmentation.  In CVPR, 2021.
  * [47] Chi-Wei Hsiao, Cheng Sun, Hwann-Tzong Chen, and Min Sun.  Specialize and fuse: Pyramidal output representation for semantic segmentation.  In ICCV, 2021.
  * [48] Zhenchao Jin, Bin Liu, Qi Chu, and Nenghai Yu.  Isnet: Integrate image-level and semantic-level context for semantic segmentation.  In ICCV, 2021.
  * [49] Zhenchao Jin, Tao Gong, Dongdong Yu, Qi Chu, Jian Wang, Changhu Wang, and Jie Shao.  Mining contextual information beyond image for semantic segmentation.  In ICCV, 2021.
  * [50] Guangrui Li, Guoliang Kang, Wu Liu, Yunchao Wei, and Yi Yang.  Content-consistent matching for domain adaptive semantic segmentation.  In ECCV, 2020.
  * [51] Guangrui Li, Guoliang Kang, Xiaohan Wang, Yunchao Wei, and Yi Yang.  Adversarially masking synthetic to mimic real: Adaptive noise injection for point cloud segmentation adaptation.  In CVPR, 2023.
  * [52] Tianfei Zhou, Liulei Li, Xueyi Li, Chun-Mei Feng, Jianwu Li, and Ling Shao.  Group-wise learning for weakly supervised semantic segmentation.  IEEE TIP, 31:799–811, 2021.
  * [53] Liang-Chieh Chen, Jonathan T Barron, George Papandreou, Kevin Murphy, and Alan L Yuille.  Semantic image segmentation with task-specific edge detection using cnns and a discriminatively trained domain transform.  In CVPR, 2016.
  * [54] Henghui Ding, Xudong Jiang, Ai Qun Liu, Nadia Magnenat Thalmann, and Gang Wang.  Boundary-aware feature propagation for scene segmentation.  In CVPR, 2019.
  * [55] Gedas Bertasius, Jianbo Shi, and Lorenzo Torresani.  Semantic segmentation with boundary neural fields.  In CVPR, 2016.
  * [56] Xiangtai Li, Xia Li, Li Zhang, Guangliang Cheng, Jianping Shi, Zhouchen Lin, Shaohua Tan, and Yunhai Tong.  Improving semantic segmentation via decoupled body and edge supervision.  In ECCV, 2020.
  * [57] Yuhui Yuan, Jingyi Xie, Xilin Chen, and Jingdong Wang.  Segfix: Model-agnostic boundary refinement for segmentation.  In ECCV, 2020.
  * [58] Adam W Harley, Konstantinos G Derpanis, and Iasonas Kokkinos.  Segmentation-aware convolutional networks using local attention masks.  In ICCV, 2017.
  * [59] Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He.  Non-local neural networks.  In CVPR, 2018.
  * [60] Hanchao Li, Pengfei Xiong, Jie An, and Lingxue Wang.  Pyramid attention network for semantic segmentation.  arXiv preprint arXiv:1805.10180, 2018.
  * [61] Hengshuang Zhao, Yi Zhang, Shu Liu, Jianping Shi, Chen Change Loy, Dahua Lin, and Jiaya Jia.  Psanet: Point-wise spatial attention network for scene parsing.  In ECCV, 2018.
  * [62] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In CVPR, 2018.
  * [63] Junjun He, Zhongying Deng, and Yu Qiao.  Dynamic multi-scale filters for semantic segmentation.  In ICCV, 2019.
  * [64] Xia Li, Zhisheng Zhong, Jianlong Wu, Yibo Yang, Zhouchen Lin, and Hong Liu.  Expectation-maximization attention networks for semantic segmentation.  In ICCV, 2019.
  * [65] Jun Fu, Jing Liu, Haijie Tian, Yong Li, Yongjun Bao, Zhiwei Fang, and Hanqing Lu.  Dual attention network for scene segmentation.  In CVPR, 2019.
  * [66] Zilong Huang, Xinggang Wang, Lichao Huang, Chang Huang, Yunchao Wei, and Wenyu Liu.  Ccnet: Criss-cross attention for semantic segmentation.  In ICCV, 2019.
  * [67] Zongxin Yang, Yunchao Wei, and Yi Yang.  Collaborative video object segmentation by multi-scale foreground-background integration.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):4701–4712, 2021.
  * [68] Zongxin Yang, Yunchao Wei, and Yi Yang.  Associating objects with transformers for video object segmentation.  In NeurIPS, 2021.
  * [69] Zongxin Yang and Yi Yang.  Decoupling features in hierarchical propagation for video object segmentation.  In NeurIPS, 2022.
  * [70] Mingfei Han, Yali Wang, Zhihui Li, Lina Yao, Xiaojun Chang, and Yu Qiao.  Html: Hybrid temporal-scale multimodal learning framework for referring video object segmentation.  In ICCV, 2023.
  * [71] Wenguan Wang, Tianfei Zhou, Fisher Yu, Jifeng Dai, Ender Konukoglu, and Luc Van Gool.  Exploring cross-image pixel contrast for semantic segmentation.  In ICCV, 2021.
  * [72] Tianfei Zhou, Wenguan Wang, Ender Konukoglu, and Luc Van Gool.  Rethinking semantic segmentation: A prototype view.  In CVPR, 2022.
  * [73] Chen Liang, Wenguan Wang, Jiaxu Miao, and Yi Yang.  Gmmseg: Gaussian mixture based generative semantic segmentation models.  In NeurIPS, 2022.
  * [74] Yurong Zhang, Liulei Li, Wenguan Wang, Rong Xie, Li Song, and Wenjun Zhang.  Boosting video object segmentation via space-time correspondence learning.  In CVPR, 2023.
  * [75] Liulei Li, Wenguan Wang, Tianfei Zhou, Jianwu Li, and Yi Yang.  Unified mask embedding and correspondence learning for self-supervised video segmentation.  In CVPR, 2023.
  * [76] Wuyang Chen, Xinyu Gong, Xianming Liu, Qian Zhang, Yuan Li, and Zhangyang Wang.  Fasterseg: Searching for faster real-time semantic segmentation.  arXiv preprint arXiv:1912.10917, 2019.
  * [77] Chenxi Liu, Liang-Chieh Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L Yuille, and Li Fei-Fei.  Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation.  In CVPR, 2019.
  * [78] Vladimir Nekrasov, Hao Chen, Chunhua Shen, and Ian Reid.  Fast neural architecture search of compact semantic segmentation models via auxiliary cells.  In CVPR, 2019.
  * [79] Yanwei Li, Lin Song, Yukang Chen, Zeming Li, Xiangyu Zhang, Xingang Wang, and Jian Sun.  Learning dynamic routing for semantic segmentation.  In CVPR, 2020.
  * [80] Enze Xie, Wenhai Wang, Zhiding Yu, Anima Anandkumar, Jose M Alvarez, and Ping Luo.  Segformer: Simple and efficient design for semantic segmentation with transformers.  In NeurIPS, 2021.
  * [81] Robin Strudel, Ricardo Garcia, Ivan Laptev, and Cordelia Schmid.  Segmenter: Transformer for semantic segmentation.  In ICCV, 2021.
  * [82] Sixiao Zheng, Jiachen Lu, Hengshuang Zhao, Xiatian Zhu, Zekun Luo, Yabiao Wang, Yanwei Fu, Jianfeng Feng, Tao Xiang, Philip HS Torr, et al.  Rethinking semantic segmentation from a sequence-to-sequence perspective with transformers.  In CVPR, 2021.
  * [83] Bowen Cheng, Alexander G. Schwing, and Alexander Kirillov.  Per-pixel classification is not all you need for semantic segmentation.  In NeurIPS, 2021.
  * [84] James Liang, Tianfei Zhou, Dongfang Liu, and Wenguan Wang.  Clustseg: Clustering for universal segmentation.  In ICML, 2023.
  * [85] Tuo Feng, Wenguan Wang, Xiaohan Wang, Yi Yang, and Qinghua Zheng.  Clustering based point cloud representation learning for 3d analysis.  In ICCV, 2023.
  * [86] Terrence W Deacon.  The co-evolution of language and the brain.  WW Norlon, Nueva Ymk, 1997.
  * [87] Stuart J. Russell and Peter Norvig.  Artificial Intelligence: A modern approach.  Pearson, 3 edition, 2009.
  * [88] Steven Horst.  The computational theory of mind.  Stanford Encyclopedia of Philosophy, 2005.
  * [89] Wenguan Wang, Zhijie Zhang, Siyuan Qi, Jianbing Shen, Yanwei Pang, and Ling Shao.  Learning compositional neural information fusion for human parsing.  In ICCV, 2019.
  * [90] Wenguan Wang, Hailong Zhu, Jifeng Dai, Yanwei Pang, Jianbing Shen, and Ling Shao.  Hierarchical human parsing with typed part-relation reasoning.  In CVPR, 2020.
  * [91] Tsung-Wei Ke, Jyh-Jing Hwang, Yunhui Guo, Xudong Wang, and Stella X Yu.  Unsupervised hierarchical semantic segmentation with multiview cosegmentation and clustering transformers.  In CVPR, 2022.
  * [92] Zhuowen Tu, Xiangrong Chen, Alan L Yuille, and Song-Chun Zhu.  Image parsing: Unifying segmentation, detection, and recognition.  IJCV, 63(2):113–140, 2005.
  * [93] Erik B Sudderth, Antonio Torralba, William T Freeman, and Alan S Willsky.  Learning hierarchical models of scenes, objects, and parts.  In ICCV, 2005.
  * [94] Erik B Sudderth, Antonio Torralba, William T Freeman, and Alan S Willsky.  Describing visual scenes using transformed objects and parts.  IJCV, 77(1-3):291–330, 2008.
  * [95] Feng Han and Song-Chun Zhu.  Bottom-up/top-down image parsing with attribute grammar.  IEEE TPAMI, 31(1):59–73, 2008.
  * [96] Jian Yao, Sanja Fidler, and Raquel Urtasun.  Describing the scene as a whole: Joint object detection, scene classification and semantic segmentation.  In CVPR, 2012.
  * [97] Bingke Zhu, Yingying Chen, Ming Tang, and Jinqiao Wang.  Progressive cognitive human parsing.  In AAAI, 2018.
  * [98] Ruyi Ji, Dawei Du, Libo Zhang, Longyin Wen, Yanjun Wu, Chen Zhao, Feiyue Huang, and Siwei Lyu.  Learning semantic neural tree for human parsing.  In ECCV, 2020.
  * [99] Warren S McCulloch and Walter Pitts.  A logical calculus of the ideas immanent in nervous activity.  The bulletin of mathematical biophysics, 5(4):115–133, 1943.
  * [100] Jordan B Pollack.  Recursive distributed representations.  Artificial Intelligence, 46(1-2):77–105, 1990.
  * [101] Lokendra Shastri and Venkat Ajjanagadde.  From simple associations to systematic reasoning: A connectionist representation of rules, variables and dynamic bindings using temporal synchrony.  Behavioral and Brain Sciences, 16(3):417–451, 1993.
  * [102] Geoffrey G Towell and Jude W Shavlik.  Knowledge-based artificial neural networks.  Artificial intelligence, 70(1-2):119–165, 1994.
  * [103] Tony A Plate.  Holographic reduced representations.  IEEE TNN, 6(3):623–641, 1995.
  * [104] Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel J Gershman.  Building machines that learn and think like people.  Behavioral and brain sciences, 40, 2017.
  * [105] Gary Marcus.  Deep learning: A critical appraisal.  arXiv preprint arXiv:1801.00631, 2018.
  * [106] Eleonora Giunchiglia and Thomas Lukasiewicz.  Multi-label classification neural networks with hard logical constraints.  Journal of Artificial Intelligence Research, 72:759–818, 2021.
  * [107] Eleonora Giunchiglia, Mihaela Catalina Stoian, and Thomas Lukasiewicz.  Deep learning with logical constraints.  In IJCAI, 2022.
  * [108] Miles Cranmer, Alvaro Sanchez Gonzalez, Peter Battaglia, Rui Xu, Kyle Cranmer, David Spergel, and Shirley Ho.  Discovering symbolic models from deep learning with inductive biases.  In NeurIPS, 2020.
  * [109] Komal Teru, Etienne Denis, and Will Hamilton.  Inductive relation prediction by subgraph reasoning.  In ICML, 2020.
  * [110] Bill Yuchen Lin, Xinyue Chen, Jamin Chen, and Xiang Ren.  Kagnet: Knowledge-aware graph networks for commonsense reasoning.  In EMNLP, 2019.
  * [111] Zhiting Hu, Xuezhe Ma, Zhengzhong Liu, Eduard Hovy, and Eric Xing.  Harnessing deep neural networks with logic rules.  In ACL, 2016.
  * [112] Russell Stewart and Stefano Ermon.  Label-free supervision of neural networks with physics and domain knowledge.  In AAAI, 2017.
  * [113] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck.  A semantic loss function for deep learning with symbolic knowledge.  In ICML, 2018.
  * [114] Tim Rocktäschel and Sebastian Riedel.  End-to-end differentiable proving.  In NeurIPS, 2017.
  * [115] Michelangelo Diligenti, Marco Gori, and Claudio Sacca.  Semantic-based regularization for learning and inference.  Artificial Intelligence, 244:143–165, 2017.
  * [116] Marc Fischer, Mislav Balunovic, Dana Drachsler-Cohen, Timon Gehr, Ce Zhang, and Martin Vechev.  Dl2: Training and querying neural networks with logic.  In ICML, 2019.
  * [117] Marwin HS Segler, Mike Preuss, and Mark P Waller.  Planning chemical syntheses with deep neural networks and symbolic ai.  Nature, 555(7698):604–610, 2018.
  * [118] Hanjun Dai, Chengtao Li, Connor Coley, Bo Dai, and Le Song.  Retrosynthesis prediction with conditional graph logic network.  In NeurIPS, 2019.
  * [119] Lili Mou, Zhengdong Lu, Hang Li, and Zhi Jin.  Coupling distributed and symbolic execution for natural language queries.  In ICML, 2017.
  * [120] Daoming Lyu, Fangkai Yang, Bo Liu, and Steven Gustafson.  Sdrl: interpretable and data-efficient deep reinforcement learning leveraging symbolic planning.  In AAAI, 2019.
  * [121] Fangkai Yang, Daoming Lyu, Bo Liu, and Steven Gustafson.  Peorl: Integrating symbolic planning and hierarchical reinforcement learning for robust decision-making.  In IJCAI, 2018.
  * [122] Forough Arabshahi, Sameer Singh, and Animashree Anandkumar.  Combining symbolic expressions and black-box function evaluations in neural programs.  In ICLR, 2018.
  * [123] Qing Li, Siyuan Huang, Yining Hong, Yixin Chen, Ying Nian Wu, and Song-Chun Zhu.  Closed loop neural-symbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning.  In ICML, 2020.
  * [124] Guillaume Lample and François Charton.  Deep learning for symbolic mathematics.  In ICLR, 2019.
  * [125] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt.  Deepproblog: neural probabilistic logic programming.  In NeurIPS, 2018.
  * [126] Wang-Zhou Dai, Qiuling Xu, Yang Yu, and Zhi-Hua Zhou.  Bridging machine learning and logical reasoning by abductive learning.  In NeurIPS, 2019.
  * [127] Yaqi Xie, Ziwei Xu, Mohan S Kankanhalli, Kuldeep S Meel, and Harold Soh.  Embedding symbolic knowledge into deep networks.  In NeurIPS, 2019.
  * [128] Samy Badreddine, Artur d’Avila Garcez, Luciano Serafini, and Michael Spranger.  Logic tensor networks.  Artificial Intelligence, 303:103649, 2022.
  * [129] Wei Bi and James T Kwok.  Multilabel classification on tree-and dag-structured hierarchies.  In ICML, 2011.
  * [130] Eleonora Giunchiglia and Thomas Lukasiewicz.  Coherent hierarchical multi-label classification networks.  In NeurIPS, 2020.
  * [131] Luca Bertinetto, Romain Mueller, Konstantinos Tertikas, Sina Samangooei, and Nicholas A Lord.  Making better mistakes: Leveraging class hierarchies with deep networks.  In CVPR, 2020.
  * [132] Jonatas Wehrmann, Ricardo Cerri, and Rodrigo Barros.  Hierarchical multi-label classification networks.  In ICML, 2018.
  * [133] Emile van Krieken, Erman Acar, and Frank van Harmelen.  Analyzing differentiable fuzzy logic operators.  Artificial Intelligence, 302:103602, 2022.
  * [134] Vilém Novák, Irina Perfilieva, and Jiri Mockor.  Mathematical principles of fuzzy logic, volume 517.  Springer Science & Business Media, 2012.
  * [135] Petr Hájek.  Metamathematics of fuzzy logic, volume 4.  Springer Science & Business Media, 2013.
  * [136] Solomon Feferman, John W Dawson Jr, Stephen C Kleene, Gregory H Moore, Robert M Solovay, and Jean Van Heijenoort.  Kurt Godel: collected works. Vol. 1: Publications 1929-1936.  Oxford University Press, Inc., 1986.
  * [137] Joseph A Goguen.  The logic of inexact concepts.  Synthese, pages 325–373, 1969.
  * [138] Umberto Michieli, Edoardo Borsato, Luca Rossi, and Pietro Zanuttigh.  Gmnet: Graph matching network for large scale part semantic segmentation in the wild.  In ECCV, 2020.
  * [139] Abel Gonzalez-Garcia, Davide Modolo, and Vittorio Ferrari.  Do semantic parts emerge in convolutional neural networks?  IJCV, 126(5):476–494, 2018.
  * [140] Yifan Zhao, Jia Li, Yu Zhang, and Yonghong Tian.  Multi-class part parsing with joint boundary-semantic awareness.  In ICCV, 2019.
  * [141] Rishubh Singh, Pranav Gupta, Pradeep Shenoy, and Ravikiran Sarvadevabhatla.  Float: Factorized learning of object attributes for improved multi-object multi-part scene parsing.  In CVPR, 2022.
  * [142] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L Yuille.  Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs.  IEEE TPAMI, 2017.
  * [143] Meng-Hao Guo, Cheng-Ze Lu, Qibin Hou, Zhengning Liu, Ming-Ming Cheng, and Shi-Min Hu.  Segnext: Rethinking convolutional attention design for semantic segmentation.  In NeurIPS, 2022.
  * [144] Jia Deng, Nan Ding, Yangqing Jia, Andrea Frome, Kevin Murphy, Samy Bengio, Yuan Li, Hartmut Neven, and Hartwig Adam.  Large-scale object classification using label relation graphs.  In ECCV, 2014.
  * [145] Lorenzo Porzi, Samuel Rota Bulo, Aleksander Colovic, and Peter Kontschieder.  Seamless scene segmentation.  In CVPR, 2019.
  * [146] Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia.  Pyramid scene parsing network.  In CVPR, 2017.
  * [147] Wenwei Zhang, Jiangmiao Pang, Kai Chen, and Chen Change Loy.  K-net: Towards unified image segmentation.  In NeurIPS, 2021.
  * [148] George A Miller.  Wordnet: a lexical database for english.  Communications of the ACM, 38(11):39–41, 1995.

In this document, we first provide the pseudo code of LogicSeg in §A. We next
show the detailed label hierarchy for each dataset in §B. In addition, we
offer more qualitative results in §C. Finally, we discuss the limitations and
border impact of our algorithm in §D and §E, respectively. To ensure
reproducibility and foster future research, our full implementation will be
released after acceptance.

##  Appendix A Pseudo Code

To facilitate a comprehensive understanding of LogicSeg, we provide pseudo
code for the logic-induced inference (§3) of LogicSeg in Algorithm S1 and
Algorithm S2, respectively. It can be seen that all the message creation
processes are implemented in matrix operation which can enjoy the acceleration
of the parallel architecture of GPUs. The for-loop is merely adopted in
Algorithm S1 when normalizing or summarizing the prediction in a level-wise
manner, with $O(n)$ time complexity.

##  Appendix B Label Hierarchy

For Mapillary Vistas 2.0 [28] and Cityscapes [29] datasets, we adopt the
officially provided label hierarchies following [13]. For Pascal-Part-108
[30], we use the hierarchy defined in [138, 141]. For ADE20K [31], we
organize a three-level label hierarchy by considering the semantic relations
between labels according to the WordNet [148]. The detailed label hierarchies
for each datasets are provided in Fig. S1-S4.

##  Appendix C More Qualitative Comparison Result

We provide more visual results that compare LogicSeg to Mask2Former [33] and
to DeeplabV3+ [32] in Fig. S5-S6 and Fig. S7-S8, respectively. It can be
observed that LogicSeg performs robust in hard cases and can consistently
deliver more satisfying results compared with the baseline algorithms.

##  Appendix D Limitation

Currently our algorithm is specifically designed for tree-shape label
hierarchy. It is interesting to extend our algorithm to handle more
complicated and real-world semantic structures, for example, parent classes
sharing some child classes. We leave this as a part of our future work.

##  Appendix E Border Impact

This paper contributes to research on intelligent scene understanding, and
thus is expected to eventually benefit automatic driving, education, health
care, and economic development of the human society. Moreover, although our
algorithm is able to parse the hierarchical relations between semantic
concepts and yields improved performance over current top-leading competitors,
the relevant security measures still need to be erected and caution should
always be exercised.

Algorithm S1 Pseudo-code for logic-induced inference of LogicSeg in a PyTorch-
like style (Part I).

⬇

"""

T:␣index␣matrix␣indicates␣the␣hierarchy,␣for␣example:

␣␣␣␣␣␣␣␣␣␣␣␣␣␣a␣␣␣␣␣ ␣␣a␣b␣c␣d␣e␣f

␣␣␣␣␣␣␣␣␣␣␣␣␣/␣\␣␣␣␣␣␣␣␣ ␣␣␣␣a␣0␣1␣1␣0␣0␣0

␣␣␣␣␣␣␣␣␣␣␣␣b␣␣ ␣␣c␣␣ ␣␣␣\-->␣␣␣ ␣␣␣b␣0␣0␣0␣1␣1␣0

␣␣␣␣␣␣␣␣␣␣␣/\␣␣␣ ␣\␣ ␣␣␣␣c␣0␣0␣0␣0␣0␣1

␣␣␣␣␣␣␣␣␣␣d␣ e␣ ␣f

P:␣matrix␣indicates␣the␣peer␣relation,␣for␣example:

␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣a␣b␣c␣d␣e␣f

␣␣␣␣␣␣␣␣␣␣␣␣␣␣a␣␣␣␣␣ ␣␣a␣0␣0␣0␣0␣0␣0

␣␣␣␣␣␣␣␣␣␣␣␣␣/␣\␣␣␣␣␣␣␣␣ ␣␣␣␣b␣0␣0␣1␣0␣0␣0

␣␣␣␣␣␣␣␣␣␣␣␣b␣␣ ␣␣c␣␣ ␣␣␣\-->␣␣␣ ␣␣␣c␣0␣1␣0␣0␣0␣0

␣␣␣␣␣␣␣␣␣␣␣/\␣␣␣ ␣\␣ ␣␣␣␣d␣0␣0␣0␣0␣1␣1

␣␣␣␣␣␣␣␣␣␣d␣ e␣ ␣f␣ ${}_{\\!}$␣␣␣␣␣␣e␣0␣0␣0␣1␣0␣1

␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣f␣0␣0␣0␣1␣1␣0

V:␣array␣stores␣the␣class␣number␣in␣each

␣␣␣␣hierarchical␣level,␣V[l]␣=␣$|\mathcal{V}^{l+1}|$

R:␣round␣of␣message␣passing

L:␣number␣of␣hierarchical␣level

s_k:␣grounded␣predicates␣($|\mathcal{V}|$␣x␣HW)

"""

def message_passing(s_k):

s_k += c_score(s_k) + d_score(s_k) + e_score(s_k)

# hierarchical level-wise normalization

n = 0

for l in range(L, 0, -1):

s_k[n:n+V[l]] = s_k[n:n+V[l]].softmax(dim=0)

n += V[l]

return s_k

def inference(s_k):

# R times of message passing

for t in range(R):

s_k = message_passing(s_k)

# (N_p x $|\mathcal{V}|$ x 1)*(1 x $|\mathcal{V}|$ x HW)

s_f = T.unsqueeze(-1) * s_k.unsqueeze(0)

n = V[L-1]

t_s = s_f[:V[L-1]]

#---------top-scoring path (Eq. 18)----------#

for l in range(L-2, -1, -1):

t_s = t_s.unsqueeze(1)

# ($|\mathcal{V}^{l}|$ x $|\mathcal{V}|$ x HW) + ($|\mathcal{V}^{l}|$ x 1 x
HW)

t_s = (s_f[n:n+V[l]] + t_s)

# ($|\mathcal{V}^{l}|$ x $|\mathcal{V}|$ x HW) \--> ($|\mathcal{V}|$ x HW)

t_s = t_s*(T[n:n+V[l]].unsqeeze(-1)).sum(0)

n += V[l]

# ($|\mathcal{V}^{l-1}|$ x HW)

t_s = t_s[n:n+V[l-1]]

# ($|\mathcal{V}^{1}|$ x HW) \--> (HW)

pred = t_s.argmax(dim=0)

return pred

Algorithm S2 Pseudo-code for logic-induced inference of LogicSeg in a PyTorch-
like style (Part II).

⬇

"""

N_p:␣class␣number␣of␣non-leaf␣nodes

s_k:␣grounded␣predicates␣($|\mathcal{V}|$␣x␣HW)

"""

def c_score(s_k):

#-------------C-message (Eq. 16)-------------#

# (N_p x $|\mathcal{V}|$ x 1)*(1 x $|\mathcal{V}|$ x HW)

c_f = T.unsqueeze(-1) * s_k.unsqueeze(0)

# (N_p x 1 x HW)*(N_p x $|\mathcal{V}|$ x HW)

c_m = s_k[:N_p].unsqueeze(1) * c_f

# $1\\!-\\!\bm{s}_{k}[v]\\!+\\!\bm{s}_{k}[v]\\!\cdot_{\\!}\bm{s}_{k}[p_{v}]$

c_m = 1 - c_f + c_m

#-----gather received C-messages (Eq. 17)----#

# (N_p x HW)

c_s = (c_f * c_m).sum(dim=1)

c_s = c_s / T.sum(dim=1).unsqueeze(-1)

# ($|\mathcal{V}|$ x HW)

c = torch.zeros($|\mathcal{V}|$, HW)

c[:N_p, :] = c_s

return c

def d_score(s_k):

#-------------D-message (Eq. 16)-------------#

# (N_p x $|\mathcal{V}|$ x 1)*(1 x $|\mathcal{V}|$ x HW)

d_f = T.unsqueeze(-1) * s_k.unsqueeze(0)

# (N_p x HW)*(N_p x HW)

d_m = s_k[:N_p] * d_f.max(dim=1)

#
$1\\!-\\!\bm{s}_{k}[v]\\!+\\!\bm{s}_{k}[v]\\!\cdot\\!\texttt{max}(\\{\bm{s}_{k}[c^{n}_{v}]\\}_{n})$

d_m = 1-s_k[:N_p] + d_m

#-----gather received D-messages (Eq. 17)----#

# (N_p x HW)x(N_p x HW)

d_s = s_k[:N_p] * d_m

# (N_p x 1 x HW)*(N_p x $|\mathcal{V}|$ x 1)

d_s = d_s.unsqueeze(1) * T.unsqueeze(-1)

# ($|\mathcal{V}|$ x HW)

d_s = d_s.sum(dim=0)

return d_s

def e_score(s_k):

#-------------E-message (Eq. 16)-------------#

# ($|\mathcal{V}|$ x $|\mathcal{V}|$ x 1)*(1 x $|\mathcal{V}|$ x HW)

e_f = P.unsqueeze(-1) * s_k.unsqueeze(0)

# ($|\mathcal{V}|$ x 1 x HW)*($|\mathcal{V}|$ x $|\mathcal{V}|$ x HW)

e_m = s_k.unsqueeze(1) * e_f

#
$-_{\\!}~{}(1\\!-\\!\textstyle\frac{1}{M}_{\\!}\\!\sum_{m=1}^{M}\\!\bm{s}_{k}[v]_{\\!}\cdot_{\\!}\bm{s}_{k}[a_{v}^{m}])$

e_m = -1+e_m.sum(dim=1)/P.sum(dim=1).unsqueeze(-1)

#-----gather received E-messages (Eq. 17)----#

# ($|\mathcal{V}|$ x HW)

e_s = e_f.sum(dim=1) / P.sum(dim=1).unsqueeze(-1)

# E-message should be same for all nodes in the same hierarchical level

e_s = e_m * e_s

return e_s

Figure S1: Hierarchical label structure of Mapillary Vistas 2.0 [28]. Figure
S2: Hierarchical label structure of Cityscapes [29]. Figure S3: Hierarchical
label structure of Pascal-Part-108 [30]. Figure S4: Hierarchical label
structure of ADE20K [31].

Figure S5: Visual comparison results on Mapillary Vistas 2.0 [28] val. Top:
Mask2Fomer [33] _vs_. Bottom: LogicSeg Figure S6: Visual comparison results
on Cityscapes [29] val. Top: Mask2Fomer [33] _vs_. Bottom: LogicSeg Figure
S7: Visual comparison results on ADE20K [31] val. Top: DeepLabV3+ [32] _vs_.
Bottom: LogicSeg Figure S8: Visual comparison results on Pascal-Part-108 [30]
test. Top: DeepLabV3+ [32] _vs_. Bottom: LogicSeg