A Spectral Framework for a Class of Undirected Hypergraphs

Thomas Ricatte 1 Gemma Garriga 1 Rémi Gilleron 1, 2 Marc Tommasi 1, 2
1 MAGNET - Machine Learning in Information Networks
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : 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.
Type de document :
Rapport
[Research Report] 2013
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00914286
Contributeur : Team Magnet <>
Soumis le : lundi 3 février 2014 - 15:57:03
Dernière modification le : vendredi 16 septembre 2016 - 15:16:42
Document(s) archivé(s) le : dimanche 4 mai 2014 - 06:20:32

Fichiers

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00914286, version 2

Citation

Thomas Ricatte, Gemma Garriga, Rémi Gilleron, Marc Tommasi. A Spectral Framework for a Class of Undirected Hypergraphs. [Research Report] 2013. 〈hal-00914286v2〉

Partager

Métriques

Consultations de la notice

486

Téléchargements de fichiers

492