HITS Algorithm, in depth: hubs and authorities, the singular vector view, a sparse implementation and why ties break it

Two scores defined by each other

Let the directed graph have adjacency matrix M with M[u][v] = 1 when page u links to page v. Kleinberg's mutual reinforcement is two sentences. A good authority is pointed to by many good hubs. A good hub points to many good authorities. As updates:

a(v) = sum over u with u -> v  of h(u)      # authority: in-links weighted by hub score
h(u) = sum over v with u -> v  of a(v)      # hub: out-links weighted by authority score

in matrix form:   a = M^T h        h = M a

Apply both repeatedly and the numbers grow without bound, so normalise after each step (Kleinberg used the sum of squares; any norm works for ranking). Substitute one equation into the other and the structure is plain: a = M^T M a and h = M M^T h, up to scaling. The authority vector is the principal eigenvector of M^T M, a matrix whose (i, j) entry counts the pages that link to both i and j, which is co-citation. The hub vector is the principal eigenvector of M M^T, which counts shared out-links, bibliographic coupling. Both are Gram matrices, so they are symmetric positive semidefinite with real, non-negative eigenvalues, and because their entries are non-negative, Perron-Frobenius lets the principal eigenvector be chosen non-negative.

There is a cleaner way to say the same thing. If M = U S V^T is the singular value decomposition, then M^T M = V S^2 V^T and M M^T = U S^2 U^T. HITS authority scores are the first right singular vector of M and hub scores are the first left singular vector. Running HITS is running power iteration for the top singular triple, which is why anything you know about the SVD, including how badly it behaves when the top two singular values are close, transfers directly.

The base set: HITS is query dependent

HITS was designed to be query dependent, and that is the biggest practical difference from PageRank. You do not run it on the whole web. For each query you build a focused subgraph in three steps:

1. Root set. Take the top t results of an ordinary text retrieval for the query. Kleinberg used t = 200.
2. Base set. Add every page a root page links to, and up to d pages that link to each root page (d = 50 in the paper). The cap matters: a popular root page can have millions of in-links, and you want a sample, not all of them.
3. Prune. Drop links between pages on the same host. Those are mostly navigation, and keeping them lets a single site vote for itself.

The base set is typically a few thousand pages, so the iteration is cheap. Building it is not: you need fast out-link and in-link lookups at query time. That cost is a big reason PageRank, computed once offline, won the search-engine argument, and why modern uses of HITS precompute per topic cluster or run over a bounded neighbourhood.

Worked example: six pages by hand

Six pages. P links to A and B. Q links to A, B and C. R links to A. A links to B. Nothing else. Start with every hub score at 1 and normalise each vector to unit length after it is computed. Only the normalised vectors are shown, because normalising a before or after computing h changes the raw magnitudes but never the direction.

Read the result the way HITS intends. A and B tie as top authorities: each has three in-links, and the pages pointing at them are strong hubs. C has one in-link, but from the best hub, so it is not zero. Q is the best hub because it points at all three authorities. P is second. R and A tie as weak hubs because each points at exactly one top authority. Note that A is both an authority and a hub; the two scores are independent properties of the same page. B and C have hub score 0 because they link nowhere.

Convergence took three to four steps to reach three decimals. The reason is the eigengap. The eigenvalues of M^T M here are 5.449, 1 and 0.551 (the top one is exactly 3 + sqrt(6)), and power iteration error shrinks by the ratio of the second eigenvalue to the first each step: 1 / 5.449, about 0.18. Small focused graphs with one dense community usually have a large gap like this. When the gap closes, so does your confidence in the ranking, which is the subject of the failure modes below.

A sparse implementation with tests

A production implementation stores M in compressed sparse row form and never forms M^T M, which can be much denser than M. Each iteration is two sparse matrix-vector products. The stopping rule should look at the change in both vectors, and the function should report how many iterations it took, because a slow run is diagnostic information.

import numpy as np
import scipy.sparse as sp

def hits(edges, n, tol=1e-10, max_iter=1000, h0=None):
    # edges: iterable of (u, v) meaning u links to v; nodes are 0..n-1
    rows, cols = zip(*edges) if edges else ((), ())
    M = sp.csr_matrix((np.ones(len(rows)), (rows, cols)), shape=(n, n))
    M.sum_duplicates()
    M.data[:] = 1.0                      # a page that links twice still votes once
    MT = M.T.tocsr()
    h = np.ones(n) if h0 is None else np.asarray(h0, dtype=float)
    h /= np.linalg.norm(h)
    a = np.zeros(n)
    for it in range(1, max_iter + 1):
        a_new = MT @ h
        na = np.linalg.norm(a_new)
        if na == 0:                      # no links at all
            return a_new, h, it
        a_new /= na
        h_new = M @ a_new
        h_new /= np.linalg.norm(h_new)
        delta = np.abs(a_new - a).sum() + np.abs(h_new - h).sum()
        a, h = a_new, h_new
        if delta < tol:
            return a, h, it
    raise RuntimeError(f"HITS did not converge in {max_iter} iterations")

