Hidden Ancestor Graphs with Assortative Vertex Attributes

Add to your list(s) Download to your calendar using vCal

• Richard Darling (NSA)
• Tuesday 06 September 2022, 15:00-16:00
• MR9, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Jason Miller.

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.

This talk is part of the Probability series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR9, Centre for Mathematical Sciences
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.