Incorrectly named function for adjacency matrix.

[tonioteran]

I would opt to change the names of these functions, since they don't really return the adjacency matrix of the graph, nor do they return the incidence matrix.

They return the "boolean" version of the measurement Jacobian, which @dehann very cleverly calls it the first order Taylor expansion of the graph.

Probably getMeasurementMatrix would be better?

https://github.com/JuliaRobotics/DistributedFactorGraphs.jl/blob/05b6c1e8bc2d591a2506d7324a1f3a163a7dd791/src/services/AbstractDFG.jl#L539

https://github.com/JuliaRobotics/DistributedFactorGraphs.jl/blob/05b6c1e8bc2d591a2506d7324a1f3a163a7dd791/src/services/AbstractDFG.jl#L561

[Affie]

I think its called a biadjacency matrix. Special case for a bipartite graph.

[tonioteran]

I believe it cannot be an adjacency matrix, since it would have to be square, with rows and columns being the factor graph variables, and the ones representing edge existence.

In this case we have the columns being the factor graph variables and the rows denoting the factors, with the ones expressing the variables involved in each one. Note we need not have a square matrix.

Here's a toy example of such a matrix.

   x1    x2    x3
 _                   _
|   1                  |   prior on x1
|          1           |   prior on x2
|                 1    |   prior on x3
|   1     1            |   odometry btwn x1 and x2
|_        1      1    _|   odometry btwn x2 and x3

EDIT: wow, it's harder than I thought to write down a nice matrix.

More on this can be found on Kaess et al. IJRR paper on iSAM2 (Figure 3).

[GearsAD]

Hi @tonioteran, yes I believe it's not a true adjacency matrix. If it leads to confusion we can change the name in v0.6.

Btw cheat code for markdown table generation - https://www.tablesgenerator.com/markdown_tables

x1	x2	x3	desc
1			prior on x1
	1		prior on x2
		1	prior on x3
1	1		odometry btwn x1 and x2
	1	1	odometry btwn x2 and x3

DF EDIT: so this is the thing we need to name properly and current getAdjacency is misleading...

[dehann]

I agree with Tonio to change the name, and would suggest we change it to:

• getIncidenceMatrix[Sparse].

Concern with getMeasurementMatrix is that would be slightly more specific to a Jacobian (iSAM2 style)---hence Gaussian---assumptions. HISTORY: Guess the origin way back was "getMeasurementAssociations/Adjacency" and then just snapped to "getAdjacency"

I think its called a biadjacency matrix. Special case for a bipartite graph.

So biadjacency is still square -- if i'm understanding this right? I had never heard that before. Why don't we then also just expose:

• getBiAdjacencyMatrix[Sparse], which will internally calculate the square of getIncidenceMatrix[Sparse] (or however we end up naming it).

[Affie]

If you calculate the square (literally) version it would be an adjacency matrix.

Edit to clarify: B is the matrix currently returned by getAdjacencyMatrix sometimes called a biadjacency matrix. A is an adjacency matrix. That is exactly what i did in the LightDFG driver. I got the adjacency matrix and removed the redundant entries to be left with B. If you want an incidence matrix you have to modify the code to return an incidence matrix.

[tonioteran]

So biadjacency is still square -- if i'm understanding this right?

Yes, as with any adjacency matrix. In this case, since the factor graph is a bipartite, we would get the special 'biadjacency' one. An important thing to note though, is that for this to hold, we'd need to consider the factors to be variables, which we do not (as far as I know?), which is why we also do not use the adjacency matrix with respect to inference when dealing with factor graphs.

If you calculate the square version it would be an adjacency matrix.

I'm a bit confused with this as well, since the square of the incidence matrix of a graph is not the adjacency. The relation is something like:

I^T * I = A + D,

where I is the incidence matrix, A the adjacency, and D the degree matrix. This matrix does not have a specific given name that I'm aware of.

Re the getMeasurementMatrix name, I agree that it would signify more of a "Gaussian" version of the factor graph, so I am fully in favor of going with the getIncidenceMatrix[Sparse] (which is still a tiny tad of a misnomer, since we're denoting the priors on variables as a type of self loop with the rows with individual 1's, but I think we don't need to get that nitpicky hehe).

Sorry I haven't been super active; still on vacation at a remote location with dial-up style internet connection haha.

[GearsAD]

@tonioteran no worries same here.

Will rename as getIncidenceMatrix[Sparse], that works :+1: it'll be in 0.6

[GearsAD]

https://github.com/JuliaRobotics/DistributedFactorGraphs.jl/blob/4Q19/poc/v0_6/src/services/AbstractDFG.jl#L569-L591 :rocket:

[dehann]

I'm worried Adjacency implies square matrix. When using CCOLAMD ordering, we definitely do not want the square but rather rectangular form matrix (currently penciled as IncidenceMatrix). I'd like to understand @Affie 's concern with that a little more? I mention becuase Cholesky (AMD ordering) requires a square matrix, which I feel is the Adjacency/BiadjacencyMatrix...

Is there consensus that BiAdjacency is still square, and we definitely definitely need a function call that gives the information form (aka IncidenceMatrix) as per Tonio's equation above?

• EDIT DF, I think BiAdjacency is square.

xref #272

[dehann]

Perhaps I could ask for another opinion from @david-m-rosen please?

[tonioteran]

You can also take a peep at the same discussion, but that we've been having here: JuliaRobotics/IncrementalInference.jl#473.

The matrix is intrinsically related to the incidence matrix, being that it does describe the edge relationship between variables (in a kind of Markov Random Field way, plus the priors). I understand that it is not identical to the incidence, and thus the hesitation to name it so, hence my initial suggestion of naming it something with the word Measurement.

What is to me crystal clear is that it has absolutely nothing to do with the adjacency matrix (it's not even square!), and thus should not bear that name, or any flavor of adjacency name for that matter.

[Affie]

I don't know what else to say.

The function (currently named getAdjacencyMatrixSparse) definitely returns the "B" matrix in https://github.com/JuliaRobotics/DistributedFactorGraphs.jl/issues/249#issuecomment-569770051 I think the getAdjacencyMatrix that returns a dense matrix of Symbols is deprecated, or should be.

What is wrong with adjacent? it is used in the literature as "where Θi is the set of variables θj adjacent to the factor fi".

Maybe some other name ideas :smiley:

• getBMatrix
• getTheMatrixShowingVariablesAndFactorsAdjacency
• getTheSparsityPatternMatrixOfTheBlockFormMeasurementJacobianMatrix
• getMatrixIndicatingWhetherVariableFactorPairsAreAdjacentOrNotInTheGraph
• getTheAdjacencyMatrix"A"OfABipartiteGraphOrginizeItSoThat"B"UniquelyDefinesTheGraphAndThatTheRemainingPartsOf"A"CanBeDiscardedAsRedundantAndCallItTheBiadjacencyMatrix

[tonioteran]

I'm down for this one: getTheAdjacencyMatrix"A"OfABipartiteGraphOrginizeItSoThat"B"UniquelyDefinesTheGraphAndThatTheRemainingPartsOf"A"CanBeDiscardedAsRedundantAndCallItTheBiadjacencyMatrix

[Affie]

Haha, It has the added benefit of keeping your pinkies fit with all the capital letters.

[dehann]

that returns a dense matrix of Symbols is deprecated, or should be

agree

[dehann]

consider the factors to be variables, which we do not (as far as I know?)

Too deep for here, but factors are just observed states, no? So they are variables that are fixed... It's little tricky to interpret a general from where the algebra structure exists on the edges. Perhaps the big secret is that the edges in the factor graph represent relation ship only, and not closed from expressions in any way, but rather a series of special cases where a collection of factors with edges to variables are modeled together with closed form expressions.

The function (currently named getAdjacencyMatrixSparse) definitely returns the "B" matrix in #249 (comment)

We are not going to resolve this without an example -- at least I'm not fast enough to see the square. See example further developed example here https://github.com/JuliaRobotics/IncrementalInference.jl/issues/473#issuecomment-581102453

[dehann]

resolved in JuliaRobotics/IncrementalInference.jl#473