On Finding All Connected Maximum-Sized Common Subgraphs in Multiple Labeled Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912305835409408 |
|---|---|
| author | Petersen, Johannes B. S. Davoodi, Akbar Gärtner, Thomas Hellmuth, Marc Merkle, Daniel |
| author_facet | Petersen, Johannes B. S. Davoodi, Akbar Gärtner, Thomas Hellmuth, Marc Merkle, Daniel |
| contents | We present an exact algorithm for computing all common subgraphs with the maximum number of vertices across multiple graphs. Our approach is further extended to handle the connected Maximum Common Subgraph (MCS), identifying the largest common subgraph in terms of either vertices or edges across multiple graphs, where edges or vertices may additionally be labeled to account for possible atom types or bond types, a classical labeling used in molecular graphs. Our approach leverages modular product graphs and a modified Bron-Kerbosch algorithm to enumerate maximal cliques, ensuring all intermediate solutions are retained. A pruning heuristic efficiently reduces the modular product size, improving computational feasibility. Additionally, we introduce a graph ordering strategy based on graph-kernel similarity measures to optimize the search process. Our method is particularly relevant for bioinformatics and cheminformatics, where identifying conserved structural motifs in molecular graphs is crucial. Empirical results on molecular datasets demonstrate that our approach is scalable and fast. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_22368 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Finding All Connected Maximum-Sized Common Subgraphs in Multiple Labeled Graphs Petersen, Johannes B. S. Davoodi, Akbar Gärtner, Thomas Hellmuth, Marc Merkle, Daniel Data Structures and Algorithms Discrete Mathematics Combinatorics Molecular Networks We present an exact algorithm for computing all common subgraphs with the maximum number of vertices across multiple graphs. Our approach is further extended to handle the connected Maximum Common Subgraph (MCS), identifying the largest common subgraph in terms of either vertices or edges across multiple graphs, where edges or vertices may additionally be labeled to account for possible atom types or bond types, a classical labeling used in molecular graphs. Our approach leverages modular product graphs and a modified Bron-Kerbosch algorithm to enumerate maximal cliques, ensuring all intermediate solutions are retained. A pruning heuristic efficiently reduces the modular product size, improving computational feasibility. Additionally, we introduce a graph ordering strategy based on graph-kernel similarity measures to optimize the search process. Our method is particularly relevant for bioinformatics and cheminformatics, where identifying conserved structural motifs in molecular graphs is crucial. Empirical results on molecular datasets demonstrate that our approach is scalable and fast. |
| title | On Finding All Connected Maximum-Sized Common Subgraphs in Multiple Labeled Graphs |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics Molecular Networks |
| url | https://arxiv.org/abs/2503.22368 |