CISPA
Browse

Graph Similarity Description: How Are These Graphs Similar?

Download (2.53 MB)
conference contribution
posted on 2023-11-29, 18:18 authored by Corinna Coupette, Jilles VreekenJilles Vreeken
How do social networks differ across platforms? How do information networks change over time? Answering questions like these requires us to compare two or more graphs. This task is commonly treated as a measurement problem, but numerical answers give limited insight. Here, we argue that if the goal is to gain understanding, we should treat graph similarity assessment as a description problem instead. We formalize this problem as a model selection task using the Minimum Description Length principle, capturing the similarity of the input graphs in a common model and the differences between them in transformations to individual models. To discover good models, we propose Momo, which breaks the problem into two parts and introduces efficient algorithms for each. Through an extensive set of experiments on a wide range of synthetic and real-world graphs, we confirm that Momo works well in practice

History

Preferred Citation

Corinna Coupette and Jilles Vreeken. Graph Similarity Description: How Are These Graphs Similar?. In: ACM International Conference on Knowledge Discovery and Data Mining (KDD). 2021.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM International Conference on Knowledge Discovery and Data Mining (KDD)

Legacy Posted Date

2021-12-16

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3545, title = "Graph Similarity Description: How Are These Graphs Similar?", author = "Coupette, Corinna and Vreeken, Jilles", booktitle="{ACM International Conference on Knowledge Discovery and Data Mining (KDD)}", year="2021", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC