Search

We propose a decentralised "local2global"' approach to graph representation learning, that one can a-priori use to scale any embedding technique. Our local2global approach proceeds by first dividing the input graph into overlapping subgraphs (or "patches") and training local representations for each patch independently. In a second step, we combine the local representations into a globally consistent representation by estimating the set of rigid motions that best align the local representations using information from the patch overlaps, via group synchronization. A key distinguishing feature of local2global relative to existing work is that patches are trained independently without the need for the often costly parameter synchronization during distributed training. This allows local2global to scale to large-scale industrial applications, where the input graph may not even fit into memory and may be stored in a distributed manner. We apply local2global on data sets of different sizes and show that our approach achieves a good trade-off between scale and accuracy on edge reconstruction and semi-supervised classification. We also consider the downstream task of anomaly detection and show how one can use local2global to highlight anomalies in cybersecurity networks., Comment: 25 pages, 6 figures. arXiv admin note: substantial text overlap with arXiv:2107.12224

We propose a graph spectrum-based Gaussian process for prediction of signals defined on nodes of the graph. The model is designed to capture various graph signal structures through a highly adaptive kernel that incorporates a flexible polynomial function in the graph spectral domain. Unlike most existing approaches, we propose to learn such a spectral kernel, where the polynomial setup enables learning without the need for eigen-decomposition of the graph Laplacian. In addition, this kernel has the interpretability of graph filtering achieved by a bespoke maximum likelihood learning algorithm that enforces the positivity of the spectrum. We demonstrate the interpretability of the model in synthetic experiments from which we show the various ground truth spectral filters can be accurately recovered, and the adaptability translates to superior performances in the prediction of real-world graph data of various characteristics., 13 pages, 5 Figures

Hypergraph structure learning, which aims to learn the hypergraph structures from the observed signals to capture the intrinsic high-order relationships among the entities, becomes crucial when a hypergraph topology is not readily available in the datasets. There are two challenges that lie at the heart of this problem: 1) how to handle the huge search space of potential hyperedges, and 2) how to define meaningful criteria to measure the relationship between the signals observed on nodes and the hypergraph structure. In this paper, for the first challenge, we adopt the assumption that the ideal hypergraph structure can be derived from a learnable graph structure that captures the pairwise relations within signals. Further, we propose a hypergraph structure learning framework HGSL with a novel dual smoothness prior that reveals a mapping between the observed node signals and the hypergraph structure, whereby each hyperedge corresponds to a subgraph with both node signal smoothness and edge signal smoothness in the learnable graph structure. Finally, we conduct extensive experiments to evaluate HGSL on both synthetic and real world datasets. Experiments show that HGSL can efficiently infer meaningful hypergraph topologies from observed signals.

Diversity of physical encounters and social interactions in urban environments are known to spur economic productivity and innovation in cities, while also to foster social capital and resilience of communities. However, mobility restrictions during the pandemic have forced people to substantially reduce urban physical encounters, raising questions on the social implications of such behavioral changes. In this paper, we study how the income diversity of urban encounters have changed during different periods throughout the pandemic, using a large-scale, privacy-enhanced mobility dataset of more than one million anonymized mobile phone users in four large US cities, collected across three years spanning before and during the pandemic. We find that the diversity of urban encounters have substantially decreased (by 15% to 30%) during the pandemic and has persisted through late 2021, even though aggregated mobility metrics have recovered to pre-pandemic levels. Counterfactual analyses show that while the reduction of outside activities (higher rates of staying at home) was a major factor that contributed to decreased diversity in the early stages of the pandemic, behavioral changes including lower willingness to explore new places and changes in visitation preferences further worsened the long-term diversity of encounters. Our findings suggest that the pandemic could have long-lasting negative effects on urban income diversity, and provide implications for managing the trade-off between the stringency of COVID-19 policies and the diversity of urban encounters as we move beyond the pandemic., main: 13 pages, 4 figures; supplementary: 46 pages, 25 figures, 14 tables

