Link-analysis algorithms, such as PageRank, are instrumental in understanding the structural dynamics of networks by evaluating the importance of individual vertices based on their connectivity. Recently, with the rising importance of responsible AI, the question of fairness in link-analysis algorithms has gained traction.

Diversification is a useful tool for exploring large collections of information items. It has been used to reduce redundancy and cover multiple perspectives in information-search settings. Diversification finds applications in many different domains, including presenting search results of information-retrieval systems and selecting suggestions for recommender systems.

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.

We consider a variant of the densest subgraph problem in networks with single or multiple edge attributes. For example, in a social network, the edge attributes may describe the type of relationship between users, such as friends, family, or acquaintances, or different types of communication. For conceptual simplicity, we view the attributes as edge colors. The new problem we address is to find a diverse densest subgraph that fulfills given requirements on the numbers of edges of specific colors. When searching for a dense social network community, our problem will enforce the requirement that the community is diverse according to criteria specified by the edge attributes. We show that the decision versions for finding exactly, at most, and at least h colored edges densest subgraph, where h is a vector of color requirements, are NP-complete, for already two colors. For the problem of finding a densest subgraph with at least h colored edges, we provide a linear-time constant-factor approximation algorithm when the input graph is sparse. On the way, we introduce the related at least h (non-colored) edges densest subgraph problem, show its hardness, and also provide a linear-time constant-factor approximation. In our experiments, we demonstrate the efficacy and efficiency of our new algorithms.

Structural bias or segregation of networks refers to situations where two or more disparate groups are present in the network, so that the groups are highly connected internally, but loosely connected to each other. Examples include polarized communities in social networks, antagonistic content in video-sharing or news-feed platforms, etc. In many cases it is of interest to increase the connectivity of disparate groups so as to, e.g., minimize social friction, or expose individuals to diverse viewpoints. A commonly-used mechanism for increasing the network connectivity is to add edge shortcuts between pairs of nodes. In many applications of interest, edge shortcuts typically translate to recommendations, e.g., what video to watch, or what news article to read next. The problem of reducing structural bias or segregation via edge shortcuts has recently been studied in the literature, and random walks have been an essential tool for modeling navigation and connectivity in the underlying networks. Existing methods, however, either do not offer approximation guarantees, or engineer the objective so that it satisfies certain desirable properties that simplify the optimization task.

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.