While deep generative models have significantly advanced representation learning, they may inherit or amplify biases and fairness issues by encoding sensitive attributes alongside predictive features. Enforcing strict independence in disentanglement is often unrealistic when target and sensitive factors are naturally correlated. To address this challenge, we propose CAD-VAE(Correlation-Aware Disentangled VAE), which introduces a correlated latent code to capture the information shared between the target and sensitive attributes. Given this correlated latent, our method effectively separates overlapping factors without extra domain knowledge by directly minimizing the conditional mutual information between target and sensitive codes. A relevance-driven optimization strategy refines the correlated code by efficiently capturing essential correlated features and eliminating redundancy. Extensive experiments on benchmark datasets demonstrate that CAD-VAE produces fairer representations, realistic counterfactuals, and improved fairness-aware image editing.

The increasing use of deep neural networks (DNNs) in high-stakes domains such as hiring, healthcare, and finance has heightened concerns about algorithmic fairness. Because training data can encode historical and societal biases, learned models may exhibit disparate outcomes for underrepresented groups. Prior work is largely model-centric, improving fairness via specialized loss functions or architectural modifications, which can introduce additional training overhead and hinder deployment in modular or rapidly evolving pipelines. We instead study a data-centric alternative: constructing a fair training dataset that promotes equitable behavior without changing the model architecture. We propose FairData, which synthesizes a fair dataset by optimizing a gradient-matching objective that aligns the training dynamics of a randomly initialized model on the synthetic data with those on the original data, while explicitly regularizing for group fairness. The resulting dataset is model-agnostic, lightweight, and remains in the original input space, enabling straightforward reuse across downstream models. Experiments on four benchmark datasets show that FairData consistently reduces group disparities across diverse architectures while maintaining competitive predictive performance, suggesting fairness-aware dataset optimization as a practical complement to model-specific fairness techniques.

Dynamic graph neural networks (dynamic GNNs) have demonstrated remarkable effectiveness in analyzing time-varying graph-structured data. However, their black-box nature often hinders users from understanding their predictions, which can limit their applications. In recent years, there has been a surge in research aimed at explaining GNNs, but most studies have focused on static graphs, leaving the explanation of dynamic GNNs relatively unexplored. Explaining dynamic GNNs presents a unique challenge due to their complex spatial and temporal structures. As a result, existing approaches designed for explaining static graphs are not directly applicable to dynamic graphs because they ignore temporal dependencies among graph snapshots. To address this issue, we propose DGExplainer, which offers a reliable explanation of dynamic GNN predictions. DGExplainer utilizes the relevance back-propagation technique both time-wise and layer-wise. Specifically, it incorporates temporal information by computing the relevance of node representations along the inverse of the time evolution. Additionally, for each time step, it calculates layer-wise relevance from a graph-based module by redistributing the relevance of node representations along the back-propagation path. Quantitative and qualitative experimental results on six real-world datasets demonstrate the effectiveness of DGExplainer in identifying important nodes for link prediction and node regression in dynamic GNNs.

Explicit noise-level conditioning is widely regarded as essential for the effective operation of Graph Diffusion Models (GDMs). In this work, we challenge this assumption by investigating whether denoisers can implicitly infer noise levels directly from corrupted graph structures, potentially eliminating the need for explicit noise conditioning. To this end, we develop a theoretical framework centered on Bernoulli edge-flip corruptions and extend it to encompass more complex scenarios involving coupled structure-attribute noise. Extensive empirical evaluations on both synthetic and real-world graph datasets, using models such as GDSS and DiGress, provide strong support for our theoretical findings. Notably, unconditional GDMs achieve performance comparable or superior to their conditioned counterparts, while also offering reductions in parameters (4-6%) and computation time (8-10%). Our results suggest that the high-dimensional nature of graph data itself often encodes sufficient information for the denoising process, opening avenues for simpler, more efficient GDM architectures.

