Data-Driven Graph Node-Directed Classification Algorithm

A Data-Driven Graph Node-Directed Classification Algorithm is a Link Prediction Algorithm that is a Data-Driven Multiclass Classification Algorithm.

• AKA: Data-Driven Link Prediction Algorithm.
• Context:
  • It can be applied by a Data-Driven Link Prediction System (that can solve a Data-Driven Link Prediction Task).
  • It can range from being a Supervised Data-Driven Link Prediction Algorithm to being an Unsupervised Data-Driven Link Prediction Algorithm.
  • …
• Counter-Example(s):
  • a Heuristic Data-Driven Link Prediction Algorithm.
• See: Node-Pair Distance Metric.

---

---

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: At a high level, existing link prediction models fall into two classes: unsupervised and supervised. Unsupervised models compute scores for pairs of nodes based on topological properties of the graph. For example, one such score is the number of common neighbours that two nodes share. Other popular scores are the Adamic-Adar [1] and Katz score [22]. These models use predefined scores that are invariant to the specific structure of the input graph, and thus do not involve any learning. Supervised models, on the other hand, attempt to be directly predictive of link behaviour by learning a parameter vector θ via … The choice of these terms depends on the type of model.
    We list some popular approaches:
    1. Feature-based models. Suppose each node [math]\displaystyle{ i }[/math] in the graph has an associated feature vector [math]\displaystyle{ x_i \in \mathbb{R}^d }[/math]. Suppose further that each dyad (i, j) has a feature vector ...
    2. Graph regularization models. Here, we assume the existence of node features [math]\displaystyle{ x_i }[/math] ∈ Rd, based on which we construct a kernel Kiit jjt that compares the node pairs (i, j) and (it, jt). We ...
    3. Latent class models. These models assign each node of the graph to a class, and use the classes to predict the link structure. [4] assumes that nodes interact solely through their class …
    4. Latent feature models. Here, we treat link prediction as a matrix completion problem, and factorize G ≈ L(UΛUT ) for some U ∈ Rn×k , Λ ∈ Rk×k and link function L(•). Each node i thus has …

2010

• (Lichtenwalter et al., 2010) ⇒ Ryan N. Lichtenwalter, Jake T. Lussier, and Nitesh V. Chawla. (2010). “New Perspectives and Methods in Link Prediction.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010).

---