Geometric Deep Learning sub-network extraction for Maximum Clique Enumeration.
The paper presents an algorithm to approach the problem of Maximum Clique Enumeration, a well known NP-hard problem that have several real world applications. The proposed solution, called LGP-MCE, exploits Geometric Deep Learning, a Machine Learning technique on graphs, to filter out nodes that do...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2024-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0296185&type=printable |
| _version_ | 1827378756167139328 |
|---|---|
| author | Vincenza Carchiolo Marco Grassia Michele Malgeri Giuseppe Mangioni |
| author_facet | Vincenza Carchiolo Marco Grassia Michele Malgeri Giuseppe Mangioni |
| author_sort | Vincenza Carchiolo |
| collection | DOAJ |
| description | The paper presents an algorithm to approach the problem of Maximum Clique Enumeration, a well known NP-hard problem that have several real world applications. The proposed solution, called LGP-MCE, exploits Geometric Deep Learning, a Machine Learning technique on graphs, to filter out nodes that do not belong to maximum cliques and then applies an exact algorithm to the pruned network. To assess the LGP-MCE, we conducted multiple experiments using a substantial dataset of real-world networks, varying in size, density, and other characteristics. We show that LGP-MCE is able to drastically reduce the running time, while retaining all the maximum cliques. |
| first_indexed | 2024-03-08T13:01:27Z |
| format | Article |
| id | doaj.art-aac9e4df42b54b74a98f78d6cb3d3589 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-03-08T13:01:27Z |
| publishDate | 2024-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-aac9e4df42b54b74a98f78d6cb3d35892024-01-19T05:46:08ZengPublic Library of Science (PLoS)PLoS ONE1932-62032024-01-01191e029618510.1371/journal.pone.0296185Geometric Deep Learning sub-network extraction for Maximum Clique Enumeration.Vincenza CarchioloMarco GrassiaMichele MalgeriGiuseppe MangioniThe paper presents an algorithm to approach the problem of Maximum Clique Enumeration, a well known NP-hard problem that have several real world applications. The proposed solution, called LGP-MCE, exploits Geometric Deep Learning, a Machine Learning technique on graphs, to filter out nodes that do not belong to maximum cliques and then applies an exact algorithm to the pruned network. To assess the LGP-MCE, we conducted multiple experiments using a substantial dataset of real-world networks, varying in size, density, and other characteristics. We show that LGP-MCE is able to drastically reduce the running time, while retaining all the maximum cliques.https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0296185&type=printable |
| spellingShingle | Vincenza Carchiolo Marco Grassia Michele Malgeri Giuseppe Mangioni Geometric Deep Learning sub-network extraction for Maximum Clique Enumeration. PLoS ONE |
| title | Geometric Deep Learning sub-network extraction for Maximum Clique Enumeration. |
| title_full | Geometric Deep Learning sub-network extraction for Maximum Clique Enumeration. |
| title_fullStr | Geometric Deep Learning sub-network extraction for Maximum Clique Enumeration. |
| title_full_unstemmed | Geometric Deep Learning sub-network extraction for Maximum Clique Enumeration. |
| title_short | Geometric Deep Learning sub-network extraction for Maximum Clique Enumeration. |
| title_sort | geometric deep learning sub network extraction for maximum clique enumeration |
| url | https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0296185&type=printable |
| work_keys_str_mv | AT vincenzacarchiolo geometricdeeplearningsubnetworkextractionformaximumcliqueenumeration AT marcograssia geometricdeeplearningsubnetworkextractionformaximumcliqueenumeration AT michelemalgeri geometricdeeplearningsubnetworkextractionformaximumcliqueenumeration AT giuseppemangioni geometricdeeplearningsubnetworkextractionformaximumcliqueenumeration |