Challenges find a dense temporal determine a time interval [,j] subgraph find a dense subgraph given [,j Filter-and-Verification[ Bogdanov et al. 11 consider all time intervals [, j] and find dense subgraphs by fixing[i, j] each time filter [ j] if its upper bound of cohesive density is worse than the best cohesive density achieved prune 99%of a total of T*(T+1)2 time intervals T 447 1,414 14,142 T*T+1/2 10 10 10 108 unpruned 10 10 104 106 Filter-and-Verification is insuficient for large temporal graphs! A new and better algorithm design philosophy is needed P BogdanoV, M. Mongiov, A K Singh. Mining heavy subgraphs in time-evolving networks. In /CDM, 2011. 8Challenges ➢ Filter-and-Verification[Bogdanov et al. 11] • consider all time intervals [i, j] and find dense subgraphs by fixing [i, j] each time • filter [i, j] if its upper bound of cohesive density is worse than the best cohesive density achieved • prune 99% of a total of T*(T+1)/2 time intervals P. Bogdanov, M. Mongiov, A. K. Singh. Mining heavy subgraphs in time-evolving networks. In ICDM, 2011. 8 T 141 447 1,414 ··· 14,142 T*(T+1)/2 104 105 106 ··· 108 # unpruned 102 103 104 ··· 106 Filter-and-Verification is insufficient for large temporal graphs! A new and better algorithm design philosophy is needed. determine a time interval [i, j] find a dense subgraph given [i, j] find a dense temporal subgraph