C3MM: Clique-Closure based Hyperlink Prediction

1 Introduction

Relations in nature, more often than not, exist between a set of entities rather than a pair thereof. For a lossless representation, complex structures such as hypergraphs [Berge, 1984] are used, wherein hyperlinks or hyperedges are used to represent higher-order relations. Hyperlink prediction refers to predicting future/missing hyperlinks in a given hypergraph [Xu et al., 2013; Zhang et al., 2018; Benson et al., 2018]. We draw inspirations from recent literature and the existing state-of-the-art, i.e., Coordinated Matrix Minimization (CMM) [Zhang et al., 2018], to solve the problem of predicting arbitrary-sized hyperlinks in networks. We first formulate a Clique-Closure Hypothesis (CCH), which can be summarized as follows: Hyperlinks in a network are more likely to be formed from closures of cliques (and near-cliques) rather than those of non-cliques. In simpler terms, we hypothesize that for a given hyperlink, prior to its first occurrence, its incident nodes should have had more interactions than a set of arbitrary number of nodes usually does. I.e., we expect every hyperlink to have evolved gradually, rather than having spontaneously "sprung-up". Consider the example shown in Figure 1, where it could be noted how at any t = ti, smaller hyperlinks from the past (dotted) combine together to form larger ones (solid) in the present.

∗Contact Author

We first test CCH on real datasets, and then use it for hyperlink prediction via a method we term "Clique-Closure based Coordinated Matrix Minimization" (C3MM). We ingest CCH into the objective function of CMM to get C3MM, and then solve it in a similar fashion. Choosing datasets from different domains, we note significant improvements over CMM. Major improvements come from the fact that C3MM gives a chance to those hyperlinks that could explain existing relations.

1.1 Our Contributions

1. We formulate and test a clique-closure hypothesis (CCH) for hypergraph network evolution. As a result, we provide novel insights into hyperlink evolution.
2. We provide a hyperlink prediction algorithm C3MM that significantly improves upon CMM.
3. We extend hyperlink prediction for hyperlinks of arbitrary size and to multiple domains.

2 Preliminaries and Notation

We define basic notations in Table 1 for easy look-up. Hyperlink prediction, just like link prediction, could be formulated as a binary classification problem where positive and negative classes correspond to hyperlink and non-hyperlink respectively. For our experiments, we first partition the set of hyperlinks into two parts, namely observed and unobserved hyperlinks (Fobs and Funobs). For temporal hypergraphs, the set of hyperlinks is partitioned chronologically whereas for non-temporal hypergraphs, it is done randomly.

Next, we pick non-hyperlinks through under-sampling of the negative class due to extreme class imbalance (i.e., O(2|V | ) possible non-hyperlinks), and denote the sampled negative class as ˆ Funobs. Finally, we state the hyperlink prediction problem as follows: Given a set of observed hyperlinks Fobs, find scores s : Funobs ∪ ˆ Funobs → [0, 1], mapping potential hyperlinks to their hyperlink-formation probabilities. Later in this article, we also refer to Funobs as ∆F, ˆ Funobs as ∆ ˆ F , and Fobs as plainly F .

3 The Clique Closure Hypothesis

Occurrence of a hyperlink marks the collaboration among multiple entities via a single common event. It is intuitive that subsets of these entities would have interacted in some form in the past, rather than the hyperlink getting formed spontaneously. In formal terms, in a temporal hypergraph H = (V, F, T), corresponding to a hyperlink f ∈ F formed at a given time T (f ), we could expect to find some hyperlinks f ′ ∈ F<T(f) that overlap densely with subsets of nodes incident on f . Since if that were not true, there is not much explanation - at least not any using the hypergraph topology - as to why the relation f is formed in the first place. In the projected graph η(H<T(f)), this translates as densely connected subgraphs (near-cliques) or sometimes even cliques. In simple words, CCH states that with high probability, nodes of a hyperlink were part of dense subgraphs before they formed hyperlinks.

