[00:00.000 --> 00:10.520]  The next talk will be on dimensionalization again, and this time we're looking at layout
[00:10.520 --> 00:11.520]  algorithms.
[00:11.520 --> 00:16.680]  So if you have a large graph, computing and good layout for the graph is actually computational
[00:16.680 --> 00:21.280]  expensive, and also hard, and oftentimes we end up with hairballs, as you've seen in
[00:21.280 --> 00:29.000]  the Sigma, Sigma example, but there are other approaches as well, and so I'm really excited
[00:29.000 --> 00:33.560]  today for an ML-based approach, right?
[00:33.560 --> 00:37.640]  So we've all seen that ML models are taking over more and more of our jobs, so we can
[00:37.640 --> 00:43.440]  all just relax all day and don't do anything anymore, because our ML overlords will take
[00:43.440 --> 00:44.920]  care of everything.
[00:44.920 --> 00:50.640]  So I'm really glad that Simone and Tomaso are here today to talk about a different approach
[00:50.640 --> 00:55.240]  to graph layouts, and so very much welcome and enjoy the talk.
[00:55.240 --> 00:57.560]  Thanks very much.
[00:57.560 --> 01:00.640]  Can you hear me in the back?
[01:00.640 --> 01:02.640]  Okay.
[01:02.640 --> 01:04.680]  Good morning to everyone.
[01:04.680 --> 01:07.680]  Thanks you for being here.
[01:07.680 --> 01:10.880]  Let me present myself briefly.
[01:10.880 --> 01:11.960]  My name is Tomaso.
[01:11.960 --> 01:14.240]  I'm here with Simone.
[01:14.240 --> 01:17.760]  We are to front-end and data visualization.
[01:17.760 --> 01:23.600]  So there's no amplification, so the last group and the last group can hear you.
[01:23.600 --> 01:24.600]  Okay.
[01:24.600 --> 01:26.400]  It's okay.
[01:26.400 --> 01:33.480]  We are to front-end and data visualization developer for Laus company from Venice, Italy,
[01:33.480 --> 01:42.760]  and today we are here to talk about new artificial intelligence-based approach to graph visualization
[01:42.760 --> 01:45.320]  discussed in recent papers.
[01:45.320 --> 01:47.320]  So let's start.
[01:47.320 --> 01:55.080]  Graph drawing is a very wide and vast field of computer engineering, so if we observe
[01:55.080 --> 02:03.320]  its evolution during the last 70 years, we can find many graph visualization algorithms.
[02:03.320 --> 02:11.040]  So we can find hierarchical techniques, radial layouts, orthogonal layouts, geometric methods,
[02:11.040 --> 02:16.080]  and also, of course, we know force-based approaches.
[02:16.080 --> 02:27.080]  And typically, most of these algorithms work by applying some kind of heuristics or models
[02:27.080 --> 02:33.800]  or geometric relationships in order to achieve the final visual results.
[02:33.800 --> 02:43.440]  And for example, we all know that post-direct algorithms work with physical models to unfold
[02:43.440 --> 02:45.560]  the graphs.
[02:46.560 --> 02:56.480]  Yeah, post-directed algorithms are those that probably have become more popular over time.
[02:56.480 --> 02:59.040]  This has happened for many reasons.
[02:59.040 --> 03:06.200]  They are very easy to use, easy to implement, can be used with all types of graphs and can
[03:06.200 --> 03:09.480]  be parallelized and many other reasons.
[03:09.480 --> 03:16.720]  But they present, for me, of course, a limit in terms of design control.
[03:16.720 --> 03:27.040]  If we run our first directed algorithms, it may be easy to introduce a steady conference
[03:27.040 --> 03:29.600]  over the layout.
[03:29.600 --> 03:35.120]  So we can only be sure that the graph will converge in order to find a balance between
[03:35.120 --> 03:42.200]  the forces, of course, but we can control which are the graphic features, the visual
[03:42.200 --> 03:46.040]  features that will be improved of design.
[03:46.040 --> 03:52.480]  And to do this, in recent years, the growing use of artificial intelligence models to solve
[03:52.480 --> 04:01.640]  problems has led to the creation of a new family of graphicization algorithms.
[04:01.960 --> 04:07.600]  These algorithms work by exploiting the concept of cost function.
[04:07.600 --> 04:16.680]  And so cost function is basically a mathematical function that allows us to measure how far
[04:16.680 --> 04:20.840]  a given system deviates from an ideal state.
[04:20.840 --> 04:28.320]  So if we have a graph composed of blue nodes, any cost function related to that graph will
[04:28.320 --> 04:36.840]  take the nodes, axes, coordinates on the screen as input and return a number as a value.
[04:36.840 --> 04:44.760]  That number indicates us how much the graph is respecting the graphic feature encoded
[04:44.760 --> 04:47.640]  in that cost function.
[04:47.640 --> 04:57.240]  And indeed, a cost function can be fully established and formulated by the programmer, the developer.
[04:57.240 --> 05:07.080]  And theoretically, we can encode any graphic feature in a cost function.
[05:07.080 --> 05:14.960]  So the question is, how can we formulate cost functions related to graphs?
[05:14.960 --> 05:22.120]  And to answer these questions, we have to ask ourselves which are the graphic features
[05:22.120 --> 05:24.320]  that we want to improve.
[05:24.680 --> 05:29.600]  One way to do this is to observe a bad layout.
[05:29.600 --> 05:38.160]  So if we look at the image, we can immediately notice that the topological distances, for
[05:38.160 --> 05:40.960]  example, are not respected.
[05:40.960 --> 05:48.960]  So we can find pairs of nodes with two ops that are seven times more distant than pairs
[05:48.960 --> 05:50.920]  of nodes with one hop.
[05:50.920 --> 05:58.440]  This is certainly a negative aspect of this design in terms of using of space.
[05:58.440 --> 06:05.760]  In addition, if we look at the topological node, we can see that the angles are not uniform
[06:05.760 --> 06:07.080]  on the graphs.
[06:07.080 --> 06:09.440]  The structure is not homogeneous.
[06:09.440 --> 06:12.960]  Same as for APD and distances.
[06:12.960 --> 06:19.440]  And finally, there are also conclusions of nodes known to be the element that most compromise
[06:19.480 --> 06:22.320]  the quality of a layout.
[06:22.320 --> 06:33.200]  So all these observations can be encoded in a cost function.
[06:33.200 --> 06:35.720]  So let's see an example now.
[06:35.720 --> 06:40.960]  For time reasons, we will talk only about a single cost function.
[06:40.960 --> 06:47.280]  Specifically, we will talk about the topological distances.
[06:47.280 --> 06:56.600]  So if we look at the tree in the image, it makes sense to think that the Euclidean distances
[06:56.600 --> 07:05.440]  between the pairs of nodes should be somehow proportional to the topological distances,
[07:05.440 --> 07:07.760]  the length of the shortest path.
[07:07.760 --> 07:14.040]  This is valid not only for three graphs, but in general for all types of graphs.
[07:14.040 --> 07:25.160]  So our goal is to formulate a cost function that gives us a measure of how much the current
[07:25.160 --> 07:31.880]  APD and distances between pairs of nodes are similar to the topological distances.
[07:31.880 --> 07:38.560]  And as in any artificial intelligence problem, we have to follow a data-driven approach.
[07:38.560 --> 07:45.560]  So we need a source of data that indicates us which is the ideal state of the system
[07:45.560 --> 07:49.240]  in order to train our model according to it.
[07:49.240 --> 07:57.720]  And in this case, our data source is metrics, is the topological distances metrics.
[07:57.720 --> 08:04.320]  So we can know which is the length of the shortest path between pairs of nodes.
[08:04.320 --> 08:13.760]  And with this data source, we can compute for each pair of nodes INJ the quadratic deviations
[08:13.760 --> 08:22.600]  between the current Euclidean distances and the real topological distances of INJ nodes.
[08:22.600 --> 08:31.040]  And finally, we can sum all the contributions of all of pairs, sorry, and build a single
[08:31.040 --> 08:38.920]  cost function in two variables that give us a measure of how much the graph is respecting
[08:38.920 --> 08:42.080]  the topological distances.
[08:42.080 --> 08:50.400]  So once that the cost function has been formulated, we can optimize it by running an optimization
[08:50.400 --> 08:51.840]  algorithm.
[08:51.840 --> 09:00.920]  So we can run Vanilla-Garand-Dichent, Stochastic-Garand-Dichent, Momentum, Adam, and many other algorithms.
[09:01.400 --> 09:07.400]  We know that the function variables, the cost function variables consist of the node
[09:07.400 --> 09:09.840]  axis coordinates on the screen.
[09:09.840 --> 09:19.480]  So if we optimize that cost function, we are moving the graph in order to find a minimum
[09:19.480 --> 09:22.160]  or a maximum of that cost function.
[09:22.160 --> 09:28.560]  So the graph will move in order to respect topological distances.
[09:28.560 --> 09:39.120]  And so we have linked the papers of these official intelligence methodologies.
[09:39.120 --> 09:51.360]  And today the authors have provided a tool to show these algorithms.
[09:51.360 --> 09:56.760]  So we can change, for example, types of graphs.
[09:56.760 --> 10:04.160]  And we can see, in this case, we have the spreads, loss function, cost functions.
[10:04.160 --> 10:12.360]  And we can combine many cost functions by applying a linear combination of all these
[10:12.360 --> 10:14.360]  cost functions.
[10:15.040 --> 10:23.040]  Well, in these introductions, I have talked about the methodologies.
[10:23.040 --> 10:32.840]  But our goal today here is to present contributions in 10 or 13 months.
[10:32.840 --> 10:40.320]  So I let the world to Simone, who will talk about our contributions in our web application.
[10:44.360 --> 10:57.520]  Hi.
[10:57.520 --> 11:05.120]  When you design a layout, it must be analyzed on the basis of two terms.
[11:05.120 --> 11:06.440]  Effectiveness and efficiency.
[11:06.440 --> 11:13.880]  The effectiveness covered by Tom Maso is the ability of a layout to highlight important
[11:13.880 --> 11:17.800]  structure in the graph and ensuring that they are understanding.
[11:17.800 --> 11:26.640]  Efficiency, which I will talk about, aims to visualize as many elements as possible while
[11:26.640 --> 11:29.320]  granting interactivity.
[11:29.320 --> 11:35.560]  And this is very important nowadays where everything is characterized by good data.
[11:35.560 --> 11:43.320]  Here we can see the results obtained with a glassy solution explained by Tom Maso with
[11:43.320 --> 11:50.040]  just only the stress function, not the wall of the other 10, but just only with the stress
[11:50.040 --> 11:51.040]  one.
[11:51.040 --> 11:56.600]  And as we can see, with just less than 3,000 volts, we can't guarantee the interactivity
[11:56.600 --> 11:57.600]  line.
[11:57.600 --> 12:05.880]  So because the layout can perform at least 15 iterations per second anymore.
[12:05.880 --> 12:14.880]  And I think also that in our web application, this is a task CPU intensive and make it unusable
[12:14.880 --> 12:18.320]  for the entire time.
[12:18.320 --> 12:25.320]  Our target for this project is to allow the visualization of as many nodes and edges as
[12:25.320 --> 12:32.920]  possible through the CPU and the parallel programming, so parallel programming on CPUs.
[12:32.920 --> 12:37.200]  In our web application.
[12:37.200 --> 12:40.400]  Let's see together how the algorithm is composed.
[12:40.400 --> 12:44.000]  So we are using just only the stress function.
[12:44.000 --> 12:49.400]  So the first thing to do is create the topological distance mathematics.
[12:49.400 --> 12:56.800]  Then until we achieve the goal, for every duration, we are calculating the gradient and
[12:56.800 --> 13:00.120]  not positions.
[13:00.120 --> 13:04.040]  Calculating the gradient, we traverse the topological distance mathematics.
[13:04.040 --> 13:13.120]  For every pair of nodes, we calculate the partial derivates over the Euclidean and topological
[13:13.120 --> 13:14.120]  distances.
[13:14.120 --> 13:20.600]  And in the end, we update the positions, the non-spositions, very simple.
[13:20.600 --> 13:27.800]  But as can be seen, this step of every duration is a quality time.
[13:27.800 --> 13:31.920]  So in every duration, you have to perform it.
[13:31.920 --> 13:41.280]  And the idea is to split this calculation of the gradient into two various threads.
[13:41.280 --> 13:50.000]  When you, if you would like to create a solution and multi-times solution, you have to consider
[13:50.000 --> 13:51.600]  at least two aspects.
[13:51.600 --> 13:59.520]  The memory you are sending every time to each thread and the load balancing across thread.
[13:59.520 --> 14:04.820]  For memory, for optimizing memory, we saw that the topological distance mathematics is
[14:04.820 --> 14:05.820]  mirrored.
[14:05.820 --> 14:08.760]  So it's divided by two triangles, the upper and the lower.
[14:08.760 --> 14:12.560]  So we are using just only one triangle.
[14:12.560 --> 14:23.760]  For load balancing, we take the triangle and create an array and split it into threads.
[14:23.760 --> 14:28.760]  Now every thread calculates a partial gradient.
[14:28.760 --> 14:37.080]  And in the end, the final gradient is coming from the sum of all the partials.
[14:37.080 --> 14:44.060]  Now the results over typescript and just only five threads.
[14:44.060 --> 14:49.760]  And the green line is the results over multi-times solution.
[14:49.760 --> 14:57.960]  As can be seen, it's very close to if the layout was linear time.
[14:57.960 --> 15:04.360]  So this line representing that.
[15:04.360 --> 15:13.760]  And let's see together the speed up of the solution.
[15:13.760 --> 15:20.960]  Considering the graph with 5,000 nodes and more or less 10,000 edges.
[15:20.960 --> 15:29.800]  So we are in this situation here.
[15:29.800 --> 15:35.120]  And comparing the solution with just only the main thread in the application versus
[15:35.120 --> 15:41.200]  the five thread, we can see that the speed up is more than eight.
[15:41.200 --> 15:43.640]  But that is possible with five thread.
[15:43.640 --> 15:49.360]  It's possible because as can be seen here, when you have five thread in a web application,
[15:49.360 --> 15:56.080]  they are performing the layout while the main thread is free to doing other things.
[15:56.080 --> 16:01.280]  If you have just only the main thread, he has to handle all everything.
[16:01.280 --> 16:10.400]  So the fact is also explained by this other solution with multiple thread with just only
[16:10.400 --> 16:17.080]  one thread plus the main in which we have five or less.
[16:17.080 --> 16:28.600]  This means that this is a problem that can have very good parallelization with five thread
[16:28.600 --> 16:30.960]  with five.
[16:30.960 --> 16:40.040]  Now I would like to show a simple example with a random generated graph.
[16:40.040 --> 16:48.600]  So we now are just only watching the performances and not the aspects.
[16:48.600 --> 16:59.800]  And this can be seen, I hope you can see, it's very fluid, with 8,000 nodes and more
[16:59.800 --> 17:07.360]  or less 16,000 edges.
[17:07.360 --> 17:18.520]  He is searching for a structure but he is a random generated, so it is an entire structure.
[17:18.520 --> 17:20.200]  So future works.
[17:20.200 --> 17:27.520]  So we saw that the problem is perfect parallelized.
[17:27.520 --> 17:37.400]  So the next step for us is to transform the problem from the parallel OSGPU to parallel
[17:37.400 --> 17:44.000]  OSGPU because we are just only using the GPU for the rendering but not for the computation.
[17:44.000 --> 17:53.800]  And with another solution, we perform the classic force layout, we obtain performance
[17:53.800 --> 17:58.400]  like 900 times more.
[17:58.400 --> 18:03.600]  So achieving more or less one million nodes visualize.
[18:03.600 --> 18:14.880]  So the hope is that about efficiency but also study if this is this kind of layout can guarantee
[18:14.880 --> 18:16.960]  the effectiveness.
[18:16.960 --> 18:25.040]  So making also not just only the stress one but more cost function and understand if he
[18:25.040 --> 18:32.880]  can guarantee a good visualization with 100,000 nodes.
[18:32.880 --> 18:37.800]  That's it for us.
[18:37.800 --> 18:49.560]  What?
[18:49.560 --> 18:55.880]  This version is not available but we will publish it, sorry.
[18:55.880 --> 19:01.520]  He asked if the code is available online.
[19:01.520 --> 19:18.080]  This kind of version is not available online, you can find the version of the spring and
[19:18.080 --> 19:39.040]  better here, you can find the, this is the same code more or less.
[19:39.040 --> 20:03.360]  Does it work for directly the graph, yes, of course, yeah.
[20:03.360 --> 20:23.040]  Yes, of course, there are many quality measures that allow us to show complex graph as a clip.
[20:23.040 --> 20:43.480]  If you go on the table, you can find the quality measure called the net volume, this is the
[20:43.480 --> 21:02.000]  quality measure and combining that measure with the stress with another one you can show
[21:02.000 --> 21:03.000]  also complex graphs.
[21:03.000 --> 21:04.000]  Are you using auto-exift tools to calculate partial derivatives of the cost function?
[21:04.000 --> 21:05.000]  No.
[21:05.000 --> 21:06.000]  It's being done by hand?
[21:06.000 --> 21:07.000]  No, it's interneted by us.
[21:07.000 --> 21:14.200]  We have used a tool for calculating of the derivatives, the partial gradients, etc.
[21:14.200 --> 21:26.720]  Now we have implemented the font-squash but the derivatives are very easy to compute from
[21:26.720 --> 21:29.720]  the most of quality measures.
[21:29.720 --> 21:42.760]  They are not very complex to compute and also to build an efficient multi-training solution
[21:42.760 --> 22:01.000]  because tool chains exist along with the parallelization on GPU, they come with 4-series of tools.
[22:01.000 --> 22:02.000]  Yes, yes.
[22:02.000 --> 22:17.440]  So, the formula was using TensorFlow.js but as easy as it is implemented, it's not that
[22:17.440 --> 22:23.440]  the complexity, it's not giving from there the time-square complexity.
[22:23.440 --> 22:32.800]  Does Julia out-support interactive adding of new nodes like when user wants to expand
[22:32.800 --> 22:33.800]  to see new neighborhoods?
[22:33.800 --> 22:34.800]  Yes.
[22:34.800 --> 22:41.320]  So, the new nodes appeared around the double pick note and the other nodes doesn't get around.
[22:41.320 --> 22:44.040]  Yes, it depends of how you have the...
[22:44.040 --> 22:47.040]  Ribbit, yes, yes.
[22:47.040 --> 22:48.040]  He has...
[22:48.040 --> 22:49.040]  Sorry.
[22:49.040 --> 23:00.840]  If we continue to work, if we, for example, expand a node, we do something on the graph,
[23:00.840 --> 23:06.480]  yes, of course, it depends of how you have built your applications.
[23:06.480 --> 23:16.160]  For example, if you have continuously run over the time, you can expand a node, update the
[23:16.160 --> 23:20.880]  graph topology and the renderer will continue to work.
[23:20.880 --> 23:21.880]  Yes.
[23:21.880 --> 23:24.880]  You can perform it also to the introduced nodes.
[23:24.880 --> 23:25.880]  Sorry.
[23:25.880 --> 23:26.880]  Thank you.
[23:26.880 --> 23:33.880]  How does it compare to first layouts regarding number of iterations, convergence speed?
[23:33.880 --> 23:34.880]  Okay.
[23:34.880 --> 23:40.120]  It is about the same because if you are watching to the classic first layout, so the spring
[23:40.120 --> 23:48.640]  and better of Peter it's time square because for every relation, you take the charge and
[23:48.640 --> 23:51.640]  this is time square.
[23:51.640 --> 23:52.640]  Okay.
[23:52.640 --> 24:05.920]  The time complexity is the same, but the velocity of convergence depends of how you have tuned
[24:05.920 --> 24:12.800]  the hyperparameters of the model and depends from the optimization algorithm that you have
[24:12.800 --> 24:13.800]  used.
[24:13.800 --> 24:20.440]  For example, gradient descent is known to be very slow to converge, but if you use more
[24:20.440 --> 24:32.240]  efficient optimization algorithm, such as Adam's command that accumulates an inertia
[24:32.240 --> 24:40.360]  during the iteration, the speed up is more than gradient descent and depends also on
[24:40.360 --> 24:44.800]  the learning rate curve that you put on the system.
[24:44.800 --> 24:53.200]  For example, you can add an exponential decay of the learning rate in order to have a very
[24:53.200 --> 24:57.840]  speed during the iteration, very large speed in the iteration.
[24:57.840 --> 25:05.240]  And then when the graph starts to converge, you can reduce the learning rate in order to
[25:05.240 --> 25:10.000]  find a better minimum or a better maximum.
[25:10.000 --> 25:11.360]  Thank you.
[25:11.360 --> 25:15.280]  The last one or so?
[25:15.280 --> 25:19.280]  If you have more questions, you can just continue.
[25:19.280 --> 25:20.280]  Thank you so much, everyone.
[25:20.280 --> 25:21.280]  Thank you to Majora.
[25:21.280 --> 25:21.280]  Thank you.
[25:27.840 --> 25:28.840]  Thank you.
[25:28.840 --> 25:28.840]  Bye.