PaperlayerView exact revision on arXiv

Source-linked AI summary

Inference of hyperedges and overlapping communities in hypergraphs

Martina Contisciani, Federico Battiston, Caterina De Bacco

arXiv:2204.05646v2cs.SIphysics.data-anphysics.soc-phstat.ML

TL;DR

Pairwise graphs cannot faithfully represent interactions among three or more units, which occur in many real-world systems. The paper proposes Hypergraph-MT, a probabilistic mixed-membership model for detecting overlapping communities and predicting missing hyperedges. Across its applications, the authors report strong prediction performance, robust community detection, and faster running time than clique-expansion methods.

  • Problem

    Traditional graphs encode dyadic relations, while many real-world systems contain interactions among three or more units.

    Source: INTRODUCTION · p. 1

  • Method

    Hypergraph-MT is a mixed-membership probabilistic generative model that infers overlapping communities and assigns probabilities to potential hyperedges.

    Source: MODEL · p. 2

  • Results

    Hypergraph-MT achieves high performance in missing-hyperedge prediction, runs faster than clique-expansion methods, and is more robust to large noisy hyperedges and community detection aligned with hyperedge information.

    Source: DISCUSSION · p. 8

  • Takeaways & Limitations

    The method provides a way to evaluate community structure through missing-hyperedge prediction, including when metadata are absent.

    Source: DISCUSSION · p. 8

    The model assumes conditional independence between hyperedges given latent variables, and the paper does not explore relaxing this assumption.

    Source: MODEL · p. 2

Abstract

from arXiv · show

Hypergraphs, encoding structured interactions among any number of system units, have recently proven a successful tool to describe many real-world biological and social networks. Here we propose a framework based on statistical inference to characterize the structural organization of hypergraphs. The method allows to infer missing hyperedges of any size in a principled way, and to jointly detect overlapping communities in presence of higher-order interactions. Furthermore, our model has an efficient numerical implementation, and it runs faster than dyadic algorithms on pairwise records projected from higher-order data. We apply our method to a variety of real-world systems, showing strong performance in hyperedge prediction tasks, detecting communities well aligned with the information carried by interactions, and robustness against addition of noisy hyperedges. Our approach illustrates the fundamental advantages of a hypergraph probabilistic model when modeling relational systems with higher-order interactions.

INTRODUCTION

Pairwise graphs cannot faithfully encode interactions among three or more units, which are common across diverse biological and social systems. The paper introduces a statistical-inference method for overlapping hypergraph communities and hyperedge prediction.

INTRODUCTION

  • Hyperedges represent structured interactions among any number of units, whereas traditional graphs encode only dyadic relations.The passages cite higher-order interactions in cellular, brain, social, ecological, face-to-face, and collaboration systems.Source: INTRODUCTION · p. 1
  • The mesoscale organization of real-world hypergraphs remains largely unexplored despite prior work on higher-order models, metrics, and inference.Related approaches include topological data analysis, inference from pairwise records, and extensions of clustering, spectral methods, centrality, motifs, and network backboning.Source: INTRODUCTION · p. 1
  • Hypergraph-MT uses statistical inference to detect overlapping communities and predict missing hyperedges, and can generate synthetic hypergraphs with specified community structure.The paper reports efficient implementation and applies the method to real-world systems.Source: INTRODUCTION · p. 1

MODEL

Hypergraph-MT is a mixed-membership probabilistic generative model that infers overlapping communities from higher-order interactions. It uses an assortative affinity restriction to control model dimension and an efficient inference routine; synthetic tests report stronger recovery than competing methods once community structure is less noisy.

MODEL

  • Nodes have mixed-membership vectors that determine the probability of hyperedges among any subset of nodes.The model represents the observed hypergraph as an adjacency tensor whose entries are interaction weights.Source: MODEL · p. 2
  • The affinity tensor links compatible communities, while an assortative restriction leaves only diagonal entries nonzero and reduces it to a D × K matrix.D is the maximum hyperedge size in the dataset; this restriction is presented as interpretable, predictive, and computationally scalable.Source: MODEL · p. 2
  • The likelihood assumes conditional independence between hyperedges given the latent variables, a condition the paper does not relax.The authors note that relaxation is possible through approaches in Refs. (53–55).Source: MODEL · p. 2
  • Inference estimates membership vectors and affinities from the observed hypergraph using maximum likelihood or maximum a posteriori estimation with an expectation-maximization algorithm.The described EM procedure exploits dataset sparsity.Source: MODEL · p. 2
  • The membership updates exploit sparse incidence-matrix entries, while a reformulated summation reduces computational complexity to O(NDK).The original denominator can require summing over all possible hyperedges up to maximum size D; the reformulation updates an initial value at O(1) cost.Source: MODEL · pp. 2–3
  • Hypergraph-MT significantly outperforms Graph-MT, Pairs-MT, and the method of (45) once the ground-truth community structure becomes less noisy.This holds on synthetic datasets generated by a process different from Hypergraph-MT's own.Source: MODEL · p. 3

