A Survey on Machine Learning Solutions for Graph Pattern Extraction (2022-04-03T00:00:00.000000Z)

TL;DR

A comprehensive review on five well known subgraph problems that have been tackled by using machine learning methods, including subgraph isomorphism (both counting and matching), maximum common subgraph, community detection and community search problems.

Abstract

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.

Authors

Chenhao Ma

2 papers

Reynold Cheng

2 papers

Kai Siong Yow

1 papers

TL;DR

Abstract

Authors

References161 items

COCLEP: Contrastive Learning-based Semi-Supervised Community Search

AEDNet: Adaptive Edge-Deleting Network For Subgraph Matching

ICS-GNN $$^+$$ + : lightweight interactive community search via graph neural network

Interpretable Neural Subgraph Matching for Graph Retrieval

Neural Subgraph Counting with Wasserstein Estimator

DMCS : Density Modularity based Community Search

Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching

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

Active Learning for the Subgraph Matching Problem

On Directed Densest Subgraph Discovery

Foundations of Machine Learning

A Learned Sketch for Subgraph Counting

A Comprehensive Survey on Community Detection With Deep Learning

Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art

Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed

Sub-GMN: The Neural Subgraph Matching Network Model

Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art

LMKG: Learned Models for Cardinality Estimation in Knowledge Graphs

Combinatorial optimization and reasoning with graph neural networks

Subgraph Matching on Multiplex Networks

Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results

Multiobjective Optimization and Local Merge for Clustering Attributed Graphs

Community detection using unsupervised machine learning techniques on COVID-19 dataset

Neural Subgraph Matching

Graph Neural Network Encoding for Community Detection in Attribute Networks

G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching

In-Memory Subgraph Matching: An In-depth Study

A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems

Reinforcement Learning for Combinatorial Optimization: A Survey

Can graph neural networks count substructures?

GLSearch: Maximum Common Subgraph Detection via Learning to Search

Effective and efficient community search over large heterogeneous information networks

A local search algorithm with reinforcement learning based repair procedure for minimum weight independent dominating set

Neural Subgraph Isomorphism Counting

Using Statistical Measures and Machine Learning for Graph Reduction to Solve Maximum Weight Clique Problems

Effective and Efficient Community Search Over Large Directed Graphs

Neural Maximum Common Subgraph Detection with Guided Subgraph Extraction

Representation Learning for Dynamic Graphs: A Survey

Scalable Subgraph Counting: The Methods Behind The Madness

Approximation Ratios of Graph Neural Networks for Combinatorial Problems

A survey of community search over big graphs

Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems

Graph Neural Networks: A Review of Methods and Applications

Deep Learning on Graphs: A Survey

Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon

On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties

Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

How Powerful are Graph Neural Networks?

Overlapping Community Detection with Graph Neural Networks

Factorisation of Greedoid Polynomials of Rooted Digraphs

Learning to Solve NP-Complete Problems - A Graph Neural Network for the Decision TSP

Conditional Neural Processes

A Multiobjective Evolutionary Algorithm Based on Structural and Attribute Similarities for Community Detection in Attributed Networks

Learning Heuristics for the TSP by Policy Gradient

VizCS: Online Searching and Visualizing Communities in Dynamic Graphs

Tutte Invariants for Alternating Dimaps

Graph Attention Networks

Mastering the game of Go without human knowledge

Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks

Semi-supervised Learning over Heterogeneous Information Networks by Ensemble of Meta-graph Guided Random Walks

A Partitioning Algorithm for Maximum Common Subgraph Problems

Attention is All you Need

Inductive Representation Learning on Large Graphs

Introducing VF3: A New Algorithm for Subgraph Isomorphism

Learning Combinatorial Optimization Algorithms over Graphs

Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks

Effective Community Search over Large Spatial Graphs

Mining Graphlet Counts in Online Social Networks

Fusion and community detection in multi-layer graphs

Neural Combinatorial Optimization with Reinforcement Learning

Optimization as a Model for Few-Shot Learning

Semi-Supervised Classification with Graph Convolutional Networks

Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems

Attribute-Driven Community Search

Effective Community Search for Large Attributed Graphs

Parameter-Free Auto-Weighted Multiple Graph Learning: A Framework for Multiview Clustering and Semi-Supervised Classification