PhD Defence: Advances in Node and Graph Embeddings: Algorithms, Evaluation Frameworks, and Applications

Candidate: Ashkan Dehghan-Kooshkghazi

Supervisors: Dr. Pawel Pralat and Dr. Wei Xu

Abstract
Complex systems are naturally modeled as graphs, where entities appear as nodes and relationships as edges. This abstraction spans domains from social networks to protein interactions to financial transactions. However, graphs have irregular structure, and most machine learning methods require fixed-length vector inputs. Embedding methods bridge this gap by mapping nodes, edges, or entire graphs to continuous vector spaces, yielding representations that preserve relevant information. The study of embeddings centers on three pillars: designing algorithms that capture relevant information, evaluating the resulting vectors, and applying embeddings to downstream tasks. This thesis contributes to each pillar.

Local Signature Matrix Embedding (LSME) is a structural embedding algorithm that learns node representations by constructing label-invariant signature matrices. The algorithm organizes each node's local neighborhood into concentric layers based on hop distance, then computes transition probabilities between layers. These matrices capture structural equivalence by encoding how nodes connect to their neighborhoods, enabling unsupervised learning of structural representations without labeled data.

To address the gap in evaluation frameworks for structural embedding, we developed an unsupervised framework measuring how well structural embeddings preserve and learn node and structural features. In addition to providing a quantitative metric for measuring embedding performance, our framework reveals which embedding dimensions encode specific features, enabling practitioners to both quantify embedding quality and understand what their algorithms capture.

The Network Embedding Exploration Tool (NEExT) addresses the challenge of embedding entire graph collections varying in size, density, and structure. The framework treats each graph as a distribution of node feature vectors and measures dissimilarity using optimal transport theory. NEExT operates in supervised and unsupervised modes for feature selection, with a key contribution being explainability through interpretable node features. Experiments demonstrate competitive classification accuracy while maintaining interpretability. 

Finally, social media bot detection demonstrates how embeddings classify accounts as bots or humans. Since bots struggle to control their local network structure despite generating natural-looking content, we compared classical and structural node embeddings on Twitter datasets. Structural embeddings consistently outperform classical approaches for bot detection, as they capture functional roles independent of network position.