Random Projections of Sparse Adjacency Matrices
Frank Qiu
We analyze a random projection method for adjacency matrices, studying its
utility in representing sparse graphs. We show that these random projections
retain the functionality of their underlying adjacency matrices while having
extra properties that make them attractive as dynamic graph representations. In
particular, they can represent graphs of different sizes and vertex sets in the
same space, allowing for the aggregation and manipulation of graphs in a
unified manner. We also provide results on how the size of the projections need
to scale in order to preserve accurate graph operations, showing that the size
of the projections can scale linearly with the number of vertices while
accurately retaining first-order graph information. We conclude by
characterizing our random projection as a distance-preserving map of adjacency
matrices analogous to the usual Johnson-Lindenstrauss map.