Search

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.

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.

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.

Urban income segregation is a widespread phenomenon that challenges societies across the globe. Classical studies on segregation have largely focused on the geographic distribution of residential neighborhoods rather than on patterns of social behaviors and interactions. In this study, we analyze segregation in economic and social interactions by observing credit card transactions and Twitter mentions among thousands of individuals in three culturally different metropolitan areas. We show that segregated interaction is amplified relative to the expected effects of geographic segregation in terms of both purchase activity and online communication. Furthermore, we find that segregation increases with difference in socio-economic status but is asymmetric for purchase activity, i.e., the amount of interaction from poorer to wealthier neighborhoods is larger than vice versa. Our results provide novel insights into the understanding of behavioral segregation in human interactions with significant socio-political and economic implications.

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.

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

We simplify the classic convolutional neural network (CNN) of handwriting recognition - LetNet-5, and achieve classification based on the dataset MNIST by using an interconnected system of inverse-designed optical scattering units. © 2020 The Author(s)

Social behaviours emerge from the exchange of information among individuals—constrained by and reciprocally influencing the structure of information flows. The Internet radically transformed communication by democratizing broadcast capabilities and enabling easy and borderless formation of new acquaintances. However, actual information flows are heterogeneous and confined to self-organized echo-chambers. Of central importance to the future of society is understanding how existing physical segregation affects online social fragmentation. Here, we show that the virtual space is a reflection of the geographical space where physical interactions and proximity-based social learning are the main transmitters of ideas. We show that online interactions are segregated by income just as physical interactions are, and that physical separation reflects polarized behaviours beyond culture or politics. Our analysis is consistent with theoretical concepts suggesting polarization is associated with social exposure that reinforces within-group homogenization and between-group differentiation, and they together promote social fragmentation in mirrored physical and virtual spaces.

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

The understanding and modeling of human purchase behavior in city environment can have important implications in the study of urban economy and in the design and organization of cities. In this article, we study human purchase behavior at the community level and argue that people who live in different communities but work at close-by locations could act as “social bridges” between the respective communities and that they are correlated with similarity in community purchase behavior. We provide empirical evidence by studying millions of credit card transaction records for tens of thousands of individuals in a city environment during a period of three months. More specifically, we show that the number of social bridges between communities is a much stronger indicator of similarity in their purchase behavior than traditionally considered factors such as income and sociodemographic variables. Our findings also suggest that such an effect varies across different merchant categories, that the presence of female customers in social bridges is a stronger indicator compared to that of their male counterparts, and that there seems to be a geographical constraint for this effect, all of which may have implications in the studies of urban economy and data-driven urban planning.

We study traffic scheduling in optical-electrical switching fabrics in Data Center Networks (DCNs) based on multi-stage Clos networks to minimize data transmission delay and ensure 100% throughput. The existing classical ADAPT scheduling algorithm can minimize the speedup (the radio of the internal transmission rate inside the optical switch to the external line-rate), but still has some idle time-slots (i.e., not-yet-utilized slots), especially for uneven traffic distribution. To solve this issue, we propose a Multi-Hop Routing and Scheduling (MHRS) algorithm by utilizing idle bandwidths without increasing the speedup in multi-stage Clos networks for DCNs. Similar to ADAPT, MHRS divides traffic matrix into quotient and residual matrices. It includes two steps: single-hop scheduling as the first and multi-hop scheduling as the second. The first step is to schedule packets in the residual matrix to the idle time-slots of configuration matrices generated from the quotient matrix. When those packets cannot be directly scheduled in the first step, the second step invokes multi-hop scheduling process by making a detour for transmission. Simulation results confirm that MHRS can achieve a better performance in multi-stage Clos networks as compared with ADAPT.

Orthogonal frequency-division multiplexing (OFDM) has been proposed as an enabling technique for elastic optical networks to support heterogeneous traffic demands by enabling rate and modulation adaptive bandwidth allocation. The authors investigate the energy efficiency of optical OFDM-based networks. A mixed integer linear programming model is developed to minimise the total power consumption of rate and modulation adaptive optical OFDM networks. Considering a symmetric traffic, the results show that optical OFDM-based networks can save up to 31% of the total network power consumption compared to conventional Internet protocol over wavelength division multiplexing (WDM) networks. Considering the power consumption of the optical layer, the optical OFDM-based network saves up to 55% of the optical layer power consumption. The results also show that under an asymmetric traffic scenario, where more traffic is destined to or originates from popular nodes, for example data centres, the power savings achieved by the optical OFDM-based networks are limited as the higher traffic demands to and from data centres reduce the bandwidth wastage associated with conventional WDM networks. Furthermore, the achievable power savings through data compression have been investigated, considering an optical OFDM-based network.

We summarize the various techniques developed by the GreenTouch consortium over the past 5 years to minimize core network power consumption. Adopting GreenTouch techniques can potentially improve the energy efficiency by 316× in a 2020 reference network compared to the state of the art in 2010.

The analysis of large collections of image data is still a challenging problem due to the difficulty of capturing the true concepts in visual data. The similarity between images could be computed using different and possibly multimodal features such as color or edge information or even text labels. This motivates the design of image analysis solutions that are able to effectively integrate the multi-view information provided by different feature sets. We therefore propose a new image retrieval solution that is able to sort images through a random walk on a multi-layer graph, where each layer corresponds to a different type of information about the image data. We study in depth the design of the image graph and propose in particular an effective method to select the edge weights for the multi-layer graph, such that the image ranking scores are optimised. We then provide extensive experiments in different real-world photo collections, which confirm the high performance of our new image retrieval algorithm that generally surpasses state-of-the-art solutions due to a more meaningful image similarity computation.

In this paper, we discuss energy-efficiency improvements in core networks obtained as a result of work carried out by the GreenTouch consortium over a five-year period. A number of techniques that yield substantial energy savings in core networks were introduced, including (i) the use of improved network components with lower power consumption, (ii) putting idle components into sleep mode, (iii) optically bypassing intermediate routers, (iv) the use of mixed line rates, (v) placing resources for protection into a low power state when idle, (vi) optimization of the network physical topology, and (vii) the optimization of distributed clouds for content distribution and network equipment virtualization. These techniques are recommended as the main energy-efficiency improvement measures for 2020 core networks. A mixed integer linear programming optimization model combining all the aforementioned techniques was built to minimize energy consumption in the core network. We consider group 1 nations' traffic and place this traffic on a US continental network represented by the AT&T network topology. The projections of the 2020 equipment power consumption are based on two scenarios: a business as usual (BAU) scenario and a GreenTouch (GT) (i.e., BAU + GT) scenario. The results show that the 2020 BAU scenario improves the network energy efficiency by a factor of 4.23 x compared with the 2010 network as a result of the reduction in the network equipment power consumption. Considering the 2020 BAU + GT network, the network equipment improvements alone reduce network power by a factor of 20 x compared with the 2010 network. Including of all the BAU + GT energy-efficiency techniques yields a total energy efficiency improvement of 315×. We have also implemented an experimental demonstration that illustrates the feasibility of energy-efficient content distribution in IP/WDM networks.

The effective representation, processing, analysis, and visualization of large-scale structured data, especially those related to complex domains, such as networks and graphs, are one of the key questions in modern machine learning. Graph signal processing (GSP), a vibrant branch of signal processing models and algorithms that aims at handling data supported on graphs, opens new paths of research to address this challenge. In this article, we review a few important contributions made by GSP concepts and tools, such as graph filters and transforms, to the development of novel machine learning algorithms. In particular, our discussion focuses on the following three aspects: exploiting data structure and relational priors, improving data and computational efficiency, and enhancing model interpretability. Furthermore, we provide new perspectives on the future development of GSP techniques that may serve as a bridge between applied mathematics and signal processing on one side and machine learning and network science on the other. Cross-fertilization across these different disciplines may help unlock the numerous challenges of complex data analysis in the modern age.