### Research interests

• Machine Learning
• Data Mining
• Graph Machine Learning
• Network Analysis
• Complex Systems

### Focus on problems

• Data clustering and cluster analysis
• Learning methods for high-dimensional data
• Representation and clustering of text documents
• Multimedia data semantics (text, image, video)
• Online learning on data streams
• Diffusion processes and control in networks
• Graph signals

### Publications

#### – Journals

• Learning Laplacian Matrix from Graph Signals with Sparse Spectral Representation. P. Humbert, B. Le Bars, L. Oudre, A. Kalogeratos, and N. Vayatis, Journal of Machine Learning Research (JMLR), 2021. [pdf][bib][code] Abstract
In this paper, we consider the problem of learning a graph structure from multivariate signals, known as graph signals. Such signals are multivariate observations carrying measurements corresponding to the nodes of an unknown graph, which we desire to infer. They are assumed to enjoy a sparse representation in the graph spectral domain, a feature which is known to carry information related to the cluster structure of a graph. The signals are also assumed to behave smoothly with respect to the underlying graph structure. For the graph learning problem, we propose a new optimization program to learn the Laplacian of this graph and provide two algorithms to solve it, called IGL-3SR and FGL-3SR. Based on a 3-steps alternating procedure, both algorithms rely on standard minimization methods – such as manifold gradient descent or linear programming – and have lower complexity compared to state-of-the-art algorithms. While IGL-3SR ensures convergence, FGL-3SR acts as a relaxation and is significantly faster since its alternating process relies on multiple closed-form solutions. Both algorithms are evaluated on synthetic and real data. They are shown to perform as good or better than their competitors in terms of both numerical performance and scalability. Finally, we present a probabilistic interpretation of the optimization program as a Factor Analysis Model. Keywords: Graph learning, graph Laplacian, non-convex optimization, graph signal processing, sparse coding, clustering.
• Revealing posturographic profile of patients with Parkinsonian syndromes through a novel hypothesis testing framework based on machine learning. I. Bargiotas, A. Kalogeratos, M. Limnios, P.–P. Vidal, D. Ricard, and N. Vayatis, PLoS ONE, 2021. [pdf] Abstract
Falling in Parkinsonian syndromes (PS) is associated with postural instability and consists a common cause of disability among PS patients. Current posturographic practices record the body’s center-of-pressure displacement (statokinesigram) while the patient stands on a force platform. Statokinesigrams, after appropriate signal processing, can offer numerous posturographic features, which however challenges the efforts for valid statistics via standard univariate approaches. In this work, we present the ts-AUC, a non-parametric multivariate two-sample test, which we employ to analyze statokinesigram differences among PS patients that are fallers (PSF) and non-fallers (PSNF). We included 123 PS patients who were classified into PSFor PSNFbased on clinical assessment and under-went simple Romberg Test (eyes open/eyes closed). We analyzed posturographic features using both multiple testing with p-value adjustment and the ts-AUC. While the ts-AUCshowed significant difference between groups (p-value = 0.01), multiple testing did not show any such difference. Interestingly, significant difference between the two groups was found only using the open-eyes protocol. PSF showed significantly increased antero-posterior movements as well as increased posturographic area, compared to PSNF. Our study demonstrates the superiority of the ts-AUC test compared to standard statistical tools in distinguishing PSF and PSNF in the multidimensional feature space. This result highlights more generally the fact that machine learning-based statistical tests can be seen as a natural extension of classical statistical approaches and should be considered,especially when dealing with multifactorial assessments.
• Suppressing Epidemics in Networks using Priority-Planning, K. Scaman, A. Kalogeratos, N. Vayatis, IEEE Transactions on Network Science and Engineering, vol. 3, no. 4, pp. 271-285, 2016. [pdf][bib] – Prior, 2014 arxiv version [arXiv link]. Abstract
In this paper, we analyze a large class of dynamic resource allocation (DRA) strategies, named priority planning, that aim to suppress SIS epidemics taking place in a network. This is performed by distributing treatments of limited efficiency to its infected nodes, according to a priority-order precomputed offline. Under this perspective, an efficient DRA strategy for a given network can be designed by learning a proper linear arrangement of its nodes. In our theoretical analysis, we derive upper and lower bounds for the extinction time of the diffusion process that reveal the role of the maxcut of the considered linear arrangement. Accordingly, we highlight that the cutwidth, which is the minimum maxcut of all possible linear arrangements for a network, is a fundamental network property that determines the resource budget required to suppress the epidemic under priority planning. Finally, by making direct use of our theoretical results, we propose a novel and efficient DRA strategy, called maxcut minimization (MCM), which outperforms other competing strategies in our simulations, while offering desirable robustness under various noise profiles.
• Text Document Clustering Using Global Term Context Vectors, A. Kalogeratos and A. Likas, Knowledge and Information Systems (KAIS), vol. 31, no. 3, pp. 455–474, 2012. [pdf][recompiled pdf][bib]. Abstract
Despite the advantages of the traditional vector space model (VSM) representation, there are known deficiencies concerning the term independence assumption. The high dimensionality and sparsity of the text feature space and phenomena such as polysemy and synonymy can only be handled if a way is provided to measure term similarity. Many approaches have been proposed that map document vectors onto a new feature space where learning algorithms can achieve better solutions. This paper presents the global term context vector-VSM (GTCV-VSM) method for text document representation. It is an extension to VSM that: (i) it captures local contextual information for each term occurrence in the term sequences of documents; (ii) the local contexts for the occurrences of a term are combined to define the global context of that term; (iii) using the global context of all terms a proper semantic matrix is constructed; (iv) this matrix is further used to linearly map traditional VSM (Bag of Words—BOW) document vectors onto a ‘semantically smoothed’ feature space where problems such as text document clustering can be solved more efficiently. We present an experimental study demonstrating the improvement of clustering results when the proposed GTCV-VSM representation is used compared with traditional VSM-based approaches.
• Document clustering using synthetic cluster prototypes, A. Kalogeratos and A. Likas, Data and Knowledge Engineering, vol.70, no. 3, pp. 284–306, 2011. [pdf][recompiled pdf][bib]. Abstract
The use of centroids as prototypes for clustering text documents with the k-means family of methods is not always the best choice for representing text clusters due to the high dimensionality, sparsity, and low quality of text data. Especially for the cases where we seek clusters with small number of objects, the use of centroids may lead to poor solutions near the bad initial conditions. To overcome this problem, we propose the idea of synthetic cluster prototype that is computed by first selecting a subset of cluster objects (instances), then computing the representative of these objects and finally selecting important features. In this spirit, we introduce the MedoidKNN synthetic prototype that favors the representation of the dominant class in a cluster. These synthetic cluster prototypes are incorporated into the generic spherical k-means procedure leading to a robust clustering method called k-synthetic prototypes (k-sp). Comparative experimental evaluation demonstrates the robustness of the approach especially for small datasets and clusters overlapping in many dimensions and its superior performance against traditional and subspace clustering methods.

#### – Conferences

• To tree or not to tree? Assessing the impact of smoothing the decision boundaries. A. Merida, A. Kalogeratos, and M. Mougeot, 31st International Conference on Artificial Neural Networks (ICANN 2022). [pdf] Abstract
When analyzing a dataset, it can be useful to assess how smooth the decision boundaries need to be for a model to better fit the data. This paper addresses this question by proposing the quantification of how much should the ‘rigid’ decision boundaries, produced by an algorithm that naturally finds such solutions, be relaxed to obtain a performance improvement. The approach we propose starts with the rigid decision boundaries of a seed Decision Tree (seed DT), which is used to initialize a Neural DT (NDT). The initial boundaries are challenged by relaxing them progressively through training the NDT. During this process, we measure the NDT’s performance and decision agreement to its seed DT. We show how these two measures can help the user in figuring out how expressive his model should be, before exploring it further via model selection. The validity of our approach is demonstrated with experiments on simulated and benchmark datasets.
• Offline detection of change-points in the mean for stationary graph signals. A. de la Concha, N. Vayatis, and A. Kalogeratos, 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021). [pdf][appendix][code][poster] Abstract
This paper addresses the problem of segmenting a stream of graph signals: we aim to detect changes in the mean of the multivariate signal defined over the nodes of a known graph. We propose an offline algorithm that relies on the concept of graph signal stationarity and allows the convenient translation of the problem from the original vertex domain to the spectral domain (Graph Fourier Transform), where it is much easier to solve. Although the obtained spectral representation is sparse in real applications, to the best of our knowledge this property has not been much exploited in the existing related literature. Our main contribution is a change-point detection algorithm that adopts a model selection perspective, which takes into account the sparsity of the spectral representation and determines automatically the number of change-points. Our detector comes with a proof of a non-asymptotic oracle inequality, numerical experiments demonstrate the validity of our method.
• Multivariate two-sample hypothesis testing through AUC maximization for biomedical applications. I. Bargiotas, A. Kalogeratos, M. Limnios, P.-P. Vidal, D. Ricard, N. Vayatis, SETN 2020: 11th Hellenic Conference on Artificial Intelligence, pp. 56–59, Sep. 2020. [pdf, appendix] Abstract
Clinical datasets usually carry numerous features (biomarkers, characteristics, etc.) concerning the examined populations. This fact, although beneficial, challenges the statistical analysis via standard univariate approaches. In the two-sample setting, the majority of the clinical studies evaluate their assumptions relying on a variety of available univariate tests, such as the Student’s t-test or Mann-Whitney Wilcoxon. We developed an easy-to-use-and-interpret non-parametric two-sample hypothesis testing framework (ts-AUC) particularly using machine learning and the AUC maximization criterion. We test and verify the effectiveness of ts-AUC in real data containing posturographic features of Parkinsonian patients (PS) with and without history of falling.
• Learning the piece-wise constant graph structure of a varying Ising model. B. Le Bars, P. Humbert, A. Kalogeratos, and N. Vayatis, International Conference on Machine Learning 2020. [pdf] Abstract
This work focuses on the estimation of multiple change-points in a time-varying Ising model that evolves piece-wise constantly. The aim is to identify both the moments at which significant changes occur in the Ising model, as well as the underlying graph structures. For this purpose, we propose to estimate the neighborhood of each node by maximizing a penalized version of its conditional log-likelihood. The objective of the penalization is twofold: it imposes sparsity in the learned graphs and, thanks to a fused-type penalty, it also enforces them to evolve piece-wise constantly. Using few assumptions, we provide two change-points consistency theorems. Those are the first in the context of unknown number of change-points detection in time-varying Isingmodel. Finally, experimental results on several synthetic datasets and a real-world dataset demonstrate the performance of our method.
• Optimal Multiple Stopping Rule for Warm-Starting Sequential Selection, M. Fekom, N. Vayatis, and A. Kalogeratos, IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2019. [pdf][arxiv link] Abstract
This work focuses on the estimation of change-points in a time-varying Ising graphical model (outputs −1 or 1) evolving in a piecewise constant fashion. The occurring changes alter the graphical structure of the model, a structure which we also estimate in the present paper. For this purpose, we propose a new optimization program consisting in the minimization of a penalized negative conditional log-likelihood. The objective of the penalization is twofold: it imposes the learned graphs to be sparse and, thanks to a fused-type penalty, it enforces them to evolve piecewise constantly. Using few assumptions, we then give a change-point consistency theorem. Up to our knowledge, we are the first to present such theoretical result in the context of time-varying Ising model. Finally, experimental results on several synthetic examples and a real-world dataset demonstrate the empirical performance of our method.
• Sequential Dynamic Resource Allocation for Epidemic Control, M. Fekom, N. Vayatis, and A. Kalogeratos, IEEE Conference on Decision and Control 2019 (CDC), 2019. [pdf][arxiv link] Abstract
TUnder the Dynamic Resource Allocation (DRA) model, an administrator has the mission to allocate dynamically a limited budget of resources to the nodes of a network in order to reduce a diffusion process (DP) (e.g. an epidemic). The standard DRA assumes that the administrator has constantly full information and instantaneous access to the entire network. Towards bringing such strategies closer to real-life constraints, we first present the Restricted DRA model extension where, at each intervention round, the access is restricted to only a fraction of the network nodes, called sample. Then, inspired by sequential selection problems such as the well-known Secretary Problem, we propose the Sequential DRA (SDRA) model. Our model introduces a sequential aspect in the decision process over the sample of each round, offering a completely new perspective to the dynamic DP control. Finally, we incorporate several sequential selection algorithms to SDRA control strategies and compare their performance in SIS epidemic simulations.
• Learning Laplacian Matrix from Bandlimited Graph Signals, B. Le Bars, P. Humbert, L. Oudre, and A. Kalogeratos, IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP). [pdf] Abstract
In this paper, we present a method for learning an underlying graph topology using observed graph signals as training data. The novelty of our method lies on the combination of two assumptions that are imposed as constraints to the graph learning process: i) the standard assumption used in the literature that signals are smooth with respect to graph structure (i.e. small signal variation at adjacent nodes), with ii) the additional assumption that signals are bandlimited, which implies sparsity in the signals’ representation in the spectral domain. The latter assumption affects the inference of the whole eigenvalue decomposition of the Laplacian matrix and leads to a challenging new optimization problem. The conducted experimental evaluation shows that the proposed algorithm to solve this problem outperforms a reference state-of-the-art method that is based only on the smoothness assumption, when compared in the graph learning task on synthetic and real graph signals.
• A Probabilistic Framework to Node-level Anomaly Detection in Communication Networks, B. Le Bars and A. Kalogeratos, IEEE International Conference on Computer Communications 2019 (INFOCOM), 29 Apr – 2 May 2019, Paris, France. [pdf][bib] Abstract