RESULTS

The empirical analyses compare Hypergraph-MT with graph-based baselines on structures derived from the same data. A high-school illustration contrasts the partitions recovered by the hypergraph and clique-expanded graph methods after a simulated event.

RESULTS

  • The empirical comparison uses Hypergraph-MT on hypergraphs and two baselines: clique expansions and graphs containing only registered pairwise interactions.The methods are run on structures derived from the same empirical data.Source: RESULTS · p. 3
  • The high-school illustration compares the Hypergraph-MT and Graph-MT partitions after adding a simulated event as a large hyperedge.The graph view shows the clique-expanded interactions added by that event; the figure presents the hypergraph representation as more resilient to the noisy addition.Source: Figure 1 · p. 4

The advantage of using hypergraphs

The paper tests whether representing higher-order contacts as hypergraphs improves community detection over graph representations. In the four contact datasets, performance is similar when interactions are mainly pairwise, while a toy example shows greater resilience to one noisy large hyperedge.

The advantage of using hypergraphs

  • Hypergraphs and graphs perform similarly on four human-contact datasets, whose mean hyperedge size is around 2.2 and whose larger interactions often contain already pairwise-connected people.The authors conclude that a network algorithm is sufficient for these datasets.Source: The advantage of using hypergraphs · p. 4
  • The comparison evaluates inferred partitions against node metadata using F1-score, which ranges from 0 to 1, with 1 indicating a perfect match.The metadata describe classes, departments, or roles; Table 2 compares the hypergraph, clique-expansion, and pairwise-only structures.Source: The advantage of using hypergraphs · pp. 4–5
  • In the toy example, Hypergraph-MT assigns the ten external guests zero membership in both classes, while Graph-MT assigns them to the blue class.The simulated size-20 event adds edges through clique expansion; the authors present the example as a case where hypergraphs are more resilient to a noisy large hyperedge.Source: The advantage of using hypergraphs · pp. 4–5

Hyperedge prediction: Analysis of a Gene-Disease

The Gene-Disease analysis tests missing-hyperedge prediction while varying the maximum hyperedge size. At D = 15, 16, Hypergraph-MT significantly outperforms Graph-MT and Pairs-MT.

Hyperedge prediction: Analysis of a Gene-Disease

  • The evaluation uses cross-validation: train hyperedges estimate parameters, while test-set AUC measures prediction; pairwise comparisons use the same pair subset.Hypergraph-MT and Graph-MT are also scored on test pairs while still training on the full training set.Source: dataset · p. 5
  • At D = 15, 16, Hypergraph-MT significantly outperforms Graph-MT and Pairs-MT, whether predicting hyperedges or pairs.The improvement is reported across held-out hyperedge sizes, not only pairs; the authors attribute it to useful information in larger hyperedges.Source: dataset · p. 5, Figure 2 · p. 5
  • Larger hyperedges carry predictive information that clique expansions do not fully capture, including information useful for predicting smaller hyperedges.The authors suggest clique expansion can add dense, potentially uncorrelated edges that blur the input observations.Source: dataset · p. 5

Analysis of a Justice dataset

The Supreme Court voting analysis compares inferred communities with both party affiliation and voting patterns. Hypergraph-MT’s overlapping memberships more closely match Justices’ voting behavior than Graph-MT’s.

Analysis of a Justice dataset

  • The study treats each Justice as a node and each case’s shared vote as a hyperedge, comparing inferred partitions with Democrat or Republican metadata.The dataset covers Supreme Court votes from 1946 to 2019; it contains 38 nodes and 2,826 hyperedges.Source: Analysis of a Justice dataset · p. 6
  • For three Justices, political-party alignment favors Graph-MT over Hypergraph-MT; inspecting vote-majority patterns helps interpret these exceptions.The figure compares per-Justice cosine similarities with party affiliation and summarizes the party majority of each Justice’s participating hyperedges.Source: Analysis of a Justice dataset · pp. 6–7, Figure 3 · p. 6
  • Hypergraph-MT’s overlapping memberships match Justices’ voting behavior more closely than Graph-MT’s, including cases where voting patterns diverge from party affiliation.For Justice Ruth Bader Ginsburg, Hypergraph-MT assigns greater membership to the Republican-voting community, while Graph-MT assigns her mostly to the Democratic community.Source: Analysis of a Justice dataset · p. 7
  • Hypergraph-MT also achieves higher AUC than Graph-MT for predicting both pairwise and higher-order interactions in this dataset.The authors caution that party metadata need not fully represent the diversity of Justices’ preferences and voting behavior.Source: Analysis of a Justice dataset · p. 7

The computational efficiency of Hypergraph-MT

Hypergraph-MT’s runtime advantage over clique-expansion methods is greatest on datasets with larger maximum hyperedge sizes. Prediction performance is similar for the two methods on most datasets.

The computational efficiency of Hypergraph-MT

  • Hypergraph-MT and Graph-MT perform similarly in missing-hyperedge prediction on most of the co-sponsorship, committee, co-purchasing, and click datasets.The authors note that predictive performance alone may not determine which method to use, because clique expansion can substantially increase graph size and computational cost.Source: The computational efficiency of… · p. 8
  • Clique-expansion graph size depends on the number and size of hyperedges, so it can grow arbitrarily large relative to the hypergraph.For House bills, the expanded graph has almost 4×10^5 edges compared with 4×10^4 hyperedges.Source: The computational efficiency of… · p. 8
  • For datasets with larger maximum hyperedge size D, Hypergraph-MT runs much faster than Graph-MT; on small-hyperedge data, their runtimes are similar.The authors report an order-of-magnitude difference in running time for the House bills data, where clique expansion produces almost 4×10^5 edges versus 4×10^4 hyperedges.Source: The computational efficiency of… · p. 8

DISCUSSION

The discussion presents Hypergraph-MT as a mixed-membership generative model for overlapping communities and missing-hyperedge prediction. Its reported advantages include faster computation and benefits where higher-order information is lost by dyadic projection.

DISCUSSION

  • Hypergraph-MT jointly offers overlapping-community inference and principled missing-hyperedge prediction, which can assess fit when metadata are unavailable.The discussion describes it as a mixed-membership probabilistic generative model for higher-order interactions.Source: DISCUSSION · p. 8
  • An efficient routine reduces the computational cost of expensive quantities during updates, and Hypergraph-MT runs faster than clique-expansion methods on large-hyperedge data.The authors present this as making the method suitable for higher-order datasets with large hyperedges.Source: DISCUSSION · p. 8
  • The method’s advantage is strongest where hyperedges carry information that dyadic projections can lose; the discussion also reports resilience to added large noisy hyperedges.The Gene-Disease and U.S. Justices analyses are cited as examples of critical hyperedge sizes and communities aligned with hyperedge information.Source: DISCUSSION · p. 8
  • The current formulation uses assortative affinities and one interaction type; extensions to other structures, multilayer interactions, temporal communities, and node attributes remain open directions.The discussion also suggests synthetic hypergraph benchmarks as a possible application.Source: DISCUSSION · p. 8

SUPPORTING INFORMATION (SI)

The SI details Hypergraph-MT’s generative model and efficient EM inference, then describes its regularization options, prediction evaluation, and synthetic-data experiments.

A. INFERENCE OF HYPERGRAPH-MT

  • Hypergraph-MT assigns hyperedges probabilities from node memberships and community affinities, using an assortative model with a D × K affinity matrix and inferring latent variables from observed hypergraphs.A hyperedge containing a node with zero membership in a community has zero probability under that community’s contribution.Source: A. INFERENCE OF HYPERGRAPH-MT · p. 12

A.1. Expectation-Maximization updates

  • EM alternates updates of variational community assignments and model parameters until convergence; ten random initializations are run because each fixed point is only a local maximum.To reduce the cost of membership updates, the algorithm reuses products across nodes and updates them incrementally, reducing the stated complexity to O(NDK).Source: A. INFERENCE OF HYPERGRAPH-MT · p. 12, §A.1 · p. 13

A.2. Priors, regularization, and constraints

  • Exponential priors on memberships and affinities yield L1 regularization, while membership vectors can also be constrained to sum to one.Experiments report the better-performing constrained or unconstrained model.Source: §A.2 · p. 15

B. HYPEREDGE PREDICTION AND CROSS-VALIDATION

  • Missing-hyperedge prediction uses five-fold cross-validation, with Hypergraph-MT trained on hyperedges and Graph-MT trained on their clique expansions; AUC is estimated from balanced positive and negative samples.Pairs-MT uses only size-2 hyperedges, and the other models are also evaluated on pairs to assess the utility of larger hyperedges for pairwise prediction.Source: B. HYPEREDGE PREDICTION AND… · p. 15

