Joint Entity and Relation Extraction with Span Pruning and Hypergraph
  Neural Networks
Entity and Relation Extraction (ERE) is an important task in information
extraction. Recent marker-based pipeline models achieve state-of-the-art
performance, but still suffer from the error propagation issue. Also, most of
current ERE models do not take into account higher-order interactions between
multiple entities and relations, while higher-order modeling could be
beneficial.In this work, we propose HyperGraph neural network for ERE
($\hgnn{}$), which is built upon the PL-marker (a state-of-the-art marker-based
pipleline model). To alleviate error propagation,we use a high-recall pruner
mechanism to transfer the burden of entity identification and labeling from the
NER module to the joint module of our model. For higher-order modeling, we
build a hypergraph, where nodes are entities (provided by the span pruner) and
relations thereof, and hyperedges encode interactions between two different
relations or between a relation and its associated subject and object entities.
We then run a hypergraph neural network for higher-order inference by applying
message passing over the built hypergraph. Experiments on three widely used
benchmarks (\acef{}, \ace{} and \scierc{}) for ERE task show significant
improvements over the previous state-of-the-art PL-marker.
Zhaohui Yan, Songlin Yang, Wei Liu, Kewei Tu
# Joint Entity and Relation Extraction with Span Pruning and

###### Abstract

Entity and Relation Extraction (ERE) is an important task in information extraction. Recent marker-based pipeline models achieve state-of-the-art performance, but still suffer from the error propagation issue. Also, most of current ERE models do not take into account higher-order interactions between multiple entities and relations, while higher-order modeling could be beneficial.In this work, we propose HyperGraph neural network for ERE (HGERE), which is built upon the PL-marker (a state-of-the-art marker-based pipeline model). To alleviate error propagation,we use a high-recall pruner mechanism to transfer the burden of entity identification and labeling from the NER module to the joint module of our model. For higher-order modeling, we build a hypergraph, where nodes are entities (provided by the span pruner) and relations thereof, and hyperedges encode interactions between two different relations or between a relation and its associated subject and object entities. We then run a hypergraph neural network for higher-order inference by applying message passing over the built hypergraph. Experiments on three widely used benchmarks (ACE2004, ACE2005 and SciERC) for ERE task show significant improvements over the previous state-of-the-art PL-marker. 1

Footnote 1: Source code is available at [https://github.com/yanzhh/HGERE](https://github.com/yanzhh/HGERE)

## 1 Introduction

Entity and Relation Extraction (ERE) is a fundamental task in information extraction (IE), compromising two sub-tasks: Named Entity Recognition (NER) and Relation Extraction (RE). There is a long debate on joint vs. pipeline methods for ERE. Pipeline decoding extracts entities first and predicts relations solely on pairs of extracted entities, while joint decoding predicts entities and relations simultaneously.

Recently, the seminal work of [22] shows that pipeline decoding with a frustratingly simple marker-based encoding strategy -- i.e., inserting solid markers [1, 20] around predicted subject and object spans in the input text -- achieves state-of-the-art RE performance. Modified sentences (with markers) are fed into powerful pre-trained large language models (LLM) to obtain more subject- and object-aware representations for RE classification, which is the key to the performance improvement. However, current marker-based pipeline models (e.g., the recent state-of-the-art ERE model PL-marker [23]) _only_ send predicted entities from the NER module to the RE module, therefore missing entities would never have the chance to be re-predicted, suffering from the _error propagation issue_. On the other hand, for joint decoding approaches (e.g. Table Filling methods [13, 21, 22])--though they do not suffer from the error propagation issue--it is hard to incorporate markers for leveraging LLMs, since entities are not predicted prior to relations. Our desire is to obtain the best of two worlds, being able to use marker-based encoding mechanism for enhancing RE performance and meanwhile alleviating the error propagation problem. We adopt PL-marker as the backbone of our proposed model and a span pruning strategy to mitigate error propagation. That is, instead of sending only predicted entity spans to the RE module, we _over-predict_ candidate spans so that the recall of gold entity spans is nearly perfect (but there also could be many non-entity spans), transferring the burden of entity classification and labeling from the NER module to the RE module of PL-marker. The number of over-predicted spans is upper-bounded, balancing the computational complexity of marker-based encoding and the recall of gold entity span. Empirically, we find this simple strategy by itself clearly improves PL-marker.
We further incorporate a _higher-order_ interaction module into our model. Most previous ERE models either implicitly model the interactions between instances by shared parameters Wang and Lu (2020); Yan et al. (2021); Wang et al. (2021) or use a traditional graph neural network that models pairwise connections between a relation and an entity Sun et al. (2019). It is difficult for these approaches to explicitly model higher-order relationships among multi-instances, e.g. the dependency among a relation and its corresponding subject and object entities. Many recent works in structured prediction tasks show that explicit higher-order modeling is still beneficial even with powerful large pretrained encoders Zhang et al. (2020); Li et al. (2020); Yang and Tu (2022); Zhou et al. (2022), _inter alia_), motivating us to use an additional higher-order module to enhance performance.

