Dynamic Graph Link Prediction Techniques

Nonparametric Link Prediction in Dynamic Graphs Purnamrita Sarkar (UC Berkeley) Deepayan Chakrabarti (Facebook) Michael Jordan (UC Berkeley) 1

Link Prediction Who is most likely to be interact with a given node? Should Facebook suggest Alice as a friend for Bob? Alice Bob Friend suggestion in Facebook 2

Link Prediction Alice Should Netflix suggest this movie to Alice? Bob Charlie Movie recommendation in Netflix 3

Link Prediction Prediction using simple features degree of a node number of common neighbors last time a link appeared What if the graph is dynamic? 4

Related Work Generative models Exp. family random graph models [Hanneke+/ 06] Dynamics in latent space [Sarkar+/ 05] Extension of mixed membership block models [Fu+/10] Other approaches Autoregressive models for links [Huang+/09] Extensions of static features [Tylenda+/09] 5

Goal Link Prediction incorporating graph dynamics, requiring weak modeling assumptions, allowing fast predictions, and offering consistency guarantees. 6

Outline Model Estimator Consistency Scalability Experiments 7

The Link Prediction Problem in Dynamic Graphs YT+1 (i,j)=? Y1 (i,j)=1 Y2 (i,j)=0 G2 GT+1 G1 YT+1(i,j) | G1,G2, ,GT ~ Bernoulli (gG1,G2, GT(i,j)) Features of previous graphs and this pair of nodes Edge in T+1 8

Including graph-based features Example set of features for pair (i,j): cn(i,j) (common neighbors) (i,j) (last time a link was formed) deg(j) Represent dynamics using datacubes of these features. multi-dimensional histogram on binned feature values 1 cn 3 3 deg 6 1 2 t = #pairs in Gt with these features high t+/ t this feature combination is more likely to create a new edge at time t+1 cn deg t+ = #pairs in Gt with these features, which had an edge in Gt+1 9

Including graph-based features 1 cn(i,j) 3 3 deg(i,j) 6 1 (i,j) 2 YT+1 (i,j)=? Y2 (i,j)=0 Y1 (i,j)=1 G2 G1 GT How do we form these datacubes? Vanilla idea: One datacube for Gt Gt+1 aggregated over all pairs (i,j) Does not allow for differently evolving communities 10

Our Model 1 cn(i,j) 3 3 deg(i,j) 6 1 (i,j) 2 YT+1 (i,j)=? Y2 (i,j)=0 Y1 (i,j)=1 G2 G1 GT How do we form these datacubes? Our Model: One datacube for each neighborhood Captures local evolution 11

Our Model Neighborhood Nt(i)= nodes within 2 hops 1 cn(i,j) 3 3 deg(i,j) 6 1 (i,j) 2 Features extracted from (Nt-p, Nt) Datacube Number of node pairs - with feature s - in the neighborhood of i - at time t Number of node pairs - with feature s - in the neighborhood of i - at time t - which got connected at time t+1 12

Our Model Datacube dt(i) captures graph evolution in the local neighborhood of a node in the recent past Model: g(dt(i), st(i,j)) YT+1(i,j) | G1,G2, ,GT ~ Bernoulli ( gG1,G2, GT(i,j)) What is g(.)? Features of the pair Local evolution patterns 13

Outline Model Estimator Consistency Scalability Experiments 14

Kernel Estimator for g G1 G2 GT-2 GT-1 GT { { { { { { { { { { { { { { { { { { { { { { { { { { query data-cube at T-1 and feature vector at time T compute similarities datacube, feature pair t=2 datacube, feature pair t=1 datacube, feature pair t=3 15

Kernel Estimator for g K( , )I{ == } } } } Factorize the similarity function Allows computation of g(.) via simple lookups 16

Kernel Estimator for g G1 G2 GT-2 GT-1 GT compute similarities only between data cubes w1 w2 w3 w4 w w + 1 , 1+ 2 , 2+ 3 , 3+ 4 , 4+ datacubes t=3 w datacubes t=2 datacubes t=1 + + + + + 2 w + + w w w w 1 1 2 3 3 4 4 1 + 2 + 3 4 17 1 2 3 4

Kernel Estimator for g K( , )I{ == } } } } Factorize the similarity function Allows computation of g(.) via simple lookups What is K( , )? 18

Similarity between two datacubes Idea 1 For each cell s, take ( 1+/ 1 2+/ 2)2 and sum 1 , 1+ Problem: Magnitude of is ignored 5/10 and 50/100 are treated equally Consider the distribution 2 , 2+ 19

Similarity between two datacubes Idea 2 0.07 0.06 0.05 0.04 For each cell s, compute posterior distribution of edge creation prob. dist = total variation distance between distributions summed over all cells 0.03 0.02 0.01 0 0 5 10 15 20 25 30 35 40 45 1 , 1+ 0.14 0.12 0.1 0.08 0.06 0.04 0.02 0 0 5 10 15 20 25 30 35 40 45 2 , 2+ = dist( , ) K( , ) b 0<b<1 As b 0, K( , ) 0 unless dist( , ) =0 20

Kernel Estimator for g 1 h + = t ) , K( + 1 # ( h , ) = g ( g , ) g Want to show: ( f , ) 1 f = t ) , K( + 1 # 21

Outline Model Estimator Consistency Scalability Experiments 22

Consistency of Estimator ( h , ) = ( g , ) ( f , ) Lemma 1: As T , for some R>0, Proof using: As T , 23

Consistency of Estimator ( h , ) = ( g , ) ( f , ) Lemma 2: As T , 24

Consistency of Estimator Assumption: finite graph Proof sketch: Dynamics are Markovian with finite state space the chain must eventually enter a closed, irreducible communication class geometric ergodicity if class is aperiodic (if not, more complicated ) strong mixing with exponential decay variances decay as o(1/T) 25

Consistency of Estimator Theorem: Proof Sketch: for some R>0 So 26

Outline Model Estimator Consistency Scalability Experiments 27

Scalability Full solution: Summing over all n datacubes for all T timesteps Infeasible Approximate solution: Sum over nearest neighbors of query datacube How do we find nearest neighbors? Locality Sensitive Hashing (LSH) [Indyk+/98, Broder+/98] 28

Using LSH Devise a hashing function for datacubes such that Similar datacubes tend to be hashed to the same bucket Similar = small total variation distance between cells of datacubes 29

Using LSH Step 1: Map datacubes to bit vectors 0.07 Use B2 bits for each bucket 0.06 0.05 0.04 0.03 For probability mass p the first bits are set to 1 0.02 0.01 0 0 5 10 15 20 25 30 35 40 45 Use B1 buckets to discretize [0,1] Total M*B1*B2 bits, where M = max number of occupied cells << total number of cells 30

Using LSH Step 1: Map datacubes to bit vectors Total variation distance L1 distance between distributions Hamming distance between vectors Step 2: Hash function = k out of MB1B2 bits 31

Fast Search Using LSH 0000 0001 0011 1111111111000000000111111111000 10000101000011100001101010000 . . . . 10101010000011100001101010000 1011 101010101110111111011010111110 1111111111000000000111111111001 1111 32

Outline Model Estimator Consistency Scalability Experiments 33

Experiments Baselines LL: last link (time of last occurrence of a pair) CN: rank by number of common neighbors in ?? AA: more weight to low-degree common neighbors Katz: accounts for longer paths static on ?? CN-all: apply CN to ?1 ?? AA-all, Katz-all: similar static on ?? 34

Setup G2 G1 GT+1 GT Test data Training data Pick random subset S from nodes with degree>0 in GT+1 ? ?, predict a ranked list of nodes likely to link to s Report mean AUC (higher is better) 35

Simulations Social network model of Hoff et al. Each node has an independently drawn feature vector Edge(i,j) depends on features of i and j Seasonality effect Feature importance varies with season different communities in each season Feature vectors evolve smoothly over time evolving community structures 36

Simulations NonParam is much better than others in the presence of seasonality CN, AA, and Katz implicitly assume smooth evolution 37

Sensor Network* * www.select.cs.cmu.edu/data 38

Summary Link formation is assumed to depend on the neighborhood s evolution over a time window Admits a kernel-based estimator Consistency Scalability via LSH Works particularly well for Seasonal effects differently evolving communities 39