A local geometry of hyperedges in hypergraphs, and its applications to social networks

One of the challenges in the modern age is to classify data arising from many resources; for example, following the rapid developments of several areas in mathematics, a large number of publications in mathematics creates a tremendous amount of data, which signifies useful information such as relationship (or collaborations) among authors and their publications, and their influences on development of mathematics. It is often the case that analyzing such data is not straightforward, and very difficult task because of the extremely fast growth of relations among data, and of data itself.

One of the main problems in machine learning is weight (respectively, label) prediction problem in which each instance is associated with a set of weights (respectively, labels), and the aim is to propose predictive models for predicting weights (respectively, labels) for unobserved data. These learning problem have important applications in many areas such as protein function classification [4], text categorization [17], and semantic scene classification [2], to cite a few. For networks which can be modeled as graphs, many approaches to prediction problem were proposed (see, for example, [7], [5], [6], [13], [14], [15]).

In real world datasets, for example, in social networks, it often occurs that higher order relations among data points are present which can not be captured because graph modeling of such datasets only signifies binary relation. So it is natural to consider weight (respectively, label) prediction problem for a generalization of graphs–hypergraphs. Recall that a hypergraph $X$ is a pair $(\mathcal{V}(X),\mathcal{E}(X))$, where $\mathcal{V}(X)$ is the set of data points (called vertices of $X$), and $\mathcal{E}(X)$ is a subset of the power set of $\mathcal{V}(X)$ which represents higher order relations among data points. Each element in $\mathcal{E}(X)$ is called a hyperedge. Since each hyperedge can consist of a collection of data points, it captures the higher order correlation information among these data points. Recent trends in learning problem have been focused on hypergraph datasets (see, for example, [1], [16])

In this paper, we propose a geometric approach for studying weight (respectively, label) prediction problem on hypergraph data which will be used to apply for analyzing networks arising from sociology. Traditionally for datasets which can be modeled as graphs, there is a standard method called $k$ nearest neighbors which applies to weight (respectively, label) prediction problem. The classical $k$ nearest neighbors method relies on the Euclidean metrics. In contrast with many traditionally geometric approaches based on the Euclidean metrics (or distances), we propose a new methodology of nearest neighbors in hypergraphs, using metrics modulo equivalence relations which is a weaker notion than that of usual metrics, but it seems natural to use such metrics in learning data. Equivalence relation signifies the correlation among data points, and a metric modulo such an equivalence relation signifies how much different among data points are, with respect to such correlation information. In this work, we suggest that equivalence relation is a natural mathematical notion for modeling correlation information in datasets, and that metrics modulo equivalence relations are more suitable for learning correlation in datasets.

The structure of our paper is as follows. In Subsection 2.1, we introduce a notion of metric spaces with respect to equivalence relations. In Subsection 2.2, based on the notion of metric spaces with respect to equivalence relation, we propose our methodology for studying weight (respectively, label) prediction problem. In Subsection 2.3, we construct a class of metrics modulo equivalence relations on the set of hyperedges of a hypergraph which can be combined with the methodology proposed in Subsection 2.2 for studying prediction problems. In Section 3, we apply our methodology to real world datasets from sociology, and report our experimental results.

In weight (respectively, label) prediction problem, one is given a dataset consisting of data points $x_{1},\ldots,x_{n}$ such that there is a subset, say $\{x_{i_{1}},\ldots,x_{i_{k}}\}$, each of whose element is associated to a weight (respectively, label). The aim is to propose a predictive model for predicting the weight (respectively, label) of each element in the set $\{x_{1},\ldots,x_{n}\}\setminus\{x_{i_{1}},\ldots,x_{i_{k}}\}$. In this paper, we propose a new approach using insights from metric geometry to weight (respectively, label) prediction problem for datasets which can be modeled as hypergraphs.

A hypergraph $X$ is a pair $(\mathcal{V}(X),\mathcal{E}(X))$, where $\mathcal{V}(X)$ is the set of points, called vertices of $X$, and $\mathcal{E}(X)$ is a subset of the power set of $\mathcal{V}(X)$, each of whose elements is called a hyperedge of $X$. Each hyperedge $\mathfrak{e}$ is a subset of $\mathcal{V}(X)$. If $\mathfrak{e}$ has exactly $m$ elements, $\mathfrak{e}$ is called an $m$-hyperedge of $X$. In this paper, we are interested in weight (respectively, label) prediction problem for hypergraphs, and so the following notion is natural for modeling such datasets.

In classical weight (respectively, label) prediction problem for datasets which can be modeled as graphs, one can apply the classical $k$ nearest neighbors method. The main idea of the classical $k$ nearest neighbors method is that a dataset $X=\{x_{1},\ldots,x_{n}\}$ is equipped with a Euclidean metric (or distance), say $d$. For each $x\in X$, let $x_{i_{1}},\ldots,x_{i_{k}}$ be the $k$ nearest points from $X$ to $x$ with respect to the metric $d$ such that

Then the $k$ nearest neighbors method expect that the weight (respectively, label) of $x$ should be in proximity with the $x_{i_{m}}$ for $1\leq m\leq k$.

Our main contribution in this paper is to introduce modified $k$ nearest neighbors methods for learning hypergraphs, especially for weight (respectively, label) prediction problem. In order to do that, we introduce a class of metrics modulo equivalence relations on the set of hyperedges in a hypergraph. Note that in contrast with the usual metric, a metric $d$ modulo an equivalence relation $\cong$ allows that $d(\mathfrak{e},\mathfrak{f})=0$ as long as $\mathfrak{e}\cong\mathfrak{f}$ (which means that $a$ is equivalent to $b$ with respect to certain properties, for example, similar weights or labels.) Thus such a metric is more suitable for studying weight (respectively, label) prediction problem since two distinct points in a dataset may have the same weight (respectively, label). In this case, the equivalence relation $\cong$ signifies the relation that certain distinct points in datasets share similar properties with respect to weight (respectively, label) map, and $d(\mathfrak{e},\mathfrak{f})=0$ encodes the information that the points $\mathfrak{e},\mathfrak{f}$ are expected to have the same weight (respectively, label).

We first introduce a notion of metric spaces modulo equivalence relations which is used in many places in this paper.

In this section, we apply the methodology proposed in Subsection 2.2 combined with the class of metrics in Subsection 2.3 to construct predictive models for weight (respectively, label) prediction problem for hypergraph datasets.

We are not aware of any hypergraph datasets containing weights (respectively, labels) of hyperedges. So in our experimental analysis, we use datasets of weighted bipartite networks, and transform them into hypergraphs.

Let $G=(U,V,E)$ be a bipartite network, where $U$ and $V$ are disjoint sets of vertices, $E$ is the set of edges. For each $e\in E$, $e$ is uniquely formed by a pair of vertices $(u,v)$ where $u\in U$ and $v\in V$. A hypergraph $X=(\mathcal{V}(X),\mathcal{E}(X))$ induced by the bipartite graph $G$ is defined as follows.

• (i)

  By exchanging the notation between $U$ and $V$, one, without loss of generality, lets $\mathcal{V}(X)=U$, that is, the set of vertices in $X$ is defined to be one set of vertices in $G$.

• (ii)

  For each $v\in V$, let $\mathfrak{e}_{v}$ denotes the set of all vertices $u$ in $U$ such that $(u,v)\in E$. We define the set of hyperedges of $X$ as

  $\displaystyle\mathcal{E}(X)=\{\mathfrak{e}_{v}\;|\;v\in V\}.$

  In this case, each hyperedge $\mathfrak{e}$ in $\mathcal{E}(X)$ uniquely corresponds to a vertex in $V$. And thus $\mathcal{E}(X)$ is in bijection with $V$.

In our experimental analysis, we use two real-world datasets from social networks which are Epinions network and MovieLens network. They are both bipartite rating networks where one set of vertices are users and the other set of vertices are items. The weight of an edge presents a rating score from a user to an item. In the hypergraphs induced by these two networks, the set of vertices $\mathcal{V}(X)$ is the set of users, then each hyperedge is formed by the set of all users that rate the same item. Therefore, each hyperedge corresponds to an item in the bipartite graph. An example of transforming a bipartite graph into a hypergraph is shown in Figure 2 and 3. Descriptions of the two datasets are as follows.

• •

  Epinions. This dataset was collected by Paola Massa in a $5$-week crawl (Novemeber/December 2003) from the Epinions.com Website (see the dataset at http://www.trustlet.orgdownloaded_epinions.html )(see [9]). In Epinions, the vertices are users and reviews, each user rates the helpfullness of a review on a $1-5$ scale, where $1$ means totally not helpful and $5$ means totally helpful.

• •

  MovieLens. This dataset contains movie ratings collected from https://movielens.org/ (see [10]). In this dataset, the vertices are users and movies, each edge connects a user with a movie and represents a rating score. The rating scores are integers from $0$ to $5$.

Table 3 contains descriptions of hypergraphs used in our computation. The weights of hyperedges are computed using the edge weights from bipartite network datasets and the notion of goodness introduced in [7]. In both of the two hypergraphs, each hyperedge corresponds to an item in the bipartite graphs, the weight of each hyperedge, which is computed using goodness, indicates how good an item is. In order to associate each hyperedge with a label, we divide the range of weights, which is a closed interval from minimum value of weights to maximum value of weights, into $q$ intervals with equal length. Then the label of a hyperedge is $i$ if its weight belongs to the $i$th interval. The set of labels are integers from $1$ to $q$.

According to the definitions of neighborhoods, one needs to select tuning parameters $h$ for $\mathcal{N}_{h,\mathcal{E}_{0}(X),+\infty}(\mathfrak{e})$, and $\mathcal{N}_{h,\mathcal{E}_{0}(X),\epsilon}(\mathfrak{e})$. In our computation, we set the value of $h$ based on the neighborhood of each hyperedge. For each $\mathfrak{e}\in\mathcal{E}$ , $h$ equals to the standard deviation of weights of all hyperedges that belong to the neighborhood of $\mathfrak{e}$. The choices of $k$ for $k$NN are integers from $1$ to $20$, and the values of $\epsilon$ are set to be $\frac{5}{3},\frac{4}{3},1,\frac{2}{3}$, or $\frac{1}{2}$. The performances of weight predictions are evaluated using mean of absolute error (MAE) and root mean squared error (RMSE). The performances of label predictions are evaluated using error rate which is computed by the proportion of incorrect prediction. We select the values of $k$ and $\epsilon$ that correspond to the smallest MAE or error rate.

Figures 4 and 5 present the results of predicting weights of hyperedges using Epinions dataset. In this example, the smallest MAE and RMSE values are obtained by setting $\epsilon$ equal to $\frac{5}{3}$. In general, using the second type of neighborhood ($\mathcal{N}_{h,\mathcal{E}_{0}(X),\epsilon}(\mathfrak{e})$) leads to a better prediction results than using the first type of neighborhood ($\mathcal{N}_{h,\mathcal{E}_{0}(X),+\infty}(\mathfrak{e})$).

Tables 4 and 5 present the results of predicting weights of hyperedges using modified $k$NN method and embedded $k$NN method. In our experimental analysis, for simplicity, we set $q=2$ for the computation of $T_{\mathcal{E}(X)}(\mathfrak{e})=(\eta_{1}(\mathcal{N}_{\text{edge}}(\mathfrak{e})),\ldots,\eta_{q}(\mathcal{N}_{\text{edge}}(\mathfrak{e})))$ in the embedded $k$NN method, where $\mathcal{N}_{\text{edge}}(\mathfrak{e})$ is either type I or type II neighborhood of $\mathfrak{e}$. Each cell reports a pair of numbers (mean of absolute error (MAE), root mean squared error (RMSE)).

Table 6 presents the error rates of predicting labels of hyperedges using modified $k$NN methods. Table 7 presents the error rates of predicting labels of hyperedges using embedded $k$NN methods.