Acronym: GRASP

PI: Dr Miloš Radovanović, associate professor, Faculty of Sciences, University of Novi Sad

SRO: Faculty of Sciences, University of Novi Sad

Graphs, i.e. networks, help us understand the world around us. Points i.e. graph nodes can represent entities – say people – while connections between points express a relationship or interaction – e.g. acquaintance – between them. In this way, almost every phenomenon, from the level of an atom to the level of a galaxy, can be modelled in the form of a graph.

One of the most important operations available with graphs is their transformation into a “traditional” data form – a table. It allows the application of “traditional” tabular techniques of artificial intelligence and data analysis to gain insights which would be difficult or impossible to obtain by direct observation of networks. By applying tried and tested tabular techniques to the Facebook user interaction graph, we can classify users into categories of interest, identify communities, or suggest friends.

Traditional machine learning techniques and data analysis are sensitive to a large number of columns in the table, for which the term high dimensionality is used.

This sensitivity – the curse of dimensionality – can lead to difficulties and failures. This project deals with the negative effects of high dimensionality on the success of graph embedding, and the subsequent application of techniques for classification, clustering, similarity search and link prediction.

PROJECT OBJECTIVE: The project objective is to improve graph embedding, which will enable the application of a wide range of machine learning and data analysis techniques on graphs, or in simple terms – networks.

METHODOLOGY: During the implementation of the project, machine learning, fast similarity search and link prediction techniques and existing but also new graph embedding techniques will be applied.

EXPECTED RESULTS: New graph embedding techniques which take into account the dimensionality of their tabular form, and free open source software tools.

Illustration: Monika Lang