5 ms·

Can anyone explain why the PageRank patent was valuable when an alternative (Prof Jon Kleinberg's Hypertext Induced Topic Search or HITS algo) was published at

Can anyone explain why the PageRank patent was valuable when an alternative (Prof Jon Kleinberg's Hypertext Induced Topic Search or HITS algo) was published at the same time and available for use? https://en.wikipedia.org/wiki/HITS_algorithm https://en.wikipedia.org/wiki/HITS_algorithm

988747 4y ago
From your linked Wikipedia page: "it is executed at query time, not at indexing time, with the associated hit on performance that accompanies query-time processing" - for a search engine that planned to take over the Web that might have been a dealbreaker.
- iamcurious 4y ago
  Seems like an obvious optimization though. Is that enough to grant a patent?
saiajc 4y ago
Kleinberg's HITS algorithm actually came first. PageRank simplified HITS and made it more practical, by performing the ranking mechanism in batch mode for the entire web graph. If you read the original HITS paper, you'll see that HITS computes the top two eigenvectors for the cluster of all pages containing the query word (and pages pointing to those pages). Computing new eigenvectors for every search query obviously is much slower than PageRank.
srean 4y ago
The HITS algorithm has one drawback that it is super easy to game it. PageRank is not entirely resistant, but its a little more robust. For an algorithm that is used in the real world where commercial interests rules, sensitivity to adversarial attacks is very important -- Game Theory inspired algorithms will not be out of place. Note, one can definitely adopt 'hardening' strategies for both HITS and PageRank. Even around 2004 a naive, as presented in the tech-report, version of the PageRank algorithm was unusable without tweaks. Had you tried the unmodified version, you would have found that the top tier pages were mostly porn. There's also the fact that PageRank was presented as a query independent computation that could be done ahead of time and HITS as a query dependent computation. A resourceful enough person could however modify HITS into topic-wise precomputed HITS scores to be combined at run time based on the query. Ok so here is how one can game HITS. Create a harvester page that points to lots and lots of popular, high traffic pages on the internet. By virtue of doing this it can accumulate a lot of Hubs score which it can redirect as an Authority score to an intended page.
- samhw 4y ago
  > The HITS algorithm has one drawback that it is super easy to game it. PageRank is not entirely resistant, but its a little more robust. > Create a harvester page that points to lots and lots of popular, high traffic pages on the internet. By virtue of doing this it can accumulate a lot of Hubs score which it can redirect as an Authority score to an intended page. I'm not sure how HITS is any more "easy to game" than PageRank? As far as I understand it, the differences are almost entirely limited to performance characteristics, not semantics. The example you give doesn't seem to be specific to HITS (as opposed to PageRank) in any way. (I'm also not sure how "game theory" is relevant here, unless by "game theory" you just mean "the idea that people will try to game it".)
  - srean 4y ago
    One could pose this as an adversarial game. For the simplistic case consider two participants -- (i) the ranker that chooses a ranking scheme (we need to constrain the space of ranking schemes somehow for this to lead to any useful formulation), (ii) web page who tries to outrank other pages by strategically linking to other pages, and possibly buying links to itself from other pages. One can give (ii) a budget to add and delete links and pages that it can control. In this framework one then try to compute what's an equilibrium strategy. The multiplayer version is a lot more complicated. If you check my original comment, I gave a simple scheme to attack HITS rank. The main drawback is that one can 'harvest' Authority score using 'out-links'. Outlinks are cheap and easy, compared to 'inlinks'. Sybil attack is a little harder for Pagerank.
    - samhw 4y ago
      > If you check my original comment I gave a simple scheme to attack HITS rank. Sybil attack is a little harder for Pagerank. OK, but how is it harder for PageRank? I can't really see any differences in the semantics of the two algorithms, so I'm not sure what kind of added vulnerability one or the other could have. > One could pose this as an adversarial game. Yeah, I appreciate that, that's what I was referring to as "the idea that people will try to game it". It's not really the kind of 'game' that would be considered in game theory, though, because it doesn't have any interesting or emergent properties - the designer's response will just be "oh yeah we should stop people gaming our algorithm".

988747 4y ago

From your linked Wikipedia page: "it is executed at query time, not at indexing time, with the associated hit on performance that accompanies query-time processing" - for a search engine that planned to take over the Web that might have been a dealbreaker.

iamcurious 4y ago
Seems like an obvious optimization though. Is that enough to grant a patent?

saiajc 4y ago

Kleinberg's HITS algorithm actually came first. PageRank simplified HITS and made it more practical, by performing the ranking mechanism in batch mode for the entire web graph. If you read the original HITS paper, you'll see that HITS computes the top two eigenvectors for the cluster of all pages containing the query word (and pages pointing to those pages). Computing new eigenvectors for every search query obviously is much slower than PageRank.

srean 4y ago

The HITS algorithm has one drawback that it is super easy to game it. PageRank is not entirely resistant, but its a little more robust. For an algorithm that is used in the real world where commercial interests rules, sensitivity to adversarial attacks is very important -- Game Theory inspired algorithms will not be out of place. Note, one can definitely adopt 'hardening' strategies for both HITS and PageRank. Even around 2004 a naive, as presented in the tech-report, version of the PageRank algorithm was unusable without tweaks. Had you tried the unmodified version, you would have found that the top tier pages were mostly porn. There's also the fact that PageRank was presented as a query independent computation that could be done ahead of time and HITS as a query dependent computation. A resourceful enough person could however modify HITS into topic-wise precomputed HITS scores to be combined at run time based on the query. Ok so here is how one can game HITS. Create a harvester page that points to lots and lots of popular, high traffic pages on the internet. By virtue of doing this it can accumulate a lot of Hubs score which it can redirect as an Authority score to an intended page.

samhw 4y ago
> The HITS algorithm has one drawback that it is super easy to game it. PageRank is not entirely resistant, but its a little more robust. > Create a harvester page that points to lots and lots of popular, high traffic pages on the internet. By virtue of doing this it can accumulate a lot of Hubs score which it can redirect as an Authority score to an intended page. I'm not sure how HITS is any more "easy to game" than PageRank? As far as I understand it, the differences are almost entirely limited to performance characteristics, not semantics. The example you give doesn't seem to be specific to HITS (as opposed to PageRank) in any way. (I'm also not sure how "game theory" is relevant here, unless by "game theory" you just mean "the idea that people will try to game it".)
- srean 4y ago
  One could pose this as an adversarial game. For the simplistic case consider two participants -- (i) the ranker that chooses a ranking scheme (we need to constrain the space of ranking schemes somehow for this to lead to any useful formulation), (ii) web page who tries to outrank other pages by strategically linking to other pages, and possibly buying links to itself from other pages. One can give (ii) a budget to add and delete links and pages that it can control. In this framework one then try to compute what's an equilibrium strategy. The multiplayer version is a lot more complicated. If you check my original comment, I gave a simple scheme to attack HITS rank. The main drawback is that one can 'harvest' Authority score using 'out-links'. Outlinks are cheap and easy, compared to 'inlinks'. Sybil attack is a little harder for Pagerank.
  - samhw 4y ago
    > If you check my original comment I gave a simple scheme to attack HITS rank. Sybil attack is a little harder for Pagerank. OK, but how is it harder for PageRank? I can't really see any differences in the semantics of the two algorithms, so I'm not sure what kind of added vulnerability one or the other could have. > One could pose this as an adversarial game. Yeah, I appreciate that, that's what I was referring to as "the idea that people will try to game it". It's not really the kind of 'game' that would be considered in game theory, though, because it doesn't have any interesting or emergent properties - the designer's response will just be "oh yeah we should stop people gaming our algorithm".