Truss Decomposition in Hypergraphs

Summary: Introduces hypertruss decomposition, where each node participates in at least k hyper-triangles. Its key contribution is scalable hyper-triangle counting via hybrid edge/node iterators and prefix forests, with ordering optimizations for shared-node hypergraphs. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14058
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,857 | 25.52%
DOI: 10.14778/3734839.3734854

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Hongchao Qin (Beijing Institute of Technology)
2. Guang Zeng (Ant Financial)
3. Rong-Hua Li (Beijing Institute of Technology)
4. Longlong Lin (Southwest University)
5. Ye Yuan (Beijing Institute of Technology)
6. Guoren Wang (Beijing Institute of Technology)

BibTeX Citation

@article{qin_vldb25,
        title = {{Truss Decomposition in Hypergraphs}},
        author = {Qin, Hongchao and Zeng, Guang and Li, Rong-Hua and Lin, Longlong and Yuan, Ye and Wang, Guoren},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {7},
        pages = {2185--2197},
        doi = {10.14778/3734839.3734854},
        url = {https://doi.org/10.14778/3734839.3734854},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
102	Truss Decomposition in Massive Networks	2012	VLDB	0.00034255289
189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026114928
982	Influential Community Search in Large Networks	2015	VLDB	0.0001283311
1,113	Approximate Closest Community Search in Networks	2016	VLDB	0.00012124571
1,640	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010153865
2,635	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.3200595e-05
3,254	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	7.5928992e-05
3,686	Accelerating Triangle Counting on GPU	2021	SIGMOD	7.2029305e-05
3,855	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	7.0712144e-05
4,916	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB	6.4474058e-05
5,697	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	6.1174514e-05
5,977	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	6.0219619e-05
6,465	Fast Algorithms for Core Maximization on Large Graphs	2022	VLDB	5.871325e-05
6,873	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.7495468e-05
7,032	Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach	2023	SIGMOD	5.7222954e-05
8,011	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	5.5074939e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,411	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD
2	7,408	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB
3	2,083	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB
4	8,991	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB
5	1,416	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB
6	2,323	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD
7	9,301	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD
8	11,094	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB
9	102	Truss Decomposition in Massive Networks	2012	VLDB
10	3,503	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB