Graph alignment, also known as network alignment, is a fundamental task in social network analysis. Many recent works have relied on partially labeled cross-graph node correspondences, i.e., anchor links. However, due to the privacy and security issue, the manual labeling of anchor links for diverse scenarios may be prohibitive. Aligning two graphs without any anchor links is a crucial and challenging task. In this paper, we propose an Unsupervised Adversarial Graph Alignment (UAGA) framework to learn a cross-graph alignment between two embedding spaces of different graphs in a fully unsupervised fashion ( no existing anchor links and no users' personal profile or attribute information is available). The proposed framework learns the embedding spaces of each graph, and then attempts to align the two spaces via adversarial training, followed by a refinement procedure. We further extend our UAGA method to incremental UAGA (iUAGA) that iteratively reveals the unobserved user links based on the pseudo anchor links. This can be used to further improve both the embedding quality and the alignment accuracy. Moreover, the proposed methods will benefit some real-world applications, link prediction in social networks. Comprehensive experiments on real-world data demonstrate the effectiveness of our proposed approaches UAGA and iUAGA for unsupervised graph alignment.
The graph alignment, which aims to find node correspondence across different graphs, has attracted lots of research interests with extensive literatures in the past decade. Graph alignment was first studied by exploring the graph structure to align the topology of the underlying graphs. For example, IsoRank @cite_18 aligns different graphs greedily based on the pairwise topology similarities ( node similarity) calculated with spectral graph theory and finds the alignment by solving the maximum bipartite matching. NetAlign @cite_21 proposes a distributed and efficient algorithm for the sparse bipartite graph matching problem by using the max-product belief propagation based on the graph topology. UniAlign @cite_32 proposes to distinguish the nodes of graphs by types ( users and groups) and find the correspondences at different granularities at once for the fast bipartite or unipartite graph matching problem. Klau @cite_14 formulates the pairwise global graph alignment problem as the graph-based maximum structural matching problem, which is solved by a Lagrangian relaxation approach. These approaches, however, ignore the rich attribute information on nodes and or edges in many real graphs and are prone to lead to sub-optimal results.
@cite_14 @cite_18 @cite_21 @cite_32
2949708310 2255320195 1974682889 2097746044
Network alignment is the problem of matching the nodes of two graphs, maximizing the similarity of the matched nodes and the edges between them. This problem is encountered in a wide array of applications - from biological networks to social networks to ontologies - where multiple networked data sources need to be integrated. Due to the difficulty of the task, an accurate alignment can rarely be found without human assistance. Thus, it is of great practical importance to develop network alignment algorithms that can optimally leverage experts who are able to provide the correct alignment for a small number of nodes. Yet, only a handful of existing works address this active network alignment setting. The majority of the existing active methods focus on absolute queries ("are nodes @math and @math the same or not?"), whereas we argue that it is generally easier for a human expert to answer relative queries ("which node in the set @math is the most similar to node @math ?"). This paper introduces a novel relative-query strategy, TopMatchings, which can be applied on top of any network alignment method that constructs and solves a bipartite matching problem. Our method identifies the most informative nodes to query based on the top- @math matchings of a bipartite graph. We compare the proposed approach to several commonly-used query strategies and perform experiments on both synthetic and real-world datasets. Our matching-based strategy yields the highest overall performance, outperforming all the baseline methods by more than 15 percentage points in some cases. Graph matching has a wide spectrum of computer vision applications such as finding feature point correspondences across images. The problem of graph matching is generally NP-hard, so most existing work pursues suboptimal solutions between two graphs. This paper investigates a more general problem of matching N attributed graphs to each other, i.e. labeling their common node correspondences such that a certain compatibility affinity objective is optimized. This multi-graph matching problem involves two key ingredients affecting the overall accuracy: a) the pairwise affinity matching score between two local graphs, and b) global matching consistency that measures the uniqueness and consistency of the pairwise matching results by different sequential matching orders. Previous work typically either enforces the matching consistency constraints in the beginning of iterative optimization, which may propagate matching error both over iterations and across different graph pairs; or separates score optimizing and consistency synchronization in two steps. This paper is motivated by the observation that affinity score and consistency are mutually affected and shall be tackled jointly to capture their correlation behavior. As such, we propose a novel multi-graph matching algorithm to incorporate the two aspects by iteratively approximating the global-optimal affinity score, meanwhile gradually infusing the consistency as a regularizer, which improves the performance of the initial solutions obtained by existing pairwise graph matching solvers. The proposed algorithm with a theoretically proven convergence shows notable efficacy on both synthetic and public image datasets. How can we find the virtual twin (i.e., the same or similar user) on Linked In for a user on Facebook? How can we effectively link an information network with a social network to support cross-network search? Graph alignment - the task of finding the node correspondences between two given graphs - is a fundamental building block in numerous application domains, such as social networks analysis, bioinformatics, chemistry, pattern recognition. In this work, we focus on aligning bipartite graphs, a problem which has been largely ignored by the extensive existing work on graph matching, despite the ubiquity of those graphs (e.g., users-groups network). We introduce a new optimization formulation and propose an effective and fast algorithm to solve it. We also propose a fast generalization of our approach to align unipartite graphs. The extensive experimental evaluations show that our method outperforms the state-of-art graph matching algorithms in both alignment accuracy and running time, being up to 10x more accurate or 174x faster on real graphs. In this paper, we propose a general framework for graph matching which is suitable for different problems of pattern recognition. The pattern representation we assume is at the same time highly structured, like for classic syntactic and structural approaches, and of subsymbolic nature with real-valued features, like for connectionist and statistic approaches. We show that random walk based models, inspired by Google's PageRank, give rise to a spectral theory that nicely enhances the graph topological features at node level. As a straightforward consequence, we derive a polynomial algorithm for the classic graph isomorphism problem, under the restriction of dealing with Markovian spectrally distinguishable graphs (MSD), a class of graphs that does not seem to be easily reducible to others proposed in the literature. The experimental results that we found on different test-beds of the TC-15 graph database show that the defined MSD class "almost always" covers the database, and that the proposed algorithm is significantly more efficient than top scoring VF algorithm on the same data. Most interestingly, the proposed approach is very well-suited for dealing with partial and approximate graph matching problems, derived for instance from image retrieval tasks. We consider the objects of the COIL-100 visual collection and provide a graph-based representation, whose node's labels contain appropriate visual features. We show that the adoption of classic bipartite graph matching algorithms offers a straightforward generalization of the algorithm given for graph isomorphism and, finally, we report very promising experimental results on the COIL-100 visual collection.