| Title:
|
Interpretable random forest model for identification of edge 3-uncolorable cubic graphs (English) |
| Author:
|
Dudáš, Adam |
| Author:
|
Modrovičová, Bianka |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
59 |
| Issue:
|
6 |
| Year:
|
2023 |
| Pages:
|
807-826 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
random forest |
| Keyword:
|
proper edge coloring |
| Keyword:
|
interpretable machine learning |
| Keyword:
|
snark |
| MSC:
|
68T10 |
| MSC:
|
68T20 |
| idZBL:
|
Zbl 07830566 |
| DOI:
|
10.14736/kyb-2023-6-0807 |
| . |
| Date available:
|
2024-02-26T11:05:58Z |
| Last updated:
|
2024-08-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/152259 |
| . |
| Reference:
|
[1] Bon-Gang, H.: Performance and Improvements of Green Construction Projects..Elsevier 2018. |
| Reference:
|
[2] Caro, Y., Petrusevski, M., Skrekovski, R.: Remarks on proper conflict-free colorings of graphs..Discrete Math. 346 (2023), 2, 113221. MR 4499342, |
| Reference:
|
[3] Chaitin, G. J.: Register allocation & spilling via graph colouring..In: Proc. 1982 SIGPLAN Symposium on Compiler Construction 1982, pp. 98-105. |
| Reference:
|
[4] Coolsaet, K., D'hondt, S., Goedgebeur, J.: House of Graphs 2.0: A database of interesting graphs and more..Discrete Appl. Math. 325 (2023), 97-107. MR 4506063, |
| Reference:
|
[5] Custode, L. L., Iacca, G.: Evolutionary learning of interpretable decision trees..IEEE Access 11 (2023), 6169-6184. |
| Reference:
|
[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. |
| Reference:
|
[7] GraphFilter: Software to help Graph researches providing filtering and visualization to a given list of graphs..Graphfilter 2021. |
| Reference:
|
[8] Kowalik, L.: Improved edge-coloring with three colors..Theoret. Computer Sci. 410 (2009), 38-40, 3733-3742. MR 2553326, |
| Reference:
|
[9] Marx, D.: Graph colouring problems and their applications in scheduling..Periodica Polytechn., Electr. Engrg. 48 (2004), 1-2, 11-16. |
| Reference:
|
[10] Molnar, C.: Interpretable Machine Learning..Published independently, 2019. |
| Reference:
|
[11] Nettleton, D.: Commercial Data Mining..Elsevier 2014. |
| Reference:
|
[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. |
| Reference:
|
[13] Roditty, L., Williams, V. V.: 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. MR 3210813, |
| Reference:
|
[14] SageMath: Free open-source mathematics software system licensed under the GPL..Sagemath 2005. |
| Reference:
|
[15] Suil, O., Jeong, R. P., Jongyook, P., Wenqian, Z.: Sharp spectral bounds for the edge-connectivity of regular graphs..Europ. J. Combinatorics 110 (2023). MR 4564485, |
| Reference:
|
[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). |
| Reference:
|
[17] Vizing, V. G.: On an estimate of the chromatic class of a p-graph..Diskret. Analiz. 3 (1964), 25-30. MR 0180505, |
| Reference:
|
[18] Zhen-Mu, H., Hong-Jian, L., Zheng-Jiang, X.: Connectivity and eigenvalues of graphs with given girth or clique number..Linear Algebra Appl. 607 (2020), 319-340. MR 4139132, |
| . |
