Interpretable random forest model for identification of edge 3-uncolorable cubic graphs

Adam Dudáš; Bianka Modrovičová

Kybernetika (2023)

  • Volume: 59, Issue: 6, page 807-826
  • ISSN: 0023-5954

Abstract

top
Random forest is an ensemble method of machine learning that reaches a high level of accuracy in decision-making but is difficult to understand from the point of view of interpreting local or global decisions. In the article, we use this method as a means to analyze the edge 3-colorability of cubic graphs and to find the properties of the graphs that affect it most strongly. The main contributions of the presented research are four original datasets suitable for machine learning methods, a random forest model that achieves 97 . 35 % accuracy in distinguishing edge 3-colorable and edge 3-uncolorable cubic graphs, and the identification of crucial features of graph samples from the point of view of its edge colorability using Shapley values.

How to cite

top

Dudáš, Adam, and Modrovičová, Bianka. "Interpretable random forest model for identification of edge 3-uncolorable cubic graphs." Kybernetika 59.6 (2023): 807-826. <http://eudml.org/doc/299198>.

@article{Dudáš2023,
abstract = {Random forest is an ensemble method of machine learning that reaches a high level of accuracy in decision-making but is difficult to understand from the point of view of interpreting local or global decisions. In the article, we use this method as a means to analyze the edge 3-colorability of cubic graphs and to find the properties of the graphs that affect it most strongly. The main contributions of the presented research are four original datasets suitable for machine learning methods, a random forest model that achieves $97.35\%$ accuracy in distinguishing edge 3-colorable and edge 3-uncolorable cubic graphs, and the identification of crucial features of graph samples from the point of view of its edge colorability using Shapley values.},
author = {Dudáš, Adam, Modrovičová, Bianka},
journal = {Kybernetika},
keywords = {random forest; proper edge coloring; interpretable machine learning; snark},
language = {eng},
number = {6},
pages = {807-826},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Interpretable random forest model for identification of edge 3-uncolorable cubic graphs},
url = {http://eudml.org/doc/299198},
volume = {59},
year = {2023},
}

TY - JOUR
AU - Dudáš, Adam
AU - Modrovičová, Bianka
TI - Interpretable random forest model for identification of edge 3-uncolorable cubic graphs
JO - Kybernetika
PY - 2023
PB - Institute of Information Theory and Automation AS CR
VL - 59
IS - 6
SP - 807
EP - 826
AB - Random forest is an ensemble method of machine learning that reaches a high level of accuracy in decision-making but is difficult to understand from the point of view of interpreting local or global decisions. In the article, we use this method as a means to analyze the edge 3-colorability of cubic graphs and to find the properties of the graphs that affect it most strongly. The main contributions of the presented research are four original datasets suitable for machine learning methods, a random forest model that achieves $97.35\%$ accuracy in distinguishing edge 3-colorable and edge 3-uncolorable cubic graphs, and the identification of crucial features of graph samples from the point of view of its edge colorability using Shapley values.
LA - eng
KW - random forest; proper edge coloring; interpretable machine learning; snark
UR - http://eudml.org/doc/299198
ER -

References

top
  1. Bon-Gang, H., Performance and Improvements of Green Construction Projects., Elsevier 2018. 
  2. Caro, Y., Petrusevski, M., Skrekovski, R., , Discrete Math. 346 (2023), 2, 113221. MR4499342DOI
  3. Chaitin, G. J., Register allocation & spilling via graph colouring., In: Proc. 1982 SIGPLAN Symposium on Compiler Construction 1982, pp. 98-105. 
  4. Coolsaet, K., D'hondt, S., Goedgebeur, J., , Discrete Appl. Math. 325 (2023), 97-107. MR4506063DOI
  5. Custode, L. L., Iacca, G., , IEEE Access 11 (2023), 6169-6184. DOI
  6. Dudáš, A., Modrovičová, B., Decision trees in proper edge k-coloring of cubic graphs., In: Proc. 33rd Conference FRUCT Association 2023, pp. 21-29. 
  7. GraphFilter, Software to help Graph researches providing filtering and visualization to a given list of graphs., Graphfilter 2021. 
  8. Kowalik, L., , Theoret. Computer Sci. 410 (2009), 38-40, 3733-3742. MR2553326DOI
  9. Marx, D., Graph colouring problems and their applications in scheduling., Periodica Polytechn., Electr. Engrg. 48 (2004), 1-2, 11-16. 
  10. Molnar, C., Interpretable Machine Learning., Published independently, 2019. 
  11. Nettleton, D., Commercial Data Mining., Elsevier 2014. 
  12. Rabčan, J., Rusnák, P., Subbotin, S., Classification by Fuzzy decision trees inducted based on cumulative mutual information., In: Proc. 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET), 2018, pp. 208-212. 
  13. Roditty, L., Williams, V. V., , In: STOC '13, Proc. forty-fifth annual ACM symposium on Theory of Computing 2013, pp. 515-524. MR3210813DOI
  14. SageMath, Free open-source mathematics software system licensed under the GPL., Sagemath 2005. 
  15. Suil, O., Jeong, R. P., Jongyook, P., Wenqian, Z., , Europ. J. Combinatorics 110 (2023). MR4564485DOI
  16. Tantau, T., Complexity of the undirected radius and diameter problems for succinctly represented graphs., Technical Report SIIM-TR-A-08-03, Universität zu Lübeck, Lübeck, Germany, (2008). 
  17. Vizing, V. G., , Diskret. Analiz. 3 (1964), 25-30. MR0180505DOI
  18. Zhen-Mu, H., Hong-Jian, L., Zheng-Jiang, X., , Linear Algebra Appl. 607 (2020), 319-340. MR4139132DOI

NotesEmbed ?

top

You must be logged in to post comments.