[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Graph Matching Networks Meet Optimum-Path Forest: How to Prune Ensembles Efficiently

  • Conference paper
  • First Online:
Pattern Recognition (ICPR 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15307))

Included in the following conference series:

  • 79 Accesses

Abstract

Ensemble pruning techniques are widely used to enhance a set of classifiers’ efficiency and predictive performance by selecting a subset of representative models, preventing redundancy, and ensuring diversity in classification tasks. The Optimum-Path Forest (OPF), a stable and efficient graph-based framework, offers versatile supervised and unsupervised capabilities in various machine-learning applications. The supervised version provides remarkable results with a simple graph-based structure produced by a training process conducted over a single dataset. However, one can notice little effort in OPF-based ensemble learning. This paper introduces an innovative approach to pruning OPF classifiers using meta-descriptions learned by Graph-Matching Networks, which are further employed to cluster similar OPF instances. The strategy selectively chooses representative models that excel in predictive tasks from groups generated by unsupervised OPF. Results demonstrate competitive performance to state-of-the-art pruning algorithms, with experiments conducted over fifteen public datasets, encouraging further exploration of Graph Matching Networks applied to ensemble pruning.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 49.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 64.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    https://archive.ics.uci.edu.

  2. 2.

    https://github.com/sbuschjaeger/PyPruning.

  3. 3.

    Although unsupervised OPF figures one hyperparameter only, i.e., k-max, it can learn the number of clusters on-the-fly.

  4. 4.

    https://github.com/Lin-Yijie/Graph-Matching-Networks.

References

  1. Biggs, N., Lloyd, E.K., Wilson, R.J.: Graph Theory, pp. 1736–1936. Oxford University Press, Oxford (1986)

    Google Scholar 

  2. Caetano, T.S., McAuley, J.J., Cheng, L., Le, Q.V., Smola, A.J.: Learning graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 31(6), 1048–1058 (2009)

    Article  Google Scholar 

  3. Fernandes, S.E.N., Passos, L.A., Jodas, D.S., Akio, M., de Souza, A.N., Papa, J.P.: A multi-class probabilistic optimum-path forest. In: Proceedings of the 18th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2023), vol. 5: VISAPP, pp. 361–368. INSTICC, SciTePress (2023)

    Google Scholar 

  4. Fernandes, S.E., Pereira, D.R., Ramos, C.C., Souza, A.N., Gastaldello, D.S., Papa, J.P.: A probabilistic optimum-path forest classifier for non-technical losses detection. IEEE Trans. Smart Grid 10(3), 3226–3235 (2018)

    Article  Google Scholar 

  5. Fey, M., Lenssen, J.E., Morris, C., Masci, J., Kriege, N.M.: Deep graph matching consensus. arXiv preprint arXiv:2001.09621 (2020)

  6. Guo, H., Liu, H., Li, R., Wu, C., Guo, Y., Xu, M.: Margin & diversity based ordering ensemble pruning. Neurocomputing 275, 237–246 (2018)

    Article  Google Scholar 

  7. Guo, X., Hu, J., Chen, J., Deng, F., Lam, T.L.: Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment. IEEE Rob. Autom. Lett. 6(4), 8349–8356 (2021)

    Article  Google Scholar 

  8. Jiang, Z., Hu, X., Gao, S.: A parallel ford-fulkerson algorithm for maximum flow problem. In: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), p. 70. The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp) (2013)

    Google Scholar 

  9. Jodas, D.S., Passos, L.A., Adeel, A., Papa, J.P.: PL-kNN: a parameterless nearest neighbors classifier. In: 2022 29th International Conference on Systems, Signals and Image Processing (IWSSIP), pp. 1–4. IEEE (2022)

    Google Scholar 

  10. Jodas, D.S., Passos, L.A., Rodrigues, D., Lucas, T.J., Da Costa, K.A.P., Papa, J.P.: OPFsemble: an ensemble pruning approach via optimum-path forest. In: 2023 30th International Conference on Systems, Signals and Image Processing (IWSSIP), pp. 1–5. IEEE (2023)

    Google Scholar 

  11. Lê-Huu, D.K., Paragios, N.: Alternating direction graph matching. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4914–4922. IEEE (2017)

    Google Scholar 

  12. Li, Y., Gu, C., Dullien, T., Vinyals, O., Kohli, P.: Graph matching networks for learning the similarity of graph structured objects. In: International Conference on Machine Learning, pp. 3835–3845. PMLR (2019)

    Google Scholar 

  13. Lin, Y., Yang, M., Yu, J., Hu, P., Zhang, C., Peng, X.: Graph matching with bi-level noisy correspondence. In: 2023 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 23305–23314. IEEE Computer Society, Los Alamitos (2023)

    Google Scholar 

  14. Lyzinski, V., et al.: Spectral clustering for divide-and-conquer graph matching. Parallel Comput. 47, 70–87 (2015)

    Article  MathSciNet  Google Scholar 

  15. Martínez-Muñoz, G., Hernández-Lobato, D., Suárez, A.: An analysis of ensemble pruning techniques based on ordered aggregation. IEEE Trans. Pattern Anal. Mach. Intell. 31(2), 245–259 (2008)

    Article  Google Scholar 

  16. Mei-Ko, K.: Graphic programming using odd or even points. Chin. Math. 1, 237–277 (1962)

    MathSciNet  Google Scholar 

  17. Papa, J.P., Falcão, A.X., Albuquerque, V.H.C., Tavares, J.M.R.S.: Efficient supervised optimum-path forest classification for large datasets. Pattern Recogn. 45(1), 512–520 (2012)

    Article  Google Scholar 

  18. Papa, J.P., Falcão, A.X., Suzuki, C.T.N.: Supervised pattern classification based on optimum-path forest. Int. J. Imaging Syst. Technol. 19(2), 120–131 (2009)

    Article  Google Scholar 

  19. Passos, L.A., Papa, J.P., Hussain, A., Adeel, A.: Canonical cortical graph neural networks and its application for speech enhancement in audio-visual hearing aids. Neurocomputing 527, 196–203 (2023)

    Article  Google Scholar 

  20. Passos, L.A., Jodas, D.S., Ribeiro, L.C., Akio, M., De Souza, A.N., Papa, J.P.: Handling imbalanced datasets through optimum-path forest. Knowl.-Based Syst. 242, 108445 (2022)

    Article  Google Scholar 

  21. Pavithra, R., Priyadharshini, S., Hemanandhini, G.: Image matching using weighted graph matching algorithm. In: 7th International Conference on Advanced Computing and Communication Systems (ICACCS), vol. 1, pp. 1–5 (2021)

    Google Scholar 

  22. Qu, J., Ling, H., Zhang, C., Lyu, X., Tang, Z.: Adaptive edge attention for graph matching with outliers. In: Zhou, Z.H. (ed.) Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 966–972. International Joint Conferences on Artificial Intelligence Organization (8 2021)

    Google Scholar 

  23. Rocha, L.M., Cappabianco, F.A.M., Falcão, A.X.: Data clustering as an optimum-path forest problem with applications in image analysis. Int. J. Imaging Syst. Technol. 19(2), 50–68 (2009)

    Article  Google Scholar 

  24. Swoboda, P., Rother, C., Alhaija, H., Kainmuller, D., Savchynskyy, B.: A study of lagrangean decompositions and dual ascent solvers for graph matching. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 7062–7071. IEEE Computer Society, Los Alamitos (2017)

    Google Scholar 

  25. Ugander, J., Karrer, B., Backstrom, L., Marlow, C.: The anatomy of the facebook social graph. arXiv preprint arXiv:1111.4503 (2011)

  26. Wang, R., Yan, J., Yang, X.: Learning combinatorial embedding networks for deep graph matching. In: 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 3056–3065. IEEE Computer Society, Los Alamitos (2019)

    Google Scholar 

  27. Xu, H., Luo, D., Zha, H., Duke, L.C.: Gromov-Wasserstein learning for graph matching and node embedding. In: Proceedings of the 36th International Conference on Machine Learning, pp. 6932–6941. PMLR (2019)

    Google Scholar 

  28. Zyblewski, P., Woźniak, M.: Novel clustering-based pruning algorithms. Pattern Anal. Appl. 23(3), 1049–1058 (2020)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors are grateful to the Brazilian National Council for Scientific and Technological Development (CNPq) grants 308529/2021-9 and 400756/2024-2, to the São Paulo Research Foundation (FAPESP) grants 2013/07375-0, 2018/25225-9, 2019/07665- 4, 2023/14427-8, 2023/10823-6, 2023/03726-4, 2023/01374-3, and 2023/14354-0, to Unesp-IEPe-RC-#06/2023 PROPe grant, and the Petrobrás Brazil grant #2017/00285-6 for their financial support.

