Programming with Personalized PageRank: A Locally Groundable First-Order Probabilistic Logic

INTRODUCTION

In many probabilistic first-order representation systems, including Markov Logic Networks and Probabilistic Similarity Logic , inference is performed by mapping a first-order program to a propositional representation, and performing inference in that propositional representation. This mapping is often called grounding. For example, Figure 1 shows a simple MLN.This MLN does a very simple sort of label-propagation through hyperlinks. As is often the case, this MLN has two parts: the rules $R_{1},R_{2}$, which are weighted first-order clauses; and the database $DB$, which consists of facts (unit clauses) of the form links(a,b) for constants $a,b$. The figure also shows the the grounded version of this MLN, which is an ordinary Markov network: the DB facts become constraints on node values, and the clauses become clique potentials.

Grounding a first-order program can be an expensive operation. For a realistic hyperlink graph, a Markov network with size even linear in the number of facts in the database, $|DB|$, is impractically large for inference. Superficially, it would seem that groundings must inheritly be $o(|DB|)$ for some programs: in the example, for instance, the probability of aboutSport(x) must depends to some extent on the entire hyperlink graph (if it is fully connected). However, it also seems intuitive that if we are interested in inferring information about a specific page—say, the probability of aboutSport(d1)–then the parts of the network only distantly connected to d1 are likely to have a small influence. This suggests that an approximate grounding strategy might be feasible, in which a query such as aboutSport(d1) would be grounded by constructing a small subgraph of the full network, followed by inference on this small “locally grounded” subgraph. Likewise, consider learning (e.g., from a set of queries $Q$ with their desired truth values). Learning might proceed by locally-grounding every query goal, allowing learning to also take less than $O(|DB|)$ time.

In this paper, we present a first-order probabilistic language which is well-suited to approximate “local” grounding. We present an extension to stochastic logic programs (SLP) that is biased towards short derivations, and show that this is related to personalized PageRank (PPR) on a linearized version of the proof space. Based on the connection to PPR, we develop a proveably-correct approximate inference scheme, and an associated proveably-correct approximate grounding scheme: specifically, we show that it is possible to prove a query, or to build a graph which contains the information necessary for weight-learning, in time $O(\frac{1}{\alpha\epsilon})$, where $\alpha$ is a reset parameter associated with the bias towards short derivations, and $\epsilon$ is the worst-case approximation error across all intermediate stages of the proof. This means that both inference and learning can be approximated in time independent of the size of the underlying database—a surprising and important result.

The ability to locally ground queries has another important consequence: it is possible to decompose the problem of weight-learning to a number of moderate-size subtasks (in fact, tasks of size $O(\frac{1}{\alpha\epsilon})$ or less) which are weakly coupled. Based on this we outline a parallelization scheme, which in our initial implementation provides a order-of-magnitude speedup in learning time.

Below, we will first introduce our formalism, and then describe our weight-learning algorithm. We will then present experimental results on a prototypical inference task, and compare the scalability of our method to Markov logic networks. We finally discuss related work and conclude.

Programming with Personalized PageRank (PROPPR)

$G^{\prime}$ is often large or infinite so it is not constructed explicitly. Instead Prolog performs a depth-first search on $G^{\prime}$ to find the first solution vertex $v$—i.e., a vertex with an empty subgoal list—and if one is found, returns the transformed query from $v$ as an answer to $Q$. Table 1 and Figure 2 show a simple Prolog program and a proof graph for it.The annotations after the hashmarks and the edge labels in the proof graph will be described below. For conciseness, only $R_{1},\ldots,R_{k}$ is shown in each node $u=(Q,(R_{1},\ldots,R_{k}))$. Given the query $Q=\textit{about(a,Z)}$, Prolog’s depth-first search would return $Q=\textit{about(a,fashion)}$.

Note that in this proof formulation, the nodes are conjunctions of literals, and the structure is, in general, a digraph (rather than a tree). Also note that the proof is encoded as a graph, not a hypergraph, even if the predicates in the LP are not binary: the edges represent a step in the proof that reduces one conjunction to another, not a binary relation between entities.

2 FROM STOCHASTIC LOGIC PROGRAMS TO PROPPR

In stochastic logic programs (SLPs) , one defines a randomized procedure for traversing the graph $G^{\prime}$ which thus defines a probability distribution over vertices $v$, and hence (by selecting only solution vertices) a distribution over transformed queries (i.e. answers) $Q\theta$. The randomized procedure thus produces a distribution over possible answers, which can be tuned by learning to upweight desired (correct) answers and downweight others.

In past work, the randomized traversal of $G^{\prime}$ was defined by a probabilistic choice, at each node, of which clause to apply, based on a weight for each clause. We propose two extensions. First, we will introduce a new way of computing clause weights, which allows for a potentially richer parameterization of the traversal process. We will associate with each edge ${{u\rightarrow{}v}}$ in the graph a feature vector $\phi_{{{u\rightarrow{}v}}}$. This edge is produced indirectly, by associating with every clause $c\in{}LP$ a function $\Phi_{c}(\theta)$, which produces the $\phi$ associated with an application of $c$ using mgu $\theta$. This feature vector is computed during theorem-proving, and used to annotate the edge ${{u\rightarrow{}v}}$ in $G^{\prime}$ created by applying $c$ with mgu $\theta$. Finally, an edge ${{u\rightarrow{}v}}$ will be traversed with probability $\Pr(v|u)\propto f(\textbf{w},\phi_{{u\rightarrow{}v}})$ where w is a parameter vector and where $f(\textbf{w},\phi)$ is a weighting function—e.g., $f(\textbf{w},\phi)=\exp(\textbf{w}_{i}\cdot\phi)$. This weighting function now determines the probability of a transition, in theorem-proving, from $u$ to $v$: specifically, $\Pr_{\textbf{w}}(v|u)\propto f(\textbf{w},\phi_{{u\rightarrow{}v}})$. Weights in w default to 1.0, and learning consists of tuning these.

These links back to the start vertex bias will the traversal of the proof graph to upweight the results of short proofs. To see this, note that if the restart probability $P(v_{0}|u)=\alpha$ for every node $u$, then the probability of reaching any node at depth $d$ is bounded by $(1-\alpha)^{d}$.

To summarize, if $u$ is a node of the search graph, $u=(Q\theta,(R_{1},\ldots,R_{k}))$, then the transitions from $u$, and their respective probabilities, are defined as follows, where $Z$ is an appropriate normalizing constant:

If $v=v_{0}=(Q,Q)$ is the initial state in $G$, then

If $v$ is any other node, then $\Pr(v|u)=0$.

The requirementThe requirement that the feature literals returned by $\phi_{c}(\theta)$ must be ground in $\theta$ is not strictly necessary for correctness. However, in developing ProPPR programs we noted than non-ground features were usually not what the programmer intended. that edge features $F_{i}\theta$ are ground is the reason for introducing the apparently unnecessary predicate linkedBy(X,Y,W) into the program of Table 1: adding the feature literal by(W) to the second clause for sim would result in a non-ground feature by(W), since $W$ is a free variable when $\Phi_{c}$ is called. Notice also that the weight on the by(W) features are meaningful, even though there is only one clause in the definition of linkedBy, as the weight for applying this clause competes with the weight assigned to the restart edges.

It would be cumbersome to annotate every database fact, and difficult to learn weights for so many features. Thus, if $c$ is the unit clause that corresponds to a database fact, then $\Phi_{c}(\theta)$ returns a default value $\phi=\{\textit{db}\}$, where db is a special feature indicating that a database predicate was used.If a non-database clause $c$ has no annotation, then the default vector is $\phi=\{\textit{id(c)}\}$, where c is an identifier for the clause $c$.

The function $\Phi_{restart}(R)$ depends on the functor and arity of $R$. If $R$ is defined by clauses in $LP$, then $\Phi_{restart}(R)$ returns a unit vector $\phi=\{\textit{defRestart}\}$. If $R$ is a database predicate (e.g., hasWord(doc1,W)) then we follow a slightly different procedure, which is designed to ensure that the restart link has a reasonably large weight even with unit feature weights: we compute $n$, the number of possible bindings for $R$, and set $\phi[\textit{defRestart}]=n\cdot{}\frac{\alpha}{1-\alpha}$, where $\alpha$ is a global parameter. This means that with unit weights, after normalization, the probability of following the restart link will be $\alpha$.

