Differentially Describing Groups of Graphs


  • Corinna Coupette Max Planck Institute for Informatics
  • Sebastian Dalleiger CISPA Helmholtz Center for Information Security
  • Jilles Vreeken CISPA Helmholtz Center for Information Security




Data Mining & Knowledge Management (DMKM), Machine Learning (ML)


How does neural connectivity in autistic children differ from neural connectivity in healthy children or autistic youths? What patterns in global trade networks are shared across classes of goods, and how do these patterns change over time? Answering questions like these requires us to differentially describe groups of graphs: Given a set of graphs and a partition of these graphs into groups, discover what graphs in one group have in common, how they systematically differ from graphs in other groups, and how multiple groups of graphs are related. We refer to this task as graph group analysis, which seeks to describe similarities and differences between graph groups by means of statistically significant subgraphs. To perform graph group analysis, we introduce Gragra, which uses maximum entropy modeling to identify a non-redundant set of subgraphs with statistically significant associations to one or more graph groups. Through an extensive set of experiments on a wide range of synthetic and real-world graph groups, we confirm that Gragra works well in practice.




How to Cite

Coupette, C., Dalleiger, S., & Vreeken, J. (2022). Differentially Describing Groups of Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4), 3959-3967. https://doi.org/10.1609/aaai.v36i4.20312



AAAI Technical Track on Data Mining and Knowledge Management