Graph Iso/Auto-morphism: A Divide-&-Conquer Approach

Summary: Introduces DviCL, divide-and-conquer labeling using the k-th minimum permutation; builds AutoTree to preserve automorphisms. Enables efficient automorphism-group and SSM; root labeling derives from child labels, beating state-of-the-art on 22 graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6162
Venue: SIGMOD
Year: 2021
Pagerank: 5.093636e-05
Overall Rank: 11,666 | 19.97%
DOI: 10.1145/3448016.3452820

Incoming Non-self Citations Over Time

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

Authors

1. Can Lu (Chinese University of Hong Kong)
2. Jeffrey Xu Yu (Chinese University of Hong Kong)
3. Zhiwei Zhang (Beijing Institute of Technology)
4. Hong Cheng (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{lu_sigmod21,
        title = {{Graph Iso/Auto-morphism: A Divide-\&-Conquer Approach}},
        author = {Lu, Can and Yu, Jeffrey Xu and Zhang, Zhiwei and Cheng, Hong},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3452820},
        url = {https://dl.acm.org/doi/10.1145/3448016.3452820},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017717377
1,509	Finding the Maximum Clique in Massive Graphs	2017	VLDB	0.00010539891
1,531	Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study	2017	SIGMOD	0.00010472526

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
2	485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD
3	2,453	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD
4	2,860	Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs	2022	VLDB
5	1,036	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD
6	1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB
7	1,006	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD
8	2,718	Graph Homomorphism Revisited for Graph Matching	2010	VLDB
9	9,759	Divide & Conquer: I/O Efficient Depth-First Search	2015	SIGMOD
10	1,487	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB