The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	On non-linear network embedding methods
Author:	Le, Huong Yen
View Online:	njit-etd2021-044 (xii, 78 pages ~ 5.0 MB pdf)
Department:	Department of Computer Science
Degree:	Doctor of Philosophy
Program:	Computer Science
Document Type:	Dissertation
Advisory Committee:	Koutis, Ioannis (Committee chair) Mili, Ali (Committee member) Wang, Jason T. L. (Committee member) Cucuringu, Mihai (Committee member) Basu Roy, Senjuti (Committee member)
Date:	2021-08
Keywords:	Cut approximator Spectral algorithm Spectral clustering Spectral graph theory Spectral modification Spectral modification framework
Availability:	Unrestricted
Abstract:	As a linear method, spectral clustering is the only network embedding algorithm that offers both a provably fast computation and an advanced theoretical understanding. The accuracy of spectral clustering depends on the Cheeger ratio defined as the ratio between the graph conductance and the 2nd smallest eigenvalue of its normalizedLaplacian. In several graph families whose Cheeger ratio reaches its upper bound of Theta(n), the approximation power of spectral clustering is proven to perform poorly. Moreover, recent non-linear network embedding methods have surpassed spectral clustering by state-of-the-art performance with little to no theoretical understanding to back them. The dissertation includes work that: (1) extends the theory of spectral clustering in order to address its weakness and provide ground for a theoretical understanding of existing non-linear network embedding methods.; (2) provides non-linear extensions of spectral clustering with theoretical guarantees, e.g., via different spectral modification algorithms; (3) demonstrates the potentials of this approach on different types and sizes of graphs from industrial applications; and (4)makes a theory-informed use of artificial networks.