Color-coding algorithms

[szarnyasg]

Hi @benedekrozemberczki, this is an interesting collection, thanks!

I work as a researcher mostly in the intersection of semantic technologies, database systems, and high-performance computing so I might be able to add some papers. But first, I am not 100% sure about what the exact definition of "tree search" is here (and I guess, there is a number of possible definitions). However, I have recently stumbled upon "color-coding algorithms" use repeated relabeling operations to count/enumerate isomorphic matches of subtrees. Some papers that could be relevant are as follows:

• ISMB'08: Alon et al.'s "Biomolecular network motif counting and discovery by color coding", one of the seminal papers
• TMSCS'18: color coding in MapReduce: "In this paper, we present SAHAD, a MapReduce algorithm for detecting and counting trees of bounded size using the elegant color coding technique developed by N. Alon et al. SAHAD is a randomized algorithm, and we show rigorous bounds on the approximation quality and the performance of it."
• preprint'19: arbitrary subgraph matching using the GraphBLAS* standard which defines linear algebraic operations for graph algorithms. These states in the introduction that "Alon et al. [2, 3] provide a practical algorithm to count trees and graphs of bounded treewidth (size less than 10) from PPINs of unicellular and multicellular organisms by using the color-coding technique developed in [4]"

Let me know if this seems relevant to how the "tree search" problem is defined in the ML/DM communities (and in this repository).

*Regarding GraphBLAS, I happen to have my own awesome-style collection of resources, including papers, presentations, implementations, etc.

[benedekrozemberczki]

Dear @szarnyasg,

I am primarily focusing on Monte Carlo tree search and applications of it in ML. I will add other tree search techniques which are used in ML.

Regarding GrapBLAS, I am planning to write a library which covers widely used graph factorization (network embedding techniques). Is it something that handles spare linear algebra well?

Benedek

[szarnyasg]

Hi,

Is it something that handles spare linear algebra well?

Yes, it is designed to do matrix-matrix/matrix-vector multiplications on sparse matrices defined over arbitrary. However, there are no sparse solvers included to perform something like Cholesky decomposition. For that, SuiteSparse is your best bet which also has a GraphBLAS implementation, SuiteSparse:GraphBLAS but I am not sure how interoperable vanilla SuiteSparse and SuiteSparse:GraphBLAS are.