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. - Addresses a number of challenging state-of-the-art problems in multimedia analysis like summarization, co-summarization, and action recognition - Handles a wide class of video with different genres, durations, and numbers - Applies a class of theoretically rich algorithms from the discipline of graph theory, in conjunction with deep learning, constrained optimization and game theory - Includes thorough complexity analyses of the proposed solutions, and an appendix containing implementable source codes