With the rise of machine learning techniques, ensuring the fairness of decisions made by machine learning algorithms has become of great importance in critical applications. However, measuring fairness often requires full access to the model parameters, which compromises the confidentiality of the models. In this paper, we propose a solution using zero-knowledge proofs, which allows the model owner to convince the public that a machine learning model is fair while preserving the secrecy of the model. To circumvent the efficiency barrier of naively proving machine learning inferences in zero-knowledge, our key innovation is a new approach to measure fairness only with model parameters and some aggregated information of the input, but not on any specific dataset. To achieve this goal, we derive new bounds for the fairness of logistic regression and deep neural network models that are tighter and better reflecting the fairness compared to prior work. Moreover, we develop efficient zero-knowledge proof protocols for common computations involved in measuring fairness, including the spectral norm of matrices, maximum, absolute value, and fixed-point arithmetic. We have fully implemented our system, FairZK, that proves machine learning fairness in zero-knowledge. Experimental results show that Fairzk is significantly faster than the naive approach and an existing scheme that use zero-knowledge inferences as a subroutine. The prover time is improved by 3.1x-1789x depending on the size of the model and the dataset. FairZK can scale to a large model with 47 million parameters for the first time, and generates a proof for its fairness in 343 seconds. This is estimated to be 4 orders of magnitude faster than existing schemes, which only scale to small models with hundreds to thousands of parameters.

As machine learning (ML)-driven decisions proliferate, particularly in cases involving sensitive attributes, such as gender, race, and age, to name a few, the need for equity and impartiality has emerged as a fundamental concern. In situations demanding real-time decision-making, fairness objectives become more nuanced and complex: instantaneous fairness to ensure equity in every time slot and long-term fairness to ensure fairness over a period of time. There is a growing awareness that real-world systems operating over long periods require fairness over different timelines. Most existing approaches mainly address dynamic costs with time-invariant fairness constraints, often disregarding the challenges posed by time-varying fairness constraints. Time-varying fairness constraints require the learners to adapt their decisions to meet the changing constraints. However, long-term dynamics are hard to assess and accurately predicting the changes in constraints can be difficult. To bridge this gap, this work introduces a framework for ensuring long-term fairness within dynamic decision-making systems characterized by time-varying fairness constraints. We formulate the decision problem with fairness constraints over a period as a constrained online optimization problem. A novel online algorithm, named long-term fairness-aware online learning algorithm (LoTFair), is presented that solves the problem "on the fly." We demonstrate that long-term fairness for real-time decision making can be addressed flexibly and efficiently by LoTFair: it achieves overall fairness while maintaining performance over the long run.

Finding specific preference-guided Pareto solutions that represent different trade-offs among multiple objectives is critical yet challenging in multi-objective problems. Existing methods are restrictive in preference definitions and/or their theoretical guarantees. In this work, we introduce a Flexible framEwork for pREfeRence-guided multi-Objective learning (**FERERO**) by casting it as a constrained vector optimization problem. Specifically, two types of preferences are incorporated into this formulation -- the *relative preference* defined by the partial ordering induced by a polyhedral cone, and the *absolute preference* defined by constraints that are linear functions of the objectives. To solve this problem, convergent algorithms are developed with both single-loop and stochastic variants. Notably, this is the *first single-loop primal algorithm* for constrained optimization to our knowledge. The proposed algorithms adaptively adjust to both constraint and objective values, eliminating the need to solve different subproblems at different stages of constraint satisfaction. Experiments on multiple benchmarks demonstrate the proposed method is very competitive in finding preference-guided optimal solutions. Code is available at https://github.com/lisha-chen/FERERO/.

Federated learning is renowned for its efficacy in distributed model training, ensuring that users, called clients, retain data privacy by not disclosing their data to the central server that orchestrates collaborations. Most previous work on federated learning assumes that clients possess static batches of training data. However, clients may also need to make real-time predictions on streaming data in non-stationary environments. In such dynamic environments, employing pre-trained models may be inefficient, as they struggle to adapt to the constantly evolving data streams. To address this challenge, clients can fine-tune models online, leveraging their observed data to enhance performance. Despite the potential benefits of client participation in federated online model fine-tuning, existing analyses have not conclusively demonstrated its superiority over local model fine-tuning. To bridge this gap, the present paper develops a novel personalized federated learning algorithm, wherein each client constructs a personalized model by combining a locally fine-tuned model with multiple federated models learned by the server over time. Theoretical analysis and experiments on real datasets corroborate the effectiveness of this approach for real-time predictions and federated model fine-tuning.

Conformal prediction is an uncertainty quantification method that constructs a prediction set for a previously unseen datum, ensuring the true label is included with a predetermined coverage probability. Adaptive conformal prediction has been developed to address data distribution shifts in dynamic environments. However, the efficiency of prediction sets varies depending on the learning model used. Employing a single fixed model may not consistently offer the best performance in dynamic environments with unknown data distribution shifts. To address this issue, we introduce a novel adaptive conformal prediction framework, where the model used for creating prediction sets is selected ‘on the fly’ from multiple candidate models. The proposed algorithm is proven to achieve strongly adaptive regret over all intervals while maintaining valid coverage. Experiments on both real and synthetic datasets corroborate that the proposed approach consistently yields more efficient prediction sets while maintaining valid coverage, outperforming alternative methods.

Machine learning over graphs has recently attracted growing attention due to its ability to analyze and learn complex relations within critical interconnected systems. However, the disparate impact that is amplified by the use of biased graph structures in these algorithms has raised significant concerns for their deployment in real-world decision systems. In addition, while synthetic graph generation has become pivotal for privacy and scalability considerations, the impact of generative learning algorithms on structural bias has not yet been investigated. Motivated by this, this work focuses on the analysis and mitigation of structural bias for both real and synthetic graphs. Specifically, we first theoretically analyze the sources of structural bias that result in disparity for the predictions of dyadic relations. To alleviate the identified bias factors, we design a novel fairness regularizer that offers a versatile use. Faced with the bias amplification in graph generation models brought to light in this work, we further propose a fair graph generation framework, FairWire, by leveraging our fair regularizer design in a generative model. Experimental results on real-world networks validate that the proposed tools herein deliver effective structural bias mitigation for both real and synthetic graphs.

Graphs can facilitate modeling various complex systems such as gene networks and power grids as well as analyzing the underlying relations within them. Learning over graphs has recently attracted increasing attention, particularly graph neural network (GNN)–based solutions, among which graph attention networks (GATs) have become one of the most widely utilized neural network structures for graph-based tasks. Although it is shown that the use of graph structures in learning results in the amplification of algorithmic bias, the influence of the attention design in GATs on algorithmic bias has not been investigated. Motivated by this, the present study first carries out a theoretical analysis in order to demonstrate the sources of algorithmic bias in GAT-based learning for node classification. Then, a novel algorithm, FairGAT, which leverages a fairness-aware attention design, is developed based on the theoretical findings. Experimental results on real-world networks demonstrate that FairGAT improves group fairness measures while also providing comparable utility to the fairness-aware baselines for node classification and link prediction.

Online learning with expert advice is widely used in various machine learning tasks. It considers the problem where a learner chooses one from a set of experts to take advice and make a decision. In many learning problems, experts may be related, henceforth the learner can observe the losses associated with a subset of experts that are related to the chosen one. In this context, the relationship among experts can be captured by a feedback graph, which can be used to assist the learner's decision-making. However, in practice, the nominal feedback graph often entails uncertainties, which renders it impossible to reveal the actual relationship among experts. To cope with this challenge, the present work studies various cases of potential uncertainties and develops novel online learning algorithms to deal with uncertainties while making use of the uncertain feedback graph. The proposed algorithms are proved to enjoy sublinear regret under mild conditions. Experiments on real datasets are presented to demonstrate the effectiveness of the novel algorithms.

Node representation learning has attracted increasing attention due to its efficacy for various applications on graphs. However, fairness is a largely under-explored territory within the field, although it is shown that the use of graph structure in learning amplifies bias. To this end, this work theoretically explains the sources of bias in node representations obtained via graph neural networks (GNNs). It is revealed that both nodal features and graph structure lead to bias in the obtained representations. Building upon the analysis, fairness-aware data augmentation frameworks are developed to reduce the intrinsic bias. Our theoretical analysis and proposed schemes can be readily employed in understanding and mitigating bias for various GNN-based learning mechanisms. Extensive experiments on node classification and link prediction over multiple real networks are carried out, and it is shown that the proposed augmentation strategies can improve fairness while providing comparable utility to state-of-the-art methods.

This article considers predicting future statuses of multiple agents in an online fashion by exploiting dynamic interactions in the system. We propose a novel collaborative prediction unit (CoPU), which aggregates the predictions from multiple collaborative predictors according to a collaborative graph. Each collaborative predictor is trained to predict the agent status by integrating the impact of another agent. The edge weights of the collaborative graph reflect the importance of each predictor. The collaborative graph is adjusted online by multiplicative update, which can be motivated by minimizing an explicit objective. With this objective, we also conduct regret analysis to indicate that, along with training, our CoPU achieves similar performance with the best individual collaborative predictor in hindsight. This theoretical interpretability distinguishes our method from many other graph networks. To progressively refine predictions, multiple CoPUs are stacked to form a collaborative graph neural network. Extensive experiments are conducted on three tasks: online simulated trajectory prediction, online human motion prediction, and online traffic speed prediction, and our methods outperform state-of-the-art works on the three tasks by 28.6%, 17.4%, and 21.0% on average, respectively; in addition, the proposed CoGNNs have lower average time costs in one online training/testing iteration than most previous methods.

Many real-world networks such as social networks, traffic networks vary over time, which can be modeled as dynamic graphs. Despite the significant number of systems that can facilitate from the algorithmic tools over dynamic graphs, dynamic graph representation learning is an under-explored research area. Furthermore, while the fairness of algorithms is essential for their deployment in real-world systems, this issue has never been considered in the context of dynamic graphs to the best of our knowledge. Motivated by this, the present study proposes an efficient online node representation learning framework over dynamic graphs that can also mitigate bias. Specifically, the proposed technique combines different observations (graph structure and nodal attributes) of the same source (attributed graph) in a complementary way while also reducing the intrinsic bias in the learned representations. Experimental results on dynamic graphs show that the proposed online strategy can improve the group fairness measures for node classification together with comparable/better utility to the baselines.

Graph machine learning algorithms have become popular tools in helping us gain a deeper understanding of the ubiquitous graph data. Despite their effectiveness, most graph machine learning algorithms lack considerations for fairness, which can result in discriminatory outcomes against certain demographic subgroups or individuals. As a result, there is a growing societal concern about mitigating the bias exhibited in these algorithms. To tackle the problem of algorithmic bias in graph machine learning algorithms, this tutorial aims to provide a comprehensive overview of recent research progress in measuring and mitigating the bias in machine learning algorithms on graphs. Specifically, this tutorial first introduces several widely-used fairness notions and the corresponding metrics. Then, we present a well-organized review of the theoretical understanding of bias in graph machine learning algorithms, followed by a summary of existing techniques to debias graph machine learning algorithms. Furthermore, we demonstrate how different real-world applications benefit from these graph machine learning algorithms after debiasing. Finally, we provide insights on current research challenges and open questions to encourage further advances.

Multi-kernel learning (MKL) has been widely used in learning problems involving function learning tasks. Compared with single kernel learning approach which relies on a pre-selected kernel, the advantage of MKL is its flexibility results from combining a dictionary of kernels. However, inclusion of irrelevant kernels in the dictionary may deteriorate the accuracy of MKL, and increase the computational complexity. Faced with this challenge, a novel graph-aided framework is developed to select a subset of kernels from the dictionary with the assistance of a graph. Different graph construction and refinement schemes are developed based on incurred losses or kernel similarities to assist the adaptive selection process. Moreover, to cope with the scenario where data may be collected in a sequential fashion, or cannot be stored in batch due to the massive scale, random feature approximation are adopted to enable online function learning. It is proved that our proposed algorithms enjoy sub-linear regret bounds. Experiments on a number of real datasets showcase the advantages of our novel graph-aided algorithms compared to state-of-the-art alternatives.

Learning representations of nodes in a low dimensional space is a crucial task with numerous interesting applications in network analysis, including link prediction, node classification, and visualization. Two popular approaches for this problem are \textit{matrix factorization} and \textit{random walk}-based models. In this paper, we aim to bring together the best of both worlds, towards learning node representations. In particular, we propose a weighted matrix factorization model that encodes random walk-based information about nodes of the network. The benefit of this novel formulation is that it enables us to utilize kernel functions without realizing the exact proximity matrix so that it enhances the expressiveness of existing matrix decomposition methods with kernels and alleviate their computational complexities. We extend the approach with a multiple kernel learning formulation that provides the flexibility of learning the kernel as the linear combination of a dictionary of kernels in data-driven fashion. We perform an empirical evaluation on real-world networks, showing that the proposed model outperforms baseline node embedding algorithms in downstream machine learning tasks.

Online learning with expert advice is widely used in various machine learning tasks. It considers the problem where a learner chooses one from a set of experts to take advice and make a decision. In many learning problems, experts may be related, henceforth the learner can observe the losses associated with a subset of experts that are related to the chosen one. In this context, the relationship among experts can be captured by a feedback graph, which can be used to assist the learner’s decision-making. However, in practice, the nominal feedback graph often entails uncertainties, which renders it impossible to reveal the actual relationship among experts. To cope with this challenge, the present work develops a novel online learning algorithm to deal with uncertainties while making use of the uncertain feedback graph. The proposed algorithm is proved to enjoy sublinear regret under mild conditions. Experiments on real datasets are presented to demonstrate the effectiveness of the novel algorithm.

Selective sampling is an online learning framework where the learner tries to detect the data samples whose labels can boost the performance maximally, and only the labels of chosen data samples are queried. While the design of selective sampling algorithms is extensively studied for independent data samples, the area is rather under-explored in the context of graphs. Furthermore, the limited number of existing graph-based approaches do not take into consideration the nodal attributes that are available in attributed graphs. In this study, existing online learning and selective sampling algorithms are modified to be used with graphs that have nodal features. Additionally, the bias in the results of original algorithms is investigated, and a novel bias reduction strategy is proposed that can be embedded into the dimensionality reduction step without incurring a significant complexity cost. Experiments for node classification are carried out on real social networks to showcase the advantages of incorporating nodal features, as well as the fairness-enhancement framework.

Multi-kernel learning (MKL) exhibits well-documented performance in online non-linear function approximation. Federated learning enables a group of learners (called clients) to train an MKL model on the data distributed among clients to perform online non-linear function approximation. There are some challenges in online federated MKL that need to be addressed: i) Communication efficiency especially when a large number of kernels are considered ii) Heterogeneous data distribution among clients. The present paper develops an algorithmic framework to enable clients to communicate with the server to send their updates with affordable communication cost while clients employ a large dictionary of kernels. Utilizing random feature (RF) approximation, the present paper proposes scalable online federated MKL algorithm. We prove that using the proposed online federated MKL algorithm, each client enjoys sub-linear regret with respect to the RF approximation of its best kernel in hindsight, which indicates that the proposed algorithm can effectively deal with heterogeneity of the data distributed among clients. Experimental results on real datasets showcase the advantages of the proposed algorithm compared with other online federated kernel learning ones.

