Signed graphs are crucial data structures for expressing positive and negative relationships simultaneously. Their application ranges from structural health monitoring to financial models, where the sign of a relationship can add important nuance. Among the various graph learning tasks, node classification, which aims to predict the labels of unlabeled nodes given a partially labelled graph, is one of the most common tasks. While this problem has been extensively studied for unsigned graphs, where edges represent similarities between connected nodes, the appropriate design for models that tackle this task in signed networks remains relatively unexplored. This thesis focuses on Signed Graph Convolutional Networks (Signed-GCN), which provide powerful tools to realize the potential of signed graphs via the integration of advancements in machine learning and graph theory. A range of Signed-GCN approaches are developed and validated with the goal of providing intuitive interpretations of negative edges while achieving competitive and consistent performance for node classification in the context of semi-supervised learning. Progress towards this objective is achieved through multiple steps. Initially, a comprehensive review of (signed) graph representation learning is conducted to understand the necessity of transitioning from traditional machine learning methods to recent deep learning approaches capable of learning representations encoding a graph's structural information. Subsequently, various existing Signed-GCN methods, especially their aggregation process of integrating negative edges into the GCN framework, are reviewed in terms of their mathematical formulation, providing new insight using a combination of vector visualisations and theoretical analysis. Following this, alternative approaches are proposed. We embrace an interpretation of negative edges as representing a "repulsion effect'' between nodes, and this is reflected in our model design. We explore a number of formulations to model the direction and magnitude of the effect. Our proposed models are compared to existing approaches across a range of synthetic and real-world datasets, presenting a range of different data challenges. The competitive performance of the proposed models highlights the advantages of integrating a more direct interpretation of negative edge signs into the model design.
Date of Award | 31 Dec 2024 |
---|
Original language | English |
---|
Awarding Institution | - The University of Manchester
|
---|
Supervisor | Luis Ospina-Forero (Supervisor) & Julia Handl (Supervisor) |
---|
- node classification
- Graph Convolutional Network
- signed graph
GRAPH CONVOLUTIONAL NETWORKS FOR NODE CLASSIFICATION IN SIGNED GRAPHS
Dinh, T. T. (Author). 31 Dec 2024
Student thesis: Phd