BD
B. Das
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
10 records found
1
Graph learning aims to infer a network structure directly from observed data, enabling the analysis of complex dependencies in irregular domains. Traditional methods focus on scalar signals at each node, ignoring dependencies along additional dimensions such as time, configurations of the observation device, or populations. In this work, we propose a graph signal processing framework for learning graphs from two-dimensional signals, modeled as matrix graph signals generated by joint filtering along both dimensions. This formulation leverages the concept of graph stationarity across the two dimensions and leverages product graph representations to capture structured dependencies. Based on this model, we design an optimization problem that can be solved efficiently and provably recovers the optimal underlying Kronecker/Cartesian/strong product graphs. Experiments on synthetic data demonstrate that our approach achieves higher estimation accuracy and reduced computational cost compared to existing methods.
...
Graph learning aims to infer a network structure directly from observed data, enabling the analysis of complex dependencies in irregular domains. Traditional methods focus on scalar signals at each node, ignoring dependencies along additional dimensions such as time, configurations of the observation device, or populations. In this work, we propose a graph signal processing framework for learning graphs from two-dimensional signals, modeled as matrix graph signals generated by joint filtering along both dimensions. This formulation leverages the concept of graph stationarity across the two dimensions and leverages product graph representations to capture structured dependencies. Based on this model, we design an optimization problem that can be solved efficiently and provably recovers the optimal underlying Kronecker/Cartesian/strong product graphs. Experiments on synthetic data demonstrate that our approach achieves higher estimation accuracy and reduced computational cost compared to existing methods.
Extending the concepts of classical signal processing to graphs, a wide array of methods have come to the fore, including filtering, reconstruction, classification, and sampling. Existing approaches in graph signal processing consider a known and static topology, i.e., fixed number of nodes and a fixed edge support. Two types of tasks stand out, namely, topology inference, where the edge support along with their weights are estimated from signals; and data processing, where existing data and the known topology are used to perform different tasks. However, such tasks become quite challenging when the network size and support changes over time. Particularly, these challenges involve adapting to the changing topology, data distributions and dealing with unknown topological information. The latter manifests for example, when new nodes are available to attach to the graph but their connectivity is uncertain as is the case in cold start graph-based recommender systems.
The key contribution of this dissertation is proposing methodologies for signal processing over dynamic networks which are aimed at the two aforementioned tasks. For dynamic networks with incoming nodes, we process signals by introducing a parametric stochastic attachment model. In this model, the incoming nodes connect with probability to existing nodes with certain weights. This uncertainty allows us to model input output relations and allows us to cast them in the context of different graph signal processing tasks. We learn the model attachment parameters in a task-aware setting, allowing us to interpret topology identification in task-aware settings. Separately, we also propose filter design strategies for processing signals both at the incoming and existing nodes using stochastic attachment models.
Another contribution of this dissertation is to extend graph signal processing with graph filters to the scenario where the graph keeps growing in size with streaming data. We propose online graph filter design which updates the filter online, based on incoming nodes. We design this both for scenarios where the incoming node connectivity is known and unknown. In the unknown connectivity case, we study the performance difference between knowing and not knowing the topology and how the stochastic attachment influences it. We also show that by adapting the stochastic attachment, we can learn faster from the data stream.
Finally,we consider the task of topology decomposition and identification for dynamic networks with fixed nodes but changing edge support. We build a tensor of partially observed adjacency matrices corresponding to such a dynamic topology and express this in terms of underlying latent graphs and their temporal signatures. Furthermore, we account for the time-varying graph signals as a prior to aid identifying these latent graphs and missing components of the topology. These latent graphs are individually and collectively expressive and provide interpretable decompositions along with outperforming traditional structure agnostic low-rank decompositions. ...
The key contribution of this dissertation is proposing methodologies for signal processing over dynamic networks which are aimed at the two aforementioned tasks. For dynamic networks with incoming nodes, we process signals by introducing a parametric stochastic attachment model. In this model, the incoming nodes connect with probability to existing nodes with certain weights. This uncertainty allows us to model input output relations and allows us to cast them in the context of different graph signal processing tasks. We learn the model attachment parameters in a task-aware setting, allowing us to interpret topology identification in task-aware settings. Separately, we also propose filter design strategies for processing signals both at the incoming and existing nodes using stochastic attachment models.
Another contribution of this dissertation is to extend graph signal processing with graph filters to the scenario where the graph keeps growing in size with streaming data. We propose online graph filter design which updates the filter online, based on incoming nodes. We design this both for scenarios where the incoming node connectivity is known and unknown. In the unknown connectivity case, we study the performance difference between knowing and not knowing the topology and how the stochastic attachment influences it. We also show that by adapting the stochastic attachment, we can learn faster from the data stream.
Finally,we consider the task of topology decomposition and identification for dynamic networks with fixed nodes but changing edge support. We build a tensor of partially observed adjacency matrices corresponding to such a dynamic topology and express this in terms of underlying latent graphs and their temporal signatures. Furthermore, we account for the time-varying graph signals as a prior to aid identifying these latent graphs and missing components of the topology. These latent graphs are individually and collectively expressive and provide interpretable decompositions along with outperforming traditional structure agnostic low-rank decompositions. ...
Extending the concepts of classical signal processing to graphs, a wide array of methods have come to the fore, including filtering, reconstruction, classification, and sampling. Existing approaches in graph signal processing consider a known and static topology, i.e., fixed number of nodes and a fixed edge support. Two types of tasks stand out, namely, topology inference, where the edge support along with their weights are estimated from signals; and data processing, where existing data and the known topology are used to perform different tasks. However, such tasks become quite challenging when the network size and support changes over time. Particularly, these challenges involve adapting to the changing topology, data distributions and dealing with unknown topological information. The latter manifests for example, when new nodes are available to attach to the graph but their connectivity is uncertain as is the case in cold start graph-based recommender systems.
The key contribution of this dissertation is proposing methodologies for signal processing over dynamic networks which are aimed at the two aforementioned tasks. For dynamic networks with incoming nodes, we process signals by introducing a parametric stochastic attachment model. In this model, the incoming nodes connect with probability to existing nodes with certain weights. This uncertainty allows us to model input output relations and allows us to cast them in the context of different graph signal processing tasks. We learn the model attachment parameters in a task-aware setting, allowing us to interpret topology identification in task-aware settings. Separately, we also propose filter design strategies for processing signals both at the incoming and existing nodes using stochastic attachment models.
Another contribution of this dissertation is to extend graph signal processing with graph filters to the scenario where the graph keeps growing in size with streaming data. We propose online graph filter design which updates the filter online, based on incoming nodes. We design this both for scenarios where the incoming node connectivity is known and unknown. In the unknown connectivity case, we study the performance difference between knowing and not knowing the topology and how the stochastic attachment influences it. We also show that by adapting the stochastic attachment, we can learn faster from the data stream.
Finally,we consider the task of topology decomposition and identification for dynamic networks with fixed nodes but changing edge support. We build a tensor of partially observed adjacency matrices corresponding to such a dynamic topology and express this in terms of underlying latent graphs and their temporal signatures. Furthermore, we account for the time-varying graph signals as a prior to aid identifying these latent graphs and missing components of the topology. These latent graphs are individually and collectively expressive and provide interpretable decompositions along with outperforming traditional structure agnostic low-rank decompositions.
The key contribution of this dissertation is proposing methodologies for signal processing over dynamic networks which are aimed at the two aforementioned tasks. For dynamic networks with incoming nodes, we process signals by introducing a parametric stochastic attachment model. In this model, the incoming nodes connect with probability to existing nodes with certain weights. This uncertainty allows us to model input output relations and allows us to cast them in the context of different graph signal processing tasks. We learn the model attachment parameters in a task-aware setting, allowing us to interpret topology identification in task-aware settings. Separately, we also propose filter design strategies for processing signals both at the incoming and existing nodes using stochastic attachment models.
Another contribution of this dissertation is to extend graph signal processing with graph filters to the scenario where the graph keeps growing in size with streaming data. We propose online graph filter design which updates the filter online, based on incoming nodes. We design this both for scenarios where the incoming node connectivity is known and unknown. In the unknown connectivity case, we study the performance difference between knowing and not knowing the topology and how the stochastic attachment influences it. We also show that by adapting the stochastic attachment, we can learn faster from the data stream.
Finally,we consider the task of topology decomposition and identification for dynamic networks with fixed nodes but changing edge support. We build a tensor of partially observed adjacency matrices corresponding to such a dynamic topology and express this in terms of underlying latent graphs and their temporal signatures. Furthermore, we account for the time-varying graph signals as a prior to aid identifying these latent graphs and missing components of the topology. These latent graphs are individually and collectively expressive and provide interpretable decompositions along with outperforming traditional structure agnostic low-rank decompositions.
Temporal networks arise due to certain dynamics influencing their connections or due to the change in interactions between the nodes themselves, as seen for example in social networks. Such evolution can be algebraically represented by a three-way tensor, which lends itself to using tensor decompositions to study the underpinning factors driving the network evolution. Low rank tensor decompositions have been used for temporal networks but mostly with a focus on downstream tasks and have been seldom used to study the temporal network itself. Here, we use the tensor decomposition to identify a limited number of key mode graphs that can explain the temporal network, and which linear combination can represent its evolution. For this, we put for a novel graph-based tensor decomposition approach where we impose a graph structure on the two modes of the tensor and a smoothness on the temporal dimension. We use these mode graphs to investigate the temporal network and corroborate their usability for network reconstruction and link prediction.
...
Temporal networks arise due to certain dynamics influencing their connections or due to the change in interactions between the nodes themselves, as seen for example in social networks. Such evolution can be algebraically represented by a three-way tensor, which lends itself to using tensor decompositions to study the underpinning factors driving the network evolution. Low rank tensor decompositions have been used for temporal networks but mostly with a focus on downstream tasks and have been seldom used to study the temporal network itself. Here, we use the tensor decomposition to identify a limited number of key mode graphs that can explain the temporal network, and which linear combination can represent its evolution. For this, we put for a novel graph-based tensor decomposition approach where we impose a graph structure on the two modes of the tensor and a smoothness on the temporal dimension. We use these mode graphs to investigate the temporal network and corroborate their usability for network reconstruction and link prediction.
Graph filters are a staple tool for processing signals over graphs in a multitude of downstream tasks. However, they are commonly designed for graphs with a fixed number of nodes, despite real-world networks typically grow over time. This topological evolution is often known up to a stochastic model, thus, making conventional graph filters ill-equipped to withstand such topological changes, their uncertainty, as well as the dynamic nature of the incoming data. To tackle these issues, we propose an online graph filtering framework by relying on online learning principles. We design filters for scenarios where the topology is both known and unknown, including a learner adaptive to such evolution. We conduct a regret analysis to highlight the role played by the different components such as the online algorithm, the filter order, and the growing graph model. Numerical experiments with synthetic and real data corroborate the proposed approach for graph signal inference tasks and show a competitive performance w.r.t. baselines and state-of-the-art alternatives.
...
Graph filters are a staple tool for processing signals over graphs in a multitude of downstream tasks. However, they are commonly designed for graphs with a fixed number of nodes, despite real-world networks typically grow over time. This topological evolution is often known up to a stochastic model, thus, making conventional graph filters ill-equipped to withstand such topological changes, their uncertainty, as well as the dynamic nature of the incoming data. To tackle these issues, we propose an online graph filtering framework by relying on online learning principles. We design filters for scenarios where the topology is both known and unknown, including a learner adaptive to such evolution. We conduct a regret analysis to highlight the role played by the different components such as the online algorithm, the filter order, and the growing graph model. Numerical experiments with synthetic and real data corroborate the proposed approach for graph signal inference tasks and show a competitive performance w.r.t. baselines and state-of-the-art alternatives.
Simplicial convolutional filters can process signals defined over levels of a simplicial complex such as nodes, edges, triangles, and so on with applications in e.g., flow prediction in transportation or financial networks. However, the underlying topology expands over time in a way that new edges and triangles form. For example, in a transportation network, a new connection between two locations is newly built, or in a currency exchange market, two currencies can be exchanged without an intermediate currency that can be understood as a new edge between them. To handle the streaming nature of data, we propose an online prediction for edge flows which generalizes to other higher-order simplicial signals. This is achieved by updating the filter coefficients via an online gradient descent with a provable sub-linear regret relative to the simplicial filter optimized over the whole sequence of edge flows. The update of the filter coefficients associated with the lower and upper Hodge Laplacians can be uncoupled in general. We test the online edge flow prediction on an expanding synthetic simplicial complex and a coauthorship complex showing a close performance to the offline counterpart.
...
Simplicial convolutional filters can process signals defined over levels of a simplicial complex such as nodes, edges, triangles, and so on with applications in e.g., flow prediction in transportation or financial networks. However, the underlying topology expands over time in a way that new edges and triangles form. For example, in a transportation network, a new connection between two locations is newly built, or in a currency exchange market, two currencies can be exchanged without an intermediate currency that can be understood as a new edge between them. To handle the streaming nature of data, we propose an online prediction for edge flows which generalizes to other higher-order simplicial signals. This is achieved by updating the filter coefficients via an online gradient descent with a provable sub-linear regret relative to the simplicial filter optimized over the whole sequence of edge flows. The update of the filter coefficients associated with the lower and upper Hodge Laplacians can be uncoupled in general. We test the online edge flow prediction on an expanding synthetic simplicial complex and a coauthorship complex showing a close performance to the offline counterpart.
Current spatiotemporal learning methods for complex data exploit the graph structure as an inductive bias to restrict the function space and improve data and computation efficiency. However, these methods work principally on graphs with a fixed size, whereas in several applications there are expanding graphs where new nodes join the network; e.g., new sensors joining a sensor network or new users joining a recommender system. This paper focuses on the non-trivial extension of spatiotemporal methods to this setting, where now it is key to jointly capture both the topological and signal dynamics. Specifically, it considers a graph vector autoregressive (GVAR) model for multivariate time series. The GVAR is a multivariate linear model that leverages a bank of graph filters allowing scalability and data efficiency. To account for the dynamic nature of the graphs, the filters’s parameters are learned on-the-fly via adaptive gradient descent with provable sub-linear regret. Numerical results on both synthetic and real data corroborate the proposed method.
...
Current spatiotemporal learning methods for complex data exploit the graph structure as an inductive bias to restrict the function space and improve data and computation efficiency. However, these methods work principally on graphs with a fixed size, whereas in several applications there are expanding graphs where new nodes join the network; e.g., new sensors joining a sensor network or new users joining a recommender system. This paper focuses on the non-trivial extension of spatiotemporal methods to this setting, where now it is key to jointly capture both the topological and signal dynamics. Specifically, it considers a graph vector autoregressive (GVAR) model for multivariate time series. The GVAR is a multivariate linear model that leverages a bank of graph filters allowing scalability and data efficiency. To account for the dynamic nature of the graphs, the filters’s parameters are learned on-the-fly via adaptive gradient descent with provable sub-linear regret. Numerical results on both synthetic and real data corroborate the proposed method.
Performing signal processing over graphs requires knowledge of the underlying fixed topology. However, graphs often grow in size with new nodes appearing over time, whose connectivity is typically unknown; hence, making more challenging the downstream tasks in applications like cold start recommendation. We address such a challenge for signal interpolation at the incoming nodes blind to the topological connectivity of the specific node. Specifically, we propose a stochastic attachment model for incoming nodes parameterized by the attachment probabilities and edge weights. We estimate these parameters in a data-driven fashion by relying only on the attachment behaviour of earlier incoming nodes with the goal of interpolating the signal value. We study the non-convexity of the problem at hand, derive conditions when it can be marginally convexified, and propose an alternating projected descent approach between estimating the attachment probabilities and the edge weights. Numerical experiments with synthetic and real data dealing in cold start collaborative filtering corroborate our findings.
...
Performing signal processing over graphs requires knowledge of the underlying fixed topology. However, graphs often grow in size with new nodes appearing over time, whose connectivity is typically unknown; hence, making more challenging the downstream tasks in applications like cold start recommendation. We address such a challenge for signal interpolation at the incoming nodes blind to the topological connectivity of the specific node. Specifically, we propose a stochastic attachment model for incoming nodes parameterized by the attachment probabilities and edge weights. We estimate these parameters in a data-driven fashion by relying only on the attachment behaviour of earlier incoming nodes with the goal of interpolating the signal value. We study the non-convexity of the problem at hand, derive conditions when it can be marginally convexified, and propose an alternating projected descent approach between estimating the attachment probabilities and the edge weights. Numerical experiments with synthetic and real data dealing in cold start collaborative filtering corroborate our findings.
Data processing over graphs is usually done on graphs of fixed size. However, graphs often grow with new nodes arriving over time. Knowing the connectivity information of these nodes, and thus, the expanded graph is crucial for processing data over the expanded graph. In its absence, its inference and the subsequent data processing become essential. This paper provides contributions along this direction by considering task-driven data processing for incoming nodes without connectivity information. We model the incoming node attachment as a random process dictated by the parameterized vectors of probabilities and weights of attachment. The attachment is driven by the existing graph topology, the corresponding graph signal, and an associated processing task. We consider two such tasks, one of interpolation at the incoming node, and that of graph signal smoothness. We show that the model bounds implicitly the spectral perturbation between the nominal topology of the expanded graph and the drawn realizations. In the absence of connectivity information our topology, task, and data-aware stochastic attachment performs better than purely data-driven and topology driven stochastic attachment rules, as is confirmed by numerical results over synthetic and real data.
...
Data processing over graphs is usually done on graphs of fixed size. However, graphs often grow with new nodes arriving over time. Knowing the connectivity information of these nodes, and thus, the expanded graph is crucial for processing data over the expanded graph. In its absence, its inference and the subsequent data processing become essential. This paper provides contributions along this direction by considering task-driven data processing for incoming nodes without connectivity information. We model the incoming node attachment as a random process dictated by the parameterized vectors of probabilities and weights of attachment. The attachment is driven by the existing graph topology, the corresponding graph signal, and an associated processing task. We consider two such tasks, one of interpolation at the incoming node, and that of graph signal smoothness. We show that the model bounds implicitly the spectral perturbation between the nominal topology of the expanded graph and the drawn realizations. In the absence of connectivity information our topology, task, and data-aware stochastic attachment performs better than purely data-driven and topology driven stochastic attachment rules, as is confirmed by numerical results over synthetic and real data.
Diffusion-based semi-supervised learning on graphs consists of diffusing labeled information of a few nodes to infer the labels on the remaining ones. The performance of these methods heavily relies on the initial labeled set, which is either generated randomly or using heuristics. The first sometimes leads to unsatisfactory results because random labeling has no guarantees to label all classes while heuristic methods only yield a good performance when multiple recursive training stages are possible. In this paper, we put forth a new paradigm for one-shot active semi-supervised learning for graph diffusions. We rephrase active learning as the problem of selecting the output labels from a label propagation model. Subsequently, we develop two methods to solve this problem and label the nodes. The first method assumes there are only a few starting labels and relies on projected compressive sensing to build the label set. The second method drops the assumption of a few starting labels and builds on sparse sensing techniques to label a few nodes. Both methods have solid mathematical grounds in signal processing and require a single training phase. Numerical results on three scenarios corroborate our findings and showcase the improved performance compared with the state of the art.
...
Diffusion-based semi-supervised learning on graphs consists of diffusing labeled information of a few nodes to infer the labels on the remaining ones. The performance of these methods heavily relies on the initial labeled set, which is either generated randomly or using heuristics. The first sometimes leads to unsatisfactory results because random labeling has no guarantees to label all classes while heuristic methods only yield a good performance when multiple recursive training stages are possible. In this paper, we put forth a new paradigm for one-shot active semi-supervised learning for graph diffusions. We rephrase active learning as the problem of selecting the output labels from a label propagation model. Subsequently, we develop two methods to solve this problem and label the nodes. The first method assumes there are only a few starting labels and relies on projected compressive sensing to build the label set. The second method drops the assumption of a few starting labels and builds on sparse sensing techniques to label a few nodes. Both methods have solid mathematical grounds in signal processing and require a single training phase. Numerical results on three scenarios corroborate our findings and showcase the improved performance compared with the state of the art.
GiB
A game theory inspired binarization technique for degraded document images
Document image binarization classifies each pixel in an input document image as either foreground or background under the assumption that the document is pseudo binary in nature. However, noise introduced during acquisition or due to aging or handling of the document can make binarization a challenging task. This paper presents a novel game theory inspired binarization technique for degraded document images. A two-player, non-zero-sum, non-cooperative game is designed at the pixel level to extract the local information, which is then fed to a K -means algorithm to classify a pixel as foreground or background. We also present a preprocessing step that is performed to eliminate the intensity variation that often appears in the background and a post-processing step to refine the results. The method is tested on seven publicly available datasets, namely, DIBCO 2009-14 and 2016. The experimental results show that game theory inspired binarization outperforms competing state-of-the-art methods in most cases.
...
Document image binarization classifies each pixel in an input document image as either foreground or background under the assumption that the document is pseudo binary in nature. However, noise introduced during acquisition or due to aging or handling of the document can make binarization a challenging task. This paper presents a novel game theory inspired binarization technique for degraded document images. A two-player, non-zero-sum, non-cooperative game is designed at the pixel level to extract the local information, which is then fed to a K -means algorithm to classify a pixel as foreground or background. We also present a preprocessing step that is performed to eliminate the intensity variation that often appears in the background and a post-processing step to refine the results. The method is tested on seven publicly available datasets, namely, DIBCO 2009-14 and 2016. The experimental results show that game theory inspired binarization outperforms competing state-of-the-art methods in most cases.