graphlet

graphlet is a Rust library for graphlet and network-motif mining on top of petgraph: it counts and enumerates small connected subgraphs, attributes nodes to their graphlet orbits, finds and tests the significance of named motifs, matches arbitrary template patterns, generates null-model random graphs, and computes a few structural graph statistics (clustering, assortativity, link prediction, graph kernels). It is for anyone doing structural/network-science analysis on a petgraph graph who needs motif-level detail that the rest of the Rust graph ecosystem does not provide. It depends only on petgraph and rand, and works directly on Graph, StableGraph, and DiGraph, directed or undirected, with any node/edge weights.

At a glance

use graphlet::catalog::{find_diamonds, Induced};
use graphlet::{count, graphlet_degree_vectors, Registry, Selector};
use petgraph::graph::UnGraph;

// A diamond (K4 minus one edge: two triangles sharing the 0-2 spine) with a
// pendant vertex 4 hanging off node 3.
let g: UnGraph<(), ()> =
    UnGraph::from_edges([(0, 1), (1, 2), (2, 3), (3, 0), (0, 2), (3, 4)]);

// Class census of connected 3-node induced subgraphs (triangles and paths).
let census = count(&g, &Selector::connected_k_subsets(3));
assert_eq!(census.values().sum::<u64>(), 6);

// Per-node graphlet degree vectors across all 73 orbits (k <= 5).
// The registry is built once and reused across calls.
let reg = Registry::build();
let gdv = graphlet_degree_vectors(&g, &reg);
assert_eq!(gdv.orbit_count(), 73);

// Named-motif query: this graph contains exactly one induced diamond.
assert_eq!(find_diamonds(&g, Induced::Yes).len(), 1);

What it does

Subgraph census

The organizing center of the crate is a single pipeline: enumerate every connected induced subgraph up to 5 nodes, label it by canonical isomorphism class, and fold. enumerate yields each match lazily as an Instance (the host node ids plus its class); count folds the same traversal into a Census (class to count) whose memory tracks graph size, not the number of matches. Both are generic over Graph, StableGraph, and DiGraph; the underlying structure is always treated as simple and undirected (self-loops stripped, parallel edges deduped, directed edges unioned).

Graphlet degree vectors (GDV/GDD)

graphlet_degree_vectors attributes every node of every matched subgraph to its automorphism orbit within that subgraph, producing the 73-entry graphlet-degree vector per node, for graphlets of order 2 through 5. A Registry computes the orbit structure once and is reused across calls.

The exact path canonicalizes every subgraph instance, which gets expensive at k=5. rim::scalable::fast_graphlet_degree_vectors recovers the same 73-orbit result an ORCA-style way, without ever canonically labelling a connected 5-node subset: it counts degrees, per-edge triangles, and per-vertex K4 memberships directly for orders 2 through 4, and decomposes order-5 orbits through connected 4-node cores plus attachment tallies. It is verified exact, node-for-node and count-for-count, against the exact census path across a battery of standard graphs (paths, cycles, stars, complete graphs, wheels, trees, complete bipartite graphs, the Petersen graph, the cube graph Q3) plus fuzzed random graphs. Because the exact path pays a k! canonicalization per 5-subset while the fast path never labels one, the gap widens with graph size and density rather than sitting at a fixed multiplier: on seeded G(n, p) random graphs it grows from roughly 10x at n=40 to over 100x by n=150, and past there the exact path leaves the seconds regime entirely while the fast path stays in the millisecond-to-few-second range (at n=200, p=0.1 and n=100+, p=0.3 the exact census is already impractical to time, yet the fast path finishes in a few seconds). The shipped examples/scalable_bench.rs reproduces the whole sweep; run it with cargo run --release -p graphlet --example scalable_bench.

Named motifs

catalog provides named Pattern constructors for the standard small motifs, path (P_k), cycle (C_k), star, complete graph (K_k), triangle, claw, paw, diamond, plus a MotifCatalog to register and look up arbitrary patterns by name. count_pattern / count_motif count any connected pattern of order up to 5 against a host graph, in both induced and non-induced semantics; find_motif returns the actual node-set occurrences (find_diamonds is a thin wrapper over find_motif for the diamond pattern).

Template matching

template matches an arbitrary petgraph query graph against a host graph, in two distinct semantics, unbounded in pattern size and honoring node/edge predicates and directedness:

• Induced (induced_matches): delegates to petgraph's own VF2 (subgraph_isomorphisms_iter).
• Non-induced / monomorphism (monomorphisms): this crate's own ordered-backtracking, edge-preserving enumerator (petgraph has no monomorphism search).

Both return raw embeddings (every automorphism of the pattern counted separately); divide by |Aut(pattern)| for distinct occurrences.

Null-model generators (rim::null_model)

Random-graph generators for significance testing, each seeded via &mut impl Rng: the configuration model (raw and simple/loop-free variants), degree-preserving double-edge-swap rewiring, Watts-Strogatz small-world graphs, and an LFR benchmark graph with planted community structure. LFR is a documented partial: it approximates the target degree and mixing parameters rather than enforcing them exactly, and has other known deviations from the reference algorithm (see its doc comment).

Significance testing (rim::significance)

motif_significance and census_significance_profile compare an observed motif count, or the full graphlet census, against an ensemble of null graphs, reporting a z-score and an empirical p-value per target. The significance profile's normalized (unit-length) vector is None whenever any z-score in the profile is non-finite (which happens when a null model's count has zero variance but disagrees with the observed count) rather than silently leaking a NaN.

Neighborhood statistics (rim::neighborhood)

Link-prediction indices (common neighbors, Jaccard, Adamic-Adar, resource allocation, preferential attachment), local/average/global clustering coefficients with triangle counting, degree assortativity (Newman/Pearson), and the rich-club coefficient.

Graph kernels (rim::kernels)

A graphlet kernel (built directly from the census substrate's own class-count vectors), a Weisfeiler-Lehman subtree kernel, a shortest-path kernel, and a generic Gram-matrix builder (raw or cosine-normalized) usable with any of the three feature representations, or your own.

Directed graphlets (rim::directed)

A directed generalization of the census/orbit substrate, respecting arc direction throughout (two directed graphlets that fold to the same undirected class, such as a -> b -> c and a -> b <- c, are distinct directed classes): directed graphlet census, per-node directed orbits, for weakly-connected subgraphs of order 2 through 5, plus the standard 16-type Holland-Leinhardt directed triad census (order 3, every 3-subset, connected or not). k=5 is exact but slow: canonicalizing a directed 5-node instance costs 5! permutations of a 20-bit mask, and building the order-5 registry sweeps all 2^20 labelled digraphs once.

Examples

Census and graphlet degree vectors

use graphlet::{count, graphlet_degree_vectors, Registry, Selector};
use petgraph::graph::UnGraph;

// A 5-cycle.
let g: UnGraph<(), ()> = UnGraph::from_edges([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]);

let census = count(&g, &Selector::connected_k_subsets(3));
// Every 3-subset of a 5-cycle is a path, never a triangle.
assert_eq!(census.len(), 1);

let reg = Registry::build();
let gdv = graphlet_degree_vectors(&g, &reg);
// Every node of a symmetric cycle sits in the same orbit for every orbit id.
let row0 = gdv.row(0).to_vec();
for v in 1..5 {
    assert_eq!(gdv.row(v), row0.as_slice());
}

Motif significance against a null model

use graphlet::catalog::{Induced, Pattern};
use graphlet::rim::significance::{motif_significance, NullModel};
use petgraph::graph::UnGraph;
use rand::SeedableRng;
use rand::rngs::StdRng;

// Five disjoint triangles: over-represented relative to a degree-preserving
// null (which breaks triangles up into larger cycles).
let g: UnGraph<(), ()> = UnGraph::from_edges([
    (0u32, 1), (1, 2), (2, 0),
    (3, 4), (4, 5), (5, 3),
    (6, 7), (7, 8), (8, 6),
    (9, 10), (10, 11), (11, 9),
    (12, 13), (13, 14), (14, 12),
]);
let mut rng = StdRng::seed_from_u64(42);
let tri = Pattern::triangle();
let results = motif_significance(
    &g,
    &[("triangle", &tri, Induced::Yes)],
    40,
    NullModel::DegreePreserving { n_swaps_per_edge: 10 },
    &mut rng,
);
let (_name, entry) = &results[0];
assert!(entry.z_score > 0.0, "triangles should be over-represented");

Graphlet kernel between two graphs

use graphlet::rim::kernels::{graphlet_features, graphlet_kernel_cosine};
use petgraph::graph::UnGraph;

let triangle: UnGraph<(), ()> = UnGraph::from_edges([(0, 1), (1, 2), (2, 0)]);
let path: UnGraph<(), ()> = UnGraph::from_edges([(0, 1), (1, 2)]);

let ft = graphlet_features(&triangle, 3);
let fp = graphlet_features(&path, 3);
// Different classes at k=3, so they share no graphlet-class counts.
assert_eq!(graphlet_kernel_cosine(&ft, &fp), 0.0);

Scope, and what this is not

• The census, orbit, catalog, and kernel machinery treats every input as a simple undirected graph: self-loops are stripped, parallel edges (and directed reciprocal pairs) are deduped, and directed input is analyzed on its underlying undirected structure. Only rim::directed and the triad census respect arc direction.
• Graphlets and orbits are bounded to order 5 (k <= 5); this is where the "science-facing" surface (GDV/GDD, orbits, the named-motif catalog) is closed. The template module has no such bound and matches patterns of any size, at the cost of being a search rather than a closed-form count.
• Exact k=5 enumeration (both the undirected census/orbit path and the directed graphlet census) is slow on large or dense graphs: canonicalizing each instance costs up to k! permutations. The fast ORCA-style path (rim::scalable) covers only undirected orbit counting; there is no equivalent fast path yet for the directed side or for k > 5.
• This is a structural-mining / graphlet library, not a general graph-algorithms toolkit. It has no shortest paths, no centrality measures, no flow algorithms, and no general isomorphism beyond what the census/template machinery needs. For those, use petgraph directly (which also provides the VF2 isomorphism search this crate builds on) or rustworkx-core for a broader algorithm suite.

License

MIT. See the LICENSE file.