Author information

Authors and Affiliations

  1. São Paulo State University (UNESP), School of Sciences, Bauru, Brazil

    Danilo Jodas, Leandro A. Passos, Douglas Rodrigues, Kelton Costa & João Paulo Papa

Authors
  1. Danilo Jodas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Leandro A. Passos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Douglas Rodrigues
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kelton Costa
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. João Paulo Papa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Danilo Jodas .

Editor information

Editors and Affiliations

  1. University of Salford, Salford, Lancashire, UK

    Apostolos Antonacopoulos

  2. Indian Institute of Technology Bombay, Mumbai, Maharashtra, India

    Subhasis Chaudhuri

  3. Johns Hopkins University, Baltimore, MD, USA

    Rama Chellappa

  4. Chinese Academy of Sciences, Beijing, China

    Cheng-Lin Liu

  5. IIT Kharagpur, Kharagpur, West Bengal, India

    Saumik Bhattacharya

  6. Indian Statistical Institute Kolkata, Kolkata, West Bengal, India

    Umapada Pal

Rights and permissions

Reprints and permissions

Copyright information

© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Jodas, D., Passos, L.A., Rodrigues, D., Costa, K., Paulo Papa, J. (2025). Graph Matching Networks Meet Optimum-Path Forest: How to Prune Ensembles Efficiently. In: Antonacopoulos, A., Chaudhuri, S., Chellappa, R., Liu, CL., Bhattacharya, S., Pal, U. (eds) Pattern Recognition. ICPR 2024. Lecture Notes in Computer Science, vol 15307. Springer, Cham. https://doi.org/10.1007/978-3-031-78183-4_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-78183-4_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-78182-7

  • Online ISBN: 978-3-031-78183-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation