| G. Drakopoulos, Ph. Mylonas |
| A Genetic Algorithm For Boolean Semiring Matrix Factorization With Applications To Graph Mining |
| IEEE International Conference on Big Data (IEEE BigData 2022) December 17-20, 2022, Osaka, Japan |
|
ABSTRACT
|
| Matrix factorization is paramount in large scale graph mining as well as a versatile paradigm for dimensionality reduction. In particular, factoring a graph adjacency matrix may well reveal, depending on the specific factor properties, higher order structure. The latter describes global graph properties better compared to first order connectivity patterns such as vertex degrees. The Boolean semiring factorization of an adjacency matrix yields a product of two smaller and sparser matrices where the former contains disjoint fundamental vertex subsets and the latter combinations thereof. Therefore, the first factor represents community structure and the second has the cross connections between them. In this way graph partitioning and dimensionality reduction are simultaneously achieved. Because of the nature of the Boolean semiring, most common linear algebraic solvers cannot be applied. Moreover, the exact factorization is NP hard. To address these limitations, a genetic algorithm has been developed with evolutionary operations tailored to heuristically compute said factorization which offers interpretability and a high parallelism potential. Besides graph mining the major applications of the Boolean semiring factorization include role mining in enterprise database and operating system realms, curriculum design, and graph flows under inflexible uniqueness constraints.The results obtained by applying the proposed genetic algorithm to synthetic graph benchmarks are very encouraging.
|
| 17 December , 2022 |
| G. Drakopoulos, Ph. Mylonas, "A Genetic Algorithm For Boolean Semiring Matrix Factorization With Applications To Graph Mining", IEEE International Conference on Big Data (IEEE BigData 2022) December 17-20, 2022, Osaka, Japan |
[  PDF] [
BibTex] [
Print] [
 Back] |
