Predicting the edge weights of a graph is a critical task across many domains. Some examples include predicting traffic flow in transportation networks, strength of interactions in protein-protein networks, and collaboration frequency in co-authorship networks. Graph Neural Networks have been very successful in edge-weight prediction tasks. However, these predictions lack rigorous statistical uncertainty quantification. Recent work has demonstrated the efficacy of conformal inference in quantifying the uncertainties of the predictions made by graph neural networks. However, there has been limited research in conformal inference for edge-weight prediction.

Network alignment, or the task of finding corresponding nodes in different networks, is an important problem formulation in many application domains. We propose CAPER, a multilevel alignment framework that Coarsens the input graphs, Aligns the coarsened graphs, Projects the alignment solution to finer levels and Refines the alignment solution. We show that CAPER can improve upon many different existing network alignment algorithms by enforcing alignment consistency across multiple graph resolutions: nodes matched at finer levels should also be matched at coarser levels. CAPER also accelerates the use of slower network alignment methods, at the modest cost of linear-time coarsening and refinement steps, by allowing them to be run on smaller coarsened versions of the input graphs. Experiments show that CAPER can improve upon diverse network alignment methods by an average of 33% in accuracy and/or an order of magnitude faster in runtime.

While most network embedding techniques model the proximity between nodes in a network, recently there has been significant interest in structural embeddings that are based on node equivalences , a notion rooted in sociology: equivalences or positions are collections of nodes that have similar roles—i.e., similar functions, ties or interactions with nodes in other positions—irrespective of their distance or reachability in the network. Unlike the proximity-based methods that are rigorously evaluated in the literature, the evaluation of structural embeddings is less mature. It relies on small synthetic or real networks with labels that are not perfectly defined, and its connection to sociological equivalences has hitherto been vague and tenuous. With new node embedding methods being developed at a breakneck pace, proper evaluation, and systematic characterization of existing approaches will be essential to progress. To fill in this gap, we set out to understand what types of equivalences structural embeddings capture. We are the first to contribute rigorous intrinsic and extrinsic evaluation methodology for structural embeddings, along with carefully-designed, diverse datasets of varying sizes. We observe a number of different evaluation variables that can lead to different results (e.g., choice of similarity measure, classifier, and label definitions). We find that degree distributions within nodes’ local neighborhoods can lead to simple yet effective baselines in their own right and guide the future development of structural embedding. We hope that our findings can influence the design of further node embedding methods and also pave the way for more comprehensive and fair evaluation of structural embedding methods.

Network alignment, or the task of finding meaningful node correspondences between nodes in di↵erent graphs, is an important graph mining task with many scientific and industrial applications.An important principle for network alignment is matched neighborhood consistency (MNC): nodes that are close in one graph should be matched to nodes that are close in the other graph.We theoretically demonstrate a close relationship between MNC and alignment accuracy.As many existing network alignment methods struggle to preserve topological consistency in di cult scenarios, we show how to refine their solutions by improving their MNC.Our refinement method, RefiNA, is straightforward to implement, admits scalable sparse approximation, and can be paired post hoc with any network alignment method.Extensive experiments show that RefiNA increases the accuracy of diverse unsupervised network alignment methods by up to 90%, making them robust enough to align graphs that are 5⇥ more topologically di↵erent than were considered in prior work.

While most network embedding techniques model the relative positions of nodes in a network, recently there has been significant interest in structural embeddings that model node role equivalences, irrespective of their distances to any specific nodes. We present PhUSION, a proximity-based unified framework for computing structural and positional node embeddings, which leverages well-established methods for calculating node proximity scores. Clarifying a point of contention in the literature, we show which step of PhUSION produces the different kinds of embeddings and what steps can be used by both. Moreover, by aggregating the PhUSION node embeddings, we obtain graph-level features that model information lost by previous graph feature learning and kernel methods. In a comprehensive empirical study with over 10 datasets, 4 tasks, and 35 methods, we systematically reveal successful design choices for node and graph-level machine learning with embeddings.

Network alignment, the process of finding correspondences between nodes in different graphs, has many scientific and industrial applications. Existing unsupervised network alignment methods find suboptimal alignments that break up node neighborhoods, i.e. do not preserve matched neighborhood consistency. To improve this, we propose CONE-Align, which models intra-network proximity with node embeddings and uses them to match nodes across networks after aligning the embedding subspaces. Experiments on diverse, challenging datasets show that CONE-Align is robust and obtains 19.25% greater accuracy on average than the best-performing state-of-the-art graph alignment algorithm in highly noisy settings.

