Graph classification has long been a focus of net-work mining, with graph kernel methods and representation learning at the forefront. Despite their success, many of these studies require heavy computation, making them impractical for large-scale datasets. In this paper, we design a novel structural feature extraction technique that leverages node subsets and random walk probabilities, presenting a scalable, unsupervised, and easily interpretable alternative. Initially, we partition each graph based on the structural roles of nodes. This process creates soft alignments of node subsets across graphs of varying sizes. Then, we measure the connection strengths within and between these subsets, which form the fingerprints for graph classification. Additionally, this technique can seamlessly incorporate node features. Through empirical assessment encompassing a broad range of graph datasets, we demonstrate that our method achieves high levels of computational efficiency while maintaining robust classification accuracy. Code and data are available at https://github.com/KXDY233/RWF.

Hyperlink prediction aims to predict interactions among multiple entries, constituting a practical yet challenging problem in the literature. While a handful of solutions have been proposed, they generally operate on the entire hypergraph. A practical subgraph-based solution not only enables better identification of localized characteristics of the central hyperedge but also alleviates scalability concerns. In this study, we present SSF, an innovative hyperlink prediction methodology based on Subgraph Structural Features. The rationale behind SSF is that hyperedges and non-hyperedges exhibit distinct local patterns, which can be unveiled through the assimilation of subgraph structural features. To this end, we utilize well-established structural heuristics such as walks and loops as the fundamental building blocks. We commence by extracting a subgraph encompassing each focal hyperedge, subsequently integrating an edge weakening scheme to facilitate feature extraction from the initial subgraph and its variations. The extracted feature vector is interpretable, and the designed edge weakening scheme empowers SSF with an adaptive capability to handle hypergraphs with varying densities. Lastly, a multilayer perceptron classifier is trained for prediction. Experiment results on ten real-world hypergraph networks demonstrate the effectiveness of the proposed approach. The source code of SSF is available at this URL1.1https://github.com/KXDY233/SSF

In many social networks, besides peer-to-peer communication, people share information via groups. An interesting problem arises in this scenario: for such networks, which are the best groups to start information diffusion so that the number of eventually informed nodes can be maximized? In this study, we formulate a novel information coverage maximization problem in the context of hypergraphs, wherein nodes are connected by arbitrary-size hyperedges (i.e., groups). In contrast to the existing literature on influence maximization, which aims to find authority nodes with high influence, we are interested in identifying the key groups. To address this problem, we present a new information diffusion model for hypergraphs, namely Hypergraph- Independent-Cascade (HIC). HIC generalizes the popular independent cascade model to hypergraphs to allow capturing group-level information diffusion. We prove the NP- hardness of the proposed problem under HIC, and the submodular monotone property of the information coverage function. Further, inspired by the Degree Discount algorithm, we derive a new heuristic method named Influence Discount (InfDis). Extensive experiments provide empirical evidence for the effectiveness and efficiency of our approach.

Understanding the evolution of large graphs over time is of significant importance in user behavior understanding and prediction. Modeling user behavior with temporal networks has gained increasing attention in recent years since it allows capturing users’ dynamic preferences and predicting their next actions. Recently, some approaches have been proposed to model user behavior. However, these methods suffer from two problems: they work on static data, which ignores the dynamic evolution, or they model the whole behavior sequences directly by recurrent neural networks and thus suffer from noisy information. To tackle these problems, we propose a dynamic user behavior learning algorithm called LDBR. It views user behaviors as a set of dynamic events and uses recent event embedding to predict future user behavior and infer the current semantic labels. Specifically, we propose a new strategy to automatically learn a good event embedding in behavior sequence by introducing a smooth sampling strategy and minimizing the temporal link prediction error.

Multi-label classification problem has gained growing attention in recent years due to its diverse applications to real-world problems such as image annotation and query suggestions. However, traditional multi-label classification methods tend to fail due to the inconsistency between input and output space, where similar instances in the feature space may have distinct semantic labels in the output space. To eliminate the inconsistency problem, in this paper, we propose a supervised metric learning approach for multi-label classification, called MLMLI, which attempts to learn a similarity metric for multi-label data. The basic idea is to incorporate label similarity in output space as weak supervision to assign higher similarity to the pairs of instances with more similar labels. To this end, a weighted triple loss, and a step-specified coordinate descent method are employed. Different from traditional dimensionality reduction approaches, MLMLI is independent of any prior information of data, and thus enjoys a high capacity of generalization. Moreover, the metric learned by MLMLI offers a new venue for feature learning. Experiments on real-world datasets have further demonstrated the effectiveness of MLMLI and show its superiority over many state-of-the-art algorithms.

Community detection in attributed networks has gained growing attention in recent years due to the booming of network data with both topological structure and attributes of nodes. To date, numerous algorithms have been proposed to leverage both kinds of information to yield high-quality communities based on homophily assumption (i.e., nodes are likely to link with those who share similar attributes). However, these approaches tend to focus on consistent information only and fail to consider the heterogeneity between topology and attributes. In light of the problem, we propose a new algorithm called CDLM (Community Detection via Local Metric learning) for attributed networks. The key point is to combine topological structure and node attributes in local metric space and perform community detection and local metric learning iteratively. With such a strategy, the learned local distance measures will benefit the performance of community detection, and in turn, the identification of intrinsic community structure helps to eliminate the negative effects of noisy edges in learning local metrics. Notably, homogeneity and heterogeneity between topological structure and node attributes are simultaneously considered to boost the performance of community detection. Experimental results on both synthetic and real-world networks have demonstrated the effectiveness of the proposed CDLM algorithm.

The scarcity of labeled data in real streaming environments has boosted the study of online semi-supervised learning (SSL). However, existing online SSL models often rely on some specific assumptions (e.g., manifold assumption) and need to maintain some extra constraints (e.g., the Laplacian matrix) on the fly, which is usually time and resource consuming. In this paper, we propose an efficient and effective online semi-supervised learning approach via Budgeted Least Square (BLS). Specifically, we first derive both closed-form transductive and inductive solutions for kernel least squares classification in the semi-supervised setting. Then, together with online kernel learning, BLS allows a concise online update. Besides, the theoretical regret bound of BLS is analysed, and empirical experiments on both static and streaming data further demonstrate its superiority over state-of-the-art algorithms.

In this paper, we introduce a novel method to discover common and distinct structural connectivity patterns between SZP and MDD via a Cluster-Driven Nonnegative Matrix Factorization (called CD-NMF). Specifically, CD-NMF is applied to decompose the joint structural connectivity map into common and distinct parts, and each part is further factorized into two sub-matrices (i.e. common/distinct basis matrix and common/distinct encoding matrix) correspondingly. By imposing the clustering constraints on common and distinct encoding matrices, the discriminative patterns as well as the common patterns between the two disorders are extracted simultaneously. Experimental results demonstrate that CD-NMF allows finding the common and distinct structural patterns effectively. More importantly, the derived distinct patterns, show powerful ability to discriminate the patients of schizophrenia and major depressive disorder.