5.1 Weight tuning

There are several motivations for learning the graph weights Θ in the underlying graph. First, some dependency relations – foremost, subject and object – are in general more salient than others (Lin Reference Lin1998; Padó and Lapata Reference Padó and Lapata2007). In addition, dependency relations may have varying importance per different notions of word similarity. Weight tuning allows the adaptation of edge weight parameters Θ to the type of similarity sought. Given the adapted edge weights, the graph walk process is biased toward nodes linked over meaningful relations (1).

The weight tuning method implemented in this work is based on an error backpropagation hill-climbing algorithm (Diligenti, Gori and Maggini Reference Diligenti, Gori and Maggini2005). The algorithm minimizes the following cost function:

(4) \begin{equation} E = {1 \over N} \sum _{z \in N} e_z = {1 \over N} \sum _{z \in N}{1 \over 2} \big (p_z - p^{Opt}_z\big)^2 \end{equation}

5.2 Node reranking

Reranking of top candidates in a ranked list has been successfully applied to multiple NLP tasks (Collins Reference Collins2002; Collins and Koo Reference Collins and Koo2005; Shen and Joshi Reference Shen and Joshi2005). In essence, discriminative reranking allows the re-ordering of results obtained by methods that perform some form of local search. It is generally assumed that the initial ordering produced by the local search is of high quality so that the top-ranked candidates include relevant answers. The goal in reranking is to improve the initial ordering using higher level information. Since features that encode high-level phenomena are typically costly to compute, reranking is applied to a limited number of top-ranked candidates. In our framework, the graph walk serves as a local search procedure that outputs an initially ranked list of nodes, given a large space of candidates corresponding to all of the graph nodes. Only local information is used in the graph walk, as random graph walks are a memory-less Markovian process. We will use reranking to represent nodes in terms of global, high-level connectivity patterns in the graph. The reranking function and features used are described below.

The reranking function: Formally, for every training example i (1 ≤ i ≤ N), the reranking algorithm is provided with an initially ranked list of l_i nodes. Let z_ij be the output node ranked at rank j in l_i, and let $p_{z_{ij}}$ be the probability assigned to z_ij by the graph walk. Each output node z_ij is represented through m features, which are computed by pre-defined feature functions f ₁, . . ., f_m. The reranking function for node z_ij is defined as

(5) \begin{equation} F(z_{ij},\bar{\alpha}) = \alpha _{0}\text{log}(p_{z_{ij}}) + \sum _{k=1}^{m}\alpha _{k}f_{k}(z_{ij}) \end{equation}

$\bar{\alpha}$

$F(z_{ij},\bar{\alpha})$

$\bar{\alpha}$

Features: We describe a target node z_ij in terms of the set of paths traversed from the query distribution V_q in reaching that node by the graph walk process. These path-describing features can be computed in the process of executing the graph walk, or as a post-processing step (Cohen and Minkov Reference Cohen and Minkov2006). It has been previously shown that reranking graph nodes using path-describing features can improve results significantly (Minkov and Cohen Reference Minkov and Cohen2010). Specifically, we evaluate the following binary feature templates.

• • Edge label sequences. Features indicating whether a particular ordered sequence of edge labels ℓ_i (path) occurred within the set of paths leading from the query distribution to the target node z_ij.

• • Lexical unigrams. These features indicate whether a word mention of a particular lexical value t_k was traversed in the graph walk leading to z_ij.

• • Source-count. This feature indicates the number of different source nodes in the query distribution V_q that z_ij was reached from. The underlying intuition is that nodes linked to multiple query nodes, where applicable, are more relevant.

Example. Consider the graph depicted in Figure 1, where the query distribution is V_q = {‘new york’}. The target node ‘tokyo’Footnote ⁴ is described by the features (denoted as feature-name.feature-value): sequence.amod.prep.in-inv (where the edges mention and isa are omitted for brevity) and lexical.headquarters. (The source-count feature is degenerate in this case as the query distribution is point-wise.) Another potential target node, ‘Honda’, is reached from V_q over a different edge sequence, and will be described by the features sequence.amod.poss and lexical.headquarters. If the reranker is provided with this example query, along with labels indicating that ‘tokyo’ is a correct response for the query, whereas ‘honda’ is an incorrect response, it will learn a model that associates the features observed for ‘tokyo’ and other correct target nodes with high node relevancy and vice versa.

5.3 Path-constrained graph walk

While node reranking allows the incorporation of high-level features, it is a costly procedure that is typically applied to a small set of the top candidates retrieved by the local search procedure (aka, the graph walk). Reranking performance is therefore bound by the quality of the initially ranked list of candidates. For this reason, it is desirable to incorporate useful high-level information earlier in the graph walk process. We propose a variant of a graph walk, which is constrained by high-level path information. Assume that preliminary knowledge is available that indicates the probability of reaching a relevant node after following a particular edge-type sequence (path) from the query distribution V_q. We are interested in directing a random walker to follow paths for which this probability is high. In the proposed PCW variant, this is achieved by replacing the fixed edge weights Θ with edge weights that are conditioned on the history of the walk. As will be shown, this results in accuracy gains, where paths that lead mostly to irrelevant nodes are degraded in the graph walk process. In addition, it is straightforward to apply a threshold to prune paths with low estimated probability of reaching a relevant node in the walk to improve both qualitative performance and efficiency.

This section describes the path-constrained graph walk variant. The algorithm includes two main components. First, it addresses the evaluation of dynamic edge weights that are conditioned on the history of a walk, based on training examples. The space of path histories is |Θ|^K for finite graph walks of length K so that a compact representation is required. To this end, a path tree is constructed based on training examples in which each node denotes a unique walk history, and leaf nodes denote full paths observed. Every leaf node in the path tree is associated with the probability of reaching a relevant target node following the underlying edge sequence. These probabilities are propagated in the tree to obtain estimates of edge weights conditional on the history of the walk. The second component of the algorithm adapts the random walk algorithm to consider path history. We represent the nodes traversed as a set of node pairscomprising the graph node and the corresponding vertices in the path tree. The outgoing edge weights from each node pair are estimated according to the respective vertex in the path tree. Next we describe in detail how we construct a path tree from labeled examples, and outline the path-constrained graph walk variant.

5.3.1 The path-tree

We are given a training set of labeled example queries. An initial graph walk of length K (using fixed edge weights Θ) is performed to generate a ranked list of nodes per query. Let a path p denote a sequence of j ≤ K edge types. For each training example i (1 ≤ i ≤ N), we recover all of the full connecting paths leading from each query node to the top M (correct and incorrect) nodes. We consider only acyclic paths.Footnote ⁵ Let C ⁺_p be the count of a path p within the paths leading to correct nodes over all example target nodes N·M; and similarly, let C ⁻_p denote its count within the paths leading to the negatively labeled nodes in the example node set. The full set of paths observed can be represented as a tree. (The conversion to a tree is straightforward, where identical path prefixes are merged.) The leaves of the tree correspond to the paths traversed to a target node and are assigned a Laplace-smoothed probability:

(6) \begin{equation} Pr(p)={C_p^+ +1\over {C_p^+ + C_p^- +2}} \end{equation}

Pr(p) is a (smoothed) maximum likelihood estimate of the probability of reaching a correct node following p, based on observed examples.

While the probability of reaching relevant nodes following various paths over a random walk of length K is estimated directly from data, we are interested in assessing conditional typed edge weights that guide the random walk process in relevant directions, reflecting the probability of reaching a correct target node given partial walk history (corresponding to a path prefix). We approximate the edge weights conditioned on walk history by propagating the path (leaf) probabilities backwards in the path tree to all tree vertices, applying the MAX operator. This approximation provides an upper bound of the downstream probability of reaching a correct response once the walk is fully executed.Footnote ⁶

Example. Consider the graph shown on the left part of Figure 2. Suppose that the topmost node in the graph (in black) is submitted as a query V_q, where the two nodes at the bottom correspond to relevant (on the left, in blue) and irrelevant (on the right, in red) responses. Assuming a graph walk of three steps or more, there are three acyclic paths overall, including two unique paths that lead to the relevant node:

\begin{linenomath} \begin{matrix} \buildrel{\ell}\over\longrightarrow & \buildrel{m}\over\longrightarrow & \buildrel{k}\over\longrightarrow & \times 2 \\ \buildrel{\ell}\over\longrightarrow & \buildrel{n}\over\longrightarrow & \buildrel{k}\over\longrightarrow & \times 1 \\ \end{matrix} \end{linenomath}

\begin{linenomath} \begin{matrix} \buildrel{\ell}\over\longrightarrow & \buildrel{n}\over\longrightarrow & \buildrel{k}\over\longrightarrow & \times 2 \\ \buildrel{\ell}\over\longrightarrow & \buildrel{m}\over\longrightarrow & \buildrel{n}\over\longrightarrow & \times 2 \\ \buildrel{m}\over\longrightarrow & \buildrel{\ell}\over\longrightarrow & \times 1 \\ \end{matrix} \end{linenomath}

