Graph Mining Algorithm

A graph mining algorithm is a relational mining algorithm that can be implemented by a graph mining system to solve a graph mining task.

• AKA: Network Analysis Algorithm.
• Context:
  • It can range from being a Directed Graph Mining Algorithm to being an Undirected Graph Mining Algorithm.
  • …
• Example(s):
  • a Graph Classification Algorithm.
  • a Graph Component Classification Algorithm, such as a Node Classification Algorithm, or an Edge Classification Algorithm.
  • a Graph Regression Algorithm, such as a Node Value Regression Algorithm or an Edge Value Regression Algorithm.
  • a Graph Clustering Algorithm, such as a Graph Node Clustering Algorithm or a Graph Edge Clustering Algorithm.
  • a Graph Node Ranking Algorithm.
  • …
• Counter-Example(s):
  • a Tuple Classification Algorithm.
  • a Tuple Association Learning Algorithm.
  • a Tuple Clustering Algorithm.
  • a Graph Design Task.
• See: Social Network Analysis, Protein-Protein Interaction Analysis, Inductive Database Graph Mining Algorithm.

---

---

References

2012

• (Merrill et al., 2012) ⇒ Duane Merrill, Michael Garland, and Andrew Grimshaw. (2012). “Scalable GPU Graph Traversal.” In: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming. ISBN:978-1-4503-1160-1 doi:10.1145/2370036.2145832
  • QUOTE: Breadth-first search (BFS) is a core primitive for graph traversal and a basis for many higher-level graph analysis algorithms. It is also representative of a class of parallel computations whose memory accesses and work distribution are both irregular and data-dependent. Recent work has demonstrated the plausibility of GPU sparse graph traversal, but has tended to focus on asymptotically inefficient algorithms that perform poorly on graphs with non-trivial diameter.

2005

• (Getoor & Diehl, 2005) ⇒ Lise Getoor, and Christopher P. Diehl. (2005). “Link Mining: A survey.” In: [[SIGKDD Explorations], 7(2).

1995

• (Blum & Furst, 1995) ⇒ Avrim L. Blum, and Merrick L. Furst. (1995). “Fast Planning Through Planning Graph Analysis.” In: Proceedings of the 14th International Joint Conference on AI (IJCAI 1995). doi:10.1016/S0004-3702(96)00047-1
  • Planning Graph.

---