dmlc / dmlc/dgl

[GraphBolt] Compress type_per_edge array so that instead of COO, we use CSC.

Open
#7,143 3 comments 0 reactions 2 assignees Assigned to @frozenbugs View on GitHub
Work Item
Dominant language
Python
Stars
14.3k
Forks
3.1k
PR merge metrics
No merged PRs in 30d

Description

Our sampling code assumes that edges are sorted with respect to the edge types. Thus, we can actually use CSC to store it instead of COO. If the type per edge array for 2 vertices looks like this: [[1 1 1] [0 0 2 2 2 2]] with first vertex having 3 edges, second having 6, then this could be compressed into 3 arrays as:
`indptr=[0, 1, 3]` offsetting into: `tindptr=[0, 3, 5, 9]` and `types=[1, 0, 2]` giving actual type ids.

For example:
```python
for node_id in nodes:
for i in range(indptr[node_id], indptr[node_id + 1]):
type = types[i]
# indices values of edges with same type
indices[tindptr[i]: tindptr[i + 1]]
```

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.