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.
Document type :
Reports
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-00914286
Contributor : Team Magnet <>
Submitted on : Monday, February 3, 2014 - 3:57:03 PM
Last modification on : Thursday, February 21, 2019 - 10:52:55 AM
Long-term archiving on : Sunday, May 4, 2014 - 6:20:32 AM

Files

main.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

597

Files downloads

595