Conceptual Graph Counterfactuals

Questions:

1. The choice of utilizing N/2 pairs for the successful training of the GNN is indeed an experimental observation. This is clearly stated in the manuscript during the description of the proposed method (in Section 3 “Ground Truth Construction” it says “computing GED for only N/2 pairs to construct the training set is adequate for achieving high quality representations, as validated experimentally”). We believe that this empirical result is sound. The conducted study was consistent among several different datasets as well as node embedding components (Tables 6, 15). On top of this ablative result, it is worth noting that employing this specific number of pairs for all reported best scores resulted in superior performance compared to our competitors. This outcome further supports the efficacy of our chosen approach in achieving competitive results while optimizing computational efficiency.
2. Actionability, being a concept well-known within the XAI community, is deliberately introduced as a smaller component of our analysis. In the Introduction section, our focus is primarily on establishing motivation, and we intentionally refrain from providing a definition at that stage. Instead, a dedicated and detailed explanation is deferred to the concluding paragraph of Section 4.1.

We trust that our responses have addressed the reviewer's inquiries and concerns. We encourage a reassessment of their evaluations, expressing our gratitude once again for their time and critiques.

We sincerely appreciate the reviewer's comments and evaluations. We are eager to address any inquiries in the hope of convincingly conveying the contribution of our work, which we believe to be substantial.

Regarding reported weaknesses:

1. We wish to draw the reviewer's attention to the novel aspect of our approach, which lies in the representation of the input using semantic graphs. This unique approach enhances the expressivity and flexibility of the proposed counterfactual method, facilitated by the utilization of simple yet effective and efficient GNNs —a combination unprecedented in this field. While it is accurate to acknowledge that each individual technical method employed in our paper is not introduced here, we maintain that the collective innovation stemming from their integration significantly contributes to the overall novelty of our approach. To this end, as described at the end of the Introduction and presented in detail later in the paper, we have undertaken a comprehensive series of experiments encompassing multiple datasets and classifiers. These experiments employ a diverse range of evaluation methods, incorporating both quantitative metrics and human evaluations. Considering the extensive volume of experiments conducted, we assert that showcasing the method's efficacy on two modalities is presently sufficient. Expanding this work further poses challenges in terms of space and readability, given the substantial amount of information already presented in the paper.

2. Assuming we have correctly interpreted the reviewer's comment, we would like to clarify that the density of the database is not a specific aspect addressed in this work. While we acknowledge the importance of this consideration, we believe that this assumption is not directly tied to our proposed approach but rather represents a general challenge for any counterfactual method in terms of utility and interpretability. The density of our graph database aligns with the data distribution of the input, making it a characteristic inherent to the dataset itself. In terms of graph size, it is essential to note that employing a GNN - which does not engage in a matching process in terms of edit operations - significantly mitigates computational demands. The potential "combinatorial explosion" is primarily associated with the computation of supervision GED labels. In our practical experience, even when dealing with larger CUB graphs (Table 9), computation times remained within a reasonable range (Table 8). It is crucial to emphasize that, given our focus on visual classifier explanations, and in alignment with the methods compared, scene graphs predominantly fall within the category of medium-sized graphs.

3. Evaluation of explanation methods is a rather challenging task; thus, we have employed several techniques to prove the superiority of our method. Regarding Table 5, we acknowledge the proximity of the reported results for the average number of edits metric, a point that we ourselves have highlighted. However, according to our other comparative measures, we can deduce the superiority in terms of semantic content. Firstly, qualitative results paired with provided analysis prove the importance of structure and relations (‘on’ predicate to separate the surfing activity from simply walking on the beach, correlated toppings etc.). This observation is also reinforced by Section 4.3’s driver vs pedestrian experiment. Secondly, ranking results in terms of the GED gold-standard are consistently higher than SC. To further validate these points, we have added the actual GED between source and counterfactuals in Figure 4 and overall results in Section D.2 of the Appendix. We kindly urge the reviewer to take these into consideration as well.

We sincerely appreciate the reviewer's thorough analysis and attention to detail regarding our work. We are eager to address any inquiries they may have and are committed to providing comprehensive responses in the hope of convincingly conveying the soundness and contribution of our work, which we hold with confidence.

