Approximating cutnorm: A robust method to compute distance between dense graphs for prediction and interpretation

This thesis presents techniques of modeling large and dense networks and methods of computing distances between them. Large and dense networks arise in many disciplines. Through recent advancements in dense graph theory and graph convergence, we have a new perspective on how large graphs should be considered and how the similarity of graphs should be computed. The thesis discusses the steps to approximate the distance between graphs and the integration of a new search algorithm to accelerate computation. A software package is produced to estimate distances between graphs and made available as the Cutnorm package on PyPI. The algorithm and software shows great performance on theoretical models and is faster than existing implementations. The thesis also explores practical applications of the graph convergence theory and Cut-Distances. It presents the theory and techniques to analyze human brain connectivity graphs from the ADHD200 dataset of the 1000 Connectome Project. It also presents a new insight to monitoring Artificial Neural Network convergence during the training process.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2018

Author dc:creator

• Chiu, Ping-Ko

Contributors dc:contributor

• Koyejo, Oluwasanmi

• Cutnorm, Cut-Distance, Approximation Algorithm, Graph, Graph Theory, Dense Graph, Neroscience, Artificial Neural Networks

Statement dc:rights

• Copyright 2018 Ping-Ko Chiu

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/101227

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/101227