To some extent, texts can be represented in the form of graphs, such as dependency graphs in which nodes represent words and edges represent grammatical dependencies between words. Graph representation of texts is an interesting alternative to string representation because it provides an additional level of abstraction over the syntax that is sometime easier to compute. In this paper, we study the use of graph mining methods on texts represented as dependency graphs, for extracting relationships between pairs of annotated entities. We propose a three step approach that includes (1) the transformation of texts in a collection of dependency graphs; (2) the selection of frequent subgraphs, named hereafter patterns, on the basis of positive sentences; and (3) the extraction of relationships by searching for occurrences of patterns in novel sentences. Our method has been experimented by extracting disease-symptom relationships from a corpus of 51,292 PubMed abstracts (428,491 sentences) related to 50 rare diseases. The extraction of correct disease-symptom relationships has been evaluated on 565 sentences, showing a precision of 0.91 and a recall of 0.49 (F-Meaure is 0.63). These preliminary experiments show the feasibility of extracting good quality relationships using frequent subgraph mining.
In many domains such as biomedical research, text is a major source of
information; unfortunately text corpora are frequently too large to be fully considered
manually [
Texts may be represented at di↵erent levels: words, bag of words, sequences of words, syntactic trees, graphs (dependency graphs); and they may be enriched by some linguistic features: part of speech, syntactic or semantic features. In this paper we study how text, represented in the form of graphs, can be processed with simple graph mining methods, to perform RE.
Frequent Subgraph Mining (FSM) is a graph mining method that extracts
frequently occurring subgraphs either from a single graph or a set of graphs [
The paper is organized as follows: Section 2 presents background elements regarding graph mining. Section 3 introduces our three step method. Section 4 reports experiments of our method on the extraction of disease–symptom relationships. Section 5 presents related works and Section 6 discusses the interest of using graph mining for RE. 2
A graph is defined as a pair G = (V, E) where V is a set of vertices (or nodes) and E is a set of edges connecting vertices such as E ✓ V ⇥ V . A graph is a directed graph when edges are oriented pairs of vertices. A graph is a labeled graph when vertices and edges are associated with labels. 2.1
S = (SV, SE) is a subgraph of G if SV ✓ V and SE ✓ E. Given a graph collection G = {G1, G2, ..., Gk}, with Gi = (Vi, Gi), and a minimum support min sup, the Frequent Subgraph Mining task (denoted FSM) extracts the collection of subgraphs S = {S1, ..., Sn}, with Si = (SVi, SGi) that occur in G with a support greater than min sup. The support of a subgraph Si is the number of its occurrences in G1. 1 The relative support of Si is ||SGi||
FSM algorithms are mainly based on two distinct approaches: Apriori -based
and pattern growth-based approaches. Apriori -based graph mining algorithms
share similarities with Apriori-based frequent itemset mining algorithms [
gSpan gSpan is a FSM algorithm that processes undirected labeled graphs. Given a collection of such graphs, gSpan returns the set of frequent subgraphs and their support. To generate this result, gSpan generates a Tree Search Space (TSS) that is composed of all trees and subtrees that rely in the collection of graphs. gSpan represents each tree of the TSS using a specific encoding, named minimum Depth-First Search (DFS) Code. This code is unique for each tree because it is constructed following the unique DFS traversal that follows the lexicographic order of vertex labels.
gSpan follows a pattern-growth mining approach, i.e., expends at each iteration a frequent graph with a new edge, trying every potential position. An issue with this approach is that the same graph can be discovered several times from di↵erent frequent graphs. gSpan avoids this problem by introducing a right-most extension technique, where edge extensions only takes place on a specific position determined by DFS Codes. 3
We propose an original method based on FSM to extract relationships from text. Figure 2 depicts an overview of this three step method. Each step is detailed in next subsections. 3.1
This step aims at transforming a collection of texts into a collection of Dependency Graphs (DG). To achieve this, texts are submitted to the following tasks: Sentence Splitting, NER and Named Entity (NE) Substitution, Sentence Filtering, Dependency Parsing and lemmatization. First, texts are split into sentences. Then, NEs are recognized. We focused on relation between diseases and symptoms. Thus, we replaced each occurrence of these entities by the corresponding generic word “DISEASE” or “SYMPTOM”. Sentences are filtered to keep those involving at least two entities of interest. Dependency parsing produces for each sentence one labeled directed graph, named DG. Such DG is made of vertices that represent words and edges that are grammatical dependencies between words. Figure 3 shows the dependency graph of the sentence “DMD is a neuromuscular disease characterized by progressive weakness.”.
Finally, words in DG are replaced by their lemmas, by a more general form that is more likely to appear in other graphs. Figure 4 shows an example of DG resulting from the data preparation step.
The collection of formatted DG is the input to FSM for mining the most frequent subgraph patterns that preserve the relations between two named entities. 3.2
Frequent Subgraph Mining (FSM) aims at extracting useful patterns for the relation extraction process. Given a set of DGs and the support threshold, gSpan extracts an undirected subgraph patterns. These patterns give the relationships between interesting annotated entities. Figure 5 shows an example of such pattern, extracted from graph in Figure 4. This subgraph pattern gives the relation based on grammatical dependencies between the disease “DMD” and the symptom “weakness”.
Then, the patterns that contain the following are excluded: (1) conj and or conj or dependency relation between any two nodes; (2) The dependency path for DISEASE is equal to the dependency path for SYMPTOM, this means that DISEASE and SYMPTOM have the same semantic role in the sentence and this might be an error from NER; (3) no node for DISEASE or SYMPTOM (at least one disease and one symptom must be exist). Figure 6 shows an example of such excluded patterns. These patterns can be discovered from a sentence like “this disease is characterized by DISEASE and SYMPTOM”2. 2 The uppercase words are the generic words for NEs
Bunescu and Mooney proposed a kernel method that used the shortest path
between the two entities in the undirected version of the dependency graph [
Figure 7 shows the shortest path between the two entities DISEASE and SYMPTOM in the dependency graph.
Given the following two annotated sentences “DISEASE is a disease characterized by SYMPTOM” and “DISEASE is anomaly accompanied by SYMPTOM”. First, SPM get the graph of each sentence as shown in figure 8. Then, SPM compute the common shortest path from the graphs of the two sentences. If the values of the nodes in the pattern are di↵erent, their values are replaced by “*” and keeping a list of all possible values for each node. Hence, two graphs patterns can be merged and represented in one generalized pattern 3. The support of the new generalized pattern is less than or equal the sum of the supports of the two patterns. The support of the generalized pattern is automatically computed when executing the generalization operation which makes the process run faster.
Figure 9 shows two examples of pattern, one resulting from SPM patterns
and the other resulting from gSpan. SPM method checks every node in the
subgraph pattern to contain all possible values. This makes the pattern more
general than gSpan pattern and increases the frequency value of the pattern.
This has two advantages: first it produces a smaller set of patterns than gSpan
patterns which is easier for analysis and evaluation purposes; second it leads to
3 There is no redundancy because all redundant patterns are merged into one pattern
a higher coverage than gSpan when the pattern may not be extracted by gSpan
because of its low frequency. On the other side, SPM did not use POS tags as
a single feature as proposed in [
When SPM extends every node with all possible values, some values don’t represent a correct relation between the annotated entities. Figure 10 shows rejected patterns that should be removed by the generalization operation to increase the quality of patterns.
The extracted patterns are classified into two classes: positive and negative patterns. The classification is based on pattern support and quality. The quality Q of a pattern is computed by the following formula
Q =
T S where T is the number of all correct sentences in the pattern extension and S is the support of the pattern. A sentence is correct if it contains the pattern and the relation identified by the pattern is correct. For example, the pattern in Figure 8 has support 23. This means that the number of sentences that contain this pattern is 23. All disease-symptom relationships provided in these 23 sentences are correct. Then, T=23 and Q=23/23. Hence, the quality of this pattern is 1.
The pattern is a positive pattern if its support is higher than a minimum support (min sup) threshold and its quality is higher than a minimum quality (1) threshold. Only positive patterns are considered for extracting new relationships from a new corpus. 3.3
Positive patterns previously selected are used to discover new relationships between entities mentioned in a new corpus. Similarly to the learning process, a set of dependency graphs are generated from the new corpus exactly as the data preparation step (sentences splitting and NER are also required before dependency parsing). Then, a pattern matching for the selected patterns with the dependency graphs is done to extract the binary relationships between the interesting entities. A value that expresses the quality of each new extracted relation is also returned (accordingly to the quality of the pattern used in the extraction process).
We build-up experiments on the basis of a medical corpus related to rare diseases. This corpus is explored to extract relationships between diseases and symptoms. Figure 11 presents the process of our experiments and its evaluation. Details are provided in the following subsections. Our rare disease corpus is composed of 51,292 PubMed abstracts related to 50 Orphanet4 rare diseases5. Abstracts are obtained by querying manually PubMed, using its web user interface. The query submitted to PubMed has the following form: “(disease1,pref name or disease1,syn1 or...or disease1,synn ) or... or (diseasek,pref name or diseasek,syn1 or...or diseasek,synm )”
where diseasei,pref name and diseasei,synj are respectively referring to the preferred name and the jth synonym of disease i according to the Orphanet Rare Disease Ontology6.
5 The 50 diseases are listed at: http://www.loria.fr/~msayed/50RareDiseases 6 http://www.bioportal.bioontology.org/ontologies/ORDO
Building a Dependency Graph Dataset
51,292 abstracts are split in 428,941 sentences using LingPipe7, and subsequently
submitted to disease and symptom NER. We use MetaMap to annotate each
sentence of the corpus using UMLS semantic types “Disease or Syndrome” and
“Sign or Symptom” [
The Stanford Parser is used to build the Dependency Graph (DG) of each
sentence [
From prepared dependency graphs, gSpan extracts all frequent subgraphs. Those are filtered to keep only subgraphs that contain one disease and one symptom. This guarantees that only patterns that describe the dependency relation between disease and symptom are kept. We applied our program to gSpan subgraphs to identify in each case the shortest path between the nodes DISEASE and SYMPTOM. When several diseases or symptoms are in a unique sentence, one shortest path is computed for each pair (DISEASEx–SYMTOMy). This resulted in 6,048 subgraph patterns, a smaller set compared to gSpan result, consequently easier to evaluate. Because we think that shortest paths represent the most significance part of subgraph, we focused on these reduced graphs. 4.4
First, patterns with a f requency 2 are selected from the 6,048. Accordingly, 615 patterns are frequent, covering 2,535 sentences from all 5,653 (44.84%). Second, patterns with a pattern quality 0.5, our quality threshold, are selected (see formula 1). It results 324 patterns (that cover 1,329 sentences or 23.51%), which are considered as positive patterns and are aiming at extracting new relationships from text.
Finally, we evaluate the ability of positive patterns to identify disease-symptom relationships in the test corpus. The evaluation process can be divided in three tasks. (i) For each sentence in the test corpus, two lists of disease-symptom pairs are composed: the list i-a of all possible disease-symptom pairs found in the sentence; the list i-b of pairs extracted by our method, i.e., when a positive pattern matches the DG of a test sentence. Obviously, list (i-b) is a subset of (i-a). (ii) Each pair of list i-a is marked manually as Correct if it corresponds to a relation actually mentioned in the sentence, or Incorrect, if it is not. (iii) Pairs that are marked as Correct and are extracted by our method (i.e., in list i-b) are True Positive (TP); pairs that are marked as Incorrect and are not extracted by our method are True Negative (TN); pairs that are marked as Incorrect and are extracted by our method (i.e., in list i-b) are False Positive (FP); pairs that are marked as Correct and are not extracted by our method are False Negative (FN).
Co-occurrence is the simplest method to identify relationships between two
entities that co-occur in the same sentence. This approach is based on the
hypothesis that if two entities are mentioned frequently together, it is likely that these
two entities are related. Co-occurrence methods have been successfully applied to
the automated construction of networks of biomolecules such as protein-protein
or gene-disease networks [
Bags of words are artificial constructs where one textual document is represented as an unordered set of the words it contains, i.e., the bag. In this set, each word is usually associated with its frequency of occurrence in the document, then enabling to weight words within the bag. This is used to classify documents with similar words and words frequency profiles. Indeed, when associated with a proper dictionary, a document represented as a bag can be encoded as a simple vector of integers. This is a compact representation that enables to work with large corpora of documents. It su↵ers from low precision.
Sequence of words It consists of a partial order (i.e., the sequence) of words,
POS tags, general POS tags, entity or chunk type, etc. These features are used
to build patterns or rules that assert a relationships between entities. Blohm et
al. presented method based on a taxonomic sequential pattern for RE which
extends a sequential mining algorithm to take into account a taxonomy of
morphosyntactic and lexico-semantic features [
Parse Tree is an ordered, rooted tree that represents the syntactic structure of
a sentence. Some works have been proposed to use such syntactic structure for
extracting relations between entities. Galitsky introduced the operation of the
syntactic generalization which take a pair of syntactic parse trees and find the
maximal common subtrees [
Many RE methods based on DG have been proposed [
Chowdhury et Lavelli also proposed to use a reduced graph pattern that is a set of syntactic dependences of the corresponding reduced graph. For example, the reduced graph pattern of the graph represented Figure 7 is hnsuj, cop, det, jj, partmod, agenti. Note that, in this case, reduced graph patterns are undirected.
Adolphs et al. developed a rule learning algorithm to learn graph rules which
identify subgraphs in arbitrary graphs [
The proposed hybrid kernel approach of Chowdhury et Lavelli [
In our experiments, we fixed min sup=2. When min sup=2, the number of extracted patterns is 615. When increasing the min sup threshold, the number of extracted patterns and recall decrease. For example, if min sup=3, then the number of extracted patterns is 268. When decreasing the min sup threshold, the number of extracted patterns and recall increase. For example, If min sup=1, then the number of extracted patterns is 6048. This number of patterns is large for analysis and patterns with support=1 may be not important because they are rare patterns.
Figure 12 shows the relation between the precision and pattern quality threshold and between recall and pattern quality threshold. Precision increases and recall decreases when the pattern quality threshold increases. The best precision value is 0.94 when the quality threshold is 100 and the best recall value is 0.67 when the quality threshold is 0. The trade-o↵ between the precision and recall is required according to the purpose of the application.
The study of FN and FP relations is necessary for improving the recall and precision respectively. In the following sentence “In areas in which transmission is occurring, WNV infection should be considered in patients with acute flaccid paralysis.”, the relation between disease “WNV” and symptom “flaccid paralysis” is marked as FN relation (because we didn’t generate a positive pattern that describes this relation). A possible solution for this problem is to consider patterns with low frequency (rare patterns), another solution is to enlarge the learning corpus. These produce a larger patterns set which reduces FN relations and increases the recall.
On the other side, to increase the precision, the number of FP relations needs to be reduced. The following sentence “Muscular dystrophy is a nosology for a group of hereditary muscle disorders characterized by progressive wasting and weakness of skeletal muscle, where degeneration of muscle fibers is detected by pathological examination” generates a FP relation between “hereditary muscle” and “weakness”. One solution is to consider only patterns with high quality by increasing the quality threshold to ensure that the extracted patterns are precise enough.
Finally, Unlike gSpan and Chowdhury’s work, SPM doesn’t able to keep other features such as negation relation. issues like this must be token in consideration for further improvements and extensions to SPM. 6.2
This paper illustrates how graph mining can be used for RE. We propose a simple method based on FSM to extract relationship from a corpus of text represented as DGs. FSM enables to identify subgraph patterns that are filtered based on their frequency and quality. Selected patterns are in turn used to extract relationships form novel sentences. Our evaluation on a corpus related to rare diseases showed a very high precision of 0.91.
In the future, the recall of the FSM-based method may be enhanced by improving its ability to identify FN relations. Also, thanks of the readability of the extracted patterns, studying and adding new features or constraints to improve the quality of these patterns is possible and may increase the recall and precision values. Combining features of sequences, syntax trees and dependency graphs may introduce more precise patterns with higher recall.