Graph Modelling Study led by Lassonde Student Named Best Student Paper Finalist

At the 2021 IEEE International Conference on Acoustics, Speech and Signal Processing, Saghar Bagheri, was selected out of over 3600 submissions as a Best Student Paper finalist for her publication “Learning Sparse Graph Laplacian with K Eigenvector Prior Via Iterative GLASSO and Projection” which she presented virtually on June 10, 2021.

While there is currently no shortage of big datasets, finding correlations within them and being able to model them remains a distinct challenge. Work currently being conducted in the research group of Gene Cheung, associate professor in the Department of Electrical Engineering and Computer Science at the Lassonde School of Engineering, is looking to examine graphs that represent networks of data points.

When most people hear the word “graph” they think of a bar graph or a line graph. However, to Saghar, who is a master’s student in Professor Cheung’s research group, a graph is a complex network with numerous nodes which represent datapoints. Pairs of data points are connected by edges, and together, the nodes and edges create the network known as a graph. “A great example of a graph is someone’s social media network. For example, people can be represented by ‘nodes’ and the connection between them can be represented by ‘edges’. We can then study these graphs, as sets of nodes and edges and find patterns,” Saghar said.

These graphs are so massive and complex that it is impossible to extrapolate and model their behaviour without making some assumptions. Saghar and her co-authors were able to make assumptions about the behaviour of the graphs by using some creative mathematics and approaching the problem in a way that no other research team has before. 

“In order to model these massive networks, most researchers have primarily made assumptions within the nodal domain,” explained Saghar. “What we did was different – we made assumptions within the spectral domain.”

Simply speaking, using nodal space represents a direct approach whereas using spectral space is an indirect approach to solving the problem of modelling datasets. The spectral space contains eigenvectors and eigenvalues. These eigenvectors can aggregate all the information from the edges of a graph and can specify the most common patterns, which can then be used as fuel to construct a model that is significantly better at demonstrating correlations than existing algorithms. While Saghar and her co-authors demonstrated the effectiveness of their approach for image processing applications, they believe that this approach can be applied to any type of graph. In the future, they are interested in working with data mining applications and with brain data, via collaborations with VISTA, of which Professor Cheung is a core member.

In theory, the use of this new method can improve the efficiency and accuracy of graph-based modelling. This means finding more accurate correlations within real-world datasets and better predicting future trends. For example, improved modelling of data obtained from wireless sensors in forests could be used to anticipate forest fires. Datasets derived from social network activity, political voting patterns, and brain activity could also be modelled.

Originally from Iran, Saghar completed her undergraduate degree at Sharif University studying math and computer science. It was her love of math that led her to pursue a graduate degree and with Professor Cheung’s research group. Saghar defended her master’s thesis in June and is planning on staying on as a doctoral student in Professor Cheung’s group.  

“I always enjoyed studying math problems,” said Saghar. “When I was looking for graduate supervisors, I learned that Dr. Cheung’s work was highly mathematical which made joining his group an easy choice.” 

Saghar asserts that her work is far from done and that she wants to perform more experiments, try different spectral assumptions and work with the different datasets in the near future.  

The IEEE International Conference on Acoustics, Speech and Signal Processing is one of the most famous conferences in the signal processing society. In 2021 it was hosted virtually in Toronto at the Metro Toronto Conventional Centre.  

This article also appeared in YFile