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: hba4bb6f976f8e496
Venue: VLDB
Year: 2025
Pagerank: 5.3350162e-05
Overall Rank: 8,419 | 43.40%
DOI: 10.14778/3734839.3734854

Incoming Non-self Citations Over Time

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 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,806	Efficient Hyper-truss Decomposition over Hypergraphs	2026	VLDB	4.9793485e-05

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
100	Truss Decomposition in Massive Networks	2012	VLDB	0.00033977856
184	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026100147
1,007	Influential Community Search in Large Networks	2015	VLDB	0.00012556573
1,129	Approximate Closest Community Search in Networks	2016	VLDB	0.00011903608
1,648	Distance-generalized Core Decomposition	2019	SIGMOD	9.9863775e-05
2,669	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.1531412e-05
3,314	Accelerating Triangle Counting on GPU	2021	SIGMOD	7.4380767e-05
3,318	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	7.4324312e-05
3,867	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	6.9581326e-05
4,314	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB	6.6695257e-05
5,720	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	6.018559e-05
6,061	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	5.8988316e-05
6,548	Fast Algorithms for Core Maximization on Large Graphs	2022	VLDB	5.7507029e-05
6,968	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.6316571e-05
7,043	Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach	2023	SIGMOD	5.6141221e-05
8,066	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	5.3950351e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,547	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB
2	2,119	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB
3	9,150	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB
4	1,443	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB
5	2,086	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD
6	9,474	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD
7	11,446	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB
8	100	Truss Decomposition in Massive Networks	2012	VLDB
9	3,495	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB
10	10,806	Efficient Hyper-truss Decomposition over Hypergraphs	2026	VLDB