Graph Edge Prediction Task

A Graph Edge Prediction Task a multiclass classification task that requires the class prediction of a graph edge for one graph node (to another graph node).

• AKA: Link Prediction, Network Edge Prediction.
• Context:
  • It can be solved by a Link Prediction System (that can implement a link prediction algorithm).
  • It can range from being a Supervised Link Prediction Task (with labeled link training records) to being an Unsupervised Link Prediction Task.
  • It can range from being a Directed Graph Link Prediction Task to being Undirected Graph Link Prediction Task.
  • It can range from being a Structural Link Prediction Task (with partially observed graphs) to being a Temporal Link Prediction Task (with fully observed graphs).
• Example(s):
  • a Social Network Link Prediction Task, such as a friend recommendation task.
  • a Concept Mention Link Prediction Task.
  • a Protein Interaction Prediction Task.
  • …
• Counter-Example(s):
  • a Graph Analysis Task.
• See: Link-based Object Classification Task.

---

---

References

2011

• (Menon & Elkan, 2011) ⇒ Aditya Krishna Menon, and Charles Elkan. (2011). “Link Prediction via Matrix Factorization.” In: Proceedings of the 2011 European conference on Machine learning and knowledge discovery in databases - Volume Part II. ISBN:978-3-642-23782-9
  • QUOTE: Link prediction is the problem of predicting the presence or absence of edges between nodes of a graph. There are two types of link prediction: (i) structural, where the input is a partially observed graph, and we wish to predict the status of edges for unobserved pairs of nodes, and (ii) temporal, where we have a sequence of fully observed graphs at various time steps as input, and our goal is to predict the graph state at the next time step. Both problems have important practical applications, such as predicting interactions between pairs of proteins and recommending friends in social networks respectively.

• (Lü & Zhou, 2011) ⇒ Linyuan Lü, and Tao Zhou. (2011). “Link Prediction in Complex Networks: A Survey.” In: Physica A: Statistical Mechanics and its Applications, 390(6).
  • QUOTE: Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. … We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labeled networks.

• (Namata & Getoor, 2011) ⇒ Galileo Namata; Lise Getoor. (2011). “Link Prediction.” In: (Sammut & Webb, 2011) p.609

2006

• (Al Hasan et al., 2006) ⇒ Mohammad Al Hasan, Vineet Chaoji, Saeed Salem, and Mohammed Zaki. (2006). “Link Prediction Using Supervised Learning.” In: SDM’06: Workshop on Link Analysis, Counter-terrorism and Security.
  • Link prediction in a social network is an important problem and it is very helpful in analyzing and understanding social groups.

2003

• (Taskar et al., 2003) ⇒ Ben Taskar, Ming-Fai Wong, Pieter Abbeel and Daphne Koller. (2003). “Link Prediction in Relational Data.” In: Neural Information Processing Systems Conference (NIPS 2003)
  • QUOTE: This paper focuses on predicting the existence and the type of links between entities in such domains.
• (Liben-Nowell & Kleinberg) ⇒ David Liben-Nowell, and Jon Kleinberg. (2003). “The Link Prediction Problem for Social Networks.” In: Proceedings of the twelfth International Conference on Information and knowledge management (CIKM 2003). doi:10.1145/956863.956972
• (Popescul & Ungar, 2003) ⇒ Alexandrin Popescul, and Lyle H. Ungar. (2003). “Statistical Relational Learning for Link Prediction.” In: Proceedings of IJCAI Workshop on Learning Statistical Models from Relational Data.
  • QUOTE: Link prediction is a complex, inherently relational, task. Be it in the domain of scientific citations, social networks or hypertext links, the underlying data are extremely noisy and the characteristics useful for prediction are not readily available in a “flat” file format, but rather involve complex relationships among objects.

2002

• (Krebs. 2002) ⇒ V. E. Krebs. (2002). “Mapping Networks of Terrorist Cells.” In: Connections, 24(3).

2000

• (Sarukkai, 2000) ⇒ Ramesh R. Sarukkai. (2000). “Link Prediction and Path Analysis Using Markov Chains.” doi:10.1016/S1389-1286(00)00044-X

1997

• (Kautz et al., 1997) ⇒ H. Kautz, B. Selman, and M. Shah. (1997). “Referral Web: Combining social networks and collaborative filtering.” In: Communications of the ACM, 40(3).

---