Titles and Abstracts - Fall 2021 DMD

Tina Eliassi-Rad, Northeastern University

Here's a short biographical sketch of Dr. Eliassi-Rad

Title: Geometric and Topological Graph Analysis for Machine Learning Applications

Abstract: This talk has two parts: (1) geometric analysis for graph embedding and (2) topological analysis for graph distances. First, graph embedding seeks to build an accurate low-dimensional representation of a graph. This low-dimensional representation is then used for various downstream tasks such as link prediction. One popular approach is Laplacian Eigenmaps, which constructs a graph embedding based on the spectral properties of the Laplacian matrix of a graph. The intuition behind it, and many other embedding techniques, is that the embedding of a graph must respect node similarity: similar nodes must have embeddings that are close to one another. We dispose of this distance-minimization assumption. In its place, we use the Laplacian matrix to find an embedding with geometric properties (instead of spectral ones) by leveraging the simplex geometry of the graph. We introduce Geometric Laplacian Eigenmap Embedding (or GLEE for short) and demonstrate that it outperforms various other techniques (including Laplacian Eigenmaps) in the tasks of graph reconstruction and link prediction. This work is joint with Leo Torres and Kevin Chan, and was published in the Journal of Complex Networks in March 2020 (http://eliassi.org/papers/torres_jcn2020.pdf). Second, measuring graph distance is a fundamental task in graph mining. For graph distance, determining the structural dissimilarity between networks is an ill-defined problem, as there is no canonical way to compare two networks. Indeed, many of the existing approaches for network comparison differ in their heuristics, efficiency, interpretability, and theoretical soundness. Thus, having a notion of distance that is built on theoretically robust first principles and that is interpretable with respect to features ubiquitous in complex networks would allow for a meaningful comparison between different networks. We rely on the theory of the length spectrum function from algebraic topology, and its relationship to the non-backtracking cycles of a graph, in order to introduce the Non-Backtracking Spectral Distance (NBD) for measuring the distance between undirected, unweighted graphs. NBD is interpretable in terms of features of complex networks such as presence of hubs and triangles. We showcase the ability of NBD to discriminate between networks in both real and synthetic data sets. This work is joint with Leo Torres and Pablo Suarez-Serrato, and was published in the Journal of Applied Network Science in June 2019 (http://eliassi.org/papers/appliednetsci19_nbd.pdf). Time permitting, I will finish with recent work on non-backtracking eigenvalues under node removal. This work is joint with Leo Torres, Kevin Chan, and Hanghang Tong, and was published in the SIAM Journal on Mathematics in Data Science in 2021

Lauren Rose, Bard College

Here is Dr. Rose's website

Title: EvenQuads: Notable Women in Math Playing Cards

Abstract: To celebrate their 50th Anniversary, the AWM published a card deck with profiles of women mathematicians on one side and a card deck for the game QUADS on the other side. QUADS was invented to be a variant of the popular card game SET®, with 4 states to each attribute instead of 3.

A SET® deck on the left, a QUADS deck on the right.

There has been a wealth of research about the mathematics behind SET®, mostly involving combinatorics, probability, finite geometry and algebra. The most famous unsolved problem associated with SET® is the "maximal cap" problem that arises in finite geometry. A cap is a collection of cards that do not contain a set, and a maximal cap is a cap of maximal size for a given number of attributes. The size of a maximal cap is only known for up to 6 attributes.

We introduce QUADS, a card game with 64 cards, where each card has a unique combination of one of 4 colors, shapes and numbers. The goal of this research is to adapt mathematical results about SET® to QUADS, and in particular to study the maximal cap problem for QUADS.

We provide results for small n, as well as some more general results.

Daniela Ferrero, Texas State University

Here is Dr. Ferrero's website

Title: New Challenges on Power Domination

Abstract: Electric power networks need continuous monitoring in order to prevent blackouts and power surges. This is usually accomplished by placing Phasor Measurement Units (PMUs) at strategically selected network locations and using their synchronized readings to determine the state of the network at any location without a PMU. This method requires a PMU placement that provides sufficient information, while due to their cost, the number of PMUs should be minimized. When an electrical power network is modeled by a graph, a PMU placement using the minimum number of PMUs corresponds to a minimum power dominating set for the graph.

In recent years, the deployment of wide area measurement systems of PMUs at large scale has shown that minimizing the number of PMUs alone yields unsatisfactory results, mainly due to the lack of redundancy to recover lost, or incorrect, PMU readings. While a higher level of redundancy implies larger numbers of PMUs, and increased costs, the addition of a few PMUs produces advantages to offset their cost.

In this talk, we introduce the power domination problem in graph theory, present its connection to linear algebra, and a brief summary of fundamental results. We then focus on new challenging problems on power domination arising in the study of the relationship between the cost of additional PMUs and the advantages obtained in the upgraded system.

Puck Rombach, University of Vermont

Here is Dr. Rombach's website

Title: Expressing graphs as symmetric differences of cliques of the complete graph

Abstract: Given a group of people and their friendship network, is it possible to form a set of clubs so that two people are together in an odd set of clubs if and only if they are friends? The answer is yes, since each pair of friends can form a 2-person club. A more interesting question is: what is the smallest number of clubs that achieves this?

In graph terminology, we are looking to express a graph G in terms of a collection C₁, ..., C_k of subsets of the vertices, so that two vertices have an edge in G if and only if they appear together in an odd number of subsets. We will call this a clique construction, and its minimum cardinality the clique build number. We first came across this problem in a mathoverflow question by Vince Vatter, who phrased it as expressing a graph as a sum of edge sets of cliques modulo 2. It turned out that Alekseev and Lozin had studied this question already in an algebraic phrasing: assign a set of vectors to the vertex set of your graph G, such that the dot product is 1 when vertices are adjacent and 0 when they are not. What is the minimum dimension of such a representation? If we work over 𝔽₂, then this question is equivalent to finding a minimum clique construction. If we let X be the matrix with such a vector set as its rows, then X X^Tgives a matrix equal to the adjacency matrix off the diagonal. The minrank of a graph over 𝔽₂ is defined as the minimum rank over all matrices where off-diagonal entries equal the adjacency matrix. Therefore, the clique build number gives us an upper bound on the minrank. In fact, we will show that they differ by one at most.

In this talk, we will discuss various properties of this invariant, its close connection to the minimum rank problem, and characterizations of graph classes for which the clique build number differs from the minrank. This is joint work with Calum Buchanan and Chris Purcell.