Document Open Access Logo

Counting and Sampling from Substructures Using Linear Algebraic Queries

Authors Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.8.pdf
  • Filesize: 0.84 MB
  • 20 pages

Document Identifiers

Author Details

Arijit Bishnu
  • Indian Statistical Institute, Kolkata, India
Arijit Ghosh
  • Indian Statistical Institute, Kolkata, India
Gopinath Mishra
  • University of Warwick, Coventry, UK
Manaswi Paraashar
  • Aarhus University, Denmark

Cite As Get BibTex

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar. Counting and Sampling from Substructures Using Linear Algebraic Queries. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.8

Abstract

For an unknown n Γ— n matrix A having non-negative entries, the inner product (IP) oracle takes as inputs a specified row (or a column) of A and a vector 𝐯 ∈ ℝⁿ with non-negative entries, and returns their inner product. Given two input vectors x and y in ℝⁿ with non-negative entries, and an unknown matrix A with non-negative entries with IP oracle access, we design almost optimal sublinear time algorithms for the following two fundamental matrix problems:  
- Find an estimate 𝒳 for the bilinear form x^T A y such that 𝒳 β‰ˆ x^T A y.
- Designing a sampler 𝒡 for the entries of the matrix A such that β„™(𝒡 = (i,j)) β‰ˆ x_i A_{ij} y_j /(x^T A y), where x_i and y_j are i-th and j-th coordinate of 𝐱 and 𝐲 respectively.  As special cases of the above results, for any submatrix of an unknown matrix with non-negative entries and IP oracle access, we can efficiently estimate the sum of the entries of any submatrix, and also sample a random entry from the submatrix with probability proportional to its weight. We will show that the above results imply that if we are given IP oracle access to the adjacency matrix of a graph, with non-negative weights on the edges, then we can design sublinear time algorithms for the following two fundamental graph problems:  
- Estimating the sum of the weights of the edges of an induced subgraph, and
- Sampling edges proportional to their weights from an induced subgraph.  We show that compared to the classical local queries (degree, adjacency, and neighbor queries) on graphs, we can get a quadratic speedup if we use IP oracle access for the above two problems.
Apart from the above, we study several matrix problems through the lens of IP oracle, like testing if the matrix is diagonal, symmetric, doubly stochastic, etc. Note that IP oracle is in the class of linear algebraic queries used lately in a series of works by Ben-Eliezer et al. [SODA'08], Nisan [SODA'21], Rashtchian et al. [RANDOM'20], Sun et al. [ICALP'19], and Shi and Woodruff [AAAI'19]. Recently, IP oracle was used by Bishnu et al. [RANDOM'21] to estimate dissimilarities between two matrices.

Subject Classification

ACM Subject Classification
  • Mathematics of computing β†’ Probabilistic algorithms
Keywords
  • Query complexity
  • Bilinear form
  • Uniform sampling
  • Weighted graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Intel C++ Compiler Classic Developer Guide and Reference: Floating Point Dot Product Intrinsics. URL: https://software.intel.com/content/www/us/en/develop/documentation/cpp-compiler-developer-guide-and-reference/top/compiler-reference/intrinsics/intrinsics-for-intel-streaming-simd-extensions-4-intel-sse4/vectorizing-compiler-and-media-accelerators/floating-point-dot-product-intrinsics.html.
  2. NVIDIA Developer: Cg 3.1 Toolkit Documentation. URL: https://developer.download.nvidia.com/cg/dot.html.
  3. K. J. Ahn, S. Guha, and A. McGregor. Analyzing Graph Structure via Linear Measurements. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 459-467, 2012. Google Scholar
  4. M. Aliakbarpour, A. S. Biswas, T. Gouleakis, J. Peebles, R. Rubinfeld, and A. Yodpinyanee. Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling. Algorithmica, 80(2):668-697, 2018. Google Scholar
  5. S. Assadi, D. Chakrabarty, and S. Khanna. Graph connectivity and single element recovery via linear and OR queries. In European Symposium on Algorithms, ESA, volume 204, pages 7:1-7:19, 2021. Google Scholar
  6. S. Assadi, M. Kapralov, and S. Khanna. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In Innovations in Theoretical Computer Science Conference, ITCS, pages 6:1-6:20, 2019. Google Scholar
  7. M.-F. Balcan, Y. Li, D. P. Woodruff, and H. Zhang. Testing Matrix Rank, Optimally. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 727-746, 2019. Google Scholar
  8. P. Beame, S. Har-Peled, S. N. Ramamoorthy, C. Rashtchian, and M. Sinha. Edge Estimation with Independent Set Oracles. In Innovations in Theoretical Computer Science Conference, ITCS, pages 38:1-38:21, 2018. Google Scholar
  9. I. Ben-Eliezer, T. Kaufman, M. Krivelevich, and D. Ron. Comparing the strength of query types in property testing: the case of testing k-colorability. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1213-1222, 2008. Google Scholar
  10. M. Benzi and C. Klymko. Total Communicability as a Centrality Measure. Journal of Complex Networks, 1:124-149, 2013. Google Scholar
  11. A. Bishnu, A. Ghosh, S. Kolay, G. Mishra, and S. Saurabh. Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers. In International Symposium on Algorithms and Computation, ISAAC, pages 25:1-25:12, 2018. Google Scholar
  12. A. Bishnu, A. Ghosh, and G. Mishra. Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 207, pages 44:1-44:22, 2021. Google Scholar
  13. A. Bishnu, A. Ghosh, G. Mishra, and M. Paraashar. Efficiently sampling and estimating from substructures using linear algebraic queries. CoRR, abs/1906.07398, 2019. Version 2. URL: http://arxiv.org/abs/1906.07398v2.
  14. F. Bonchi, P. Esfandiar, D. F. Gleich, C. Greif, and L. V.S. Lakshmanan. Fast Matrix Computations for Pairwise and Columnwise Commute Times and Katz Scores. Internet Mathematics, 1-2(8):73-112, 2012. Google Scholar
  15. D. Chakraborty, L. Kamma, and K. G. Larsen. Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication. In ACM SIGACT Symposium on Theory of Computing, STOC, pages 1297-1306, 2018. Google Scholar
  16. A. Chattopadhyay, M. KouckΓ½, B. Loff, and S. Mukhopadhyay. Simulation Beats Richness: New Data-Structure Lower Bounds. In ACM SIGACT Symposium on Theory of Computing, STOC, pages 1013-1020, 2018. Google Scholar
  17. H. Dell, J. Lapinskas, and K. Meeks. Approximately Counting and Sampling Small Witnesses using a Colourful Decision Oracle. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2201-2211, 2020. Google Scholar
  18. D. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 1st edition, 2009. Google Scholar
  19. T. Eden, A. Levi, D. Ron, and C. Seshadhri. Approximately Counting Triangles in Sublinear Time. SIAM Journal on Computing, 46(5):1603-1646, 2017. Google Scholar
  20. T. Eden, D. Ron, and C. Seshadhri. On Approximating the Number of k-Cliques in Sublinear Time. In ACM SIGACT Symposium on Theory of Computing, STOC, pages 722-734, 2018. Google Scholar
  21. T. Eden and W. Rosenbaum. On Sampling Edges Almost Uniformly. In Symposium on Simplicity in Algorithms, SOSA, pages 7:1-7:9, 2018. Google Scholar
  22. E. Estrada and D. J. Higham. Network Properties Revealed through Matrix Functions. SIAM Review, 52:696-714, 2010. Google Scholar
  23. U. Feige. On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph. SIAM Journal on Computing, 35(4):964-984, 2006. Google Scholar
  24. O. Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  25. O. Goldreich and D. Ron. Approximating Average Parameters of Graphs. Random Structures & Algorithms, 32(4):473-493, 2008. Google Scholar
  26. J. L. Hennessy and D. A. Patterson. Computer Architecture - A Quantitative Approach (5. ed.). Morgan Kaufmann, 2012. Google Scholar
  27. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  28. K. G. Larsen and R. R. Williams. Faster Online Matrix-Vector Multiplication. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2182-2189, 2017. Google Scholar
  29. N. Nisan. The demand query model for bipartite matching. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 592-599, 2021. Google Scholar
  30. S. N. Ramamoorthy and C. Rashtchian. Equivalence of Systematic Linear Data Structures and Matrix Rigidity. In Innovations in Theoretical Computer Science Conference, ITCS, volume 151, pages 35:1-35:20, 2020. Google Scholar
  31. A. Rao and A. Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. Google Scholar
  32. C. Rashtchian, D. P. Woodruff, and H. Zhu. Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 176, pages 26:1-26:20, 2020. Google Scholar
  33. D. Ron and G. Tsur. The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling. ACM Trans. Comput. Theory, 8(4):15:1-15:19, 2016. Google Scholar
  34. A. Rubinstein, T. Schramm, and S. M. Weinberg. Computing Exact Minimum Cuts Without Knowing the Graph. In Innovations in Theoretical Computer Science Conference, ITCS, pages 39:1-39:16, 2018. Google Scholar
  35. J. Sanders and E. Kandrot. CUDA by Example: An Introduction to General-Purpose GPU Programming. Addison-Wesley, Upper Saddle River, NJ, 2010. Google Scholar
  36. X. Shi and D. P. Woodruff. Sublinear Time Numerical Linear Algebra for Structured Matrices. In AAAI Conference on Artificial Intelligence, AAAI, pages 727-746, 2019. Google Scholar
  37. L. J. Stockmeyer. The Complexity of Approximate Counting (Preliminary Version). In ACM SIGACT Symposium on Theory of Computing, STOC, pages 118-126, 1983. Google Scholar
  38. L. J. Stockmeyer. On Approximation Algorithms for #P. SIAM Journal on Computing, 14(4):849-861, 1985. Google Scholar
  39. X. Sun, D. P. Woodruff, G. Yang, and J. Zhang. Querying a Matrix Through Matrix-Vector Products. In International Colloquium on Automata, Languages, and Programming, ICALP, pages 94:1-94:16, 2019. Google Scholar
  40. X. Sun, D. P. Woodruff, G. Yang, and J. Zhang. Querying a Matrix Through Matrix-Vector Products. In International Colloquium on Automata, Languages, and Programming, ICALP, volume 132, pages 94:1-94:16, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact