Large Language Models (LLMs) often produce fluent but factually incorrect responses, a phenomenon known as hallucination. Abstention, where the model chooses not to answer and instead outputs phrases such as "I don't know", is a common safeguard. However, existing abstention methods typically rely on post-generation signals, such as generation variations or feedback, which limits their ability to prevent unreliable responses in advance. In this paper, we introduce Aspect-Based Causal Abstention (ABCA), a new framework that enables early abstention by analysing the internal diversity of LLM knowledge through causal inference. This diversity reflects the multifaceted nature of parametric knowledge acquired from various sources, representing diverse aspects such as disciplines, legal contexts, or temporal frames. ABCA estimates causal effects conditioned on these aspects to assess the reliability of knowledge relevant to a given query. Based on these estimates, we enable two types of abstention: Type-1, where aspect effects are inconsistent (knowledge conflict), and Type-2, where aspect effects consistently support abstention (knowledge insufficiency). Experiments on standard benchmarks demonstrate that ABCA improves abstention reliability, achieves state-of-the-art performance, and enhances the interpretability of abstention decisions.

Location-Based Services (LBS) such as ride-sharing, accommodation, food delivery, and location-driven social media platforms entangle digital systems with physical spaces, thereby generating impacts that extend beyond users to others who share the same environments. Existing design approaches struggle to address the dual challenge of value tensions that arise in shared physical spaces and the locality-specific contexts in which LBS operate. To respond, we introduce Location-Aware Value Sensitive Design (LA-VSD), a domain-specific adaptation of VSD tailored to the distinctive characteristics of LBS. LA-VSD guides designers through three heuristics to help (1) identify and prioritise stakeholders through local space-sharing scenarios, (2) adapt empirical methods to capture values and tensions in context, and (3) support value-aligned interactions across both digital and physical layers of the service. Through a case study of e-scooter sharing in Melbourne, Australia, we demonstrate how LA-VSD enables more grounded, context-aware, and actionable design of LBS.

Large-language-model (LLM) based user simulation is increasingly adopted for evaluating search engines, recommender systems, and retrieval-augmented generation pipelines, yet most simulators remain opaque: it is difficult to determine why a simulated user made a particular choice or whether that choice is consistent with the intended user profile. Compounding this, recent research shows that LLMs can produce biased or discriminatory responses depending on user background characteristics such as language, education level, and cultural context, raising concerns about the equitable treatment of minority and disadvantaged groups. This half-day, in-person tutorial introduces a proposed design-and-audit framework that treats a user simulator as a verifiable engineering artefact composed of seven auditable components---structured Persona, task-aware Contract, matched human-vs-agent Execution, auditable Trace, persona-aligned Verification, structured Feedback, and a Refinement loop that updates personas and contracts. Through two hands-on mini-labs on recommendation-list evaluation and search-query formulation, participants will inspect simulator behaviour end-to-end, distinguish diagnostic discrepancy analysis from statistical validation, and apply checks for fidelity, credibility, and demographic bias. The tutorial targets information retrieval and recommender systems researchers and practitioners interested in user behaviour simulation and responsible AI.

Large Language Model (LLM)-based agent simulation has emerged as a promising approach to meet the increasing demand for real-time and rigorous evaluation in modern recommender systems. A typical LLM-driven simulation framework comprises three essential components: the profile module, memory module, and action module. However, existing studies have primarily concentrated on enhancing the memory and action modules, with limited attention to profile generation, which plays a pivotal role in ensuring realistic agent behaviours and aligning simulated interactions with real user dynamics. Moreover, the scarcity of datasets specifically designed for recommendation simulations has led to heavy reliance on manually crafted profiles, significantly limiting the scalability and generalisability of simulation frameworks across different datasets. To address these challenges, this work proposes an Automated Profile Generation Framework for Recommendation Simulation, APG4RecSim, that constructs realistic, coherent, and robust user profiles with minimal supervision. Extensive experiments on three benchmark datasets demonstrate that APG4RecSim achieves the best overall performance on discrimination, ranking, and rating tasks, improving ranking quality by up to 7% in nDCG@10 and reducing rating distribution divergence by 8% in JSD compared to existing profile-generation baselines. Beyond overall performance gains, our results show that APG4RecSim produces profiles that are resilient to popularity- and position-induced biases and maintain stable performance across datasets and different LLMs.

Large language models (LLMs) are widely used for question answering (QA) but can generate biased or stereotype-driven answers due to demographic associations learned during pre-training. Existing mitigation strategies often rely on model access or fine-tuning, which limits their applicability to closed-source LLMs. We propose a Causal Front Door Prompting framework (CFDP) that reduces demographic influence by intervening on the chain of thought reasoning, which is treated as an observable mediator. CFDP samples and clusters multiple reasoning traces and estimates answer probabilities through weighted aggregation. Experiments on two widely used bias-sensitive QA benchmarks, BBQ and Stereotype, across major LLMs show that CFDP consistently improves fairness metrics without sacrificing QA accuracy. Ablation and sensitivity analyses confirm the value of each component, indicating that causal intervention on reasoning provides an effective and practical approach for bias mitigation in LLM-based QA.

Recommenders built upon implicit collaborative filtering are typically trained to distinguish between users' positive and negative preferences. When direct observations of the latter are unavailable, negative training data are constructed with sampling techniques. But since items often exhibit clustering in the latent space, existing methods tend to oversample negatives from dense regions, resulting in homogeneous training data and limited model expressiveness. To address these shortcomings, we propose a novel negative sampler with diversity guarantees. To achieve them, our approach first pairs each positive item of a user with one that they have not yet interacted with; this instance, called hard negative, is chosen as the top-scoring item according to the model. Instead of discarding the remaining highly informative items, we store them in a user-specific cache. Next, our diversity-augmented sampler selects a representative subset of negatives from the cache, ensuring its dissimilarity from the corresponding user's hard negatives. Our generator then combines these items with the hard negatives, replacing them to produce more effective (synthetic) negative training data that are informative and diverse. Experiments show that our method consistently leads to superior recommendation quality without sacrificing computational efficiency.

When it comes to expensive black-box optimization problems, Bayesian Optimization (BO) is a well-known and powerful solution. Many real-world applications involve a large number of dimensions, hence scaling BO to high dimension is of much interest. However, state-of-the-art high-dimensional BO methods still suffer from the curse of dimensionality, highlighting the need for further improvements. In this work, we introduce BOIDS, a novel high-dimensional BO algorithm that guides optimization by a sequence of one-dimensional direction lines using a novel tailored line-based optimization procedure. To improve the efficiency, we also propose an adaptive selection technique to identify most optimal lines for each round of line-based optimization. Additionally, we incorporate a subspace embedding technique for better scaling to high-dimensional spaces. We further provide theoretical analysis of our proposed method to analyze its convergence property. Our extensive experimental results show that BOIDS outperforms state-of-the-art baselines on various synthetic and real-world benchmark problems.

Large Language Models (LLMs) demonstrate human-like capabilities in language understanding, reasoning, and generation, driving interest in using LLM-based agents to simulate human feedback in recommender systems. However, most existing approaches rely on static user profiling, neglecting the temporal and dynamic nature of user interests. This limitation stems from a disconnect between language modelling and behaviour modelling, which constrains the capacity of agents to represent sequential patterns. To address this challenge, we propose a Dynamic Temporal-aware Agent-based simulator for Recommender Systems, DyTA4Rec, which enables agents to model and utilise evolving user behaviour based on historical interactions. DyTA4Rec features a dynamic updater for real-time profile refinement, temporal-enhanced prompting for sequential context, and self-adaptive aggregation for coherent feedback. Experimental results at group and individual levels show that DyTA4Rec significantly improves the alignment between simulated and actual user behaviour by modelling dynamic characteristics and enhancing temporal awareness in LLM-based agents.

Recommender systems trained on implicit feedback data rely on negative sampling to distinguish positive items from negative items for each user. Since the majority of positive interactions come from a small group of active users, negative samplers are often impacted by data imbalance, leading them to choose more informative negatives for prominent users while providing less useful ones for users who are not so active. This leads to inactive users being further marginalised in the training process, thus receiving inferior recommendations. In this paper, we conduct a comprehensive empirical study demonstrating that state-of-the-art negative sampling strategies provide more accurate recommendations for active users than for inactive users. We also find that increasing the number of negative samples for each positive item improves the average performance, but the benefit is distributed unequally across user groups, with active users experiencing performance gain while inactive users suffering performance degradation. To address this, we propose a group-specific negative sampling strategy that assigns smaller negative ratios to inactive user groups and larger ratios to active groups. Experiments on eight negative samplers show that our approach improves user-side fairness and performance when compared to a uniform global ratio.

High-dimensional Bayesian Optimization (BO) has attracted significant attention in recent research. However, existing methods have mainly focused on optimizing in continuous domains, while combinatorial (ordinal and categorical) and mixed domains still remain challenging. In this paper, we first propose MOCA-HESP, a novel high-dimensional BO method for combinatorial and mixed variables. The key idea is to leverage the hyper-ellipsoid space partitioning (HESP) technique with different categorical encoders to work with high-dimensional, combinatorial and mixed spaces, while adaptively selecting the optimal encoders for HESP using a multi-armed bandit technique. Our method, MOCA-HESP, is designed as a meta-algorithm such that it can incorporate other combinatorial and mixed BO optimizers to further enhance the optimizers’ performance. Finally, we develop three practical BO methods by integrating MOCA-HESP with state-of-the-art BO optimizers for combinatorial and mixed variables: standard BO, CASMOPOLITAN, and Bounce. Our experimental results on various synthetic and real-world benchmarks show that our methods outperform existing baselines. Our code implementation can be found at https://github.com/LamNgo1/moca-hesp.

In recent years, utility optimization and fairness have emerged as key objectives in spatial-temporal resource allocation systems, such as ridesharing and food delivery, attracting significant research interest due to their often conflicting nature. Systems focused solely on optimizing utility can create disparities, such as disparate earnings among rideshare drivers, leading to ethical and economic issues. Conversely, focusing solely on fairness can paradoxically reduce overall utility, resulting in a scenario where no one truly benefits. To address this, many Reinforcement Learning (RL)-based approaches have been proposed due to its capacity to generate dynamic, non-myopic allocation plans. Typically, RL-based approaches balance utility and fairness by constructing direct trade-off functions between them. However, this paper argues that in dynamic situations, the scale of the objectives may differ significantly, causing RL to overemphasize one objective at the expense of the other. To effectively address this issue, we propose formulating the challenge of balancing utility and fairness in spatial-temporal resource allocation as a Constrained Markov Decision Process. Here, fairness is treated as a constraint while utility optimization serves as the standard reward. Building on this foundation, we introduce Dynamic Budgeted Proximal Policy Optimization (DB-PPO). We demonstrate that DB-PPO outperforms existing approaches in fairness-oriented spatial-temporal resource allocations using two real-world publicly available datasets.

Deep spatio-temporal neural networks are increasingly used in urban computing, impacting critical infrastructure such as public transport, emergency services, and traffic systems. While most methods focus on accuracy, fairness has become a key concern as biased predictions can disadvantage specific demographic or geographic groups, reinforcing inequalities. We propose FairDRL-ST, a disentangled representation learning framework for fair spatio-temporal prediction, with a focus on mobility demand forecasting. By combining adversarial and disentangled learning, our approach separates sensitive attributes and achieves fairness in an unsupervised manner with minimal performance loss. Experiments on real-world urban mobility datasets show that FairDRL-ST reduces fairness gaps while maintaining competitive predictive accuracy against state-of-the-art fairness-aware methods.1

Bayesian Optimization (BO) is a powerful tool for optimizing expensive black-box objective functions. While extensive research has been conducted on the single-objective optimization problem, the multi-objective optimization problem remains challenging. In this paper, we propose MOBO-OSD, a multi-objective Bayesian Optimization algorithm designed to generate a diverse set of Pareto optimal solutions by solving multiple constrained optimization problems, referred to as MOBO-OSD subproblems, along orthogonal search directions (OSDs) defined with respect to an approximated convex hull of individual objective minima. By employing a well-distributed set of OSDs, MOBO-OSD ensures broad coverage of the objective space, enhancing both solution diversity and hypervolume performance. To further improve the density of the set of the Pareto optimal candidate solutions without requiring an excessive number of subproblems, we leverage a Pareto Front Estimation technique to generate additional solutions in the neighborhood of existing solutions. Additionally, MOBO-OSD supports batch optimization, enabling parallel function evaluations to accelerate the optimization process when resources are available. Through extensive experiments and analysis on a variety of synthetic and real-world benchmark functions with two to six objectives, we demonstrate that MOBO-OSD consistently outperform the state-of-the-art algorithms.

Traditional offline evaluation methods for recommender systems struggle to capture the complexity of modern platforms due to sparse behavioural signals, noisy data, and limited modelling of user personality traits.While simulation frameworks can generate synthetic data to address these gaps, existing methods fail to replicate behavioural diversity, limiting their effectiveness.To overcome these challenges, we propose the Personality-driven User Behaviour Simulator (PUB), an LLM-based simulation framework that integrates the Big Five personality traits to model personalised user behaviour.PUB dynamically infers user personality from behavioural logs (e.g., ratings, reviews) and item metadata, then generates synthetic interactions that preserve statistical fidelity to real-world data.Experiments on the Amazon review datasets show that logs generated by PUB closely align with real user behaviour and reveal meaningful associations between personality traits and recommendation outcomes.These results highlight the potential of the personality-driven simulator to advance recommender system evaluation, offering scalable, controllable, high-fidelity alternatives to resource-intensive real-world experiments.1

Abstract With the introduction of machine learning in high stakes decision-making, ensuring algorithmic fairness has become an increasingly important task. To this end, many mathematical definitions of fairness have been proposed, and a variety of optimisation techniques have been developed, all designed to maximise a given notion of fairness. Fair solutions, however, tend to rely on the quality of training data, and can be highly sensitive to noise. Recent studies have shown that robustness of many such fairness strategies—i.e., their ability to perform well on unseen data—is not a given and requires careful consideration. To address this challenge, we propose robustness ratio , which is a novel criterion to measure the robustness of diverse fairness optimisation strategies. We support our analysis with multiple extensive experiments on five benchmark fairness data sets, using three prominent fairness strategies, in view of four of the most popular definitions of fairness. Our experiments show that while fairness methods that rely on threshold optimisation (post-processing) mostly outperform other techniques, they are acutely sensitive to noise. This is in contrast to two other methods—correlation remover (pre-processing) and exponentiated gradient descent (in-processing)—which become increasingly fairer as the random noise injected into the data becomes larger. Our findings offer a comprehensive overview of fairness strategies that proves invaluable when tasked with choosing the most suitable method for the task at hand. To the best of our knowledge, we are the first to quantitatively evaluate the robustness of fairness optimisation strategies.

Abstract Algorithmic recourse suggests actions to individuals who have been adversely affected by automated decision-making, helping them to achieve the desired outcome. Knowing the recourse, however, does not guarantee that users can implement it perfectly, either due to environmental variability or personal choices. Recourse generation should thus anticipate its sub-optimal or noisy implementation. While several approaches construct recourse that is robust to small perturbations – e.g., arising due to its noisy implementation – they assume that the entire recourse is implemented in a single step, thus model the noise as one-off and uniform. But these assumptions are unrealistic since recourse often entails multiple sequential steps, which makes it harder to implement and subject to increasing noise. In this work, we consider recourse under plausible noise that adheres to the local data geometry and accumulates at every step of the way. We frame this problem as a Markov Decision Process and demonstrate that such a distribution of plausible noise satisfies the Markov property. We then propose the RObust SEquential (ROSE) recourse generator for tabular data; our method produces a series of steps leading to the desired outcome even when they are implemented imperfectly. Given plausible modelling of sub-optimal human actions and greater recourse robustness to accumulated uncertainty, ROSE provides users with a high chance of success while maintaining low recourse cost. Empirical evaluation shows that our algorithm effectively navigates the inherent trade-off between recourse robustness and cost while ensuring its sparsity and computational efficiency.

Electric scooters (e-scooters) offer flexible urban mobility but raise safety concerns in shared spaces. This study investigates how e-scooters can better communicate their presence to pedestrians and cyclists in shared active mobility environments. A focus group with e-scooter riders identified notifying others of arrival as a key challenge. To address this, we co-designed audio and visual alerts in a participatory workshop and evaluated them in a real-world Wizard of Oz (WoZ) study involving live encounters. WoZ self-report data showed that voice and bell alerts were rated significantly higher in visibility, safety, communication, and acceptance than continuous sounds and flashing lights. These findings were supported by video analysis, which captured clear spatial responses such as turning or moving aside. Cyclists rated alerts as more distracting than pedestrians. Eye-tracking data revealed increased pedestrian attention during overtaking. By combining self-reports, video, and gaze data, we provide in-situ evidence and design recommendations to improve e-scooter signalling and reduce conflict. The dataset, including anonymized ratings, fixation data, alert designs, and analysis scripts, is available at https://github.com/HiruniNuwanthika/User-Perception-Evaluation-Escooter-Alerts.git.

Itinerary recommendation involves suggesting a sequence of Points of Interests (POIs) that users obtain maximum satisfaction under a time budget. Existing models have three challenges. First, they model user interest as non-time dependent, which cannot capture user interest appropriately because user interest can be contextual on time, e.g., interest in restaurants are likely higher during typical meal times. Second, they model the distance dependency of user interest as a linear one, which does not always adequately capture this relationship, e.g., it could be a cubic decay relationship. Finally, existing studies treat POI recommendation and itinerary optimisation as two separate problems, which can result in sub-optimal itinerary recommendations. In this paper, we propose a deep learning model that recommends POIs and constructs the itinerary simultaneously and in an integrated manner. It captures user dynamic interest and non-linear spatial dependencies in itinerary recommendations. The proposed model has two steps, where the candidate selection policy generates a set of personalised candidate POIs based on user interest and the itinerary construction step maximises user interest within budget time. To recommend an appropriate candidate set, we propose a multi-head, attention-based transformer to leverage periodic trends and recent activities to capture user dynamic preferences. We also introduce a new co-visiting patterns-based graph convolutional network (GCN) model to capture user non-linear spatial dependencies. To construct the full itinerary from the dynamic candidate sets, we apply greedy policy that incrementally constructs itineraries within the budget time which aims to maximise user interest and minimize queuing time. Experimental results show that the proposed deep learning model outperforms state-of-the-art baselines in itinerary recommendation in four theme parks and four cities datasets. The proposed model outperforms the baselines in itinerary recommendation from 7.79% to 26.28% on various datasets in terms of F1-score value. We also show that the proposed candidate generation approach outperforms the state-of-the-art next POI recommendation models in eight real datasets. The proposed model outperforms the baselines on average by 11.29 % in terms of F1-score@5 values and 9.08% in terms of F1-score@10 values. We have publicly shared our source code at GitHub 1 for the reproducibility of our proposed model.

Dynamic Vehicle Routing Problem (DVRP), is an extension of the classic Vehicle Routing Problem (VRP), which is a fundamental problem in logistics and transportation. Typically, DVRPs involve two stakeholders: service providers that deliver services to customers and customers who raise requests from different locations. Many real-world applications can be formulated as DVRP such as ridesharing and non-compliance capture. Apart from original objectives like optimising total utility or efficiency, DVRP should also consider fairness for all parties. Unfairness can induce service providers and customers to give up on the systems, leading to negative financial and social impacts. However, most existing DVRP-related applications focus on improving fairness from a single side, and there have been few works considering two-sided fairness and utility optimisation concurrently. To this end, we propose a novel framework, a Two-sided Fairness-aware Genetic Algorithm (named 2FairGA), which expands the genetic algorithm from the original objective solely focusing on utility to multi-objectives that incorporate two-sided fairness. Subsequently, the impact of injecting two fairness definitions into the utility-focused model and the correlation between any pair of the three objectives are explored. Extensive experiments demonstrate the superiority of our proposed framework compared to the state-of-the-art.

Complex social event summarization is a problem which has been important for real-world applications, including crisis management, rumor control and government policy tracking. However, in many critical situations, social events are complex and context-sensitive, which demands the online summarization of social events in an integrated manner. Motivated by this, we propose an online complex social event summarization approach, namely SOMA, which summarizes the complex social events over multiple attributes including media content and contexts simultaneously. The evaluation shows that our proposed approach outperforms the existing solutions for event summarizaiton in terms of effectiveness and efficiency.

Point-of-interest (POI) recommendation considers spatio-temporal factors like distance, peak hours, and user check-ins. Given their influence on both consumer experience and POI business, it’s crucial to consider fairness from multiple perspectives. Unfortunately, these systems often provide less accurate recommendations to inactive users and less exposure to unpopular POIs. This paper develops a post-filter method that includes provider and consumer fairness in existing models, aiming to balance fairness metrics like item exposure with performance metrics such as precision and distance. Experiments show that a linear scoring model for provider fairness in re-scoring items offers the best balance between performance and long-tail exposure, sometimes without much precision loss. Addressing consumer fairness by recommending more popular POIs to inactive users increased precision in some models and datasets. However, combinations that reached the Pareto front of consumer and provider fairness resulted in the lowest precision values, highlighting that tradeoffs depend greatly on the model and dataset.

Micro-mobility services (e.g., e-bikes, e-scooters) are increasingly popular among urban communities, being a flexible transport option that brings both opportunities and challenges. As a growing mode of transportation, insights gained from micro-mobility usage data are valuable in policy formulation and improving the quality of services. Existing research analyses patterns and features associated with usage distributions in different localities, and focuses on either temporal or spatial aspects. In this paper, we employ a combination of methods that analyse both spatial and temporal characteristics related to e-scooter trips in a more granular level, enabling observations at different time frames and local geographical zones that prior analysis wasn’t able to do. The insights obtained from anonymised, restricted data on shared e-scooter rides show the applicability of the employed method on regulated, privacy preserving micro-mobility trip data. Our results showed population density is the topmost important feature, and it associates with e-scooter usage positively. Population owning motor vehicles is negatively associated with shared e-scooter trips, suggesting a reduction in e-scooter usage among motor vehicle owners. Furthermore, we found that the effect of humidity is more important than precipitation in predicting hourly e-scooter trip count. Buffer analysis showed, nearly 29% trips were stopped, and 27% trips were started on the footpath, revealing higher utilisation of footpaths for parking e-scooters in Melbourne.

First developed to rank website relevance, PageRank has become ubiquitous in many areas of graph machine learning including deep learning. We demonstrate that a number of recently published deep graph neural networks are qualitatively equivalent to shallow networks utilizing Personalized PageRank (PPR), and that their performance improvements over existing PPR implementations can be fully explained by hyperparameter choices. We also show that PPR with these hyperparameters outperform more recently published sophisticated variations of PPR-based graph neural networks, and present efficient implementations that reduce training times and memory requirements while improving scalability.

Abstract Knowledge graphs (KGs) are becoming essential resources for many downstream applications. However, their incompleteness may limit their potential. Thus, continuous curation is needed to mitigate this problem. One of the strategies to address this problem is KG alignment, i.e., forming a more complete KG by merging two or more KGs. This paper proposes i-Align, an interpretable KG alignment model. Unlike the existing KG alignment models, i-Align provides an explanation for each alignment prediction while maintaining high alignment performance. Experts can use the explanation to check the correctness of the alignment prediction. Thus, the high quality of a KG can be maintained during the curation process (e.g., the merging process of two KGs). To this end, a novel Transformer-based Graph Encoder (Trans-GE) is proposed as a key component of i-Align for aggregating information from entities’ neighbors (structures). Trans-GE uses Edge-gated Attention that combines the adjacency matrix and the self-attention matrix to learn a gating mechanism to control the information aggregation from the neighboring entities. It also uses historical embeddings, allowing Trans-GE to be trained over mini-batches, or smaller sub-graphs, to address the scalability issue when encoding a large KG. Another component of i-Align is a Transformer encoder for aggregating entities’ attributes. This way, i-Align can generate explanations in the form of a set of the most influential attributes/neighbors based on attention weights. Extensive experiments are conducted to show the power of i-Align. The experiments include several aspects, such as the model’s effectiveness for aligning KGs, the quality of the generated explanations, and its practicality for aligning large KGs. The results show the effectiveness of i-Align in these aspects.

Complex social event summarization is a problem which has been shown having great utility for real-world applications, including crisis management, rumor control and government policy tracking. In recent years there has been significant research effort spent on effectively extracting meaningful textual descriptions of an event. However, in many critical situations, social events are complex and context-sensitive, which demands the online summarization of social events in an integrated manner. In this paper, we propose the first online complex social event summarization approach, namely SOMA, which summarizes the complex social events over multiple attributes including media content and contexts simultaneously. Specifically, we first propose a deep learning model that comprehensively summarizes events in regards to the text description and locations that they appear in, by utilizing their hidden connections in posts. We then propose a summary generator over time, text and location to achieve a maximal coverage of the summary over the original social event and minimal redundancy of the summary. Furthermore, we propose a location estimation method to address the location sparsity issue of complex events by mining the correlation between text and location. The evaluation over four real-event datasets and three benchmark datasets shows that our proposed approach outperforms the existing solutions for event summarizaiton in terms of effectiveness and efficiency.

The predict+optimize problem combines machine learning and combinatorial optimization by predicting the problem coefficients first and then using these coefficients to solve the optimization problem. While this problem can be solved in two separate stages, recent research shows end to end models can achieve better results. This requires differentiating through a discrete combinatorial function. Models that use differentiable surrogates are prone to approximation errors, while existing exact models are limited to dynamic programming, or they do not generalize well with scarce data. In this work we propose a novel divide and conquer algorithm based on transition points to reason over exact optimization problems and predict the coefficients using the optimization loss. Moreover, our model is not limited to dynamic programming problems. We also introduce a greedy version, which achieves similar results with less computation. In comparison with other predict+optimize frameworks, we show our method outperforms existing exact frameworks and can reason over hard combinatorial problems better than surrogate methods.

Event popularity prediction over social media is crucial for estimating information propagation scope, decision making, and emergency prevention. It has been widely inves-tigated by existing approaches focusing on predicting single attribute occurrences which are not comprehensive enough for representing complex social event propagation. Motivated by this, we propose a novel hashtag-influence-based event popularity prediction by mining the impact of an influential hashtag set on the event propagation. We have conducted extensive experiments to prove the effectiveness and efficiency of the proposed approach.

Disentangled representation learning offers useful properties such as dimension reduction and interpretability, which are essential to modern deep learning approaches. Although deep learning techniques have been widely applied to spatio-temporal data mining, there has been little attention to further disentangle the latent features and understanding their contribution to the model performance, particularly their mutual information and correlation across features. In this study, we adopt two state-of-the-art disentangled representation learning methods and apply them to three large-scale public spatio-temporal datasets. To evaluate their performance, we propose an internal evaluation metric focusing on the degree of correlations among latent variables of the learned representations and the prediction performance of the downstream tasks. Empirical results show that our modified method can learn disentangled representations that achieve the same level of performance as existing state-of-the-art ST deep learning methods in a spatio-temporal sequence forecasting problem. Additionally, we find that our methods can be used to discover real-world spatial-temporal semantics to describe the variables in the learned representation.

Point-of-interest (POI) recommendation is a challenging problem due to different contextual information and a wide variety of human mobility patterns. Prior studies focus on recommendation that considers user travel spatiotemporal and sequential patterns behaviours. These studies do not pay attention to user personal interests, which is a significant factor for POI recommendation. Besides user interests, queuing time also plays a significant role in affecting user mobility behaviour, e.g., having to queue a long time to enter a POI might reduce visitor's enjoyment. Recently, attention-based recurrent neural networks-based approaches show promising performance in the next POI recommendation task. However, they are limited to single head attention, which can have difficulty in finding the appropriate user mobility behaviours considering complex relationships among POI spatial distances, POI check-in time, user interests and POI queuing times. In this research work, we are the first to consider queuing time and user interest awareness factors for next POI recommendation. We demonstrate how it is non-trivial to recommend a next POI and simultaneously predict its queuing time. To solve this problem, we propose a multi-task, multi-head attention transformer model called TLR-M_UI. The model recommends the next POIs to the target users and predicts queuing time to access the POIs simultaneously by considering user mobility behaviours. The proposed model utilises POIs description-based user personal interest that can also solve the new categorical POI cold start problem. Extensive experiments on six real-world datasets show that the proposed models outperform the state-of-the-art baseline approaches in terms of precision, recall, and F1-score evaluation metrics. The model also predicts and minimizes the queuing time. For the reproducibility of the proposed model, we have publicly shared our implementation code at GitHub (https://github.com/sajalhalder/TLR-M_UI).

