Supervised Hypergraph Reconstruction

• URL: http://arxiv.org/abs/2211.13343v1
• Date: Wed, 23 Nov 2022 23:15:03 GMT
• Title: Supervised Hypergraph Reconstruction
• Authors: Yanbang Wang, Jon Kleinberg
• Abstract summary: Many real-world systems involving high-order interactions are best encoded by hypergraphs. Their datasets often end up being published or studied only in the form of their projections. We propose supervised hypergraph reconstruction. Our approach outperforms all baselines by an order of magnitude in accuracy on hard datasets.
• Score: 3.69853388955692
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study an issue commonly seen with graph data analysis: many real-world complex systems involving high-order interactions are best encoded by hypergraphs; however, their datasets often end up being published or studied only in the form of their projections (with dyadic edges). To understand this issue, we first establish a theoretical framework to characterize this issue's implications and worst-case scenarios. The analysis motivates our formulation of the new task, supervised hypergraph reconstruction: reconstructing a real-world hypergraph from its projected graph, with the help of some existing knowledge of the application domain. To reconstruct hypergraph data, we start by analyzing hyperedge distributions in the projection, based on which we create a framework containing two modules: (1) to handle the enormous search space of potential hyperedges, we design a sampling strategy with efficacy guarantees that significantly narrows the space to a smaller set of candidates; (2) to identify hyperedges from the candidates, we further design a hyperedge classifier in two well-working variants that capture structural features in the projection. Extensive experiments validate our claims, approach, and extensions. Remarkably, our approach outperforms all baselines by an order of magnitude in accuracy on hard datasets. Our code and data can be downloaded from bit.ly/SHyRe.

Related papers

• SPHINX: Structural Prediction using Hypergraph Inference Network [19.853413818941608]
  We introduce Structural Prediction using Hypergraph Inference Network (SPHINX), a model that learns to infer a latent hypergraph structure in an unsupervised way. We show that the recent advancement in k-subset sampling represents a suitable tool for producing discrete hypergraph structures. The resulting model can generate the higher-order structure necessary for any modern hypergraph neural network.
  arXiv  Detail & Related papers  (2024-10-04T07:49:57Z)
• From Graphs to Hypergraphs: Hypergraph Projection and its Remediation [2.0590577326314787]
  We study the implications of the modeling choice to use a graph, instead of a hypergraph, to represent real-world interconnected systems. We develop a learning-based hypergraph reconstruction method based on an important statistic of hyperedge distributions.
  arXiv  Detail & Related papers  (2024-01-16T17:31:54Z)
• Hypergraph Transformer for Semi-Supervised Classification [50.92027313775934]
  We propose a novel hypergraph learning framework, HyperGraph Transformer (HyperGT) HyperGT uses a Transformer-based neural network architecture to effectively consider global correlations among all nodes and hyperedges. It achieves comprehensive hypergraph representation learning by effectively incorporating global interactions while preserving local connectivity patterns.
  arXiv  Detail & Related papers  (2023-12-18T17:50:52Z)
• Hypergraph Neural Networks through the Lens of Message Passing: A Common Perspective to Homophily and Architecture Design [7.410655263764799]
  We introduce a novel conceptualization of homophily in higher-order networks based on a Message Passing scheme. We investigate some natural, yet mostly unexplored, strategies for processing higher-order structures within HNNs.
  arXiv  Detail & Related papers  (2023-10-11T17:35:20Z)
• Network Alignment with Transferable Graph Autoencoders [79.89704126746204]
  We propose a novel graph autoencoder architecture designed to extract powerful and robust node embeddings. We prove that the generated embeddings are associated with the eigenvalues and eigenvectors of the graphs. Our proposed framework also leverages transfer learning and data augmentation to achieve efficient network alignment at a very large scale without retraining.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• Enhancing Hyperedge Prediction with Context-Aware Self-Supervised Learning [64.46188414653204]
  We propose a novel hyperedge prediction framework (CASH) CASH employs context-aware node aggregation to capture complex relations among nodes in each hyperedge for (C1) and (2) self-supervised contrastive learning in the context of hyperedge prediction to enhance hypergraph representations for (C2) Experiments on six real-world hypergraphs reveal that CASH consistently outperforms all competing methods in terms of the accuracy in hyperedge prediction.
  arXiv  Detail & Related papers  (2023-09-11T20:06:00Z)
• Hypergraph Structure Inference From Data Under Smoothness Prior [46.568839316694515]
  We propose a method to infer the probability for each potential hyperedge without labelled data as supervision. We use this prior to derive the relation between the hypergraph structure and the node features via probabilistic modelling. Experiments on both synthetic and real-world data demonstrate that our method can learn meaningful hypergraph structures from data more efficiently than existing hypergraph structure inference methods.
  arXiv  Detail & Related papers  (2023-08-27T18:28:58Z)
• Augmentations in Hypergraph Contrastive Learning: Fabricated and Generative [126.0985540285981]
  We apply the contrastive learning approach from images/graphs (we refer to it as HyperGCL) to improve generalizability of hypergraph neural networks. We fabricate two schemes to augment hyperedges with higher-order relations encoded, and adopt three augmentation strategies from graph-structured data. We propose a hypergraph generative model to generate augmented views, and then an end-to-end differentiable pipeline to jointly learn hypergraph augmentations and model parameters.
  arXiv  Detail & Related papers  (2022-10-07T20:12:20Z)
• Finding Bipartite Components in Hypergraphs [9.759415650727892]
  We study a new heat diffusion process in hypergraphs and employ this process to design a new algorithm that finds approximately bipartite components in a hypergraph. We find that our new algorithm consistently and significantly outperforms the previous state-of-the-art across a wide range of hypergraphs.
  arXiv  Detail & Related papers  (2022-05-05T16:46:31Z)
• Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs [59.71134113268709]
  We present General Hypergraph Spectral Convolution(GHSC), a general learning framework that can handle EDVW and EIVW hypergraphs. In this paper, we show that the proposed framework can achieve state-of-the-art performance. Experiments from various domains including social network analysis, visual objective classification, protein learning demonstrate that the proposed framework can achieve state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-03-31T10:46:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.