A common higher-order modeling approach is by means of probabilistic modeling (i.e., conditional random field (CRF)) with end-to-end Mean-Field Variational Inference (MFVI), which can be seamlessly integrated into neural networks as a recurrent neural network layer Zheng et al. (2015), and has been widely used in various structured prediction tasks, such as dependency parsing Wang et al. (2019), semantic role labeling Li et al. (2020); Zhou et al. (2022), and information extraction Jia et al. (2022). However, the limitations of CRF modeling with MFVI are i): CRF's potential functions are parameterized in log-linear forms with strong independence assumptions, suffering from low model capacities Qu et al. (2022), ii) MFVI uses fully-factorized Bernoulli distributions to approximate the otherwise multimodal true posterior distributions, oversimplifying the inference problem and thus is sub-optimal. Therefore we need more _expressive_ tools to improve the quality of higher-order inference. Fortunately, there are many recent works in the machine learning community showing that graph neural networks (GNN) can be used as an inference tool and outperform approximate statistical inference algorithms (e.g., MFVI) Yoon et al. (2018); Zhang et al. (2020); Kuck et al. (2020); Satorras and Welling (2021) (see Hua (2022) for a survey). Inspired by these works, we employ a hypergraph neural network (HyperGNN) instead of MFVI for high-order inference and propose our model HGERE (HyperGraph Neural Network for ERE). Concretely, we build a hypergraph where nodes are candidate subjects and objects (obtained from the span pruner) and relations thereof, and hyperedges encode the interactions between either two relations with shared entities or a relation and its associated subject and object entity spans. In contrast, existing GNN models for IE Sun et al. (2019); Nguyen et al. (2021) only model the pairwise interactions between a relation and one of its corrsponding entity. We empirically show the advantages of our higher-order interaction module (i.e., hypergraph neural network) over MFVI and traditional GNN models.

Our contribution is three-fold: i) We adopt a simple and effective span pruning method to mitigate the error propagation issue, enforcing the power of marker-based encoding. ii) We propose a novel hypergraph neural network enhanced higher-order model, outperforming higher-order CRF-based models with MFVI. iii) We show great improvements over the prior state-of-the-art PL-marker on three commonly used benchmarks for ERE: ACE2004, ACE2005 and SciERC.

## 2 Background

### Problem formulation

Given a sentence \(X\) with \(n\) tokens: \(x_{1},x_{2},...,x_{n}\), an entity span is a sequence of tokens labeled with an entity type and a relation is an entity span pair labeled with a relation type. We denote the set of all entity spans of the sentence with a span length limit \(L\) by \(S(X)=\{s_{1},s_{2},...,s_{m}\}\) and define \(\text{ST}(i)\) and \(\text{ED}(i)\) as the start and end token indices of the span \(s_{i}\).

The joint ERE task is to simultaneously solve the NER and RE tasks. Let \(\mathcal{C}_{e}\) be the set of entity types and \(\mathcal{C}_{r}\) be the set of relation types. For each span \(s_{i}\in S(X)\), the NER task is to predict an entity type \(y_{e}(s_{i})\in\mathcal{C}_{e}\) or \(y_{e}(s_{i})=\texttt{null}\) if the span \(s_{i}\) is not an entity. The RE task is to predict a relation type \(y_{r}(r_{ij})\in\mathcal{C}_{r}\) or \(y_{r}(r_{ij})=\texttt{null}\) for each span \(r_{ij}=(s_{i},s_{j}),s_{i},s_{j}\in S(X)\).

### Packed levitated marker (PL-marker)

Zhong and Chen (2021) insert two pairs of solid markers (i.e., \([S]\) and \([\backslash S]\)) to highlight both the subject and object entity spans in a given sentence, and this simple approach achieves state-of-the-art RE performance. We posit that this is because LLM is more aware of the subject and object spans (with markers) and thus can produce better span representations to improve RE. But this strategy needs to iterate over all possible entity span pairs and is
thus slow. To tackle the efficiency problem, Zhong and Chen (2021) propose an approximated variant wherein each possible entity span is associated with a pair of levitated markers (i.e., \([O]\) and \([\setminus O]\)) whose representations are initialized with the positional embedding of the span's start and end tokens, and all such levitated markers are concatenated to the end of the sentence. As such, levitated-marker-based encoding needs only one pass, significantly improving efficiency at the cost of slight performance drop. Zhong and Chen (2021) also propose a masked attention mechanism such that the original input text tokens are not able to attend to markers, while markers can attend to paired markers (but not unpaired markers) and all input text tokens. As a consequence, the relative positions of levitated markers in the concatenated sentence do not matter at all, eliminating potential implausible inductive bias on the concatenation order.

However, marker-base encoding is only used in RE, not in NER. To leverage marker-based encoding in the NER module for modeling span inter-relations, PL-marker (Ye et al., 2022) associates each possible span with two levitated markers and concatenates all of them to the end of the input sentence. However, this strategy could make the input sentence extremely long since there are quadratic number of spans. To solve this issue, PL-marker clusters the markers based on the starting position of their corresponding spans, and divides them into \(N\) groups. Then the input sentence is duplicated \(N\) times and each group of levitated markers is concatenated to the end of one sentence copy. Ye et al. (2022) refers to this strategy as _neighborhood-oriented packing scheme_. Furthermore, to balance the efficiency and the model expressiveness, Ye et al. (2022) combine solid markers and levitated markers, proposing _Subject-oriented Packing for Span Pair_ in the RE module. That is, if there are \(m\) entities, they copy the sentence for \(m\) times, and for each copy, they use solid markers to mark a different entity as the subject and concatenate the levitated markers of all other entities (as objects) at the end of the sentence.

## 3 Method

Overview.Our method is built upon the state-of-the-art PL-marker. We employ a high-recall span pruner to obtain candidate entity spans, similar to the NER module in PL-marker. However, instead of aiming to accurately predict all possible entity spans, our pruner focuses on removing unlikely candidates to achieve a much higher recall. Then we feed the candidate span set to the RE module to obtain entity and relation representations, which are used to initialize the node representations of our hypergraph neural network for higher-order inference with a message passing scheme. Finally, we perform NER and RE based on the refined entity and relation representations. Fig. 1 depicts the neural architecture of our model.

### Span Pruner

We adopt the neighborhood-oriented packing scheme from PL-marker for span encoding, except that we simply predict entity existence (i.e., binary classification) instead of predicting entity labels during the training phrase. See Appendix A.4 for

Figure 1: Illustration of our framework
details.

To produce a candidate span set, we rank all the spans by their scores and take top \(K\) as our prediction \(S_{p}(X)\). We assume that the number of entity spans of a sentence is linear to its length \(n\), so \(K\) is set to \(\lambda\cdot n\) where \(\lambda\) is a coefficient. For a very long sentence, the number of entity spans is often sublinear to \(n\), while for a very short sentence, we wish to keep enough candidate spans, so we additionally set an upper and lower bound: \(K=\text{max}(l_{\text{min}},\text{min}(\lambda\cdot n,l_{\text{max}}))\).

In practice, with our span pruner, more than 99% gold entity spans are included in the candidate set for all three datasets. If we predict entities as in PL-marker instead of pruning, only around 95% and 80% gold entities are kept in the predicted entities for ACE2005 and SciERC respectively, leading to severe error propagation (see SS5.1 for an ablation study).

The span pruner is trained independently from the joint ERE model introduced in the next section. This is because the joint ERE training loss will be defined based on candidate entity spans produced by the span pruner. When sharing parameters, the pruner would provide a different candidate span set during training, leading to moving targets and thereby destabilizing the whole training process.

### Joint ERE Model: First-order Backbone

The backbone module is based on the RE module of PL-marker. Concretely, given an input sentence \(X=\{x_{1},x_{2},...,x_{n}\}\) and a subject span \(s_{i}=(x_{\text{ST}(i)},x_{\text{ED}(i)})\in S_{p}(X)\) provided by the span pruner, every entity span \(s_{j}\in S_{p}(X),1\leq j\leq K,j\neq i\) could be a candidate object span of \(s_{i}\). The module inserts a pair of solid markers \([S]\) and \([\backslash S]\) before and after the subject span and assign every object span \(s_{j}\) a pair of levitated markers \([O]_{j}\) and \([\backslash O]_{j}\). As shown below, the levitated markers are packed together and inserted at the end of the input sequence to a PLM:

\[x_{1},...,[S],x_{\text{ST}(i)},...,x_{\text{ED}(i)},[\backslash S ],...,x_{n},\] \[[O]_{1},...,[O]_{K},[\backslash O]_{1},...,[\backslash O]_{K}\]

Then we obtain the contextualized hidden representation \(\mathbf{h}_{x}\) of the modified input sequence and the final subject representation is:

\[\mathbf{h}_{s}(s_{i})=\text{FFN}_{s}([\mathbf{h}_{x}([S]);\mathbf{h}_{x}([ \backslash S])])\]

FFN represents a single linear layer in this work. The object representation of \(s_{j}\) for the current subject \(s_{i}\) and the representation of relation \(r_{ij}=(s_{i},s_{j})\) are:

\[\mathbf{h}_{o}^{i}(s_{j})=\text{FFN}_{o}([\mathbf{h}_{x}([O]_{j});\mathbf{h}_ {x}([\backslash O]_{j})])\]

\[\mathbf{h}_{r}(r_{ij})=\text{FFN}_{r}([\mathbf{h}_{s}(s_{i});\mathbf{h}_{o}^{i }(s_{j})])\]

Repeating \(K\) times, we get all \(K\) subject representations and \(K(K-1)\) relation representations. As the object representation of \(s_{j}\) is not identical for different subject span \(s_{i}\), there are \(K\) object representation sets \(\mathbf{h}_{o}^{i},1\leq i\leq K\). We apply a max-pooling layer to obtain a unique object representation for each object span \(s_{j}\in S_{p}(X)\):

\[\mathbf{h}_{o}(s_{j})=\text{Maxpooling}_{1\leq i\leq K,i\neq j}(\mathbf{h}_{o} ^{i}(s_{j}))\]

### Joint ERE Model: Higher-order Inference with Hypergraph Neural Networks

Hypergraph BuildingSo far, the representations of the entities and relations from the backbone module do not explicitly consider beneficial interactions among related instances. To model higher-order interactions among a relation and its associated subject and object entities as well as between any two relations sharing an entity, we build a hypergraph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) to connect the related instances.The nodes set \(\mathcal{V}\) is composed of candidate subjects, objects (provided by the span pruner) and all possible pairwise relations thereof, and we denote them as \(\mathcal{V}_{s}=\{v_{s}^{i}|i\in[1,K]\}\), \(\mathcal{V}_{o}=\{v_{s}^{i}|j\in[1,K]\}\) and \(\mathcal{V}_{r}=\{v_{r}^{ij}|i,j\in[1,K],i\neq j\}\).

