Hypernode Graphs for Spectral Learning on Binary Relations over Sets

Thomas Ricatte 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
2 LIFL - Laboratoire d'Informatique Fondamentale de Lille
Abstract : We introduce hypernode graphs as weighted binary relations between sets of nodes: a hypernode is a set of nodes, a hyperedge is a pair of hypernodes, and each node in a hypernode of a hyperedge is given a non negative weight that represents the node contribution to the relation. Hypernode graphs model binary relations between sets of individuals while allowing to reason at the level of individuals. We present a spectral theory for hypernode graphs that allows us to introduce an unnormalized Laplacian and a smoothness semi-norm. In this framework, we are able to extend spectral graph learning algorithms to the case of hypernode graphs. We show that hypernode graphs are a proper extension of graphs from the expressive power point of view and from the spectral analysis point of view. Therefore hypernode graphs allow to model higher order relations whereas it is not true for hypergraphs as shown in~\cite{Agarwal2006}. In order to prove the potential of the model, we represent multiple players games with hypernode graphs and introduce a novel method to infer skill ratings from game outcomes. We show that spectral learning algorithms over hypernode graphs obtain competitive results with skill ratings specialized algorithms such as Elo duelling and TrueSkill.
Keywords : Graphs Hypergraphs Semi-supervised Learning Multiple Players Games
Type de document :
Communication dans un congrès
ECML/PKDD - 7th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Sep 2014, Nancy, France. 2014, Machine Learning and Knowledge Discovery in Databases
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01017025
Contributeur : Team Magnet <>
Soumis le : mardi 1 juillet 2014 - 16:17:59
Dernière modification le : jeudi 11 janvier 2018 - 06:25:27
Document(s) archivé(s) le : mercredi 1 octobre 2014 - 13:01:02

Fichier

Hypernode_Graphs_for_Spectral_...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01017025, version 1

Collections

INRIA | UNIV-LILLE3 | CRISTAL | CRISTAL-MAGNET

Citation

Thomas Ricatte, Rémi Gilleron, Marc Tommasi. Hypernode Graphs for Spectral Learning on Binary Relations over Sets. ECML/PKDD - 7th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Sep 2014, Nancy, France. 2014, Machine Learning and Knowledge Discovery in Databases. 〈hal-01017025〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

743

Téléchargements de fichiers

664

Contact


archive-ouverte@inria.fr