Fix #450: support 64-bit indices in Louvain

[fjsj]

Modifications:

• Closes " 64-bit Louvain? Support more than 2147483647 edges #450"

Impacted submodules:

• sknetwork.clustering.louvain

This pull request:

• [ ] does not decrease code coverage
• [ ] passes the tests
• [ ] is documented and the documentation build passes
• [ ] has PEP8-compliant code and explicit variable naming
• [ ] has a tutorial (facultative but recommended)

Any doubts about some technicalities? Do not hesitate to look at the dedicated Wiki.

[fjsj]

I'm having issues with psutil builds in Travis.

[nathandelara]

Thanks for the PR!

We are currently trying to think of ways not to use this extra dependency. You are experimenting first hand the troubles that we usually encounter with new dependencies and continuous integration. So adding one extra dependency just for this very specific feature might not be worth it.

In my opinion, there are still many workarounds to explore. Hopefully, we will give you a feedback soon.

Best

[fjsj]

Sounds great @nathandelara. I was able to build locally psutil in a Mac and CentOS 7 just fine. I suspect Travis may be making things more difficult here. But I agree ideally a new dependency shouldn't be added here.

[QLutz]

Hello,

We gave this some more thought and found that the 32/64-bit index switch can be handled in a much simpler way: letting SciPy choose the most appropriate size and sticking to it. Using the fused type you introduced, it seems to work without much effort. I tried making a commit to add those changes but it seems your organisation's parameters won't allow me to push on your fork. If you can apply these changes yourself (they are minimal), they consist in:

• removing psutil:
  • setup.py, line 24: remove third entry of the list
  • louvain.py, line 13: remove the import
• removing the np_int_t attribute in louvain.py:
  • lines 107-112: remove all
  • lines 140-141: remove .astype(self.np_int_t)
  • line 198: remove , dtype=self.np_int_t

• adapting the tests in test_louvain.py:

  • Remove from unittest import mock

  • Change test_options_with_64 to:

    def test_options_with_64_bit(self):
    adjacency = karate_club()
    # force 64-bit index
    adjacency.indices = adjacency.indices.astype(np.int64)
    adjacency.indptr = adjacency.indptr.astype(np.int64)
    
    # resolution
    louvain = Louvain(resolution=2)
    labels = louvain.fit_transform(adjacency)
    self.assertEqual(len(set(labels)), 7)
    
    # tolerance
    louvain = Louvain(resolution=2, tol_aggregation=0.1)
    labels = louvain.fit_transform(adjacency)
    self.assertEqual(len(set(labels)), 12)
    
    # shuffling
    louvain = Louvain(resolution=2, shuffle_nodes=True, random_state=42)
    labels = louvain.fit_transform(adjacency)
    self.assertEqual(len(set(labels)), 9)
    
    # aggregate graph
    louvain = Louvain(return_aggregate=True)
    labels = louvain.fit_transform(adjacency)
    n_labels = len(set(labels))
    self.assertEqual(louvain.adjacency_.shape, (n_labels, n_labels))
    
    # aggregate graph
    Louvain(n_aggregations=1, sort_clusters=False).fit(adjacency)

  • In test_options, do not forget to remove:

  # check used np.int type
  louvain = Louvain()
  self.assertEqual(louvain.np_int_t, np.int32)

[fjsj]

Sounds great, thanks for the input! I'll do these updates ASAP.

[fjsj]

OK, just force-pushed to have a single commit and added an additional check self.assertEqual(labels.dtype, np.int64). Please LMK if it's fine or not.

Thanks again for reviewing this!

[QLutz]

Hi,

The build failed due to unrelated issues that arose after you opened the PR. Can you merge with the latest commit of develop to correct them?

Thanks for the additional check! Also, if you happen to be able to test the algorithm on a graph that needs 64-bit indexing, do not hesitate to give us feedback (especially if there are any issues).

Thanks for contributing!

[fjsj]

Thanks for checking.

Failed again, this time on Mac setup at "Installing iTunes, iTunes Device Support Update, Security Update 2020-005, Safari, Command Line Tools (macOS High Sierra version 10.13) for Xcode".

Tested on my local Mac, working fine.

I'll let you folks know once I test it on the huge graph, thanks!

[QLutz]

I've tried to make a lighter update for Travis not to timeout. Could you give it a try?

We're looking forward to hearing from you then!

[codecov[bot]]

Codecov Report

Merging #456 (36bf889) into develop (4bb8d35) will increase coverage by 0.00%. The diff coverage is 100.00%.

@@           Coverage Diff            @@
##           develop     #456   +/-   ##
========================================
  Coverage    97.96%   97.97%           
========================================
  Files          167      167           
  Lines         7383     7402   +19     
========================================
+ Hits          7233     7252   +19     
  Misses         150      150           

Impacted Files	Coverage Δ
sknetwork/clustering/louvain.py	100.00% <100.00%> (ø)
sknetwork/clustering/louvain_core.pyx	100.00% <100.00%> (ø)
sknetwork/clustering/tests/test_louvain.py	100.00% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 4bb8d35...36bf889. Read the comment docs.

[QLutz]

Closing this now but do not hesitate to tell us how the package behaves on huge graphs.

Thanks a lot for the contribution!