Hello everybody. In this talk, I'd like to tell you about recent work I've been doing on counting homomorphisms which relates to vector embeddings in machine learning and also other work on graph

isomorphism testing and graph similarity I've been interested in. The specific result I want to talk about today considers homomorphism counts of graphs of bounded tree depth and relates them to equivalence in first-order logic with counting. Let me start by introducing

homomorphism counts for graphs F and G. By homomorph F, G I denote the number of homomorphisms from F to G and homomorphisms are just mappings from the vertex set of F to the vertex set of G that preserve adjacency.

Okay, they have to map edges to edges but not necessarily non-edges to non-edges, and they also don't have to be injective or bijective or anything. The starting point for this whole theory is an old result due to Lovasz which says that two graphs G and H are

isomorphic if and only if for all graphs F the number of homomorphisms from F into G equals the number of homomorphisms from F into H. So why are we interested in this? One of the main motivations is to consider vector embeddings of graphs.

Vector embeddings are just embeddings of graphs into some vector space which should be a Hilbert space, that is, have an inner product, doesn't have to be finite dimensional. Okay, and the idea is to embed the graphs in such a way

that relationships, semantic relationships between the graphs, are reflected in geometric relationships of their images. Now the easiest instance of this could be that graphs that are somehow similar, for example structurally similar, should be mapped to the vectors that are close to one another. But there can be more complex relationships.

The practical reason for an interest in this comes from machine learning because standard machine learning algorithms operate on vector representations of the data, and if we want to do machine learning on graphs,

well vector embeddings give us such vector representations. And actually even in practice these embeddings can be infinite dimensional. There's a trick known as the kernel trick that handles infinite dimensional data by just accessing them through their inner product, which we always have in the Hilbert space.

Finally, vector embeddings also allow us to speak about similarity of graphs. They allow us to define distance measures on graphs. We're just saying that the distance between two graphs is the distance, the geometric distance, of their images in the vector space.

So these are some reasons why vector embeddings are interesting, and now let's return to homomorphism counts. Homomorphism counts give us very natural and generic vector embeddings of graphs. Namely, if we have a class F of graphs, we can define a vector embedding which I denote by

homF which maps the class of all graphs, so G, curly G is the class of all graphs, to a real vector space indexed by the elements of this class F, and it's defined by just

listing all the homomorphism counts from graphs F in F to a graph G. So homF of G is the vector with all the homomorphism counts as entries. In particular, we say that graphs G and H are homomorphism indistinguishable over the class F if they are mapped to the same vector. So we

can rephrase Lovasz's theorem from the first slide by saying two graphs G and H are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs.

And one more remark. I said we wanted to embed into Hilbert spaces where the crucial ingredient is an inner product, and indeed we can define an inner product on the range of these homomorphism vectors by taking point-wise products and then scaling them appropriately. Okay, here's an example

of a homomorphism vector embedding. I just look at the embedding, well, of these graphs using homF for a class F just consisting of three graphs, complete graphs on one, two, and three vertices. So I've illustrated the embedding here, although without giving the scale so you can't

see much, but one thing you can maybe see or figure out is that this and this graph, which I call G and H here, are homomorphism indistinguishable over this class F. They have

the same homomorphism vector which is 10, 20, 0, so maybe we can briefly check how we get there. Embeddings from the single vertex graph to a graph just counts how many vertices there are. Both of these graphs have 10 vertices. They also both have 10 edges, and embeddings from the

graph with just one edge essentially count edges, although every edge is counted twice, once in every direction. Homomorphisms from this graph basically count triangles. Again,

every triangle appears in six different homomorphisms, but these have zero triangles, so the third component is zero here. That would be the image of these two graphs. So now let's move on and let me tell you a list of very nice results about homomorphism

indistinguishable, many of which have only surfaced quite recently. The first one is an old result, although phrased in a way that is slightly unusual. For all graphs G and H, the following are equivalent. G and H are homomorphism indistinguishable over the class of all cycles, if and only if they are co-spectral. So that means their adjacency

matrices have the same multi-set of eigenvalues. The usual way of phrasing this result is in closed walks, but closed walks are just images, homomorphic images of cycles.

Second result, due to Drorjak, is 10 years old, and it says that two graphs are homomorphism indistinguishable over the class of all graphs of tree width at most k, for some positive integer k, if and only if they are not distinguished by the k-dimensional

Weisweiler-Lemann graph isomorphism algorithm. So the next results I want to mention are of a more algebraic nature. Let's again say we have two graphs G and H with vertex sets V and W, and let A and B be their adjacency matrices.

And we can put up a system of linear equations which has the equations in variables X, V, W, so the variables of our system are X, V, W for V and V, W and W.

So you can also think of these as being a matrix. Then the first equation basically reads as A times X, adjacency matrix of A times this variable matrix X equals

X times B, so that's this equation, and the second tells us that the row and column sums in our matrix are one. So these are the column sums, these are the row sums, they are all one. One thing we can observe is that this system of linear equations has a non-negative

integer solution, if and only if the two graphs are isomorphic. Why is that? Well, these equations tell us, if we look at non-negative integer solutions, that we have exactly one one in every row and in every column, so we have a permutation matrix

as the only possible solutions for this. And then we have this equation, we're looking for a permutation matrix satisfying this equation, and we can rewrite this for permutation matrices as X transpose A X equals B, and this simply means we're looking for a simultaneous permutation

of rows and columns of matrix A to obtain matrix B, and that's simply an isomorphism from A to B. Okay, and here's a very nice consequence of Dvorak's result from the previous slide, actually when we combine it with an old characterization of the

one-dimensional Weisfeiler-Leman algorithm due to Tinhofer, and it says that graphs G and H are homomorphism indistinguishable over the class of all trees, if and only if the system of equations has a non-negative rational solution. So, non-negative integer solution

corresponds to isomorphism or homomorphism indistinguishability over the class of all graphs, rational solution corresponds to homomorphism indistinguishability over the

class of all trees. And actually this can be extended to classes of graphs of bounded tree width and the higher dimensional Weisfeiler-Leman algorithm. Here's another very nice characterization that uses the same system of equations that says that the system has a rational solution,

which may have negative entries, if and only if the graphs are homomorphism indistinguishable over the class of all paths. Okay, and the next result I want to mention is about homomorphism indistinguishability over the class of planar graphs.

Two graphs are homomorphism indistinguishable over the class of all planar graphs, if and only if they are quantum isomorphic. Now quantum isomorphic is a notion that for someone like me is not particularly intuitive, but its definition is in terms of a very similar

system of equations as L of GH. Only now we're not looking for solutions over the reals or the rationals, but for solutions in some C star algebra. So essentially matrices satisfying

such equations. All right, so now let us finally come to the connection to logic. So the logic we're interested in here is the counting extension of first order logic, where we add counting quantifiers, there exists at least i elements x satisfying something. Now

this can be expressed in first order logic. So it's only a syntactic extension, it doesn't add any expressive power. But it lets us define new interesting fragments of first order logic

that we want to study here. And the first one is the fragment that uses a bounded number of variables. And again, as a corollary of Dvorak's results now combined with an old result due to Seiführer and Immermann, we obtain that two graphs are homomorphism indistinguishable

over the class of all graphs of tree with at most k, if and only if they are equivalent in the k plus one variable fragment of this logic. That is, they satisfy the same sentences of this logic with at most k plus one variables. Now bounded variable restrictions have

played an important role in finite model theory. So this is a very nice result and very relevant also for finite model theory. Although from a logical perspective, the restriction to a fixed number of variables may not be the most natural. What we would look at first in logic is a

restriction to a bounded quantifier ramp, that is, nesting depth of quantifiers. And this is what I've done in my licks paper. And to be able to state the main result,

I need to introduce the notion of tree depth of graphs. And the first thing we need for that is a definition of elimination forests of a graph. So it's convenient here to view rooted trees and also rooted forests as partially ordered sets. Okay, so let's say we have a tree

like this. Okay, so it's a rooted tree. So then the root is the minimal element and basically an element is greater than all its predecessors. So that gives us a partial order

where the predecessors of each element form a chain. And we say the height of such a tree is the maximum length of a chain. So in my picture, it would be so this would be a chain of maximum length and the length here would be one, two, three, four. So the height of this

tree would be four. That's the way we would measure it if we take this partial order view. Okay, and then an elimination forest for a graph G is a forest S with the same vertex set as the

graph G such that there's an edge between two vertices only if they are comparable in the partial order. So if there is an edge, then either V is smaller than or equal to W or W is smaller than or equal to V. Okay, that would make a forest an elimination forest. And here's

an example. We have a graph G here and the blue tree is an elimination forest, actually an elimination tree for my graph. So you only have edges between nodes and their predecessors.

And the tree depth of a graph is just the minimum height of an elimination forest for the graph. So for example, that's my previous example. And the elimination tree is actually one of minimum height, it has height three and the way we count height. So the tree depth of this

