[BUG] Segmentation fault with hierarchical_leiden

[Nithanaroy]

Expected Behavior

graspologic.partition.leiden.hierarchical_leiden should return a list of nodes along with their cluster and level IDs

Actual Behavior

Fails with a segmentation fault

Example Code

Please see How to create a Minimal, Reproducible example for some guidance on creating the best possible example of the problem

import graspologic as gc
import networkx as nx
import pickle
import faulthandler

faulthandler.enable()

# construct my graph which I cannot unfortunately share

clusters = gc.partition.hierarchical_leiden(
    graph=G, max_cluster_size=986, random_seed=42
)

Full Traceback

Fatal Python error: Segmentation fault

Current thread 0x00007f6b0c2031c0 (most recent call first):
  File "<MY_PYTHON_BIN_PATH>/python3.10/site-packages/graspologic/partition/leiden.py", line 588 in hierarchical_leiden
  File "<@beartype(graspologic.partition.leiden.hierarchical_leiden) at 0x7f69ae76af80>", line 304 in hierarchical_leiden
  File "<MY_PROJECT_PATH>/test/leiden_test.py", line 13 in <module>

Extension modules: numpy.core._multiarray_umath, numpy.core._multiarray_tests, numpy.linalg._umath_linalg, numpy.fft._pocketfft_internal, numpy.random._common, numpy.random.bit_generator, numpy.random._bounded_integers, numpy.random._mt19937, numpy.random.mtrand, numpy.random._philox, numpy.random._pcg64, numpy.random._sfc64, numpy.random._generator, scipy._lib._ccallback_c, scipy.linalg._fblas, scipy.linalg._flapack, scipy.linalg.cython_lapack, scipy.linalg._cythonized_array_utils, scipy.linalg._solve_toeplitz, scipy.linalg._decomp_lu_cython, scipy.linalg._matfuncs_sqrtm_triu, scipy.linalg.cython_blas, scipy.linalg._matfuncs_expm, scipy.linalg._decomp_update, scipy.sparse._sparsetools, _csparsetools, scipy.sparse._csparsetools, scipy.sparse.linalg._dsolve._superlu, scipy.sparse.linalg._eigen.arpack._arpack, scipy.sparse.linalg._propack._spropack, scipy.sparse.linalg._propack._dpropack, scipy.sparse.linalg._propack._cpropack, scipy.sparse.linalg._propack._zpropack, scipy.sparse.csgraph._tools, scipy.sparse.csgraph._shortest_path, scipy.sparse.csgraph._traversal, scipy.sparse.csgraph._min_spanning_tree, scipy.sparse.csgraph._flow, scipy.sparse.csgraph._matching, scipy.sparse.csgraph._reordering, sklearn.__check_build._check_build, psutil._psutil_linux, psutil._psutil_posix, scipy.special._ufuncs_cxx, scipy.special._cdflib, scipy.special._ufuncs, scipy.special._specfun, scipy.special._comb, scipy.special._ellip_harm_2, scipy.spatial._ckdtree, scipy._lib.messagestream, scipy.spatial._qhull, scipy.spatial._voronoi, scipy.spatial._distance_wrap, scipy.spatial._hausdorff, scipy.spatial.transform._rotation, scipy.ndimage._nd_image, _ni_label, scipy.ndimage._ni_label, scipy.optimize._minpack2, scipy.optimize._group_columns, scipy.optimize._trlib._trlib, scipy.optimize._lbfgsb, _moduleTNC, scipy.optimize._moduleTNC, scipy.optimize._cobyla, scipy.optimize._slsqp, scipy.optimize._minpack, scipy.optimize._lsq.givens_elimination, scipy.optimize._zeros, scipy.optimize._highs.cython.src._highs_wrapper, scipy.optimize._highs._highs_wrapper, scipy.optimize._highs.cython.src._highs_constants, scipy.optimize._highs._highs_constants, scipy.linalg._interpolative, scipy.optimize._bglu_dense, scipy.optimize._lsap, scipy.optimize._direct, scipy.integrate._odepack, scipy.integrate._quadpack, scipy.integrate._vode, scipy.integrate._dop, scipy.integrate._lsoda, scipy.special.cython_special, scipy.stats._stats, scipy.stats.beta_ufunc, scipy.stats._boost.beta_ufunc, scipy.stats.binom_ufunc, scipy.stats._boost.binom_ufunc, scipy.stats.nbinom_ufunc, scipy.stats._boost.nbinom_ufunc, scipy.stats.hypergeom_ufunc, scipy.stats._boost.hypergeom_ufunc, scipy.stats.ncf_ufunc, scipy.stats._boost.ncf_ufunc, scipy.stats.ncx2_ufunc, scipy.stats._boost.ncx2_ufunc, scipy.stats.nct_ufunc, scipy.stats._boost.nct_ufunc, scipy.stats.skewnorm_ufunc, scipy.stats._boost.skewnorm_ufunc, scipy.stats.invgauss_ufunc, scipy.stats._boost.invgauss_ufunc, scipy.interpolate._fitpack, scipy.interpolate.dfitpack, scipy.interpolate._bspl, scipy.interpolate._ppoly, scipy.interpolate.interpnd, scipy.interpolate._rbfinterp_pythran, scipy.interpolate._rgi_cython, scipy.stats._biasedurn, scipy.stats._levy_stable.levyst, scipy.stats._stats_pythran, scipy._lib._uarray._uarray, scipy.stats._ansari_swilk_statistics, scipy.stats._sobol, scipy.stats._qmc_cy, scipy.stats._mvn, scipy.stats._rcont.rcont, scipy.stats._unuran.unuran_wrapper, pyarrow.lib, pyarrow._hdfsio, pandas._libs.tslibs.ccalendar, pandas._libs.tslibs.np_datetime, pandas._libs.tslibs.dtypes, pandas._libs.tslibs.base, pandas._libs.tslibs.nattype, pandas._libs.tslibs.timezones, pandas._libs.tslibs.fields, pandas._libs.tslibs.timedeltas, pandas._libs.tslibs.tzconversion, pandas._libs.tslibs.timestamps, pandas._libs.properties, pandas._libs.tslibs.offsets, pandas._libs.tslibs.strptime, pandas._libs.tslibs.parsing, pandas._libs.tslibs.conversion, pandas._libs.tslibs.period, pandas._libs.tslibs.vectorized, pandas._libs.ops_dispatch, pandas._libs.missing, pandas._libs.hashtable, pandas._libs.algos, pandas._libs.interval, pandas._libs.lib, pyarrow._compute, pandas._libs.ops, pandas._libs.hashing, pandas._libs.arrays, pandas._libs.tslib, pandas._libs.sparse, pandas._libs.internals, pandas._libs.indexing, pandas._libs.index, pandas._libs.writers, pandas._libs.join, pandas._libs.window.aggregations, pandas._libs.window.indexers, pandas._libs.reshape, pandas._libs.groupby, pandas._libs.json, pandas._libs.parsers, pandas._libs.testing, sklearn.utils._isfinite, sklearn.utils.sparsefuncs_fast, sklearn.utils.murmurhash, sklearn.utils._openmp_helpers, ot.lp.emd_wrap, sklearn.metrics.cluster._expected_mutual_info_fast, sklearn.preprocessing._csr_polynomial_expansion, sklearn.preprocessing._target_encoder_fast, sklearn.metrics._dist_metrics, sklearn.metrics._pairwise_distances_reduction._datasets_pair, sklearn.utils._cython_blas, sklearn.metrics._pairwise_distances_reduction._base, sklearn.metrics._pairwise_distances_reduction._middle_term_computer, sklearn.utils._heap, sklearn.utils._sorting, sklearn.metrics._pairwise_distances_reduction._argkmin, sklearn.metrics._pairwise_distances_reduction._argkmin_classmode, sklearn.utils._vector_sentinel, sklearn.metrics._pairwise_distances_reduction._radius_neighbors, sklearn.metrics._pairwise_distances_reduction._radius_neighbors_classmode, sklearn.metrics._pairwise_fast, sklearn.utils._fast_dict, sklearn.cluster._hierarchical_fast, sklearn.cluster._k_means_common, sklearn.cluster._k_means_elkan, sklearn.cluster._k_means_lloyd, sklearn.cluster._k_means_minibatch, sklearn.neighbors._partition_nodes, sklearn.neighbors._ball_tree, sklearn.neighbors._kd_tree, sklearn.utils.arrayfuncs, sklearn.utils._random, sklearn.utils._seq_dataset, sklearn.linear_model._cd_fast, _loss, sklearn._loss._loss, sklearn.svm._liblinear, sklearn.svm._libsvm, sklearn.svm._libsvm_sparse, sklearn.linear_model._sag_fast, sklearn.utils._weight_vector, sklearn.linear_model._sgd_fast, sklearn.decomposition._online_lda_fast, sklearn.decomposition._cdnmf_fast, sklearn.cluster._dbscan_inner, sklearn.cluster._hdbscan._tree, sklearn.cluster._hdbscan._linkage, sklearn.cluster._hdbscan._reachability, sklearn._isotonic, sklearn.tree._utils, sklearn.tree._tree, sklearn.tree._partitioner, sklearn.tree._splitter, sklearn.tree._criterion, sklearn.neighbors._quad_tree, sklearn.manifold._barnes_hut_tsne, sklearn.manifold._utils, _cffi_backend, simplejson._speedups, gensim._matutils, gensim.corpora._mmreader, gensim.models.word2vec_inner, gensim.models.word2vec_corpusfile, gensim.models.doc2vec_inner, gensim.models.doc2vec_corpusfile, gensim.models.fasttext_inner, gensim.models.fasttext_corpusfile, gensim.models.nmf_pgd, gensim.similarities.fastss, numba.core.typeconv._typeconv, numba._helperlib, numba._dynfunc, numba._dispatcher, numba.core.runtime._nrt_python, numba.np.ufunc._internal, numba.experimental.jitclass._box, sklearn.ensemble._gradient_boosting, sklearn.ensemble._hist_gradient_boosting.common, sklearn.ensemble._hist_gradient_boosting._gradient_boosting, sklearn.ensemble._hist_gradient_boosting._binning, sklearn.ensemble._hist_gradient_boosting._bitset, sklearn.ensemble._hist_gradient_boosting.histogram, sklearn.ensemble._hist_gradient_boosting._predictor, sklearn.ensemble._hist_gradient_boosting.splitting, scipy.signal._sigtools, scipy.signal._max_len_seq_inner, scipy.signal._upfirdn_apply, scipy.signal._spline, scipy.signal._sosfilt, scipy.signal._spectral, scipy.signal._peak_finding_utils, PIL._imaging, kiwisolver, scipy.cluster._vq, scipy.cluster._hierarchy, scipy.cluster._optimal_leaf_ordering (total: 259)
Segmentation fault

Your Environment

• Python version: 3.10.14
• graspologic version: 3.4.1

Additional Details

Any other contextual information you might feel is important.
Some statistics of the graph, G above

Number of nodes: 978
Number of edges: 20415
Average degree: 41.74846625766871
Average shortest path length: 2.167557294250376
Average clustering coefficient: 0.846603236827461
Graph density: 0.042731285831800116

[Nithanaroy]

More findings - When I sample edges randomly from the graph and try, it doesn't fail!?

import networkx as nx
import random

def sample_edges(G, num_edges_to_sample):

    # Get a list of all edges
    all_edges = list(G.edges())

    # Determine the number of edges you want to sample
    # num_edges_to_sample = 100  # Or any desired number

    # Sample a random subset of edges'
    num_edges_to_sample = min(num_edges_to_sample, len(all_edges))

    print(f"Sampling {num_edges_to_sample} edges.")

    sampled_edges = random.sample(all_edges, num_edges_to_sample)

    # Create a new graph with the sampled edges (and the nodes connected to them)
    G_sampled = nx.Graph()  # Or use nx.DiGraph() for directed graphs
    G_sampled.add_edges_from(sampled_edges)

    # Now G_sampled contains a subgraph with a random sample of edges from G
    return G_sampled

 for i in range(1000, 20001, 1000):
    try:
        print(f"Clustering with {i} edges.")
        G_sampled = sample_edges(G, i)
        clusters = gc.partition.hierarchical_leiden(
            graph=G_sampled, max_cluster_size=30, random_seed=42
        )
    except Exception as e:
        print(f"Error with {i} edges: {e}")

