Functional Matching of Logic Subgraphs: Beyond Structural Isomorphism

• URL: http://arxiv.org/abs/2505.21988v1
• Date: Wed, 28 May 2025 05:31:49 GMT
• Title: Functional Matching of Logic Subgraphs: Beyond Structural Isomorphism
• Authors: Ziyang Zheng, Kezhi Li, Zhengyuan Shi, Qiang Xu,
• Abstract summary: Subgraph matching in logic circuits is foundational for numerous Electronic Design Automation (EDA) applications.<n>We introduce the concept of functional subgraph matching, a novel approach that identifies whether a given logic function is implicitly present within a larger circuit.
• Score: 11.568574570864602
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Subgraph matching in logic circuits is foundational for numerous Electronic Design Automation (EDA) applications, including datapath optimization, arithmetic verification, and hardware trojan detection. However, existing techniques rely primarily on structural graph isomorphism and thus fail to identify function-related subgraphs when synthesis transformations substantially alter circuit topology. To overcome this critical limitation, we introduce the concept of functional subgraph matching, a novel approach that identifies whether a given logic function is implicitly present within a larger circuit, irrespective of structural variations induced by synthesis or technology mapping. Specifically, we propose a two-stage multi-modal framework: (1) learning robust functional embeddings across AIG and post-mapping netlists for functional subgraph detection, and (2) identifying fuzzy boundaries using a graph segmentation approach. Evaluations on standard benchmarks (ITC99, OpenABCD, ForgeEDA) demonstrate significant performance improvements over existing structural methods, with average $93.8\%$ accuracy in functional subgraph detection and a dice score of $91.3\%$ in fuzzy boundary identification.

Related papers

• FuncGNN: Learning Functional Semantics of Logic Circuits with Graph Neural Networks [0.0]
  And-Inverter Graph synthesiss (AIGs) are widely adopted for representing Boolean logic in modern circuits.<n>We propose FuncGNN, which integrates hybrid feature aggregation to extract multi-granularity topological patterns.<n>FuncGNN achieves improvements of 2.06% and 18.71%, respectively, while reducing training time by approximately 50.6% and GPU memory usage by about 32.8%.
  arXiv  Detail & Related papers  (2025-06-07T13:04:07Z)
• Homomorphic Encryption of Intuitionistic Logic Proofs and Functional Programs: A Categorical Approach Inspired by Composite-Order Bilinear Groups [0.0]
  We present a conceptual framework for extending homomorphic encryption beyond arithmetic or Boolean operations into the domain of intuitionistic logic.<n>We outline strategies for making the approach potentially efficient, including software optimizations and hardware acceleration.
  arXiv  Detail & Related papers  (2025-02-26T10:10:10Z)
• LASE: Learned Adjacency Spectral Embeddings [7.612218105739107]
  We learn nodal Adjacency Spectral Embeddings (ASE) from graph inputs.<n>LASE is interpretable, parameter efficient, robust to inputs with unobserved edges.<n>LASE layers combine Graph Convolutional Network (GCN) and fully-connected Graph Attention Network (GAT) modules.
  arXiv  Detail & Related papers  (2024-12-23T17:35:19Z)
• RAGFormer: Learning Semantic Attributes and Topological Structure for Fraud Detection [8.050935113945428]
  We present a novel framework called Relation-Aware GNN with transFormer(RAGFormer)<n>RAGFormer embeds both semantic and topological features into a target node.<n>The simple yet effective network consists of a semantic encoder, a topology encoder, and an attention fusion module.
  arXiv  Detail & Related papers  (2024-02-27T12:53:15Z)
• Homomorphism Counts for Graph Neural Networks: All About That Basis [8.25219440625445]
  We argue for a more fine-grained approach, which incorporates the homomorphism counts of all structures in the basis'' of the target pattern. This yields strictly more expressive architectures without incurring any additional overhead in terms of computational complexity.
  arXiv  Detail & Related papers  (2024-02-13T16:57:06Z)
• Logical recognition method for solving the problem of identification in the Internet of Things [0.0]
  The goal of this work is to develop a logical method for object recognition consisting of a reference table with logical features and classes of non-intersecting objects. The method consists of considering the reference table as a logical function that is not defined everywhere and constructing an optimal continuation of the logical function to the entire feature space.
  arXiv  Detail & Related papers  (2024-02-06T19:20:58Z)
• Dynamic Perceiver for Efficient Visual Recognition [87.08210214417309]
  We propose Dynamic Perceiver (Dyn-Perceiver) to decouple the feature extraction procedure and the early classification task. A feature branch serves to extract image features, while a classification branch processes a latent code assigned for classification tasks. Early exits are placed exclusively within the classification branch, thus eliminating the need for linear separability in low-level features.
  arXiv  Detail & Related papers  (2023-06-20T03:00:22Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Graph Adaptive Semantic Transfer for Cross-domain Sentiment Classification [68.06496970320595]
  Cross-domain sentiment classification (CDSC) aims to use the transferable semantics learned from the source domain to predict the sentiment of reviews in the unlabeled target domain. We present Graph Adaptive Semantic Transfer (GAST) model, an adaptive syntactic graph embedding method that is able to learn domain-invariant semantics from both word sequences and syntactic graphs.
  arXiv  Detail & Related papers  (2022-05-18T07:47:01Z)
• Real-Time Scene Text Detection with Differentiable Binarization and Adaptive Scale Fusion [62.269219152425556]
  segmentation-based scene text detection methods have drawn extensive attention in the scene text detection field. We propose a Differentiable Binarization (DB) module that integrates the binarization process into a segmentation network. An efficient Adaptive Scale Fusion (ASF) module is proposed to improve the scale robustness by fusing features of different scales adaptively.
  arXiv  Detail & Related papers  (2022-02-21T15:30:14Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• LogicalFactChecker: Leveraging Logical Operations for Fact Checking with Graph Module Network [111.24773949467567]
  We propose LogicalFactChecker, a neural network approach capable of leveraging logical operations for fact checking. It achieves the state-of-the-art performance on TABFACT, a large-scale, benchmark dataset.
  arXiv  Detail & Related papers  (2020-04-28T17:04:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.