Dynamic pattern recognition in large-scale graphs with applications to social networks

A graph is a versatile data structure facilitating representation of interactions among objects in various complex systems. Very often these objects have attributes whose measurements change over time, reflecting the dynamics of the system. This general data framework can be used in many fields to represent complex data structures: brain networks and neuronal spikes, web networks and clickstreams, social networks and activity of the users, among others. In all of these examples, the structural and dynamic components of the data are inseparable, which significantly complicates the detection, analysis, and interpretation of patterns that emerge in the networks. The increasing size and complexity of graph-structured data require scalable and interpretable algorithms for dynamic pattern detection in such systems.

In this dissertation, we present an unsupervised approach for dynamic pattern detection in large-scale graphs. In this approach, we combine intuitions derived from attention mechanisms, Hopfield networks, and memory networks to build scalable, efficient, and interpretable algorithms. We then demonstrate multiple applications of this approach in recommendation systems, information recovery algorithms, and collective behavior studies. Additionally, we use our algorithm to detect dynamic activity patterns in social and communication networks. We conduct extensive experiments on Wikipedia data, detecting and analyzing patterns in the viewership activity in its web network. To study the collective behavior of Wikipedia readers, we develop an automated pattern interpretation model, which allows for comparison of trending topics across multiple language editions of Wikipedia. The results of the experiments reveal provocative insights into how people interact and search for information in online social networking environments, opening new avenues for future research on collective behavior analysis at a large scale.

Finally, we present a distributed data processing framework for Wikipedia server logs that allows others to reproduce all pattern detection experiments presented in this thesis and to conduct similar collective behavior studies on the latest data.

Crowding and the importance of grouping and segmentation processes in human vision

Alban Bornet

Human vision has evolved to make sense of a world in which elements almost never appear in isolation. Surprisingly, the recognition of an element in a visual scene is strongly limited by the presence of other nearby elements, a phenomenon known as visual crowding. Crowding impacts vision at all levels and is thus a versatile tool to understand the fundamental mechanisms of vision. For decades, visual crowding was perfectly well explained by traditional feedforward models of vision. In these models, vision starts with the detection of low-level features. This information is combined locally along the hierarchy of the visual cortex to build more and more complex feature detectors, until neurons respond selectively and robustly to complex objects. Crowding happens when nearby elements interfere in this local feature combination process and impair target recognition. However, recent studies have shown that crowding is not determined by local interactions but by the global configuration across the entire visual field. Depending on how elements group together, crowding can even almost disappear, a phenomenon called uncrowding. Hence, crowding is rather a complex, global and high-level phenomenon, that simple feedforward models cannot explain. In this thesis, I first analyse which models of crowding can explain uncrowding. I compare the performance of diverse models, selected according to different architectural and functional features, such as feedforward vs. recurrent architecture, local or global information processing, including a grouping stage or not. I show that the only model that reproduces human behaviour includes a dedicated recurrent grouping processing stage. Second, I show that global effects in crowding cannot be explained by low-level accounts. It was argued that the Texture Tiling model, based on a complex and high-dimensional pooling stage, may account for global effects in crowding, without requiring any recurrent grouping stage. To test this model, I use a large pool of recent crowding data. I show that the Texture Tiling model is equivalent to a simple pooling model and is thus as limited as these models. Next, I focus on deep neural networks, which are well in the spirit of the feedforward framework of vision and have become state-of-the-art models both in computer vision and neuroscience. I test whether AlexNet and ResNet-50, which have been proposed as realistic models of the visual system, exhibit uncrowding. I show that these networks do not reproduce uncrowding for principled reasons. Finally, I use a genetic algorithm to generate stimuli based on the performance of different models, i.e., in a bottom-up manner. The goal is to avoid using stimuli that favour models of grouping from the start. I compare the distribution of stimuli that are produced by the models to the ones that are produced by humans. I show that only the models that include grouping and segmentations processes behave like humans. Taken together, the results in my thesis highlight the importance of recurrent grouping and segmentation processes in human vision when large portions of the visual field are involved. These results can be used as direct guidelines for future models of vision, in order to constraint how recurrent processing should be incorporated to improve the performance of deep neural networks and other feedforward models of vision, and help them generalize to more complex visual inputs.

EPFL2021

Sequential Topic Models for Mining Recurrent Activities and their Relationships

Jagannadan Varadarajan

