Functional Matching of Logic Subgraphs: Beyond Structural Isomorphism

• URL: http://arxiv.org/abs/2505.21988v2
• Date: Wed, 08 Oct 2025 06:16:46 GMT
• Title: Functional Matching of Logic Subgraphs: Beyond Structural Isomorphism
• Authors: Ziyang Zheng, Kezhi Li, Zhengyuan Shi, Qiang Xu,
• Abstract summary: Subgraph matching 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: 13.064477057274226
• 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. The source code and implementation details can be found at https://github.com/zyzheng17/Functional_Subgraph_Matching-Neurips25.

Related papers

• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  We propose SWING: Space Walks for Implicit Network Graphs, a new class of algorithms for computations involving Graph Random Features on graphs.<n>We provide detailed analysis of SWING and complement it with thorough experiments on different classes of i-graphs.
  arXiv  Detail & Related papers  (2026-02-13T08:12:38Z)
• Beyond Pixels: Vector-to-Graph Transformation for Reliable Schematic Auditing [34.54168175788343]
  We propose a Vector-to-Graph (V2G) pipeline that converts CAD diagrams into property graphs where nodes represent components and edges encode connectivity.<n>On a diagnostic benchmark of electrical compliance checks, V2G yields large accuracy gains across all error categories, while leading MLLMs remain near chance level.
  arXiv  Detail & Related papers  (2026-02-12T07:50:49Z)
• Beyond Softmax: A Natural Parameterization for Categorical Random Variables [61.709831225296305]
  We introduce the $textitcatnat$ function, a function composed of a sequence of hierarchical binary splits.<n>A rich set of experiments show that the proposed function improves the learning efficiency and yields models characterized by consistently higher test performance.
  arXiv  Detail & Related papers  (2025-09-29T12:55:50Z)
• 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)
• Learning Implicit Feature Alignment Function for Semantic Segmentation [51.36809814890326]
  Implicit Feature Alignment function (IFA) is inspired by the rapidly expanding topic of implicit neural representations. We show that IFA implicitly aligns the feature maps at different levels and is capable of producing segmentation maps in arbitrary resolutions. Our method can be combined with improvement on various architectures, and it achieves state-of-the-art accuracy trade-off on common benchmarks.
  arXiv  Detail & Related papers  (2022-06-17T09:40:14Z)
• 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)
• Logic Constrained Pointer Networks for Interpretable Textual Similarity [11.142649867439406]
  We introduce a novel pointer network based model with a sentinel gating function to align constituent chunks. We improve this base model with a loss function to equally penalize misalignments in both sentences, ensuring the alignments are bidirectional. The model achieves an F1 score of 97.73 and 96.32 on the benchmark SemEval datasets for the chunk alignment task.
  arXiv  Detail & Related papers  (2020-07-15T13:01:44Z)
• 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.