Higher-order trade-offs in hypergraph community detection

Area of Science:

• Network Science
• Data Mining
• Statistical Physics

Background:

• Community detection traditionally focuses on pairwise networks.
• Hypergraphs present unique challenges due to structural heterogeneity and varying hyperedge orders.
• Existing algorithms face difficulties in handling non-uniform hypergraphs and balancing hyperedge splits.

Purpose of the Study:

• To develop a unified framework for community detection in non-uniform hypergraphs.
• To introduce a quantitative analysis of trade-offs in hyperedge partitioning within higher-order networks.
• To enable principled model selection and efficient spectral clustering for hypergraph data.

Main Methods:

• Development of a unified framework based on the hypergraph stochastic block model.
• Introduction of a general signal-to-noise ratio for analyzing higher-order network trade-offs.
• Derivation of a Bethe Hessian operator for spectral clustering in non-uniform hypergraphs.

Main Results:

• A novel spectral clustering method for non-uniform hypergraphs is presented.
• Analytical predictions for spectral detectability thresholds are derived and compared to belief propagation limits.
• Synthetic experiments reveal biases towards preserving higher-order and balanced hyperedges.

Conclusions:

• The proposed framework effectively addresses challenges in hypergraph community detection.
• The study highlights the importance of considering higher-order detectability trade-offs in real-world systems.
• The methods provide a principled approach to analyzing complex network structures beyond pairwise interactions.