  Traditional statistical learning theory relies on the assumption that data
are identically and independently distributed (i.i.d.). However, this
assumption often does not hold in many real-life applications. In this survey,
we explore learning scenarios where examples are dependent and their dependence
relationship is described by a dependency graph, a commonly utilized model in
probability and combinatorics. We collect various graph-dependent concentration
bounds, which are then used to derive Rademacher complexity and stability
generalization bounds for learning from graph-dependent data. We illustrate
this paradigm through practical learning tasks and provide some research
directions for future work. To our knowledge, this survey is the first of this
kind on this subject.
