Skip to main content
SpringerLink
Log in
Book cover

International Workshop on Graph-Based Representations in Pattern Recognition

GbRPR 2017: Graph-Based Representations in Pattern Recognition pp 165–174Cite as

On the Interplay Between Strong Regularity and Graph Densification

  • Conference paper
  • First Online:

Part of the book series: Lecture Notes in Computer Science ((LNIP,volume 10310))

Abstract

In this paper we analyze the practical implications of Szemerédi’s regularity lemma in the preservation of metric information contained in large graphs. To this end, we present a heuristic algorithm to find regular partitions. Our experiments show that this method is quite robust to the natural sparsification of proximity graphs. In addition, this robustness can be enforced by graph densification.

This is a preview of subscription content, log in via an institution.

References

  1. Alon, N., Duke, R.A., Lefmann, H., Rödl, V., Yuster, R.: The algorithmic aspects of the regularity lemma. J. Algorithms 16(1), 80–109 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large graphs. Combinatorica 20(4), 451–476 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  3. Benavent, A.P., Escolano, F.: Entropy-based incremental variational Bayes learning of Gaussian mixtures. IEEE Trans. Neural Netw. Learn. Syst. 23(3), 534–540 (2012). http://dx.doi.org/10.1109/TNNLS.2011.2177670

  4. Escolano, F., Curado, M., Hancock, E.R.: Commute times in dense graphs. In: Robles-Kelly et al. [14], pp. 241–251

    Google Scholar 

  5. Escolano, F., Curado, M., Lozano, M.A., Hancock, E.R.: Dirichlet graph densifiers. In: Robles-Kelly et al. [14], pp. 185–195

    Google Scholar 

  6. Fiorucci, M., Torcinovich, A.: Alonszemerediregularitylemma github repository (2013). https://github.com/MarcoFiorucci/AlonSzemerediRegularityLemma

  7. Gowers, T.: Lower bounds of tower type for Szemerédi’s uniformity lemma. Geom. Func. Anal. 7(2), 322–337 (1997)

    Article  MATH  Google Scholar 

  8. Hardt, M., Srivastava, N., Tulsiani, M.: Graph densification. In: Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, 8–10 January 2012, pp. 380–392 (2012). http://doi.acm.org/10.1145/2090236.2090266

  9. Komlós, J., Shokoufandeh, A., Simonovits, M., Szemerédi, E.: The regularity lemma and its applications in graph theory. In: Khosrovshahi, G.B., Shokoufandeh, A., Shokrollahi, A. (eds.) Theoretical Aspects of Computer Science: Advanced Lectures, pp. 84–112. Springer, Berlin (2002)

    Chapter  Google Scholar 

  10. Komlós, J., Simonovits, M.: Szemerédi’s regularity lemma and its applications in graph theory. In: Miklós, D., Szonyi, T., Sós, V.T. (eds.) Combinatorics, Paul Erdós is Eighty, pp. 295–352. János Bolyai Mathematical Society, Budapest (1996)

    Google Scholar 

  11. Liu, W., He, J., Chang, S.: Large graph construction for scalable semi-supervised learning. In: Proceedings of the 27th International Conference on Machine Learning (ICML-2010), Haifa, Israel, 21–24 June 2010, pp. 679–686 (2010)

    Google Scholar 

  12. von Luxburg, U., Radl, A., Hein, M.: Hitting and commute times in large random neighborhood graphs. J. Mach. Learn. Res. 15(1), 1751–1798 (2014)

    MathSciNet  MATH  Google Scholar 

  13. Pelillo, M., Elezi, I., Fiorucci, M.: Revealing structure in large graphs: Szemerédi’s regularity lemma and its use in pattern recognition. Pattern Recogn. Lett. 87, 4–11 (2017)

    Article  Google Scholar 

  14. Robles-Kelly, A., Loog, M., Biggio, B., Escolano, F., Wilson, R. (eds.): S+SSPR 2016. LNCS, vol. 10029. Springer, Cham (2016)

    Google Scholar 

  15. Sperotto, A., Pelillo, M.: Szemerédi’s regularity lemma and its applications to pairwise clustering and segmentation. In: Proceedings of the 6th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2007, Ezhou, China, 27–29 August 2007, pp. 13–27 (2007)

    Google Scholar 

  16. Szemerédi, E.: Regular partitions of graphs. In: Colloques Internationaux CNRS 260–Problèmes Combinatoires et Théorie des Graphes, pp. 399–401. Orsay (1976)

    Google Scholar 

Download references

Acknowledgments

We are grateful to I. Elezi for his advice on our code implementation, and to the anonymous reviewers for their constructive feedback. Francisco Escolano and Manuel Curado are funded by the Project TIN2015-69077-P of the Spanish Government.

Author information

Authors and Affiliations

  1. DAIS, Ca’ Foscari University, Via Torino 155, 30172, Venezia Mestre, Italy

    Marco Fiorucci, Alessandro Torcinovich & Marcello Pelillo

  2. DCCIA, University of Alicante, 03690, San Vicente del Raspeig, Alicante, Spain

    Manuel Curado & Francisco Escolano

  3. ECLT, Ca’ Foscari University, S. Marco 2940, 30124, Venezia, Italy

    Marcello Pelillo

Authors
  1. Marco Fiorucci
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alessandro Torcinovich
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Manuel Curado
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Francisco Escolano
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Marcello Pelillo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francisco Escolano .

Editor information

Editors and Affiliations

  1. Università degli Studi di Salerno, Fisciano, Italy

    Pasquale Foggia

  2. Chinese Academy of Sciences, Beijing, China

    Cheng-Lin Liu

  3. Università degli Studi di Salerno, Fisciano, Italy

    Mario Vento

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Fiorucci, M., Torcinovich, A., Curado, M., Escolano, F., Pelillo, M. (2017). On the Interplay Between Strong Regularity and Graph Densification. In: Foggia, P., Liu, CL., Vento, M. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2017. Lecture Notes in Computer Science(), vol 10310. Springer, Cham. https://doi.org/10.1007/978-3-319-58961-9_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-58961-9_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-58960-2

  • Online ISBN: 978-3-319-58961-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation