Proofs: HITS algorithm

The HITS iterates converge to principal eigenvectors of A^T A and A A^T full

This proof shows: correctness, termination.

Let $G$ have $n$ nodes and adjacency matrix $A$ with non-negative entries, and let $M = A^{\mathsf T} A$. Write $a_t$ and $h_t$ for the vectors $a$ and $h$ after round $t$ of HITS, and $\mathbf{1}$ for the vector of all ones, so $h_0 = \mathbf{1}$. All norms are Euclidean.

Lemma 1 (the rounds are power iteration). If $A \ne 0$, then for each $t \ge 1$ that the algorithm reaches, $a_t = M^{t-1} x_0 / \lVert M^{t-1} x_0 \rVert$ with $x_0 = A^{\mathsf T} \mathbf{1}$, and $h_t = A a_t / \lVert A a_t \rVert$. Line L5 never returns, and line L6 never divides by zero.

Proof. Line L3 sets $a'_v = \sum_{(u,v) \in E} h_u$, which is $(A^{\mathsf T} h)_v$, and line L4 sets $h'_u = \sum_{(u,v) \in E} a'_v = (A a')_u$. By induction on $t$, assume $h_{t-1}$ is a positive multiple of $A M^{t-2} x_0$ for $t \ge 2$, and $h_0 = \mathbf{1}$. Then $a'$ in round $t$ is a positive multiple of $A^{\mathsf T} \mathbf{1} = x_0$ when $t = 1$, and of $A^{\mathsf T} A M^{t-2} x_0 = M^{t-1} x_0$ when $t \ge 2$. Lemma 2 below shows $M^{t-1} x_0 \ne 0$, so $a' \ne 0$ and line L5 does not return. Then $h' = A a'$, and $h_{t-1}^{\mathsf T} h' = (A^{\mathsf T} h_{t-1})^{\mathsf T} a' = \lVert a' \rVert^2 > 0$, so $h' \ne 0$. Line L6 scales both by positive numbers, which gives the formulas of the claim and keeps the hypothesis for $t + 1$, since $h_t$ is a positive multiple of $A a' $, a positive multiple of $A M^{t-1} x_0$. $\square$

Lemma 2 (the start vector sees the top eigenspace). $M$ is symmetric and positive semidefinite. Let $\lambda_1$ be its largest eigenvalue and $P$ the orthogonal projection onto its eigenspace. If $A \ne 0$, then $\lambda_1 > 0$ and $P x_0 \ne 0$.

Proof. $M^{\mathsf T} = A^{\mathsf T} A = M$, and $y^{\mathsf T} M y = \lVert A y \rVert^2 \ge 0$ for each $y$. The trace of $M$ is $\sum_{u,v} A_{uv}^2 > 0$, so $\lambda_1 > 0$. The matrix $M$ has non-negative entries. By the Perron-Frobenius theorem for non-negative matrices, its spectral radius, which is $\lambda_1$ since all eigenvalues are non-negative, has an eigenvector $w$ with $w \ge 0$ and $w \ne 0$. Since $w = A^{\mathsf T}(A w) / \lambda_1$, each entry $w_v$ is a sum of non-negative terms $A_{uv} (Aw)_u / \lambda_1$, so $w_v = 0$ at each node $v$ with no entering arc. At each node $v$ with $w_v > 0$, some $A_{uv} > 0$, so $(x_0)_v = \sum_u A_{uv} > 0$. Hence $x_0^{\mathsf T} w > 0$. As $w$ lies in the eigenspace, $x_0^{\mathsf T} w = (P x_0)^{\mathsf T} w$, so $P x_0 \ne 0$. In particular $M^{t} x_0 \ne 0$ for every $t$, since its projection is $\lambda_1^{t} P x_0 \ne 0$. $\square$

Theorem (convergence). Assume $A \ne 0$. Let $\lambda_2'$ be the largest eigenvalue of $M$ that is less than $\lambda_1$, or $0$ if there is none. Then $a_t \to a^* = P x_0 / \lVert P x_0 \rVert$ and $h_t \to h^* = A a^* / \lVert A a^* \rVert$, with $\lVert a_t - a^* \rVert \le 2 (\lambda_2'/\lambda_1)^{t-1} \lVert x_0 \rVert / \lVert P x_0 \rVert$. The vector $a^*$ is a non-negative eigenvector of $M$ for $\lambda_1$, and $h^*$ is a non-negative eigenvector of $A A^{\mathsf T}$ for $\lambda_1$.

Proof. Take an orthonormal basis of eigenvectors of $M$. Write $x_0 = P x_0 + r$, where $r$ lies in the span of the eigenvectors with eigenvalues below $\lambda_1$. Then $M^{t-1} x_0 = \lambda_1^{t-1} (P x_0 + r_t)$ with $r_t = M^{t-1} r / \lambda_1^{t-1}$, and since every eigenvalue in that span is in $[0, \lambda_2']$, $\lVert r_t \rVert \le (\lambda_2'/\lambda_1)^{t-1} \lVert r \rVert \le (\lambda_2'/\lambda_1)^{t-1} \lVert x_0 \rVert$. For non-zero vectors $p$ and $p + q$, $\big\lVert \frac{p + q}{\lVert p + q \rVert} - \frac{p}{\lVert p \rVert} \big\rVert \le \frac{2 \lVert q \rVert}{\lVert p \rVert}$, by the triangle inequality and $\big| \lVert p + q \rVert - \lVert p \rVert \big| \le \lVert q \rVert$. With Lemma 1 and $p = P x_0$, $q = r_t$, this gives the bound, which tends to 0 because $\lambda_2' < \lambda_1$. The vector $a^*$ is in the eigenspace of $\lambda_1$. It is non-negative because each $a_t$ is non-negative, as a scaled sum of non-negative terms, and the limit of non-negative vectors is non-negative. It is not zero, so $A a^* \ne 0$ because $\lVert A a^* \rVert^2 = a^{*\mathsf T} M a^* = \lambda_1 > 0$. The map $y \mapsto A y / \lVert A y \rVert$ is continuous where $A y \ne 0$, so $h_t \to h^*$ by Lemma 1. Finally $A A^{\mathsf T} (A a^*) = A (M a^*) = \lambda_1 A a^*$, so $h^*$ is an eigenvector of $A A^{\mathsf T}$ for $\lambda_1$. $\square$

Termination. The loop of line L2 runs at most $K$ rounds, so the algorithm stops. If $\varepsilon > 0$, it may stop earlier at line L9: by the theorem, $a_t$ and $h_t$ converge, so $\lVert a_t - a_{t-1} \rVert + \lVert h_t - h_{t-1} \rVert \to 0$, and the test of line L9 holds after finitely many rounds. If $A = 0$, line L3 gives $a' = 0$ in round 1 and line L5 returns two zero vectors, which is the stated output for a graph with no arcs.

Uniqueness. If $\lambda_1$ is a simple eigenvalue, its eigenspace is a line, and $a^*$ is the unique eigenvector of norm 1 with non-negative entries on it; $h^*$ is then unique too. If $\lambda_1$ is repeated, $a^*$ is the normalized projection of the in-degree vector $x_0$ onto the eigenspace, which is determined by the graph. $\blacksquare$