Mohit Bansal Abstract Pre-trained sequence-to-sequence language models have led to widespread success in many natural language generation tasks. However, there has been relatively less work on analyzing their ability to generate structured outputs such as graphs. Unlike natural language, graphs have distinct structural and semantic properties in the context of a downstream NLP task, e.g., generating a graph that is connected and acyclic can be attributed to its structural constraints, while the semantics of a graph can refer to how meaningfully an edge represents the relation between two node concepts. In this work, we study pre-trained language models that generate explanation graphs in an end-to-end manner and analyze their ability to learn the structural constraints and semantics of such graphs. We first show that with limited supervision, pre-trained language models often generate graphs that either violate these constraints or are semantically incoherent. Since curating large amount of human-annotated graphs is expensive and tedious, we propose simple yet effective ways of graph perturbations via node and edge edit operations that lead to structurally and semantically positive and negative graphs. Next, we leverage these graphs in different contrastive learning models with Max-Margin and InfoNCE losses. Our methods lead to significant improvements in both structural and semantic accuracy of explanation graphs and also generalize to other similar graph generation tasks. Lastly, we show that human errors are the best negatives for contrastive learning and also that automatically generating more such human-like negative graphs can lead to further improvements. 1 1 Introduction Pre-trained sequence-to-sequence language models (PLMs) like BART (Lewis et al., 2020) and 1 Our code and models are publicly available at https: //github.com/swarnaHub/ExplagraphGen . T5 (Raffel et al., 2020) have led to significant advances in many natural language generation tasks like text summarization and machine translation. The models are pre-trained on massive amounts of text data with self-supervision, thus enabling them to construct coherent natural language sentences for downstream tasks. This then raises the question whether pre-trained language models, trained on free-form natural language data, can also adapt themselves to generate structured outputs like graphs. Graphs are common in NLP tasks 1190 that involve representing structured knowledge in the form of knowledge bases (Guarino and Gia-retta, 1995), constructing event chains from documents (Chambers and Jurafsky, 2009), or more recent work on encoding reasoning chains, explanations, or deductive proofs (Saha et al., 2020; Tafjord et al., 2021; Dalvi et al., 2021). Graphs differ from free-form natural language. In the context of NLP, natural language graphs (con-sisting of textual nodes and edges) can have distinct structural and semantic properties. For example, consider a recently proposed commonsense explanation graph generation task shown in Fig. 1 (Saha et al., 2021b). Each example shows a belief, an argument and an explanation graph explaining how the argument supports or refutes the belief. These explanation graphs encode structured knowledge (augmented with commonsense) and consist of concepts as nodes and relations from ConceptNet (Liu and Singh, 2004) as edges. For example, the second graph encodes the knowledge that both salads and fast food are part of mcdonalds and hence mcdonalds is not greasy and fattening, thus explicitly refuting the belief. From prior work, the structural constraints enforce the graphs to be connected directed acyclic and the nodes to contain at least two concepts from the belief and two from the argument. The semantic aspect deals with commonsense and evaluates whether each edge expresses coherent relational knowledge and if the whole graph explains the stance. Following Saha et al. (2021b), we represent graphs as strings composed of concatenated edges and fine-tune T5 to generate graphs in an autoregressive manner. We observe that while moderate amount of supervision enables the model to learn valid graph encodings, the graphs frequently violate task-specific structural constraints (like con-nectivity). For instance, the first example in Fig. 1 shows a graph generated by T5 that is disconnected and hence structurally incorrect. Moreover, for the fraction of graphs that are structurally correct, the model also makes commonsense mistakes, a type of semantic error, by inferring wrong or incoherent relations between concepts. Both T5-generated graphs shown in Fig. 1 contain incoherent or non-commonsensical edges (marked by dashed arrows) like fast food; has context; salads. Based on these observations, we study PLMs that generate explanation graphs in an end-to-end manner and analyze their ability to learn the structural constraints as well as the semantics of such graphs. While a general recipe towards improving the structural and semantic aspects of graph generation can be via large-scale training with more human-annotated graphs, it is prohibitive under most practical scenarios because of the cognitive load associated with a complex data creation task like graph annotation (Dalvi et al., 2021; Saha et al., 2021b). Hence, we propose simple yet effective methods of graph perturbations that perform various kinds of node and edge addition, deletion, and replacement operations to construct structurally and semantically positive (correct) and negative (incor-rect) graphs. Overall, we leverage three types of negative graphs (synthetic structural, synthetic semantic, and human-created semantic) and develop multiple contrastive learning models (Hjelm et al., 2018; Chen et al., 2020a; Khosla et al., 2020; Gunel et al., 2020) for effectively distinguishing between correct and incorrect graphs. Our first method is a Generate-and-Refine model that first generates an initial graph and further refines it using another T5 model. Next, we propose two improved models  one that uses the negative graphs in a max-margin formulation and another that uses both positive and negative graphs with a InfoNCE (van den Oord et al., 2018) contrastive loss. On two real-world tasks of explanation graph generation and temporal graph generation, with varied node and edge semantics, we observe that our proposed methods and graph perturbation techniques generalize well and lead to improvements in both structural and semantic accuracy of graphs. Further analysis of different types of negative graphs reveal that the human-error graphs are the hardest, most diverse, and hence the best type of negatives to learn from in contrastive learning. Hence, we also develop methods to automatically generate more such human-like semantic negative graphs, which leads to further improvements. We summarize our contributions as follows. We present a detailed analysis of graph structure and semantics for end-to-end explanation graph generation via pre-trained language models. We propose simple yet effective graph perturbation techniques for constructing positive and negative graphs and use them in different graph contrastive learning models. Our methods lead to significant improvements in both structural and semantic accuracy of explanation graphs and also generalize to other similar graph generation tasks. Graph Generation from Language Models. Representative works on graph generation from language models include knowledge graph completion models like Comet (Bosselut et al., 2019; Hwang et al., 2021) that fine-tune GPT (Radford et al., 2019; Brown et al., 2020) and BART (Lewis et al., 2020), generation of event influence graphs (Tan-don et al., 2019; Madaan et al., 2020), partially ordered scripts (Sakaguchi et al., 2021), temporal graphs (Madaan and Yang, 2021), entailment trees (Dalvi et al., 2021), proof graphs (Saha et al., 2020; Tafjord et al., 2021; Saha et al., 2021a) and commonsense explanation graphs (Saha et al., 2021b). Linguistic tasks like syntactic parsing (Zhou et al., 2020; Mohammadshahi and Henderson, 2021; Kondratyuk and Straka, 2019) and semantic parsing (Chen et al., 2020b; Shin et al., 2021) have also made use of language models. There is also a large body of work on building generative models for learning unconditional graph distributions (You et al., 2018; Simonovsky and Komodakis, 2018; Grover et al., 2019; Liao et al., 2019; Shi* et al., 2020) without any semantics attached to the graphs. Our novelty lies in presenting the first systematic analysis of structure and semantics of graph generation for two downstream NLP tasks using pre-trained language models and improving them via constrastive learning. Data Augmentation and Contrastive Learning. Data Augmentation for NLP (Hedderich et al., 2020; Feng et al., 2021; Chen et al., 2021) has been a powerful tool in low-data settings, ranging from its early usages with synonym replacement (Kolomiyets et al., 2011; Wang and Yang, 2015) to more recent methods of perturbing hidden representations (Miyato et al., 2016; Shen et al., 2020). Contrastive learning, beyond its historical use in learning robust image representations (Chopra et al., 2005; Hadsell et al., 2006; Gutmann and Hyvri-nen, 2010; Hoffer and Ailon, 2015; Hjelm et al., 2018; Chen et al., 2020a; He et al., 2020) has been explored in supervised scenarios (Khosla et al., 2020; Gunel et al., 2020) and for NLP, in training self-supervised language models (Fang et al., 2020), learning sentence representations (Gao et al., 2021), document clustering (Zhang et al., 2021), summarization (Liu and Liu, 2021; Cao and Wang, 2021) and generic text generation (Lee et al., 2020). It has also been used in unconditional graph representation learning (You et al., 2020; Hassani and Khasahmadi, 2020; Zhu et al., 2021). We follow this rich line of work to explore their applicability in supervised graph generation tasks from pre-trained language models in low-resource settings. Generative Commonsense Reasoning. While traditional commonsense reasoning tasks are discriminative in nature (Zellers et al., 2018; Talmor et al., 2019; Sap et al., 2019; Bisk et al., 2020; Sakaguchi et al., 2020; Talmor et al., 2021), recent focus on generative evaluation have led to the development of tasks and benchmarks that explore unstructured commonsense sentence generation (Lin et al., 2020), event influence graph generation (Madaan et al., 2020), commonsense explanation graph generation (Saha et al., 2021b), etc. We experiment with two graph generation tasks, primarily focusing on ExplaGraphs (Saha et al., 2021b) because of the clear distinction in the underlying structural constraints and the semantic aspect dealing with commonsense. Our primary task of interest is a recently proposed commonsense explanation graph generation task called ExplaGraphs (Saha et al., 2021b). In Sec. 6.4, we also experiment with another related task of temporal graph generation (Madaan et al., 2020). In both these tasks, the structural aspect deals with satisfying certain task-specific constraints on the graph (like connectivity) and the semantic aspect deals with the construction of meaningful edges (that adhere to commonsense). Below we discuss ExplaGraphs briefly and analyze pre-trained language models for their ability to generate explanation graphs. ExplaGraphs (Saha et al., 2021b). In this task, given a belief and an argument, an agent has to perform two sub-tasks  predict the stance (sup-port/counter) and also generate an explanation graph explaining the stance. Explanation graphs are structured explanations that capture explicit reasoning chains between the belief and the argument, thereby making models more interpretable. Formally, an explanation graph is a connected DAG with nodes as concepts and edges as commonsense relations between two concepts (See Fig. 1). The concepts are either part of the belief or the argument (represented with solid boxes) or any external commonsense phrase (represented with dashed boxes). Each edge in the graph forms a coherent sentence and the graph, when read as a whole, 1192 forms reasoning structures explaining why the argument supports or refutes the belief. Saha et al. (2021b) evaluate explanation graphs by defining two accuracy metrics  (1) Structural Correctness Accuracy (StCA) : Fraction of graphs that satisfy all structural constraints, and (2) Semantic Correctness Accuracy (SeCA) : Fraction of graphs that are both structurally and semantically correct. A graph is considered structurally correct if it satisfies the following constraints: (1) it is connected, (2) it is a DAG, (3) the edge relations belong to a pre-defined list, (4) there are at least two concepts from the belief and two from the argument. If all these constraints are satisfied, the graph is next evaluated for semantic correctness by a model-based metric (Saha et al., 2021b). It works on the principle that an explanation graph is semantically correct if the stance inferred from the belief and the graph matches the gold stance. Refer to Appendix A for a detailed description of all evaluation metrics. Baseline T5 Model. Following prior work (Saha et al., 2021b), we generate explanation graphs as post-hoc explanations by conditioning on the belief, argument and the predicted stance. 2 The stance prediction model is a fine-tuned RoBERTa model (Liu et al., 2019) which we keep unaltered from prior work and focus on the graph generation sub-task. We generate graphs as linearized strings in an end-to-end manner by leveraging an encoder-decoder pre-trained language model, T5 (Raffel et al., 2020). The input to the model is the concatenated belief, argument and the stance along with a prefix Gen-erate an Explanation Graph for . The graphs are encoded as concatenated bracketed edges, in which the edges are ordered according to the Depth First Search (DFS) order of the nodes. While we choose T5 because of its superior performance (Saha et al., 2021b), we do not make any model-specific assumptions and graphs can be generated via any encoder-decoder style pre-trained language model (e.g., see Appendix E for results with BART). Analysis of T5 Baseline. We analyze the quality of the explanation graphs generated by T5 in Table 1. We vary the amount of training data from 500 to 2368 samples (all) and report StCA and SeCA along with other metrics like Graph-BertScore (G-BS) introduced in prior work (Saha et al., 2021b). While the structural accuracy improves with increase in training data, the gain saturates quickly and even after training on the entire data, we find a significant fraction of graphs to violate the structural constraints. We note that a high 91% of T5's generations are valid graph encodings i.e., the generated strings can be parsed into graphical structures (without any post-processing), suggesting that T5 is able to learn the graph encoding from a fairly small amount of supervision. However, it fails to satisfy the various structural constraints  (1) 20% of the graphs are disconnected, (2) 6% of the graphs contain cycles, and (3) 14% of the graphs have less than two concepts from the belief or from the argument. Note that these constraints are not encoded in the model, thus making them fairly hard to learn from limited supervision. On the fraction of structurally correct graphs, the model makes further semantic errors and a lower SeCA of 35% demonstrates that. In Fig. 1, we show examples of structurally incorrect and semantically incorrect graphs generated by T5. Overall, these results indicate that there is a significant scope for improvement both on graph structure and semantics, thus motivating us to develop methods with design choices aimed at improving both aspects. Most prior works that collect human-annotated graphs for a downstream NLP task have found such collection processes to be quite expensive and tedious (Tandon et al., 2019; Dalvi et al., 2021; Saha et al., 2021b). For instance, Saha et al. (2021b) obtained high-quality data only after multiple rounds of refinement and Dalvi et al. (2021) employ trained expert annotators for entailment tree construction. The corresponding datasets are also relatively small in size (2-3k), thus limiting the prospect of large-scale training. Hence, our approach towards improving explanation graph generation is through data augmentation techniques that perturb human-curated graphs to construct positive and negative graphs. As noted earlier, we wish to construct graphs that enable better learning of 1193 "Generate an Explanation graph for Belief: Banning whaling is humane. [SEP] Argument: Banning whaling would harm the workforce, which would be an inhumane act for the people. [SEP] Stance: Counter " T5 Positive Negatives G o l d G r a ph harm the workforce loss of jobs banningwhaling capable of causes humane is not a S y n t h e t i c P o s i t i ve G r a ph harm the workforce going of business banningwhaling capable of causes humane is not a S y n t h e t i c S e m a n t i c ( S y S e ) harm the workforce loss of jobs banningwhaling antonym of causes humane is a H u m a n S e m a n t i c ( H u S e ) occupation workforce whaling part of used for inhumane has property banning not desires S y n t h e t i c S t r u c t u r a l ( S y S t) harm the workforce loss of jobs banningwhaling capable of humane is not a , , Figure 2: Our T5-based contrastive learning framework for graph generation using positively and three kinds of negatively perturbed graphs. One simple method to augment existing training data is to create synthetic positive graphs. These graphs should be created such that all the task-specific constraints continue to hold upon perturbations. E.g., removing a node that makes the graph disconnected is a prohibitive action. Hence, we choose nodes (concepts) that are not part of the belief or the argument (also termed as commonsense nodes) and replace them with phrases that are synonymous to the original phrases. To do so, we select words from the concept with POS tags of Adjective, Noun, Adverb, or Verb and replace them with that synonym from Wordnet (Miller, 1995) for which the cosine similarity of their word2vec representations (Mikolov et al., 2013) is the highest. 3 Fig. 2 shows an example of a positive graph perturbation where the node loss of jobs is replaced with going of business. Note that our node replacement operations will always lead to structurally similar graphs. Automatically constructing structurally diverse positive graphs is a challenging problem and we leave that for future work. In order to enable the model to learn from explicit hard negatives, we construct three diverse types of graphs  synthetically constructed structural negatives for learning graph constraints and synthetic 3 We also tried similar replacement operations with antonyms. However, they often lead to semantically inconsistent graphs. E.g., A causes B does not always imply A not causes not B or not A not causes not B. and human-created semantic negatives to capture a fairly large space of semantically incorrect graphs. Below we discuss the construction of these graphs. Synthetic & Structurally Negative Graphs (SySt). As shown previously, one common source of errors in the generated explanation graphs is the violation of structural constraints. To enable learning these constraints, we generate four types of negative graphs by performing the following perturbations on each ground-truth graph: (1) removing an edge at random such that the resultant graph becomes disconnected, (2) adding an edge between two randomly chosen nodes such that the resultant graph becomes cyclic, (3) adding and removing one edge at random such that the resultant graph becomes both disconnected and cyclic, (4) removing a node randomly such that the resultant graph contains less than two concepts from the belief or argument. Fig. 2 shows an example of a disconnected graph created as part of the structurally negative graphs. Synthetic & Semantic Negative Graphs (SySe). We also construct semantically incorrect negative explanation graphs. While the previous category of negative graphs (SySt) captures structural constraints, SySe captures the relational knowledge in graphs. Semantic incorrectness typically arises from inappropriate relations that do not adhere to human commonsense (loss of jobs; is a; humane). We create such negative graphs by selecting a random number of edges and then replacing the relations with some other relations. Fig. 2 shows a semantic negative graph in which the relations marked with dashed lines are perturbed. Human-created & Semantic Negative Graphs (HuSe). The space of semantically incorrect graphs is fairly large and in order to augment our synthetic negative graphs with harder structurally-diverse negatives, we make use of human-created incorrect graphs from prior work (Saha et al., 2021b). 4 Humans make subtle errors, thus making them ideal negative candidates for contrastive learning. ExplaGraphs was constructed via an iterative framework in which the graphs are iteratively refined (up to two times) until they are verified as correct. We treat these refined graphs as negatives. Specifically, in two rounds, if an initial graph G 1 4 Publicly released by Saha et al. (2021b) at https: //github.com/swarnaHub/ExplaGraphs/blob/main/data/refinement_graphs_train.tsv . is refined into graphs G 2 and G 3 successively, then G 1 and G 2 are considered as negative graphs. Unlike SySe which only perturb the relations, these negatives are structurally diverse (see Fig. 2) and capture semantics not just at the level of each edge but for the graph as a whole (e.g., a graph might be refined because it does not explain the stance). Note that human-created graphs can only be semantically incorrect, since their structural correctness is already ensured during construction. Next we propose different methods of leveraging these positive and negative graphs for explanation graph generation. Our models either use only positive graphs as simple data augmentation, only negative graphs in a max-margin model, or both in a Generate & Refine model and a Contrastive model. In this first simple approach, we augment the training data with the synthetically created positive graphs and retrain the baseline T5 model. Our next model leverages the negatively perturbed graphs in a max-margin formulation. During training, given a (belief, argument, stance) context x , a ground truth graph G ( g ) and a negative graph G ( n ) , linearized into a sequence of words { y ( g ) i } ki =1 and { y ( n ) i } li =1 respectively, we define the loss function L as a linear combination of the standard cross-entropy loss LCE and a max-margin loss LMM , defined between a word y ( g ) i of the positive graph and a word y ( n ) i of the negative graph. LCE = (cid:88) i  logP  ( y ( g ) i | y ( g ) <i , x ) LMM = (cid:88) i max(0 , logP  ( y ( g ) i | y ( g ) <i , x )  log P  ( y ( n ) i | y ( n ) <i , x ) +  ) L = LCE +  LMM where  and  (margin) are hyperparameters. As noted earlier, the baseline model often makes commonsense mistakes in distinguishing between positive and negative relations (causes vs not causes) and our relation perturbing negative graphs and the max-margin loss component facilitate learning a better boundary between them. ExplaGraphs was constructed using a Refinement phase wherein the initially constructed graphs that are marked incorrect by human verifiers are further refined by another set of annotators. Here we emulate the graph refinement phase with the help of a model. Specifically, our approach is a 2-stage pipeline  first, an initial graph is generated by the baseline T5 model and second, an Explanation Graph Refinement model conditions on the initial graph, along with the belief, argument and the stance to refine the graph. The refiner is also a T5 model fine-tuned with the prefix Refine the Explanation Graph for on all positive and negative graphs described in Sec. 4. Note that our approach differs from the actual data collection process in two aspects. Unlike the human-annotated graphs, which are refined only for semantic correctness, the model-generated graphs can be both structurally and semantically incorrect. Second, our approach does not involve a graph verification stage and thus, the refiner model acts on all (correct and incorrect) graphs generated in stage 1 and is thus trained with both correct and incorrect graphs. Our Contrastive Graph Generation Model (Fig. 2) also leverages both positive and negative graphs but instead of doing so in a 2-stage Generate & Refine model, uses a contrastive learning framework (Khosla et al., 2020; Gunel et al., 2020). Given a ground-truth graph G ( g ) , a positive graph G ( p ) and a set of negative graphs {G ( n ) i } Mi =1 , contrastive learning aims to learn the graph representations such that the gold graph's representation is close to that of the synthetic positive graph while being distant from those of the negative graphs. Similar to Cao and Wang (2021), we use the last layer of the decoder in T5 as the representation of each token in the graph and obtain the graph representation by averaging over the constituent token representations. Let the graph representations be denoted by h ( g ) , h ( p ) and { h ( n ) i } Mi =1 . Given H ( g ) = { h ( p ) } (cid:83) { h ( n ) i } Mi =1 , our overall loss combines the cross-entropy loss LCE and the InfoNCE contrastive loss (van den Oord et al., 2018) LCL as shown below. where  and the temperature  are the hyperparameters and sim() denotes the cosine similarity function between the graph representations. In Table 2, we compare the various modeling techniques described in Sec. 5 and their effect on the structural and semantic correctness of the generated graphs. While our primary metrics of interest are Graph Structural Accuracy (StCA) and Semantic Accuracy (SeCA), following prior work (Saha et al., 2021b), we also report Stance Accuracy (SA), Graph-BertScore (G-BS), Graph Edit Distance (GED) and Edge Accuracy (EA). Effect of Model Size and Training Data. The T5-Large model uses the same setup as the T5-Base model experimented with in Saha et al. (2021b). We observe that using a larger T5 model improves StCA by 12% and SeCA by 16%. This finding is in line with other commonsense reasoning tasks (Lourie et al., 2021; Elazar et al., 2021) which also show that fine-tuning a larger language model typically leads to better performance. Together with the results reported in Table 1, we conclude that much of the improvement in explanation graph generation comes from increasing the training data and using a larger model. Given its superior performance, we build our proposed models on T5-large. Results with Generate & Refine Model. The Generate & Refine model (Sec. 5.3) improves all metrics; however the gains are small. Note that this model refines all graphs (correct or not) and can lead to already correct graphs becoming incorrect after refinement. In practice, we observe that most graphs do not change much after refinement which we believe stems from the model's inability to distinguish between correct and incorrect graphs. Effect of Positive Graph Perturbations. On retraining T5 augmented with the positively perturbed graphs (Sec. 5.1), we observe that it obtains significant improvement over T5 and Generate & Refine both in structural and semantic accuracy. Note that, by construction, the positive graphs only differ in the commonsense concepts (not part of the belief or argument) while keeping the structure intact. Hence, the model has more supervision about the semantics of the graphs as opposed to the structural constraints. This is reflected in the larger improvement in SeCA. The positive graphs, being structurally correct, also reinforces the model's belief about structural correlation with correct graphs, thus leading to some improvement in StCA as well. Effect of Negative Graph Perturbations. The Max-Margin model (Sec. 5.2) leverages all structurally and semantically incorrect graphs and obtains up to 6% and 9% improvement in StCA and SeCA respectively over the baseline T5 model. The model implicitly learns the structural constraints through relevant supervision and the margin-based loss enables it to learn a better boundary between correct and incorrect graphs. Similarly, the semantically perturbed graphs improves the model's relation prediction capability between concepts. The Max-Margin model outperforms the Pos Data Aug model because of the former having access to both structural and semantic supervision while the latter is only augmented with structurally similar graphs. Perturbations with Contrastive Learning. The Contrastive Graph Generation model (Sec. 5.4) leverages both positive and negative graphs and improves StCA to 60% with comparable SeCA to the Max-Margin model. The overall improvements in StCA and SeCA are 9% and 8% respectively compared to T5. We hypothesize that the constrastive model does not lead to further improvement in SeCA because of the structurally similar positive 1196 StCA  SeCA  G-BS  GED  EA  T5-Large 46.5 31.6 36.8 0.66 26.7 + SySt 50.2 34.1 40.7 0.64 27.4 + SySe 50.7 35.1 40.8 0.63 27.3 + HuSe 49.5 38.4 39.4 0.64 26.1 Table 3: Ablation study showing the effect of different types of negative graphs on ExplaGraphs dev set. graphs. This can potentially be improved by incorporating more structurally diverse graphs. Finally, our best SeCA is far from perfect and significant future work can be done in improving the graph semantics. Further ablations of negative graphs and human evaluation are done on the Max-Margin model, due to its slightly higher SeCA. Automatically evaluating graphs for semantic correctness is challenging. We conduct human evaluation to further validate our findings. We compare the graphs generated by T5 and our Max-Margin model on Amazon Mechanical Turk where three annotators choose which graph is better or if they are mostly similar (instructions in Appendix F). For fair comparison, we evaluate only those samples where both models predict the correct stance and the graphs are also structurally correct. In fact, this lets us evaluate the semantic aspect in isolation when both graphs are structurally correct. With majority voting on 150 samples, we observe that our Max-Margin model's graphs are preferred 13% more times compared to those of the T5 model (43% vs 30% and statistically significant with p < 0.05) while in 22% cases, the graphs are marked similar (remaining have no majority). In Table 3, we show the effect of different types of negative graphs. We compare the results on the ExplaGraphs validation set by leveraging Synthetic Structural (SySt), Synthetic Semantic (SySe) and Human-created Semantic (HuSe) graphs with the Max-Margin graph generation model. All types of negatives graphs lead to consistent increase in SeCA. Leveraging human-created negative graphs leads to a bigger gain in SeCA because of the hard-Belief: Collectivism is terrible for society. Argument: Collectivism increases empathy. ness and diversity in these graphs and hence are the best candidates for contrastive learning. We test the generalizability of constructing structurally and semantically perturbed graphs for contrastive learning by also experimenting on a temporal graph generation task (Madaan and Yang, 2021) that requires constructing a temporal graph from a document. The nodes in the graph are events from the document and the edges are temporal relations between events (before, after, etc). Following our overall goal of improving graph generation with limited data, we randomly sample 1.3% of the overall corpus (  9.5k samples) as the training data such that all graphs are connected DAGs. Similar to ExplaGraphs, we create structurally negative graphs with disconnected and cyclic graphs and semantic negative graphs by perturbating the temporal relations. E.g., if an edge relation is be-fore, we replace it with after. We construct positive graphs by replacing edges like A before B with B after A (more details in Appendix C). In Table 4, we report structural correctness accuracy (StCA) (percentage of connected DAGs) and Graph-BertScore (G-BS) for measuring approximate semantic correctness wrt gold graphs. We observe that our contrastive model not only generates more valid graph encodings but also improves StCA by 8% and G-BS by 3%. Fig. 3 shows an example of the graphs generated by different models (more examples in Appendix F). Unlike T5, our models' graphs are both structurally and semantically correct with diverse commonsense nodes (Groupthink, Good Thing). While our models generate more correct graphs, they lack in structural diversity  the Contrastive model generates 77% of linear graphs (i.e., the nodes are in a linear chain) which is comparable to 75% in the T5 model. This can be attributed to our structurally similar positive graphs as the model does not obtain enough supervision to generate diverse graphs. Structural diversity is not a measure of graph correctness; however, like diverse text generation (Vijayakumar et al., 2018), generating diverse graphs is an interesting direction for future work. 6.6 Generating Human-like Semantic Negatives (HuSe-Gen) In ExplaGraphs, human-created negatives account for 38% of the samples for which the initially constructed graph was incorrect and was refined. Moreover, we see in the previous section that human-error graphs are the best negative candidates for contrastive learning (which is intuitive since tricky and subtle errors made by expert human annotators would make for some of the hardest nega-tives/distractors for a contrastive learning model to learn from). Hence, in this final section, we further explore whether it is also possible to automatically imitate and generate more of such harder humanlike incorrect graphs for the remaining samples as well. Our method consists of the following steps. Human-like Negative Edge Generation. We first fine-tune a T5 model that conditions on the belief, argument and the stance to generate a set of incorrect edges (which is the set of edges that are present in the incorrect graph and not in the refined graph). Human-like Negative Graph Construction. This generated set of incorrect edges is then added to the correct graph to construct the incorrect graph, such that it is structurally correct and hence representative of human-like erroneous graphs. Filtering High-quality Negative Graphs. Contrastive models will only benefit from these negatives if the negative edge generation model is accurate and generates edges that are actually incorrect. Hence, we control the quality of the generated incorrect graphs by the following two techniques (a) Thresholding via fraction of Acceptable Edges (AE): We say that a generated incorrect edge is acceptable if it is not part of the correct graph and can be added to the correct graph without violating any structural constraints. We compute the fraction of acceptable edges for every generated negative graph and choose only those graphs with AE above a certain threshold  . Intuitively, this ensures that a high fraction of the generated edges are actually incorrect and hence when added to the correct graph, will lead to a sufficiently different (human-like) incorrect graph. (b) Thresholding via Incorrect Probability of a graph (IP): We use our SeCA metric model (that classifies a graph into support, counter, or incorrect class) to compute the probability of the generated graph being incorrect and choose those graphs that are above a certain threshold  of incorrect probability. We set  = 0 . 4 and  = 0 . 5 (tuned on the dev set) and train the Max-margin model using these additionally generated human-like negative graphs. As shown in Table 5 both thresholding approaches lead to further improvements over using just the human-created negative graphs. These initial promising results for emulating hard/tricky human errors as strong negatives for contrastive learning will hopefully lead to further future work in this interesting direction. We presented an empirical study of graph structure and semantics for end-to-end explanation graph generation from pre-trained language models and showed that the generated graphs often violate structural constraints or are semantically incorrect. We significantly improve both the structural and semantic accuracy of graph generation by proposing contrastive learning models that leverage simple yet efficient methods of graph perturbations and also generalize to similar graph generation tasks. From an ethics standpoint, we provide a brief overview and show samples from the datasets that our models are trained on throughout the paper and also in the Appendix. Explanation graph generation improves the interpretability of neural commonsense reasoning systems and could prove to be effective in understanding and debugging such models. Hence we do not foresee any major risks or negative societal impact of our work. However, like any other ML model, the graphs generated by our models may not always be completely accurate and hence should be used with caution for real-world applications. We thank the reviewers for their helpful feedback and the annotators for their time and effort. This work was supported by DARPA MCS Grant N66001-19-2-4031, NSF-CAREER Award 1846185, DARPA YFA17-D17AP00022, ONR Grant N00014-18-1-2871, Microsoft Investigator Fellowship, and Munroe & Rebecca Cobey Fellowship. The views in this article are those of the authors and not the funding agency.
abstain abstain abstain abstain method objective objective abstain result result other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method result abstain abstain abstain method abstain objective abstain objective abstain objective abstain objective objective method objective result other other other other objective other other other other objective other other method abstain method other method other other other other other other other other other other other other method method method other other abstain other method abstain abstain method other other other abstain objective abstain abstain abstain abstain method abstain abstain abstain method method abstain abstain method method abstain abstain abstain abstain abstain abstain method abstain abstain method abstain abstain method abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain method abstain abstain method other abstain abstain abstain abstain abstain abstain abstain method method abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain result abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain result abstain abstain abstain abstain abstain abstain result result result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result objective abstain abstain abstain method other other other