Hypergraph partitioning using tensor eigenvalue decomposition.

Area of Science:

• Machine Learning
• Graph Theory
• Data Mining

Background:

• Hypergraphs offer a more comprehensive way to model complex relationships than traditional graphs.
• Existing hypergraph partitioning methods often lose information by reducing hypergraphs to graphs.

Purpose of the Study:

• To propose a novel tensor-based approach for partitioning k-uniform hypergraphs.
• To overcome the limitations of graph reduction methods in capturing super-dyadic interactions.

Main Methods:

• Utilizing tensor-based representations for hypergraphs to capture super-dyadic interactions.
• Extending graph cut notions (min-ratio-cut, normalized-cut) to hypergraphs using Laplacian tensor eigenvalue decomposition.
• Developing a hypergraph partitioning algorithm inspired by spectral graph theory and introducing a 'hyperedge score' metric.

Main Results:

• The proposed method effectively captures super-dyadic interactions, outperforming graph reduction techniques.
• A tighter upper bound for the minimum positive eigenvalue of even-order hypergraph Laplacian tensors was derived.
• Numerical experiments on synthetic hypergraphs demonstrated the efficacy of the proposed partitioning method.

Conclusions:

• The tensor-based approach provides a superior framework for hypergraph partitioning compared to existing methods.
• The novel formulation enhances the ability to analyze and partition complex relational data represented by hypergraphs.