Counting and Sampling from Substructures Using Linear Algebraic Queries

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi ParaasharFSTTCS 2022 · OpenReview

TL;DR

This paper introduces the Inner Product (IP) oracle as a powerful tool for efficiently analyzing unknown matrices. It presents sublinear-time algorithms for estimating bilinear forms and sampling matrix entries, which translate to significant speedups for graph problems like estimating subgraph edge weights and sampling edges.

What Problem Does This Paper Address?

The paper tackles the challenge of understanding large, unknown matrices and their substructures when direct access to all entries is infeasible. Specifically, it focuses on two fundamental problems:

  1. Bilinear Form Estimation (BFE): Estimating the value of $x^T A y$, where $A$ is an unknown $n \times n$ matrix, and $x$ and $y$ are known vectors. This is a generalization of many matrix analysis tasks.
  2. Almost Uniform Sampling (AUS): Designing a method to sample entries $(i, j)$ of matrix $A$ with a probability proportional to $x_i A_{ij} y_j / (x^T A y)$.

These matrix problems have direct implications for graph analysis, particularly for induced subgraphs. For instance, estimating the sum of edge weights in an induced subgraph or sampling edges proportionally to their weights are crucial graph problems. The authors aim to provide efficient, sublinear-time solutions to these problems, offering a significant improvement over traditional query models.

Methods

The core of the paper's contribution lies in leveraging the Inner Product (IP) oracle. This oracle, given a row (or column) of matrix $A$ and a vector $v$, returns their inner product $(A_i, v)$. The authors demonstrate that this oracle, despite being seemingly simple, is surprisingly powerful.

Key methodological aspects include:

  • Sublinear Time Algorithms: The algorithms are designed to run in time significantly less than the size of the matrix ($n^2$), often depending on parameters like the number of non-zero entries in the input vectors and the desired approximation factor $\epsilon$.
  • Reduction to IP Oracle: The paper shows how graph problems, such as estimating edge counts in induced subgraphs, can be elegantly reduced to matrix problems solvable with the IP oracle.
  • Quadratic Speedup: For graph problems like edge estimation and sampling in induced subgraphs, the IP oracle provides a quadratic speedup compared to traditional "local" graph queries (degree, adjacency, neighbor).
  • Specialized Algorithms: The paper develops specific algorithms for BFE and AUS, often inspired by existing work but extended to the IP oracle model. These algorithms involve techniques like random sampling, partitioning, and probabilistic reasoning (e.g., using Chernoff bounds).

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and their query complexity for unknown matrices and graphs, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Power of the IP Oracle: The most significant insight is that the humble Inner Product oracle is a remarkably powerful primitive for matrix and graph analysis, enabling efficient solutions to problems that are hard with other query models.
  • Sublinear Analysis of Substructures: The paper demonstrates that it's possible to gain deep insights into substructures (like submatrices or induced subgraphs) of large, unknown matrices/graphs without examining all their elements.
  • Quadratic Separation: The IP oracle offers a substantial advantage (quadratic speedup) over classical local graph queries for tasks related to induced subgraphs, highlighting its superior expressive power for these specific problems.
  • Generalization of Existing Work: The IP oracle framework allows for a unified approach to problems previously studied with different query models, extending known results and providing new insights.

Key Results

  • Bilinear Form Estimation (BFE) and Almost Uniform Sampling (AUS): The paper provides sublinear-time algorithms for these fundamental matrix problems using IP queries. The query complexity for BFE and AUS is shown to be $\tilde{O}(\sqrt{p \cdot \text{nnz}(x) \cdot \text{nnz}(y) / (x^T A y)})$, where $p$ is related to the maximum entry value and $\text{nnz}$ denotes the number of non-zero entries.
  • Submatrix Analysis: As a consequence, efficient algorithms are presented for estimating the sum of entries in any submatrix and sampling an entry from a submatrix proportionally to its weight.
  • Graph Problems: For graphs with non-negative edge weights, algorithms are developed to estimate the sum of weights of edges in an induced subgraph and to sample edges proportionally to their weights. These algorithms achieve a quadratic speedup compared to using only local graph queries.
  • Comparison with Other Oracles: Table 1 in the paper quantifies the query complexities of IP queries versus matrix-vector (MV) and vector-matrix-vector (VMV) queries for various matrix problems, showing IP queries to be a powerful intermediate option.

Limitations and Future Work

  • Positive Entries Assumption: The current techniques primarily work for matrices with non-negative entries. The authors acknowledge that their methods do not directly extend to matrices with both positive and negative entries.
  • Open Questions: The paper poses several open questions:
  • Can BILINEAR FORM ESTIMATION and SAMPLING be solved with fewer queries for specific types of matrices?
  • Can other linear algebraic problems be solved efficiently using IP queries?
  • Are there other graph problems where INDUCED DEGREE queries outperform LOCAL queries?
  • Data Structure Complexity: The paper raises the question of finding efficient pre-processing schemes for matrices such that IP queries can be answered quickly.

Summary updated

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.
BibTeX
@inproceedings{bishnu2022counting,
  author = {Arijit Bishnu and Arijit Ghosh and Gopinath Mishra and Manaswi Paraashar},
  title = {{Counting and Sampling from Substructures Using Linear Algebraic Queries}},
  booktitle = {FSTTCS},
  year = {2022},
  url = {https://openreview.net/forum?id=9ATkiCGq8w},
}
Figure