Decision tree learning is a widely used approach in machine learning, favoured in applications that require concise and interpretable models. Heuristic methods are traditionally used to quickly produce models with reasonably high accuracy. A commonly criticised point, however, is that the resulting trees may not necessarily be the best representation of the data in terms of accuracy and size. In recent years, this motivated the development of optimal classification tree algorithms that globally optimise the decision tree in contrast to heuristic methods that perform a sequence of locally optimal decisions. We follow this line of work and provide a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our algorithm supports constraints on the depth of the tree and number of nodes. The success of our approach is attributed to a series of specialised techniques that exploit properties unique to classification trees. Whereas algorithms for optimal classification trees have traditionally been plagued by high runtimes and limited scalability, we show in a detailed experimental study that our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances, providing several orders of magnitude improvements and notably contributing towards the practical use of optimal decision trees.

Abstract Personalized itinerary recommendation has garnered wide research interests for their ubiquitous applications. Recommending personalized itineraries is complex because of the large number of points of interest (POI) to consider in order to construct an itinerary based on visitors’ interest and preference, time budget and uncertain queuing time. Previous studies typically aim to plan itineraries that maximize POI popularity, visitors’ interest and minimize queuing time. However, existing solutions may not reflect visitor preferences because when creating itineraries, they prefer to recommend POIs with short prior visiting periods. These recommendations can conflict with real-life scenarios as visitors typically spend less time at POIs that they do not enjoy, thus leading to the inclusion of unsuitable POIs. Moreover, constructing itineraries based on selected POIs is a challenging and time-consuming process. Existing approaches involve searching through a large number of non-optimal, duplicate itineraries that are time-consuming to review and generate. To address these issues, we propose an adaptive Monte Carlo tree search (MCTS)-based reinforcement learning algorithmEffiTourRecusing an effective POI selection strategy by giving preference to POIs with long visiting times and short queuing times along with high POI popularity and visitor interest. In addition, to reduce non-optimal and duplicated itineraries generation, we propose an efficient MCTS search pruning technique to explore a smaller, more promising portion of solution space. Experiment results in real theme park datasets show clear advantages of our proposed method over baselines, where our method outperforms the current state-of-the-art by 20.89 to 52.32% in precision, 8.36 to 21.35% in F1-score and 40.00 to 67.64% in execution time.

Event popularity prediction over social media is crucial for estimating information propagation scope, decision making, and emergency prevention. However, existing approaches only focus on predicting the occurrences of single attribute such as a message, a hashtag or an image, which are not comprehensive enough for representing complex social event propagation. In this paper, we predict the event popularity, where an event is described as a set of messages containing multiple hashtags. We propose a novel hashtag-influence-based event popularity prediction by mining the impact of an influential hashtag set on the event propagation. Specifically, we first propose a hashtag-influence-based cascade model to select the influential hashtags over an event hashtag graph built by the pairwise hashtag similarity and the topic distribution of event-related hashtags. A novel measurement is proposed to identify the hashtag influence of an event over its content and social impacts. A hashtag correlation-based algorithm is proposed to optimize the seed selection in a greedy manner. Then, we propose an event-fitting boosting model to predict the event popularity by embedding the feature importance over events into the XGBOOST model. Moreover, we propose an event-structure-based method, which incrementally updates the prediction model over social streams. We have conducted extensive experiments to prove the effectiveness and efficiency of the proposed approach.

This work proposes a Bayesian optimisation with Gaussian Process approach to learn decision maker (DM) preferences in the attribute search space of a multi-objective optimisation problem (MOP). The DM is consulted periodically during optimisation of the problem and asked to provide their preference over a series of pairwise comparisons of candidate solutions. After each consultation, the most preferred solution is used as the reference point in an appropriate multiobjective optimisation evolutionary algorithm (MOEA). The rationale for using Bayesian optimisation is to identify the most preferred location in the decision search space with the least number of DM queries, thereby minimising DM cognitive burden and fatigue. This enables non-expert DMs to be involved in the optimisation process and make more informed decisions. We further reduce the number of preference queries required, by progressively redefining the Bayesian search space to reflect the MOEA's decision bounds as it converges toward the Pareto Front. We demonstrate how this approach can locate a reference point close to an unknown preferred location on the Pareto Front, of both benchmark and real-world problems with relatively few pairwise comparisons.

Deep reinforcement learning (DRL) has demonstrated promising performance to learn effective heuristics to solve complex combinatorial optimisation problems via policy networks. However, traditional reinforcement learning (RL) suffers from insufficient exploration, which often results in pre-convergence to poor policies and many challenges the performance of DRL. To prevent this, we propose an Entropy Regularised Reinforcement Learning (ERRL) method that supports exploration by providing more stochastic policies, improving optimisation. The ERRL method incorporates an entropy term, defined over the policy network's outputs, into the loss function of the policy network. Hence, policy exploration can be explicitly advocated subjected to a balance to maximise the reward. As a result, the risk of pre-convergence to inferior policies can be reduced. We implement the ERRL method based on two existing DRL algorithms. We have compared the performances of our implementations with the two DRL algorithms along with several state-of-the-art heuristic-based non-RL approaches for three categories of routing problems, i.e., travelling salesman problem (TSP), capacitated vehicle routing problem (CVRP) and multiple routing with fixed fleet problems (MRPFF). Experimental results show that the proposed method can find better and faster solutions in most test cases than the state-of-the-art algorithms.

Existing parking recommendation solutions mainly focus on finding and suggesting parking spaces based on the unoccupied options only. However, there are other factors associated with parking spaces that can influence someone’s choice of parking such as fare, parking rule, walking distance to destination, travel time, likelihood to be unoccupied at a given time. More importantly, these factors may change over time and conflict with each other which makes the recommendations produced by current parking recommender systems ineffective. In this paper, we propose a novel problem called multi-objective parking recommendation. We present a solution by designing a multi-objective parking recommendation engine called MoParkeR that considers various conflicting factors together. Specifically, we utilise a non-dominated sorting technique to calculate a set of Pareto-optimal solutions, consisting of recommended trade-off parking spots. We conduct extensive experiments using two real-world datasets to show the applicability of our multi-objective recommendation methodology.

We study the predict+optimise problem, where machine learning and combinatorial optimisation must interact to achieve a common goal. These problems are important when optimisation needs to be performed on input parameters that are not fully observed but must instead be estimated using machine learning. We provide a novel learning technique for predict+optimise to directly reason about the underlying combinatorial optimisation problem, offering a meaningful integration of machine learning and optimisation. This is done by representing the combinatorial problem as a piecewise linear function parameterised by the coefficients of the learning model and then iteratively performing coordinate descent on the learning coefficients. Our approach is applicable to linear learning functions and any optimisation problem solvable by dynamic programming. We illustrate the effectiveness of our approach on benchmarks from the literature.

Feature selection has been shown to be beneficial for many data mining and machine learning tasks, especially for big data analytics. Mutual Information (MI) is a well-known information-theoretic approach used to evaluate the relevance of feature subsets and class labels. However, estimating high-dimensional MI poses significant challenges. Consequently, a great deal of research has focused on using low-order MI approximations or computing a lower bound on MI called Variational Information (VI). These methods often require certain assumptions made on the probability distributions of features such that these distributions are realistic yet tractable to compute. In this paper, we reveal two sets of distribution assumptions underlying many MI and VI based methods: Feature Independence Distribution and Geometric Mean Distribution. We systematically analyze their strengths and weaknesses and propose a logical extension called Arithmetic Mean Distribution, which leads to an unbiased and normalised estimation of probability densities. We conduct detailed empirical studies across a suite of 29 real-world classification problems and illustrate improved prediction accuracy of our methods based on the identification of more informative features, thus providing support for our theoretical findings.

To provide effective services for intelligent transportation systems (ITS), such as optimizing ride services and recommending trips, it is important to predict the distributions of passenger flows from various origins to destinations. However, existing crowd flow prediction models have not sufficiently addressed this problem, and most methods have only focused on in and out flows of individual regions. The main challenges of origin-destination (OD) crowd flow prediction are diverse flow patterns across city networks and data sparsity. To solve these problems, we propose a Multi Attention 3D Residual Network (MAThR) to predict city-wide OD crowd flows. In particular, we develop a multi-component 3D residual structure with a novel global self-attention mechanism to dynamically aggregate the OD spatial-temporal dependencies, by modeling three components: contextual information of the region, and long and short term periodic crowd flows. For each component, we design a tensor criss-cross self-attention block, which can simultaneously discover the global and local correlation of spatial (where), temporal (when) and contextual (which) information between all OD pairs. Evaluation on real-world crowd flow data demonstrates the advantages of our MAThR method on prediction accuracy, compared to other existing state-of-the-art methods.

Deep learning has been extended to a number of new domains with critical success, though some traditional orienteering problems such as the Travelling Salesman Problem (TSP) and its variants are not commonly solved using such techniques. Deep neural networks (DNNs) are a potentially promising and under-explored solution to solve these problems due to their powerful function approximation abilities, and their fast feed-forward computation. In this paper, we outline a method for converting an orienteering problem into a classification problem, and design a multi-layer deep learning network to approximate traditional optimisation solutions to this problem. We test the performance of the network on a real-world parking violation dataset, and conduct a generic study that empirically shows the critical architectural components that affect network performance for this problem.

Blockmodelling is an important technique in social network analysis for discovering the latent structures and groupings in graphs. State-of-the-art approaches approximate the graph using matrix factorisation, which can discover both the latent graph structures and vertex groupings. However, factorisation is a one-way approximation, in that it only approximates the graph with a lossy model that removes the background noise. Traditional Blockmodelling methods rely on an alternating 2-step optimization that involves iteratively updating the matrix representing membership while fixing the matrix representing the graph's underlying structure, and then updating the structure matrix while keeping the membership matrix fixed. We propose a single step optimization method, which uses algebraic simplifi-cation to directly update the lower dimensional, latent structure representation. This helps improve both the convergence and accuracy of blockmodelling. We also show that this approach can solve multi-view blockmodelling problems, involving multiple graphs over the same vertices. We use real datasets to show that our approach has much higher accuracy and comparable running times to competing approaches.

BACKGROUND: Glycans are complex sugar chains, crucial to many biological processes. By participating in binding interactions with proteins, glycans often play key roles in host-pathogen interactions. The specificities of glycan-binding proteins, such as lectins and antibodies, are governed by motifs within larger glycan structures, and improved characterisations of these determinants would aid research into human diseases. Identification of motifs has previously been approached as a frequent subtree mining problem, and we extend these approaches with a glycan notation that allows recognition of terminal motifs. RESULTS: In this work, we customised a frequent subtree mining approach by altering the glycan notation to include information on terminal connections. This allows specific identification of terminal residues as potential motifs, better capturing the complexity of glycan-binding interactions. We achieved this by including additional nodes in a graph representation of the glycan structure to indicate the presence or absence of a linkage at particular backbone carbon positions. Combining this frequent subtree mining approach with a state-of-the-art feature selection algorithm termed minimum-redundancy, maximum-relevance (mRMR), we have generated a classification pipeline that is trained on data from a glycan microarray. When applied to a set of commonly used lectins, the identified motifs were consistent with known binding determinants. Furthermore, logistic regression classifiers trained using these motifs performed well across most lectins examined, with a median AUC value of 0.89. CONCLUSIONS: We present here a new subtree mining approach for the classification of glycan binding and identification of potential binding motifs. The Carbohydrate Classification Accounting for Restricted Linkages (CCARL) method will assist in the interpretation of glycan microarray experiments and will aid in the discovery of novel binding motifs for further experimental characterisation.

The ubiquity of personal sensing devices has enabled the collection of large, diverse, and fine-grained spatio-temporal datasets. These datasets facilitate numerous applications from traffic monitoring and management to location-based services. Recently, there has been an increasing interest in profiling individuals' movements for personalized services based on fine-grained trajectory data. Most approaches identify the most representative paths of a user by analyzing coarse location information, e.g., frequently visited places. However, even for trips that share the same origin and destination, individuals exhibit a variety of behaviors (e.g., a school drop detour, a brief stop at a supermarket). The ability to characterize and compare the variability of individuals' fine-grained movement behavior can greatly support location-based services and smart spatial sampling strategies. We propose a TRip DIversity Measure --TRIM – that quantifies the regularity of users' path choice between an origin and destination. TRIM effectively captures the extent of the diversity of the paths that are taken between a given origin and destination pair, and identifies users with distinct movement patterns, while facilitating the comparison of the movement behavior variations between users. Our experiments using synthetic and real datasets and across geographies show the effectiveness of our method.

One of the core challenges in open-plan workspaces is to ensure a good level of concentration for the workers while performing their tasks. Hence, being able to infer concentration levels of workers will allow building designers, managers, and workers to estimate what effect different open-plan layouts will have and to find an optimal one. In this article, we present an ambient-physical system to investigate the concentration inference problem. Specifically, we deploy a series of pervasive sensors to capture various ambient and physical signals related to perceived concentration at work. The practicality of our system has been tested on two large open-plan workplaces with different designs and layouts. The empirical results highlight promising applications of pervasive sensing in occupational concentration inference, which can be adopted to enhance the capabilities of modern workplaces.

This article investigates the cyber-physical behavior of users in a large indoor shopping mall by leveraging anonymized (opt in) Wi-Fi association and browsing logs recorded by the mall operators. Our analysis shows that many users exhibit a high correlation between their cyber activities and their physical context. To find this correlation,propose a mechanism to semantically label a physical space with rich categorical information from DBPedia concepts and compute a contextual similarity that represents a user’s activities with the mall context. We demonstrate the application of cyber-physical contextual similarity in two situations: user visit intent classification and future location prediction. The experimental results demonstrate that exploitation of contextual similarity significantly improves the accuracy of such applications.

Itinerary planning is one of the most important tasks in tourism. A well-planned itinerary enhances the tourist experience and their visit satisfaction in new cities. However, the task of planning personalized tour itineraries is complicated by tourists with different interest preferences. Furthermore, there is an added complexity of recommending an itinerary with discrete budget, time and cost. Due to an increase in web-technologies and online geo-location services, there is emerging research targeting itinerary recommendation based on each tourist's interest, preferences and trip constraints. While several research works consider tourist interest, they adopt a simple measure based on the number of times a tourist has visited a place or the number of photos taken by the tourist at a place. Our research proposes an improved sentiment-aware personalized tour planner that considers each tourist's interests based on his/her sentiments on specific categories relative to his/her overall preferences. Unlike the previous approaches that do not consider the actual opinion based preferences, our proposed approach determines user interests based on their sentiments associated with their written text about a place of their visit. This interest measure is based on the intuition that users are more likely to post favorable comments about places they like. Using a dataset from Twitter, we compare our proposed algorithm against the baseline and experimental results show that our algorithm obtained superior performance in terms of tour precision, recall, Fl-score and overall popularity.

Using evolutionary algorithms to solve optimisation problems with multiple objectives has proven very successful over the past few decades. The ability of these methods to efficiently find sets of solutions representing trade-offs between conflicting objectives has enhanced decision making in a wide variety of fields. Increasingly though, such techniques are being adapted to incorporate end-user preferences in order to reduce search spaces and provide smaller sets of targeted solutions. Eliciting these preferences interactively during optimisation has also become popular and helps a decision maker explore and learn and the problem and its range of solutions. Interactivity also facilitates the correction of mistakes and inaccurate preferences, leading to more satisfactory solutions, faster. In order to achieve these benefits an algorithm must be able to rapidly respond to changes in preferences. This work explores the use of secondary population archives to ensure a preference-based algorithm can change its search focus efficiently and effectively. When preferences change and the search is redirected to a new region of interest, an archive of previously found solutions can be consulted and solutions close to the new region can be included in the current population. This work shows how such archives can be implemented and how they can improve responsiveness for certain problems.

The prediction of flight delays plays a significantly important role for airlines and travellers because flight delays cause not only tremendous economic loss but also potential security risks. In this work, we aim to integrate multiple data sources to predict the departure delay of a scheduled flight. Different from previous work, we are the first group, to our best knowledge, to take advantage of airport situational awareness map, which is defined as airport traffic complexity (ATC), and combine the proposed ATC factors with weather conditions and light information. Features engineering methods and most state-of-the-art machine learning algorithms are applied to a large real-world data sources. We reveal a couple of factors at the airport which has a significant impact on flight departure delay time. The prediction results show that the proposed factors are the main reasons behind the flight delays. Using our proposed framework, an improvement in accuracy for flight departure delay prediction is obtained.

With the increasing popularity of e-commerce, the number of product-related queries generated by customers is growing. Answering these queries manually in real time is infeasible, and so automatic question-answering systems can be immensely helpful. Product queries are, however, very different from open-domain questions: they tend to be product-specific and the answers they demand can be very subjective. Previous research suggests that reviews are a valuable resource for answering product queries, but a key challenge is the language mismatch between user queries and reviews. To address this, we propose two neural models that discover relevant reviews for answering product queries. We demonstrate that our best model produces strong performance, outperforming state-of-the-art systems by consistently finding the most relevant reviews for product queries.

We study the predict+optimise problem, where machine learning and combinatorial optimisation must interact to achieve a common goal. These problems are important when optimisation needs to be performed on input parameters that are not fully observed but must instead be estimated using machine learning. Our contributions are two-fold: 1) we provide theoretical insight into the properties and computational complexity of predict+optimise problems in general, and 2) develop a novel framework that, in contrast to related work, guarantees to compute the optimal parameters for a linear learning function given any ranking optimisation problem. We illustrate the applicability of our framework for the particular case of the unit-weighted knapsack predict+optimise problem and evaluate on benchmarks from the literature.

On-ground aircraft trajectory information plays a key role in airport situations awareness prediction and management. Airport administration needs to arrange and schedule the time and order of aircraft landing and take-off events based on a precise and real-time information of on-ground aircraft. Recently, a large dataset of GPS-derived aircraft at airports, available from the Federal Aviation Administration (FAA), provides researchers with an opportunity to monitoring on-ground aircraft trajectory. In this paper, we present a framework to incrementally cluster airport aircraft trajectories based on the GPS data. The framework consists of two steps: 1) Classifying airport aircraft data according to spatial and temporal information. 2) Merging the similar aircraft trajectories incrementally. We evaluate our framework experimentally using a state-of-the-art test-bed technique, and find that it can effectively and efficiently construct and update on-ground aircraft trajectory map.