\begin{linenomath} \begin{matrix} <C_{\ell.m.k}^+=2, C_{\ell.m.k}^-=0>\\ <C_{\ell.n.k}^+=1, C_{\ell.n.k}^-=2>\\ <C_{\ell.m.n}^+=0, C_{\ell.m.n}^-=2>\\ <C_{m.\ell}^+=0, C_{m.\ell}^-=1>\\ \end{matrix} \end{linenomath}

The irrelevant node is reached via five paths overall, consisting of three unique paths, as follows. These path counts are summarized as follows: In this toy example, the count statistics indicate that the path ℓ.n.k is relatively ‘noisy’, in the sense that this path reaches incorrect responses with high probability (twice out of three times observed). Similarly, the paths ℓ.m.n and m.ℓ lead to irrelevant nodes only in the observed example. In practice, considering cumulative path counts over a set of example nodes, path count statistics are expected to represent general phenomena in the graph. We wish to assign lower walk probability along noisy paths compared with paths that lead mostly to nodes judged as relevant.

Fig. 2.

The toy graph on the left (a) is annotated with a query node (in black), as well as a correct answer node (left bottom node, in blue), and an irrelevant node (right bottom node, in red). The path tree constructed based on this example is shown on the right (b), including the computed conditional typed edge weights. The graph and path tree include the edge labels ℓ, m, n and k.

The path tree constructed based on this example is shown on the right part of Figure 2. The conditional typed edge weights are displayed next to each edge in the path tree. According to the computed path counts and (6), the leaf probability of the path ℓ.m.k is estimated at 0.75, and at 0.25 for the path ℓ.m.n. Assuming that the path prefix ℓ.m has been traversed in the walk, the outgoing edge weights according to the path tree are θ(k|ℓ→m) = 0.75 and θ(n|ℓ→m) = 0.25. Accordingly, given that only an edge of type ℓ was traversed, the weight of an edge of type m is estimated as the maximal probability estimate of the corresponding downstream leaves in the path tree, i.e. $\theta (m|\ell)=\text{Max}(\theta (k|\ell \rightarrow m),\theta (m|\ell \rightarrow m))=0.75$. Similarly, at the root of the tree, the computed edge weights are estimated at θ(ℓ|.) = 0.75 and θ(m|.) = 0.33. We assume the weights associated with edge types not included in the path tree at a given vertex to be zero.

5.3.2 A path-constrained graph walk

The path-constrained graph walk adheres both to the topology of the graph G and the path tree T. Walk histories of each node x visited in the walk are compactly represented as pairs 〈t, x〉, where t denotes the relevant vertex in the path tree. This means, however, that if x was reached via n different paths, it would be represented using n node pairs.

Example. Assume that a walk is performed using the path tree shown in Figure 2. If the graph displayed in Figure 2 is used, then after one walk step, the walk distribution would include a couple of node-history pairs: 〈T(ℓ), x ₁〉 and 〈T(m), x ₂〉. Suppose that another graph node x ₃ (in a hypothetical graph) is reached in the next walk step from both x ₁ and x ₂; in this case, node x ₃ would be represented by multiple node pairs, including 〈T(ℓ→n), x ₃〉 and 〈T(m→ℓ), x ₃〉.

Given the path tree vertex indicated in each node-history pair, the weights of outgoing edges are retrieved from the path tree. These weights are normalized at each node traversed to generate local transition probabilities (following (1)).

Example. Consider the node pair 〈T(ℓ), x ₁〉, where the outgoing edges from node x ₁ are of types m, n and k. Assuming that the path tree shown in Figure 2 is provided, the edge weights for this node-history pair are θ(m|ℓ) = 0.75 and θ(n|ℓ) = 0.4. (We set θ(k|ℓ) = 0 because the sequence ℓ→k is not a path prefix in the path tree.) Given these conditional edge weights, the graph walk proceeds according to its original schema.

The pseudo-code for the path-constrained graph walk is given in Algorithm 1. Note that the number of nodes effectively processed in the path-constrained graph walk is larger relative to an unconstrained walk, as a graph node may be processed multiple times, per walk history. On the other hand, paths in the graph that are not represented in the path tree are pruned. (It is possible, of course, to assign a small probability to previously unseen paths.) In addition, it is straightforward to discard paths in the path tree that are associated with a lower probability than some threshold. A threshold of 0.5, for example, implies that only paths that led to a majority of positively labeled nodes in the training set are followed. Path pruning has a direct effect on the time complexity of the walk, reducing the number of nodes and edges visited. This is further discussed in Section 8.

Algorithm 1

Pseudo-code for path-constrained graph walk

5.4 A comparative discussion

We have outlined different approaches for learning to rank graph nodes given labeled examples and initial rankings generated using graph walks. We now discuss the strengths and weaknesses of these methods with respect to several key criteria, including the scope of information modeled by each approach, potential impact of learning on the graph walk ranking and computational aspects.