1. In our experiments we have made a deliberate effort to maintain a consistent evaluation process to ensure fairness. Given the challenging nature of the evaluation of XAI methods, especially when the methods under comparison define distance on a completely different level (pixels vs semantics), we believe that using GED is a good way to establish a ground-truth (refer to paragraph “Evaluation” Section 4). In fact, having motivated the importance of basing explanations on semantics rather than mere pixels [1, 2], we believe GED is in fact the most method-agnostic way to establish semantic distance because it is directly based on all possible semantic changes both in terms of objects as well as relations. Practically optimizing for GED does not introduce bias into our approach; rather, it is a logical consequence of our emphasis on semantic relevance. To be even more precise, there is no doubt about the fairness of GED when comparing our method with SC. SC is also a conceptual method which models CEs by measuring distance. More precisely the authors are actually using a proxy for GED, which focuses on rolling up the edges into concepts. In terms of comparison with CVE, which is also semantically-driven, we believe that semantic distance between the depicted concepts and the way they interact should be quantifiable. Nonetheless, we have also reported further metrics as the reviewer points out. Human evaluation in this case did not just establish that humans prefer our proposed counterfactuals, they can understand the decision process of the classifier so well through conceptual graph counterfactual edits, that during training they do not even need to look at the images (pixel information).

2. The main contribution in comparison to SC lies on the input representation. We place an emphasis on semantic graphs because they are able to model the relations between objects combined with the underlying structure. As explained, SC do in fact propose the use of GED as a means of counterfactual computation. However, due to their choice of representation through sets of concepts, they are not able to actually compute it. To this end they roll up edges into concepts and perform an algorithm resembling GED. However, as pointed out in our paper the set representation leads to loss of information (Section 2). In the majority of their experiments they end up not leveraging edge information at all (this includes VG, CUB experiments) and when they do, they are still unable to detect “the multiplicity of objects and their relations” (as stated in our paper and explained with examples in the qualitative results of sections 4.1 and F). The novelty in terms of the computation method (i.e. the use of GNNs for GED approximation to facilitate counterfactuals) is a direct consequence which only adds to our contribution. Regarding the closeness of results in Table 5, we would like to point out that minimum number of edits is only one of our proposed metrics and as stated in the paper, one should view the results as a whole and with close attention to qualitative insights which can help us deduce the superiority of our method in terms of semantic content. To this end we have added the actual GED between source and counterfactuals in Figure 4 and further overall results in Section D.2 of the Appendix. Firstly, qualitative results paired with provided analysis prove the importance of structure and relations (‘on’ predicate to separate the surfing activity from simply walking on the beach, correlated toppings etc.). This observation is also reinforced by Section 4.3’s driver vs pedestrian experiment. Secondly, ranking results in terms of the GED gold-standard are consistently higher than SC.

3. The choice of baselines for the user studies is directly correlated with the purpose of each study. We performed two separate human evaluations. The first with the purpose to establish user preference among explanations and the second to test the understability of our semantic–driven graph-based method in comparison to a method purely based on pixels (detailed in section 4 “Evaluation” and further in Appendix A). To this end, in the first one we compared with both baselines, while in the second, a direct replication of the survey in CVE, we compare only with them. After all, we continue our analysis and dive deeper into the comparison with the method most similar to ours in the section directly following. Also the reviewer incorrectly states that CVE comparison is missing from Table 3.

