Adjacency and Spectral Embedding Features

[dpmcsuss]

There are a few features that I would like to see in igraph with regards to the adjacency matrix and spectral embeddings. This is a general feature request and/or a profession of ignorance about features in igraph. Urgency level is low but here are my thoughts. I have not figured out which of these are easy/hard to implement.

1. It would be nice to retrieve an adjacency matrix with weights. I could see implementing this using the edge feature where the default value for non-edges would be 0 and otherwise the weight matrix would be populated with the specified numeric edge attribute.
2. Similarly, sometimes we have categorical edge features so it would be nice to retrieve the adjacency matrix that corresponds to edges only with a particular edge feature, ie where E(g)$x == y for some edge feature x and edge feature value y. I think right now you would do this with get.adjacency(subgraph.edges(g, which(E(g)$x==y)).
3. I would like to be able to do the adjacency spectral embedding using one of the above adjacency matrices.
4. I would like to be able to embed the graph laplacian either normalized or non-normalized. Possible options include D-A, I-D^{-1/2}AD^{-1/2}, D^{-1/2}AD^{-1/2}. There are other versions such as the regularized version Karl Rohe came up with.
5. Right now it seems like igraph is taking the svd of A and returns the embedding corresponding to the largest eigenvalues in magnitude. Sometimes we want the largest eigenvalues in the algebraic ordering (at least for undirected graphs) and for some of the laplacians we want the smallest algebraic.

[gaborcsardi]

1 It would be nice to retrieve an adjacency matrix with weights. I could see implementing this using the edge feature where the default value for non-edges would be 0 and otherwise the weight matrix would be populated with the specified numeric edge attribute.

g[]

2 Similarly, sometimes we have categorical edge features so it would be nice to retrieve the adjacency matrix that corresponds to edges only with a particular edge feature, ie where E(g)$x == y for some edge feature x and edge feature value y. I think right now you would do this with get.adjacency(subgraph.edges(g, which(E(g)$x==y)).

What is wrong with this? Btw. are you sure that you want to remove isolate vertices here?

3 I would like to be able to do the adjacency spectral embedding using one of the above adjacency matrices.

You can, just convert them to an igraph graph, with graph.adjacency().

4 I would like to be able to embed the graph laplacian either normalized or non-normalized. Possible options include D-A, I-D^{-1/2}AD^{-1/2}, D^{-1/2}AD^{-1/2}. There are other versions such as the regularized version Karl Rohe came up with.

So you want all these?

5 Right now it seems like igraph is taking the svd of A and returns the embedding corresponding to the largest eigenvalues in magnitude. Sometimes we want the largest eigenvalues in the algebraic ordering (at least for undirected graphs) and for some of the laplacians we want the smallest algebraic.

[dpmcsuss]

Thanks Gabor!

1. OK, so g[] always uses the weight attributes?
2. This is fine I think. I also see the delete.vertices argument.
3. Seems fine if a little cumbersome. I still don't see how to get an embedding uses the spectral decomposition of the weight matrix though.
4. Eventually, I think it would be nice. These technically could all be implemented with a another argument to adjacency.spectral.embedding that the user can give a diagonal matrix with the default being the identity. Together with our diagonal augmentation this would allow us to create any of the above.
5. Any thoughts? Is this harder

[gaborcsardi]

1 OK, so g[] always uses the weight attributes?

If present, yes. http://igraph.org/r/doc/graph.structure.html

3 Seems fine if a little cumbersome. I still don't see how to get an embedding uses the spectral decomposition of the weight matrix though.

Well, it is cumbersome if you work with matrices. The idea is that you work with igraph graphs, because they are typically more efficient for graph operations. I can add the weighted option.

I am a bit reluctant to make igraph functions work on matrices, because then you'll be converting between the two back and forth. And then why not add it for the other 200 functions? It will be very confusing that some functions work with matrices, others with graphs.

5 Any thoughts? Is this harder

No, easy, ARPACK can do all these, that's why I did not comment on it.

[dpmcsuss]

Well, it is cumbersome if you work with matrices. The idea is that you work with igraph graphs, because they are typically more efficient for graph operations. I can add the weighted option.

I am a bit reluctant to make igraph functions work on matrices, because then you'll be converting between the two back and forth. And then why not add it for the other 200 functions? It will be very confusing that some functions work with matrices, others with graphs.

I don't want any functions to work with matrices. Rather, I just want the adjacency.spectral.embedding function to have an option to return the embedding of the weight matrix also. I think the other cases are accomplished with adjacency.spectral.embedding(subgraph.edges(g,eges.to.keep),no) or some such.

[gaborcsardi]

I don't want any functions to work with matrices. Rather, I just want the adjacency.spectral.embedding function to have an option to return the embedding of the weight matrix also.

Yes, that's what I meant by 'I can add the weighted option'.

I think the other cases are accomplished with adjacency.spectral.embedding(subgraph.edges(g,eges.to.keep),no) or some such.

Yes, btw. I'll rename adjacency.spectral.embedding to ase and subgraph.edges will be rewritten/renamed to subgraph, so this will be ase(subgraph(g, E(g)[x==y])), which is a bit better.

I can work on a more compact notation for selecting subgraphs if we end up doing this frequently, but I probably would not create a function for each special case like ase.

[dpmcsuss]

Great! Sorry I missed the your weighted comment. This is all very great!