Scope. A random graph walk process is strictly Markovian, where the random walker does not ‘remember’ the history of the walk. Similarly, in learning the graph edge weights using methods such as error backpropagation, the graph walk is decomposed into single time steps, and optimization is performed ‘locally’. In contrast, the node reranking and constrained graph walk approaches allow one to exploit global properties of the walk; in particular, both methods can model information about edge sequences traversed over multiple time steps in the walk. As will be demonstrated, modeling path information is highly important in estimating semantic relations based on distributional evidence in the proposed word graph. Overall, reranking is the most ‘global’ method out of the approaches considered. In addition to edge sequences, reranking can incorporate features that describe properties of the nodes traversed in a path, for example, their lexical value. Moreover, information about the collection of paths leading to a node may be represented as features in reranking. For example, the source count feature denotes the number of different query nodes that link to the target node. Similarly, reranking features can explicitly model the number of paths leading to a node, and other global properties pertaining to node connectivity. Finally, reranking can also model arbitrary domain-specific features, incorporating additional relevant information sources that are independent of the graph walk (Minkov and Cohen Reference Minkov and Cohen2010). In contrast, the proposed formula of the path-constrained walk models information about the edge sequences traversed, but cannot model neither properties of the nodes traversed, or information at path set level.

Impact. Learning may alter the graph walk-based initial rankings to varying extents. The method of tuning the graph edge weight parameters Θ has relatively limited impact on the rankings generated using the Personalized PageRank graph walk scheme. The reason for this is that Personalized PageRank applies an exponential decay over walk length (3); this makes a node's distance from the query nodes the dominant factor in its assigned score. In other words, a strong bias is applied toward nodes that are linked to the query nodes over short connecting paths. Hence, we observe that edge weight tuning mainly affects the relative rankings of ‘competing’ nodes residing in similar distance from the query. In contrast, the path-constrained graph walk variant can affect the output rankings to a large extent: nodes that are reached from the query nodes over short but unmeaningful paths will be demoted, or excluded from, the output ranking. Unlike reranking, the path-constrained walk applies to all of the graph nodes. Finally, discriminative reranking can significantly alter the ranked list output by the graph walk. However, for computational reasons, reranking is only applied to the top candidates (nodes) ranked. This means that reranking performance is bound by the quality of the initially ranked lists. It is therefore desirable to apply reranking in combination with a good initial ranking function. In particular, reranking has been successfully applied in combination with graph walks that use a learned set of edge weights Θ* (Minkov and Cohen Reference Minkov and Cohen2010). Similarly, we expect that applying reranking to the top results retrieved using the path-constrained walks may be beneficial in some cases; as discussed before, while both methods incorporate high-level information about the edge sequences traversed, additional information can be incorporated using reranking.

Cost. The learning methods differ in terms of training and run-time requirements. In training, the error backpropagation weight-tuning approach requires re-computing the graph walk in each iteration. In addition, in order to avoid local minima, a recommended strategy is to repeat training multiple times using randomized initial edge weight parameters and to select the overall best learned set of edge weights Θ*. The training procedure of weight tuning is therefore relatively slow. However, having learned Θ*, a graph walk is readily applied using the modified edge weight parameters with no overhead during runtime. The reranking approach requires a one-time execution of the graph walk to generate the graph walk rankings. Features describing the top graph nodes retrieved can be derived either during the graph walk (Cohen and Minkov Reference Cohen and Minkov2006), or as a separate step, using a path unfolding procedure (Minkov and Cohen Reference Minkov and Cohen2010). While the procedure of learning a reranking function and applying the learned model to other feature vectors is efficient, encoding nodes with their feature values adds processing overhead to query execution. Finally, the path-constrained graph walk approach is simple and fast to train. Like reranking, it requires a single execution of the graph walk for the given example queries, as well as path unfolding, during training. In run time, maintaining node pairs that represent the set of walk histories for each graph node traversed imposes relatively large memory requirements, thus affecting the processing time and scalability of the walk. We discuss and evaluate empirically the effect of the PCW algorithm on scalability in Section 8.2.

6.1 Corpora and datasets

