Biological and cellular systems are often modeled as graphs in which vertices represent objects of interest (genes, proteins, drugs) and edges represent relational ties among these objects (binds-to, interacts-with, regulates). This approach has been highly successful owing to the theory, methodology and software that support analysis and learning on graphs. Graphs, however, often suffer from information loss when modeling physical systems due to their inability to accurately represent multiobject relationships. Hypergraphs, a generalization of graphs, provide a framework to mitigate information loss and unify disparate graph-based methodologies. In this paper, we present a hypergraph-based approach for modeling physical systems and formulate vertex classification, edge classification and link prediction problems on (hyper)graphs as instances of vertex classification on (extended, dual) hypergraphs in a semi-supervised setting. We introduce a novel kernel method on vertex- and edge-labeled (colored) hypergraphs for analysis and learning. The method is based on exact and inexact (via hypergraph edit distances) enumeration of small simple hypergraphs, referred to as hypergraphlets, rooted at a vertex of interest. We extensively evaluate this method and show its potential use in a positive-unlabeled setting to estimate the number of missing and false positive links in protein-protein interaction networks.
Under a supervised learning framework, Wachman and Khardon @cite_50 propose random walk-based hypergraph kernels on ordered hypergraphs, while Sun @cite_42 present a hypergraph spectral learning formulation for multi-label classification. More recently, Bai @cite_52 introduced a hypergraph kernel that transforms a hypergraph into a directed line graph and computes a Weisfeiler-Lehman isomorphism test between directed graphs. A major drawback of most such approaches is that no graph representation fully captures the hypergraph structure. For instance, Ihler @cite_56 have shown that it is impossible to have an exact representation of a hypergraph via a graph while still retaining its cut properties. Therefore, there is a need for a robust hypergraph-based methodology for learning directly on hypergraph data.
@cite_42 @cite_52 @cite_50 @cite_56
1976617626 2005683516 1973113780
In this paper, we present a hyper graph kernel computed using substructure isomorphism tests. Measuring the isomorphisms between hyper graphs straightforwardly tends to be elusive since a hyper graph may exhibit varying relational orders. We thus transform a hyper graph into a directed line graph. This not only accurately reflects the multiple relationships exhibited by the hyper graph but is also easier to manipulate isomorphism tests. To locate the isomorphisms between hyper graphs through their directed line graphs, we propose a new directed Weisfeiler-Lehman isomorphism test for directed graphs. The new isomorphism test precisely reflects the structure of the directed edges. By identifying the isomorphic substructures of directed graphs, the hyper graph kernel for a pair of hyper graphs is computed by counting the number of pair wise isomorphic substructures from their directed line graphs. We show that our kernel limits tottering that arises in the existing walk and sub tree based (hyper)graph kernels. Experiments on challenging (hyper)graph datasets demonstrate the effectiveness of our kernel. The paper presents a kernel for learning from ordered hypergraphs, a formalization that captures relational data as used in Inductive Logic Programming (ILP). The kernel generalizes previous approaches to graph kernels in calculating similarity based on walks in the hypergraph. Experiments on challenging chemical datasets demonstrate that the kernel outperforms existing ILP methods, and is competitive with state-of-the-art graph kernels. The experiments also demonstrate that the encoding of graph data can affect performance dramatically, a fact that can be useful beyond kernel methods. Abstract An elegant and general way to apply graph partitioning algorithms to hypergraphs would be to model hypergraphs by graphs and apply the graph algorithms to these models. Of course such models have to simulate the given hypergraphs with respect to their cut properties. An edge-weighted graph ( V , E ) is a cut-model for an edge-weighted hypergraph ( V , H ) if the weight of the edges cut by any bipartition of V in the graph is the same as the weight of the hyperedges cut by the same bipartition in the hypergraph. We show that there is no cut-model in general. Next we examine whether the addition of dummy vertices helps: An edge-weighted graph ( V ∪ D , E ) is a mincut-model for an edge-weighted hypergraph ( V, H ) if the weight of the hyperedges cut by a bipartition of the hypergraphs vertices is the same as the weight of a minimum cut separating the two parts in the graph. We construct such models using positive and negative weights. On the other hand, we show that there is no mincut-model in general if only positive weights are allowed.