Videos

Hypergraph edit distance - theory, algorithms, and applications

Presenter
June 29, 2026
Abstract
Data that records groups of interacting entities, or groups of entities that share a common property, especially over time, is quite common in a variety of domains. These data can be modeled mathematically as a hypergraph with vertices representing the entities and hyperedges representing the groups. Understanding how the hypergraphs evolve over time, or how multiple groupings (hypergraphs) on the same entities differ, can be crucial to identifying trends and anomalies. For example, in computer networks each user has its own pattern of how they use various programs and files which can be summarized in a user-centric hypergraph. Tracking the structural difference between multiple user's behaviors can group users into categories, help spot anomalous users, which might be malicious, or help identify when two usernames correspond to the same person (i.e., entity disambiguation). One method of tracking changes in hypergraph structure is hypergraph edit distance, a generalization of the well-known graph edit distance. Both are known to be NP-hard to compute exactly but there are approximation algorithms or special cases where computation is possible. This talk will introduce two formulations of hypergraph edit distance, survey some theoretical results on how they relate to graph edit distance, and discuss a hypergraph neural network approach to approximating hypergraph edit distance. We then show applications to cyber anomaly detection and author disambiguation. This work is a collaboration with Audun Myers and Cliff Joslyn.