Abstract
In this work, we study a variant of nonnegative matrix factorization where we wish to find a symmetric factorization of a given input matrix into a sparse, Boolean matrix. Formally speaking, given {đ} â {â¤}^{mÃ m}, we want to find {đ} â {0,1}^{mÃ r} such that â {đ}  {đ} {đ}^â¤ ââ is minimized among all {đ} for which each row is ksparse. This question turns out to be closely related to a number of questions like recovering a hypergraph from its line graph, as well as reconstruction attacks for private neural network training.
As this problem is hard in the worstcase, we study a natural averagecase variant that arises in the context of these reconstruction attacks: {đ} = {đ} {đ}^{â¤} for {đ} a random Boolean matrix with ksparse rows, and the goal is to recover {đ} up to column permutation. Equivalently, this can be thought of as recovering a uniformly random kuniform hypergraph from its line graph.
Our main result is a polynomialtime algorithm for this problem based on bootstrapping higherorder information about {đ} and then decomposing an appropriate tensor. The key ingredient in our analysis, which may be of independent interest, is to show that such a matrix {đ} has full column rank with high probability as soon as m = ÎŠĖ(r), which we do using tools from LittlewoodOfford theory and estimates for binary Krawtchouk polynomials.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs.ITCS.2022.46,
author = {Chen, Sitan and Song, Zhao and Tao, Runzhou and Zhang, Ruizhe},
title = {{Symmetric Sparse Boolean Matrix Factorization and Applications}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {46:146:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15642},
URN = {urn:nbn:de:0030drops156422},
doi = {10.4230/LIPIcs.ITCS.2022.46},
annote = {Keywords: Matrix factorization, tensors, random matrices, averagecase complexity}
}
Keywords: 

Matrix factorization, tensors, random matrices, averagecase complexity 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 