Graph-based event schema induction in open-domain corpus

Word extraction

Word extraction is divided into three steps: (1) utilizing dependency parser and named reality body recognition to obtain candidate word sets; (2) filtering word sets based on salience formula; (3) word sense disambiguation (WSD).

Graph builder

To enhance the effectiveness of clustering models, more features are usually required. We find a rich graph-based event feature that can be extracted using external knowledge sources (Fan et al., 2022). In this section we describe how we construct the features of the graph.

We transform each {w_v, w_e1, w_e2, …} set into a subgraph G_i. Each word corresponds to a node. Edges (w_v, w_e) connecting predicate verbs w_v with entity nouns w_e, indicating the association between the predicate verb and the entity noun.

We process all subgraphs G_i as input and generate a graph G using Algorithm 1 . The first step of the algorithm is to concatenate all subgraphs. We iterate over each node in the subgraph set {G₁, G₂, …, G_n} and store the nodes as keys in the dictionary. The corresponding values are lists that store the sentence IDs where the key node appears. Then, we use a list to store all the edges.

 
__________________________ 
Algorithm 1 : Graph Builder._____________________________________________________________________________ 
Input: Subgraph list [G1,G2,...,Gn], Gi = [nodesi,linksi]; 
     where nodesi is a list, contains predicate verb and entity nouns of sentence Si, linksi is a lists, each 
     element consists of two node ids, indicating that there is a correlation between the two; 
 1:  G ← ϕ; 
 2:  nodes ← ϕ;   // A hashmap, key is str, value is list. 
 3:  links ← ϕ;   // A list. 
 4:  // Step1. Concat all subgraphs 
 5:  for i ← 0 to n ∈ do 
 6:     for j ← 0 to Len(Gi[0]) do 
 7:        node = Gi[0]j; 
 8:        if node not in nodes then 
 9:           nodes ← Put(node, [i]); 
10:        else 
11:           nodes ← Append(links,Gi[1]); 
12:        end if 
13:     end for 
14:     links ← Append(links,Gi[1]) 
15:  end for 
16:  // Step2. Query and link concept node by ConceptNet WebAPI 
17:  for i ← 0 to Len(nodes) do 
18:     node,sentIds = Entry(nodesi); 
19:     edges = Query(node);    // request WebAPI. 
20:     for j ← 0 to Len(edges) do 
21:        conceptNode = edgesi[end]; 
22:        if conceptNode not in nodes then 
23:           nodes ← PutIfAbsent(conceptNode); 
24:           links ← Append([node,conceptNode]); 
25:        end if 
26:     end for 
27:  end for 
28:  G = [nodes,links] 
Return:  G;_________________________________________________________________________________________________________________________    

The second step of the algorithm is to iterate the previous nodes. Each node serves as a query keyword to request responses from the ConceptNet WebAPI. The responses from the API provide the edges associated with the current node in ConceptNet. These edges contain information about related words and their relationships with the current node. The official documentation of ConceptNet WebAPI (https://github.com/commonsense/conceptnet5/wiki/Relations) includes 34 types of relationships. We exclude unreasonable associations, such as “ExternalURL” and “Antonym”. We iterate over these edges, extract the associated words (concept words), add them to the set, and append their corresponding edges to the list.

Finally, we merge all nodes and links to form the result G.

Text encoder

To extract features for each word w (predicate verb w_v or entity noun w_e), the most basic method is to encode the text. Two distinct features can be computed: contextual and semantic features: (1) Contextual feature refers to the information surrounding a particular word or sequence of words within a text. (2) Semantic feature denotes the meaning attributes associated with a specific word. We computed semantic features to represent the meaning, as words may have different senses. Finally, these contextual and semantic features are aggregated to form the textual feature representation for the word.

For the textual feature. Firstly, we locate the word w in the corpus. During the graph building, each node records the sentences in which the current word appears. Next, we identify the position of the word w in the token sequence of each sentence. We extract the M tokens before and after the word w as the context. We input the context token sequence into BERT and take the CLS token as the contextual feature ${\mathbf{h}}_{w,i}^{ctx}$ for word w in the ith sentence.

For the semantic feature. Firstly, vectorize the interpretation of each word in the sense dictionary. and then input it into BERT, taking CLS as the semantic features ${\mathbf{h}}_w^{ses}$.

Finally, we average all the contextual features of word w to obtain ${\mathbf{h}}_w^{txt}$: ${\displaystyle {\mathbf{h}}_w^{txt}=\left[{\mathbf{h}}_{w,i}^{ses};{\mathbf{h}}_w^{ctx}\right].}$

Graph autoencoder

This section will explain how to use an unsupervised graph neural network model to encode structural features for each node in the graph G. We use the Graph Autoencoder model for unsupervised graph representation learning. Figure 3 shows that graph autoencoder consists of an encoder and a decoder. The encoder learns hidden representations h_t of nodes from the raw graph data while the decoder reconstructs the original graph structure from the hidden representations h_t: ${\displaystyle {\mathbf{h}}_t=\tilde{A}\mathbf{RELU}\left(\tilde{A}X{W}^0\right)W^1}$ where the adjacency matrix A and the feature matrix X are the inputs to the model. h_t ∈ ℝ^N×d, N is the number of nodes. d is the dimension. $\tilde{A}=D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}$ represents the symmetrically normalized adjacency matrix. And W⁰ and W¹ are the GCN parameters that need to be learned. For the adjacency matrix A, we can obtain it directly from the graph G.

