The cold-start problem is the inability to make predictions for entities with no historical data. A new user on an e-commerce platform has no purchase history, no browsing sessions, no reviews. Collaborative filtering cannot recommend products (no learned user vector). A tabular churn model cannot score them (no historical features to compute). A fraud model cannot assess their risk (no transaction patterns).
GNNs address cold start fundamentally differently from traditional approaches: they compute embeddings from what a node is (features) and who it connects to (graph structure), not from what it has done (history).
Why traditional methods fail
Collaborative filtering
Matrix factorization learns a latent vector for each user and each item by factorizing the interaction matrix. User-item affinity is the dot product of their vectors. A new user has no vector because they have no interactions to learn from. The model literally has no representation for them.
Shallow graph embeddings
Node2Vec and DeepWalk learn a fixed vector per node from random walks. New nodes were not in the training graph, so they have no embedding. Retraining on the updated graph is required, but by the time retraining finishes, more new nodes have arrived.
Feature-based tabular models
A churn model with features like “number of orders in last 30 days” and “average session duration” produces all-zero features for a new user. The model defaults to the population base rate, providing no personalization.
How GNNs solve cold start
GNNs are inductive: they compute embeddings from features and structure, not from lookup tables. A new node can be embedded immediately if it has:
1. Attribute features
Even new entities have attributes. A new user has age, location, device type, and registration channel. A new product has title, category, price, and brand. These attributes are encoded as the node's initial feature vector, providing a starting representation.
2. Initial connections
A new user who signed up via a referral link is connected to the referrer. A new user who browsed the “electronics” category is connected to that category node. A new product in the “shoes” category is connected to the category node and the brand node.
These initial connections, even if sparse, provide graph context. Through message passing, the new node receives information from its connected nodes, which have rich historical embeddings.
3. Type information
In heterogeneous graphs, node type provides immediate context. A “premium account” node type inherits different initial representations from a “free tier” node type. Type-specific encodings provide a useful prior before any interaction data exists.
Cold start quality depends on available signal
Not all cold starts are equal. The prediction quality depends on what information the new node brings:
- Rich features + connections: new user with demographic data, referred by an active user, browsed several categories. High-quality embedding.
- Features only: new user with demographic data but no connections yet. Moderate quality; the GNN uses features but cannot leverage graph context.
- Connections only: new product with no description but assigned to a category. Moderate quality; the GNN inherits category context.
- Minimal information: anonymous user, no features, no connections. Lowest quality; the model falls back to population-level priors.
Enterprise impact
In enterprise applications, cold start is not an edge case. It is continuous:
- E-commerce: thousands of new products listed daily, millions of new user sessions weekly
- Financial services: new accounts opened hourly, new merchants onboarding daily
- Healthcare: new patients admitted, new drugs prescribed, new diagnoses recorded
Systems that handle cold start poorly lose value on every new entity until enough history accumulates. GNN-based systems provide useful predictions from day one.