number of hierarchy levels running off to infinity

graph-tool
1

Dear list,

I'm trying to fit a nested blockmodel to a (bipartite) network with ~10^6
edges. The algorithm minimize_nested_blockmodel_dl() doesn't terminate; it
keeps on adding layers indefinitely until it runs out of memory / hits
walltime, see below. What could be going on?

Many thanks in advance,

Peter

level 2 : replaced (94, 1) -> (94, 16) , dS: -15452.0134871 3

    l=3 B: 8 <- 16 shrinking 16 -> 11

    l=3 B: 8 <- 16 B=11 niter: 1 count: 1 breaks: 1
min_S: 1002.5742 max_S: 1002.5742 S: 1002.5742 ΔS: 0.00000 moves:
    0

    l=3 B: 8 <- 16 shrinking 11 -> 8

    l=3 B: 8 <- 16 B=8 niter: 1 count: 1 breaks: 1
min_S: 838.70438 max_S: 838.70438 S: 838.70438 ΔS: 0.00000 moves:
    0

    l=3 Current bracket: (2, 8, 16) (691.21840695494018,
838.70438205706921, 1340.6798309766764)

    l=3 B: 5 <- 8 shrinking 8 -> 5

    l=3 B: 5 <- 8 B=5 niter: 1 count: 0 breaks: 0
min_S: 752.39171 max_S: 753.34067 S: 752.39171 ΔS: -0.948956 moves:
    2

    l=3 B: 5 <- 8 B=5 niter: 2 count: 0 breaks: 0
min_S: 751.86303 max_S: 753.34067 S: 751.86303 ΔS: -0.528683 moves:
    1

    l=3 B: 5 <- 8 B=5 niter: 3 count: 1 breaks: 1
min_S: 751.86303 max_S: 753.34067 S: 751.86303 ΔS: 0.00000 moves:
    0

    l=3 Current bracket: (2, 5, 8) (691.21840695494018,
751.86302859686145, 838.70438205706921)

    l=3 B: 3 <- 5 shrinking 5 -> 3

    l=3 B: 3 <- 5 B=3 niter: 1 count: 0 breaks: 0
min_S: 720.12311 max_S: 720.62000 S: 720.12311 ΔS: -0.496886 moves:
    1

    l=3 B: 3 <- 5 B=3 niter: 2 count: 1 breaks: 1
min_S: 720.12311 max_S: 720.62000 S: 720.12311 ΔS: 0.00000 moves:
    0

    l=3 Current bracket: (2, 3, 5) (691.21840695494018, 720.123114036723,
751.86302859686145)

    l=3 Current bracket: (2, 2, 3) (691.21840695494018,
691.21840695494018, 720.123114036723)

    l=3 Bisect at B = 2 with S = 691.2184069549402

    l=3 Best result: B = 2, S = 691.2184069549402

level 3 : replaced (16, 1) -> (16, 2) , dS: -628.252218219 4

    l=4 Current bracket: (2, 2, 2) (26.653307346627116,
26.653307346627116, 26.653307346627116)

    l=4 Current bracket: (2, 2, 2) (26.653307346627116,
26.653307346627116, 26.653307346627116)

    l=4 Bisect at B = 2 with S = 26.65330734662712

    l=4 Best result: B = 2, S = 26.65330734662712

level 4 : replaced (2, 1) -> (2, 2) , dS: -1.86264514923e-09 5

    l=5 Current bracket: (2, 2, 2) (26.653307346627116,
26.653307346627116, 26.653307346627116)

    l=5 Current bracket: (2, 2, 2) (26.653307346627116,
26.653307346627116, 26.653307346627116)

    l=5 Bisect at B = 2 with S = 26.65330734662712

    l=5 Best result: B = 2, S = 26.65330734662712

level 5 : replaced (2, 1) -> (2, 2) , dS: -1.86264514923e-09 6

    l=6 Current bracket: (2, 2, 2) (26.653307346627116,
26.653307346627116, 26.653307346627116)

    l=6 Current bracket: (2, 2, 2) (26.653307346627116,
26.653307346627116, 26.653307346627116)

    l=6 Bisect at B = 2 with S = 26.65330734662712

    l=6 Best result: B = 2, S = 26.65330734662712