C. EXPERIMENTS WITH SYNTHETIC DATA

C.1. Community detection

On synthetic hypergraphs, Hypergraph-MT’s community detection improves as assortative structure strengthens and performs especially well with overlapping communities. It also runs faster than Graph-MT across tested sizes, though a sparse implementation could improve its computational complexity.

C.1. Community detection

  • Hypergraph-MT’s NMI improves as cin/cout increases and it significantly outperforms the other methods except Spectral Clustering, which benefits from a similar inference routine to the data generator.The benchmark uses hard-membership planted partitions; Graph-MT remains low and nearly constant, while Hypergraph AON-MLL stays near zero.Source: §C.1 · p. 16, Figure S1 · p. 17
  • CS = 0.97 for Hypergraph-MT versus CS = 0.85 for Spectral Clustering in a two-community overlap test, and CS = 0.93 versus CS = 0.67 in a three-group test.The benchmark includes nodes with mixed memberships; Hypergraph-MT’s advantage grew in more complicated overlap settings.Source: §C.1 · p. 17

C.2. Time complexity

  • Across tested synthetic sizes, Hypergraph-MT is faster than Graph-MT, and the authors say a sparse implementation could further improve computational complexity.The timing comparison varies node count and reports one-iteration running times.Source: §C.2 · p. 18, Figure S2 · p. 18

D. EXPERIMENTS WITH EMPIRICAL DATA

The empirical evaluation spans contact, gene-disease, judicial, congressional, retail, and hotel datasets. Community counts are generally set from node metadata, although the congressional datasets vary the maximum hyperedge size.

D. EXPERIMENTS WITH EMPIRICAL DATA

  • The number of communities is generally fixed to match node metadata, rather than selected by comparing predictive performance across candidate values.For congressional datasets, the number is set to two from political-party labels, while the maximum hyperedge size D is varied from 2 to 25.Source: D. EXPERIMENTS WITH EMPIRICAL DATA · p. 19
  • Four SocioPatterns datasets cover close-proximity contacts in schools, a workplace, and a hospital, with communities corresponding to classes or hospital roles.The datasets use wearable sensor records; the hospital includes patient and health-care-worker interactions.Source: D. EXPERIMENTS WITH EMPIRICAL DATA · p. 19
  • The Gene-Disease hypergraph links genes to diseases and retains genes with non-missing Disease Pleiotropy Index values and hyperedges of size 2–25.The index is used to set the number of communities.Source: D. EXPERIMENTS WITH EMPIRICAL DATA · p. 19
  • The Justice dataset groups Supreme Court justices by shared case votes from 1946 to 2019, with communities corresponding to the two political parties.Source: D. EXPERIMENTS WITH EMPIRICAL DATA · p. 19
  • Congressional bill co-sponsorship and committee-membership hypergraphs represent legislators and senators, with political-party labels defining two communities.For bill datasets, each hyperedge contains a bill’s sponsor and cosponsors; committee hyperedges represent membership at a specified meeting.Source: D. EXPERIMENTS WITH EMPIRICAL DATA · p. 19
  • Walmart co-purchases and Trivago hotel browsing sessions form hyperedges, with product categories or hotel countries setting community counts.The analysis uses the Walmart 3-core and Trivago 5-core to reduce sparsity.Source: D. EXPERIMENTS WITH EMPIRICAL DATA · p. 19

E. ANALYSIS OF THE GENE-DISEASE DATASET

On the Gene-Disease dataset, Hypergraph-MT outperforms clique-expanded Graph-MT beyond the shift around maximum size D = 15–16. Its predictive gains extend across hyperedge sizes, not only pairs.

E. ANALYSIS OF THE GENE-DISEASE DATASET

  • Beyond the shift around D = 15–16, Hypergraph-MT outperforms clique-expanded Graph-MT in cumulative hyperedge-prediction AUC.The comparison uses means over 5-fold cross-validation test sets.Source: Figure S3 · p. 20
  • The figure measures cumulative AUC for hyperedges of sizes 2 ≤ d ≤ D while varying the maximum size D.Source: Figure S3 · p. 20
  • Hypergraph-MT improves prediction homogeneously across hyperedge sizes, including larger hyperedges rather than only pairs.Source: Figure S3 · p. 20

Related papers

Loading 2204.05646v2…