2016/09/15 by Rajmonda S. Caceres, Leah Weiner, Caceres, Rajmonda S. +7
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Bioinformatics and Genomic Networks #FOS: Computer and information sciences #FOS: Physical sciences #Graph Theory and Algorithms #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #cs.SI #physics.soc-ph
paper · pdf · doi:10.48550/arxiv.1609.04859
7 pages
arxiv created 2016/09/15 · openalex publication_date 2016/09/15 · arxiv updated 2016/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graphs are powerful abstractions for capturing complex relationships in diverse application settings. An active area of research focuses on theoretical models that define the generative mechanism of a graph. Yet given the complexity and inherent noise in real datasets, it is still very challenging to identify the best model for a given observed graph. We discuss a framework for graph model selection that leverages a long list of graph topological properties and a random forest classifier to learn and classify different graph instances. We fully characterize the discriminative power of our approach as we sweep through the parameter space of two generative models, the Erdos-Renyi and the stochastic block model. We show that our approach gets very close to known theoretical bounds and we provide insight on which topological features play a critical discriminating role.