Random Projections of Sparse Adjacency Matrices

We saw in Section 3 that operations in a new orthonormal basis require swapping coordinate vectors with the new basis vectors. Similarly, we can perform all the usual graph operations with the projection $\pi_{V}(A)$ by substituting the appropriate random code for each vertex. For example, to query if the edge $(v_{i},v_{j})$ is in the edgeset, we would usually compute the product $e_{i}^{T}Ae_{j}$. This returns a 1 if $(v_{i},v_{j})$ is an edge and 0 otherwise. The randomized analogue then takes the form $p_{i}^{T}\pi_{V}(A)p_{j}$. This quantity is close to 1 with high probability if $(v_{i},v_{j})$ is an edge and close to 0 with high probability otherwise.

In general, every graph operation has an analogue on the projected matrices by substituting in the random vertex codes. Rather than using the coordinate vector $e_{i}$ associated with vertex $v_{i}$, when working with the randomized projection $\pi_{V}(A)$ we use the $i^{th}$ column vector $p_{i}$ of the projection matrix $P_{V}$ instead.

One attractive property about our random projections is that they transform nicely under changes to the underlying vertex set. Suppose we wish to expand our graph by adding a new vertex $v_{n+1}$ and new edges $\{(v_{i},v_{n+1})\}_{i}$. With the usual $n\times n$ adjacency matrix, this would require expanding to a $n+1\times n+1$ matrix and filling in the appropriate entries of the added column and row. However, for the projected matrix we need to only generate a new random vector $p_{n+1}$ and add the appropriate edges to the projection: $\pi_{V}(A)+\sum_{i}p_{i}p_{n+1}^{T}$.

Our random matrix projection can be viewed as a projection method for the set of graphs whose vertices are in a fixed vertex set $V$. In light of the above discussion, this projection can be naturally extended to sets containing $V$ or restricted to subsets of $V$ by expanding or restricting the set of random vertex codes respectively. This property is particularly attractive for dynamic graph representations, where the edge and vertex set of the graph change over time. The dimension of the projected matrices stays the same under changes to the vertex set, and the addition/deletion of edges involving new vertices is simple. We only need to keep in mind the total capacity of the projection space: how many edges we can add to a projected matrix before accuracy in graph operations begins to break down. We analyze this behavior in Section 5.

Once we assign a random code to each vertex and construct our projection matrix $P_{V}$, that vertex-vector codebook is fixed. However, we might desire to reassign a new random vector to each vertex. This translation procedure has a simple analogue for projected matrices. Suppose we have a vertex set $V$ with two different random projection matrices $P_{V}$ and $Q_{V}$. The $i^{th}$ columns of $P_{V}$ and $Q_{V}$ are the random vectors assigned to vertex $v_{i}$ under each projection respectively. In order to swap the vector $p_{i}$ with $q_{i}$, we construct the translation matrix $T_{(P,Q)}=Q_{V}P_{V}^{T}$. By pseudo-orthonormality, we see that $T_{(P,Q)}p_{i}\approx q_{i}$ for every $i$. Hence, if $A_{P}$ is the projection of $A$ under $P_{V}$ and $A_{Q}$ is the projection under $Q_{V}$, we have the following relation:

Given a subset $S\subseteq V$, the subgraph generated generated by $S$, denoted $G_{S}\subset G$, is the subgraph generated by all edges involving vertices in $S$. Given the projected adjacency matrix $\pi(A_{G})$, we can extract the projection of the subgraph $\pi(A_{G_{S}})$ by the following procedure. Let $P_{S}$ be the $d\times|S|$ matrix whose columns are the random codes assigned to each vertex of $S$, and define $T_{S}=P_{S}P_{S}^{T}$. By pseudo-orthonormality, we have the following approximate relation:

This subset procedure, along with graph translation, can be applied to aggregate multiple graphs into a single large graph. For example, suppose we have two disjoint graphs $G$ and $H$. Their aggregate graph $G\cup H=(V_{G}\cup V_{H},E_{G}\cup E_{H})$ is the result of combining their vertex and edge sets together. We saw earlier that edge addition corresponds to adding the projected edges to our projected matrices. Therefore, given projections $\pi(A_{G})$ and $\pi(A_{H})$, the projection of their aggregate is the sum of their projections:

This can be combined in tandem with the subsetting procedure to combine selected subgraphs from a collection of graphs. Even when their vertex codes are different, the translation procedure mentioned previously allows use to translate them all into a single code before aggregation.

One interesting application of this suite of procedures is allowing a divide-and-conquer approach to storing a large sparse graph. Graph operations on the projected matrices depend on the size of the projection space (see Section 5), so breaking a large graph into subgraphs allows us to store their projections in a smaller projection space. Operations involving an individual subgraph also happen in a lower-dimensional space and have decreased time complexity. However, when the need arises to operate on information from a pool of these subgraphs, we can use the above subset and pooling procedures to easily generate a wide suite of projections that correspond to those generated by their graph aggregates.

