Dirichlet Densifiers: Beyond Constraining the Spectral Gap

摘要

In this paper, we derive a new bound for commute times estimation. This bound does not rely on the spectral gap but on graph densi-fication (or graph rewiring). Firstly, we motivate the bound by showing that implicitly constraining the spectral gap through graph densifica-tion cannot fully explain some estimations in real datasets. Then, we set our working hypothesis: if densification can deal with a small/moderate degradation of the spectral gap, this is due to the fact that inter-cluster commute distances are considerably shrunk. This suggests a more detailed bound which explicitly accounts for the shrinking effect of densification. Finally, we formally develop this bound, thus uncovering the deep implications of graph densification in commute times estimation.