Graph Convolution over Multiple Dependency Sub-graphs for Relation Extraction

We propose a contextualised graph convolution network over multiple dependency-based sub-graphs for relation extraction. A novel method to construct multiple sub-graphs using words in shortest dependency path and words linked to entities in the dependency parse is proposed. Graph convolution operation is performed over the resulting multiple sub-graphs to obtain more informative features useful for relation extraction. Our experimental results show that the proposed method achieves superior performance over the existing GCN-based models achieving state-of-the-art performance on cross-sentence n-ary relation extraction dataset and SemEval 2010 Task 8 sentence-level relation extraction dataset. Our model also achieves a comparable performance to the SoTA on the TACRED dataset.

Introduction
In recent times, Graph Convolutional Network (GCN) (Kipf and Welling, 2016) based models such as Contextualised GCN (C-GCN)  and Attention Guided GCN (AGGCN) (Guo et al., 2019) are shown to be useful for relation extraction. The C-GCN model employs pruned dependency trees obtained using a path-centric pruning distance to filter irrelevant nodes from sentence graph to aid in relation extraction. Experiments with C-GCN model shows that the performance of the C-GCN model significantly decreases with the inclusion of all nodes in the sentence graph obtained from the dependency graph , thus making it important to use a right pruning distance to achieve optimum performance. The AGGCN model (Guo et al., 2019) on the other hand, instead of using pruned dependency trees, considers the full dependency tree with a self-attention mechanism to learn node representation useful for relation extraction. In contrast to these GCN-based models using a single graph, we propose in this paper to use multiple sub-graphs constructed from dependency tree to represent a sentence for relation extraction. Given the decrease in performance of C-GCN with an increase in the size of graph , we hypothesise that using multiple sub-graphs in place of a single graph can boost performance of GCN-based models for relation extraction. In comparison to the AGGCN model (Guo et al., 2019), our proposed model simply considers smaller graphs associated with entities to learn representation for important nodes in the sentence.
Further, while the pruning strategy used by the C-GCN model ) is applicable for sentence-level relation extraction, it is not suitable for cross-sentence n-ary relation extraction as there could be more than two entities across multiple sentences. The challenges arise in obtaining a single dependency path in the LCA sub-tree connecting n-ary entities across sentences for cross-sentence relation extraction. Previous work on cross-sentence relation extraction task (Peng et al., 2017;Song et al., 2018;Guo et al., 2019) have largely made use of full dependency graph with additional features such as adjacent words and co-reference links (Peng et al., 2017). The usage of full dependency tree significantly increases network parameters, requiring high computational power. In contrast to these works on n-ary relation extraction, we propose in this paper a novel method to construct sub-graphs using connections between entities and root terms in dependency tree across sentences. Our approach described in this paper significantly reduces the number of nodes in a graph and also at the same time helps in achieving higher performance for cross-sentence n-ary relation extraction.
More specifically, the key contributions of this paper are: (a) propose a C-GCN model over multiple sub-graphs (C-GCN-MG) for cross-sentence n-ary relation extraction and sentence-level relation extraction tasks; (b) propose novel methods to construct sub-graphs around entities using the dependency tree for relation extraction; (c) provide evidence to substantiate the use of multiple sub-graphs instead of a single graph for relation extraction; and (d) evaluate C-GCN-MG model on standard datasets for relation extraction and show that C-GCN-MG achieves SoTA performance on cross-sentence n-ary relation extraction dataset (Peng et al., 2017) and SemEval 2010 Task 8 dataset (Hendrickx et al., 2019) to outperform C-GCN and AGGCN models. We also show that C-GCN-MG achieves comparable performance against C-GCN and AGGCN models on TACRED dataset (Zhang et al., 2017).

Related Work
GCNs have been successfully applied for various information retrieval tasks in different areas such as bioinformatics (Borgwardt et al., 2005), chemoinformatics (Duvenaud et al., 2015), social network analysis (Backstrom and Leskovec, 2011), urban computing (Bao et al., 2017) and natural language processing (Borgwardt et al., 2005). With specific application to relation extraction, several studies have examined the use of graph-based mechanisms to improve relation extraction. For example, a combination of dependency graphs, PropBank and FrameNet based features and surface-level lexical features were successfully used with support vector machines to improve relation extraction (Rink and Harabagiu, 2010). Sequence-based Neural network models such as Recurrent Neural Networks (RNNs), LSTMs, BiLSTMs have been used with graph-based features for relation extraction (Socher et al., 2012). Shortest dependency path (SDP) between entities combined with RNNs are also shown to be useful for relation extraction (Xu et al., 2015). Further, word sequence and dependency tree substructures are combined to jointly model entity and relation extraction (Miwa and Bansal, 2016). More recently, graph-based LSTM networks have been shown particularly useful in the context of n-ary cross-sentence relation extraction (Peng et al., 2017;Song et al., 2018). GCN-based models such C-GCN  and AGGCN (Guo et al., 2019) are shown to achieve SoTA performance on sentence-level and cross-sentence relation extraction. A combined neural network model that brings together the usefulness of LSTM networks in learning from longer sequences and CNNs to capture salient features is also proposed cross-sentence n-ary relation extraction (Mandya et al., 2018). The main focus of this paper is to examine the use of multiple sub-graphs along with graph convolution models for relation extraction. In contrast to previous GCN-based models for relation extraction such as C-GCN  and AGGCN (Guo et al., 2019) which use a single graph to learn node representations, we propose in this paper a C-GCN model that uses multiple sub-graphs to learn a richer node representation that helps in relation extraction. For this purpose, we propose a novel method to obtain multiple sub-graphs from dependency parse trees of a given sentence. To the best knowledge of the authors, this is the first study which effectively combines GCNs with multiple sub-graphs for relation extraction and shows that such a strategy is useful for achieving SoTA performance for relation extraction.

Constructing multiple sub-graphs for relation extraction
We propose a method to encode multiple sub-graphs with GCNs for two different tasks: (a) sentencelevel relation extraction; and (b) cross-sentence n-ary relation extraction as follows:

Sentence-level relation extraction
In sentence-level relation extraction, the task is to identify binary relation across entities e 1 and e 2 in a given sentence. For instance, for EXAMPLE SENTENCE 1, given below, the task is to identify the relation Entity-Origin across entities knowledge (e 1 ) and recruits (e 2 ). EXAMPLE SENTENCE 1: "Their knowledge of the power and rank symbols of the Continental empires was gained from the numerous Germanic recruits in the Roman army, and from the Roman practice of various Germanic warrior groups with land in the imperial provinces." Accordingly, multiple sub-graphs (as shown in Figure 1) are constructed to represent a sentence, which includes (a) graph using nodes in SDP between two entities "knowledge" and "recruits" (Figure 1(ii)); and (b) graph using nodes linked to entity mentions "knowledge" (e 1 ) (Figure 1(iii)) and entity mention "recruits" (e 2 ) ( Figure 1(iv)). The SDP is defined as the dependency path in the LCA sub-tree, connecting the two entities. Figure 1(i) shows partial the dependency tree for EXAMPLE SENTENCE 1.

Cross-sentence n-ary relation extraction
While the above described method to construct multiple graphs is applicable for sentence-level relation extraction, it cannot be used in the context of cross-sentence n-ary relation extraction, where the task is to identify the n-ary relation across n-ary entities present across multiple sentences. For instance, the EXAMPLE TEXT 1 provided below is an instance of cross-sentence n-ary relation extraction, where the task is to identify ternary relation sensitivity across three entities L858R, EFGR, gefitnib present in the first, second and third sentence, respectively. EXAMPLE TEXT 1: "Furthermore, although common mutations , such as exon 19 deletions and L858R mutations in exon 21 have been associated with response to EGFR TKIs, many other mutations are detected only occasionally , and correlations with response are not defined . A recent study screened 681 cases and found 18 rare mutations; responses to EGFR TKIs were reported on a case by case basis and varied by mutation. For example, exon 20 and 21 mutations were more likely to confer resistance to erlotinib or gefitnib, while exon 18 and 19 mutations were more often associated with improved efficacy outcome." To build graph connecting multiple entities, we propose a two-fold strategy. We first use nodes in SDP between each entity term and the root term in the dependency tree to derive graphs around each entity terms, followed by adding an edge between each entity terms to obtain a full-connected graph. For example, in Figure 2, the nodes in SDP between entity terms "L858R", "EGFR" and "gefitnib" and their respective root terms "detected", "likely" and "screened" in the dependency tree of sentence 1, 2 and 3, respectively are used to create the initial graphs for three entities (entity mentions and root terms present in different sentences are shown in different colours in Figure 2), followed by adding an edge between entities. This strategy helps to build a fully-connected graph irrespective of the number of entities and sentences in the text. In addition, we also construct two sub-graphs using nodes associated with the first and the last entity in the cross-sentence instance, as described previously for sentence-level relation extraction. This method of deriving multiple sub-graphs for both cross-sentence n-ary relation instances, results in constructing three sub-graphs to represent each instance, irrespective of the number of entities and sentences present in the instance.

C-GCN over Multiple Sub-graphs
In this section, we formally describe the problem and explain the architecture of C-GCN-MG model.

Problem Formulation
Let E = [e 1 , .., e n ] be the set of entities in a text span s i ∈ S containing t consecutive sentences. S is the set of all relation extraction instances. Given E and s i , the relation extraction task is to predict a relation r from a predefined set R that holds across entities [e 1 , .., e n ] or "no relation" otherwise. In this work, we apply C-GCN-MG in two different settings: (a) when n=2 and t=1, we predict binary relation in a single sentence which forms sentence level relation extraction problem; and (b) when n ≥ 2 and t > 1, we predict n-ary relation across t sentences also known as cross-sentence n-ary relation extraction problem. In both the settings, we model the task of relation extraction as graph classification problem. Each instance s i is transformed into set of sub-graphs, upon which GCN operation is performed to learn rich node representations in each sub-graph. Using an attention mechanism, each sub-graph is transformed into a fixed dimensional vector. The attentions vectors resulting from multiple sub-graphs combined to obtain entity-centric feature vector, which is used to predict relation r for the instance s i .

Architecture of C-GCN-MG
The architecture of the proposed C-GCN-MG model shown in Figure 3 is described below.

Graph Building Layer
The input to the network is the sequence of tokens [x 1 , . . . , x m ] ∈ s i , which also consists entities [e 1 , . . . , e n ] across which holds a relation r ∈ R. For explanation purposes, in Figure 3, the input s i provided to the network is a single sentence (t = 1) comprising entities e 1 and e 2 . Initially, s i is transformed into a set of 3 sub-graphs, following the method described in Section 3, as shown in Figure 3. A set of 3 graphs are constructed for each instance irrespective of whether the input is a sentence-level binary or cross-sentence n-ary relation instance to obtain graph G(s i ) = g k i , where k = 1, 2, 3. An adjacency matrix (A) is obtained for each graph that provides information of connected nodes in the graph. An edge weight matrix (E) providing weight of the grammatical relation for edges between nodes is also obtained. The method for obtaining edge weights is further explained in section 4.2.4.

Input Encoding Layer
Each graph g k i comprise a set of tokens [x k 1 , . . . , x k m ], which also forms the nodes in the graph is encoded into a fixed-length vector by the input coding layer comprising the following embeddings: (a) contextual; (b) part-of-speech; (c) dependency; (d) named entity type; and (e) word type embeddings. For contextual embeddings, the BERT model (Devlin et al., 2018) is used. Byte-pair-encoding (BPE) tokeniser used by BERT tokenises each a word w into s BPE tokens w = {b 1 , b 2 , ..., b s } and generates L hidden states for each BPE token, h l t , 1 ≤ l ≤ L, 1 ≤ t ≤ s. The contextual embedding BERT w for word w is obtained by summing the last four layers of the BERT model: The best performance was observed when the last four layers of the BERT model were used in the experiments. In addition to contextual embeddings, for each word w, a p-dimensional feature vector is included for Part-of-Speech (POS) tags (f pos w ); dependency grammatical relations (f dep w ); and named entity types (f net w ) embeddings. Further, a q-dimensional feature vector is included to indicate whether a given word w is the entity mention or not (f wt w ). The syntactic embeddings are randomly initialised. Word-type embeddings comprise of a q-dimensional vector of ones, if the given word is an entity mention or vector of zeros if the word is a non-entity term. Thus, the input vector for each tokenx k i ∈ R d and is:

BiLSTM Layer
Previously, using a BiLSTM layer is found to be useful for fine-tuning pre-trained input word embeddings before providing them as input to GCN layer Guo et al., 2019). Although BERT provides contextual embeddings, we propose to use a BiLSTM contextual layer to further finetune input embeddings by learning sequential information available in the word order in the sentence. Accordingly, the encoded set of tokens [x k 1 , . . . ,x k m ] in the graph are initially fed as input to a contextual BiLSTM layer. As seen in Figure 3, the word sequence for terms in graph is obtained from the sentence and is provided as input to the BiLSTM layer, as experiments using full sequence showed a decrease in performance. Thus, the BiLSTM layer takes as input a series of input vectors and produces a d ldimensional hidden state vector for each input in both forward and backward directions. The BiLSTM layer is jointly trained along with the rest of the model. The output of the BiLSTM layer is given by: Here, h i ∈ R 2d l , where d l is the dimension of the hidden state of the LSTM. h i is the hidden state vector of the BiLSTM at time-step i considering both forward and backward directions.

Graph Convolution (GCN) Layer
The hidden state vectors obtained from the BiLSTM layer and the graphical structure obtained in the first step (Graph Building Layer) is provided as input to the GCN layer. Specifically, for graph g k i , the GCN takes the following inputs: (a) an input feature matrix X ∈ R n×2d l , where n is the number of nodes and 2d l is the dimensions of input features (output obtained from BiLSTM layer for each node); (b) the graph structure is provided by an adjacency matrix A ∈ R n×n , where A ij = 1, if there exists an edge from node i to node j; and (c) an edge weight vector e ∈ R 2ne , where n e is the number of edges in the graph. The dimension is 2n e as the edge vector for a given pair of nodes is considered in both directions. The edge weights are obtained as follows: Let e rg p i ,q j be the edge weight of the grammatical relation r g ∈ R g going from node i to node j. R g is the set of all grammatical relations; p and q are the POS tags of nodes i and j, respectively. Both p and q are in set P , where P is the set of POS tags seen in the dataset and p == q for nodes i and j with the same POS tag. For a given p, q ∈ P and r g ∈ R g , if pq n is the number of times the triples (p i , q j , r g ) is seen in the corpus and pq t is the total number of triples across all POS tags and grammatical relations, the edge weight from node i to node j with a given dependency relation r g is given by: e rg p i ,q j = pq n pq t Thus, the graph convolution operation to produce node features h l i ∈ R dg at layer l is given by: where W (l) and b (l) is the weight matrix and bias term, respectively for the l th layer, h l−1 are the node features in the l − 1 th layer, the initial layer H (0) = X, and σ is the non-linear function such as ReLU, d g is the dimensions of the hidden state in GCN layer. Although, the graph convolution operation helps to obtain node features h i , the resulting features do not provide a complete representation as the features of its own node are not considered by the convolution operation. To address this problem, a self-loop is added for each node in the graph (Kipf and Welling, 2016). Further, since certain nodes in the dependency graph can be high-degree nodes with higher connections, the node representation obtained from is likely to favour high-degree nodes, resulting in bias in overall sentence representation. To solve this issue, the node features are normalised by transforming the adjacency matrix A, where A is multiplied with the inverse degree matrix D (Kipf and Welling, 2016). Applying these two transformations, the graph convolution operation to produce node features h i at layer l is given by: Here,Ã = A + I with I being the n × n identity matrix, and d i = n j=iÃ ij is the degree of token i in the dependency graph. The output of graph convolution operation is the node level output Z ∈ R m ×f , where m is the number of nodes in the graph and f is the number of output features of the GCN layer. Intuitively, the feature representation of node h L i ∈ R f is an aggregation of information from the connecting neighbouring nodes and edges in the graph.

