Network sampling is the task of selecting a subset of nodes and links from a network in a way that preserves its topological properties and other user requirements. This paper investigates the problem of generating an unbiased network sample that contains balanced proportion of nodes from different groups. Creating such a representative sample would require handling the trade-off between ensuring structural preservability and group representativity of the selected nodes. We present a novel max-min subgraph fairness measure that can be used as a unifying framework to combine both criteria. A greedy algorithm is then proposed to generate a fair and representative sample from an initial set of target nodes. A theoretical approximation guarantee for the output of the proposed greedy algorithm based on submodularity and curvature ratios is also presented. Experimental results on real-world datasets show that the proposed method will generate more fair and representative samples compared to other existing network sampling methods.

Algorithmic fairness is a major concern in recent years as the influence of machine learning algorithms becomes more widespread. In this paper, we investigate the issue of algorithmic fairness from a network-centric perspective. Specifically, we introduce a novel yet intuitive function known as fairness perception and provide an axiomatic approach to analyze its properties. Using a peer-review network as a case study, we also examine its utility in terms of assessing the perception of fairness in paper acceptance decisions. We show how the function can be extended to a group fairness metric known as fairness visibility and demonstrate its relationship to demographic parity. We also discuss a potential pitfall of the fairness visibility measure that can be exploited to mislead individuals into perceiving that the algorithmic decisions are fair. We demonstrate how the problem can be alleviated by increasing the local neighborhood size of the fairness perception function.

Networks provide a powerful representation tool for modeling dyadic interactions among interconnected entities in a complex system. For many applications such as social network analysis, it is common for the entities to appear in more than one network. Network alignment (NA) is an important first step towards learning the entities' behavior across multiple networks by finding the correspondence between similar nodes in different networks. However, learning the proper alignment matrix in noisy networks is a challenge due to the difficulty in preserving both the neighborhood topology and feature consistency of the aligned nodes. In this paper, we present OPTANE, a robust unsupervised network alignment framework, inspired from an optimal transport theory perspective. The framework provides a principled way to combine node similarity with topology information to learn the alignment matrix. Experimental results conducted on both synthetic and real-world data attest to the effectiveness of the OPTANE framework compared to other baseline approaches.

Network representation learning algorithms seek to embed the nodes of a network into a lower-dimensional feature space such that nodes that are in close proximity to each other share a similar representation. In this paper, we investigate the effectiveness of using network representation learning algorithms for link prediction problems. Specifically, we demonstrate the limitations of existing algorithms in terms of their ability to accurately predict links between nodes that are in the same or different communities and nodes that have low degrees. We also show that incorporating node attribute information can help alleviate this problem and compare three different approaches to integrate this information with network representation learning for link prediction problems. Using five real-world network datasets, we demonstrate the efficacy of one such approach, called SPIN, that can effectively combine the link structure with node attribute information and predict links between nodes in the same and different communities without favoring high degree nodes.

Existing collaborative ranking based recommender systems tend to perform best when there is enough observed ratings for each user, and the observed data is uniformly sampled at random. However, when the observed ratings are extremely sparse (e.g. in the case of cold-start item where no rating data is available), and are not sampled uniformly at random, existing ranking methods fail to effectively leverage side information to transduct the knowledge from existing ratings to unobserved ones. We propose a semi-supervised collaborative ranking model, dubbed S2COR, to improve the quality of cold-start item recommendation. S2COR mitigates the sparsity issue by leveraging side information about both observed and missing ratings by collaboratively learning the ranking model. This enables it to deal with the case of data missing not at random, but to also effectively incorporate the available side information in transduction. We experimentally evaluated our proposed algorithm on a number of challenging real-world datasets and compared our results against state-of-the-art models for cold-start recommendation. We show significantly higher quality recommendations with our algorithm when compared to other state-of-the-art methods.

Although recommendation systems based on the latent factor models provide an appealing solution to the collaborative filtering problem, some major issues such as data sparsity and cold-start problems, still remain open. In particular, for a large portion of items that there are not sufficient purchase records, their latent factors cannot be estimated accurately. In this paper, we aim to learn and exploit the preference of users in combination with the latent factor models to mitigate these issues and to improve recommendation accuracy. To this end, we propose a novel algorithm to accurately learn the preference of users from observed ratings and available taxonomy of items. We show that predictions made based on the extracted users' preferences enable to capture the taste of users and generates more effective recommendations than pure latent factor models. To the best of our knowledge, the proposed algorithm is the first to extract and exploit the implicit preference of users in the recommendation. We conduct thorough experiments on real datasets that demonstrate the proposed model improves significantly over state-of-the-art latent factor models.

