Project topics and materials
Get Complete Project Material File(s) Now! »
The case of hypergraph Laplacians
In this section, we propose to review the case of hypergraphs and show that the di erent hypergraph Laplacians that have been proposed in recent years are not more expressive than graph Laplacians. First, let us recall basic notions about hypergraphs.
Hypergraphs have been introduced by Berge (1989) in order to model prob-lems where relationships are no longer binary, that is when they involve more than two individuals. Hypergraphs have been used for instance in bioinfor-matics (Klamt et al. 2009), computer vision (Zhang et al. 1993) and natural language processing (Cai and Strube 2010). In the hypergraph model, a hyperedge is simply a set of nodes. The key idea is to encode the fact that several nodes share a common property. An example is given in Figure 2.13 where nodes are documents described by two features (type of document and language). We create two hyperedges: the rst one t1; 2; 3u contains all the documents written in French while the second one t2; 3; 4u contains all the reports. Note that we do not create any additional hyperedge since there is only one document written in English and one book in the example dataset. A hypergraph is formally de ned as a set of nodes N together with a set of hyperedges E. Each hyperedge e P E is a set of nodes and is embedded with a positive weight wpeq P R . As said above, several attempts have been made to de ne Laplacian oper-ators for hypergraphs. The most popular ones are the Laplacians B from Bolla (1993), R from Rodr guez (2003) and ZHS from Zhou et al. (2006). We have the following result: Proposition 9. Let us consider a hypergraph on a nodeset N and the Lapla-cian pairs p R; Nq, p B; Nq and p ZHS; Nq. We can show that R and B are equal to graph Laplacian using an adequate expansion. Moreover, we can nd a normalized graph Laplacian s that generalizes ZHS according to De nition 6. Proof. The proof of this proposition is partly based on Agarwal et al. (2006). First note that hypergraphs can be approximated by graphs using two main constructions: The clique expansion, where each hyperedge e is replaced by an unifor-mally weighted clique. When the pair is contained in multiple hyper-edges, the nal weight is either the average or the sum of the weights corresponding to each clique. The star expansion, where we introduce a new node for each hyperedge e P E. Each of the original nodes of e is linked to the new node through an edge. The star expansion is denoted by hs pN Y Ns; Esq where Ns is the set of additional nodes.
Paths and signed components
In order to de ne a non-ambiguous notion of path, we base our analysis on the pairwise weight matrix de ned in Section 3.1.1 . De ned as a sum over all the hyperedges, the pairwise weight allows to take into account all the information between a given pair of nodes. Moreover, it is fully consistent with the equivalence relation since two equivalent hypernode graphs share the same pairwise weight matrix (see Corollary 1). De nition 8. Let h pN; Hq be a hypernode graph with pairwise weight matrix W . A path between two nodes i and j is a sequence of nodes i1 i; i2; : : : ; ip 1; ip j such that Wik;ik 1 0 for 1 ⁄ k p. When the hypernode graph is a graph, the de nition coincides with the de nition of path in undirected graphs since W is equal to the adjacency matrix. Moreover, since two equivalent hypernode graphs share the same pairwise weight matrix, this notion of path is consistent with the equivalence relation. Consequently, the notion of path presented in De nition 8 satis es the two requirements (a) and (b). We de ne a signed component to be a maximal connected set, i.e., a maximal set of nodes such that there exists a path between any two nodes. By de nition, two signed components have necessarily a null intersection. In the graph case, this de nition coincides with the classic notion of connected components presented in Section 2.1.1. With these de nitions, h5 has two signed components C1 t1; 2u and C2 t3; 4u. Indeed, there is no path between 1 and 3, 1 and 4, 2 and 3 or 2 and 4.
As in the graph case, we now show that the indicator function of a signed component nullify the smoothness measure . Consequently, we can de ne independently a constant label for each signed component, without modify-ing the global smoothness. Proposition 14. Let C1; : : : ; C‘ be the ‘ signed components of a hypernode graph h pN; Hq. Let be the smoothness measure of h. We have
Spanp1C1 ; : : : ; 1C‘ q Nullp q : (3.4).
Independent components and strong connectivity
Let us consider throughout this section a hypernode graph h pN; Hq and its Laplacian matrix . As announced above, our objective is to study the sets of nodes whose indicator function nullify the smoothness measure . As shown in Proposition 14, this is in particular the case for all the signed components (and all the possible unions of signed components). We show in the following that many other sets satisfy this property. We call these sets the independent components of the hypernode graph. We start by de ning the notion of node independency. A node i in N is said to be independent of S N if i R S and if the contribution of the nodes in S to the degree of i is 0, i.e.if ‚ Wi;j 0 : j PS. Proposition 15. Let us consider a set of nodes S N. The indicator function 1S is in Nullp q if and only if the following conditions are satis ed:
1. All the nodes of S are independent of S
2. All the nodes of S are independent of S
Table of contents :
1 Introduction
2 Hypernode graphs
2.1 Undirected Graphs and Spectral Framework
2.1.1 Graphs and Laplacians
2.1.2 Graph kernels and distances
2.2 Hypernode graphs
2.2.1 Model denition
2.2.2 Hypernode graph Laplacians
2.2.3 Equivalent hypernode graphs
2.3 Expressiveness of the Laplacian framework
2.3.1 The case of hypernode graphs
2.3.2 The case of hypergraph Laplacians
2.4 Conclusion
3 Properties of hypernode graphs
3.1 Hypernode graphs, graphs and signed graphs
3.1.1 Pairwise Weight Matrix and Laplacians
3.1.2 Signed graph reduction
3.2 Paths and components in hypernode graphs
3.2.1 Paths and signed components
3.2.2 Independent components and strong connectivity
3.3 Hypernode graph kernels and distances
3.3.1 Denition and main properties
3.3.2 Diusion on hypernode graphs and relations with d2
3.3.3 The transition matrix P D1W
3.4 Conclusion
4 Skill rating with hypernode graphs
4.1 Skill rating in multiplayer games
4.1.1 Notations and team additive model
4.1.2 The Elo rating system
4.1.3 The TrueSkill rating system
4.2 Learning skill ratings with hypernode graphs
4.2.1 Modeling Games with Hypernode Graphs
4.2.2 Regularizing the hypernode graph
4.2.3 Inferring Skill Ratings and Predicting Game Outcomes
4.3 Experiments
4.3.1 Tennis Singles
4.3.2 Tennis Doubles
4.3.3 Xbox Title Halo2
4.4 Conclusion
5 Perspectives and open problems
5.1 Cuts in hypernode graphs
5.1.1 Cuts in undirected graphs
5.1.2 Cuts and hypernode graphs
5.1.3 The Min-Cut problem on hypernode graphs
5.1.4 Relation with the signed graph cuts
5.1.5 Algorithmical perspectives and partial results
5.2 Directed hypernode graphs
5.3 An algebraical interpretation of hypernode graphs
5.3.1 The classes of Graph Kernels and Graph Laplacians .
5.3.2 The class of Hypernode graph Laplacians
5.3.3 A convex hull conjecture and an intermediate class Fpnq
5.3.4 A Riemanian geometry for strongly connected hypernode graphs
6 Conclusion
