Local Hyper-flow Diffusion

Kimon Fountoulakis, Pan Li, Shenghao Yang

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 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 many 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.

The Challenge of Local Hypergraph Clustering

Hypergraphs generalize standard graphs by allowing a single "hyperedge" to connect more than two nodes, making them ideal for modeling complex group interactions like co-authorship or multi-species food webs. A common task is local hypergraph clustering: finding a dense community around a specific "seed" node without processing the entire graph.

While graph diffusion is a standard tool for this, existing hypergraph methods suffer from significant limitations. They often only support simple "unit" cut-costs (where any split of a hyperedge costs the same) and their theoretical approximation errors typically degrade as hyperedge sizes increase. Furthermore, none could handle general submodular cut-costs, which are essential for modeling asymmetric penalties when separating specific subsets of nodes.

Methodology: A Primal-Dual Approach to Hyper-Flow

The authors introduce Hyper-Flow Diffusion (HFD), formulated as a convex optimization problem with a primal-dual structure:

  • The Primal Problem (Network Flow): This is modeled as routing initial mass from seed nodes to neighbors over hyperedges. The flow is constrained by the specific submodular cut-cost function of each hyperedge.
  • The Dual Problem (Cut-based): This involves assigning "heights" to nodes to separate the seed mass from the rest of the graph, penalized by an $\ell_2$-norm on the cut-costs.
Visualizing the routing of mass and flow values between nodes in the primal problem.

To solve this efficiently, the authors use a mathematical relaxation (the $\sigma$ parameter) that allows a controlled amount of "excess mass" to remain on nodes. This makes the problem separable and solvable via a highly parallelizable Alternating Minimization (AM) algorithm.

The Power of Submodular Cut-Costs

A major innovation of HFD is its support for general submodular cut-costs. In many real-world scenarios, treating all splits of a hyperedge equally is insufficient. For example, in a food web, separating a predator from its prey should logically incur a different cost than separating two similar prey species.

Modeling a network motif as a hyperedge with specific, asymmetric submodular cut-costs.

HFD is the first local diffusion method flexible enough to model these nuanced relationships. This flexibility allowed the researchers to achieve logically meaningful node-ranking results in complex networks where standard methods failed.

Key Insights and Results

  • Edge-Size Independence: HFD achieves a Cheeger-type quadratic approximation error that does not degrade as hyperedges grow larger, a significant theoretical leap over prior work.
  • Strict Locality: The algorithm is genuinely local; the number of non-zero nodes in the optimal solution depends only on the initial mass size, ensuring it scales to massive datasets.
  • Performance: On the Amazon-reviews dataset, HFD improved F1 scores by up to 52% over baselines. In the Florida Bay food network, using specialized submodular costs (S-HFD) improved F1 scores by 20% and correctly grouped similar species.

Conclusion

Hyper-Flow Diffusion represents a significant advancement in local hypergraph analysis. By combining edge-size-independent guarantees with the flexibility of submodular cut-costs, it provides a robust and scalable tool for uncovering the local structure of complex, higher-order networks. While proving the worst-case running time of the AM algorithm remains an open theoretical challenge, its empirical efficiency and accuracy make it a new state-of-the-art for the field.

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 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 many 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