graph is three. And one fact that is good to know in this context is that a connected graph of tree depth k has radius at most two to the k minus one minus one. And finally, here's my main theorem. Two graphs are homomorphism indistinguishable over the class of graphs of

tree depth at most k, if and only if they satisfy the same sentences of this counting logic C, but now with bounded quantifier rank and the quantifier rank is at most k. The result in itself may not be too surprising. What I found surprising though is

that I have this exact correspondence between tree depth and quantifier rank. So homomorphism in distinguishability over natural graph classes corresponds very often to natural equivalence relations, defined in terms of logic or algebra as the system of

equations we considered before, or algorithmic spectral. So it's quite fascinating, I think, that we have these correspondences. And to me, this indicates that these homomorphism vector embeddings are indeed quite natural and the equivalence relation or the notion of

homomorphism in distinguishability is quite natural. One remark I have on this theorem, we can view the theorem as a locality theorem because, as I said, graphs of bounded tree depth

have bounded radius. So homomorphisms or homomorphic images of graphs of bounded tree width always have bounded radius. So these homomorphism numbers only depend on basically local neighborhoods in the graph. In that sense, it's a locality result. It can also be viewed

as a quantifier elimination result because we replace a complex formula with nested quantifiers interleaved with Boolean connectives by just flat homomorphism counts. Now, both of these results, locality quantifier elimination, are not too hard to prove directly,

so that's not the point. My point is just there is this connection and there is this logical view on this result. So let me say a few words on the proof. The proof uses essentially known techniques but you have to be very careful to apply them in the right way

and that's not completely trivial, I would say. So the proof goes in two steps and the first step is a reduction to a particular form of homomorphisms that I call past preserving.

So a homomorphism from a graph F to a graph G is past preserving and that always refers to an elimination tree of the graph F. If the restriction of this homomorphism to the chains in the elimination tree, to each chain is an isomorphism. So for example, I can never map

an element to a strict predecessor of this element. And then we introduce a second form of homomorphisms which are shrinking homomorphisms and these are in a way precisely orthogonal to the past preserving homomorphisms there. Every element has to be mapped

to a predecessor and there's an additional technical condition, the shrinking homomorphism has to be idempotent. So if I apply it twice, I don't obtain anything new. Okay, and now what we do is we decompose homomorphisms into a sum of shrinking and past preserving homomorphisms.

And then we can apply linear algebra. Basically we can write this, the homomorphism numbers now in terms of a matrix product and then we can invert one of the matrices, the matrices corresponding to the shrinking homomorphisms. And this way we can express homomorphism counts

for arbitrary homomorphisms in terms of past preserving homomorphisms and the other way around. And this linear algebra argument that we use in the last step that goes back to Lovers. The difficult part here or the part that requires care is to find the right decomposition.

And then in the second step of the proof, we connect this to logic. We simulate pebble game and ernfoechtrise style game using homomorphism counts. A fact that we use is that equivalence with respect to formulas of our counting logic of quantifier rank at most

k can be characterized by the k-move bijective pebble game. That's, as I said, an ernfoechtrise style game. And the main result here is a lemma that allows us to simulate a single move of the

game and I just want to state the lemma without going into any more details. It says that if we have two graphs g and g' such that for all graphs of tree depth at most k and all elimination trees of these graphs of height k, so optimal elimination trees, the number of past

preserving homomorphisms of f into g with respect to this tree equals the number of past preserving homomorphisms into g'. Then we can find a bijection between the vertex sets such that for all vertices the number of past preserving homomorphisms mapping the root of the elimination

tree to v equals the number of past preserving homomorphisms into g' mapping the root to the image of v under the bijection. That essentially allows us then to simulate one move of the

pebble game and we can use this to prove the theorem. And I'll stop here with a few open problems. The first is, well we have this characterization of homomorphism in distinguishability over classes of bounded tree width and we also had a characterization over paths in terms of a

system of equations. The question is can we combine these two and obtain a characterization of homomorphism in distinguishability over classes of bounded path widths. The second is whether there are natural graph classes such that homomorphism in distinguishability over these

classes characterizes graphs up to isomorphisms, of course other than the class of all graphs. So for example a candidate would be the class of all graphs of maximum degree at most three.

But so far we weren't able to prove any such results. Third question goes in the direction of graph similarity, distance measures on graphs. And the question is well these homomorphism embeddings give us distance measures as I've sketched before. The question is how do they relate to other distance measures, for example

defining terms of matrix norms on the graphs. And that's it. Thank you very much.