MLG 2022 - 17th International Workshop on Mining and Learning with Graphs

	Morning Sessions
8:30-8:45am	Opening Remarks
8:45-9:30am	Keynote: Jiawei Han Towards Automatic Construction of Text-Rich Information Networks from Text
9:30-10:00am	Break and Poster Setup
10:00-10:45am	Keynote: Neil Shah Scaling up Graph Neural Networks at Snap
10:45-11:15am	Contributed Talks Christopher Musco et al. How to Quantify Polarization in Models of Opinion Dynamics Jiaqi Ma et al. Partition-Based Active Learning for Graph Neural Networks
11:15-12:00pm	Panel: Jiawei Han, Lingfei Wu, Xiaojie Guo, Neil Shah, Tim Weninger Learning and Reasoning on Knowledge Graphs: Graph Neural Networks vs Foundation Models
12:00-1:30pm	Lunch Break

	Afternoon Sessions
1:30-2:15 pm	Keynote: Yizhou Sun Combining Representation Learning and Logical Rule Reasoning for Knowledge Graph Inference
2:15-2:45 pm	Contributed Talks Yu Shi et al. mvn2vec: Preservation and Collaboration in Multi-View Network Embedding John Palowitch et al. Robust Synthetic GNN Benchmarks with GraphWorld
2:45-3:30 pm	Break and Poster Session
3:30-4:15 pm	Keynote: Jennifer Neville Social reinforcement learning for optimizing network-level goals in multi-agent systems
4:15-4:45pm	Closing Remarks

Accepted Papers

ColdGuess: A General and Effective Relational Graph Convolutional Network to Tackle Cold Start Cases PDF
Bo He, Xiang Song, Christos Faloutsos and Vincent Gao

Abstract: Low-quality listings and bad actor behavior in online retail web-sites threatens e-commerce business as these result in sub-optimal buying experience and erode customer trust. When a new listing is created, how to tell it has good-quality? Is the method effective, fast, and scalable? Previous approaches often have three limitations/challenges: (1) unable to handle cold start problems where new sellers/listings lack sufficient selling histories. (2) inability of scoring hundreds of millions of listings at scale, or compromise performance for scalability. (3) has space challenges from large-scale graph with giant e-commerce business size. To overcome these limitations/challenges, we proposed ColdGuess, an inductive graph-based risk predictor built upon a heterogeneous seller-product graph, which effectively identifies risky seller/product/listings at scale. ColdGuess tackles the large-scale graph by consolidated nodes, and addresses the cold start problems using homogeneous influence1. The evaluation on real data demonstrates that ColdGuess has stable performance as the number of unknown features increases. It outperforms the lightgbm by up to 34 pcp ROC AUC in a cold start case when a new seller sells a new product.The resulting system, ColdGuess, is effective, adaptable to changing risky seller behavior, and is already in production. This paper belongs to “Application and analysis – Large-scale graph and modeling”, and in the "Novel research paper" category.