In this paper we consider the task of detecting abnormal communication volume occurring at node-level in communication networks. The signal of the communication activity is modeled by means of a clique stream: each occurring communication event is instantaneous, and activates an undirected subgraph spanning over a set of equally participating nodes. We present a probabilistic framework to model and assess the communication volume observed at any single node. Specifically, we employ non-parametric regression to learn the probability that a node takes part in a certain event knowing the set of other nodes that are involved. On the top of that, we present a concentration inequality around the estimated volume of events in which a node could participate, which in turn allows us to build an efficient and interpretable anomaly scoring function. Finally, the superior performance of the proposed approach is empirically demonstrated in real-world sensor network data, as well as using synthetic communication activity that is in accordance with that latter setting.

• Multivariate Hawkes Processes for Large-scale Inference, R. Lemonnier, K. Scaman, A. Kalogeratos, 31st AAAI Conference on Artificial Intelligence (AAAI-17). [pdf][supplementary][poster] – Prior arxiv version [arXiv link]. Abstract

In this paper, we present a framework for fitting multivariate Hawkes processes for large-scale problems both in the number of events in the observed history n and the number of event types d (i.e. dimensions). The proposed Low-Rank Hawkes Process (SLRHP) framework introduces a low-rank approximation of the kernel matrix that allows to perform the nonparametric learning of the d^2 triggering kernels using at most O(ndr^2) operations, where r is the rank of the approximation (r << d, n). This comes as a major improvement to the existing state-of-the-art inference algorithms that are in O(nd^2). Furthermore, the low-rank approximation allows SLRHP to learn representative patterns of interaction between event types, which is usually for the analysis of complex processes in real-world networks.

• Improving Text Stream Clustering using Term Burstiness and Co-burstiness, A. Kalogeratos, P. Zagorisios, and A. Likas, Hellenic Conference of Artificial Intelligence (SETN), 2016. [pdf][recompiled][notes][slides][bib]. Abstract

In text streams, documents appear over time and their timestamps can be used to improve typical approaches for text representation and clustering. A way to exploit temporal information is through the detection of bursty terms in such streams, i.e. terms that appear in many documents during short time period. Research efforts so far have shown that utilizing the burst information in the text representation can improve the performance of text clustering algorithms. However, most attempts take into account the bursty terms individually, without investigating the relation between them.

In this work, we take advantage of the fact that most of the important documents of a topic are published during the period in which the main’ topic terms are bursty. Therefore, we focus on both term burstiness and co-burstiness by determining groups of terms that are simultaneously bursty at a time period and also co-occurring in the same documents. Next, the documents that contain co-bursty terms from those groups, are considered as important for the respective topics and are used to construct robust synthetic prototypes following an agglomerative process. These prototypes are finally used to initialize in a deterministic fashion the spherical k-means clustering algorithm. Experimental results validate empirically the quality of the solutions provided by the proposed approach which seems to efficiently overcome the initialization problem of spherical k-means.

• A Greedy Approach for Dynamic Control of Diffusion Processes in Networks, K. Scaman, A. Kalogeratos, and N. Vayatis, IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 652-659, 2015. [pdf][suppl. material][bib] .::||::. [code]. Abstract

This paper investigates the control of a diffusion process by utilizing real-time information. More specifically, we allow the network administrator to adjust the allocation of control resources, a set of treatments that increase the recovery rate of infected nodes, according to the evolution of the diffusion process. We first present a novel framework for describing a large class of dynamic control strategies. These strategies rely on sorting the nodes according to a priority score in order to treat more sensitive regions first. Then, we propose the Largest Reduction in Infectious Edges (LRIE) control strategy which is based on a greedy minimization of the cost associated to the undesired diffusion, and has the benefits of being efficient and easy to implement. Our simulations, which were conducted using a software package that we developed and made available to the community, show that the LRIE strategy substantially outperforms its competitors in a wide range of scenarios.

• Dip-means: an incremental clustering method for estimating the number of clusters, A. Kalogeratos and A. Likas, Proceedings of the 26th Annual Conference on Neural Information Processing Systems (NIPS), 2012. [pdf][poster][bib] .::||::. [software]. Abstract
Learning the number of clusters is a key problem in data clustering. We present dip-means, a novel robust incremental method to learn the number of data clusters that can be used as a wrapper around any iterative clustering algorithm of k-means family. In contrast to many popular methods which make assumptions about the underlying cluster distributions, dip-means only assumes a fundamental cluster property: each cluster to admit a unimodal distribution. The proposed algorithm considers each cluster member as an individual ‘viewer’ and applies a univariate statistic hypothesis test for unimodality (dip-test) on the distribution of distances between the viewer and the cluster members. Important advantages are: i) the unimodality test is applied on univariate distance vectors, ii) it can be directly applied with kernel-based methods, since only the pairwise distances are involved in the computations. Experimental results on artificial and real datasets indicate the effectiveness of our method and its superiority over analogous approaches.
• Movie Segmentation into Scenes and Chapters Using Locally Weighted Bag of Visual Words, V. Chasanis, A. Kalogeratos, and A. Likas, Proceedings of the ACM International Conference on Image and Video Retrieval (CIVR), pp. 8–10, 2009. [pdf][bib]. Abstract

Movies segmentation into semantically correlated units is a quite tedious task due to ”semantic gap”. Low-level features do not provide useful information about the semantical correlation between shots and usually fail to detect scenes with constantly dynamic content. In the method we propose herein, local invariant descriptors are used to represent the key-frames of video shots and a visual vocabulary is created from these descriptors resulting to a visual words histogram representation (bag of visual words) for each shot. A key aspect of our method is that, based on an idea from text segmentation, the histograms of visual words corresponding to each shot are further smoothed temporally by taking into account the histograms of neighboring shots. In this way, valuable contextual information is preserved. The final scene and chapter boundaries are determined at the local maxima of the difference of successive smoothed histograms for low and high values of the smoothing parameter respectively. Numerical experiments indicate that our method provides high detection rates while preserving a good tradeoff between recall and precision.

• A Significance-Based Graph Model for Clustering Web Documents, A. Kalogeratos and A. Likas, Hellenic Conference of Artificial Intelligence (SETN), LNAI 3955, pp. 516–519, Springer-Verlag, 2006. [pdf][extended pdf][bib]. Abstract

Traditional document clustering techniques rely on single-term analysis, such as the widely used Vector Space Model. However, recent approaches have emerged that are based on Graph Models and provide a more detailed description of document properties. In this work we present a novel Significance-based Graph Model for Web documents that introduces a sophisticated graph weighting method, based on significance evaluation of graph elements. We also define an associated similarity measure based on the maximum common subgraph between the graphs of the corresponding web documents. Experimental results on artificial and real document collections using well-known clustering algorithms indicate the effectiveness of the proposed approach.

#### – Book chapters

• Information Diffusion and Rumor Spreading, A. Kalogeratos, K. Scaman, L. Corinzia, and N. Vayatis, chapter in the book Cooperative and Graph Signal Processing – Principles and Applications, eds. P.M. Djuric and C. Richard, Elsevier, 2018. [pdf][publisher’s link][bib] Abstract
This chapter studies information cascades on social networks with a special focus on types of diffusion processes such as rumors and false news. The complex temporal dynamics of information cascades and rapid changes in user interests require flexible mathematical modeling to properly describe the diffusion dynamics. After mentioning the modeling advancements of recent decades, we get to modern models, such as the Information Cascade Model (ICM), that are indeed capable of describing such time-dependent user interests and are thus particularly suited to the analysis of information diffusion. We provide a theoretical analysis of ICM, relating the dynamics of the cascade to structural characteristics of the social network, and then use that analysis to design control policies capable of efficiently reducing the undesired diffusion. The presented framework for activity shaping is generic while enjoying a simple convex relaxation. Finally, we present an algorithm for the control of Continuous-Time Independent Cascades which is evaluated and compared against baseline and state-of-the art approaches through diffusion simulations on real and synthetic social networks.
• Algorithmes efficaces pour contenir des processus de contagion sur des réseaux, A. Kalogeratos and K. Scaman, Book: Big Data et politiques publiques dans les transports, , Economica, 2017. [book]
• Mining Clinical Data, A. Kalogeratos, V. Chasanis, G. Rakocevic, A. Likas, Z. Babovic, M. Novakovic, Book: Computational Medicine in Data Mining and Modeling, Eds. G. Rakocevic et al., pp. 1-34, 2013. [link][pdf][bib]

Note: Additional recompiled pdf versions of the papers are provided above in some cases, with the material as published after correcting very few minor typos.

#### – Working papers – Preprints

