We revisit rule-based algorithms for multi-agent path finding (MAPF) where the task is being solved by applying a fixed set of movement primitives. MAPF is a task of navigating agents from their initial positions to given individual goal positions via non-conflicting paths. The environment in which agents move is modeled as an undirected graph with agents in its vertices. Rule-based algorithms we study in this paper are complete, polynomial-time, and sub-optimal with respect to common cumulative objectives used in MAPF such as makespan or sum-of-costs. Out contribution consists in a new step that pre-processes the input graph by decomposing it into highly connected components via spectral clustering. Agents are moved to their goal cluster first before the rule-based algorithm is applied. The benefit of this approach is twofold: (1) the algorithms are often more efficient on highly connected clusters and (2) we can potentially run the algorithms in parallel on individual clusters.