A subgraph H of a given graph G is isometric if the distances between every pair of vertices in H are the same as the distances of those vertices in G. We say a graph G is distance preserving if there exists an isometric subgraph of every possible order up to the order of G. Distance preserving property has been applied to many real world problems such as route recommendation systems and all kinds of shortest-path-related applications. Here, we propose a biologically-inspired search algorithm to address the problem of finding isometric subgraphs that consequently determines if a given graph is distance preserving. In this algorithm, using a well defined fitness function, selection operator selects almost isometric subgraphs to generate the offspring for the next generation. There is a trade-off between the population size and searching speed. On one hand, the larger the population size is, the slower the search algorithm would be. On the other hand, by increasing the population size, we increase the likelihood of finding an existing isometric subgraph. Experimental results depict the performance of the proposed algorithm in finding isometric subgraphs even for challenging problems, and interestingly by these results one can see that "almost" all graphs are distance preserving. In closing, we show the smallest distance preserving graph whose product factors are not distance preserving. This graph has 80 vertices, and can be used as benchmark for algorithms in this concept.

Although the matrix completion paradigm provides an appealing solution to the collaborative filtering problem in recommendation systems, some major issues, such as data sparsity and cold-start problems, still remain open. In particular, when the rating data for a subset of users or items is entirely missing, commonly known as thecold-startproblem, the standard matrix completion methods are inapplicable due the non-uniform sampling of available ratings. In recent years, there has been considerable interest in dealing with cold-start users or items that are principally based on the idea of exploiting other sources of information to compensate for this lack of rating data. In this paper, we propose a novel and general algorithmic framework based on matrix completion that simultaneously exploits the similarity information among users and items to alleviate the cold-start problem. In contrast to existing methods, our proposed recommender algorithm, dubbed DecRec,decouplesthe following two aspects of the cold-start problem to effectively exploit the side information: (i) the completion of a rating sub-matrix, which is generated by excluding cold-start users/items from the original rating matrix; and (ii) the transduction of knowledge from existing ratings to cold-start items/users using side information. This crucial difference prevents the error propagation of completion and transduction, and also significantly boosts the performance when appropriate side information is incorporated. The recovery error of the proposed algorithm is analyzed theoretically and, to the best of our knowledge, this is the first algorithm that addresses the cold-start problem with provable guarantees on performance. Additionally, we also address the problem where both cold-start user and item challenges are present simultaneously. We conduct thorough experiments on real datasets that complement our theoretical results. These experiments demonstrate the effectiveness of the proposed algorithm in handling the cold-start users/items problem and mitigating data sparsity issue.

This paper investigates the network completion problem, where it is assumed that only a small sample of a network (e.g., a complete or partially observed subgraph of a social graph) is observed and we would like to infer the unobserved part of the network. In this paper, we assume that besides the observed subgraph, side information about the nodes such as the pairwise similarity between them is also provided. In contrast to the original network completion problem where the standard methods such as matrix completion is inapplicable due the non-uniform sampling of observed links, we show that by effectively exploiting the side information, it is possible to accurately predict the unobserved links. In contrast to existing matrix completion methods with side information such as shared subsapce learning and matrix completion with transduction, the proposed algorithm decouples the completion from transduction to effectively exploit the similarity information. This crucial difference greatly boosts the performance when appropriate similarity information is used. The recovery error of the proposed algorithm is theoretically analyzed based on the richness of the similarity information and the size of the observed submatrix. To the best of our knowledge, this is the first algorithm that addresses the network completion with similarity of nodes with provable guarantees. Experiments on synthetic and real networks from Facebook and Google+ show that the proposed two-stage method is able to accurately reconstruct the network and outperforms other methods.

