Geodesic
Interpretable random forest model for identification of edge 3-uncolorable cubic graphs
Kybernetika, Tome 59 (2023) no. 6, pp. 807-826
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2023-6-0807
Classification : 68T10, 68T20
Keywords: random forest; proper edge coloring; interpretable machine learning; snark 
@article{10_14736_kyb_2023_6_0807,
     author = {Dud\'a\v{s}, Adam and Modrovi\v{c}ov\'a, Bianka},
     title = {Interpretable random forest model for identification of edge 3-uncolorable cubic graphs},
     journal = {Kybernetika},
     pages = {807--826},
     year = {2023},
     volume = {59},
     number = {6},
     doi = {10.14736/kyb-2023-6-0807},
     zbl = {07830566},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-6-0807/}
}
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
SP  - 807
EP  - 826
VL  - 59
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-6-0807/
DO  - 10.14736/kyb-2023-6-0807
LA  - en
ID  - 10_14736_kyb_2023_6_0807
ER  - 
%0 Journal Article
%A Dudáš, Adam
%A Modrovičová, Bianka
%T Interpretable random forest model for identification of edge 3-uncolorable cubic graphs
%J Kybernetika
%D 2023
%P 807-826
%V 59
%N 6
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-6-0807/
%R 10.14736/kyb-2023-6-0807
%G en
%F 10_14736_kyb_2023_6_0807
Dudáš, Adam; Modrovičová, Bianka. Interpretable random forest model for identification of edge 3-uncolorable cubic graphs. Kybernetika, Tome 59 (2023) no. 6, pp. 807-826. doi: 10.14736/kyb-2023-6-0807

[1] Bon-Gang, H.: Performance and Improvements of Green Construction Projects. Elsevier 2018.

[2] Caro, Y., Petrusevski, M., Skrekovski, R.: Remarks on proper conflict-free colorings of graphs. Discrete Math. 346 (2023), 2, 113221. | DOI | MR

[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.: House of Graphs 2.0: A database of interesting graphs and more. Discrete Appl. Math. 325 (2023), 97-107. | DOI | MR

[5] Custode, L. L., Iacca, G.: Evolutionary learning of interpretable decision trees. 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.: Improved edge-coloring with three colors. Theoret. Computer Sci. 410 (2009), 38-40, 3733-3742. | DOI | MR

[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.: 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 | MR

[14] SageMath: Free open-source mathematics software system licensed under the GPL. Sagemath 2005.

[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). | DOI | MR

[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.: On an estimate of the chromatic class of a p-graph. Diskret. Analiz. 3 (1964), 25-30. | DOI | MR

[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. | DOI | MR

Cité par Sources :