The above examples demonstrate that we can represent graphs of varying size and different vertex sets in the same projection space. Translation and pooling operations are of fixed dimension, allowing for a unified way to manipulate and combine a broad range of graphs. This suggests that random projections are also ideal for applications where graph aggregation is an important operation such as the divid-and-conquer situation described above.

First, we need to define $m$-order graph operations. This is important because each order requires a different scaling of the projection space. We say a graph operation has order $\boldsymbol{m}$ if it can be expressed as an operation involving the $m^{th}$ power of the adjacency matrix. For example, the edge query is a first order graph operation because it is a function of the adjacency matrix: $q((v_{i},v_{j}),G)=e_{i}^{T}Ae_{j}$.

We first characterize how the size of the projection needs to scale in order to retain accurate first and second order graph operations. Intuitively, these correspond to edge information of the 1-hop and 2-hop neighborhoods of the graph respectively. We give two informal statements on how the dimension $d$ of the projection space $\mathbb{R}^{d\times d}$ must scale with the number of edges, subject to a constraint on the vertex connectivity (number of edges each vertex participates in). An account of the technical results justifying these statements is given in Appendix A.

For sparse graphs, the node degree condition is satisfied for all or a majority of vertices. Indeed, a closer inspection of the proofs in Appendix A show that as long as the vertices of the relevant edges satisfy this or a much looser bound on the node degree, the results still hold. This allows us to include sparse graphs that might have central vertices, which act like hubs and connect to many other vertices. If we are only interested in first order properties of the graph, the first result implies that we can compress a large sparse adjacency matrix using $n^{2}$ parameters into a smaller matrix using $\Omega(n)$ parameters, resulting a drastic compression for large sparse graphs.

While first and possibly second order operations comprise a bulk of the interesting graph operations, for completeness we have the following informal scaling statement for $m$-order graph operations.

We first consider the coordinate list representation. This represents a sparse matrix as a list of 3-tuples $(r,c,v)$ corresponding to each non-zero entry, where $r$ and $c$ are the row and column indices while $v$ is the value. A related representation is the Dictionary of Keys (DoK) representation, which is similar to the coordinate list representation except now each row-column index $(r,c)$ serves as a key with value $v$. Finally, the CSR format represents a matrix using three arrays containing the non-zero values, their column indices, and the number of non-zero entries above each row respectively. The CSR format can be easily computed from the previous two representations and vice versa.

A sparse graph with $n$ vertices has $O(n)$ edges. Hence, from their descriptions all three of the alternate sparse matrix representations require $O(n)$ parameters. For random projections, if we are only concerned with representing first-order properties, Theorem A.1 establishes that the $d\times d$ projections must have $d=\Omega(n)$, meaning the projections are of size $O(n)$.

We analyze some graph operations where the complexity differs based on the representation. For data structure operations, we use their complexity in Python as stated in the Python Wiki. Throughout this section, our random projection are $d\times d$ matrices.

One important aspect of our random projections is they benefit from numerical methods for linear algebra, such as parallel computation. This means that the time complexity of graph operations can be substantially reduced through these methods. The other sparse matrix representations do not enjoy these benefits, as we saw with the edge composition example. Hence, in practice the time complexity of graph operations with random projections can be significantly reduced, and they benefit from advances in numerical linear algebra.

In our previous work [18], we noted that there is a natural inner product on the space of adjacency matrices that counts the number of shared edges. Consider two graphs $G$ and $H$ whose vertex sets are contained in some larger set $V$. Given an ordering of $V$, we have the induced adjacency matrices $A_{G}$ and $A_{H}$. Define the inner product between their adjacency matrices as:

Expressing each adjacency matrix as the sum of coordinate outer products, we see that this function counts the number of edges common to both graphs:

One can check this is indeed an inner product, and in fact it generates the Frobenius norm: $tr(A^{T}A)=||A||_{F}^{2}$.

Note that we assumed the vertex sets of both graphs were contained in some larger set $V$. This is not an issue for a finite set of graphs $G_{i}$ with finite vertex sets $V_{i}$, as we can define $V=\cup V_{i}$. The adjacency matrix of a graph with respect to this large set $V$ is a block matrix whose single block is equal to the original adjacency matrix.

In light of graph inner product defined in Section 7.1, we almost have a JL-type result since the Frobenius norm of matrices coincides with the Euclidean norm if we regard matrices in $\mathbb{R}^{d\times d}$ as vectors in $\mathbb{R}^{d^{2}}$. We confirm this by proving that, with high probability, our random projection method is a map that satisfies the conditions of the JL Lemma.