We formally define CCH in this section, but before doing so, we need to keep certain concepts well-defined, since their equivalents do not exist in the literature. We define hypergraph density of a hypergraph H as d(H) := d(η(H)), the density of its clique-expanded graph. Similarly, subgraph density d(f,H) of any set of nodes f ⊆ V (where f need not be a hyperlink) is defined as d(f,H) := d(η(H)|f). Note that f ∈ F =⇒ d(f,H) = 1. We define a slight modification of this notion for temporal and non-temporal hypergraphs, viz., pre-hyperlink density dpre(f,H) := d(f,H<T(f)) and punctured hyperlink density dpunc(f,H) := d(f,H-f) respectively. The prefixes punctured- and pre- here refer to the fact that density is calculated on the hypergraph that existed without and before hyperlink f respectively. A higher pre-hyperlink density for a hyperlink would mean it evolved from near-cliques. Moreover, a hyperlink f evolving from cliques would have dpre(f, H) = 1, and those having an underlying clique structure would have dpunc(f,H) = 1. In other words, dpunc is used as an alternative for dpre in a non-temporal hypergraph, where the concept of evolution (i.e. order of hyperedge discovery is irrelevant) does not exist.

1 As defined by [Agarwal et al., 2006]

Let the clique-fraction cf(H) of hypergraph H be defined as cf(H) := |{f ∈ F : dx(f,H) = 1}| / |F|, the fraction of hyperlinks that formed from cliques, where dx denotes dpunc and dpre for temporal and non-temporal hypergraphs respectively. Since cf(H) is expected to be too low for non-temporal datasets, we also define a constant minimumclique-fraction cfmin and fix it to be cfmin = 0.05, which is a little more than the maximum hypergraph density among all non-temporal hypergraphs (ref Table 3). Finally, we define cliqueness of a hyperlink f ∈ F as follows:

where dx denotes dpunc and dpre for temporal and nontemporal hypergraphs respectively. We are now ready with a well-defined measure - cliqueness - to capture the notion of how dense is the region from which a given hyperlink is formed. Cliqueness captures both clique-fraction, as well as density, thereby catering to both clique- as well as nearclique-structure of a given hyperlink.

Hypothesis 1 (CCH: Clique Closure Hypothesis) Given a hypergraph H = (V, F) (or (V, F, T)), with significance α = 0.1, the null and alternate hypotheses for CCH are defined as follows for a hyperlink f ∈ F:

where E[d|H] := 1 |2V | ·∑f ′∈2V d(f ′ ,H), the mean subgraph density over all subsets of V .

In order to simplify CCH, and to make it more deterministic, we have the following result in place.

Theorem 1 Mean subgraph density of H over all subsets of V is equal to its hypergraph-density. In other words, E[d|H] = d(H).

Hypothesis 2 (CCH restated)

where d(H) and χ(f,H) denote density of hypergraph H and cliqueness of hyperlink f therein.

Algorithm 1 An algorithm to test CCH on a temporal hypergraph H = (V, F, T). Each hyperlink f = {v1, . . . , v|f|} ∈ F is evaluated w.r.t. connections η(H<T(f)) in its past based on how densely {v1, . . . , v|f|} are connected.

Input: Temporal hypergraph, H = (V, F, T ) Output: p-value of H0 for H

1: F>2 ← {f ∈ F : |f| > 2}

2: dH ← 2 ∗ |η(F)|

|V | ∗ (|V | - 1)

• 3: Nc ← 0
• 4: D← {}
• 5: for f ∈ F>2 do
• 6: Ef ← {{u, v} | ∀ u, v ∈ f}
• 7: t ← T (f )

8: F<t ← T -1 ([0, t))

9: E<t ← η(F<t)

10: D[f] ← |Ef ∩E<t|

11:

|Ef |

if (f,Ef ∩E<t) is a clique then

12: D[f] == 1

13: else

14: Nc ←Nc +1

15: end if

16: end for

17: cf ←max(cfmin,Nc/|F>2|)

18: NCCH ← 0

19: for f ∈ F>2 do

20: χf ←D[f] ∗ cf

21:

if χf ≤ dH then

22: NCCH ←NCCH +1

23: end if

• 24: end for
• 25: p ←NCCH/|F>2|
• 26: return p

We test CCH on a given temporal hypergraph H using Algorithm 1 and report results in Table 3.

