Optimal and efficient text counterfactuals using Graph Neural Networks (2024)

Abstract: As NLP models become increasingly integral to decision-making processes, the need for explainability and interpretability has become paramount. In this work, we propose a framework that achieves the aforementioned by generating semantically edited inputs, known as counterfactual interventions, which change the model prediction, thus providing a form of counterfactual explanations for the model. We frame the search for optimal counterfactual interventions as a graph assignment problem and employ a GNN to solve it, thus achieving high efficiency. We test our framework on two NLP tasks - binary sentiment classification and topic classification - and show that the generated edits are contrastive, fluent and minimal, while the whole process remains significantly faster than other state-of-the-art counterfactual editors.

## introduction since the introduction of the transformer @xcite the field of nlp has enjoyed an abundance of impressive implementations targeting a variety of linguistic tasks. explainability @xcite and interpretability @xcite in nlp are topics of increasing popularity, researching biases and spurious correlations which hinder the generalization capabilities of state-of-the-art (sota) models. adversarial attacks @xcite can trigger alternative outcomes of nlp models unveiling inner workings, therefore providing post-hoc interpetability. several prior attempts in creating adversarially perturbed inputs, focused on label-flipping scenarios, have been presented in recent literature @xcite @xcite , while other general-purpose approaches @xcite attempt to generate more generic perturbations. these methods though are accompanied with shortcomings, despite producing promising results in linguistic terms. one practical constraint is that they are computationally expensive @xcite and relatively slow during inference (i.e. mice requires more than 47 hours to produce edits for 1000 samples foot_1 ). another emerging issue is the fact that diverging from generalized textual generation towards interpretability requires a far more controlled generation process, as the opaque behavior of general-purpose editors @xcite built upon large language models (llms) often leads to sub-optimal substitutions @xcite ) (or at least we have no evidence regarding their optimality and why they were selected). in fact, creating optimal linguistic interventions is an algorithmically challenging problem, requiring efficient optimization of the search space of alternatives @xcite @xcite . in this work, we focus on word-level counterfactual interventions to test the behaviour of textual classifiers when different words are perturbed. our proposal revolves around placing all implemented interventions under a framework which presents the following characteristics regarding interventions: we approach these requirements by viewing counterfactual interventions as a combinatorial optimization problem, solvable via graph assignment algorithms from graph theory @xcite . to further enhance our method, we consider the use of graph neural networks (gnns) @xcite as a faster approximate substitute of these algorithms @xcite . our proposed method can be applied to both model-specific and general purpose scenarios, since there is no strict reliance on changing the final label. this property allows for generated edits to be used for different tasks apart from label-flipping, such as semantic similarity @xcite or untargeted generation @xcite ; nevertheless, in this paper, we focus on classification tasks for direct comparison with prior work. to this end, we compare our approach with two sota editors @xcite using appropriate metrics for label-flipping, fluency and semantic closeness. approaches based on large language models @xcite are not considered in this work, due to their hardware requirements foot_2 . to sum up our contributions are: ## related work exposing vulnerabilities present in sota models has been an active area of research @xcite , endorsing the probing of opaque models through adversarial/counterfactual inputs. granularity of perturbations ranges from character @xcite to word level @xcite or even sentence level @xcite . in our work, we focus on semantic changes, following the paradigm of word-level perturbations. manual creation of adversarial examples has been explored @xcite @xcite with the purpose of changing the true label. automatic text generation initially implemented via paraphrases @xcite , and most recently using masked language modelling @xcite @xcite , targets predicted label changes in binary/multi-label classification or textual entailment setups. similarity-driven substitutions based on word embedding distance @xcite ensure optimality in local level for classification tasks, while constraint perturbations guarantee controllability of adversarials @xcite . those works partially preserve some desiderata of our approach; however, they are model-specific and thus constrained. general purpose counterfactual generators fine-tune llms to offer diverse perturbations, applicable in multiple granularities @xcite @xcite . prompting on llms opens novel trajectories for textual counterfactuals @xcite , even though explainability of interventions is completely sacrificed, due to the unpredictability of llm decision-making. overall, utilizing llms is computationally expensive, while produced substitutions may not be optimal as far as word distance is concerned @xcite . on the other hand, interventions through the use of graph-related optimizations @xcite have recently emerged, showcasing that advanced performance and explainability of interventions are on par with computational efficiency. ## problem formulation the basis of our work constitutes a graph-based structure that places words extracted from sentences on nodes, and their in-between substitution costs on edges. let's consider a bipartite graph @xmath0, e), where the edge set e consists of all the weighted edges in the graph, and the node set v consists of the source set s of cardinality |s| = n and the target set t of cardinality |t | = m, such that s ∪ @xmath1, s ∩ @xmath2. finding optimal connections between nodes of g has been a long sought discrete optimization problem of graph theory, where the optimal match for each node @xmath3. assuming that w denotes the edge weight set consisting of the weights of all edges @xmath4, a min weight matching m ⊆ e searches for a subset of the lightest possible sum of edge weights w e , w @xmath5, |t |) set of g. therefore, in the case of |s| ≤ |t |, all nodes in s will be substituted 4 , should an outcoming edge e @xmath6, denoting that this substitution is feasible. under these requirements, we formulate the following constraint optimization problem: min w e , subject to s ̸ = t if ∃e @xmath7 a naive solution to this constraint optimization problem would be the exhaustive search of all possible (s, t) combinations, by examining all possible m! permutations of t until the optimal solution of min w e is reached. this yields an exponential complexity of o(m n ) (proof in app. d), supposing that g is complete, i.e. each pair of st nodes is connected so that @xmath8, |e| = nm. nevertheless, computational efficiency compared to the naive approach is guaranteed if we view this constraint optimization problem as a variant of the rectangular linear assignment problem (rlap) (bijsterbosch and volgenant, 2010): n source nodes should be assigned to @xmath9, so that the total weight of the assignment is minimized. rlap also allows multiple matchings to each source node s thus providing more flexibility in optimal matchings. assignment algorithms borrowed from older literature @xcite are adapted to solve rlap, achieving best deterministic complexity of o(mn log n), significantly reducing the exponential o(m n ). ## counterfactual generation overview the workflow of our method (figure 2 ) comprises of three stages. a textual dataset d serves as the input to our workflow. in the first stage, words are extracted from d, based on their part of speech (pos), and used as the source node set s. the target set t is either a copy of s, or else produced from an external lexical source such as wordnet @xcite , containing all possible candidate substitutions of the source words (nodes). the s and t sets form a bipartite graph g (described in section 3), with their in-between edge weights reflecting word similarity. in the second stage, we pass the constructed g as input to the trained gcn which outputs an approximate rlap solution, in the form of a list of candidate word pairs. each word pair, consists of the source word s @xmath10. in the third and final stage, we harness beam search to define the final changes. beam search uses a heuristic function to choose the most suitable substitutions from those returned by the gnn. the selected words from s are then substituted with their respective pair from t , producing a counterfactual dataset d*. ## mixedbread-ai/mxbai-embed-large-v1 figure 2 : the pipeline of our method. in the first stage, we construct a bipartite graph using words as nodes, and in the second stage we utilize a gnn to get feasible substitutions that approximately solve the rlap. in the final stage, we use beam search to change appropriate words of the original dataset, thus getting a new counterfactual dataset. ## experiments in this section, we present our experiments along with the results, which showcase that our framework produces fluent, minimal edits with high labelflipping percentage in a short amount of time compared to the other editors. all experiments were run on the same system consisting of a 16 gb gpu, an intel i7 cpu and 16 gb ram. ## conclusion in this work, we present a framework for generating optimal and controllable word-level counterfactuals via graph-based substitutions, which we evaluate on two classification tasks. we introduce a gnn approach that enhances our proposed baseline deterministic graph assignment algorithm and significantly speeds up the process overall. we compare our results with two sota editors, and show that we surpass them in most metrics, while being considerably faster. as future work, we consider integrating more external lexical sources (e.g. conceptnet) to enhance the possible substitution candidates, as well as improving the performance of the gnn model used to solve rlap to further approximate deterministic optimal solutions. other future directions include comparison with llm-based counterfactual editors and evaluation on other nlp tasks apart from classification.