Entities in world are connected by various relations. We can discover the underlying patterns among entities by studying their relations. In our research of relational learning, we examine one fundamental relation -- co-occurrence.
Co-occurrence relations can be found in many applications. These relations can be modeled as a hypergraph. Entities are represented by the vertices in the hypergraph, and the co-occurrences are represented by the hyperedges. The following hypergraph encodes the co-occurrence relations among students who take the same course. Can you tell which students are studying computer science and which are in the humanities?
We propose a new hypergraph transformation called hyperedge expansion (HE expansion). Compared to the existing works (e.g. star expansion or normalized hypergraph cut), the learning results with HE expansion would be less sensitive to the vertex distribution among clusters, especially in the case that cluster sizes are unbalanced, or a hyperedge could contain vertices from more than one clusters.
An example of 2-dimensional embeddings from hyperedge expansion and state-of-the-art (the hypergraph consists of many animals which share some attributes):
Software: the Hypergraph Analysis Toolbox (HAT) is a set of Matlab functions that could help to analyze a hypergraph. With HAT, you can easily create a hypergraph, pre-process a hypergraph, run hypergraph clustering/classification algorithms in batch mode, print/visualize the results, and run recommender system algorithms with the hypergraph representation. Please use this link to download the current version of HAT (including demos): download HAT 0.2.0.
Li Pu and Boi Faltings, Hypergraph Learning with Hyperedge Expansion, ECML-PKDD, 2012 [pdf] [Matlab code, for Java implementation, please contact Li Pu]