Putting this all together with the standard iterative approach to computing personalized PageRank over a graph , we arrive at the following inference algorithm for answering a query $Q$, using a weight vector w. Below, we let $N_{v_{0}}(u)$ denote the neighbors of $u$—i.e., the set of nodes $v$ where $\Pr(v|u)>0$ (including the restart node $v=v_{0}$). We also let W be a matrix such that $\textbf{W}[u,v]=\Pr_{\textbf{w}}(v|u)$, and in our discussion, we use $\textbf{ppr}(v_{0})$ to denote the personalized PageRank vector for $v_{0}$.

Let $v_{0}=(Q,Q)$ be the start node of the search graph. Let $G$ be a graph containing just $v_{0}$. Let $\textbf{v}^{0}=\{v_{0}\}$.

For $t=1,\ldots,T$ (i.e., until convergence):

Let $\textbf{v}^{t}$ be an all-zeros vector.

For each $u$ with non-zero weight in $\textbf{v}^{t-1}$, and each $v\in{}N_{u+0}(u)$, add $(u,v,\phi_{{{u\rightarrow{}v}}})$ to $G$ with weight $\Pr_{\textbf{w}}(v|u)$, and set $\textbf{v}^{t}=\textbf{W}\cdot\textbf{v}^{t-1}$

At this point $\textbf{v}^{T}\approx\textbf{ppr}(v_{0})$. Let $S$ be the set of nodes $(Q\theta,\Box)$ that have empty subgoal lists and non-zero weight in $\textbf{v}^{T}$, and let $Z=\sum_{u\in{}S}\textbf{v}^{T}[u]$. The final probability for the literal $L=Q\theta$ is found by extracting these solution nodes $S$, and renormalizing:

For example, given the query $Q=\textit{about(a,Z)}$ and the program of Table 1, this procedure would give assign a non-zero probability to the literals about(a,sport) and about(a,fashion), concurrently building the graph of Figure 2.

3 LOCALLY GROUNDING A QUERY

Note that this procedure both performs inference (by computing a distribution over literals $Q\theta$) and “grounds” the query, by constructing a graph $G$. ProPPR inference for this query can be re-done efficiently, by running an ordinary PPR process on $G$. This is useful for faster weight learning. Unfortunately, the grounding $G$ can be very large: it need not include the entire database, but if $T$ is the number of iterations until convergence for the sample program of Table 1 on the query $Q=about(d,Y)$, $G$ will include a node for every page within $T$ hyperlinks of $d$.

To construct a more compact local grounding graph $G$, we adapt an approximate personalized PageRank method called PageRank-Nibble . This method has been used for the problem of local partitioning: in local partitioning, the goal is to find a small, low-conductanceFor small subgraphs $G_{S}$, conductance of $G_{S}$ is the ratio of the weight of all edges exiting $G_{S}$ to the weight of all edges incident on a node in $G_{S}$. component of a large graph $G$ that contains a given node $v$.

The PageRank-Nibble-Prove algorithm is shown in Table 2. It maintains two vectors: p, an approximation to the personalized PageRank vector associated with node $v_{0}$, and r, a vector of “residual errors” in p. Initially, $\textbf{p}=\emptyset$ and $\textbf{r}=\{v_{0}\}$. The algorithm repeatedly picks a node $u$ with a large residual error $\textbf{r}[u]$, and reduces this error by distributing a fraction $\alpha^{\prime}$ of it to $\textbf{p}[u]$, and the remaining fraction back to $\textbf{r}[u]$ and $\textbf{r}[v_{1}],\ldots,\textbf{r}[v_{n}]$, where the $v_{i}$’s are the neighbors of $u$. The order in which nodes $u$ are picked does not matter for the analysis (in our implementation, we follow Prolog’s usual depth-first search as much as possible.) Relative to PageRank-Nibble, the main differences are the the use of a lower-bound on $\alpha$ rather than a fixed restart weight and the construction of the graph $\hat{G}$.

Following the proof technique of Andersen et al, it can be shown that after each push, $\textbf{p}+\textbf{r}=\textbf{ppr}(v_{0})$. It is also clear than when PageRank-Nibble terminates, then for any $u$, the error $\textbf{ppr}(v_{0})[u]-\textbf{p}[u]$ is bounded by $\epsilon{}N(u)$: hence, in any graph where $N(u)$ is bounded, a good approximation can be obtained. It can also be shown that the subgraph $\hat{G}$ (of the full proof space) is in some sense a “useful” subset: for an appropriate setting of $\epsilon$, if there is a low-conductance subgraph $G_{*}$ of the full graph that contains $v_{0}$, then $G_{*}$ will be contained in $\hat{G}$: thus if there is a subgraph $G_{*}$ containing $v_{0}$ that approximates the full graph well, PageRank-Nibble will find (a supergraph of) $G_{*}$.

Finally, we have the following efficiency bound:

Let $u_{i}$ be the $i$-th node pushed by PageRank-Nibble-Prove. Then $\sum_{i}|N(u_{i})|<\frac{1}{\alpha^{\prime}\epsilon}$.

This can be proved by noting that initially $|\textbf{r}|_{1}=1$, and also that $|\textbf{r}|_{1}$ decreases by at least $\alpha^{\prime}\epsilon|N(u_{i})|$ on the $i$-th push. As a direct consequence we have the following:

The number of edges in the graph $\hat{G}$ produced by PageRank-Nibble-Prove is no more than $\frac{1}{\alpha^{\prime}\epsilon}$.

Importantly, the bound holds independent of the size of the full database of facts. The bound also holds regardless of the size or loopiness of the full proof graph, so this inference procedure will work for recursive logic programs.

To summarize, we have outlined an efficient approximate proof procedure, which is closely related to personalized PageRank. As a side-effect of inference for a query $Q$, this procedure will create a ground graph $\hat{G}_{Q}$ on which personalized PageRank can be run directly, without any (relatively expensive) manipulation of first-order theorem-proving constructs such as clauses or logical variables. As we will see, this “locally grounded” graph will be very useful in learning weights w to assign to the features of a ProPPR program.

As an illustration of the sorts of ProPPR programs that are possible, some small sample programs are shown in Figure 3. Clauses $c_{1}$ and $c_{2}$ are, together, a bag-of-words classifier: each proof of predictedClass(D,Y) adds some evidence for $D$ having class $Y$, with the weight of this evidence depending on the weight given to $c_{2}$’s use in establishing related(w,y), where $w$ and $y$ are a specific word in $D$ and $y$ is a possible class label. In turn, $c_{2}$’s weight depends on the weight assigned to the $r(w,y)$ feature by w, relative to the weight of the restart link.The existence of the restart link thus has another important role in this program, as it avoids a sort of “label bias problem” in which local decisions are difficult to adjust. Adding $c_{3}$ and $c_{4}$ to this program implements label propagation, and adding $c_{5}$ and $c_{6}$ implements a sequential classifier.

In spite of its efficient inference procedure, and its limitation to only definite clauses, ProPPR appears to have much of the expressive power of MLNs , in that many useful heuristics can apparently be encoded.

4 LEARNING FOR PROPPR

As noted above, inference for a query $Q$ in ProPPR is based on a personalized PageRank process over the graph associated with the SLD proof of a query goal $G$. More specifically, the edges ${{u\rightarrow{}v}}$ of the graph $G$ are annotated with feature vectors $\phi_{{{u\rightarrow{}v}}}$, and from these feature vectors, weights are computed using a parameter vector w, and finally normalized to form a probability distribution over the neighbors of $u$. The “grounded” version of inference is thus a personalized PageRank process over a graph with feature-vector annotated edges.

We adopt this learning for ProPPR, with some modifications. The training data $D$ is a set of triples $\{(Q^{1},P^{1},N^{1}),\ldots,(Q^{m},P^{m},N^{m})\}$ where each $Q^{k}$ is a query, $P^{k}=\langle Q\theta_{+}^{1},\ldots,Q\theta_{+}^{I}\rangle$ is a list of correct answers, and $N^{k}$ is a list $\langle Q\theta_{-}^{1},\ldots,Q\theta_{-}^{J}\rangle$ incorrect answers. Each such triple is then locally grounded using the PageRank-Nibble-Prove method and used to produce a set $I*J$ of “learning-to-order” triples of the form $(v^{k}_{0},u_{+}^{k,i},u_{-}^{k,j})$ where $v_{0}^{k}$ corresponds to $Q^{k}$, and the $u$’s are the nodes in $\hat{G}_{Q^{K}}$ that correspond to the (in)correct answers for $Q^{K}$. We use a squared loss on the difference of scores $h=\textbf{p}_{v_{0}}[u_{+}]-\textbf{p}_{v_{0}}[u_{-}]$, i.e.,

