Comprehensive Exam - Justin Carpenter

Presented by Justin Carpenter
Computing PhD, Computer Science emphasis

Location: City Center Plaza 352

Towards a Comprehensive Understanding of Techniques for Graph-Based Network Representation

Abstract: Graph representations are crucial in domains such as social networks and bioinformatics, where detailed graph analysis is needed. Recent research trends have shifted away from random walk and matrix factorization approaches, focusing instead on Graph Neural Networks (GNNs) and Graph Representation Learning. However, GNNs face limitations like overfitting and difficulties in capturing the complete graph structure. Traditional graph representation learning methods also struggle with capturing complex structures due to limited neighborhood depth.

Node representation learning (NRL) aims to generate numerical vectors (embeddings) for the nodes of a graph, capturing meaningful structural information. In structural NRL, embeddings are designed to reflect the structural roles of nodes within the graph, making them particularly effective for tasks like node classification, where nodes belonging to the same class often share similar structural features, even if they are not directly connected. This is different from proximity-based methods, where embeddings are influenced by the spatial closeness of nodes within the graph.

The state-of-the-art in graph representation learning now increasingly relies on higher-order Weisfeiler-Lehman (WL) tests. This evolution is motivated by the need for more precise and detailed graph representations, which are critical for advanced applications. While higher-order WL tests, such as 3-dimensional variants, provide enhanced representations, they still face challenges related to computational inefficiency and high complexity, especially for medium to large graphs.

Committee: Dr. Edoardo Serra (chair), Dr. Francesca Spezzano, Dr. Amit Jain, Dr. Liljana Babinkostova (Comp EE)