Skip to content

[ENH] Allow edge betweenness centrality to return edge IDs and scores without endpoints #5617

Description

@alexbarghi-nv

Feature request

Add an option to edge betweenness centrality—especially the
pylibcugraph API—to return only edge IDs and centrality scores when the input
graph has edge IDs, without returning or materializing the source and
destination arrays.

A possible Python shape would be an opt-in flag such as
return_endpoints=False, returning (values, edge_ids). The default can
preserve the current (srcs, dsts, values, edge_ids) contract.

Motivation

We want to use approximate edge betweenness as an edge weight/bias for
cuGraph-PyG sampling on very large, distributed graphs. The graph already has
stable edge IDs, so consumers can associate each score with the original edge
without receiving its endpoints again.

The current pylibcugraph.edge_betweenness_centrality implementation obtains
and copies source vertices, destination vertices, centrality values, and edge
IDs (when present) into CuPy arrays. For a graph with E edges, the source and
destination results add two E-sized arrays that duplicate topology already
represented by the graph. Avoiding them would materially reduce result and
peak memory, particularly with 64-bit vertex IDs and multi-GPU graphs.

Our intended workflow is:

  1. Construct the distributed graph with edge IDs.
  2. Select a bounded k set, likely the highest-degree vertices.
  3. Run approximate edge betweenness.
  4. Retain only (edge_id, score) and discretize scores into quantile-based
    sampling weights.

Scope question

Would the memory saving require an option in the C/C++ result construction as
well as the pylibcugraph wrapper? Skipping only the final
copy_to_cupy_array() calls would reduce returned memory, but avoiding endpoint
materialization in the underlying result would provide the largest peak-memory
improvement.

Acceptance criteria

  • An opt-in API returns edge IDs and centrality scores without endpoint arrays.
  • Endpoint result allocation/copying is avoided when feasible, rather than
    merely hidden from the Python return tuple.
  • Existing callers retain the current return contract by default.
  • The behavior is covered for SG and MG graphs with edge IDs.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions