Sparse online learning has received extensive attention during the past few years. Most of existing algorithms that utilize ℓ1-norm regularization or ℓ1-ball projection assume that the feature space is fixed or changes by following explicit constraints. However, this assumption does not always hold in many real applications. Motivated by this observation, we propose a new online learning algorithm tailored for data streams described by open feature spaces, where new features can be occurred, and old features may be vanished over various time spans. Our algorithm named RSOL provides a strategy to adapt quickly to such feature dynamics by encouraging sparse model representation with an ℓ1- and ℓ2 -mixed regularizer. We leverage the proximal operator of the ℓ1,2 -mixed norm and show that our RSOL algorithm enjoys a closed-form solution at each iteration. A sub-linear regret bound of our proposed algorithm is guaranteed with a solid theoretical analysis. Empirical results benchmarked on nine streaming datasets validate the effectiveness of the proposed RSOL method over three state-of-the-art algorithms.

Simplicial neural networks (SNNs) were proposed to generate higher-order simplicial complex representations as vectors that encode not only pairwise relationships but also higher-order interactions between nodes. Although these vectors allowing us to consider richer data representations compared to typical graph convolution, most real-world graphs associated with molecule or human-related activities are often sensitive and might contain confidential information, e.g., molecular geometry or friend lists. However, little works investigate the potential threats for these simplicial complexes (higher-order interactions between nodes). We name this threat by Simplicial Complexes Reconstruction Attack (SCRA) and conduct this attack by studying whether the vectors can be inverted to (approximately) recover the simplicial complexes who used to generate them. Specifically, we first generate the vectors via a k-simplex2vec approach that extends the node2vec algorithm to simplices of higher dimensions to associate Euclidean vectors to simplicial complexes. We then present a Simplex2vec Backward algorithm to perform the SCRA on k-simplex2vec vectors by pointwise mutual information (PMI) matrix reconstruction.

Releasing the representations of nodes in real-world graphs associated with people or human-related activities, such as social and economic networks, gives adversaries a potential way to infer the sensitive information of edges. For example, graph convolutional layers initially aggregate node representations with their neighbors before passing them through non-linear activation functions. Hence, the released node representations may potentially breach edge privacy of the node neighbors. Thus, in this work, we study whether representations can be inverted to recover the graph used to generate them. We study three types of outputs that are trained on the graph, i.e., representations output from graph convolutional networks (GCNs), representations output from graph attention networks (GATs), and representations output from our proposed simplicial neural networks (SNNs). Unlike the first two types of representations that only encode pairwise relationships, the third type of representation, i.e., SNN outputs, encodes higher-order interactions (e.g., homological features) between nodes. We propose two graph reconstruction attacks (GRAs), i.e., Type-1 and Type-2 attacks, to recover a graph’s adjacency matrix from the three types of outputs trained on the graph. Specifically, our GRAs utilize a graph-decoder to minimize the reconstruction loss for the generated adjacency matrix via back-propagation. Our conclusions are two folds. First, our Type-2 attack achieves the best performance among all current GRAs. Second, we find that GCN outputs obtain the least precision and AUC on five datasets, followed by the GAT outputs, followed by the SNN outputs. Therefore, the SNN outputs reveal the lowest privacy-preserving ability to defend the GRAs. We further propose an unbiased multi-bit rectifier, by which the server can communicate with the nodes to privately collect their representations to defend the GRAs from potential adversaries.

Effective streaming feature selection in dynamic on-line environments is essential in numerous applications. However, most existing methods evaluate high-dimensional features individually and ignore the potentially pertainable group structures of features. Moreover, the class imbalance underlying streaming data may further decrease the discriminative efficacy of the selected features, resulting in deteriorated classification performance. Motivated by this observation, we propose a proximal cost-sensitive sparse group online learning (PCSGOL) framework to handle imbalanced and high-dimensional streaming data. Specifically, we formulate this issue as a new cost-sensitive online optimization problem by leveraging the ℓ2-norm, ℓ1-norm, and group-wise sparsity constraints in the dual averaging regularization. The average weighted distance is also introduced in PCSGOL to achieve stable prediction results. We mathematically derive closed-form solutions to the optimization problems with four modified hinge loss functions, leading to four variants of PCSGOL. Extensive empirical studies on real-world streaming datasets demonstrate the effectiveness of our proposed method.

Most existing online learning methods focus on mining ever-evolving streaming data based on the principle of first-order optimization. However, one drawback of these methods is the slow convergence rate in each iteration, resulting in sub-optimal solutions and deteriorated performance. Second-order methods, while are able to provide faster convergence, have been under-studied due to the high cost of computing the curvature information. To address this problem, in this paper, we develop a second-order projection dual averaging based online learning (SPDA) method to effectively handle high-throughput streaming data. By fully exploiting the regularized dual averaging optimization, the second-order information, and an optimal projection operator, SPDA converges fast with fairly optimal solutions. Two speed-up versions of SPDA, i.e., SPDA-diag and SPDA-sketch, are developed via the diagonal operator and Hessian sketch, respectively. Theoretical derivations on the regret bound of SPDA establish a solid convergence guarantee for this method. Extensive experiments demonstrate the efficacy of the proposed algorithms on large-scale online learning tasks, such as online binary and multi-class classification and online anomaly detection, shedding light on their potential wide applications.

For decades, research in natural language processing (NLP) has focused on summarization. Sequence-to-sequence models for abstractive summarization have been studied extensively, yet generated summaries commonly suffer from fabricated content, and are often found to be near-extractive. We argue that, to address these issues, summarizers need to acquire the co-references that form multiple types of relations over input sentences, e.g., 1-to-N, N-to-1, and N-to-N relations, since the structured knowledge for text usually appears on these relations. By allowing the decoder to pay different attention to the input sentences for the same entity at different generation states, the structured graph representations generate more informative summaries. In this paper, we propose a hierarchical graph attention networks (HGATs) for abstractive summarization with a topic-sensitive PageRank augmented graph. Specifically, we utilize dual decoders, a sequential sentence decoder, and a graph-structured decoder (which are built hierarchically) to maintain the global context and local characteristics of entities, complementing each other. We further design a greedy heuristic to extract salient users' comments while avoiding redundancy to drive a model to better capture entity interactions. Our experimental results show that our models produce significantly higher ROUGE scores than variants without graph-based attention on both SSECIF and CNN/Daily Mail (CNN/DM) datasets.

Private information can either take the form of key phrases that are explicitly contained in the text or be implicit. For example, demographic information about the author of a text can be predicted with above-chance accuracy from linguistic cues in the text itself. Letting alone its explicitness, some of the private information correlates with the output labels and therefore can be learned by a neural network. In such a case, there is a tradeoff between the utility of the representation (measured by the accuracy of the classification network) and its privacy. This problem is inherently a multi-objective problem because these two objectives may conflict, necessitating a trade-off. Thus, we explicitly cast this problem as multi-objective optimization (MOO) with the overall objective of finding a Pareto stationary solution. We, therefore, propose a multiple-gradient descent algorithm (MGDA) that enables the efficient application of the Frank-Wolfe algorithm [10] using the line search. Experimental results on sentiment analysis and part-of-speech (POS) tagging show that MGDA produces higher-performing models than most recent proxy objective approaches, and performs as well as single objective baselines.