Vibration analysis is proved effective for bearing performance degradation assessment (PDA). In most of the current studies, vibration signals from one monitored bearing are collected and analyzed. However, in the real-industrial applications, bearings in pairs or even more are often mounted on the same shaft. Therefore, the collected vibration signal is actually a mixed signal from multiple bearings. In this study, our recently developed method named kernel joint approximate diagonalization of eigenmatrices (JADE) is investigated for PDA under this situation. Due to the nonlinear mapping capability of the kernel method and the blind source separation ability of the JADE algorithm, the proposed method could extract latent source features that are accurately reflecting the performance degradation from the mixed vibration signal. The method includes the following three steps: 1) statistical features are calculated and transformed into the high-dimension through nonlinear mapping. 2) Latent source features are obtained by exploiting the fourth-order moments. 3) The two-class model (SS) is proposed to assess the difference between the monitored sample and the healthy sample, which could reflect the bearing health condition. The effectiveness of this method is verified using two experimental cases within four coaxial bearings. Comparative results show that the proposed method could identify the defect earlier than the traditional rms feature and the traditional JADE method and the principal component analysis method.

Photonic Ising machine is a new paradigm of optical computing, which is based on the characteristics of light wave propagation, parallel processing and low loss transmission. Thus, the process of solving the combinatorial optimization problems can be accelerated through photonic/optoelectronic devices. In this work, we have proposed and demonstrated the so-called Phase-Encoding and Intensity Detection Ising Annealer (PEIDIA) to solve arbitrary Ising problems on demand. The PEIDIA is based on the simulated annealing algorithm and requires only one step of optical linear transformation with simplified Hamiltonian calculation. With PEIDIA, the Ising spins are encoded on the phase term of the optical field and only intensity detection is required during the solving process. As a proof of principle, several 20-dimensional Ising problems have been solved with high ground state probability (0.98 within 1000 iterations for the antiferromagnetic cubic model, > 0.99 within 4000 iterations for two random spin-glass models, respectively).

An optical–electronic hybrid convolutional neural network (CNN) system is proposed and investigated for its parallel processing capability and system design robustness. It is regarded as a practical way to implement real-time optical computing. In this paper, we propose a complex-valued modulation method based on an amplitude-only liquid-crystal-on-silicon spatial light modulator and a fixed four-level diffractive optical element. A comparison of computational results of convolutions between different modulation methods in the Fourier plane shows the feasibility of the proposed complex-valued modulation method. A hybrid CNN model with one convolutional layer of multiple channels is proposed and trained electrically for different classification tasks. Our simulation results show that this model has a classification accuracy of 97.55% for MNIST, 88.81% for Fashion MNIST, and 56.16% for Cifar10, which outperforms models using only amplitude or phase modulation and is comparable to the ideal complex-valued modulation method.

The construction of a meaningful graph topology plays a crucial role in the effective representation, processing, analysis and visualization of structured data. When a natural choice of the graph is not readily available from the data sets, it is thus desirable to infer or learn a graph topology from the data. In this tutorial overview, we survey solutions to the problem of graph learning, including classical viewpoints from statistics and physics, and more recent approaches that adopt a graph signal processing (GSP) perspective. We further emphasize the conceptual similarities and differences between classical and GSP-based graph inference methods, and highlight the potential advantage of the latter in a number of theoretical and practical scenarios. We conclude with several open issues and challenges that are keys to the design of future signal processing and machine learning algorithms for learning graphs from data., corrected several imprecise statements in previous versions of the manuscript as well as in the article of the same title in the May 2019 issue of IEEE Signal Processing Magazine (vol. 36, no. 3, pp. 44-63, May 2019)

Traditional understanding of urban income segregation is largely based on static coarse-grained residential patterns. However, these do not capture the income segregation experience implied by the rich social interactions that happen in places that may relate to individual choices, opportunities, and mobility behavior. Using a large-scale high-resolution mobility data set of 4.5 million mobile phone users and 1.1 million places in 11 large American cities, we show that income segregation experienced in places and by individuals can differ greatly even within close spatial proximity. To further understand these fine-grained income segregation patterns, we introduce a Schelling extension of a well-known mobility model, and show that experienced income segregation is associated with an individual’s tendency to explore new places (place exploration) as well as places with visitors from different income groups (social exploration). Interestingly, while the latter is more strongly associated with demographic characteristics, the former is more strongly associated with mobility behavioral variables. Our results suggest that mobility behavior plays an important role in experienced income segregation of individuals. To measure this form of income segregation, urban researchers should take into account mobility behavior and not only residential patterns., Urban income segregation is often discussed in terms of where people live. Here, the authors show that the way people experience income segregation is also associated with their mobility patterns and the places they visit.

A correction to this paper has been published: https://doi.org/10.1007/s43926-021-00013-8

