Graph Based Multimedia Analysis applies concepts from graph theory to the problems of analyzing overabundant video data. Video data can be quite diverse: exocentric (captured by a standard camera) or egocentric (captured by a wearable device like Google Glass); of various durations (ranging from a few seconds to several hours); and could be from a single source or multiple sources. Efficient extraction of important information from such a large class of diverse video data can be overwhelming. The book, with its rich repertoire of theoretically elegant solutions, from graph theory in conjunction with deep learning, constrained optimization, and game theory, empowers the audience to achieve tasks like obtaining concise yet useful summaries and precisely recognizing single as well as multiple actions in a computationally efficient manner. The book provides a unique treatise on topics like egocentric video analysis and scalable video processing.