Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Computing Vertex-Vertex Dissimilarities Using Random Trees: Application to Clustering in Graphs

Kevin Dalleau 1 Miguel Couceiro 2 Malika Smail-Tabbone 3
2 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
3 CAPSID - Computational Algorithms for Protein Structures and Interactions
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : A current challenge in graph clustering is to tackle the issue of complex networks, i.e, graphs with attributed vertices and/or edges. In this paper, we present GraphTrees, a novel method that relies on random decision trees to compute pairwise dissimilarities between vertices in a graph. We show that using different types of trees, it is possible to extend this framework to graphs where the vertices have attributes. While many existing methods that tackle the problem of clustering vertices in an attributed graph are limited to categorical attributes, GraphTrees can handle heterogeneous types of vertex attributes. Moreover, unlike other approaches, the attributes do not need to be preprocessed. We also show that our approach is competitive with well-known methods in the case of non-attributed graphs in terms of quality of clustering, and provides promising results in the case of vertex-attributed graphs. By extending the use of an already well established approach-the random trees-to graphs, our proposed approach opens new research directions, by lever-aging decades of research on this topic.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/hal-02427563
Contributor : Miguel Couceiro <>
Submitted on : Friday, January 3, 2020 - 5:24:41 PM
Last modification on : Thursday, January 16, 2020 - 10:56:03 AM
Long-term archiving on: : Monday, April 6, 2020 - 8:26:37 PM

File

GraphTrees-Overleaf.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02427563, version 1

Citation

Kevin Dalleau, Miguel Couceiro, Malika Smail-Tabbone. Computing Vertex-Vertex Dissimilarities Using Random Trees: Application to Clustering in Graphs. 2019. ⟨hal-02427563⟩

Share

Metrics

Record views

64

Files downloads

204