[Nithanaroy]

After more debugging, it fails when weights are added. clustering works fine for unweighted graph. However we did not observe a significant difference in distributions of edge weights between the graph that fails vs the one that works.

cc. https://github.com/ha2trinh

[bdpedigo]

what is the scale/datatype of the weights? could there be negative edge weights?

[Nithanaroy]

Float type and yes there could be negative weights.

[bdpedigo]

could try seeing if removing only negative edge weights (or making them positive) fixes the issue - I dont recall whether leiden makes sense in the case of negatives or not

[Nithanaroy]

Yes, I removed the negative weight edges and it works. However, for another graph with the below edge weight distribution, it works even with negative weights.

1. So I'm unsure if removing the negative weights is really a fix?
2. Also I am a little worried with the segmentation fault for this graph instance instead of a graceful error?

Also, I created a dumb notebook demonstrating negative edge weights is not an actual issue https://colab.research.google.com/drive/1Af04Kr_44U_BBTF0sw1gknJjCqXyi5UQ?usp=sharing

[daxpryce]

@Nithanaroy you're absolutely right that there should not be a panic. I didn't see this issue until now, but I'll try to make an exemplar test case to fix it. I am unclear if the Leiden paper suggests it should work for negative edge weights or not but no matter what, even if it doesn't support negative weights, it should tell you that instead of exploding in a firey inferno.