With complex systems emerging in various applications, e.g., financial, biological and social networks, graphs become working horse to model and analyse these systems. Nodes within networks usually entail attributes. Due to privacy concerns and missing observations, nodal attributes may be unavailable for some nodes in real-world networks. Besides, new nodes with unknown nodal attributes may emerge at any time, which require evaluation of the corresponding attributes in real-time. In this context, the present paper reconstructs nodal attributes of unobserved ones via an estimated nodal function based on their connectivity patterns with other nodes in the graph. Unlike existing works which only consider single-hop neighbors, the present paper further explores global information and adaptively combines the effects of multi-hop neighbors together. A multikernel-based approach is developed, which is capable of leveraging global network information, and scales well with network size as well. In addition, it has the flexibility to account for different nonlinear relationship by adaptively selecting the appropriate kernel combination. Experiments on real-word datasets corroborate the merits of the proposed algorithm.

Combining benefits of kernels with Bayesian models, Gaussian process (GP) based approaches have well-documented merits not only in learning over a rich class of nonlinear functions, but also quantifying the associated uncertainty. While most GP approaches rely on a single preselected prior, the present work employs a weighted ensemble of GP priors, each having a unique covariance (kernel) belonging to a prescribed kernel dictionary – which leads to a richer space of learning functions. Leveraging kernel approximants formed by spectral features for scalability, an online interactive ensemble (OI-E) GP framework is developed to jointly learn the sought function, and for the first time select interactively the EGP kernel on-the-fly. Performance of OI-EGP is benchmarked by the best fixed function estimator via regret analysis. Furthermore, the novel OI-EGP is adapted to accommodate dynamic learning functions. Synthetic and real data tests demonstrate the effectiveness of the proposed schemes.

Multi-kernel learning (MKL) exhibits reliable performance in nonlinear function approximation tasks. Instead of using one kernel, it learns the optimal kernel from a pre-selected dictionary of kernels. The selection of the dictionary has crucial impact on both the performance and complexity of MKL. Specifically, inclusion of a large number of irrelevant kernels may impair the accuracy, and increase the complexity of MKL algorithms. To enhance the accuracy, and alleviate the computational burden, the present paper develops a novel scheme which actively chooses relevant kernels. The proposed framework models the pruned kernel combination as feedback collected from a graph, that is refined ’on the fly.’ Leveraging the random feature approximation, we propose an online scalable multi-kernel learning approach with graph feedback, and prove that the proposed algorithm enjoys sublinear regret. Numerical tests on real datasets demonstrate the effectiveness of the novel approach.

Kernel-based methods exhibit well-documented performance in various nonlinear learning tasks. Most of them rely on a preselected kernel, whose prudent choice presumes task-specific prior information. Especially when the latter is not available, multi-kernel learning has gained popularity thanks to its flexibility in choosing kernels from a prescribed kernel dictionary. Leveraging the random feature approximation and its recent orthogonality-promoting variant, the present contribution develops a scalable multi-kernel learning scheme (termed Raker) to obtain the sought nonlinear learning function `on the fly,' first for static environments. To further boost performance in dynamic environments, an adaptive multi-kernel learning scheme (termed AdaRaker) is developed. AdaRaker accounts not only for data-driven learning of kernel combination, but also for the unknown dynamics. Performance is analyzed in terms of both static and dynamic regrets. AdaRaker is uniquely capable of tracking nonlinear learning functions in environments with unknown dynamics, and with with analytic performance guarantees Tests with synthetic and real datasets are carried out to showcase the effectiveness of the novel algorithms.

Kernel-based methods exhibit well-documented performance in various nonlinear learning tasks. Most of them rely on a preselected kernel, whose prudent choice presumes task-specific prior information. To cope with this limitation, multi-kernel learning has gained popularity thanks to its flexibility in choosing kernels from a prescribed kernel dictionary. Leveraging the random feature approximation and its recent orthogonality-promoting variant, the present contribution develops an online multi-kernel learning scheme to infer the intended nonlinear function ‘on the fly.’ To further boost performance in non-stationary environments, an adaptive multi-kernel learning scheme is developed with affordable computation and memory complexity. Performance is analyzed in terms of both static and dynamic regret. To our best knowledge, AdaRaker is the first algorithm that can optimally track nonlinear functions in non-stationary settings with strong theoretical guarantees. Numerical tests on real datasets are carried out to showcase the effectiveness of the proposed algorithms.

Kernel-based methods have well-appreciated performance in various nonlinear learning tasks. Most of them rely on a preselected kernel, whose prudent choice presumes task-specific prior information. To cope with this limitation, multi-kernel learning has gained popularity thanks to its flexibility in choosing kernels from a prescribed kernel dictionary. Leveraging the random feature approximation and its recent orthogonality-promoting variant, the present contribution develops an online multi-kernel learning scheme to infer the intended nonlinear function `on the fly.' Performance analysis shows that the novel algorithm can afford sublinear regret. Numerical tests on real datasets are carried out to showcase the effectiveness of the proposed algorithms.

