Translation. Region: Russian Federal

Source: State University Higher School of Economics – State University Higher School of Economics –

Established in 2011 International Laboratory of Algorithms and Technologies for Network Structure Analysis (LATASS) HSE University in Nizhny Novgorod conducts a wide range of fundamental and applied research, including joint projects with large companies: Sber, Yandex and other leaders of the IT industry. The methods developed by HSE scientists not only enrich science, but also improve the work of companies’ transport, and conduct medical and genetic research more successfully. HSE.Glavnoe talked about the work of the laboratory with its head, Professor Valery Kalyagin.

— Tell us how the laboratory was created.

— It was organized in 2011 under the Russian government mega-grant program. At that time, the work of a foreign scientist was a mandatory condition for participation in the competition. We were lucky that Professor Panagiotis Pardalos of the University of Florida responded to our proposal for cooperation. He continues to actively collaborate with the HSE and remains the scientific director of the laboratory. Oleg Kozyrev, Eduard Babkin and Boris Goldengorin actively participated in the preparation of the application. Boris Goldengorin played an important role in the development of the laboratory.

At that time, the study of algorithms for analyzing network structures and what is now called computer science was a new direction for HSE in Nizhny Novgorod.

Three years later, the grant work was highly appreciated by the Ministry of Education and Science of the Russian Federation, and it was extended for two years. When it was ending, we applied to create an international laboratory at the HSE, we were supported, and now we continue our work as a laboratory of the National Research University Higher School of Economics.

In the first years of our work, we attracted many young researchers who later became renowned scientists and practitioners.

— What interested them in the new laboratory?

— They had a unique opportunity to develop, to work with famous scientists in a creative atmosphere. Almost all of them took advantage of it and over the past years have grown as scientists, researchers and teachers. The development strategy from the very beginning was built on the obligatory combination of scientific research and teaching. And now all our research staff teach, this component of the work, the transfer of experience and competencies, is very important for a scientist.

— What have you managed to accomplish during this time?

— Over the past years, the laboratory has become a well-known scientific center in Russia and in the world, largely due to the efforts of Professor Pardalos, who pays much attention to recognition. We have many contacts with colleagues from different universities and scientific centers. Our laboratory is a co-organizer of a large international conference on optimization and applications, we participate in its program committee, and our scientific director is a multiple honorary chairman of the program committee.

We actively cooperate with our leading universities – MIPT, MSU, the Keldysh Institute of Applied Mathematics of the Russian Academy of Sciences, with Siberian and Ural scientific centers in Novosibirsk, Irkutsk and Yekaterinburg.

— What are the key areas of your work?

— These are mainly computer sciences: network models, technologies for analyzing network structures, various aspects of optimization, including problems of combinatorial or discrete optimization on graphs, applications to data mining.

— How can this be explained to a person who is not knowledgeable in higher mathematics?

— I will try to explain it in an accessible way. A network is a set of nodes and connections between them. The most understandable examples are social and telecommunication networks, where nodes are people or clients of a mobile operator, and connections are communications between them, measured in a certain way. This can be a graph with special attributes or a hypergraph.

The optimization task is also clear: you have, for example, a social network, and you want to understand which nodes to place information in so that it passes through the network faster, or, on the contrary, which nodes to block so that a fake message stops circulating in the network.

Another class of tasks that interests employees are large databases, queries for information in them. This is called the “nearest neighbor search problem” in a data array, when you give some query to a large data set and want to find the object in this database that is most similar to your query.

If the database consists of 10-20 objects, there are no difficulties, but when there are many of them, you need to organize the search correctly and quickly. For this search, a special graph structure is created on this data, and it speeds up the search by an order of magnitude using special algorithms.

— Is it possible to use your results in biology or medicine?

— We are investigating a class of network models that includes some biological networks, such as the network of neurons in the brain or the co-expression network of genes.

There are billions of neurons, and we can’t measure anything in these networks. But with the help of an electroencephalogram, it is possible to track the activity of individual areas of the brain and analyze the connections between them. Interesting network structures are being created that can be used to study brain activity, including in diseases — for example, analyzing neuron networks in Parkinson’s disease and epilepsy, which helps in their research.

A gene co-expression network (GCN) is constructed based on gene expression profiles for multiple samples or experimental conditions. Researchers look for pairs of genes that show a similar expression pattern across all samples. The result is a network model that can be analyzed for practical purposes, such as identifying the most important nodes in the model. The identified gene cluster means that the gene and its neighbors have similar expression profiles. This can then be used to simplify drug testing.

— How widely is your work applied in economics?

— Another well-known network is stock markets. We analyze assets, identify connections between them. Taking them into account, a stock market network is formed. Analysis of stock market networks allows us to form investment portfolios. A classic example is the Markowitz model of the optimal investment portfolio. However, using such models does not mean that you will avoid a risk that can cancel out all potential income.

Large trading companies, banks, and firms that advise investors want to have a clear model for how to form investment portfolios. They do not strive for super-profits, but want to invest reliably. And then network models turn out to be useful. Additional information about connections helps to identify portfolios with the necessary characteristics.

– You and your colleagues are probably rich people.

— We do not trade on the markets and do not give recommendations. Students write final theses on these and other topics and analyze how and which portfolios work on different markets.

This does not replace analysis, but it is useful for it and opens up additional opportunities for activity in the stock market.

For example, there is a possibility of choosing a portfolio by constructing a market network graph and identifying independent sets in it. It has been experimentally proven that such sets provide diversified and interesting portfolios in terms of profitability.