Hyperedges \(\mathcal{E}\) capture the interactions we are concerned with, and they can be divided into two categories: the subject-object-relation (sub-obj-rel) hyperedges \(\mathcal{E}_{sor}\) and the relation-relation (rel-rel) hyperedges \(\mathcal{E}_{rr}\). Each hyperedge \(e_{sor}^{ij}\in\mathcal{E}_{sor}\) connects a subject node \(v_{s}^{i}\), an object node \(v_{o}^{j}\) and the corresponding relation node \(v_{r}^{ij}\), and we refer to these hyperedges as _retany_ edges (_ter_ for short). Each rel-rel edge \(e_{rr}^{ijk}\in\mathcal{E}_{rr}\) connects two relation nodes with a shared subject or object entity. We assume in a relation, the subject is the parent node and the object is the child node, and then we can refine rel-rel edges into three subtypes, _sibling_ (_sib_, connecting \(v_{r}^{ij}\) and \(v_{r}^{ik}\)), _co-parent_ (_cop_, connecting \(v_{r}^{ij}\) and \(v_{r}^{kj}\)) and _grand-parent_ (_gp_, connecting \(v_{r}^{ij}\) and \(v_{r}^{jk}\)), following the common definitions in the dependency parsing literature.

If we incorporate all aforementioned hyperedges into the hypergraph, we obtain the _tersibcopgp_ variant which is illustrated in Fig. 1. By removing some types of hyperedges we can get different variants, but without loss of generality we describe
the message passing scheme in the following using _tersibcopgp_.

As such, we can define a CRF on the hypergraph and leverage probabilistic inference algorithms such as MFVI for higher-order inference. However, as discussed in SS1, we can use a more expressive method to improve inference quality and introduce a HyperGraph Neural Network (HGNN) as described next.

Initial node representationFor a relation node \(v_{r}^{ij}\) with its associated subject node \(v_{s}^{i}\) and object node \(v_{o}^{j}\), we use \(\mathbf{g}^{l}(v_{r}^{ij}),\mathbf{g}^{l}(v_{s}^{i})\), \(\mathbf{g}^{l}(v_{o}^{g})\) to denote their respective representation outputs from the \(l\)-th HGNN layer. Initial node representations (before being fed to a HGNN) are \(\mathbf{g}^{0}(v_{s}^{i})=\mathbf{h}_{s}(s_{i})\), \(\mathbf{g}^{0}(v_{o}^{j})=\mathbf{h}_{o}(s_{j})\) and \(\mathbf{g}^{0}(v_{r}^{ij})=\mathbf{h}_{r}(r_{ij})\), respectively (from the backbone module).

Message representationA hyperedge connecting to nodes serve as the bridge for message passing between nodes connected by it. Let \(\mathcal{N}_{e}(v)\) be the set of hyperedges connecting to a node \(v\).

For a _ter_ hyperedge \(e_{ter}^{ij}\in\mathcal{E}_{sor}\) connecting a subject node \(v_{s}^{i}\), a object node \(v_{o}^{j}\) and a relation node \(v_{r}^{ij}\), the message representation it carries is:

\[\mathbf{h}\mathbf{r}_{ij}^{l} =\text{FFN}_{r}^{ter}(\mathbf{g}^{l-1}(v_{r}^{ij}))\] \[\mathbf{h}\mathbf{s}_{i}^{l} =\text{FFN}_{s}^{ter}(\mathbf{g}^{l-1}(v_{s}^{i}))\] \[\mathbf{h}\mathbf{o}_{j}^{l} =\text{FFN}_{o}^{ter}(\mathbf{g}^{l-1}(v_{o}^{j}))\] \[\mathbf{m}^{l}(e_{ter}^{ij}) =\text{FFN}_{e}^{ter}(\mathbf{h}\mathbf{r}_{ij}^{l}\circ\mathbf{ h}\mathbf{s}_{i}^{l}\circ\mathbf{h}\mathbf{o}_{j}^{l})\]

where \(\circ\) is the Hadamard product.

A rel-rel edge \(e_{2}^{ijk}\in\mathcal{E}_{rr},\mathtt{z}\in\{\mathit{sib},\mathit{cop}, \mathit{gp}\}\) connects two relations sharing an entity. For simplicity, we denote them relation \(a\) and \(b\). If we fix \(a\) as \(a\triangleq v_{r}^{ij}\), then as previously described, relation \(b\) is \(v_{r}^{ik}\) for _sib_ edge, \(v_{r}^{kj}\) for _cop_ edge, and \(v_{r}^{jk}\) for _gp_ edge. The message \(e_{z}^{ijk}\) carries is given by,

\[\mathbf{h}_{z}^{l}(a)=\text{FFN}_{a}^{\mathtt{z}}(\mathbf{g}^{l -1}(a))\] \[\mathbf{h}_{z}^{l}(b)=\text{FFN}_{e}^{\mathtt{z}}(\mathbf{g}^{l -1}(b))\] \[\mathbf{m}^{l}(e_{z}^{ijk})=\text{FFN}_{e}^{\mathtt{z}}(\mathbf{ h}_{z}^{l}(a)\circ\mathbf{h}_{z}^{l}(b))\]

Node representation updateWe aggregate messages for each node \(v\in\mathcal{V}\) from adjacent edges \(\mathcal{N}_{e}(v)\) with an attention mechanism by taking a learned weighted sum, and add the aggregated message to the prior node representation,

\[\beta^{l}(e,v)=\mathbf{w}^{\top}\sigma(\mathbf{W}[\mathbf{g}^{l-1}(v); \mathbf{m}^{l}(e)]\] \[\alpha^{l}(e,v)=\frac{\exp\beta^{l}(e,v)}{\sum_{e^{\prime}\in \mathcal{N}_{e}(v)}\exp\beta^{l}(e^{\prime},v)}\] \[\mathbf{g}^{l}(v)=\mathbf{g}^{l-1}(v)+\sum_{e\in N_{e}(v)} \alpha^{l}(e,v)\mathbf{m}^{l}(e)\]

where \(\sigma(\cdot)\) is a non-linear activator and \(\mathbf{w},\mathbf{W}\) are two trainable parameters. An entity node would receive messages only from _ter_ edges while a relation node would receive messages from both _ter_ edges and rel-rel edges.

TrainingWe obtain refined \(\mathbf{g}^{l}(v)\) from the final layer of HGNN. Give an entity span \(s_{i}\in S_{p}(X)\), we concatenate the corresponding subject representation \(\mathbf{g}^{l}(v_{s}^{i})\) and object representation \(\mathbf{g}^{l}(v_{o}^{i})\) to obtain the entity representation, and compute the probability distribution over the types \(\{\mathcal{C}_{e}\}\bigcup\{\texttt{null}\}\):

\[P_{e}(\hat{y}_{e}|s_{i})=\text{Softmax}(\text{FFN}_{e}^{cls}([\mathbf{g}^{l}(v _{s}^{i});\mathbf{g}^{l}(v_{o}^{i})]))\]

Given a relation \(r_{ij}=(s_{i},s_{j}),s_{i},s_{j}\in S_{p}(X)\), we compute the probability distribution over the types \(\{\mathcal{C}_{r}\}\bigcup\{\texttt{null}\}\):

\[P_{r}(\hat{y}_{r}|r_{ij})=\text{Softmax}(\text{FFN}_{r}^{cls}(\mathbf{g}^{l}( v_{r}^{ij})))\]

We use the cross-entropy loss for both entity and relation prediction:

\[L_{e} =-\sum_{s_{i}\in S_{p}(X)}\log(P_{e}(y_{e}^{*}(s_{i})|s_{i}))\] \[L_{r} =-\sum_{s_{i},s_{j}\in S_{p}(X)}\log(P_{r}((y_{r}^{*}(r_{ij})|r_{ ij}))\]

where \(y_{e}^{*}\) and \(y_{r}^{*}\) are gold entity and relation types respectively. The total loss is \(L=L_{e}+L_{r}\).

## 4 Experiment

DatasetsWe experiment on SciERC [1], ACE2004 [5] and ACE2005 [10]. We follow Ye et al. (2022) to split ACE2004 into 5 folds and split ACE2005 and SciERC into train/dev/test sets. See Appendix A.1 for detailed dataset statistics.

Evaluation metricsWe report micro labeled F1 measures for NER and RE. For RE, the difference between Rel and Rel+ is that the former requires correct prediction of subject and object entity spans and the relation type between them, while the latter additionally requires correct prediction of subject and object entity types.
BaselineOur baseline models include: i) **Backbone**. It is described in Sect. 3.2 and does not contain the higher-order interaction module. ii) **GCN**. It has a similar architecture to Sun et al. (2019); Nguyen et al. (2021) and does not contain higher-order hyperedges. See Appendix A.6 for a detailed description. iii) **MFVI**. It defines a CRF on the same hypergraph as our model and uses MFVI instead of hypergraph neural networks for higher-order inference. See Appendix A.5 for a detailed description.

Implementation detailsFor a fair comparison with previous work, we use _bert-base-uncased_(Devlin et al., 2019) and _albert-xxlarge-v1_(Lan et al., 2020) as the base encoders for ACE2004 and ACE2005, _scibert-scivocab-uncased_(Beltagy et al., 2019) as the base encoder for SciERC. GCN and MFVI are also built upon Backbone. The implementation details of experiments are in Appendix A.3.

Main resultsFor HGRE, we report the best results among the following variants of hypergraphs with different types of hyperedges: _ter_, _cop_, _sib_, _gp_, _terscib_, _tercp_, _terspb_, _terscipgp_, and _tersibcopgp_. The best variants of HGRE are _terscibcop_ on SciERC and ACE2005 (BERT\({}_{B}\)); _terscib_ on ACE2005 (ALBERT); _tercp_ on ACE2004. For MFVI we use the same variants as used in HGRE.

Table 1 shows the main results. Surprisingly, Backbone outperforms prior approaches in almost all metrics by a large margin (except on ACE2004 with BERT\({}_{B}\) and ACE2005 with ALBERT), which we attribute to the reduction of error propagation with a span pruning mechanism. Our proposed model HGRE outperforms almost all baselines in all metrics (except the entity metric on ACE2004), validating that using hyperedges to encode higher-order interactions is effective (compared with GCN) and that using hypergraph neural networks for higher-order modeling and inference is better than CRF-based probabilistic modeling with MFVI. Finally, we remark that HGRE obtains state-of-the-art performances on all the three datasets.

## 5 Analysis

### Effectiveness of the span pruner

To study the effectiveness of the span pruner, we replace it with an entity identifier which is the original NER module from PL-marker and is trained only on entity existence. The performance of the span pruner and the entity identifier (denoted by Eid) on entity existence is shown in Table 2. We can observe that if we replace the span pruner with the entity identifier, the recall of gold _unlabeled

\begin{table}
\begin{tabular}{l c c c c c c c c c c} \hline \hline \multirow{2}{*}{Models} & \multirow{2}{*}{Encoder} & \multicolumn{4}{c}{ACE2005} & \multicolumn{4}{c}{ACE2004} & \multicolumn{4}{c}{SciERC} \\ \cline{3-10}  & & Ent & Rel & Rel+ & Ent & Rel & Rel+ & Ent & Rel & Rel+ \\ \hline (Wadden et al., 2019)\({}^{*}\) & & 88.6 & 63.4 & - & - & - & 67.5 & 48.4 & - \\ (Wang et al., 2021)\({}^{*}\) & & 88.8 & - & 64.3 & 87.7 & - & 60.0 & 68.4 & - & 36.9 \\ (Zhong and Chen, 2021)\({}^{*}\) & & 90.1 & 67.7 & 64.8 & 89.2 & 63.9 & 60.1 & 68.9 & 50.1 & 36.8 \\ (Yan et al., 2021) & & - & - & - & - & - & - & 66.8 & - & 38.4 \\ (Shen et al., 2021)\({}^{*}\) & BERT\({}_{B}\)/ & 87.6 & 66.5 & 62.8 & - & - & - & 70.2 & 52.4 & - \\ (Nguyen et al., 2021) & SciBERT & 88.9 & 68.9 & - & - & - & - & - & - & - \\ (Ye et al., 2022)\({}^{*}_{w}\) & & 89.1 & 68.3 & 65.1 & 88.5 & 66.3 & 62.2 & 68.8 & 51.1 & 38.3 \\ Backbone\({}^{*}\) & & 90.0 & 69.8 & 66.7 & 89.5 & 66.6 & 62.1 & 71.3 & 52.3 & 40.2 \\ GCN\({}^{*}\) & & 90.2 & 69.6 & 66.5 & **90.0** & 67.6 & 63.5 & 74.1 & 54.8 & 42.9 \\ MFVI\({}^{*}\) & & 90.2 & 69.7 & 67.1 & 89.7 & 67.4 & 63.4 & 73.3 & 54.7 & 42.5 \\ HGRE\({}^{*}\) (our model) & & 90.2 & **70.7** & **67.5** & 89.9 & **68.2** & **64.2** & **74.9** & **55.7** & **43.6** \\ \hline (Liu et al., 2022) & T5\({}_{3B}\) & 91.3 & 72.7 & 70.5 & - & - & - & - & - & - \\ \hline (Wang and Lu, 2020) & & 89.5 & 67.6 & 64.3 & 88.6 & 63.3 & 59.6 & - & - & - \\ (Wang et al., 2021)\({}^{*}\) & & 90.2 & - & 66.0 & 89.5 & - & 63.0 & - & - & - \\ (Zhong and Chen, 2021)\({}^{*}\) & & 90.9 & 69.4 & 67.0 & 90.3 & 66.1 & 62.2 & - & - & - \\ (Yan et al., 2021) & & 89.0 & - & 66.8 & 89.3 & - & 62.5 & - & - & - \\ (Ye et al., 2022)\({}^{*}_{w}\) & ALBERT & 91.3 & 72.5 & 70.5 & 90.5 & 69.3 & 66.1 & - & - & - \\ Backbone\({}^{*}\) & & 91.5 & 72.9 & 70.2 & 91.6 & 70.2 & 66.6 & - & - & - \\ GCN\({}^{*}\) & & 91.7 & 73.1 & 69.9 & **92.0** & 71.5 & 67.9 & - & - & - \\ MFVI\({}^{*}\) & & 91.6 & 72.7 & 70.1 & 89.9 & 68.5 & 65.1 & - & - & - \\ HGRE\({}^{*}\) (our model) & & **91.9** & **73.5** & **70.8** & 91.9 & **71.9** & **68.3** & - & - & - \\ \hline \hline \end{tabular}
\end{table}
Table 1: F1 scores and standard deviations on ACE2004, ACE2005 and SciERC. The models marked with \(\star\) leverage cross-sentence information. A model with subscript _re_ means we re-evaluate the model with the evaluation method commonly used in other work\({}^{2}\). Backbone, MFVI and GCN are our baseline models.
entity spans drops from 99.2 to 78.7 on the SciERC test set, and drops from 99.8 to 95.8 on the ACE2005 test set. We further investigate how the choice of the span pruner vs. the entity identifier influences NER and RE performances. The results are shown in Table 3. We can see that without a span pruner, both NER and RE performances drop significantly, validating the usefulness of using a span pruner. Moreover, it has a consequent influence on the higher-order inference module (i.e., HGNN). Without a span pruner, the improvement from using a HGNN over Backbone is marginal compared to that with a span pruner. We posit that without a pruner many gold entity spans could not exist in the hypergraph of HGNNs, making true entities and relations less connected in the hypergraph and thus diminishing the usefulness of HGNNs.

### Effect of the choices of hyperedges

We compare different variants of HGNN with different combinations of hyperedges. Note that if _ter_ is not used, entity nodes do not have any hyperedges connecting to them, so their representations would not be refined. We can see that in the _sib_ and _cop_ variants, the NER performance improves slightly, which we attribute to the shared encoder of NER and RE tasks 3. On the other hand, in the _ter_ variant, entity node representations are iteratively refined, resulting in significantly better NER performance than Backbone (74.2 vs. 71.3). Combining _ter_ edges with other rel-rel edges (e.g., _sib_) is generally better than using _ter_ alone in terms of NER performance, suggesting that joint (and higher-order) modeling of NER and RE indeed has a positive influence on NER, while prior pipeline approaches (e.g., PL-marker) cannot enjoy the benefit of such joint modeling.

Footnote 3: Though Zhong and Chen (2021) argue that using shared encoders would suffer from the _feature confusion problem_, later works show that shared encoders can still outperform separated encoders Yan et al. (2021, 2022).

For RE, _sib_ and _cop_ have positive effects on the performance (despite _gp_ having a negative effect somehow), showing the advantage of modeling interactions between two different relations. Further combining them with _ter_ improves RE performances in all cases, indicating that NER also has a positive effect on RE and confirming again the advantage of joint modeling of NER and RE.

### Inference speed of higher-order module

To analyze the computing cost of our higher-order module, we present the inference speed of HGRE with three baseline models Backbone, GCN and MFVI on the test sets of SciERC and ACE2005. Inference speed is measured by the number of candidate entities processed per second. The results are shown in Table 5. We can observe that

\begin{table}
\begin{tabular}{l c c c} \hline \hline \multirow{2}{*}{HGRE} & \multicolumn{3}{c}{SciERC} \\ \cline{2-4}  & Ent & Rel & Rel+ \\ \hline Backbone & 71.3 & 52.3 & 40.2 \\ _ter_ & 74.2 & 55.1 & 42.6 \\ _sib_ & 71.7 & 54.3 & 41.7 \\ _cop_ & 71.7 & 52.9 & 40.8 \\ _gp_ & 71.3 & 51.9 & 40.1 \\ _tersib_ & 74.7 & **55.9** & 43.3 \\ _tercop_ & 74.7 & 55.7 & **43.6** \\ _tergp_ & 74.5 & 54.9 & 42.4 \\ _tersibcop_ & **74.9** & 55.7 & **43.6** \\ _tersibgp_ & 74.2 & 54.1 & 41.8 \\ _tercopgp_ & 74.7 & 54.0 & 42.3 \\ _tersibcopgp_ & 74.3 & 54.6 & 41.7 \\ \hline \hline \end{tabular}
\end{table}
Table 4: F1 scores of HGRE with different graph topologies on the SciERC test set.

\begin{table}
\begin{tabular}{l c c c c c c c} \hline \hline \multirow{2}{*}{} & \multicolumn{3}{c}{SciERC} & \multicolumn{3}{c}{ACE2005 (BERT\({}_{B}\))} \\ \cline{2-8}  & & P & R & F1 & P & R & F1 \\ \hline \multirow{3}{*}{Eid} & train & 98.8 & 98.2 & 98.5 & 100.0 & 99.9 & 99.9 \\  & dev & 81.0 & 81.6 & 81.3 & 94.7 & 94.6 & 94.7 \\  & test & 80.4 & 78.7 & 79.5 & 95.6 & 95.8 & 95.7 \\ \hline \multirow{3}{*}{Pruner} & train & 38.0 & 99.2 & 54.9 & 37.2 & 99.9 & 54.2 \\  & dev & 38.1 & 99.1 & 55.0 & 36.4 & 99.7 & 53.3 \\ \cline{1-1}  & test & 38.7 & 99.2 & 55.7 & 37.0 & 99.8 & 54.0 \\ \hline \end{tabular}
\end{table}
Table 2: Evaluation results on entity existence of the span pruner vs. an entity identifier.

\begin{table}
\begin{tabular}{l l c c c} \hline \hline \multirow{2}{*}{SciERC} & \multicolumn{3}{c}{Ent} & Rel & Rel+ \\ \hline \multirow{2}{*}{Eid} & Backbone & 69.4 & 50.3 & 39.0 \\  & HGRE & 69.4 & 51.5 & 39.5 \\ \hline \multirow{2}{*}{pruner} & Backbone & 71.3 & 52.3 & 40.2 \\  & HGRE & 74.9 & 55.7 & 43.6 \\ \hline \multirow{2}{*}{ACE2005 (BERT\({}_{B}\))} & Ent & Rel & Rel+ \\ \hline \multirow{2}{*}{Eid} & Backbone & 89.5 & 68.3 & 65.3 \\  & HGRE & 89.5 & 68.5 & 66.0 \\ \hline \multirow{2}{*}{pruner} & Backbone & 90.0 & 69.8 & 66.7 \\  & HGRE & 90.2 & 70.7 & 67.5 \\ \hline \hline \end{tabular}
\end{table}
Table 3: F1 scores of Backbone and HGRE with and without a pre-trained span pruner on the SciERC and ACE2005 (BERT\({}_{B}\)) test set.
when utilizing a relatively smaller PLM, HGERE, GCN and MFVI were slightly slower than the first-order model Backbone. However, the difference in speed between HGERE and the other models was relatively small. When using ALBERT, which is much slower than BERT\({}_{B}\), all four models demonstrated comparable inference speeds.

### Error correction analysis

We provide quantitative error correction analysis between our higher-order approach HGERE and the first-order baseline Backbone on the SciERC dataset in Fig. 2. We can see that most error corrections of entities and relations made by HGERE come from two categories. The first category is where Backbone incorrectly predicts a true entity or relation as null, and the second category is where Backbone incorrectly assigns a label to a null sample.

## 6 Related Work

