Methods, systems, and computer-readable media for a method of propagating signals across a web graph. A signal describes a document or otherwise provides useful information about a document in a web graph. A web graph is a collection of documents that are related to one another through links, such as hyperlinks. The signals are propagated in the sense that information from the related pages is associated with the target page even though the information may not be directly found in the target page. This information may then be used by a search engine to determine that a particular page is relevant to a search query.