Perfect Clustering in Nonuniform Hypergraphs

• URL: http://arxiv.org/abs/2504.08980v1
• Date: Fri, 11 Apr 2025 21:12:48 GMT
• Title: Perfect Clustering in Nonuniform Hypergraphs
• Authors: Ga-Ming Angus Chan, Zachary Lubberts,
• Abstract summary: We introduce a hyper-edge-centric model for analyzing hypergraphs, called the interaction hypergraph.<n>We show that a spectral estimate of the interaction latent positions can achieve perfect clustering once enough interactions are observed.
• Score: 2.2252684361733293
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While there has been tremendous activity in the area of statistical network inference on graphs, hypergraphs have not enjoyed the same attention, on account of their relative complexity and the lack of tractable statistical models. We introduce a hyper-edge-centric model for analyzing hypergraphs, called the interaction hypergraph, which models natural sampling methods for hypergraphs in neuroscience and communication networks, and accommodates interactions involving different numbers of entities. We define latent embeddings for the interactions in such a network, and analyze their estimators. In particular, we show that a spectral estimate of the interaction latent positions can achieve perfect clustering once enough interactions are observed.

Related papers

• Hyperedge Anomaly Detection with Hypergraph Neural Network [0.08192907805418582]
  We propose an end-to-end hypergraph neural network-based model for identifying anomalous associations in a hypergraph.<n>Our proposed algorithm operates in an unsupervised manner without requiring any labeled data.
  arXiv  Detail & Related papers  (2024-12-07T12:52:22Z)
• 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)
• 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)
• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  We present an expressive family of parameterized, hypergraph-regularized energy functions. We then demonstrate how minimizers of these energies effectively serve as node embeddings. We draw parallels between the proposed bilevel hypergraph optimization, and existing GNN architectures in common use.
  arXiv  Detail & Related papers  (2023-06-16T04:40:59Z)
• Learning Causal Effects on Hypergraphs [33.41001768564952]
  We study hypergraphs from the perspective of causality. In this work, we investigate high-order interference modeling, and propose a new causality learning framework powered by hypergraph neural networks.
  arXiv  Detail & Related papers  (2022-07-07T23:14:10Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  Graph neural networks (GNNs) rely on the message passing paradigm to propagate node features and build interactions. Recent works point out that different graph learning tasks require different ranges of interactions between nodes. We study two common graph construction methods in scientific domains, i.e., emphK-nearest neighbor (KNN) graphs and emphfully-connected (FC) graphs.
  arXiv  Detail & Related papers  (2022-05-15T11:38:14Z)
• Principled inference of hyperedges and overlapping communities in hypergraphs [0.0]
  We propose a framework based on statistical inference to characterize the structural organization of hypergraphs. We show strong performance in hyperedge prediction tasks, detecting communities well aligned with the information carried by interactions, and robustness against addition of noisy hyperedges.
  arXiv  Detail & Related papers  (2022-04-12T09:13:46Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• Learning over Families of Sets -- Hypergraph Representation Learning for Higher Order Tasks [12.28143554382742]
  We develop a hypergraph neural network to learn provably expressive representations of variable sized hyperedges. We evaluate performance on multiple real-world hypergraph datasets and demonstrate consistent, significant improvement in accuracy, over state-of-the-art models.
  arXiv  Detail & Related papers  (2021-01-19T18:37:50Z)
• Towards Interaction Detection Using Topological Analysis on Neural Networks [55.74562391439507]
  In neural networks, any interacting features must follow a strongly weighted connection to common hidden units. We propose a new measure for quantifying interaction strength, based upon the well-received theory of persistent homology. A Persistence Interaction detection(PID) algorithm is developed to efficiently detect interactions.
  arXiv  Detail & Related papers  (2020-10-25T02:15:24Z)
• A Graph-based Interactive Reasoning for Human-Object Interaction Detection [71.50535113279551]
  We present a novel graph-based interactive reasoning model called Interactive Graph (abbr. in-Graph) to infer HOIs. We construct a new framework to assemble in-Graph models for detecting HOIs, namely in-GraphNet. Our framework is end-to-end trainable and free from costly annotations like human pose.
  arXiv  Detail & Related papers  (2020-07-14T09:29:03Z)

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.