We learn user preferences from ratings and reviews by using multi-task learning (MTL) of rating prediction and summarization of item reviews. Reviews of an item tend to describe detailed user preferences (e.g., the cast, genre, or screenplay of a movie). A summary of such a review or a rating describes an overall user experience of the item. Our objective is to learn latent vectors which are shared across rating prediction and review summary generation. Additionally, the learned latent vectors and the generated summary act as explanations for the recommendation. Our MTL-based approach J3R uses a multi-layer perceptron for rating prediction, combined with pointer-generator networks with attention mechanism for the summarization component. We provide empirical evidence for joint learning of rating prediction and summary generation being beneficial for recommendation by conducting experiments on the Yelp dataset and six domains of the Amazon 5-core dataset. Additionally, we provide two ways of explanations visualizing (a) the user vectors on different topics of a domain, computed from our J3R approach and (b) a ten-word review summary of a review and the attention highlights generated on the review based on the user-item vectors

MOTIVATION: Compared to traditional haploid reference genomes, graph genomes are an efficient and compact data structure for storing multiple genomic sequences, for storing polymorphisms or for mapping sequencing reads with greater sensitivity. Further, graphs are well-studied computer science objects that can be efficiently analyzed. However, their adoption in genomic research is slow, in part because of the cognitive difficulty in interpreting graphs. RESULTS: We present an intuitive graphical representation for graph genomes that re-uses well-honed techniques developed to display public transport networks, and demonstrate it as a web tool. AVAILABILITY AND IMPLEMENTATION: Code: https://github.com/vgteam/sequenceTubeMap. DEMONSTRATION: https://vgteam.github.io/sequenceTubeMap/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Diffusion models are powerful tools for understanding the spread of diverse content such as information, opinions and ideas through social networks. Although these models have been successfully used to study the spreading dynamics such as viral marketing, there are many real scenarios (e.g. vaccination, evacuation) that require a more complex model. Hence, we propose a new hybrid framework that combines diffusion modelling with cognitive agent modelling. The hybrid, generic framework is grounded on BDI (Belief-Desire-Intention), an advanced, efficient cognitive agent framework. We demonstrate our framework to a wildfire evacuation case study consisting of 5,000 agents. We then compare and analyse the diffusion outcomes of our model against two baseline models, the standard Linear Threshold (LT) model and a slightly modified version of the LT model, across 17 different input configurations. The results show (statistically) significant differences with the baselines for the majority of the configurations, highlighting the need for cognitive agents in diffusion modelling. The framework presented here provides the basis for modelling complex reasoning to capture diffusion phenomena in complex and dynamic social systems.

An explosion of high-throughput DNA sequencing in the past decade has led to a surge of interest in population-scale inference with whole-genome data. Recent work in population genetics has centered on designing inference methods for relatively simple model classes, and few scalable general-purpose inference techniques exist for more realistic, complex models. To achieve this, two inferential challenges need to be addressed: (1) population data are exchangeable, calling for methods that efficiently exploit the symmetries of the data, and (2) computing likelihoods is intractable as it requires integrating over a set of correlated, extremely high-dimensional latent variables. These challenges are traditionally tackled by likelihood-free methods that use scientific simulators to generate datasets and reduce them to hand-designed, permutation-invariant summary statistics, often leading to inaccurate inference. In this work, we develop an exchangeable neural network that performs summary statistic-free, likelihood-free inference. Our framework can be applied in a black-box fashion across a variety of simulation-based tasks, both within and outside biology. We demonstrate the power of our approach on the recombination hotspot testing problem, outperforming the state-of-the-art.

Blockmodelling is an important technique for detecting underlying patterns in graphs. However, existing blockmodelling algorithms do not provide the user with any explicit control to specify which patterns might be of interest. Furthermore, existing algorithms focus on finding standard community structures in graphs, and are likely to overlook informative but more complex patterns, such as hierarchical or ring blockmodel structures. In this paper, we propose a generic constraint programming framework for blockmodelling, which allows a user to specify and search for complex blockmodel patterns in graphs. Our proposed framework can be incorporated into existing iterative blockmodelling algorithms, operating as a hybrid optimization scheme that provides high flexibility and expressiveness. We demonstrate the power of our framework for discovering complex patterns, via experiments over a range of synthetic and real data sets.

The on-street parking system is an indispensable part of civic projects, as it provides travelers and shoppers with parking spaces. With the recent in-ground sensors deployed throughout the Melbourne central business district (CBD), there is a significant problem on how to use the sensor data to manage parking violations and issue infringement notices efficiently in a short time-window. In this paper, we use a large realworld dataset with on-street parking sensor data from the local city council, and establish a formulation of the traveling officer problem with a general probability-based model. We propose two solutions using a spatio-temporal probability model for parking officers to maximize the number of infringing cars caught with limited time cost. Using real-world parking sensor data and Google Maps road network information, the experimental results show that our proposed algorithms outperform the existing patrolling routes.

Traditionally, recommender systems modelled the physical and cyber contextual influence on people's moving, querying, and browsing behaviors in isolation. Yet, searching, querying, and moving behaviors are intricately linked, especially indoors. Here, we introduce a tripartite location-query-browse graph (LQB) for nuanced contextual recommendations. The LQB graph consists of three kinds of nodes: locations, queries, and Web domains. Directed connections only between heterogeneous nodes represent the contextual influences, while connections of homogeneous nodes are inferred from the contextual influences of the other nodes. This tripartite LQB graph is more reliable than any monopartite or bipartite graph in contextual location, query, and Web content recommendations. We validate this LQB graph in an indoor retail scenario with extensive dataset of three logs collected from over 120,000 anonymized, opt-in users over a 1-year period in a large inner-city mall in Sydney, Australia. We characterize the contextual influences that correspond to the arcs in the LQB graph, and evaluate the usefulness of the LQB graph for location, query, and Web content recommendations. The experimental results show that the LQB graph successfully captures the contextual influence and significantly outperforms the state of the art in these applications.

Personalized itinerary recommendation is a complex and time-consuming problem, due to the need to recommend popular attractions that are aligned to the interest preferences of a tourist, and to plan these attraction visits as an itinerary that has to be completed within a specific time limit. Furthermore, many existing itinerary recommendation systems do not automatically determine and consider queuing times at attractions in the recommended itinerary, which varies based on the time of visit to the attraction, e.g., longer queuing times at peak hours. To solve these challenges, we propose the PersQ algorithm for recommending personalized itineraries that take into consideration attraction popularity, user interests and queuing times. We also implement a framework that utilizes geo-tagged photos to derive attraction popularity, user interests and queuing times, which PersQ uses to recommend personalized and queue-aware itineraries. We demonstrate the effectiveness of PersQ in the context of five major theme parks, based on a Flickr dataset spanning nine years. Experimental results show that PersQ outperforms various state-of-the-art baselines, in terms of various queuing-time related metrics, itinerary popularity, user interest alignment, recall, precision and F1-score.

Currently, large amounts of Wi-Fi access logs are collected in diverse indoor environments, but cannot be widely used for fine-grained spatio-temporal analysis due to coarse positioning. We present a Log-based Differential (D-Log) scheme for post-hoc localization based on differentiated location estimates obtained from large-scale Access Point (AP) logs of WiFi connectivity traces, which can be used for data analysis and knowledge discovery of visitor behaviours. Specifically, the location estimates are calculated by utilizing a combination of Received Signal Strength Indicator (RSSI) records from two neighbouring APs. D-Log exploits real-world industry WiFi logs where RSSI data sampled at low rates from single AP sources are recorded in each connectivity trace. The approach is independent of device and network infrastructure type. D-Log is evaluated using WiFi logs collected from controlled environment as well as real-world uncontrolled public indoor spaces, which includes discrete single-AP RSSI traces of around 100,000 mobile devices over a one-year period. The experiment results indicate that, despite of the challenges with the infrequent sampling rate and the limitations of the data that only records RSSI from single AP sources in each instance, D-Log performs comparatively well to the state-of-the-art RSSI-based localization methods and presents a viable alternative for many application areas where high-accuracy positioning infrastructure may not be cost effective or where positioning applications are considered on legacy information infrastructure.

Cloud computing enables users to consume various IT resources in an on-demand manner, and with low management overhead. However, customers can face new security risks when they use cloud computing platforms. In this paper, we focus on one such threat-the co-resident attack, where malicious users build side channels and extract private information from virtual machines co-located on the same server. Previous works mainly attempt to address the problem by eliminating side channels. However, most of these methods are not suitable for immediate deployment due to the required modifications to current cloud platforms. We choose to solve the problem from a different perspective, by studying how to improve the virtual machine allocation policy, so that it is difficult for attackers to co-locate with their targets. Specifically, we (1) define security metrics for assessing the attack; (2) model these metrics, and compare the difficulty of achieving co-residence under three commonly used policies; (3) design a new policy that not only mitigates the threat of attack, but also satisfies the requirements for workload balance and low power consumption; and (4) implement, test, and prove the effectiveness of the policy on the popular open-source platform OpenStack.

Previously, eight popular information-theoretic-based cluster validity indices have been generalized and tested for probabilistic partitions built by the expectation-maximization (EM) algorithm for the Gaussian mixture model. However, the analysis was limited to probabilistic clusters, and there were limited explanations for differences in the performance of the indices. In this paper, we extend the tests to partitions found by fuzzy c-means (FCM) and provide further explanations and insights about the performance of these indices. Of the eight generalized indices, we advocate a normalized version of the soft mutual information cluster validity index (NMI sM) as the best overall choice, as it outperforms the other seven indices for both FCM and EM according to our tests on synthetic and real data. The superiority of NMIsM is most pronounced for datasets with overlapped and/or varying-sized clusters. Finally, we provide a theoretical analysis, which helps explain the superior performance of NMIsM compared with the other three normalizations of soft mutual information.

This paper adapts topic models to the psychometric testing of MOOC students based on their online forum postings. Measurement theory from education and psychology provides statistical models for quantifying a person's attainment of intangible attributes such as attitudes, abilities or intelligence. Such models infer latent skill levels by relating them to individuals' observed responses on a series of items such as quiz questions. The set of items can be used to measure a latent skill if individuals' responses on them conform to a Guttman scale. Such well-scaled items differentiate between individuals and inferred levels span the entire range from most basic to the advanced. In practice, education researchers manually devise items (quiz questions) while optimising well-scaled conformance. Due to the costly nature and expert requirements of this process, psychometric testing has found limited use in everyday teaching. We aim to develop usable measurement models for highly-instrumented MOOC delivery platforms, by using participation in automatically-extracted online forum topics as items. The challenge is to formalise the Guttman scale educational constraint and incorporate it into topic models. To favour topics that automatically conform to a Guttman scale, we introduce a novel regularisation into non-negative matrix factorisation-based topic modelling. We demonstrate the suitability of our approach with both quantitative experiments on three Coursera MOOCs, and with a qualitative survey of topic interpretability on two MOOCs by domain expert interviews.

There has been a growing interest in recommending trips for tourists using location-based social networks. The challenge of trip recommendation not only lies in searching for relevant points-of-interest (POIs) to form a personalized trip, but also selecting the best time of day to visit the POIs. Popular POIs can be too crowded during peak times, resulting in long queues and delays. In this work, we propose the Personalized Crowd-aware Trip Recommendation (PersCT) algorithm to recommend personalized trips that also avoid the most crowded times of the POIs. We model the problem as an extension of the Orienteering Problem with multiple constraints. We extract user interests by collaborative filtering and we propose an extension of the Ant Colony Optimisation algorithm to merge user interests with POI popularity and crowdedness data to recommend trips. We evaluate our algorithm using foot traffic information obtained from a real-life pedestrian sensor dataset and user travel histories extracted from a Flickr photo dataset. We show that our algorithm out-performs several benchmarks in achieving a balance between conflicting objectives by satisfying user interests while reducing the crowdedness of the trips.

Energy usage of large-scale data centers has become a major concern for cloud providers. There has been an active effort in techniques for the minimization of the energy consumed in the data centers. However, most approaches lack the analysis and application of real cloud backend traces. In existing approaches, the variation of cloud workloads and its effect on the performance of the solutions are not investigated. Furthermore, the focus of existing approaches is on virtual machine migration and placement algorithms, with little regard to tailoring virtualmachine configuration to workload characteristics, which can further reduce the energy consumption and resource wastage in a typical data center. To address these weaknesses and challenges, we propose a new architecture for cloud resource allocation that maps groups of tasks to customized virtual machine types. This mapping is based on the task usage patterns obtained from the analysis of the historical data extracted from utilization traces. In our work, the energy consumption is decreased via efficient resource allocation based on the actual resource usage of tasks. Experimental results show that, when resources are allocated based on the discovered usage patterns, significant energy saving can be achieved.

While cloud computing has facilitated easy and affordable access to IT resources, it has also introduced a wide range of security risks from almost every layer and component of cloud systems. In this paper, we focus on one risk at the virtual machine level and the co-resident attack, where by constructing various types of side channels, malicious users can obtain sensitive information from other virtual machines that co-locate on the same physical server. Most previous work has focused on the elimination of side channels, or more generally speaking, the possible countermeasures after attackers co-locate with their targets. In contrast, we provide a different perspective, and propose a defence mechanism that makes it difficult and expensive for attackers to achieve co-residence in the first place. Specifically, we first identify the potential differences between the behaviors of attackers and legal users. Second, we apply clustering analysis and semi-supervised learning techniques to classify users. Third, we model the problem as a two-player security game, and give a detailed analysis of the optimum strategies for both players. Finally, we demonstrate that the attacker's overall cost is increased dramatically by one-to-two orders of magnitude as a result of our defence mechanism.

The growth in pervasive network infrastructure called the Internet of Things (IoT) enables a wide range of physical objects and environments to be monitored in fine spatial and temporal detail. The detailed, dynamic data that are collected in large quantities from sensor devices provide the basis for a variety of applications. Automatic interpretation of these evolving large data is required for timely detection of interesting events. This article develops and exemplifies two new relatives of the visual assessment of tendency (VAT) and improved visual assessment of tendency (iVAT) models, which uses cluster heat maps to visualize structure in static datasets. One new model is initialized with a static VAT/iVAT image, and then incrementally (hence inc-VAT/inc-iVAT) updates the current minimal spanning tree (MST) used by VAT with an efficient edge insertion scheme. Similarly, dec-VAT/dec-iVAT efficiently removes a node from the current VAT MST. A sequence of inc-iVAT/dec-iVAT images can be used for (visual) anomaly detection in evolving data streams and for sliding window based cluster assessment for time series data. The method is illustrated with four real datasets (three of them being smart city IoT data). The evaluation demonstrates the algorithms’ ability to successfully isolate anomalies and visualize changing cluster structure in the streaming data.

Bioinformatics (2014) 30(19), 2832–2833 doi: 10.1093/bioinformatics/btu381 The above article contained the following errors that have been corrected: The original URL given for the MATLAB implementation of LICRE is no longer viable and has been changed from http://ww2.cs.mu.oz.au/∼gwong/LICRE to https://sites.google.com/site/licrerepository/. The received manuscript history date for this article was incorrectly given as November 23, 2014 and has been corrected to November 23, 2013.

Mutual information (MI) based approaches are a popular feature selection paradigm. Although the stated goal of MI-based feature selection is to identify a subset of features that share the highest mutual information with the class variable, most current MI-based techniques are greedy methods that make use of low dimensional MI quantities. The reason for using low dimensional approximation has been mostly attributed to the difficulty associated with estimating the high dimensional MI from limited samples. In this paper, we argue a different viewpoint that, given a very large amount of data, the high dimensional MI objective is still problematic to be employed as a meaningful optimization criterion, due to its overfitting nature: the MI almost always increases as more features are added, thus leading to a trivial solution which includes all features. We propose a novel approach to the MI-based feature selection problem, in which the overfitting phenomenon is controlled rigourously by means of a statistical test. We develop local and global optimization algorithms for this new feature selection model, and demonstrate its effectiveness in the applications of explaining variables and objects.

There have been a large number of external validity indices proposed for cluster validity. One such class of cluster comparison indices is the information theoretic measures, due to their strong mathematical foundation and their ability to detect non-linear relationships. However, they are devised for evaluating crisp (hard) partitions. In this paper, we generalize eight information theoretic crisp indices to soft clusterings, so that they can be used with partitions of any type (i.e., crisp or soft, with soft including fuzzy, probabilistic and possibilistic cases). We present experimental results to demonstrate the effectiveness of the generalized information theoretic indices.

While the services-based model of cloud computing makes more and more IT resources available to a wider range of customers, the massive amount of data in cloud platforms is becoming a target for malicious users. Previous studies show that attackers can co-locate their virtual machines (VMs) with target VMs on the same server, and obtain sensitive information from the victims using side channels. This paper investigates VM allocation policies and practical countermeasures against this novel kind of co-resident attack by developing a set of security metrics and a quantitative model. A security analysis of three VM allocation policies commonly used in existing cloud computing platforms reveals that the server's configuration, oversubscription and background traffic have a large impact on the ability to prevent attackers from co-locating with the targets. If the servers are properly configured, and oversubscription is enabled, the best policy is to allocate new VMs to the server with the most VMs. Based on these results, a new strategy is introduced that effectively decreases the probability of attackers achieving co-residence. The proposed solution only requires minor changes to current allocation policies, and hence can be easily integrated into existing cloud platforms to mitigate the threat of co-resident attacks.

Graphs are a powerful representation of relational data, such as social and biological networks. Often, these entities form groups and are organised according to a latent structure. However, these groupings and structures are generally unknown and it can be difficult to identify them. Graph clustering is an important type of approach used to discover these vertex groups and the latent structure within graphs. One type of approach for graph clustering is non-negative matrix factorisation However, the formulations of existing factorisation approaches can be overly relaxed and their groupings and results consequently difficult to interpret, may fail to discover the true latent structure and groupings, and converge to extreme solutions. In this paper, we propose a new formulation of the graph clustering problem that results in clusterings that are easy to interpret. Combined with a novel algorithm, the clusterings are also more accurate than state-of-the-art algorithms for both synthetic and real datasets.

Most current mutual information (MI) based feature selection techniques are greedy in nature thus are prone to sub-optimal decisions. Potential performance improvements could be gained by systematically posing MI-based feature selection as a global optimization problem. A rare attempt at providing a global solution for the MI-based feature selection is the recently proposed Quadratic Programming Feature Selection (QPFS) approach. We point out that the QPFS formulation faces several non-trivial issues, in particular, how to properly treat feature `self-redundancy' while ensuring the convexity of the objective function. In this paper, we take a systematic approach to the problem of global MI-based feature selection. We show how the resulting NP-hard global optimization problem could be efficiently approximately solved via spectral relaxation and semi-definite programming techniques. We experimentally demonstrate the efficiency and effectiveness of these novel feature selection frameworks.

MOTIVATION: Recent advances in high-throughput lipid profiling by liquid chromatography electrospray ionization tandem mass spectrometry (LC-ESI-MS/MS) have made it possible to quantify hundreds of individual molecular lipid species (e.g. fatty acyls, glycerolipids, glycerophospholipids, sphingolipids) in a single experimental run for hundreds of samples. This enables the lipidome of large cohorts of subjects to be profiled to identify lipid biomarkers significantly associated with disease risk, progression and treatment response. Clinically, these lipid biomarkers can be used to construct classification models for the purpose of disease screening or diagnosis. However, the inclusion of a large number of highly correlated biomarkers within a model may reduce classification performance, unnecessarily inflate associated costs of a diagnosis or a screen and reduce the feasibility of clinical translation. An unsupervised feature reduction approach can reduce feature redundancy in lipidomic biomarkers by limiting the number of highly correlated lipids while retaining informative features to achieve good classification performance for various clinical outcomes. Good predictive models based on a reduced number of biomarkers are also more cost effective and feasible from a clinical translation perspective. RESULTS: The application of LICRE to various lipidomic datasets in diabetes and cardiovascular disease demonstrated superior discrimination in terms of the area under the receiver operator characteristic curve while using fewer lipid markers when predicting various clinical outcomes. AVAILABILITY AND IMPLEMENTATION: The MATLAB implementation of LICRE is available from http://ww2.cs.mu.oz.au/∼gwong/LICRE

Blockmodelling is an important technique in social network analysis for discovering the latent structure in graphs. A blockmodel partitions the set of vertices in a graph into groups, where there are either many edges or few edges between any two groups. For example, in the reply graph of a question and answer forum, blockmodelling can identify the group of experts by their many replies to questioners, and the group of questioners by their lack of replies among themselves but many replies from experts.

We discuss a new formulation of a fuzzy validity index that generalizes the Newman-Girvan (NG) modularity function. The NG function serves as a cluster validity functional in community detection studies. The input data is an undirected graph G = (V, E) that represents a social network. Clusters in V correspond to socially similar substructures in the network. We compare our fuzzy modularity to an existing modularity function using the well-studied Karate Club data set.

Conventional non-negative tensor factorization (NTF) methods assume there is only one tensor that needs to be decomposed to low-rank factors. However, in practice data are usually generated from different time periods or by different class labels, which are represented by a sequence of multiple tensors associated with different labels. This raises the problem that when one needs to analyze and compare multiple tensors, existing NTF is unsuitable for discovering all potentially useful patterns: 1) if one factorizes each tensor separately, the common information shared by the tensors is lost in the factors, and 2) if one concatenates these tensors together and forms a larger tensor to factorize, the intrinsic discriminative subspaces that are unique to each tensor are not captured. The cause of such an issue is from the fact that conventional factorization methods handle data observations in an unsupervised way, which only considers features and not labels of the data. To tackle this problem, in this paper we design a novel factorization algorithm called CDNTF (common and discriminative subspace non-negative tensor factorization), which takes both features and class labels into account in the factorization process. CDNTF uses a set of labelled tensors as input and computes both their common and discriminative subspaces simultaneously as output. We design an iterative algorithm that solves the common and discriminative subspace factorization problem with a proof of convergence. Experiment results on solving graph classification problems demonstrate the power and the effectiveness of the subspaces discovered by our method.

Analysing and modelling the characteristics of virtual machine (VM) usage gives cloud providers crucial information when dimensioning cloud infrastructure and designing appropriate allocation policies. In addition, administrators can use these models to build a normal behaviour profile of job requests, in order to differentiate malicious and normal activities. Finally, it allows researchers to design more accurate simulation environments. An open challenge is to empirically develop and verify an accurate model of VM usage for users in these applications. In this paper, we study the VM usage in the popular Amazon EC2 and Windows Azure cloud platforms, in terms of the VM request arrival and departure processes, and the number of live VMs in the system. We find that both the VM request arrival and departure processes exhibit self-similarity and follow the power law distribution. Our analysis also shows that the autoregressive integrated moving average (ARIMA) model can be used to fit and forecast the VM demands, which is an important requirement for managing the workload in cloud services.

In large and complex graphs of social, chemical/biological, or other relations, frequent substructures are commonly shared by different graphs or by graphs evolving through different time periods. Tensors are natural representations of these complex time-evolving graph data. A factorization of a tensor provides a high-quality low-rank compact basis for each dimension of the tensor, which facilitates the interpretation of frequent substructures of the original graphs. However, the high computational cost of tensor factorization makes it infeasible for conventional tensor factorization methods to handle large graphs that evolve frequently with time. To address this problem, in this paper we propose a novel iterative tensor factorization (ITF) method whose time complexity is linear in the cardinalities of all dimensions of a tensor. This low time complexity means that when using tensors to represent dynamic graphs, the computational cost of ITF is linear in the size (number of edges/vertices) of graphs and is also linear in the number of time periods over which the graph evolves. More importantly, an error estimation of ITF suggests that its factorization correctness is comparable to that of the standard factorization method. We empirically evaluate our method on publication networks and chemical compound graphs, and demonstrate that ITF is an order of magnitude faster than the conventional method and at the same time preserves factorization quality. To the best of our knowledge, this research is the first work that uses important frequent substructures to speed up tensor factorizations for mining dynamic graphs.

Existing graph compression techniquesmostly focus on static graphs. However for many practical graphs such as social networks the edge weights frequently change over time. This phenomenon raises the question of how to compress dynamic graphs while maintaining most of their intrinsic structural patterns at each time snapshot. In this paper we show that the encoding cost of a dynamic graph is proportional to the heterogeneity of a three dimensional tensor that represents the dynamic graph. We propose an effective algorithm that compresses a dynamic graph by reducing the heterogeneity of its tensor representation, and at the same time also maintains a maximum lossy compression error at any time stamp of the dynamic graph. The bounded compression error benefits compressed graphs in that they retain good approximations of the original edge weights, and hence properties of the original graph (such as shortest paths) are well preserved. To the best of our knowledge, this is the first work that compresses weighted dynamic graphs with bounded lossy compression error at any time snapshot of the graph.

Blockmodelling is an important technique for decomposing graphs into sets of roles. Vertices playing the same role have similar patterns of interactions with vertices in other roles. These roles, along with the role to role interactions, can succinctly summarise the underlying structure of the studied graphs. As the underlying graphs evolve with time, it is important to study how their blockmodels evolve too. This will enable us to detect role changes across time, detect different patterns of interactions, for example, weekday and weekend behaviour, and allow us to study how the structure in the underlying dynamic graph evolves. To date, there has been limited research on studying dynamic blockmodels. They focus on smoothing role changes between adjacent time instances. However, this approach can overfit during stationary periods where the underling structure does not change but there is random noise in the graph. Therefore, an approach to a) find blockmodels across spans of time and b) to find the stationary periods is needed. In this paper, we propose an information theoretic framework, SeqiBloc, combined with a change point detection approach to achieve a) and b). In addition, we propose new vertex equivalence definitions that include time, and show how they relate back to our information theoretic approach. We demonstrate their usefulness and superior accuracy over existing work on synthetic and real datasets.

Data mining techniques for understanding how graphs evolve over time have become increasingly important. Evolving graphs arise naturally in diverse applications such as computer network topologies, multiplayer games and medical imaging. A natural and interesting problem in evolving graph analysis is the discovery of compact subgraphs that change in a similar manner. Such subgraphs are known as regions of correlated change and they can both summarise change patterns in graphs and help identify the underlying events causing these changes. However, previous techniques for discovering regions of correlated change suffer from limited scalability, making them unsuitable for analysing the evolution of very large graphs. In this paper, we introduce a new algorithm called ciForager, that addresses this scalability challenge and offers considerable improvements. The efficiency of ciForager is based on the use of new incremental techniques for detecting change, as well as the use of Voronoi representations for efficiently determining distance. We experimentally show that ciForager can achieve speedups of up to 1000 times over previous approaches. As a result, it becomes feasible for the first time to discover regions of correlated change in extremely large graphs, such as the entire BGP routing topology of the Internet.

In recent years, the summarisation and decomposition of social networks has become increasingly popular, from community finding to role equivalence. However, these approaches concentrate on one type of model only. Generalised blockmodelling decomposes a network into independent, interpretable, labeled blocks, where the block labels summarise the relationship between two sets of users. Existing algorithms for fitting generalised blockmodels do not scale beyond networks of 100 vertices. In this paper, we introduce two new algorithms, one based on genetic algorithms and the other on simulated annealing, that is at least two orders of magnitude faster than existing algorithms and obtaining similar accuracy. Using synthetic and real datasets, we demonstrate their efficiency and accuracy and show how generalised blockmodelling and our new approaches enable tractable network summarisation and modelling of medium sized networks. 1

There is growing interest in studying dynamic graphs, or graphs that evolve with time. In this work, we investigate a new type of dynamic graph analysis – finding regions of a graph that are evolving in a similar manner and are topologically similar over a period of time. For example, these regions can be used to group a set of changes having a common cause in event detection and fault diagnosis. Prior work [6] has proposed a greedy framework called cSTAG to find these regions. It was accurate in datasets where the regions are temporally and spatially well separated. However, in cases where the regions are not well separated, cSTAG produces incorrect groupings. In this paper, we propose a new algorithm called regHunter. It treats the region discovery problem as a multi-objective optimisation problem, and it uses a multi-level graph partitioning algorithm to discover the regions of correlated change. In addition, we propose an external clustering validation technique, and use several existing internal measures to evaluate the accuracy of regHunter. Using synthetic datasets, we found regHunter is significantly more accurate than cSTAG in dynamic graphs that have regions with small separation. Using two real datasets – the access graph of the 1998 World Cup website, and the BGP connectivity graph during the landfall of Hurricane Katrina – we found regHunter obtained more accurate results than cSTAG. Furthermore, regHunter was able to discover two interesting regions for the World Cup access graph that CSTAG was not able to find.