BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Hidden Ancestor Graphs with Assortative Vertex Attributes - Richar
 d Darling (NSA)
DTSTART:20220906T140000Z
DTEND:20220906T150000Z
UID:TALK178478@talks.cam.ac.uk
CONTACT:Jason Miller
DESCRIPTION:Synthetic vertex-labelled graphs play a valuable role indevelo
 pment and and testing of graph machine learning algorithms.  The hidden an
 cestor 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 t
 ree $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 low
 est 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 s
 parsity\, can all coexist in this model. Subgraphs consisting of the agree
 ment edges (end point labels agree)\, and the conflict edges (end point la
 bels differ)\, respectively\, play an important role in testing anomaly co
 rrection algorithms. Instances with a hundred million edges can be built i
 n minutes on an average workstation with sufficient memory.
LOCATION:MR9\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR