> 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/experiments.md).

# Experiments

We compare our proposed algorithm with some of the GNN variants who have the fixed finite number of propagations T.

$$\mathcal{D}^{train}={\mathbf{X}^{tr},\mathbf{y}^{tr}}$$    $$\mathcal{D}^{test}={\mathbf{X}^{ts}}$$ 

Inductive Learning: $$\mathbf{X}^{ts}$$ will not be used during training.

Transductive Learning:  $$\mathbf{X}^{ts}$$ will be used during training.

more: <https://www.wikiwand.com/en/Transduction_(machine_learning)>

## 1. Algorithm-learning: Connectivity Detection

Task: identify the component ID for a certain node.

### Transductive setting:

* training: 10% nodes with labels
* testing : the rest

![](https://1687130946-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEnQbUIupyAn8eMmrmG%2F-MHHR0YfnbKYiuCiBNCw%2F-MHI4JVCrmWs5cospe4X%2Fexp1.png?alt=media\&token=d9d663e9-f0a6-4d66-9c07-9789be55445b)

## 2. Algorithm-learning: PageRank

### 1) Real-world graphs: (Blogcatalog, and Pubmed graphs)

Transductive setting:

* training: varying the training set size from 10%-90% of the total nodes
* testing : reserve 10% nodes for held-out evaluation

![](https://1687130946-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEnQbUIupyAn8eMmrmG%2F-MHHR0YfnbKYiuCiBNCw%2F-MHI6MoRZx3vJEGtl3Xv%2Ffig3.png?alt=media\&token=4bca26b8-5a39-4a78-8ce9-bdee7797f079)

* **SSE**
* **S2V-degree**
* GCN
* structure2vec

### 2) Barabasi-Albert random graphs

Transductive setting:

* split the nodes equally into training and test set

Inductive setting:

* the training is performed in a single graph, while the algorithm is asked to generalize to new graphs from the same distribution

![](https://1687130946-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEnQbUIupyAn8eMmrmG%2F-MHHR0YfnbKYiuCiBNCw%2F-MHI6k-cpJ1N4DbyEogw%2Ftb1.png?alt=media\&token=823d8339-ee59-4a64-a2a3-380a1b4d4617)

## 3. Algorithm-learning: Mean Field Inference on Graphical Model

Task: learn the mean-field score for each node over a 128\*128 lattice with $$\mathbf{x}\_v$$ set to be binary with a Gaussian perturbation.

(Figure 3c)

## 4. Application: Node Classification

### Transductive setting:

![](https://1687130946-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEnQbUIupyAn8eMmrmG%2F-MHHR0YfnbKYiuCiBNCw%2F-MHICSGVVCg1rBIfZ6S3%2Ftb3.png?alt=media\&token=7d6bff15-ea08-4af8-ac21-98b17def83e8)

### Inductive setting:

![](https://1687130946-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEnQbUIupyAn8eMmrmG%2F-MHHR0YfnbKYiuCiBNCw%2F-MHICln4q4O4qxCFU3DQ%2Ftb4.png?alt=media\&token=cf42269b-a676-4f85-a4e3-1b0d48f4f8ef)

## 5. Scalability&#x20;

* efficient for large-scale graphs in terms of both convergence speed and execution time

### 1) time per update

![](https://1687130946-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEnQbUIupyAn8eMmrmG%2F-MHIE2bKK9DhBkr_R7-H%2F-MHIF11ISZ0uMzlevOch%2Ffig4.png?alt=media\&token=35ed2d80-8a1e-4c49-9a39-96f18f72764e)

### 2) convergence&#x20;

* faster than others

## Conclusion

we presented SSE, an algorithm that can **learn many steady-state algorithms** over graphs.&#x20;

Different from graph neural network family models, **SSE is trained stochastically which only requires 1-hop information**, but can capture fixed point relationships efficiently and effectively.&#x20;

We demonstrate this in both synthetic and real-world benchmark datasets, with **transductive and inductive experiments** for learning various graph algorithms.&#x20;

The algorithm also **scales well up to 100m nodes** with much less training effort.&#x20;

Future work includes investigation in learning more complicated graph algorithms, as well as distributed training.

##