Compressive imaging senses optically encoded high-dimensional scene data with far fewer measurements and then performs reconstruction via appropriate algorithms. In this paper, we present a novel noniterative end-to-end deep learning-based framework for compressive imaging, dubbed CoCoCs. In comparison to existing approaches, we extend the pipeline by co-optimizing the recovery algorithm with optical coding as well as cascaded high-level computer vision tasks to boost the quality of the reconstruction. We demonstrate the proposed framework on two typical compressive imaging systems, i.e., single pixel imaging and snapshot video compressive imaging. Extensive results, including conventional image quality criteria, mean opinion scores, and accuracy in image classification and motion recognition, confirm that CoCoCs can yield realistic images and videos, which are friendly to both human viewing and computer vision. We hope CoCoCs will give impetus to bridge the gap between compressive imagers and computer vision and the perception of human.

Learning the topology of a graph from available data is of great interest in many emerging applications. Some examples are social networks, internet of things networks (intelligent IoT and industrial IoT), biological connection networks, sensor networks and traffic network patterns. In this paper, a graph topology inference approach is proposed to learn the underlying graph structure from a given set of noisy multi-variate observations, which are modeled as graph signals generated from a Gaussian Markov Random Field (GMRF) process. A factor analysis model is applied to represent the graph signals in a latent space where the basis is related to the underlying graph structure. An optimal graph filter is also developed to recover the graph signals from noisy observations. In the final step, an optimization problem is proposed to learn the underlying graph topology from the recovered signals. Moreover, a fast algorithm employing the proximal point method has been proposed to solve the problem efficiently. Experimental results employing both synthetic and real data show the effectiveness of the proposed method in recovering the signals and inferring the underlying graph.

Graph neural networks are experiencing a surge of popularity within the machine learning community due to their ability to adapt to non-Euclidean domains and instil inductive biases. Despite this, their stability, i.e., their robustness to small perturbations in the input, is not yet well understood. Although there exists some results showing the stability of graph neural networks, most take the form of an upper bound on the magnitude of change due to a perturbation in the graph topology. However, the change in the graph topology captured in existing bounds tend not to be expressed in terms of structural properties, limiting our understanding of the model robustness properties. In this work, we develop an interpretable upper bound elucidating that graph neural networks are stable to rewiring between high degree nodes. This bound and further research in bounds of similar type provide further understanding of the stability properties of graph neural networks., To appear at the 46th International Conference on Acoustics, Speech and Signal Processing (ICASSP 2021)

Spectral graph filters are a key component in state-of-the-art machine learning models used for graph-based learning, such as graph neural networks. For certain tasks stability of the spectral graph filters is important for learning suitable representations. Understanding the type of structural perturbation to which spectral graph filters are robust lets us reason as to when we may expect them to be well suited to a learning task. In this work, we first prove that polynomial graph filters are stable with respect to the change in the normalised graph Laplacian matrix. We then show empirically that properties of a structural perturbation, specifically the relative locality of the edges removed in a binary graph, effect the change in the normalised graph Laplacian. Together, our results have implications on designing robust graph filters and representations under structural perturbation.

In an increasingly connected global market, news sentiment towards one company may not only indicate its own market performance, but can also be associated with a broader movement on the sentiment and performance of other companies from the same or even different sectors. In this paper, we apply NLP techniques to understand news sentiment of 87 companies among the most reported on Reuters for a period of seven years. We investigate the propagation of such sentiment in company networks and evaluate the associated market movements in terms of stock price and volatility. Our results suggest that, in certain sectors, strong media sentiment towards one company may indicate a significant change in media sentiment towards related companies measured as neighbours in a financial network constructed from news co-occurrence. Furthermore, there exists a weak but statistically significant association between strong media sentiment and abnormal market return as well as volatility. Such an association is more significant at the level of individual companies, but nevertheless remains visible at the level of sectors or groups of companies., Comment: 12 pages, 5 figures, 1 table (29 pages including References and Appendices). Published in Scientific Reports 11

The smart factory of Industry 4.0 has been regarded as a solution for handling the increasing production complexity caused by growing global economy and demand for customized products. Besides, it will make the interactions between humans, machines, and products become a highly competitive area for market capitalization in the near feature. Nowadays, cloud computing with the high performance of computing and self-service access plays an important role in realizing smart factor. To minimize the overall cost of company in a heterogeneous cloud environment, including multiple public clouds, while ensuring a proper level of quality-of-service, task placement across multiple public clouds is a critical problem, where task deadlines and long-haul data transmission costs between smart factory and different clouds must be considered. We formulate this task placement problem as an integer linear program (ILP) to minimize company cost under the task deadline constraint. With extensive simulations, we evaluate the performance of our proposed ILP model in heterogeneous public clouds with finite and infinite resources.

Optical diffractive deep neural network (OD2NN) is an optical machine learning framework that utilizes diffraction on the cascaded diffractive surfaces to perform an arbitrary function. Compared with the deep neural networks (DNNs) implemented in electronic domain, proof-of-principle demonstrations of OD2NNs show promising advantages in terms of speed and power efficiency. However, the classification accuracy of the demonstrated OD2NN has been limited by the absence of optical nonlinear operations, even in the hybrid OD2NNs which are integrated with electronic neural networks. Here, we propose a novel training framework to improve the classification accuracy of the OD2NNs without employing any nonlinear physical elements. In this framework, the hybrid OD2NN with a fully connected electronic layer integrated (hybrid) are preferred and knowledge distillation (KD) and stochastic gradient descent β-Lasso (SGD-β-Lasso) joint-training are used. A blind testing classification accuracy of 70.19% and 85.17% have been obtained for Cifar-10 and Cats vs. Dogs dataset, respectively, which is the state-of-the-art accuracy achieved by the hybrid OD2NN so far. In addition, the proposed framework can significantly reduce the complexity of hardware fabrication and layers alignment since the hybrid OD2NN only consists of 5 diffractive layers. This work take a big step forward the application of the OD2NN in realistic scenarios.

The network traffic matrix is widely used in network operation and management. It is therefore of crucial importance to analyze the components and the structure of the network traffic matrix, for which several mathematical approaches such as Principal Component Analysis (PCA) were proposed. In this paper, we first argue that PCA performs poorly for analyzing traffic matrix that is polluted by large volume anomalies, and then propose a new decomposition model for the network traffic matrix. According to this model, we carry out the structural analysis by decomposing the network traffic matrix into three sub-matrices, namely, the deterministic traffic, the anomaly traffic and the noise traffic matrix, which is similar to the Robust Principal Component Analysis (RPCA) problem previously studied in [13]. Based on the Relaxed Principal Component Pursuit (Relaxed PCP) method and the Accelerated Proximal Gradient (APG) algorithm, we present an iterative approach for decomposing a traffic matrix, and demonstrate its efficiency and flexibility by experimental results. Finally, we further discuss several features of the deterministic and noise traffic. Our study develops a novel method for the problem of structural analysis of the traffic matrix, which is robust against pollution of large volume anomalies., Accepted to Elsevier Computer Networks

This paper analyzes millions of credit card transaction records during several months for tens of thousands of individuals from two different countries. The study shows that, purchase patterns are strongly correlated with important societal indices such as socioeconomic status and political inclination. The results suggest the possibility of understanding and predicting the evolution of such societal indices from purchase behavioral patterns, potentially at high temporal and spatial resolutions.

The problem of graph learning concerns the construction of an explicit topological structure revealing the relationship between nodes representing data entities, which plays an increasingly important role in the success of many graph-based representations and algorithms in the field of machine learning and graph signal processing. In this paper, we propose a novel graph learning framework that incorporates the node-side and observation-side information, and in particular the covariates that help to explain the dependency structures in graph signals. To this end, we consider graph signals as functions in the reproducing kernel Hilbert space associated with a Kronecker product kernel, and integrate functional learning with smoothness-promoting graph learning to learn a graph representing the relationship between nodes. The functional learning increases the robustness of graph learning against missing and incomplete information in the graph signals. In addition, we develop a novel graph-based regularisation method which, when combined with the Kronecker product kernel, enables our model to capture both the dependency explained by the graph and the dependency due to graph signals observed under different but related circumstances, e.g. different points in time. The latter means the graph signals are free from the i.i.d. assumptions required by the classical graph learning models. Experiments on both synthetic and real-world data show that our methods outperform the state-of-the-art models in learning a meaningful graph topology from graph signals, in particular under heavy noise, missing values, and multiple dependency., Comment: 13 pages, with extra 3-page appendices