Applying CCH to a non-temporal hypergraph would be futile, since there's no concept of evolution per se defined for it. For instance, reactions (hyperlinks) in a metabolite hypergraph [Zhang et al., 2018] cannot be arranged in a chronological order. However, we attempt to test CCH for such networks using a proxy mechanism, in that we set dx = dpunc in eq. 1 while calculating cliqueness χ(f,H). Making few changes to lines 7-10 in Algorithm 1, so as to calculate D[f] ← dpunc(f,H) for each hyperlink f, we could find p-values for a non-temporal hypergraph as well. The idea is to validate whether for a hyperedge, its incident nodes are well-connected even without its presence. Finally, we present the results in Table 3 for both temporal and non-temporal datasets.

In the literature, Benson et al. [Benson et al., 2018], who restrict themselves to 3- and 4-sized hyperlinks only, refer (although implicitly) to a similar phenomenon, wherein they argue that a clique (an open simplex) eventually forms a hyperlink (a closed simplex). The results of evaluating CCH on various datasets are tabulated and discussed in Section 7.1.

As would be discussed later, temporal hypergraphs strongly satisfy CCH, i.e., it is evident that most hyperlinks were cliques or near-cliques (densely connected) in the projected graph before they become hyperlinks.

4 C3MM: CCH based Hyperlink Prediction

We exploit this unique characteristic of clique-closure to predict hyperlinks. The approach is similar to Coordinated Matrix Minimization (CMM) by Zhang et al. [Zhang et al., 2018]. We call our method Clique-Closure based CMM (C3MM). It is formed as follows.

For a given hypergraph H = (V, F), define S ∈ {0, 1}|V |×|F| to be its incidence matrix. And let ∆F ⊆ P(V ) \ F represent the hyperlinks that are missing from (or yet to occur in) H. Clearly, F ∩ ∆F = ∅. Let ∆S ∈ {0, 1}|V |×|∆F | be the incidence matrix corresponding to ∆F . Let H′ := (V, F ⊎∆F) be the completed hypergraph, whose incidence matrix S′ ∈ {0, 1}|V |×(|F|+|∆F|) could be represented as follows 2 :

Adjacency matrix for projected graph η(H) is defined as A := η(S) := SST ∈ R|V |×|V | . Similarly, A′ := S′S′T refers to the adjacency matrix of η(H′ ), for which we have:

where ∆A refers to the links (edges) in adjacency space that get projected by missing hyperlinks ∆F represented by ∆S.

Let Funiv = {f1, f2, . . . , f|Funiv|} represent the set of universal hyperlinks (or candidate hyperlinks), forming our test set. Of Funiv, ∆F corresponds to true hyperlinks (the positive class); the remaining hyperlinks, Funiv \ ∆F, called as non-hyperlinks, can be represented by ∆ˆ F. and let ∆ˆ S ∈ {0, 1}|V |×|∆ ˆ F be the corresponding incidence matrix.

Let U = [u1 u2 · · · u|Funiv|] ∈ R|V |×|Funiv| to be the incidence matrix for the of set of candidate hyperlinks Funiv. Once the adjacency matrix ∆A of the missing links is predicted, the next step would be to pick those hyperlinks from Funiv, that best explain A and ∆A. For a given diagonal matrix ΛU = diag(λ1, λ2, . . . , λ|Funiv|) ∈ {0, 1}|Funiv|×|Funiv| , the product incidence matrix UΛU would "select" exactly those columns ui from U, for which λi = 1. The corresponding adjacency matrix is then UΛU(UΛU)T = UΛ2U U T = UΛUU T . Hence ΛU functions as hyperlink selector or predictor.

For the purpose of link prediction, any feasible link prediction method can be used. Here, we use a Common Neighbor (CN) [Newman, 2001; Liben-Nowell and Kleinberg, 2003] based link prediction technique. We first complete the adjacency matrix using the CN score, and then achieve its low rank approximation via Symmetric NMF [Kuang et al.,

2 Here, [A;B] denote column-wise concatenation of matrices A and B having the same number of rows.

2012]. The matrix ACN = A2 -diag(A2 ) captures the common neighbor information of the projected graph η(H) of H. To predict missing links ∆A we first approximate A + ACN with a low-rank matrix W ∈ R|V |×k , where k < |V |, such that A + ACN ≈ WW T .

The representation capability of W is low and hence such approximation ends up removing noisy links which might have been introduced due to ACN. Thus we define the predicted links as ∆A := WW T - A.

