Open Relation and Event Type Discovery with Type Abstraction

Sha Li, Heng Ji, Jiawei Han
University of Illinois Urbana-Champaign
{shal2, hengji, hanj}@illinois.edu


Abstract

Conventional “closed-world" information extraction (IE) approaches rely on human ontologies to define the scope for extraction. As a result, such approaches fall short when applied to new domains. This calls for systems that can automatically infer new types from given corpora, a task which we refer to as type discovery. To tackle this problem, we introduce the idea of type abstraction, where the model is prompted to generalize and name the type. Then we use the similarity between inferred names to induce clusters. Observing that this abstraction-based representation is often complementary to the entity/trigger token representation, we set up these two representations as two views and design our model as a co-training framework. Our experiments on multiple relation extraction and event extraction datasets consistently show the advantage of our type abstraction approach.

1 Introduction↩︎

Information extraction has enjoyed widespread success, however, the majority of information extraction methods are “reactive”, relying on end-users to specify their information needs in prior and provide supervision accordingly. This leads to “closed-world” systems [1][5] that are confined to a set of pre-defined types. It is desirable to make systems act more “proactively” like humans who are always on the lookout for interesting new information, generalize them into new types, and find more instances of such types, even if they are not seen previously.

One related attempt is the Open Information Extraction paradigm [6], which aims at extracting all (subject, predicate, object) triples from text that denote some kind of relation. While OpenIE does not rely on pre-specified relations, its exhaustive and free-form nature often leads to noisy and redundant extractions.

To bridge the gap between closed-world IE and OpenIE, a vital step is for systems to possess the ability of automatically inducing new types and extracting instances of such new types. Under various contexts, related methods have been proposed under the name of “relation discovery” [7], [8],“open relation extraction” [9], [10] and “event type induction” [11], [12]. In this paper, we unify such terms and refer to the task as type discovery.

Figure 1: For each instance, the token view is computed from the pre-trained LM embedding of the first token in entity/trigger. The mask view is computed from the [MASK] token embedding in the type prompt.

Type discovery can naturally be posed as a clustering task. This heavily relies on defining an appropriate metric space where types are easily separable. The token embedding space from pre-trained language models is a popular choice, but as observed by  [13], the original metric space derived from BERT [14] is often prone to reflect surface form similarity rather than the desired relation/event-centered similarity. One way to alleviate this issue is to use known types to help learn a similarity metric that can also be applied to unknown types  [9], [11], [13].

Table 1: Probing \(k\)-NN Accuracy of the token view and the mask view on distinguishing relations without training. We compute \(k\)-NN using cosine similarity of embeddings with \(k=32\) on TACRED [15]. While on average the mask view outperforms the token view, the two views excel at different types.
Relation Mask view Token view \(\Delta\)
website (of org) 0.2424 0.9366 -0.6941
age (of person) 0.2896 0.389 -0.0994
founded_by 0.2734 0.1268 0.1466
employee_of 0.4434 0.2703 0.1731
Avg 0.3678 0.2989 0.0688

In this paper we introduce another idea of abstraction: a discovered type should have an appropriate and concise type name. The human vocabulary serves as a good repository of concepts that appear meaningful to people. When we assign a name to a cluster, we implicitly define the commonality of instances within the cluster and also the criteria for including new instances to the cluster. Since masked language models have the ability to “fill in the blank”, with the help of a type-inducing prompt as shown in Figure 1, we can guide the model to predict a name or indicative word for any relation/event instance. Moreover, since inferring the best name for a cluster from a single instance is a difficult task, we do not require this prediction to be exact: we utilize the similarity between predicted names to perform clustering.

This abstraction-based representation is complementary to the widely-adopted token-based representation of relations/events. We refer to our abstraction-based representation as “mask view” since the embedding for the instance is derived from the [MASK] token. Alternatively, we can also compute a “token view” derived from the pre-trained LM embeddings of the involved entity/trigger directly. As shown in Table 1, without any training, the token-based representation (token view) and the type abstraction representation (mask view) specialize in different types. When the relation type is strongly connected to the entity type as in “website", the token view provides a strong prior. The mask view can distinguish relations with similar entity types (person, organization) based on relational phrases such as”found, create, work at".

Therefore, we combine the mask view and the token view in a co-training framework [16], utilizing information from both ends. As shown in Figure 2, our model consists of a shared contextual encoder, two view-specific projection networks and classification layers for known and unknown types respectively. Since no annotation is available for new types, we perform clustering over the two views to obtain pseudo-labels and then use such labels to guide the training of the classification layer of the opposite view. We apply our model to both relation discovery and event discovery with minimal changes to the type-inducing prompt. Our model serves the dual proposes of (1) inducing clusters with exemplar instances from the input corpus to assist ontology construction and (2) serving as a classifier for instances of unknown types. On the task of relation discovery our model outperforms the previous transfer-learning based SOTA model by 4.3% and 2.2% accuracy on benchmark datasets TACRED and FewRel respectively. On event discovery we also set the new SOTA, achieving 77.3% accuracy for type discovery with gold-standard triggers.

Figure 2: Overview of our type discovery model. We show two instances of the Start-Org event type (green) and two instances of Assist event type (purple). For each instance, we compute the token view and the mask view through two separate projection networks. We use K-means clustering in the respective embedding spaces to obtain pseudo labels and use the labels to supervise the alternative view.

The main contributions of this paper include:

  • We propose the idea of type abstraction, implicitly using inferred type names from the language model to improve type discovery.

  • We design a co-training framework that combines the advantage of type abstraction and the conventional token-based representation.

  • We show that our model can be applied to the discovery of both relation types and event types and achieve superior performance over existing models on both tasks.

2 Problem Definition↩︎

We first define the task of type discovery and then discuss the realization of this task to relations and events.

Given a set of unlabeled instances \(D^u = \{x_1^u, x_2^u, \cdots, x_M^u\}\) and an estimated number of unknown types \(|C^u|\), the goal of type discovery is to learn a model \(f\) that can map \(x \in X^u\) into one of \(y \in C^u\) unknown types.

In the case of relation discovery, each instance \(x\) is an entity mention pair \(\{h, t\}\) embedded within a sentence context. As shown in Figure 1, the instance is “John earned a bachelor’s degree from the University of Wollongong” with the head entity mention “John” and the tail entity mention “University of Wollongong”. Each entity mention is a span with start and end indexes \((s, e)\) in the sentence. The associated label \(y\) in this case is relation type “School_Attended”.1

In the case of event discovery, each instance \(x\) is a trigger word/phrase mention \(t\) with start and end indexes \((s, e)\) in a sentence context as shown in Figure 2. The label \(y\) is the event type. Note that for both relations and events, it is possible for multiple instances to appear within the same sentence, but they have different entity or trigger mentions.

To assist the learning of such a model, we further assume that we have access to a set of labeled instances \(D^l = \{(x_1^l, y_1^l), (x_2^l, y_2^l), \cdots, (x_N^l, y_N^l)\}\). The type labels \(Y = \{y_1^l, y_2^l, \cdots, y_N^l\}\) present in \(D^l\) belong to \(C^l\) known classes which are disjoint from the classes to discover, namely \(C^l \cap C^u = \emptyset\).

3 Method↩︎

Our model is built on the observation that the token view and the mask view are often complementary and work well for different types. Thus, the core of our model is the construction of two views and how they can be utilized for co-training.

3.1 Instance Representation↩︎

We first describe how the relation instances are represented and then discuss the changes for event instances. Similar to  [17], in the input sentence we mark up the entity/trigger with special tokens. We use \(\langle h \rangle\) and \(\langle t \rangle\) for head and tail entities respectively and \(\langle tgr \rangle\) for the trigger. For each instance we have two views: the token view and the mask view. The two views share the same BERT [14] encoder, but have slightly different inputs.

3.1.0.1 Relation Instances.

For the token view, we embed the sentence using BERT and take the embedding for the first token in the entity (index \(s\)) as the entity representation.2 We concatenate the representations for the head and tail entity to obtain the relation representation [17]. \[\begin{align} \vec{h} &= \text{BERT}(x)[s_h] ; \vec{t} = \text{BERT}(x)[s_t] \\ \vec{x}_1 &= [\vec{h}; \vec{t}] \end{align}\]

For the mask view, we append a type prompt \(p_r\) to the input sentence. The type prompt is designed so that the relation type name should be fit into the [MASK] token position. For relations, we use the prompt of “\(\langle\)tail\(\rangle\) is the [MASK] of \(\langle\) head \(\rangle\)” where \(\langle\)tail\(\rangle\) and \(\langle\) head \(\rangle\) are replaced by the actual head and tail entity strings for each instance. Then we embed the sentence along with the type prompt with BERT and use the embedding for the [MASK] token as the relation representation.

\[\vec{x_2} = \text{BERT}(x; p_r)[s_{mask}]\]

3.1.0.2 Event Instances.

For event instances in the token view we use the embedding for the first token in the trigger mention as the event representation. In the mask view we use a different type prompt \(p_e\): “\(\langle\) trigger \(\rangle\) is a [MASK] event" where \(\langle\) trigger \(\rangle\) is replaced by the actual trigger.

\[\begin{align} \vec{x_1} & = \text{BERT}(x)[s] \\ \vec{x_2} & = \text{BERT}(x;p_e)[s_{mask}] \end{align}\]

3.2 Multi-view Model↩︎

Our model consists of a shared BERT encoder, two projection networks \(f\) and four classifier heads \(g\) (for known types and unknown types per view, respectively).

The projection networks map the instance representation \(\vec{x}\) to a lower dimension space representation \(\vec{h}\) and the classifier heads \(g\) maps \(\vec{h}\) into logits \(\vec{l}\) corresponding to the labels.

\[\begin{align} \vec{h} &= f(\vec{x}) \\ \vec{ l^u} & = g^u(\vec{h}) ; \vec{ l^l} = g^l (\vec{h}) \\ \vec{\hat{y}} &= \text{softmax}\left( [\vec{l^l}; \vec{l^u}]\right) \end{align}\]

For instances of known classes, we use the cross-entropy loss with label smoothing to train the network: \[\mathcal{L}^l = - \frac{1}{|D^l|}\sum_{D^l} \sum_{c=1}^C y_c \log (\hat{y}_c)\]

For instances of unknown classes, we run K-means clustering on the projection network output to assign pseudo-labels: \[\tilde{y}^u = \text{K-means}(\vec{h}) \in \{1,\cdots, C^u\}\]

As the pseudo-label assignment might not align across views (cluster 1 in the token view is not the same as cluster 1 in the mask view), for each batch of instances, we further transform the cluster assignment labels into pairwise labels: \[q_{ij} = \mathbb{1}(\tilde{y}_i = \tilde{y}_j)\]

We compute the discrepancy between the predictions of the pair \(x_i, x_j\) using the Jensen-Shannon(JS) divergence: \[\small d_{ij} = \text{JSD} (\hat{\vec{y}}_i, \hat{\vec{y}}_j) = \frac{1}{2} \left\{ \text{KL} (\hat{\vec{y}}_i || \hat{\vec{y}}_j) + \text{KL} (\hat{\vec{y}}_j || \hat{\vec{y}}_i) \right\}\]