As the experimental corpora, we use the training set portion of the MUC-6 dataset (MUC6 1995), as well as articles from the Associated Press (AP) extracted from the AQUAINT corpus (Bilotti et al. Reference Bilotti, Ogilvie, Callan and Nyberg2007), all parsed using the Stanford dependency parser (de Marneffe, MacCartney and Manning Reference de Marneffe, MacCartney and Manning2006). (Due to lower parsing quality, sentences longer than seventy words were omitted.) The MUC corpus provides true named entity tags, while the AQUAINT corpus includes automatically generated noisy, named entity tags. In constructing the graphs, we represent multi-word named entity expressions using a single node; for example, as shown in Figure 1, the named entity mention New-York³ is denoted by a single node, and so is the corresponding (normalized, low-case) term, new york. Statistics on the experimental corpora and their corresponding graph representation are detailed in Table 1. As shown, the MUC corpus contains about 140 thousand words, whereas the MUC+AP experimental corpus is substantially larger, containing about 2.5 million words in total. In processing the corpora into word graphs, ‘stop words’ (uninformative words such as ‘the’, ‘to’ etc.) were eliminated. The processed MUC graph contains about 17 thousand term nodes, and 65 thousand word mention nodes; the MUC+AP graph contains about 80 thousand term nodes and about 1 million word mention nodes. While the dictionary used grows moderately with the size of the corpus, the number of word mentions is proportional to corpus size. Finally, the graphs are relatively sparse: there are about three connecting edges per node in the graph.

Table 1.

NE coordinate term extraction: corpus statistics

We generated ten queries, each comprising four city names selected randomly according to the distribution of city name mentions in MUC-6. Similarly, we generated a set of ten queries that include four person names selected randomly from the MUC corpus. Using a set of seeds, rather than a single seed, gives a refined definition of the semantic class sought, and is the typical setting in extracting named entity classes (Wang and Cohen Reference Wang and Cohen2007). Another reason for using queries that include multiple entities is that some entity nodes may be poorly connected in the graph and thus provide weak contextual evidence; for example, minor cities are typically mentioned a small number of times in the corpora so that the set of paths originating from the corresponding terms in the graph, and the number of other city names that can be reached over these paths using finite graph walks, are limited. Given multiple seed entities, it is expected that at least a subset of them would provide useful evidence. For each task, we use five queries for training and tuning and the remaining queries for testing. Note that while the number of test queries is relatively small, all of the city, or person, names in the corpus are considered as correct answers. This means that a large number of positive and negative query-target node similarity pairs are evaluated per query. In the experiments, we perform the same set of queries using the MUC corpus, and the larger MUC+AP corpus, so that performance is assessed on the same queries for different corpora sizes. To allow such a comparison, the smaller MUC corpus was appended to AP so that the same query sets are applicable in both cases.

6.2 Experiments

We evaluated cross-validation performance over the training queries in terms of mean average precision (MAP) for varying walk lengths K. We found that beyond K = 6 improvements were small (see also Section 8.1). We therefore set K = 6. Weight tuning was performed using the training queries and two dozens of target nodes overall. In reranking, we set a feature count cutoff of 3 to avoid over-fitting. Reranking was applied to the top 200 ranked nodes output by the graph walk using the tuned edge weights. Finally, path trees were constructed using the top twenty correct nodes and twenty incorrect nodes retrieved by the uniformly weighted graph walk. In the experiments, we apply a threshold of 0.5 to the path-constrained graph walk method, eliminating paths associated with lower probability of reaching a correct response from the path tree.

We note that for learning, true labels were used for the fully annotated MUC corpus (we hand-labeled all of the named entities of type ‘location’ in the corpus as to whether they were city names). However, noisy negative examples were considered for the larger automatically annotated AP corpus. (Specifically, for cities, we only considered city names included in the MUC corpus as correct answers.)

A co-occurrence vector-space model was applied using a window of two tokens to the right and to the left of the focus word. Inter-word similarity was evaluated in this model using cosine similarity, where the underlying co-occurrence counts were normalized by log-likelihood ratio (Padó and Lapata Reference Padó and Lapata2007). The parameters of the DV method were set based on a cross-validation evaluation (using the MUC+AP corpus). The medium set of dependency paths and the oblique edge weighting scheme were found to perform best.Footnote ⁷ We experimented with cosine as well as the Lin similarity measure in combination with the DV representation. In applying the vector-space-based methods, we compute a similarity score between every candidate entity and each of the query terms, and then average these scores (as the query distributions are uniform) to construct a ranked list. Given the large number of candidates in the MUC+AP corpus (see Table 1), we show the results of applying the considered vector-space models to the top, high-quality entities retrieved from this corpus. Specifically, the set of entities considered includes the union of the top 200 results obtained using the tuned graph walks (i.e. the same set of results that was processed using reranking) per query. Finally, for both the graph walk and the vector-based models, we limit the considered set of candidates to named entities.

7.1 Dataset and corpus

We have constructed a set of example queries that describe word synonym pairs, distinguishing between nouns (twenty-two examples), adjectives (twenty-four examples) and verbs (twenty-three examples). The synonym pairs considered correspond to popular examples given on websites dedicated to teaching English as a second language. (Since such sources listed only a handful of adverbs, we did not include adverbs in this case study.) The full synonym list that constitutes our dataset is given in Figure 4. Alternatively, one can consider the synonym sets included in a lexico-semantic ontology, such as WordNet, to construct a dataset for learning and evaluation. However, the synonymy distinctions annotated in WordNet are often intricate and context-dependent. We choose to focus on coarse synonymy in this case study, as we are interested in learning general, rather than word-specific, synonymy relations.

Fig. 4.

Word synonym pairs: the left words were used as query terms in our experiments.

We constructed a corpus of parsed text using the British National Corpus (BNC; Burnard Reference Burnard1995) for the experiments. The full BNC corpus is a 100-million-word collection of samples of written and spoken language from multiple sources, designed to represent a wide cross-section of contemporary British English. We extracted sentences from the BNC corpus that contained synonymous words. The number of extracted sentences was limited to 2000 per word. In addition, for infrequent words, we extracted more example sentences from AP articles included in the AQUAINT corpus (Bilotti et al. Reference Bilotti, Ogilvie, Callan and Nyberg2007) so as to increase the number of sentences per word to at least 300, if possible. The constructed corpus, BNC+AP, includes 1.3 million words overall. This corpus was parsed using the Stanford dependency parser. While named entity tags are included in the AP corpus, this information is not readily available for the BNC corpus. The nodes of the constructed graph therefore correspond to individual words in this case. The corresponding graph included about 400 thousand word mention nodes, about 40 thousand term nodes and 1.7 million edges overall.

7.2 Experiments

In our experimental setting, the query distribution V_q consists of a single term of interest. We assume that the word type of the query term is known. Rather than ranking all terms in response to a query, we use available (noisy) part of speech information to narrow down the search to the terms of the same type as the query term, e.g. for the query ‘film’ we retrieve nodes of type τ = noun.

In preliminary experiments, we found that while weight tuning improves graph walk performance, the quality of the local graph walk models was relatively poor on the synonym extraction dataset. These results are in line with the findings reported before (Figure 3). An analysis of the word graph showed that out of the synonym word pairs included in our dataset, 12.5 percent, 9.5 percent and 4.5 percent of adjective, verb and noun word pairs, respectively, co-appeared within a single sentence in the corpus. Since the Personalized PageRank graph walk schema is biased toward nodes linked over shorter paths in the graph, this means that most synonyms, connected over relatively long cross-sentence connecting paths, are assigned low probability scores by the graph walk. In addition, applying reranking to the top results of the graph walk models gave low performance in this case. We observed that due to the small number of correct examples available in this dataset (having a single correct answer specified per query, compared with many relevant terms in the named entity extraction case study) on one hand, and the high variability of contexts in which general words appear on the other hand (demoting the importance of lexical path features), this dataset was not large enough to allow effective learning by the discriminative reranking model. Hence, in this case study we focus on the PCW method, which incorporates high-level information about the connecting paths as part of the random graph walk process.

We applied the PCW method, learning separate models for nouns, verbs and adjectives. The path trees were constructed using the paths leading to the node known to be a correct answer, as well as to the otherwise irrelevant top-ranked ten terms, per query. In the experiments, we considered paths that are six segments long. Such paths represent distributional similarity phenomena, allowing a direct comparison against the DV method. In conducting the constrained walk, we applied a threshold of 0.5 to truncate paths associated with lower probability of reaching a relevant response.

Details about the implementation of the DV method are provided in Section 6. We use here the union of the top 300 terms retrieved by path-constrained walk as candidate terms for dependency vectors. For all queries, these sets of terms included the correct answer annotated. We evaluate the following variants of dependency vectors: having inter-word similarity computed using Lin's measure (DV-Lin; Lin Reference Lin1998), or using cosine similarity (DV-Cos). In addition, we consider a non-syntactic variant, where a word's vector consists of its co-occurrence counts with other terms (using a window of two words); that is, ignoring the dependency structure (CO-Lin).

One difference between distributional methods and graph walk methods is that distributional similarity measures incorporate heuristics that account for the effect of non-informative word co-occurrences, where co-occurrences of the target word with highly frequent words (Manning and Schütze Reference Manning and Schütze1999), or with otherwise highly infrequent words (Hughes and Ramage Reference Hughes and Ramage2007), are often non-informative. For example, Lin's similarity metric, which was designed for the task of evaluating general word similarity from corpus statistics, is based on the mutual information measure, downweighting frequent word co-occurrences. In order to demote the effect of uninformative word co-occurrences, we evaluate the PCW approach also in settings where random and noisy edges have been eliminated from the underlying graph. Specifically, dependency links in the graph were associated with pointwise mutual information (PMI) scores of the linked word mention pairs (Manning and Schütze Reference Manning and Schütze1999); edges with low scores are assumed to represent word co-occurrences of low significance, and so are removed. We empirically set the PMI score threshold to 2.0, using cross validation (PCW-P).Footnote ⁸ Finally, for comparison purposes, in addition to the specialized PCW models, we also learned a uniform model over all word types in these settings; that is, this model is trained using the union of all training examples, being learned and tested using a mixture of queries of all types (PCW-P-U).