Next step is to predict the missing hyperlinks ∆F from the predicted missing links ∆A. Since U contains missing hyperlinks as well as non-hyperlinks, the diagonal matrix ΛU should be such that the hyperlinks selected by UΛU correspond to the links in ∆A when they are projected on graph. This can be obtained by optimizing ΛU w.r.t following objective function:

This is where we bring CCH into the picture. According to CCH, links in A also play a major role in formation of future hyperlinks. Hence, the predicted hyperlinks in ∆F should not only explain missing links of ∆A but also existing links in A (through clique and near-clique closure). However, as we already know, links in A are formed by F and hence can always be explained by S. Then hyperlinks can be predicted by optimizing ΛU w.r.t following objective function:

The L1-penalty imposed on ΛS is important to avoid a trivial solution where ΛS = I and ΛU = 0.

Satisfying the objective functions specified in eqs. (8) and (7) leads to a joint optimization problem for hyperlink prediction, which we formulate next. We note that since the problems in eqs. (7 - 8) fall into the integer programming paradigm, and since such problems are NP-complete, we relax the domains of ΛU and ΛS to the unit interval [0, 1] instead of {0, 1}. Hence our final problem boils down to the following:

In summary, we have exploited our clique-closure hypothesis by explicitly forcing the objective function to consider cliques and near-cliques from the projected graph of the observed hyperlinks, as well as new information ∆A simultaneously, and predict hyperlinks that explain them both.

Alternating Minimization

Finding an optimal solution to the problem (9) can be done by minimizing it alternatively - first for W, and then for ΛS and ΛU .

This leads to an alternating optimization where we first predict missing links with the help of W obtained as per eq (6) and then predict missing hyperlinks by solving the optimization problem in eq (9). At the end of each iteration we update A with the new predicted links by adding UΛUU T . Overall C3MM predicts hyperlinks by performing following steps alternatively:

Step 1: For fixed ΛU from Step 2 below (or by fixing it to be a randommatrix for the first iteration), solve for W:

Step 2: Defining ∆A := WW T - A for W fixed from Step 1 above, find the optimal ΛU according to Eq. (9).

Since both Step 1 and Step 2 are convex optimization problems, we solve them by alternatively minimizing them for matrices ΛU, ΛS and W, and finally use ΛU, that denotes the newly predicted hyperlinks.

5 RelatedWork

The hyperlink prediction problem focuses on predicting unknown/unseen interactions between a set of nodes, whose analogue in usual networks is the link prediction problem. Here, we given a brief overview of the related work in both link- as well as hyperlink-prediction.

Although research in hyperlink prediction has been limited, its literature is convincing enough to vouch for its importance. Ever since the near-seminal works by [Agarwal et al., 2006] and [Zhou et al., 2006] that unite the fields of hypergraphs and machine learning, there has been four major works focusing on hyperlink prediction. Xu et al. [Xu et al., 2013] and both works by Zhang et al. [Zhang et al., 2018; Zhang et al., 2016] deal with specific domains, viz., email and metabolite networks respectively. Benson et al. [Benson et al., 2018], on the other hand, bring a multitude of domains to the table (see Section 6 for more details). While Zhang et al. [Zhang et al., 2018] introduce a matrix completion based solution called Coordinated Matrix Minimization (CMM) that works well for a non-temporal network of metabolites, Benson et al. [Benson et al., 2018] restrict the problem to that of predicting the closure of a 3-4 sized open simplex, which is a problem temporal in nature.

Researchers have previously worked on the task of predicting links in heterogeneous and bipartite networks as well [Kunegis et al., 2010; Yu et al., 2014], however, their relevance to the current work is limited since hyperlink prediction parallels neither to link prediction on such networks, nor their one-mode projections.

6 Experimental Setup

We test our algorithm (C3MM 3 ) on both structural as well as temporal link prediction problems, and report results on diverse datasets, using a few baselines to compare against. But before that, we test our hypothesis (CCH) on these datasets, and elucidate that it holds statistically significantly for most of them. Let us describe the datasets we have used.

3 Code available at https://github.com/govindjsk/c3mm

6.1 Datasets

We have performed our experiments on altogether ten datasets, of which four are temporal hypergraphs and we use the six non-temporal metabolite hypergraphs from Zhang et al. [Zhang et al., 2018].

