gigl.utils.csr#

Memory-lean COO -> CSR/CSC conversion.

graphlearn_torch.utils.coo_to_csr delegates to torch_sparse.SparseTensor, which builds a composite sort key, sorts it, and gathers row and col through the permutation while the caller’s originals are still live. Seven full-size int64 arrays exist at the peak, measured at 7.25x one int64 array on 400M edges. At a multi-billion-edge partition that is hundreds of GiB and the conversion, not the graph, is what exhausts the host.

This implementation is a two-pass counting sort: degrees give the exact output layout up front, so the output is allocated once and written in place, and the input is consumed in chunks so transients are bounded by chunk size rather than by edge count:

peak = row + col + indices + 2 x (num_rows + 1) + O(chunk + max_degree)

which is 2.0x one int64 array with int32 inputs. The max_degree term comes from the within-row sort, which cannot split a single row across blocks; it only matters for a graph whose largest row is a meaningful fraction of its edge count.

CompactTopology wraps the result as a GLT Topology.

Attributes#

DEFAULT_BAND_BYTES

DEFAULT_CHUNK_SIZE

DEFAULT_SORT_BLOCK_EDGES

logger

Classes#

CompactTopology

A GLT Topology built by build_csr_from_coo(), with no edge ids or weights.

Functions#

build_csr_from_coo(row, col[, num_rows, chunk_size, ...])

Convert a COO edge index to CSR without ever holding more than one int64 copy.

Module Contents#

class gigl.utils.csr.CompactTopology(edge_index, layout, num_rows=None)[source]#

Bases: graphlearn_torch.data.Topology

A GLT Topology built by build_csr_from_coo(), with no edge ids or weights.

Topology.__init__ is not called: it would fabricate torch.arange(num_edges) edge ids and convert with coo_to_csr, the two costs this class exists to avoid. Edge features are read by edge id, so a graph that has them cannot use this class.

Parameters:

  • edge_index (torch.Tensor) – [2, num_edges] COO. int32 and int64 are used as they are; anything else is cast to int64, as GLT’s Topology does.

  • layout (Literal["CSR", "CSC"]) – The layout GLT samples from.

  • num_rows (Optional[int]) – Size of the compressed dimension. Defaults to the largest compressed id + 1, as GLT’s Topology does.

gigl.utils.csr.build_csr_from_coo(row, col, num_rows=None, chunk_size=DEFAULT_CHUNK_SIZE, sort_block_edges=DEFAULT_SORT_BLOCK_EDGES, band_bytes=DEFAULT_BAND_BYTES)[source]#

Convert a COO edge index to CSR without ever holding more than one int64 copy.

Drop-in replacement for the (rowptr, col) half of graphlearn_torch.utils.coo_to_csr, which is 7.25x more expensive at the peak.

Edge ids and edge weights are unsupported: permuting them is a large part of what makes the upstream version expensive, and GiGL already declines to materialize edge ids when no edge type carries features.

To build CSC instead, pass the column indices as row and the row indices as col.

Parameters:

  • row (torch.Tensor) – 1-D row indices, int32 or int64.

  • col (torch.Tensor) – 1-D column indices, same length as row.

  • num_rows (Optional[int]) – Size of the row dimension; indptr has num_rows + 1 entries. Defaults to max(row) + 1, as coo_to_csr does.

  • chunk_size (int) – Edges per scatter chunk. Bounds the transient working set.

  • sort_block_edges (int) – Edges per block of the within-row sort, which orders each row’s columns ascending as coo_to_csr does.

  • band_bytes (int) – Destination window for the scatter, used only when indices could not be placed in memory.

Returns:

indptr of shape [num_rows + 1], always int64, and indices of shape [num_edges], both int64.

Return type:

Tuple[torch.Tensor, torch.Tensor]

Raises:

ValueError – If row and col disagree in length, a row id is out of range, or the scatter does not exactly fill every row.

gigl.utils.csr.DEFAULT_BAND_BYTES = 4294967296[source]#
gigl.utils.csr.DEFAULT_CHUNK_SIZE = 16777216[source]#
gigl.utils.csr.DEFAULT_SORT_BLOCK_EDGES = 33554432[source]#
gigl.utils.csr.logger[source]#