Widespread machine learning methods behind ‘link prediction’ perform very poorly, researchers say

When you browse a social media feed, you will likely be asked to follow or become friends with another person, expanding your personal network and contributing to the growth of the app itself. The person suggested to you is the result of link prediction: a popular machine learning (ML) task that evaluates the links in a network (your friends and everyone else’s) and attempts to predict what the links will be. next links.

In addition to being the engine that fuels the expansion of social media, link prediction is also used in a wide range of scientific research, such as predicting the interaction between genes and proteins, and is used by researchers as a reference for testing the performance of new ML algorithms.

New research from UC Santa Cruz computer science and engineering professor C. “Sesh” Seshadhri, published in the journal Proceedings of the National Academy of Sciences establishes that the metric used to measure link prediction performance is missing crucial information and that link prediction tasks perform far worse than the popular literature indicates.

Seshadhri and his co-author Nicolas Menand, a former UCSC undergraduate and master’s student and current Ph.D. candidate at the University of Pennsylvania, recommend that ML researchers stop using the standard practice metric for measuring link prediction, known as AUC, and introduce a new, more comprehensive metric for this issue. The research has implications for the reliability of ML decision-making.

The ineffectiveness of the AUC

Seshadhri, who works in theoretical computer science and data mining and is currently a researcher at Amazon, has previously researched ML algorithms for networks. In this previous work, he discovered some mathematical limitations that negatively impacted the performance of the algorithms, and in an effort to better understand the mathematical limitations in context, he delved deeper into link prediction due to its importance as a as a testbed problem for ML algorithms.

“The reason we were interested is because link prediction is one of those very important scientific tasks that is used to evaluate a lot of machine learning algorithms,” Seshadhri said.

“What we found was that the performance seemed really good… but we felt like there seemed to be something wrong with that metric. It feels like if you measured things a different way, you might not see such a thing. excellent results.”

Link prediction is based on the ML algorithm’s ability to perform low-dimensional vector embeddings, the process by which the algorithm represents people within a network as a mathematical vector in the space. All machine learning happens as mathematical manipulations of these vectors.

AUC, which stands for “area under curve” and is the most common metric for measuring link prediction, assigns ML algorithms a score from zero to one based on the algorithm’s performance.

In their research, the authors found that there are fundamental mathematical limitations to using low-dimensional embeddings for link predictions, and that AUC cannot measure these limitations. The inability to measure these limitations led the authors to conclude that AUC does not accurately measure link prediction performance.

Seshadhri said these results call into question the widespread use of low-dimensional vector embeddings in the ML field, given the mathematical limitations his research has highlighted on their performance.

State-of-the-art methods are not enough

Discovering the AUC’s shortcomings led researchers to create a new measure to better capture the limitations, which they call VCMPR. They used VCMPR to measure 12 ML algorithms chosen to be representative of the domain, including algorithms such as DeepWalk, Node2vec, NetMF, GraphSage, and graphics benchmark leader HOP-Rec, and found that link prediction performance was worst using VCMPR as a metric. rather than the AUC.

“When we look at the VCMPR scores, we see that the scores for most of the major methods available are really poor,” Seshadhri said. “It looks like they’re not doing a good job when you measure things a different way.”

The results also showed that not only was performance lower across the board, but some of the algorithms that performed worse than others when measured with AUC in turn performed better than cohort with VCMPR, and vice versa.

Reliability in machine learning

Seshadhri suggests that ML researchers use VCMPR to compare the link prediction performance of their algorithms, or at the very least stop using AUC as a metric. Since metrics are closely related to ML decision-making, using a flawed system to measure performance could lead to faulty decision-making about which algorithms to use in the world’s ML applications real.

“Metrics are so closely tied to what we decide to deploy in the real world: people need to have some confidence in it. If you have a bad way of measuring, how can you trust the results? » said Seshadri. “This article is somewhat of a cautionary tale: we need to be more careful in how we conduct our machine learning experiments and we need to come up with a richer set of metrics.”

In academia, using an accurate metric is crucial to creating advancements in the field of ML.

“It’s sort of a conundrum for scientific progress. A new result has to be supposed to be better than all the previous ones, otherwise it doesn’t do anything new, but it all depends on how you measure it.”

Beyond machine learning, researchers in a wide range of fields are using link prediction and ML to conduct their research, often with considerable potential impact. For example, some biologists use link prediction to determine which proteins are likely to interact in drug discovery. These biologists and other researchers outside of ML depend on ML experts to create reliable tools, because they often cannot become ML experts themselves.

While he thinks these results may not come as a huge surprise to those deeply involved in the field, he hopes that the broader community of ML researchers, and particularly those of graduate and PhD students, will involve. Students who use current literature to learn best practices and common wisdom in the field will take note of these findings and exercise caution in their work. He sees this research that presents a skeptical view as somewhat contrasting with a dominant philosophy of ML, which tends to accept a set of metrics and focuses on “pushing the bar” when it comes to progress in the field. .

“It’s important that we have a skeptical point of view, try to understand more deeply and constantly ask ourselves, ‘Are we measuring things correctly?'”