Learning Graph Node Embeddings by Smooth Pair Sampling

Konstantin KutzkovAISTATS 2025

TL;DR

This paper introduces SmoothDeepWalk, a regularization technique for graph node embeddings that addresses the "rich-get-richer" problem in random walk-based models. By smoothing the frequency of node pairs used during training, the authors ensure that embeddings capture a broader range of structural relationships, leading to significant performance gains in link prediction and node classification, especially for low-degree nodes.

What Problem Does This Paper Address?

Most modern graph embedding techniques, like DeepWalk and node2vec, rely on the Skip-gram model. They generate random walks across a graph and treat nodes appearing close together in a walk as "positive pairs" that should have similar vector representations.

However, in real-world graphs, the frequency of these pairs follows a highly skewed, power-law (Zipfian) distribution. A tiny fraction of node pairs appears thousands of times, while the vast majority appear only once or twice. In standard training, the "heavy hitters" dominate the optimization objective. This causes the model to over-focus on preserving the similarity of a few highly connected nodes while neglecting the "middle-class" pairs that define the graph's more nuanced structure. This skewness makes the learning process less robust and often results in poor embeddings for nodes with fewer connections (low-degree nodes).

Methods

The authors propose Smooth Pair Sampling (and its implementation, SmoothDeepWalk) to rebalance the training data.

  1. Frequency Smoothing: Instead of using every pair generated by a random walk, they sample pairs with a probability proportional to $\#(u, v)^{\beta-1}$, where $\#(u, v)$ is the pair's frequency and $\beta \in (0, 1]$ is a smoothing exponent. When $\beta=1$, it’s standard DeepWalk; as $\beta$ decreases, the "tax" on frequent pairs increases, effectively boosting the relative importance of less frequent pairs.
  2. Efficient Sketching: Storing the exact frequency of every possible node pair is memory-prohibitive for large graphs. To solve this, the authors adapt the FREQUENT algorithm—a data sketching technique from the "heavy hitters" literature. This allows them to approximate pair frequencies in two passes over the random walk corpus with a very small memory footprint.
  3. Optimization: The smoothed pairs are fed into a standard binary classification model (using negative sampling) to learn the final $d$-dimensional embeddings.

Datasets

The researchers evaluated their approach on eight diverse, publicly available graph datasets:

  • Citation Networks: Cora, Citeseer, and Pubmed.
  • Social/Interaction Networks: Git, Deezer, and BlogCatalog.
  • Image/Word Networks: Flickr (images connected by properties) and Wikipedia (word co-occurrences).

These datasets vary significantly in size (from 2.7K to 89.3K nodes) and density, allowing the authors to test how graph structure affects the benefits of smoothing.

Key Insights and Ideas

  • The "Progressive Tax" Analogy: Smoothing acts as a regularizer that prevents a few "rich" pairs from monopolizing the embedding space. By lowering the training frequency of the top 5% of pairs, the model "discovers" the structural importance of the middle-class pairs.
  • Boosting the Underdog: A major "aha" moment in the paper is the discovery that smoothing specifically helps low-degree nodes. Because these nodes appear in fewer walks, their pairs are usually in the tail of the distribution. Smoothing ensures these nodes get enough "signal" to be embedded accurately without being drowned out by hubs.
  • Clustering Matters: The benefit of smoothing is tied to the graph's clustering coefficient. In dense graphs with high local connectivity (like Wikipedia), aggressive smoothing can actually be harmful because it might destroy local community structures. In sparse graphs (like Git or Flickr), smoothing is almost universally beneficial.
  • Efficiency over Complexity: Compared to previous "smooth negative sampling" (SNS) approaches, which require complex MCMC sampling and are computationally expensive, SmoothDeepWalk is orders of magnitude faster because it handles smoothing on the positive side using a simple hash-table lookup.

Key Results

  • Link Prediction: SmoothDeepWalk showed "impressive improvements" on larger, sparse graphs like Pubmed, Deezer, Git, and Flickr. In some cases, it outperformed standard DeepWalk by a wide margin in Precision@100 and Recall@100.
  • Node Classification: The authors observed statistically significant gains in Macro-F1 scores across six of the eight graphs.
  • Speed: The proposed method is roughly 30x to 50x faster than the leading competitor (SNS). While it adds a small overhead to standard DeepWalk (about 1.2x to 2.9x depending on the graph), the performance trade-off is highly favorable.
  • Stability: The results were consistent across different training sizes and hyperparameter settings, suggesting that the default values ($\beta \approx 0.5$ for sparse graphs) are robust.

Limitations and Future Work

The authors acknowledge a few areas for further exploration:

  • Small/Dense Graphs: On very small graphs like Cora and Citeseer, the improvements were not statistically significant. The authors suggest that in these cases, the data is so limited that even the "frequent" pairs are necessary for basic structure.
  • GNN Integration: While this paper focuses on transductive embeddings (DeepWalk/node2vec), the authors briefly showed that smoothing can be applied to Graph Neural Networks (like GraphSage). However, the gains there were more modest, and more work is needed to integrate smoothing into the GNN message-passing framework.
  • Theoretical Gap: While the paper provides strong empirical evidence and some Zipfian analysis, a complete theoretical explanation for why smoothing fails to help link prediction on high-clustering graphs remains an open question.

Summary updated

BibTeX
@inproceedings{kutzkov2025learning,
  author = {Konstantin Kutzkov},
  title = {{Learning Graph Node Embeddings by Smooth Pair Sampling}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
}

Loading related content...

Figure