STruD: Truss Decomposition of Simplicial Complexes

Giulia Preti, Gianmarco De Francisci Morales, Francesco Bonchi

Abstract

This paper introduces STruD (Simplicial Truss Decomposition), a novel framework that generalizes truss decomposition from graphs to simplicial complexes. By accounting for $n$-ary relationships, STruD identifies cohesive higher-order communities in complex networks. The authors present a memory-aware, scalable algorithm that utilizes a-priori pruning and out-of-core operations to manage combinatorial complexity. Evaluation on real-world datasets demonstrates that simplicial trussness uncovers structural nuances lost in traditional graph-based analysis and provides a robust filtration for topological data analysis.

Introduction

Traditional network analysis often reduces complex interactions to binary edges. However, many real-world phenomena involve group-based interactions, such as co-authorship or multi-recipient emails. Simplicial complexes offer a more faithful representation of these interactions by modeling them as simplices (triangles, tetrahedra, etc.). While graph truss decomposition is a popular method for finding dense, triangle-rich communities, extending this concept to higher-order structures is computationally challenging due to the "downward closure" property: any interaction among a group implies interactions among all its subgroups.

Comparison between a simplicial complex (left) and its graph representation (right).

Methods

STruD defines the Simplicial $k$-truss by introducing "joists"—higher-order structures that provide support for a simplex. To handle the potential combinatorial explosion of data, the algorithm employs several key technical strategies:

  • A-priori Pruning: Borrowing from frequent itemset mining, the algorithm uses the property that a $(q+1)$-dimensional simplex cannot have higher trussness than the $q$-dimensional faces it contains. This allows for massive search-space pruning.
  • Memory-Aware Architecture: STruD uses a compact inverted index and a strategy that switches to "out-of-core" (disk-based) operations when the dataset exceeds available RAM, ensuring scalability for massive datasets like DBLP.
  • Top-N Variant: A specialized version of the algorithm that finds only the most cohesive structures without computing the full decomposition, facilitating rapid exploratory analysis.

Results and Key Insights

The authors evaluated STruD on diverse datasets, including DBLP co-authorship, Enron emails, and financial ETF correlations.

Richness vs. Simplicity

A primary finding is that simplicial trussness reveals structural information that is lost when "flattening" data into a simple graph. For instance, in the ETF dataset, the size distribution of simplicial trusses is concave, whereas the graph-based version is convex. This indicates the presence of significant higher-order clusters that graph-based methods fail to distinguish.

Size distribution comparison between Graph k-Truss (left) and Simplicial k-Truss (right).

Topological Data Analysis (TDA)

STruD also serves as an effective "filtration" for Persistent Homology. This allows researchers to identify topological features, such as "holes" or "voids," that persist across different levels of cohesion. Furthermore, the authors demonstrate that simplicial trussness can quantify "manifoldness"—how much a dataset deviates from a smooth, locally Euclidean space. Real-world data like DBLP shows highly heterogeneous, "clumpy" behavior compared to perfect manifolds.

Conclusion

STruD provides a scalable and memory-efficient solution for uncovering higher-order cohesion in complex networks. By successfully processing datasets with millions of vertices and identifying structures up to dimension 17, the algorithm proves practical for large-scale analysis. Future work includes parallelizing the algorithm and exploring its application in domains such as protein-protein interaction networks and brain functional connectivity.

Summary updated

Abstract

A simplicial complex is a generalization of a graph: a collection of n-ary relationships (instead of binary as the edges of a graph), named simplices. In this paper, we develop a new tool to study the structure of simplicial complexes: we generalize the graph notion of truss decomposition to complexes, and show that this more powerful representation gives rise to different properties compared to the graph-based one. This power, however, comes with important computational challenges derived from the combinatorial explosion caused by the downward closure property of complexes. Drawing upon ideas from itemset mining and similarity search, we design a memory-aware algorithm, dubbed STruD, which is able to efficiently compute the truss decomposition of a simplicial complex. STruD adapts its behavior to the amount of available memory by storing intermediate data in a compact way. We then devise a variant that computes directly the n simplices of maximum trussness. By applying STruD to several datasets, we prove its scalability, and provide an analysis of their structure. Finally, we show that the truss decomposition can be seen as a filtration, and as such it can be used to study the persistent homology of a dataset, a method for computing topological features at different spatial resolutions, prominent in Topological Data Analysis.
BibTeX
@inproceedings{preti2021strud,
  author = {Giulia Preti and Gianmarco De Francisci Morales and Francesco Bonchi},
  title = {{STruD: Truss Decomposition of Simplicial Complexes}},
  booktitle = {The Web Conference},
  year = {2021},
  url = {https://openreview.net/forum?id=6beoTF1TJTK},
}
Figure