Solving Problems on Graph

Graphs can be used in many problem and there are many possible problems on graphs. We will mention a few popular problems on graphs12.

Node Classification

Created based on the text in Hamilton2020
Is the user in black a bot or a normal user?

Created based on the text in Hamilton2020

Given graph that has incomplete attribute labeling of the nodes, predict the attributes on the nodes.

The following concepts can be used to classify nodes.

Statement of the node classification problem

Given $\mathcal V_{\mathrm{train}}\subset \mathcal V$ on a graph, infer labels $y_u$ of node $u$, with $u\in \mathcal V\setminus \mathcal V_{\mathrm{train}}$.

Relation Prediction

Also named as link prediction, graph completion.

Users and Movies as a Bipartite Graph
Connections of Users on Social Network

Statement of the relation prediction problem

Given the nodes $\mathcal V$ on a graph $\mathcal G$, and $\mathcal E_{\text{train}}\subset \mathcal E$, predict other edges $\mathcal E \setminus \mathcal E_{\text{train}}$.

Clustering and Community Detection

Each node is an author, the edges indicate collaborations between the authors.
Communities of collaboration network

Each node is an author, the edges indicate collaborations between the authors.

Assign nodes to groups. See [[Popularity versus similarity in growing networks]] Popularity versus similarity in growing networks Introduce geometry into the manifold of complex networks for examples.

Classification, Regression, and Clustering on Graph Level

Given some graphs, perform classification, regression, and clustering on the set of graphs, e.g., predict the toxicity of molecules.

  1. Hamilton2020 Hamilton WL. Graph Representation Learning. Morgan & Claypool Publishers; 2020. pp. 1–159. doi:10.2200/S01045ED1V01Y202009AIM046  ↩︎

  2. Sanchez-Lengeling2021 Sanchez-Lengeling B, Reif E, Pearce A, Wiltschko AB. A Gentle Introduction to Graph Neural Networks. Distill. 2021;6. doi:10.23915/distill.00033  ↩︎

  3. McPherson2001 McPherson M, Smith-Lovin L, Cook JM. Birds of a Feather: Homophily in Social Networks. Annu Rev Sociol. 2001;27: 415–444. doi:10.1146/annurev.soc.27.1.415  ↩︎

Planted: by ;

L Ma (2021). 'Solving Problems on Graph', Datumorphism, 09 April. Available at: