A sparse graph has relatively few edges compared with the number of possible edges. Its adjacency matrix therefore contains a low percentage of nonzero elements. Density and degree statistics make sparsity concrete: a graph with 7,650 nodes, more than 143,000 edges, and density 0.0049 is very sparse. section 5.2.1 section 7.5
Use sparsity to guide representation and exploratory analysis:
- Count nodes and stored edges, then calculate density against the possible edge count. section 5.2.1
- Inspect the degree distribution to find typical connectivity, low-degree nodes, hubs, and long tails. section 5.2.1
- Prefer sparse storage when few vertex pairs are connected; dense storage can be faster for graphs with many connections. section 7.5
Amazon Electronics co-purchaser graph
Products such as cameras and lenses form nodes connected by past co-purchases. The graph is medium-sized but very sparse, and most nodes have degree below 10, with a smaller higher-degree peak and a long tail. section 5.2.1
torch_geometric.transforms import ToSparseTensor dataset = YourDataset(transform=ToSparseTensor())
Convert a dense dataset to PyG sparse representation with ToSparseTensor; manual conversion through SparseTensor.from_dense is also available. section 7.5
