Dirichlet densifiers for improved commute times estimation

Highlights：

• Investigate links between densification, spectral gap and cheeger constant. SDP densification can be seen a simplification of the problem of bounding the spectral gap (making the spectral gap very low is a necessary condi- tion for improving the measurement of commute times in mid-size/large graphs).

• Given that the SDP approach is both inefficient and non-scalable we pro- pose an alternative: Dirichlet densifiers.

• Dirichlet densifiers rely on the idea of rewiring the weights of the input graphs so that the resulting graph is better conditioned for measuring commute times (a kind of “graph processing”).

• We show that the combination between filtering random walks (return random walks) and Dirichlet (minimal energy) diffusion leads to improve significantly the estimation of commute times.

• We find “universal” thresholds for several datasets.

摘要

•Explain the densification problem in terms of Semi-definite programming (SDP) to a Pattern Recognition audience. This is motivated by the need of improving the measurements of commute times in mid-sized graphs.•Investigate links between densification, spectral gap and cheeger constant. SDP densification can be seen a simplification of the problem of bounding the spectral gap (making the spectral gap very low is a necessary condi- tion for improving the measurement of commute times in mid-size/large graphs).•Given that the SDP approach is both inefficient and non-scalable we pro- pose an alternative: Dirichlet densifiers.•Dirichlet densifiers rely on the idea of rewiring the weights of the input graphs so that the resulting graph is better conditioned for measuring commute times (a kind of “graph processing”).•We show that the combination between filtering random walks (return random walks) and Dirichlet (minimal energy) diffusion leads to improve significantly the estimation of commute times.•We find “universal” thresholds for several datasets.