and $L_{2}$ regularization of the parameter weights. Hence the final function to be optimized is

To optimize this loss, we use stochastic gradient descent (SGD), rather than the quasi-Newton method of Backstrom and Leskovic. Weights are initialized to $1.0+\delta$, where $\delta$ is randomly drawn from $[0,0.01]$. We set the learning rate $\beta$ of SGD to be $\beta=\frac{\eta}{epoch^{2}}$ where $epoch$ is the current epoch in SGD, and $\eta$, the initial learning rate, defaults to 1.0.

We implemented SGD because it is fast and has been adapted to parallel learning tasks . Local grounding means that learning for ProPPR is quite well-suited to parallelization. The step of locally grounding each $Q_{i}$ is “embarassingly” parallel, as every grounding can be done independently. To parallelize the weight-learning stage, we use multiple threads, each of which computes the gradient over a single grounding $\hat{G}_{Q^{k}}$, and all of which accesses a single shared parameter vector w. Although the shared parameter vector is a potential bottleneck , it is not a severe one, as the gradient computation dominates the learning cost.This is not the case when learning a linear classifier, where gradient computations are much cheaper.

EXPERIMENTS

To evaluate this method, we use data from an entity resolution task previously studied as a test case for MLNs . The program we use in the experiments is shown in Table 4: it is approximately the same as the MLN(B+T) approach from Singla and Domingos.The principle difference is that we do not include tests on the absence of words in a field in our clauses. To evaluate accuracy, we use the CORA dataset, a collection of 1295 bibliography citations that refer to 132 distinct papers. Throughout the experiments, we set the regularization coefficient $\mu$ to $0.001$, the total number of epochs to 5, and learning rate parameter $\eta$ to 1. A standard log loss function was used in our objective function.

2 RESULTS

We first consider the cost of the PageRank-Nibble-Prove inference/grounding technique. Table 5 shows the time required for inference (with uniform weights) for a set of 52 randomly chosen entity-resolution tasks from the CORA dataset, using a Python implemention of the theorem-prover. We report the time in seconds for all 52 tasks, as well as the mean average precision (MAP) of the scoring for each query. It is clear that PageRank-Nibble-Prove offers a substantial speedup on these problems with little loss in accuracy: on these problems, the same level of accuracy is achieved in less than a tenth of the time.

While the speedup in inference time is desirable, the more important advantages of the local grounding approach are that (1) grounding time, and hence inference, need not grow with the database size and (2) learning can be performed in parallel, by using multiple threads for parallel computations of gradients in SGD. Figure 3 illustrates the first of these points: the scalability of the PageRank-Nibble-Prove method as database size increases. For comparison, we also show the inference time for MLNs with three well-published inference methods: Gibbs refers to Gibbs sampling, and Lifted BP is the lifted belief propagation method. We also compare with the maximum a posteriori (MAP) inference approach, which does not return probabilistic estimates of the specified queries. In each case the performance task is inference over 16 test queries.

Note that ProPPR’s runtime is constant, independent of the database size: it takes essentially the same time for $2^{8}=256$ entities as for $2^{4}=16$. In contrast, lifted belief propagation is around 1000 times slower on the larger database.

Figure 4 explores the speedup in learning (from grounded examples) due to multi-threading. The weight-learning is using a Java implementation of the algorithm which runs over ground graphs. The full CORA dataset was used in this experiment. As can be seen, the speedup that is obtained is nearly optimal, even with 16 threads running concurrently.

