Enhancing Link Prediction on Graphs : A Multifaceted Approach
Graphs are a common way of representing real-world structured data. A graph is composed of nodes connected with one another via edges (i.e., "links"), where a link models how such nodes are related to one another. Due to the prevalence of graph-structured data, machine learning on graph data has become very popular.Link prediction, which attempts to predict unseen links in a graph, is a fundamental task on graphs. Link prediction has a multitude of real-world applications, including in recommender systems, knowledge graphs, and biology. In recent years, a flurry of methods have been introduced that make use of graph neural networks (GNNs) for this task. However, we find that multiple limitations impede our ability to create effective link prediction models that can perform in real-world settings. First, we find that the current method of evaluating link prediction models is both unrealistic and too easy, resulting in inflated model performance that doesn't reflect real-world performance. Second, we observe that current methods are limited in their ability to model various patterns in link formation. This poses a challenge in real-world datasets where links can form for a number of reasons. Third, efficiency is an important concern in link prediction, as effective models are often expensive to run. Lastly, we find that link prediction models on knowledge graphs suffer from degree bias, where poor representations are learnt for lower-degree nodes, leading to subpar performance. In this thesis, we first uncover the root cause of these fundamental limitations. I will then introduce our attempts to combat these problems, through the design of new evaluation strategies and new model design. Through the introduction of these new approaches, we help promote better use of link prediction in more realistic scenarios that can occur in the wild.
Read
- In Collections
-
Electronic Theses & Dissertations
- Copyright Status
- Attribution 4.0 International
- Material Type
-
Theses
- Authors
-
Shomer, Harry
- Thesis Advisors
-
Tang, Jiliang
- Committee Members
-
Shah, Neil
Liu, Kevin
Peng, Tai-Quan
- Date Published
-
2025
- Subjects
-
Computer science
- Program of Study
-
Computer Science - Doctor of Philosophy
- Degree Level
-
Doctoral
- Language
-
English
- Pages
- 143 pages
- Permalink
- https://doi.org/doi:10.25335/4730-c364