Relational Concept Bottleneck Models
Authors: Pietro Barbiero
Francesco Giannini
Gabriele Ciravegna
Michelangelo Diligenti
Giuseppe Marra
Venue: NeurIPS 2024 poster (2024)
Keywords: Concept Bottleneck Models
Neuro-symbolic Models
Message Passing
Logic-based explanations
Primary area: interpretability_and_explainability
TL;DR: This work presents R-CBMs, a family of concept bottleneck models designed for relational tasks, which match the generalization performance of existing relational black-boxes, while support the generation of quantified concept-based explanations.

Abstract: The design of interpretable deep learning models working in relational domains poses an open challenge: interpretable deep learning methods, such as Concept Bottleneck Models (CBMs), are not designed to solve relational problems, while relational deep learning models, such as Graph Neural Networks (GNNs), are not as interpretable as CBMs. To overcome these limitations, we propose Relational Concept Bottleneck Models (R-CBMs), a family of relational deep learning methods providing interpretable task predictions. As special cases, we show that R-CBMs are capable of both representing standard CBMs and message passing GNNs. To evaluate the effectiveness and versatility of these models, we designed a class of experimental problems, ranging from image classification to link prediction in knowledge graphs. In particular we show that R-CBMs (i) match generalization performance of existing relational black-boxes, (ii) support the generation of quantified concept-based explanations, (iii) effectively respond to test-time interventions, and (iv) withstand demanding settings including out-of-distribution scenarios, limited training data regimes, and scarce concept supervisions.

Relational Concept Bottleneck Models
Pietro Barbiero
Francesco Giannini Scuola Normale Superiore francesco, g gww.ninineeemmmmmmmmmmnm ien.ininiiiii....mmmmmmm it
Università della Svizzera Italiana University of Cambridge ba barbiero@tutanota. com
Gabriele Ciravegna
Michelangelo Diligenti University of Siena
Politecnico di Torino
gabriele, wwt.:ee.....aaaaapppooo.oooooo..
michelangelo. htt.eeaarneeoo.diiieeeeiiiiooone 1.n.
Giuseppe Marra
KU Leuven
Abstract
The design of interpretable deep learning models working in relational domains poses am open challenge: interpretable deep learning methods, such as Concept Bottleneck Models (CBMs), not designed to solve relational problems, while relational deep learning models, such as Graph Neural Networks (GNNs), are not interpretable CBMs. To overcome these limitations, tional Concept Bottleneck Models (R-CBMs), a family relational deep learning methods providing interpretable task predictions. As special cases, show that R-CBMs are capable of both representing standard CBMs and message-passingg GNNs. To evaluate the effectiveness and versatility of these models, we designed class of experimental problems, ranging from image classification to link prediction knowledge graphs. In particular show that R-CBMs (i) match generaliza- tion performance of existing relational black-boxes, (ii) support the generation of quantified concept-based explanations, (iii) effectively respond test-time in- terventions, and (iv) withstand demanding settings including cat-of-distribution scenarios, limited training data regimes, and scarce concept supervisions.
propose Rela-
Introduction
Chemistry, politics, economics, traffic jams: we con- stantly rely relations to describe, explain and rea- son on everyday life problems. For instance, we easily deduce Bart's citizenship if consider Homer's citizenship and his status as Bart's father (Figure []. While relational Deep Learning (DL) can effectively solve such problems, the design of interpretable neural mod- els capable of relational reasoning is still an open challenge. Among DL methods, Concept Bottleneck Models (CBMs) [33 are interpretable methods ex- plaining their predictions by first mapping input fea- tures to set of human-unden undarstnndtttelbbllle concepts and
male(H))
parent H, B)
task predictor
models 229 19
32 [6]
US(H)
US(B))
mate( B)
Figure 1: Relational Concept Bottleneck Models
correctly predict and explain Bart's (B) citizen- ship by considering Homer's (H) citizenship and his status as Bart's parent.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

