A Spectral Framework for a Class of Undirected Hypergraphs

Ricatte, Thomas; Garriga, Gemma; Gilleron, Rémi; Tommasi, Marc

Document type :

Rapport de recherche

Title :

A Spectral Framework for a Class of Undirected Hypergraphs

Author(s) :

Ricatte, Thomas [Auteur]
Machine Learning in Information Networks [MAGNET]
Garriga, Gemma [Auteur]
Machine Learning in Information Networks [MAGNET]
Gilleron, Rémi [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Machine Learning in Information Networks [MAGNET]
Tommasi, Marc [Auteur]

Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Machine Learning in Information Networks [MAGNET]

Publication date :

2013-12-05

English keyword(s) :

Graph Spectral Theory
Undirected Hypergraphs
Graph Laplacian
Graph Kernel
Resistance Distance

HAL domain(s) :

Informatique [cs]/Intelligence artificielle [cs.AI]

English abstract : [en]

We extend the graph spectral framework to a new class of undirected hypergraphs with bipartite hyperedges. A bipartite hyperedge is a pair of disjoint sets of nodes in which every node is associated with a weight. A bipartite ...
Show more >We extend the graph spectral framework to a new class of undirected hypergraphs with bipartite hyperedges. A bipartite hyperedge is a pair of disjoint sets of nodes in which every node is associated with a weight. A bipartite hyperedge can be viewed as a relation between two teams of nodes in which every node has a weighted contribution to its team. Undirected hypergraphs generalize over undirected graphs. Consistently with the case of graphs, we define the notions of hypergraph gradient, hypergraph Laplacian, and hypergraph kernel as the Moore-Penrose pseudoinverse of a hypergraph Laplacian. Therefore, smooth labeling of (teams of) nodes and hypergraph regularization methods can be performed. Contrary to the graph case, we show that the class of hypergraph Laplacians is closed by the pseudoinverse operation (thus it is also the class of hypergraphs kernels), and is closed by convex linear combination. Closure properties allow us to define (hyper)graph combinations and operations while keeping a hypergraph interpretation of the result. We exhibit a subclass of signed graphs that can be associated with hypergraphs in a constructive way. A hypergraph and its associated signed graph have the same Laplacian. This property allows us to define a distance between nodes in undirected hypergraphs as well as in the subclass of signed graphs. The distance coincides with the usual definition of commute-time distance when the equivalent signed graph turns out to be a graph. We claim that undirected hypergraphs open the way to solve new learning tasks and model new problems based on set similarity or dominance. We are currently exploring applications for modeling games between teams and for graph summarization.Show less >

Language :

Anglais

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

https://hal.inria.fr/hal-00914286v2/document
Open access
Access the document

https://hal.inria.fr/hal-00914286v2/document
Open access
Access the document

https://hal.inria.fr/hal-00914286v2/document
Open access
Access the document

A Spectral Framework for a Class of ... BibTeX CSV Excel RIS

Files

A Spectral Framework for a Class of ...

BibTeX

CSV

Excel

RIS