Graph neural networks (GNNs) have exhibited state-of-the-art performance across a wide range of domains. Yet message-passing GNNs suffer from over-squashing---exponential compression of long-range information from distant nodes---which limits expressivity. Rewiring techniques can ease this bottleneck, but their practical impacts are unclear due to the lack of a direct empirical over-squashing metric. We propose a topology-focused method for assessing over-squashing between node pairs using the decay rate of their mutual sensitivity. We then extend these pairwise assessments to graph-level statistics. Coupling these metrics with a within-graph causal design, we quantify how rewiring strategies affect over-squashing on diverse graph- and node-classification benchmarks. Our extensive empirical analyses show that most graph classification datasets suffer from over-squashing (but to various extents), and rewiring effectively mitigates it---though the degree of mitigation, and its translation into performance gains, varies by dataset and method. We also found that over-squashing is less notable in node classification datasets, where rewiring often increases over-squashing, and performance variations are uncorrelated with over-squashing changes. These findings suggest that rewiring is most beneficial when over-squashing is both substantial and corrected with restraint---while overly aggressive rewiring, or rewiring applied to minimally over-squashed graphs, is unlikely to help and may even harm performance. Our plug-and-play diagnostic tool lets practitioners decide whether rewiring is likely to pay off.

Personal Identification Numbers (PINs) are widely used for authentication on mobile devices such as smartphones, which act as gateways to many important accounts (e.g., financial, email, etc.). Unfortunately, people tend to choose easy-to-recall PINs involving birthdays, anniversaries, or keypad patterns that are vulnerable to guessing attacks. System-assigned PINs can improve PIN security in this regard; however, they have usability problems such as feeling the need to store the assigned PIN, longer login times, and difficulty remembering. In this paper, we propose, design, and evaluate a set of short training techniques (16-34 seconds) inspired by implicit learning techniques, to improve the usability of system-assigned PINs. We evaluated our designs in a two-session user study with 184 university students. Our results show that some designs offer significant improvements in the login success rate, login times, and user perceptions. These advantages are in addition to our design’s short single-session training, making it more compatible with typical registration workflows than previously proposed multisession training techniques.

Graph Neural Networks (GNNs) have emerged as the predominant method for analyzing graph-structured data. However, canonical GNNs have limited expressive power and generalization capability, thus triggering the development of more expressive yet computationally intensive methods. One such approach is to create a series of perturbed versions of input graphs and then repeatedly conduct multiple message-passing operations on all variations during training. Despite their expressive power, this approach does not scale well on larger graphs. To address this scalability issue, we introduce Scalable Expressiveness through Preprocessed Graph Perturbation (SE2P). This model offers a flexible, configurable balance between scalability and generalizability with four distinct configuration classes. Our extensive experiments demonstrate that SE2P can enhance generalizability compared to benchmarks while achieving significant speed improvements of up to 8-fold.

Subgraph classification is an emerging field in graph representation learning where the task is to classify a group of nodes (i.e., a subgraph) within a graph (e.g., identifying rare diseases given a collection of phenotypes). Graph neural network (GNN) solutions for node, link, and graph tasks fail to perform well on subgraph classification as they do not capture the external topology of the subgraph (i.e., how the subgraph is located within the larger graph). The current state-of-the-art models address this shortcoming through either labeling tricks or multiple message-passing channels, which are computationally expensive and not scalable to large graphs. To address the scalability issue while maintaining generalization, we propose Stochastic Subgraph Neighborhood Pooling (SSNP), which jointly aggregates the subgraph and its neighborhood (i.e., external topology) information while removing the need for any computationally expensive operations (e.g. labeling tricks). Our extensive experiments demonstrate that SSNP outperforms or is comparable to state-of-the-art methods while being up to 13x faster in runtime.