4. In Sections 4.1 and 4.2 we utilized the available graphs because they already existed. To address the potential dependence of explanations on the scene graph generator, we conducted the experiments on Section 4.3. The “Unannotated Datasets” section does not only test the framework’s applicability on datasets were graphs are not originally available, but also tests two independent SGG settings - applying a SOTA SGG and creating graphs from image captions to avoid known SGG biases. The similarity in essence in the average counterfactual triple edits they produce, establishes that even with varying annotations (refer to Table 19 for graph statistics) the important semantic context to transition from one class to the other stays the same. This experiment is very close in nature to the approach proposed by the reviewer (using an SGG on VG, CUB)
5. Distances are not correlated to the distances in the classifier space. Although an interesting suggestion, we believe it is not in our best interest to adopt such an approach. The information needed to enforce this constraint would require us to peek inside the classifier and therefore automatically render our method white-box, stripping it from its flexibility and potentially its applicability to different modalities.
6. The choice of the Places365 classifier was a conscious decision. While ImageNet classifiers are more widely recognized and researched, they are trained on the ImageNet dataset, which primarily consists of foreground objects. In Visual Genome, the majority of instances depict scenes, providing substantial background. Although some instances focus more on specific objects, they are still situated within a particular environment. In contrast, ImageNet classifiers face challenges with such inputs, as only about 3% of the target classes in the corresponding dataset pertain to broader scenes. The reviewer rightfully noted that this analysis was missing from the manuscript, prompting us to address it by adding a paragraph in Appendix C.

We trust that our responses have addressed the reviewer's inquiries and concerns and strongly believe that these clarifications mitigate the grounds for the paper's outright rejection. We encourage a reassessment of their evaluations, expressing our gratitude once again for their time and insights.

[1] Dervakos, E., Thomas, K., Filandrianos, G., & Stamou, G. (8 2023). Choose your Data Wisely: A Framework for Semantic Counterfactuals. In E. Elkind (Ed.), Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23 (pp. 382–390). doi:10.24963/ijcai.2023/43 [2] Browne, K., & Swift, B. (2020). Semantics and explanation: why counterfactual explanations produce adversarial examples in deep neural networks. arXiv preprint arXiv:2012.10076.

We sincerely appreciate the reviewer’s critiques and would like to directly address their concerns, adhering to their format.

[Major]

1. Method & motivation: The reviewer's apprehension regarding the proposed framework's dependence on annotations rather than directly capturing the target classifier is essentially a critique of black-box models in general. However, this concern is not a specific issue to be addressed in the context of our paper. Previous work [1] has successfully embraced the black-box setting. As demonstrated in Tables 1, 2, 3, and 4, black-box models like ours not only compare favorably to methods with direct access to the model but can actually outperform them. Their superiority is not only quantitatively substantiated but also validated through human perception—an aspect of utmost significance given that explanations, including counterfactuals, ultimately target human understanding. It is essential to note that dismissing our approach based on potential adversarial attack risks may be unjust, as none of the other SOTA approaches provide similar guarantees. Even CVE, which is a white-box pixel-level technique and might initially be perceived as more robust against malicious input changes, fails to explore this specific use case and lacks corresponding insights. It is crucial to emphasize that a comprehensive robustness analysis of our method is a planned aspect of our future work, as outlined in Sections 5 and H. We appreciate the reviewer for these valuable suggestions that will contribute to our ongoing efforts in this direction.

[Minor]

1. Figures and Diagrams: Following this reviewer’s comment, we plan to apply this process for a potential camera-ready version. Reliance on annotations:
2. As highlighted by the reviewer, our method hinges on the availability or creation of annotations. We have conscientiously addressed this aspect not only in Appendix H but also in Section 4.3 (Unannotated Datasets) of the main paper, along with additional clarification provided in Section F of the Appendix. In our experimental setup, we employed a SOTA scene graph generator and BLIP, one of the most widely used captioners, in conjunction with a well-established relation extraction module to extract annotations. It's worth noting that the large multi-modal models proposed by the reviewer are designed to perform tasks that are not directly correlated with the annotations required by our framework (i.e. image segmentation, VQA, object classification etc.). Given the nature of our framework, where this specific aspect serves as a subsection demonstrating its extensibility, we contend that an exhaustive analysis of annotation construction is beyond the scope of this paper. We acknowledge the potential for constructing intricate pipelines to generate optimal annotations using the proposed models, and we recognize this as an intriguing future exploration.

We trust that our responses have addressed the reviewers' inquiries, encouraging a reassessment of their evaluations. We express our gratitude once again for their time and thoughtful suggestions.

[1] Dervakos, E., Thomas, K., Filandrianos, G., & Stamou, G. (8 2023). Choose your Data Wisely: A Framework for Semantic Counterfactuals. In E. Elkind (Ed.), Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23 (pp. 382–390). doi:10.24963/ijcai.2023/43

