VC-dimension and Rademacher Averages of Subgraphs, with Applications to Graph Mining.
Paolo PellizzoniFabio VandinPublished in: ICDE (2023)
Keyphrases
- graph mining
- vc dimension
- covering numbers
- risk bounds
- generalization bounds
- function classes
- upper bound
- graph databases
- pattern mining
- statistical learning theory
- sample complexity
- sample size
- frequent subgraphs
- inductive inference
- empirical risk minimization
- lower bound
- graph data
- frequent subgraph mining
- concept classes
- connected components
- subgraph mining
- uniform convergence
- pattern discovery
- community detection
- compression scheme
- link prediction
- euclidean space
- worst case
- generalization error
- data dependent
- link analysis
- gaussian kernels
- theoretical analysis
- special case