Intuitive Overview
Before diving into formal definitions, let’s build intuition with a simple conceptual overview.
The Core Idea
Imagine you have a dataset with many predictors, some of which are highly correlated. For example:
- Temperature at noon and temperature at 2pm (likely correlated ~0.9)
- Monthly income and annual income (perfectly correlated)
- Survey items “I am satisfied” and “I feel happy” (correlated ~0.7)
When building statistical models, including highly correlated predictors creates problems:
- Coefficient instability: Small data changes cause large coefficient swings
- Inflated variance: Standard errors become unreliable
- Interpretability issues: Hard to isolate individual predictor effects
The solution: remove redundant predictors while keeping as many variables as possible.
How corrselect Works
corrselect transforms this statistical problem into a graph problem:
- Represent variables as nodes in a graph
- Draw edges between compatible variables (correlation below threshold τ)
- Find maximal groups where all nodes are connected (maximal cliques)
Each maximal clique represents a valid subset: a group of variables where every pair has correlation below τ.
Why “Maximal” Not “Maximum”?
A maximal subset cannot be extended by adding more variables—it’s locally complete.
A maximum subset is the single largest possible subset—globally optimal.
corrselect finds all maximal subsets because:
- Real datasets often have multiple equally good solutions
- You may prefer a smaller subset containing specific variables
- Comparing alternatives reveals correlation structure
- Exact enumeration is feasible for typical problem sizes
Toy Example (4 Variables)
Consider 4 variables with this correlation matrix:
# Construct a simple 4x4 correlation matrix
cor_4var <- matrix(c(
1.00, 0.85, 0.10, 0.15,
0.85, 1.00, 0.12, 0.18,
0.10, 0.12, 1.00, 0.75,
0.15, 0.18, 0.75, 1.00
), nrow = 4, byrow = TRUE)
colnames(cor_4var) <- rownames(cor_4var) <- paste0("V", 1:4)
# Display matrix
print(cor_4var)
#> V1 V2 V3 V4
#> V1 1.00 0.85 0.10 0.15
#> V2 0.85 1.00 0.12 0.18
#> V3 0.10 0.12 1.00 0.75
#> V4 0.15 0.18 0.75 1.00Observations:
- V1 and V2 are highly correlated (0.85) - likely redundant
- V3 and V4 are moderately correlated (0.75)
- Between-group correlations are low (0.10-0.18)
Set threshold τ = 0.7. Which pairs violate the threshold?
- V1-V2: |0.85| ≥ 0.7 ✗ (too high)
- V3-V4: |0.75| ≥ 0.7 ✗ (too high)
- All other pairs: < 0.7 ✓ (acceptable)
Graph Representation
Now we build the threshold graph where edges connect compatible variables (correlation < 0.7).
Text representation:
Variables: V1, V2, V3, V4
Edges (|correlation| < 0.7):
V1 —— V3 (cor = 0.10)
V1 —— V4 (cor = 0.15)
V2 —— V3 (cor = 0.12)
V2 —— V4 (cor = 0.18)
Missing edges (|correlation| ≥ 0.7):
V1 ⨯ V2 (cor = 0.85, too high)
V3 ⨯ V4 (cor = 0.75, too high)
Maximal cliques (maximal variable subsets):
{V1, V3}: Both connected, cannot add V2 or V4
{V1, V4}: Both connected, cannot add V2 or V3
{V2, V3}: Both connected, cannot add V1 or V4
{V2, V4}: Both connected, cannot add V1 or V3Let’s verify this with code:
# Adjacency matrix for threshold graph (edges where |cor| < 0.7)
adj_matrix <- abs(cor_4var) < 0.7
diag(adj_matrix) <- FALSE # No self-loops
# Visualize as adjacency matrix
cat("Threshold graph edges (1 = edge exists):\n")
#> Threshold graph edges (1 = edge exists):
print(adj_matrix * 1)
#> V1 V2 V3 V4
#> V1 0 0 1 1
#> V2 0 0 1 1
#> V3 1 1 0 0
#> V4 1 1 0 0Interpretation: An edge exists between Vi and Vj if they can coexist in a valid subset.
- V1 connects to: V3, V4 (not V2)
- V2 connects to: V3, V4 (not V1)
- V3 connects to: V1, V2 (not V4)
- V4 connects to: V1, V2 (not V3)
Visual Graph Representation
Let’s visualize this threshold graph with nodes and edges:
# Node positions (arranged in a square for clarity)
node_pos <- matrix(c(
0, 1, # V1 (top-left)
2, 1, # V2 (top-right)
0, 0, # V3 (bottom-left)
2, 0 # V4 (bottom-right)
), ncol = 2, byrow = TRUE)
# Plot setup
par(mar = c(2, 2, 3, 2))
plot(node_pos, type = "n", xlim = c(-0.5, 2.5), ylim = c(-0.5, 1.5),
xlab = "", ylab = "", axes = FALSE,
main = "Threshold Graph (τ = 0.7)\nEdges connect variables with |correlation| < 0.7")
# Draw edges (where correlation < 0.7)
edge_color <- rgb(0.2, 0.5, 0.8, 0.6)
edge_lwd <- 2
for (i in 1:4) {
for (j in 1:4) {
if (i < j && adj_matrix[i, j]) {
segments(node_pos[i, 1], node_pos[i, 2],
node_pos[j, 1], node_pos[j, 2],
col = edge_color, lwd = edge_lwd)
}
}
}
# Draw nodes
node_size <- 0.15
for (i in 1:4) {
# Node circle
symbols(node_pos[i, 1], node_pos[i, 2],
circles = node_size, add = TRUE,
inches = FALSE, bg = "white", fg = "black", lwd = 2)
# Node label
text(node_pos[i, 1], node_pos[i, 2],
labels = paste0("V", i), cex = 1.2, font = 2)
}
# Add correlation annotations
text(1, 1.35, "cor = 0.85\n(too high, no edge)", cex = 0.8, col = "red")
text(1, -0.35, "cor = 0.75\n(too high, no edge)", cex = 0.8, col = "red")
# Legend showing maximal cliques
legend("right",
legend = c("Maximal cliques:", "{V1, V3}", "{V1, V4}", "{V2, V3}", "{V2, V4}"),
bty = "o", bg = "white", cex = 0.9,
pch = c(NA, 19, 19, 19, 19),
col = c(NA, "black", "black", "black", "black"))
# Add box around graph
box()
Graph interpretation:
- Nodes: Each variable is a vertex
- Edges (blue lines): Connect variables with correlation < 0.7 (compatible pairs)
- Missing edges (no connection): Variables with
correlation ≥ 0.7 (cannot coexist)
- V1-V2: No edge (corr = 0.85)
- V3-V4: No edge (corr = 0.75)
Maximal cliques (groups where everyone connects to everyone):
- {V1, V3}: V1—V3 edge exists ✓, cannot add V2 (no V1—V2 edge) or V4 (no V3—V4 edge)
- {V1, V4}: V1—V4 edge exists ✓, cannot add V2 (no V1—V2 edge) or V3 (no V3—V4 edge)
- {V2, V3}: V2—V3 edge exists ✓, cannot add V1 (no V1—V2 edge) or V4 (no V3—V4 edge)
- {V2, V4}: V2—V4 edge exists ✓, cannot add V1 (no V1—V2 edge) or V3 (no V3—V4 edge)
This visual representation makes the graph-theoretic formulation concrete: finding maximal valid variable subsets is equivalent to finding maximal cliques in the threshold graph.
Network Visualization with cor_example
For larger matrices, we can use igraph to visualize the threshold
graph structure. Let’s demonstrate with cor_example, which
has 20 variables with known block structure:
data(cor_example)
# Build threshold graph (edges where |correlation| < 0.7)
threshold <- 0.7
adj_mat <- abs(cor_example) < threshold
diag(adj_mat) <- FALSE
if (requireNamespace("igraph", quietly = TRUE)) {
library(igraph)
# Create graph from adjacency matrix
g <- graph_from_adjacency_matrix(adj_mat, mode = "undirected")
# Find maximal cliques
cliques <- max_cliques(g)
cat(sprintf("Found %d maximal cliques at threshold %.1f\n", length(cliques), threshold))
# Color nodes by which block they belong to
block_colors <- c(rep("#d73027", 5), # Block 1 (V1-V5): high correlation
rep("#fc8d59", 5), # Block 2 (V6-V10): moderate
rep("#91bfdb", 5), # Block 3 (V11-V15): low
rep("#4575b4", 5)) # Block 4 (V16-V20): minimal
# Plot network
par(mar = c(1, 1, 3, 1))
plot(g,
vertex.size = 10,
vertex.color = block_colors,
vertex.label.cex = 0.8,
vertex.label.color = "black",
edge.color = rgb(0.5, 0.5, 0.5, 0.3),
edge.width = 1,
layout = layout_with_fr(g),
main = sprintf("Threshold Graph (τ = %.1f): Variables with |cor| < %.1f are connected",
threshold, threshold))
# Add legend
legend("topleft",
legend = c("Block 1 (V1-V5): High cor",
"Block 2 (V6-V10): Moderate cor",
"Block 3 (V11-V15): Low cor",
"Block 4 (V16-V20): Minimal cor"),
fill = c("#d73027", "#fc8d59", "#91bfdb", "#4575b4"),
bty = "o", bg = "white", cex = 0.8)
} else {
cat("Install igraph for network visualization: install.packages('igraph')\n")
cat("Adjacency matrix (first 5×5 block):\n")
print(adj_mat[1:5, 1:5] * 1)
}
#>
#> Attaching package: 'igraph'
#> The following objects are masked from 'package:stats':
#>
#> decompose, spectrum
#> The following object is masked from 'package:base':
#>
#> union
#> Found 5 maximal cliques at threshold 0.7
Interpretation:
- Variables within high-correlation blocks (red, orange) have few or no edges because their pairwise correlations exceed 0.7
- Variables within low-correlation blocks (light blue, dark blue) have many edges because their correlations are below 0.7
- Maximal cliques tend to include variables from multiple low-correlation blocks
- This explains why corrselect tends to select variables from Block 3 and Block 4: they have more compatible neighbors
Finding Maximal Cliques
A clique is a group where every pair is connected. In our graph:
Potential cliques:
- {V1, V3}: Both connect to each other ✓
- {V1, V4}: Both connect to each other ✓
- {V2, V3}: Both connect to each other ✓
- {V2, V4}: Both connect to each other ✓
- {V1, V3, V4}: Does V3 connect to V4? No ✗
- {V2, V3, V4}: Does V3 connect to V4? No ✗
Maximal cliques: Can any 2-variable clique be extended?
{V1, V3}
Add V2? No (V1–V2 not connected).
Add V4? No (V3–V4 not connected).
Maximal ✓{V1, V4}
Add V2? No (V1–V2 not connected).
Add V3? No (V3–V4 not connected).
Maximal ✓{V2, V3}
Add V1? No (V1–V2 not connected).
Add V4? No (V3–V4 not connected).
Maximal ✓{V2, V4}
Add V1? No (V1–V2 not connected).
Add V3? No (V3–V4 not connected).
Maximal ✓
So there are 4 maximal cliques of size 2, each representing a valid variable subset.
Let corrselect confirm this:
results <- MatSelect(cor_4var, threshold = 0.7, method = "bron-kerbosch")
show(results)
#> CorrCombo object
#> -----------------
#> Method: bron-kerbosch
#> Threshold: 0.700
#> Subsets: 4 maximal subsets
#> Data Rows: 4 used in correlation
#> Pivot: TRUE
#>
#> Top combinations:
#> No. Variables Avg Max Size
#> ------------------------------------------------------------
#> [ 1] V1, V3 0.100 0.100 2
#> [ 2] V2, V3 0.120 0.120 2
#> [ 3] V1, V4 0.150 0.150 2
#> [ 4] V2, V4 0.180 0.180 2Result interpretation:
- 4 maximal subsets found (as predicted)
- All have size 2 (cannot be extended further)
- Each satisfies |correlation| < 0.7 for all pairs
- Mean/max correlations are low (well below threshold)
Key Insight
This toy example shows why corrselect enumerates all solutions:
- There’s no single “best” subset—all 4 are equally valid
- Choice depends on domain knowledge (which variables are theoretically important?)
- Seeing all options reveals the correlation structure (two clusters: {V1,V2} and {V3,V4})
Real datasets have similar structure but with more variables and more complex clustering.
Key Points — Intuitive Overview
- corrselect finds variable subsets where no pair exceeds a correlation threshold
- Multiple valid subsets typically exist; all are enumerated for user choice
- Graph representation: variables = nodes, low-correlation pairs = edges
- Maximal cliques in this graph = maximal valid subsets
- Comparing subsets reveals correlation structure (clusters of related variables)