For the feature matrix X, we use ${\mathbf{H}}_w^{txt}$ obtained from the text encoder as the feature X_i.

For the concept w_c without ${\mathbf{H}}_w^{txt}$, we use a context replacement method. We randomly sample a neighboring node of the concept word w_p. Then, we replace the instance word w_p in sentence S_p = {w₁, w₂, …, w_p, …, w_n} with the concept word w_c to generate a pseudo-sentence $S_c^{\prime }=\left\{w_1,w_2,\dots ,w_c,\dots ,w_n\right\}$. This pseudo-sentence is regarded as the context for the concept word w_p. Finally, the pseudo-sentence and the concept word are fed into the text encoder, and the resulting output is used as the feature X_i.

Then, the decoder reconstructs the adjacency matrix through the inner product of the embedding vectors $\hat{A}$: ${\displaystyle \hat{A}=\sigma \left({\mathbf{h}}_t{\mathbf{h}}_t^T\right).}$ In Graph Autoencoder, our goal is to optimize the parameters W⁰ and W¹ of the encoder to reconstruct the adjacency matrix $\hat{A}$ using the decoder, aiming to make it as similar as possible to the original adjacency matrix A. Since the adjacency matrix determines the graph’s structure, the closer the reconstructed adjacency matrix, based on the node embedding vectors, is to the original adjacency matrix, the better the node embedding vectors represent the graph structure.

The loss function of Graph Autoencoder is defined as follows: ${\displaystyle {\mathcal{L}}_G=-\frac{1}{N}\sum \left(ylog\hat{y}+\left(1-y\right)log\left(1-\hat{y}\right)\right)}$ where y denotes an element in the original adjacency matrix A, taking values of 0 or 1. A value of 1 indicates the presence of an edge between nodes, whereas 0 indicates its absence. $\hat{y}$ denotes an element within the reconstructed adjacency matrix $\hat{A}$. By minimizing the cross-entropy loss between the reconstructed adjacency matrix and the original adjacency matrix, the Graph Autoencoder model can learn hidden node representations that preserve the structural information of the graph. We utilize this model to learn node representations in the context of the graph.

Clustering

The goal of this section is to cluster the word set {w_v, w_e1, w_e2, …} as a clustering unit. The feature representations required for word sets are categorized into three types, namely verb textual features h_v, entity noun textual feature h_e and structural features h_t.

To cluster the three types of features, it is not feasible to simply aggregate them as [h_v; h_e; h_t]. We need to unify all the features into the same vector space. To achieve this, we adopted a Latent Space Generative Model (Shen et al., 2021), which can unify two feature spaces and guide the clustering process based on the clustering objective. The clustering process can benefit from the well-separated structure in the latent space, resulting in mutual reinforcement. We modified this network model to handle the three types of features.

The model has two objective functions. The first objective is the reconstruct objective ${\mathcal{O}}_{\text{rec}}$ so that the model retains as much of the semantics of the input space as possible: ${\displaystyle {\mathcal{O}}_{\text{rec}}=\sum _{i=1}^N\left(\right.cos\left({\mathbf{h}}_{v_i},g_v\left(f_v\left({\mathbf{h}}_{v_i}\right)\right)\right)+cos\left({\mathbf{h}}_{e_i},g_e\left(f_e\left({\mathbf{h}}_{e_i}\right)\right)\right)+cos\left({\mathbf{h}}_{t_i},g_t\left(f_t\left({\mathbf{h}}_{t_i}\right)\right)\right)\left)\right.}$ where N denotes the number of cluster units. g_v, g_e, g_t denotes the deep neural network. Joint learning mapping functions f_v:h_v → Z, f_e:h_e → Z and f_t:h_t → Z.Z is the vector space. The second objective is the clustering-promoting objective ${\mathcal{O}}_{\text{clus}}$. Assumes the existence of a spherical potential space with K clusters. Each cluster in this space corresponds to the same events and is associated with a von Mises-Fisher (vMF) distribution (Banerjee et al., 2005).