Entity and relation extractionThe entity and relation extraction task has been studied for a long time. The mainstream methods could be divided into pipeline and joint approaches. Pipeline methods tackle the two subtasks, named entity recognition and relation extraction, consecutively Zelenko et al. (2003); Chan and Roth (2011); Zhong and Chen (2021); Ye et al. (2022). By utilizing a new marker-based embedding method, Ye et al. (2022) becomes the new state-of-the-art ERE model. However, pipeline models have the inherent error propagation problem and they could not fully leverage interactions across the two subtasks. Joint approaches, on the other hand, can alleviate the problem by simultaneously tackling the two subtasks, as empirically revealed by Yan et al. (2022). Various joint approaches have been proposed to tackle ERE. Miwa and Bansal (2016); Katiyar and Cardie (2017) use a stacked model for joint learning through shared parameters. Miwa and Sasaki (2014); Gupta et al. (2016); Wang and Lu (2020); Wang et al. (2021); Yan et al. (2021) tackle both the NER and RE tasks as tagging entries of a table. Fu et al. (2019); Sun et al. (2019) leverage a graph convolutional network (GCN) on an instance dependency graph to enhance instance representations. Nguyen et al. (2021) propose a framework to tackle multiple Information Extraction tasks jointly including the ERE task where a GCN is used to capture the interactions between related instances.

Another line of research is based on text-to-text models for structure prediction including ERE. Normally they are not task-specialized and could solve

Figure 2: Error correction of entity and relation types on the SciERC dataset. Red color indicates positive corrections and blue color indicates negative corrections. Specifically, positive numbers on the diagonal of the matrix (in red color) indicate that HGERE makes more correct predictions compare to Backbone; negative numbers on non-diagonal entries (in red color) indicate that HGERE makes fewer wrong predictions compare to Backbone. Numbers in blue indicate the opposite. We do not count the null-null case.

\begin{table}
\begin{tabular}{l c c c} \hline \hline  & \multicolumn{2}{c}{SciERC} & \multicolumn{2}{c}{ACE2005} \\ \cline{2-4}  & SciBERT & BERT\({}_{B}\) & ALBERT \\ \hline Backbone & 19.4 & 38.0 & 6.1 \\ GCN & 15.7 & 33.8 & 6.3 \\ MFVI & 16.5 & 36.9 & 6.1 \\ HGERE & 15.7 & 30.7 & 6.0 \\ \hline \hline \end{tabular}
\end{table}
Table 5: Comparison of inference speed (#entities/sec) between HGERE and three baseline models on test sets of SciERC and ACE2005.
several structure prediction tasks in a unified way (Paolini et al., 2021; Lu et al., 2022; Liu et al., 2022).

This work is similar to Sun et al. (2019); Nguyen et al. (2021) for we both use a graph neural network to enhance the instance representations. The main difference is that the GCN they use cannot adequately model higher-order relationship among multiple instances, while our hypergraph neural network is designed for higher-order modeling.

CRF-based higher-order modelA commonly used higher-order model utilizes approximate inference algorithms (mean-field variational inference or loopy belief propagation) on CRFs. Zheng et al. (2015) formulate the mean-field variational inference algorithm on CRFs as a stack of recurrent neural network layers, leading to an end-to-end model for training and inference. Many higher-order models employ this technique for various NLP tasks, such as semantic parsing (Wang et al., 2019; Wang and Tu, 2020) and information extraction (Jia et al., 2022).

Hypergraph neural networkHypergraph neural network (HyperGNN) is another way to construct an higher-order model. Traditional Graph Neural Networks employ pairwise connections among nodes, whereas HyperGNNs use a hypergraph structure for data modeling. Feng et al. (2019) and Bai et al. (2021) proposed spectral-based HyperGNNs utilizing the normalized hypergraph Laplacian. Arya et al. (2020) is a spatial-based HyperGNN which aggregates messages in a two-stage procedure. Huang and Yang (2021) proposed _UniGNN_, a unified framework for interpreting the message passing process in HyperGNN. Gao et al. (2023) introduced a general high-order multi-modal data correlation modeling framework to learn an optimal representation in a single hypergraph based framework.

## 7 Conclusion

In this paper, we present HGERE, a joint entity and relation extraction model equipped with a span pruning mechanism and a higher-order interaction module (i.e., HGNN). We found that simply using the span pruning mechanism by itself greatly improve the performance over prior state-of-the-art PL-marker, indicating the existence of the error propagation problem for pipeline methods. We compared our model with prior traditional GNN-based models which do not contain hyperedges connecting multiple instances and showed the improvement, suggesting that modeling higher-order interactions between multiple instances is beneficial. Finally, we compared our model with the most popular higher-order CRF models with MFVI and showed the advantages of HGNN in higher-order modeling.

## Limitations

Our model achieves a significant improvement in most cases (on ACE2004, SciERC datasets and on ACE2005 with Bertbase). While on ACE2005 with stronger encoder (e.g., ALBERT) we observe less significant improvements. We posit that, with powerful encoders, the recall of gold entity spans would increase, thereby mitigating the error propagation issue and diminishing the benefit of using a span pruning mechanism.

Another concern regarding our model is computational efficiency. The time complexity of the _Subject-oriented Packing for Span Pair_ encoding scheme from PL-marker grows linearly with the size of candidate span size. Recall that we over-predict many spans using a span pruning mechanism, which slows down the running time. In practice, our model's running time is around as three times as that of PL-marker.

## Acknowledgments

This work was supported by the National Natural Science Foundation of China (61976139).
