Beyond Snapshots: Learning from the History of Edge Creation for Link Prediction

TL;DR

Unsupervised link prediction usually treats graphs as static snapshots, ignoring how the graph actually grew. This paper introduces a method that "rewinds" the graph to the moment every existing edge was born, using those historical topological features to train a predictor that outperforms standard baselines and time-series models with significantly lower computational overhead.

Background: The Static Snapshot Limitation

Most link prediction algorithms (like Jaccard or Adamic-Adar) look at a graph at time $T$ and ask: "Who is likely to connect at $T+1$?" While effective, this ignores a goldmine of data: the network was not always this way. Every edge currently in the graph was once a "predicted" link that came true.

The authors argue that by ignoring the state of the network at the time of those past "births," we lose the very context—the specific topological "weather"—that makes a connection likely.

Methodology: The Edge Creation History Retrieval ($H$)

The proposed method $H$ follows a unique three-step pipeline integrated into the standard unsupervised workflow:

1. History Retrieval: For every edge $(u,v)$ that appeared in the training set, the algorithm calculates similarity metrics (Common Neighbors, Adamic-Adar, etc.) based on the network state exactly at the timestamp $t$ when that edge was created.
2. Clustering the "Birth" Conditions: These historical data records are clustered (using k-means). This identifies regions in the feature hyperspace where connections are most frequent.
3. Link Potential Calculation: For a new, non-connected pair, the method calculates its current features, maps it to the nearest cluster, and assigns a score based on that cluster's historical productivity ($NormPop$) and how "typical" the pair is relative to the cluster's centroid.

Figure: The process of retrieving historical states and clustering for score assignment.

Why it Works (Physical Intuition)

In a co-authorship network, two researchers might connect because they share a small, tight-knit group of collaborators, or because they are both extremely "popular" (high degree). By clustering, the model implicitly learns these different "modes" of connection. A pair that looks like a "typical" historical connection gets a higher score.

Experimental Results

The authors tested the method on four major physics co-authorship datasets (Gr-qc, Hep-th, Cond-mat, Hep-ph).

Superiority over Agnostic Methods

The "History-Aware" version ($H$) was compared against a "History-Agnostic" version ($C$) that used the same metrics but only on the final snapshot. $H$ won in 18 out of 20 tested scenarios, proving that when you measure similarity matters as much as what you measure.

Performance vs. Time-Series

Compared to more complex time-series models like Linear Regression (LR) or Moving Averages (MA):

• Accuracy: $H$ was statistically superior to Random Walk (RW) and Moving Average (MA).
• Efficiency: This is where $H$ shines. While time-series models required processing all non-connected pairs over multiple frames (taking hours or even days), $H$ only processes the existing edges for its history retrieval, completing in under 31 minutes even on the largest graphs.

Table: Comparison of Improvement Factors (Imp.) and Execution Time across scenarios.

Critical Insight & Conclusion

The method's genius lies in its event-driven nature. Traditional time-aware methods use fixed-length time "frames" (e.g., snapshots every month). These frames are arbitrary—Twitter moves in seconds; Academia moves in years.

By anchoring history retrieval to the exact moment of edge creation, $H$ becomes agnostic to the "speed" of the network. It captures the "circumstances" of connection regardless of the timeframe.

Future Outlook

While powerful, the current method is tested primarily on co-authorship graphs. The next frontier is applying this "Birth History" logic to more volatile networks (like social media follows) or supervised learning frameworks where this historical data could serve as enriched feature sets for GNNs.