By the same authors

From the same journal

From the same journal

Dirichlet Densifier Bounds: Densifying Beyond the Spectral Gap Constraint

Research output: Contribution to journalArticle

Author(s)

Department/unit(s)

Publication details

JournalPattern Recognition Letters
DateAccepted/In press - 2 Jun 2019
DatePublished (current) - 1 Jul 2019
Volume125
Number of pages7
Pages (from-to)425-431
Original languageEnglish

Abstract

In this paper, we characterize the universal bounds of our recently reported Dirichlet Densifier. In particular we aim to study the impact of densification on the bounding of intra-class node similarities. To this end we derive a new bound for commute time estimation. This bound does not rely on the spectral gap, but on graph densification (or graph rewiring). Firstly, we explain how our densifier works and we motivate the bound by showing that implicitly constraining the spectral gap through graph densification cannot fully explain the cluster structure in real-world datasets. Then, we pose our hypothesis about densification: a graph densifier can only deal with a moderate degradation of the spectral gap if the inter-cluster commute distances are significantly shrunk. This points to a more detailed bound which explicitly accounts for the shrinking effect of densification. Finally, we formally develop this bound, thus revealing the deeper implications of graph densification in commute time estimation.

Bibliographical note

© Elsevier, 2019. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy.

    Research areas

  • Commute times, Graph densification, Spectral graph theory

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations