There is a great deal of interest in analyzing data that is best represented as a graph. Examples include the WWW, social networks, biological networks, communication networks, transportation networks, energy grids, and many others. These graphs are typically multi-modal, multi-relational and dynamic. In the era of big data, the importance of being able to effectively mine and learn from such data is growing, as more and more structured and semi-structured data is becoming available. The workshop serves as a forum for researchers from a variety of fields working on mining and learning from graphs to share and discuss their latest findings.
There are many challenges involved in effectively mining and learning from this kind of data, including:
Understanding the different techniques applicable, including graph mining algorithms, network embeddings, graphical models, latent variable models, matrix factorization methods and more.
Dealing with the heterogeneity of the data.
The common need for information integration and alignment.
Handling dynamic and changing data.
Addressing each of these issues at scale.
Traditionally, a number of subareas have contributed to this space: communities in graph mining, learning from structured data, statistical relational learning, inductive logic programming, and, moving beyond subdisciplines in computer science, social network analysis, and, more broadly network science.
ExCeL London, London, UK | ICC Capital Suite Room 8
All accepted papers will be presented in the poster session.
Based on scheduling constraints, some papers are selected as contributed talks or spotlight presentations.
The contributed talks will be 15 min presentations including Q&A, and spotlight presentations will be 90 seconds (1 slide).
Morning Sessions
8:45 am
Opening Remarks & Best Paper Announcement
8:55 am
Keynote:
Luna Dong
Harvesting Knowledge from Semi-structured Web Data
9:30 am
Coffee Break
10:00 am
Keynote:
Kristina Lerman
Global Consequences of Local Bias in Networks
Contributed Talk:
Adaptive Diffusions for Scalable Learning over Graphs
1:55 pm
Keynote:
Tanya Berger-Wolf
Networks in Behavioral Ecology: Why Zebras Don't Have Facebook?
2:30 pm
Coffee Break (+ Poster Session)
3:00 pm
Keynote:
Taha Yasseri
Social Conflict, Learning Through Motif Analysis
3:35 pm
Contributed Talk:
From acquaintance to best friend forever: robust and fine-grained inference of social-tie strengths
3:50 pm
Closing Remarks
4:00 pm
Poster Session
Keynote Speakers
Tanya Berger-Wolf
Professor U. of Illinois Chicago
Luna Dong
Principal Scientist Amazon
Christos Faloutsos
Professor Carnegie Mellon U.
Kristina Lerman
Associate Professor U. of Southern California
Sujith Ravi
Research Scientist Google Research
Taha Yasseri
Assistant Professor University of Oxford
Accepted Papers
All accepted papers will present a poster, spotlights and talks are marked with
and
Growing Better Graphs With Latent-Variable Probabilistic Graph GrammarsPDF Xinyi Wang, Salvador Aguinaga, Tim Weninger and David Chiang
Abstract: Recent work in graph models has found that probabilistic hyperedge replacement grammars (HRGs) can be extracted from graphs and used to generate new random graphs with graph properties and substructures close to the original. In this paper, we show how to add latent variables to the model, trained using Expectation-Maximization, to generate still better graphs, that is, ones that generalize better to the test data. We evaluate the new method by separating training and test graphs, building the model on the former and measuring the likelihood of the latter, as a more stringent test of how well the model can generalize to new graphs. On this metric, we find that our latent-variable HRGs consistently outperform several existing graph models and provide interesting insights into the building blocks of real world networks.
@inproceedings{mlg2018_9,
title={Growing Better Graphs With Latent-Variable Probabilistic Graph Grammars},
author={Xinyi Wang, Salvador Aguinaga, Tim Weninger and David Chiang},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Adaptive Diffusions for Scalable Learning over GraphsPDF Dimitris Berberidis, Athanasios N. Nikolakopoulos and Georgios B. Giannakis
Abstract: Diffusion-based classifiers such as those relying on the Personalized
PageRank and the Heat kernel, enjoy remarkable classification accuracy at modest computational requirements. Their performance
however is affected by the extent to which the chosen diffusion
captures a typically unknown label propagation mechanism, that
can be specific to the underlying graph, and potentially different for
each class. The present work introduces a disciplined, data-efficient
approach to learning class-specific diffusion functions adapted to the
underlying network topology. The novel learning approach leverages the notion of "landing probabilities" of class-specific random
walks, which can be computed efficiently, thereby ensuring scalability to large graphs. This is supported by rigorous analysis of
the properties of the model as well as the proposed algorithms.
Classification tests on real networks demonstrate that adapting the
diffusion function to the given graph and observed labels, significantly improves the performance over fixed diffusions; reaching --
and many times surpassing -- the classification accuracy of computationally heavier state-of-the-art competing methods, that rely on
node embeddings and deep neural networks.
Keywords: Semi-supervised Classification, Random Walks, Diffusions
@inproceedings{mlg2018_21,
title={Adaptive Diffusions for Scalable Learning over Graphs},
author={Dimitris Berberidis, Athanasios N. Nikolakopoulos and Georgios B. Giannakis},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
From acquaintance to best friend forever: robust and fine-grained inference of social-tie strengthsPDF Florian Adriaens, Tijl De Bie, Aristides Gionis, Jefrey Lijffijt and Polina Rozenshtein
Abstract: Social networks often provide only a binary perspective on social ties: two individuals are either connected or not.
While sometimes external information can be used to infer the strength of social ties, access to such information may be restricted or impractical.
Sintos and Tsaparas (KDD 2014) first suggested to infer the strength of social ties from the topology of the network alone, by leveraging the Strong Triadic Closure (STC) property, postulated to hold in social networks.
The STC property states that if person A has strong social ties with persons B and C, B and C must be connected to each other as well (whether with a weak or strong tie).
Sintos and Tsaparas exploited this property to formulate the inference of the strength of social ties as an NP-hard optimization problem, and proposed two approximation algorithms.
We refine and improve this line of work,by developing a sequence of linear relaxations of the problem, which can be solved exactly in polynomial time.
Usefully, these relaxations infer more fine-grained levels of tie strength (beyond strong and weak),which also allows to avoid making arbitrary strong/weak strength assignments when the network topology provides inconclusive evidence.
One of the relaxations simultaneously infers the presence of a limited number of STC violations.
An extensive theoretical analysis leads to two efficient algorithmic approaches.
Finally, our experimental results elucidate the strengths of the proposed approach, and sheds new light on the validity of the STC property in practice.
Keywords: Strong Triadic Closure, Strength of social ties, Linear Programming, Convex Relaxations
@inproceedings{mlg2018_28,
title={From acquaintance to best friend forever: robust and fine-grained inference of social-tie strengths},
author={Florian Adriaens, Tijl De Bie, Aristides Gionis, Jefrey Lijffijt and Polina Rozenshtein},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Watch Your Step: Learning Graph Embeddings Through AttentionPDF Sami Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou and Alex Alemi
Abstract: Graph embedding methods represent nodes in a continuous vector space,
preserving information from the graph (e.g. by sampling random walks).
There are many hyper-parameters to these methods (such as random walk length) which have to be manually tuned for every graph.
In this paper, we replace random walk hyper-parameters with trainable parameters that we automatically learn via backpropagation. In particular, we learn a novel attention model on the power series of the transition matrix, which guides the random walk to optimize an upstream objective.
Unlike previous approaches to attention models, the method that we propose
utilizes attention parameters exclusively on the data (e.g. on the random walk), and not used by the model for inference.
We experiment on link prediction tasks, as we aim to produce embeddings that best-preserve the graph structure, generalizing to unseen information. We improve state-of-the-art on a comprehensive suite of real world datasets including social, collaboration, and biological networks. Adding attention to random walks can reduce the error by 20% to 45% on datasets we attempted.
Further, our learned attention parameters are different for every graph, and our automatically-found values agree with the optimal choice of hyper-parameter if we manually tune existing methods.
Keywords: Graph, Embedding, Attention, Context Distribution, Deep Learning
@inproceedings{mlg2018_50,
title={Watch Your Step: Learning Graph Embeddings Through Attention},
author={Sami Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou and Alex Alemi},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
t-PINE: Tensor-based Predictable and Interpretable Node EmbeddingsPDF Saba Al-Sayouri, Ekta Gujral, Danai Koutra, Evangelos Papalexakis and Sarah Lam
Abstract: Graph representations have increasingly grown in popularity dur- ing the last years. Existing representation learning approaches ex- plicitly encode network structure. Despite their good performance in downstream processes (e.g., node classi cation, link prediction), there is still room for improvement in di erent aspects, like e cacy, visualization, and interpretability. In this paper, we propose, t-PINE, a method that addresses these limitations. Contrary to baseline methods, which generally learn explicit graph representations by solely using an adjacency matrix, t-PINE avails a multi-view infor- mation graph—the adjacency matrix represents the rst view, and a nearest neighbor adjacency, computed over the node features, is the second view—in order to learn explicit and implicit node repre- sentations, using the Canonical Polyadic (a.k.a. CP) decomposition. We argue that the implicit and the explicit mapping from a higher- dimensional to a lower-dimensional vector space is the key to learn more useful, highly predictable, and gracefully interpretable rep- resentations. Having good interpretable representations provides a good guidance to understand how each view contributes to the representation learning process. In addition, it helps us to exclude unrelated dimensions. Extensive experiments show that t-PINE drastically outperforms baseline methods by up to 158.6% with respect to Micro-F1, in several multi-label classi cation problems, while it has high visualization and interpretability utility.
Keywords: information networks, graph embeddings, tensor decomposition
@inproceedings{mlg2018_1,
title={t-PINE: Tensor-based Predictable and Interpretable Node Embeddings},
author={Saba Al-Sayouri, Ekta Gujral, Danai Koutra, Evangelos Papalexakis and Sarah Lam},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Fully Heterogeneous Collective RegressionPDF David Liedtka and Luke McDowell
Abstract: Prior work has demonstrated that multiple methods for link-based classification (LBC) can substantially improve accuracy when the nodes of interest are interconnected. To date, however, very little work has considered how methods for LBC could be applied in domains that require continuous, rather than categorical, predictions. In addition, prior work with LBC has learned only one predictive model to use for all nodes of a given type, but some domains exhibit significant node diversity that is not well-suited to this approach. In response, we introduce fully heterogeneous collective regression (FHCR), a new method that learns node-specific models from data and uses these models to jointly predict continuous outputs. We apply FHCR to a voting prediction task, and create novel correlation-based link generation methods that outperform alternative methods. In addition, we introduce multiple new methods for inferring continuous outputs that can incorporate link-based information, and show that regression-specific methods based on Bayesian inference outperform the naive approach of inserting regression into existing LBC methods. Overall, we demonstrate the viability of the new FHCR paradigm by producing results that are comparable or better than those of previous link-unaware methods, yet are at least two orders of magnitude faster.
@inproceedings{mlg2018_33,
title={Fully Heterogeneous Collective Regression},
author={David Liedtka and Luke McDowell},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Reducing Network Incompleteness Through Online Learning: A Feasibility StudyPDF Timothy Larock, Timothy Sakharov, Sahely Bhadra and Tina Eliassi-Rad
Abstract: Real-world phenomena are often partially observed. This partial observability leads to incomplete data. Acquiring more data is often expensive, hard, or impossible. We present a feasibility study on the limits of online learning to reduce incompleteness in network data. In particular, we investigate the following problem: given a network and limited resources to collect more data (i.e., a budget), can an optimal strategy be learned for reducing the network's incompleteness? Reducing the incompleteness of a network can be interpreted in different ways and represented by various objective functions. For example, it could mean: observe as many previously unobserved nodes as possible, or observe as many new nodes with a certain property, or observe as many new nodes and triangles, etc. Here, we focus on the first interpretation -- i.e., we use the given budget to increase the number of nodes in the incomplete graph; but our proposed method can handle various objective functions. Using one unit of the budget means querying an oracle that has access to the fully observed network and getting back full information about a single node's neighbors (at the time of query). We refer to this process as probing a node. Examples of probing nodes include using an API to get information about an account, placing monitors on routers to get information about Internet traffic flow, etc. We make no assumptions about the underlying model generating the network data or how the incomplete network was observed. Our findings on synthetic and real-world networks showcase when learning is feasible, when it is not, and when one should just use a heuristic (i.e., when learning is unnecessary or redundant).
Keywords: Partially observed networks, Online learning, Feasibility study
@inproceedings{mlg2018_40,
title={Reducing Network Incompleteness Through Online Learning: A Feasibility Study},
author={Timothy Larock, Timothy Sakharov, Sahely Bhadra and Tina Eliassi-Rad},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
What the HAK? Estimating Ranking Deviations in Incomplete GraphsPDF Helge Holzmann, Avishek Anand and Megha Khosla
Abstract: Most real-world graphs collected from the Web like Web graphs and social network graphs are incomplete. This leads to inaccurate estimates of graph properties based on link analysis such as PageRank. In this paper we focus on studying such deviations in ordering/ranking imposed by PageRank over incomplete graphs. We first show that deviations in rankings induced by PageRank are indeed possible. We measure how much a ranking, induced by PageRank, on an input graph could deviate from the original unseen graph. More importantly, we are interested in conceiving a measure that approximates the rank correlation among them without any knowledge of the original graph. To this extent we formulate the HAK measure that is based on computing the impact redistribution of PageRank according to the local graph structure. Finally, we perform extensive experiments on both real-world Web and social network graphs with more than 100M vertices and 10B edges as well as synthetic graphs to showcase the utility of HAK.
@inproceedings{mlg2018_2,
title={What the HAK? Estimating Ranking Deviations in Incomplete Graphs},
author={Helge Holzmann, Avishek Anand and Megha Khosla},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Hierarchical Graph Clustering based on Node Pair SamplingPDF Thomas Bonald, Bertrand Charpentier, Alexis Galland and Alexandre Hollocou
Abstract: We present a novel hierarchical graph clustering algorithm inspired by modularity-based clustering techniques. The algorithm is agglomerative and based on a simple distance between clusters induced by the probability of sampling node pairs. We prove that this distance is reducible, which enables the use of the nearest-neighbor chain to speed up the agglomeration. The output of the algorithm is a regular dendrogram, which reveals the multi-scale structure of the graph. The results are illustrated on both synthetic and real datasets.
@inproceedings{mlg2018_4,
title={Hierarchical Graph Clustering based on Node Pair Sampling},
author={Thomas Bonald, Bertrand Charpentier, Alexis Galland and Alexandre Hollocou},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Generalized Embedding Models for Knowledge Graph MiningPDF Qiao Liu, Rui Wan, Xiaohui Yang, Yifu Zeng and Haibin Zhang
Abstract: Many types of relations in physical, biological, social and information systems can be modeled as homogeneous or heterogeneous concept graphs. Hence, learning from and with graph embeddings has drawn a great deal of research interest recently, but developing an embedding learning method that is flexible enough to accommodate variations in physical networks is still a challenging problem. In this paper, we conjecture that the one-shot supervised learning mechanism is a bottleneck in improving the performance of the graph embedding learning, and propose to extend this by introducing a multi-shot “unsupervised” learning framework where a 2-layer MLP network for every shot .The framework can be extended to accommodate a variety of homogeneous and heterogeneous networks. Empirical results on several real-world data set show that the proposed model consistently and significantly outperforms existing state-of-the-art approaches on knowledge base completion and graph based multi-label classification tasks.
@inproceedings{mlg2018_5,
title={Generalized Embedding Models for Knowledge Graph Mining},
author={Qiao Liu, Rui Wan, Xiaohui Yang, Yifu Zeng and Haibin Zhang},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Network Signatures from Image Representation of Adjacency Matrices: Deep/Transfer Learning for Subgraph ClassificationPDF Kshiteesh Hegde, Malik Magdon-Ismail, Ram Ramanathan and Bishal Thapa
Abstract: This paper is a hybrid between novel research and a demo. We show the power of image representation of subgraphs for classification of network fragments with the targets being their parent networks. The graph image representation is based on 2D image embeddings of adjacency matrices. We use this image representation in two modes. First, as the input to a machine learning algorithm. Second, as the input to a pure transfer learner. Our conclusions from several datasets are that
i. deep learning using our structured image features performs the best compared to benchmark graph kernel and classical features based methods; and,
ii. pure transfer learning works effectively with minimum interference from the user and is robust against small data.
Keywords: Deep Learning, Network Signatures, Graph Classification, Image Embeddings of Graphs, Transfer Learning
@inproceedings{mlg2018_10,
title={Network Signatures from Image Representation of Adjacency Matrices: Deep/Transfer Learning for Subgraph Classification},
author={Kshiteesh Hegde, Malik Magdon-Ismail, Ram Ramanathan and Bishal Thapa},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Testing Alignment of Node Attributes with Network Structure Through Label Propagation PDF Natalie Stanley, Marc Niethammer and Peter J. Mucha
Abstract: Attributed network data is becoming increasingly common across fields, as we are often equipped with information about nodes in addition to their pairwise connectivity patterns. This extra information can manifest as a classification, or as a multidimensional vector of features. Recently developed methods that seek to extend community detection approaches to attributed networks have explored how to most effectively combine connectivity and attribute information to identify quality communities. These methods often rely on some assumption of the dependency relationships between attributes and connectivity. In this work, we seek to develop a statistical test to assess whether node attributes align with network connectivity. The objective is to quantitatively evaluate whether nodes with similar connectivity patterns also have similar attributes. To address this problem, we use a node sampling and label propagation approach. We apply our method to several synthetic examples that explore how network structure and attribute characteristics affect the empirical p-value computed by our method. Finally, we apply the test to a network generated from a single cell mass cytometry (CyTOF) dataset and show that our test can identify markers associated with distinct sub populations of single cells.
Keywords: community detection, attributed networks, label propagation, computational biology, clustering
@inproceedings{mlg2018_13,
title={Testing Alignment of Node Attributes with Network Structure Through Label Propagation },
author={Natalie Stanley, Marc Niethammer and Peter J. Mucha},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
The Power Mean Laplacian for Multilayer Graph ClusteringPDF Pedro Mercado, Antoine Gautier, Francesco Tudisco and Matthias Hein
Abstract: Multilayer graphs encode different kind of interactions between the same set of entities. When one wants to cluster such a multilayer graph, the natural question arises how one should merge the information from different layers. We introduce in this paper a one-parameter family of matrix power means for merging the Laplacians from different layers and analyze it in expectation in the stochastic block model. We show that this family allows to recover ground truth clusters under different settings and verify this in real world data. While computing the matrix power mean can be very expensive for large graphs, we introduce a numerical scheme to efficiently compute its eigenvectors for the case of large sparse graphs.
Keywords: Multilayer Graphs, Spectral Clustering, Numerical Linear Algebra
@inproceedings{mlg2018_18,
title={The Power Mean Laplacian for Multilayer Graph Clustering},
author={Pedro Mercado, Antoine Gautier, Francesco Tudisco and Matthias Hein},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Spread Sampling for Graphs: Theory and ApplicationPDF Yu Wang, Bortik Bandyopadhyay, Aniket Chakrabarti, David Sivakoff and Srinivasan Parthasarathy
Abstract: This paper proposes a novel scalable node sampling algorithm for large graphs that can achieve better \textit{spread}
or diversity across communities intrinsic to the graph without requiring any costly pre-processing steps.
The proposed method leverages a simple iterative sampling technique controlled by two parameters: \textit{infection rate},
that controls the dynamics of the procedure and \textit{removal threshold} that affects the end-of-procedure sampling size.
We present theoretical analyses of the sampling probability for this method on the celebrated Erd\H os--R\'enyi graph model,
and of the community diversity on the Stochastic Block Model.
Efficiently finding small samples with high diversity from large graphs has a number of practical applications such as online survey and community detection.
Our method achieves very high community diversity with extremely low sampling budget on both synthetic and real-world graphs, with either balanced or imbalanced communities.
We leverage the proposed sampling technique on community detection and show it outperforms the baselins of the same type.
Keywords: Sampling, Graph Mining, Community Detection
@inproceedings{mlg2018_22,
title={Spread Sampling for Graphs: Theory and Application},
author={Yu Wang, Bortik Bandyopadhyay, Aniket Chakrabarti, David Sivakoff and Srinivasan Parthasarathy},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Temporal Walk Based Centrality Metric for Graph StreamsPDF Ferenc Beres, Andras A. Benczur and Robert Palovics
Abstract: Centrality measures account for the importance of the nodes of a network.
In the seminal study of Boldi and Vigna (2014), the comparative evaluation of centrality measures was termed a difficult, arduous task.
In networks with fast dynamics, such as the Twitter mention or retweet graphs, predicting emerging centrality is even more challenging.
Our main result is a new, temporal walk based dynamic centrality measure that models temporal information propagation by considering the order of edge creation.
This measure outperforms graph snapshot based static and other recently proposed dynamic centrality measures in assigning the highest time-aware centrality to the actually relevant nodes of the network.
One of our main contributions is creating a quantitative experiment to assess temporal centrality metrics.
Keywords: Temporal graphs, Twitter, Centrality, Data Stream
@inproceedings{mlg2018_27,
title={Temporal Walk Based Centrality Metric for Graph Streams},
author={Ferenc Beres, Andras A. Benczur and Robert Palovics},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
A Method for Learning Representations of Signed NetworksPDF Inzamam Rahaman and Patrick Hosein
Abstract: There has been an increasing interest in learning low dimensional
representations of graphs that can be exploited in machine learning
and data mining. The geometric relationships between the
representations learned for nodes should reflect relationships between
nodes in the graph. Most work has concentrated on unsigned
graphs, which only model positive relationships. However, such
techniques can be inadequate for signed graphs, which model both
positive and negative relationships. In this work in progress paper,
we present a method - StEM (Signed neTwork Embedding Model) -
for learning representations of signed networks that can achieve
good performance on the tasks of visualization, node classification,
and signed link prediction.
Keywords: Signed Networks, Representation Learning, Graph Embedding
@inproceedings{mlg2018_31,
title={A Method for Learning Representations of Signed Networks},
author={Inzamam Rahaman and Patrick Hosein},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Logistic-Tropical Decompositions and Nested SubgraphsPDF Sanjar Karaev, Saskia Metzler and Pauli Miettinen
Abstract: Communities in graphs are usually modelled as (quasi-) cliques, but this is not the only -- or even necessarily the best -- model. Other models, such as stars, hyperbolic shapes, or core-periphery communities have been proposed as well. These can be generalized to nested subgraphs, i.e. graphs whose adjacency matrix is nested. In this paper, we study the problem of summarizing a graph as a union of nested subgraphs. We approach the problem by applying a recent characterization of nested graphs using rounding rank. We extend this characterization to sets of overlapping nested matrices using tropical algebra. This allows us to model the problem as a thresholded subtropical matrix factorization, and design an algorithm for a maximum-likelihood version of the problem. Our experiments show that our algorithm is very scalable and can find good summarizations using structures that cannot be concisely expressed in terms of normal matrix factorizations.
Keywords: tropical algebra, community detection, nested matrix, rounding rank
@inproceedings{mlg2018_35,
title={Logistic-Tropical Decompositions and Nested Subgraphs},
author={Sanjar Karaev, Saskia Metzler and Pauli Miettinen},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Graph CNN + LSTM Framework For Dynamic Macroscopic Traffic Congestion PredictionPDF Sudatta Mohanty and Alexey Pozdnukhov
Abstract: Accurate real-time predictions for traffic congestion in a region and knowledge of its causes may allow implementation of effective dynamic control strategies. However, the complex nature of congestion propagation and network-wide spatio-temporal correlations make prediction challenging. To facilitate this process, we define a novel dynamic state variable corresponding to a zone with homogeneous and slowly evolving traffic, called Macroscopic Congestion Level (MCL). We hypothesize that future MCL is a function of the current and past network states for the region-wide network, defined by Origin-Destination (O-D) demand, link counts, link travel times and observed MCL values. We leverage the fact that transportation systems often generate graph-like data either because physical movement is constrained to a road network or due to the coordination of travel choices made by various individuals. We construct a knowledge graph and implement a Graph-CNN + LSTM model to make real-time predictions. The model accuracy is tested against several baselines: (i) 1-NN model, (ii) LSTM-only model and (iii) Graph-CNN + LSTM model with no road network related priors; on simulated data of home-work and work-home trips on a simplified freeway network representing nine counties in the SF Bay Area. Our results indicate improvement in performance which may be attributed to better feature learning by Graph-CNN. Finally, we develop a Neural Attention based framework to produce a spatio-temporal saliency heatmap of input variables. Tests on a toy network with hypothetical demand demonstrate the effectiveness of the proposed framework for identifying the specific cause of congestion.
This paper has been jointly submitted to 14th International Workshop On Mining And Learning With Graphs as well as 3rd Mining Urban Data Workshop, both organized in conjunction with ACM SIGKDD 2018.
@inproceedings{mlg2018_41,
title={Graph CNN + LSTM Framework For Dynamic Macroscopic Traffic Congestion Prediction},
author={Sudatta Mohanty and Alexey Pozdnukhov},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Temporal Graph Generation Based on a Distribution of Temporal MotifsPDF Sumit Purohit, Lawrence B Holder and George Chin
Abstract: Generating a synthetic graph that is similar to a given real-world graph is a critical requirement for privacy preservation and benchmarking purposes. Various generative models attempt to generate static graphs similar to real-world graphs. However, generation of temporal graphs is still an open research area. We present a temporal-motif based approach to generate synthetic temporal graph datasets and show results from three real-world use cases. We show that our approach can generate high fidelity synthetic graph. We also show that this approach can also generate multi-type heterogeneous graph. We also present a parameterized version of our approach which can generate linear, sub-linear, and super-linear preferential attachment graph.
Keywords: Temporal Graph, Graph Generative Model, Motifs Distribution
@inproceedings{mlg2018_42,
title={Temporal Graph Generation Based on a Distribution of Temporal Motifs},
author={Sumit Purohit, Lawrence B Holder and George Chin},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Relevance Measurements in Online Signed Social NetworksPDF Tyler Derr, Chenxing Wang, Suhang Wang and Jiliang Tang
Abstract: Measuring relevance for two nodes is fundamental to social network analysis, which has been proven to benefit many network analysis tasks and applications such as link prediction, node classification, community detection, search and recommendations. The majority of existing relevance measurements focused on unsigned social networks (or networks with only positive links). However, social media provides mechanisms that allow online users to specify negative links in addition to positive ones. For example, Slashdot users can create foe links; users in Epinions can establish distrust relations; while users in Facebook and Twitter can block or unfriend others. Thereby, social networks with both positive and negative links (or signed social networks) become ubiquitous in social media and have attracted increasing attention in recent years. On the one hand, it is evident from recent studies that negative links have added value in a number of analytical tasks. On the other hand, the availability of negative links challenges existing relevance measurements designed for unsigned networks. Hence, we need dedicated relevance measurements for signed social networks. In this paper, we present an initial and comprehensive investigation on signed relevance measurements and design numerous relevance measurements for signed social networks from both local and global perspectives. Empirical experiments on four real-world signed social networks demonstrate the importance of negative links in building signed relevance measurements and their effects on social network analysis tasks.
Keywords: Signed networks, Relevance measurement, Balance theory
@inproceedings{mlg2018_48,
title={Relevance Measurements in Online Signed Social Networks},
author={Tyler Derr, Chenxing Wang, Suhang Wang and Jiliang Tang},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
A Marketing Game: a rigorous model for strategic resource allocationPDF Matthew Reyes
Abstract: We have recently introduced a model of consumer choice that parametrizes actions taken by a marketer to influence decisions made within a social network. The foundation of our model is the theory of random utility due to McFadden and others, and the extension to contingent decision-making pioneered by Blume, on top of which we introduced a marketer for each of the alternatives from which consumers make their respective choice decisions, and the concept of a marketing response indicating the marketing strength that results from a particular dollar investment.
In this paper we follow up on our previous work and consider a number of questions relevant to marketing on topologies on interest.
@inproceedings{mlg2018_53,
title={A Marketing Game: a rigorous model for strategic resource allocation},
author={Matthew Reyes},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
GeniePath: Graph Neural Networks with Adaptive Receptive PathsPDF Ziqi Liu and Jun Zhou
Abstract: We present, GeniePath, a scalable approach for learning adaptive receptive fields of neural networks defined on permutation invariant graph data. In GeniePath, we propose an adaptive path layer consists of two functions designed for breadth and depth exploration respectively, where the former learns the importance of different sized neighborhoods, while the latter extracts and filters signals aggregated from neighbors of different hops away. Our method works both in transductive and inductive settings, and extensive experiments com- pared with state-of-the-art methods show that our approaches are useful especially on large graph.
Keywords: graph neural networks, graph representation learning, receptive field learning
@inproceedings{mlg2018_59,
title={GeniePath: Graph Neural Networks with Adaptive Receptive Paths},
author={Ziqi Liu and Jun Zhou},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal NetworksPDF Ingo Scholtes
Abstract: We introduce a framework for the modeling of sequential data capturing pathways of varying lengths observed in a network. Such data are important, e.g., when studying click streams in the Web, travel patterns in transportation systems, information cascades in social networks, biological pathways, or time-stamped social interactions. While it is common to apply graph analytics and network analysis to such data, recent works have shown that temporal correlations can invalidate the results of such methods. This raises a fundamental question: When is a network abstraction of sequential data justified? Addressing this open question, we propose a framework that combines Markov chains of multiple, higher orders into a multi-layer graphical model that captures temporal correlations in pathways at multiple length scales simultaneously. We develop a model selection technique to infer the optimal number of layers of such a model and show that it outperforms baseline Markov order detection techniques. An application to eight data sets on pathways and temporal networks shows that it allows to infer graphical models that capture both topological and temporal characteristics of such data. Our work highlights fallacies of graph mining and network analysis techniques and provides a principled answer to the open question when they are justified. Generalizing network representations to multi-order graphical models, it opens perspectives for new data mining and machine learning algorithms for graphs.
This submission is a shortened version of a research paper published at KDD'17.
Keywords: higher-order network analysis, representation learning, model selection, dynamic social networks, pathway data, time series analysis, node ranking
@inproceedings{mlg2018_55,
title={When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks},
author={Ingo Scholtes},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Towards Shortest Paths Via Adiabatic Quantum ComputingPDF Christian Bauckhage, Rafet Sifa, Jannis Schücker, Cesar Ojeda, Eduado Brito and Kostadin Cvejoski
Abstract: Since first working quantum computers are now available, accelerated developments of this technology may be expected. This will likely impact graph- or network analysis because quantum computers promise fast solutions for many problems in these areas. In this paper, we explore the use of adiabatic quantum computing in finding shortest paths. We devise an Ising energy minimization formulation for this task and discuss how to set up a system of quantum bits to find minimum energy states of the model. In simulation experiments, we numerically solve the corresponding Schroedinger equations and observe our approach to work well. This evidences that shortest path computation can at least be assisted by quantum computers.
@inproceedings{mlg2018_7,
title={Towards Shortest Paths Via Adiabatic Quantum Computing},
author={Christian Bauckhage, Rafet Sifa, Jannis Schücker, Cesar Ojeda, Eduado Brito and Kostadin Cvejoski},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Semi-Supervised Learning on Graphs Based on Local Label DistributionsPDF Evgeniy Faerman, Felix Borutta, Julian Busch and Matthias Schubert
Abstract: Most approaches that tackle the problem of node classification consider nodes to be similar, if they have shared neighbors or are close to each other in the graph. Recent methods for attributed graphs additionally take attributes of neighboring nodes into account. We argue that the class labels of the neighbors bear important information and considering them helps to improve classification quality. Two nodes which are similar based on class labels in their neighborhood do not need to be close-by in the graph and may even belong to different connected components. In this work, we propose a novel approach for the semi-supervised node classification. Precisely, we propose a new node embedding which is based on the class labels in the local neighborhood of a node. We show that this is a different setting from attribute-based embeddings and thus, we propose a new method to learn label-based node embeddings which can mirror a variety of relations between the class labels of neighboring nodes. Our experimental evaluation demonstrates that our new methods can significantly improve the prediction quality on real world data sets.
@inproceedings{mlg2018_8,
title={Semi-Supervised Learning on Graphs Based on Local Label Distributions},
author={Evgeniy Faerman, Felix Borutta, Julian Busch and Matthias Schubert},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Abstract: Knowledge graphs, which are rich networks of entities and concepts connected via multiple types of relationships, have gained traction as powerful structures for natural language understanding and question answering. Although recent research efforts have started to address efficient querying and storage of knowledge graphs, such methods are neither \emph{user-driven} nor \emph{flexible to changes in the data}, both of which are important in the real world. We thus introduce and motivate \textbf{adaptive knowledge graph summarization} to create personalized local knowledge graphs that contain only the information most relevant to an individual user's interests. Such concise summaries may be stored on mobile devices, allowing for fast interactive querying, and constantly updated to serve changing user needs and data evolution. In this position paper, we make a case for adaptive knowledge graph summarization, outlining promising approaches toward efficient, personalized knowledge graph management.
@inproceedings{mlg2018_11,
title={Adaptive Personalized Knowledge Graph Summarization},
author={Lukas Faber, Tara Safavi, Davide Mottin, Emmanuel Müller and Danai Koutra},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
GraphRAD: A Graph-based Risky Account Detection SystemPDF Jun Ma, Danqing Zhang, Yun Wang, Yan Zhang and Alexey Pozdnoukhov
Abstract: Given the linked account graph with tens of millions of vertices, and a list of confirmed risky accounts, how can we quickly find a short list of potential risky accounts for further human expert investigation? Most mainstream graph-based fraud detection algorithms focusing on detecting dense blocks of fake follows, or fake reviews from the social media graph, however, do not align well with the answer of the question.
Here we hypothesize that fraud accounts share dense connections within a "fraud community", but have less so with accounts outside of community. We propose GraphRAD, a risky account detection system based on local graph clustering algorithms. Our experiments show that from a real-world account graph of 60 million vertices and 500 million edges, GraphRAD was able to catch 67 previously unidentified fraud accounts by proposing 28 small-scale local communities, which is significantly more effective than the baseline model.
The paper is submitted as work-in-progress.
Keywords: fraud detection, payment fraud, local graph clustering, community detection, semi-supervised learning, graph regularization
@inproceedings{mlg2018_12,
title={GraphRAD: A Graph-based Risky Account Detection System},
author={Jun Ma, Danqing Zhang, Yun Wang, Yan Zhang and Alexey Pozdnoukhov},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Jointly learning relevant subgraph patterns and nonlinear models of their indicatorsPDF Ryo Shirakawa, Yusei Yokoyama, Fumiya Okazaki and Ichigaku Takigawa
Abstract: Classification and regression in which the inputs are graphs of arbitrary size and shape have been paid attention in various fields such as computational chemistry and bioinformatics. Subgraph indicators are often used as the most fundamental features, but the number of possible subgraph patterns are intractably large due to the combinatorial explosion. We propose a novel efficient algorithm to jointly learn relevant subgraph patterns and nonlinear models of their indicators. Previous methods for such joint learning of subgraph features and models are based on search for single best subgraph features with specific pruning and boosting procedures of adding their indicators one by one, which result in linear models of subgraph indicators. In contrast, the proposed approach is based on directly learning regression trees for graph inputs using a newly derived bound of the total sum of squares for data partitions by a given subgraph feature, and thus can learn nonlinear models through standard gradient boosting. An illustrative example we call the Graph-XOR problem to consider nonlinearity, numerical experiments with real datasets, and scalability comparisons to naïve approaches using explicit pattern enumeration are also presented.
@inproceedings{mlg2018_17,
title={Jointly learning relevant subgraph patterns and nonlinear models of their indicators},
author={Ryo Shirakawa, Yusei Yokoyama, Fumiya Okazaki and Ichigaku Takigawa},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
A Graph Model with Indirect Co-location LinksPDF Md Shahzamal, Raja Jurdak, Bernard Mans and Frank de Hoog
Abstract: Graph models are widely used to analyse diffusion processes embedded in social contacts and to develop applications. A range of graph models are available to replicate the underlying social structures and dynamics realistically. However, most of the current graph models can only consider concurrent interactions among individuals in the co-located interaction networks. However, they do not account for indirect interactions that can transmit spreading items to individuals who visit the same locations at different times but within a certain time limit. The diffusion phenomena occurring through direct and indirect interactions is called same place different time (SPDT) diffusion. This paper introduces a model to synthesize co-located interaction graphs capturing both direct interactions, where individuals meet at a location, and indirect interactions, where individuals visit the same location at different times within a set timeframe. We analyze 60 million location updates made by 2 million users from a social networking application to characterize the graph properties, including the space-time correlations and its time evolving characteristics, such as bursty or ongoing behaviors. The generated synthetic graph reproduces diffusion dynamics of a realistic contact graph, and reduces the prediction error by up to 82 when compare to other contact graph models demonstrating its potential for forecasting epidemic spread.
Keywords: Network embedding models, Graph mining, Statistical models of graph structure, Large-scale analysis and modeling, Social networks, Spatio-temporal data
@inproceedings{mlg2018_19,
title={A Graph Model with Indirect Co-location Links},
author={Md Shahzamal, Raja Jurdak, Bernard Mans and Frank de Hoog},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Probabilistic Random Walks for Churn Prediction using Representation LearningPDF Sandra Mitrovic and Jochen De Weerdt
Abstract: Unleashing the full potential of data is oftentimes a cumbersome task, especially when dealing with network data. It is therefore possible that while focusing on one part of the solution, other valuable pieces of information remain under-treated leading to under-performing results. In this work, we zoom into the nature of an augmentation of call graphs devised for addressing churn prediction in telco. By shifting the focus from a homogeneous to a heterogeneous perspective, by defining different probabilistic meta paths, and by applying representation learning on graphs using these defined meta paths, we demonstrate the benefits of this approach, not only by means of improvements of predictive results, but also with promising insights regarding the interplay of meta path type and predictive outcome. As such, this is still a work in progress but the current results have also been submitted to (and are currently under review at) another conference.
Keywords: Probabilistic Random Walks, Node Embedding, RFM-Augmented Networks, Churn Prediction
@inproceedings{mlg2018_24,
title={Probabilistic Random Walks for Churn Prediction using Representation Learning},
author={Sandra Mitrovic and Jochen De Weerdt},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Mining Subjectively Interesting Attributed SubgraphsPDF Anes Bendimerad, Ahmad Mel, Jefrey Lijffijt, Marc Plantevit, Céline Robardet and Tijl De Bie
Abstract: Community detection in graphs, data clustering, and local pattern mining are three mature fields of data mining and machine learning.
In recent years, attributed subgraph mining is emerging as a new powerful data mining task in the intersection of these areas. Given a graph and a set of attributes for each vertex, attributed subgraph mining aims to find cohesive subgraphs for which (a subset of) the attribute values has exceptional values in some sense.
While research on this task can borrow from the three abovementioned fields, the principled integration of graph and attribute data poses two challenges: the definition of a pattern language that is intuitive and lends itself to efficient search strategies, and the formalization of the interestingness of such patterns.
We propose an integrated solution to both of these challenges. The proposed pattern language improves upon prior work in being both highly flexible and intuitive.
We show how an effective and principled algorithm can enumerate patterns of this language. The proposed approach for quantifying interestingness of patterns of this language is rooted in information theory, and is able to account for prior knowledge on the data.
Prior work typically quantifies interestingness for the cohesion of the subgraph and for the exceptionality of its attributes separately, to combine these in a parameterized trade-off. Instead, in our proposal this trade-off is implicitly handled in a principled, parameter-free manner.
Extensive empirical results confirm the proposed pattern syntax is intuitive, and the interestingness measure aligns well with actual subjective interestingness.
@inproceedings{mlg2018_26,
title={Mining Subjectively Interesting Attributed Subgraphs},
author={Anes Bendimerad, Ahmad Mel, Jefrey Lijffijt, Marc Plantevit, Céline Robardet and Tijl De Bie},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
From clusters to queries: exploiting uncertainty in the modularity landscape of complex networksPDF James Gilbert and Jamie Twycross
Abstract: Uncovering latent community structure in complex networks is a field that has received an enormous amount of attention.
Unfortunately, whilst potentially very powerful, unsupervised methods for uncovering labels based on topology alone has been shown to suffer from several difficulties.
For example, the search space for many module extraction approaches, such as the modularity maximisation algorithm, appears to be extremely glassy, with many high valued solutions that lack any real similarity to one another.
However, in this paper we argue that this is not a flaw with the modularity maximisation algorithm but, rather, information that can be used to aid the context specific classification of functional relationships between vertices.
Formally, we present an approach for generating a high value modularity consensus space for a network, based on the ensemble space of locally optimal modular partitions.
We then use this approach to uncover latent relationships, given small query sets.
The methods developed in this paper are applied to biological and social datasets with ground-truth label data, using a small number of examples used as seed sets to uncover relationships.
When tested on both real and synthetic datasets our method is shown to achieve high levels of classification accuracy in a context specific manner, with results comparable to random walk with restart methods.
Keywords: Complex networks, Community detection, Graph clustering, Semi-supervised Learning, Analysis of biological networks
@inproceedings{mlg2018_36,
title={From clusters to queries: exploiting uncertainty in the modularity landscape of complex networks},
author={James Gilbert and Jamie Twycross},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Clustering Affiliation Inference from Graph SamplesPDF Jianpeng Zhang, Kaijie Zhu, Yulong Pei, George Fletcher and Mykola Pechenizkiy
Abstract: Graph sampling is a widely-used approach to address the scalability issue when analyzing large-scale graphs. Several promising cluster-preserving sampling algorithms have been proposed. However, once the clustering structure on a sampled graph is obtained, we may still need a method to infer the clustering affiliations of all other nodes in the original graph from the clustered nodes in the sampled subgraph. In this paper, we present a new two-stage clustering inference (\textit{TCI}) method to infer clustering affiliations of all nodes in the original graph. \textit{TCI} is composed of two stages: 1) initialization of clustering affiliations for unsampled nodes based on computed neighborhood affiliation information; 2) label propagation for the whole graph. Our experimental results demonstrate that the proposed \textit{TCI} method in conjunction with any considered cluster-preserving sampling strategy is capable of inferring the clustering affiliation of the population commendably, and it performs better than the competing methods.
Keywords: Graph Sampling, Clustering Structure, Population Inference, Representative Sample
@inproceedings{mlg2018_37,
title={Clustering Affiliation Inference from Graph Samples},
author={Jianpeng Zhang, Kaijie Zhu, Yulong Pei, George Fletcher and Mykola Pechenizkiy},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
What are they up to? Distilling the Twitter Stream of SubpopulationsPDF Ido Dangur, Ron Bekkerman and Einat Minkov
Abstract: Social network researchers have been tackling community detection / community search for over a decade. Detecting communities -- small groups of people who know each other and interact with each other -- have numerous applications, starting from marketing and computational advertisement, all the way to the homeland security domain. By now, the problem can be considered mostly solved, in either its unsupervised form (community detection) or semi-supervised form (community search). In our quest to answer general -- and very exciting -- questions \emph{What are people up to? What do they care about? What are they discussing?}, we move beyond detecting communities to circumscribing subpopulations -- large groups of people who share some common characteristics, for example activists, students, engineers, New Yorkers, football fans etc. We want to know what are $<\dots>$ talking about on Twitter, where $<\dots>$ is any subpopulation. Initially, the subpopulation is characterized by a few representative members, who are treated as seeds in the iterative Personalized PageRank (PPR) framework that enlarges the subpopulation at each iteration. We immediately hit the scalability limitation, which we overcome by proposing the Splash PPR algorithm, inspired by Splash Belief Propagation. We implement Splash PPR on Apache Spark and show its efficiency and effectiveness on extracting the Twitter stream of a subpopulation of machine learning practitioners, by which we pave the road to distilling valuable signal out of the sea of Twitter noise.
Keywords: Twitter, Subpopulations, Personalized PageRank, Big Data
@inproceedings{mlg2018_45,
title={What are they up to? Distilling the Twitter Stream of Subpopulations},
author={Ido Dangur, Ron Bekkerman and Einat Minkov},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
N-GCN: Multi-scale Graph Convolution for Semi-supervised Node ClassificationPDF Sami Abu-El-Haija, Amol Kapoor, Bryan Perozzi and Joonseok Lee
Abstract: Graph Convolutional Networks (GCNs) have shown significant improvements in semi-supervised learning on graph-structured data. Concurrently, unsupervised learning of graph embeddings has benefited from the information contained in random walks. In this paper, we propose a model: Network of GCNs (N-GCN), which marries these two lines of work. At its core, N-GCN trains multiple instances of GCNs over node pairs discovered at different distances in random walks, and learns a combination of the instance outputs which optimizes the classification objective. Our experiments show that our proposed N-GCN model improves state-of-the-art baselines on all of the challenging node classification tasks we consider: Cora, Citeseer, Pubmed, and PPI. In addition, our proposed method has other desirable properties, including generalization to recently proposed semi-supervised learning methods such as GraphSAGE, allowing us to propose N-SAGE, and resilience to adversarial input perturbations.
Keywords: Graph, Convolution, Spectral, Semi-Supervised Learning, Deep Learning
@inproceedings{mlg2018_49,
title={N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification},
author={Sami Abu-El-Haija, Amol Kapoor, Bryan Perozzi and Joonseok Lee},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Error-Bounded Graph Construction for Semi-supervised Manifold LearningPDF Christopher Symons
Abstract: Graphs are commonly used in semi-supervised learning to represent a manifold on which the data reside in a high-dimensional ambient space. The graph can then be utilized in different ways, typically via the Laplacian of the graph, in order to leverage associations among the unlabeled data to improve learning. One common way to leverage the graph Laplacian is as a regularization term, where models that would disagree with the graph are penalized. More often the spectrum of the graph Laplacian is used to find a lower dimensional embedding in which neighboring relations encoded via the graph are preserved. Most manifold-based methods of semi-supervised learning depend upon geometric structure in the ambient feature space in order to construct a graph whose edges encode similarity that should be useful in selecting a model. A critical assumption is that some standard measure of similarity applied to the ambient space can be used to construct a graph that is error-free or of low error, meaning that examples (i.e., vertices) from distinct classes are not connected. However, this assumption often precludes the use of such methods in noisy or complex feature spaces, even though such spaces often arise in problems that can most benefit from structure that might be uncovered within the unlabeled data. This paper presents a method of graph construction for manifold-based semi-supervised learning that respects the manifold assumptions underlying these methods and bounds the error on the graph itself, which then permits bounds on the overall generalization error of the learning algorithms without relying on assumptions that do not hold in many modern problem domains.
@inproceedings{mlg2018_51,
title={Error-Bounded Graph Construction for Semi-supervised Manifold Learning},
author={Christopher Symons},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
ROACH: Online Apprentice Critic Focused Crawling via CSS Cues and ReinforcementPDF Asitang Mishra, Chris Mattmann, Paul Ramirez and Wayne Burke
Abstract: The Internet today is replete with forum sites that - in the context of the deep/dark web - are used to sell illicit goods, and to deal in illegal activities including human trafficking (HT). Working on the DARPA MEMEX project, our team collaborated with law en- forcement to perform bulk analysis and crawl these sites and in doing so found a number of challenges. Forum sites contained pages with many links and little content and the ads - the rich source of content - were hidden behind link-dense hubs. To identify impor- tant links that led to ads, crawlers had to take advantage of CSS visual cues. As forum sites changed often, training a model offline would not be sufficient. We address these issues by creating ROACH, or Reinforcement-based, Online, Apprentice-Critic based focused crawling approacH. ROACH provides an online, adaptive crawling mechanism that employs static subject matter expert knowledge, with online learning based on a simplified version of reinforce- ment learning with back propagation. We use the widely popular apprentice-critic framework for performing this capability. ROACH is independent of any crawler implementation. The approach is scalable and accurate and overall provides better link relevancy scores than two baseline approaches including Apache Nutch. We evaluate ROACH on a dataset collected in the human trafficking domain from the DARPA MEMEX effort.
Keywords: Web Crawling, Graph-based Reinforcement Learning, Focused Crawling, Information Retrieval, Machine Learning
@inproceedings{mlg2018_54,
title={ROACH: Online Apprentice Critic Focused Crawling via CSS Cues and Reinforcement},
author={Asitang Mishra, Chris Mattmann, Paul Ramirez and Wayne Burke},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Social Relation Inference via Label PropagationPDF Yingtao Tian, Haochen Chen, Bryan Perozzi, Muhao Chen, Xiaofei Sun and Steven Skiena
Abstract: Collaboration networks are a ubiquitous way to characterize the
interactions between people. In this paper, we consider the problem
of inferring social relations in collaboration networks, such as the
fields that researchers collaborate in, or the categories of projects
that Github users work on together.
Social relation inference can be formalized as a multi-label classification
problem on graph edges, but many popular algorithms for
semi-supervised learning on graphs only operate on the nodes of a
graph. To bridge this gap, we propose a principled method which
leverages the natural homophily present in collaboration networks.
First, observing that the fields of collaboration for two people are
usually at the intersection of their interests, we transform an edge
labeling into node labels. Second, we use a label propagation algorithm
to propagate node labels in the entire graph. Once the label
distribution for all nodes has been obtained, we can easily infer the
label distribution for all edges. Experiments on three large-scale
collaboration networks demonstrate that our method outperforms
the state-of-the-art methods for social relation inference by a large
margin, in addition to running several orders of magnitude faster.
@inproceedings{mlg2018_58,
title={Social Relation Inference via Label Propagation},
author={Yingtao Tian, Haochen Chen, Bryan Perozzi, Muhao Chen, Xiaofei Sun and Steven Skiena},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Fusion Graph Convolutional NetworksPDF Priyesh Vijayan, Yash Chandak, Mitesh M. Khapra and Balaraman Ravindran
Abstract: State of the art methods for semi-supervised node classification in graphs uses differentiable functions to aggregate neighborhood information from multiple hops. Differentiable functions such as Graph Convolutional Networks (GCN) aggregate neighborhood information recursively over multiple hops and are learned end to end. These higher order propagation models primarily vary in their neighborhood aggregation functions as well as in their instantiation of weighted combinations of the node and its neighbors' information at each hop. However, these variants are limited in their ability to combine information from different hops efficiently. In this paper, we analyze this particular limitation with existing models that restrict them from performing well across datasets from different domains. Further, we provide a fusion component which is mathematically motivated to improve the existing models to learn the importance of information from different hops. This proposed mechanism is shown to improve over existing methods across 8 popular datasets from different domains. Specifically, our model improves the original Graph Convolutional Network (GCN) by a significant margin providing highly competitive state of the art results.
Keywords: Node classification, Semi-supervised learning, Social Networks, Collective classification, Data mining
@inproceedings{mlg2018_63,
title={Fusion Graph Convolutional Networks},
author={Priyesh Vijayan, Yash Chandak, Mitesh M. Khapra and Balaraman Ravindran},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Graphlets versus node2vec and struc2vec in the task of network alignmentPDF Shawn Gu and Tijana Milenkovic
Abstract: Network embedding aims to represent each node in a network
as a low-dimensional feature vector that summarizes the given
node’s (extended) network neighborhood. The nodes’ feature vectors
can then be used in various downstream machine learning
tasks. Recently, many embedding methods that automatically learn
the features of nodes have emerged, such as node2vec and struc2vec,
which have been used in tasks such as node classification, link prediction,
and node clustering, mainly in the social network domain.
There are also other embedding methods that explicitly look at
the connections between nodes, i.e., the nodes’ network neighborhoods,
such as graphlets. Graphlets have been used in many tasks
such as network comparison, link prediction, and network clustering,
mainly in the computational biology domain. Even though
the two types of embedding methods (node2vec/struct2vec versus
graphlets) have a similar goal – to represent nodes as features
vectors, no comparisons have been made between them, possibly
because they have originated in the different domains. Therefore,
in this study, we compare graphlets to node2vec and struc2vec,
and we do so in the task of network alignment. In evaluations on
synthetic and real-world biological networks, we find that graphlets
are both more accurate and faster than node2vec and struc2vec.
This work falls under the following submission types: “Novel research
paper” and “Appraisal paper of existing methods and tools”.
Keywords: social networks, biological networks, network embedding, graphlets, network alignment
@inproceedings{mlg2018_38,
title={Graphlets versus node2vec and struc2vec in the task of network alignment},
author={Shawn Gu and Tijana Milenkovic},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
SANE: Scalable Attribute-aware Network EmbeddingPDF Weiyi Liu, Zhining Liu, Toyotaro Suzumura and Guangmin Hu
Abstract: Network in the real world generally contains topological features and attribute features.
How to integrate features in the topological and attribute space simultaneously has gradually become one of the research focuses in network embedding.
In this position paper, we propose SANE: scalable attribute-aware network embedding.
The present preliminary results show that, by enforcing the alignment of a local linear relationship between each node and its K-nearest neighbors in topology and attribute space, SANE is more informative comparing with a single representation from topology or attributes alone.
@inproceedings{mlg2018_6,
title={SANE: Scalable Attribute-aware Network Embedding},
author={Weiyi Liu, Zhining Liu, Toyotaro Suzumura and Guangmin Hu},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Temporal graph-based clustering for historical record linkagePDF Charini Nanayakkara, Peter Christen and Thilina Ranbaduge
Abstract: Research in the social sciences is increasingly based on large and complex data collections, where individual data sets from different domains are linked and integrated to allow advanced analytics. A popular type of data used in such a context are historical censuses, as well as birth, death, and marriage certificates. Individually, such data sets however limit the types of studies that can be conducted. Specifically, it is impossible to track individuals, families, or households over time. Once such data sets are linked and family trees spanning several decades are available, it is possible to, for example, investigate how education, health, mobility, employment and social status influence each other and the life of people over two or even more generations. A major challenge is however the accurate linkage of historical data sets which is due to data quality and commonly also the lack of ground truth data being available. Unsupervised techniques need to be employed, which can be based on similarity graphs generated by comparing individual records. In this paper we present initial results from clustering birth records from Scotland where we aim to identify all births of the same mother and group siblings into clusters. We extend existing clustering techniques for record linkage by incorporating temporal constraints that must hold between births of the same mother, and explore novel temporal clustering ideas. Experimental results show improvements over non-temporary approaches, however further work is needed to obtain links of high quality.
Keywords: Entity resolution, Birth records, Scottish, Star clustering
@inproceedings{mlg2018_14,
title={Temporal graph-based clustering for historical record linkage},
author={Charini Nanayakkara, Peter Christen and Thilina Ranbaduge},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
HGsuspector: Scalable Collective Fraud Detection in Heterogeneous GraphsPDF Xiang Li, Wen Zhang, Jiuzhou Xi and Hao Zhu
Abstract: Heterogeneous graphs have drawn more and more attention in both research and engineering, such as Amazon's who-buys-what graph, Facebook's who-likes-page graph, opinion graphs and etc. Present work of fraud detection on heterogeneous graphs is either on bipartite graphs or heterogeneous graphs with a handful of node and edge types. For a common heterogeneous graph, it is not easy to detect suspicious subgraphs directly, while fraud detection of bipartite graphs with metric is accurate and fast. What if handle heterogeneous graphs by utilizing the advantages of bipartite graphs?
Here we propose HGsuspector, a novel, simple and scalable algorithm for detecting collective fraud in directed heterogeneous graphs. At first, we decompose directed heterogeneous graphs into a set of bipartite graphs, then for each bipartite graphs we define a metric on each connected bipartite graph and calculate scores on it. Finally, we obtain corresponding suspicious subgraphs with anomaly detection algorithms.
We demonstrate the effectiveness and competitive performance of HGsuspector in experiments on real-world datasets, which indicates that HGsuspector could detect the suspicious subgraphs both accurately and fast on large graphs with billion nodes and edges, and it outperforms other state-of-the-art algorithms.
Keywords: Bipartite Graph, Heterogeneous Graph, Connected Bipartite Subgraph, Edge Density Function
@inproceedings{mlg2018_16,
title={HGsuspector: Scalable Collective Fraud Detection in Heterogeneous Graphs},
author={Xiang Li, Wen Zhang, Jiuzhou Xi and Hao Zhu},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
A New Algorithmic Model for Graph Analysis of Streaming DataPDF Chunxing Yin, Jason Riedy, and David A. Bader
Abstract: The constant and massive influx of new data into analysis systems needs to be addressed without assuming we can pause the onslaught. Here we consider one aspect: non-stop graph analysis of streaming data. We formalize a new and practical algorithm model that includes both single-run analysis as well as efficiently updating analysis results only around changed data. In our model, a massive graph undergoes changes from an input stream of edge insertions and removals. These changes occur concurrently with analysis. Algorithms do not pause or stop the input stream. Assuming basic data access safety, we consider an algorithm valid for our model if the output is correct for a graph consisting of the initial graph and some implicit subset of concurrent changes.
Our technical contributions include 1) the first formal model for graph analysis with concurrent changes, 2) properties of the model including how our model is the strongest possible without point-in-time graph views, 3) demonstrations of our model on connected components and PageRank, and 4) an extension to updating computed results incrementally.
Keywords: graph analysis, streaming data, high-performance data analysis
@inproceedings{mlg2018_23,
title={A New Algorithmic Model for Graph Analysis of Streaming Data},
author={Chunxing Yin, Jason Riedy, and David A. Bader},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Temporal Analysis of Reddit Networks via Role EmbeddingsPDF Siobhán Grayson and Derek Greene
Abstract: Inspired by diachronic word analysis from the field of natural language processing, we propose an approach for uncovering temporal insights regarding user roles from social networks using graph embedding methods. Specifically, we apply the role embedding algorithm, struc2vec, to a collection of social networks exhibiting either "loyal" or "vagrant" characteristics, derived from the popular online social news aggregation website Reddit. For each subreddit, we extract nine months of data and create network role embeddings on consecutive time windows. We are then able to compare and contrast how user roles change over time by aligning the resulting temporal embeddings spaces. In particular, this is a 'work-in-progress paper' where we analyze temporal role embeddings, from both an individual and community-level perspective, for both loyal and vagrant user communities present on Reddit.
Keywords: temporal role analysis, graph embeddings, social network analysis
@inproceedings{mlg2018_43,
title={Temporal Analysis of Reddit Networks via Role Embeddings},
author={Siobhán Grayson and Derek Greene},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Temporal Motifs in Heterogeneous Information NetworksPDF Yuchen Li, Zhengzhi Lou, Yu Shi and Jiawei Han
Abstract: Network motifs are crucial building blocks of understanding and modeling complex networks for its capacity in characterizing higher-order interactions. Meanwhile, heterogeneous information networks (HINs) are ubiquitous in real-world applications, which often come with rich temporal information. We are hence motivated to study temporal motifs in the context of heterogeneous information networks. With examples from real-world datasets, we demonstrate HIN motifs can be armed with substantially more discriminability by incorporating temporal information. Furthermore, counting temporal HIN motif instances in large-scale networks is time consuming. We therefore develop efficient counting algorithm for the HIN motifs that are of the most interests in the literature. Empirical observations in the experiment showed that interesting motif instances can be identified from large-scale HINs thanks to the improved discriminability of temporal HIN motifs, and the proposed efficient counting algorithm enjoys linear complexity that is multiple orders of magnitude faster than the baseline method in four real-world HINs.
Keywords: heterogeneous information networks, network motifs, algorithms, graph mining
@inproceedings{mlg2018_46,
title={Temporal Motifs in Heterogeneous Information Networks},
author={Yuchen Li, Zhengzhi Lou, Yu Shi and Jiawei Han},
booktitle={Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)},
year={2018}
}
Call for Papers
This workshop is a forum for exchanging ideas and methods for mining and learning with graphs, developing new common understandings of the problems at hand, sharing of data sets where applicable, and leveraging existing knowledge from different disciplines. The goal is to bring together researchers from academia, industry, and government, to create a forum for discussing recent advances graph analysis. In doing so, we aim to better understand the overarching principles and the limitations of our current methods and to inspire research on new algorithms and techniques for mining and learning with graphs.
To reflect the broad scope of work on mining and learning with graphs, we encourage submissions that span the spectrum from theoretical analysis to algorithms and implementation, to applications and empirical studies. As an example, the growth of user-generated content on blogs, microblogs, discussion forums, product reviews, etc., has given rise to a host of new opportunities for graph mining in the analysis of social media. We encourage submissions on theory, methods, and applications focusing on a broad range of graph-based approaches in various domains.
Topics of interest include, but are not limited to:
Theoretical aspects:
Computational or statistical learning theory related to graphs
Theoretical analysis of graph algorithms or models
Sampling and evaluation issues in graph algorithms
Analysis of dynamic graphs
Algorithms and methods:
Graph mining
Probabilistic and graphical models for structured data
Heterogeneous/multi-model graph analysis
Network embedding models
Statistical models of graph structure
Combinatorial graph methods
Semi-supervised learning, active learning, transductive inference, and transfer learning in the context of graph
Applications and analysis:
Analysis of social media
Analysis of biological networks
Knowledge graph construction
Large-scale analysis and modeling
We welcome many kinds of papers, such as, but not limited to:
Novel research papers
Demo papers
Work-in-progress papers
Visionary papers (white papers)
Appraisal papers of existing methods and tools (e.g., lessons learned)
Relevant work that has been previously published
Work that will be presented at the main conference
Authors should clearly indicate in their abstracts the kinds of submissions that the papers belong to, to help reviewers better understand their contributions.
All papers will be peer reviewed, single-blinded.
Submissions must be in PDF, no more than 8 pages long — shorter papers are welcome — and formatted according to the standard double-column ACM Proceedings Style.
The accepted papers will be published on the workshop’s website and will not be considered archival for resubmission purposes.
Authors whose papers are accepted to the workshop will have the opportunity to participate in a spotlight and poster session, and some set will also be chosen for oral presentation, and considered for $1,000 best paper award sponsored by Google and Kyndi.
To receive updates about the current and future workshops and the Graph Mining community, please join the Mailing List, or follow the Twitter Account.
Important Dates
Paper Submission Open:April 1, 2018
Paper Abstract Deadline:May 8, 2018
Paper Submission Deadline:May 15, 2018
Author Notification:June 8, 2018
Camera Ready:June 28, 2018
Workshop: August 20, 2018
Workshop Organizers
Shobeir Fakhraei
Research Scientist University of Southern California (ISI)
Danai Koutra
Assistant Professor University of Michigan Ann Arbor
Julian McAuley
Assistant Professor University of California San Diego
Bryan Perozzi
Research Scientist Google Research
Tim Weninger
Assistant Professor University of Notre Dame
Program Committee
Aris Anagnostopoulos (Sapienza University of Rome)
Ana Paula Appel (I.B.M.)
Miguel Araujo (Feedzai)
Arindam Banerjee (University of Minnesota)
Christian Bauckhage (Fraunhofer IAIS)
Ulf Brefeld (Leuphana Universität Lüneburg)
Ivan Brugere (University of Illinois at Chicago)
Aaron Clauset (University of Colorado at Boulder)
Alessandro Epasto (Google)
Emilio Ferrara (University of Southern California)
Thomas Gärtner (University of Nottingham)
David Gleich (Purdue University)
Mohammad Hasan (Indiana U.–Purdue U. Indianapolis)
Jake Hofman (Microsoft Research)
Larry Holder (Washington State University)
Bert Huang (Virginia Tech)
Kristian Kersting (TU Darmstadt)
Stefano Leucci (ETH Zurich)
Fred Morstatter (University of Southern California)
Vagelis Papalexakis (University of California Riverside)
Ali Pinar (Sandia National Laboratories)
Aditya Prakash (Virginia Tech)
Arti Ramesh (Binghamton University)
Jan Ramon (INRIA)
Xiang Ren (University of Southern California)
Neil Shah (Snap Inc.)
Sucheta Soundarajan (Syracuse University)
Yizhou Sun (University of California, Los Angeles)
Acar Tamersoy (Symantec Research Labs)
Jiliang Tang (Michigan State University)
Hanghang Tong (Arizona State University)
Stefan Wrobel (Fraunhofer IAIS)
Xin-Zeng Wu (Information Sciences Institute)
Zhongfei Zhang (Binghamton University)
Elena Zheleva (University of Illinois at Chicago)
