# Does marginalization increase the number of edges in Graph SLAM?

I thought marginalization does not change the number of the edges but this material (page 11) describes that as a result of marginalization we will have more edges in graph. Why does it increase the edges?

For those who does not want to open the page, it is written as follows.

Marginalization: Cons Con: More edges in graph

1. Feature with N observations leads to O(N2) edges
2. Slower/harder to solve, (Information Matrix less sparse)

Exact marginalization will change the number of edges, because once a node (pose) is eliminated, the information in the edges that were incident to that node would have to be stored as edges between the existing nodes. This densification of the graph automatically means that the information matrix is dense because of the newly added edges. This results in what is known as an 'elimination clique'.

A nice example of this is shown in this paper, which I am reproducing here:

When moving from pose $x_t$ to $x_{t+1}$, the SLAM algorithm would naturally want to marginalize the $x_t$ node away: but that means the direct landmark-pose observations that were encoded in the edges connecting $x_t$ and $L_i$ would now have to be rewired to be incident on $x_{t+1}$, which is equivalent to obtaining new observations of $L_i$. Notice how the information matrix becomes denser.

The alternative to this is called approximate marginalization. As an example, this paper attempts approximate marginalization by using Chow-Liu trees, where the graph is pruned such that each node connects only to one other node that affords the maximum mutual information.