Internet of Things (IoT) is featured with its seamless connectivity of billions of smart devices, which offer different functionalities and serve various personalized tasks. To meet the task-specific requirements such as latency and privacy, the fog computing emerges to extend cloud computing services to the edge of the Internet backbone. This paper deals withonline fog computingemerging in IoT, where the goal is to balance computation and communication at fog networks on-the-fly to minimize service latency. Due to heterogeneous devices and human participation in IoT, the online decisions here need to flexibly adapt to the temporally unpredictable user demands and availability of fog resources. By generalizing the classic online convex optimization (OCO) framework, the low-latency fog computing task is first formulated as an OCO problem involving both time-varying loss functions and time-varying constraints. These constraints are revealed after making decisions, and allow instantaneous violations yet they must be satisfied in the long term. Tailored for heterogeneous tasks in IoT, a “thing-adaptive” online saddle-point (TAOSP) scheme is developed, which automatically adjusts the stepsize to offer desirabletask-specificlearning rates. It is established that without prior knowledge of the time-varying parameters, TAOSP simultaneously yields near-optimality and feasibility, provided that the best dynamic solutions vary slowly over time. Numerical tests corroborate that our novel approach outperforms the state-of-the-art in minimizing network latency.

Identifying graph topologies as well as processes evolving over graphs emerge in various applications involving gene-regulatory, brain, power, and social networks, to name a few. Key graph-aware learning tasks include regression, classification, subspace clustering, anomaly identification, interpolation, extrapolation, and dimensionality reduction. Scalable approaches to deal with such high-dimensional tasks experience a paradigm shift to address the unique modeling and computational challenges associated with data-driven sciences. Albeit simple and tractable, linear time-invariant models are limited since they are incapable of handling generally evolving topologies, as well as nonlinear and dynamic dependencies between nodal processes. To this end, the main goal of this paper is to outline overarching advances, and develop a principled framework to capture nonlinearities through kernels, which are judiciously chosen from a preselected dictionary to optimally fit the data. The framework encompasses and leverages (non) linear counterparts of partial correlation and partial Granger causality, as well as (non)linear structural equations and vector autoregressions, along with attributes such as low rank, sparsity, and smoothness to capture even directional dependencies with abrupt change points, as well as time-evolving processes over possibly time-evolving topologies. The overarching approach inherits the versatility and generality of kernel-based methods, and lends itself to batch and computationally affordable online learning algorithms, which include novel Kalman filters over graphs. Real data experiments highlight the impact of the nonlinear and dynamic models on consumer and financial networks, as well as gene-regulatory and functional connectivity brain networks, where connectivity patterns revealed exhibit discernible differences relative to existing approaches.