The vMF distribution of the event cluster is determined by the mean vector c, and the goal of the model is to learn the latent space with K well-separated cluster structures. Specifically, an expectation–maximization algorithm p(⋅) is used to sharpen the posterior distribution of each word set. The cluster soft assignment q(⋅) for each word set is computed and used to update the model during the maximization step. So the clustering objective function ${\mathcal{O}}_{\text{clus}}$ can be obtained as follows: ${\displaystyle {\mathcal{O}}_{\text{clus}}=\sum _{i=1}^N\sum _{k=1}^{K}q\left(c_k|{\mathbf{z}}_i\right)logp\left(c_k|{\mathbf{z}}_i\right)}$ where N is the number of word sets, K is the number of clusters. c_k is sampled from the joint distribution and the implicit vector z_i is generated from the vMF distribution. We first train the model during training using only the first objective function. Then, we jointly train the model using all the objective functions $\mathcal{O}$: ${\displaystyle \mathcal{O}={\mathcal{O}}_{\text{rec}}+\lambda {\mathcal{O}}_{\text{clus}}}$ where the hyperparameter λ is used to balance the two objective functions. After clustering with this model, we obtain k clusters. We keep each group’s top m cluster elements, and each cluster element is mapped back to the original set {w_v, w_e1, w_e2, …} for event schema induction.

Conceptualization

To conceptualize clusters and generate event schemas, traditional methods manually cause possible slots from clustered event mentions or simply divide slots into Person, Org, Physical Object, or Other and then classify entity words. The disadvantage is the high cost associated with manual construction.

As the scale of models and corpus expands, large language models like GPT-3 are trained on amounts of internet text data. They predict and generate the next token based on a given context. The combination of large datasets and high-parameter language models has produced compelling language models and developed a new ability known as in-context learning (Min et al., 2022), which has become a new paradigm in natural language processing. Excellent results can be achieved by demonstrating examples composed of a few contexts.

So, to conceptualize each cluster into a corresponding event schema, we use in-context learning to model conceptualization as an in-context generation process.

Specifically, we design a prompt as shown in Table 1. The “Example” section includes five event sentences describing the Bombing event, the event type, and slots. For each slot, a set of words is appended to indicate the specific entities referred to by that slot in the sentences above. The sentences provided in the “Target” section are the sentences to be induced. We assume that each cluster contains only one event type, so in the “Target” section, we require it to generate one event schema at a time. In this process, the granularity of event schemas depends on the clustering algorithm and parameters used. Fine-grained settings may generate event schemas corresponding to specific event types, while coarse-grained settings may generate more general event schemas.

Datasets and evaluation metric

Experimental setting

Our model comprises six main components: (1) Word Extraction: We use the en_core_web_lg model from spaCy 3.5 for dependency parsing and named entity recognition, and then utilize a verb sense dictionary based on OntoNotes sense grouping to filter irrelevant meanings and disambiguation. This dictionary is based on OntoNotes sense grouping. (2) Graph builder: We employ the WebAPI of ConceptNet, an external knowledge base, to establish word connections. (3) Text encoder: We adopt the bert-base-uncased model from BERT to encode the original text. (4) Graph encoder: We employ Graph Autoencoder, an unsupervised graph embedding learning model, with the input dimensions of the first GCN layer set to 512 and the second layer to 256. The learning rate is set to 0.001, and the training epoch is set to 250. (5) Clustering model: We utilize the Latent Space Generative Model for feature unification and clustering. The dimension parameters are set to 1000-2000-1000-100, and the aggregation strategy is based on the product method. (6) Conceptualization: We utilize the API provided by Claude to access its model, which is a large-scale PLM similar to GPT-3.

Baselines

