Hidden Ancestor Graphs with Assortative Vertex Attributes

Synthetic vertex-labelled graphs play a valuable role indevelopment and and testing of graph machine learning algorithms. The hidden ancestor graph is a new stochastic model for a vertex-labelled multigraph $G$ in which the observable vertices are the leaves $L$ of a random rooted tree $T$, whose edges and non-leaf nodes are hidden. The likelihood of an edge in $G$ between two vertices in $L$ depends on the height of their lowest common ancestor in $T$. The label of a vertex $v$ in $L$ depends on a randomized label inheritance mechanism within $T$ such that vertices with the same parent often have the same label. High label assortativity,high average local clustering, heavy tailed vertex degree distribution, and sparsity, can all coexist in this model. Subgraphs consisting of the agreement edges (end point labels agree), and the conflict edges (end point labels differ), respectively, play an important role in testing anomaly correction algorithms. Instances with a hundred million edges can be built in minutes on an average workstation with sufficient memory.

• Speaker: Richard Darling (NSA)
• Tuesday 06 September 2022, 15:00–16:00
• Venue: MR9, Centre for Mathematical Sciences.
• Series: Probability; organiser: Jason Miller.