then using such concepts to solve the given tasks. However, current CBMs are not well-suited for addressing relational problems as they can process only one imput entity at a time by construction. To solve relational problems, CBMs would need to handle concepts/tasks involving multiple entities (e.g., the concept "parent" which depends on both the entity "Homer" and "Bart"), thus foreing CBMs to process more entities at time. Moreover, the definition of a suitable relational bottleneck layer is generally not straightforward, as a task prediction may require complex connections among multiple relational concepts. On the other side, while existing relational DL methods, such Graph Neural Networks (GNN), may effectively solve such problems (e.g., correctly predicting Bart's citizenship), they are still unable to explain their predictions as CBMs would do (e.g., Bart is US citizen since Homer is a US citizen and Homer is the father of Bart). Hence, a knowledge gap persists in the existing literature: defining a DL model capable of relational reasoning (akin to a GNN), while also being interpretable (akin to a CBM).
To address this gap, we propose Relational Concept Bottleneck Models (R-CBMs, Section 3 family of concept bottleneck models where both concepts and tasks may depend on multiple entities. and that have both CBMs and GNNs special cases. The results of our experiments (Section show that R-CBMs: (i) match the generalization performance of existing relational black-boxes, (ii) support the generation of first-order logic explanations, (iii) effectively respond to test-time concept and rule interventions improving their task performance, (iv) withstand demanding test scenarios including out-of-distribution settings, limited training data regimes, and scarce concept supervisions.
2 Background
Concept bottleneck models. A Concept Bottleneck Model (CBM) a function composing: (i) concept encoder g X - C' mapping each entity e with feature representation Ze X C R (e.g., an image) to a set of concepts c é C S [0. 1 (e.g.. "red", "round"), and (ii) a task predictor C + Y mapping concepts to set of m tasks y Y C [0, 1| (e.g.. "apple","tomatt" "tommtto". Each component 9; and fy vehicle the prediction of the i-th concept and j-th task, respectively.
Relational languages. A relational setting can be outlined using a function-fre first-order logic language L (E, P),, where& E is finite set of constants for specific domain entities"] V a set of variables for anonymous entities, and P is set of n-ary predicates for relations among entities. The central objects of a relational language are its atoms, i.e. expressions P(TI, TT), where p is an n-ary predicate and Ti...., Tn are constants or variables. In case Ti..... Tn are all constants, p(TI....: .T) is called a ground atom. Examples of atoms can be male male(Bart) and parent(u, u, v), with Bart E and u, V. Given set of atoms I' defined the process of applying a substitution By = (v1/e1,.. ..., /n/ en to is called grounding, i.c. the substitution of all the variables v, with some constants I;, according to Py. For example, given r T= [pareent (11 02)), parent U22, 03]] and the substitution @ = (uz /Abe, 1/2 / Homer, /3/ (a//Bar), we can parent(Homer, obtain the ground list Ør [parenr(Aber Homer), parent (omee,, Bart)]. The set of all the ground
joint set of variables V = (2),.... Un).
atoms of a relational language is called its Herbrand base (HB). Logic rules are defined as usual by applying logic connectives {-, V, } and quantifiers (V, 3} on atoms.
Graph neural networks. The architecture of a typical GNN for node-classification tasks consists of three primary steps. For every node i, 1) an incoming message M,-s is passed from a neighbor node j E (i) to i, where (1) denotes the set of all the incoming neighbours of i, 2) the embedding representation of node i is updated by aggregating all the incoming messages from its neighbors, 3) readout function is applied to the node embeddings to predict the class label gi). Steps 1)-2) are typically repeated multiple times to allow multi-hop information propagation.
3 Relational Concept Bottleneck Models
This work addresses a key research question: how can we bridge the gap between the interpretability of concept-based models and the reasoning capabilities of relational DL? To answer this question, we extend the notion of bottleneck to a relational setting (Section 3.1 and classic message- paassaggppssinggggg to also update atom predictions during the recursive steps (Section B.2). Then we illustrate the learning problem that R-CBMs can solve (Section (.3). and finally we discuss the connections of R-CBMs with both standard CBMs and GNNs (Section 3.4
Assuming 1-to-1 mapping between constants and entities allows use these words interchangeably.

---

3.1 Relational Concept Bottlenecks
The structure of the relational concept bottleneck can be defined as a relational structure, where each atom corresponds to node. The dependencies among the atoms are represented as directed hypergraph, where each hyperedge is positional, and can have multiple nodes as head, but only a single node tail. In this regard, every hyperedge defines relational concept bottleneck from (possibly) many source ground atoms to a destination ground atom. Moreover, each hyperedge is assumed to be sufficient to carry out the prediction for the destination atom, which can however be collectively improved by merging separate predictions. Formally, an atom dependency graph for a node A, is positional, labeled hypergraph H. (HIB, R), whose nodes are the atoms in the Herbrand Base HB of a relational language, and each hyperedge R is such that = ([A,..... Amm] [A]), with , ing that in H there is a hyperedge with source [AI:...; Am] and destination A. Each hyperedge is labelled with a type identifier I(r). Given atom A, we indicate by R(A) the set of hyperedges with destination A, and by (A)(A)
Ps(a)
(a.
P: (6.a)
predictor
Pa(
P1
prodictor
guom encoder
HB, mean-
palc, bj
Palo,
Pa(c)
Figure 2:
The graph represents the de- pendencies among the atoms. Here, the atom pb(b) can be predicted either from the orange (ps(b), (ps(b))p2(a) (2 b), (b,b, a)] or violet
the source of the hyperedge r if r R(A) the emp-
tyset otherwise. Figure 2 shows an example with two hy- peredges with destination Pb(b), where N Norange (Pa (b))
[pr (b, (c b)] tuples of neighhours.
[pa(b) (b), P2 (a b), Pı (b, a)] and Neriotee (Pa(b) = [pi (b, c), b)], we used different colors to iden- tify different hyperedges.
3.2 The Model
Relational Concept Bottleneck Models (R-CBM) merge CBMs and GNNs into an interpretable relational setting. An R-CBM first processes the atoms of relational language by encoder, and then map them by a predictor (like a CBM). The final prediction is computed by aggregating all the ones from separate groups of neighbour atoms, according The pipeline of R-CBMs can be described as follows: (i) the atom encoder and predictor embeds each atom into concept embedding and prediction score, respectively (ii) message-passing is performed to refine the embeddings and scores according to the structure defined by the atom dependency graph, and (iii) the atom predictions obtained by aggregating the predictions.
given dependency graph (like GNN).
Atom encoder. An n-ary ground atom A is defined by a predicate p and tuple of entities e = (el, (e.,....,e en), such that A = p(e). Like in GNN, the entities have feature representation X.- (Ze, (Ze....... Tea. )...)ee E Rdt", being d the representation size. For each atom A p(e), the atom encoder Ip computes the atom encoding (x,) E R. being H the embedding size.
Message-passinne passing..snn.... Given the relational concept bottlenecks, the updating of the embeddings and predictions of the atoms be expressed as message-pasiin schema the dependency graph. For each A E HB, with A = p(e), the initial embedding and prediction for A are calculated by:
(A) gp (Xo).
(A) = (A))
where 9p is the atom encoder and = [0, 1] is learnable predictor function working on the local (non-relational) embeddings, such as an MLP with sigmoid activation function. Assuming the mussage-passing is running for T time steps, for every r E R(A), 1 1 T, we have the updates:
(A)[[N+ BEN vf(A) S(()) (A), [M,(B). (BB) BEN.(A))
he (A)) = ui(r)
h((A) = EXER(A) (A)
(AA)) DrER(A) (A)
where (h(()) and fuy. are edge-type specific functions implementing. respectively: combine/update operation that provides a refined latent representation (A), and a local readout operation that provides a candidate prediction based on single neighbourhood (,(.A.. The operator O aggregates the predictions over the neighbourhoods r E R(A),, e.g, by maximum or summation, whose selection criterion for interpretable models will be discussed in Section 3.4
3

---

Relational task predictor. The final task prediction for the atom A is given by y" (A), via the combination of the aggregation function and the local readout fulr at time T. We note that this formulation unifies and extends the role of the task predictor in CBMs and of a readout function in GNNs. In practice, each task predictor fi(-)) can be implemented by any blackbox-like function, like the one used in GNN architectures (29] or CBM-Deep 13] However, an interesting alternative is to use either a partially interpretable function, like in linear CBMs, or a fully interpretable function, like in Deep Concept Reasoners (DCR) M. which constructs logic rule combining the predictions of the incoming atoms. Further details on selectable task predictors are in App. A.4
Example 3.1. Given a local neighbourhood for the atom grandparent( Abe, Bart), such that
N (ggrandparent( Abe, Bart)) - pparent(Ale Abe, Hamen) H omer, Bart), pareet) (oonent(Homerr Hmmer, Lisa)]
a non-interpretable Ji()) can compute the prediction v, (grandparent( Abe, Bart)) based on the neighbourhood. An interpretable fi()). like the one used by DCR, can also provide an explanation for the prediction, like e.g. parent( Abe, Homer) A parenr( Homer, Bart) - grandparent( Abe,, Bart).
3.3 Learning
In this paper, we use joint (end-to-end) SGD training of the atom encoder and predictor, as the original CBM paper [13] suggests for generalization. The learning problem can be stated as follows.
Definition 3.2 (Learning Problem). Given: a relational language (E, P) with all the atoms collected in HB; set of entities represented by their corresponding feature vectors in X (i.e. the imput); a dataset composed of subset of supervised atoms D = 44) A; E HB, 1 E {0, 1}}, where 4 is the corresponding ground-truth value for A;; models Ip: 8, Wegr): f((r) with parameters т and a maximum number of iterations T; an atom dependency graph determining the relational structure of all the atoms; a loss function L. Find: min, EMAADED L ((y(((A)) (A)),
3.4 Examples of Relational Concept Bottlenecks
To derive specific instantiations of R-CBMs, we introduce the notion of templetized hyperedge for an atom dependency graph. A templetized hyperedge p is defined as a standard hyperedge, but where the source and/or the destination contain one more variables. For example, p (Ip (u, u), P2(u, p(v,e) e)) is a templetized hyperedge, meaning that we have an hyperedge istance for each possible grounding the hyperedges generated by the same template are associated to the same edge label 1(r), so that both model functions "y([), Sr(t)- are shared across all instances of the same template. We omit the subscript in case there is a single templetized hyperedge in the hypergraph (e.g. one single edge type in the dependency graph).
the variables occurring in the atoms (i.e. v, u in the example). All
Case #1: Standard CBMs. A standard (non-relational) CBM can be easily seen as an R- R-CBM, by making few assumptions the relational language and the atom dependency graph it is based on: (i) all predicates are unary, and can be partitioned into two disjoint sets, i.c. the concepts c....., Cj and tasks fi, ....... fim. respectively, (ii) in the atom dependency graph any concept atom has no parents, i.e. for every atom of the form c(e), we have R(c(e)) = 0, and for every task f there is exactly one templetized hyperedge P whose source is composed by all the concept atoms, iee (t(vi) = [cr (v), ((()),,....(())))))) (. (iii) T = 1. Hence, the final prediction on an atom A = p(e) is obtained as s(A) = s(g,(x)) if p is a concept predicate, and y(A) fp(((c (e))...., ((cx((()))))) (e))). if p is a task predicate. For instance, given the unary predicates P = {red, round, tomato). possible concept bottleneck is given by the templetized hyperedge N (tomato(v)) = [red(v). round(v)).
Case #2: Node classification via GNNs. R- R-CBMs allow the modelling of simple relational structures, such as relation -ntityy graphs, which are typically used by GNNs to generate and update node embeddings. For instance, let us consider a node classification task wrt a class p. and let q denotes the relation in the graph. This can be represented by the templetized hyperedge A (p(()) (q u)]- For a heterogeneous graph with qı.-.. qu relations, we can instead consider the templetized hyperedge ((p(v)) (q1 (v. u......... Ih (V, w)]. besssagepaassing and readout in GNNs special cases of R-CBMs, as embeddings do not depend on atom predictions and readout occurs only at step T::
((A) = u (R (A), [B) (B)) (A) = (A)(
4

---

croleddiins
oVNN chooder
slow profictor
predictions
USipart)
W sibe.. Borth
ewaity eucoddrr
U.S.Homerr
UiSi/aatt)
jareatt Harth
(n/HHuooee))
(()))) - [
refational concept bettlencek
Figure 3: In R- R-CBMs (i) the atom encoder maps input entities to a set of ground atoms (red/green indicate the ground atom label false/true), (ii) the relational bottleneck guides the selection of concept atoms by considering all the possible variable substitutions in O (iii) the atom predictor maps the selected atoms into task prediction, and (iv) the aggregator @ combines all evidence into a final task prediction.
Case study #3: Templetized relational concept bottlenecks. The templatization standard CBMs can be further generalized, as relational bottlenecks represent more complex interactions.
Definition 3.3 (Templetized relational concept bottleneck). Given an n-ary predicate p, and an integer w 2 0, we define a templetized relational concept bottleneck of width w as the expression:
N(p(F)) b(ū,
where 0 = (Ui,..., vn). ã = (u....., Uw) are variables and b(ū, ū) is list of atoms with predicates P and tuples of variables taken from {Vi...., Uny U1..... }
For instance, assuming partition the predicates into two disjoint sets, i.e. concepts and tasks, similarly to what considered for standard CBMs, Definition 3.3 specifies the input-output interface of concept-based task predictor in a relational context, being p a task predicate and the predicates contained in b the concept The following example grounds this definition in a concrete setting.
Example 3.4. Given the binary predicates grandparent (task) and parent (concept), b(v1, U2, u) = [parent(vr, (n,, u), purent(u, v2)] we get the templetized relational concept bottleneck:
1 and
N N(grandparent(en (01, u2)) pparen( (U1, u), parent(u, v2)]
Figure 3 illustrates the instantiation of relational concept bottleneck N(US(w)) (U)( parentu,, v)]. for & = |iillie, Homer, Bari].
We notice that by replacing the variables e with entity tpple in Definition 3.3 does not correspond to an univocal instantiation of a relational concept bottleneck, as the same destination atom is predicted for every substitution 0 of the variables ü. For instance i = [Abe, Homer, Bart, Lisa] in Example 3.4 we have different hyperedges having grandparent( (Abe, Bart) as tail:
N Wggrandparem(AAe Abe,, Barl)) Iparent( Abe, Abe), parent( Abee,i(AAbe Bart)]
(0. {u/Abe})
N (grandparent Abe, Barl)) parent( Homer), (aneer))prreer parent( Homer, Bart)]
(0.. {w/ Homer))
N (graanpparen Abe, Barl)) pparent Bart), .parent Bart, Bur()]
(0.. (a/Brr))
N (grandparent, Abe, Bart)) = |parens[Abo Abe, Lisa), parent Lisa, Bart))
(A.. Tu/Lisa)
Each separate grounding of relational concept bottleneck corresponds to separate predicate prediction, as the same destination atom can be predicted by different bottlenecks. Taking again Example 3.4, we can assume to have also the bottleneck: Na(grandparent(vn, v2)) (grandpurent( u), sister(u, v2)] which also adds the hyperedge:
N2 Na(grundparenn( Abe, Barl)) Igrandparent Abe, Lisa), sister Lisa, Bart)] (0.= Lisa))
The final prediction obtained by aggregating all the single predictions with the + operator.
App. discusses how select the atoms input relational concept bottleneck.
5

---

