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.

University of Michigan - Ann Arbor

Google

Modeling Edge Dependencies

There is a strong limitation of assuming the edges are independent because real-world graphs exhibit many complex dependencies between edges.

For example, the tendency for real-world graphs to have high clustering coefficients is difficult to capture in an edge-independent model

Hence, dependency is a solution to alleviate this issue while maintaining tractability

Why edges are dependent

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

Learn Before

Related