mismatches between mathematical essences and data structures

[gusl]

Lately, I've been faced with problems of the following type:
* there are many ways to represent an object
* a canonical representation is either hard to define, or unnatural to work with

(1) optimizing over the space of k-dim linear subspaces (a.k.a. k-flats). They can be represented as bases (more canonically, orthogonal bases), but that's not enough to identify them uniquely. We can define k-flats to be points in a Grassmanian, which is the appropriate quotient space (in which bases of the same space form an equivalence class). But optimizing here involves doing calculus on surfaces, which requires knowledge of differential geometry... or easier, one could use Lagrange multipliers, but I don't have enough constraints (I don't know how to constrain the rotation of the orthogonal basis).

(2) suppose you have an unknown probability distribution over clusterings of nodes. You can easily assign a label to each node such that two nodes are in the same cluster if they have the same label. Of course, these labels are just names, and permuting them results in an equivalent structure, which necessarily has the same probability. Now, suppose you get several samples from this distribution (say, by MCMC), and you want to estimate the distribution. Now, for each sample, you could simply add the other n!-1 relabelings ("mirror images"), but can you do better?
This is known as the "label-switching problem", and in some cases it can addressed by "artificial identifiability constraints" (e.g. in the form of: WOLOG, node 1 is always labeled with "a"), but this too can become unmanageable and unnatural.

Tangentially, is there a nice way to represent graphs modulo isomorphism? I'm aware of spectral techniques (e.g. graph Laplacian), but these are usually lossy, i.e. querying whether two graphs are the "same" (i.e. isomorphic) will result in some false positives.

Comments

[ikeepaleopard]

Graph isomorphism is NP-complete so if you had such a representation, creating an instance for a given graph would have to be Hard.

[gustavolacerda.livejournal.com]

I was just thinking that.

[gustavolacerda.livejournal.com]

OR you'd have a proof of P=NP.

[gustavolacerda.livejournal.com]

... hard in the worst case. One can still hope that there exists something that works fast most of the time.
See http://en.wikipedia.org/wiki/Smoothed_analysis

[bhudson.livejournal.com]

The wiki article on the graph isomorphism problem shows a bunch of special cases of graph classes for which isomorphism is easy. A lot of geometric graphs fall into at least one of these categories (bounded-degree, for example).

[bhudson.livejournal.com]

Actually, it's not; it and factoring are the usual examples of problems in NP, not known to be in P, but not NP-complete. So you can solve isomorphism but you still won't be able to fire your theorem-proving mathematicians.

[ikeepaleopard]

Oh, I knew that, but I always get it confused with subgraph isomorphism but I know that I get confused about it and then get things backwards anyway by overthinking.

[bhudson.livejournal.com]

I did not know that the really fucking boring* talk I went to about proving that min-weight triangulation was NP-complete was such an important piece of work.


*: it takes a lot for me to get excited about widgets anymore. Maybe if the still-living Michael Jackson had presented the result I might have been interested. Maybe.

Graphs

[(Anonymous)]

Forming a canonicalization algorithm for representing graphs modulo isomorphism is clearly at least as hard as checking whether two graphs are, in fact, isomorphic (proof: just run the canonicalizer on both graphs and check if the results are equal).

And the graph isomorphism problem currently has no known polynomial-time solution.

Re: Graphs

[(Anonymous)]

...... aaaaand I didn't notice that there were 8 comments before mine, because they weren't on the same page :)

Re: Graphs

[gustavolacerda.livejournal.com]

yes, that's what aleffert and I were saying.

btw, who is this?

Re: Graphs

[(Anonymous)]

Chris

Re: Graphs

[gustavolacerda.livejournal.com]

from UBC, or from Toronto?

Re: Graphs

[(Anonymous)]

UBC. I didn't know you knew another one!

Re: Graphs

[gustavolacerda.livejournal.com]

I have 18 Facebook friends named "Chris*", 3 of whom are at UBC.
Are you Chris H?

Re: Graphs

[(Anonymous)]

Yep. And that's a lot! I don't have any others.

Re: Graphs

[gustavolacerda.livejournal.com]

I think that Chrises tend to be Chrisophobic. Like, names is one area where you see reverse homophily.

Re: Graphs

[(Anonymous)]

Maybe. Hadn't really thought about it. It makes sense that it might feel slightly odd to refer to someone by "your own" name.

Re: Graphs

[gustavolacerda.livejournal.com]

s/reverse homophily/heterophily/

[mdinitz.livejournal.com]

As a theoretician it pains me to do this, but there are some decent algorithms out there for testing graph isomorphism and reducing to a canonical graph. In a previous life, when I was doing combinatorial design theory, I used Brendan McKay's nauty, which does exactly what you asked for -- given a graph, it returns a representation that is canonical up to isomorphism. I have no idea what algorithm it uses, but it was reasonably fast when I used it 7 or 8 years ago.

[simrob.livejournal.com]

Wait why are you in pain?

[mdinitz.livejournal.com]

Because I just suggested that someone use an algorithm that is exponential time in the worst case, and moreover suggested that it was a pretty decent algorithm. Considering that I firmly believe in the fundamental importance of the worst case polytime vs. worst case exptime distinction, this was a painful suggestion to make.

[neelk]

I take it you don't like ML type inference? Worst case exptime, but in practice it is never anything other than linear-times-inverse-Ackermann unless you very, very carefully engineer your program to hit the bad case.

[(Anonymous)]

is (1) just an example or you actually have some problem which requires some sort of optimization over the space of "k-flats"? if you have such a problem, maybe you can exploit better the structure of it in order to simplify matters. for example, you can characterize the k-th largest eigenvalue of a hermitian matrix as the solution of a certain non-linear min-max problem in which the min is taken over the space of "k-flats" and the max is taken in that space (removing the origin, actually) that's the result of the Courant-Fischer Minimax Theorem, you can take a look at its statement here http://www.cs.tau.ac.il/~haima/gen_cf.pdf

my point is, exploiting the structure of your problem may lead to other more useful characterizations of the solution-set which wouldn't require you to actually try to find a representation for the set of k-flats... there are many different methods to compute eigenvalues...

a propósito, sou eu, Ives...

[gustavolacerda.livejournal.com]

Thanks, Ives!

Both of these are actual problems motivated by research ideas. #1 is like a regression problem: given points on a unit hypersphere centered at the origin, which k-dim "great circle" minimizes the residual sum of squares? The great circles correspond to the set of k-flats (aka "k-planes") through the origin (the circle is just the intersection of the flat and the sphere).

I don't see how eigenvalues might help here. Do you? I don't have a square matrix anywhere.

[(Anonymous)]

what do you mean by "residual sum of squares"? is it the sum of the squared distances to the k-flat? could it be the maximum of the squared distances? I will think about it...

Ives

[gustavolacerda.livejournal.com]

<< is it the sum of the squared distances to the k-flat? >>

yup. You could use either geodesic distance (ideal) or orthogonal distance. It probably doesn't matter which.

[(Anonymous)]

did it... if you use the orthogonal distance (regular euclidean distance), it turns out that the solution is the same as that given by PCA... that's where an eigendecomposition solves this problem... ;)

just to fix notation, the solution (k-flat) corresponds to the vector space spanned by the eigenvectors associated to the k largest eigenvalues of the matrix \sum_i{x_i x_i^T}, x_i being the points on that sphere...

if you really want the proof, I guess I could take some time later to write it down for you or just meet me at UBC some day...

nice exercise, tough... I guess the geodesic distance would be way more complicated...

cheers,
Ives

[gustavolacerda.livejournal.com]

Thanks for working on this. The geodesic distance is easy to write down, and probably convex.

[(Anonymous)]

you're welcome... regarding the geodesic distance, it is simple to write down, but to optimize it I guess wouldn't be so simple... regarding convexity, I don't know what you could do since the sphere is not convex. I have some ideas to circumvent this but I'm not sure how useful they would be...

Ives

[gustavolacerda.livejournal.com]

the sphere isn't convex??

[(Anonymous)]

nop... but the closed ball is... I mean, a convex subset of the euclidean space...
maybe we are adopting the same name for different things... let me make it clear...
for me, the sphere is the set of x such that ||x||=1, and the closed ball is the set of x such that ||x|| <= 1
as a subset of the euclidean vector space (inheriting the usual addition and scalar multiplication), the sphere is not convex, but the closed ball is...
are you ok with that?

cheers,
Ives

[gustavolacerda.livejournal.com]

ah, right.

[gustavolacerda.livejournal.com]

This square matrix, is it n-by-n (where n is the dimension of the Euclidean space), or P-by-P (where P is the number of points)?
I think the former. When you take all the eigenvectors, you end up with the original hypersphere.

I now understand why PCA is the solution here.