Graduate Defense: Janet Layne

Dissertation Information

Title: Advancing Structural Representation Learning for Static and Dynamic Graphs

Program: Doctor of Philosophy in Computing

Advisor: Dr. Edoardo Serra, Computer Science

Committee Members: Dr. Francesca Spezzano, Computer Science and Dr. Marion Scheepers, Mathematics

Abstract

Graphs, i.e., sets of entities (nodes) linked to one other (via edges), represent a universal data structure to describe interacting entities. Machine learning tasks on graphs are enabled by Graph Representation Learning, which automates the task of calculating numerical vector representations for components of a graph (nodes, edges, subgraphs, entire graphs) that preserve relationship information. Structural graph representation learning (e.g. for nodes) aims to encode information about the structure of a node’s neighborhood, rather than the identity of its connected nodes. Few works have developed efficient and effective structural graph representation learning approaches for dynamic graphs. This work introduces Temporal SIR-GN, which calculates node representations based upon the probabilities that their neighborhood structures transition from one type to another over time. The time complexity for this algorithm is linear in the number of timestamps in a graph, and demonstrates drastically shorter runtimes than the state-of-the-art. In addition, Temporal SIR-GN outperforms existing SOTA at capturing temporal structure, resulting in better performance at node classification tasks. Capitalizing on the efficiency and performance of Temporal SIR-GN, a high-order temporal method will be presented that captures structural evolution in terms of extended (rather than pairwise) transitions. This higher-order method, while still efficient, outperforms even Temporal SIR-GN on node classification tasks. Finally, important modifications to Temporal SIR-GN enabled its use in a streaming approach, that is, to update incrementally as the graph is changing. Together, these works provide propitious advancements to the field of graph representation learning for dynamic graphs