Files in this item

FilesDescriptionFormat

application/pdf

application/pdfLI-DISSERTATION-2019.pdf (2MB)
(no description provided)PDF

Description

Title:Learning on graphs with high-order relations: spectral methods, optimization and applications
Author(s):Li, Pan
Director of Research:Milenkovic, Olgica
Doctoral Committee Chair(s):Milenkovic, Olgica
Doctoral Committee Member(s):Han, Jiawei; Hajek, Bruce; He, Niao; Gleich, David
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):hypergraph
spectral clustering
submodular function
Lovasz extension
semi-supervised learning
PageRank
Abstract:Learning on graphs is an important problem in machine learning, computer vision and data mining. Traditional algorithms for learning on graphs primarily take into account only low-order connectivity patterns described at the level of individual vertices and edges. However, in many applications, high-order relations among vertices are necessary to properly model a real-life problem. In contrast to the low-order cases, in-depth algorithmic and analytic studies supporting high-order relations among vertices are still lacking. To address this problem, we introduce a new mathematical model family, termed inhomogeneous hypergraphs, which captures the high-order relations among vertices in a very extensive and flexible way. Specifically, as opposed to classic hypergraphs that treat vertices within a high-order structure in a uniform manner, inhomogeneous hypergraphs allow one to model the fact that different subsets of vertices within a high-order relation may have different structural importance. We propose a series of algorithms and relevant analytic results for this new model. First, after we introduce the formal definitions and some preliminaries, we propose clustering algorithms over inhomogeneous hypergraphs. The first clustering method is based on a projection method, where we use graphs with pairwise relations to approximate high-order relations and then directly use spectral clustering methods over obtained graphs. For this type of method, we provide provable performance guarantee, which works for a sub-class of inhomogeneous hypergraphs that additionally impose constraints on the internal structures of high-order relations. Such constraints are related to submodular functions, so we term such a sub-class of inhomogeneous hypergraphs as submodular hypergraphs. Later, we study the Laplacian operators for these hypergraphs and generalize many important results in spectral theory for this setting including Cheeger's inequalities and discrete nodal domain theorems. Based on these new results, we further develop new clustering algorithms with tighter approximating properties than projection methods. Second, we propose some optimization algorithms for inhomogeneous hypergraphs. We first find that min-cut problems over submodular hypergraphs are closely related to an extensively studied optimization problem termed decomposable submodular hypergraph minimization (DSFM). Our contribution is how to leverage hypergraph structures to accelerate canonical solvers for DSFM problems. Later, we connect PageRank approaches to submodular hypergraphs and propose a new optimization problem termed quadratic decomposable submodular hypergraph minimization (QDSFM). For this new problem, we propose algorithms with first provable linear convergence guarantee and identify new relevant applications.
Issue Date:2019-06-11
Type:Text
URI:http://hdl.handle.net/2142/105596
Rights Information:Copyright 2019 Pan Li
Date Available in IDEALS:2019-11-26
Date Deposited:2019-08


This item appears in the following Collection(s)

Item Statistics