What Does a Link Mean? Categorizing the Web at Kosmix
(This post is about our work at Kosmix in and around 2006)
Every hyperlink on the web is a decision somebody made. An author writing about diabetes stopped, chose one page out of all the pages in the world, and pointed at it. That decision carries information. But what information it carries depends entirely on what you think the decision was.
PageRank gave one answer, and it is a beautiful one. A link is a vote for importance: a page matters to the degree that pages which matter point at it. And because a reader browsing the web can follow only one link at a time, the importance a page passes along is divided among its outgoing links. Point at five hundred pages and each receives a five-hundredth of what you have to give.
That division is not an accounting convenience. It is a claim about the world, and for importance it is a correct one. Importance is finite. A reader has only so much attention, a page has only so much standing to lend, and the more places it sends you the less any one of them can be worth. The division is also what keeps the computation under control: nothing leaves a page that did not arrive there, so the numbers cannot run away, and the whole thing settles.
We were reading the same links to answer a different question. Kosmix was built on the premise that the web could be organized by topic, and we did not want to know which pages mattered. We wanted to know what each page was about.
Our intuition was that the links already knew. The author writing about diabetes does not point at random pages. She points at other pages about diabetes. So the same edge that PageRank reads as a vote is also, at the same moment, a claim of kinship: this page and I are about the same thing. If that claim could be followed the way importance is followed, then the web graph was not only a ranking waiting to be computed. It was a map.
Flavors
We called our scores flavors, and we built them the way topic-sensitive PageRank suggested. Instead of a walk that restarts anywhere on the web, you restart it only among a seed set — pages you are confident are about the topic — so that what accumulates is authority flavored by that topic rather than authority in general. Run that over our corpus of ten billion URLs and every page comes out with a score for how much of the topic it holds.
The seeds we chose by hand. We were running only a small number of flavors, so this was affordable, and it was deliberate: we did not want to be in the business of deciding how much starting weight to give each of thousands of pages. Pick a handful of pages that are unmistakably about health, give them the topic, and let the graph carry it outward. That was the bargain we made. Few seeds, and trust the propagation to do the rest.
What I was looking at
I was the one putting the signals together at query time, which is why this became my problem and not somebody else’s.
Some of the scores were computed offline and stored with each document — the popularity score, which was PageRank-like, and the flavor scores. One was computed live against the query, the classical text match, tf-idf as we did it in those days. My job was to weigh them against each other and produce a result list.
So I was not thinking about the meaning of an edge from a whiteboard. I was watching, query after query, what the flavor score actually did to a page’s position. And it worked. The flavors fed ranking, they made query categorization possible, they were what our vertical products stood on, and by any reasonable account they were earning their place. I do not think anybody else on the team was troubled by them.
But I kept coming away with the feeling that the signal was not giving us as much as it ought to. Not that it was wrong — that it was quiet. A graph containing this much topical information was handing back much less of it than it held. I should say plainly that this was a judgment and not a measurement. I ran no experiment that proved it. I had my hands in the data every day, and the flavor scores never moved a result list the way a signal this fundamental ought to move one.
What was actually happening
Take a top health site, a WebMD or a Mayo Clinic. That is exactly the kind of page you hand-pick as a seed for health, because it is unmistakably and comprehensively about health. Now look at what such a page does. It links to a thousand pages, nearly all of them health pages, because that is what a great health site is. Under the division rule, each of those thousand children receives one one-thousandth of the seed’s health score.
And here is the part that should have bothered me sooner. Every one of those thousand children receives exactly the same share. The best diabetes article on the web gets a thousandth. So does the careers page, and the privacy policy, and the terms of service, and the advertising partner. The propagation has no opinion whatever about which of those links is carrying the subject and which is the plumbing of a website. It divides by a count.
That single fact produced both of the symptoms I was seeing, though for a long time I thought they were separate problems.
The topic did not travel. We had chosen a small seed set on purpose, which meant the propagation was doing nearly all of the work, and the mass leaving each carefully chosen seed was fractionated a thousand ways at the first hop and fractionated again at the next. Whatever the graph knew about health three links out from Mayo Clinic, we were never going to hear it.
And the topic leaked. Health flowed into the careers page and out again into whatever the careers page happened to point at, because nothing in the arithmetic knew that a careers link is not a claim about health.
The rule counts links. It does not read them.
Importance divides. Aboutness does not.
This is where I came out, and it took me longer than it should have.
We had borrowed PageRank’s machinery, and we had borrowed its physics along with it without noticing that we had. Dividing a score among a page’s outgoing links asserts that what travels along an edge is a finite substance, conferred by the source and used up in the giving. For importance that is true. For aboutness it is nonsense.
When a page about diabetes links to five hundred other pages about diabetes, it is not sending a five-hundredth of a diabetes down each link. Every one of those links is a full-strength piece of evidence about the two pages it joins, and the fact that the author also wrote four hundred and ninety-nine others does not make any single one of them weaker. A claim of kinship is not diluted by being repeated. Importance divides among your neighbors. Aboutness does not.
That is the observation. What took me years to get straight in my own head is that the observation contains two quite different complaints, and only one of them can be fixed.
The fixable half
The first complaint is that the rule does not read the edges, and that is a defect you can simply repair.
Put a cheap text classifier inside the propagation. For each link, ask what it is carrying — look at the target page, look at the anchor text, which even then we knew was one of the most informative things on the web — and let the answer decide how much of the outflow goes down that edge. Health flows down the health links. Nothing at all goes to the careers page. The edges stop being interchangeable siblings and start being weighed according to what they are about.
We talked about doing this. We never did it. There was always something more urgent, it was one idea among many, and I was the only person it was keeping up at night. It would have helped, and I think it would have helped a great deal, and it was entirely within our reach in 2006.
But I should be clear about what it would and would not have done. Weighting the edges fixes the leak. It does not touch the dilution. If a thousand links out of Mayo Clinic are all genuinely about health, a classifier that correctly recognizes all thousand of them still has to divide the health among them, because otherwise the page gives away more than it was given. The signal would have gone to the right places. It would still have arrived thin.
That is division that reads, which is better than division that counts. It is still division.
The half I could not fix
The second complaint is the one that is still with me.
If aboutness really is not a finite substance, and each of Mayo’s thousand health links carries evidence at full strength, then the propagation is no longer moving a fixed quantity around the graph. It is manufacturing one. A page that received a single unit of health and points at a thousand health pages now emits a thousand units. Iterate that a few times and the numbers cease to mean anything.
This is not a technicality that a cleverer implementation gets around. Conservation is what makes these computations stop. The reason PageRank has an answer at all is that nothing leaves a node which did not arrive there, and if you give that up you have to buy stability some other way. Every way I could think of came back, in the end, to putting the division back where it had been.
So I had an objection that was right and a formulation that was unusable, which is a poor position to argue from, and I did not argue it very hard. What ran was the computation that converged. As the years went on we leaned more and more on text-based categorization to supply what the graph would not give us.
What I could not see then, and can only half see now, is that I was probably asking the wrong thing of the mathematics. I was treating it as a choice between aboutness being conserved and aboutness being unbounded, and evidence is neither of those. Ten pages telling you a document is about diabetes should make you more confident than one page telling you, but not ten times as confident, and never more than certain. Aboutness ought to saturate. A page should be able to be fully about diabetes and no more than that — and a computation with a ceiling in it does not need conservation to make it stop, because it has nowhere to run away to.
I could not write that computation down in 2006. There has been work in this direction since — ways of propagating a label through a graph that stay bounded without conserving anything, ways of combining evidence so that it accumulates toward certainty rather than adding up without limit. I have not spent the time to know whether any of it answers the question I was actually asking.
The two things a link says
I have never let go of the intuition. A link really does say we are about the same thing, and the web graph really is a map of topics as well as a ranking of pages. The difficulty was never in seeing that.
The difficulty is that a link says two things at once, and the two things obey different laws. Importance is a quantity and it is spent. Aboutness is a claim, and repeating it costs nothing. We had a beautiful machine for computing the first. We pointed it at the second, and for a long time I did not understand why the answers came back so thin.
That is the part I still turn over.