1 Induced subgraphs and induced embeddings
1.1 Definitions of induced subgraphs
An induced subgraph is formed by selecting a subset of vertices from a host graph and keeping all edges between the chosen vertices that exist in the host. No additional edges are added, and no existing edges among the selected vertices are removed. This “keep exactly what the host has” rule makes induced subgraphs sensitive to both adjacency and non-adjacency among the selected vertices.
1.2 Counting induced occurrences vs non-induced subgraphs
Counting general (not necessarily induced) subgraph occurrences typically allows the mapped vertices to realize the pattern edges while permitting additional edges among mapped vertices that are not part of the pattern. Induced counting is stricter: when a pattern is placed on a vertex subset, every adjacency relation in the pattern must correspond to an edge in the host, and every non-adjacency relation in the pattern must correspond to a missing edge in the host. As a result, induced frequency distinguishes between structures that would look similar under non-induced counting but differ in how extra edges appear.
1.3 Induced frequency as a normalized statistic
Raw induced counts depend strongly on the number of available vertex subsets, and thus on the host graph size. Induced frequency therefore is often normalized to yield quantities that are easier to compare across graphs of different orders or across patterns of different sizes. Common normalizations include dividing by the number of k-vertex subsets, using counts per subset, or scaling by factors that account for label conventions and automorphisms.
2 Formal definitions of induced subgraph frequency
2.1 Vertex subsets and induced subgraph extraction
2.1.1 Choosing k-vertex subsets from a host graph
| Let \(G=(V,E)\) be a graph and let \(k\) be a positive integer. One considers all vertex subsets \(S\subseteq V\) with \( | S | =k\). Each subset determines an induced subgraph \(G[S]\), defined on vertex set \(S\) with edge set |
|---|
\[ E(G[S])=\{ \{u,v\}\in E : u,v\in S\}. \] The induced frequency of a pattern graph \(H\) on \(k\) vertices is about how many such subsets yield an induced subgraph isomorphic to \(H\).
2.1.2 Induced match criteria with adjacency and non-adjacency
Let \(H\) be a pattern graph with vertex set \(\{1,\dots,k\}\). An induced embedding (often phrased as an induced isomorphism once vertices are identified) corresponds to a bijection \(\phi:V(H)\to S\) such that for every pair of vertices \(i,j\),
- \(\{i,j\}\in E(H)\) if and only if \(\{\phi(i),\phi(j)\}\in E(G)\).
Equivalently, adjacency and non-adjacency are both matched: pairs adjacent in \(H\) must be adjacent in \(G[S]\), and pairs non-adjacent in \(H\) must be non-adjacent in \(G[S]\).
2.2 Frequency formulas and normalization options
2.2.1 Raw counts
Assume \(H\) has \(k\) vertices. The induced subgraph frequency count is typically defined as \[
| N^{\mathrm{ind}}(H;G)= | \{S\subseteq V(G): | S | =k,\; G[S]\cong H\} | . |
|---|
\] This counts k-vertex subsets whose induced subgraph is isomorphic to \(H\). Depending on convention, one may instead count embeddings (injective vertex maps) rather than subsets; these are related by a factor involving automorphisms of \(H\).
2.2.2 Normalized frequencies (e.g., per k-vertex subset)
A basic normalization divides by the total number of k-vertex subsets: \[
| f^{\mathrm{ind}}(H;G)=\frac{N^{\mathrm{ind}}(H;G)}{\binom{ | V(G) | }{k}}. |
|---|
\] Other normalizations include dividing by the number of embeddings implied by automorphisms or using z-scores across a dataset to support comparative analysis. Choice of normalization affects interpretability: per-subset frequency is often easiest to understand as a probability that a uniformly chosen k-vertex subset induces \(H\).
2.3 Labeled vs unlabeled frequency conventions
2.3.1 Automorphisms and overcounting considerations
If frequency is defined in terms of embeddings \(\phi\) (injective maps) rather than vertex subsets, multiple embeddings can correspond to the same induced subgraph instance due to symmetries in \(H\). The number of embeddings associated with an induced copy relates to the size of the automorphism group of \(H\), denoted \(\mathrm{Aut}(H)\). Conventions that count labeled occurrences (specific vertex bijections from \(H\) to a chosen subset) must account for this to avoid inconsistency with subset-based definitions.
A common reconciliation is:
- subset-based frequency counts each induced copy once (up to vertex choice),
- embedding-based frequency counts each copy multiple times according to labelings that preserve \(H\).
3 Types of patterns and example subgraphs
3.1 Common small induced patterns
Induced frequency is often used with small \(k\) (e.g., \(k=3,4,5\)) because enumerating larger induced structures can be expensive. For \(k=3\), a host of patterns exists, such as the induced path on three vertices, the induced triangle, and the independent set of size three. For \(k=4\), patterns include various induced trees, cycles, and configurations with one missing or extra edge relative to others.
3.2 Motifs and their induced frequency interpretation
In network science, “motifs” refer to small subgraphs that recur frequently and are treated as building blocks of network structure. When motifs are counted as induced subgraphs, induced frequency measures how often a motif appears as an exact local template, not merely as an arrangement of edges that can be extended with additional connections. This sharpened meaning can change which motifs are deemed characteristic: a configuration that is frequent under non-induced counting might not be frequent under induced counting if extra edges commonly appear.
3.3 Complement-related patterns (using graph complements)
For an undirected simple graph \(H\), its complement \(\overline{H}\) swaps edges and non-edges (excluding loops). Induced occurrences in a host graph \(G\) can be related to induced occurrences of complements in the complement graph \(\overline{G}\). This relation provides a way to reuse computation or to interpret patterns: an induced “edge-rich” pattern in \(G\) corresponds to an induced “edge-poor” pattern in \(\overline{G}\), and induced frequencies correspond under this transformation.
4 Computational aspects
4.1 Naive enumeration complexity
| A direct implementation can enumerate all k-vertex subsets of \(G\) and test whether the induced subgraph matches \(H\). The number of subsets is \(\binom{n}{k}\) for \(n= | V(G) | \), so the worst-case growth is combinatorial in \(k\). Additionally, checking isomorphism for each subset can be nontrivial, making naive enumeration feasible only for small graphs, very small \(k\), or restricted families of patterns. |
|---|
4.2 Exact counting via subgraph isomorphism techniques
Exact induced subgraph counting can be formulated as an instance of induced subgraph isomorphism. Many approaches use backtracking search with pruning:
- build partial mappings from pattern vertices to host vertices,
- enforce adjacency/non-adjacency constraints as soon as enough vertices are mapped,
- prune mappings that cannot be extended.
When counting labeled embeddings, constraint propagation can be strengthened using degree constraints, neighborhood intersections, and color refinement (in variants akin to canonical labeling). For certain pattern families, specialized algorithms exist that leverage structure to reduce search.
4.3 Sampling and approximate induced frequency estimation
For large graphs or larger \(k\), exact counting may be infeasible. Approximation often proceeds by sampling k-vertex subsets uniformly (or via importance sampling) and testing induced isomorphism to \(H\). The induced frequency is then estimated as the fraction of sampled subsets that match. Variance depends on how rare the pattern is, motivating:
- larger sample budgets for rare patterns,
- stratified sampling by degree or other vertex properties,
- multiple patterns counted simultaneously to amortize computation.
4.4 Hashing/canonical labeling for faster pattern matching
To accelerate the “does \(G[S]\cong H\)?” step, one can compute a canonical form for each induced subgraph \(G[S]\). If canonical labels (or hashes) are invariant under isomorphism, then isomorphic induced subgraphs share the same canonical representation, enabling fast equality checks. In practice, canonical labeling can be computed on demand for sampled subsets or for all subsets when \(k\) is small enough. Care must be taken to ensure that hashing is collision-resistant or that collisions are handled deterministically via a fallback isomorphism test.
5 Statistical properties and comparisons
5.1 Dependence on graph size and density
Induced frequency is influenced by the number of vertices and by how edges are distributed. Even with the same pattern size \(k\), different host graph densities can substantially alter the likelihood that a random k-vertex subset matches a specific induced template. For example, patterns requiring many edges (like an induced clique) become rarer in sparse graphs, while patterns requiring many non-edges become rarer in dense graphs.
5.2 Expected frequencies under random graph models
5.2.1 Basic model comparisons (e.g., Erdős–Rényi intuition)
Under an Erdős–Rényi model \(G(n,p)\), induced subgraphs on k vertices resemble random graphs conditioned on k and p. For a fixed pattern \(H\) with \(m\) edges, the probability that a particular k-vertex subset induces \(H\) is tied to \(p^m(1-p)^{\binom{k}{2}-m}\), up to automorphism factors depending on whether one considers subsets or labeled embeddings. This gives a baseline expectation that helps detect when a pattern is over- or under-represented in empirical data relative to randomness.
5.2.2 Degree-based effects on induced patterns
Real networks often exhibit degree heterogeneity. Even in ensembles that capture degree sequences, induced pattern frequencies shift because k-vertex subsets are not equally likely to contain particular degree combinations. As a result, induced frequencies can reveal local structural biases not captured by simple edge probability alone.
5.3 Comparing frequency vectors across graphs
5.3.1 Distance and similarity measures for feature vectors
A common workflow represents each graph by a vector of induced frequencies over a selected family of patterns \(\{H_1,\dots,H_r\}\). Similarity between graphs can then be measured using metrics such as:
- Euclidean distance (sensitive to absolute differences),
- cosine similarity (emphasizes direction, useful when totals scale),
- divergence measures (when frequencies are treated as probability-like distributions).
The choice depends on whether the frequencies are normalized to sum to 1, whether patterns are correlated, and how robust the method should be to sampling noise.
6 Applications in graph analytics
6.1 Feature engineering for graph classification
Induced subgraph frequency vectors can serve as descriptors for machine learning tasks. Because induced counting is sensitive to missing edges as well as present edges, the features often capture finer local structure than edge-only motif counts. When patterns up to moderate \(k\) are included, the resulting features can differentiate graphs with similar global sizes but different local connectivity arrangements.
6.2 Network characterization and descriptive statistics
In exploratory analysis, induced frequencies summarize local structure in a way that is interpretable. For instance, a comparison of induced triangle frequency versus induced path frequency can indicate whether local clustering or tree-like neighborhoods dominate. Such statistics can be tracked across datasets, time points, or experimental conditions to describe structural trends.
6.3 Detecting structural anomalies or changes
When a graph is expected to conform to a baseline structure (e.g., graphs from the same system under normal operation), deviations in induced motif frequencies can signal anomalies. Because induced frequencies respond to both edges and non-edges, they can detect changes that alter connection patterns rather than merely adding or removing some edges.
7 Induced subgraph frequency in special graph settings
7.1 Undirected vs directed induced frequencies
For directed graphs, induced subgraph matching must account for edge directions. A pair of vertices can fall into multiple relation types: no arc, arc from u to v, or arc from v to u. Induced frequency definitions extend by requiring equality of these relation types for every ordered pair involved in the pattern. The number of possible relation configurations grows, which can increase computational complexity.
7.2 Weighted/attributed graphs and adaptations
In attributed graphs, vertices and/or edges may carry labels or weights. Induced frequency can be adapted in several ways:
- treat attributes as part of the pattern matching (exact label agreement),
- allow coarse-graining (e.g., bucket weights into categories),
- use probabilistic or threshold-based definitions (e.g., “edge exists” if weight exceeds a cutoff).
Such adaptations change what “induced” means: the induced subgraph is still formed by vertex selection, but the matching criterion incorporates attribute compatibility.
7.3 Dynamic graphs and time-indexed frequencies
For temporal networks, one may compute induced frequencies over sliding windows of time or at discrete timestamps. This yields time series of motif frequencies that reflect evolving local structure. Proper handling includes choosing window length, addressing missing data, and ensuring that normalization is consistent across time points when the number of available vertices changes.
8 Practical pitfalls and best practices
8.1 Handling disconnected induced patterns
Some patterns are disconnected, meaning the induced template contains multiple components. Counting disconnected patterns is valid but can interact with sampling and normalization: a pattern’s frequency may increase simply because there are many subsets that produce disconnected induced graphs when the host is sparse. Interpreting such frequencies may require attention to baseline expectations from random models or degree-aware baselines.
8.2 Sensitivity to relabeling and graph isomorphism
Induced frequency should be invariant under relabeling of vertices. Implementations must therefore rely on isomorphism-invariant checks (canonical labeling or robust induced isomorphism tests). If naive hashing is used, collisions or weak invariants can break this property. Validation with known isomorphic graphs and with patterns having nontrivial automorphism groups helps ensure correctness.
8.3 Interpreting frequencies with small-sample issues
For rare patterns, estimates obtained from sampling can have high variance and sometimes zero counts in a finite sample. Analysts should consider confidence intervals, increase sample sizes, or aggregate patterns to reduce sparsity. When exact counting is feasible, it eliminates sampling variance but may still face computational constraints.
9 Relation to related statistics
9.1 Subgraph frequency vs induced subgraph frequency
Subgraph frequency counts occurrences where the pattern edges exist in the host but extra edges are allowed. Induced subgraph frequency requires that the induced structure matches exactly, forbidding extra edges and requiring forbidden edges to be absent. Consequently, induced frequencies can be interpreted as stricter “local structure match” probabilities, while non-induced frequencies are closer to “pattern embeddability” measures.
9.2 Homomorphism density vs induced density
Homomorphism density typically counts graph homomorphisms from the pattern into the host, allowing edges in the pattern to map to edges in the host but without enforcing non-adjacency constraints for non-edges in the pattern. Induced density is more restrictive and corresponds to matching adjacency and non-adjacency. This makes induced measures more discriminative but also generally more difficult to compute.
9.3 Graphon and limit perspectives (high-level connection)
In graph limit theory, densities of small subgraphs can be extended to limiting objects (graphons). Induced subgraph densities correspond to limits that capture both edge and non-edge behavior in a consistent way. While induced density computations in finite graphs are discrete, their limiting interpretations motivate how induced frequencies behave as graphs grow and how one can compare sequences of graphs via convergent structural profiles.
10 Illustrative worked examples
10.1 Computing induced frequency for a toy graph
Consider a host graph \(G\) with a small number of vertices, and choose \(k\). The first step is to list all k-vertex subsets \(S\). For each subset, form \(G[S]\) by including every edge between vertices in \(S\) that exists in \(G\). Next, compare each induced subgraph \(G[S]\) to the pattern \(H\) using induced isomorphism. The induced frequency is the fraction of subsets where the match holds (or the raw count, depending on convention).
10.2 Frequency of a specific k-vertex induced pattern
| Suppose the pattern \(H\) is an induced triangle on three vertices, and \(k=3\). For each 3-vertex subset \(S\), \(G[S]\) is a triangle if and only if every pair of vertices in \(S\) is connected in \(G\). In that case, the subset contributes 1 to \(N^{\mathrm{ind}}(H;G)\); otherwise it contributes 0. Dividing by \(\binom{ | V(G) | }{3}\) yields the normalized induced triangle frequency. |
|---|
10.3 Validating implementations with symmetry/automorphism checks
Correct induced counting should remain unchanged under vertex relabeling of \(G\). It also must properly handle patterns with symmetries. A practical validation method is:
- generate an isomorphic copy of \(G\) with permuted vertex labels and confirm identical induced frequencies,
- test patterns with known automorphism structures and verify that embedding-count-based formulas agree with subset-based counts after accounting for automorphisms.