In this thesis, we address the analysis of activities from long term data logs with an emphasis on video recordings. Starting from simple words from video, we progressively build methods to infer higher level scene semantics. The main strategies used to achieve this are: the use of simple low-level visual features that can be readily extracted, and of probabilistic topic models that come with powerful learning and inference tools. In the initial part of the thesis, we investigate the use of a simple topic model called Probabilistic Latent Semantic Analysis (PLSA) for video scene analysis. By quantizing location, optical flow direction and foreground blob size into words, and considering short video clips as documents, we discover topics from PLSA that represent recurrent activities in the scene. We then demonstrate how the topics can be used to analyze the scene activities, segment the scene into homogeneous activity regions and detect abnormalities. The topics from PLSA have no temporal structure and hence do not represent activities well. To address this issue, we develop a novel sequential topic model called Probabilistic Latent Sequential Motifs (PLSM) which automatically discovers sequential patterns called motifs that include temporal information from videos. To address the problem of observations caused by multiple activities in the scene, the PLSM formulation uses explicit random variables to represent time at different levels: at a higher level to determine when a motif starts in the video, and at a lower level to know the order of words within the motif. Using a sparsity constraint on the event start times, and MAP priors on the temporal axis of the motifs, we designed an inference algorithm. When applied to surveillance videos, the model captures motifs that resemble trajectories. The model provides more information than PLSA, giving clues about when and where an activity starts, when it ends and how it is executed. As in many unsupervised topic models, deciding the most appropriate number of topics is a difficult problem. To address this, we reformulate PLSM using principles of Bayesian non-parametrics. The new method called Hierarchical Dirichlet Latent Sequential Motifs (HDLSM) uses Dirichlet processes at multiple levels to select a suitable number of motifs and identify their occurrences in the data. The final objective is to analyze how events in a scene are organized. At a global level, a scene can be thought of as undergoing a sequence of phases, each with distinct characteristics. At a more local level, the individual activities can exhibit dependencies that are possibly causal in nature. Following this, we propose a new graphical model called Mixed Event Relationship (MER) model, that incorporates the learning of both local rules and global states simultaneously from a binary event matrix. Learning these scene semantics is achieved using an iterative Gibbs sampling procedure. While the global scene states recover traffic cycles, the local rules provide information about single and multi-object activity interactions. We validate the proposed methods with elaborate experiments on nine different challenging datasets with a wide variety of activity content. The results prove the general applicability of the different methods proposed in this thesis. We believe that they can have wider applications on data coming from sensor logs of other modalities too.

EPFL2012

Towards patient-tailored interventions for stroke recovery: graph theoretical approaches and modeling of non-invasive brain stimulation

Giorgia Giulia Evangelista

Stroke is a disease that causes the death of precious brain cells that will never grow back and which will affect one in four humans at some point in their life. While therapies and treatments for this debilitating condition are fairly standard, their outcomes are highly heterogeneous, with deficits all too often leading to permanent disability. These unsatisfactory outcomes point to the need for a paradigm shift towards precision medicine, where therapies and treatments are tailored to individual patients. This in turn requires a better understanding of the mechanisms underlying post-stroke impairment and recovery. Recent technological innovations provide an unprecedented opportunity to acquire a detailed picture of the anatomy and electrophysiology of the human brain non-invasively. Therefore, we apply multimodal methodologies to investigate the inner workings of the stroke-affected brain with a view to establishing biomarkers and creating stratifications that maximize the effectiveness of stroke therapy by making it personalized.In the first part of this thesis, network-theoretic models of the brain known as connectomes are created, under the assumption that these provide sufficiently detailed information about the individual patient to inform personalized recommendations. In particular, we leverage existing knowledge about how brain networks are organized into specialized modules connected by a "rich-club" of hubs. In a novel contribution to the field of connectomics, we combine these connectomes with detailed images of the lesion to obtain a network-theoretic lesion profile and a map of the non-lesioned part of the network, which we expect to be a better reflection of true brain connectivity. Using this methodology, we establish that the rich-club, in addition to being a source of network robustness, is also a source of vulnerability in that attacks against it lead to poor behavioral outcomes disproportionate to the size of the attacks.The creation of in-silico simulation of individual patients presents a great opportunity to quickly experiment with treatments, making it a potential game-changer in medical research. However, current technology is not able to faithfully capture the complexity of a whole human brain. The complex brain abnormalities inherent to stroke only add to the difficulty of the challenge. Any models one might wish to create must strike a balance between technological feasibility and sensitivity to inter-patient variability across a large parameter space. In the second part of this thesis, we investigate whether one major source of inter-patient variability, namely the size and location of the lesion, induces substantial variability in the effects of non-invasive brain stimulation to be included as factors in the design of stimulation protocols. Based on our modeling of the stimulation, personalizing stimulation protocols by taking the lesion into account produces little added value, except possibly when one is targeting brain areas close to the lesion and the lesion is significantly large.The proposed studies represent a step of the march towards precision medicine, by examining sources of variability in stroke patients and by associating them with variability in some outcomes of interest. Each step of this march brings stroke therapy farther from the status quo of homogeneous treatments and heterogeneous outcomes and closer to the ideal of heterogeneous treatments and homogeneously positive outcomes.

EPFL2022