Beyond Static Graphs: Understanding Graph Neural Networks and Homophily in Dynamic Node Classification
Michael Ito, University of Michigan
Graph Neural Networks (GNNs) have been successfully applied in many settings, demonstrating competitive performance across many domains. In parallel, our theoretical understandings of GNNs have increased. For example, in node classification GNNs are known to perform well on homophilous graphs where a majority of edges connect nodes of similar label and poorly on heterophilous graphs where a majority of edges connect nodes of opposing label. However, analyses of GNNs have been limited to static graph settings lacking any temporal or dynamic components. Under many real-world settings, the graph is in fact dynamic and changes over time. In our work, we explore limitations of GNNs in dynamic settings, focusing on homophily. We first show that the direct application of homophily to the dynamic setting as defined in the static setting fails to accurately represent task difficulty. As a result, we define a new metric called the transition homophily. We demonstrate theoretically that under certain assumptions transition homophily accurately reflects task difficulty. Empirically, we apply transition homophily to a dynamic node classification problem from epidemiology, where we show that transition homophily accurately reflects task difficulty.
Abstract Author(s): Michael Ito, Jenna Wiens