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.

分析了一种用于邻接矩阵的随机投影方法，研究其在表示稀疏图中的实用性，展示了这些随机投影保留了其底层邻接矩阵的功能，同时具有额外的特性，使它们作为动态图表示具有吸引力。特别地，它们可以在相同的空间中表示不同大小和顶点集的图，从而实现对图的聚合和操作的统一方式。同时提供关于投影大小需要如何扩展以保留准确的图操作的结果，表明投影的大小可以与顶点数线性扩展，同时准确地保留一阶图信息。最后，将这种随机投影描述为保持距离的邻接矩阵映射，类似于通常的 Johnson-Lindenstrauss 映射。