Skip to Main Content

a Graphical Design?

Catherine Babecki

Communicated by Notices Associate Editor Emilie Purvine

Graphical designs are quadrature rules for graphs . Broadly speaking, a graphical design is a relatively small subset of vertices that captures the global behavior of functions . We motivate the precise definition through numerical integration on the sphere.

The regular icosahedron (Figure 1) inscribed in the unit sphere has the following amazing property: for any polynomial of degree at most 5, the average of on the vertices of the icosahedron is equal to the average of over . By exploiting symmetry, these 12 points exactly average the 36-dimensional vector space of polynomials with degree at most 5. More generally, a spherical -design 3 is a finite subset of points chosen so that for any polynomial of degree at most ,

Figure 1.

The regular icosahedron is a spherical 5-design.

Graphic without alt text

The space of polynomials restricted to the sphere is spanned by the eigenfunctions of the spherical Laplacian , known as spherical harmonics. What is a natural analogue of spherical harmonics for a graph? We start by defining an operator analogous to for a finite, undirected graph . Let be the adjacency matrix of defined as if and 0 otherwise, and let be the diagonal matrix with , the number of edges adjacent to . Then behaves similarly to in that for a function ,

averages in the neighborhood of .

Figure 2.

An 11-graphical design on the truncated icosahedral graph.

Graphic without alt text
Figure 3.

The contiguous United States graph. Vertices are states, and edges connect adjacent states. Each eigenvector was affinely transformed so that and . The interval was assigned a smooth gradient. With respect to the graph geometry, and are smooth, but is not so smooth.

Graphic without alt text

Spherical harmonics are ordered by their degree as polynomials, also called frequency. Similarly, the eigenvalues of can be ordered as

Here means is lower frequency than . This also orders the eigenspaces of ; if the eigenspace has eigenvalue , we write if . With this ordering, low-frequency eigenvectors respect the structure of (see Figure 3). The spectrum of is a rich object of study in its own right in spectral graph theory. Throughout this paper, let be a graph for which has distinct eigenspaces ordered from low to high frequency as .

Definition 1 (17).

A subset averages an eigenspace of if for all ,

To mimic the qualities of a spherical -design, we seek vertex subsets that exactly average the low frequency eigenspaces of .

Definition 2.

A -graphical design on is that averages , …, .

Figure 2 shows an 11-graphical design on the trucated icosahedral graph. These 30 vertices average a 49-dimensional subspace of the 60-dimensional space of functions . We call a subset that averages as many eigenspaces as possible for the graph a maximal design. Figure 4 shows a maximal design; no proper subset can average 14 or more of the 16 eigenspaces.

Graphical designs have strong connections to the combinatorics of a graph, especially in the presence of structure and symmetry. A gallery of designs can be found at:

Figure 4.

A 13-graphical design on the J7 Flower Snark.

Graphic without alt text

We can generalize Definition 1 by allowing weighted sums on the left of 1 and call these subsets weighted designs (Figure 5). Weighted designs are connected to oriented matroid duality and the rich literature of eigenpolytopes 2.

The neighborhood of a graphical design

Graphical designs were introduced by Steinerberger in 7. The -neighborhood of a subset is the set of vertices that are at most edges away from . Steinerberger shows that if is a graphical design, either the -neighborhoods of grow exponentially, or is large. Indeed, in Figures 2, 4, and 5, the 1-neighborhood of is . In Figure 6, the 1-neighborhood of is 2072 of 2277 vertices, and the 2-neighborhood of is .

Figure 5.

A weighted 8-graphical design on the Szekeres Snark. Pink indicates a smaller weight – all weights are positive.

Graphic without alt text

Extremal graphical designs

In 4, Golubev considered extremal designs, which are subsets that integrate all but one eigenspace of , though this eigenspace may come anywhere in our frequency ordering. As an example, the Kneser graph has vertices corresponding to the -element subsets of . Two vertices are adjacent if their subsets are disjoint. Golubev shows that extremal configurations from the Erdős-Ko-Rado theorem, namely a subset of vertices corresponding to all the -element subsets of containing a fixed element, are extremal designs on .

Graphical designs in Cayley graphs

Cayley graphs are created from an underlying group, and this additional structure can provide enough information for explicit constructions.

Denote the -dimensional cube graph by , where if differ on exactly one coordinate. Graphical designs on this family of Cayley graphs connect to error correcting codes. We can interpret the vertices of as bit strings, and subsets as codes. The Hamming code is the “best” -graphical design on in several senses; it is maximal, it is extremal, and it optimizes the ratio between and . All minimal extremal designs of cycles and cocktail party graphs, two other families of Cayley graphs, are described in 2.

Applications and connections

Graphical designs lie at an exciting intersection between contemporary applications and mathematical theory. The appearance of the graph Laplacian suggests further ties to spectral graph theory, 1 connects to coding theory, and extremal combinatorics appears in 4. Graphical designs in Cayley graphs are rooted in group representations, and probabilistic tools were used in 7.

Modern data, such as social networks, ad preferences, movie recommendations, and traffic updates, is often modeled through graphs, driving a need for new data processing methods. The relatively new field of graph signal processing 5 seeks to extend classical signal processing techniques to the domain of graphs. Graphical designs provide a framework for graph sampling and numerical integration on graphs. For instance, Figure 6 shows a weighted graphical design with all positive weights on a highly nonlinear graph from real world data. In applications, it may suffice to look for approximate designs where the equality in 1 is relaxed. This can be modeled via optimization.

Figure 6.

The 228 red vertices are a weighted 229-graphical design on this network of 2277 English-language Wikipedia pages related to chameleons 6. Vertices represent pages, and edges join pages that are mutually connected by hyperlinks.

Graphic without alt text


C. Babecki, Codes, cubes, and graphical designs, J. Fourier Anal. Appl. 27 (2021), no. 5, Paper No. 81, 34, DOI 10.1007/s00041-021-09852-z. MR4309817Show rawAMSref\bib{cubescodes}{article}{ author={Babecki, Catherine}, title={Codes, cubes, and graphical designs}, journal={J. Fourier Anal. Appl.}, volume={27}, date={2021}, number={5}, pages={Paper No. 81, 34}, issn={1069-5869}, review={\MR {4309817}}, doi={10.1007/s00041-021-09852-z}, } Close amsref.
C. Babecki and R. R. Thomas, Graphical designs and gale duality, Preprint, arXiv:2204.01873, 2022, accepted.Show rawAMSref\bib{GaleDuality}{eprint}{ author={Babecki, C.}, author={Thomas, R.~R.}, title={Graphical designs and gale duality}, journal={Mathematical Programming}, arxiv={2204.01873}, date={2022, accepted}, } Close amsref.
P. Delsarte, J. M. Goethals, and J. J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), no. 3, 363–388, DOI 10.1007/bf03187604. MR485471Show rawAMSref\bib{sphericalTdesigns}{article}{ author={Delsarte, P.}, author={Goethals, J. M.}, author={Seidel, J. J.}, title={Spherical codes and designs}, journal={Geometriae Dedicata}, volume={6}, date={1977}, number={3}, pages={363--388}, review={\MR {485471}}, doi={10.1007/bf03187604}, } Close amsref.
K. Golubev, Graphical designs and extremal combinatorics, Linear Algebra Appl. 604 (2020), 490–506, DOI 10.1016/j.laa.2020.07.012. MR4123763Show rawAMSref\bib{Golubev}{article}{ author={Golubev, Konstantin}, title={Graphical designs and extremal combinatorics}, journal={Linear Algebra Appl.}, volume={604}, date={2020}, pages={490--506}, issn={0024-3795}, review={\MR {4123763}}, doi={10.1016/j.laa.2020.07.012}, } Close amsref.
A. Ortega, P. Frossard, J. Kovacevic, J. M. F. Moura, and P. Vandergheynst, Graph signal processing: Overview, challenges, and applications, Proceedings of the IEEE 106 (2018), no. 5, 808–828.Show rawAMSref\bib{signalprocessing}{article}{ author={Ortega, A.}, author={Frossard, P.}, author={Kovacevic, J.}, author={Moura, J. M.~F.}, author={Vandergheynst, P.}, title={Graph signal processing: Overview, challenges, and applications}, date={2018}, journal={Proceedings of the IEEE}, volume={106}, number={5}, pages={808\ndash 828}, } Close amsref.
B. Rozemberczki, C. Allen, and R. Sarkar, Multi-scale attributed node embedding, J. Complex Netw. 9 (2021), no. 2, Paper No. cnab014, 22, DOI 10.1093/comnet/cnab014. MR4256683Show rawAMSref\bib{rozemberczki2019multiscale}{article}{ author={Rozemberczki, Benedek}, author={Allen, Carl}, author={Sarkar, Rik}, title={Multi-scale attributed node embedding}, journal={J. Complex Netw.}, volume={9}, date={2021}, number={2}, pages={Paper No. cnab014, 22}, issn={2051-1310}, review={\MR {4256683}}, doi={10.1093/comnet/cnab014}, } Close amsref.
S. Steinerberger, Generalized designs on graphs: sampling, spectra, symmetries, J. Graph Theory 93 (2020), no. 2, 253–267, DOI 10.1002/jgt.22485. MR4043757Show rawAMSref\bib{graphdesigns}{article}{ author={Steinerberger, Stefan}, title={Generalized designs on graphs: sampling, spectra, symmetries}, journal={J. Graph Theory}, volume={93}, date={2020}, number={2}, pages={253--267}, issn={0364-9024}, review={\MR {4043757}}, doi={10.1002/jgt.22485}, } Close amsref.


Figures 1–6 are courtesy of Catherine Babecki.

Photo of Catherine Babecki is courtesy of Kyle Naylor.