Then the loss function for an unlabeled pair is defined as the JS divergence if two instances are assigned to the same cluster and a hinge loss over the JS divergence if two instances are assigned to different clusters.

\[\small \begin{align} & l(d_{ij}, q_{ij}) = q_{ij} d_{ij} + (1-q_{ij}) \max(0, \alpha - d_{ij}) \\ & \mathcal{L}^u = \frac{1}{\binom{|D^u|}{2}}\sum_{x_i, x_j \in D^u} \left( l(d^1_{ij}, q^2_{ij}) + l(d^2_{ij}, q^1_{ij}) \right) \end{align}\] where \(d^1_{ij}\) is computed from the token view, \(d^2_{ij}\) is computed from the mask view and the similarly for \(q^1_{ij}\) and \(q^2_{ij}\). \(\alpha\) is a hyper-parameter for the hinge loss.

If a single view was used, this loss falls back to the contrastive loss term defined for unlabeled instances in [13], [18].

In the training process, we observe that since the pseudo label \(\tilde{y}\) is used as the target for the opposite view, when these two views produce very different clusters, it leads to performance oscillation over epochs.

To alleviate this issue, we add a consistency loss that encourages the predictions of the two views to be similar to each other: \[\mathcal{L}^c = \frac{1}{|D^u|}\sum_{D^u} \text{JSD}(\hat{y}^1, \hat{y}^2)\]

The final loss function is a weighted sum of the aforementioned terms: \[\mathcal{L} = \mathcal{L}^l + \mathcal{L}^u + \beta \mathcal{L}^c \label{eq:loss}\tag{1}\] \(\beta\) is a hyperparameter and empirically set to 0.2 in our experiments.

3.3 Training Procedure↩︎

Before we train our model with the loss function in Equation 1 , we warmup our model by pre-training on the labeled data. The loss function here is simply the cross-entropy loss \(\mathcal{L}_{pre} = \mathcal{L}^l\).

After pre-training, we load the weights for BERT and the projection networks \(f\) to the model for further training. Note that we do not keep the weights for the known class classifier head \(g^l\).

4 Experiments↩︎

In the following experiments, we refer to our model as TAbsto stand for “type abstraction”.

Table 2: Statistics of the datasets used. The first two are for relation discovery and the last two datasets are used for event discovery.
Dataset Known Unknown
#Classes # Ins #Classes #Ins
TACRED 31 23,477 10 1,996
FewRel 64 44,800 16 11,200
ACE-controlled 10 4,089 23 1,221
ACE-end2end 10 1,663 - 17,172

4.1 Relation Discovery Setting↩︎

4.1.0.1 Datasets.

We follow RoCORE [13] and evaluate our model on two relation extraction benchmark datasets: TACRED [15] and FewRel [19]. For the TACRED dataset, 31 relation types are treated as known and 10 relation types are unknown, with the types defined in the TAC-KBP slot filling task [20] 3. Instances with the no_relation label are filtered out as in [13]. For the FewRel dataset, we treat the 64 relation types in the original training set as known relations and 16 relation types in the original development set as unknown relations. For both datasets, we leave out 15% of the instances of both known and unknown relation types, and we report results on the set of unknown relation instances. 4

4.1.0.2 Baselines.

We primarily compare with RoCORE [13] and RSN [9]. which is the state-of-the-art for relation discovery. RoCORE earns its name from their proposed “relation-oriented clustering module” that attempts to shape the latent space for clustering by a center loss (which pushes instances towards centroids) and a reconstruction loss. We also compare with RSN [9], which learns a pairwise similarity metric between relations and transfers such a metric to unknown instances. The encoder is replaced by BERT [14] for a fair comparison. RSN originally uses the Louvain algorithm [21] for clustering, however we observe that sometimes this would lead to all instances assigned to the same cluster so we experiment with a variant using spectral clustering that takes the same graph input as Louvain. For the Louvain variant, we report the best run instead of average and deviation due to cases of clustering collapse.

Table 3: Relation discovery results on TACRED and FewRel. Experiments are ran with 5 different seeds and we report the average score and standard deviation.
Dataset Model Acc \(B^3\) F1 V measure ARI
TACRED RSN [9] 0.7645 \(\pm\) 0.034 0.7194 \(\pm\) 0.036 0.7587 \(\pm\) 0.030 0.6456 \(\pm\) 0.047
RSN-spectral 0.7425 \(\pm\) 0.041 0.7163 \(\pm\) 0.013 0.7569 \(\pm\) 0.013 0.635 \(\pm\) 0.047
ROCORE [13] 0.8468 \(\pm\) 0.059 0.8307 \(\pm\) 0.031 0.8612 \(\pm\) 0.019 0.7867 \(\pm\) 0.052
0.8896 \(\pm\) 0.011 0.8535 \(\pm\) 0.016 0.8718 \(\pm\) 0.017 0.8276 \(\pm\) 0.018
FewRel RSN [9] 0.4880 0.4783 0.6718 0.4184
RSN-Spectral 0.6277 \(\pm\) 0.021 0.6306 \(\pm\) 0.030 0.7351 \(\pm\) 0.020 0.5490 \(\pm\) 0.030
ROCORE [13] 0.7801 \(\pm\) 0.012 0.7652 \(\pm\) 0.025 0.8407 \(\pm\) 0.016 0.7039 \(\pm\) 0.022
0.8022 \(\pm\) 0.023 0.7606 \(\pm\) 0.026 0.8374 \(\pm\) 0.018 0.7266 \(\pm\) 0.032
Table 4: Event discovery results on ACE.
Model Acc \(B^3\) F1 V measure ARI
Controlled Setting
Spherical Clustering [12] 0.3830 0.3861 0.5470 0.2726
SS-VQ-VAE [11] 0.2951 0.2921 0.4063 0.1242
0.7732 \(\pm\) 0.023 0.7110 \(\pm\) 0.034 0.8028\(\pm\) 0.027 0.6647 \(\pm\) 0.038
End-to-end Setting
0.5089 0.5611 0.7049 0.3629

