Separating Structure from Noise in Large Graphs Using the Regularity Lemma

作者：

Highlights：

• Provides a summarization algorithm based on the Regularity Lemma, which is able to separate structural information from noise in large graphs.

• Discusses how to use our summarization framework to efficiently retrieve from a database the top-k graphs that are most similar to a query graph.

• Successfully validates the proposed framework both on synthetic and real-world networks showing that our algorithm surpasses the state-of-the-art in terms of noise robustness.

摘要

•Provides a summarization algorithm based on the Regularity Lemma, which is able to separate structural information from noise in large graphs.•Discusses how to use our summarization framework to efficiently retrieve from a database the top-k graphs that are most similar to a query graph.•Successfully validates the proposed framework both on synthetic and real-world networks showing that our algorithm surpasses the state-of-the-art in terms of noise robustness.

论文关键词：Regularity lemma,Graph summarization,Structural patterns,Noise,Randomness,Graph similarity search

论文评审过程：Received 10 December 2018, Revised 4 September 2019, Accepted 26 September 2019, Available online 27 September 2019, Version of Record 6 October 2019.

论文官网地址：https://doi.org/10.1016/j.patcog.2019.107070