Graph summarization has become integral for managing and analyzing large-scale graphs in diverse real-world applications, including social networks, biological networks, and communication networks. Existing methods for graph summarization often face challenges, being either computationally expensive, limiting their applicability to large graphs, or lacking the incorporation of node attributes. In response, we introduce SsAG , an efficient and scalable lossy graph summarization method designed to preserve the essential structure of the original graph. SsAG computes a sparse representation (summary) of the input graph, accommodating graphs with node attributes. The summary is structured as a graph on supernodes (subsets of vertices of G ), where weighted superedges connect pairs of supernodes. The methodology focuses on constructing a summary graph with k supernodes, aiming to minimize the reconstruction error (the difference between the original graph and the graph reconstructed from the summary) while maximizing homogeneity with respect to the node attributes. The construction process involves iteratively merging pairs of nodes. To enhance computational efficiency, we derive a closed-form expression for efficiently computing the reconstruction error (RE) after merging a pair, enabling constant-time approximation of this score. We assign a weight to each supernode, quantifying their contribution to the score of pairs, and utilize a weighted sampling strategy to select the best pair for merging. Notably, a logarithmic-sized sample achieves a summary comparable in quality based on various measures. Additionally, we propose a sparsification step for the constructed summary, aiming to reduce storage costs to a specified target size with a marginal increase in RE. Empirical evaluations across diverse real-world graphs demonstrate that SsAG exhibits superior speed, being up to 17 × faster, while generating summaries of comparable quality. This work represents a significant advancement in the field, addressing computational challenges and showcasing the effectiveness of SsAG in graph summarization.

Data analysis requires a pairwise proximity measure over objects. Recent work has extended this to situations where the distance information between objects is given as comparison results of distances between three objects (triplets). Humans find comparison tasks much easier than the exact distance computation, and such data can be easily obtained in big quantities via crowdsourcing. In this work, we propose triplets augmentation, an efficient method to extend the triplets data by inferring the hidden implicit information from the existing data. Triplets augmentation improves the quality of kernel-based and kernel-free data analytics. We also propose a novel set of algorithms for common data analysis tasks based on triplets. These methods work directly with triplets and avoid kernel evaluations, thus are scalable to big data. We demonstrate that our methods outperform the current best-known techniques and are robust to noisy data.

Analysis of the fairness of machine learning (ML) algorithms has attracted many researchers’ interest. Several studies have shown that ML methods produce a bias toward different groups, which limits the applicability of ML models in many applications, such as crime rate prediction. The data used for ML may have missing values, which, if not appropriately handled, are known to further harmfully affect fairness. To address this issue, many imputation methods have been proposed to deal with missing data. However, research on the effect of missing data imputation on fairness is still rather limited. In this paper, we analyze the impact of imputation on fairness in the context of graph data (node attributes) using different embedding and neural network methods. Extensive experiments on six datasets demonstrate several issues of fairness in graph node classification when dealing with missing data and various imputation techniques. We find that the choice of the imputation method affects both fairness and accuracy. Our results provide valuable insights into fairness ML over graph data and how to handle missingness in graphs efficiently.

In many graphs such as social networks, nodes have associated attributes representing their behavior. Predicting node attributes in such graphs is an important task with applications in many domains like recommendation systems, privacy preservation, and targeted advertisement. Attribute values can be predicted by treating each node as a data point described by attributes and employing classification/regression algorithms. However, in social networks, there is complex interdependence between node attributes and pairwise interaction. For instance, attributes of nodes are influenced by their neighbors (social influence), and neighborhoods (friendships) between nodes are established based on pairwise (dis)similarity between their attributes (social selection). In this article, we establish that information in network topology is extremely useful in determining node attributes. In particular, we use self- and cross-proclivity measures (quantitative measures of how much a node attribute depends on the same and other attributes of its neighbors) to predict node attributes. We propose a feature map to represent a node with respect to a specific attribute a , using all attributes of its h -hop neighbors. Different classifiers are then learned on these feature vectors to predict the value of attribute a . We perform extensive experimentation on 10 real-world datasets and show that the proposed method significantly outperforms known approaches in terms of prediction accuracy.