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

[BUG]: cugraph.louvain does not handle empty graphs well #3804

Closed
2 tasks done
eriknw opened this issue Aug 16, 2023 · 2 comments · Fixed by #3886
Closed
2 tasks done

[BUG]: cugraph.louvain does not handle empty graphs well #3804

eriknw opened this issue Aug 16, 2023 · 2 comments · Fixed by #3886
Assignees
@rlratzel @naimnv
Labels
bug Something isn't working

Comments

@eriknw
Copy link
Contributor

eriknw commented Aug 16, 2023 •
edited
Loading

Version

22.10 (dev)

Which installation method(s) does this occur on?

Source

Describe the bug.

cugraph.louvain is very, very slow for empty input graphs. I would expect this condition to be detected and handled quickly.

I handled this in cugraph-nx here: https://github.com/rapidsai/cugraph/pull/3803/files#diff-506c93446829d8794348fa8b6773e7326ede87b095ac120c9c47fed46e56c699R31-R33

Minimum reproducible example

import sys
import networkx as nx
import cugraph

G = nx.Graph()
G.add_nodes_from(range(5))
# G = cugraph.utilities.ensure_cugraph_obj_for_nx(G)  # Optional
cugraph.louvain(G, sys.maxsize)  # Runs for a very long time

Relevant log output

No response

Environment details

No response

Other/Misc.

No response

Code of Conduct

  • I agree to follow cuGraph's Code of Conduct
  • I have searched the open bugs and have found no duplicates for this bug report
@eriknw eriknw added ? - Needs Triage Need team to review and classify bug Something isn't working labels Aug 16, 2023
@eriknw eriknw mentioned this issue Aug 16, 2023
Merged
@BradReesWork BradReesWork removed the ? - Needs Triage Need team to review and classify label Aug 22, 2023
@BradReesWork
Copy link
Member

@eriknw I cannot reproduce

rapids-bot bot pushed a commit that referenced this issue Aug 31, 2023
@eriknw
Add louvain_communities to cugraph-nx (#3803)
9268b08 
See: #3773 

Possible follow-up tasks:
- Update to use threshold parameter exposed from C++ (#3792)
- Add `max_level` argument to networkx implementation
  - ~Or, add `max_level` as extra`cugraph_nx`-specific argument~ (**done**)
- Update PLC to handle empty graphs gracefully (#3804)
- Update PLC to handle directed graphs
- Add `louvain_partitions` (needs added to PLC)
  - https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.louvain.louvain_partitions.html

This is passing many networkx tests. I don't have this as draft, b/c it's usable (and I would argue) mergable as is.

Authors:
  - Erik Welch (https://github.com/eriknw)

Approvers:
  - Rick Ratzel (https://github.com/rlratzel)

URL: #3803
@rlratzel
Copy link
Contributor

rlratzel commented Sep 6, 2023

@BradReesWork I'm able to reproduce this. I think the important arg to remember is sys.maxsize, did you use that?

rlratzel pushed a commit to rlratzel/cugraph that referenced this issue Sep 8, 2023
@eriknw @rlratzel
Add louvain_communities to cugraph-nx (rapidsai#3803)
f270817 
See: rapidsai#3773

Possible follow-up tasks:
- Update to use threshold parameter exposed from C++ (rapidsai#3792)
- Add `max_level` argument to networkx implementation
  - ~Or, add `max_level` as extra`cugraph_nx`-specific argument~ (**done**)
- Update PLC to handle empty graphs gracefully (rapidsai#3804)
- Update PLC to handle directed graphs
- Add `louvain_partitions` (needs added to PLC)
  - https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.louvain.louvain_partitions.html

This is passing many networkx tests. I don't have this as draft, b/c it's usable (and I would argue) mergable as is.

Authors:
  - Erik Welch (https://github.com/eriknw)

Approvers:
  - Rick Ratzel (https://github.com/rlratzel)

URL: rapidsai#3803
This was referenced Sep 26, 2023
Closed
Merged
@naimnv naimnv self-assigned this Sep 27, 2023
rapids-bot bot pushed a commit that referenced this issue Sep 29, 2023
@naimnv
Adds logic to handle isolated vertices at python layer (#3886)
6e5e066 
- Adds logic to handle isolated vertices
- Clamp downs max level to a sane number

closes #3804

Authors:
  - Naim (https://github.com/naimnv)

Approvers:
  - Joseph Nke (https://github.com/jnke2016)
  - Brad Rees (https://github.com/BradReesWork)
  - Chuck Hastings (https://github.com/ChuckHastings)
  - Rick Ratzel (https://github.com/rlratzel)

URL: #3886
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@rlratzel rlratzel

@naimnv naimnv

Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
4 participants
@eriknw @rlratzel @BradReesWork @naimnv