On the five-page web of PageRank, page $A$ ranked first. It has a single in-link, from $C$, and $C$ passes it everything. Page $C$ is linked from three pages and came second. A reader looking for the best source on that small web might reasonably prefer $C$, and might also want to know which pages are good places to start from, a question PageRank does not ask. Can the links separate pages that are good sources from pages that are good guides to sources, and score each kind? They can: the method called HITS gives every page two scores, and on the five-page web it makes $C$ the leading source and gives $A$ nothing.
HITS, for hyperlink-induced topic search, is due to Kleinberg (1999). It calls a good source an authority and a good guide a hub, and defines each by the other: a good hub links to many good authorities, and a good authority is linked from many good hubs. Unlike PageRank, it is run at query time, on a small graph gathered for that query.
Here is the route. First we build the graph HITS runs on, the root set and base set. Then we state the two updates and run one round by hand. Next we write them as matrices, trace the iteration on the five-page web until it settles, and prove that it always settles, to principal eigenvectors of two matrices. We look at what goes wrong when the largest eigenvalue is repeated, and read the result as a singular value decomposition. Finally we compare HITS with PageRank and with SALSA, and solve worked problems. The article assumes PageRank, which defines eigenvectors, power iteration and the five-page web.
The graph: root set and base set
HITS does not score the whole web. It scores a few thousand pages chosen for one query, and the choice is half of the method. Kleinberg (1999, §2) builds the set in two steps.
- The root set. Send the query to a text search engine and keep its top $t$ results. Kleinberg used $t = 200$.
- The base set. Add every page that a root page links to, and pages that link to a root page, at most $d$ of them for each root page. Kleinberg used $d = 50$, and reports base sets of 1,000 to 5,000 pages.
The reasons for the second step are the reasons the method exists. The root set contains the query's words, but a strong authority often does not: the course text's example is that many of IBM's pages are authoritative on computer hardware without containing those words (Manning, Raghavan, and Schütze, 2008, §21.3.1). Such a page is likely to be linked from some root page, and following out-links brings it in. In the other direction, a root page that is an authority brings in the hubs that point to it. The root set alone also has too few links to analyze: Kleinberg found only 15 links between pages in different domains in the root set for the query java, out of $200 \times 199 = 39{,}800$ possible. The cap $d$ is needed because some pages are linked from hundreds of thousands of others.
One refinement removes links that carry no judgment. Kleinberg deletes intrinsic links, those between pages with the same domain name, and keeps transverse links, those between different domains. Links within a site mostly serve navigation. What remains is a directed graph on the base set, and the rest of the method uses only that graph. From this point the query's words play no further part.
The two updates
Give every page $p$ of the graph an authority score $x_p$ and a hub score $y_p$, all starting at 1. Write $q \to p$ when page $q$ links to page $p$. HITS repeats two updates:
$$x_p \leftarrow \sum_{q \to p} y_q, \qquad y_p \leftarrow \sum_{p \to q} x_q.$$
The first sets a page's authority to the total hub score of the pages that link to it. The second sets a page's hub score to the total authority of the pages it links to. After each round the scores are rescaled, since only their proportions matter. Kleinberg (1999, §3) scales each vector so that its squares sum to 1. This article scales each to sum to 1, which changes the numbers but not their proportions or the order of the pages. Without rescaling they would grow without bound.
Example (one round on the five-page web). After the first round, $C$ is the leading authority and $A$ and $B$ are the leading hubs. The five-page web has the links $A \to B$, $A \to C$, $B \to C$, $B \to E$, $C \to A$ and $D \to C$. With every hub score equal to 1, the authority update counts in-links:
$$(x_A, x_B, x_C, x_D, x_E) = (1,\ 1,\ 3,\ 0,\ 1).$$
The hub update then adds the new authority scores of each page's targets. $A$ links to $B$ and $C$, so $y_A = 1 + 3 = 4$. $B$ links to $C$ and $E$, so $y_B = 3 + 1 = 4$. $C$ links to $A$, so $y_C = 1$. $D$ links to $C$, so $y_D = 3$. $E$ links to nothing, so $y_E = 0$. Dividing each vector by its sum gives
$$x = (0.1667,\ 0.1667,\ 0.5,\ 0,\ 0.1667), \qquad y = (0.3333,\ 0.3333,\ 0.0833,\ 0.25,\ 0).$$
$D$ already shows the separation of the two roles. Nothing links to it, so its authority is zero, yet it is a fair hub because its one link goes to the best authority.
The updates as matrices
Let $M$ be the adjacency matrix of the graph: $M_{qp} = 1$ if $q$ links to $p$, and 0 otherwise. Kleinberg and the course text call this matrix $A$; here $A$ already names a page. With the authority scores as a column vector $x$ and the hub scores as a column vector $y$, the two updates are
$$x \leftarrow M^{\mathsf{T}} y, \qquad y \leftarrow M x.$$
Entry $p$ of $M^{\mathsf{T}}y$ is $\sum_q M_{qp}\,y_q$, the sum of $y_q$ over the pages $q$ that link to $p$, and entry $p$ of $Mx$ is $\sum_q M_{pq}\,x_q$, the sum over the pages $p$ links to. Substituting one update into the other shows what a full round does to each vector alone:
$$x \leftarrow M^{\mathsf{T}} M\, x, \qquad y \leftarrow M M^{\mathsf{T}}\, y.$$
So, apart from rescaling, the authority vector is multiplied by the matrix $M^{\mathsf{T}}M$ once a round and the hub vector by $MM^{\mathsf{T}}$. This is power iteration, the method PageRank uses, applied to two new matrices. For the five-page web, with rows and columns in the order $A$ to $E$,
$$M = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}, \quad M^{\mathsf{T}}M = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 3 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{pmatrix}, \quad MM^{\mathsf{T}} = \begin{pmatrix} 2 & 1 & 0 & 1 & 0 \\ 1 & 2 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$$
The entries have a direct reading. Entry $(p, p')$ of $M^{\mathsf{T}}M$ is $\sum_q M_{qp} M_{qp'}$, the number of pages that link to both $p$ and $p'$. Its diagonal holds the in-degrees, $1, 1, 3, 0, 1$. The entry for $B$ and $C$ is 1 because one page, $A$, links to both. Entry $(q, q')$ of $MM^{\mathsf{T}}$ is the number of pages that both $q$ and $q'$ link to, and its diagonal holds the out-degrees, $2, 2, 1, 1, 0$. Both matrices are symmetric, which the link matrix of PageRank was not, and that makes the analysis below simpler than PageRank's.
The iteration, traced
The table runs the two updates from all ones, rescaling each vector to sum to 1 after every round. The last column is the distance $\sum_p \lvert x_p^{(k)} - x_p \rvert$ of the authority vector from its limit.
| Round $k$ | Authority $A, B, C, D, E$ | Hub $A, B, C, D, E$ | Error |
|---|---|---|---|
| 1 | 0.1667, 0.1667, 0.5000, 0, 0.1667 | 0.3333, 0.3333, 0.0833, 0.2500, 0 | 0.33 |
| 2 | 0.0500, 0.2000, 0.5500, 0, 0.2000 | 0.3571, 0.3571, 0.0238, 0.2619, 0 | 0.10 |
| 3 | 0.0139, 0.2083, 0.5694, 0, 0.2083 | 0.3636, 0.3636, 0.0065, 0.2662, 0 | 0.028 |
| 4 | 0.0038, 0.2105, 0.5752, 0, 0.2105 | 0.3654, 0.3654, 0.0017, 0.2675, 0 | 0.0075 |
| 5 | 0.0010, 0.2111, 0.5768, 0, 0.2111 | 0.3659, 0.3659, 0.0005, 0.2678, 0 | 0.0020 |
| 6 | 0.0003, 0.2113, 0.5772, 0, 0.2113 | 0.3660, 0.3660, 0.0001, 0.2679, 0 | 0.00054 |
| 20 | 0.0000, 0.2113, 0.5774, 0, 0.2113 | 0.3660, 0.3660, 0.0000, 0.2679, 0 | $5 \times 10^{-12}$ |
The scores settle quickly. $A$'s authority and $C$'s hub score, which looked respectable after one round, shrink toward zero by a factor of nearly four each round. The limits are
$$x = (0,\ 0.2113,\ 0.5774,\ 0,\ 0.2113), \qquad y = (0.3660,\ 0.3660,\ 0,\ 0.2679,\ 0),$$
and numpy's eigenvector routine, applied to $M^{\mathsf{T}}M$ and $MM^{\mathsf{T}}$ and rescaled to sum to 1, returns the same two vectors. The next section proves that this is no accident, and The example solved exactly finds the limits in closed form.
Why the iteration converges
Here is the idea. A symmetric matrix stretches space by a different factor along each of its eigenvector directions. Applying it again and again makes the direction with the largest factor dominate, so the rescaled vector turns toward that direction. Three facts need checking: that the directions exist, that the start has some part along the dominant one, and that nothing else keeps pace.
The formal version. Let $B = M^{\mathsf{T}}M$, an $n \times n$ matrix. The argument for $MM^{\mathsf{T}}$ is the same with $M^{\mathsf{T}}$ in place of $M$ throughout, since $MM^{\mathsf{T}} = (M^{\mathsf{T}})^{\mathsf{T}}(M^{\mathsf{T}})$ has the same form.
Step 1: an orthonormal basis of eigenvectors, with eigenvalues that are not negative. $B$ is symmetric, since $(M^{\mathsf{T}}M)^{\mathsf{T}} = M^{\mathsf{T}}M$. By the spectral theorem for real symmetric matrices, there are orthonormal vectors $u_1, \dots, u_n$ with $B u_i = \lambda_i u_i$ and real eigenvalues, which we order as $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$. None is negative: $\lambda_i = u_i^{\mathsf{T}} B u_i = (M u_i)^{\mathsf{T}}(M u_i) = \lVert M u_i \rVert^2 \ge 0$. If the graph has at least one link then $B$ is not the zero matrix and $\lambda_1 > 0$.
Step 2: the expansion. Let $m$ be the number of eigenvalues equal to the largest, so $\lambda_1 = \dots = \lambda_m > \lambda_{m+1}$. Write the starting vector in the basis, $z = \sum_i c_i u_i$ with $c_i = u_i^{\mathsf{T}} z$, and let
$$p = \sum_{i=1}^{m} c_i u_i$$
be the part of $z$ in the eigenspace of the largest eigenvalue. Each multiplication by $B$ multiplies the term along $u_i$ by $\lambda_i$, so
$$\frac{B^k z}{\lambda_1^k} = p + \sum_{i > m} c_i \left(\frac{\lambda_i}{\lambda_1}\right)^k u_i.$$
Step 3: the remainder vanishes. Every ratio in the sum satisfies $0 \le \lambda_i/\lambda_1 \le \lambda_{m+1}/\lambda_1 < 1$. Because the $u_i$ are orthonormal, the length of the sum is
$$\Big\lVert \sum_{i > m} c_i \left(\frac{\lambda_i}{\lambda_1}\right)^k u_i \Big\rVert = \sqrt{\sum_{i>m} c_i^2 \left(\frac{\lambda_i}{\lambda_1}\right)^{2k}} \le \left(\frac{\lambda_{m+1}}{\lambda_1}\right)^k \lVert z \rVert,$$
which tends to zero. So $B^k z / \lambda_1^k \to p$. If $p \ne 0$, rescaling removes the factor $\lambda_1^k$: the unit vector in the direction of $B^k z$ converges to $p / \lVert p \rVert$, and the vector rescaled to sum to 1 converges to $p$ divided by the sum of its entries, provided that sum is not zero. For the hub vector started at $\mathbf{1}$ it is positive: $p$ is the orthogonal projection of $\mathbf{1}$ onto the top eigenspace, so $\mathbf{1}^{\mathsf{T}}p = p^{\mathsf{T}}p = \lVert p \rVert^2 > 0$. For the authority vector, $(M^{\mathsf{T}}M)^k M^{\mathsf{T}}\mathbf{1} = M^{\mathsf{T}}(MM^{\mathsf{T}})^k\mathbf{1}$, so its limit direction is $M^{\mathsf{T}}$ applied to the hub limit, which has no negative entries when the largest eigenvalue is not repeated and so has a positive sum. Scaling by length, as Kleinberg does, needs no such condition. The limit satisfies $Bp = \lambda_1 p$, so it is an eigenvector for the largest eigenvalue. The error shrinks by the factor $\lambda_{m+1}/\lambda_1$ each round.
Step 4: the start has a part along the top eigenspace. It remains to show $p \ne 0$ for the starting vectors HITS uses. First, the top eigenspace contains a vector with no negative entries. Take a unit eigenvector $u$ for $\lambda_1$ and let $\lvert u \rvert$ be the vector of the absolute values of its entries, also of unit length. Since the entries of $B$ are not negative,
$$\lvert u \rvert^{\mathsf{T}} B\, \lvert u \rvert = \sum_{i,j} B_{ij}\, \lvert u_i \rvert\, \lvert u_j \rvert \ \ge\ \sum_{i,j} B_{ij}\, u_i u_j = u^{\mathsf{T}} B u = \lambda_1.$$
On the other hand, for any unit vector $w = \sum_i a_i u_i$, $w^{\mathsf{T}} B w = \sum_i \lambda_i a_i^2 \le \lambda_1 \sum_i a_i^2 = \lambda_1$, with equality only if $a_i = 0$ whenever $\lambda_i < \lambda_1$, that is, only if $w$ lies in the top eigenspace. So $\lvert u \rvert^{\mathsf{T}} B \lvert u \rvert = \lambda_1$ exactly and $\lvert u \rvert$ is itself an eigenvector for $\lambda_1$.
Now take the start. If $z = \mathbf{1}$, the vector of all ones, then $z^{\mathsf{T}} \lvert u \rvert = \sum_i \lvert u_i \rvert > 0$, so $z$ is not orthogonal to the top eigenspace and $p \ne 0$. This covers the hub vector, which starts at $\mathbf{1}$ and is multiplied by $MM^{\mathsf{T}}$. The authority vector after the first half round is $M^{\mathsf{T}}\mathbf{1}$, the vector of in-degrees, and from there it is multiplied by $B = M^{\mathsf{T}}M$. Its inner product with $\lvert u \rvert$ is $\mathbf{1}^{\mathsf{T}} M \lvert u \rvert$, the sum of the entries of $M\lvert u \rvert$. Those entries are not negative, and they are not all zero, because $M^{\mathsf{T}}(M \lvert u \rvert) = \lambda_1 \lvert u \rvert \ne 0$. So the sum is positive and again $p \ne 0$. $\blacksquare$
This proves the two theorems of Kleinberg (1999, §3), who cites the power-iteration step as a standard result and assumes $\lvert \lambda_1 \rvert > \lvert \lambda_2 \rvert$. He remarks that without the assumption the analysis "is not affected in any substantial way". The iteration does still converge, but, as the next section shows, its limit then depends on the starting vector. The two theorems are:
- Convergence. Started from all ones, the rescaled authority and hub vectors converge.
- The limits. If the largest eigenvalue is not repeated ($m = 1$), the limits are the principal eigenvectors of $M^{\mathsf{T}}M$ and $MM^{\mathsf{T}}$: the unique eigenvectors for $\lambda_1$ with nonnegative entries and the chosen scale. They depend only on the graph.
The proof also gives the two conditions in the form a user needs. The starting vector must not be orthogonal to the top eigenspace, which holds for any start with all entries positive, by the same inner product. And the speed is set by the eigenvalue gap, the ratio $\lambda_{m+1}/\lambda_1$ of the next distinct eigenvalue to the largest: the smaller the ratio, the faster the convergence.
Now the check on the example. The eigenvalues of both matrices are $3.7321,\ 1,\ 1,\ 0.2679,\ 0$. The largest is not repeated, and the ratio is $1/3.7321 = 0.268$. In the table, the ratios of successive errors are $0.300$, $0.278$, $0.271$, $0.269$ and then $0.268$. Thirty random starting vectors with positive entries, drawn with a fixed seed, all reach the same limits. A start that is orthogonal to the principal hub vector does not: beginning with hub weight on $C$ alone, the iteration stays at authority $(1, 0, 0, 0, 0)$ and hub $(0, 0, 1, 0, 0)$ forever, an eigenvector for the eigenvalue 1.
In practice the iteration is stopped early. Kleinberg found that 20 rounds were enough for the top few scores to become stable, and the course text reports that about five rounds give fairly good results, since only the order of the top pages matters.
When the largest eigenvalue is repeated
Step 3 shows what happens when $m > 1$. The iteration still converges, but to $p$, the part of the starting vector in the top eigenspace, and that depends on the start. There is then no single principal eigenvector, and the scores are not a property of the graph alone.
Example (two separate links). A web with just the links $X \to Y$ and $Z \to W$ has no principal eigenvector, and HITS returns whatever proportions it was started with. Here $M^{\mathsf{T}}M$ has a 1 in the diagonal places of $Y$ and $W$ and zeros elsewhere, so its eigenvalues are $1, 1, 0, 0$ and every vector supported on $Y$ and $W$ is an eigenvector for the largest. Starting from all ones gives authorities $(Y, W) = (0.5, 0.5)$. Starting with hub scores $(X, Y, Z, W) = (3, 1, 1, 1)$ gives $(0.75, 0.25)$. Starting with $(1, 0, 9, 0)$ gives $(0.1, 0.9)$. Each is reached in one round and never changes.
The example is extreme, but its cause is ordinary. When the graph falls into pieces with no links between them, $M^{\mathsf{T}}M$ splits into separate blocks, one for each piece, and its eigenvalues are those of the blocks. If two blocks tie for the largest eigenvalue, the scores divide between them according to the start. If one block wins, the proof shows that every page outside it converges to zero, however many links it has. That is the fate of $A$ on the five-page web, and the tightly knit community effect below is the same fact seen at a larger scale. PageRank avoids both problems by teleporting, which makes every entry of its matrix positive and its principal eigenvector unique (PageRank proves this). HITS has no such step.
Kleinberg (1999, §6) puts the other eigenvectors to use. The non-principal eigenvectors of $M^{\mathsf{T}}M$ and $MM^{\mathsf{T}}$ pick out further densely linked groups of hubs and authorities, which for a query such as jaguar can correspond to its different meanings.
The singular value decomposition
The two eigenvector problems are one problem. Every real matrix has a singular value decomposition
$$M = U \Sigma V^{\mathsf{T}},$$
where the columns $u_1, u_2, \dots$ of $U$ are orthonormal, the columns $v_1, v_2, \dots$ of $V$ are orthonormal, and $\Sigma$ is diagonal with entries $\sigma_1 \ge \sigma_2 \ge \dots \ge 0$, the singular values. Multiplying out, and using $U^{\mathsf{T}}U = I$ and $V^{\mathsf{T}}V = I$,
$$M^{\mathsf{T}}M = V \Sigma U^{\mathsf{T}} U \Sigma V^{\mathsf{T}} = V \Sigma^2 V^{\mathsf{T}}, \qquad MM^{\mathsf{T}} = U \Sigma V^{\mathsf{T}} V \Sigma U^{\mathsf{T}} = U \Sigma^2 U^{\mathsf{T}}.$$
So the eigenvectors of $M^{\mathsf{T}}M$ are the right singular vectors $v_i$, the eigenvectors of $MM^{\mathsf{T}}$ are the left singular vectors $u_i$, and both matrices have the eigenvalues $\sigma_i^2$. In these terms:
- the authority vector is the first right singular vector $v_1$ of the adjacency matrix;
- the hub vector is the first left singular vector $u_1$;
- the two are tied by $M v_1 = \sigma_1 u_1$ and $M^{\mathsf{T}} u_1 = \sigma_1 v_1$, which are the two HITS updates at their fixed point, with $\sigma_1$ as the rescaling factor.
For the five-page web, numpy's decomposition gives singular values $1.9319,\ 1,\ 1,\ 0.5176,\ 0$, whose squares are the eigenvalues above, and its first singular vectors are the hub and authority vectors of the table. The largest is $\sigma_1 = \sqrt{2 + \sqrt{3}}$.
A classical fact about the decomposition says what HITS is fitting: $\sigma_1 u_1 v_1^{\mathsf{T}}$ is the best approximation of $M$ by a matrix of rank one, in the sense of least squared error (the Eckart–Young theorem, which Manning, Raghavan, and Schütze, 2008, §18.3, state for low-rank approximation). HITS summarizes the link matrix by a single pattern, "page $q$ links to page $p$ in proportion to $q$'s hub score times $p$'s authority score", and reports that pattern. Latent semantic indexing applies the same decomposition to the matrix of terms and documents and keeps more than one pattern.
The example solved exactly
The limits in the table can be found by hand, which shows where the zeros come from. In $M^{\mathsf{T}}M$ above, the row and column of $D$ are zero, because $D$ has no in-links. The row and column of $A$ hold only the diagonal 1: $A$'s one in-link comes from $C$, and $C$ links to nothing else, so no page links to $A$ and to another page. The matrix therefore splits into three blocks, $\{A\}$ with eigenvalue 1, $\{D\}$ with eigenvalue 0, and $\{B, C, E\}$:
$$\begin{pmatrix} 1 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 & 1 \end{pmatrix}.$$
$B$ and $E$ enter this block in the same way, so look for an eigenvector of the form $(1, c, 1)$. The first row gives $1 + c = \lambda$, and the second gives $2 + 3c = \lambda c$. Substituting $\lambda = 1 + c$ into the second, $2 + 3c = c + c^2$, so $c^2 - 2c - 2 = 0$ and $c = 1 \pm \sqrt{3}$. The positive root gives the eigenvalue $\lambda_1 = 2 + \sqrt{3} \approx 3.732$ with eigenvector $(1,\ 1 + \sqrt{3},\ 1)$. The other root gives $2 - \sqrt{3} \approx 0.268$, and the vector $(1, 0, -1)$ gives the block's third eigenvalue, 1.
The largest eigenvalue of the whole matrix is therefore $2 + \sqrt{3}$, from the block $\{B, C, E\}$, and the principal eigenvector is zero outside that block. Dividing $(1,\ 1 + \sqrt{3},\ 1)$ by its sum $3 + \sqrt{3}$ gives the authority scores
$$x_B = x_E = \frac{1}{3 + \sqrt{3}} = \frac{3 - \sqrt{3}}{6} \approx 0.2113, \qquad x_C = \frac{1 + \sqrt{3}}{3 + \sqrt{3}} = \frac{1}{\sqrt{3}} \approx 0.5774, \qquad x_A = x_D = 0.$$
The hub scores follow from one more update, $y \propto Mx$. With $x \propto (0,\ 1,\ 1 + \sqrt{3},\ 0,\ 1)$: $y_A = x_B + x_C = 2 + \sqrt{3}$, $y_B = x_C + x_E = 2 + \sqrt{3}$, $y_C = x_A = 0$, $y_D = x_C = 1 + \sqrt{3}$ and $y_E = 0$. Dividing by the sum $5 + 3\sqrt{3}$,
$$y_A = y_B = \frac{2 + \sqrt{3}}{5 + 3\sqrt{3}} = \frac{\sqrt{3} - 1}{2} \approx 0.3660, \qquad y_D = \frac{1 + \sqrt{3}}{5 + 3\sqrt{3}} = 2 - \sqrt{3} \approx 0.2679, \qquad y_C = y_E = 0.$$
These are the limits the iteration reached. $C$ is the authority, with the hubs $A$, $B$ and $D$ pointing to it. $A$ ends with no authority although it started with one in-link, like $B$ and $E$: its in-link comes from a page that is a hub for nothing else, so the reinforcement between hubs and authorities never reaches it.
HITS and PageRank
The two methods read the same links and can disagree completely, as they do about $A$:
| Page | PageRank ($d = 0.85$) | HITS authority | HITS hub |
|---|---|---|---|
| A | 0.3171 | 0 | 0.3660 |
| B | 0.1872 | 0.2113 | 0.3660 |
| C | 0.3113 | 0.5774 | 0 |
| D | 0.0524 | 0 | 0.2679 |
| E | 0.1320 | 0.2113 | 0 |
The differences in design explain the differences in behavior.
One score against two. PageRank passes importance forward along links: a page is important if important pages link to it. HITS passes weight forward and backward in turn. A page with no in-links has no PageRank beyond its share of teleportation, but it can be a strong hub, as $D$ is.
Query-independent against query-dependent. PageRank is computed once for the whole collection, before any query, and the course text calls it a query-independent measure of static quality (Manning, Raghavan, and Schütze, 2008, §21.2.2). HITS is computed for each query on that query's base set. Its scores are specific to the topic, and the price is an eigenvector computation at query time, on a graph that must first be fetched from a connectivity server.
Topic drift. Once the base set is built, HITS ignores the query, so nothing holds the result to the topic. Kleinberg (1999, §7) observed that for a query that is too narrow, the base set does not contain a dense enough group of relevant pages, and the pages of a broader, better-linked topic win instead. He called this diffusion. His example is the query WWW conferences, for which the top authorities were general resources about the web. Bharat and Henzinger (1998) named the same failure topic drift and reduced it by weighting pages by the similarity of their text to the query. The course text notes a related effect: the top hubs and authorities for an English query often include pages in other languages, drawn into the base set by links alone (§21.3.1).
The tightly knit community effect. The principal eigenvector favors the most densely linked group of hubs and authorities, which need not be the largest or the most relevant. Lempel and Moran (2000) define a tightly knit community as a small but highly interconnected set of pages, and the TKC effect as such a community scoring high although its pages are not authoritative on the topic, or cover only one aspect of it.
Example (a small dense community beats a larger one). In a graph built to show the effect, HITS gives all of the authority to the three pages of the small community and none to the most linked page of the graph. Community 1 has three hubs that each link to all three of its authorities $a_1, a_2, a_3$: 9 links, in-degree 3 each. Community 2 has six hubs that all link to authority $b_1$, and in pairs to $b_2$, $b_3$ and $b_4$: 12 links, with in-degree 6 for $b_1$ and 2 for the others. No link joins the communities, so $M^{\mathsf{T}}M$ has one block for each. The block of community 1 is the $3 \times 3$ matrix of all 3s, with largest eigenvalue 9. The block of community 2 has 6 on the diagonal for $b_1$, 2 on the rest of the diagonal and 2 between $b_1$ and each other page. Trying an eigenvector $(s, t, t, t)$ gives $6s + 6t = \lambda s$ and $2s + 2t = \lambda t$, so $\lambda = 8$ with $(3, 1, 1, 1)$. Since $9 > 8$, the limit is
| Page | In-degree | HITS authority | SALSA authority |
|---|---|---|---|
| $a_1, a_2, a_3$ | 3 each | 0.3333 each | 0.1429 each |
| $b_1$ | 6 | 0 | 0.2857 |
| $b_2, b_3, b_4$ | 2 each | 0 | 0.0952 each |
The community with more pages, more links and the single most cited page ends with nothing, because the smaller one is completely interlinked. The eigenvalue ratio here is $8/9$, so the effect takes time to appear. After 5 rounds $b_1$ still leads, with $0.227$ against $0.182$ for each $a_i$. Each round multiplies community 2's share, relative to community 1's, by $8/9$. After 20 rounds community 2 holds $0.125$ of the authority, and after 50 rounds $0.004$. An implementation that stops after a few rounds reports an order that the method itself would reverse.
Stability and manipulation. The course text (§21.4) reports the finding of Ng and colleagues that PageRank's scores are less sensitive than HITS's to small changes in the graph, and adds that teleporting contributes much of that robustness. It also notes that both methods can be manipulated by adding links, as link farms do.
SALSA. Lempel and Moran (2000) proposed SALSA, the stochastic approach for link-structure analysis, to keep the two roles of HITS while weakening the coupling that causes the TKC effect. It replaces the mutual reinforcement with two random walks on the same base set. The authority walk steps from an authority back along one of its in-links, chosen at random, to a hub, and then forward along one of that hub's out-links, chosen at random, to an authority. The hub walk does the reverse. Authorities are ranked by the long-run distribution of the first walk and hubs by that of the second. In matrix terms, HITS iterates $M^{\mathsf{T}}M$. SALSA's authority walk has the transition matrix $M_c^{\mathsf{T}} M_r$, where $M_r$ is $M$ with each row divided by its out-degree and $M_c$ is $M$ with each column divided by its in-degree. Every row of this product sums to 1, so it is the transition matrix of a Markov chain. Lempel and Moran prove that within a connected piece of the graph the long-run probability of an authority is proportional to its in-degree. The reason is that the chain is reversible: the probability flow from authority $i$ to authority $j$, $d_i \cdot \frac{1}{d_i}\sum_h \frac{1}{\text{out}(h)}$ summed over the hubs $h$ that link to both, is the same in both directions. Started from the uniform distribution, each piece keeps the share of probability it began with. SALSA is thus a weighted count of in-links, cheaper to compute than HITS and, as Lempel and Moran show, less vulnerable to the TKC effect. In the table above it ranks $b_1$ first, with $\frac{4}{7} \times \frac{6}{12} = 0.2857$. On the five-page web it gives the authorities $A$, $B$, $C$ and $E$ the scores $0.25$, $0.15$, $0.45$ and $0.15$, so $A$ keeps a quarter where HITS gave it zero.
Every number in this article is computed by tools/experiments/crawling/hits_math.py in the site repository, which checks the iteration against numpy's eigenvectors and singular vectors.
Worked problems
Problems 1 to 4 are Exercises 21.19 to 21.22 of the course text (Manning, Raghavan, and Schütze, 2008), restated in our words. Problem 5 is posed here. The numbers are checked in hits_math.py.
Problem 1 (Exercise 21.19). If all hub and authority scores start at 1, what are a page's scores after one iteration?
Its authority score is its in-degree, and its hub score depends on the order of the two updates. The authority update gives $x_p = \sum_{q \to p} 1$, the number of pages linking to $p$. If the hub update is applied at the same time, using the old authority scores of 1, then $y_p = \sum_{p \to q} 1$ is the out-degree of $p$. If it is applied after the authority update, as in Kleinberg's procedure and in this article, then $y_p = \sum_{p \to q} x_q$ is the sum of the in-degrees of the pages $p$ links to. On the five-page web the in-degrees are $(1, 1, 3, 0, 1)$ and the out-degrees $(2, 2, 1, 1, 0)$, while the sequential hub scores are $(4, 4, 1, 3, 0)$, as in the example above.
The course text itself runs the updates in the other order (its Equation 21.8: hub scores first, then authority scores from the new hub scores). Then $y_p$ is the out-degree of $p$, and $x_p = \sum_{q \to p} y_q$ is the sum of the out-degrees of the pages that link to $p$. On the five-page web that gives hub scores $(2, 2, 1, 1, 0)$ and authority scores $(1, 2, 5, 0, 2)$: $A$ is linked from $C$, with out-degree 1; $B$ from $A$, with 2; $C$ from $A$, $B$ and $D$, with $2 + 2 + 1 = 5$; and $E$ from $B$, with 2.
Counting links is thus the first approximation that HITS refines, in every order. When the largest eigenvalue is not repeated, all three orders converge to the same limits: each sequential order multiplies the hub vector by $MM^{\mathsf{T}}$ once a round, and the simultaneous order does so once every two rounds.
Problem 2 (Exercise 21.20). How should the entries of $MM^{\mathsf{T}}$ and $M^{\mathsf{T}}M$ be interpreted?
Entry $(q, q')$ of $MM^{\mathsf{T}}$ is $\sum_p M_{qp}M_{q'p}$. Each term is 1 exactly when both $q$ and $q'$ link to $p$, so the entry counts the pages that $q$ and $q'$ both link to. Two pages with a large entry cite many of the same pages. The diagonal entry $(q, q)$ is the out-degree of $q$. Entry $(p, p')$ of $M^{\mathsf{T}}M$ is $\sum_q M_{qp}M_{qp'}$, the number of pages that link to both $p$ and $p'$: how often the two are cited together. Its diagonal entry is the in-degree of $p$.
The exercise also asks for the connection to the matrix $CC^{\mathsf{T}}$ of the course text's chapter 18, where $C$ is the term-document matrix. The construction is the same with terms in the role of linking pages and documents in the role of linked pages: entry $(t, t')$ of $CC^{\mathsf{T}}$ counts, for a 0/1 matrix, the documents in which terms $t$ and $t'$ both occur. $M^{\mathsf{T}}M$ measures the co-occurrence of two pages in the link lists of other pages, as $CC^{\mathsf{T}}$ measures the co-occurrence of two terms in documents.
Problem 3 (Exercise 21.21). What are the principal eigenvalues of $MM^{\mathsf{T}}$ and $M^{\mathsf{T}}M$?
They are equal, and each is $\sigma_1^2$, the square of the largest singular value of $M$. The singular value decomposition above shows it. A direct proof shows more, that the two matrices share all their nonzero eigenvalues. Suppose $M^{\mathsf{T}}M x = \lambda x$ with $\lambda \ne 0$ and $x \ne 0$. Multiply on the left by $M$: $MM^{\mathsf{T}}(Mx) = \lambda (Mx)$. The vector $Mx$ is not zero, since $M^{\mathsf{T}}(Mx) = \lambda x \ne 0$. So $Mx$ is an eigenvector of $MM^{\mathsf{T}}$ with the same eigenvalue $\lambda$. The same argument with $M$ and $M^{\mathsf{T}}$ exchanged, starting from $MM^{\mathsf{T}}y = \lambda y$, shows that $M^{\mathsf{T}}y$ is an eigenvector of $M^{\mathsf{T}}M$ for $\lambda$. Every nonzero eigenvalue of one matrix is therefore an eigenvalue of the other, and in particular the largest is shared. It also shows how the two principal eigenvectors are related: the hub vector is $M$ times the authority vector, rescaled.
On the five-page web the shared principal eigenvalue is $2 + \sqrt{3} \approx 3.732$. The script confirms the statement on 200 random link matrices.
Problem 4 (Exercise 21.22). Three pages have the links $d_1 \to d_2$, $d_1 \to d_3$, $d_2 \to d_3$ and $d_3 \to d_2$ (the course text's Figure 21.7). Compute PageRank with teleport probability $\alpha = 0.1$, teleporting uniformly, and the hub and authority scores normalized so that the largest of each is 1. Give the order of the three pages under each score, with ties.
PageRank. In this article's notation $\alpha = 0.1$ is $d = 0.9$, and no page is dangling. Nothing links to $d_1$, so it receives only teleportation: $\pi_1 = \alpha/3 = 1/30 \approx 0.033$. Pages $d_2$ and $d_3$ are symmetric: exchanging them maps the graph to itself, and the steady state is unique, so $\pi_2 = \pi_3$. The three values sum to 1, so $\pi_2 = \pi_3 = (1 - 1/30)/2 = 29/60 \approx 0.483$. As a check, $d_2$ receives half of $d_1$'s rank and all of $d_3$'s: $\alpha/3 + 0.9\,(\pi_1/2 + \pi_3) = 1/30 + 0.9\,(1/60 + 29/60) = 1/30 + 9/20 = 29/60$. The order is $d_2 = d_3 > d_1$.
Authorities. With rows and columns in the order $d_1, d_2, d_3$,
$$M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}, \qquad M^{\mathsf{T}}M = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 2 & 1 \\ 0 & 1 & 2 \end{pmatrix}, \qquad MM^{\mathsf{T}} = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}.$$
On $\{d_2, d_3\}$ the block of $M^{\mathsf{T}}M$ has eigenvectors $(1, 1)$ with eigenvalue $2 + 1 = 3$ and $(1, -1)$ with eigenvalue $2 - 1 = 1$, and $d_1$ contributes the eigenvalue 0. The largest eigenvalue, 3, is not repeated, and its eigenvector is $(0, 1, 1)$. That vector already has largest entry 1, so the authority scores are $(0, 1, 1)$. The order is $d_2 = d_3 > d_1$.
Hubs. The hub vector is $M$ times the authority vector: $y \propto Mx = (1 + 1,\ 1,\ 1) = (2, 1, 1)$. It is an eigenvector of $MM^{\mathsf{T}}$ for the eigenvalue 3, as the first row confirms: $2 \cdot 2 + 1 + 1 = 6 = 3 \cdot 2$. Divided by its largest entry, the hub scores are $(1, 0.5, 0.5)$. The order is $d_1 > d_2 = d_3$.
In this article's own scaling, to a sum of 1, the same vectors are $(0, 0.5, 0.5)$ and $(0.5, 0.25, 0.25)$. The scaling changes the numbers and not the order. $d_1$ is the best hub and the worst authority, and has the lowest PageRank: it links to both authorities and nothing links to it.
Problem 5 (a three-link graph by hand). A graph has pages $P, Q, R, S$ and links $P \to R$, $Q \to R$ and $Q \to S$. Find the hub and authority scores, scaled to sum to 1, and the rate at which the iteration approaches them.
Only $R$ and $S$ have in-links, so only they can have authority. $R$ is linked from $P$ and $Q$, $S$ from $Q$, and one page, $Q$, links to both. On $\{R, S\}$,
$$M^{\mathsf{T}}M = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}, \qquad \det\begin{pmatrix} 2 - \lambda & 1 \\ 1 & 1 - \lambda \end{pmatrix} = \lambda^2 - 3\lambda + 1 = 0, \qquad \lambda = \frac{3 \pm \sqrt{5}}{2}.$$
The largest eigenvalue is $\lambda_1 = (3 + \sqrt{5})/2 \approx 2.618$. Its eigenvector $(x_R, x_S)$ satisfies the second row, $x_R + x_S = \lambda_1 x_S$, so $x_R = (\lambda_1 - 1)\,x_S = 1.618\,x_S$. Scaled to sum to 1,
$$x_R = \frac{1.618}{2.618} = 0.618, \qquad x_S = \frac{1}{2.618} = 0.382, \qquad x_P = x_Q = 0.$$
The hubs follow from $y \propto Mx$: $y_P = x_R = 0.618$ and $y_Q = x_R + x_S = 1$, before scaling. Dividing by $1.618$ gives $y_P = 0.382$ and $y_Q = 0.618$, with $y_R = y_S = 0$. The number $1.618$ is the golden ratio $\varphi = (1 + \sqrt{5})/2$, and $\lambda_1 = \varphi^2$.
$R$ is the better authority, as its two in-links suggest, and $Q$ is the better hub, since it points to both authorities. The other eigenvalue is $(3 - \sqrt{5})/2 \approx 0.382$, so the error shrinks by the factor $0.382/2.618 = 0.146$ each round. The iteration from all ones gives $x_R = 0.6667$, $0.6250$, $0.6190$ and $0.6182$ in its first four rounds.
What we have learned
HITS scores each page of a query's base set twice, as an authority and as a hub, by repeating two updates that are multiplication by $M^{\mathsf{T}}$ and by $M$. The rescaled iteration is power iteration on the symmetric matrices $M^{\mathsf{T}}M$ and $MM^{\mathsf{T}}$. From a positive start it always converges, to the part of the start in the eigenspace of the largest eigenvalue, at the rate set by the eigenvalue gap. When the largest eigenvalue is not repeated the limits are the first right and left singular vectors of $M$. On the five-page web they make $C$ the authority, with a score of $0.5774$, and give $A$ none. Because HITS has no teleporting, it can give zero to whole parts of a graph, drift from a narrow topic to a broad one, and favor a small tightly knit community over a larger one.
PageRank and HITS, like the crawl behind them, are built for collections of billions of pages. Monitoring websites closes the topic with the job most programs that fetch pages actually do, watching a handful of pages for changes, and shows how much of the topic carries over to it.
References
- Bharat, K., and Henzinger, M. R. (1998). Improved algorithms for topic distillation in a hyperlinked environment. In Proceedings of SIGIR 1998, 104–111. record
- Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5), 604–632. record · 3 pages
- Lempel, R., and Moran, S. (2000). The stochastic approach for link-structure analysis (SALSA) and the TKC effect. Computer Networks, 33(1–6), 387–401. record · 2 pages
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, sections 18.3, 21.2 and 21.3. Cambridge University Press. record · 93 pages