8.1 Graph walk

The graph walk framework includes two parameters: the reset probability γ; and, as we perform finite graph walks, the length of the walk K. In this section we discuss the effect of these parameters on performance.

In all of the experiments reported thus far, the reset probability was set to γ = 0.5. In experiments conducted on the tasks and corpora evaluated in this work, we found that the value of γ had negligible effect on the actual produced rankings. These results are in line with previous findings, showing that while the reset probability parameter affects the actual scores assigned to the graph nodes, it does not change their ranking (Page et al. Reference Page, Brin, Motwani and Winograd1998; Agirre and Soroa Reference Agirre and Soroa2009; Minkov and Cohen Reference Minkov and Cohen2010).

We further report empirical results of tuning the graph walk length. Figure 7 shows performance for the city name (left) and person name (right) extraction tasks varying the walk length K. The graphs report results for the MUC corpus, which is fully annotated, thus allowing us to show performance in terms of a precision-recall curve. Both graphs in Figure 7 demonstrate clearly that increasing the graph walk length improves recall. For both tasks, short walks where k≦ 4 yielded poor recall. (For the person name extraction task, recall was near zero, and the corresponding curves were eliminated from the figure.) The reason for this low recall is that there are relatively few relevant nodes that can be reached over short connecting paths in this domain. For example, the two-hops path ‘mention – conj-and – isa’ models a conjunction relation between words appearing in the same sentence. This type of evidence is relatively scarce in our experimental corpora, occurring more frequently for city names than for person names. (Co-occurrence frequency within the same sentence is generally low for word synonyms, or hypernyms; Snow et al. Reference Snow, Jurafsky and Ng2005.) The majority of meaningful paths are of length six in the graph; e.g. the path that models a common direct object or subject arguments is of length six. Increasing the walk beyond length K = 6 in this domain improves recall, as shown in the figure; however, the additional nodes reached in longer walks are generally added at the bottom of the retrieved list due to the exponential decay associated with the walk. Based on these results, we set the walk length in the experiments to K = 6.

Fig. 7.

Precision-recall curves varying the walk length K for city name extraction (top) and person name extraction (bottom). The left graphs show full curves, and the right graphs focus on the top of the lists (down to recall 0.2). These results were all generated using the MUC corpus.

8.2 Path-constrained walks

The number of distinct paths observed in our experiments, using constrained graph walks up to length K = 6, ranged roughly from 400 to 1500. The corresponding path trees consist of roughly 500 to 3500 nodes respectively. In general, the number of distinct paths observed increases with the number of examples, as well as with the size of the corpus. In the experiments conducted, highly meaningful paths (reported in Sections 6.3 and 7.3) were found to be highly frequent, and were observed in most of the examples used. In general, pruning infrequent paths from the path tree may be desired to avoid over fitting and for efficiency considerations. It is possible, however, that infrequent paths be useful in some domains; we recommend tuning the training set size empirically by means such as cross validation.

The PCW algorithm allows the elimination of paths associated with a low probability of reaching relevant target nodes. Specifically, it is straightforward to prune paths from the path tree for which the estimated path probability is below a pre-set threshold. Next we discuss and empirically evaluate the effect of pruning the path-constrained walks on performance and scalability.

Figure 8 shows the results of applying the PCW variant to the task of city name extraction and the MUC corpus using various thresholds. Specifically, we have evaluated thresholds of value 0 (PCW:0), considering all the paths in the corresponding path tree; 0.5 (PCW:0.5), following paths that lead to a majority of relevant nodes only and 0.8 (PCW:0.8), following paths that lead to a strong majority of relevant nodes. Results are shown in terms of a precision-recall curve, using the MUC corpus gold labels. In addition to PCW, the figure includes the performance of graph walks with uniform weights for reference. It is shown that applying a higher threshold to the path-constrained walk leads to improved precision, in this case, at the top ranks. It is also shown, on the other hand, that using a higher threshold yields lower overall recall as the result of decreased path coverage. Based on these results, we have elected to apply a threshold of 0.5 in our experiments, as this threshold gives good performance both in terms of precision and recall. In general, the utility of a threshold of a particular value may be task- or domain-dependent, and can be tuned as a system parameter. In addition, one should consider the effect of the selected threshold on scalability.

