Solving Problems on Graph

#Graph #Basics

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

Node Classification

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.

[[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 ↩︎ ³,
Homophily
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 ↩︎
[[Structural equivalence]] Structural Equivalence on Graph Structural Equivalence means that nodes with similar neighborhood structures will share similar attributes. ,
Structural equivalence
Structural 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.
Heterophily
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.

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.

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

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.

Planted: 2021-09-25 by L Ma;

References: