# 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 graphs^{1}^{2}.

## Node Classification

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.

- [[Homophily]]
Homophily on Graph
Homophily is the principle that a contact between similar people occurs at ahigher rate than among dissimilar people – McPherson20011
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 ↩︎
^{3},HomophilyHomophily is the principle that a contact between similar people occurs at ahigher rate than among dissimilar people – McPherson20011 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 ↩︎ - [[Structural equivalence]]
Structural Equivalence on Graph
Structural Equivalence means that nodes with similar neighborhood structures will share similar attributes.
,
Structural equivalenceStructural Equivalence means that nodes with similar neighborhood structures will share similar attributes.
- [[Heterophily]]
Heterophily on Graph
Heterophily is the tendency to differ from others. Heterophily on a graph is the tendency to connect to nodes that are different from itself, e.g., nodes with different attributes have higher probability of edge.
HeterophilyHeterophily is the tendency to differ from others. Heterophily on a graph is the tendency to connect to nodes that are different from itself, e.g., nodes with different attributes have higher probability of edge.

## Relation Prediction

Also named as link prediction, graph completion.

## Clustering and Community Detection

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.

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

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 ↩︎

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 ↩︎

- Hamilton2020 Hamilton WL. Graph Representation Learning. Morgan & Claypool Publishers; 2020. pp. 1–159. doi:10.2200/S01045ED1V01Y202009AIM046
- 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
- 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

`wiki/graph/basics/ml-problems-on-graph`

Links to:L Ma (2021). 'Solving Problems on Graph', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/wiki/graph/basics/ml-problems-on-graph/.