Attention Layer
Not all nodes in the GCN output would equally contribute to relation extraction. An attention layer is used to obtain a fixed length vector that best represents the graph. Thus, instead of using multiple GCN layers, a single GCN layer followed by an attention is layer is employed for this purpose. This also significantly reduce the number of parameters in the model. The attention mechanism assigns a weight α i to each node annotation h i . A fixed representation v g i ∈ R dg is computed for the entire graph, as the weighted sum of all node annotations: The final representation v for the input sequence is obtained by summing all three attention vectors (from three sub-graphs) along with hidden state vectors of entity mentions e 1 and e 2 obtained at GCN layer: where h l e 1 and h l e 2 are hidden state vectors of entity mentions e 1 and e 2 at layer l of GCN, respectively.

Output Layer
The final feature vector v ∈ R dg is used for classification and is fed to a fully connected softmax layer to obtain a probability distribution over relation labels. The cross-entropy loss for label prediction is given by: where r is the total number of relations and θ are the parameters of the model. During inference, the test sentences are represented as graphs and fed to the classifier model to predict the relation label.

Datasets and Metrics
The performance of our model is evaluated on two tasks: cross-sentence n-ary relation extraction and sentence-level relation extraction. For cross-sentence n-ary relation extraction task, we use the dataset introduced by (Peng et al., 2017) (n-ary dataset), which contains 6,987 ternary relation instances and 6,087 binary relation instances extracted from PubMed 1 . For sentence level relation extraction task, the performance of our model is evaluated on two datasets: (a) SemEval-2010 Task 8 (SemEval) dataset (Hendrickx et al., 2019); and (b) TACRED dataset (Zhang et al., 2017). SemEval is a standard dataset for relation extraction containing 10,717 examples annotated with 9 different relation types, and an artificial relation 'Other'. The dataset is split into 8,000 training examples and 2,717 test examples, with each sentence marked with two nominals, e 1 and e 2 . The TACRED dataset is a larger dataset comprising 106K instances annotated using 41 relation types and a special "no relation" types. Models are evaluated using previously used metrics. For the cross-sentence n-ary relation extraction task, test accuracies averaged over five cross-validation folds are reported following previous evaluation methods (Peng et al., 2017;Song et al., 2018;Guo et al., 2019). For sentence-level relation extraction, we report the official macro F1-Score excluding the 'Other' relation for SemEval dataset (Hendrickx et al., 2019) and for TACRED dataset we report official micro F1-scores (Zhang et al., 2017).

Implementation Details
PyTorch (Paszke et al., 2017) and PyTorch Geometric (PyG) (Fey and Lenssen, 2019) was used to build the GCN-based model. Spacy (Honnibal and Montani, 2017) was used to obtain POS tags, named entity types, and dependency relations. Since SemEval dataset has dedicated train and test sets, 10% of the training dataset was held-out for validation purposes. The hyperparameters of the model were tuned using the validation set. The model was developed using the validation set and was tested on the test set. The model was trained for 200 iterations following mini-batch gradient descent (SGD) with a batch size of 50. Word embeddings were initialised using 768-dimensional contextual BERT embeddings. The dimensions for embeddings for part-of-speech (POS), named entity tags, dependency tags was set to 40 and were initialised randomly. The dimensions for word-type embeddings was set to 10. A vector of size 10 with all entries as ones and zeros was added for entity mentions and non-entity words, respectively. The dimensions of hidden state vector in the LSTM, GCN and Attention layer was set to 256.
6 Results and Discussion

Cross-Sentence n-ary Relation Extraction
For cross-sentence n-ary relation extraction, following prior work Guo et al., 2019), the proposed model is evaluated against the following baselines: (1) feature-based classifier using lexical features in the SDP between each pair of entities (Quirk and Poon, 2016); (2) (Guo et al., 2019); and (4) in addition, following (Song et al., 2018), the tree-structured LSTM model (SPTree) (Miwa and Bansal, 2016) is also included as a baseline for drug-mutation binary relation extraction. The five-fold cross validation results of the proposed model are provided in Table 1. For ternary relation extraction (first two columns in Table 1), the proposed C-GCN-MG model achieves an accuracy of 88.3 and 88.1, on instances within single sentences and on all instances, respectively, outperforming all baselines. For binary relation extraction (third and fourth columns in Table 1), the C-GCN-MG model consistently outperforms both GS G-LSTM and AGGCN model, indicating the usefulness of the proposed model. Following prior work (Song et al., 2018;Guo et al., 2019), the proposed model is evaluated on all instances for both ternary and binary relations (last two columns in Table 1) for multiclass classification. As seen, the performance of different model significantly drops when evaluated on fine-grained classes against binary class. However the C-GCN-MG model performs better on finegrained classes models by scoring higher than SoTA models for ternary and binary multi-class relation extraction. The binary and multi-class n-ary results clearly establish the ability of C-GCN-MG to exploit the underlying graph structure by using multiple sub-graphs. While, the performance of GCN is observed to decrease with the increase in nodes , the result obtained by C-GCN-MG model, particularly on multi-class classification (Table 1) show that the use of smaller sub-graphs considerably helps fine-grained classification.

Single graph vs. Multiple sub-graphs
To further evaluate the contribution of multiple graphs for relation extraction, we examine the performance of the following two models: (a) C-GCN-SG: A C-GCN using a single graph (SG) constructed using the nodes in the SDP between the entities; and (b) C-GCN-MG: A C-GCN using multiple graphs (MG) constructed using (a) nodes in SDP; and (b) nodes associated with the entity mentions in the dependency graph. Table 4 shows that C-GCN-MG significantly outperforms C-GCN-SG, both in terms of precision and recall, by scoring an F1-score of 85.91 against 83.73 (p ≤ 0.05 under the Wilcoxon Signed-Rank Test). Using multiple graphs facilitates inclusion of additional nodes that help in identifying relations more accurately, while providing better coverage by retrieving more relevant instances. These results further confirms our hypothesis that using multiple sub-graphs with GCNs are more useful than using a single graph.

Contribution of multiple sub-graphs
To further study the contribution of multiple sub-graphs (C-GCN-MG) against single graph (C-GCN-SG), sentences in SemEval test set are categorised into three groups using distance between entities. The average number of tokens (µ) and the standard deviation (σ) over different lengths of tokens between e 1 and e 2 are used to obtain three different groups of sentences: (a) short-distance spans (j ≤ µ − σ), (b) medium-distance spans (µ − σ < j < µ + σ), and (c) long-distance spans (j ≥ µ + σ), where j Model P R F Model P R F LR (Zhang et al., 2017) 73.5 49.9 59.4 GCN  69.8 59.0 64.0 SDP-LSTM (Xu et al., 2015) 66.3 52.7 58.7 C-GCN  69.9 63.3 66.4 Tree-LSTM (Tai et al., 2015) 66.0 59.2 62.4 AGGCN (Guo et al., 2019) 69.9 60.9 65.1 PA-LSTM     is the number of tokens between e 1 and e 2 . The average number of tokens µ was found to be 3 and the standard deviation σ obtained was 9. The numbers of sentences in different categories shown in Table 5, shows that a large proportion of sentences (ca. 72%) are categorised as MEDIUM SPANS with sentences having 6 − 12 tokens between entities. The performance of C-GCN-MG and C-GCN-SG across different spans of sentences in SemEval test set is provided in Table 6, shows that C-GCN-MG achieves higher performance consistently across all three spans of sentences over C-GCN-SG. These results shows that multiple sub-graphs are extremely useful, particularly for LONG SPAN sentences with large distances between the entities. The contribution of C-GCN-MG is also significant for sentences in the MEDIUM SPANS category. However, for SHORT SPANS sentences the difference in the performance of C-GCN-MG and C-GCN-SG is less significant, indicating that a single graph is sufficient for shorter sentences.

Number of nodes used in the graph
The C-GCN-MG and C-GCN-SG models are evaluated using path-centric pruning distance  in the following three settings to examine the effect of expanding nodes in SDP: (a) K = 0: using entities in SDP; (b) K = 1: include nodes directly connected to nodes in SDP; and (c) K = ∞: use full dependency graph. The evaluation results provided in Table 7 shows that as an overall trend, the F-scores of both the models drops significantly when the nodes in the graph are added incrementally by expanding the SDP. Both C-GCN-MG and C-GCN-SG models achieve the best F-scores by using only the nodes in the SDP, corresponding to C-GCN-MG (K = 0) and C-GCN-SG (K = 0) in Table  7. The superior performance by scoring a higher recall without compromising on precision, indicates the usefulness of limiting to a minimum set of nodes in the graph. Although the use of higher number of nodes facilitates achieving higher precision, the models largely suffer from poor recall resulting in lower F-scores. Interestingly, considering multiple sub-graphs as done by C-GCN-MG models leads to better F-scores in comparison to the corresponding C-GCN-SG models, confirming our hypothesis to use multiple sub-graphs for relation extraction. The visualisation of the attention weights of nodes at the final attention layer by C-GCN-MG for a an example sentence is shown Figure 4, indicates that the model restricting to nodes in the SDP (4b.1) with lesser number of nodes facilitates finer representations for each word in the graph, with nodes besides entity mentions also contributing to the task. In the associated sub-graphs, higher weights are assigned to e 1 (school), whereas e 2 receives a lower weight, indicating that the model uses information from the corresponding sub-graphs. In contrast, when a model uses a larger set of nodes (Figure 4c.1), the contribution of words in the graph is less evident.

Ablation study
The ablation study examining different feature sets is provided in Table 8. As seen, BERT helps to achieve a significant improvement in the overall performance. The syntactic embeddings (POS, NER, DEP, word-type (WT), edge weights) helps to increase performance. In addition to syntactic embeddings, the use of edge weights are observed to boost the F1-score to 85.9. The contribution of the contextual BiLSTM layer is also significant in the overall performance, without which the model achieves a low F1-score of 78.2, showing the importance of using contextual layer to derive node features for GCN.

Conclusion
To conclude, we proposed a contextualised GCN model using multiple sub-graphs representing a sentence as against a single graph to improve relation extraction. The proposed model scores both in terms of precision and recall to achieve a higher accuracy and better coverage. The improvement in performance is observed to largely come from accurately predicting relations for instances with large distance between entities. The superior performance of the model against SoTA graph-based models on standard relation extraction datasets clearly establish the strength of the proposed model.


RESEARCH ON SEMANTIC-ASSISTED SLAM IN COMPLEX DYNAMIC INDOOR ENVIRONMENT

Visual Simultaneous Localization and Mapping (SLAM) systems have been widely investigated in response to requirements, since the traditional positioning technology, such as Global Navigation Satellite System (GNSS), cannot accomplish tasks in restricted environments. However, traditional SLAM methods which are mostly based on point feature tracking, usually fail in harsh environments. Previous works have proven that insufficient feature points caused by missing textures, feature mismatches caused by too fast camera movements, and abrupt illumination changes will eventually cause state estimation to fail. And meanwhile, pedestrians are unavoidable, which introduces fake feature associations, thus violating the strict assumption that the unknown environment is static in SLAM. In order to ensure how our system copes with the huge challenges brought by these factors in a complex indoor environment, this paper proposes a semantic-assisted Visual Inertial Odometer (VIO) system towards low-textured scenes and highly dynamic environments. The trained U-net will be used to detect moving objects. Then all feature points in the dynamic object area need to be eliminated, so as to avoid moving objects to participate in the pose solution process and improve robustness in dynamic environments. Finally, the constraints of inertial measurement unit (IMU) are added for low-textured environments. To evaluate the performance of the proposed method, experiments were conducted on the EuRoC and TUM public dataset, and the results demonstrate that the performance of our approach is robust in complex indoor environments.

INTRODUCTION
As the basis of intelligent services for robots, autonomous navigation and positioning are the frontiers of the robotics research field. Its applications are increasingly embedded in people's daily lives including autonomous parking, advanced home services, medical services, path planning and obstacle avoidance. Traditional positioning technology, such as Global Navigation Satellite System (GNSS), enables accurate outdoor positioning. However, positioning and navigation tasks cannot be accomplished in GNSS-restricted environments, especially indoor environments due to complex indoor structures and the failure to receive satellite signals.
Over the past decades, visual Simultaneous Localization and Mapping (SLAM) systems have been widely investigated in response to requirements. It provides autonomous navigation and positioning in an unknown environment since rich image information obtained by a vision sensor can be used to estimate its own motion. In an ideal environment, many visual SLAM systems have achieved high location accuracy. MonoSLAM has been developed to generate 3D trajectory of unknown scene quickly through monocular camera (Andrew et al., 2007). However, the computing efficiency is limited by the size of the scene since extended Kalman filtering is used to optimize camera pose (Hauke et al., 2012). PTAM is the first system to propose parallel computing of tracking and mapping (Klein, Murray, 2007). It is worth mentioning that nonlinear optimization instead of filters is used as backend in this system. Based on ORB SLAM (Mur-Artal et al., 2015), ORB SLAM2 system (Mur-Artal, Tardós, 2017) was developed for monocular, stereo and RGB-D camera. The structure includes feature * Corresponding author tracking of front-end modules, optimization of back-end modules, loop closing modules to identify known locations and mapping modules. It adopts Oriented FAST and Rotated BRIEF (ORB) as the feature point detection algorithm (Rublee et al., 2011). ORB SLAM2 is the representative of the feature point methods and the association between points is obtained by feature matching. The camera poses and map points position will be calculated by minimizing reprojection errors. LSD-SLAM (Engel, Cremers, 2014), as one of the direct method SLAM systems, optimizes the camera pose and 3D points coordinates by constructing a photometric error function, without the correspondence between points. It achieves a semi-dense scene reproduction on the CPU. The emergence of DSO (Engel et al., 2018) makes the direct method more mature, which uses fully direct method. It proposes photometric calibration to solve the effect of light on the direct method, Photometric parameters of uncalibrated cameras will be dynamically estimated. These make the direct method more robust.
In recent years, visual SLAM has gradually merged with various sensors (Heng et al., 2018). The integration of inertial measurement unit (IMU) measurements and visual SLAM can overcome the shortcomings of the arbitrary scale of the monocular system (Mur-Artal, Tardós, 2017). The sliding window strategy has been used in most Visual Inertial Odometer (VIO) systems (Dong-Si, Mourikis, 2012). VINS (Li et al., 2017) is a system based on semi-direct method, which uses optical flow for front-end tracking, but the back-end is still optimized for reprojection error.
The above SLAM systems have achieved high location accuracy under ideal circumstances. However, traditional methods which are mostly based on point feature tracking, usually fail in harsh environments. Previous works have proven that insufficient feature points caused by missing textures, feature mismatches caused by too fast camera movements, and abrupt illumination changes will eventually cause state estimation to fail. And meanwhile, pedestrians are unavoidable, which introduces fake feature associations, thus violating the strict assumption that the unknown environment is static in SLAM. With the development of deep learning technology, researchers can accurately obtain the semantic information and geometric information of the scene at the same time, which is helpful for us to recognize the dynamic objects in the scene and eliminate their effect (Bescos et al., 2018).
In recent years, the semantic SLAM, which has the ability of scene understanding, assists mapping and positioning through accurate understanding of object targets in the environment (Bowman et al., 2017). The results of semantic segmentation and object detection can provide SLAM with higher-level information (Zhi, 2019). It provides an understanding of the surrounding environment. Semantic SLAM focuses on the incremental storage of image sequences and the update of semantic information (Civera, et al., 2011), as well as the fusion of multi-view semantic labels. The CNN-SLAM (Tateno et al., 2017) predicts both depth and labels at the same time, realizes label fusion and integrates the predicted depth information into SLAM, so that it can restore the true scale and obtain a semantically consistent map. At present, researchers mostly use the probabilistic model for data association, and correctly match the target object detected in the image to the existing 3D object of this category in the map data.
In order to ensure how our system copes with the huge challenges brought by these factors in a complex indoor environment, this paper proposes a semantic-assisted VIO system towards low-textured scenes and highly dynamic environments. Our approach is committed to the improvement of the system from the following two aspects: (1) The constraints of IMU are added for low-textured environments and (2) the geometric consistency of the system is improved by semantic information provided by deep learning technology in the highly dynamic environments.

METHODOLOGY
As shown in Figure 1, we propose a semantic-assisted VIO system, which contains the following two aspects: (1) Firstly, feature extraction and semantic segmentation are performed. Semantic segmentation is used to identify dynamic objects and eliminate the effects of outliers, and finally obtain reliable feature points. (2) After eliminating outliers, the joint optimization of IMU measurement errors and reprojection errors ensures the system to acquire good pose calculation results.

Semantic SLAM
In this section, we will introduce the combination of traditional SLAM system and semantic segmentation module. The feature extraction module and outlier filtering module of the traditional SLAM system will be used. In addition, we introduced the semantic module, which will assist the system to identify dynamic objects and finally filter outliers based on the object level.

Semantic segmentation:
Our system adopts U-net based on PyTorch to provide pixel-wise semantic segmentation. The U-net trained on PASCAL VOC dataset could segment each image. In real life, people are most likely to be dynamic objects, so we assume that feature points extracted from people are most likely to be outliers. Figure 2 shows segmentation results of sitting people and walking people. The state of the person reflects the level of the dynamic environment.   figure 3 shows the results of traditional SLAM feature extraction.
The matched feature points will be used to calculate the camera poses. However, we can know that people in motion will also be extracted to the feature points. In order to obtain reliable poses, it is necessary to ensure that the feature points involved in the pose calculation have accurate data associations. RANSAC method tests the data for consistency by random sampling and iterate continuously. Although it can filter out some outliers, it does not consider the connection between samples in a multiobject motion scene, that is, the points on the same rigid body have the same motion state. But the semantic segmentation has the advantage of identifying whether points are on the same object.

Outlier elimination:
The result of semantic segmentation provides semantic level information for visual SLAM. People are regarded as potential dynamic objects, and feature points existing on potential dynamic objects will be eliminated to reduce the impact of mismatch. Descriptors are only calculated for the remaining key points to perform the feature matching process. The right side of Figure 3 shows the results of our system feature extraction.

VIO
As mentioned in the introduction, low-texture environments and abrupt illumination changes will be inevitable in the real world. However, such scenes are either insufficient in feature points or mismatched, which ultimately leads to the failure of pose estimation. Figure 4 shows the complex environment in a room. This shows the disadvantage of the camera: it is greatly affected by the external environment. Compared with the camera, IMU has the characteristics of small error accumulation in a short time and is not affected by the external environment. Therefore, multi-sensor fusion has become the trend of research.
When the IMU performs navigation alone, it needs to remain stationary for a period of time for initialization. In fact, the SLAM system does not provide enough initialization time for IMU. Therefore, the visual information will be used to assist IMU initialization as most VIO systems. The initialization process will be described in detail later.
The scale obtained by traditional monocular SLAM is arbitrary. Figure 5 shows the trajectory graph predicted by ORB SLAM2 system. The IMU measurements can assist the monocular system to obtain the true scale. In this section, we introduce the VIO system in detail.

IMU initialization:
The IMU data will be processed concurrently with the image data. The method of obtaining IMU measures with visual assistance is mainly performed by calculating the camera poses of the first few frames. That is, first, the gyro deviation can be obtained from the relative direction between the two frames. Then the scale factor and gravity approximation will be calculated from the gyro deviation if accelerometer deviation is ignored. After that, the acceleration is taken into consideration to get the accelerometer deviation, the corrected scale factor and gravity. This completes the initialization process.

Tracking:
Reliable camera pose will be predicted with IMU. The map points in the local map are projected and matched with reliable feature points from the previous section. Then the IMU error terms and reprojection errors of all matched static feature points are jointly optimized to calculate the camera pose. When there is a map update from the Local Mapping or Loop Closing thread, these two errors are calculated as follows for the current frame j and last key frame i: (1) * = argmin(∑ proj ( , ) + IMU ( , ) k ) ( 2) where , , are the orientation, position and velocity of IMU respectively, and g , a are biases of the accelerometer and gyroscope respectively. When there is not a map update, for frame j + 1: , , , +1 , +1 , +1 , +1 , +1 } (10) * = argmin(∑ proj ( , + 1) + IMU ( , k + 1) + proj ( ))

Local mapping:
Compared to traditional visual SLAM, the local window of our system is determined by the last few key frames since the IMU errors are cumulative. Thus, IMU error terms and reprojection error terms are cost functions to further optimize the local window. Old frames that can observe map points only provide visual constraints. In this way, IMU measurements provide constraints for pose calculations to improve performance in low-textured.

EXPERIMENTS AND RESULTS
To evaluate the performance of the proposed method, experiments were conducted on the TUM public dataset and EuRoC public dataset. The low-texture scenes and highly dynamic environments have been encountered.
The fr3 image sequences in the TUM dataset contain sitting and walking people. Datasets are classified into low dynamic environment and high dynamic environment according to the state of people. This can be used to detect the impact of dynamic objects on the positioning result.
The EuRoC dataset consists of three scenes and 11 sequences, including abrupt illumination changes, fast camera movement and low-textured environments. The datasets are divided into three levels of easy, medium and difficult according to the above situation. Compared with the monocular visual system, our system not only obtains the observability scale, but also improves the global positioning accuracy.
The results of the two datasets will be analysed separately. In order to illustrate the resistance of our system to dynamic objects, we selected five sequences on the TUM dataset and ran them on ORB SLAM2 system and our system respectively. Table 1 illustrates the positioning results of sequences. The first two sequences are low dynamic environments and the last three sequences are high dynamic environments. The RMSE reflects the robustness and accuracy of the system, and S.D. reflects the stability of the system.
From the Table 1, it can be seen that whether it is a low dynamic environment or a high dynamic environment, compared with the ORB system, the RMSE and S.D. of our system are reduced. It proves that our system performance has been improved, especially in high dynamic environment.
In order to express the ability of our system to resist dynamic environments, the positioning results will be visualized. We show the predicted trajectory and the real trajectory of fr3_sitting_static and fr3_walking_rpy in the following figures.  The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XLIII- B4-2020, 2020XXIV ISPRS Congress (2020 They are representatives of low dynamic environment and high dynamic environment respectively. Figure 6 shows the trajectory of fr3_sitting_static predicted by ORB SLAM2 and our method. It can be seen from the Table 1 and Figure 6 that the performance in the low dynamic environment has improved even if it is small. Figure 7 and Figure 8 are used to clearly express the difference in system positioning accuracy. Figure 7 shows the trajectory of fr3_sitting_static projected in xyz direction. It can be seen from the Figure 7 that although the errors of the two systems are similar in low dynamic environment, the trajectory predicted by our system is closer to the true trajectory. Figure 8 shows the predicted Euler angle. Obviously, the performance of our system is better than ORB SLAM2. Figure 9 shows the trajectory of fr3_walking_rpy and fr3_walking_half projected onto the plane in high dynamic scenes. As can be seen from the figure, the positioning error of the ORB SLAM2 is large in the high dynamic environment, which is quite different from the real trajectory. It proves that the positioning result is disturbed by dynamic objects in the traditional SLAM system. However, as can be seen from Figure  9, our system can greatly reduce the interference of dynamic objects. It is consistent with the results in Table 1 that the improvement of positioning performance in high dynamic scene is very obvious. Table 2 shows the results of experiments conducted on the EuRoc dataset. The environment of the EuRoc dataset is shown in Figure 4. Five sequences were selected for experiments to illustrate the resistance of our system to complex environments. (a) Trajectory of fr3_walking_rpy (b) Trajectory of fr3_walking_half Figure 9. Trajectory predicted by ORB_SLAM2 and our system. Figure 10. Trajectory graph of MH03 predicted by ORB_SLAM2 and our system. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XLIII-B4-2020, 2020 XXIV ISPRS Congress (2020 edition) As can be seen from the Table 2, in the five sequences, the RMSE and S.D. of our system are mostly lower than the ORB SLAM2 system, which proves that the stability and robustness of our system is better than the ORB SLAM2 system. Figure 10 plots the trajectory of MH03 sequence predicted by the ORB SLAM2 system and our system respectively.
For the MH03, the maximum ATE of ORB SLAM2 is 0.101m, and that of our method is 0.059m. The trajectory predicted by our system is closer to the real trajectory than ORB SLAM2 system. In order to show the performance of the system more clearly, the trajectory error graph is displayed in Figure 11 and 12.

CONCLUSION
In our paper, a VIO system based on semantic assistance is proposed. Compared with the traditional visual SLAM, it has a module for semantic recognition of dynamic objects, and its performance is improved in dynamic environment by removing feature points on dynamic objects. In addition, the joint optimization of IMU measurement errors and reprojection errors ensures the system to acquire good pose calculation results under low-textured environment. Experiments prove that the performance of our system has been improved in a complex indoor environment. In the future research, we will introduce semantic data association, that is, the fusion of semantic labels of static objects to the proposed system, and a semantic consistency map will eventually be established. Figure 11. Trajectory of MH03 projected in xyz direction Figure 12. Euler angle of MH03 predicted by ORB_SLAM2 and our system.


extfieldsofstudy:
Computer Science
Business

text:
Vulnerability Evaluation Method for E-Commerce Transaction Systems With Unobservable Transitions

E-commerce transaction systems have become an important factor in trading activities. However, e-commerce systems are still undergoing development. Unobservable actions and attacks on systems are frequent problems that increase the vulnerability of e-commerce systems. Most existing approaches to addressing these issues cannot describe or analyze the overall structure of a local specification and unobservable actions well. The vulnerable e-commerce transaction net (VET-net) is a useful model for describing the unobservable actions, online transactions and third-party payment platforms of e-commerce systems. Based on a VET-net, we focus on the detection and evaluation of e-commerce transaction systems to attacks. We propose the concept of vulnerable transitions, which include not only vulnerable actions but also unobservable transitions. Then, we use an improved slice method to locate the vulnerable transitions. For these vulnerable transitions, we propose a vulnerable transition evaluation method based on a hidden Markov model along with a reachability graph (HMM-RG). The HMM-RG uses hidden Markov models (HMMs) to approximate the state reachability graph of a VET-net. By calculating the firing probability, the HMM-RG can evaluate the vulnerability degree of malicious states. We use a real-world case to show our method’s effectiveness and reasonability.

I. INTRODUCTION
With the development of e-commerce, an increasing number of people are paying attention to the study of economic systems. Due to the imperfect nature of the e-commerce system itself, there are many problems in managing e-commerce systems [1]. There are some useful modeling methods to describe e-commerce systems, such as those of [2]- [8]. Du et al. [2] use a labeled Petri net (LPN) to analyze the obligation and accountability of cooperative systems and extend the LPN to a labeled workflow net (LWN) to model e-commerce workflows. However, they do not consider the The associate editor coordinating the review of this manuscript and approving it for publication was Zhiwu Li . three parties (shopper, merchant, and third-party payment platform (TPP)) involved in the transaction. Yu et al. [4], [6] propose an e-commerce business process net (EBPN) to construct an e-commerce business process. Based on the EBPN, they describe malicious behavior patterns in [5]. The behavior patterns represent potential attacks that violate security [5]. However, they are not suitable for vulnerable e-commerce systems with unobservable actions. For a safe system, there are methods that can be used to diagnose insecurity for users, such as those of [9]- [11]. In fact, this premise of system security is idealized. Most of the time, an e-commerce system is not completely secure. Thus, it is important to analyze vulnerable e-commerce systems. For a vulnerable e-commerce system, our previous VOLUME 8, 2020 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ work [12] proposes vulnerable e-commerce transaction nets (VET-nets). VET nets consider both normal actions and malicious actions. Malicious actions include attacks and unobservable actions. In this paper, we use VET-nets as modeling tools. For a VET-net, we know that if we provide a known attack form, we can locate the cause of the attack form in an e-commerce system using, e.g., the methods in [12]- [14]. Depending on the attack, there are vulnerable points used to complete the attack process. In fact, there may not be only one of these points. Some points are closely related to these unobservable transitions. These actions may play different roles in a VET-net. The different effects can be represented in terms of the effect degree. This effect degree is called the vulnerability degree. Existing methods mainly aim at observable system attacks, and they are suitable for vulnerability diagnosis from observable activities. For some unobservable activities and unpredictable attack forms, these methods are not applicable. From the perspective of observed actions, one only analyzes these unobservable states of malicious activity. Such a method ignores the effects of unobservable activities that lead to a malicious state. It cannot perform the appropriate adjustment of the e-commerce system. In other words, the system mostly performs analysis after malicious activity, and it does not prevent the effects. It is mostly postmortem analysis. It has difficulty preventing attacks. Another method only considers unexpected attack forms and ignores unobservable actions. It is not good for testing the e-commerce system itself. So our goal is to address two issues (i.e., unknown attacks and unobservable actions). The starting point of security practices for e-commerce systems is to evaluate their vulnerability. When a potential threat exploits the vulnerable actions of the system, it can lead to the destruction and damage of the system. Vulnerability assessment is a process of interpretation and vulnerability analysis. The purpose of vulnerability assessment is to find and control vulnerability. In fact, if we can control these unobservable actions and assess the occurrence probability of each path to the final condition, we can diagnose and assess the e-commerce system. Therefore, we emphasize unobservable actions.
Our goal is to determine how to use a formal method to identify the vulnerable actions of a VET-net system and to give a formal calculation method for the vulnerability degree of a VET-net. The contributions of this paper include: 1) We propose the concept of vulnerable transitions, which includes not only vulnerable actions but also unobservable transitions. We present a new method to locate the vulnerable transitions of a VET-net. 2) We use hidden Markov models (HMMs) to approximate the state reachability graph of a VET-net. Based on this, we give a vulnerable state evaluation method for a VET-net. Fig. 1 shows the framework of our methods. In the first stage, by capturing the user transaction behaviors of the e-commerce trading process, we analyze the observable and unobservable actions and then construct a VET-net model. Based on the VET-net, we can find all paths to the final condition; then, according to the characteristics of behaviors, we can locate the vulnerable actions of VET-nets, locating the source of fragility of the trading system for the user in the second step. In the third step, we can obtain a hidden Markov model according to the reachability graph of the VET-net. According to the hidden Markov model and reachability graph, we can compute the vulnerability degree of the VET-net.
The remainder of this paper is organized as follows: Section II discusses related work. Section III reviews some basic concepts and definitions as the basis of the study. Section IV proposes a vulnerability analysis and evaluation method. In Section V, we provide and analyze a real e-commerce example. Finally, we conclude in Section VI.

II. RELATED WORK
Some researchers have studied vulnerability detection and assessment. Some studies on vulnerability diagnosis, for example, Emeka and Liu [15] proposed a method to identify software security vulnerabilities. However, their work mostly concerned software rather than systems themselves. Xu and Nygard [7], Fang et al. [16] proposed a method to locate change based on behavioral profiles. They determined the different parts by comparing the differences between two models. However, this method was based on two models, and it was not suitable for a single model. In fact, in most cases, we do not know the meta-model. In our previous work [12], [13], we proposed a method to diagnose the vulnerability of a model. At the same time, we provided a method to locate the vulnerable points. However, this method could not evaluate these vulnerable points. Allodi and Massacci [17] considered two-stage attacks and escalated the attacks. The escalated attack could be performed by exploiting local vulnerabilities in the target. Wang et al. [18] proposed a method for fault diagnosis of a timed Petri net (TPN). They used a fault diagnosis graph to diagnose an observable TPN. Li and Hadjicostis [19] proposed a method for estimating the minimum initial marking in labeled Petri nets. They used this method to determine the minimum number of resources. Prakash et al. [20] proposed a method to perform online fault detection and isolate multiple faults. They analyzed global and local faults by using the global fault sensitivity signature matrix (GFSSM) and fault sensitivity signature matrix (FSSM). Lefebvre [21] proposed a diagnosis decision method by analyzing observation sequences. However, this method was suitable for observable actions.
Some studies on vulnerability diagnosis, for example, Al-Dwairi and Kamala [22] used security, privacy, design, and content to evaluate the quality of B2C e-commerce websites. They gave an evaluation pattern for B2C e-commerce. However, for an arbitrary e-commerce system, they did not give a clear determination and evaluation method. Wang et al. [23] proposed a vulnerability evaluation method based on the attack graph. This method could address lowcomplexity attack paths. However, it could not address attack paths with unobservable activities. Fonseca et al. [24] gave a method and a tool to evaluate security mechanisms. This method could determine the possibility of injecting realistic vulnerabilities in a website. However, this diagnostic method was suitable for the process model itself. Pedroni [25] analyzed uncertainty modeling and quantification methods to assess reliability and risk. The analysis compared advanced methods for the modeling, simulation and analysis of safety-critical systems and infrastructure under uncertainty. Khalid et al. [26] examined the degree of customer satisfaction with an e-commerce system. They used a modified American customer satisfaction index (ACSI) model to describe 149 online data points. They showed that customer expectations and e-commerce service quality could affect perceived value. Najafi [27] introduced e-trust building models and provided a method to enhance e-commerce security. Grejner-Brzezinska et al. [28] proposed a method based on spatial positioning, navigation, and timing (PNT) to analyze accuracy, continuity, and reliability. Cabasino et al. [29] used Petri nets based on the notions of minimal explanations and markings to diagnose DESs. They assumed that fault events could be modeled by observable transitions. This method was suitable for observable transitions. Hu et al. [30] proposed a method based on active diagnosis to enhance the diagnosability for a finite state automaton. This method had the computational advantage than the diagnoser-based ones, but it was not suitable for unobservable transitions. Basile et al. [31] proposed a state estimation and fault diagnosis method for a labeled-time Petri net. They used a modified state class graph (MSCG) to perform fault diagnosis. Shoukry et al. [32] proposed a method to evaluate security. They used satisfiability modulo theory to address the complexity of secure state estimation. Bonhomme [33] proposed a method to assess the marking of an unlabeled P-time Petri net with unobservable transitions. This method used the candidate firing sequences to estimate the marking. Koga et al. [34] used the full-state and associated output feedback control law to control and estimate the one-phase Stefan problem. Hu et al. [35] proposed a method to determine the optimal marked signal distribution. They used a given distortion constraint and expected embedding rate to obtain the optimal distribution.
Although these methods have their own advantages, they are not suitable for detecting the vulnerabilities of unobservable actions. Overall, no sufficient vulnerability assessment methods exist for VET-nets. Thus, in this paper, we focus on vulnerability assessment methods for VET-nets.

III. PRELIMINARIES
This section describes the basic concepts and definitions used in this paper. For more details, the definitions of Petri nets and labeled Petri nets can be found in [16], [36]- [47]. For the definitions of the hidden Markov model and Bayes' theorem, we can refer to [48]- [58].
The triple N = (P, T , F) is a net, if it satisfies the conditions : where dom(F) = {x ∈ P T | ∃y ∈ P T : (x, y) ∈ F} and cod(F) = {x ∈ P T | ∃y ∈ P T : (y, x) ∈ F} P and T are two disjoint sets called the set of places and set of transitions, respectively. F is the flow relation of N .
A Petri net satisfies the following enabling and firing rules: iii) If there exist transitions t 1 , t 2 , and · · · , t k and markings  called a reachability marking set and satisfies the following two conditions: A labeled PN is a 3-tuple G L = (N , , L), which is a labeling function that assigns a label (which can be the null label ε) to each transition.
To better describe the abnormal actions containing unobservable behaviors in the electronic transaction process, our previous work [12] proposes a vulnerable e-commerce transaction net (VET -net).
Definition 1 (VET-net [12]): A VET-net is a 10-tuple 1) (P, T , F, M 0 ) is a Petri net; P is a finite set of places, p I ∈ P is a source place satisfying · p I = ∅ and p F ∈ P is a sink place satisfying · p F = ∅; 2) A is a finite set of actions; where yo represents an observable input, no represents an unobservable input, yf represents an observable output, and nf represents an unobservable output.
The dotted box represents an unobservable transition. The dashed-line box represents an observable transition. Fig. 2 shows four simple VET -nets. In Fig. 2(a) The enabling and firing rules can refer to GSPN [36] and literature [12].
In fact, from the definition of VET-net and GSPN, it is not difficult to see the difference between the two is that VET-net focuses on considering both normal actions and malicious actions. Hence, it is possible to use the PIPE tool to analyze its firing sequence and reachability analysis. An attack [59]- [62] is a sequence of actions a 1 .a 2 · · · a n ∈ T such that there exists an elementary path from some initial state induced by a 1 · · · a n that reaches the set G. Fig. 3 characterizes the attack. Based on the attack, vulnerable points can be obtained. Then, the vulnerable transitions can be computed.
A vulnerable point [12] is a point that induces an attack. Accordingly, a vulnerable transition is a transition triggered by a vulnerable point and an unobservable transition.
For example, in Fig. 2(a), the unobservable transitions t 1 , t 2 , t 3  5) π = {π 1 , · · · , π n }, π 1 = p(X 1 = q j ) is the initial state distribution. For 1), we use s t to denote the hidden state at time t, and the value of s t is an element in the set X . For 4), let us suppose that X = X 1 , · · · , X t ; then, b ij (k) = p(X t = O k | s t−1 = q i , s t = q j ).

IV. VULNERABILITY ANALYSIS AND EVALUATION A. VULNERABILITY ANALYSIS
According to the definition of vulnerable transitions, if we locate the vulnerable points of the VET-net, we can compute the vulnerable transitions. We are inspired by the idea of slices [64], [65]. We assume that the malicious state is the final state, and the vulnerable points are the points in a slice of a VET-net that lead to malicious states. Algorithm 1 is the method to locate the vulnerable transitions.
Theorem 1: Algorithm 1 is correct and can be terminated. Proof: Steps 1-33 absorb all conditions of firing path relations. If there is not only one path to P q , then V P is P q , as shown steps 8, 18. If there is some common path C to P q , then V P = slice(M i−1 , C, P q ) by step 6. Steps 34-35 satisfy the definition of vulnerable transitions. If there is another common path to P q , then the set of vulnerable points is the whole set P, according the definition of slice, vulnerable point and vulnerable transition. Therefore, Algorithm 1 is correct. There are eight decision conditions, at Steps 4, 5, 7, 14, 15, 17, 24 and 26, that are used to determine the firing sequences. The firing sequences σ i are finite sets. Then, the algorithm moves backward by adding a new firing sequence to the slice and removing the current slice until it is empty. Thus, Algorithm 1 will terminate. Algorithm 1 is the process of locating vulnerable transitions. The input of Algorithm 1 consists of a VET-net, reachability graph, unobservable transitions set and goal state set. Given such input, it always terminates.

