Knowledge graphs form large networks of millions of entities (e.g., Michelle Obama, Barack Obama) and relationships (e.g., married). To obtain an overview of the entity, we need to inspect a potentially large number of relationships to other entities. For this reason, entity summarization aims to extract succinct but expressive descriptions of each entity. Yet, existing methods build their summaries only based on the immediate connections of an entity, disregarding how indirect relationships contain essential information for describing the entity (e.g., understanding Michelle Obama also via her husband's role as former president). We propose IRES, an unsupervised entity summarization method built on graph theoretical principles. We draw a notable connection between the informativeness of a summary and graph partitioning, and devise an effective approach to learn diverse aspects that characterize an entity. In a comprehensive experimental study, IRES shows superior summary quality. In particular, when full neighborhood information is available, IRES outperforms existing methods by 6 percentage points F1 while maintaining competitive computational efficiency.

Centrality measures, quantifying the importance of vertices or edges, play a fundamental role in network analysis. To date, triggered by some positive approximability results, a large body of work has been devoted to studying centrality maximization, where the goal is to maximize the centrality score of a target vertex by manipulating the structure of a given network. On the other hand, due to the lack of such results, only very little attention has been paid to centrality minimization, despite its practical usefulness.

Dense subgraph discovery methods are routinely used in a variety of applications including the identification of a team of skilled individuals for collaboration from a social network. However, when the network's node set is associated with a sensitive attribute such as race, gender, religion, or political opinion, the lack of diversity can lead to lawsuits.

Network analysis has played a key role in knowledge discovery and data mining. In many real-world applications in recent years, we are interested in mining multilayer networks, where we have a number of edge sets called layers, which encode different types of connections and/or time-dependent connections over the same set of vertices. Among many network analysis techniques, dense subgraph discovery, aiming to find a dense component in a network, is an essential primitive with a variety of applications in diverse domains. In this paper, we introduce a novel optimization model for dense subgraph discovery in multilayer networks. Our model aims to find a stochastic solution, i.e., a probability distribution over the family of vertex subsets, rather than a single vertex subset, whereas it can also be used for obtaining a single vertex subset. For our model, we design an LP-based polynomial-time exact algorithm. Moreover, to handle large-scale networks, we also devise a simple, scalable preprocessing algorithm, which often reduces the size of the input networks significantly and results in a substantial speed-up. Computational experiments demonstrate the validity of our model and the effectiveness of our algorithms.

Dense subgraph discovery is a fundamental problem in graph mining whose goal is to extract a dense subgraph from a given graph, and it has a wide range of applications [18]. However, numerous real-world applications, ranging from computational biology and computational neuroscience to computational social science, take as input a dual graph, namely a pair of graphs on the same set of nodes. Despite the large number of such applications, research on dense subgraph discovery has focused on a single graph input, with few notable exceptions [9, 22, 35, 36]. In this work, we contribute to this line of research by studying the following novel algorithmic problem: Given a pair of graphs G, H on the same set of nodes V, how do we find a subset of nodes S ⊆ V that induces a well-connected subgraph in G and a dense subgraph in H? Our formulation generalizes previous research [11, 44, 45], by enabling to control the connectivity constraint on G. We propose a mathematical formulation and prove that it is solvable exactly in polynomial time. We compare our method to state-of-the-art competitors and find empirically that controlling the connectivity constraint enables the practitioner to obtain information that is otherwise inaccessible. Finally, we show that our proposed mining tool can be used to better understand how users interact on Twitter and connectivity aspects of human brain networks with and without Autism Spectrum Disorder (ASD).

Many social phenomena are triggered by public opinion that is formed in the process of opinion exchange among individuals. To date, from the engineering point of view, a large body of work has been devoted to studying how to manipulate individual opinions so as to guide public opinion towards the desired state. Recently, Abebe et al. (KDD 2018) have initiated the study of the impact of interventions at the level of susceptibility rather than the interventions that directly modify individual opinions themselves. For the model, Chan et al. (The Web Conference 2019) designed a local search algorithm to find an optimal solution in polynomial time. However, it can be seen that the solution obtained by solving the above model might not be implemented in real-world scenarios. In fact, as we do not consider the amount of changes of the susceptibility, it would be too costly to change the susceptibility values for agents based on the solution.

A hypergraph is a useful combinatorial object to model ternary or higher-order relations among entities. Clustering hypergraphs is a fundamental task in network analysis. In this study, we develop two clustering algorithms based on personalized PageRank on hypergraphs. The first one is local in the sense that its goal is to find a tightly connected vertex set with a bounded volume including a specified vertex. The second one is global in the sense that its goal is to find a tightly connected vertex set. For both algorithms, we discuss theoretical guarantees on the conductance of the output vertex set. Also, we experimentally demonstrate that our clustering algorithms outperform existing methods in terms of both the solution quality and running time. To the best of our knowledge, ours are the first practical algorithms for hypergraphs with theoretical guarantees on the conductance of the output set.

Community detection is one of the fundamental tasks in graph mining, which has many real-world applications in diverse domains. In this study, we propose an optimization model for finding a community that is densely connected internally but sparsely connected to the rest of the graph. The model extends the densest subgraph problem, in which we maximize the density while minimizing the average cut size. We first show that our proposed model can be solved efficiently. Then we design two polynomial-time exact algorithms based on linear programming and a maximum flow algorithm, respectively. Moreover, to deal with larger-sized graphs in practice, we present a scalable greedy algorithm that runs in almost linear time with theoretical performance guarantee of the output. In addition, as our model is closely related to a quality function called the modularity density, we show that our algorithms can also be used to find global community structure in a graph. With thorough experiments using well-known real-world graphs, we demonstrate that our algorithms are highly effective in finding a suitable community in a graph. For example, for web-Google, our algorithm finds a solution with more than 99.1% density and less than 3.1% cut size, compared with a solution obtained by a baseline algorithm for the densest subgraph problem.

Dense subgraph discovery is an important primitive in graph mining, which has a wide variety of applications in diverse domains. In the densest subgraph problem, given an undirected graph G = (V, E) with an edge-weight vector w = (We)e∈E, we aim to find a subset of vertices S that maximizes the density, i.e., w(S) / |S|, where w(S) is the sum of the weights of the edges in the subgraph induced by S. Although the densest subgraph problem is one of the most well-studied optimization problems for dense subgraph discovery, there is an implicit strong assumption; it is assumed that the weights of all the edges are known exactly as input. In real-world applications, there are often cases where we have only uncertain information of the edge weights. In this study, we provide a framework for dense subgraph discovery under the uncertainty of edge weights. Specifically, we address such an uncertainty issue using the theory of robust optimization. First, we formulate our fundamental problem, the robust densest subgraph problem, and present a simple algorithm. We then formulate the robust densest subgraph problem with sampling oracle that models dense subgraph discovery using an edge-weight sampling oracle, and present an algorithm with a strong theoretical performance guarantee. Computational experiments using both synthetic graphs and popular real-world graphs demonstrate the effectiveness of our proposed algorithms.

In this study, we introduce a novel quality function for a network community, which we refer to as the communitude. The communitude has a strong statistical background. Specifically, it measures the Z-score of a subset of vertices S with respect to the fraction of the number of edges within the subgraph induced by S. Due to the null model of a random graph used in the definition, our quality function focuses not only on the inside of the subgraph but also on the cut edges, unlike some quality functions for extracting dense subgraphs. To evaluate the detection ability of our quality function, we address the communitude maximization problem and its variants for realistic scenarios. For the problems, we propose a two-phase heuristic algorithm together with some modified versions. In the first phase, it repeatedly removes the vertex with the smallest degree, and then obtains the subgraph with maximum communitude over the iterations. In the second phase, the algorithm improves the obtained solution using a simple local search heuristic. This algorithm runs in linear time when the number of iterations is fixed to a constant; thus, it is applicable to massive graphs. Computational experiments using both synthetic graphs and real-world networks demonstrate the validity and reliability of the proposed quality function and algorithms.