Linear structural vector autoregressive models constitute a generalization of structural equation models (SEMs) and vector autoregressive (VAR) models, two popular approaches for topology inference of directed graphs. Although simple and tractable, linear SVARMs seldom capture nonlinearities that are inherent to complex systems, such as the human brain. To this end, the present paper advocates kernel-based nonlinear SVARMs, and develops an efficient sparsity-promoting least-squares estimator to learn the hidden topology. Numerical tests on real electrocorticographic (ECoG) data from an Epilepsy study corroborate the efficacy of the novel approach.

In this paper, we study the problem of sparse signal recovery when partial but partly erroneous prior knowledge of the signal's support is available. Based on the conventional sparse Bayesian learning framework, we propose an improved hierarchical prior model. The proposed modeling constitutes a three-layer hierarchical form. The first two layers, similar to the conventional sparse Bayesian learning, place a Gaussian-inverse-Gamma prior on the signal, while the third layer is newly added, with a prior placed on the parameters {bi}, where {bi} are parameters characterizing the sparsity-controlling hyperparameters {αi}. Such a modeling enables to automatically learn the true support from partly erroneous information through learning the values of the parameters {bi}. A variational Bayesian inference algorithm is developed based on the proposed prior model. Numerical results are provided to illustrate the performance of the proposed algorithm.

In this paper, we develop a new sparse Bayesian learning method for recovery of block-sparse signals with unknown cluster patterns. A pattern-coupled hierarchical Gaussian prior model is introduced to characterize the statistical dependencies among coefficients, where a set of hyperparameters are employed to control the sparsity of signal coefficients. Unlike the conventional sparse Bayesian learning framework in which each individual hyperparameter is associated independently with each coefficient, in this paper, the prior for each coefficient not only involves its own hyperparameter, but also the hyperparameters of its immediate neighbors. In doing this way, the sparsity patterns of neighboring coefficients are related to each other and the hierarchical model has the potential to encourage structured-sparse solutions. The hyperparameters, along with the sparse signal, are learned by maximizing their posterior probability via an expectation-maximization (EM) algorithm.

In many practical applications such as direction-of- arrival (DOA) estimation and line spectral estimation, the sparsifying dictionary is usually characterized by a set of unknown parameters in a continuous domain. To apply the conventional compressed sensing to such applications, the continuous parameter space has to be discretized to a finite set of grid points. Discretization, however, incurs errors and leads to deteriorated recovery performance. To address this issue, we propose an iterative reweighted method which jointly estimates the unknown parameters and the sparse signals. Specifically, the proposed algorithm is developed by iteratively decreasing a surrogate function majorizing a given objective function, which results in a gradual and interweaved iterative process to refine the unknown parameters and the sparse signal. Numerical results show that the algorithm provides superior performance in resolving closely-spaced frequency components.

This paper considers the problem of reconstructing sparse or compressible signals from one-bit quantized measurements. We study a new method that uses a log-sum penalty function, also referred to as the Gaussian entropy, for sparse signal recovery. Additionally, in the proposed method, the sigmoid function is introduced to quantify the consistency between the measured one-bit quantized data and the reconstructed signal. A fast iterative algorithm is developed by iteratively minimizing a convex surrogate function that bounds the original objective function. This leads to an iterative reweighted process that alternates between estimating the sparse signal and refining the weights of the surrogate function. Connections between the proposed algorithm and other existing methods are discussed. Numerical results are provided to illustrate the effectiveness of the proposed algorithm.

The fact that fewer measurements are needed by log-sum minimization for sparse signal recovery than the ℓ1-minimization has been observed by extensive experiments. Nevertheless, such a benefit brought by the use of the log-sum penalty function has not been rigorously proved. This paper provides a theoretical justification for adopting the log-sum as an alternative sparsity-encouraging function. We prove that minimizing the log-sum penalty function subject to Az = y is able to yield the exact solution, provided that a certain condition is satisfied. Specifically, our analysis suggests that, for a properly chosen regularization parameter, exact reconstruction can be attained when the restricted isometry constant δ3Kis smaller than one, which presents a less restrictive isometry condition than that required by the conventional ℓ1-type methods.