Clique finding complexity and optimisations

[yvan-sraka]

Originally posted by @yvan-sraka on internal Discord:

The discussion here #2307 remind it's important to talk about algorithmic design (side to other performance triage), one part of the problem is "how we measure things (and what we try to optimize? Latency? Memory usage? Charge resistance?)", and the other part (which could be more on whiteboard reflection) is thinking about time and space complexity of problem we try to solve:

For e.g. our consensus algorithm (which should be the more computation heavy part of our program) try to solve the NP-time problem of maximal clique in a graph, but is this really true?

1 - The problem we try to solve is the incremental P version of the problem: computing the max clique of a graph G + 1 node knowing already the max clique of the previous graph G ⇒ Dynamic Programming
2 - We do not compute the max clique of a random graph, our graph have a strong internal structure (because of incompatibility rules), that's a strong insight that a better strategy than the « without knowledge » standard version of the algorithm should apply!

It could be a neat challenge to prove that with a benchmark, if the consensus algorithm could be encapsulated properly in a function (thanks to refactoring), and then we could test it / prove its correctness with prop testing, fuzzing, etc ...

... reply by @damip:

it is a good challenge, and encapsulating the consensus is one of the goals of the refactoring !

[qdrn]

There are interesting questions regarding the complexity of maintaining the list of maximal cliques in a dynamic graph. I haven't been able to find good references regarding this problem. For instance this paper focuses on computing the set of maximal clique when the magnitude of chance is small, which is not our case is general. It may be interesting to look at references mentioned in the paper tho'.

Another related question is why did we chose to use IK_GPX ? There are other algorithms to compute maximal clique. Some may be more adapted or optimised for our specific problem.

[sebastien-forestier]

1- The problem of finding the maximal cliques is NP-time, so the incremental problem is obviously also NP-time. Btw we already have incremental optimisations, like not recomputing the cliques if there are no new direct incompatibility.
2- Yes the structure of the graph is not arbitrary at all, maybe we can find a faster solution for our particular case. However the general-purpose solution with the pivot vertex choice of the GPX scheme is already good for our case. Maybe optimisations can be made on the original algorithm, like caching the number of edges of each node, improving the pivot vertex choice or not computing the full graph as we know when incompatibilities start.

I think most of the cpu time should be spent in signature verification of operations. Currently computing cliques accounts for ~0.001% of cpu time, and it should not be otherwise unless there are attacks specifically trying to make clique finding take more time.

[yvan-sraka]

CPU time is (in the case of an asynchronous app) a wrong measure of what make the application actually slow or not resistant to charge, as explained here https://github.com/massalabs/massa/discussions/2315!

I wasn't clear in my point on the incremental algorithm, I would say that even if x = clique(G) is NP-time, incremental_clique(G + 1, G, x) where G + 1 is a lazy notation for saying that the graph G have just one more node added and only new edges from that node, and x is what we would call in dynamic programming an intermediate result, could be P-time, and often was when we have insight of an internal subproblem structure.

I'm not the best to explain all these concept here, I can of course do some whiteboard scheme at office next week, but I encourage also everyone to read the really applicable in real life lecture from Jeff Erickson http://algorithms.wtf/ :)

[sebastien-forestier]

The point was that in the general case, the incremental clique problem is NP. If it was P, then the clique problem would be P.
Again maybe in our case we can find something better :)

[yvan-sraka]

You mean that it exist a polynomial reduction from incremental algorithm to the non-incremental one starting from an empty graph! And that imply that the incremental version couldn't be P-time at each step, since iterating through step is O(n) with n the cardinal of G, I get it :)

[yvan-sraka]

But side to the computability problem, there is an order of magnitude between a solution that do useless computation without caching intermediate result and one that does. I like to remind that dynamic programming is just smart recursion using memoization!