Effective information analysis generally boils down to properly identifying the structure or geometry of the data, which is often represented by a graph. In some applications, this structure may be partly determined by design constraints or pre-determined sensing arrangements, like in road transportation networks for example. In general though, the data structure is not readily available and becomes pretty difficult to define. In particular, the global smoothness assumptions, that most of the existing works adopt, are often too general and unable to properly capture localized properties of data. In this paper, we go beyond this classical data model and rather propose to represent information as a sparse combination of localized functions that live on a data structure represented by a graph. Based on this model, we focus on the problem of inferring the connectivity that best explains the data samples at different vertices of a graph that is a priori unknown. We concentrate on the case where the observed data is actually the sum of heat diffusion processes, which is a quite common model for data on networks or other irregular structures. We cast a new graph learning problem and solve it with an efficient nonconvex optimization algorithm. Experiments on both synthetic and real world data finally illustrate the benefits of the proposed graph learning framework and confirm that the data structure can be efficiently learned from data observations only. We believe that our algorithm will help solving key questions in diverse application domains such as social and biological network analysis where it is crucial to unveil proper geometry for data understanding and inference.

Customer retention is crucial in a variety of businesses as acquiring new customers is often more costly than keeping the current ones. As a consequence, churn prediction has attracted great attention from both the business and academic worlds. Traditional efforts in the financial domain mainly focus on domain specific variables such as product ownership or service usage aggregation, however, without considering dynamic behavioral patterns of customers’ financial transactions. In this paper, we attempt to fill in this gap by investigating the spatio-temporal patterns and entropy of choices underlying the customers’ financial decisions, and their relations to customer churning activities. Inspired by previous works in the emerging field of computational social science, we built a prediction model based on spatio-temporal and choice behavioral traits using individual transaction records. Our results show that proposed dynamic behavioral models could predict churn decisions significantly better than traditionally considered factors such as demographic-based features, and that this effect remains consistent across multiple data sets and various churn definitions. We further study the relative importance of the various behavioral features in churn prediction, and how the predictive power varies across different demographic groups. More generally, the proposed features can also be applied to churn prediction in other domains where spatio-temporal behavioral data are available. Keywords: Churn prediction, Customer behavior, Spatio-temporal patterns, Credit card data

Societal unrest and similar events are important for societies, but it is often difficult to quantify their effects on individuals, hindering a timely and effective policy-making in emergencies and in particular localized social shocks such as protests. Traditionally, effects are assessed through economic indicators or surveys with relatively low temporal and spatial resolutions. In this work, we compute two behavioral indexes, based on the use of credit card transaction data, for measuring the economic effects of a series of protests on consumer actions and personal consumption. Using data from a metropolitan area in an OECD country, we show that protests affect consumers’ shopping frequency and spending, but in noticeably different ways. The effects show strong temporal and spatial patterns, vary between neighborhoods and customers of different socio-demographical characteristics as well as between merchants of different categories, and suggest interesting subtleties in purchase behavior such as displaced or delayed shopping activities. Our method can generally serve for the real-time monitoring of the effects of major social shocks or events on urban economy and consumer sentiment, providing high-resolution and cost-effective measurement tools to complement traditional economic indicators. Keywords: Social shocks; Economic effect; Consumer behavior; Spatiotemporal pattern; Credit card transaction

Phenomena such as “small-world” and “six degrees of separation” reveal the connectivity between individuals that are seemingly unrelated in the society. Beyond merely connectivity, it has been shown in recent years that social contagion exists in online interactions. Along this line of investigation, we are interested in the subtle and invisible social influence on real-world behavior across offline communication networks. In particular, we study how social influence propagates and triggers behavioral change, and how such effect expands deeply across the social network in a way similar to the physical phenomenon of ripples across the water. To this end, we analyze a large-scale one-month international event in Andorra using nation-wide mobile phone data, and investigate the change in the likelihood of attending the event for people that have been influenced by and are of different social distances from the attendees. Our results suggest that social influence exhibits the ripple effect, decaying across social distances from the source but persisting up to six degrees of separation in the social network. We further show that such influence decays as communication delay increases and communication intensity decreases, and that it is stronger among people who are more explorative geographically. Our findings may have important implications in a number of domains, such as marketing, public health, and social mobilizations.

Appendix 1. Performance Comparison of Models Trained with Various 1 Churn Definitions. Various churn definition variants are listed and performance summaries of models built with these churn definitions are provided. The significance test results of the pair-wise comparisons of feature sets as well as a detailed list of parameters applied in the prediction models are included. (PDF 113 kB)