We provide a brief introductory overview of these datasets below. For more information, we suggest the reader to refer to Benson et al. [Benson et al., 2018] for an extensive analysis of the four (and more) temporal datasets, and to Zhang et al. [Zhang et al., 2018] for the six metabolites datasets. Summary is in Table 2.

1. contact-ps and contact-hs: These are contact networks, wherein nodes are primary/high school students and a hyperlink between them represents those observed to be within a close proximity to each other over a period of three days.
2. MAG-G: This refers to a co-authorship network, wherein nodes are authors and a hyperlink between them denotes a set of authors who have exclusively coauthored at least one paper. Since this is one of the biggest datasets we have, we reduce it using the same core-based filtering technique as Liben-Nowell et al. [Liben-Nowell and Kleinberg, 2003].
3. tags-ms: It is a hypergraph where nodes refer to tags given to question-answer threads on Math StackExchange, and a set of all tags associated a thread forms a hyperlink. We take only one year's (most recent) data for tags-ms.
4. Metabolites: This is a group of six datasets of metabolic reactions, where nodes are metabolites (reactants and products) of a metabolic reaction, which represents a hyperlink. They have been named iJO1366, iAF1260b, iAF692, iHN637, iIT341, and iAB RBC 283.

6.2 Baselines

Coordinated Matrix Minimization (CMM) [Zhang et al., 2018] as well as baseline algorithms mentioned in their paper form the baselines for our experiments. More specifically, we use the following methods as our baselines: Bayesian Sets (BS) [Ghahramani and Heller, 2006], Spectral Hypergraph Clustering (SHC) [Zhou et al., 2006], Factorization Machines (FM) [Rendle, 2012], Katz [Katz, 1953], and Hyper Common Neighbors (CN) [Zhang et al., 2018; Liben-Nowell and Kleinberg, 2007]. For more information we refer to Zhang et al. [Zhang et al., 2018] or the respective references therein.

To evaluate the performance of hyperlink prediction algorithms, we make use of the area under ROC curves (AUC) metric.

Negative Sampling

Owing to extreme class imbalance (of ratio O (2|V | /|F|)) between non-hyperlinks and hyperlinks in hyperlink prediction, the issue of negative sampling (i.e., undersampling the negative/dominant class) becomes serious, lest biased results get reported. The literature on fair evaluation of link prediction algorithms [Garcia Gasulla et al., 2015; Lichtenwalter et al., 2010; Lichtnwalter and Chawla, 2012; Yang et al., 2015] highlights the role of negative sampling in evaluating solutions, which extends to hyperlink prediction as well. We extend Lichtenwalter et al.'s [Lichtenwalter et al., 2010] geodesic-distance ℓ = 2 (i.e., one-hop neighbor) based negative-sampling technique to hypergraphs as follows [Patil et al., 2020].

We sample the negative class (i.e., non-hyperlinks) by randomly picking a hyperlink f ∈ F (of size, say s) and replacing its lowest degree node (say v0 ∈ f) with a commonneighbor (say v′ /∈ f) of all other s - 1 nodes in f-v0 := f \ {v0}, such that f ′ := (f-v0 ) ∪ {v′ } /∈ F. We repeat this process to extract multiple non-hyperlinks f ′ /∈ F corresponding to a hyperlink f ′ , and stop when we have an enough (defined as a factor p ∈ R of the positive class size) number of them. This method is a simple extension of the usual one-hop (ℓ = 2) negative sampling performed in link prediction [Lichtenwalter et al., 2010].

Data Preparation

We sample 15 times as many non-hyperlinks as there are hyperlinks in the unobserved hypergraph for all of the temporal hypergraphs. For the non-temporal hypergraphs (i.e., the Metabolites datasets), Zhang et al. [Zhang et al., 2018] already refer to a manually curated negative class (or nonhyperlinks) 4 ; hence there is no need to generate any negative samples. We fix the size of latent dimension for symmetric NMF in (6) to be k = 30 for the all the datasets, just as Zhang et al. [Zhang et al., 2018] do as a default choice for CMM.

7 Results and Discussion

7.1 CCHHypothesis Testing

