Learning on Inhomogeneous Hypergraphs

Although graphs are widely used in a myriad of machine learning tasks, they are limited to representing pairwise interactions. By contrast, in many real-world applications the entities engage in higher-order relations. Such relations can be modeled by hypergraphs, where the notion of an edge is generalized to a hyperedge that can connect more than two vertices. Traditional hypergraph models treat all the vertices in a hyperedge equally while in practice these vertices might contribute differently to the hyperedge. To deal with such cases, edge-dependent vertex weights (EDVWs) are introduced into hypergraphs which are able to reflect different importance of vertices within the same hyperedge. In this thesis, I study several fundamental problems considering the hypergraph model with EDVWs. First, I develop valid Laplacian matrices for this hypergraph model through random walks defined on vertices and hyperedges and incorporating EDVWs, based on which I propose spectral partitioning algorithms for co-clustering vertices and hyperedges. Second, I develop a framework for incorporating EDVWs into hypergraph cut problems via introducing a new class of hyperedge splitting functions which are both submodular and dependent on EDVWs. I also generalize existing reduction as well as sparsification techniques to our setting. Finally, I define p-Laplacians for this hypergraph model and focus on the p=1 case. I propose an efficient algorithm to compute the eigenvector associated with the second smallest eigenvalue of the 1-Laplacian and then use this eigenvector to cluster vertices in order to achieve better performance than traditional spectral clustering based on the 2-Laplacian.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

2023

Author dc:creator

• Zhu, Yu

Advisor dc:contributor.advisor

• Segarra, Santiago

• hypergraphs
• inhomogeneous hyperedges
• minimum s-t cut
• hyperedge expansion
• p-Laplacian
• spectral clustering

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/114890

OAI identifier oai:identifier

oai:repository.rice.edu:1911/114890