An official website of the United States government
We consider algorithms with access to an unknown matrix M ε F n×d via matrix-vector products , namely, the algorithm chooses vectors v 1 , ⃛ , v q , and observes Mv 1 , ⃛ , Mv q . Here the v i can be randomized as well as chosen adaptively as a function of Mv 1 , ⃛ , Mv i-1 . Motivated by applications of sketching in distributed computation, linear algebra, and streaming models, as well as connections to areas such as communication complexity and property testing, we initiate the study of the number q of queries needed to solve various fundamental problems. We study problems in three broad categories, including linear algebra, statistics problems, and graph problems. For example, we consider the number of queries required to approximate the rank, trace, maximum eigenvalue, and norms of a matrix M; to compute the AND/OR/Parity of each column or row of M, to decide whether there are identical columns or rows in M or whether M is symmetric, diagonal, or unitary; or to compute whether a graph defined by M is connected or triangle-free. We also show separations for algorithms that are allowed to obtain matrix-vector products only by querying vectors on the right, versus algorithms that can query vectors on both the left and the right. We also show separations depending on the underlying field the matrix-vector product occurs in. For graph problems, we show separations depending on the form of the matrix (bipartite adjacency versus signed edge-vertex incidence matrix) to represent the graph. Surprisingly, very few works discuss this fundamental model, and we believe a thorough investigation of problems in this model would be beneficial to a number of different application areas.
more »
« less
Mathematical foundations of the GraphBLAS
The GraphBLAS standard (GraphBlas.org) is being developed to bring the potential of matrix-based graph algorithms to the broadest possible audience. Mathematically, the GraphBLAS defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the mathematics of the GraphBLAS. Graphs represent connections between vertices with edges. Matrices can represent a wide range of graphs using adjacency matrices or incidence matrices. Adjacency matrices are often easier to analyze while incidence matrices are often better for representing data. Fortunately, the two are easily connected by matrix multiplication. A key feature of matrix mathematics is that a very small number of matrix operations can be used to manipulate a very wide range of graphs. This composability of a small number of operations is the foundation of the GraphBLAS. A standard such as the GraphBLAS can only be effective if it has low performance overhead. Performance measurements of prototype GraphBLAS implementations indicate that the overhead is low.
more »
« less
- PAR ID:
- 10037304
- Date Published:
- Journal Name:
- Proceedings of the IEEE High Performance Extreme Computing Conference
- Page Range / eLocation ID:
- 1 to 9
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We develop algorithms for online topology inference from streaming nodal observations and partial connectivity information; i.e., a priori knowledge on the presence or absence of a few edges may be available as in the link prediction problem. The observations are modeled as stationary graph signals generated by local diffusion dynamics on the unknown network. Said stationarity assumption implies the simultaneous diagonalization of the observations' covariance matrix and the so-called graph shift operator (GSO), here the adjacency matrix of the sought graph. When the GSO eigenvectors are perfectly obtained from the ensemble covariance, we examine the structure of the feasible set of adjacency matrices and its dependency on the prior connectivity information available. In practice one can only form an empirical estimate of the covariance matrix, so we develop an alternating algorithm to find a sparse GSO given its imperfectly estimated eigenvectors. Upon sensing new diffused observations in the streaming setting, we efficiently update eigenvectors and perform only one (or a few) online iteration(s) of the proposed algorithm until a new datum is observed. Numerical tests showcase the effectiveness of the novel batch and online algorithms in recovering real-world graphs.more » « less
-
The graph distinguishability problem investigates whether a graph can be uniquely identified by the spectrum of its adjacency matrix, specifically determining if two graphs with the same spectrum are isomorphic. This issue is central to spectral graph theory and has significant implications for graph machine learning. In this paper, we explore the intricate connections between graph distinguishability and graph controllability–an essential concept in the control of networked systems. Focusing on oriented graphs and their skew-adjacency matrices, we establish controllability-based conditions that ensure their distinguishability. Notably, our conditions are less restrictive than existing methods, enabling a broader class of graphs to satisfy the distinguishability criteria. We illustrate the effectiveness of our results with several examples. Our findings highlight the applications of network control methods in tackling this crucial problem in algebraic graph theory, with implications for machine learning and network design.more » « less
-
In machine learning applications, data are often high-dimensional and intricately related. It is often of interest to find the underlying structure and Granger causal relationships among the data and represent these relationships with directed graphs. In this paper, we study multivariate time series, where each series is associated with a node of a graph, and where the objective is to estimate the topology of a sparse graph that reflects how the nodes of the graph affect each other, if at all. We propose a novel fully Bayesian approach that employs a sparsity-encouraging prior on the hyperparameters. The proposed method allows for nonlinear and multiple lag relationships among the time series. The method is based on Gaussian processes, and it treats the entries of the graph adjacency matrix as hyperparameters. It utilizes a modified automatic relevance determination (ARD) kernel and allows for learning the mapping function from selected past data to current data as edges of a graph . We show that the resulting adjacency matrix provides the intrinsic structure of the graph and answers causality-related questions. Numerical tests show that the proposed method has comparable or better performance than state-of-the-art methods.more » « less
-
The spectral decomposition of graph adjacency matrices is an essential ingredient in the design of graph signal processing (GSP) techniques. When the adjacency matrix has multi-dimensional eigenspaces, it is desirable to base GSP constructions on a particular eigenbasis that better reflects the graph’s symmetries. In this paper, we provide an explicit and detailed representation-theoretic account for the spectral decomposition of the adjacency matrix of a weighted Cayley graph. Our method applies to all weighted Cayley graphs, regardless of whether they are quasi-Abelian, and offers detailed descrip- tions of eigenvalues and eigenvectors derived from the coefficient functions of the representations of the underlying group. Next, we turn our attention to constructing frames on Cayley graphs. Frames are overcomplete spanning sets that ensure stable and potentially redundant systems for signal re- construction. We use our proposed eigenbases to build frames that are suitable for developing signal processing on Cayley graphs. These are the Frobenius–Schur frames and Cayley frames, for which we provide a characterization and a practical recipe for their construction.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/HPEC.2016.7761646
