Learning Web Page Scores by Error Back-Propagation

1 Introduction

In this paper we propose an algorithm able to learn a generic distribution of values over the nodes of a graph with symbolic labels. In many applications, the input data is naturally represented by a labeled graph. However, the actual lack of adequate algorithms to directly process this structured data commonly forces to convert the input patterns to vectors of real numbers, loosing significant information. In particular, "Web like" data structures are common in many pattern recognition tasks and possible applications range from object recognition in segmented images to molecular analysis in bioinformatics, and so on.

Like in the PageRank algorithm [Page et al., 1998], the score of a node is assumed to correspond to the probability that a random walker will visit that node at any given time. The score distribution computed by the random walker depends both on the connectivity graph and the labels assigned to each node. Markov Chain theory allows to define a set of constrains on the parameters of the random walker in order to guarantee some desired features like convergence and independence of the final distribution on the initial state. A learning algorithm which is based on error back-propagation through the graph is used to optimize the parameters of the random walker minimizing the distance of the scores assigned by the walker from the target values provided by a supervisor for some nodes in the graph.

Previous work in the same field achieved very limited results. For example, in [Kondor and Lafferty, 2002] the authors present an algorithm that processes only non labeled graphs, while the technique presented in [Chang et al., 2000] is very application specific and features very limited generalization capabilities. In [Tsoi et al., 2003] a method to modify PageRank scores computed over a collection of pages on the basis of a supervisor's feedback is proposed. This algorithm has limited approximation capabilities, since it controls only a term of the PageRank equation and it does not optimize how the scores flow though the connectivity graph.

The algorithm presented in this paper allows to learn target scores assigned as real numbers, and this makes it more general than the one proposed in [Diligenti et al., 2003] which allows only to specify a set of nodes whose scores should be increased or decreased.

The paper is organized as follows. In the next section the web surfer model is introduced. Then, in section 3 the learning algorithm based on error back-propagation is described, while the experimental results are presented in section 4. Finally, in section 5 the conclusions are drawn.

2 RandomWalks

We consider the model of a graph walker that can perform one out of two atomic actions while visiting the Web graph: jumping to a node of the graph (action J) and following a hyperlink from the current node (action l).

In general, the action taken by the surfer will depend on the label and outlinks from the node where it is located. We can model the user's behavior by a set of probabilities which depend on the current node: x(l|q) is the probability of following one hyperlink from node q, and x(J|q) = 1 - x(l|q) is the probability of jumping from node q.

The two actions need to specify their targets: x(p|q, J) is the probability of jumping from node q to node p, and x(p|q, l) is the probability of selecting a hyperlink from node q to node p. x(p|q, l) is not null only for the nodes p linked directly by node q, i.e. p ∈ ch(q), being ch(q) the set of the children of node q in the graph G. These sets of values must satisfy the probability normalization constraints ∀q ∈ G ∑p∈G x(p|q, J) = 1 and ∑p∈ch(q) x(p|q, l) = 1.

The model considers a temporal sequence of actions performed by the surfer and it can be used to compute the probability xp(t) that the surfer is located in node p at time t. The probability distribution on the nodes of the Web is updated by taking into account the actions at time t+1 using the following equation

where pa(p) is the set of the parents of node p. The score xp of a node p is computed using the stationary distribution of the Markov Chain defined by equation (1) (i.e. xp = limt→∞xp(t)). The probability distribution over all the nodes at time t is represented by the vector x(t) = [x1(t), . . . , xN(t)]′ , being N the total number of nodes.

An interesting property of this model is that, under the assumption that x(J|q) ̸= 0 and x(p|q, J) ̸= 0, ∀p, q ∈ G, the stationary distribution x⋆ does not depend on the initial state vector x(0) (see [Diligenti et al., 2002]). For example this is true for the PageRank equation for which x(J|q) = 1 - d, being 0 < d < 1, and x(p|q, J) = 1N .

The random walker model of equation (1) is a simplified version of the model proposed in [Diligenti et al., 2002], where two additional actions are considered by allowing the surfer to follow backlinks or to remain in the same node. The learning algorithm proposed in the next section can be easily extended to this more general model.

3 Learning the score distribution

The random surfer assigns the scores according to the probabilities x(p|q, J), x(J|q), x(p|q, l), and x(l|q). In most of the approaches proposed in the literature, these parameters are predefined or computed from some features describing the node p and/or the node q. For example, setting the parameters to x(l|q) = d, x(J|q) = 1 - d, x(p|q, J) = 1N , and x(p|q, l) = 1 ch(q) , we obtain the popular PageRank random surfer [Page et al., 1998].

In the general case, the model has a number of parameters quadratic in the number of nodes and it is infeasible to estimate these parameters without any assumption to reduce their number. In particular, we assume that the labels of nodes can assume n distinct values C = {c1, . . . , cn} and that the surfer's behavior for any node p is dependent only on its label cp ∈ C and the labels of the nodes pointed by p. Therefore, the parameters of the model are rewritten as:

where cq ∈ C is the label of node q and |cp | is the number of nodes with label cp . The parameter x(cp |cq , l) represents the tendency of the surfer to follow a hyperlink from a node with label cq to a node with label cp , the parameter x(cp |cq , J) is the probability of the surfer to jump from a node with label cq to a node with label cp and x(l|ci) = 1 - x(J|ci) represents the probability that the surfer decides to follow a link out of a node with label ci. In the following, we indicate as P the set of model parameters. T , J , B indicate transition, jump and behavior parameters, respectively. In particular, it holds that: P = {T ,J , B}, T = {x(ci|cj, l) i, j = 1, . . . , n}, J = {x(ci|cj, J) i, j = 1, . . . , n}, and B = {x(l|ci) i = 1, . . . , n}. Under these assumptions, the random surfer equation becomes,

Typically, the values x(cp |cq , l) are initialized to 1, such that all links are equally likely to be followed. Because of the model assumptions, the stronger is the tendency of the surfer to move to a node with a specific label, the higher are the scores associated to the nodes with that label. These assumptions reduce the number of free parameters to 2·(n2-n)+n = 2 · n2 - n, being n the number of distinct labels.

3.1 Learning the parameters

We assume that a supervisor provides a set of examples E in the graph G, where each example s ∈ E is a node associated to a target score xds .

Consider the following cost function for the scores computed by a surfer model using the set of parameters P,

where ePs is called instant error for the node s. Such error takes into account the distance between the target score and the value returned by the ranking function.

We want to minimize the cost function (3) by gradient descent with respect to a generic parameter w ∈ P, i.e.,

Using a procedure similar to the back-propagation through time algorithm (BPTT) [Haykin, 1994], commonly used in training recurrent neural networks, for each node s in the training set we unfold the graph starting from s at time T and moving backward in time through the path followed by the random surfer. The graph unfolding is basically a backward breadth-first visit of the graph, starting from the target node at time T, where each new unfolded level corresponds to moving backward of one time step. Each unfolded node is associated to the variable xq(T -t) where q is the corresponding graph node, t is the number of backward steps from the target node. Similarly, the parameters of the model are split into an independent set of parameters corresponding to the different time steps. We indicate with P(t) the model parameters at time t and with w(t) ∈ P(t) the value of any given parameter at time t. An infinite unfolding is perfectly equivalent to the original graph with respect to the computation of the score xPs (T) for a target node s. However, the unfolding takes into account only the score propagation due to the forward links, whereas the contribution of jumps (coming from any node in the graph) is neglected.

In the following, we indicate as Us(t) the set of nodes contained in the unfolding centered on node s for the time step t. See figure 1 for an example of graph unfolding.

Thanks to the parameter decoupling in the unfolding, a parameter w(t) influences only the scores at the following time step. Thus, the derivative of the instant error with respect to a parameter w(t) can be written as,

Assuming that the parameters of the surfer are stationary (i.e. they do not depend on time: w(t) = w ∀t), the derivative with respect to a single parameter can be obtained summing all the contributions for the single time steps,

The term ∂ePs ∂xPp (t+1) in equation (6) can not be directly computed, unless when t = T - 1, s = p. In this latter case, it holds that,

Let δp(t) indicate ∂ePs ∂xPp (t) . If p is not a target node, then ∂ePs ∂xPp (t) can be rewritten as,

where ch(p) is the set of children of node p in the unfolding and P(p, t1 → z, t2) indicates the probability of the surfer to follow a path in the unfolding connecting the node p at time t1 to the node z at time t2. Only the influence of transition parameters on the score of node p was taken into account in the propagation of the delta values.

Neglecting the influence of the jump parameters (i.e. taking into account only the influence due to link following) is an accurate approximation when the probability of following a link is much higher than the probability of jumping (like it is commonly assumed in PageRank). However, the experimental results show that such an approximation provides good results in the general case.

A generic node p at time t has influence over a supervised node s at time T proportional to the probability P(p, t → s, T) that the surfer will follow the path from the node p at time t to the central node s at time T. An implication of this result is that farther nodes will have less influence, given the exponential decrease of the probability of following a path with its length. In particular, a node p influences ∂ePs ∂xPp (t) only if P(p, t → s, T) ̸= 0. Since Us(T - t) is the set of nodes from which it is possible to reach node s at time T starting at time t, only for the nodes in this set it holds that P(p, t → s, T) ̸= 0. Thus, in equation (8) not all the score variables at time t + 1 must be considered in the application of the chain rule. Inserting equation (8) into (6), and limiting the chain rule only to the nodes with a non-zero influence, yields,

Since the stable point of the system does not depend on the initial state, without loss of generality, the unfolding can be interrupted at time 1 (the graph is unfolded T times) assuming that T is large enough so that the state before time 1 has no effect on the final state (this is also expressed by the fact that the probability of following a path in the unfolding P(p, t → s, T ) converges to 0 when the path length T - t increases),

In the following sections, we compute the derivative ∂xPp (t+1) ∂w(t) to be inserted into equation (9) for a transition, jump and behavior parameter.

3.2 Learning the transition parameters

For a transition parameter w = x(ci|cj, l), equation (2) shows that ∂xPp (t+1) ∂x(ci|cj,l)(t) = 0 if cp ̸= ci. On the other hand if cp = ci, it holds that,

The application of the derivative rule for a fraction of functions, yields that when cp = ci,

where |k ∈ ch(q) : ck = ci| is the number of children nodes of q having label ci.

Without loss of generality, it can be assumed that the system has already converged at time 0 (i.e. xq = xq(t), t = 0, . . . , T, ∀q ∈ G). Inserting equation (10) into (9) and, after removing all temporal dependencies from the parameters and from the node scores under the assumption of model stationarity and convergence at time 0, the derivative of the instant error for the considered transition parameter is obtained.

Averaging over all the examples, the model parameters can be updated by gradient descent according to equation (4). The new parameters can be used to compute a new score distribution over the nodes xPp . Function optimization and score estimation can be iterated through multiple epochs, till a termination criterion is satisfied.

3.3 Learning the jump parameters

For a jump parameter w = x(ci|cj , J), equation (2) shows that it holds that,

where |ci| indicates the number of nodes in the graph Gwith label ci. The previous equation can be inserted into (9) and, removing all temporal dependencies under the assumption of model convergence and stationarity, yields the derivative of the instant error with respect to a jump parameter.

3.4 Learning the surfer action bias

Following a procedure similar to that shown for the transition and jump parameters, we start computing the derivative ∂xPp (t+1) ∂x(l|ci)(t) for a single parameter.

In particular, equation (2) shows that,

where the surfer model is assumed to respect the probabilistic constrains at every time step, i.e. x(J|ci)(t) = 1-x(l|ci)(t).

Merging equation (9) and (11) under the assumption of model stationarity and convergence at time 0, yields the derivative of the instant error with respect to a behavior parameter. All parameters can be simultaneously updated as described in section 3.2, 3.3 and 3.4 to train the model. After the updating, the jump and behavior parameters must be normalized to respect the probabilistic constrains.

Finally, using an EM-style algorithm [Dempster et al., 1977] the adapted surfer model can re-surf the Web graph yielding a new estimate of the scores. The procedure can be repeated till a stop criterion is satisfied. Since the parameters are estimated from a few levels deep unfoldings, only a small set of nodes must be considered at each iteration. The main overhead of the proposed learning algorithm is the full PageRank computation that must be completed at each step. Our experiments show that usually only very few iterations are needed to converge.

4 Experimental results

The experiments were performed on two datasets, which were collected by focus crawling the Web [Diligenti et al., 2000], on the topics "wine" and "Playstation", respectively. The "wine" dataset contains 1.000.000 documents, while the "Playstation" one 500.000. The documents were clustered using a hierarchical version of the k-means algorithm [Duda and Hart, 1973]. In particular, in two different runs, we clustered the pages from the dataset on topic "Playstation" into 25 sets, whereas the dataset on topic "wine" was clustered into 25 and 100 sets.

Two topic-specific search engines were built containing the downloaded documents. The rank of each page in the dataset was computed using a random walker producing the standard PageRank scores. We tested the quality of the ranking function by submitting a set of queries to the search engine whose results were sorted by the scores assigned by the random surfer. By browsing the results, we found pages which were authorities on the specific topic but were (incorrectly) not inserted in the top positions of the result list. Such pages were selected as examples of pages which should get a higher rank (positive examples). A target score equal to one (the maximum reachable score according to the model) was assigned to the positive examples. On the other hand, we found pages having a high rank which were not authorities for the topic. Such pages were selected as negative examples and a target score equal to zero was assigned to those pages. The learning algorithm, as previously described was applied to these datasets, using the selected examples. Only a small set of examples (3-15) was typically labeled as positive or negative in any single experiment.

