Uncertainty-aware Efficient Subgraph Isomorphism using Graph Topology

2022-09-15 · Arpan Kusari, Wenbo Sun

Subgraph isomorphism or subgraph matching is generally considered as an NP-complete problem, made more complex in practical applications where the edge weights take real values and are subject to measurement noise and possible anomalies. To the best of our knowledge, almost all subgraph matching methods utilize node labels to perform node-node matching. In the absence of such labels (in applications such as image matching and map matching among others), these subgraph matching methods do not work. We propose a method for identifying the node correspondence between a subgraph and a full graph in the inexact case without node labels in two steps - (a) extract the minimal unique topology preserving subset from the subgraph and find its feasible matching in the full graph, and (b) implement a consensus-based algorithm to expand the matched node set by pairing unique paths based on boundary commutativity. Going beyond the existing subgraph matching approaches, the proposed method is shown to have realistically sub-linear computational efficiency, robustness to random measurement noise, and good statistical properties. Our method is also readily applicable to the exact matching case without loss of generality. To demonstrate the effectiveness of the proposed method, a simulation and a case study is performed on the Erdos-Renyi random graphs and the image-based affine covariant features dataset respectively.

📄 PDF Abstract BibTeX arXiv:2209.09090

Code (0)

등록된 구현이 없습니다.

Tasks

Computational Efficiency

Neural Subgraph Isomorphism Counting

2019-12-25 · Xin Liu, Haojie Pan, Mutian He, Yangqiu Song 외

In this paper, we study a new graph learning problem: learning to count subgraph isomorphisms. Different from other traditional graph learning problems such as node classification and link prediction, subgraph isomorphis…

Domain Adaptation Graph Learning Link Prediction Node Classification+2

Hierarchical Topology Isomorphism Expertise Embedded Graph Contrastive Learning

2023-12-21 · Jiangmeng Li, Yifan Jin, Hang Gao, Wenwen Qiang 외

Graph contrastive learning (GCL) aims to align the positive features while differentiating the negative features in the latent space by minimizing a pair-wise contrastive loss. As the embodiment of an outstanding discrim…

Contrastive Learning Graph Representation Learning Representation Learning Transfer Learning

Topology-Informed Graph Transformer

2024-02-03 · Yun Young Choi, Sun Woo Park, Minho Lee, Youngho Woo

Transformers have revolutionized performance in Natural Language Processing and Vision, paving the way for their integration with Graph Neural Networks (GNNs). One key challenge in enhancing graph transformers is strengt…

Graph Classification Graph Regression Inductive Bias Node Classification

Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching

2021-12-16 · Xin Liu, Yangqiu Song

Graph neural networks (GNNs) and message passing neural networks (MPNNs) have been proven to be expressive for subgraph structures in many applications. Some applications in heterogeneous graphs require explicit edge mod…

Node Classification Representation Learning

FedTAD: Topology-aware Data-free Knowledge Distillation for Subgraph Federated Learning

2024-04-22 · Yinlin Zhu, Xunkai Li, Zhengyu Wu, Di wu 외

Subgraph federated learning (subgraph-FL) is a new distributed paradigm that facilitates the collaborative training of graph neural networks (GNNs) by multi-client subgraphs. Unfortunately, a significant challenge of sub…

Data-free Knowledge Distillation Federated Learning Knowledge Distillation Transfer Learning