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

In the autoregressive approach, we assume that edges are generated sequentially and that the likelihood of each edge can be conditioned on the edges that have been previously generated.

What's new: conditionality

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

University of Michigan - Ann Arbor

GRL Book

1) consists of at least three layers of nodes: an input layer, a hidden layer and an output layer.

2) Learning occurs in the perceptron by changing connection weights after each piece of data is processed, based on the amount of error in the output compared to the expected result. This is an example of supervised learning, and is carried out through backpropagation, a generalization of the least mean squares algorithm in the linear perceptron.

Learn Before

Related

Learn After