@inproceedings{mlg2022_866,
title={ColdGuess: A General and Effective Relational Graph Convolutional Network to Tackle Cold Start Cases},
author={Bo He, Xiang Song, Christos Faloutsos and Vincent Gao},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

How to Quantify Polarization in Models of Opinion Dynamics PDF
Christopher Musco, Indu Ramesh, Johan Ugander and R. Teal Witter

Abstract: It is widely believed that society is becoming increasingly polarized around important issues, a dynamic that does not align with common mathematical models of opinion formation in social networks. In particular, measures of polarization based on opinion variance are known to decrease over time in frameworks such as the popular DeGroot model. Complementing recent work that seeks to resolve this apparent inconsistency by modifying opinion models, we instead resolve the inconsistency by proposing changes to how polarization is quantified. We present a natural class of group-based polarization measures that capture the extent to which opinions are clustered into distinct groups. Using theoretical arguments and empirical evidence, we show that these group-based measures display interesting, non-monotonic dynamics, even in the simple DeGroot model. In particular, for many natural social networks, group-based metrics can increase over time, and thereby correctly capture perceptions of increasing polarization. Our results build on work by DeMarzo et al., who introduced a group-based polarization metric based on ideological alignment. We show that a central tool from that work, a limit analysis of individual opinions under the DeGroot model, can be extended to the dynamics of other group-based polarization measures, including established statistical measures like bimodality. We also consider local measures of polarization that operationalize how polarization is perceived in a network setting. In conjunction with evidence from prior work that group-based measures better align with real-world perceptions of polarization, our work provides formal support for the use of these measures in place of variance-based polarization in future studies of opinion dynamics.

@inproceedings{mlg2022_1202,
title={How to Quantify Polarization in Models of Opinion Dynamics},
author={Christopher Musco, Indu Ramesh, Johan Ugander and R. Teal Witter},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Tailored vertex ordering for faster triangle listing in large graphs PDF
Fabrice Lécuyer, Louis Jachiet, Clémence Magnien and Lionel Tabourier

Abstract: Listing triangles is a fundamental graph problem with many applications, and large graphs require fast algorithms. Vertex ordering allows the orientation of edges from lower to higher vertex indices, and state-of-the-art triangle listing algorithms use this to accelerate their execution and to bound their time complexity. Yet, only two basic orderings have been tested. In this paper, we show that studying the precise cost of algorithms instead of their bounded complexity leads to faster solutions. We introduce cost functions that link ordering properties with the running time of a given algorithm. We prove that their minimization is NP-hard and propose heuristics to obtain new orderings with different trade-offs between cost reduction and ordering time. Using datasets with up to two billion edges, we show that our heuristics accelerate the listing of triangles by an average of 30% when the ordering is already given as an input, and 15% when the ordering time is included.

@inproceedings{mlg2022_1980,
title={Tailored vertex ordering for faster triangle listing in large graphs},
author={Fabrice Lécuyer, Louis Jachiet, Clémence Magnien and Lionel Tabourier},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Knowledge-aware Neural Collective Matrix Factorization for Cross-domain Recommendation PDF
Li Zhang, Yan Ge, Jun Ma, Jianmo Ni and Haiping Lu

Abstract: Cross-domain recommendation (CDR) can help customers find more satisfying items in different domains. Existing CDR models mainly use common users or mapping functions as bridges between domains but have very limited exploration in fully utilizing item-item relationships across domains. In this paper, we propose the incorporation of multi-domain knowledge graph (KG) to enable items in different domains sharing knowledge even without explicit common contents. To this end, we first construct a new dataset \textit{AmazonKG4CDR} from the Freebase KG and a subset of Amazon Review Data in three domains: movies, books, and music. This new dataset facilitates linking knowledge to bridge within- and cross-domain items for CDR. Then we propose a new framework, KG-aware Neural Collective Matrix Factorization (KG-NeuCMF), leveraging KG to enrich item representations. It learns item embeddings by graph convolutional autoencoder to capture both domain-specific and domain-general knowledge from adjacent and higher-order neighbours in KG. To further improve KG-aware item embedding, we maximize the mutual information between representations learned from the KG and user-item matrix to establish cross-domain relationships for better CDR. We conduct extensive experiments on the newly constructed dataset and demonstrate that our model significantly outperforms the best-performing baselines.

@inproceedings{mlg2022_9580,
title={Knowledge-aware Neural Collective Matrix Factorization for Cross-domain Recommendation},
author={Li Zhang, Yan Ge, Jun Ma, Jianmo Ni and Haiping Lu},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

OASYS: Domain-Agnostic Automated System for Constructing Knowledge Base from Unstructured Text PDF
Minsang Kim, Sanghyun Je and Eunjoo Park

Abstract: In recent years, creating and managing knowledge bases have become crucial to the retail product and enterprise domains. We present an automatic knowledge base construction system that mines data from documents. This system can generate training data during the training process without human intervention. Therefore, it is domain-agnostic trainable using only the target domain text corpus and a pre-defined knowledge base. This system is called OASYS and is the first system built with the Korean language in mind. In addition, we also have constructed a new human-annotated benchmark dataset of the Korean Wikipedia corpus paired with a Korean DBpedia to aid system evaluation. The system performance results on this human-annotated benchmark dataset are meaningful and show that the generated knowledge base from OASYS trained on only auto-generated data is useful. We provide both a human-annotated test dataset and an auto-generated dataset.

@inproceedings{mlg2022_3178,
title={OASYS: Domain-Agnostic Automated System for Constructing Knowledge Base from Unstructured Text},
author={Minsang Kim, Sanghyun Je and Eunjoo Park},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Semi-Supervised Node Classification on Graph via Inconsistent Nodes Correction PDF
Shuhao Shi, Jian Chen, Kai Qiao, Shuai Yang, Linyuan Wang and Bin Yan

Abstract: This article is a work-in-progress paper. In traditional graph convolutional networks (GCNs), node feature aggregation in graph convolutional learning is guided only by topology graphs. In reality, both network topology and node features offer unique and valuable information. Using topology alone cannot obtain fully and completely accurate neighborhood information. This paper advocates a representation learning method with output correction for GCNs (OC-GCN), simultaneously using topological structure and node features information. Specifically, we use two GCN encoders to extract node embeddings in feature space and topology space. Then, determine inconsistent nodes by the pseudo-labels generated by the two models. Finally, we use the representations of consistent neighbors to regenerate representations of inconsistent nodes in feature and topology views. Our experiments have shown that the OC-GCN can significantly improve the classification accuracy of inconsistent nodes in feature and topology views. We conducted extensive experiments on the benchmark datasets and demonstrated that OC-GCN is substantially better than state-of-the-art baselines at different label rates.

@inproceedings{mlg2022_3678,
title={Semi-Supervised Node Classification on Graph via Inconsistent Nodes Correction},
author={Shuhao Shi, Jian Chen, Kai Qiao, Shuai Yang, Linyuan Wang and Bin Yan},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Graph-Assisted Tensor Disaggregation PDF
Mariana Duarte, Evangelos Papalexakis and Jia Chen

Abstract: Consider a multi-aspect tensor dataset which is only observed in multiple complementary aggregated versions, each one at a lower resolution than the highest available one. Recent work has demonstrated that given two such tensors, which have been aggregated in lower resolutions in complementary dimensions, we can pose and solve the disaggregation as an instance of a coupled tensor decomposition. In this work, we are exploring the scenario in which, in addition to the two complementary aggregated views, we also have access to a graph where nodes correspond to samples of the tensor mode that has not been aggregated. Given this graph, we propose a graph-assisted tensor disaggregation method. In our experimental evaluation, we demonstrate that our proposed method performs on par with the state of the art when the rank of the underlying coupled tensor decomposition is low, and significantly outperforms the state of the art in cases where the rank increases, producing more robust and higher-quality disaggregation.

@inproceedings{mlg2022_4272,
title={Graph-Assisted Tensor Disaggregation},
author={Mariana Duarte, Evangelos Papalexakis and Jia Chen},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Attributed Labeled BTER-Based Generative Model for Benchmarking of Graph Neural Networks PDF
Polina Andreeva, Egor Shikov and Claudie Bocheninа

Abstract: Graph Neural Networks (GNNs) have become increasingly popular for tasks such as link prediction, node classification, and graph generation. However, a number of models show weak performance on graphs with low assortativity measure. At the same time, other graph characteristics may also influence GNN quality. Therefore, it is extremely important for benchmark datasets to cover a wide range of different graph properties, which can not be provided by real-world sources. In this paper, we present a generative model for attributed graphs based on Block Two-Level Erdos-Renyi model. Our model allows one to vary larger number of graph structural characteristics (namely, clustering coefficient, average degree, average shortest paths length, label and attribute assortativity) in a wider range. Our attribute generative method can be applied to any other non-attributed graph generative model and allows to control attribute assortativity corresponding to structure of graph. The experimental study shows that AL-BTER outperforms ADC-SBM and GenCAT under the assumption of equal importance of desired graph characteristics and provides wider ranges for attribute assortativity and average shortest paths and outperforms LFR in terms of clustering coefficient. GNN performance analysis confirms the sensitivity of the results to all topological properties except average degree and shows that benchmark graphs provided by AL-BTER are useful to discover new regimes of performance of graph convolutional networks.

@inproceedings{mlg2022_5068,
title={Attributed Labeled BTER-Based Generative Model for Benchmarking of Graph Neural Networks},
author={Polina Andreeva, Egor Shikov and Claudie Bocheninа},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Learning Personalized Representations using Graph Convolutional Network PDF
Hongyu Shen, Jinoh Oh, Shuai Zhao, Guoyin Wang, Tara Taghavi and Sungjin Lee

Abstract: Generating representations that precisely reflect customers’ behavior is an important task for providing personalized skill routing experience in Alexa. Currently, Dynamic Routing (DR) team, who is responsible for routing Alexa traffic to providers/skills, relies on two features to be served as personal signals: absolute traffic count and normalized traffic count of every skill usage per customer. Neither of them considers the network-structure for interactions between customers and skills, which contain richer information for customer preferences. In this work, we first build a heterogeneous edge-attributed graph based customers’ past interactions with the invoked skills, in which the user requests (utterances) are modeled as edges. Then we propose a graph convolutional network(GCN)-based model, namely Personalized Dynamic Routing Feature Encoder (PDRFE), that generates personalized customer representations learned from the built graph. Compared with existing models, PDRFE is able to further capture contextual information in the graph convolutional function. The performance of our proposed model is evaluated by a downstream task, defect prediction, that predicts the defect label from the learned embeddings of customers and their triggered skills. We observe up to 41\% improvements on the cross-entropy metric for our proposed models compared to the baselines.

@inproceedings{mlg2022_6009,
title={Learning Personalized Representations using Graph Convolutional Network},
author={Hongyu Shen, Jinoh Oh, Shuai Zhao, Guoyin Wang, Tara Taghavi and Sungjin Lee},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Distance-wise Prototypical Graph Neural Network for Imbalanced Node Classification PDF
Yu Wang, Charu Aggarwal and Tyler Derr

Abstract: Recent years have witnessed the significant success of applying graph neural networks (GNNs) in learning effective node representations for classification. However, current GNNs are mostly built under the balanced data-splitting, which is inconsistent with real-world networks where the number of training nodes can be extremely imbalanced among the classes. Thus, directly utilizing current GNNs on imbalanced data would generate coarse representations of nodes in minority classes. This therefore portends the importance of developing effective GNNs for handling imbalanced graph data. In this work, we propose a novel Distance-wise Prototypical Graph Neural Network (DPGNN), which utilizes a class prototype-driven training to balance the training loss between majority and minority classes and then leverages distance metric learning to differentiate the contributions of different dimensions of representations and fully encode the relative position of each node to each class prototype. Moreover, we design a new imbalanced label propagation mechanism to derive extra supervision from unlabeled nodes and employ self-supervised learning to smooth representations of adjacent nodes while separating inter-class prototypes. Comprehensive node classification experiments and parameter analysis on multiple networks are conducted and the proposed DPGNN almost always significantly outperforms all other baselines. The implementation of DPGNN is available at: https://github.com/YuWVandy/DPGNN.

@inproceedings{mlg2022_6707,
title={Distance-wise Prototypical Graph Neural Network for Imbalanced Node Classification},
author={Yu Wang, Charu Aggarwal and Tyler Derr},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Understanding Self-Supervised Graph Representation Learning from a Data-Centric Perspective PDF
Puja Trivedi, Ekdeep Singh Lubana, Mark Heimann, Danai Koutra and Jayaraman Thiagarajan

Abstract: Recent analyses of self-supervised representation learning (SSL) find the following data-centric properties to be critical for learning high-quality representations: invariance to task-irrelevant semantics, separability of classes in some latent space, and recoverability of labels from augmented samples. However, given their discrete, non-Euclidean nature, graph datasets and graph SSL methods are unlikely to satisfy these properties. This raises the question: how do graph SSL methods work well? To systematically probe this question, we perform a generalization analysis for GGA based on dataset recoverability and separability constraints, yielding insights into task-relevance of data augmentations. As we empirically show, popularly used, generic graph augmentations (GGA) do not induce task-relevant invariances on common benchmark datasets, leading to only marginal gains over naive, untrained baselines. Our theory motivates a synthetic data generation process that enables control over both augmentation recoverability and dataset separability, enabling a better benchmark for evaluation of graph URL methods that demonstrates different training paradigms are effective in different regimes. Overall, our work rigorously contextualizes, both empirically and theoretically, the effects of data-centric properties on augmentation strategies and learning paradigms for graph SSL.

@inproceedings{mlg2022_7168,
title={Understanding Self-Supervised Graph Representation Learning from a Data-Centric Perspective},
author={Puja Trivedi, Ekdeep Singh Lubana, Mark Heimann, Danai Koutra and Jayaraman Thiagarajan},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Coarsen, Align, Project, Refine - A General Multilevel Framework for Network Alignment PDF
Jing Zhu, Danai Koutra and Mark Heimann

Abstract: 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 anorder of magnitude faster in runtime.

@inproceedings{mlg2022_7903,
title={Coarsen, Align, Project, Refine - A General Multilevel Framework for Network Alignment},
author={Jing Zhu, Danai Koutra and Mark Heimann},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Fast and Efficient n-Metrics for Multiple Graphs PDF
Kimia Shayestehfard, Dana Brooks and Stratis Ioannidis

Abstract: Graphs are widely used in diverse areas such as chemistry, engineering and network science to express relations among a set of objects. In all these fields, measuring the similarity among a group of graphs or indicating the correspondence among their nodes is of great importance. Many of the algorithms introduced for this purpose are not metrics and the few graph distance functions that do satisfy the properties of a metric are extremely slow to compute. In this work, we propose a fast and efficient framework to compute the distance among a group of graphs. Our method can improve the computation time up to 20 times over existing methods.

@inproceedings{mlg2022_8073,
title={Fast and Efficient n-Metrics for Multiple Graphs},
author={Kimia Shayestehfard, Dana Brooks and Stratis Ioannidis},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Ethereum Fraud Detection with Heterogeneous Graph Neural Networks PDF
Hiroki Kanezashi, Toyotaro Suzumura, Xin Liu and Takahiro Hirofuchi

Abstract: While transactions with cryptocurrencies such as Ethereum are becoming more prevalent, fraud and other criminal transactions are not uncommon. Graph analysis algorithms and machine learning techniques detect suspicious transactions that lead to phishing in large transaction networks. Many graph neural network (GNN) models have been proposed to apply deep learning techniques to graph structures. Although there is research on phishing detection using GNN models in the Ethereum transaction network, models that address the scale of the number of vertices and edges and the imbalance of labels have not yet been studied. In this paper, we compared the model performance of GNN models on the actual Ethereum transaction network dataset and phishing reported label data to exhaustively compare and verify which GNN models and hyperparameters produce the best accuracy. Specifically, we evaluated the model performance of representative homogeneous GNN models which consider single-type nodes and edges and heterogeneous GNN models which support different types of nodes and edges. We showed that heterogeneous models had better model performance than homogeneous models. In particular, the RGCN model achieved the best performance in the overall metrics.

@inproceedings{mlg2022_8513,
title={Ethereum Fraud Detection with Heterogeneous Graph Neural Networks},
author={Hiroki Kanezashi, Toyotaro Suzumura, Xin Liu and Takahiro Hirofuchi},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

mvn2vec: Preservation and Collaboration in Multi-View Network Embedding PDF
Yu Shi, Fangqiu Han, Xinwei He, Xinran He, Carl Yang, Luo Jie and Jiawei Han

Abstract: Multi-view networks are broadly present in real-world applications. In the meantime, network embedding has emerged as an effective representation learning approach for networked data. Therefore, we are motivated to study the problem of multi-view network embedding with a focus on the optimization objectives that are specific and important in embedding this type of networks. In our practice of embedding real-world multi-view networks, we explicitly identify two such objectives, which we refer to as preservation and collaboration. The in-depth analysis of these two objectives are discussed throughout this paper. In addition, the novel mvn2vec algorithms are proposed to (i) study how varied extent of preservation and collaboration can impact embedding learning and (ii) explore the feasibility of achieving better embedding quality by modeling them simultaneously. With experiments on a large-scale internal Snapchat dataset, two public datasets and a series of synthetic datasets, we confirm the validity and importance of preservation and collaboration as two objectives for multi-view network embedding. These experiments further demonstrate that better embedding can be obtained by simultaneously modeling the two objectives, while not over-complicating the model or requiring additional supervision. The code and the processed datasets are available at https://yu-shi-homepage.github.io/.

@inproceedings{mlg2022_9224,
title={mvn2vec: Preservation and Collaboration in Multi-View Network Embedding},
author={Yu Shi, Fangqiu Han, Xinwei He, Xinran He, Carl Yang, Luo Jie and Jiawei Han},
booktitle={Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG)},
year={2022}
}

Introduction

Schedule

Washington DC Convention Center - 207A

-Held jointly with Workshop on Deep Learning on Graphs (KDD-DLG)-

Keynote Speakers

Jiawei Han

Jennifer Neville

Yizhou Sun

Neil Shah

Accepted Papers

Call for Papers

Important Dates

Workshop Organizers

Shobeir Fakhraei

Tim Weninger

Neil Shah

Sami Abu-el-haija

Saurabh Verma

Tara Safavi

Program Committee

Previous Workshops

Introduction

Schedule

Washington DC Convention Center - 207A -Held jointly with Workshop on Deep Learning on Graphs (KDD-DLG)-

Keynote Speakers

Jiawei Han

Jennifer Neville

Yizhou Sun

Neil Shah

Accepted Papers

Call for Papers

Important Dates

Workshop Organizers

Shobeir Fakhraei

Tim Weninger

Neil Shah

Sami Abu-el-haija

Saurabh Verma

Tara Safavi

Program Committee

Previous Workshops

Washington DC Convention Center - 207A

-Held jointly with Workshop on Deep Learning on Graphs (KDD-DLG)-