Back to search

NJIT

On non-linear network embedding methods

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy in Computing Sciences - (Ph.D.)
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Le, Huong Yen
Contributors dc:contributor
  • Ioannis Koutis
  • Ali Mili
  • Jason T. L. Wang

Subjects

dc:subject × 8

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.njit.edu/dissertations/1537

Chain of custody

source
Harvested from
NJIT
Base URL
digitalcommons.njit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Le, Huong Yen. On non-linear network embedding methods. https://digitalcommons.njit.edu/dissertations/1537