Link-Only Training of Host-Level Web Graph Embeddings

Why People Wanted It

A web graph tells you which hosts link to which other hosts, but a list of edges is awkward input for many machine-learning tasks. The useful question is: can the link structure alone give each host a compact numerical representation that reflects its place in the graph?

The challenge is scale and sparsity. A host with almost no links gives little evidence about its role, yet including every such node adds work. The goal here is not to encode what a site says, but to turn who it links to—and who links to it—into a usable host-level vector.

The Core Move

Give each retained host a vector, then train linked pairs to score above randomly sampled unlinked pairs:

$s(u,v)=\mathbf{z}_u^\top\mathbf{z}_v,\qquad s(u,v^+) > s(u,v^-)$

Here $u$ is a host, $v^+$ is a real linked host, and $v^-$ is a sampled non-link. The representation is learned from graph links alone, with no host text or metadata.

Why Low-Link Hosts Add Little Structure

Now the version for readers who want more of the machinery: the filter is an evidence threshold, not a claim that excluded hosts are unimportant. A node with only a handful of incident links provides few observed relationships from which to position its vector. Keeping such nodes in training would spend capacity on representations constrained by very little graph context.

The training graph starts with 279.4 million hosts and about 13.4 billion links, drawn from the November 2025, December 2025, and January 2026 crawls. Retaining hosts with at least eight links leaves 52.9 million hosts—19% of the hosts—while preserving 97.3% of the links. The practical tradeoff is explicit: drop many weakly connected nodes to retain nearly all observed edges. This threshold does not make the remaining graph complete or remove sampling bias; it simply focuses training on hosts with more link evidence.

Why Positive Links Compete With Sampled Non-Links

Here is the part that gets technical: each training comparison asks whether a real edge should be more compatible than randomly selected host pairs. The host vectors are the learnable quantities, and the score is their inner product, $\mathbf{z}_u^\top\mathbf{z}_v$. In words, hosts whose vectors align get a higher pair score.

For an observed link $(u,v^+)$, the procedure draws 50 random non-links $v^-_1,\ldots,v^-_{50}$ and adjusts the vectors so the observed pair scores higher than those sampled pairs. This is a relative ranking signal, not a text-based label and not a guarantee that every unlinked pair is truly unrelated: the negatives are sampled non-links. The source specifies the comparison goal and sample count, not a particular margin or loss formula, so the mechanism is best stated at that level.

Why the Vectors Encode Only Link Structure

Now one level deeper: the model receives anonymous node numbers and graph links, not hostnames, page text, or metadata. That constraint determines what a learned coordinate can mean. A vector can reflect patterns in which hosts connect to which other hosts, but it cannot directly encode a site's wording or an explicitly supplied topic label.

The released representation has 128 dimensions for each retained host. Similarity in that space can therefore arise from link-structural patterns; it should not be read as proof that two sites share content or intent. The source reports that language regions separate in a visualization despite the absence of text input, consistent with sites tending to link to others in the same language. That is an emergent structural signal, not a language feature supplied to the training objective.

Minimal Causal Code

This plain loop makes the learning signal visible. It uses a generic pairwise ranking loss to illustrate the stated goal; it is not a claim about the exact training loss implementation.

import torch
import torch.nn.functional as F

# One learnable vector per host; positive_edges contains observed links.
emb = torch.nn.Embedding(num_hosts, 128)
optimizer = torch.optim.Adam(emb.parameters())

for src, dst in batches:
    # Compare each real link against 50 sampled non-links.
    negatives = sample_host_ids(len(src), 50)
    u = emb(src)
    pos = (u * emb(dst)).sum(dim=-1)
    neg = (u[:, None, :] * emb(negatives)).sum(dim=-1)

    # Make each positive score exceed its sampled negative scores.
    loss = F.softplus(neg - pos[:, None]).mean()
    optimizer.zero_grad()
    loss.backward()
    optimizer.step()

What You Gain, and What You Lose

You gain a compact, host-level representation learned from hyperlinks without needing text or metadata as model inputs. The link-only constraint also makes the learned signal interpretable in scope: it comes from graph connectivity.

You lose direct access to what pages say. Sparse hosts are filtered out, and sampled non-links are only training contrasts—not verified examples of semantic dissimilarity. A vector captures link patterns, so treating it as a complete description of a website would overstate what the training signal contains.

Quiz

What is the training signal for the host vectors?

Every host should be assigned a manually chosen topic label.

Real linked host pairs should score higher than randomly sampled non-linked pairs.

Hosts with similar text should receive identical vectors.

Unlinked pairs are treated as verified examples of semantic opposites.

$ check