• Online Centralized Non-parametric Change-point Detection via Graph-based Likelihood-ratio Estimation, A. de la Concha, A. Kalogeratos, and N. Vayatis, arxiv preprint, 2023 [pdf].Abstract
Consider each node of a graph to be generating a data stream that is synchronized and observed at near real-time. At a change-point τ, a change occurs at a subset of nodes C, which affects the probability distribution of their associated node streams. In this paper, we propose a novel kernel-based method to both detect τ and localize C, based on the direct estimation of the likelihood-ratio between the post-change and the pre-change distributions of the node streams. Our main working hypothesis is the smoothness of the likelihood-ratio estimates over the graph, i.e. connected nodes are expected to have similar likelihood-ratios. The quality of the proposed method is demonstrated on extensive experiments on synthetic scenarios.
• DeGroot-based opinion formation under a global steering mechanism, I. Conjeaud, P. Lorenz-Spreen, and A. Kalogeratos, arxiv preprint, 2022 [pdf].  Abstract
In this paper we investigate how interacting agents arrive to a consensus or a polarized state. More specifically, we study the opinion formation process under the effect of a global steering mechanism (GSM). We consider that the GSM aggregates agents’ opinions at the network level and feeds back to them a form of global information. We propose the GSM-DeGroot model, a new two-layer agent-based opinion formation model that captures the coupled dynamics between agent-to-agent local interactions and the GSM’s steering effect. This way, agents are subject to the effects of a DeGroot-like local opinion propagation, as well as to a wide variety of possible aggregated information that can affect their opinions, such as trending news feeds, press coverage, polls, elections, etc. The cornerstone feature of our model that, contrary to the standard DeGroot model, allows polarization to emerge, is the differential way in which agents react to the global information. We explore numerically the model dynamics to find regimes of qualitatively different behavior, using simulations on synthetic data. Moreover, we challenge our model by fitting it to the dynamics of real topics, related to protests, social movements, and the escalation of a long geopolitical conflict to a war, which attracted the public attention and were recorded on Twitter. Our experiments show that the proposed model holds explanatory power, as it evidently captures real opinion formation dynamics via a relatively small set of interpretable parameters.
• Clustering for directed graphs using parametrized random walk diffusion kernels, H. Sevi, M. Jonckheere, and A. Kalogeratos, arxiv preprint, 2022 [pdf] Abstract
Clustering based on the random walk operator has been proven effective for undirected graphs, but its generalization to directed graphs (digraphs) is much more challenging. Although the random walk operator is well-defined for digraphs, in most cases such graphs are not strongly connected, and hence the associated random walks are not irreducible, which is a crucial property for clustering that exists naturally in the undirected setting. To remedy this, the usual workaround is to either naively symmetrize the adjacency matrix or to replace the natural random walk operator by the teleporting random walk operator, but this can lead to the loss of valuable information carried by edge directionality. In this paper, we introduce a new clustering framework, the Parametrized Random Walk Diffusion Kernel Clustering (P-RWDKC), which is suitable for handling both directed and undirected graphs. Our framework is based on the diffusion geometry and the generalized spectral clustering framework. Accordingly, we propose an algorithm that automatically reveals the cluster structure at a given scale, by considering the random walk dynamics associated with a parametrized kernel operator, and by estimating its critical diffusion time. Experiments on K-NN graphs constructed from real-world datasets and real-world graphs show that our clustering approach performs well in all tested cases, and outperforms existing approaches in most of them.
• Collaborative likelihood-ratio estimation over graphs, A. de la Concha, A. Kalogeratos, and N. Vayatis, arxiv preprint, 2022 [pdf]. Abstract
Assuming we have i.i.d observations from two unknown probability density functions (pdfs), p and p’, the likelihood-ratio estimation (LRE) is an elegant approach to compare the two pdfs just by relying on the available data, and without knowing the pdfs explicitly. In this paper we introduce a graph-based extension of this problem: Suppose each node of a fixed graph has access to observations coming from two unknown node-specific pdfs, p_i and p’_i; the goal is then to compare the respective and of each node by also integrating information provided by the graph structure. This setting is interesting when the graph conveys some sort of similarity’ between the node-wise estimation tasks, which suggests that the nodes can collaborate to solve more efficiently their individual tasks, while on the other hand trying to limit the data sharing among them. Our main contribution is a distributed non-parametric framework for graph-based LRE, called GRULSIF, that incorporates in a novel way elements from f-divengence functionals, Kernel methods, and Multitask Learning. Among the several applications of LRE, we choose the two-sample hypothesis testing to develop a proof of concept for our graph-based learning framework. Our experiments compare favorably the performance of our approach against state-of-the-art non-parametric statistical tests that apply at each node independently, and thus disregard the graph structure.
• Generalized Spectral Clustering for Directed and Undirected Graphs, H. Sevi, M. Jonckeere, and A. Kalogeratos, arxiv preprint, 2022. [pdf]. Abstract
Spectral clustering is a popular approach for clustering undirected graphs, but its extension to directed graphs (digraphs) is much more challenging. A typical workaround is to naively symmetrize the adjacency matrix of the directed graph, which can however lead to discarding valuable information carried by edge directionality. In this paper, we present a generalized spectral clustering framework that can address both directed and undirected graphs. Our approach is based on the spectral relaxation of a new functional that we introduce as the generalized Dirichlet energy of a graph function, with respect to an arbitrary positive regularizing measure on the graph edges. We also propose a practical parametrization of the regularizing measure constructed from the iterated powers of the natural random walk on the graph. We present theoretical arguments to explain the efficiency of our framework in the challenging setting of unbalanced classes. Experiments using directed K-NN graphs constructed from real datasets show that our graph partitioning method performs consistently well in all cases, while outperforming existing approaches in most of them.
• Online non-parametric change-point detection for heterogeneous data streams observed over graph nodes . A. de la Concha, A. Kalogeratos, and Nicolas Vayatis, arxiv preprint, 2021. [pdf] Abstract
Consider a heterogeneous data stream being generated by the nodes of a graph. The data stream is in essence composed by multiple streams, possibly of different nature that depends on each node. At a given moment τ, a change-point occurs for a subset of nodes C, signifying the change in the probability distribution of their associated streams. In this paper we propose an online non-parametric method to infer τ based on the direct estimation of the likelihood-ratio between the post-change and the pre-change distribution associated with the data stream of each node. We propose a kernel-based method, under the hypothesis that connected nodes of the graph are expected to have similar likelihood-ratio estimates when there is no change-point. We demonstrate the quality of our method on synthetic experiments and real-world applications.
• Epidemic Models for COVID-19 during the First Wave from February to May 2020: a Methodological Review. M. Garin, M. Limnios, A. Nicolaï, I. Bargiotas, O. Boulant, S.E. Chick, A. Dib, T. Evgeniou, M. Fekom, A. Kalogeratos, C. Labourdette, A. Ovchinnikov, R. Porcher, C. Pouchol, and N. Vayatis, arxiv:2109.01450, Sep 2021. [pdf] Abstract
We review epidemiological models for the propagation of the COVID-19 pandemic during the early months of the outbreak: from February to May 2020. The aim is to propose a methodological review that highlights the following characteristics: (i) the epidemic propagation models, (ii) the modeling of intervention strategies, (iii) the models and estimation procedures of the epidemic parameters and (iv) the characteristics of the data used. We finally selected 80 articles from open access databases based on criteria such as the theoretical background, the reproducibility, the incorporation of interventions strategies, etc. It mainly resulted to phenomenological, compartmental and individual-level models. A digital companion including an online sheet, a Kibana interface and a markdown document is proposed. Finally, this work provides an opportunity to witness how the scientific community reacted to this unique situation.
• Efficient stream-based Max-Min diversification with minimal failure rate, M. Fekom and A. Kalogeratos, 2020 [pdf] Abstract
The stream-based Max-Min diversification problem concerns the task of selecting a limited number of diverse instances from a data stream. The nature of the problem demands immediate and irrevocable decisions. The set-wise diversity to be maximized is the minimum distance among any pair of the selected instances. Standard algorithmic approaches for sequential selection disregard the possibility of selection failures, which is the situation where the last instances of the stream are picked by default to prevent having an incomplete selection. This defect can be catastrophic for the Max-Min diversification objective. In this paper we present the Failure Rate Minimization (FRM) algorithm that allows the selection of a set of disparate instances while reducing significantly the probability of having failures. This is achieved by means of both analytical and empirical techniques. FRM is put in comparison with relevant algorithms from the literature through simulations on real datasets, where we demonstrate its efficiency and low time complexity.
• Winning the competition: enhancing counter-contagion in SIS-like epidemic processes. A. Kalogeratos and S.S. Mannelli, Technical Report, Jun 2020. [pdf] Abstract
In this paper we consider the epidemic competition between two generic diffusion processes, where each competing side is represented by a different state of a stochastic process. For this setting, we present the Generalized Largest Reduction in Infectious Edges (gLRIE) dynamic resource allocation strategy to advantage the preferred state against the other. Motivated by social epidemics, we apply this method to a generic continuous-time SIS-like diffusion model where we allow for: i) arbitrary node transition rate functions that describe the dynamics of propagation depending on the network state, and ii) competition between the healthy (positive) and infected (negative) states, which are both diffusive at the same time, yet mutually exclusive on each node. Finally we use simulations to compare empirically the proposed gLRIE against competitive approaches from literature.
• Dynamic Epidemic Control via Sequential Resource Allocation, M. Fekom, N. Vayatis, and A. Kalogeratos, Technical Report, Jun 2020. [pdf] Abstract
In the Dynamic Resource Allocation (DRA) problem, an administrator has to allocate a limited amount of resources to the nodes of a network in order to reduce a diffusion process (DP) (e.g. an epidemic). In this paper we propose a multi-round dynamic control framework, which we realize through two derived models: the Restricted and the Sequential DRA (RDRA, SDRA), that allows for restricted information and access to the entire network, contrary to standard full-information and full-access DRA models. At each intervention round, the administrator has only access — simultaneous for the former, sequential for the latter — to a fraction of the network nodes. This sequential aspect in the decision process offers a completely new perspective to the dynamic DP control, making this work the first to cast the dynamic control problem as a series of sequential selection problems. Through in-depth SIS epidemic simulations we compare the performance of our multi-round approach with other resource allocation strategies and several sequential selection algorithms on both generated, and real-data networks. The results provide evidence about the efficiency and applicability of the proposed framework for real-life problems.
• The Warm-starting Sequential Selection Problem and its Multi-round Extension, M. Fekom, A. Kalogeratos, and N. Vayatis, Technical Report (eprint arxiv:1709.05231), Nov 2019. [pdf][arXiv link] (this updated the older version with title “The Multi-Round Sequential Selection“, from Sep 2018.Abstract
In the Sequential Selection Problem (SSP), immediate and irrevocable decisions need to be made as candidates randomly arrive for a job interview. Standard SSP variants, such as the well-known secretary problem, begin with an empty selection set (cold-start) and perform the selection process once over a single candidate set (single-round). In this paper we address these two limitations. First, we introduce the novel Warm-starting SSP (WSSP) setting which considers at hand a reference set, a set of previously selected items of a given quality, and tries to update optimally that set by (re-)assigning each job at most once. We adopt a cutoff-based approach to optimize a rank-based objective function over the final assignment of the jobs. In our technical contribution, we provide analytical results regarding the proposed WSSP setting, we introduce the algorithm Cutoff-based Cost Minimization (CCM) (and the low failures-CCM, which is more robust to high rate of resignations) that adapts to changes in the quality of the reference set thanks to the translation method we propose. Finally, we implement and test CCM in a multi-round setting that is particularly interesting for real-world application scenarios.
• A Spectral Method for Activity Shaping in Continuous-Time Information Cascades, K. Scaman, A. Kalogeratos, L. Corinzia, N. Vayatis, Technical Report, Sep 2017. [pdf][arXiv link].Abstract
The Information Cascades Model captures dynamical properties of user activity in a social network. In this work, we develop a novel framework for activity shaping under the Continuous-Time Information Cascades Model which allows the administrator for local control actions by allocating targeted resources that can alter the spread of the process. Our framework employs the optimization of the spectral radius of the Hazard matrix, a quantity that has been shown to drive the maximum influence in a network, while enjoying a simple convex relaxation when used to minimize the influence of the cascade. In addition, use-cases such as quarantine and node immunization are discussed to highlight the generality of the proposed activity shaping framework. Finally, we present the NetShape influence minimization method which is compared favorably to baseline and state-of-the-art approaches through simulations on real social networks.

### Workshops / Meetings (short papers, posters, abstracts, no proc.)

• Collaborative likelihood-ratio estimation over graphs, A. de la Concha, A. Kalogeratos, and N. Vayatis, Workshop NeurIPS@Paris 2022 [program], 23-24 November 2022. [paper][slides][poster]
• Data inspection via challenging decision boundaries’ rigidity, A. Merida, A. Kalogeratos, and Mathilde Mougeot. Int. Conf. of Computational Statistics (COMPSTAT), 2022.
• Generalized Spectral Clustering for Directed and Undirected Graphs, H. Sevi, M. Jonckeere, and A. Kalogeratos, poster at the  Workshop on Recent Advancements on Graph Machine Learning, Sorbonne University, 2022. [paper]
• The Warm-starting Sequential Selection Problem, M. Fekom, N. Vayatis, and A. Kalogeratos, International Workshop in Sequential Methodologies (IWSM), June 2019, State University of New York at Binghamton, US.
• Node-level Anomaly Detection in Communication Networks, B. Le Bars and A. Kalogeratos, 3rd Graph Signal Processing Workshop (GSP), 2018. [short paper, no proc.; longer version will become soon available] Abstract
In this paper we consider the task of the detection of abnormal communication volume, occurring at node-level in a communication network. We model the communication by means of a dynamic graph with edges related to an occurring communication event appearing instantaneously. We propose a statistical model for the communication volume recorded at a single node, in order to detect anomalies. Our approach is evaluated in real-world communication data.
• Optimizing group selection over multiple sequential selection rounds, M. Fekom, A. Kalogeratos, and N. Vayatis, Poster at the Workshop on Multi-Armed Bandits and Learning Algorithms, 2018.
• On behavioral epidemics and dynamic control, S. Sarao, A. Kalogeratos, K. Scaman, and N. Vayatis, Poster at the 42nd Middle European Cooperation in Statistical Physics (MECO), Feb 2017, Lyon, France.
• Dynamic control of social diffusions using extensions of the SIS model, A. Kalogeratos, S. Sarao, K. Scaman, and N. Vayatis, to appear as a full oral presentation in 2016 Conference on Complex Systems in Amsterdam (no proceedings). Abstract

Diffusion processes model propagation phenomena on complex networks, such as epidemics, information diffusion, and viral marketing. In many situations, it is critical to suppress an undesired diffusion process by means of dynamic resource allocation, where one need to decide targeted actions by taking into account the evolving infection state of the network.

In the context of continuous-time SIS, and with provided full information regarding the nodes’ state, we consider the scenario where a budget of treatment resources of limited efficiency is available at each time for distribution to infected nodes. Recent results on this particular problem include the Priority Planning approach which computes a linear ordering of the nodes with minimal maxcut, and the optimal greedy approach called Largest Reduction of Infectious Edges (LRIE). The latter is a simple, yet efficient, strategy that computes an intuitive priority score for the infected nodes which combines the notion of node virality (possibility to infect other nodes) and vulnerability (possibility to get reinfected after recovery).

In this work we show that the principle of the LRIE score holds for a wide range of SIS-like modeling scenarios. More specifically, we propose the Generalized LRIE (gLRIE) strategy and study the dynamic diffusion control by introducing a two-fold extension to SIS which can model important aspects of social diffusion (e.g. behaviors or habits). The first considers nonlinear functions of infection rates with saturation. On the top that, our second extension considers competition in the sense that the two node states, the infected and the healthy, are both diffusive, though each node can only be in only one of them at a time. In this case, our control strategy has to align with the healthy diffusion to help it to win the competition. Finally, simulations on large-scale real and synthetic networks show the efficiency of gLIE.

• Learning to Suppress SIS Epidemics in Networks, A. Kalogeratos, K. Scaman, and N. Vayatis, NIPS 2015 Networks in the Social and Information Sciences workshop (NIPS 2015), 2015. [workshop link][pdf][poster][bib]. Abstract

In this paper, we introduce the class of priority planning strategies for suppressing SIS epidemics taking place in a network. This is performed via dynamic allocation of treatment resources with limited efficiency to the infected nodes, according to a precomputed priority-order. Using recent theoretical results that highlight the role of the maxcut of a node ordering and the extinction time of an epidemic, we propose a simple and efficient strategy called MaxCut Minimization (MCM) that outperforms competing state-of-the-art strategies in simulated epidemic scenarios.

• Dynamic Treatment Allocation for Epidemic Control in Arbitrary Networks, K. Scaman, A. Kalogeratos, N. Vayatis, WSDM 2014 Diffusion in Networks and Cascade Analytics (DiffNet) Workshop, 2014. [workshop link][pdf][slides][poster][bib]. Abstract

While static epidemic control, e.g. using vaccination, has been extensively studied for various network types, controlling epidemics dynamically remains an open issue. In this work, we first propose a general model formulation for the dynamic treatment allocation problem for the Susceptible-Infected-Susceptible diffusion model. Then, we investigate dynamic control strategies and further propose the novel Largest Reduction in Infectious Edges (LRIE) heuristic that gives priority to the treatment of nodes that have both a high dissemination rate of the infection to many healthy nodes, and low reinfection probability after recovery. Experiments on random and a real-world network show that the dynamic problem is significantly different from vaccination, since the latter strategies can lead to disastrous results, and that the proposed heuristic is an effective strategy under various initial infection conditions.

### Invited Talks

• At the 10th International Workshop on Applied Probability (IWAP) 2023 at Thessaloniki. I will talk about the Warm-starting selection process and a multi-round extention.
• At the French German Summer School on Transfer Learning, ENS-Paris-Saclay, June 4-6 2018.
• Invited seminar talk on “Epidemics, Competition and Resource Management” was given in Paris at a Working Group on Machine Learning and Big Data of the French Ministry of Social Affairs and Health (organizer: Magali Beffy). The group is formed by scientists and researchers working on various organizations/institutions (Ministry of Health, INSEE, IRDES, Dauphine) – 25/1/2017.
• Dynamic suppression of epidemics on networks, at the Complex Networks research group of LIP6, Paris 6 (Jussieu), France, 13/6/2016.
• Epidemics in the new socio-economic era: challenges and applications, at the Department of Computer Science and Engineering, University of Ioannina, Greece, 25/5/2016.
• Suppressing epidemics on arbitrary networks using treatment resources of limited efficiency, at INRA Research Center at Jouy-en-Josas, Paris area, 4/3/2016.
• Invited TalkEfficient algorithms for the suppression of diffusion processes on networks with application in epidemiology and marketing, summit: “Big data and public policies for the transportation” organized by the General Direction of Infrastructures, Transportation, and the General Commissioner on Durable Development of the Ministry of Ecology, Durable Development and Energy, along with ENS Cachan and PSE-School of Economics of Paris (15/10/2015) [agenda][presentation].