PDFLINK |

# a Graphical Design?

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 ,

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 .

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 .

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

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: https://sites.math.washington.edu/~GraphicalDesigns/.

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 of a subset -neighborhood is the set of vertices that are at most edges away from Steinerberger shows that if . is a graphical design, either the of -neighborhoods 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 .

### 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 subsets of -element 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 . subsets of -element 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 cube graph by -dimensional 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” design on -graphical 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.

## References

- [1]
- 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.^{✖} - [2]
- 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.^{✖} - [3]
- 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.^{✖} - [4]
- 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.^{✖} - [5]
- 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.^{✖} - [6]
- 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.^{✖} - [7]
- 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.^{✖}

## Credits

Figures 1–6 are courtesy of Catherine Babecki.

Photo of Catherine Babecki is courtesy of Kyle Naylor.