We finally consider the effectiveness of weight learning. We train on the first four sections of the CORA dataset, and report results on the fifth. Following Singla and Domingos we report performance as area under the ROC curve (AUC). Table 6 shows AUC on the test set used by Singla and Domingos for several methods. The line for MLN(Fig 1) shows results obtained by an MLN version of the program of Figure 1. The line MLN(S&D) shows analogous results for the best-performing MLN from . Compared to these methods, ProPPR does quite well even before training (with unit feature weights, w=1); the improvement here is likely due to the ProPPR’s bias towards short proofs, and the tendency of the PPR method to put more weight on shared words that are rare (and hence have lower fanout in the graph walk.) Training ProPPR improves performance on three of the four tasks, and gives the most improvement on citation-matching, the most complex task.

The results in Table 6 all use the same data and evaluation procedure, and the MLNs were trained with the state-of-the-art Alchemy system using the recommended commands for this data (which is distributed with Alchemyhttp://alchemy.cs.washington.edu). However, we should note that the MLN results reproduced here are not identical to previous-reported ones . Singla and Domingos used a number of complex heuristics that are difficult to reproduce—e.g., one of these was combining MLNs with a heuristic, TFIDF-based matching procedure based on canopies . While the trained ProPPR model outperformed the reproduced MLN model in all prediction tasks, it outperforms the reported results from Singla and Domingos only on venue, and does less well than the reported results on citation and authorPerformance on title matching is not reported by Singla and Domingos..

RELATED WORK

Although we have chosen here to compare experimentally to MLNs , ProPPR represents a rather different philosophy toward language design: rather than beginning with a highly-expressive but intractible logical core, we begin with a limited logical inference scheme and add to it a minimal set of extensions that allow probabilistic reasoning, while maintaining stable, efficient inference and learning. While ProPPR is less expressive than MLNs (for instance, it is limited to definite clause theories) it is also much more efficient. This philosophy is similar to that illustrated by probabilistic similarity logic (PSL) ; however, unlike ProPPR, PSL does not include a “local” grounding procedure, which leads to small inference problems, even for large databases.

Technically, ProPPR is most similar to stochastic logic programs (SLPs) . The key innovation is the integration of a restart into the random-walk process, which, as we have seen, leads to very different computational properties.

There has been some prior work on reducing the cost of grounding probabilistic logics: noteably, Shavlik et al describe a preprocessing algorithm called FROG that uses various heuristics to greatly reduce grounding size and inference cost, and Niu et al describe a more efficient bottom-up grounding procedure that uses an RDBMS. Other methods that reduce grounding cost and memory usage include “lifted” inference methods (e.g., ) and “lazy” inference methods (e.g., ); in fact, the LazySAT inference scheme for Markov networks is broadly similar algorithmically to PageRank-Nibble-Prove, in that it incrementally extends a network in the course of theorem-proving. However, there is no theoretical analysis of the complexity of these methods, and experiments with FROG and LazySAT suggest that they still lead to a groundings that grow with DB size, albeit more slowly.

ProPPR is also closely related to the Path Ranking Algorithm (PRA), learning algorithm for link prediction . Like ProPPR, PRA uses random-walk methods to approximate logical inference. However, the set of “inference rules” learned by PRA corresponds roughly to a logic program in a particular form—namely, the form

ProPPR allows much more general logic programs. However, unlike PRA, we do not consider the task of searching for new logic program clauses.

CONCLUSIONS

We described a new probabilistic first-order language which is designed with the goal of highly efficient inference and rapid learning. ProPPR takes Prolog’s SLD theorem-proving, extends it with a probabilistic proof procedure, and then limits this procedure further, by including a “restart” step which biases the system to short proofs. This means that ProPPR has a simple polynomial-time proof procedure, based on the well-studied personalized PageRank (PPR) method.

Following prior work on PPR-like methods, we designed a local grounding procedure for ProPPR, based on local partitioning methods , which leads to an inference scheme that is an order of magnitude faster that the conventional power-iteration approach to computing PPR, takes time $O(\frac{1}{\epsilon\alpha^{\prime}})$, independent of database size. This ability to “locally ground” a query also makes it possible to partition the weight learning task into many separate gradient computations, one for each training example, leading to a weight-learning method that can be easily parallelized. In our current implementation, an additional order-of-magnitude speedup in learning is made possible by parallelization. Experimentally, we showed that ProPPR performs well, even without weight learning, on an entity resolution task, and that supervised weight-learning improves accuracy.

References