Spectral Clustering of Random Hypergraphs

Thumbnail Image

Files

master_Välimaa_Ian_2024.pdf (1.12 MB)

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2024-07-31

Department

Major/Subject

Mathematics

Mcode

SCI3054

Degree programme

Master’s Programme in Mathematics and Operations Research

Language

en

Pages

77

Series

Abstract

Multiway clustering is a clustering problem with multidimensional data arrays. Such data can be used to represent higher-order interactions, hypergraphs and multilayer networks. This has various applications such as gene clustering from multitissue gene expression data or higher-order gene interactions, and personalized web search from clickthrough data. The main objective of this thesis is to determine when an underlying true cluster structure can be recovered from large and noisy data. Specifically, assuming a statistical model (tensor block model), how sparse a data array can be for a fast algorithm to recover the underlying clusters with high probability. This thesis develops a spectral clustering algorithm to solve this statistical problem, proves weak consistency with mathematical rigor and demonstrates it with numerical simulations. The weak consistency is proved by developing concentration inequalities for certain random matrices. The obtained weak consistency regime improves existing results.

Monisuuntaisen klusteroinnin tavoitteena on klusteroida moniulotteisesta datataulukosta. Tällaisella aineistolla voidaan esittää korkeamman asteen vuorovaikutuksia, hyperverkkoja ja monikerroksisia verkkoja ja sillä on sovelluksia muun muassa geenien klusteroinnissa monikudosgeeniekspressioista tai geenien vuorovaikutuksia kuvaavasta hyperverkosta sekä personoitujen hakutulosten tuottamisesta käyttäjien hakujen ja klikkausten perusteella. Tämän työn päämääränä on määrittää, milloin todellinen klusterirakenne voidaan päätellä datasta. Täsmällisemmin, olettamalla tilastollinen malli (tensorilohkomalli), kuinka harvaa data voi olla, jotta todelliset klusterit voidaan päätellä nopealla algoritmilla suurella todennäköisyydellä. Ongelman ratkaisemiseksi työssä kehitetään spektrinen klusterointialgoritmi, todistetaan matemaattisesti sen olevan heikosti tarkentuva ja demonstroidaan tarkentuvuus numeerisilla simulaatioilla. Heikon tarkentuvuuden todistamiseksi työssä kehitetään satunnaismatriisien keskittymisepäyhtälöiden teoriaa. Heikon tarkentuvuuden tulokset parantavat olemassaolevia tuloksia.

Description

Supervisor

Leskelä, Lasse

Thesis advisor

Leskelä, Lasse

Keywords

hypergraph, tensor block model, concentration inequality, random matrix, weak consistency, spectral clustering

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202501121151

Collections

[dipl] Perustieteiden korkeakoulu / SCI