Assuming that edges are generated independently is a strong limitation, because real-world graphs exhibit many complex dependencies between edges. For example, the tendency of real-world graphs to have high clustering coefficients is difficult to capture in an edge-independent model. Explicitly modeling dependencies between edges alleviates this issue while keeping the model tractable.

University of Michigan - Ann Arbor

Google

Modeling Edge Dependencies

L: denote the lower-triangular portion of the adjacency matrix A

L[v1, :] denote the row of L corresponding to node v1

assume that the rows of L are indexed by nodes v1, ..., v|V|

due to the lower-triangular nature of L, we will have that L[vi, vj] = 0, ∀j > i, meaning that we only need to be concerned with generating the first i entries for any row L[vi, :] because the rest will be zeros

when we generate row L[vi, :], we condition on all the previous generated rows L[vj, :] with j < i

Autoregressive model formula

In the autoregressive approach to graph generation, it is assumed that edges are generated sequentially. The likelihood of each edge is conditioned on the edges that have been previously generated in the sequence.

Learn Before

Related