level 6 : replaced (2, 1) -> (2, 2) , dS: -1.86264514923e-09 7

    l=7 Current bracket: (2, 2, 2) (26.653307346627116,
26.653307346627116, 26.653307346627116)

    l=7 Current bracket: (2, 2, 2) (26.653307346627116,
26.653307346627116, 26.653307346627116)

    l=7 Bisect at B = 2 with S = 26.65330734662712

    l=7 Best result: B = 2, S = 26.65330734662712

level 7 : replaced (2, 1) -> (2, 2) , dS: -1.86264514923e-09 8

    l=8 Current bracket: (2, 2, 2) (26.653307346627116,
26.653307346627116, 26.653307346627116)

    l=8 Current bracket: (2, 2, 2) (26.653307346627116,
26.653307346627116, 26.653307346627116)

    l=8 Bisect at B = 2 with S = 26.65330734662712
and l is increasing into the thousands if the left alone.

attachment.html (6.66 KB)

2

This is a silly bug due to finite machine precision. It has already been
fixed in git, and will be available in the next release.

Best,
Tiago

3

Great, thanks Tiago

attachment.html (2.42 KB)

4

Just thought I mention that I've reproduced this bug again on my laptop.
Below some output, it keeps repeating at infinitum (got as far as level
l=14021)...
This is for just the minimize_nested_blockmodel_dl(), no layers, no
weights, bipartite structure.
Hope this helps,
Peter

    l=1 Current bracket: (2, 2, 2) (31.317096602087641,
31.317096602087641, 31.317096602087641)

    l=1 Current bracket: (2, 2, 2) (31.317096602087641,
31.317096602087641, 31.317096602087641)

    l=1 Bisect at B = 2 with S = 31.31709660208764

    l=1 Best result: B = 2, S = 31.31709660208764

level 1 : rejected replacement (2, 1) -> (2, 2) , dS: nan

    l=1 Current bracket: (2, 2, 2) (31.317096602087641,
31.317096602087641, 31.317096602087641)

    l=1 Current bracket: (2, 2, 2) (31.317096602087641,
31.317096602087641, 31.317096602087641)

    l=1 Bisect at B = 2 with S = 31.31709660208764

    l=1 Best result: B = 2, S = 31.31709660208764

level 2 : inserted 2 , dS: nan

    l=3 Current bracket: (2, 2, 2) (31.317096602087641,
31.317096602087641, 31.317096602087641)

    l=3 Current bracket: (2, 2, 2) (31.317096602087641,
31.317096602087641, 31.317096602087641)

    l=3 Bisect at B = 2 with S = 31.31709660208764

    l=3 Best result: B = 2, S = 31.31709660208764

level 3 : rejected replacement (2, 1) -> (2, 2) , dS: nan

    l=3 Current bracket: (2, 2, 2) (31.317096602087641,
31.317096602087641, 31.317096602087641)

    l=3 Current bracket: (2, 2, 2) (31.317096602087641,
31.317096602087641, 31.317096602087641)

    l=3 Bisect at B = 2 with S = 31.31709660208764

    l=3 Best result: B = 2, S = 31.31709660208764

level 4 : inserted 2 , dS: nan

    l=5 Current bracket: (2, 2, 2) (31.317096602087641,
31.317096602087641, 31.317096602087641)

    l=5 Current bracket: (2, 2, 2) (31.317096602087641,
31.317096602087641, 31.317096602087641)

    l=5 Bisect at B = 2 with S = 31.31709660208764

    l=5 Best result: B = 2, S = 31.31709660208764

attachment.html (9.91 KB)

5

Hi,

This is not very useful without the actual script and network that causes
it, otherwise I cannot try to reproduce it.

Are you using the newest version? Does it also happen with the current git
version?

Best,
Tiago

6

Hi Tiago,
yeah, sorry, I don't have enough to file a real bug report. This is on 2.22
(there's always a bit of lag until our high performance computing cluster
team can update graph-tool). But I just thought I mention this as a warning
that this machine precision bug might still be around.
Peter

attachment.html (8.46 KB)

7

This problem seems different from the previous one in this thread, since the
entropy difference is yielding NAN.

I haven't observed this problem myself yet. But if it is there, providing an
actual reproducible case would be helpful in fixing it.

Best,
Tiago

8

Maybe the entropy difference is NAN because it's infinity - infinity? As
in, too big for machine representation. My dataset has 1,961,256 vertices
and 4,465,869 edges...

attachment.html (2.92 KB)

9

This is not quite big enough to exhaust machine precision. Any system would
run out of memory much sooner.

I have used networks with upwards of 30 million edges, without any problems.

It must be something else.