4.2 Event Discovery Setting↩︎

4.2.0.1 Datasets.

We use ACE under the processing by [1] for our event discovery experiments. We follow [11] and set the 10 most popular event types as known types and the remaining 23 event types to be discovered. As ACE is of relatively smaller size compared to the previous datasets used for relation discovery, we leave out 30% of the instances for testing. Results are reported for the unknown type instances only.

4.2.0.2 Controlled Setting.

In the controlled setting we give the models access to ground truth trigger mentions. We compare with the SS-VQ-VAE model from [11] and the spherical latent clustering model from [12]. As the two models originally operated on a different set of instances (sense-tagged triggers in [11] and predicate-object pairs in [12]), we reimplement these methods to work with the gold-standard trigger mentions from ACE.

4.2.0.3 End-to-end Setting.

In the end-to-end setting for our system we treat all non-auxiliary verbs as candidate trigger mentions. For the 10 known types, if the annotated trigger matches with one of the candidate trigger mentions, we treat that instance as labeled. All remaining candidate triggers are treated as unknown and we set the number of unknown types \(K=100\). Under this setting, we compare with the full pipeline of ETypeClus [12].

4.3 Metrics↩︎

The following metrics for cluster quality evaluation are adopted: Accuracy, BCubed-F1 [22], V measure [23], Adjusted Rand Index(ARI) [24].5 Accuracy is computed by finding the maximal matching between the predicted clusters and the ground truth clusters using the Jonker-Volgenant algorithm [25]6.

4.4 Implementation Details↩︎

We use bert-base-uncased as our base encoder. The projection network \(f\) is implemented as a two layer MLP with dimensions 768-256-256 and ReLU activation. The classifier heads are implemented as two layer MLPs as well, with dimensions of 256-256-\(C\), where \(C\) is either the number of known types or unknown types. For additional hyperparameters, see Appendix Section 10.

4.5 Main Results↩︎

We present results on relation discovery in Table 3. While all models benefit from transferring relation knowledge from known types to unknown types, RSN [9] separates the clustering step from the representation step, so the representations are not highly optimized for clustering unlike RoCORE [13] and our model. Compared with RoCORE, our model (1) employs a multiview representation; (2) removes the relation-oriented clustering module and (3) uses a simpler pretraining procedure with only known classes. Although the training procedure is simplified, the use of both token features and mask features leads to improved effectiveness of the model.

On the event type discovery task in Table 4, we show that our model has a great advantage over unsupervised methods such as spherical latent clustering model [12] that does not make use of known types. Among models that perform transfer learning, SS-VQ-VAE [11] does not employ a strong clustering objective over the unknown classes. In the end-to-end setting, our model still outperforms the previous work. However, the gap between the end-to-end performance and the controlled performance show that extra processing on trigger might be necessary before apply this model to the wild. In the human evaluation Table 5, annotators judged 70% of discovered clusters to be semantically coherent compared to 59% of the clusters from the ETypeClus pipeline.

Figure 3: Comparison of predicted relation clusters on TACRED. Instances in the purple box are shared, instances in the pink box are unique to ROCORE output and instances in the blue box are unique to our model’s output.
Table 5: Human evaluation for end-to-end event discovery on the cluster level and instance level. Reported numbers are the ratio of clusters/instances rated as “coherent”/“discernable” by annotators. Cohen’s \(\kappa=0.426\) for this binary decision process. More details about the evaluation protocol can be found in Appendix Section [sec:sec:human-eval].
Model Cluster Instance
Coherence Rate Discernability Rate
ETypeClus 0.59 0.682
0.70 0.725
Table 6: Comparison with model variations on TACRED. PL Acc is the pseudo label accuracy computed from K-means. (Results are from a single run with the same random seed.)
Model Acc \(B^3\) PL Acc
Full model 0.903 0.881 0.878
A:Token view only 0.849 0.828 0.820
B:Mask view only 0.849 0.832 0.822
C:Two branch token 0.866 0.843 0.833
D:Two branch mask 0.869 0.844 0.837
Table 7: Ablation studies on the training process for TACRED.
Model Acc \(B^3\)
Full Model 0.903 0.881
w/o supervised pre-training 0.856 0.862
w/o consistency loss 0.896 0.868

m10em m15em m20em Best Matched Type & Predicted Names & Instance

per:date_of_birth & birthday, year, years, february, month & McNair, born on Dec. 14 , 1923, in the rural Low Country of South Carolina, ...
per:cause_of_death (by disease) & pmid, cord, sign, diagnosed, cause & Palestinian leader Abu Daoud, who planned the daring deadly attack died Saturday of illness ...
per:charges & felony, and, anything, cocaine, wrong & Wen Qiang, was also accused of rape and being unable to explain the sources of his assets ...

Personnel:Start-Position & first, inaugural, introduced, appointed, unopposed & The ruling Millennium Democratic Party (MDP)... has suffered declining popularity since President Roh Moo-Hyun took office in February.
Business:Start-Org, End-Org, Merge-Org & separate, fold, new, employee, strategic & Major US insurance group AIG is in a deal to create Japan ’s sixth largest life insurer
Conflict:Demonstrate & street, demonstration, protest, march, picket & Chalabi staged his own rally yesterday to support his bid to become the next leader of Iraq.

4.6 Ablation Study↩︎

4.6.0.1 Different Views

We compare our full model with several ablations of obtaining the different views as shown in Table 6. Variants A and B use only one view to represent the instance showing the advantage of co-training. We further experiment with different ways of constructing the two views. Variant C first computes the token representation of the instance and then apply two different dropout functions to construct two views. This dropout operation can serve as task-agnostic data augmentation, which has proved to be effective for representation learning [26]. Variant D uses two different type abstraction prompts to construct two representations for the same instance. Both of these variants are more effective than the single view variants but not as effective as combining the token view and the mask view.

4.6.0.2 Model Design

In Table 7 we compare the performance of our full model with variants that omit the pre-training stage and the consistency loss. Pretraining the model on known types is critical to the model’s final performance. The consistency loss, while useful, does not contribute as much to the accuracy but rather alleviates the model oscillation over epochs.

4.6.0.3 Clustering Method

In Table 8 we experiment with different clustering methods under our framework. All implementations are from the sklearn library. For the spectral clustering variant, we use the default radial basis function (RBF) kernel to compute the affinity matrix7, whereas for the other clustering methods we using Eulidean distance to compute the affinity matrix. This metric difference might explain why spectral clustering is underperforming. While DBSCAN and Agglomerative-Ward both achieve reasonably good performance, we observe that DBSCAN is quite sensitive to its eps parameter, which defines the maximum distance between two samples for one to be considered in the neighborhood of the other. In fact, this parameter needs to be set differently for different random seeds based on the distribution of the nearest neighbor distance. In general, \(k\)-means clustering is both stable and efficient for our use case. Note that both our model and ROCORE use k-means clustering to obtain pseudo labels.

Table 8: Comparison of different clustering methods.
Clustering Acc \(B^3\)
\(k\)-means 0.9030 0.8806
DBSCAN 0.8595 0.8481
Agglomerative-Ward 0.8495 0.8497
Spectral 0.7324 0.7258
Table 9: Predicted clusters of event instances on ACE. The triggers are marked in bold.
Matched Type Instances in Cluster
Personnel: Start-Position Condi Rice has been chosen by President Bush to become the new Secretary of State ...
If you were president, which national figures would you appoint to your cabinet and why?
Al-Douri taught international law at Baghdad University before becoming a diplomat ...
Chui Sai On, who has been named [Personnel: Nominate] director of the SARS task force ...
Conflict:Demonstrate Some 70 people were arrested Saturday as demonstrators clashed with police at the end of a major peace rally ...
Between 2,500 and 3,000 people picketed the CNN studios in Los Angeles ...
The crowd filled the street leading to the Kazimiya mosque in the northeast of Baghdad ...
Justice: Arrest-Jail Some 70 people were arrested Saturday as demonstrators clashed with police at the end of a major peace rally ...
Ferris disappeared from sight, and CNN has confirmed he was taken into custody.

5 Analysis↩︎

5.0.0.1 Predicted Type Names.

In Table ¿tbl:tab:pred95names? we show the predicted type names produced by our model. Although our model does not directly rely on such names (but rather the similarity of [MASK] embeddings) to perform clustering , the predictions give insights into the internal workings of the model. For example, the predicted names for the per:cause_of_death cluster are strongly related to disease. In contrast, the following instance Assaf Ramon, 21, died on Sunday when the F-16 fighter jet he was flying crashed was abstracted to names such as death, rotor, life, loss and as a result, was not included as part of the cluster.

5.0.0.2 Relation Discovery.

In Figure 3 we examine the differences in the predicted relation clusters. In the first relation city_of_death, ROCORE incorrectly merges many instances of city_of_birth into the target cluster. These two relation types not only share the same entity types of (person, city) but can also involve the exact same entities, e.g. Jerusalem. As ROCORE is primary relying on token features to make the prediction, instances with shared entities have high similarity and this propagates errors to other instances. In the second example, we observe that both models work well in more conventional cases, but when it comes to rare values such as “hunger strike”, only our model can correctly identify it as the cause_of_death.

5.0.0.3 Event Discovery.

We show predicted clusters of event types from our algorithm under the controlled setting in Table 9. Our model is able to handle (1) diverse triggers, e.g. “chosen”, “appoint” and “becoming” all refer to the Start-Position event type; (2) ambiguous triggers such as “becoming” and “filled” cannot be assigned to the event type without referring to the context; and (3) multi-word triggers, e.g. “take into custody” refers to Arrest. In the Start-Position cluster, we see a few mis-classified instances of Nominate. These two event types are similar as they both involve a person and a position/title, the difference being whether the person has already been appointed the position or not.

5.0.0.4 Remaining Challenges

Abstract types. Relation types such as “part_of”,“instance_of” and “same_as” from the FewRel dataset are highly abstract and can be associated with various types of entities. In fact, such relations are often best dealt with separately in the context of hypernym detection [27], taxonomy construction [28][30] or synonym identification [31], [32].

Misaligned level of granularity. We observe that our automatically induced clusters are sometimes not at the same level of granularity as clusters defined by human annotation. For instance the discovered per:cause_of_death cluster is more like per:disease_of_death and the several business-related events Start-Org, End-Org and Merge-Org are combined into a single cluster. This calls for models that can produce multi-level types or account for human feedback (the user can specify whether the cluster needs to be further split).

6 Related Work↩︎

6.0.0.1 Relation Type Discovery

Early work in this direction represented relations as clusters of lexical patterns or syntactic paths  [7], [33][37]. A wave of newer methods used learned relation representations [8][10], [13], [38][41], often defining the relation as a function of the involved entities. One key observation made by RSN [9] and RoCORE [13] is the possibility of relational knowledge transfer from known relation types to new types. In this work, we also adopt this transfer setting and introduce a new idea of abstraction: a relation cluster is meaningful if it aligns well with a human concept.

6.0.0.2 Event Type Discovery

Our task of event discovery is similar to the verb clustering task in SemEval 2019 [42] which requires mapping verbs in context to semantic frames.8 ETypeClus [12] represents events as (predicate, object) pairs and design a reconstruction-based clustering method over such P-O pairs. SS-VQ-VAE [11] leverages a vector quantized variational autoencoder model to utilize known types.

7 Conclusions and Future Work↩︎

In this paper we study the type discovery problem: automatically identifying and extracting new relation and event types from a given corpus. We propose to leverage type abstraction, where the model is prompted to name the type, as an alternative view of the data. We design a co-training framework, and demonstrate that our framework works favorably in both relation and event type discovery settings. Currently we have assumed that the new types are disjoint to the old types and the model operates similarly to a transfer learning setting. While the model can be easily extended to handle both new types and old types, more analysis might be needed in this direction. One potential direction would be to explore a continual learning setting, where new types could emerge periodically.

8 Limitations↩︎

In this paper we studied datasets that are English and mostly in the newswire genre. Although our method is not strictly restricted to English, the design of the type-inducing prompt will require some prior knowledge about the target language.

For both relation and event type discovery, the model requires the input of candidate entities pairs or triggers. As shown in Table 4, there is a large gap in model performance between the controlled setting and the end-to-end setting (although this could be partially attributed to incomplete annotation and our simple candidate extraction process). This would limit the model’s application in the real world and we believe this should be the focus of future research.

9 Ethical Considerations↩︎

Intended use. The model introduced in this paper is intended to be used for exploratory analysis of datasets. For instance, when presented with a new corpus, the model can be used to extract clusters of new event types that can then be judged by human annotators and used as a basis for developing an event ontology and event extraction system.

Biases. The model does not perform any filtering of its input. If the input corpus contains mentions of discriminatory or offensive language, the model will be unaware and will likely surface such issues in its output.

Acknowledgements↩︎

We would like to thank Yiqing Xie and Jiaming Shen for early discussions about the project idea. We also appreciate the help of Jinfeng Xiao, Yizhu Jiao and Yunyi Zhang on the evaluation. This research was supported by US DARPA KAIROS Program No. FA8750-19-2-1004. Any opinions, findings, and conclusions or recommendations expressed herein are those of the authors and do not necessarily represent the views, either expressed or implied, of DARPA or the U.S. Government.

10 Experiment Details↩︎

We use an effective batch size of 32 (among \(\{8, 16, 32, 64\}\)) and train with an initial learning rate of \(5e-5\) (among \(\{1e-5, 3e-5, 5e-5, 1e-5\}\)) using the AdamW optimizer and a linear schedule. The model is pretrained for 3 epochs for initialization and then further trained for 30 epochs on TACRED/ACE and 20 epochs on FewRel. For the hyperparameters in our model, we set the margin for the hinge loss \(\alpha=2\) following  [18]. We show some additional tuning results in Table 10. The weight for the consistency loss \(\beta=0.2\) was tuned from \(\{0.1, 0.2, 0.5\}\). We tuned our hyperparameters on TACRED based on accuracy and applied them to FewRel and ACE.

Our models are trained on a single Nvidia RTX A6000 GPU. A single run on TACRED takes 2 hours, a run on FewRel takes 2.5 hours and a run on ACE takes 40 minutes. Our model has 111M parameters (110M are from bert-base).

Table 10: Tuning the hinge loss margin \(\alpha\) on TACRED.
\(\alpha\) Acc \(B^3\)
0.5 0.9063 0.8841
1 0.8696 0.8493
2 0.9030 0.8806
5 0.9063 0.8842

11 Varying Cluster Number \(K\)↩︎

In Figure 4 and 5 we show how the model’s performance changes with different specified number of unknown types \(K\). Generally speaking, \(K\) will impact the granularity of the discovered types. On the ACE dataset, a slightly larger number of \(K\) will lead to improved performance. At \(K=35\), the model is able to separate Business:End-Org from Business:Merge-Org which were originally mixed at \(K*=23\). On TACRED, though, \(K*=10\) seems to be the optimal value, and a larger \(K=20\) would result in per:cause_of_death being split into subcategories of disease, homicide, accident and per: charges being split into subcategories of violent (e.g. murder) and non-violent (e.g. espionage).

Figure 4: Performance of type discovery on ACE with varying cluster number K. The ground truth number of clusters K=23.
Figure 5: Performance of type discovery on TACRED with varying cluster number K. The ground truth number of clusters K=10.

12 Human Evaluation Protocol↩︎

We evaluate the end-to-end results for event discovery from both the cluster level and instance level. For each cluster, we present the top 10 and bottom 10 instances and ask annotators if this cluster is meaningful and relevant to the corpus. For instance-level evaluation, we ask the annotator whether an instance belongs to a set of candidate instances or not. This set of candidate instances is either sampled from the same predicted cluster or randomly selected from other clusters with 50% probability.

Figure 6: An example of the evaluation interface presented to annotators.

13 End-to-end Event Discovery Case Study↩︎

In Table 11 we show the results of our model along with ETypeClus under the end-to-end setting. The pipeline of ETypeClus converts predicate mentions into predicate-object (P-O) pairs, selects salient P-O pair then clusters such salient pairs. As a result, the output clusters do not cover infrequent triggers such as “swinging” and “siphoning” and the clusters themselves are often tied together by shared predicates or shared objects (establish state, establish administration and endorse administration). Our model, on the other hand, operates directly on predicate mentions, allowing us to identify events with infrequent triggers and events with named entity or pronoun objects as in “set up EasyJet” and “blame each other”.

Table 11: Discovered type clusters in the end-to-end setting on ACE. The event type names were manually assigned based on the cluster content. The predicate mentions are in bold. The questionable assignments are underlined.
Event Type ETypeClus Ours
Predicate-Obj Predicate Mentions
Transaction return-1 piece, sell-3 cookie, sell-3 commercial, buy-0 pudding, sell-0 park, build-0 housing, sell-5 share sell The program allows Iraq to sell unlimited quantities of oil to buy food
buying They’re basically buying future medical care throughout their lives
swinging Motorola and Texas Instruments both in the chips base swinging to profits
siphoning He had also been accused of siphoning millions of dollars from Project Coast to finance a lavish, globe-trotting lifestyle
Create build-2 blog, establish-0 country, form-2 group, endorse-1 administration, incorporate-0 blog, establish-0 state, establish-0 administration create Major US insurance group AIG is in the final stage of talks ... in a deal to create Japan ’s sixth largest life insurer
produce The electricity that Enron produced was so exorbitant that the government decided it was cheaper not to buy electricity
set (up) EasyCinema founder Stelios Haji - Ioannou , who set up easyJet in 1995
pass U.S. Ambassador John Negroponte was asked whether the United States would withdraw the resolution if it didn’t have the votes to pass it
Oppose maintain-1 innocence, plead-2 conspiracy, denounce-0 move, reject-0 change, rid-0 move, oppose-0 move, announce-2 creation, denounce-1 presence rejecting the flight attendants came in with a close vote rejecting these concessions
opposed 78 of 100 people surveyed opposed the military action in Iraq
blamed A summit ... had been planned for Wednesday but was postponed, according to Israeli and Palestinian officials , who blamed each other for the delay.
objected Russia objected to World Bank rules that required monitoring of patients receiving medication

References↩︎