Network alignment is useful for multiple applications that require increasingly large graphs to be processed. Existing research approaches this as an optimization problem or computes the similarity based on node representations. However, the process of aligning every pair of nodes between relatively large networks is time-consuming and resource-intensive. In this paper, we propose a framework, called G-CREWE (Graph CompREssion With Embedding) to solve the network alignment problem. G-CREWE uses node embeddings to align the networks on two levels of resolution, a fine resolution given by the original network and a coarse resolution given by a compressed version, to achieve an efficient and effective network alignment. The framework first extracts node features and learns the node embedding via a Graph Convolutional Network (GCN). Then, node embedding helps to guide the process of graph compression and finally improve the alignment performance. As part of G-CREWE, we also propose a new compression mechanism called MERGE (Minimum DEgRee NeiGhbors ComprEssion) to reduce the size of the input networks while preserving the consistency in their topological structure. Experiments on all real networks show that our method is more than twice as fast as the most competitive existing methods while maintaining high accuracy.

Graph classification is an important problem in many fields, from bioinformatics and neuroscience to computer vision and social network analysis. That said, the task of comparing graphs for the purpose of graph classification faces several major challenges. In particular, an effective graph comparison method must (1) expressively and inductively compare graphs; (2) efficiently compare large graphs; and (3) enable the use of fast machine learning models for graph classification. To address such challenges, we propose Randomized Grid Mapping (RGM), a fast-to-compute feature map that represents a graph via the distribution of its node embeddings in feature space. We justify RGM with close connections to kernel methods: RGM provably approximates the Laplacian kernel mean map and has the multiresolution properties of the pyramid match kernel. We also show that RGM can be extended to incorporate node labels using the Weisfeiler-Lehman framework. Extensive experiments show that graph classification accuracy with RGM feature maps is better than or competitive with many powerful graph kernels, unsupervised graph feature mappings, and deep neural networks. Moreover, comparing graphs based on their node embeddings with RGM is up to an order of magnitude faster than competitive baselines, while maintaining high classification accuracy.

Email is ubiquitous in the workplace. Naturally, machine learning models that make third-party email clients "smarter" can dramatically impact employees' productivity and efficiency. Motivated by this potential, we study the task of professional role inference from email data, which is crucial for email prioritization and contact recommendation systems. The central question we address is: Given limited data about employees, as is common in third-party email applications, can we infer where in the organizational hierarchy these employees belong based on their email behavior? Toward our goal, in this paper we study professional role inference on a unique new email dataset comprising billions of email exchanges across thousands of organizations. Taking a network approach in which nodes are employees and edges represent email communication, we propose EMBER, or EMBedding Email-based Roles, which finds email-centric embeddings of network nodes to be used in professional role inference tasks. EMBER automatically captures behavioral similarity between employees in the email network, leading to embeddings that naturally distinguish employees of different hierarchical roles. EMBER often outperforms the state-of-the-art by 2-20% in role inference accuracy and 2.5-344x in speed. We also use EMBER with our unique dataset to study how inferred professional roles compare between organizations of different sizes and sectors, gaining new insights into organizational hierarchy.

Problems involving multiple networks are prevalent in many scientific and other domains. In particular, network alignment, or the task of identifying corresponding nodes in different networks, has applications across the social and natural sciences. Motivated by recent advancements in node representation learning for single-graph tasks, we propose REGAL (REpresentation learning-based Graph ALignment), a framework that leverages the power of automatically-learned node representations to match nodes across different graphs. Within REGAL we devise xNetMF, an elegant and principled node embedding formulation that uniquely generalizes to multi-network problems. Our results demonstrate the utility and promise of unsupervised representation learning-based network alignment in terms of both speed and accuracy. REGAL runs up to 30x faster in the representation learning stage than comparable methods, outperforms existing network alignment methods by 20 to 30% accuracy on average, and scales to networks with millions of nodes each.

As graph datasets grow, faster data mining methods become indispensable. Random Walk with Restart (RWR), belief propagation, semi-supervised learning, and more graph methods can be expressed as a set of linear equations. In this work, we focus on solving such equations fast and accurately when large number of queries need to be handled. We use RWR as a case study, since it is widely used not only to evaluate the importance of a node, but also as a basis for more complex tasks, e.g., representation learning and community detection. We introduce a new, intuitive two-step divide-and-conquer formulation and a corresponding parallelizable method, FlowR, for solving RWR with two goals: (i) fast and accurate computation under multiple queries; (ii) one-time message exchange between subproblems. We further speed up our proposed method by extending our formulation to carefully designed overlapping subproblems (FlowR-OV) and by leveraging the strengths of iterative methods (FlowR-Hyb). Extensive experiments on synthetic and real networks with up to ∼8 million edges show that our methods are accurate and outperform in runtime various state-of-the-art approaches, running up to 34× faster in preprocessing and up to 32× faster in query time.