Learning to count isomorphisms with graph neural networks
Subgraph isomorphism counting is an important problem on graphs, as many graph-based tasks exploit recurring subgraph patterns. Classical methods usually boil down to a backtracking framework that needs to navigate a huge search space with prohibitive computational costs. Some recent studies resort...
Saved in:
Main Authors: | , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2023
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/8178 https://ink.library.smu.edu.sg/context/sis_research/article/9181/viewcontent/AAAI23_CountGNN.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-9181 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-91812023-09-26T10:28:18Z Learning to count isomorphisms with graph neural networks YU, Xingtong LIU, Zemin FANG, Yuan ZHANG, Xinming Subgraph isomorphism counting is an important problem on graphs, as many graph-based tasks exploit recurring subgraph patterns. Classical methods usually boil down to a backtracking framework that needs to navigate a huge search space with prohibitive computational costs. Some recent studies resort to graph neural networks (GNNs) to learn a low-dimensional representation for both the query and input graphs, in order to predict the number of subgraph isomorphisms on the input graph. However, typical GNNs employ a node-centric message passing scheme that receives and aggregates messages on nodes, which is inadequate in complex structure matching for isomorphism counting. Moreover, on an input graph, the space of possible query graphs is enormous, and different parts of the input graph will be triggered to match different queries. Thus, expecting a fixed representation of the input graph to match diversely structured query graphs is unrealistic. In this paper, we propose a novel GNN called Count-GNN for subgraph isomorphism counting, to deal with the above challenges. At the edge level, given that an edge is an atomic unit of encoding graph structures, we propose an edge-centric message passing scheme, where messages on edges are propagated and aggregated based on the edge adjacency to preserve fine-grained structural information. At the graph level, we modulate the input graph representation conditioned on the query, so that the input graph can be adapted to each query individually to improve their matching. Finally, we conduct extensive experiments on a number of benchmark datasets to demonstrate the superior performance of Count-GNN. 2023-02-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/8178 info:doi/10.48550/arXiv.2302.03266 https://ink.library.smu.edu.sg/context/sis_research/article/9181/viewcontent/AAAI23_CountGNN.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Classical methods Computational costs Graph neural networks Graph-based Input graphs Message-passing Query graph Search spaces Subgraph isomorphism Subgraphs Information Security |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Classical methods Computational costs Graph neural networks Graph-based Input graphs Message-passing Query graph Search spaces Subgraph isomorphism Subgraphs Information Security |
spellingShingle |
Classical methods Computational costs Graph neural networks Graph-based Input graphs Message-passing Query graph Search spaces Subgraph isomorphism Subgraphs Information Security YU, Xingtong LIU, Zemin FANG, Yuan ZHANG, Xinming Learning to count isomorphisms with graph neural networks |
description |
Subgraph isomorphism counting is an important problem on graphs, as many graph-based tasks exploit recurring subgraph patterns. Classical methods usually boil down to a backtracking framework that needs to navigate a huge search space with prohibitive computational costs. Some recent studies resort to graph neural networks (GNNs) to learn a low-dimensional representation for both the query and input graphs, in order to predict the number of subgraph isomorphisms on the input graph. However, typical GNNs employ a node-centric message passing scheme that receives and aggregates messages on nodes, which is inadequate in complex structure matching for isomorphism counting. Moreover, on an input graph, the space of possible query graphs is enormous, and different parts of the input graph will be triggered to match different queries. Thus, expecting a fixed representation of the input graph to match diversely structured query graphs is unrealistic. In this paper, we propose a novel GNN called Count-GNN for subgraph isomorphism counting, to deal with the above challenges. At the edge level, given that an edge is an atomic unit of encoding graph structures, we propose an edge-centric message passing scheme, where messages on edges are propagated and aggregated based on the edge adjacency to preserve fine-grained structural information. At the graph level, we modulate the input graph representation conditioned on the query, so that the input graph can be adapted to each query individually to improve their matching. Finally, we conduct extensive experiments on a number of benchmark datasets to demonstrate the superior performance of Count-GNN. |
format |
text |
author |
YU, Xingtong LIU, Zemin FANG, Yuan ZHANG, Xinming |
author_facet |
YU, Xingtong LIU, Zemin FANG, Yuan ZHANG, Xinming |
author_sort |
YU, Xingtong |
title |
Learning to count isomorphisms with graph neural networks |
title_short |
Learning to count isomorphisms with graph neural networks |
title_full |
Learning to count isomorphisms with graph neural networks |
title_fullStr |
Learning to count isomorphisms with graph neural networks |
title_full_unstemmed |
Learning to count isomorphisms with graph neural networks |
title_sort |
learning to count isomorphisms with graph neural networks |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2023 |
url |
https://ink.library.smu.edu.sg/sis_research/8178 https://ink.library.smu.edu.sg/context/sis_research/article/9181/viewcontent/AAAI23_CountGNN.pdf |
_version_ |
1779157192232927232 |