Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning

DOI10.1613/jair.1.13976zbMath1502.68257arXiv2201.01825OpenAlexW4306652901MaRDI QIDQ5870483

Itay Levinas, Yoram Louzoun

Publication date: 9 January 2023

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2201.01825

zbMATH Keywords

cliquemachine learningplanted cliquegraph convolutional network

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Graph theory (including graph drawing) in computer science (68R10)

Uses Software

• GitHub

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nuclear norm minimization for the planted clique and biclique problems
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Expected complexity of graph partitioning problems
• Hiding cliques for cryptographic security
• Public-key cryptography from different assumptions
• Hidden Cliques and the Certification of the Restricted Isometry Property
• How Hard Is It to Approximate the Best Nash Equilibrium?
• Parallel tempering for the planted clique problem
• Edge sign prediction based on a combination of network structural topology and sign propagation
• Large Cliques Elude the Metropolis Process
• On the Shannon capacity of a graph
• A Statistical Model for Motifs Detection
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
• Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time
• Finding and certifying a large hidden clique in a semirandom graph
• Reducibility among Combinatorial Problems
• Finding Hidden Cliques in Linear Time with High Probability