Link prediction is a fundamental problem for graph-structured data (e.g., social networks, drug side-effect networks, etc.). Graph neural networks have offered robust solutions for this problem, specifically by learning the representation of the subgraph enclosing the target link (i.e., pair of nodes). However, these solutions do not scale well to large graphs as extraction and operation on enclosing subgraphs are computationally expensive. This paper presents a scalable link prediction solution, that we call ScaLed, which utilizes sparse enclosing subgraphs to make predictions. To extract sparse enclosing subgraphs, ScaLed takes multiple random walks from a target pair of nodes, then operates on the sampled enclosing subgraph induced by all visited nodes. By leveraging the smaller sampled enclosing subgraph, ScaLed can scale to larger graphs with much less overhead while maintaining high accuracy. Through comprehensive experiments, we have shown that ScaLed can produce comparable accuracy to those reported by the existing subgraph representation learning frameworks while being less computationally demanding.

We focus on making recommendations for a new group of users whose preferences are unknown, but we are given the decisions of other groups. By formulating this problem as group recommendation from group implicit feedback, we focus on two of its practical instances: group decision prediction and reverse social choice. Given a set of groups and their observed decisions, group decision prediction intends to predict the decision of a new group of users, whereas reverse social choice aims to infer the preferences of those users involved in observed group decisions. These two problems are of interest to not only group recommendation, but also to personal privacy when the users intend to conceal their personal preferences but have participated in group decisions. To tackle these two problems, we propose and study DeepGroup---a deep learning approach for group recommendation with group implicit data. We empirically assess the predictive power of DeepGroup on various real-world datasets and group decision rules. Our extensive experiments not only demonstrate the efficacy of DeepGroup but also shed light on the privacy-leakage concerns of some decision-making processes.

Passphrases offer an alternative to traditional passwords which aim to be stronger and more memorable. However, users tend to choose short passphrases with predictable patterns that may reduce the security they offer. To explore the potential of long passphrases, we formulate a set of passphrase policies and guidelines aimed at supporting their creation and use. Through a 39-day user study we analyze the usability and security of passphrases generated using our policies and guidelines. Our analysis indicates these policies lead to reasonable usability and promising security for some use cases, and that there are some common pitfalls in free-form passphrase creation. Our results suggest that our policies can support the use of long passphrases.

Variational Autoencoders (VAEs) have shown to be effective for recommender systems with implicit feedback (e.g., browsing history, purchasing patterns, etc.). However, a little attention is given to ensembles of VAEs, that can learn user and item representations jointly. We introduce Joint Variational Autoencoder (JoVA), an ensemble of two VAEs, which jointly learns both user and item representations to predict user preferences. This design allows JoVA to capture user-user and item-item correlations simultaneously. We also introduce JoVA-Hinge, a JoVA's extension with a hinge-based pairwise loss function, to further specialize it in recommendation with implicit feedback. Our extensive experiments on four real-world datasets demonstrate that JoVA-Hinge outperforms a broad set of state-of-the-art methods under a variety of commonly-used metrics. Our empirical results also illustrate the effectiveness of JoVA-Hinge for handling users with limited training data.

Social choice theory provides a principled framework for the aggregation of individuals' preferences in support of group decision‐making and recommendation. Much of this work, however, either assumes that individuals' subjective preferences (and thus, their votes) are correctly specified by the individuals themselves, or alternatively that the votes of individuals are noisy estimates of some underlying ground truth over rankings of alternatives. We argue that neither model appropriately addresses some of the issues which arise in the context of group‐recommendation domains where individuals have subjective preferences but for some reason (eg, the high cognitive burden, concerns about privacy, etc.) may instead vote using a noisy estimate of their subjective preference rankings. In this paper, we propose a general probabilistic framework for modeling noisy subjective preferences, and explore the accuracy and reliability of four well‐studied voting rules under various noise models. Our results demonstrate that there is no single reliable method amongst the examined methods. Specifically, we observe the change in noise distribution can flip one method from being the most reliable to the least.

The known adversary threat model has drawn growing attention of the security community. The known adversary is any individual with elevated first-hand knowledge of a potential victim and/or elevated access to a potential victim's devices. However, little attention is given on how to carefully recruit paired participants for user studies, who are qualified as legitimate known adversaries. Also, there is no formal framework for detecting and quantifying the known adversary. We develop three models, inspired by Social Psychology literature, to quantify the known adversary in paired user studies, and test them using a case study. Our results indicate that our proposed adapted-relationship closeness inventory and known adversary inventory models could accurately quantify and predict the known adversary. We subsequently discuss how social network analysis and artificial intelligence can automatically quantify the known adversary using publicly available data. We further discuss how these technologies can help the development of privacy assistants, which can automatically mitigate the risk of sharing sensitive information with potential known adversaries.

Fallback authentication is the backup authentication method used when the primary authentication method (e.g., passwords, biometrics, etc.) fails. Currently, widely-deployed fallback authentication methods (e.g., security questions, email resets, and SMS resets) suffer from documented security and usability flaws that threaten the security of accounts. These flaws motivate us to design and study Geographical Security Questions (GeoSQ), a system for fallback authentication. GeoSQ is an Android application that utilizes autobiographical location data for fallback authentication. We performed security and usability analyses of GeoSQ through an in-person two-session lab study (n=36, 18 pairs). Our results indicate that GeoSQ exceeds the security of its counterparts, while its usability (specifically login time and memorability) has room for improvement.

We propose and study the use of geographic hints to aid memorability of passphrase-style authentication secrets. Geographic hints are map locations that are selected by the user at the time of passphrase creation, and shown to the user as a hint at the time of passphrase login. We implement the GeoHints system and analyze how geographic hints impact the usability and security of passphrase-style secrets in a multi-session user study (n=38). The study involved testing for multiple passphrase interference-each participant was asked to recall 4 distinct passphrases. Our study indicates that while geographic hints showed promise for reducing memory interference, GeoHints (as implemented) does not produce a viable authentication system, as the login success rate was 25% 7-11 days after passphrase selection. We analyze the root causes of login errors, finding that most were due to inexact recall of free-form text input. This finding points towards opportunities to improve the system design, and we suggest improvements that we believe will lead to viable systems that employ geographic hints.

We design and explore the usability and security of two geographic authentication schemes: GeoPass and GeoPassNotes. GeoPass requires users to choose a place on a digital map to authenticate with (a location password). GeoPassNotes-an extension of GeoPass-requires users to annotate their location password with a sequence of words that they can associate with the location (an annotated location password). In GeoPassNotes, users are authenticated by correctly entering both a location and an annotation. We conducted user studies to test the usability and assess the security of location passwords and annotated location passwords. The results indicate that both the variants are highly memorable, and that annotated location passwords may be more advantageous than location passwords alone due to their increased security and the minimal usability impact introduced by the annotation.

Social networks facilitate a variety of social, economic, and political interactions. Homophily---the tendency for people to associate or interact with similar peers---and social influence---the tendency to adopt certain characteristics of those with whom one interacts---suggest that preferences (e.g., over products, services, political parties) are likely to be correlated among people whom directly interact in a social network. We develop a model, preference-oriented social networks, that captures such correlations of individual preferences, where preferences take the form of rankings over a set of options. We develop probabilistic inference methods for predicting individual preferences given observed social connections and partial observations of the preferences of others in the network. We exploit these predictions in a social choice context to make group decisions or recommendations even when the preferences of some group members are unobserved. Experiments demonstrate the effectiveness of our algorithms and the improvements made possible by accounting for social ties.

We provide a simple yet powerful demonstration of how an unobtrusive change to a graphical password interface can modify the distribution of user chosen passwords, and thus possibly the security it provides. The only change to the interface is how the background image is presented to the user in the password creation phase--we call the effect of this change the "presentation effect". We demonstrate the presentation effect by performing a comparative user study of two groups using the same background image, where the image is presented in two different ways prior to password creation. Our results show a statistically different distribution of user's graphical passwords, with no observed usability consequences.

