Revisiting Link Prediction with the Dowker Complex

Oregon Convention Center 

We propose a novel method to study properties of graph-structured data by means of a geometric construction called Dowker complex. We study this simplicial complex through the use of persistent homology, which has shown to be a prominent tool to uncover relevant geometric and topological information in data. A positively weighted graph induces a distance in its sets of vertices. A classical approach in persistent homology is to construct a filtered Vietoris-Rips complex with vertices on the vertices of the graph. However, when the size of the set of vertices of the graph is large, the obtained simplicial complex may be computationally hard to handle. A solution The Dowker complex is constructed on a sample in the set of vertices of the graph called landmarks. A way to guaranty sparsity and proximity of the set of landmarks to all the vertices of the graph is by considering ε-nets. We provide theoretical proofs of the stability of the Dowker construction and comparison with the Vietorips-Rips construction. We perform experiments showing that the Dowker complex based neural networks model performs good with respect to baseline methods.