Fastest mixing Markov chain on graphs with symmetries

1.1 The fastest mixing Markov chain problem

• The problem is a convex optimization problem that can be formulated as an SDP and solved to any given precision in polynomial time by interior-point methods.Source: §1 · p. 1, §1.1 · p. 2
• The FMMC problem chooses a symmetric stochastic transition matrix on the graph to minimize its second-largest eigenvalue modulus, which governs convergence speed.Source: §1.1 · p. 2

1.2 Exploiting problem structure

• Sparsity alone has limited effect on interior-point complexity because the Newton system is typically dense, leaving an O(m^3) per-iteration cost.Without exploiting structure, the stated flop count is on the order of max{mn^3, m^2n^2, m^3}.Source: §1.2 · p. 3

1.3 Outline

• The paper previews orbit theory and block diagonalization, along with closed-form results for edge-transitive and distance-transitive graphs.Orbit chains and symmetry-adapted bases provide the two reduction routes described in the outline.Source: §1.3 · p. 4

2.1 Graph automorphisms and classes

• Automorphisms partition vertices and edges into orbits; vertex-, edge-, 1-arc-, and distance-transitivity describe distinct symmetry conditions.Figure 1 illustrates that edge-transitivity need not imply vertex-transitivity, or vice versa.Source: §2.1 · p. 5, Figure 1 · p. 5

2.2 FMMC with symmetry constraints

• An optimal FMMC solution lies in the automorphism-fixed feasible set, so one transition probability per edge orbit suffices; edge-transitive graphs need only one edge weight.Source: §2.2 · pp. 6–7

2.3 Formulation with reduced number of variables

• The reduced formulation assigns a common weight to each edge orbit and uses its orbit-graph Laplacian to parameterize the transition matrix and express the reduced FMMC problem.The parameterization characterizes the fixed-point set and supports a corresponding SDP formulation.Source: §2.3 · pp. 7–8

3 Some analytic results

• For edge-transitive, Cartesian-product, and distance-transitive graphs, symmetry often simplifies FMMC to solutions expressed through adjacency- or Laplacian-matrix eigenvalues.The maximum-degree and Metropolis-Hastings heuristics discussed in do not give the optimal solution even for these highly structured classes.Source: §3 · p. 8

3.1 FMMC on edge-transitive graphs

• For an edge-transitive graph, the optimal solution uses a common edge probability, chosen by balancing extreme Laplacian eigenvalues subject to a maximum-valency constraint.The proof reduces the transition matrix to P = I − αL.Source: §3.1 · p. 8

3.1.1 Cycles

• As n →∞, the cycle’s optimal transition probability α⋆→1/2 and its SLEM µ⋆→1 −2π2/n2.Source: §3.1.1 · p. 9

3.1.2 Complete bipartite graphs

• The complete bipartite graph is edge-transitive but not vertex-transitive; for n ≥m ≥2, its Laplacian has four distinct eigenvalues with stated multiplicities.The eigenvalues are m + n, n, m and 0, with multiplicities 1, m −1, n −1 and 1, respectively.Source: §3.1.2 · pp. 9–10

3.2 Cartesian product of graphs

• The Cartesian product’s Laplacian eigenvalues are pairwise sums of eigenvalues from its factors, enabling FMMC solutions for products of simple graphs.The product Laplacian is formed from the factor Laplacians using Kronecker products.Source: §3.2 · p. 10

3.2.1 Two-dimensional meshes

• As n →∞, the wrapped two-dimensional mesh has optimal transition probability α⋆→1/4 and SLEM µ⋆→1 −π2/n2.The mesh is the Cartesian product of two copies of Cn.Source: §3.2.1 · pp. 10–11

3.2.2 Hypercubes

• The hypercube Qd is built recursively as a Cartesian product, and its Laplacian eigenvalues are 2k for k = 0, 1, . . . , d, each with stated multiplicity.The section then uses these eigenvalues to obtain the FMMC solution.Source: §3.2.2 · p. 11

3.3 FMMC on distance-transitive graphs

• Distance-transitive graphs have highly repeated eigenvalues, so the smaller intersection matrix can provide the distinct eigenvalues needed for the FMMC solution.The solution requires only the second-largest and smallest adjacency eigenvalues.Source: §3.3 · pp. 12–13

3.3.1 Complete graphs

• The complete graph’s optimal chain has P = (1/n)11T, with all n −1 non-leading eigenvalues zero, giving perfect mixing after one step.Source: §3.3.1 · p. 13

3.3.2 Petersen graph

• The Petersen graph has intersection-matrix eigenvalues η0 = 3, η1 = 1 and η2 = −2, which the section uses to obtain its FMMC parameters.Source: §3.3.2 · p. 13

3.3.3 Hamming graphs

• Hamming graphs H(d, n) are Cartesian products of d complete graphs and have intersection-matrix eigenvalues ηk = d (n −1) −kn for k = 0, . . . , d.The hypercube is the special case n = 2.Source: §3.3.3 · pp. 13–14

3.3.4 Johnson graphs

• For the Johnson graph J(n, q), the intersection-matrix eigenvalues are ηk = q (n −q) + k (k −n −1), for k = 0, . . . , q.The section applies Corollary 3.2 to obtain the optimal transition probability.Source: §3.3.4 · p. 14

4 FMMC on orbit graphs

• Orbit chains can be much smaller than the original chain while retaining all its distinct eigenvalues, reducing the FMMC problem to a smaller graph.Large automorphism groups often produce high eigenvalue multiplicities; the orbit-chain reduction focuses on distinct eigenvalues.Source: §4 · p. 14

4.1 Orbit theory

• If a subgroup has a fixed point in every orbit under Aut(G), its orbit chain contains all distinct eigenvalues of the original chain.Theorem 4.1 also gives a collection of orbit chains attaining all eigenvalues, with eigenvectors recoverable by lifting.Source: §4.1 · pp. 15–16

4.2 Fastest mixing reversible Markov chain on orbit graph

• Orbit chains are generally nonsymmetric but reversible, so detailed balance permits a convex formulation of the fastest reversible-chain problem.The method identifies edge orbits, constructs a suitable orbit chain and its stationary distribution, then solves its SDP; the optimal SLEM and original transition probabilities are recovered from the orbit solution.Source: §4.1 · p. 15, §4.2 · pp. 17–18

4.3.1 The graph Kn-Kn

• For the graph formed by joining two copies of K_n with a bridge, three edge-orbit probabilities suffice, and the SDP uses four variables and 5 × 5 matrices for every n.A subgroup chain has at most five distinct eigenvalues regardless of n; the example is revisited using block diagonalization for an exact analytic solution.Source: §4.3.1 · pp. 18, 20

4.3.2 Complete binary tree

• For T_n, the full-automorphism orbit graph is a path with n + 1 nodes and n edge probabilities; a 2n + 1-vertex orbit chain suffices for the reduction.The original SDP matrices have size |V| × |V|, exponential in n; the later block-diagonalization method further decomposes the chain matrix into blocks of sizes 1 through n + 1.Source: §4.3.2 · pp. 20–21

5 Symmetry reduction by block diagonalization

• Every transition matrix in the fixed-point subset is invariant under graph automorphisms, so it commutes with their permutation matrices.This symmetry permits a coordinate transformation that block diagonalizes every such matrix.Source: §5 · p. 22
• The transformed blocks are usually much smaller, and repeated blocks can be discarded in computation.The construction is based on classical group representation theory and was developed for more general SDPs.Source: §5 · p. 22
• The method used in this section is based on classical group representation theory, was developed for more general SDPs, and has applications in sum-of-squares polynomial minimization and controller design for symmetric dynamical systems.Source: §5 · p. 22

5.1 Some group representation theory

• A representation assigns invertible matrices to group elements while preserving multiplication, and it is irreducible when it has no nontrivial invariant subrepresentation.The paper assumes orthogonal representations so the coordinate transformation can also be chosen orthogonal.Source: §5.1 · pp. 22–23
• A finite group has finitely many inequivalent irreducible representations, and any representation decomposes into their direct sum with multiplicities.The corresponding isotypic components consist of invariant subspaces transforming according to each irreducible representation.Source: §5.1 · p. 22
• A symmetry-adapted basis yields blocks of dimension m_i for each irreducible representation, with n_i equal copies of each block.For symmetric matrices, blocks associated with complex- or quaternionian-type representations simplify to collections of equal subblocks.Source: §5.1 · pp. 22–23

5.2 Block diagonalization of SDP constraint

• The transformed SDP has one matrix inequality per inequivalent irreducible representation, with each block sized by that representation’s multiplicity; repeated copies need not be included.These blocks can be much smaller than the original vertex-sized matrices, especially when irreducible representations have high dimension.Source: §5.2 · pp. 23–24
• The all-ones term occupies only one nonzero diagonal block, and that block corresponds to the orbit chain under H.The first block also contains the eigenvalues of the orbit chain; other blocks add eigenvalues associated with orbit chains under subgroups of H.Source: §5.2 · pp. 24–25
• The number of H-fixed vectors equals the number of H-orbits, giving the dimension of the trivial-representation component.The paper constructs an orthonormal basis for this component from vectors supported on individual orbits.Source: §5.2 · p. 24

5.2.1 A running example

• The 3 × 3 grid is neither vertex- nor edge-transitive, so its two edge orbits receive separate transition probabilities.Its 9 × 9 matrix is replaced by four blocks of dimensions 3, 1, 1, and 2; the optimal values are algebraic rather than rational.Source: §5.2.1 · pp. 26–27

5.3.1 Complete bipartite graphs

• The complete bipartite graph’s block decomposition identifies its eigenvalues and connects the 2 × 2 block to an orbit chain, with other orbit chains supplying the additional eigenvalues.The resulting blocks can be used to solve the FMMC problem.Source: §5.3.1 · pp. 27–28

5.3.2 Complete k-partite graphs

• For complete k-partite graphs, block diagonalization yields one k-dimensional block and k further blocks of dimensions n_i − 1, which can be substituted into the SDP.Source: §5.3.2 · p. 28

5.3.3 Wheel graph

• For wheel graphs, block diagonalization gives a closed-form optimum; relative to a cycle, the hub improves both the SLEM and peripheral-edge transition probability by a factor of 1 − 1/n.The wheel’s block diagonalization works better here than orbit theory, whose orbit graph with a fixed peripheral vertex has at least (n + 1)/2 orbits.Source: §5.3.3 · p. 29

5.3.4 Kn-Kn

• For K_n-K_n, the block constraints have total size 5, and the reduced problem permits analytic expressions for the optimal transition probabilities and convergence rate.A high-dimensional irreducible representation with multiplicity one accounts for the large reduction.Source: §5.3.4 · p. 31

5.3.5 Complete binary trees

• For complete binary trees, recursively nested blocks encode additional eigenvalues and their multiplicities; interlacing reduces the FMMC problem to blocks B_n+1 and B_n.The latter reduction corresponds to an orbit chain with 2n + 1 vertices.Source: §5.3.5 · pp. 32–33

5.3.6 An example of Ron Graham

• For the 6n-vertex graph built from repeated six-vertex pieces, block diagonalization produces blocks no larger than 6 × 6, and numerical experiments suggest a particular edge-probability pattern for n ≥ 3.The graph has dihedral symmetry, including reflections as well as rotations; the reported probability pattern is presented as an apparent numerical finding.Source: §5.3.6 · pp. 33–34

• Symmetry can reduce both optimization-variable counts and matrix sizes, and can yield closed-form solutions for edge-transitive and distance-transitive graphs.Source: §6 · p. 34
• Orbit theory gives diagonal blocks an intuitive interpretation, while block diagonalization provides theoretical insight into constructing orbit chains.The block-diagonalization method can be mostly automated once irreducible representations are generated.Source: §6 · p. 34
• Symmetry exploitation can also remove degeneracy and improve conditioning and reliability, with potential relevance to other combinatorial optimization problems formulated as or approximated by SDP or eigenvalue optimization.Source: §6 · pp. 34–35
• The techniques require expertise in orbit theory, group representations, and SDP interior-point methods; automatic symmetry detection and integration with numerical algorithms remain practical challenges.Source: §6 · p. 35