.png){kind=icon}
.png){kind=icon}
Return
Memory Efficient Very-Large Colored Subgraph Detection
.png){kind=icon}
PRE
AI
S
D
Y
DOI：10.1109/TKDE.2026.3705310.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Algorithms for the exact detection of a subgraph <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> within a larger graph <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> are currently limited to a small number of vertices in <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula>. In colored graphs, the problem is simpler, given the constraint induced by the color match. We here propose VELCRO: (Very Efficient Large Colored subgRaph detectiOn) to detect very large colored subgraphs. VELCRO is based on efficient memory management to avoid multiplying the constraint memory cost for each vertex combination tested, smart traversal of vertices in <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula>, and a constraint on the degree of the next vertex. In short, VELCRO orders the vertices in <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> and opens a Depth First Search (DFS) in <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> to search pathways consistent with <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula>. At each stage, VELCRO efficiently tests the constraints on unmatched vertices in <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula>. The vertex order is optimized to prevent an exponential growth in the number of candidate trajectories by maximizing future constraints. VELCRO stops a path when any vertex in <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> is constrained to have no possible match in <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula>. We show the efficacy of VELCRO on simulated dense <inline-formula><tex-math notation="LaTeX">$G(n,p)$</tex-math></inline-formula>, real-world colored graphs, and real-world graphs with random coloring. VELCRO was tested on <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> of up to <inline-formula><tex-math notation="LaTeX">$5\times 10^{5}$</tex-math></inline-formula> vertices and on <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> up to millions of vertices and solves the queries within seconds to minutes. No current exact subgraph matching algorithm can search such large colored subgraphs.
Keywords:
Subgraph isomorphism
VELCRO
efficient memory management
backtracking
colored graphs
constrained programming
Journal
IF:
10.4
Papers:
6.7K
Citations:
3.2W
Organization
Cited Papers