Problem in importing the ECM

[al1yass2n]

Hello,

I was trying to run the ECM Jupiter notebook example, but I am stuck at the first cell. I just ran the cell that contains the import ECM but it is still running for hours. Any help?

Kind regards,
Ali

[deklanw]

@aliyassin4 Hey, not sure. I haven't looked at this package in awhile. If you have a serious usecase let me know and I can look into it harder and push some performance updates I've been meaning to make

But, for now, here's a Colab notebook with that example notebook functioning properly:
https://colab.research.google.com/drive/1l5ynPcca-5xKkzySfuWxzuCsAs03x2Wy?usp=sharing

[al1yass2n]

Hey, thank you for the notebook it works, however when I tried to run the code on a bigger network I received this error after running the code for two days:

RuntimeError: Didn't succeed in minimization. Message: Maximum number of iterations has been exceeded.

What does this mean?

[deklanw]

It means the optimization failed. You can try different initial conditions

instead of

initial_guess = model.get_initial_guess()

you can try

initial_guess = model.get_initial_guess(x)

where x is in [1,2,3,4,5,6]. The default is 5.

You can also try different optimization algorithms

changing
solution = model.solve(initial_guess, verbose=True)

to e.g.

solution = model.solve(initial_guess, method="Newton-CG", verbose=True)

See here for the available options

How large is the graph? If the above fails you can send me the graph and I'll see if I can get anything working on my end

[al1yass2n]

I am doing a comparison between statistical backbone extraction techniques and I would like to add you method, the graph consists of 2734 nodes and 16665 edges, so what do you suggest me to try to have a good result.

[deklanw]

The optimization of the parameters requires a starting point. They're just heuristics. None works best in all cases, afaik. I suggest trying out some of the different initializations, as above, and then if none work trying out some of the other optimization techniques, as above.

[al1yass2n]

Hello @deklanw,

I was running the ECM Filter on the US 500 airports network. I tried all the available options for the initial guess and it didn't work. However, I got this error on option 3:

 in MaxentGraph.solve(self, x0, method, verbose)
    167     raise ValueError("Invalid optimization method")
    169 start = time.time()
--> 170 sol = solver(f, x0=x0, method=method, **args)
    171 end = time.time()
    173 total_time = end - start

File ~/anaconda3/envs/backbones-env/lib/python3.10/site-packages/scipy/optimize/_minimize.py:721, in minimize(fun, x0, args, method, jac, hess, hessp, bounds, constraints, tol, callback, options)
    718     res = _minimize_trust_ncg(fun, x0, args, jac, hess, hessp,
    719                               callback=callback, **options)
    720 elif meth == 'trust-krylov':
--> 721     res = _minimize_trust_krylov(fun, x0, args, jac, hess, hessp,
    722                                  callback=callback, **options)
    723 elif meth == 'trust-exact':
    724     res = _minimize_trustregion_exact(fun, x0, args, jac, hess,
    725                                       callback=callback, **options)

File ~/anaconda3/envs/backbones-env/lib/python3.10/site-packages/scipy/optimize/_trustregion_krylov.py:51, in _minimize_trust_krylov(fun, x0, args, jac, hess, hessp, inexact, **trust_region_options)
     29 # tol_rel specifies the termination tolerance relative to the initial
     30 # gradient norm in the Krylov subspace iteration.
     31 
   (...)
     47 # Optimality of this choice of parameters among a range of possibilities
     48 # has been tested on the unconstrained subset of the CUTEst library.
     50 if inexact:
---> 51     return _minimize_trust_region(fun, x0, args=args, jac=jac,
     52                                   hess=hess, hessp=hessp,
     53                                   subproblem=get_trlib_quadratic_subproblem(
     54                                       tol_rel_i=-2.0, tol_rel_b=-3.0,
     55                                       disp=trust_region_options.get('disp', False)
     56                                       ),
     57                                   **trust_region_options)
     58 else:
     59     return _minimize_trust_region(fun, x0, args=args, jac=jac,
     60                                   hess=hess, hessp=hessp,
     61                                   subproblem=get_trlib_quadratic_subproblem(
   (...)
     64                                       ),
     65                                   **trust_region_options)

File ~/anaconda3/envs/backbones-env/lib/python3.10/site-packages/scipy/optimize/_trustregion.py:217, in _minimize_trust_region(fun, x0, args, jac, hess, hessp, subproblem, initial_trust_radius, max_trust_radius, eta, gtol, maxiter, disp, return_all, callback, inexact, **unknown_options)
    213 k = 0
    215 # search for the function min
    216 # do not even start if the gradient is small enough
--> 217 while m.jac_mag >= gtol:
    218 
    219     # Solve the sub-problem.
    220     # This gives us the proposed step relative to the current position
    221     # and it tells us whether the proposed step
    222     # has reached the trust region boundary or not.
    223     try:
    224         p, hits_boundary = m.solve(trust_radius)

File ~/anaconda3/envs/backbones-env/lib/python3.10/site-packages/scipy/optimize/_trustregion.py:86, in BaseQuadraticSubproblem.jac_mag(self)
     84 """Magnitude of jacobian of objective function at current iteration."""
     85 if self._g_mag is None:
---> 86     self._g_mag = scipy.linalg.norm(self.jac)
     87 return self._g_mag

File ~/anaconda3/envs/backbones-env/lib/python3.10/site-packages/scipy/linalg/_misc.py:145, in norm(a, ord, axis, keepdims, check_finite)
    143 # Differs from numpy only in non-finite handling and the use of blas.
    144 if check_finite:
--> 145     a = np.asarray_chkfinite(a)
    146 else:
    147     a = np.asarray(a)

File ~/anaconda3/envs/backbones-env/lib/python3.10/site-packages/numpy/lib/function_base.py:627, in asarray_chkfinite(a, dtype, order)
    625 a = asarray(a, dtype=dtype, order=order)
    626 if a.dtype.char in typecodes['AllFloat'] and not np.isfinite(a).all():
--> 627     raise ValueError(
    628         "array must not contain infs or NaNs")
    629 return a

ValueError: array must not contain infs or NaNs 

Any Idea how to solve this?
Thanks in advance