[1]
Ying Lin, Heng Ji, Fei Huang, and Lingfei Wu. 2020. https://doi.org/10.18653/v1/2020.acl-main.713. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7999–8009, Online. Association for Computational Linguistics.
[2]
Xinya Du and Claire Cardie. 2020. https://doi.org/10.18653/v1/2020.emnlp-main.49. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 671–683, Online. Association for Computational Linguistics.
[3]
Sha Li, Heng Ji, and Jiawei Han. 2021. https://doi.org/10.18653/v1/2021.naacl-main.69. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 894–908, Online. Association for Computational Linguistics.
[4]
Zexuan Zhong and Danqi Chen. 2021. https://doi.org/10.18653/v1/2021.naacl-main.5. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 50–61, Online. Association for Computational Linguistics.
[5]
Deming Ye, Yankai Lin, Peng Li, and Maosong Sun. 2022. https://doi.org/10.18653/v1/2022.acl-long.337. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 4904–4917, Dublin, Ireland. Association for Computational Linguistics.
[6]
Michele Banko, Michael J. Cafarella, Stephen Soderland, Matthew Broadhead, and Oren Etzioni. 2008. Open information extraction from the web. In CACM.
[7]
Limin Yao, Aria Haghighi, Sebastian Riedel, and Andrew McCallum. 2011. https://aclanthology.org/D11-1135. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1456–1466, Edinburgh, Scotland, UK. Association for Computational Linguistics.
[8]
Diego Marcheggiani and Ivan Titov. 2016. https://doi.org/10.1162/tacl_a_00095. Transactions of the Association for Computational Linguistics, 4:231–244.
[9]
Ruidong Wu, Yuan Yao, Xu Han, Ruobing Xie, Zhiyuan Liu, Fen Lin, Leyu Lin, and Maosong Sun. 2019. https://doi.org/10.18653/v1/D19-1021. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 219–228, Hong Kong, China. Association for Computational Linguistics.
[10]
Xuming Hu, Lijie Wen, Yusong Xu, Chenwei Zhang, and Philip Yu. 2020. https://doi.org/10.18653/v1/2020.emnlp-main.299. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 3673–3682, Online. Association for Computational Linguistics.
[11]
Lifu Huang and Heng Ji. 2020. https://doi.org/10.18653/v1/2020.emnlp-main.53. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 718–724, Online. Association for Computational Linguistics.
[12]
Jiaming Shen, Yunyi Zhang, Heng Ji, and Jiawei Han. 2021. https://doi.org/10.18653/v1/2021.emnlp-main.441. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 5427–5440, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
[13]
Jun Zhao, Tao Gui, Qi Zhang, and Yaqian Zhou. 2021. https://doi.org/10.18653/v1/2021.emnlp-main.765. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 9707–9718, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
[14]
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. https://doi.org/10.18653/v1/N19-1423. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
[15]
Yuhao Zhang, Victor Zhong, Danqi Chen, Gabor Angeli, and Christopher D. Manning. 2017. https://doi.org/10.18653/v1/D17-1004. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 35–45, Copenhagen, Denmark. Association for Computational Linguistics.
[16]
Avrim Blum and Tom. Mitchell. 1998. Combining labeled and unlabeled data with co-training. In COLT’ 98.
[17]
Livio Baldini Soares, Nicholas FitzGerald, Jeffrey Ling, and Tom Kwiatkowski. 2019. https://doi.org/10.18653/v1/P19-1279. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2895–2905, Florence, Italy. Association for Computational Linguistics.
[18]
Yen-Chang Hsu, Zhaoyang Lv, and Zsolt Kira. 2018. Learning to cluster in order to transfer across domains and tasks. ICLR.
[19]
Xu Han, Hao Zhu, Pengfei Yu, Ziyun Wang, Yuan Yao, Zhiyuan Liu, and Maosong Sun. 2018. https://doi.org/10.18653/v1/D18-1514. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4803–4809, Brussels, Belgium. Association for Computational Linguistics.
[20]
Heng Ji and Ralph Grishman. 2011. Knowledge base population: Successful approaches and challenges. In Proc. ACL2011.
[21]
Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008:10008.
[22]
Amit Bagga and Breck Baldwin. 1998. https://aclanthology.org/C98-1012. In COLING 1998 Volume 1: The 17th International Conference on Computational Linguistics.
[23]
Andrew Rosenberg and Julia Hirschberg. 2007. https://aclanthology.org/D07-1043. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 410–420, Prague, Czech Republic. Association for Computational Linguistics.
[24]
Lawrence Hubert and Phipps Arabie. 1985. Comparing partitions. Journal of classification, 2(1):193–218.
[25]
David Frederic Crouse. 2016. On implementing 2d rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems, 52:1679–1696.
[26]
Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021. https://doi.org/10.18653/v1/2021.emnlp-main.552. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 6894–6910, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
[27]
Stephen Roller, Douwe Kiela, and Maximilian Nickel. 2018. https://doi.org/10.18653/v1/P18-2057. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 358–363, Melbourne, Australia. Association for Computational Linguistics.
[28]
Rami Aly, Shantanu Acharya, Alexander Ossa, Arne Köhn, Chris Biemann, and Alexander Panchenko. 2019. https://doi.org/10.18653/v1/P19-1474. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4811–4817, Florence, Italy. Association for Computational Linguistics.
[29]
Jiaxin Huang, Yiqing Xie, Yu Meng, Yunyi Zhang, and Jiawei Han. 2020. Corel: Seed-guided topical taxonomy construction by concept learning and relation transferring. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.
[30]
Catherine Chen, Kevin Lin, and Dan Klein. 2021. https://doi.org/10.18653/v1/2021.naacl-main.373. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4687–4700, Online. Association for Computational Linguistics.
[31]
Hongliang Fei, Shulong Tan, and Ping Li. 2019. Hierarchical multi-task word embedding learning for synonym prediction. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.
[32]
Jiaming Shen, Wenda Qiu, Jingbo Shang, Michelle Vanni, Xiang Ren, and Jiawei Han. 2020. https://doi.org/10.18653/v1/2020.emnlp-main.666. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 8292–8307, Online. Association for Computational Linguistics.
[33]
Takaaki Hasegawa, Satoshi Sekine, and Ralph Grishman. 2004. https://doi.org/10.3115/1218955.1219008. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04), pages 415–422, Barcelona, Spain.
[34]
Yusuke Shinyama and Satoshi Sekine. 2006. https://aclanthology.org/N06-1039. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pages 304–311, New York City, USA. Association for Computational Linguistics.
[35]
Limin Yao, Sebastian Riedel, and Andrew McCallum. 2012. https://aclanthology.org/P12-1075. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 712–720, Jeju Island, Korea. Association for Computational Linguistics.
[36]
Bonan Min, Shuming Shi, Ralph Grishman, and Chin-Yew Lin. 2012. https://aclanthology.org/D12-1094. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1027–1037, Jeju Island, Korea. Association for Computational Linguistics.
[37]
Oier Lopez de Lacalle and Mirella Lapata. 2013. https://aclanthology.org/D13-1040. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 415–425, Seattle, Washington, USA. Association for Computational Linguistics.
[38]
Dian Yu, Lifu Huang, and Heng Ji. 2017. Open relation extraction and grounding. In Proc. the 8th International Joint Conference on Natural Language Processing (IJCNLP 2017).
[39]
Étienne Simon, Vincent Guigue, and Benjamin Piwowarski. 2019. https://doi.org/10.18653/v1/P19-1133. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1378–1387, Florence, Italy. Association for Computational Linguistics.
[40]
Thy Thy Tran, Phong Le, and Sophia Ananiadou. 2020. https://doi.org/10.18653/v1/2020.acl-main.669. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7498–7505, Online. Association for Computational Linguistics.
[41]
Fangchao Liu, Lingyong Yan, Hongyu Lin, Xianpei Han, and Le Sun. 2021. https://doi.org/10.18653/v1/2021.acl-long.361. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 4683–4693, Online. Association for Computational Linguistics.
[42]
Behrang QasemiZadeh, Miriam R. L. Petruck, Regina Stodden, Laura Kallmeyer, and Marie Candito. 2019. https://doi.org/10.18653/v1/S19-2003. In Proceedings of the 13th International Workshop on Semantic Evaluation, pages 16–30, Minneapolis, Minnesota, USA. Association for Computational Linguistics.

  1. In the relation extraction literature, the relation type is often denoted as \(r\). For unified notation we use \(y\).↩︎

  2. We overload the notation a bit here and use \(x\) to denote the sentence where the instance is from.↩︎

  3. The unknown relations are schools_attended, cause_of_death, city_of_death, stateorprovince_of_death, founded, country_of_birth, date_of_birth, city_of_birth, charges, country_of_death.↩︎

  4. As the data split is random, our reported numbers are not exactly the same.↩︎

  5. The implementation of BCubed is from https://github.com/m-wiesner/BCUBED, and the implementation of V measure and ARI are from the sklearn library.↩︎

  6. Implementation from https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html↩︎

  7. This is different from the spectral clustering variant of RSN, where the graph is precomputed following [9].↩︎

  8. We were not able to follow this setting due to unavailable data.↩︎