Dirichlet densifiers for improved commute times estimation. (July 2019)

• Record Type: Journal Article
• Authors: Curado, Manuel; Escolano, Francisco; Lozano, Miguel A.; Hancock, Edwin R.
• Is Part Of: Pattern recognition. Volume 91(2019:Jul.)
• Page Start: 56
• Page End: 68
• Publication Date: 2019-07
• Subjects: Graph densification -- Dirichlet problems -- Random walkers -- Commute times; 00-01 -- 99-00; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2019.02.012
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: 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. Abstract: In this paper, we develop a novel Dirichlet densifier that can be used to increase the edge density in undirected graphs. Dirichlet densifiers are implicit minimizers of the spectral gap for the Laplacian spectrum of a graph. One consequence of this property is that they can be used improve the estimation of meaningful commute distances for mid-size graphs by means of topological modifications of the original graphs. This results in a better performance in clustering and ranking. To do this, we identify the strongest edges and from them construct the so called line graph, where the nodes are the potential q − step reachable edges in the original graph. These strongest edges are assumed to be stable . By simulating random walks on the line graph, we identify potential new edges in the original graph. This approach is fully unsupervised and it is both more scalable and robust than recent explicit spectral methods, such as the Semi-Definite Programming (SDP) densifier and the sufficient condition for decreasing the spectral gap. Experiments show that our method is only outperformed by some choices of the parameters of a related method, the anchor graph, which relies on pre-computing clusters representatives, and that the proposed method is effective on a variety of real-world datasets.