> For the complete documentation index, see [llms.txt](https://lichangbin.gitbook.io/paper_notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lichangbin.gitbook.io/paper_notes/sep/learning-steady-states-of-iterative-algorithms-over-graphs.md). # Learning Steady-States of Iterative Algorithms over Graphs ## Motivation Many graph analytics problems can be solved via iterative algorithms according to the graph structure, and the solutions of the algorithms are often characterized by a set of steady-state conditions. * PageRank: score of a node * Mean field inference: the posterior distribution of a variable Instead of designing algorithms for each individual graph problem, we take a different perspective: Can we **design a learning framework** for a diverse range of graph problems that **learns the algorithm over large graphs** **achieving the steady-state solutions efficiently and effectively**? How to represent the meta learner for such algorithm and how to carry out the learning of these algorithms? ## Iterative algorithm over graphs For a graph: $$\mathcal{G}=(\mathcal{V}, \mathcal{E})$$ , with node set $$\mathcal{V}$$ and edge set $$\mathcal{E}$$ , many iterative algorithms over graphs can be formulated into: $$ \begin{array}{l} h\_{v}^{(t+1)} \leftarrow \mathcal{T}\left(\left{h\_{u}^{(t)}\right}*{u \in \mathcal{N}(v)}\right), \forall t \geqslant 1, \text { and } \\ h*{v}^{(0)} \leftarrow \text { constant }, \forall v \in \mathcal{V} \end{array} \space\space\space\space\space\space (1) $$ until the steady-state conditions are met: $$ h\_{v}^{*}=\mathcal{T}\left(\left{h\_{u}^{*}\right}\_{u \in \mathcal{N}(v)}\right), \forall v \in \mathcal{V} \space\space\space\space\space\space (2) $$ * $$node: v,u\in \mathcal{V}$$ * $$\text{the set of neighbor nodes of } v: \mathcal{N}(v)$$ * $$\text{some operator }: \mathcal{T}(\cdot)$$ * $$\text{Intermediate representation of node }v: h\_v$$ * $$\text{Intermediate representation of node }v \text{ at step } t: h\_v^{(t)}$$ * $$\text{Final (converged/steady) intermediate representation of node }v : h\_v^{\*}$$ Specifically: ### 1) Graph component detection problem **Goal**: find all nodes within the same connected component as **source node** $$s\in \mathcal{V}$$ **How**: iteratively propagate the label at node $$s$$ to other nodes: $$ y\_{v}^{(t+1)}=\max *{u \in \mathcal{N}(v)} y*{u}^{(t)}, y\_{s}^{(0)}=1, y\_{v}^{(0)}=0, \forall v \in \mathcal{V} $$ * $$y\_s:$$ label of node $$s$$ * $$y\_s^{(t)}:$$ label of node $$s$$ at step $$t$$ * at initial step $$t=0$$, the label at node $$s$$ are set to 1 (infected), 0 for all other nodes. **Steady state**: nodes in the same connected component as $$s$$ are infected, (labelled as 1) $$ y\_v^{*}= \max\_{u\in \mathcal{N}(v)}y\_u^{*} $$ ### 2) PageRank scores for node importance **Goal**: estimate the importance of each node in a graph **How**: update score of each node iteratively $$ r\_{v}^{(t+1)} \leftarrow \frac{(1-\lambda)}{|\mathcal{V}|}+\frac{\lambda}{|\mathcal{N}(v)|} \sum\_{u \in \mathcal{N}(v)} r\_{u}^{(t)}, \forall v \in \mathcal{V} $$ * $$r\_v^{(t)}$$ : score of node $$v$$ at step $$t$$ * Initialization: $$r\_v^{(0)} = 0, \forall v \in \mathcal{V}$$ **Steady state**: $$r\_{v}^{*} = \frac{(1-\lambda)}{|\mathcal{V}|}+\frac{\lambda}{|\mathcal{N}(v)|} \sum\_{u \in \mathcal{N}(v)} r\_{u}^{*}$$ ### ### 3) Mean field inference in graphical model **Goal**: approximate the marginal distributions of a set of variables $$x\_v$$ in a graph model defined on $$\mathcal{G}$$ In graphical model, we know: $$ p\left(\left{x\_{v}\right}*{v \in \mathcal{V}}\right) \propto \prod*{v \in \mathcal{V}} \phi\left(x\_{v}\right) \prod\_{(u, v) \in \mathcal{E}} \phi\left(x\_{u}, x\_{v}\right) $$ * $$p\left(\left{x\_{v}\right}\_{v \in \mathcal{V}}\right)$$ : true marginal distribution * $$\phi(x\_v) \text{ and } \phi(x\_u,x\_v)$$ are node and edge potential respectively **How**: The marginal approximation can be obtained in an iterative fashion by the following mean field update: $$ \begin{aligned} q^{(t+1)}\left(x\_{v}\right) \leftarrow \phi\left(x\_{v}\right) \prod\_{u \in \mathcal{N}(v)} & \exp \left(\int\_{u}q^{(t)}\left(x\_{u}\right) \log \phi\left(x\_{u}, x\_{v}\right) \mathrm{d} u\right) \end{aligned} $$ * $$q^{(t+1)}\left(x\_{v}\right)$$ : marginal approximation of a set of variables $$x\_v$$ at step $$t+1$$ **Steady State**: $$\begin{aligned} q^{*}\left(x\_{v}\right) = \phi\left(x\_{v}\right) \prod\_{u \in \mathcal{N}(v)} & \exp \left(\int\_{u}q^{*}\left(x\_{u}\right) \log \phi\left(x\_{u}, x\_{v}\right) \mathrm{d} u\right) \end{aligned}$$ ### 4) Compute long range graph convolution features (node classification) Goal: extract long range features from graph and use that features to figure to capture the relation between graph topology and external labels How: One possible parametrization of graph convolution features $$h\_v$$ can be updated from zeros initialization as: $$ h\_{v}^{(t+1)} \leftarrow \sigma\left(W\_{1} x\_{v}+W\_{2} \sum\_{u \in \mathcal{N}(v)} h\_{u}^{(t)}\right) $$ * $$h\_{v}^{(t+1)} : \text{graph convolution features for node } v \text{ at step } t+1$$ * $$\sigma : \text{a nonlinear element-wise operation}$$ * $$W\_1,W\_2: \text{parameters of the operator}$$ Steady State: $$h\_{v}^{*} \leftarrow \sigma\left(W\_{1} x\_{v}+W\_{2} \sum\_{u \in \mathcal{N}(v)} h\_{u}^{*}\right)$$ After that: the label for each node will be determined by the steady state feature $$h\_v^*$$ by a labeling function: $$f(h\_v^*)$$ ## The Algorithm Learning Problem: framework of algorithm design **Assumption**: we have collected the output of an iterative algorithm $$\mathcal{T}$$ over a single large graph. Training dataset (input of the proposed algorithm) consists of: * input graph $$\mathcal{G}=(\mathcal{V},\mathcal{E})$$ * output of the iterative algorithm for a subset of nodes, $$\mathcal{V}^{(y)} \subseteq\mathcal{V}$$ , (**Note: labeled nodes**) from the graph $$\mathcal{D}=\left{f\_v^{*}:=f(h\_v^{*})|h\_v^{*}=\mathcal{T\[{h\_u^{*}}\_{u\in \mathcal{N}(v)}], v\in \mathcal{V}}^{(y)}\right} \space\space\space\space\space (3)$$ * $$h\_v^{\*}$$ : is the quantity in the iterative algorithm satisfying the steady-state conditions * $$f(\cdot)$$ : an additional labeling function taking input the steady-state quantity, produces the final label for each node * $$f\_v^{\*}:$$ **ground truth** of node $$v$$ Given the above $$\mathcal{D}$$ , Goal: to learn a parameterized algorithm $$\mathcal{A}*{\Theta}$$ , such that the output of the algorithm $$\mathcal{A}*{\Theta}$$ can mimic the output of the original algorithm $$\mathcal{T}$$ . Namely: The output of $$\mathcal{A}*{\Theta}$$ is: $$\mathcal{A}*{\Theta}\[\mathcal{G}]={\hat{f\_v}}\_{v\in \mathcal{V}^{(y)}}$$ , which are close to $$f\_v^{\*}$$ according to some loss function. The algorithm learning problem for $$\mathcal{A}\_{\Theta}$$ can be formulated into the following optimization problem: $$ \min\_{\Theta} \sum\_{v \in \mathcal{V}^{(y)}} \ell\left(f\_{v}^{\*}, \widehat{f}*{v}\right) \space\space\space\space\space\space\space (4)\\ \text { s.t. }\left{\widehat{f}*{v}\right}*{v \in \mathcal{V}^{(y)}}=\mathcal{A}*{\Theta}\[\mathcal{G}] \space\space\space\space\space\space\space (5) $$ * $$\ell\left(f\_{v}^{\*}, \widehat{f}\_{v}\right)$$ : loss function **Design goal**: **respect steady-state conditions** and **learn fast**. **Core**: * a steady-state operator $$\mathcal{T}\_{\Theta}$$between vector embedding representations of nodes * a link function $$g$$ mapping the embedding to the algorithm output. * **Note**: namely $$\mathcal{A}*{\Theta}: \mathcal{T}*{\Theta} \text{ and } g$$ #### Stead-state operator and link function $$ \begin{aligned} \text { output }: &\left{\widehat{f}*{v}:=g(\hat{h}*{v})\right}*{v \in \mathcal{V}} \space\space\space\space\space\space\space\space\space (6)\\ \text { s.t. } & \widehat{h}*{v}=\mathcal{T}*{\Theta}\left\[\left{\widehat{h}*{u}\right}\_{u \in \mathcal{N}(v)}\right] \space\space\space\space\space\space\space\space\space (7) \end{aligned} $$ * initialization: $$\widehat{h}\_v \leftarrow \text{constant for all } v\in \mathcal{V}$$ * update using equation (7) ### **Operator** $$\mathcal{T}\_{\Theta}$$ : a two-layer NN * General nolinear function class * The operator **enforces the steady-state condition** of node embeddings based on 1-hop local neighborhood information. * Due to the variety of graph structures, this function should be able to **handle different** **number of inputs** (i.e., different number of neighbor nodes) $$ \widehat{h}*v = \mathcal{T}*{\Theta}\left\[\left{\widehat{h}*{u}\right}*{u \in \mathcal{N}(v)}\right]=W\_{1} \sigma\left(W\_{2}\left\[x\_{v}, \sum\_{u \in \mathcal{N}(v)}\left\[\widehat{h}*{u}, x*{u}\right]\right]\right) \space\space\space\space\space\space\space\space (9) $$ * $$\sigma(\cdot)$$ : element-wise activation function: Sigmoid, ReLU * $$W\_1, W\_2 : \text{weight matrices of NN} .$$ $$W\_1: \text{first layer, } W\_2: \text{2nd layer}$$ * $$x\_v$$ : the optional feature representation of nodes ### **Link function (prediction function)** $$g$$ : a two-layer NN * General nolinear function class * input: node embeddings * predict: the corresponding algorithm outputs (like label of node) $$ g\left(\widehat{h}*{v}\right)=\sigma\left(V*{2}^{\top} \operatorname{ReLU}\left(V\_{1}^{\top} \widehat{h}\_{v}\right)\right) \space\space\space\space\space\space (10) $$ * $$\widehat{h}\_{v}$$ : node embeddings * $$V\_1, V\_2 : \text{parameters of } g.$$ $$V\_1: \text{first layer, } V\_2: \text{2nd layer}$$ * $$\sigma:\text{task-specific activation function}$$ * linear regression: identity function $$\sigma(x)=x$$ * multi-class classification: $$\sigma(\cdot)$$ is softmax (output a probabilistic simplex) ### The overall optimization problem $$ \begin{array}{c} \min *{\left{W*{i}, V\_{i}\right}*{i=1}^{2}} \mathcal{L}\left(\left{W*{i}, V\_{i}\right}*{i=1}^{2}\right):=\frac{1}{\left|\mathcal{V}^{y}\right|} \sum*{v \in \mathcal{V}^{(y)}} \ell(f\_{v}^{\*}, g(\hat{h}*{v})) \\ \text { s.t. } \widehat{h}*{v}=\mathcal{T}*{\Theta}\left\[\left{\widehat{h}*{u}\right}\_{u \in \mathcal{N}(v)}\right], \forall v \in \mathcal{V} \end{array} \space\space\space\space\space\space (11) $$ * $$W\_1,W\_2: \text{parameters of } \mathcal{T}\_{\Theta}$$ * $$V\_1,V\_2: \text{parameters of } g$$ * my understanding: semi-surpervised learning ![https://www.wikiwand.com/en/Fixed-point\_iteration](/files/-MHS0EiOYaOrI-mZMsAx) ## How to solve (11): Stochastic Steady-state Embedding(SSE) An alternating algorithm: alternate between: * **using most current model to find the embeddings and make prediction** * **using the gradient of the loss with respect to** $${W\_1, W\_2, V\_1, V\_2}$$ **for update these parameters** ![](/files/-MHNxO__GIAeZOgurIbK) #### Intuition: * RL (policy iteration): improve the policy minimizing the cost proportional to $$f^{\*}$$ by updating the parameters $$\mathcal{T}\_{\Theta} \text{ and } g$$ * steady-state $$\hat{h\_v}$$ for each node: "**value function**" * embedding operator $$\mathcal{T}\_{\Theta}$$ and classifier function $$g$$ : "**policy**" * K-means and EM (mine) ### "Value" estimation: estimate steady-state $$\hat{h\_v}$$ **limitation**: it is prohibitive to solve the steady-state equation exactly in large-scale graph with millions of vertices since it requires **visiting all the nodes in the graph**. **Solution**: **stochastic fixed point iteration,** the extra randomness on the constraints for sampling the constraints to tackle the groups of equations approximately. In $$k\text{-th}$$ step, first sample a set of nodes $$\tilde{\mathcal{V}}={v\_1,v\_2,\dots,v\_N}\in \mathcal{V}$$ from the entire node set rather of the labeled set. Update the new embedding by **moving averageļ¼š** $$ \widehat{h}*{v*{i}}^{(k)} \leftarrow(1-\alpha) \hat{h}*{v*{i}}^{(k-1)}+\alpha \mathcal{T}*{\Theta}\left\[{\widehat{h}*{u}^{(k-1)}}*{u \in \mathcal{N}\left(v*{i}\right)}\right], \forall v\_{i} \in \tilde{\mathcal{V}} \space\space\space\space\space\space\space\space (12) $$ * $$\alpha: 0 \leq \alpha\leq1$$ ### "Policy" improvement: update parameters of $$\mathcal{T}\_{\Theta} \text{ and } g$$ At the $$k\text{-th}$$ step, once we have $${\widehat{h}*{v}^{(k)}}*{v\in \mathcal{V}}$$ satisfying the steady-state equation, we use vanilla stochastic gradient descent to update parameters $${W\_1, W\_2, V\_1, V\_2}$$ : $$ \begin{aligned} \frac{\partial \mathcal{L}}{\partial \color{red}V\_{i}} &=\widehat{\mathbb{E}}\left\[\frac{\partial \ell\left(f\_{v}^{*}, g\left(\hat{h}*{v}^{k}\right)\right)}{\partial g\left(\hat{h}*{v}^{k}\right)} \frac{\partial g\left(\hat{h}*{v}^{k}\right)}{\partial \color{red}V*{i}}\right] \\ \frac{\partial \mathcal{L}}{\partial \color{red}W\_{i}} &=\widehat{\mathbb{E}}\left\[\frac{\partial \ell\left(f\_{v}^{*}, g\left(\hat{h}*{v}^{k}\right)\right)}{\partial \widehat{h}*{v}^{k}} \frac{.\partial \mathcal{T}*{\Theta}}{\partial \color{red}W*{i}}\right] \end{aligned} $$ * $$\widehat{\mathbb{E}}\[\cdot]$$ : the expectation is w\.r.t. uniform distribution over labeled nodes $$\mathcal{V}^{(y)}$$ . ![](/files/-MHOuhfdkMyG-UohUEID) * $$n\_h$$ : the # of inner loops in "value" estimation * $$n\_f$$ : the # of inner loops in "policy" improvement ![Policy Iteration for comparison](/files/-MHOvGiPj713VkZxX_Bf) ### Complexity * Memory space * $$O(|\mathcal{V}|):$$ The dominating part is the persistent node embedding matrix$${\widehat{h}*v}*{v\in \mathcal{V}}$$ * $$O(T|\mathcal{V}|):$$ $$T\text{-hops}$$ for GNN family * Time: the computational cost in each iteration is just proportional to the number of edges in each mini-batch. * "policy" improvement: $$O(M\frac{|\mathcal{E}|}{|\mathcal{V}|})$$ * "value" estimation: $$O(N\frac{|\mathcal{E}|}{|\mathcal{V}|})$$ ## Reference * * * * * * * * *