mlsanityData to 7 Oct 2026

A Survey on Machine Learning Solutions for Graph Pattern Extraction

arXiv 2204.01057 ↗First posted 3 Apr 2022math.CO cs.DM cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

A subgraph is constructed by using a subset of vertices and edges of a given graph. There exist many graph properties that are hereditary for subgraphs. Hence, researchers from different communities have paid a great deal of attention in studying numerous subgraph problems, on top of the ordinary graph problems. Many algorithms are proposed in studying subgraph problems, where one common approach is by extracting the patterns and structures of a given graph. Due to the complex structures of certain types of graphs and to improve overall performances of the existing frameworks, machine learning techniques have recently been employed in dealing with various subgraph problems. In this article, we present a comprehensive review on five well known subgraph problems that have been tackled by using machine learning methods. They are subgraph isomorphism (both counting and matching), maximum common subgraph, community detection and community search problems. We provide an outline of each proposed method, and examine its designs and performances. We also explore non-learning-based algorithms for each problem and a brief discussion is given. We then suggest some promising research directions in this area, hoping that relevant subgraph problems can be tackled by using a similar strategy. Since there is a huge growth in employing machine learning techniques in recent years, we believe that this survey will serve as a good reference point to relevant research communities.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 41 of its 163 references that are in the map. First posted on arXiv 3 Apr 2022.

Builds on

41 of 163 references.

References · 41

  1. 2017Attention Is All You Needcited by 59,932
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  4. 2017Graph Attention Networkscited by 8,854
  5. 2017Inductive Representation Learning on Large Graphscited by 6,284
  6. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  7. 2018How Powerful are Graph Neural Networks?cited by 4,355
  8. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  9. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  10. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  11. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  12. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
29 more
  1. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  2. 2018Conditional Neural Processescited by 421
  3. 2018Deep Learning on Graphs: A Surveycited by 393
  4. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  5. 2019Representation Learning for Dynamic Graphs: A Surveycited by 260
  6. 2020Can Graph Neural Networks Count Substructures?cited by 235
  7. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
  8. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  9. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  10. 2018Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSPcited by 58
  11. 2020Neural Subgraph Matchingcited by 47
  12. 2019Overlapping Community Detection with Graph Neural Networkscited by 45
  13. 2019Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problemscited by 40
  14. 2019Neural Subgraph Isomorphism Countingcited by 27
  15. 2015Infinite Edge Partition Models for Overlapping Community Detection and Link Predictioncited by 23
  16. 2019A Survey of Community Search Over Big Graphscited by 21
  17. 2020GLSearch: Maximum Common Subgraph Detection via Learning to Searchcited by 19
  18. 2020Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Resultscited by 19
  19. 2020Graph Neural Network Encoding for Community Detection in Attribute Networkscited by 17
  20. 2021Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matchingcited by 11
  21. 2015Uncovering the Small Community Structure in Large Networks: A Local Spectral Approachcited by 10
  22. 2015Approximate Closest Community Search in Networkscited by 8
  23. 2016Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communitiescited by 8
  24. 2016Attribute Truss Community Searchcited by 8
  25. 2016Reinforcement learning based local search for grouping problems: A case study on graph coloringcited by 6
  26. 2021Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributedcited by 6
  27. 2022Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matchingcited by 6
  28. 2021Sub-GMN: The Neural Subgraph Matching Network Modelcited by 5
  29. 2021LMKG: Learned Models for Cardinality Estimation in Knowledge Graphscited by 4

Built on by

Not cited yet.