Fast Circuit Analysis via Neighborhood-Guided Maximum Common Subgraph

Identifying shared sub-circuits is vital for digital design synthesis, verification, and similarity analysis. This paper introduces a novel heuristic for the Maximum Common Subgraph (MCS) problem optimized for large-scale, sparse circuit graphs through two primary contributions. First, we propose an information-dense graph representation using labeled nodes and edges to eliminate redundant vertices, reducing node counts by over 5x and edge counts by 2x without sacrificing expressiveness. These labels effectively prune the search space by highlighting structural incompatibilities. Second, we implement an improved topologically driven heuristic that extends the matching radius and employs a dampening factor to weight node contribution, inspired by message-passing concepts in graph learning. By aggregating information from both fan-in and fan-out cones, we significantly enhance matching accuracy. Experimentally, we introduce an iterative McSplit variant that utilizes adjacency lists to enhance memory efficiency for massive designs. Evaluations on synthetic benchmarks and real-world cases, such as a RISC-V core, demonstrate that our approach substantially outperforms state-of-the-art methods in scalability and practical utility.