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, 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.
Keynote: Nitesh Chawla Representing, Modeling, and Visualizing Higher Order Networks
9:40 am
Paper Spotlights 1
10:00 am
Coffee Break
10:30 am
Paper Spotlights 2
10:50 am
Keynote: Vahab Mirrokni Distributed Graph Mining: Theory and Practice
11:30 am
Poster Session
12:00 pm
Lunch (+ Poster Session)
Afternoon Sessions
1:00 pm
Keynote: Elena Zheleva Sharing and Gifting Online
1:40 pm
Contributed Talks 1:
- HARP: Hierarchical Representation Learning for Networks (Bryan Perozzi)
- Neural Embeddings of Graphs in Hyperbolic Space (Ben Chamberlain)
2:00 pm
Keynote: Yan Liu Robust Diffusion Network Inference
2:40 pm
Contributed Talks 2:
- A/B Testing in Networks with Adversarial Members (Kaleigh Clary)
- A task-driven approach to time scale detection in dynamic networks (Benjamin Fish)
3:00 pm
Coffee Break
3:30 pm
Keynote: Jiliang Tang Node Relevance in Signed Networks: Measurements and Applications
4:10 pm
Keynote: Zhenhui Jessie Li Mining Mobility Flow for Urban Computing
4:50 pm
Closing Remarks
Keynote Speakers
Nitesh Chawla
Professor University of Notre Dame
Zhenhui Jessie Li
Associate Professor Pennsylvania State University
Yan Liu
Associate Professor University of Southern California
Vahab Mirrokni
Principal Scientist & Research Director Google Research
Jiliang Tang
Assistant Professor Michigan State University
Elena Zheleva
Assistant Professor University of Illinois at Chicago
Accepted Papers
HARP: Hierarchical Representation Learning for NetworksPDF Haochen Chen, Bryan Perozzi, Yifan Hu and Steven Skiena
Abstract: We present HARP, a novel method for learning low dimensional embeddings of a graph's nodes which preserves higher-order structural features. Our proposed method achieves this by compressing the input graph prior to embedding it, effectively avoiding troublesome embedding configurations (i.e. local minima) which can pose problems to non-convex optimization.
HARP works by finding a smaller graph which approximates the global structure of its input. This simplified graph is used to learn a set of initial representations, which serve as good initializations for learning representations in the original, detailed graph. We inductively extend this idea, by decomposing a graph in a series of levels, and then embed the hierarchy of graphs from the coarsest one to the original graph.
HARP is a general meta-strategy to improve all of the state-of-the-art neural algorithms for embedding graphs, including DeepWalk, LINE, and Node2vec. Indeed, we demonstrate that applying HARP's hierarchical paradigm yields improved implementations for all three of these methods, as evaluated on both classification tasks on real-world graphs such as DBLP, BlogCatalog, CiteSeer, and Arxiv, where we achieve a performance gain over the original implementations by up to 14% Macro F1.
@inproceedings{mlg2017_10,
title={HARP: Hierarchical Representation Learning for Networks},
author={Haochen Chen, Bryan Perozzi, Yifan Hu and Steven Skiena},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Neural Embeddings of Graphs in Hyperbolic SpacePDF Ben Chamberlain, Marc Deisenroth and James Clough
Abstract: Neural embeddings have been used with great success in Natural Language Processing (NLP). They provide compact representations that encapsulate word similarity and attain state-of-the-art performance in a range of linguistic tasks. The success of neural embeddings has prompted significant amounts of research into applications in domains other than language. One such domain is graph-structured data, where embeddings of vertices can be learned that encapsulate vertex similarity and improve performance on tasks including edge prediction and vertex labelling. For both NLP and graph based tasks, embeddings have been learned in high-dimensional Euclidean spaces.
However, recent work has shown that the appropriate isometric space for embedding complex networks is not the flat Euclidean space, but negatively curved, hyperbolic space. We present a new concept that exploits these recent insights and propose learning neural embeddings of graphs in hyperbolic space. We provide experimental evidence that embedding graphs in their natural geometry significantly improves performance on downstream tasks for several real-world public datasets.
@inproceedings{mlg2017_6,
title={Neural Embeddings of Graphs in Hyperbolic Space},
author={Ben Chamberlain, Marc Deisenroth and James Clough},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
A/B Testing in Networks with Adversarial MembersPDF Kaleigh Clary and David Jensen
Abstract: Many researchers attempt to study the effects of interventions in network systems. To simplify experimental design and analysis in these environments, simple assumptions are made about the behavior of its members. However, nodes may not respond to treatment, or may respond maliciously. These adversarial nodes influence treatment topology by preventing or altering the expected network effect, but may not be known or detectable. We characterize the influence of adversarial nodes and the bias these nodes introduce in average treatment effect estimates.
In particular, we derive expressions for the bias induced in average treatment effect using the linear estimator from Gui et al (2015). In addition to theoretical bounds, we empirically demonstrate estimation bias through experiments on synthetically generated networks. We consider both the case in which adversarial nodes are dispersed randomly through the network and the case where adversarial node placement is targeted to the highest degree nodes. Our work demonstrates that peer influence makes causal estimates on networks susceptible to the actions of adversaries, and specific network structures are particularly vulnerable to to adversarial responses.
Keywords: causal effect estimation, relational data, social networks, adversarial analysis
@inproceedings{mlg2017_27,
title={A/B Testing in Networks with Adversarial Members},
author={Kaleigh Clary and David Jensen},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
A task-driven approach to time scale detection in dynamic networksPDF Benjamin Fish and Rajmonda S. Caceres
Abstract: For any stream of time-stamped edges that form a dynamic network, an important choice is the aggregation granularity that an analyst uses to bin the data. Picking such a windowing of the data is often done by hand, or left up to the technology that is collecting the data. However, the choice can make a big difference in the properties of the dynamic network. Finding a good windowing is the time scale detection problem. In previous work, this problem is often solved with an unsupervised heuristic. As an unsupervised problem, it is difficult to measure how well a given windowing algorithm performs.
In addition, we show that there is little correlation between the quality of a windowing across different tasks. Therefore the time scale detection problem should not be handled independently from the rest of the analysis of the network.
Given this, in accordance with standard supervised machine learning practices, we introduce new windowing algorithms that automatically adapt to the task the analyst wants to perform by treating windowing as a hyperparameter for the task, rather than using heuristics. This approach measures the quality of the windowing by how well a given task is accomplished on the resulting network. This also allows us, for the first time, to directly compare different windowing algorithms to each other, by comparing how well the task is accomplished using that windowing algorithm. We compare this approach to previous approaches and several baselines on real data.
Keywords: dynamic networks, time scale detection, supervised learning
@inproceedings{mlg2017_17,
title={A task-driven approach to time scale detection in dynamic networks},
author={Benjamin Fish and Rajmonda S. Caceres},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
A Temporal Tree Decomposition for Generating Temporal GraphsPDF Corey Pennycuff and Tim Weninger
Abstract: Discovering the underlying structures present in large real world graphs is a fundamental scientific problem. Recent work at the intersection of formal language theory and graph theory has found that a Hyperedge Replacement Grammar (HRG) can be extracted from a tree decomposition of any graph. This HRG can be used to generate new graphs that share properties that are similar to the original graph. Because the extracted HRG is directly dependent on the shape and contents of the of tree decomposition, it is unlikely that informative graph-processes are actually being captured with the extraction algorithm. To address this problem, the current work presents a new extraction algorithm called temporal HRG (tHRG) that learns HRG production rules from a temporal tree decomposition of the graph. We observe problems with the assumptions that are made in a temporal HRG model. In experiments on large real world networks, we show and provide reasoning as to why tHRG does not perform as well as HRG and other graph generators.
@inproceedings{mlg2017_7,
title={A Temporal Tree Decomposition for Generating Temporal Graphs},
author={Corey Pennycuff and Tim Weninger},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Star sampling with and without replacementPDF Jonathan Stokes and Steven Weber
Abstract: Star sampling (SS) is a graph search mechanism wherein each sample consists of a vertex (the star center) and its one-hop neighbors (the star points). We consider the use of star sampling to find any vertex in a specified target set in a large graph, where the figure of merit is the expected number of samples until a vertex in the target set is encountered, either as a star center or as a star point. We analyze this performance measure on three related star sampling paradigms: SS with replacement (SS-R), SS without center replacement (SS-C), and SS without star replacement (SS-S). Exact expressions for the average number of samples under SS-R and SS-C are easily obtained. Much of the paper is focused on deriving an approximate expression for the performance of SS-S. Experiments are run on both "synthetic" graphs, i.e., Erdos-Renyi (ER) graphs, as well as three "real-world" graphs. The two contributions of the paper are: i) the analytical approximation for SS-S is seen to be quite accurate for both types of graphs, ii) we observe, perhaps surprisingly, there is little performance difference across the three sampling paradigms. This performance insensitivity of SS-R relative to SS-S may be understood as the result of two competing factors: removing stars reduces the number of vertices outside the target set, but also removes the number of neighbors of the target set.
Keywords: star sampling, graph search, graph sampling, performance analysis
@inproceedings{mlg2017_8,
title={Star sampling with and without replacement},
author={Jonathan Stokes and Steven Weber},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Fast Algorithms for Learning Latent Variables in Graphical ModelsPDF Mohammadreza Soltani and Chinmay Hegde
Abstract: We study the problem of learning latent variables in Gaussian graphical
models. Existing methods for this problem assume that the
precision matrix of the observed variables is the superposition of a
sparse and a low-rank component. In this paper, we focus on the
estimation of the low-rank component, which encodes the effect of
marginalization over the latent variables. We introduce fast, proper
learning algorithms for this problem. In contrast with existing approaches,
our algorithms are manifestly non-convex. We support
their efficacy via a rigorous theoretical analysis, and show that our
algorithms match the best possible in terms of sample complexity,
while achieving computational speed-ups over existing methods.
We complement our theory with several numerical experiments.
Keywords: Latent variables, Fast Algorithm, Nonconvex Algorithm, Probabilistic Graphical Models
@inproceedings{mlg2017_12,
title={Fast Algorithms for Learning Latent Variables in Graphical Models},
author={Mohammadreza Soltani and Chinmay Hegde},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Parallel Graph Summarization for Knowledge SearchPDF Qi Song, Mohammad Hossein Namaki, Peng Lin and Yinghui Wu
Abstract: Querying heterogeneous and large-scale knowledge graphs are typically expensive. This paper studies a parallel graph summarization framework to facilitate knowledge graph search. (1) We propose a class of reduced summaries characterized by graph patterns, which are capable of summarizing entities in terms of their neighborhood similarity up to a certain hop. (2) We study a bi-criteria diversified summarization problem. Given a knowledge graph G, it is to discover top-k diversified reduced summaries with maximized quality in terms of both informativeness and diversity. (3) We show that diversified summarization is feasible for large knowledge graphs, by developing a parallel approximation algorithm with quality guarantees. We show that the algorithm is parallel scalable, which ensures the feasibility of summarization in large graphs. Using real-world graphs, we experimentally verify the efficiency of our parallel summarization algorithms, and query evaluation guided by summarization.
@inproceedings{mlg2017_16,
title={Parallel Graph Summarization for Knowledge Search},
author={Qi Song, Mohammad Hossein Namaki, Peng Lin and Yinghui Wu},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
GraphZip: Mining Graph Streams using Dictionary-based CompressionPDF Charles Packer and Larry Holder
Abstract: A massive amount of data generated today on platforms such as
social networks, telecommunication networks, and the internet
in general can be represented as graph streams. Activity in a network’s
underlying graph generates a sequence of edges in the form
of a stream; for example, a social network may generate a graph
stream based on the interactions (edges) between different users
(nodes) over time. While many graph mining algorithms have already
been developed for analyzing relatively small graphs, graphs
that begin to approach the size of real-world networks stress the
limitations of such methods due to their dynamic nature and the
substantial number of nodes and connections involved.
In this paper we present GraphZip, a scalable method for mining
interesting patterns in graph streams. GraphZip is inspired by
the Lempel-Ziv (LZ) class of compression algorithms, and uses a
novel dictionary-based compression approach to discover maximally-compressing
patterns in a graph stream. We experimentally show
that GraphZip is able to retrieve both complex and insightful patterns
from large real-world graphs and artificially-generated graphs
with predefined (i.e., ground truth) patterns. Additionally, our results
demonstrate that GraphZip is both highly efficient and highly
effective compared to existing state-of-the-art methods for mining
graph streams.
Keywords: Graph mining, Compression, Streaming data
@inproceedings{mlg2017_18,
title={GraphZip: Mining Graph Streams using Dictionary-based Compression},
author={Charles Packer and Larry Holder},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Matrix Factorization with Side and Higher Order InformationPDF Vatsal Shah, Nikhil Rao and Weicong Ding
Abstract: The problem of predicting unobserved entries of a partially observed matrix has found wide applicability in several areas, such as recommender systems, computational biology, and computer vision. Many scalable methods with rigorous theoretical guarantees have been developed for algorithms where the matrix is factored into low-rank components, and embeddings are learned for the row and column variables. While there has been recent research on incorporating explicit side information in the low-rank matrix factorization setting, often implicit information can be gleaned from the data, via higher order interactions among variables. In this paper, we design a method to make use of this implicit information, via random walks on graphs. We show that the problem we intend to solve can be cast as factoring a nonlinear transform of the (partially) observed matrix and develop an efficient coordinate descent based algorithm for the same. Experiments on several datasets show that the method we propose outperforms vanilla matrix factorization, and also those methods that use explicitly available side information.
@inproceedings{mlg2017_19,
title={Matrix Factorization with Side and Higher Order Information},
author={Vatsal Shah, Nikhil Rao and Weicong Ding},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
graph2vec: Learning Distributed Representations of GraphsPDF Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu and Shantanu Jaiswal
Abstract: Recent works on representation learning for graph structured
data predominantly focus on learning distributed representations
of graph substructures such as nodes and subgraphs.
However, many graph analytics tasks such as
graph classification and clustering require representing entire
graphs as fixed length feature vectors. While the aforementioned
approaches are naturally unequipped to learn
such representations, graph kernels remain as the most effective
way of obtaining them. However, these graph kernels
use handcrafted features (e.g., shortest paths, graphlets,
etc.) and hence are hampered by problems such as poor
generalization. To address this limitation, in this work, we
propose a neural embedding framework named graph2vec
to learn data-driven distributed representations of arbitrary
sized graphs. graph2vec’s embeddings are learnt in an unsupervised
manner and are task agnostic. Hence, they could
be used for any downstream task such as graph classification,
clustering and even seeding supervised representation learning
approaches. Our experiments on several benchmark and
large real-world datasets show that graph2vec achieves significant
improvements in classification and clustering accuracies
over substructure representation learning approaches
and are competitive with state-of-the-art graph kernels.
Keywords: Representation Learning, Deep Learning, Graph Kernels, Neural Embedding
@inproceedings{mlg2017_21,
title={graph2vec: Learning Distributed Representations of Graphs},
author={Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu and Shantanu Jaiswal},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Graphs for Malware Detection: The Next FrontierPDF Abhishek Sharma and B. Aditya Prakash
Abstract: Machine Learning based approaches for malware detection have achieved a certain level of maturity as product offerings by Cybersecurity companies. VirusTotal recently included X by Invincea and MalwareScore by Endgame as signature-less anti-virus scanners. In this position paper, we argue that the significant challenges related to information heterogeneity, noisy and uncertain inputs, and the demand (from cybersecurity professionals) to generalize beyond per-sample prediction are impeding further advancement in this field. These challenges cannot be addressed by standard supervised machine learning approaches. We highlight the fact that the current applications of machine learning for cybersecurity have focused on feature based learning and largely ignored identifying and learning from the underlying relationships between malware samples. Malware graphs are the obvious abstractions for representing such relationships. We briefly discuss potential approaches and outline further research that is needed to build high-impact deployable cybersecurity solutions based on malware graphs.
@inproceedings{mlg2017_23,
title={Graphs for Malware Detection: The Next Frontier},
author={Abhishek Sharma and B. Aditya Prakash},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Location-based Event Detection Using Geotagged Semantic GraphsPDF Yifang Wei and Lisa Singh
Abstract: Event detection using Twitter has attracted a significant amount of research attention. While the emphasis of the related literature has been on detecting events without considering geography information, this work regards an event as something occurring at a particular location and time. We take a system perspective, focusing on the process of event detection using a framework that highlights different steps needed for identifying events in this noisy domain. We also propose an algorithm which leverages geotagged bursty term graphs to detect events from a tweet stream. Evaluating our approach on three large tweet streams from three different domains shows our approach significantly improves the detection precision and recall when compared to the state of the art approaches. In general, we find that simple modifications to existing algorithms improves location-based event detection across methods.
Keywords: Social Media, Text Event Detection, Location-based Graph Mining
@inproceedings{mlg2017_24,
title={Location-based Event Detection Using Geotagged Semantic Graphs},
author={Yifang Wei and Lisa Singh},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Compressive Sampling for Sparse Recovery in NetworksPDF Elahe Ghalebi K., Hamidreza Mahyar, Radu Grosu and Hamid R. Rabiee
Abstract: This paper introduces CS-SRN, a general framework for recovering sparse vectors representing specific features of nodes/links in networks. We use compressive sampling (CS) to construct a feasible measurement matrix under network topological constraints which is motivated by network inference. CS-SRN addresses the problem of monitoring the network internal characteristics using indirect end-to-end (aggregated) measurements. We evaluate the performance of the proposed method by extensive simulations on both synthetic and real-world networks under several configurations. The experimental results indicate that this framework outperforms the state-of-the-art compressive sensing-based method and can be employed to efficiently and accurately infer a wide range of networks.
@inproceedings{mlg2017_29,
title={Compressive Sampling for Sparse Recovery in Networks},
author={Elahe Ghalebi K., Hamidreza Mahyar, Radu Grosu and Hamid R. Rabiee},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Fraud Detection using Graph Topology and Temporal SpikesPDF Shenghua Liu, Bryan Hooi and Christos Faloutsos
Abstract: Fraud detection is facing more challenges when online fraudsters invest more resources, including purchasing large pools of fake user accounts and dedicated IPs, to make their attacks less obvious. Existing approaches such as average degree maximization in adjacency matrices or tensors, that aimed at finding the connections of maximum average degree density suffer from the bias of including more false positive nodes, resulting in lower accuracy and increased need for manual verification. Therefore, we propose HoloScope method to detect topology and spike suspiciousness simultaneously. A novel "contrast suspiciousness" is introduced for honoring contrast behaviors between fraudsters and normal users. In terms of graph topology, it allows us to more accurately detect fraudulent blocks, reducing the false positive nodes; In terms of temporal spikes, HoloScope takes into account the bursts caused by fraudsters' attacking, and the sudden drops due to the poor attractiveness of fake objects. In addition, we provide theoretical bounds for how much this increases the time cost needed for fraudsters to conduct adversarial attacks. Additionally, from the perspective of ratings, HoloScope incorporates the deviation of rating scores in order to catch fraudsters more accurately. Moreover, the HoloScope has a concise framework and sub-quadratic time complexity, which make our algorithm reproducible and scalable. In the experiments, HoloScope achieved significant accuracy improvements on both synthetic and real data, compared with the state-of-the-art baselines.
@inproceedings{mlg2017_3,
title={Fraud Detection using Graph Topology and Temporal Spikes},
author={Shenghua Liu, Bryan Hooi and Christos Faloutsos},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Adaptive Candidate Generation for Scalable Edge-discovery Tasks on Data GraphsPDF Mayank Kejriwal
Abstract: Several 'edge-discovery' applications over graph-based data models are known to have worst-case quadratic time complexity in the nodes, even if the discovered edges are sparse. One example is the generic link discovery problem between two graphs, which has invited research interest in several communities. Specific versions of this problem include link prediction in social networks, ontology alignment between metadata-rich RDF data, approximate joins, and entity resolution between instance-rich data. As large datasets continue to proliferate, reducing quadratic complexity to make the task practical is an important research problem. Within the entity resolution community, the problem is commonly referred to as blocking. A particular class of learnable blocking schemes is known as Disjunctive Normal Form (DNF) blocking schemes, and has emerged as state-of-the art for homogeneous (i.e. same-schema) tabular data. Despite the promise of these schemes, a formalism or learning framework has not been developed for them when input data instances are generic, attributed graphs possessing both node and edge heterogeneity. With such a development, the complexity-reducing scope of DNF schemes becomes applicable to a variety of problems, including entity resolution and type alignment between heterogeneous graphs, and link prediction in networks represented as attributed graphs. This paper presents a graph-theoretic formalism for DNF schemes, and investigates their learnability in an optimization framework. We also briefly describe an empirical case study encapsulating some of the principles in this paper.
Keywords: Candidate Generation, Blocking, Heterogeneity, Link Discovery, DNF Schemes, Data Graphs
@inproceedings{mlg2017_14,
title={Adaptive Candidate Generation for Scalable Edge-discovery Tasks on Data Graphs},
author={Mayank Kejriwal},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Cluster Hire in a Network of ExpertsPDF Meet Patel and Mehdi Kargar
Abstract: Finding a group of experts is a natural way to perform a collection of tasks that needs a set of diversified skills. This can be done by assigning skills to different experts with complementary expertise. This allows organizations and big institutes to efficiently hire a group of experts with different skill sets to deliver a series of required tasks in order to finish a set of projects. We are given a collection of projects, in which each of them needs a set of required skills. Performing each project brings a profit to the organization. We are also given a set of experts, each of them are equipped with a set of skills. In order to hire an expert, the organization should provide her monetary cost (i.e., salary). Furthermore, we are given a certain amount of budget to hire experts. The goal is to hire a group of experts within the given budget to perform a subset of projects that maximizes the total profit. This problem is called Cluster Hire and was introduced recently. In this paper, we extend this problem by making the realistic assumption that there exist an underlying network among experts. This network is built based on past collaboration among experts. If two experts have past collaboration, they form a more collaborative and efficient team in the future. In addition of maximizing the total profit, we are also interested to find the most collaborative group of experts by minimizing the communication cost between them. We propose two greedy algorithms with different strategies to solve this problem. Extensive experiments on real dataset show our proposed algorithms are able to find a group of experts that cover projects with high profit while experts are able to communicate with each other efficiently.
Keywords: Cluster Hire, Team Formation, Social Network
@inproceedings{mlg2017_22,
title={Cluster Hire in a Network of Experts},
author={Meet Patel and Mehdi Kargar},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
On Generalizing Neural Node Embedding Methods to Multi-Network ProblemsPDF Mark Heimann and Danai Koutra
Abstract: Representation learning has attracted significant interest in the community and has been shown to be successful in tasks involving one graph, such as link prediction and node classification. In this paper, we conduct an empirical study of two leading deep learning based node embedding methods, node2vec and SDNE, to examine their suitability for problems that involve multiple graphs.Although the embeddings have been shown to preserve properties necessary for the success of graph mining tasks on a single graph,we find that different runs of the same algorithm even on the same graph yield different embeddings. For node embedding methods to apply to multi-graph problems, we note that this finding motivates additional work in learning how to embed different graphs similarly.
@inproceedings{mlg2017_26,
title={On Generalizing Neural Node Embedding Methods to Multi-Network Problems},
author={Mark Heimann and Danai Koutra},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
DeepInfer: Diffusion Network Inference through Representation LearningPDF Zekarias Kefato, Nasrullah Sheikh and Alberto Montresor
Abstract: The diffusion of a contagion (e.g. news, meme, virus) is a common event in (online and offline) social networks. Unfortunately, such networks, known as diffusion networks, are often unknown: that is, one can observe when subjects are infected by a given contagion (e.g., when a piece of information arrives, when a product is adopted, when a virus is caught), but does not know through which connection the infection has been transmitted. The goal of this study is to infer such networks based on nodes infection contexts associated to diffusion events (cascades). Previous studies mostly relied on delay patterns between infection events of nodes to infer edges. It has been argued, however, that delay-agnostic approaches are also efficient for such inference. Motivated by this finding, we present a novel delay-agnostic algorithm that is largely inspired by representation learning of words in documents and nodes in networks. Moreover, unlike some delay-agnostic methods, we only consider infection context of nodes in a restricted window. After empirically observing a similarity between the distribution of words in documents and nodes in cascades, we employ the Skip-Gram model to learn a representation of nodes from cascades. The learned representation is then used to compute the probability that an edge exists between a pair of nodes. Through extensive experiments we validate the effectiveness of our algorithm, showing that it is able to recover up to ~95% of the hidden network in realistic datasets. We have also compared our algorithm to the state-of-the-art algorithm InfoPath, and achieved a large improvement on the quality of results.
@inproceedings{mlg2017_5,
title={DeepInfer: Diffusion Network Inference through Representation Learning},
author={Zekarias Kefato, Nasrullah Sheikh and Alberto Montresor},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Exploiting Gaussian Embeddings for Directed Link PredictionPDF Inzamam Rahaman and Patrick Hosein
Abstract: Many systems can be represented as graphs where nodes represent components or actors in the system and edges represent interactions between said components and actors. Link Prediction refers to the task of using the current graphical representation of a system to to suggest which interactions might not be captured by the system or which interactions might occur in the future. In this position paper, we present preliminary results on the usage of Gaussian embeddings of nodes for the task of link prediction in directed graphs.
Keywords: Learning latent representations, Dimensionality reduction and manifold learning, Classification, Link Prediction
@inproceedings{mlg2017_9,
title={Exploiting Gaussian Embeddings for Directed Link Prediction},
author={Inzamam Rahaman and Patrick Hosein},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric EnsemblesPDF Giona Casiraghi, Vahan Nanumyan, Ingo Scholtes and Frank Schweitzer
Abstract: The inference of network topologies from relational data is an important problem.
Exemplary applications include the reconstruction of social ties from data on human interactions, the inference of gene co-expression networks from DNA microarray data, or the learning of semantic relationships based on co-occurrences of words in documents.
Solving these problems requires techniques to infer significant links in noisy relational data.
In this position paper, we propose a new statistical modeling framework to address this challenge.
It builds on generalized hypergeometric ensembles, a class of generative stochastic models that give rise to analytically tractable probability spaces of directed, multi-edge graphs.
We show how this framework can be used to assess the significance of links in noisy relational data.
We illustrate our method in two data sets capturing spatio-temporal proximity relations between actors in a social system.
The results show that our theoretical framework provides a new approach to infer significant links from relational data, with interesting perspectives for mining and learning in graphs.
@inproceedings{mlg2017_11,
title={From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles},
author={Giona Casiraghi, Vahan Nanumyan, Ingo Scholtes and Frank Schweitzer},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Evaluating Social Networks Using Task-Focused Network InferencePDF Ivan Brugere, Chris Kanich and Tanya Berger-Wolf
Abstract: Networks are representations of complex underlying social processes. However, the same given network may be more suitable to model one behavior of individuals than another. In many cases, aggregate population models may be more effective than modeling on the network. We present a general framework for evaluating the suitability of given networks for a set of predictive tasks of interest, compared against alternative, networks inferred from data. We present several interpretable network models and measures for our comparison. We apply this general framework to the case study on collective classification of music preferences in a newly available dataset of the Last.fm social network.
Keywords: network inference, statistical relational learning, model selection and validation
@inproceedings{mlg2017_13,
title={Evaluating Social Networks Using Task-Focused Network Inference},
author={Ivan Brugere, Chris Kanich and Tanya Berger-Wolf},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Using Partial Probes to Infer Network StatesPDF Pavan Rangudu, Bijaya Adhikari, B. Aditya Prakash and Anil Vullikanti
Abstract: In many applications, such as the Internet and infrastructure networks, nodes fail or get congested dynamically. We study the problem of inferring all the failed nodes, when only a sample of the failures is known, and there exist correlations between node failures/congestion in networks. We formalize this as the StateInf problem, using the the Minimum Description Length (MDL) principle. We propose a greedy algorithm for minimizing the MDL cost, and show that it gives an additive approximation, relative to the optimal. We evaluate our methods on synthetic and real datasets, which includes
one from WAZE which gives traffic incident reports for the city of Boston. We find that our method gives promising results in recovering the missing failures.
@inproceedings{mlg2017_25,
title={Using Partial Probes to Infer Network States},
author={Pavan Rangudu, Bijaya Adhikari, B. Aditya Prakash and Anil Vullikanti},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
Compression of spatio-temporal networks via point-to-point process modelsPDF Xiaoyue Li and James Sharpnack
Abstract: A point-to-point process describes a dynamic network where a set of edge events are observed, each of which is associated with a time of occurrence and two vertices lying in their state spaces.
This study intends to investigate one application of such processes, using NYC Taxi and Limousine Commission dataset that reports taxi trips between two locations at a certain time.
Here a point-to-point process is formed with edge events being taxi trips and the vertices adjacent to the edge events are pick-up and drop-off locations, described by latitude and longitude pairs.
The intensity of an edge event can have a temporal dependence in addition to being dependent on a latent, spatially-coherent community structure for the vertices.
To this end, we have developed a methodology that estimates a spatially smoothed community structure and localizes temporal change-points for point-to-point processes.
By applying this to our dataset, we can explore the spatio-temporal dynamics of the demand of taxi trips.
More specifically, with reasonable assumptions, the latent community structure is estimated by spectral partitioning based on a low-rank reconstruction of aggregated taxi-trip network; and the temporal change-point localization can be carried out by solving a matrix group fused LASSO program.
@inproceedings{mlg2017_30,
title={Compression of spatio-temporal networks via point-to-point process models},
author={Xiaoyue Li and James Sharpnack},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
GECS: Graph Embedding Using Connection SubgraphsPDF Saba Al-Sayouri, Pravallika Devineni, Sarah Lam, Vagelis Papalexakis and Danai Koutra
Abstract: This paper studies the problem of learning large-scale graph representations (a.k.a. embeddings). Such representations encode the relations among distinct nodes on the continuous feature space. The learned representations generalize over various tasks, such as node classification, link prediction, and recommendation. Learning nodes representations aims to map proximate nodes close to one another in the low-dimension vector space. Thus, embedding algorithms pursue to preserve local and global network structure by identifying nodes neighborhood notions. However, the means proposed methods have been employed in order to identify nodes neighborhoods fail to precisely capture network structure. In this paper, we propose a novel scalable graph embedding algorithmic framework called GECS, which aims to learn graph representations using connection subgraphs, where analogy with electrical circuits has been employed. The connection subgraphs are created to address the proximity among each two non-adjacent nodes, which are abundant in real-world networks, by maximizing the amount of flow between them. Although a subgraph captures proximity between two non-adjacent nodes, the formation of the subgraph addresses the direct connections with immediate neighbors as well. Therefore, our algorithm better preserves the local and global structure of a network. Further, despite the fact that non-adjacent nodes are numerous in real-world networks, our algorithm can scale to large-scale graphs, because we do not deal with the graph as a whole, instead, with much more smaller extracted subgraphs.
Since our algorithm is not yet empirically examined, we here introduce a potential solution that can better learn graph representations comparing to existing embedding methods accompanied by rational reasoning.
Keywords: information networks, network flow, learning graph representations, node embedding
@inproceedings{mlg2017_28,
title={GECS: Graph Embedding Using Connection Subgraphs},
author={Saba Al-Sayouri, Pravallika Devineni, Sarah Lam, Vagelis Papalexakis and Danai Koutra},
booktitle={Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG)},
year={2017}
}
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
Relationships between MLG and statistical relational learning or inductive logic programming
Algorithms and methods:
Graph mining
Kernel methods for structured data
Probabilistic and graphical models for structured data
(Multi-) Relational data mining
Methods for structured outputs
Statistical models of graph structure
Combinatorial graph methods
Spectral graph methods
Semi-supervised learning, active learning, transductive inference, and transfer learning in the context of graph
Applications and analysis:
Analysis of social media
Social network analysis
Analysis of biological networks
Large-scale analysis and modeling
We invite the submission of regular research papers (6-8 pages) as well as position papers (2-4 pages).
We recommend papers to be formatted according to the standard double-column ACM Proceedings Style.
All papers will be peer reviewed, single-blinded.
Authors whose papers are accepted to the workshop will have the opportunity to participate in a poster session, and some set may also be chosen for oral presentation.
The accepted papers will be published online and will not be considered archival.
Please send enquiries to chair@mlgworkshop.org.
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:Apr 20, 2017
Paper Submission Deadline:June 2, 2017
Author Notification:June 23, 2017
Camera Ready:July 7, 2017
Workshop: August 14, 2017
Workshop Organizers
Michele Catasta
Stanford University
Shobeir Fakhraei
University of Maryland
Danai Koutra
University of Michigan
Silvio Lattanzi
Google Research
Julian McAuley
UC San Diego
Jennifer Neville
Purdue University
Program Committee
Nesreen Ahmed (Intel Labs)
Leman Akoglu (Carnegie Mellon University)
Aris Anagnostopoulos (Sapienza University of Rome)
Miguel Araujo (Carnegie Mellon University)
Stephen Bach (Stanford University)
Christian Bauckhage (Fraunhofer IAIS)
Aaron Clauset (University of Colorado Boulder)
Bing Tian Dai (Singapore Management University)
Alessandro Epasto (Google Research)
Bailey Fosdick (Colorado State University)
Brian Gallagher (Lawrence Livermore National Labs)
Thomas Gärtner (University of Nottingham)
Assefaw Gebremedhin (Washington State University)
David Gleich (Purdue University)
Larry Holder (Washington State University)
Kristian Kersting (TU Dortmund University)
Srijan Kumar (University of Maryland)
Evangelos Papalexakis (University of California Riverside)
Ali Pinar (Sandia National Laboratories)
Bryan Perozzi (Google Research)
Aditya Prakash (Virginia Tech)
Jay Pujara (University of California, Santa Cruz)
Jan Ramon (INRIA)
C. Seshadhri (University of California, Santa Cruz)
Neil Shah (Carnegie Mellon University)
Sucheta Soundarajan (Syracuse University)
Yizhou Sun (University of California, Los Angeles)
Jiliang Tang (Michigan State University)
Hanghang Tong (Arizona State University)
Chris Volinsky (AT&T Labs-Research)
Tim Weninger (University of Notre Dame)
Jevin West (University of Washington)
Stefan Wrobel (Fraunhofer IAIS & Univ. of Bonn)
Mark Zhang (SUNY, Binghamton)
