2
$\begingroup$

As we know, computing the authority (or hub) score of HITS ranking method, means to use the following matrix equation:

$$ \textbf{a}^{k}=A^T A\textbf{a}^{(k-1)} $$

and apply the power iteration method, but with significant problems: actually, AFAIK, the convergence in not guaranteed, for the matrix $A^T A$ is sometimes not irreducible (so we cannot use Perron-Frobenius theorem and the power method may converge to nonunique solutions).

Now, I'm wondering: why not apply the SVD to $A$, in order to find the dominant eigenvector(s) of $A^T A$? Do you notice any possible issue with this approach? Will the computational cost be prohibitive?

Improve this question
$\endgroup$
1
  • $\begingroup$ I am not an expert in this sparse matrix comp's, but my intuition is that you are correct and a Krylov-based method for sparse svd (Matlab's svds, not svd) will yield better results than a "vanilla" power iteration. I wanted to mention it because the only answer up to now points in the opposite direction (and refers to non-sparse svd only). $\endgroup$
    – Federico Poloni
    Apr 11, 2014 at 12:23

1 Answer 1

Reset to default
1
$\begingroup$

The method is typically applied to matrices that are so incredibly large that you cannot do things like an SVD. Note that in the SVD you would also compute the matrix whose vectors correspond to the singular values, and this matrix is full. This is not feasible unless $A$ is small, nor can it be done in a stable way.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ To add to this, computing an SVD is overkill for the HITS algorithm; it only wants the dominant eigenvector, so it's possible that even for a problem for which an SVD is computable, it might not be the fastest way. $\endgroup$
    – Sumedh Joshi
    Apr 8, 2014 at 1:29
  • 1
    $\begingroup$ Thanks for your replies. Two objections: 1. HITS works on a neighbourhood graph, which is much smaller than Web graph of, e.g., PageRank.. SVD might be feasible, up to some extent. 2. In some contexts, one needs more than just the first eigenvector (ambiguous or polarized queries that cause graph clustering in two or more quasi-disconnected components.. First eigenvector ranks just the largest of these clusters..) $\endgroup$
    – MadHatter
    Apr 9, 2014 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.