Lecture 11: Link Analysis

Standard IR models are important building blocks for web search, but are not sufficient. The web has some useful (and some difficult; looking at you SPAM) properties that we need to take into account.

  • Different information needs than in typical IR,
    • e.g. navigational queries: instead of typing an URL the user types a query and expects the website to be returned.
    • In this example, there is only one relevant document.
  • More information available than in full text
    • Metadata
    • Links etc.
  • Implicit usage feedback by clickthroughs on link is available and should be used

Q: In which way does web search have different information needs than traditional IR?

Web search algorithms are typically machine learning algorithms that combine standard models such as BM25 with the usage of link information, and in particular exploit large scale implicit feedback information in the form of clickthroughs

Link information

Links indicate the utility of a document.

  • Authority pages: pages that are linked to a lot
  • Hubs: pages that link to many other pages
  • Anchor text: provides extra text/summary for the document the link refers to

Link analysis

Builds on two intuitions:

  1. Textual context: The text in the anchor of a hyperlink is a good description of the target page
  2. Quality signal: The hyperlink from A to B represents an endorsement of page B by the creator of page A.
    • So very much related to the authority of a page

Q: What are the two main intuitions behind link analysis?

1. Textual context

<a href="http://www.amazon.com/">big online bookstore</a>
  • Textual context addresses the vocabulary mismatch problem information retrieval
  • The anchor text is very similar to navigational queries that search for the target
  • Separate document field can be created by aggregating anchors from all incoming links to leverage these properties

E.g. "IR summer school 2019", "ESSIR Italy", "ESSIR 2019", "European Summer School in Information Retrieval" are all descriptions to the same URL. As you can see aggregating these anchors provide a quite diverse and good description.

2. Quality signal: PageRank example

A clear example of this assumption is the PageRank algorithm, which captures page popularity (practically synonymous to authority).

Q: Which main assumption of link analysis (and which 'link information') does PageRank emphasize?

Main intuition: Pages visited more frequently in a random walk on the web are the more important ones.

Further intuitions:

  • Incoming link counts
    • A page is useful if it is cited often
  • Indirect citations
    • If important pages are pointing to a page, that page must be important
  • Smoothing
    • Smooth the citations to accommodate potential citations that have not yet been discovered.

Q: What's the purpose of citation smoothing in PageRank?

Don't really see where that came from; is also not in Zhai.

PageRank Scoring

PageRank is one of the many features that Google uses when ranking pages. This feature solely captures link structure of the web graph. The score is average popularity of that document, which expresses the chance a random surfer visits this page.

Q: Does PageRank take queries into account?

A: No, the visit probability of a page (PageRank) depends solely on the structure of the web graph (and parameter $\alpha$).

Assume a random surfer navigating the whole web.

  1. Start at a random page
  2. Go with probability $1-\alpha$ to any link from the current page, and with probability $\alpha$ to a random page in the initial set of candidates (the ones that link to the current page)
    • If there are no outgoing links, you always invoke this "teleport" function.
    • There's sort of an exploit-explore dynamic here if we see exploiting as following the current chain of links and exploring taking a bit more of a random leap and picking another chain.
  3. Repeat 2 until convergence, i.e. until PageRank value changes are below some threshold.

Final score of page d is the probability that the surfer reaches page d. More precise, assuming this random walk + teleport, it can be shown that each page will be visited a fraction of the time $\pi(v)$ (of a Markov Process) that depends on the structure of the web graph and the value of $\alpha$. I.e. the random surfer can be seen as a Markov chain with

  • one state for each web page
  • transition probabilities for the probability of moving from one web page to another web page.
  • the transition matrix can be derived from an adjacency matrix that only has 1 when two pages link to each other. (Zhai Ch.11, p.466)

$$PR(p) = \frac{\alpha}{N} + (1 - \alpha) \sum_{q \rightarrow p} \frac{PR(q)}{O(q)}$$

q -> p: q refers to page p.

N is the total number of pages in the Web graph and will be huge. Does it make sense to use it like that?

Google's PageRank actually leaves N out altogether!

O(q): number of outgoing links of page q

Note that when a page q with a lot of outgoing links (a hub) links to page p, then this contributes less authority/PageRank than when a page with little outgoing links links to the page.

Recursive. Stopping condition is when absolute values drop below a threshold. The iteration is guaranteed to converge!

A page network M can be represented as matrix M with $M_{ij}$ being probability of going from $d_i$ to $d_j$.

When we encounter a page without outgoing links, we assume it links to all other documents in the collection (i.e. it's heavily penalized). Otherwise we divide by O(q)=0, which is of course undefined.

Q: What's the role of hyperparameter alpha in the PageRank computation?

A: alpha is the probability of invoking the "teleport" function to any other node in the web graph. A typical value for alpha=0.1

N.B. in the computation example in the slide, always use the PageRank value from the previous iteration, not already the updated versions during the same iteration. Not sure if this is also the way it's applied on the whole web graph; not sure how you distinguish iterations there.

Topic-specific PageRank

If you know a user likes sports, you can change the teleport function to teleport to a random page on a subset of the webgraph with pages that are all about sports. Zhai 471-473 shows how that works.

You can create a personalized PageRank by using a mixture over these topic-specific PageRanks.

HITS (Hyperlink-Induced Topic Search)

(Not really in the lecture, see Zhai 21.3, p.474-...)

Earlier we identified two types of pages, hubs and authority pages. We can also compute a hub-score and an authority-score for each page.

For a query, we can then compute two ranked lists: one based on hub-scores, the other on authority-scores.

The main idea is that a good hub page for a particular topic points to many authorative pages for that topic. If this is true, we can use pages with very high hub-scores to find pages with high authority scores.

This means we end up with a recursive definition:

  • A good hub page is good because it points to authorative pages
  • An authority page is pointed to by many good hub pages

We can turn this into an iterative computation.

  1. Initialize each node v with $h(v)=a(v)=1$
  2. Each iteration, update hub and then authority scores

$$h(v) \leftarrow \sum_{v \rightarrow y} a(y)$$

$$a(v) \leftarrow \sum_{y \rightarrow v} h(y)$$

That is:

  • hub score increases with sum of the authority score of the nodes it points to.
  • authority score increases with the hub score of pages that refer to it

Can be shown that

  • This also converges to a steady state
  • Is also only dependent on the web graph structure