We test our hypothesis (CCH) on a total of ten datasets, four of which are temporal, while remaining are non-temporal (Table 3). On temporal datasets, we test CCH using Algorithm 1, whereas for non-temporal ones the variation as mentioned in Section 3 is used. More specifically, for each of our datasets, we report the values of d(H), cf(H), and also p-values of H0 (Hypothesis 2) over all hyperlinks f ∈ F .

4 Owing to the knowledge domain experts have about "impossible" metabolic reactions.

The first set of results (first four rows of Table 3) show that all temporal hypergraphs satisfy the hypothesis by a decent margin, in that p < α. One can infer that in these settings, it is highly required for a group of nodes to have had dense lowerorder interactions before the group evolves into a hyperlink. Also, as the hyperlink size increases, so does its mean prehyperedge density. It is therefore observed that three or four authors can relatively easily group together to collaborate on a common work, than bigger groups.

The second set of results (bottom six rows of Table 3) clearly show that metabolite datasets, which are non-temporal in nature, show little-to-no support for the hypothesis. Not much could be commented on the relative comparison between datasets since they are all equally low, wherein cf(H) lies in the range of 3-8% and p-value much higher as compared to its temporal counterparts.

In summary, temporal datasets satisfy CCH with high confidences, while non-temporal ones fail miserably. The results we report in the bottom part of Table 3 are certain summaries of the static analysis of metabolite networks, which is not bound to follow a particular pattern, at least not the pattern we expect it to (namely, CCH).

7.2 Hyperlink Prediction

We present the results for hyperlink prediction on the four temporal datasets in Table 4. Table 4 reports mean AUC scores for C3MM versus CMM and its other baselines.

In all the temporal datasets, C3MM performs better than the other baselines, of which in particular, CMM (an approach that is similar to C3MM) has much lower AUC scores. This supports the argument that our hypothesis (CCH) has helped identify hyperlinks that the earlier formulation did not. Of the datasets, MAG-G and tags-math-sx have the highest scores, since they are bigger datasets and have formed over a longer time range than the other ones. Of the other baselines, we have BS (Bayesian Sets) that has a decent AUC for all datasets, except for tags-ms, and SHC seems to be the third best baseline.

One dataset that has a relatively higher p-value for CCH and despite this fact C3MM performing well is MAG-G, where we see most (73%) of the hyperlinks forming from non-cliques. This is possibly due to MAG-G being a coauthorship network where one would anticipate future collaboration among authors who have worked together in the past in some form. The higher p-value could be attributed to the fact that we take the hypergraph snapshot of recent 7 years, which ends up ignoring meaningful connections of the past.

At the same time, performance of C3MM drops for most of the non-temporal metabolite datasets. The only dataset which shows better performance for C3MM is iAF1260b while for the rest of the datasets performance drop is anywhere between 12% to 1%. Also it should be noted that iAF1260b is the only non-temporal dataset that satisfies CCH hypothesis as seen in Table 3 while the other datasets don't as shown by Table 3. This shows that C3MM is a better algorithm for hyperlink prediction when the CCH hypothesis is strongly supported by dataset.

8 Conclusion and FutureWork

Hyperlink prediction is a difficult task to perform, at least more difficult than what link prediction is. This is so both due to the number of possible hyperlinks in a given hypergraph (which is exponential in the number of nodes), as well as lack of multi-way heuristic scores. We set out to improve upon the current state-of-the-art (CMM) by introducing a clique-closure hypothesis into its objective function, ultimately forming C3MM. It is clear from the results on the hypothesis tests that we succeed in validating that it is cliques and co-cliques that close to form hyperlinks, instead of they being formed by co-cliques or disconnected structures. Embedding the hypothesis into the objective function leads to it significantly hunting down more hyperlinks which were missed by CMM. Another conclusion we draw is that hyperlink prediction on temporal and non-temporal datasets works differently, in that the latter predicts the future, and the former, the missing hyperlinks. While CMM works well on nontemporal datasets, C3MM better predicts future links.

In an extension, we would like to extract more concepts from baselines such as Bayesian Sets and Spectral Hypergraph Clustering and incorporate them into C3MM, to hopefully improve further. Also, we would aim to work with more variety of networks: heterogeneous hypergraphs, directed hypergraphs, and weighted hypergraphs.

Acknowledgements

Prasanna Patil was supported by a fellowship grant from the Centre for Networked Intelligence (a Cisco CSR initiative) of the Indian Institute of Science, Bengaluru.