Fig. 8.

Precison-recall performance for city name extraction from the MUC corpus for path-constrained walks with varying thresholds, and graph walks with uniform weights.

In order to discuss the effect of the path-constrained walk on processing time and memory requirements, we first give details on our implementation of the graph walk, including empirical query processing times per our experimental corpora. The reported results in this paper were obtained using a commodity PC with 4-GB RAM, where graph information has been loaded to memory. The option of online computation may be less desirable given larger graphs due to longer response times and memory requirements. To evaluate performance on large graphs, we constructed three intermediate size corpora that include MUC, and incrementally larger portions of the AP corpus. Specifically, the intermediately sized corpora include a quarter of the AP corpus (MUC+1/4AP); about a half of the AP corpus (MUC+1/2AP) and about three quarters of the AP corpus (MUC+3/4AP). The number of nodes and edges of each corpus are detailed in Table 3.

Table 3.

Node and edge counts of incrementally larger corpora constructed for graph walk scalability assessment

In the experiments, we observed the processing time per query, t_i, averaged over the queries in the test set of each dataset. We obtained five such observations in repeated runs, for which we report the average: ∑⁵_{i = 1}t_i/5. Using the MUC corpus, query processing time was 0.4 seconds on average for the person name extraction task and 0.8 seconds on average for the city name extraction task. The difference in processing times between the two tasks is due to a larger number of city name occurrences in the corpus. (Most of the person names included in the experimental datasets correspond to only few mentions in the corpus such that a smaller number of edges is traversed.)

Figure 9 shows the average query processing times for MUC, as well as for the larger corpora, applying graph walks. Results are displayed as a function of corpus size (in terms of number of edges; see Table 3). As shown, average query processing time gets substantially longer, up to 11.3 seconds on average per query for the MUC+3/4AP corpus and the city name extraction task. In general, the implementation scheme applied in our experiments can be improved by using better machinery as well as by distributed computing. We therefore expect processing times to be shorter using optimized systems, as well as using algorithms that approximate the graph walk (e.g. Fogaras et al. Reference Fogaras, Rácz, Csalogány and Sarlós2005).

Fig. 9.

Average query processing time and standard deviation (sec) for the named entity coordinate extraction tasks, using graph walk of k = 6 steps and path-constrained graph walk with varying thresholds.

Figure 9 also shows the empirical average query processing time, applying the path-constrained walk with no threshold (PCW:0); with a threshold of 0.5 (PCW:0.5) and with a high threshold (PCW:0.8) on these corpora. (Results of the path-constrained walk for the MUC+3/4AP are not reported due to high memory requirements, as discussed later in this section.) The results indicate that longer processing times are required using the path-constrained walks, compared with the unconstrained graph walk. As expected, the processing times shorten as the threshold applied increases.

Rather than process the graph walk using the machine's memory, it is also possible to store the graphs in secondary memory. We used the open-source database package Sleepycat to store the user-defined nodes and edges. This allowed us to execute the graph walk for the large MUC+AP corpus (Table 1). The cumulative number of graph nodes visited at each step of the graph walk for the MUC+AP corpus is presented in Figure 10 (logarithm scale). It is shown in the figure that the number of nodes visited at each step of the walk starts dropping at k = 4 using the path-constrained walks. Constraining the graph walk to follow a path tree reduces the number of nodes (and edges) traversed in the walk for a couple of reasons. First, the path tree only represents paths observed within the set of connecting paths leading to the top nodes ranked in training examples, where other possible paths are assumed as irrelevant and discarded from the path-constrained walk. In addition, increasing the threshold on the probabilities associated with the path tree edges eliminates more (possibly frequent) paths.

Fig. 10.

The cumulative number of nodes visited at each step of the graph walk using the MUC+AP corpus, for city name extraction and person name extraction, applying unconstrained graph walk and path-constrained walk with varying thresholds.

While the path-constrained walk limits the number of nodes (and edges) that are traversed in the walk, it requires the processing of all combinations of a node and its unique histories. In the experiments reported in Figure 9, these added processing requirements overcome the savings due to node pruning in terms of running time. (See the processing times of the base graph walk in the figure as reference.) In addition, maintaining graph and path tree node pairs requires additional memory in comparison to the unconstrained walk. Therefore, we conclude that path-constrained walks, while contributing to performance, involve overall an additional computational cost. Path-constrained walks are expected to save on processing times, however, in case the graph is accessed from a secondary memory. In that case, node pruning will reduce the cost involved in disk access.