We validate the effectiveness of our proposed GESI using the following baselines. (1) Triframes (Ustalov et al., 2018): A graph-based clustering algorithm that constructs a k-NN event mention graph and uses a fuzzy graph clustering algorithm WATSET (Ustalov et al., 2019) to generate the clusters. (2) Joint constrained spectral clustering (JCSC) (Huang et al., 2016): A joint constrained spectral clustering method that iteratively refines the clustering result with a constraint function to enforce inter-dependent predicates and objects to have coherent clusters. (3) ETypeClus (Shen et al., 2021): A latent space joint embedding and clustering algorithm.

Results of event mention clustering

Tables 2 and 3 present our model’s comparative clustering evaluation results and the baseline model on the ACE 2005 and MAVEN-ERE event datasets, respectively. All values are expressed in percentages. We conducted each method ten times, presenting the final results as the average and standard deviation for each metric. Please note that the ACC metric does not apply to Triframes as it assumes an equal number of predicted and ground truth results in clusters.

The comparative results indicate that, on the ACE 2005 dataset, compared to the best-performing model, GESI achieved improvements of 13.3%, 4.45%, 1.66%, and 7.12% in ARI, NMI, ACC, and BCubed-F1, respectively. On the MAVEN-ERE dataset, compared to the best-performing model, GESI demonstrated improvements of 7.99%, 6.72%, 2.59%, and 5.4% in ARI, NMI, ACC, and BCubed-F1, respectively.

Ablation study of event mention clustering

To further verify the effectiveness of filtering, disambiguation, and graph autoencoders in the event induction task, we conducted ablation experiments on the datasets ACE 2005 and MAVEN-ERE with the complete model and several variants to better understand their relative importance.

• w/o h_t: Removing the graph autoencoder model means that graph structure embedding features are not generated, only text embedding features of predicates and entity nouns.

• w/o Filter: Removing the filter means that the significance of the extracted words will not be considered, and the quality of the words may vary.

• w/o WSD: Removing the word sense disambiguation model means that the polysemy problem of predicate verbs will not be considered, and polysemous words will be clustered as the same word.

During a series of experiments, removing a certain part and keeping the rest unchanged, the following observations can be drawn from Tables 4 and 5.

• As can be seen from the absolute percentages of the different model evaluation metrics in Tables 4 and 5, the highest scores are for the complete GESI model. Removing any component of the model results in a decrease in performance, which confirms that the inclusion of graph autoencoders, filtering, and disambiguation can all improve the clustering ability of the model.

• From the relative changes of the different variants of the model, it can be seen that the largest performance degradation is in w/o  h_t. This indicates that the structural features generated by the graph autoencoder have a greater effect on model enhancement.

• From the comparison of each variant model with the complete GESI model, it can be seen that the w/o Filter variant model performs better than the w/o WSD variant model on the ACE 2005 dataset, and the opposite is true on the MAVEN-ERE dataset, suggesting that filtering is more important than disambiguation in the presence of large data sizes.

• In terms of the performance of the model on different datasets, for example, the variant model w/o h_t, ARI, NMI, ACC, and BCubed-F1 decreased by about 4%, 5.03%, 3.31%, 5.74% on ACE 2005 dataset. And on MAVEN-ERE dataset, ARI, NMI, ACC, and BCubed- F1 decreased by about 10.88%, 6.63%, 7.52%, and 6.77% respectively, after removing the graph autoencoder, of which ARI decreased more significantly. Compared with the ACE 2005 dataset, ARI decreased more than other metrics, indicating that the graph autoencoder significantly improved ARI for larger datasets.

In summary, each component of the model in this article contributes to the final results, with slight variations in the performance of different components in different datasets, but overall a positive effect enhancement, especially for the structural information generated by the graph autocoder.

Results of event schema induction

In Tables 6 and 7, we present sample of the results of our model’s event schema induction. Our model successfully identifies the most true event schemas and produces highly accurate slots and detailed entity participants. It correctly identifies most real event schemas, such as Arrest and Conflict, and also identifies event types that are not explicitly labeled in the dataset, such as Aid and Space Exploration. This indicates that our model is highly effective and reliable. These results make our model well-suited for open-domain event schema induction research and its subsequent downstream applications.

Table 8 illustrates the performance of event schema induction. We observed that in the ACE 2005 dataset, GESI covered 18.31% of event types, with almost all uncovered event types being deemed acceptable (80.14%). However, for event slots, only 7.13% were covered, potentially due to the diversity and sparsity of event slots. In the MAVEN-ERE dataset, we observed that the model performs better, likely attributed to the larger scale of the MAVEN-ERE data, which reduced the sparsity of the data. We also conducted experiments on clusters generated by the ETypeClus method. The experimental results show that the method with better clustering performs better in event schema induction.