4.1 Analysis of the effects of learning

This first group of experiments aims at demonstrating that the surfer model as learned by the proposed training algorithm, could not be generated by a non-adaptive schema as the focused versions of PageRank proposed in the literature.

In figure 2, we show the values of the transition, jump and behavior parameters for each cluster, resulting from the training sessions for a surfer on the topic "Playstation". The learned parameters represent a complex interaction of the resulting surfer with the page clusters where a few clusters are strongly boosted and a few other strongly demoted. This behavior (expecially targeted demotions) can not be expressed by the focused versions of PageRank [Richardson and Domingos, 2002; Diligenti et al., 2002], which simply boost all the parameters leading to the clusters of relevant pages (according to the simplistic assumption that relevant pages are more likely to point to other relevant pages). This demonstrates that the trained surfer is able to exploit hierarchies of topics to model the complex path leading to good/bad pages.

In figure 3-(a) and 3-(b), there are plotted the probabilities that the surfer is located in a page of a specific cluster. In particular we show the results for the dataset on topic "wine" clustered into 100 groups and a random graph with 200.000 nodes clustered into 25 groups. The learning algorithm is able to increase the likelihood of the random surfer to visit pages belonging to a set of clusters, while decreasing its probability of visiting pages belonging to other clusters.

Figure 4 shows the value of the cost function EP at each iteration. Each plot reports the cost function when a specific set of parameters is optimized during training. The behavior parameters are less effective than the jump parameters in optimizing the surfer model. However, neither the behavior or the jump parameters are as effective as the transition parameters. As expected, when all parameters considered during the learning process, the cost function reaches its minimum.

In figure 5, there are shown the scores of the pages of cluster 8 of the dataset "Playstation" before and after learning. This cluster was manually detected as strongly on the topic "Playstation" and 3 pages belonging this cluster were explicitly inserted in learning set as pages that should get an higher score. As expected the rank of the other pages in this cluster was boosted up thanks to the capability of the algorithm to generalize from a small number of training examples.

4.2 Qualitative results

This experiment compares the quality of the page ranks before and after training. In particular, some authoritative pages on the topic "wine" were provided as positive examples, while some authoritative pages on other topics were provided as negative examples. Figure 6 reports the pages which obtained the largest variation in their rank. The pages that ob-

Most descending pages on topic "wine"

http://www.macromedia.com/go/getflashplayer

http://www.netscape.com

http://www.macromedia.com/downloads

http://www.yahoo.com

http://www.adobe.com/products/acrobat/readstep.html

http://help.yahoo.com

http://www.nl.placestostay.com/index.html

http://home.netscape.com

http://www.forgottensoldier.com

http://www.inntravels.com

Most ascending pages on topic "wine"

http://www.winecountry.com

http://webwinery.com

http://www.ny-wine.com/wineinfo.asp

http://www.wine-searcher.com

http://www.insidewine.com

http://webwinery.com

http://www.viniesaporidipuglia.com/en/index.html

http://www.vinitaly.com/home en.asp

http://www.wineinstitute.org

http://www.winespectator.com

Figure 6: URLs of the pages that yielded either the largest negative or positive rank changes among the pages that were initially in the top 1000 scoring documents.

tained a negative rank variation were either topic-generic authoritative pages (e.g. www.netscape.com) or pages relevant for different topics than "wine" (e.g. "www.forgottensoldier.org"). Among the pages that got a negative rank variation, only the page "www.yahoo.com" was specified as a negative example. On the other hand, the pages that obtained a positive rank variation were effectively authoritative pages on the topic "wine" (e.g. "www.wine-searcher.com" or "webwinery.com"). Among the most ascending documents, only the page "www.winespectator.com" was explicitly provided to the system as a positive example, whereas other pages were pushed up thanks to the capability of the system to generalize from a small set of training examples.

5 Conclusions

In this paper we introduced a novel algorithm to learn a score distribution over the nodes of a labeled graph. The learning algorithm adapts the parameters of a random surfer in order to match the target scores assigned on a small subset of the nodes. Since the parameters are estimated from the unfoldings of the graph centered on the example nodes, the learning algorithm is efficient and can be applied to graphs with many nodes. The learning algorithm was applied to the problem of learning a generic ranking function on the portion of the Web graph.