Kybernetika 59 no. 6, 807-826, 2023

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

Adam Dudáš and Bianka ModrovičováDOI: 10.14736/kyb-2023-6-0807

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\

Keywords:

random forest, proper edge coloring, interpretable machine learning, snark

Classification:

68T20, 68T10

paper.pdf

References:

  1. H. Bon-Gang: Performance and Improvements of Green Construction Projects. Elsevier 2018.   CrossRef
  2. Y. Caro, M. Petrusevski and R. Skrekovski: Remarks on proper conflict-free colorings of graphs. Discrete Math. 346 (2023), 2, 113221.   DOI:10.1016/j.disc.2022.113221
  3. G. J. Chaitin: Register allocation \& spilling via graph colouring. In: Proc. 1982 SIGPLAN Symposium on Compiler Construction 1982, pp. 98-105.   CrossRef
  4. K. Coolsaet, S. D'hondt and J. Goedgebeur: House of Graphs 2.0: A database of interesting graphs and more. Discrete Appl. Math. 325 (2023), 97-107.   DOI:10.1016/j.dam.2022.10.013
  5. L. L. Custode and G. Iacca: Evolutionary learning of interpretable decision trees. IEEE Access 11 (2023), 6169-6184.   DOI:10.1109/ACCESS.2023.3236260
  6. A. Dudáš and B. Modrovičová: Decision trees in proper edge k-coloring of cubic graphs. In: Proc. 33rd Conference FRUCT Association 2023, pp. 21-29.   CrossRef
  7. GraphFilter: Software to help Graph researches providing filtering and visualization to a given list of graphs. Graphfilter 2021.   CrossRef
  8. L. Kowalik: Improved edge-coloring with three colors. Theoret. Computer Sci. 410 (2009), 38-40, 3733-3742.   DOI:10.1016/j.tcs.2009.05.005
  9. D. Marx: Graph colouring problems and their applications in scheduling. Periodica Polytechn., Electr. Engrg. 48 (2004), 1-2, 11-16.   CrossRef
  10. C. Molnar: Interpretable Machine Learning. Published independently, 2019.   CrossRef
  11. D. Nettleton: Commercial Data Mining. Elsevier 2014.   CrossRef
  12. J. Rabčan, P. Rusnák and S. Subbotin: 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.   CrossRef
  13. L. Roditty and V. V. Williams: Fast approximation algorithms for the diameter and radius of sparse graphs. In: STOC '13, Proc. forty-fifth annual ACM symposium on Theory of Computing 2013, pp. 515-524.   DOI:10.1145/2488608.2488673
  14. SageMath: Free open-source mathematics software system licensed under the GPL. Sagemath 2005.   CrossRef
  15. O. Suil, R. P. Jeong, P. Jongyook and Z. Wenqian: Sharp spectral bounds for the edge-connectivity of regular graphs. Europ. J. Combinatorics 110 (2023).   DOI:10.1016/j.ejc.2023.103713
  16. T. Tantau: 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).   CrossRef
  17. V. G. Vizing: On an estimate of the chromatic class of a p-graph. Diskret. Analiz. 3 (1964), 25-30.   DOI:10.1515/crll.1964.216.25
  18. H. Zhen-Mu, L. Hong-Jian and X. Zheng-Jiang: Connectivity and eigenvalues of graphs with given girth or clique number. Linear Algebra Appl. 607 (2020), 319-340.   DOI:10.1016/j.laa.2020.08.015