Relational Concept Bottleneck Models

R-CBM vs CBM comparison on non-relational datasets:
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).

Why does R-CBM-Linear not effectively respond to interventions for RPS?
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.

Comparison with a simpler graph-based method that is not black box:
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.

Table 4 lists easy relations that R-CBM learned. Could you show complex relations?
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:
$\\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)
which is equivalent but longer than the following:
$\\tau=100$: wins(player1) $\\leftarrow$ paper(player1) $\\land$ rock(player2)
In 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):
locatedIn(X,Z) $\\leftarrow$ neighborOf(X,Y) $\\land$ locatedIn(Y,W) $\\land$ locatedIn(X,W) $\\land$ locatedIn(W,Z)
And we also found longer chains such as:
locatedIn(X,W) $\\leftarrow$ neighborOf(X,Y) $\\land$ neighborOf(Y,Z) $\\land$ neighborOf(Y,Z) $\\land$ locatedIn(Z,W)

It seems like the CBM provides an initialization of the GNN model & GNN baselines:

• 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.

• 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).

• 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).

Please let us know if you have any further questions or things we could clarify further. If not, we would appreciate if you could consider updating your review based on our replies.

Concepts’ evaluations, like e.g. concept completeness: 
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).

Can R-CBMs be used to find easy/hard samples?
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.

References for related works:
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.

How to extend this work for imaging datasets like scene graph understanding?
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.

References

$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.

By concept incompleteness, i did not indicate concept completeness score. Concept completeness score indicates how good your concept can be a good predictor of the downstream labels. Concept incompleteness means what if your concept set is incomplete on the first hand. Look at the papers i refered.

Regarding concept completeness score, you provided in the pdf - is those numbers in percentages? usually concept completeness scores are b/w 0-1. I see some numbers are greater than 100 (e.g., 102.52). How is that possible? So, this part i consider is not rightly estimated

For the LLM point, LLM can be used to solve the question of incompleteness. and i believe at this point relational concepts can be obtained by using LLM as well, so these are not orthogonal. How to perform intervention with LLM concepts - there are papers like Language in a bottle (LaBo) (CVPR 2023). However i agree this can be explored in future. But that makes the contribution borderline.

Thanks again.

Relations with Neural Theorem Provers:
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$ .
However, delving into more technical details, we claim that the R-CBM framework is more general and scalable than NTP for multiple reasons:

• R-CBMs are not limited to Horn clauses, for example R-DCR can learn rules with negated terms in the body.

• NTP has never been applied in classic CBMs setups where inputs are not symbolic but images.

• NTP has never been used to test interventions, which are an essential element for the interpretability of a CBM system.

• 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$ ).
  We added a summary of the above discussion in the related works (Section 6) in the revised paper.

Complex-N3 and FB15k-237:
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.

Scalability:
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$ .

Can you clarify how the learning of the symbolic rules happens?
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.

What if you need more than one application of the rules?
In R-CBMs the recursive application of the rules corresponds to repeating message-passing operations (Sec 3.2, L121). 

Why use "hyper-edges" to introduce Horn clauses?
The hyperedge notation is more natural in the GNN community, where the current literature describes message passing operations on hypergraphs $Feng et al.$ .

References for dataset/baselines:
We have added to the revised paper the references when the dataset/baseline (such as WN18RR) is first mentioned in the paper.

References:

$Feng et al.$ Feng, Yifan, et al. "Hypergraph neural networks." Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019.