def test_worked_example():
    P, Q, R, A, B, C = range(6)
    E = [(P, A), (P, B), (Q, A), (Q, B), (Q, C), (R, A), (A, B)]
    a, h, it = hits(E, 6)
    assert abs(a[A] - 0.674) < 1e-3 and abs(a[C] - 0.303) < 1e-3
    assert abs(h[Q] - 0.707) < 1e-3 and h[B] == 0
    # cross-check against the SVD: first right singular vector, sign-fixed
    M = np.zeros((6, 6))
    for u, v in E:
        M[u, v] = 1
    _, _, Vt = np.linalg.svd(M)
    assert np.allclose(np.abs(Vt[0]), a, atol=1e-6)

The SVD cross-check is the most useful test: on small graphs the authority vector must match the first right singular vector in absolute value. If it does not, either the iteration has not converged or the top singular value is repeated.

Failure modes

Ties make the answer depend on where you start. Take two disconnected pieces. In the first, P links to A and B. In the second, Q and R both link to C. The top eigenvalue of M^T M is 2 in each piece, so it is repeated, and the principal eigenvector is no longer unique. Start from all-ones hubs and HITS returns authorities (0.408, 0.408, 0.816) for (A, B, C). Start from hubs (1, 0.1, 0.1) for (P, Q, R) and it returns (0.700, 0.700, 0.140). Same graph, opposite verdict on C. Real base sets are rarely disconnected, but they are often nearly so, and then a near-tie gives the same instability in slow motion. Ng, Zheng and Jordan studied exactly this sensitivity and showed that small changes to the link set can reorder HITS results when the eigengap is small.

• Tightly knit community effect. Power iteration concentrates mass on the densest bipartite core in the base set. If that core is a cluster of pages about a related but different topic, it captures the ranking. This is topic drift, and it was the most reported complaint about HITS on the early web.
• Collusion. A group of sites that all link to each other forms a dense core by construction. Same-host pruning stops one site; it does not stop a ring of domains.
• Zero vectors. If the base set has no edges after pruning, both vectors are zero. Return that explicitly instead of dividing by zero.
• Query-time cost. 200 root pages with an in-link cap of 50 is up to ten thousand index reads per query.

Fixes: weighting, SALSA and teleport

Three adjustments cover most of the failures. First, weight the edges: Bharat and Henzinger's 1998 refinement down-weights multiple links from one host to another and weights pages by text relevance to the query, which reduces both drift and nepotism. Second, use SALSA (Lempel and Moran, 2000). SALSA replaces the mutual reinforcement with a random walk that alternates forward and backward steps on the bipartite hub-authority graph. Its authority score is a page's share of the in-links within its connected component, weighted by that component's share of all authorities, so one dense core cannot capture the whole ranking. Third, add a teleport, as PageRank does: mixing a small uniform vector into each update makes the iteration matrix strictly positive, which guarantees a unique principal eigenvector at the cost of biasing toward uniform.

Whatever you pick, measure the eigengap. The ratio of the second to the first singular value, estimated with a few extra iterations of a block method or a call to a sparse SVD routine for the top two triples, tells you whether to trust the ranking. A ratio above about 0.9 means the top results are a coin flip between two structures, and you should report that rather than a confident list.

Where HITS is still the right tool

HITS is rarely the right tool for ranking a whole web crawl today; PageRank-style global scores plus learned rankers do that job, as described in the search architecture write-up. It earns its keep on bipartite and near-bipartite data where the two roles are real:

In retrieval systems, a common modern use is as a re-ranking feature: retrieve a candidate set with lexical and dense retrieval, as in hybrid search with re-ranking, build the link or citation subgraph among the candidates, and feed the authority score to the final ranker as one signal among many.

Trade-offs

Pick HITS when the two roles mean something to your users and the subgraph is small and fresh. Pick PageRank when you need one stable global score you can precompute. Pick SALSA when you want two roles but have seen HITS collapse onto one dense cluster.

What to do next

1. Implement the sparse function above and pass the worked-example and SVD cross-check tests.
2. Build the two-component tie graph and confirm that different start vectors give different answers; then add a teleport of 0.05 and confirm they agree.
3. On your own graph, log the iteration count and an estimate of the second-to-first singular value ratio for every run.
4. Collapse duplicate links and drop same-host edges before scoring.
5. Compare HITS authority, SALSA authority and plain in-degree on a held-out relevance set before choosing one.
6. If you run it per query, cap in-link expansion and cache base sets for popular queries.