C3MM: Clique-Closure based Hyperlink Prediction

Govind Sharma, Prasanna Patil, M. Narasimha MurtyIJCAI 2020 · DOI

TL;DR

This paper introduces C3MM, a novel approach to hyperlink prediction that leverages the "clique-closure hypothesis" – the idea that hyperlinks are more likely to form from densely connected groups of nodes that have interacted previously. C3MM significantly improves prediction accuracy over existing methods, particularly for temporal hypergraphs.

What Problem Does This Paper Address?

Traditional graph analysis often focuses on pairwise relationships between entities. However, many real-world phenomena involve higher-order relationships, where an event or connection (a hyperlink) links more than two entities simultaneously. Hypergraphs are used to model these complex relationships. Predicting future or missing hyperlinks in these hypergraphs is crucial for understanding network evolution and making informed predictions. Existing methods, like Coordinated Matrix Minimization (CMM), have shown promise but struggle to fully capture the underlying dynamics of hyperlink formation, especially when considering the historical context of node interactions. This paper aims to bridge this gap by incorporating a hypothesis about how past interactions influence future hyperlink formation.

Methods

The core of this paper is the Clique-Closure Hypothesis (CCH). This hypothesis posits that for a hyperlink to form, its constituent nodes must have been part of a dense subgraph (a clique or near-clique) in the past. In simpler terms, hyperlinks don't just "appear" out of nowhere; they evolve from existing, dense connections.

To test and exploit CCH, the authors propose C3MM (Clique-Closure based Coordinated Matrix Minimization). C3MM builds upon the existing CMM framework by incorporating CCH into its objective function. This means that C3MM not only considers the current state of the hypergraph but also explicitly penalizes solutions that don't align with the clique-closure principle. The method involves:

  1. Testing CCH: The authors develop an algorithm to statistically test CCH on temporal hypergraphs, analyzing whether nodes forming a hyperlink were indeed part of dense subgraphs before the hyperlink's occurrence.
  2. Hyperlink Prediction with C3MM: C3MM reformulates the hyperlink prediction problem by optimizing an objective function that includes terms for reconstructing the observed hypergraph, predicting new links, and crucially, enforcing the clique-closure hypothesis. This is achieved through an alternating minimization strategy, iteratively updating matrices that represent node-hyperlink relationships and predicted missing links.

Datasets

The authors evaluate their approach on ten datasets:

  • Four Temporal Hypergraphs:
    • contact-ps and contact-hs: Contact networks where hyperlinks represent students observed in close proximity over three days.
  • MAG-G: A co-authorship network where hyperlinks represent authors who have co-authored at least one paper.
  • tags-ms: A hypergraph where nodes are tags associated with a question-answer thread, and a hyperlink represents all tags for a thread.
  • Six Non-Temporal Metabolite Hypergraphs:
    • iJO1366, iAF1260b, iAF692, iHN637, iIT341, iAB_RBC_283: These datasets represent metabolic reactions, where nodes are metabolites and hyperlinks represent reactions. These were previously used in CMM research.

Key Insights and Ideas

  • The "Evolutionary" Nature of Hyperlinks: The most significant insight is the validation of the clique-closure hypothesis. This suggests that hyperlinks are not random occurrences but rather emerge from a history of dense interactions among their constituent nodes. This "evolutionary" perspective is key to improving prediction.
  • Temporal vs. Non-Temporal Dynamics: The study highlights a crucial difference in how hyperlinks form in temporal versus non-temporal networks. Temporal networks strongly support CCH, indicating that past interactions are highly predictive of future hyperlinks. Non-temporal networks, lacking this temporal dimension, show little to no support for CCH, suggesting different underlying mechanisms.
  • CCH as a Predictive Signal: By explicitly incorporating CCH into the prediction model, C3MM can identify hyperlinks that were missed by previous methods, leading to improved accuracy. This is particularly evident when comparing C3MM to CMM.
  • Generalization of Hyperlink Prediction: The paper extends hyperlink prediction beyond small-sized hyperlinks to arbitrary sizes and across multiple domains, demonstrating the robustness of the proposed approach.

Key Results

  • CCH Validation: Temporal hypergraphs strongly reject the null hypothesis for CCH (p < 0.1), indicating that the clique-closure hypothesis holds for them. Non-temporal metabolite datasets, however, generally fail to reject the null hypothesis, showing little support for CCH.
  • C3MM Performance: On temporal datasets, C3MM consistently outperforms CMM and other baselines, achieving significantly higher AUC scores. For instance, on MAG-G, C3MM shows strong performance despite a high percentage of hyperlinks forming from non-cliques, suggesting its ability to capture complex relationships.
  • Performance Drop on Non-Temporal Data: C3MM's performance drops on most non-temporal metabolite datasets, especially when CCH is not supported. However, it still performs better on iAF1260b, the only non-temporal dataset that showed some support for CCH. This reinforces the idea that C3MM is most effective when CCH is well-supported.

Limitations and Future Work

  • Limitations:
    • The performance of C3MM is significantly dependent on the degree to which the CCH is supported by the dataset. For non-temporal datasets where CCH is not supported, the improvement over CMM is minimal or non-existent.
  • The paper notes that for the MAG-G dataset, a high percentage of hyperlinks formed from non-cliques, which might be due to ignoring older connections when considering only the last 7 years of data.
  • Future Work:
    • The authors suggest incorporating concepts from other baselines like Bayesian Sets and Spectral Hypergraph Clustering into C3MM to further enhance performance.
  • They also aim to extend their work to more complex network types, including heterogeneous hypergraphs, directed hypergraphs, and weighted hypergraphs.

Summary updated

BibTeX
@inproceedings{sharma2020c,
  author = {Govind Sharma and Prasanna Patil and M. Narasimha Murty},
  title = {{C3MM: Clique-Closure based Hyperlink Prediction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/465},
}
Figure