— Do the models you have developed suggest different development scenarios?

— The laboratory actively studies the uncertainty of algorithms for constructing various graph structures in network models such as gene co-expression networks, brain networks, and stock market networks.

If uncertainty is high, then conclusions may be false: we hope to get rich, but our expectations do not come true.

— How does solving fundamental scientific problems combine with applied work?

— We have a strong group headed by Dmitry Malyshev. In its direction (algorithmic graph theory), the research of this group is closer to theoretical computer science and discrete mathematics. A significant number of postgraduate students and young employees of the laboratory have defended dissertations on these topics. Despite the fundamental theoretical nature of the research, it also has applied significance. Estimates of the computational complexity of problems on graphs help to identify computationally difficult problems and find classes of problems that can be solved quickly.

In the first years of the laboratory’s work, we developed a direction of intelligent data analysis and AI. It is headed by Andrey Savchenko. He develops the direction of intelligent data analysis in conditions of limited resources, for example, on mobile devices that are less powerful than desktop computers or laptops. For example, we want to classify photos, texts, something else on our smartphone, but we do not have access to a powerful resource. On a smartphone, you cannot deploy a full-fledged neural network. He and his colleagues developed an approach that allows you to effectively solve such problems, and patented it as a result of intellectual activity (RIA). There are already applications that you can download and use.

— Is this necessary now, when we are promised quantum computers with unlimited capabilities?

— The head of a research center at a large foreign company recently said that we have returned to the situation of the 1970s, when scientists and practitioners, given the limited capabilities of processors and computer memory, paid special attention to the efficiency of algorithms. Then the speed of processors and the capacity of memory, including RAM, increased sharply, and this lost some of its relevance. Now the problem has returned, since we do not expect a significant improvement in hardware. When you train large language models or search large databases, you return to the need for fast calculations under conditions of limited resources. Now many large manufacturers of computing resources and IT companies are conducting research into the efficient use of existing capabilities. If we reduce calculations on at least one node by 1%, we will get a significant effect. We had a successful project with an IT company on the use of patterns (templates) of the computation graph to speed up the training of neural networks. Such tasks are becoming increasingly popular.

The emergence of a quantum computer with unlimited capabilities is still not a matter for the very near future.

— Which companies have used your developments?

— We developed an algorithm for organizing the delivery of products to stores for a large retail chain. This is called the transport routing problem, it is also network-based and calculates traffic along a road network. The problem has high computational complexity. If you have 100 cars and 1000 stores and you want to optimize traffic, then solving such a problem manually is difficult. It is also not easy for a computer to solve it, but clever algorithms help. This enables AI to manage the logistics of transport use.

— Is there a problem with the transition of scientists to industrial partners?

— There is a problem of personnel outflow in IT companies. We start interacting with companies, companies see the qualifications of our personnel, offer them to engage in science and solve interesting problems and attract specialists with better conditions.

— With which HSE departments does the laboratory collaborate?

— The closest cooperation has been established with International Center for Analysis and Decision Making and with Laboratory of Applied Network Analysis.

— How do you see the prospects for research?

— We focus on a combination of fundamental and applied research so that we have both good theoretical results and publications, as well as joint projects with industry.

The campus strategy is to expand applied research, and this is a nationwide trend. We must learn to meaningfully answer the question of how our theoretical developments can make a real contribution to the development of the country’s economy and social sphere. We see our prospects in the development of algorithms and technologies for artificial intelligence systems.

In addition to the purely scientific component, popularization of science is important in order to make theoretical and applied results accessible to schoolchildren, our future students and laboratory staff.

The laboratory, as one of the leading scientific centers in the field of computer science and applications, is open to new partnership projects of both fundamental and applied nature.

— What educational programs do you participate in?

“We are involved in two key programs on campus: “Applied Mathematics and Computer Science» (bachelor’s degree training) and «Intelligent data analysis» (training of masters). The laboratory’s subject matter is actively present in these programs. This is reflected both in teaching and in the students’ scientific work.

All international laboratories develop research expertise and pass it on to young people. If we do not have contact with students, where will we recruit new young employees?

I would like to add that our graduates are in demand in many companies and countries.

— Why is it important to preserve fundamental research?

— We are now seeing the second birth of mathematics, the development of intelligent data analysis and artificial intelligence technologies has generated tasks that require specialists with developed abstract thinking and a broad outlook, which fundamental mathematics provides. At the same time, many sections of mathematics are in demand. This is a sign of the 21st century.

For example, we have a huge data set and are trying to understand how it is structured. Often, the high dimensionality of the data is an obstacle to its analysis. To reduce the dimensionality without losing information, we need to have a good understanding of many sections of fundamental mathematics – from classical methods of linear algebra and mathematical analysis to advanced probabilistic models and topology.

Mathematicians have perked up, people see that they need to expand their field of activity to applied research, this is a characteristic feature of HSE.

— How do you manage to maintain international connections?

— We continue contacts with foreign scientists. Since 2012, we have regularly held an annual international conference on network analysis, international schools for young scientists. Almost everyone who came to Nizhny Novgorod continues to communicate, respond to proposals, despite the past pandemic and the current situation. For young scientists, this is an additional opportunity to assess the level of their research, it becomes clearer when in contact with colleagues from abroad. We strive for young people to actively communicate with guests. Students are also interested in this.

Please note: This information is raw content directly from the source of the information. It is exactly what the source states and does not reflect the position of MIL-OSI or its clients.