Aggregation semantics. In standard CBMss the interpretation of the prediction solely depends on the task predictor f and there a single templetized hyperedge from concepts to any task node. However. the same atom can be predicted by different bottlenecks in R-CBMs. Indeed, different bottlenecks can represent separate dependency paths for the same atom like: ( = b (7, ūn ( = by(B,, (z)................ Even when considering single bottleneck, the same grounding for ø corresponds to multiple dependencies for the same atom if w > O. Each ground bottlenck corresponds to a separate hyperedge in the dependency graph and it plays fundamental role the choice of the aggregation function ① In this paper, we select as + = max, as it guarantees a sound interpretation to R-CBMs' predictions. Indeed, the max aggregation corresponds to the semanties of an existential quantification on the variables ū. As a result, the final task prediction is true if the task predictor f fires for at least one grounding of the extra variables.
Example 3.5. Following Example 3.4, we consider a task predictor f as logic conjunction (A) between concept atoms. If we use + max, then the final task prediction true if least one substitution for u is true, i.e. if there exists an entity that is parent of Barr and such that Abe is her/his parent. Hence, the final task prediction can be interpreted as the logic formula
Bu parent(AAe, u) A parent(u u, Bart) + grandparent(Abe Bart)
In summary, assuming ! max and that each is realized logic rule y, relational concept bottleneck with N (p(()) = b(ū, ū) can be associated with the explanation:
Vo Fu c (() u))
p(7)
where Vü= = Vui,-... Vun and Big = Bu,,..., 3r like done in logic programs 14].
Experiments
In this section we analyze the following research questions: Generalization -an standard/relationall CBMs generalize well in relational tasks? Can standard//eelational CBMs generalize in out-of-
distribution settings? 3)
Interpretability-Caal relational CBMs provide meaningful explanations for their predictions? Are concept/rule interventions effective in relational CBMs? Efficiency Can relational CBMs generalize in low-data regimes? Can relational CBMs correctly predict concept/task labels with scarce concept train labels?
Data & task setup. We investigate our research questions using 7 relational datasets on image classification, link prediction and node classification. We introduce two simple but not trivial relational benchmarks, namely the Tower of Hanoi and Rock-Paper-Seissonn that standard CBMs cannot even solve very simple relational problems. The Tower of Hanoi is composed of 1000 images of disks positioned at different heights of a tower. Concepts include whether disk is larger than j (or vice versa) and whether disk is directly on top of disk j (or vice versa). The task is to predict for each disk whether it is well-positioned or not. The RPS dataset is composed of 200 images showing the characteristic hand-signs. Concepts indicate the object played by each player and the task is to predict whether a player wins, loses, or draws. We also evaluate our methods on real-world benchmark datasets specifically designed for relational learning: Cora, Citeseer, (30), PubMed (23 and Countries on two increasingly difficult splits (88). Additional details can be found in App. A. and App. A.5
(RPS), to demonstrate
Models. We compare R-CBMs against state-of-the-a concept bottleneck architectures, including CBMs with linear and non-linear task predictors (CBM-Linear and CBM-Deep) [13), flat version (Flat-CBM) where each prediction is computed as a function of the full set of ground atoms, but also with Feedforward and Relational black-box architectures. We also compared against DeepStochL.og 33), a state-of-the-art NeSy system, and other KGE specific models for the studied KGE tasks. Our relational models include R-CBM with DCR predictor (R-DCR) and its direct variant, using only 5 supervised examples per-predicate (R-DCR-Low) We also considered a non- interpretable R-CBM version where the predictions are based on an unrestricted predictor processing the atom representations (R-CBM-Emi) Emb). In the experiments, the loss function was selected to be the
'The code to replicate the experiments presented in this paper is available at atlttps:: http:::///githut com. di 1 1iiiiiic www.gmmeeeeeMMM wwwp:e/RREM-NNeueeeeeeee Neurip2024

---

Table I: Models' performance on task generalization. R-CBMs generalize well in relational tasks. A indicates methods that cannot be applied due the dataset structure. OOT indicates out-of-time training due large domains,
MODEL
FEATURES
DATASETS
Class
Nome
Rei. Interge.
Rales
RPS
Hansi
Cora
Clisser
PulMed
Countiess S1
Countries 82 (MKR f)
BROC AUC
(ROC-AUC
(Noouracy 13
(hocurccy "
(Noouacy "3
(MKR
Freehormadd
No
No
No
$1.96
16.5
15,15 4-70
Black
Yes
No
Lic
57,87
Relacioual C&S
Ves
Yes
63.50 0.005
64.90 4:4
78
Nely
Peepdrichingg eg
Yes
Yes
Given
100.00
8100
100000:0000
77.00
74.8 1.84
No
Vix
No
$1.00 0..1
A
A
A
A
A
CBM
CRM-ibesp
No
Parril
No
55.01
1.50
$6.94 1.0.8
A
A
A
No
Yes
14.88+00025
9.35
R-CHM
Ros CBBM
R-CDM--Bapp
You
Yes
Parral
Yes
No
No
100.00 0.000
50.74
0..55
100.00.1 0.00
82.01
+-3.82
TK.
007
1.48
05.00 1.75
O0T
75.56
OUT
92.75 2.12
OCT
91.81 12201
OOT
(Dung)
R-DER
Yes
Yes
Exame
96 TT 0-331
99.00 9-000
75.30 2.100
08.88 1.32
75,00 + 1774
08.33 2.0
4 1.58
Vos
Yix
Lom
96 1.00
$0.62.1
1:587
Table 2: MRR and @ metrics on the test set of the WNI8RR and FB1 233daatt.... The competitor
results have been taken from Cheng et al. [2] or from the original datasets.
Class
Name
WNIERR
FB15K-237
(MRR 1)
(Hits@1
(His@110
(MRR ")
(Hiss 1)
(Hits 10
DistMalt
0.42
0.382
0.307
0.21
0.135
0.119
Black
CoavE
0.43
0.401
0.525
0.33
0.237
0.501
Box
ComplEx
0.44
0.512
0.163
0.452
ComplEx-N3
0.48
0.570
0.37
0.560
NLIL
0.30
0.201
0.335
0,15
0.324
Logic
RNNLagiC with emhh
0.48
0.558
0.530
Based
RLogie
0.47
0.443
0.537
0.31
0,208
0,501
LPRules
0.46
0.421
0.532
0,26
0,170
0.402
LotettLogic
0.48
0.497
0.553
0.32
0.212
0,514
RCDM
R R.C Eib
0.49
0.427
0.359
0,35
0.254
0.531
(ours)
R-DCR
0.47
0.563
0.35
0,255
0,533
Evaluation. We measure generalization using standard metrics, i.e., Area Under the ROC curve for multi-class classification, accuracy for binary classification, and Mean Reciprocal Rank (MRR) for link prediction, MRR and Hits@N for KGE tasks. We use these metrics to measure generalization across all experiments, including out-o--distribution scenarios, low-data regimes, and interventions. We report additional experiments and further details in App. A.3
standard cross-entropy loss. Further details are in App. A.2
5
Key Findings
5.1 Generalization
Standard CBMs do not generalize in relational tasks (Table Standard CBM best task per- formance ~ 55% ROC-AUC is just above a random baseline. This result directly stems from the architecture of existing CBMs, which can process only one input entity at time. The experiments validate that this design fails on relational tasks that inherently involve multiple entities. Naive attempts address the relational setting, like Flat-CBMs, lead significant drop in task general- ization performance (-17% in Hanoi), and become intractable when applied to larger datasets (e.g.. Cora, Citeseer, PubMed, Countries). In RPS, instead, Flat-CBMs performance close to random as the linear predictor for this model can not well approximate the required non-linear combination of concepts. These findings expose the limitations of existing CBMs when applied relational tasks and justify the need for relational CBMs.
Relational concept bottleneck models match the generalization performance of relational black-box models (GNNs and KGEs) in relational tasks. For example, R-CBMs exhibit gains of up to 7% MRR (Countries S1), and at most a 1% loss in accuracy (Citeseer) w.r.t. relational black-boxes. In larger KGEs like WN18RR. R-DCR beats standard KGEs and competitive against state-of of-te-of-theaar custom logic-based solutions. while being more general. Non- Non-interpretable solutions R-CBM-Emb are admitted by our relational formulation when fe is selected to be generic MLP blackbox. Since R-CBM-Emt and R-DCR only differ for the selection of the predictor (interpretable for R-DCR), a comparison of the results of these models on WN18RR provides a direct measurement of the performance decay due to the additional interpretability. Relational CBMs employing a simple linear layer as task predictor
R-CBMs generalize well in relational tasks (Tables I and 2.
7

---

Table 3: CBMs response interventions. R-CBMs effectively respond human interventions.
RPS
Hanol
Before Interv.
After Interv,
Before Interv.
After Intery.
R-CBM-Linee
49.46
47.83 +: 2.19
49.26 1.01
100.00
R. CBM Deep
51.35
2.00
82.02 1 6.34
50.07 1: 0.74
100.00 0.00
RCDCR
54.47 +: 1.64
100.00 1: 0.00
49.48 1: 0.35
100.00 1: 0.00
CBM-Linear
49.41 0.89
47.75 + 1.81
50.01 + 0.16
55.03 + 0.53
CBM- Mee-
50.83
0.93 51.22
47.78 4: 1.94
50.44 1: 0.46
60.14 + 0.46
1.60
50.00
0.00
50.00 0.00
(R-CBM-Linear) underfit tasks demanding non-linear combinations of concepts (e.g., RPS). In such scenarios, a deeper task predictor (e.g.. R-CBMs Deep) trivially solves the issue, but it also hampers interpretability.. R-DCRs address this limit providing accurate predictions while generating high-quality rule-based explanations (Table[). It also matches generalization performance of neural symbolic system DeepStochL.og [33] which provided with ground truth rules.
R-CBMs generalize in out-of-distribution settings where the number of entities changes test time (Figure 4. R-CBMs show robust generalization performances even in out-of-distribution conditions where the number of entities varies between training and testing. To assess generalization in these extreme conditions, we use the Tower of Hanoi dataset, where test sets of increasing complexity are generated by augmenting the number of disks approach, such as Flat-CBMs, immediately breaks as soon as we introduce a new disk in a tower, as its architecture designed for fixed number of input entities. contrast, R-CBMs are more resilient, as we observe a smooth performance decline from 100% ROC-AUC (with 3 disks in both training and test sets) around 85% in the most challenging conditions (with 3 disks in the training set and 7 in the test set).
tower. We observe that a naive
5.2 Interpretability
R-CBMs support effective interventions (Table
100
CBM architectures allow human interaction with the learnt concepts to intervene on mispredicted concepts during testing to improve the final predictions. In our experiments we assess CBMs' response to inter-
Taak ALC (R)
75
ventions on the RPS and Hanoi datasets. We set up the evaluation by generating a batch of adversarial test samples that prompt concept encoders to mis- predict ~ 50% of concept labels by introducing a strong random noise in the input features drawn from the uniform distribution (0, 20). our findings, we note that R R-CBMs positively respond to test- rest-time concept interventions by increasing their task perfor- mance. This contrasts with standard CBMs, where perfect concept predictions are not enough to solve the relational task. Notably, the RPS dataset poses a significant challenge for relational CBMs equipped with linear task predictors, the task depends on a non-linear combination of concepts. Expanding our investigation to DCRs, we expose another dimension of hhman--mode interaction: rule interventions. Applying both concept and rule interventions, observe that R-DCRs perfectly predict all adversarial test samples.
Number
R.CHM
Black Bins
CRM
Figure 4: Model generalization on Hanoi OOD the number of disks. Only R-CBMs are able to generalize effectively settings larger than the ones they are trained on.
Relational Concept Reasoners discover semantically meaningful rules (Table Among CBMs, a key advantage of DCRs lies in the dual role of generating rules which serve for both generating and explaining task predictions. Table 4 shows instances of R-DCR explanations, confirming that R-DCR discovers rules aligned with known ground truths across diverse datasets (e.g., wins{ X) <- -roc( pappe(()) -scissors( X) (X) Arock(Y) "paper(Y) (Y)eerr(Y))))) A -scissors(Y) in RPS). Notably, R-DCR discovers meaningful rules even low data regimes (R- (R-DCR-LOw) and when the correct. rules are unknown, such as in Cora, Citeseer and PubMed.

---

Table 4: Rules extracted by relational DCRs. In Hanoi, we remove negative atoms for brevity.
Dataset
Examples of learnt rules
Vu, Elu. wrins()) + -Fock()) A paper(u) A -acissors(1) (i) A rock(u) A -poper(u) A [scissors(a)
RPS
Vu, Ru. lases(v) + -moc(()) A -paper(t) A scissors(s) A rook(u) A -poper(u) A >scissors(1)
Vv, Du. tica(e) 6- rock(e) A (ppper(() -acissora(e) A rock(u) A -ppppe(()) A A-scissoos(s)
Ve, Bug, ug. correct(e) 6- top(u1, A toplu, wa) targge((e, un) (arger(ug, v) (arger(ug. us)
Hanoi
Vv, Ban,,. correct()) top(es wa) A toplus, (2) A sop(wz. Mt) larger(e, u2) larger(12, v)
Cora
Ve, Du. an(c) ma(aa) vi(u)) irul((u) A probM
:thcoru(u) A gene(u) cite(r, u) Bu. (upel(u) typel(() (type((() (erpprrmmental() ci
PubMed
Countries
Von, vg. Ju. located//(es 02) locotedIm(e) a) MooettodIn(u, v2)
Table 5: Data efficiency (Citeseer datasct). Relational CBMs are more robust than an equivalent relational black-box when reducing the amount of supervised training nodes.
Supervision
100%
75%
50%
25%
Rel. Black-Box
68.32 = 0.71
66 02 = 0.67
46,46 2.001
7.70 : 0.0
R-CBM-Linear
67.16 + 2.05
65.96 + 0.87
57.07 + 3.74
16.92 + 4.83
R CBe-Deepp
66.92 = 0.75
64.08 = 1.99
56.59 + 1.05
12.25 + 3.53
R-DCR
66.89 = 1.52
66.42 1.66
+3.10
16.32 1.29
5.3 Low data regimes
R-CBMs generalize better than relational black-boxes in low-data regimes (Table The ability of relational CBMs and relational black box models was compared on the Citeseer dataset as the number of labeled nodes decreased 75%, 50%, and 25%. While no significant difference was observed with ample training data, a growing advantage for relational CBMs over relational black box models emerged in scenarios of scarce data. The intermediate predictions related to incoming atoms likely have crucial regularization effect, particularly in scenarios with limited data.
R-DCR accurately makes interpretable predictions with very few atom supervisions (Table D.. R-DCR-LOw is able to learn an interpretable relational predictor when reducing the training data to 5 labeled atoms for each predicate. Indeed, the supervisions are crucial to establish an alignment between human knowledge and the model on the semantics of logical explanations. The alignment can be perfectly achieved in RPS. where the predictions mutually exclusive. On the Hanoi dataset, learning the relational binary concepts larger and lop from 5 examples is challenging, leading to slightly decreased overall performance.
6 Discussion
Related work on CBMs. Concept bottleneck models 13 inspired several works focusing on
improved generalization [15 5 31,, explanations [3] D and robustness [17] TO 36 1T.. Despite
these efforts, the application of CBMs to relational domains remains unexplored. Filling this gap, our framework allows relational CBMs (i) effectively solve relational tasks, and (ii) generalize the
explanatory capabilities of these models from propositional to relational.
Related work GNNs. R-CBMs and relational black-boxes (such GNNs) share similarities in considering the relationships between multiple entities when solving a given task. The prediction computation of R-CBMs is based on message passing paradigm which is similar to pesssage-passingg in graph neural networks 77 which is a special case of the proposed architecture. However, relational CBMs also define aggregations based on semantically meaningful concepts, allowing the extraction of explanations, which can not be done by GNNs.
Related work on ILP. Among our considered R-CBMs. R-DCR is the only learning set of logic rules, hence we can draw some parallels with some algorithmic solutions defined in Inductive Logic Programming (ILP) 21. R-DCR bottlenecks are connected to ILP mode declarations or metarules (2), which define the search space. However, while ILP involves searching through a hypothesis space of possible logical rules, guided by principles like consistency, coverage, and simplicity. R-DCR is different as it searches this space via gradient descent over continuous relaxation of the logic, and the logic formulas are learnt by exploiting neural architectures.
Related work on Neuro-Symbolic AI Neural Theorem Provers (NTP) 27 and their more scalable variations [20] combine formal proof proving with neural networks for efficiency via trainable

---

heuristic search. However, R-CBMs are more general than NTP -or other specific rule learners- indeed their interpretability is not restricted to rule learning, but rather rely on concept interventions. Moreover, unlike NTP, when dealing with logic rules the R-CBM framework is not limited to Horn clauses, and can be applied classic CBMs setups where inputs are not symbolic, but images. Moreover, R-CBMs templates can represent all the rules using (subset of a) specified list of atoms in the body at the same time, and the embeddings will be used to determine which actual rule to instantiate in each given context (like in R-DCR). On the other hand, NTP's approach to rule learning to enumeeaae all possible rules and let the learning decide which rules are useful. Please note that this approach is not scalable to larger KGs because of the combinatorial explosion of the number of rules when there are many predicates in the dataset.
Limitations. A limitation of relational CBMs consists in their limited scalability to very large domains. This limitation shared with all existing relational systems, and most relational models have to rely on simplifying heuristics to scale to large relational structures like knowledge graphs 37 26 Another limitation of R-CBMs lays in the need for the definition of relational concept bottlenecks, which acts an architectural inductive bias, restricting the search space. Future extensions of relational CBMs can relax the need of an external template definition by including an automatic calibration of template widths, the construction of reduced set of variables' substitutions, or the automatic generation of the relational templates.
Conclusions. This work presents R- R-CBMs, family of concept bottleneck models designed for relational tasks. The results of our experiments show that R-CBMs: (i) match the generalization performance of existing relational black-boxes, (ii) support the generation of quantified concept- based explanations, (iii) effectively respond to test-time interventions, and (iv) withstand demanding settings including out-of-distributin extension of standard CBMs, and pave the way to further investigations using CBMs to improve interpretability in GNNs and to explain KGE predictions.
scenarios, and low data regimes. R-CBMs represent a significant
Acknowledgments and Disclosure of Funding
PB acknowledges support from SNSF project TRUST-ME (No. 21S121L_2119911 This research has also received funding from the KU Leuven Research Fund (STG/22/021, CELSA/24/008) and from the Flemish Government under the "Onderzoeksprogramma. Artificiële Intelligentie (AI) Vlaanderen" programme. FG has been supported by the Partnership Extended PE00000013 "FAIR Future Artificial Intelligence Research" Spoke 1 "HHuman-centered Ar". MD was supported by TAILOR and HumanE-AA A-l-eet-A--eet. AI-Net, projects funded by EU Horizon 2020 research and innovation programme under GA No 952215 and No 952026, respectively. This project has also be partially supported by the EU Framework Program for Research and Innovation Horizon under the Grant Agreement No 101073307 (MSCA-DN LeMuR).
References
[1] Pietro Barbiero, Gabriele Ciravegna, Francesco Giannini, Mateo Espinosa Zarlenga, Lucie Char- lotte Magister, Alberto Tonda, Pietro Lió, Frederic Precioso, Mateja Jamnik, and Giuseppe Marra. Interpretable neural-symbolic concept reasoning. In International Conference on Machine Learning, pages 1801-1825. PMLR, 2023.
[2] Kewei Cheng, Jiahao Liu, Wei Wang, and Yizhou Sun. Rlogic: Recursive logical rule learning from knowledge graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 179-189, 2022.
[3] Gabriele Ciravegna, Pietro Barbiero, Francesco Giannini, Marco Gori, Pietro Lió, Marco Maggini, and Stefano Melacci. Logic explained networks. Artificial Intelligence, 314:103822, 2023.
[4] Michelangelo Diligenti, Francesco Giannini, Stefano Fioravanti, Caterina Graziani, Moreno Falaschi, and Giuseppe Marra. Enhancing embedding representations of biomedical data using logic knowledge. In 2023 International Joint Conference on Neural Networks (ICNN), pages 1-8. IEEE, 2023.
[5] Mateo Espinosa Zarlenga, Pietro Barbiero, Gabriele Ciravegna, Giuseppe Marra, Francesco Giannini, Michelangelo Diligenti, Zohreh Shams, Frederic Precioso, Stefano Melacci, Adrian
10

---

Weller, Pietro Lió, and Mateja Jamnik. Concept embedding models: Beyond the accuracy- explainability trade-off. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave. K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 21400-21413. Curran Associates, Inc., 2022.
[6] Shantanu Ghosh, Ke Yu, Forough Arabshahi, and Kayhan Batmanghelich. Dividing and con- quering blackbox to mixture of interpretable models: route, interpret, repeat. In Proceedings of the.. International Conference on Machine Learning. International Conference on Machine Learning, volume 202, page 1 11360. NIH Public Access, 2023.
[7] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
[8] Petr Hájek. Metamathematics of fuzzy logic, volume Springer Science & Business Media, 2013.
[9] David Hand and Robert Till. A simple generalisation of the area under the roc curve for multiple class classification problems. Machine learming, 45:171-186, 2001.
[10] Marton Havasi, Sonali Parbhoo, and Finale Doshi-Velez, Addressing leakage in concept bottleneck models. Advances in Neural Information Processing Systems, 35:23386-23397, 2022.
[11] Eunji Kim, Dahuin Jung, Sangha Park, Siwon Kim, and Sungroh Yoon. Probabilistic concept bottleneck models. arXiv preprint arXiv:2306.0157, 2023.
[12] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[13] Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In International conference on muchine learning, pages 5338-5348. PMLR, 2020.
[14] John W Lloyd. Foundations of logic programming. Springer Science & Business Media, 2012.
[15] Anita Mahinpei, Justin Clark, Isaac Lage, Finale Doshi-Velez, and Weiwei Pan. Promises and pitfalls of box concept learning models. arXiv preprint arXiv:2106. 13314, 2021.
[16] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. Advances neural information processing systems, 31, 2018.
[17] Emanuele Marconato, Andrea Passerini, and Stefano Teso. Glancenets: Interpretable, leak- leak-proof concept- based models. Advances in Neural Information Processing Systems, 35:21212-21227, 2022.
[18] Giuseppe Marra, Michelangelo Diligenti, and Francesco Giannini. Relational reasoning net- works. arXiv preprint arXiv:2106.000 000900000000....00000 2021.
[19] Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20(3):498-511, 2009.
[20] Pasquale Minervini, Matko Bosnjak, Tim Rocktäschel, and Sebastian Riedel. Towards neural theorem proving scale. arXiv preprint arXiv:1807.08200 2018
[21] Stephen Muggleton and Luc De Raedt. Inductive logic programming: Theory and methods. The Journal of Logic Programming, 19:629-6799 1994.
[22] Stephen Muggleton. Inverse entailment and progol. New generation computing, 13:245-286.
1995.
[23] Galileo Namata, Ben London, Lise Getoor, Bert Huang. and U Edu. Query-driven active surveying for collective classification. In 10th international workshop on mining and learning with graphs, volume 8, page 1, 2012.

---

[24] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, higg-ppeformance deep learning library. arXiv preprint arXiv: (rXiv:9912.07033 2019.
[25] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. the Journal of machine Learning research, 12:2825-20 2830,, 2011.
[26] Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. Rnnlogic: Learning logic rules for reasoning knowledge graphs. In International Conference on Learning Representations, 2020.
[27] Tim Rocktäschel and Sebastian Riedel. Learning knowledge base inference with neural theorem provers. In Proceedings of the 5th workshop on automated knowledge base construction, pages 45-50, 2016.
[28] Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. Advances in neural information processing systems, 30, 2017.
[29] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):61-88) 2008.
[30] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
[31] Johanna Vielhaben, Stefan Bluecher, and Nils Strodthoff. Multi-dimensional concept discovery (med): A unifying framework with completeness guarantees. Transactions on Machine Learning Research, 2023.
[32] Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. IEEE Transactions on Knowledge and Data Engineering, 29(12):2724-777 2743, 2017.
[33] Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt. Deepstochlog: Neural stochastic logic programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10090-10100, 2022.
[34] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv:1412.6577 2014.
[35] Chih-Kuan Yeh, Been Kim, Sercan Arik, Chun-Liang Li, Tomas Pfister, and Pradeep Ravikumar. On completeness-aware concept-based explanations in deep neural networks. Advances in neural information processing systems, 13:20554-20565
2020.
[36] Mateo Espinosa Zarlenga, Pietro Barbiero, Zohreh Shams, Dmitry Kazhdan, Umang Bhatt, Adrian Weller, and Mateja Jamnik. Towards robust metrics for concept representation evaluation. arXiv preprint 2.0.::2001.1066.. 2023.
[37] Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks. In ICLR, 2020.
12

---

A Appendix
A.1 Datasets
A.1.1 Rock-Paper-Seiisors
We build the Rock-Paper-Scissorrs (RPS) dataset by downloading images from Kaggle:
https://wwt wwtp://wwwwkkkk
http:::/www..kagggtt wwwp::wwww......o............... wttp://ttttcccc/ccttctoocctc http://gggg...ooooooaatattrrrraa
=esource=doonload/ The dataset contains images representing the characteristic hand- signs annotated with the usual labels "rock", "paper", and "scissors". To build relational dataset we randomly select 200 pairs of images and defined the labels wins/ties/loses according to the standard game-play. To train the models we select embedding size of 10.
A.1.2 Tower of Hanoi
We build the Tower of Hanoi (Hanoi) dataset by generating disk images with matplotlib. We randomly generate 1000 images representing disks of different sizes [1, 10) and different heights of the tower in [1, 10]. We annotate the concepts top(u (u, v), larger(u, v) using pairs of disks according to the usual definitions. We define the task label each disk according to whether the disk is well positioned following the usual definition that a disk is well positioned if the disk below (if any) is larger, and the disk above (if any) smaller. To train the models we select an embedding size of 50.
A.1.3 Cora, Citeseer, PubMed, Countries
we exploit the standard splits the Planetoid Cora, Citeseer and PubMed citation networks, as defined in Pytorch Geometric https: // httptt/cccchhhcecccctteccehtchet www.oorcch-hemmmeee gwwmetzemeeteeeoeee tric readthedochs http///e/Laaaatttccccsese/////// htt.aaattttttttmmmlll....mm The classes of documents are used both for tasks and concepts
For the experiments in Table I
The Countries dataset (ODbI. licence) defines set of countries, regions and sub-regions as basic entities. We used splits and setup from Rocktaschel et al. (28), which reports the basic statistics of the dataset and also defines the tasks $1, S2 used in this paper.
A.2 Baselines
A.2.1 Exploiting prior knowledge
Additionally, we can use prior knowledge to optimize the template and the aggregation by excluding concept atoms in b(ū, ū) and groundings in θ that not relevant predict the task. This last simplification is crucial anytime we want to impose locality bias, and it is also at the base of the heuristics that are commonly used in extension of knoweldge graph embeddings with additional
knowledge 26 37 4.
A.2.2 Cora, Citeseer, PubMed
Slash notation a/b/c indicates parameters for prracciteseer/pubnee when different.
R-CBMs exploit the same concept encoder J.. which corresponds of size 32/16/16 followed by an output layer size 6/7/3 classes. Activation functions are LeakyReLu. The blackbox feedforward network is equivalent the one of the CBM models. The blackbox relational model is a GCN with 2 layers of size 16. Node features for R-CBM models initialized with the last embeddings of the GCN. R-CMB Deep task predictor exploits layer MLP with hidden layers of size 32/16/10 16 followed by an output layer of size 1. Activation functions are LeakyRell
MLP with 2 hidden layers
R-DCR exploits, as filter and sign functions linear layer of size 32/ 16/ 16. DeepStochLog exploits the same concept encoder as neural predicate. It exploits also the pretraining using GCN, As task predictor, it exploits SDCG grammar implementing the rule cite(v,, v2) - class;(11) + class,(v))
13

---

A.2.3 Countries
The DistMult Knowledge Graph Embeddings (KGE) 34
was used as BlackBox relational baseline for the Countries S1 and S2 datasets. We varied the embedding sizes in the set {10, 20, 50, 100, 200, 300 and selected the best results on the validation set. The DistMult KGE was used as basic concept encoder for CMBs. The R-CBM-Linear computes the concepts via linear layer followed by the KGE output layer. The R-CBM-Deep computes the concepts via an MLP with hidden layers followed by a KGE output layer. Activation functions are Rel.u.
A.3 Experimental Details and Additional experiments
All experiments have been carried out on a machine with Intel i7 CPU, 128GB RAM. Running times for all experiments within I hour, with the exception of the link prediction experiment on WN18RR, which took 14h:20m.
A.3.1 Training Hyperparameters
In all synthetic tasks, generate datasets with 3,000 samples and a traditional 70%-10%-200% random split for training, validation, and testing datasets, respectively. During training, we then set the weight of the concept loss to À 0.1 across all models. We then train all models for 3000 epochs using full batching and default Adam [12] optimizer with learning rate 10 KGE experiments have used the Complex and Rotate KGE encoder and scorer function for gr, in the Countries and WN18RR datasets, respectively.
A.3.2 Data Efficiency
As explained in Section Section[A.2.2 the relational CBMs exploits the features obtained by pretraining on GNN on the same data split. Such pretraining is beneficial only in high-data settings (i.e. 100%, 75% and 50%). On low data regime (i.e. 25%), pretrained features worse than original features. In these cases, we train the different baselines from scratch by using directly the low level features of the documents.
For training R-CBM models on the WNI8RR dataset, we used the heuristic, commonly employed in the NeSy community, of instantiating only hyperedges where all source atoms observed in the training set 37
A.3.3 Countries
The task consists of predicting the unknown locations of country, given the evidence in form of country neighbourhoods and some known country/region locations. The entities are divided into the C, R, W domains referring the countries, regions and continents, respectively. The predicate locIn U1, 02) determines the location of a country in a region or continent, with the variables (v1,02) E R W (21,02) E R W. The country neighbourhoods are determined by the predicate neighOf U3) with the variables v1, Vi EC.
The entities in the dataset are set of countries, regions and continents represented by their corre- sponding feature vectors as computed by a DistMult KGE (see baselines). The concept datasets respectively the set Deiecta (C x R) U (R x W) and Deneiproy C x C. The task dataset D = C x W is formed by queries about the location of some countries within a continent. The templetized relational concept bottleneck is defined as:
W(locIn(Vi, v2)) [loc/n(v), u1), loc/nno/ (wi v2), neighOO( lo) v2)]
Finally, the cross entropy loss was used both for functions for concepts.
A.3.4 Hard-to-classify samples
R-CBMs can also be used to find easy/hard samples, similar to what done for standard CBMs in G). our framework, we consider as hard examples the ones whose prediction highly uncertain when using a CBM with a propositional template (see CBM-Deep rows in Table When using relational template, instead, we verified that the distribution of the prediction uncertainty significantly decreases. We show this in Figure 5] where the prediction uncertainty decreases when transitioning
14

---

from propositional to relational template. Table shows the concept/task activation for the hardest example to classify using the propositional template (high uncertainty) and the corresponding predictions when using the relational template (low uncertainty).
Hanoi
RPS
1000
750
200
Count
Model
Count
Model
300
Standard CBM
Standard CBM
100
Relational CBM
Relational CBM
250-
0.0
0.5
1.0
0.0
0.5
1.0
Uncertainty
Uncertainty
Figure Distribution of class prediction uncertainty comparing CBMs using relational propositional bottlenecks.
Table 6: Examples of hard to classify examples using propositional bottleneck (used by CBM- (BM-Deep) which become easy to classity when using relational bottleneck (used by CCB--Deep Concept activations
Dataset Model RPS
Task activations
CBM-Deep
rock(X) = 000, paper(X)= = 1.0, scissors( x) .00
wins(X) = .31, ties(X)
= .32 loses( XX) .36
R-CBM-Deep
rock(X) .00, paper(X) 1.0, scissors(X) .00,
wins(X) 001, tics(X)
rock(Y) .0. paper(Y)== = _00. scissors(Y)
=.01, loses(X) 1.0
Hanoi
CBM-Deep
PositionU(X) = .00, (ositiinn((X=== 000, Position2(X)
correct(X)
.200 Position3(X) .65, Position4(X) 335, Po-
sition5(X) _00, Position6(X) .00, SizeO(X)
.00, Sizel(X) .20, Size2(X) = .47, Size3(X)
.19, Size4(X) = .01, Size5(X) = .00. Size6(X) = .00,
Size7(X) .00, Size8(X) = 000 Sizc .0
R-CBM-Decp
top(X.Y) 1.0, t.p(Y.X) .00, top(X.Z) ,00
correct(X) 1.0
top(Z.X) .00, top(Y.)) 1.0, top(Z.Y) ,00,
larger(X,Y) = .000 larger(Y.X) = 1.0, larger(X.Z))
.00, largen(Z.X)= = 1.0, larger(Y,Z)) = .00, larger(Z,Y)= 1.0
A.3.5
Completeness scores
While Table reported evaluation of concept efficiency, here report the completeness scores of each concept-basee based model wrt the relational baseline, following Equation in [35], The results are shown in Table
RPS
Hanoi
Cora
Citeseer
PubMed
Countries SI
Countries SI
CBM-Linear
32.44
2.09
N/A
N/A
N/A
N/A
N/A
CBM-Deep
29.86
10.12
N/A
N/A
N/A
N/A
N/A
DCR
46.98
9.39
N/A
N/A
N/A
N/A
N/A
R-CBM Linear
26.92
102.52
98.91
93,66
58,00
105.41
111.61
R-CBM Deep
100.00
102.52
106.60
92.35
101.72
102.86
110.40
R-DCR
98.16
102.50
106.15
91.92
103.73
116.28
111.40
Table 7: Completeness scores of each concept-based model wrt the relational black-box bascline.
A.4 Relational Task Predictors
In standard CBMs, wide variety of task predictors ff have been proposed on top of the concept encoder g, defining different trade-offs between model accuracy and interpretability. In the following, we resume how we adapted a selection of representative models for f to be applicable in relational setting (fixing for simplicity 0). These are the models that we will compare in the experiments (Section 4 and 5)
15

---

Relational Concept Bottleneck Model Linear (R-CBM-Linear) The most basic task predictor employed in standard CBMs is represented by a single linear layer [T3. This choice guarantees a high-degree of interpretability, but may lack expressive power and may significantly underperform whenever the task depends on non-linear combination of concepts. In the relational context, we
define it as following:
f(0ablā, a)) = W0,b(Z, ū) + wo
(2)
Deep Relational Concept Bottleneck Model (Deep R-CBM) To solve the linearity issue of R-CBM, one can increase the number of layers employed by the task predictor (as also proposed in [3]. In the relational context we can define Deep R-CBM as following:
Deep R-CBM: f(O,b( a)) - (00,b(a, u)).
where indicate with MLP multi- -aytr perceptron. However, the interpretability between concept and task predictions is lost, since MLPs are not transparent. Further, the ability of a Deep R-CBM to make accurate predictions totally depending on the existence of concepts that univocally represent the tasks, hence being possibly very inefficacy.
15 proposed to encode concepts by employing concept embeddings (instead of just concept scores), improving CBMs generalization capabilities, but affecting their interpretability. Then (1 proposed use these concept embeddings to generate symbolic rule which is then executed on the concept scores, providing a completely interpretable prediction. We adapt this model in the relational setting:
Relational Deep Concept Reasoning (R-DCR)
R-DCR: f(0ab(ā, ū)) = (0,,b((z, a)),
where o indicates the rule generated by neural module working on the concept embeddings. For further details on how yp is learned, please refer to [0 Since the logical operations in R-DCR are governed by a semantics specified by a t-norm fuzzy logic (8), whenever we use this model we require the aggregation operation @ used in Eq. 3.2 to correspond to fuzzy OR. The max operator corresponds to the OR within the Gödel fuzzy logic.
Relational Deep Embedding Reasoning (R-CBM-Emb) 18 proposes latent relational process, which computes the atom representations using the presentations of other atoms that co-occur in the same ground formula. The final readout is based on an MLP processing the final atom representation. This model can exploit the rich reletional representations developed atom embeddings, but it acts as blackbox in terms of explanations of how the decision process takes form. This model can be implemented in our general model structure by restricting the fe function to only process the ha embeddings as input, such that:
(A(A)) = 2r(() (A) [h' [B)] (E))A))))))
(A) = MLP (h.(A)
R-DCR-Low R-DCR-Low is version of R-DCR that is trained by providing the atom supervisions for only 5 incoming hyperedges. Its architecture and learning is entirely identical to DCR except for two variants:
Since DCR strongly depends on crisp concepts prediction for learning good and interpretable rule, in absence of sufficient supervision, we need different way obtain crisp predictions. To this end we substitute the standard sigmoid and softmax activation functions for concept predictors 9, with discrete differentiable sample from bernoull or categorial distributions. The diffcrentiabilitty is obtained by using the Straight Through estimators provided by PyTorch.
Since the backward signal from DCR can be very noisy at the beginning of the learning, we add parallel task predictor (and a corresponding loss term), completely identical to the one of a R-CBM-Deee model. Such predictor only guides the lcarning of the concepts during training by cleaner backward signal but is discarded during test, leaving standard DCR architecture.
Flat Concept Bottleneck Model (Flat-CB assumes each prediction to be computed function of the full set ground atoms. This model has limited scalability but it is introduced for comparison reasons in the experimental section.
16

---

A.5 Code, Licences, Resources
Libraries For our experiments, we implemented all baselines and methods in Python 3.7 and relied upon open-source libraries such as PyTorch 1.11 (24] (BSD license) and Scikit-learn [25] (BSD license). To produce the plots seen in this paper, we made use of Matplotlib 3.5 (BSD license). We will release all of the code required to recreate our experiments in MIT-licensed public repository.
Resources All of our experiments were run on private machine with Intel(R) Xeon(R) Gold 5218 CPUs (2.30GHz), 64GB of RAM, and 2 Quadro RTX 8000 Nvidia GPUs. We estimate that approximately 50-GPU hours were required to complete all of our experiments.
Ethical Statement
There are no ethical issues.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claimed contributions in the abstract and introduction reflect the main contributions of the paper in terms model definition, analysis and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors? [Yes]
Justification:
This is done in the discussion section (
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
18

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Limited details given in Sections and with the remaining details provided Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
19

---

Answer:
[No]
Justification:
We will make the code public after publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
public ctllc//qiiese Codeeeuuoeodeemummmmmm ss onPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https?
//nips. w/npssccppubbll wttpcccppppppppcteeeceecccccccep cesii///uies///eeeeeeeeeooeessee ies CodeeSume ss cioooooliio oooiccyyy icy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
These details are given in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: ments.
We provide the standard-deviations multiple seedsall for most experi-
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
20

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We reported the details the machines exploited in the experiments in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://tpwrrrrrrre......o///a/aa
Answer: [Yes]
Justification:
Our research does not raise any ethical issue.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The paper does not involve an immediate societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
21

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We mentioned and respected all the licences of software and data in the Appendix.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paaperswis wwwoosocittcceeeeoo com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
22

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: The code and the related licenses will be released upon publication of the paper.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "0WlxuYJXL9", "reviewer": "Reviewer_WYX8", "summary": "This paper introduces Relational Concept Bottleneck Models (R-CBMs), a family of relational deep learning models that can provide some degree of interpretability and explainability; R-CBMs generalise both CBMs and GNNs.\n\nAccording to the authors, R-CBMs 1) match the generalisation performance of existing black-box models, 2) support the generation of logic explanations, 3) respond to test-time concept and rule interventions, and 4) generalise to out-of-distribution samples and in limited training data regimes.\n\nR-CBMs represent a relational graph as a set of atoms and dependencies among atoms and a directed hypergraph: each hyperedge defines a relational concept bottleneck from several ground atoms to a destination ground atom. Fig. 2 provides an example: the atom p4(b) can be predicted from the atoms [p3(b), p2(a, b), p1(b, a)], and these atoms all belong to the same hyperedge. What is the difference between the hyperedge notation and writing this as a Horn clause, e.g. p4(b) :- p3(b), p2(a, b), p1(b, a)?\n\nR-CBMs are composed of a few components: 1) an atom encoder/predictor, 2) a message-passing component that updates the atom representations based on the dependency hypergraph, and 3) a relational task predictor. Having GNN-like message-passing components for updating the embeddings and the predictions of the atoms, in my opinion, may invalidate the interpretability claims of R-CBMs since GNNs are intrinsically black-box neural models.\n\nOne of my concerns in this work is that there are already models that can learn and leverage Horn rules-like structures for interpretable relational predictions, such as Neural Theorem Provers (e.g., https://arxiv.org/abs/1705.11040, https://arxiv.org/abs/2007.06477) -- what's the delta between R-CBMs and NTPs?\n\nNTPs are really similar to the proposed approach -- for example, R-CBMs use \"max\" as the aggregation function to decide which hyper-edge to use when making a prediction, which is exactly the same strategy used by NTPs for deciding which \"proof path\" to use to prove whether a given atom is true or not.\n\nExperiments -- probably the most used dataset for relational link prediction in Knowledge Graphs is FB15k-237; why did you use WN18RR instead? Are there scalability issues due to the higher number of atoms or relational predicates in FB15k-237? Also, the paper introducing WN18RR was not cited (as well as several papers introducing the baselines).\n\nFor WN18RR, the paper proposes an apparently wide set of baselines. However, extremely simple but effective baselines like ComplEx-N3 (https://github.com/facebookresearch/kbc/, https://arxiv.org/abs/1806.07297, ICML 2018) produce more accurate results than the proposed method (0.58 Hits@10 vs 0.56).\n\nI really loved Tab. 4 with the examples of learn (symbolic) rules; however, learning symbolic rules is something that NTPs can also do -- can you please expand on the delta between R-CBMs and NTPs? Also, it's not completely clear to me how rules are learned -- is it because the encoder/predictor can be used to learn a dependency hypergraph that can be used to learn hyper-edges (the Horn clause-like structures)?\n\nUpdate after reading the rebuttal: the authors addressed most of my concern, I'm increasing my score!", "questions": "1) Can you clarify how the learning of the symbolic rules happens? Is it by learning a link predictor in the atom encoder module that can be used to extract hyper-edges/Horn clauses?\n2) Any answer addressing the \"Weaknesses\" would be really helpful", "limitations": "1) Are there scalability limitations of the proposed model? E.g., would you be able to evaluate on FB15k-237?\n2) What if you need more than one application of the rules? NTPs can handle that by applying them recursively", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) Interesting work with some degrees of interpretability/explainability!\n2) Results look robust for a non-factorisation-based method (I'm referring mainly to WN18RR since other link prediction datasets tend to be mostly solved/saturated)\n3) Wide array of graph learning tasks", "weaknesses": "1) It is not clear if it's reinventing Neural Theorem Provers (e.g., https://arxiv.org/abs/1705.11040, https://arxiv.org/abs/2007.06477), which can also be used to learn FOL rules via back-prop\n2) Why WN18RR instead of, e.g., FB15k-237? Missing very simple but effective link prediction baselines, e.g. https://arxiv.org/abs/1806.07297 (ICML'18)\n3) Writing is a bit opaque -- why use \"hyper-edges\" to introduce Horn clauses?\n4) Given all the GNN-like components inside R-CBMs, are they really interpretable?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Relations with Neural Theorem Provers:*   \n**More scalable variations of NTPs, such as CTP and Minerva, have been proved to be weaker baselines than other baselines (e.g., RNNLogic) that we considered in the experiments, e.g. the results in Table 3 from the RNNLogic paper \\[24\\]. This is why we decided to not include an older method like NTP, for which we would also miss a comparison on larger KGs, as NTP/CTP do not scale on them.** Please also note that our relational extension of CBMs is more general than NTP, or any other specific rule learner. In fact, CBMs do not necessarily learn rules (see the original paper \\[12\\]), and rule learning is not necessarily required for interpretability, which is usually assessed via concept interventions (Table 3), as discussed by the original CBM paper \\[12\\].   \nHowever, delving into more technical details, we claim that the R-CBM framework is more general and scalable than NTP for multiple reasons:\n\n*   R-CBMs are not limited to Horn clauses, for example R-DCR can learn rules with negated terms in the body.\n    \n*   NTP has never been applied in classic CBMs setups where inputs are not symbolic but images.\n    \n*   NTP has never been used to test interventions, which are an essential element for the interpretability of a CBM system.\n    \n*   R-CBM templates can represent all the rules using a (subset of a) specified list of atoms in the body at the same time, and the embeddings will be used to determine which actual rule to instantiate in each given context. This is particularly explicit in R-DCR, where a template can form a FOL rule for a grounding and another rule for another grounding. On the other hand, NTP approach to rule learning is to enumerate all possible rules and let the learning decide which rules are useful. Please note that this approach is not scalable to larger KGs because of the combinatorial explosion of rules when there are many predicates in the dataset. Moreover, the rules in NTP are obtained after training by decoding the parameterized rules, **by searching for the closest representations of known predicates.** This is very different from R-DCR, where the rules use exactly the referred predicates and are transparently executed to get the final predictions in all the training phases (cf. with original DCR paper \\[1\\]).   \nWe added a summary of the above discussion in the related works (Section 6) in the revised paper.\n\n*Complex-N3 and FB15k-237:*   \n**To strengthen our results, we included Complex-N3 as baseline and added a comparison on FB15k-237 as suggested (see Table B in attached PDF)**. Please note that even if ComplEx-N3 provides competitive results, it is still a black box, and it does not directly support concept-based interventions (the main purpose of concept-based interpretability methods such as R-CBM). We added these results in Table 2 of the revised paper.\n\n*Scalability:*   \n**Model inference scales as message passing (O(N\\*C) where N is the graph size and C is the size of the largest clique)**. As any other method grounding on a relational domain (such as hyper-GNNs), the graph size N grows as the cartesian product of the domain in the template. As discussed in the limitations and in A.2.1 (please note that a deeper discussion is beyond the scope of this paper), there are effective heuristics to limit the size of the graph, while retaining the relevant information to solve a task, see for example \\[24,33\\].\n\n*Can you clarify how the learning of the symbolic rules happens?*   \n**R-CBMs do not aim to learn rules, but rather to enable concept interventions (which is the main purpose of concept-based models) as discussed in the original CBM paper \\[12\\].** However, as R-CBMs generate symbolic concept layers, existing rule-based approaches can be applied on this layer to make interpretable predictions. In our paper, we used and compared with existing rule-based approaches including concept-based (DCR, \\[1\\]), NeSy-based (DeepStochLog), and KG-based (RLogic, RNNLogic, etc). Rule learning depends on the chosen method as described in the original papers respectively. For instance, DCR (and R-DCR, its relational adaptation) consists of (i) a neural module to learn the rule structure (by learning the relevance and polarity of each concept) and (ii) a symbolic module to execute the rule on the predicted concept truth values to produce the final prediction.\n\n*What if you need more than one application of the rules?*   \nIn R-CBMs the recursive application of the rules corresponds to repeating message-passing operations (Sec 3.2, L121). \n\n*Why use \"hyper-edges\" to introduce Horn clauses?*   \nThe hyperedge notation is more natural in the GNN community, where the current literature describes message passing operations on hypergraphs \\[Feng et al.\\].\n\n*References for dataset/baselines:*   \nWe have added to the revised paper the references when the dataset/baseline (such as WN18RR) is first mentioned in the paper.\n\n\n**References:**   \n\\[Feng et al.\\] Feng, Yifan, et al. \"Hypergraph neural networks.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dlRE3go4iq", "reviewer": "Reviewer_CYvd", "summary": "The paper introduces Relational Concept Bottleneck Models (R-CBMs), which address the challenge of designing interpretable deep learning models that operate in relational domains. Existing Concept Bottleneck Models (CBMs) are interpretable but lack the capability to manage relational data, while Graph Neural Networks (GNNs) can handle relational data but are not as interpretable. R-CBMs integrate the strengths of both by allowing interpretability in a relational context. They achieve this by mapping input features to a set of human-understandable concepts, then using these concepts to make predictions. The paper evaluates R-CBMs across various experimental settings, demonstrating that they match or exceed the generalization performance of existing relational models, support quantified concept-based explanations, respond effectively to test-time interventions, and perform robustly in challenging scenarios like out-of-distribution testing and limited data availability", "questions": "See Weaknesses", "limitations": "See Weaknesses", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The integration of GNN with CBM is novel.\n2. The generalization and efficiency experiment shows impressive result. This is important if we can extend CBM's interpretability to OOD problems.\n3. The writing is excellent. Overall this is an enjoyable read. The authors clearly discuss the reasons of each component very clearly. With examples, they clearly articulate the aim of the paper.\n4. The experiments were extensive, though real-world imaging datasets were not used.", "weaknesses": "1. Related work is insufficient but should have included the interpretable methods to fix this issue. Here are the two papers, the authors should include:\n* [Posthoc based]\n\n[1] Dividing and Conquering a BlackBox to a Mixture of Interpretable Models: Route, Interpret, Repeat. Ghosh et al. ICML 2023\n\n[2] POST-HOC CONCEPT BOTTLENECK MODELS. Yuksekgonul et al. ICLR 2023\n\n* [CLIP based]\n\n[1] Label-Free Concept Bottleneck Models. Oikarinen et al.\n\n[2] Visual Classification via Description from Large Language Models. Menon et al. ICLR 2023\n\n* [Relational CBM]\n\n[1] Relational Concept Based Models. Barbiero et al. arXiv 2023.\n\n[2] Interpretable Neural-Symbolic Concept Reasoning. Barbiero et al. ICML 2023.\n\n2. Insufficient baselines. The authors should comapre with atleast one of the posthoc based baselines. Also original CBM is not SOTA anymore as there are multiple variants of CBM.\n\n3. Do the authors assume to have concept annotation? this is expensive. Can it be aliviated with the LLMs to constuct the concepts. There are existing works which include the LLM to deduce the concepts. \n\n4. Currently the community is concerned about the incompleteness of the the concept annotations. So with the assumption of having concept annotation the authors fail to answer this question? How to address this incompleteness?\n\n5. CBMs can be used to find easy/hard samples. With relational model this can be done. The authors can perform an experiment for finding out the easy/hard samples. They can see Route, Interpret, Repeat paper.\n\n6. How to quantitatively evaluate the concepts extracted? The authors should have computed the concept completness scores (Yeh at al.) to do so.\n\n7. How to extend this work for imaging datasets like scene graph understanding?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Concepts’ evaluations, like e.g. concept completeness:*   \n**We report the completeness scores of each concept-based model wrt the relational baseline**, following Equation 1 in \\[Yeh, et al.\\].  The results are shown in Table D of the attached pdf (we added this result in Table 6, Section 5). An evaluation of concept efficiency was already in Table 5 in the submitted paper (showing the impact of reducing the number of concept/task supervisions during training).\n\n*Can R-CBMs be used to find easy/hard samples?*   \n**Yes, R-CBMs can be used for this.** The methodology presented in the “Route, Interpret, Repeat” paper is a technique which is not specific to a particular CBM, and it can be adapted to our methodology as well. In our framework, we consider as hard examples the ones whose prediction is highly uncertain when using a CBM with a propositional template (see CBM-Deep rows in Table C of the attached pdf). When using a relational template, instead, we verified that the distribution of the prediction uncertainty significantly decreases. We show this in Figure A (attached pdf) where the prediction uncertainty decreases when transitioning from a propositional to a relational template. Table C (attached pdf) shows the concept/task activations for the hardest example to classify using the propositional template (high uncertainty) and the corresponding predictions when using the relational template (low uncertainty). We added this analysis Appendix A.6 of the revised version of the paper.\n\n*References for related works:*   \n**We thank the reviewer for the suggestions, we added the missing relevant references** (with the only exception for “Interpretable Neural-Symbolic Concept Reasoning” \\[1\\] which was already part of our evaluation). Regarding post-hoc and CLIP-based CBMs as related works, we are well aware of these papers, but in our opinion these are not closely related works as they focus on ways of obtaining concept labels when such concept annotations are not available, and their extension to the relational case is not trivial, but requires significant further research as discussed in the common answer to the reviewers.\n\n*How to extend this work for imaging datasets like scene graph understanding?*   \n**The “Tower of Hanoi” dataset we used in our experiments already represents an example of a setting similar to scene graphs**, where disk images correspond to objects and their relations (i.e., top(u, v), larger(u, v)) correspond to concepts.\n\n**References**   \n\\[Yeh, et al.\\] Yeh, Chih-Kuan, et al. \"On completeness-aware concept-based explanations in deep neural networks.\" Advances in neural information processing systems 33 (2020): 20554-20565.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PFXSlcJXSe", "reviewer": "Reviewer_raJm", "summary": "This paper proposed a Relational Concept Bottleneck Models(R-CBM), which merge CBMs and GNNs together. To be more specially, it encode atom into concept like CBM and did message passing afterwards like GNN.", "questions": "See the weakness above", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of combining GNN and CBM is novel and it enable the CBM to learn relational data.\n2. The results of the experiment are somewhat competitive.\n3. Relative clarity in the articulation of the motivation for the experiment", "weaknesses": "1. It seems like the CBM provide a initialization of GNN model, therefore, it is not enough to compare with only CBM model as baseline. Because essentially, this is a GNN model. I think we should provide baselines for different GNN + different initialization as comparison.\n\n2. Concepts in CBM are clearly defined. Can the author clearly defined what are the concepts in each of your dataset? When the dataset become larger, how to define your concepts?\n\n3. I think some good property that R-CBM learned like example 3.4 and 3.5 could be formalized better.\n\n4. Table 4 list some easy relations that R-CBM learned. While I think the power of R-CBM should be learning relations that people could not identify. Could you show some other complex relations?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Table 4 lists easy relations that R-CBM learned. Could you show complex relations?*   \n**Please notice that Table 4 shows rules learnt by R-DCR, other R-CBMs do not learn rules, but rather enable concept interventions (which is the main purpose of concept-based models).** R-DCR is the relational adaptation of Deep Concept Reasoner (DCR) \\[1\\], which was a method designed to provide **simple** **instance-based rules to aid interpretability** (cf. with section “Rule parsimony” in the original DCR paper \\[1\\]). In DCR, the complexity of the rules could be controlled with a hyperparameter $\\\\tau$. Modifying this hyperparameter leads to more complex rules, even though this is in direct opposition with the aim of interpretability. For instance, in RPS we obtained two different equivalent rules tuning this hyperparameter:   \n$\\\\tau=1$: wins(player1) $\\\\leftarrow$ $\\\\neg$rock(player1) $\\\\land$ paper(player1) $\\\\land$ $\\\\neg$scissors(player1) $\\\\land$ rock(player2) $\\\\land$ $\\\\neg$paper(player2) $\\\\land$ $\\\\neg$scissors(player2)   \nwhich is equivalent but longer than the following:   \n$\\\\tau=100$: wins(player1) $\\\\leftarrow$ paper(player1) $\\\\land$ rock(player2)   \nIn KGs, by tuning this hyperparameter we also found more complex rules with redundant terms such as (notice that neighborOf(X,Y) and locatedIn(Y,W) provide further relevant evidence but are redundant):   \nlocatedIn(X,Z) $\\\\leftarrow$ neighborOf(X,Y) $\\\\land$ locatedIn(Y,W) $\\\\land$ locatedIn(X,W) $\\\\land$ locatedIn(W,Z)   \nAnd we also found longer chains such as:   \nlocatedIn(X,W) $\\\\leftarrow$ neighborOf(X,Y) $\\\\land$ neighborOf(Y,Z) $\\\\land$ neighborOf(Y,Z) $\\\\land$ locatedIn(Z,W)\n\n*It seems like the CBM provides an initialization of the GNN model & GNN baselines:*\n*   **R-CBMs are not providing the initialization of the GNN model. On the contrary, GNNs provide the initialization of the R-CBM bottleneck.** To clarify the relation between R-CBMs and GNNs consider the following analogy with the non-relational setting. A CBM \\[12\\] can be seen as composed of three functions $g’ \\\\circ g’’ \\\\circ f$: the input encoder $g’: x \\\\rightarrow h$ (mapping raw features to embeddings), the concept predictor $g’’: h \\\\rightarrow c$ (mapping embeddings to concepts), and the task predictor $f: c \\\\rightarrow y$ (mapping concepts to tasks). In the non-relational setting and in the image domain, ResNets are a common function $g’$ in the literature. In the relational setting, our input encoder $g’$ is composed of GNN layers. As a result, R-CBMs do not provide initialization for the GNN, but rather the GNN provides the input for the atom predictor of the R-CBM.\n    \n*   **For a fair comparison, we compared R-CBMs with equivalent black-box baselines following the CBM literature.** For instance, in the non-relational settings, the original CBM paper (\\[12\\]) compared a ResNet (input encoder) + MLP (task predictor) black box baseline with a CBM composed of a ResNet (input encoder) + linear layer (concept predictor) + MLP (task predictor). Following this, in our experiments we compared a GNN (encoder) + MLP (task predictor readout) black-box baseline with a R-CBM composed of GNN (encoder, the same of the black box) + linear atom encoder (concept predictor) + MLP (task predictor readout).\n    \n*   **We also provided additional black-box baselines in KGs’ experiments (Table 2 in submitted paper) and we also compared with an additional graph-based method that is not black-box (cf. with C&S in Table A of the attached pdf).**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "51lu2kMxht", "reviewer": "Reviewer_XAga", "summary": "The authors propose Relational Concept Bottleneck Models, a family of relational deep learning methods that utilize concept bottleneck models to provide interpretable task predictions. R-CBMs are shown to predict well in various settings, matching the performanace of black-box models.", "questions": "What is the explanation for why R-CBM-Linear does not effectively respond to interventions for RPS?", "limitations": "Adequately addressed", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper studies an important problem\n\nThe paper is clearly written and experimental results are easy to follow\n\nThe results show strong and consistent improvements", "weaknesses": "It might be nice to include a comparison to a simpler graph-based method that is not black box, e.g. [C&S](https://arxiv.org/abs/2010.13993) and a discussion of how the choice of relational task predictor and aggregation affect interpretability\n\nWould be interesting to see how R-CBM compares with CBM on datasets that aren't specifically designed for relational prediction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*R-CBM vs CBM comparison on non-relational datasets:*   \n**Vanilla CBMs are special cases of R-CBMs in non-relational domains (as described in L158-167)**, hence R-CBMs’ results on non-relational datasets (where predicates are unary) would be identical to propositional CBMs’ results (architecture and losses are both identical).\n\n*Why does R-CBM-Linear not effectively respond to interventions for RPS?*   \n**The RPS task is a non-linear combination of concepts, so it can’t be solved with a linear model such as R-CBM-Linear.** When using non-linear task predictors (R-DCR or R-CBM-Deep), the task can be solved, and interventions become effective.\n\n*Comparison with a simpler graph-based method that is not black box:*   \n**We thank the reviewer for the suggestion. We have added the comparison with the method Correct and Smooth (C&S) as suggested (cf. Table A of attached PDF).** Please, see also the common answer on baselines for more details. We added this baseline in Table 1 in the revised version of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**Answer to all reviewers and ACs**
--------------------------------------

We first thank the reviewers for their thoughtful and insightful feedback. We think that by working on their comments, the quality of our manuscript has certainly improved, and we hope to have addressed all the raised concerns in this rebuttal. We reply to questions shared by two or more reviewers in this comment and reply to specific questions of single reviewers in the comments under their respective feedbacks. 

Summary of Changes
---------------------

In the revised version of the paper, we have included both the results of some additional experiments we conducted during the rebuttal and a few lines to better clarify some insightful points raised by reviewers. **However, the core of our work’s contribution and evaluation remains unchanged**. In the following we summarise the list of changes we have made. **Throughout the whole rebuttal we use references with letters (A-D) for tables and figures in the additional pdf page in attachment, while references with numbering refers to our original paper.** The changes are the following:

1.  We added a new experiment to compare with the Correct and Smooth (C&S) method (Table A, @XAga).
    
2.  We added a new experiment on the dataset FB15k-237, and added Complex-N3 among the baselines for the link prediction task (Table B, @WYX8).
    
3.  We added an experiment to show how our framework can be also used to identify easy/hard samples in a dataset (Table C, @CYvd).
    
4.  We included the completeness score of the concepts used by R-CBM (Table D, @raJm,@CYvd).
    
5.  We included a discussion on NTP (and its extensions) in the related work section (@WYX8).
    
6.  We added an example in Section 4 to clarify how concepts and tasks are defined in all datasets (@raJm, @CYvd).
    

**\# Answer to common questions**
---------------------------------

*@XAga @CYvd @WYX8–Baselines:*   
**Our work already includes SotA baselines** including SotA concept-based models (Deep Concept Reasoner \[1\], which is a further evolution of Concept Embedding Models \[5\], which is a SotA CBM architecture), SotA relational reasoners (DeepStochLog using optimal, ground-truth rules), and SotA KGEs (e.g., RNNLogic and the newly added ComplEx-N3). 
    
*   Regarding relational post-hoc CBMs, they would be interesting to consider, but as far as we know, there are no papers showing how to extend post-hoc CBMs to the relational case (as far as we know we are the first authors to do this extension for standard CBMs in general). In this setting, post-hoc CBMs would require relational concept discovery. However, CAV (method used in post-hoc CBMs to find concept vectors) is not designed for relational settings. In our view, this would require non-negligible further research that is not directly related to the objective of our paper. 
    
*   We have added (in Table 1 of the revised paper) the results of the suggested GNN baseline (Correct and Smooth) on our splits of the graph benchmarks (Cora, Citeseer, Pubmed) using the same GNN backbone used for all other methods (see Table A of attached PDF).
    

*@XAga, @WYX8–Impact of message passing, task predictor, and aggregation on interpretability:*   
**The meaning of 'interpretability' that we adhere to in this paper aligns with the standard notion used in CBMs: “Interventions make concept bottleneck models interpretable in terms of high-level concepts” (Koh et al. \[12\]) (quantitatively evaluated in Table 3)**. Hence, we notice that interpretability in CBMs (as well as R-CBMs) is not necessarily related to the transparency of the task predictor, but rather depends on the fact that both the input and the output of the task predictor are interpretable units of information (e.g., concepts and tasks). Similarly to ResNets in the non-relational case, GNNs are considered black boxes because message-passing layers are usually mappings between non-interpretable features (e.g. raw features or embeddings). However, R-CBMs’ message-passing propagates interpretable concepts. This enables to enlighten all message passing steps (over possibly multiple iterations), similarly to how concepts enable to enlighten the decision process of the task predictor in non-relational CBMs. In our experiments, we also considered fully-transparent task predictors based on DCR, which learns logic rules to produce task predictions based on concept activations (cf. L198-208 and paragraph “Models” in Section 4 and A.4).

*@raJm, @CYvd–Concepts’ definition/annotation for each dataset:*   
**The concepts’ definitions for RPS and Hanoi are reported in Appendix A.1. In all the other datasets there is no explicit distinction between the set of concepts and task predicates/atoms**. In order to further clarify this, we added in Section 4 the following example: “Let us consider as an example the Countries dataset. The task “locatedIn(France, Europe)” could be inferred by the concepts “locatedIn(Italy, Europe)” and “neighborOf(Italy, France)”, i.e. “locatedIn(France, Europe) $\\leftarrow$ locatedIn(Italy, Europe) $\\land$ neighborOf(Italy, France)”. But at the same time, “locatedIn(France, Europe)” could work as a concept to predict the task “locatedIn(Spain, Europe)” in another inference step, i.e. “locatedIn(Spain, Europe) $\\leftarrow$ locatedIn(France, Europe) $\\land$ neighborOf(France, Spain)”. This shows that the same predicate (locatedIn), and possibly the same ground atom (locatedIn(France, Europe)), can be used both for concepts and for tasks. As a result, there is not any additional cost to annotate concepts as these are the same labels already present in the original dataset.”.

Meta-review: The paper introduces Relational Concept Bottleneck Models (R-CBMs). Roughly speaking, R-CBMs merges CBMs and GNNs into an interpretable relational setting. The reviewers agree that this is novel and interesting work, while also pointing our some downsides, see e.g. the discussion about "concept incompleteness" and adding simple GNN-based models as additional baselines. In any case, the rebuttal of the authors helped to clarify some of the issues, and the reviews lean towards accept. I fully agree.  It would be nice if you could clarify the difference to "relational bottlenecks" (https://arxiv.org/pdf/2309.06629).
Decision: Accept (poster)