Local Hyper-Flow Diffusion

Kimon Fountoulakis, Pan Li, Shenghao Yang

Introduction

In many real-world systems—such as social networks, recommendation engines, or biological food webs—relationships extend beyond simple pairwise connections. These "higher-order" relationships are best modeled by hypergraphs, where "hyperedges" can encompass any number of nodes (e.g., multiple authors collaborating on a single paper).

A fundamental task in network analysis is local clustering: given a small set of "seed" nodes, the goal is to identify the tightly-knit community they belong to without processing the entire massive network. While diffusion methods like PageRank excel on standard graphs, hypergraphs introduce a significant challenge: how do we mathematically penalize the splitting of a hyperedge?

Existing methods often oversimplify this by assuming every split incurs the same "unit cut-cost," or they use "cardinality-based" penalties that suffer from errors scaling with hyperedge size. Crucially, prior local methods could not handle submodular cut-costs, which allow for highly specific, non-linear penalties essential for capturing complex real-world dynamics. This paper introduces Local Hyper-Flow Diffusion (HFD), the first local clustering method for hypergraphs that provides theoretical guarantees independent of hyperedge size while supporting general submodular cut-costs.

Methodology: Hyper-Flow Diffusion

The authors formulate HFD as a convex optimization problem featuring an elegant primal-dual structure:

  1. The Primal Problem (Flow): This formulation offers a natural network flow interpretation. Imagine "mass" (representing information or influence) starting at the seed nodes and spreading through the hyperedges. The objective is to route this flow efficiently while strictly respecting the capacities defined by the hyperedge cut-costs.
  2. The Dual Problem (Cuts): The dual assigns "heights" to nodes. Nodes retaining high mass (near the seeds) receive higher values, while distant nodes receive lower values. The steepness of the height change across a hyperedge directly relates to the cut-cost. By performing a "sweep cut"—sorting nodes by height and finding the optimal threshold—the algorithm extracts the final local cluster.
Illustration comparing mass flow routing through standard graphs versus hyperedges.

To solve this optimization efficiently, the researchers employ an Alternating Minimization (AM) algorithm. A defining feature of this approach is that it is "strongly local": it only processes nodes and hyperedges actively involved in the diffusion. Consequently, its computational complexity depends on the size of the output cluster rather than the entire hypergraph, enabling it to scale to networks with millions of nodes.

Key Insights and Theoretical Guarantees

HFD introduces several major theoretical advancements for hypergraph analysis:

  • Edge-Size Independence: HFD is the first local method to achieve a "Cheeger-type" guarantee—a rigorous bound on cluster quality—that does not degrade as hyperedges grow larger. This makes the method exceptionally robust for datasets characterized by massive, complex groupings.
  • The Power of Submodularity: By supporting general submodular functions, HFD can model asymmetric relationships. For instance, in an ecological food web, the algorithm can be tuned to recognize that predators and prey belong to distinct functional groups, even if they share a hyperedge.
Comparison of cut-cost penalties when splitting a standard graph versus a hypergraph.
  • Sparsity Equals Efficiency: The authors mathematically prove that the number of "active" nodes in their optimal solution remains independent of the total hypergraph size. This theoretical locality is the engine driving its practical performance on massive datasets.

Empirical Results

The researchers evaluated HFD against several benchmarks, including a synthetic generalized Hypergraph Stochastic Block Model (HSBM) and massive real-world datasets like Amazon-reviews (2.2M nodes, 4.2M hyperedges) and Trivago-clicks.

  • Superior Accuracy: On the Amazon-reviews dataset, HFD improved F1 scores (measuring precision and recall) by up to 52% over previous state-of-the-art methods (such as LH and ACL) for specific clusters.
  • Robustness to Noise: In synthetic HSBM tests, HFD maintained high performance even as ground-truth clusters became increasingly noisy, whereas competing methods degraded rapidly.
  • Meaningful Ranking: In a Florida Bay food network dataset, only the submodular variant of HFD (S-HFD) successfully ranked similar species together. Simpler cut-cost models failed to capture the underlying ecological structure.

Limitations and Future Work

While the HFD algorithm is empirically fast and strongly local, the authors note that proving the worst-case running time of their Alternating Minimization scheme remains an open theoretical challenge. Future work will also explore different $p$-norm versions of the model (beyond the standard $\ell_2$-norm), which could yield even tighter theoretical guarantees for hypergraph clustering.

Summary updated

Abstract

Recently, hypergraphs have attracted a lot of attention due to their ability to capture complex relations among entities. The insurgence of hypergraphs has resulted in data of increasing size and complexity that exhibit interesting small-scale and local structure, e.g., small-scale communities and localized node-ranking around a given set of seed nodes. Popular and principled ways to capture the local structure are the local hypergraph clustering problem and the related seed set expansion problem. In this work, we propose the first local diffusion method that achieves edge-size-independent Cheeger-type guarantee for the problem of local hypergraph clustering while applying to a rich class of higher-order relations that covers a number of previously studied special cases. Our method is based on a primal-dual optimization formulation where the primal problem has a natural network flow interpretation, and the dual problem has a cut-based interpretation using the $\ell_2$-norm penalty on associated cut-costs. We demonstrate the new technique is significantly better than state-of-the-art methods on both synthetic and real-world data.
BibTeX
@inproceedings{fountoulakis2021local,
  author = {Kimon Fountoulakis and Pan Li and Shenghao Yang},
  title = {{Local Hyper-Flow Diffusion}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=HCkJQJyoHN},
}
Figure