A major challenge in collaborative filtering based recommender systems is how to provide recommendations when rating data is sparse or entirely missing for a subset of users or items, commonly known as the cold-start problem. In recent years, there has been considerable interest in developing new solutions that address the cold-start problem. These solutions are mainly based on the idea of exploiting other sources of information to compensate for the lack of rating data. In this paper, we propose a novel algorithmic framework based on matrix factorization that simultaneously exploits the similarity information among users and items to alleviate the cold-start problem. In contrast to existing methods, the proposed algorithm decouples the following two aspects of the cold-start problem: (a) the completion of a rating sub-matrix, which is generated by excluding cold-start users and items from the original rating matrix; and (b) the transduction of knowledge from existing ratings to cold-start items/users using side information. This crucial difference significantly boosts the performance when appropriate side information is incorporated. We provide theoretical guarantees on the estimation error of the proposed two-stage algorithm based on the richness of similarity information in capturing the rating data. To the best of our knowledge, this is the first algorithm that addresses the cold-start problem with provable guarantees. We also conduct thorough experiments on synthetic and real datasets that demonstrate the effectiveness of the proposed algorithm and highlights the usefulness of auxiliary information in dealing with both cold-start users and items.

The significance of social-enhanced recommender systems is increasing, along with its practicality, as online reviews, ratings, friendship links, and follower relationships are increasingly becoming available. In recent years, there has been an upsurge of interest in exploiting social information, such as trust and distrust relations in recommendation algorithms. The goal is to improve the quality of suggestions and mitigate the data sparsity and the cold-start users problems in existing systems. In this paper, we introduce a general collaborative social ranking model to rank the latent features of users extracted from rating data based on the social context of users. In contrast to existing social regularization methods, the proposed framework is able to simultaneously leverage trust, distrust, and neutral relations, and has a linear dependency on the social network size. By integrating the ranking based social regularization idea into the matrix factorization algorithm, we propose a novel recommendation algorithm, dubbed PushTrust. Our experiments on the Epinions dataset demonstrate that collaboratively ranking the latent features of users by exploiting trust and distrust relations leads to a substantial increase in performance, and to effectively deal with cold-start users problem.

Cluster analysis describes the division of a dataset into subsets of related objects, which are usually disjoint. There is considerable variety among the different types of clustering algorithms. Some of these clustering algorithms represent the dataset as a graph, and use graph-based properties to generate the clusters. However, many graph properties have not been explored as the basis for a clustering algorithm. In graph theory, a subgraph of a graph is distance-preserving if the distances (lengths of shortest paths) between every pair of vertices in the subgraph are the same as the corresponding distances in the original graph. In this paper, we consider the question of finding proper distance-preserving subgraphs, and the problem of partitioning a simple graph into an arbitrary number of distance-preserving subgraphs for clustering purposes. We also present a clustering algorithm called DP-Cluster, based on the notion of distance-preserving subgraphs. One area of research that makes considerable use of graph theory is the analysis of social networks. For this reason we evaluate the performance of DP-Cluster on two real-world social network datasets.

The rise of email as a communication medium raises several issues. A majority of email messages sent are spam. Also, the amount of legitimate email received by many users is overwhelming. In this paper, we propose two new methods of performing email prioritization. Both techniques rank users inboxes using models created from email history. With them, lower priority email messages may be dealt with so that the use of email remains a net productivity gain.

Within networks there is often a pattern to the way nodes link to one another. It has been shown that the accuracy of node classification can be improved by using the link data. One of the challenges to integrating the attribute and link data, though, is balancing the influence that each has on the classification decision. In this paper we present a matrix alignment approach to the problem of collective classification which weights the attributes and the links according to their predictive influence. The experiments show that while our approach provides comparable accuracy in prediction to other methods, it is also very fast and descriptive.

Social networks have become a major focus of research in recent years, initially directed towards static networks but increasingly, towards dynamic ones. In this paper, we investigate how different pre-processing decisions and different network forces such as selection and influence affect the modeling of dynamic networks. We also present empirical justification for some of the modeling assumptions made in dynamic network analysis (e.g., first-order Markovian assumption) and develop metrics to measure the alignment between links and attributes under different strategies of using the historical network data. We also demonstrate the effect of attribute drift, that is, the importance of individual attributes in forming links change over time.

Communities are nodes in a network that are grouped together based on a common set of properties. While the communities and link structures are often thought to be in alignment, it may not be the case when the communities are defined using other external criterion. In this paper we provide a new way to measure the alignment. We also provide a new metric that can be used to estimate the number of communities to which a node is attached. This metric, along with degree, is used to assign a community-based role to nodes. We demonstrate the usefulness of the community-based node roles by applying them to the influence maximization problem.