Let @math be a polynomial with at most @math non-zero real coefficients. We give an algorithm for exactly reconstructing f given random examples from the uniform distribution on @math that runs in time polynomial in @math and @math and succeeds if the function satisfies the unique sign property: there is one output value which corresponds to a unique set of values of the participating parities. This sufficient condition is satisfied when every coefficient of f is perturbed by a small random noise, or satisfied with high probability when s parity functions are chosen randomly or when all the coefficients are positive. Learning sparse polynomials over the Boolean domain in time polynomial in @math and @math is considered notoriously hard in the worst-case. Our result shows that the problem is tractable for almost all sparse polynomials. Then, we show an application of this result to hypergraph sketching which is the problem of learning a sparse (both in the number of hyperedges and the size of the hyperedges) hypergraph from uniformly drawn random cuts. We also provide experimental results on a real world dataset.
@cite_6: Can we learn a sparse graph from observing the value of a few random cuts? This and more general problems can be reduced to the challenge of learning set functions known to have sparse Fourier support contained in some collectionP. We prove that if we choose O(k log 4 |P|) sets uniformly at random, then with high probability, observing any k-sparse function on those sets is sucient to recover that function exactly. We further show that other properties, such as symmetry or submodularity imply structure in the Fourier spectrum, which can be exploited to further reduce sample complexity. One interesting special case is that it suces to observe O(|E| log 4 (|V|)) values of a cut function to recover a graph. We demonstrate the eectiveness of our results on two realworld reconstruction problems: graph sketching and obtaining fast approximate surrogates to expensive submodular objective functions.
On the practical side, we give an application of the theory to the problem of hypergraph sketching. We generalize a prior work @cite_6 that applied the compressed sensing approach discussed before to graph sketching on evolving social network graphs. In our algorithm, while the sample complexity requirements are higher, the time complexity is greatly reduced in comparison. We test our algorithms on a real dataset and show that the algorithm is able to scale well on sparse hypergraphs created out of Yahoo! messenger dataset by filtering through time and location stamps.