Blink Proximity - overview
Humans have intuitions for graph proximity. Given a graph, certain pairs of nodes are perceived to have stronger relation strength than others. We know that a larger number of shorter paths indicate greater proximity, yet a precise mathematical formulation of such perception is elusive. This project is an attempt to design this formulation.
This project proposes a new measure of graph proximity, i.e., a new definition of relation strength between nodes in a graph. We demonstrate that this new measure is more consistent with human intuition than existing proximity measures, including PageRank, effective conductance, Katz and many others, and empirically quantify its advantage on link prediction benchmarks.
The following is an informal description of the basic form of this new measure. Please refer to the publications for rigorous definitions, discussions and generalizations. Consider a given graph as a graph that blinks: edges and nodes exist with certain probabilities. The proposed proximity measure is, for two nodes A and B:
s(A,B) = -log( 1 - P[at least one path exists from A to B] )
- "Measuring graph proximity with blink model," Haifeng Qian, Hui Wan, Mark N. Wegman, Luis A. Lastras and Ruchir Puri, International Workshop on Mining and Learning with Graphs (a KDD workshop), 2016. video
- "A proximity measure using blink model," Haifeng Qian, Hui Wan, Mark N. Wegman, Luis A. Lastras and Ruchir Puri, arXiv:1612.07365, 2016.
- "Ranking related objects using blink model based relation strength determinations," Haifeng Qian, Hui Wan, U.S. Patent 9946800, 2018.
These are two temporal link prediction benchmarks. Documentation can be downloaded here.
- Predicting new relations in coauthorship social networks: a replication of the experiments in the following paper. Data and code can be downloaded here.
- D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7):1019-1031, 2007.
- Predicting additions of inter-wikipage citations in Wikipedia from April 2014 to March 2015. Data and code can be downloaded here.