Algorithm 1 Vulnerable Transitions Location Algorithm
Input: VET −net, reachability graph RG, unobservable transitions set U T , a goal state set P q . Output: Vulnerability transitions set V T . 1 for all firing sequences σ 1 , σ 2 , · · · , σ n from M 0 to P q do 2 V P = ∅; transitions set is as follows: Property 1: It takes polynomial time to compute V T of a bounded VET-net.  Fig. 2(a) in PIPE tool. Proof: For a bounded VET-net, the number of places, transactions, arcs and firing sequences are all finite. Let |P| be the number of places, |T | be the number of transitions, |F| be the number of arcs in the VET-net and |σ | be the number of firing sequences. Then, we can see that most of the time is spent computing vulnerabilty transitions. In each sequence, there are at most |T | transactions and at most |T | + 1 states. Therefore, the first step computes the first sequence σ 1, which requires σ − 1 operations. The second step computes the sequence σ 2, which costs |σ | − 2 operations, and the third step computes the sequence σ 3, which requires |σ | − 3 operations. We continue with similar calculations until the last sequence σ |σ |. Thus, the total computing time is [(|σ − 1||σ |)/2]. In addition, each sequence has at most |T |+1. And we can see that the time of computing unobservable transitions at most need spent |T |. Hence, the V T can be constructed in polynomial time (i.e., O([((|T | + 1)(|σ | − 1)|σ |)/2])).
Similarly, for Fig. 2(c), the vulnerable transitions set is as follows: In fact, we find that the vulnerable transitions sets of Figs. 2(a), (b), (c) and (d) are the same set {t 1 , t 2 , t 3 , t 4 , t 5 }. In Fig. 2(c), the vulnerable transition t 2 occurs two times. However, in Figs. 2(b) and (d), the vulnerable transition t 2 occurs only one time. To distinguish these conditions, we give the evaluation method for these vulnerable transitions in section IV. B.

B. VULNERABILITY EVALUATION
The whole computation process is as follows: 1) use the PIPE tool to obtain the reachability graph; 2) compute the occurrence probability of vulnerable transitions based on the hid- and an observed label sequence ω ∈ * (i.e., ω ∈ * , ω = ε), according to [66], we know a priori probability for each initial marking, i.e., P r (M (i) Given a sequence of observations ω, along with their a posteriori probabilities, we can obtain  | ω) is a posteriori probability. l:M (l) ∈C r (ω) p (l) (ω) = 1. For ω = ε, S r (ε) = ε and C r (ε) = M 0 .
We will denote these probabilities by 0 to indicate that the VET-net started at the initial marking M (j) 0 and the sequence of transitions s (k) occurred.
Given a sequence of observations ω, we can obtain the conditional probabilities p (l) (ω), where l is an arbitrary index in C r (ω)). The only possible firing sequences are sequences in the set S r (ω). Since the sequences in the set S r (ω) are not prefixes of each other, the probability of observing ω is The probability of observing ω is the sum of the joint probabilities Pr(s (k) , M (j) 0 ) [66]. For each marking M (l) ∈ C r (ω), we can calculate using Bayes' rule and (4): According to [66], we can obtain an associated probability p M (t) that indicates the a priori probability that t fires at M . In addition, t∈T : Then for k ≥ 2, we have We see that the marking M in the above definition satisfies M ∈ C r (e i 1 e i 2 · · · e i k ). Thus, we have C r (e i 1 e i 2 · · · e i k ) = {M ∈ N n | ∃S ∈ T * T 0 , ∃M ∈ C r (e i 1 e i 2 · · · e i k ) To obtain C rP (e i 1 e i 2 · · · e i k ) by recursion based on C rP (e i 1 e i 2 · · · e i k−1 ), let ω = e i 1 e i 2 · · · e i k−1 and ω = e i 1 e i 2 · · · e i k = ω e i k , we can focus on calculating the numerator of the expression in (7), i.e., where p u stands for an unnormalized probability. Using this decomposition for each string s (k) ∈ S r (ω), we can write the second sum as follows:  Then, according to (13) and (14), we have We take Fig. 2 as an example. The Markov chain model of Fig. 5 is shown in Fig. 6. For Fig. 6(a) In Fig. 6(a), we know that observation α occurs via a transition sequence of (t1t2) * t3 or (t1t2) * t5, which leads to the marking M (1) or M (3) . We can calculate the unnormalized probabilities p (1) u (α) and p (3) u (α) as follows: Similarly, we know that observation αβ occurs via a transition sequence of (t1t2) * t3t4, which leads to the marking M (3) . VOLUME 8, 2020 We can calculate the unnormalized probability p The normalized probabilities of Fig. 6 are given in Table 1.

V. CASE STUDY
In 2015, a Tmall fraud case occurred in Mongolia in China. This process is shown in Fig. 7. We provide a description of this case [12]. First, B obtains the buyers' and sellers' contact information through a Trojan. Second, B tells seller C to help A change this information. Then, B implants a Trojan program into A's computer and transfers A's money to a1. Then, B uses a1 to buy cards and builds a Tmall shop. B transfers money from a1 to a2 as in a normal transaction [12]. The VET-net model of Fig. 7 is shown in Fig. 8. Table 2 describes the meaning of the transitions in Fig. 8. We use PIPE to construct a reachability graph, as shown in Fig. 9. Figs. 10 and 11 show the overview of the transition sequences. In Fig. 10, the horizontal axis shows each state, and the vertical coordinates show the number of sequences. According to 10, there are 504 firing sequences to reach state S 47 . In Fig. 11, the horizontal axis shows the number of layers. Layer 1 indicates the first layer, including     a15, a21, a22, a23, b22, b23, c14 that can trigger to reach S 47 . σ 1 σ 2 · · · σ i σ j = ∅; there is not only one path to S 47 , and ∀p ∈ P.M i−1 (p) ≥ M i (p). Then, according to Algorithm 1, The vulnerable transitions set is as follows: The normalized probabilities are given in Fig. 12. In Fig. 12, yellow shows the firing probability of transitions in each sequence, and blue shows the firing probability of transitions in all sequences. We can see that the probability of the transitions a15, a21, a22, b22, b23, c14 is 1 in each sequence. The probability of transitions a23 and b23 in each sequence is 0.1190 and 0.8810, respectively. The probabilities in all transitions are 0.125, 0.235119047619048, 0.264880952380952, 0.0148809523809524, 0.125, 0.110119047619048, and 0.125.

VI. CONCLUSION & FUTURE WORK
Due to the short times involved in online transactions and online payment platforms, online trading processes and trusted behavior issues are emerging along with the rapid development of online shopping and have gradually become a bottleneck in network trade development. Many e-commerce software systems are not mature and reliable, and they have flaws and mistakes that can be used by invaders. This leads to the emergence of security vulnerabilities and loss of user funds. This paper is motivated by the trusted behavior issues faced by these vulnerable network trade systems. Due to the uncomplicated graphical representation of a labeled Petri net, it can describe the overall structure of a local specification and unobservable actions well. However, the formal definition of its components can be used to provide precise abstraction. The VET-net is a subclass of labeled Petri nets. It can be used to model and simulate vulnerable e-commerce systems with unobservable actions. In this paper, on the basis of VET-nets, we describe the concept of vulnerable transitions, which include not only vulnerable actions but also unobservable transitions. Based on the concept of a slice, we then present a new method to locate the vulnerable transitions of a VET-net. We use hidden Markov models (HMMs) to approximate the state reachability graph of a VET-net; this is called the HMM-RG method. Based on the HMM-RG, we describe the vulnerable state evaluation method of VET-nets. The vulnerable state evaluation method addresses the original problem. The proposed method is suitable for verifying and evaluating an online transaction system. It can also be used to verify simple e-commerce systems. The advantages of these methods are in dealing with unobservable actions. The proposed vulnerability assessment method can help designers analyze, diagnose and evaluate system vulnerabilities. Thus, the proposed method can be readily used in the system design and analysis of industrial online transaction business processes. Due to neglecting data information, the methods are not suitable for some e-commerce systems, e.g., EBPN [4], [6], [13]. Regarding future work, there are other problems that require study related to the vulnerability evaluation of e-commerce systems, such as evaluation of data information and attack prevention.