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

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

Chiu, Ping-Ko ; Koyejo ; Oluwasanmi

关键词: Cutnorm, Cut-Distance, Approximation Algorithm, Graph, Graph Theory, Dense Graph, Neroscience, Artificial Neural Networks;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/101227/CHIU-THESIS-2018.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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.