RaRE: Decoupling Popularity from Proximity in Large-Scale Graph Embeddings

TL;DR

Most graph embedding algorithms (like Node2vec or LINE) assume that if node A connects to node B, they must be "similar." RaRE challenges this by proving that social rank (popularity) is a distinct force of attraction. By using a Bayesian framework to decouple Social Rank from Proximity, RaRE achieves superior performance in link prediction and classification on massive networks like Snapchat and Wikipedia.

The Problem: The "Celebrity" Trap in Homophily

In network science, the "Homophily" assumption—the idea that "birds of a feather flock together"—is the bedrock of embedding. If you follow a niche researcher, you likely share their interests. But what if you follow a global pop star or a major politician?

Current models treat these links identically, causing the learned vectors to become a "mixture" of true similarity and raw popularity. This leads to two major issues:

1. Feature Blur: High-degree nodes (hubs) pull unrelated nodes toward them in the latent space.
2. Inefficiency: Models need higher dimensions to compensate for the noise introduced by popularity-driven links.

Methodology: The Bayesian "Explaining Away" Effect

The core insight of RaRE is that the reason for a link changes based on the relative rank of the nodes.

The authors propose a link generation model where the probability of a link $e_{ij}$ is a function of rank difference ($dr$) and embedding distance ($dz$).

The Intuition behind the Math:

• Insignificant Others: If a link exists between two "ordinary" nodes, it is almost certainly due to Proximity (high similarity).
• Celebrity Following: If a link exists from a student to a Nobel laureate, it can be "explained away" by the Social Rank of the laureate, meaning the student's embedding doesn't necessarily need to be identical to the professor's.

Figure 1: Comparison between traditional models (left) and RaRE's decoupled Bayesian model (right).

The objective function is derived via Maximum A Posteriori (MAP) estimation, using a long-tailed Power Law prior for social ranks to reflect the reality that "influentials" are rare while "ordinary users" are many.

Experiments and SOTA Performance

The model was tested on massive datasets, including a Snapshot friendship graph with 1.5 million nodes and 66 million edges.

1. Superior Link Prediction

The results were staggering: RaRE with only 2 dimensions often outperformed traditional models like Node2vec or LINE using 32 dimensions. This proves that by specifically modeling rank, we can capture the network structure much more efficiently.

2. Real-world Value (Gender Prediction)

In a production setting at Snap Inc., the team added RaRE embeddings to an already high-performing Gradient Boosted Decision Tree (GBDT) model for gender prediction.

• Baseline Accuracy: 93.5%
• With RaRE: 95.0% (+1.5% absolute lift) In the world of billion-user industrial models, a 1.5% lift is considered a massive breakthrough.

Figure 2: Multi-label classification results showing RaRE's consistent lead over MF, GF, and LINE.

Visualizing the Network: Polar Coordinates

One of the most elegant contributions of this paper is the Polar Coordinate Visualization. Instead of a standard 2D scatter plot, the authors use:

• Radius ($r$): Representing the Social Rank (Influentials in the center).
• Angle ($heta$): Representing the Proximity-based community.

In the Venue Citation graph, this successfully placed top conferences (CVPR, ICML, KDD) at the center of the "universe," with niche venues circling the periphery.

Figure 3: RaRE Polar Visualization vs. t-SNE and PCA. Notice how RaRE naturally organizes the "hierarchy" of the network.

Critical Insight & Conclusion

RaRE succeeds because it acknowledges that networks are not flat. By treating rank as a fundamental dimension rather than a nuisance variable or a simple bias term, it creates a cleaner embedding space.

Future Outlook: As we move toward larger Graphs (Graph Neural Networks), integrating explicit hierarchy and rank-based "explaining away" logic could significantly reduce the oversmoothing problems seen in deep GNN architectures.

Takeaway: When modeling social interactions, don't just ask who is connected; ask why—is it because they are alike, or because one is simply too famous to ignore?