We design, implement, and evaluate GeoPass: an interface for digital map-based authentication where a user chooses a place as his or her password (i.e., a "location-password"). We conducted a multi-session in-lab/at-home user study to evaluate the usability, memorability, and security of location-passwords created with GeoPass. The results of our user study found that 97% of users were able to remember their location-password over the span of 8-9 days and most without any failed login attempts. Users generally welcomed GeoPass; all of the users who completed the study reported that they would at least consider using GeoPass for some of their accounts. We also perform an in-depth usability and security analysis of location-passwords. Our security analysis includes the effect of information that could be gleaned from social engineering. The results of our security analysis show that location-passwords created with GeoPass can have reasonable security against online attacks, even when accounting for social engineering attacks. Based on our results, we suggest GeoPass would be most appropriate in contexts where logins occur infrequently, e.g., as an alternative to secondary authentication methods used for password resets, or for infrequently used online accounts.

We introduce a new class of authentication schemes called "video-passwords", which require the user to watch and remember parts of a given video (e.g., a sequence of scenes, movements, and/or sounds). We propose four different video-password schemes, describe their prototypes, and analyze their security. Under certain parameters, the security of some of these schemes appears to be theoretically comparable to traditional text passwords. Video-passwords provide more than potentially better security; they also present a unique opportunity for businesses to consider -- advertising through the rich multimedia used in the login task. We suggest that the adoption of new schemes, such as video-passwords may be more likely in the presence of monetary incentives provided through advertising; we also discuss some ethical issues that may arise from such incentives.

Artificial societies—distributed systems of autonomous agents—are becoming increasingly important in open distributed environments, especially in e‐commerce. Agents require trust and reputation concepts to identify communities of agents with which to interact reliably. We have noted in real environments that adversaries tend to focus on exploitation of the trust and reputation model. These vulnerabilities reinforce the need for new evaluation criteria for trust and reputation models called exploitation resistance which reflects the ability of a trust model to be unaffected by agents who try to manipulate the trust model. To examine whether a given trust and reputation model is exploitation‐resistant, the researchers require a flexible, easy‐to‐use, and general framework. This framework should provide the facility to specify heterogeneous agents with different trust models and behaviors. This paper introduces a Distributed Analysis of Reputation and Trust (DART) framework. The environment of DART is decentralized and game‐theoretic. Not only is the proposed environment model compatible with the characteristics of open distributed systems, but it also allows agents to have different types of interactions in this environment model. Besides direct, witness, and introduction interactions, agents in our environment model can have a type of interaction called a reporting interaction, which represents a decentralized reporting mechanism in distributed environments. The proposed environment model provides various metrics at both micro and macro levels for analyzing the implemented trust and reputation models. Using DART, researchers have empirically demonstrated the vulnerability of well‐known trust models against both individual and group attacks.

Recent work has demonstrated that several trust and reputation models can be exploited by malicious agents with cyclical behaviour. In each cycle, the malicious agent with cyclical behaviour first regains a high trust value after a number of cooperations and then abuses its gained trust by engaging in a bad transaction. Using a game theoretic formulation, Salehi-Abari and White have proposed the AER model that is resistant to exploitation by cyclical behaviour. Their simulation results imply that FIRE, Regret, and a model due to Yu and Singh, can always be exploited with an appropriate value for the period of cyclical behaviour. Furthermore, their results demonstrate that this is not so for the proposed adaptive scheme. This paper provides a mathematical analysis of the properties of five trust models when faced with cyclical behaviour of malicious agents. Three main results are proven. First, malicious agents can always select a cycle period that allows them to exploit the four models of FIRE, Regret, Probabilistic models, and Yu and Singh indefinitely. Second, malicious agents cannot select a single, finite cycle period that allows them to exploit the AER model forever. Finally, the number of cooperations required to achieve a given trust value increases monotonically with each cycle. In addition to the mathematical analysis, this paper empirically shows how malicious agents can use the theorems proven in this paper to mount efficient attacks on trust models.

In many marketplaces consumers may interact with more than one supplier in order to achieve a particular goal. This paper takes the position that trust mediates agent interactions and that agent demands are likely to increase with increasing trust. Furthermore, trust of one agent in another is updated based upon a trust model. The model proposed in this paper is one in which agent demands can be divided amongst suppliers with the division determined by trust. The model evaluates five prominent trust models in a hypothetical marketplace and demonstrates empirically that FIRE, Regret, Probabilistic Trust Models and a model due to Yu and Singh can be exploited such that a consumer agent will continue to interact with a malicious agent despite periodic contract defaults by the malicious agent. Empirical studies support the hypothesis that adaptive trust models such as AER are resistant to this type of exploitation and discourage periodic or cyclical defaulting on contractual obligations.

We introduce and evaluate various methods for purely automated attacks against PassPoints-style graphical passwords. For generating these attacks, we introduce a graph-based algorithm to efficiently create dictionaries based on heuristics such as click-order patterns (e.g., five points all along a line). Some of our methods combine click-order heuristics with focus-of-attention scan-paths generated from a computational model of visual attention, yielding significantly better automated attacks than previous work. One resulting automated attack finds 7%-16% of passwords for two representative images using dictionaries of approximately 226entries (where the full password space is 243). Relaxing click-order patterns substantially increased the attack efficacy albeit with larger dictionaries of approximately 235entries, allowing attacks that guessed 48%-54% of passwords (compared to previous results of 1% and 9% on the same dataset for two images with 235guesses). These latter attacks are independent of focus-of-attention models, and are based on image-independent guessing patterns. Our results show that automated attacks, which are easier to arrange than human-seeded attacks and are more scalable to systems that use multiple images, require serious consideration when deploying basic PassPoints-style graphical passwords.

We present and evaluate various methods for purely automated attacks against click-based graphical passwords. Our purely automated methods combine click-order heuristics with focus-of-attention scan-paths generated from a computational model of visual attention. Our method results in a significantly better automated attack than previous work, guessing 8-15% of passwords for two representative images using dictionaries of less than 224.6entries, and about 16% of passwords on each of these images using dictionaries of less than 231.4entries (where the full password space is 243). Relaxing our click-order pattern substantially increased the efficacy of our attack albeit with larger dictionaries of 234.7entries, allowing attacks that guessed 48-54% of passwords (compared to previous results of 0.9% and 9.1% on the same two images with 235guesses). These latter automated attacks are independent of focus-of-attention models, and are based on image-independent guessing patterns. Our results show that automated attacks, which are easier to arrange than human-seeded attacks and are more scalable to systems that use multiple images, pose a significant threat.

This paper begins by reviewing different methods of automatic programming while emphasizing the technique of Ant Programming (AP). AP uses an ant foraging metaphor in which ants generate a program by moving through a graph. Generalized Ant Programming (GAP) uses a context-free grammar and an Ant Colony System (ACS) to guide the program generation search process. There are two enhancements to GAP that are proposed in this paper. These are: providing a heuristic for path termination inspired by building construction and a novel pheromone placement algorithm. Three well-known problems -- Quartic symbolic regression, multiplexer, and an ant trail problem -- are experimentally compared using enhanced GAP (EGAP) and GAP. The results of the experiments show the statistically significant advantage of using this heuristic function and pheromone placement algorithm of EGAP over GAP.

A swarm-based improvement to Genetic Programming (GP) is described and tested on the domain of symbolic regression in this paper. The motivating idea is to keep all of the benefits of genetic programming such as crossover and fitness proportional selection within a population of candidate solutions. The improvement comes in using swarm-based ideas similar to Ant Colony Optimization (ACO) to improve the operation of the crossover operator. Statistically significant results are reported in support of the hypothesis that ACO-inspired crossover can improve GP.