Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Create Selection primitive #2580

Closed
Tracked by #3279
ChuckHastings opened this issue Aug 12, 2022 · 1 comment
Closed
Tracked by #3279

Create Selection primitive #2580

ChuckHastings opened this issue Aug 12, 2022 · 1 comment
Assignees
@seunghwak
Milestone
22.10

Comments

@ChuckHastings
Copy link
Collaborator

Create new Selection primitive for use by Neighbor sampling and Random walks.
This was referenced Aug 12, 2022
Closed
Closed
@seunghwak seunghwak mentioned this issue Aug 12, 2022
Merged
@ChuckHastings ChuckHastings mentioned this issue Aug 12, 2022
Merged
@seunghwak seunghwak mentioned this issue Aug 15, 2022
Merged
@ChuckHastings ChuckHastings added this to the 22.10 milestone Aug 19, 2022
rapids-bot bot pushed a commit that referenced this issue Aug 24, 2022
@seunghwak
Update vertex_frontier_t to take unsorted (tagged-)vertex list with p…
b0837f7 
…ossible duplicates (#2584)

Partially address #2580

Update vertex_frontier_t to take unsorted input (tagged-)vertex list with possible duplicates.

This will be used to define a selection primitive. The primitive needs to take a (tagged-)vertex list to support Node2Vec style algorithms (tagged with the predecessor vertex ID or some derived property from the current vertex predecessor vertex pairs).

Breaking as primitives API has been changed (`vertex_frontier_t` and `transform_reduce_v_frontier_outgoing_e_by_dst`).

Authors:
  - Seunghwa Kang (https://github.com/seunghwak)

Approvers:
  - Joseph Nke (https://github.com/jnke2016)
  - Chuck Hastings (https://github.com/ChuckHastings)
  - Naim (https://github.com/naimnv)

URL: #2584
rapids-bot bot pushed a commit that referenced this issue Aug 25, 2022
@seunghwak
Define a selection primtive API (#2586)
bbb54c7 
Partially address #2580.

This PR is dependent on #2584.

This PR defines API for two selection primitives, one for the biased sampling/random walk and another for uniform random sampling/random walk.

@ChuckHastings For Node2Vec style random walk,

We can compute intersections for each (previous vertex, current vertex pairs).

We need to first create a non-detail space primitive calling detail::nbr_intersection (https://github.com/rapidsai/cugraph/blob/branch-22.10/cpp/src/prims/detail/nbr_intersection.cuh#L492) for given vertex pairs (this can be used for Jaccard and Overlap coefficients as well).

In MG, each GPU should store neighbor intersection outputs for the relevant source/destination ranges (not sure whether should we create additional utility functions to handle this, or this may not be a recurring pattern, so just leave this task much more as a dark magic for advanced users who understand how the 2D partitioning actually works). May go for the latter till we see this pattern occurring in other places.

Once we have neighbor intersection outputs and previous vertex IDs for the relevant (previous vertex ID, current vertex ID) pairs, we can create `frontier` having tagged-current vertex ID values (tag is an index to access previous vertex ID and neighbor intersection outputs for the perv vertex, current vertex pair).

Then, `e_bias_op` can check whether the outgoing neighbor belongs to the intersection or coincides with the previous vertex to properly set bias values.

Authors:
  - Seunghwa Kang (https://github.com/seunghwak)

Approvers:
  - Chuck Hastings (https://github.com/ChuckHastings)
  - Joseph Nke (https://github.com/jnke2016)

URL: #2586
rapids-bot bot pushed a commit that referenced this issue Sep 14, 2022
@ChuckHastings
MG uniform random walk implementation (#2585)
5863be2 
This PR defines a uniform random walk implementation using the neighborhood sampling functions.

This will be refactored once the new sampling primitive (#2580) is implemented, but should provide a stronger starting point than the original code.

Partially addresses #2555

Authors:
  - Chuck Hastings (https://github.com/ChuckHastings)

Approvers:
  - Seunghwa Kang (https://github.com/seunghwak)

URL: #2585
@github-actions
Copy link

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

@kingmesal kingmesal mentioned this issue Feb 14, 2023
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@seunghwak seunghwak

Labels
None yet
Projects
None yet
Milestone
22.10
Development

No branches or pull requests
2 participants
@ChuckHastings @seunghwak