Graph Reinforcement for Accurate Community Detection and Embedding on Graphs and Hypergraphs
- Graph Reinforcement for Accurate Community Detection and Embedding on Graphs and Hypergraphs
- Alternative Author(s)
- Issue Date
- 2022. 2
- A graph consisting of nodes and edges is widely used in various real-world domains to represent relationships between objects. Depending on the type of the relationship, various types of graphs exist such as unsigned graph, signed graph, and hypergraph. Various graph mining tasks have been proposed to derive meaningful information from these graphs. Community detection (CD) is the task of identifying the community structure in a given graph and graph embedding (GE) is a task of representing nodes of a given graph by vectors preserving structural properties, such as proximity in the graph space, in a low-dimensional embedding space. These two tasks are regarded as one of crucial graph mining tasks, and those tasks have widely employed into various domains. Unfortunately, many real-world graphs are very sparse. Accordingly, it may not be sufficiently trained in CD and GE. Also, a number of noise edges exist in graphs, which negatively affect the accuracy of community CD and GE. For these reasons, the accuracies of CD and GE methods in real-world graphs are often unsatisfactory. If we make a given graph sufficiently dense by adding edges and if we delete noise edges from the given graph, we can provide higher accuracy in CD and GE. In this context, we define the notion of graph reinforcement as adding edges into the graph and deleting noise edges from the graph. In this dissertation, we aim to employ the graph reinforcement in CD and GE on various types of graphs, and validate the effectiveness of the graph reinforcement.
Toward this goal, we first propose a graph reinforcement method for accurate CD on unsigned graphs, named as CR-Graph. Our method strengthens a community structure of a given graph by adding intra-community edges into the graph and deleting inter-community edges from the graph. To realize our method, we propose the following three strategies: (1) predicting intra-community and inter-community edges; (2) determining the amount of edges to be added/deleted; and (3) reducing the amount of computations in predicting the type of edges. To validate the effectiveness of CR-Graph, we conduct extensive experiments with various existing CD methods on 11 synthetic and 6 real-world unsigned graphs. The results demonstrate that CR-Graph significantly improves the accuracy regardless of CD methods and graphs, and outperforms two state-of-the-art edge weighting-based preprocessing methods in all datasets.
Second, we propose a graph reinforcement method for accurate CD on signed graphs, named as ABC. Our method first represents all the nodes of a given signed graph as vectors in a low-dimensional space based on the adversarial learning of balanced triangles, and then conducts a clustering algorithm on those vectors. To this end, we propose the following three strategies: (1) learning only the edges in the balanced triangles; (2) learning the edges in the balanced real/virtual-triangles; and (3) employing adversarial learning. Through extensive experiments using 7 real-world signed graphs, we validate the effectiveness of learning edges belonging to balanced real/virtual-triangles and employing adversarial learning for graph embedding. In addition, we show that ABC consistently and significantly outperforms the state-of-the-art CD methods in all datasets.
Lastly, we propose a graph reinforcement method for effective GE on hypergraphs, named as STARGNN. Our method represents all the nodes of a given hypergraph as vectors in a low-dimensional space based on the graph neural network on star expansion. To realize our method, we propose the following two strategies: (1) employing graph neural network on a bipartite graph and (2) combining clique loss in graph neural network. Through extensive experiments using 5 real-world hypergraphs, we show that STARGNN outperforms the state-of-the-art GE methods on hypergraphs.
- Appears in Collections:
- GRADUATE SCHOOL[S](대학원) > COMPUTER SCIENCE(컴퓨터·소프트웨어학과) > Theses (Ph.D.)
- Files in This Item:
There are no files associated with this item.
- RIS (EndNote)
- XLS (Excel)