We sincerely appreciate the reviewer’s comments and would like to directly address their concerns.

Firstly, we believe that this reviewer has missed or misconstrued some parts of the paper’s motivation and methodology. For instance, the focus of the paper does not simply lie on “analyzing scene graphs built on semantic attributes of the data” or finding “the closest scene graph with a different label”. Omitting the explainability aspect from the analysis greatly shifts the reader’s perspective of this work and undermines its contribution to the field of counterfactuals in terms of flexibility, efficiency and expressiveness.

Some of the reviewer’s suggestions, although very insightful, are in fact already implemented in our approach (“editing should be assigned less weight compared to deletion when computing distance”, counting the distance between attributes differently according to their semantics). As explained in Section 3 subsection Ground Truth Construction, we have employed techniques from SC which consider the WordNet hierarchy for operation cost computation and define deletion and insertion as more costly operations. This information is considered implicitly since GED scores are our supervision signals and it would be impossible to directly employ them for GNNs because they do not perform these operations in the first place. Furthermore, regarding the comment questioning the use of cosine similarity, we would like to highlight that this metric is a straightforward choice for embedding comparison (graph in this case) and preferred here to avoid the curse of dimensionality.

As for the reviewer’s questions, we believe that to an extent they have been covered in the paper. Therefore, in the following response we will point the reviewer to the corresponding sections and provide further clarifications that hopefully answer their concerns.

1. Why computation of the ground-truth w/o NNs is prohibitive: As outlined in the paper, “GED does belong in the NP-hard complexity class”, rendering the computation of the ground-truth not only challenging but practically infeasible for larger graphs (see CUB statistics Table 9 in the Appendix). Even by leveraging an approximation algorithm over the GNN, the calculation process requires several hours (see Table 8). The GNN, as demonstrated empirically and documented, effectively cuts the computation time in half within the proposed transductive setting.
2. Approximation error: The error is quantified by measuring the deviation from the golden-standard GED ranking, a metric explicitly detailed in the paper. Tables 2, 6 of the main paper present various ranking metrics concerning the retrieval of the ground-truth across different datasets and GNN variants. It's crucial to note that, in terms of the approximation of the similarity score itself, this is, in fact, irrelevant to our approach. Naturally, there exists a trade-off between achieving perfection and computational efficiency. Given the highly demanding computational nature of GED, accepting a margin of error becomes a necessity. This acceptance further underscores the justification for involving human evaluators in validating the retrieved results.
3. Model-agnostic approach: We believe that there has been a misunderstanding of the term model-agnostic often used in conjunction with the term black-box. To elaborate, "model-agnostic" typically refers to XAI techniques that can be applied to different machine learning models, regardless of the specific algorithm or architecture. The statement “they cannot be used to understand how models make predictions” is therefore false, as further reinforced by the cited paper which explains how black-box CEs can be used to explain the decision-making process for GDPR purposes in Section V.A. To this end, there are no restrictive use cases for this type of explanation. In contrast, model-agnostic CEs offer benefits like increased flexibility which in this case is aided by the graph representation allowing the application of this approach for practically any modality (Section 4.3). If the reviewer’s concern lies on whether a model-specific / white-box technique would be a preferable choice, we refer them to Tables 1,2,3,4 proving the superiority of black-box techniques like ours against a SOTA approach with direct access to the classifiers.

4. Scene Graph Extraction: The paper addresses the event of the unavailability of annotations in Sections 4.3 and even further elaborates in Section F of the Appendix. In summary, graphs can be extracted via a plethora of available techniques such as Scene Graph Generation, Image Captioning plus Relation parsing. As for CUB, it is mentioned that it has “structured annotations” (Section 4.1 and Table 18 for example); thus, the choice of the representation is heavily guided by the available data.
5. As established in the beginning of this response, the fifth question has been already covered in the paper and solved by methods proposed in SC and adopted by the authors.

We trust that our responses have clarified potential points of confusion and addressed the reviewers' inquiries, encouraging a reassessment of their evaluations. We express our gratitude once again for their time and insights.