Spectral Hypergraph Partitioning and Relative Entropy

Language
en
Document Type
Doctoral Thesis
Issue Date
2015-04-08
Issue Year
2015
Authors
Gmeiner, Peter
Editor
Abstract

This thesis is about the information-theoretic difference between hypergraphs and undirected graphs, which arises in spectral bisections of these objects. We also investigate the effect of general deletion and contraction operations of hyperedges in a hypergraph from different points of view. We restrict ourselves to a wellstructured class of hypergraphs, namely, simplicial complexes. This allows us to define higher-dimensional Laplace operators, which generalize graph Laplacians in a natural way. Similarly, isoperimetric numbers for graphs - combinatorial Cheeger constants - can be extended to simplicial complexes. We suggest a new isoperimetric quantity for simplicial complexes, based on minimal interaction loss, and show an isoperimetric inequality for them. The Kullback-Leibler divergence, also known as relative entropy, is used to consider the difference between simplicial complexes and undirected graphs from an information-theoretic point of view. By means of hierarchical exponential families, which are naturally induced by simplicial complexes, we define a relative entropy between simplicial complexes. For a systematic investigation of this relative entropy we consider its effect under certain operations, like deletion and contraction of simplices in a simplicial complex. With a detailed analysis of marginalized exponential families and with already known decomposition formulas for the Kullback-Leibler divergence, we succeed to identify a class of operations on simplicial complexes for which we can deduce many exact expressions and inequalities for the relative entropy. For more general operations on simplicial complexes we can show an upper bound for the relative entropy. Through an explicit construction of probability distributions we are able to state lower bounds of the relative entropy between separated and non separated simplicial complexes. Based on the observation from spectral graph theory, in which the smallest nontrivial eigenvalue of the Laplacian is related to a combinatorial Cheeger constant, we show a connection of this eigenvalue to scaled relative entropies. For this purpose, an information-theoretic Cheeger constant is introduced, which is related to a combinatorial Cheeger constant. This allows us to derive information-theoretic Cheeger inequalities for undirected graphs and simplicial complexes. In particular, it is possible to see the information-theoretic difference between undirected graphs and simplicial complexes by means of an entropy gap.

Abstract

Die vorliegende Arbeit handelt vom informationstheoretischen Unterschied zwischen Hypergraphen und ungerichteten Graphen, der sich bei spektraler Bisektion dieser Objekte zeigt. Es werden auch die Auswirkungen allgemeinerer Lösch- und Kontraktionsoperationen von Hyperkanten in einem Hypergraphen von verschiedenen anderen Blickwinkeln aus betrachtet. In der Arbeit schränken wir uns auf eine Klasse von Hypergraphen ein, die strukturell etwas reichhaltiger ist: Simplizialkomplexe. Diese ermöglichen es höherdimensionale Laplace-Operatoren zu definieren, welche in natürlicher Weise Laplace-Operatoren auf ungerichteten Graphen verallgemeinern. Ebenso können isoperimetrische Größen für Graphen - kombinatorische Cheeger- Konstanten - auf Simplizialkomplexe erweitert werden. Es wird eine neue isoperimetrische Größe für Simplizialkomplexe, basierend auf minimalem Interaktionsverlust, vorgeschlagen und eine entsprechende isoperimetrische Ungleichung für diese Größe gezeigt. Die Kullback-Leibler Divergenz, auch bekannt als relative Entropie, wird verwendet um den Unterschied zwischen Simplizialkomplexen und ungerichteten Graphen aus informationstheoretischer Sicht zu betrachten. Mittels hierarchischer Exponentialfamilien, die in natürlicher Weise von Simplizialkomplexen induziert werden, definieren wir eine relative Entropie zwischen Simplizialkomplexen. Zur systematischen Untersuchung dieser relativen Entropie betrachten wir deren Verhalten bei der Ausführung bestimmter Operationen, wie Lösch- und Kontraktionsoperationen von Simplizes, auf Simplizialkomplexen. Durch eine genaue Analyse von marginalisierten Exponentialfamilien und der Verwendung von bereits bekannten Zerlegungsformeln für die Kullback-Leibler Divergenz, gelingt es eine Klasse von Operationen auf Simplizialkomplexen zu identifizieren, für welche sich zahlreiche exakte Ausdrücke und Ungleichungen der relativen Entropie herleiten lassen. Für allgemeinere Operationen auf Simplizialkomplexen wird eine obere Schranke der relativen Entropie gezeigt. Mittels einer expliziten Konstruktion von Wahrscheinlichkeitsverteilungen lassen sich untere Schranken der relativen Entropie zwischen getrennten und nicht getrennten Simplizialkomplexen angeben. Basierend auf der Beobachtung aus der spektralen Graphentheorie, in welcher der kleinste nichttriviale Eigenwert des Laplace-Operators mit einer kombinatorischen Cheeger-Konstante in Relation gebracht wird, zeigen wir einen Zusammenhang dieses Eigenwertes mit skalierten relativen Entropiegrößen. Dazu wird eine informationstheoretische Cheeger-Konstante eingeführt, welche wir mit einer kombinatorischen Cheeger-Konstante in Verbindung bringen. Es lassen sich dann informationstheoretische Cheeger-Ungleichungen für ungerichtete Graphen und für Simplizialkomplexe herleiten. Insbesondere ist es möglich durch eine sogenannte Entropielücke den informationstheoretischen Unterschied zwischen Simplizialkomplexen und ungerichteten Graphen zu sehen.

DOI
Faculties & Collections
Zugehörige ORCIDs