todo314 @ ウィキ
todo314 @ ウィキ

気になった論文

理論計算機科学

ACM Symposium on Theory of Computing

STOC 2000

  • Circuit minimization problem
  • A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
  • Improved algorithms for submodular function minimization and submodular flow
  • On dual minimum cost flow algorithms
  • The small-world phenomenon: an algorithm perspective
  • A random graph model for massive graphs
  • Near-optimal fully-dynamic graph connectivity
  • Are bitvectors optimal?

STOC 2015

  • Testing Cluster Structure of Graphs
  • Greedy Algorithms for Steiner Forest
  • Online Submodular Welfare Maximization: Greedy beats 1/2
  • Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
  • Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time.
  • Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
  • Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).
  • The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree.
  • Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.

STOC 2016

  • Simpler Analysis and Enumeration of Parametric Minimum Cuts
    • David Karger
  • Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
  • Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
  • Graph Isomorphism in Quasipolynomial Time
    • Laszlo Babai

IEEE Symposium on Foundations of Computer Science

FOCS 2000

  • Random graph models for the web graph
  • Hardness of Approximate Hypergraph Coloring
  • How Bad is Selfish Routing?
  • Detecting a Network Failure
  • Fully Dynamic Transitive Closure: Breaking Through the O(n2) Barrier
  • The Cover Time, the Blanket Time, and the Matthews Bound
  • Randomized Rumor Spreading

FOCS 2001

  • Online Facility Location
  • Testing Subgraphs in Large Graphs
  • Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication
  • Spectral Partitioning of Random Graphs

FOCS 2002

  • Correlation Clustering
  • Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems

FOCS 2004

  • 0(sqrt (log n)) Approximation to SPARSEST CUT in O(n2) Time
  • Maximum Matchings via Gaussian Elimination
  • A Simple Linear Time (1+?)-Approximation Algorithm for k-Means Clustering in Any Dimensions
  • Dynamic Transitive Closure via Dynamic Matrix Inverse
  • Spectral Analysis of Random Graphs with Skewed Degree Distributions

FOCS 2005

  • A Recursive Greedy Algorithm for Walks in Directed Graphs
  • Additive Approximation for Edge-Deletion Problems
  • Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring

FOCS 2006

  • ✔Local Graph Partitioning using PageRank Vectors
    • 特定の頂点に近い（含む）カットを劣線形時間で求めたい
    • PPR（のようなもの）を使う
    • コンダクタンスが$$\Omega(\phi^2 / \log m)$$のカットが存在する場合，コンダクタンス$$\phi$$のカットを見つけられる

FOCS 2009

  • ✔Faster Generation of Random Spanning Trees
    • 全域木の無作為標本したい
    • 分布がちょっとずれても良いとする
    • 疎グラフでの最悪時が改善された
  • Faster Generation of Random Spanning Trees
  • Local Graph Partitions for Approximation and Testing
  • Decomposing Coverings and the Planar Sensor Cover Problem
  • Breaking the Multicommodity Flow Barrier for O(vlog n)-Approximations to Sparsest Cut
  • k-Means Has Polynomial Smoothed Complexity
  • Symmetry and Approximability of Submodular Maximization Problems
  • Submodular Function Minimization under Covering Constraints
  • Distance Oracles for Sparse Graphs
  • Higher Eigenvalues of Graphs

FOCS 2012

  • A New Direction for Counting Perfect Matchings

FOCS 2014

  • Threesomes, Degenerates, and Love Triangles
  • The Communication Complexity of Distributed ?-Approximations
  • Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search

FOCS 2015

  • Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
  • If the Current Clique Algorithms are Optimal, so is Valiant's Parser
  • Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
  • Approximately Counting Triangles in Sublinear Time
  • Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions

ACM-SIAM Symposium on Discrete Algorithms

SODA 2000

  • Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs
  • A faster method for sampling independent sets
  • Adaptive set intersections, unions, and differences
  • The prize collecting Steiner tree problem: theory and practice
  • Improved Steiner tree approximation in graphs

SODA 2001

  • Combinatorial approximation algorithms for the maximum directed cut problem
  • Tree packing and approximating k-cuts
  • Distance labeling in graphs
  • Fast approximation of centrality
  • Worst case constant time priority queue
  • New approaches to covering and packing problems
  • Algorithms for facility location problems with outliers

SODA 2002

  • Union-find with deletions
  • Mixing time and long paths in graphs
  • The diameter of a long range percolation graph
  • Experimental analysis of simple, distributed vertex coloring algorithms
  • A fully combinatorial algorithm for submodular function minimization
  • Reachability and distance queries via 2-hop labels

SODA 2003

  • Directed scale-free graphs
  • The cover time of sparse random graphs
  • Quick and good facility location
  • Skip graphs
  • Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph
  • Directed graphs requiring large numbers of shortcuts
  • Sublinear-time approximation of Euclidean minimum spanning tree

SODA 2004

  • The Bloomier filter: an efficient data structure for static support lookup tables
  • Finding a long directed cycle
  • Network failure detection and graph connectivity
  • Experimental analysis of dynamic all pairs shortest path algorithms
  • Correlation Clustering: maximizing agreements via semidefinite programming
  • Equivalence of local treewidth and linear local treewidth and its algorithmic applications

SODA 2005

  • Computing the shortest path: A search meets graph theory
  • On the spread of viruses on the internet
  • Analyzing and characterizing small-world graphs
  • Approximating the smallest k-edge connected spanning subgraph by LP-rounding
  • Approximating vertex cover on dense graphs
  • An optimal Bloom filter replacement

SODA 2006

  • Measure and conquer: a simple O(20.288n) independent set algorithm
  • An O (n log n) algorithm for maximum st-flow in a directed planar graph
  • DAG-width: connectivity measure for directed graphs
  • Counting without sampling: new algorithms for enumeration problems using statistical physics
  • Correlation clustering with a fixed number of clusters

SODA 2007

  • Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition
  • Noisy binary search and its applications
  • k-means++: the advantages of careful seeding
  • Approximation algorithms for stochastic and risk-averse optimization

SODA 2008

  • Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
  • Fast approximation of the permanent for very dense problems
  • A local algorithm for finding dense subgraphs
  • PageRank and the random surfer model
  • On the approximability of influence in social networks

SODA 2009

  • A near-linear time algorithm for constructing a cactus representation of minimum cuts
  • Improved smoothed analysis of the k-means method
  • Maximizing submodular set functions subject to multiple linear constraints
  • Clique-width: on the price of generality
  • A simple combinatorial algorithm for submodular function minimization

SODA 2010

  • Rumour Spreading and Graph Conductance
    • conductanceが大きいほどrumour spreading／randomized broadcastのステップ数が小さい
  • Counting Stars and Other Small Subgraphs in Sublinear Time
  • An (almost) Linear Time Algorithm for Odd Cyles Transversal
  • Coresets and Sketches for High Dimensional Subspace Approximation Problems
  • Correlation Clustering with Noisy Input
  • Highway Dimension, Shortest Paths, and Provably Efficient Algorithms
  • Maximum Flows and Parametric Shortest Paths in Planar Graphs
  • Randomized Shellsort: A Simple Oblivious Sorting Algorithm
  • Tree Embeddings for Two-Edge-Connected Network Design
  • Rumour Spreading and Graph Conductance

SODA 2012

  • Analyzing graph structure via linear measurements
  • Counting Perfect Matchings as Fast as Ryser

SODA 2015

  • Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
  • Online Submodular Maximization with Preemption
  • Fast Generation of Random Spanning Trees and the Effective Resistance Metric
  • 2-Edge Connectivity in Directed Graphs
  • Finding four-node subgraphs in triangle time

SODA 2016

  • Kernelization via Sampling with Applications to Dynamic Graph Streams
  • Simpler, faster and shorter labels for distances in graphs
  • Function Limits, and Parameter Estimation
  • Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
  • How to Round Subspaces: A New Spectral Clustering Algorithm
  • Deterministic Algorithms for Submodular Maximization Problems
  • Locality-sensitive Hashing without False Negatives
  • Treetopes and their Graphs
  • Improved Approximation Algorithms for k-Submodular Function Maximization
  • Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile
  • Algorithmic Complexity of Power Law Networks
  • Better Distance Preservers and Additive Spanners
  • An Algorithmic Hypergraph Regularity Lemma
  • Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee
  • On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs

SODA 2017

  • Random Contractions and Sampling for Hypergraph and Hedge Connectivity

SODA 2016

  • ✔Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
    • 影響最大化のadaptive seedingの一般化
    • 一段階目での選択が二段階目のrealizationに影響する
    • (1-1/e)^2近似アルゴリズム
  • ✔Algorithmic Complexity of Power Law Networks
    • Power lawグラフのアルゴリズム計算量を解析
    • ベキ則の判定（？）
    • なんで色んな（最悪時は遅い）アルゴリズムが高速に動作するのか？
    • ランダムグラフだとうまく行くと示されていたが（average-case analysis）
    • 固定されてものでやった

SODA 2018

  • Stochastic Packing Integer Program with Few Queries
    • クエリ数を少なく解きたい。色々なものに使えます。
  • Near-optimal approximation algorithm for simultaneous Max-Cut
    • Simultaneous Max-Cut: 同じ頂点集合上の複数グラフが与えられて最小カット値が大きいカットが欲しいよ
    • 既存手法は1/2近似、今回は0.8780近似
  • ✔Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms
    • Kirchhoff index=有効抵抗の和、θ-Kirchhoff edge centrality=辺eが弱められたときの抵抗の増分
    • betweennessやspanningよりも良さげ。
  • Efficient O˜(n/ε) Spectral Sketches for the Laplacian and its Pseudoinverse
    • $$f(x) \approx x^\topAx$$になるようなfが効率的に欲しい
  • Set Cover in Sub-linear Time
    • なんだか込み入っているなぁ。。。
  • Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
  • The Diameter of Dense Random Regular Graphs
  • Randomized MWU for Positive LPs
    • randomizationでなんか改善されるらしい
  • Estimating graph parameters via random walks with restarts
    • 頂点数とか、mixing time

ICALP 2013

  • Optimal Partitioning for Dual Pivot Quicksort
  • New Doubling Spanners: Better and Simpler
  • Maximum Edge-Disjoint Paths in k-Sums of Graphs
  • Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree
  • Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation-

ICALP 2014

  • Listing Triangles
  • Randomized Rumor Spreading in Dynamic Graphs

ICALP 2015

  • Streaming Algorithms for Submodular Function Maximization
  • On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace
  • 2-Vertex Connectivity in Directed Graphs
  • Hollow Heaps
  • Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
  • Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
  • Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
  • Core Size and Densification in Preferential Attachment Networks

ICALP 2018

  • Sublinear Algorithms for MAXCUT and Correlation Clustering
  • A polynomial-time approximation algorithm for all-terminal network reliability
  • Finding Cliques in Social Networks: A New Distribution-Free Model
  • High Probability Frequency Moment Sketches
  • A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity

International Symposium on Algorithms and Computation

ISAAC 2011

  • Contraction-Based Steiner Tree Approximations in Practice
  • Hamiltonian Paths in the Square of a Tree

ISAAC 2012

  • An 8/3 Lower Bound for Online Dynamic Bin Packing
  • Fast and Simple Fully-Dynamic Cut Tree Construction
  • Counting Partitions of Graphs
  • How Many Potatoes Are in a Mesh?
  • Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
  • On the Hyperbolicity of Small-World and Tree-Like Random Graphs
  • Parameterized Clique on Scale-Free Networks

ISAAC 2013

  • Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs
  • Exact Algorithms for Maximum Independent Set
  • On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
  • Augmenting Graphs to Minimize the Diameter
  • Sliding Bloom Filters
  • An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching
  • Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
  • Approximating the Generalized Minimum Manhattan Network Problem

ISAAC 2014

  • Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
  • An Efficient Method for Indexing All Topological Orders of a Directed Graph
    • Yuma Inoue, Shin-ichi Minato
  • Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs
  • Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality

ISAAC 2015

  • How to select the largest k elements from evolving data?
  • Fully Dynamic Betweenness Centrality
  • Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty

ACM Conference on Innovations in Theoretical Computer Science

ITCS 2014

  • ✔Why do simple algorithms for triangle enumeration work in the real world?
    • C. Seshadhri
    • ベキ則次数分布を持つグラフでの三角形列挙の性能を解析
    • 特に簡単なヒューリスティクス
    • α>7/3だと期待計算時間が線形

アルゴリズム

Workshop on Algorithm Engineering and Experiments

ALENEX 2018

  • Scaling up Group Closeness Maximization
  • Practical Minimum Cut Algorithms
  • Scalable Kernelization for Maximum Independent Sets
  • Computing Top-k Closeness Centrality in Fully-dynamic Graphs
  • Computing 2-Connected Components and Maximal 2-Connected Subgraphs in Directed Graphs: An Experimental Study

ESA 2012

  • Hierarchical Hub Labelings for Shortest Paths
  • I/O-efficient Hierarchical Diameter Approximation
  • An Experimental Study of Dynamic Dominators
  • A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
  • Minimum Average Distance Triangulations

ESA 2013

  • Computing the Greedy Spanner in Linear Space
  • Parallel String Sample Sort
  • BICO: BIRCH meets Coresets for k-means
  • Z-Skip-Links for Fast Traversal of ZDDs Representing Large-Scale Sparse Datasets

ESA 2014

  • PReaCH: A Fast Lightweight Reachability Index using Pruning and Contraction Hierarchies
  • GRASP. Extending Graph Separators for the single-source shortest-path problem
  • Robust Distance Queries on Massive Networks
  • Improved Practical Matrix Sketching with Guarantees

ESA 2018

  • Scalable Katz Ranking Computation in Large Dynamic Graphs
  • On the Worst-Case Complexity of TimSort
  • Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
  • An exact algorithm for the Steiner forest problem
  • Large Low-Diameter Graphs are Good Expanders
  • Data Reduction for Maximum Matching on Sparse Graphs: Theory and Experiments

Workshop on Algorithms and Models for the Web Graph

WAW 2012

  • ✔A Sublinear Time Algorithm for PageRank Computations
    • PageRank値がΔ以上の頂点集合をとってきたい
    • ちょっと難しいので，Δ/c未満は絶対含まない（Δ/c以上は含んでても良い）って弱める
    • O~(n/Δ)時間アルゴリズム ほぼタイト
    • 提案手法はPPRの局所的探索を改善して使う

WEA 2003

  • Improving Linear Programming Approaches for the Steiner Tree Problem
  • Algorithms and Experiments on Colouring Squares of Planar Graphs
  • New Lower and Upper Bounds for Graph Treewidth
  • Experimental Studies of Graph Traversal Algorithms
  • A Lazy Version of Eppstein's K Shortest Paths Algorithm
  • Linear Algorithm for 3-Coloring of Locally Connected Graphs
  • Analysis and Visualization of Social Networks

WEA 2004

  • Simple Max-Cut for Split-Indifference Graphs and Graphs with Few P4's
  • Engineering Shortest Path Algorithms
  • Efficient Implementation of the BSP/CGM Parallel Vertex Cover FPT Algorithm
  • Combining Speed-Up Techniques for Shortest-Path Computations
  • Pre-processing and Linear-Decomposition Algorithm to Solve the k-Colorability Problem
  • Solving Diameter Constrained Minimum Spanning Tree Problems in Dense Graphs
  • A Heuristic for Minimum-Width Graph Layering with Consideration of Dummy Nodes

WEA 2005

  • Don't Compare Averages
  • High-Performance Algorithm Engineering for Large-Scale Graph Problems and Computational Biology
  • Degree-Based Treewidth Lower Bounds
  • Acceleration of Shortest Path and Constrained Shortest Path Computation
  • Partitioning Graphs to Speed Up Dijkstra's Algorithm
  • New Upper Bound Heuristics for Treewidth
  • Experimental Evaluation of the Greedy and Random Algorithms for Finding Independent Sets in Random Graphs
  • Local Clustering of Large Graphs by Approximate Fiedler Vectors
  • Vertex Cover Approximations: Experiments and Observations
  • Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study

WEA 2006

  • Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces
  • Fast and Simple Approximation of the Diameter and Radius of a Graph
  • Kernels for the Vertex Cover Problem on the Preferred Attachment Model
  • Practical Partitioning-Based Methods for the Steiner Problem
  • Updating Directed Minimum Cost Spanning Trees
  • Experiments on Exact Crossing Minimization Using Column Generation
  • Goal Directed Shortest Path Queries Using Precomputed Cluster Distances

WEA 2007

  • Random Models for Geometric Graphs
  • Landmark-Based Routing in Dynamic Graphs
  • Crossing Minimization in Weighted Bipartite Graphs
  • A Distributed Primal-Dual Heuristic for Steiner Problems in Networks
  • Experimental Evaluation of Parametric Max-Flow Algorithms
  • Vertex Cover Approximations on Random Graphs
  • Optimal Edge Deletions for Signed Graph Balancing
  • Algorithms for the Balanced Edge Partitioning Problem
  • Experimental Analysis of Algorithms for Updating Minimum Spanning Trees on Graphs Subject to Changes on Edge Weights
  • A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

WEA 2008

  • Comparing Integer Data Structures for 32 and 64 Bit Keys
  • Fast Local Search for the Maximum Independent Set Problem
  • Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
  • Bidirectional A* Search for Time-Dependent Fast Paths
  • Multi-criteria Shortest Paths in Time-Dependent Train Networks

SEA 2009

  • Batch Dynamic Single-Source Shortest-Path Algorithms: An Experimental Study
  • A Heuristic Strong Connectivity Algorithm for Large Graphs
  • Pareto Paths with SHARC
  • Empirical Evaluation of Graph Partitioning Using Spectral Embeddings and Flow
  • Fast Algorithm for Graph Isomorphism Testing
  • Algorithms and Experiments for Clique Relaxations-Finding Maximum s-Plexes
  • Multi-level Algorithms for Modularity Clustering

SEA 2010

  • Computational Challenges with Cliques, Quasi-cliques and Clique Partitions in Graphs
  • Alternative Routes in Road Networks
  • Fully Dynamic Speed-Up Techniques for Multi-criteria Shortest Path Searches in Time-Dependent Networks
  • Exact Bipartite Crossing Minimization under Tree Constraints
  • An Analysis of Heuristics for Vertex Colouring
  • Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure
  • Modularity-Driven Clustering of Dynamic Graphs
  • Gateway Decompositions for Constrained Reachability Problems
  • Geometric Minimum Spanning Trees with GeoFilterKruskal

SEA 2011

  • Metaheuristic Optimization: Algorithm Analysis and Open Problems
  • An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms
  • An Experimental Evaluation of Treewidth at Most Four Reductions
  • A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks
  • Listing All Maximal Cliques in Large Sparse Real-World Graphs
    • Eppstein
  • An Iterative Refinement Algorithm for the Minimum Branch Vertices Problem

SEA 2012

  • Implementation and Comparison of Heuristics for the Vertex Cover Problem on Huge Graphs
  • How to Attack the NP-Complete Dag Realization Problem in Practice
  • On Computing the Diameter of Real-World Directed (Weighted) Graphs
  • Computing Strong Articulation Points and Strong Bridges in Large Scale Graphs
  • Exact Graph Search Algorithms for Generalized Traveling Salesman Path Problems
  • Advanced Coarsening Schemes for Graph Partitioning
  • A Decomposition Approach for Solving Critical Clique Detection Problems

SEA 2013

  • Hub Label Compression
  • Faster Customization of Road Networks
  • Intriguingly Simple and Fast Transit Routing
  • Transit Node Routing Reconsidered
  • Hypergraph Transversal Computation with Binary Decision Diagrams
  • Efficient Counting of Maximal Independent Sets in Sparse Graphs
  • Think Locally, Act Globally: Highly Balanced Graph Partitioning

SEA 2014

  • Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth
  • Efficient Wavelet Tree Construction and Querying for Multicore Architectures
  • DenseZDD: A Compact and Fast Index for Families of Sets
  • Hub Labels: Theory and Practice
  • Customizable Contraction Hierarchies
  • Experimental Evaluation of Dynamic Shortest Path Tree Algorithms on Homogeneous Batches
  • Partitioning Complex Networks via Size-Constrained Clustering
  • Tree-Based Coarsening and Partitioning of Complex Networks
  • Search Space Reduction through Commitments in Pathwidth Computation: An Experimental Study

SEA 2015

  • Greedily Improving Our Own Centrality in A Network
  • An Exact Algorithm for Diameters of Large Real Directed Graphs
  • Graph Partitioning for Independent Sets
  • Finding Connected Subgraphs of Fixed Minimum Density: Implementation and Experiments
  • Solving k-means on High-Dimensional Big Data
  • On Balanced Separators in Road Networks
  • SALT. A Unified Framework for All Shortest-Path Query Variants on Road Networks
  • On the Quadratic Shortest Path Problem
  • A Solution Merging Heuristic for the Steiner Problem in Graphs Using Tree Decompositions

データマイニング

ACM SIGKDD Conference on Knowledge Discovery and Data Mining

KDD 2003

  • Mining distance-based outliers in near linear time with randomization and a simple pruning rule
    • 外れ値検出割りと成功してる
    • 入れ子ループで最悪自乗な手法
    • データがランダムオーダーで枝刈り入れるとだいたい線形
  • Inverted matrix: efficient discovery of frequent items in large datasets in the context of interactive mining
    • アソシエーション分析: 商品間の関連性の分析とかそういう
    • ディスクベースの手法
  • Algorithms for estimating relative importance in networks
    • いくつかの頂点を基準とした関連
    • いろんな基準を入れた手法をつくったよ
    • テロリストネットワークとか，共同研究とか
  • CloseGraph: mining closed frequent graph patterns
    • グラフgがclosed: 真のgのsupergraphで，同じsupport(なぞすぎた？)のが無い
  • Finding recent frequent itemsets adaptively over online data streams
    • 昔の出現は割り引かれる 枝刈り？
  • Natural communities in large linked networks
    • コミュニティがどう変化すんの
    • ちょっとの摂動では変化が無い方がいい
  • Graph-based anomaly detection
    • Regularityの計算手法を使って異常検出
    • ↑がNAZO

KDD 2004

  • Approximating a collection of frequent sets
    • 出力も超大きかったりする
    • 頻出のアイテム集合のCollectionをk個の集合で「近似」
  • Fast discovery of connection subgraphs
    • connection subgraph: 2頂点間の関係をよくとらえた部分グラフ
    • 電気回路的な類推でよさ気な定義して，高速手法
  • Cyclic pattern kernels for predictive graph mining
    • 閉路と木のパターンでカーネル関数？
      • 頻度には依存しない
    • 頻出パターンに基づくグラフカーネルより良い性能
  • Mining the space of graph properties
    • 特定の性質を満たす頂点が～とかが類似度の基準とかで使われる
    • ↑適切なのってどうすんの？
    • 性質のマイニングそのものの基礎的な枠組みを提案
    • グラフの性質の空間
  • Kernel k-means: spectral clustering and normalized cuts
    • Kernel k-meansとスペクトラルクラスタリングの関係
    • 色々書いてあるけ
  • SPIN: mining maximal frequent subgraphs from graph databases
    • 特定の部分グラフ数え上げとかやばめ
    • 「極大」なものにして出力サイズを小さくする
  • Mining scale-free networks using geodesic clustering
    • 測地線?みたいなのでモデル化
    • で，クラスタリングもする（謎

KDD 2005

  • On Mining Cross-Graph Quasi-Cliques
    • 問題定義は謎
    • 応用があるらしい
    • 生物学のデータセットで色々出てくる
  • Mining tree queries in a graph
    • 木っぽいパターンを見つける
    • 色々謎
  • ✔Graphs over time: densification laws, shrinking diameters and possible explanations
  • Mining closed relational graphs with connectivity constraints
    • 頻出する連結度の高いグラフを探し出す
  • Creating social networks to improve peer-to-peer networking
    • P2Pの効率を上げたい人
    • overlay networkの生成をいろいろ試したよ
  • Discovering frequent topological structures from graph datasets
    • topologicalなのが気になる
    • topological minorがベース
  • Evaluating similarity measures: a large-scale study in the orkut social network
    • 6つの類似度をメンバ推薦に使えるか比較
  • Building connected neighborhood graphs for isometric data embedding
    • 近傍グラフ
    • 最近傍が良いとは限らん
    • k-edge-connected neighborhood graphがある
      • 手法も色々ある
    • k-connected nrighborhood graphの手法を提案

KDD 2006

  • Group formation in large social networks: membership, growth, and evolution
  • NeMoFinder: dissecting genome-wide protein-protein interactions with meso-scale network motifs
  • Estimating the global pagerank of web communities
  • Frequent subgraph mining in outerplanar graphs
  • Measuring and extracting proximity in networks
  • Center-piece subgraphs: problem definition and fast solutions
  • Structure and evolution of online social networks
  • Sampling from large graphs
  • Coherent closed quasi-clique discovery from large dense graph databases

KDD 2007

  • Correlation search in graph databases
  • GraphScope: parameter-free mining of large time-evolving graphs
  • A spectral clustering approach to optimally combining numericalvectors with a modular network
  • A framework for community identification in dynamic social networks
  • SCAN: a structural clustering algorithm for networks

KDD 2008

  • ✔Influence and correlation in social networks
  • Efficient semi-streaming algorithms for local triangle counting in massive graphs
  • Feedback effects between similarity and social influence in online communities
  • The structure of information pathways in a social communication network
  • Microscopic evolution of social networks
  • Weighted graphs and disconnected components: patterns and a generator
  • Mobile call graphs: beyond power-law and lognormal distributions
  • Community evolution in dynamic multi-mode networks
  • Colibri: fast mining of large static and dynamic graphs
  • A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances

KDD 2010

  • Community Outliers and their Efficient Detection in Information Networks
  • Fast Euclidean Minimum Spanning Tree: Algorithm, Analysis, Applications
  • Inferring Networks of Diffusion and Influence

KDD 2011

  • Triangle Listing in Massive Networks and Its Applications

KDD 2012

  • A Structural Cluster Kernel for Learning on Graphs
  • Discovering Value from Community Activity on Focused Question-Answering Sites: A Case Study of Stack Overflow
  • Efficient Personalized PageRank with Accuracy Assurance
  • Fast Algorithms for Maximal Clique Enumeration with Limited Memory
  • Feature Grouping and Selection Over an Undirected Graph

KDD 2013

  • Efficient Single-Source Shortest Path and Distance Queries on Large Graphs
  • Clustered Graph Randomization: Network Exposure to Multiple Universes
  • Mining Frequent Graph Patterns with Differential Privacy
  • Maximizing Acceptance Probability for Active Friending in On-Line Social Networks

KDD 2014

  • ✔Representative Clustering of Uncertain Data
    • 代表的クラスタリングの集合を出力、真のクラスタリング結果とそれ程離れないように
  • Streamed Approximate Counting of Distinct Elements
    • Min-countやHyperLogLogよりも強い異なり数
  • ✔Correlation clustering in MapReduce
    • Ravi Kumar
  • Improving the modified nystrom method using spectral shifting
    • 正定値行列の近似手法だけど、更にナイスに、すごそう
  • Distance queries from sampled data: accurate and efficient
    • Edith Cohen、一般的な距離の推定手法
  • Improved Testing of Low Rank Matrices
    • 低ランクかを性質検査の枠組みで爆速判定
  • DeepWalk: Online Learning of Social Representations
  • Exponential random graph estimation under differential privacy
    • グラフモデリングがやられていないらしい
  • CatchSync: Catching Synchronized Behavior in Large Directed Graphs
    • Christos Faloutsos、やばめな奴らを探したい、Synchronized behaviorsが鍵らしい
  • ✔Scalable diffusion-aware optimization of network topology
    • LTの辺をどうにかする奴、優モジュラ
  • Who to Follow and Why: Link Prediction with Explanations
    • トピックが近いからなのか、共通の近傍が大きいからなのかを説明したいモデル
  • Community Detection in Graphs through Correlation
    • モジュラリティに基づくクラスタリングのresolution limitを解決したい
  • The interplay between dynamics and networks: centrality, communities, and cheeger inequality
  • Graph Sample and Hold: A Framework for Big-Graph Analytics
    • Graph Sample and Hold (gSH)、色んな性質を保ちたい、ストリームで
  • Using strong triadic closure to characterize ties in social networks
    • 各tieが強いか弱いかラベル付、Strong Triadic Closureを保つように

KDD 2015

  • Using Local Spectral Methods to Robustify Graph-Based Learning Algorithms
    • David Gleich, Michael Mahoney いわゆるラベル伝播法、グラフ構造に敏感、ある種の密化とかをすると良い
  • Panther: Fast Top-k Similarity Search on Large Networks
    • 基準も新しい類似頂点対検索、random path sampling
  • COSNET: Connecting Heterogeneous Social Networks with Local and Global Consistency
    • 複数のグラフに渡って、一貫性のあるマッチング的なのが欲しいの新しい問題を提案したよ
  • Edge-Weighted Personalized PageRank: Breaking A Decade-Old Performance Barrier
  • Adaptive Message Update for Fast Affinity Propagation
    • Yasuhiro Fujiwara、Affinity Propagationを爆速化
  • MASCOT: Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams
    • U Kang
  • Network Lasso: Clustering and Optimization in Large-Scale Graphs
    • Jure Leskovec、一般的な凸計画よりは少し特殊なクラスタリングや最適化に使えるネットワーク上の問題
  • Set Cover at Web Scale
  • TimeCrunch: Interpretable Dynamic Graph Summarization
    • Christos Faloutsos、要約として密な部分グラフを追跡したいです
  • Integrating Vertex-centric Clustering with Edge-centric Clustering for Meta Path Graph Analysis
    • meta path graph clustering
  • An Evaluation of Parallel Eccentricity Estimation Algorithms on Real-World Graphs
    • 並列しました
  • Improved Bounds on the Dot Product under Random Projection and Random Sign Projection
    • 理論的な結果を改善して、数値計算でみてみましたよ
  • ✔Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling
  • A Learning-based Framework to handle Multi-round Multi-party influence maximization on social networks
    • それっぽい感じ
  • Deep Graph Kernels

KDD 2016

  • Structured Doubly Stochastic Matrix for Graph Based Clustering
    • 二重確率行列のクラスタ構造は謎，後処理必要
    • 凸モデルで何かいい感じにする
  • ✔Approximate Personalized PageRank on Dynamic Graphs
    • Peter Lofgren
    • Forward Push: ソースから辺に沿って確率を押し流す
    • Reverse Push: ターゲットから辺を逆に沿って局所的変化を伝播
    • RP: ランダム辺モデルでの更新時間
    • FP: ちょい違う設定での更新時間
    • ついでに新しい双方向PPR推定アルゴリズム
  • Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs
    • グラフ同士の新しい類似関数を提案して，いい感じにストリームで検出する
  • Structural Neighborhood based Classification of Nodes in a Network
    • ランダムウォークを使うと，ノイズとかに強い分類が出来るらしい
  • Graph Wavelets via Sparse Cuts
    • Multiway cutsとかと関係がある，でヒューリスティック
    • ベクトル最適化問題で定式化していい感じに解ける
  • TRIEST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size
    • Eli Upfal
    • 辺追加削除のあるストリームグラフでのワンパスアルゴリズム
    • メモリ使用量が指定できる
  • ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages
    • ランダムサンプリング，道具:Rademacher averagesとpseudodimension
      • 統計的学習理論からの概念の最初の適用
    • めちゃ良い
  • Compact and Scalable Graph Neighborhood Sketching
    • Akiba-Yano
  • PTE: Enumerating Trillion Triangles On Distributed Systems
    • U Kang
    • 分散アルゴリズムで超頑張る，ClueWeb12まで動く
  • Asymmetric Transitivity Preserving Graph Embedding
    • ベクトル空間に埋め込む
    • u-vパスがあれば，u-v辺がありやすいってなってほしい
    • そういうのの一般化した奴を保つ埋め込みアルゴリズム
  • Robust Influence Maximization
    • Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou ポスター
  • Scalable Betweenness Centrality Maximization via Sampling
    • [Yoshida. KDD'14]の改善に相当
    • ちょっと解析もする
  • Reconstructing an Epidemic over Time
    • テンポラルネットワークが入力で，流れを復元したい
    • 既存研究は仮定が強すぎ
    • テンポラルSteiner木として定式化
  • Compressing Graphs and Indexes with Recursive Graph Bisection
    • reorderingで圧縮を改善する
    • reorderingは再帰的グラフbisectionベースアルゴリズムで解く
  • Scalable Pattern Matching over Compressed Graphs via Dedensification
    • デデン！
    • 高次数頂点が辛くて
    • 周囲を圧縮するためのテクを提案
  • Diversified Temporal Subgraph Pattern Mining
    • James Cheng
    • 応用: トレンド，ホットスポット
    • 分割統治でベースラインより早いお

KDD 2017

RESEARCH ORAL

  • Finding Structures of Large Matrices Through Compression
  • Local Higher-Order Graph Clustering
    • David Gleich & Jure Leskovec
  • FORA: Simple and Effective Approximate Single-Source Personalized PageRank
    • Xiaokui Xiao
  • Graph Edge Partitioning via Neighborhood Heuristic
  • metapath2vec: Scalable Representation Learning for Heterogeneous Networks
  • Weisfeiler-Lehman Neural Machine for Link Prediction
  • A Local Algorithm for Structure-Preserving Graph Cut
  • Network Inference via the Time-Varying Graphical Lasso
  • HyperLogLog Hyper Extended: Sketches for Concave Sublinear Frequency Statistics
    • Edith Cohen
  • Fast Enumeration of Large k-Plexes
  • struc2vec: Learning Node Representations from Structural Identity RESEARCH POSTER
  • DenseAlert: Incremental Dense-Subtensor Detection in Tensor Streams
  • Construction of Directed 2K Graphs
  • Revisiting power-law distributions in spectra of real world networks
    • David Gleich
  • Bolt: Accelerated Data Mining with Fast Vector Compression
  • PAMAE: Parallel k-Medoids Clustering with High Accuracy and Efficiency
  • When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks
  • Robust Spectral Clustering for Noisy Data
  • Unsupervised Feature Selection in Signed Social Networks
  • Statistical Emerging Pattern Mining with Multiple Testing Correction
    • Junpei Komiyama & Masakazu Ishihata

KDD 2018

  • Scalable k-Means Clustering via Lightweight Coresets
    • both multiplicative and additive errors
  • Graph Classification using Structural Attention
    • Ryan Rossi、小さくても重要な部分グラフに着目→雑音に強いよ
  • ✔FASTEN: Fast Sylvester Equation Solver for Graph Mining
    • Sylvester方程式; network alignment、頂点類似度、マッチング、…だけど二乗かかる
    • Krylov部分空間に落とす、線形時間・空間、厳密解
  • Network Connectivity Optimization: Fundamental Limits and Effective Algorithms
    • いつもの貪欲？
  • ✔Spectral Clustering of Large-scale Data by Directly Solving Normalized Cut
    • 二乗時間で直接解く、さらにそれを高速化、なんか分割する？
  • SpotLight: Detecting Anomalies in Streaming Graphs
    • 密グラフ抽出で今も頑張ってるっぽい
  • Optimal Distributed Submodular Optimization via Sketching
    • k-cover, set cover, 施設配置とか
  • Scalable Spectral Clustering Using Random Binning Features
    • 類似グラフと、固有分解を両方早くする、特徴の内積で計算、線形時間までに減る
  • Multi-Round Influence Maximization
    • Lichao Sun, Weiran Huang, Philip Yu, Wei Chen
    • 複数のラウンドでマーケティングできるよ、適応的・非適応的設定を考えるよ
  • EvoGraph: An Effective and Efficient Graph Upscaling Method for Preserving Graph Properties
    • グラフの性質を保ったまま、大きいグラフを作るよ！
  • Active Opinion Maximization in Social Networks
    • なんかそれっぽい問題
  • Quantifying and minimizing risk of conflict in social networks
    • あんまり分からない
  • ✔An Empirical Evaluation of Sketching for Numerical Linear Algebra
    • tremendous speedups for problems in randomized numerical linear algebra
    • めちゃくちゃ頑張って比較したっぽい
  • ✔Approximating the Spectrum of a Graph
    • 固有値が欲しいです。ランダム頂点、ランダム近傍クエリが与えられている、劣線形時間

KDD 2019

  • Adversarially Robust Submodular Maximization under Knapsack Constraints
  • Coresets for Minimum Enclosing Balls over Sliding Windows
  • Efficient Maximum Clique Computation over Large Sparse Graphs
  • Estimating Graphlet Statistics via Lifting
  • Exact-K Recommendation via Maximal Clique Optimization
  • Factorization Bandits for Online Influence Maximization
  • Mining Algorithm Roadmap in Scientific Publications
  • Network Density of States
  • Revisiting kd-tree for Nearest Neighbor Search
  • Tensorized Determinantal Point Processes for Recommendation

IEEE International Conference on Data Mining

ICDM 2001

  • A Min-max Cut Algorithm for Graph Partitioning and Data Clustering
  • Frequent Subgraph Discovery

ICDM 2002

  • Discovering Frequent Geometric Subgraphs
  • Computing Frequent Graph Patterns from Semistructured Data

ICDM 2003

  • A Fast Algorithm for Computing Hypergraph Transversals and its Application in Mining Emerging Patterns
  • Links Between Kleinberg's Hubs and Authorities, Correspondence Analysis, and Markov Chains

ICDM 2004

  • 無し

ICDM 2005

  • Shortest-Path Kernels on Graphs
  • Usage-Based PageRank for Web Personalization
  • Parallel Algorithms for Distance-Based and Density-Based Outliers

ICDM 2006

  • Adaptive Parallel Graph Mining for CMP Architectures
  • Biclustering Protein Complex Interactions with a Biclique Finding Algorithm
  • A Parameterized Probabilistic Model of Network Evolution for Supervised Link Prediction
  • Fast Random Walk with Restart and Its Applications
  • On the Lower Bound of Local Optimums in K-Means Algorithm
  • Pattern Mining in Frequent Dynamic Subgraphs
  • An Experimental Investigation of Graph Kernels on a Collaborative Recommendation Task
  • GraphRank: Statistical Modeling and Mining of Significant Subgraphs in the Feature Space
  • Detecting Link Spam Using Temporal Information
  • Mining Maximal Quasi-Bicliques to Co-Cluster Stocks and Financial Ratios for Value Investment
  • MARGIN: Maximal Frequent Subgraph Mining

ICDM 2007

  • ORIGAMI: Mining Representative Orthogonal Graph Patterns
  • Efficient Algorithms for Mining Significant Substructures in Graphs with Quality Guarantees
  • Community Learning by Graph Approximation
  • Binary Matrix Factorization with Applications
  • Recommendation via Query Centered Random Walk on K-Partite Graph
  • Trend Motif: A Graph Mining Approach for Analysis of Dynamic Complex Networks
  • An Efficient Spectral Algorithm for Network Community Discovery and Its Applications to Biological and Social Networks

ICDM 2008

  • Nonnegative Matrix Factorization for Combinatorial Optimization: Spectral Clustering, Graph Matching, and Clique Finding
  • Overlapping Matrix Pattern Visualization: A Hypergraph Approach
  • Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws
  • RTM: Laws and a Recursive Generator for Weighted Time-Evolving Graphs
  • Mining Large Networks with Subgraph Counting
  • Spotting Significant Changing Subgraphs in Evolving Graphs
  • Frequent Subgraph Retrieval in Geometric Graph Databases

ICDM 2009

  • Accurate Estimation of the Degree Distribution of Private Networks
  • A Linear-Time Graph Kernel
  • PEGASUS: A Peta-Scale Graph Mining System
  • Efficient Discovery of Frequent Correlated Subgraph Pairs
  • Algorithms for Large, Sparse Network Alignment Problems
  • SLIDER: Mining Correlated Motifs in Protein-Protein Interaction Networks
  • Effective Anomaly Detection in Sensor Networks Data Streams
  • Efficient Algorithm for Computing Link-Based Similarity in Real World Networks
  • Knowledge Discovery from Citation Networks
  • Parallel PathFinder Algorithms for Mining Structures from Graphs
  • Discovering Organizational Structure in Dynamic Social Network
  • Constraint-Based Pattern Mining in Dynamic Graphs
  • RING: An Integrated Method for Frequent Representative Subgraph Mining

ICDM 2010

  • Detecting Novel Discrepancies in Communication Networks
  • Multi-agent Random Walks for Local Clustering on Graphs
  • Clustering Large Attributed Graphs: An Efficient Incremental Approach
  • Subspace Clustering Meets Dense Subgraph Mining: A Synthesis of Two Paradigms
  • Patterns on the Connected Components of Terabyte-Scale Graphs
  • A Generalized Linear Threshold Model for Multiple Cascades
  • Visualizing Graphs Using Minimum Spanning Dendrograms
  • Node Similarities from Spreading Activation
  • On the Vulnerability of Large Graphs
  • Max-Clique: A Top-Down Graph-Based Approach to Frequent Pattern Mining

ICDM 2011

  • Overlapping Correlation Clustering
  • Mining Heavy Subgraphs in Time-Evolving Networks
  • D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy
  • Cross Domain Random Walk for Query Intent Pattern Mining from Search Engine Log
  • Minimizing Seed Set for Viral Marketing
  • Privacy Risk in Graph Stream Publishing for Social Network Data
  • Threshold Conditions for Arbitrary Cascade Models on Arbitrary Networks
  • Detecting Community Kernels in Large Social Networks
  • BibClus: A Clustering Algorithm of Bibliographic Networks by Message Passing on Center Linkage Structure
  • Secure Clustering in Private Networks
  • Fast and Robust Graph-based Transductive Learning via Minimum Tree Cut
  • Positive and Unlabeled Learning for Graph Classification
  • On the Hardness of Graph Anonymization
  • On the Hardness of Graph Anonymization
  • Entropy-Based Graph Clustering: Application to Biological and Social Networks
  • Scalable Diversified Ranking on Large Graphs
  • Distance Preserving Graph Simplification
  • Identities Anonymization in Dynamic Social Networks
  • Finding Communities in Dynamic Social Networks
  • A Study of Laplacian Spectra of Graph for Subgraph Queries

ICDM 2012

  • Spotting Culprits in Epidemics: How Many and Which Ones?
  • GUISE: Uniform Sampling of Graphlets for Large Graph Analysis
  • Diffusion of Information in Social Networks: Is It All Local?
  • Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles
  • Reconstructing Graphs from Neighborhood Data
  • Sequential Network Change Detection with Its Applications to Ad Impact Relation Analysis
  • Nested Subtree Hash Kernels for Large-Scale Graph Classification over Streams
  • Time Constrained Influence Maximization in Social Networks
  • Reliable Clustering on Uncertain Graphs
  • Profit Maximization over Social Networks
  • Community Preserving Lossy Compression of Social Networks
  • Risks of Friendships on Social Networks
  • Privacy-Preserving SimRank over Distributed Information Network
  • Defining and Evaluating Network Communities based on Ground-truth

ICDM 2013

  • Tree-Like Structure in Large Social and Information Networks
  • Subgraph Enumeration in Dynamic Graphs
  • Compression-Based Graph Mining Exploiting Structure Primitives
  • Spectral Subspace Clustering for Graphs with Feature Vectors
  • Blocking Simple and Complex Contagion by Edge Removal
  • Mining Evolving Network Processes
  • Forecasting Spatiotemporal Impact of Traffic Incidents on Road Networks
  • On Pattern Preserving Graph Generation
  • An Efficient Approach to Updating Closeness Centrality and Average Path Length in Dynamic Networks
  • External Evaluation of Topic Models: A Graph Mining Approach
  • How Many Zombies Around You?
  • Community Detection in Networks with Node Attributes
  • Graph Partitioning Change Detection Using Tree-Based Clustering
  • Sampling Heterogeneous Networks
  • On Anomalous Hotspot Discovery in Graph Streams
  • Structural-Context Similarities for Uncertain Graphs

ICDM 2014

  • Quick Detection of High-Degree Entities in Large Directed Networks
  • SNOC: Streaming Network Node Classification
  • Modeling Adoptions and the Stages of the Diffusion of Innovations
  • Locally Estimating Core Numbers
  • Multi-graph-view Learning for Graph Classification
  • Online Spectral Learning on a Graph with Bandit Feedback
  • Graph Summarization with Quality Guarantees
  • Flow-Based Influence Graph Visual Summarization
  • On Spectral Analysis of Signed and Dispute Graphs
  • Locally Estimating Core Numbers
    • 頂点から直径δの範囲しかもらえない設定っぽい？

ICDM 2015

  • Absorbing random-walk centrality: Theory and algorithms
    • Qについて中心的な（？）頂点集合Cを求めたい
    • 具体的に：Qからランダムウォークを開始して，Cに「吸収」されるまでの期待ステップ数最小化
    • 単調劣モジュラ
  • ✔Diamond Sampling for Approximate Maximum All-pairs Dot-product (MAD) Search
    • ベクトルの集合が２つ与えられる，内積の組を見つけよ
    • (i,j)を対応する内積に比例する確率で標本する
  • Towards Frequent Subgraph Mining on Single Large Uncertain Graphs
  • Top-k Reliability Search on Uncertain Graphs
  • Fast Parallel Mining of Maximally Informative k-Itemsets in Big Data
  • Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits
  • Top-k Link Recommendation in Social Networks
  • Monitoring Stealthy Diffusion
  • Controlling Propagation at Group Scale on Networks
  • Diamond Sampling for Approximate Maximum All-pairs Dot-product (MAD) Search
  • Efficient Graphlet Counting for Large Networks
  • Influential Sustainability on Social Networks short papers
  • Scalable Hypergraph Learning and Processing
  • Analysis of Spectral Space Properties of Directed Graphs using Matrix Perturbation Theory with Application in Graph Partition
  • Absorbing random-walk centrality: Theory and algorithms
  • Hierachies in directed networks
  • Measuring Large-Scale Dynamic Graph Similarity by RICom: RWR with Intergraph Compression

ICDM 2016

  • Mining Graphlet Counts in Online Social Networks
  • On Dense Subgraphs in Signed Network Streams
  • Waddling Random Walk: Fast and Accurate Mining of Motif Statistics in Large Graphs
  • Random Walk with Restart over Dynamic Graphs
  • Time Series Motifs: Exploiting a Novel Algorithm and GPUs to break the one Hundred Million Barrier
  • Edge Weight Prediction in Weighted Signed Networks
    • Christos Faloutsos
  • shortpapers
  • Fractality of Massive Graphs: Scalable Analysis with Sketch-Based Box-Covering Algorithm
  • Cut Tree Construction from Massive Graphs
  • Personalized Ranking in Signed Networks using Signed Random Walk with Restart
    • U Kang
  • Faster Kernels for Graphs with Continuous Attributes via Hashing
  • Towards Scalable Network Delay Minimization
  • Toward Time-Evolving Feature Selection on Dynamic Networks

ICDM 2017

  • Benchmark Generator for Dynamic Overlapping Communities in Networks
  • AnySCAN: An Efficient Anytime Framework with Active Learning for Large-scale Network Clustering
  • GANG: Detecting Fraudulent Users in Online Social Networks via Guilt-by-Association on Directed Graphs
  • Revisiting Spectral Graph Clustering with Generative Community Models
  • Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs
  • Improving I/O Complexity of Triangle Enumeration
  • MNE: Emerging Network Embedding with Aligned Autoencoder
  • Scalable and Adaptive Algorithms for the Triangle Interdiction Problem on Billion-Scale Networks
  • Data-Driven Immunization
  • Edge-Based Wedge Sampling to Estimate Triangle Counts in Very Large Graphs
  • WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams
  • HitFraud: An Efficient Approach for Collective Fraud Detection in Heterogeneous Information Networks
  • Fast Compressive Spectral Clustering
  • iNEAT: Incomplete Network Alignment
  • Dynamic Propagation Rates: New Dimension to Viral Marketing in Online Social Networks
  • Effective Large-Scale Online Influence Maximization
  • ✔Spectral Lens: Explainable Diagnostics, Tools and Discoveries in Directed, Weighted Graphs
  • Local Community Detection in Dynamic Networks

European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases

ECML PKDD 2015

  • Fast Inbound Top-K Query for Random Walk with Restart
  • Finding Dense Subgraphs in Relational Graphs
  • Clustering Boolean tensors

SIAM International Conference on Data Mining

SDM 2004

  • Finding Frequent Patterns in a Large Sparse Graph
  • R-MAT: A Recursive Model for Graph Mining
  • Principal Component Analysis and Effective K-Means Clustering

SDM 2005

  • Clustering with Constraints: Feasibility Issues and the k-Means Algorithm
  • A Spectral Clustering Approach To Finding Communities in Graph
  • Mining Behavior Graphs for "Backtrace" of Noncrashing Bugs

SDM 2006

  • K-Means Clustering Over a Large, Dynamic Network
  • Clustering in the Presence of Bridge-Nodes
  • Risk-Sensitive Learning via Expected Shortfall Minimization
  • Mining Minimal Contrast Subgraph Patterns

SDM 2007

  • Clustering by weighted cuts in directed graphs
  • Less is More: Compact Matrix Decomposition for Large Sparse Graphs
  • Robust, Complete, and Efficient Correlation Clustering
  • Patterns of Cascading Behavior in Large Blog Graphs
  • Dynamic Algorithm for Graph Clustering Using Minimum Cut Tree

SDM 2008

  • Clustering from Constraint Graphs
  • The PageTrust Algorithm: How to rank web pages when negative links are allowed?
  • Statistical Density Prediction in Traffic Networks
  • Spatial Scan Statistics for Graph Clustering
  • Proximity Tracking on Time-Evolving Bipartite Graphs
  • Randomizing Social Networks: a Spectrum Preserving Approach

SDM 2009

  • FutureRank: Ranking Scientific Articles by Predicting their Future PageRank
    • 論文のランキング
      • 引用ネットワークは日々進化
    • 将来的なのが気になる→将来のPageRank
    • 共著ネットワークと公開時刻も利用
  • On Randomness Measures for Social Networks
    • ちょっとランダム性がある
    • 非ランダム性の測り方
      • 辺単位，グラフ全体でも
  • Randomization Techniques for Graphs
    • よく分からん
  • Detecting Communities in Social Networks Using Max-Min Modularity
    • Max-Min Modularityが新しいらしい
    • 階層的クラスタリング
  • Top-k Correlative Graph Mining
    • クエリグラフの出現分布が似ていると関係がある
    • 効率的な関係性のチェック，枝刈り，候補の探索

SDM 2010

  • Reconstructing Randomized Social Networks
    • グラフGと特徴ベクトルF
    • 匿名化や雑音によってG'とF'に変化
    • ある乱択手法（どういう過程かわかってる
    • 元に戻せる？
  • Reconstruction from Randomized Graph via Low Rank Approximation
    • 辺がごちゃごちゃにされたグラフから再構築
    • 低rank近似
  • GraSS: Graph Structure Summarization
    • 色々な要因で要約したい
    • ランダムワールドモデル(?)
    • クエリにも答えられる
  • Mining Frequent Graph Sequence Patterns Induced by Vertices
    • グラフ列で頻繁なパターンをとってきたい
    • 鷲尾研
  • On Clustering Graph Streams
    • アプローチ: hash-compressed micro-clusters
  • Inferring Probability Distributions of Graph Size and Node Degree from Stochastic Graph Grammars
    • 確率的グラフ
    • 頂点・辺・密度の確率質量関数
    • Graph grammarsとは？？？
  • Direct Density Ratio Estimation with Dimensionality Reduction
    • 杉山先生

SDM 2011

  • The Network Completion Problem: Inferring Missing Nodes and Edges in Networks
    • 期待値最大化の枠組
    • leskovec
  • Centralities in Large Networks: Algorithms and Observations
    • 媒介・近接は計算難しい
    • よさ気な中心性を定義，計算
  • Large Scale Graph Mining and Inference for Malware Detection
    • 信念伝播法的な
    • CMUとSymantecの共同研究
  • Non-Negative Residual Matrix Factorization with Application to Graph Anomaly Detection
    • そういうの
  • Kernel-based Similarity Search in Massive Graph Databases with Wavelet Trees
    • ラベル付きグラフの類似性
      • XML，化合物
    • 共通する部分構造の数で類似度
    • k個以上共通するとか欲しい
    • Wavelet treesでGrossi et al., SODA’03
    • たべいさん
  • Clustered low rank approximation of graphs in information science applications
    • クラスタリングして，各クラスタをいろんな方法で近似
      • 特異値分解とか
  • Towards Community Detection in Locally Heterogeneous Networks
    • グラフ上の振舞が一様だと思ってるのが駄目，大域的なコミュニティの欠点
    • 局所的簡潔性という性質
  • On Classification of Graph Streams
    • メモリ内に要約みたいなものを確率的に作る
    • 2次元ハッシュ空間で特徴的なパターンを見つける
    • 理論的に質？の保証

SDM 2012

  • Symmetric Nonnegative Matrix Factorization for Graph Clustering
    • NMF+頂点間の類似度を持つ(?)のでクラスタリングが良い？
  • Multi-skill Collaborative Teams based on Densest Subgraphs
    • 頂点には複数のスキル，辺重みは類似とか共同適合性
    • 入力: データベース専門3人，理論専門2人
    • ↑の条件で共同研究の適合性が高い人を見つけたい
    • 3-近似アルゴリズム
  • Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model
    • 競合相手の情報伝播をブロック
    • LDAGの拡張（Wei Chen
    • 似たの無かったっけ？
  • A Framework for the Evaluation and Management of Network Centrality
    • 経路数ベースの中心性の一般的に定義
    • それの最適化問題k辺とるとか
  • Structural Analysis in Multi-Relational Social Networks
    • 一般化Stochastic Block Models
    • 関係の予測？
  • Fast Random Walk Graph Kernel
    • O(n^3)/O(m^2)時間
    • low rank活用？ O(n^2)/O(m)時間
  • Global Linear Neighborhoods for Efficient Label Propagation
    • ラベルがないなら伝播するよってのが上手く言っていた前から
    • 重みつき近傍がよさ気だった
    • 大域的線形近傍を捉えるために非負low-rankグラフを学習？？？？
  • A Tree-Based Kernel for Graphs
    • 木ベースの新しいグラフカーネル
    • 順序ずけられたDAGに分解
  • The Similarity Between Stochastic Kronecker and Chung-Lu Graph Models
    • Stochastic Kronecker Graphsの性質は謎
      • Graph500とかでも使われてる
    • Chung-Luが似てるよって示すよ
      • CLはfit?しやすい
  • WIGM: Discovery of Subgraph Patterns in a Large Weighted Graph
    • 重み付きグラフでマイニング
    • 重みに閾値がついて部分グラフ抽出
    • 重みtop-kのパターン

SDM 2013

  • Dynamic Community Detection in Weighted Graph Streams
    • 何かごちゃごちゃしてる，タイトルの通り
  • DELTACON: A Principled Massive-Graph Similarity Function
    • Q. グラフがどのくらい変わった？脳のネットワークの違いは？
    • グラフ類似度関数に望ましい性質を提言
    • でアルゴリズム
  • Shattering and Compressing Networks for Betweenness Centrality
    • 圧縮して砕く枠組み
      • 近似やばそう（感想
  • Fractional Immunization in Networks
    • 必ず免疫化できるとは限らない
      • 隔離しかできないとか？
    • 分数的な
    • 線形時間アルゴリズム

SDM 2014

  • A Deep Learning Approach to Link Prediction in Dynamic Networks
    • transition variance (?)をベースに，あと，局所的近傍の影響でりんく予測
  • Local Learning for Mining Outlier Subgraphs from Network Datasets
    • 怪しげな部分グラフを検知したい
    • 線形最適化として
  • Triangle counting in streamed graphs via small vertex covers
    • 乱択
    • いろんなグラフで頂点被覆が小さい（そうなの？）
    • 4パス，辺当たり定数時間
  • Laplacian Spectral Properties of Graphs from Random Local Samples
    • 固有値スペクトラムと局所的(?)部分グラフの構造間の関係
    • 性質を求める手法

SDM 2015

  • A Divide-and-Conquer Algorithm for Betweenness Centrality
    • 媒介中心性の厳密計算は[Brandes. 2001]がこれまで最速
    • グラフのスケッチを使った手法
    • 部分グラフを簡単な構造のグラフに置き換える
    • 超速い
  • Cheetah: Fast Graph Kernel Tracking on Dynamic Graphs
    • グラフカーネル：グラフの類似尺度に使える
    • 固有分解／隣接行列のSVDを逐次的に更新する
    • sub-linearにスケール
  • Community Detection for Emerging Networks
    • Community
    • 新しい近接尺度intimacyを提案
    • （謎）
  • Dropout Training of Matrix Factorization and Autoencoder for Link Prediction in Sparse Graphs
    • 教師なし学習：Matrix factorizationとAutoencoder
    • 疎グラフのリンク予測に使う
    • MFとAEを両方使うよ
  • Efficient Algorithms for a Robust Modularity-Driven Clustering of. Attributed Graphs
    • Modularityベースのクラスタリング
    • 頂点には追加の属性がある
    • 無関係の属性や外れ値に関するクラスタリングのmodularityベースの手法（？）
  • Fast Mining of a Network of Coevolving Time Series
    • Coevolving(共進化)
    • 環境監視，ネットワークトラフィック監視，モーションキャプチャとか
    • 動的Contextual（文脈上の）行列分解アルゴリズム
  • Functional Node Detection on Linked Data
  • Hidden Hazards: Finding Missing Nodes in Large Graph Epidemics
    • 雑音がある／標本したグラフ上の感染のスナップショットがある
    • 真に感染してる紛失した頂点を復元できるか？
    • どこから始まったか？
    • MDLで考える
  • Modeling Users' Adoption Behaviors with Social Selection and Influence
    • ユーザの意思決定に作用するのはsocial selection/influence
    • (1) ユーザレベルの意思決定に↑がどう枠割を果たすのか？
    • (2) そういう要素がモデリング・予測に役立つのか？
    • モデル作るよ
  • ✔Reducing the spectral radius to control epidemic spread
    • スペクトル半径は大事だよ
    • SISモデルとかでは半径が大事なパラメータ
    • 半径を弄って感染を操作したい
    • 辺を削除して半径を抑える
    • O(log^2 n)近似
    • 主双対アルゴリズム O(log n)近似
  • Spectral Embedding of Signed Networks
    • そのまんま，既存の手法には問題が有るらしい
  • Tensor Spectral Clustering for Partitioning Higher-order Network Structures
    • スペクトラルな手法は一次Markov chainに基づく
    • 高次な△，閉路は利用してない
    • ↑を何か上手く使う
  • Vertex Clustering of Augmented Graph Streams
    • グラフストリームでクラスタリング
    • 構造的＋属性に関する類似尺度利用
    • クラスタ数が必要ない

SDM 2017

  • ✔A Dual-tree Algorithm for Fast k-means Clustering with Large k
    • k-meansの反復をO(N+klogk)に高速化、Lloyd'sと同結果、cover tree
  • Adaptive Local Exploration of Large Graphs
    • 可視化、インタラクティブにやるっぽい
  • Community-aware network sparsification
    • コミュニティも入力される疎化問題、構造を保持する
  • ✔Condensing Temporal Networks using Propagation
    • （時間幅も頂点も）凝縮する、影響最大化への応用（KDD'14の後続っぽい）
  • Finding low-tension communities
  • Graph-based semi-supervised learning for relational networks
  • ✔HiDDen: Hierarchical Dense Subgraph Detection with Application to Financial Fraud Detection
    • 階層的に粒度を変えて密部分グラフを見つけたい、最急降下法、金融詐欺に対する面白げなパターン
  • MeiKe: Influence-based Communities in Networks
    • 影響力が高いkernel nodeと、橋渡しのmedia nodeを見つけたい
  • ✔Multimodal Network Alignment
    • David F. Gleich、応用として非匿名化に使える
  • Near Optimal and Practical Algorithms for Graph Scan Statistics
    • スキャン統計なるものがあるらしく、それに対する良い感じの手法
  • Sensitivity of Community Structure to Network Uncertainty
  • Subnetwork Mining with Spatial and Temporal Smoothness

Pacific-Asia Conference on Knowledge Discovery and Data Mining

ソーシャルネットワーク

IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

ASONAM 2014

  • "Can you really trust that seed?": Reducing the Impact of Seed Noise in Personalized PageRank
    • PPRはシードが不安定だとランキングがおかしくなる
    • ちょっと辺でも大丈夫な頑健版を作ったよ

ACM Conference on Online Social Networks

International Conference on Computational Social Networks

データベース

ACM SIGMOD International Conference on Management of Data

SIGMOD 2003

  • Spectral Bloom Filters

SIGMOD 2004

  • Online Maintenance of Very Large Random Samples
  • Graph Indexing: A Frequent Structure-based Approach

SIGMOD 2005

  • Substructure Similarity Search in Graph Databases

SIGMOD 2006

  • 無し

SIGMOD 2007

  • Fast and practical indexing and querying of very large graphs
  • Fg-index: towards verification-free query processing on graph databases

SIGMOD 2008

  • Graph summarization with bounded error
  • Mining significant graph patterns by leap search
  • CSV: visualizing and mining cohesive subgraphs
  • Efficient aggregation for graph summarization
  • Efficiently answering reachability queries on very large directed graphs
  • Minimization of tree pattern queries with constraints

SIGMOD 2009

  • Monitoring path nearest neighbor in road networks
  • 3-HOP: a high-compression indexing scheme for reachability query

SIGMOD 2010

  • TEDI: efficient shortest path query answering on graphs
  • GBLENDER: towards blending visual query formulation and query processing in graph databases
  • Computing label-constraint reachability in graph databases
  • Pregel: a system for large-scale graph processing
  • Finding maximal cliques in massive networks by H*-graph
  • K-isomorphism: privacy preserving network publication against structural attacks
  • Towards proximity pattern mining in large graphs
  • GAIA: graph classification using evolutionary computation
  • Finding maximum degrees in hidden bipartite graphs
  • Connected substructure similarity search

SIGMOD 2011

  • Neighborhood-privacy protected shortest distance computing in cloud
  • On k-skip shortest paths
  • Finding shortest path on land surface
  • Neighborhood based fast graph search in large networks
  • A memory efficient reachability data structure through bit vector compression
  • Incremental graph pattern matching
  • Assessing and ranking structural correlations in graphs

SIGMOD 2012

  • Managing large dynamic graphs efficiently
  • Query preserving graph compression
  • SCARAB: scaling reachability computation on large graphs
  • A highway-centric labeling approach for answering distance queries on large sparse graphs
  • Efficient processing of distance queries in large graphs: a vertex cover approach
  • Towards effective partition management for large graphs
  • TreeSpan: efficiently computing similarity all-matching

SIGMOD 2013

  • I/O efficient: computing SCCs in massive graphs
  • TF-Label: a topological-folding labeling scheme for reachability querying in a large graph
  • Efficiently computing k-edge connected components via graph decomposition
  • Online search of overlapping communities
  • Massive graph triangulation
  • TurboISO: towards ultrafast and robust subgraph isomorphism search in large graph databases
  • Fast exact shortest-path distance queries on large networks by pruned landmark labeling
  • Efficient ad-hoc search for personalized PageRank
    • NTT研
  • A direct mining approach to efficient constrained graph pattern discovery
  • Shortest path and distance queries on road networks: towards bridging theory and practice

SIGMOD 2014

  • HYDRA: large-scale social identity linkage via heterogeneous behavior modeling
    • 異なるソーシャルメディア間での関係を同定したい
  • Influence maximization: near-optimal time complexity meets practical efficiency
  • Efficient algorithms for optimal location queries in road networks
    • 顧客とサーバがどっかにある
    • 各顧客のコスト（最近サーバまでの距離）の最大値を最小化したい
    • 施設配置問題の変種っぽい何か
  • Scalable similarity search for SimRank
    • uからSimRankがtop-kの頂点vをとってくる
  • Efficient cohesive subgraphs detection in parallel
    • k-trussを並列で計算，爆速
  • Parallel subgraph listing in a large-scale graph
    • 何か頑張ってる
  • OPT: a new framework for overlapped and parallel triangulation in large-scale graphs
    • disk-based
  • Scalable big graph processing in MapReduce
  • The pursuit of a good possible world: extracting representative instances of uncertain graphs
    • Yahoo! B
  • Navigating the maze of graph analytics frameworks using massive graph datasets
  • Local search of communities in large graphs
  • Mining statistically significant connected subgraphs in vertex labeled graphs
  • Fast and unified local search for random walk based k-nearest-neighbor query in large graphs
  • Answering top-k representative queries on graph databases
  • Querying k-truss community in large and dynamic graphs
  • Reachability queries on large dynamic graphs: a total order approach
  • Localizing anomalous changes in time-evolving graphs
  • Tracking set correlations at large scale
  • Tripartite graph clustering for dynamic sentiment analysis on social media

SIGMOD 2015

  • GetReal: Towards Realistic Selection of Influence Maximization Strategies in Competitive Networks
  • ✔BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs
    • Random Walk with Restartの計算
    • 隣接行列をreorder 逆行列を取りやすい？
    • Schur補行列
    • クエリに対してブロック対角化
  • Community Level Diffusion Extraction
  • Divide & Conquer: I/O Efficient Depth-First Search
    • グラフを分割してDFSしてマージ
  • ✔Efficient Enumeration of Maximal k-Plexes
  • Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates
    • 具体的なNN関数が無い
    • それでもよさ気な候補が欲しい
    • いろんなNN関数を分類
  • Exact Top-k Nearest Keyword Search in Large Networks
  • Updating Graph Indices with a One-Pass Algorithm
  • ✔The Minimum Wiener Connector Problem
    • Wiener index=頂点対の最短距離の総和
    • クエリ頂点を連結しつつWiener indexが最小の部分グラフ
    • 基本NP-hard
    • O~(|Q||E|)時間，定数近似
  • Real-Time Multi-Criteria Social Graph Partitioning: A Game Theoretic Approach
    • ゲーム理論的枠組を押してる
    • 各ユーザがその目的関数を最適化
  • Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity
    • 頂点集合qに対して連結度最大のSteiner成分
    • これをオンラインで解く
  • Efficient Route Planning on Public Transportation Networks: A Labelling Approach

SIGMOD 2016

  • ✔Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms
    • Laks V.S. Lakshmanan
    • local: 各辺がk-2以上の△に含まれる確率がγ以上、動的計画法
    • global: k-trussを確率γ以上で含む、サンプリング
  • Efficient and Progressive Group Steiner Tree Search
    • Group Steiner Treeを、（アルゴリズムの終了まで待たず）進歩的に解を計算していくアルゴリズム
  • Publishing Attributed Social Graphs with Formal Privacy Guarantees
  • Publishing Graph Degree Distribution with Node Differential Privacy
  • Privacy Preserving Subgraph Matching on Large Graphs in Cloud
  • ✔Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks
    • TIM+やIMMより高性能（と謳う）影響最大化アルゴリズム
  • Continuous Influence Maximization: What Discounts Should We Offer to Social Network Users?
  • Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models
    • 新しいモデルっぽい？
  • Diversified Top-k Subgraph Querying in a Large Graph
    • クエリグラフに同型で沢山の頂点を被覆して欲しい
    • 色々頑張って高速化
  • Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs
  • Efficient Subgraph Matching by Postponing Cartesian Products
  • DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine
    • ディスクベース、並列で頑張る
  • Distributed Set Reachability
  • Graph Stream Summarization: From Big Bang to Big Crunch
  • SLING: A Near-Optimal Index Structure for SimRank

SIGMOD 2017

  • Distributed Algorithms on Exact Personalized PageRank
    • 分散でPageRank厳密計算
  • DAG Reduction: Fast Answering Reachability Queries
  • Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative
    • 後悔比最小化問題を解く、2次元なら厳密、高次元で効率的近似
  • ✔Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs
    • 頻出部分グラフマイニングに使うサポートの新しい定義2つを与えた
  • ✔Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling
    • 色々なreduction ruleを入れて、線形時間でも良い独立集合を計算するよ！
    • 何処かで見たような…。
  • Parallelizing Sequential Graph Computations
    • GRAPEっていう並列システムらしい…。
  • Incremental Graph Computations: Doable and Undoable
    • 逐次的に必要な部分だけで計算できますか？
    • 色々調べる→あんまり良くない
    • localizable & bounded
  • Extracting and Analyzing Hidden Graphs from Relational Databases
    • 関係データベースから*隠れた*グラフを抽出するとメモリとか時間とかが辛い
    • いい感じに扱うよ！
  • ✔BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart
    • 高速、メモリ効率、スケーラブルな手法
    • 前処理時間が100倍高速、クエリ時間が7倍高速
  • Landmark indexing for scalable evaluation of label-constrained reachability queries
    • Lucien Valstar, George H. L. Fletcher and Yuichi Yoshida
    • 辺ラベル部分集合だけに制限した到達可能性
    • ランドマークベースの索引手法
  • A General-Purpose Counting Filter: Making Every Bit Count
    • Bloom filter, quotient filter, cuckoo filter
    • 削除が出来なかったり、頻度が分からなかったり→頑張りました
  • QuadrillionG: A Quadrillion-scale Synthetic Graph Generator using a Recursive Vector Model
    • ディスクベースで、RMAT／Kroneckerを生成、*Quadrillion-scale*は理論値（じゃ書くなや）
  • Distance Oracle on Terrain Surface
    • 地形表面; 厳密計算は難しいので、基本は近似
  • Dynamic Density Based Clustering
    • DBSCANとその近似を動的な設定で色々調査するよ

IEEE International Conference on Data Engineering

ICDE 2007

  • ✔Discriminative Frequent Pattern Analysis for Effective Classification
    • 絶妙な頻度の頻出パターンを得る方法、パターンをいい感じに生成出来る

ICDE 2009

  • ApproxRank: Estimating Rank for a Subgraph
  • Continuous Subgraph Pattern Search over Graph Streams
  • STAR: Steiner-Tree Approximation in Relationship Graphs

ICDE 2010

  • TASM: Top-k Approximate Subtree Matching
  • Top-K aggregation queries over large networks
  • Probabilistic Top-k query processing in distributed sensor networks
  • Finding top-k maximal cliques in an uncertain graph
  • Discovery-driven graph summarization
  • Anonymizing weighted social network graphs

ICDE 2011

  • Efficient Core Decomposition in Massive Networks
  • Mining Large Graphs: Algorithms, Inference, and Discoveries
  • Spectrum Based Fraud Detection in Social Networks
    • privacy
  • Decomposing DAGs into Spanning Trees: A New Way to Compress Transitive Closures
    • query proc.
  • Efficient Spectral Neighborhood Blocking for Entity Resolution
    • data mining
  • Consensus Spectral Clustering;
    • data mining
  • A New, Highly Efficient, and Easy To Implement Top-Down Join Enumeration Algorithm
    • best paper

ICDE 2012

  • An Efficient Graph Indexing Method
  • Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks
  • Community Detection with Edge Content in Social Media Networks
  • Efficient Graph Similarity Joins with Edit Distance Constraints

ICDE 2013

  • SociaLite: Datalog Extensions for Efficient Social Network Analysis
  • LinkProbe: Probabilistic Inference on Large-Scale Social Networks
  • Towards Efficient SimRank Computation on Large Graphs
  • Link Prediction across Networks by Biased Cross-Network Sampling
  • FERRARI: Flexible and Efficient Reachability Range Assignment for Graph Indexing
  • Top-k Graph Pattern Matching over Large Graphs
  • gIceberg: Towards Iceberg Analysis in Large Graphs
  • Efficient Search Algorithm for SimRank

ICDE 2014

  • A General Algorithm for Subtree Similarity-Search
    • クエリ木Qと木の集合Γに対してQに最も似ている部分木を見つける
    • 類似度はtree distanceで定義
    • 半順序木にも使える手法
  • Efficient Top-K Closeness Centrality Search
  • Contract & Expand: I/O Efficient SCCs computing
    • メモリに入らないグラフのSCCを計算したい
  • ✔Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive Stratified Sampling
    • 期待値クエリ評価と閾値クエリ評価を提案
    • Monte-Carloを避けたいのでestimatorを提案，階層的な標本
    • cut-set basedなestimator
    • 影響力評価と期待信頼距離クエリに応用
  • ✔Subgraph Pattern Matching over Uncertain Graphs with Identity Linkage Uncertainty
    • probabilistic entity graph (PEG)
    • 部分グラフパターンマッチング
  • Multi-Cost Optimal Route Planning under Time-Varying Uncertainty
    • 旅行時間や温室効果ガスとかのコストは時間に依存するし不確実
    • 道路ネットワークで，multi-cost, time-dependent, uncertain GPSデータを元に
    • 開始時間と開始・終了頂点が入力で最適経路を計算
  • ✔Fast Incremental SimRank on Link-Evolving Graphs
    • 既存は特異値分解 O(r^4 n^2)
    • 逐次的更新のためにシルベスター行列とか使う
    • 枝刈りを入れる
  • Geometry Approach for k-Regret Query
    • top-kやskylineはダメなので，k-regret queryを考える
    • 幾何的な考察をもとに，happy pointsなる点を同定する
    • 既存のものよりめっちゃ高速

ICDE 2015

  • Finding Dense and Connected Subgraphs in Dual Networks
    • 物理・概念の世界を表す2つのグラフ
    • ↑で連結↑で高密度
    • NP-hard
  • Multi-Constrained Graph Pattern Matching in Large-Scale Contextual Social Graphs
    • Contextual Social Graphs
  • ✔Multicore Triangle Computations Without Tuning
    • マルチコアを活かしきれてない
    • cache-friendly OpenMPとかで実装可能
    • G頂点
  • Preserving Privacy in Social Networks Against Connection Fingerprint Attacks
    • 新しいprivacy attack モデル
  • Real Time Personalized Search on Social Networks
    • データベースっぽい
    • 頻繁な更新とスモールワールド性を活かせてない
    • 索引構造とグラフ上の関係性
  • Quick-Motif: An Efficient and Scalable Framework for Exact Motif Discovery
    • 配列データベース
    • 関連ある部分列の組を見つけたい
    • 2段階の手法（前処理）
  • Size-Constrained Weighted Set Cover
    • Weighted Set CoverとMaximum Coverageの一般化(?)
    • 入力: T, Cost:T→R>=0，k，s^
    • S⊆T (|S|≦k)であって，
    • |∪s Ben(s)|≧s^|T|かつΣs Cost(s)が最小
  • The Safest Path via Safe Zones
    • safe zoneが与えられるので，"safe以外を通る距離"を最小化したい
    • プロコンぽい？
  • ✔Scalable SimRank Join Algorithm
    • Takanori Maehara, Mitsuru Kusumoto, Ken-ichi Kawarabayashi
    • uに対するSimRank top-kの頂点をとってくる
    • 線形っぽく，酔歩ベース，局所領域だけ，上限を使って枝刈り
    • G辺にスケール
  • Diversified Top-K Clique Search
    • top-kは重複しててツマラン
    • top-kが全体をcoverして欲しい
    • 極大クリーク列挙は辛い→top-kだけ保持しておく
    • 近似比
  • VENUS: Vertex-Centric Streamlined Graph Computation on a Single PC
    • ディスクベースシステム，安価なPCで
  • On Random Walk Based Graph Sampling
    • Rong-Hua Li, Jeffrey Xu Yu, Lu Qin, Rui Mao, Tan Jin
    • 今までのサンプリング手法（3つ）は良くない
    • 新手法2つ
  • Making Pattern Queries Bounded in Big Graphs
    • Qのパターンマッチング．GでなくG_Qだけ見れば良いようにしたい
  • A Tale of Three Graphs: Sampling Design on Hybrid Social-Affiliation Networks
    • 一つのグラフをサンプリングするんだけど，実世界のは付随した他のグラフがある
    • それを利用すると連結になってサンプリングしやすい
  • Asymmetric Structure-Preserving Subgraph Queries for Large Graphs
    • subgraph isomorphism ムズイ
    • 強力なマシンに外注→信頼性がないので秘匿したい
  • Linear Path Skylines in Multicriteria Networks
    • ちょっとSkylineとは違う？
  • Dynamic Interaction Graphs with Probabilistic Edge Decay
    • 動的相互作用を扱う，確率的減衰で
  • HaTen2: Billion-scale Tensor Decompositions
    • Inah Jeon, Evangelos E. Papalexakis, U Kang, Christos Faloutsos
    • テンソル分解，MapReduce，疎性利用
  • Bump hunting in the dark: Local discrepancy maximization on graphs
    • クエリQに対し連結部分グラフCを出力
    • |Q∩C|を多く，|C＼Q|を少なくしたい
    • 2つのアクセスモデル
    • ヒューリスティクスを実験で
  • Network Motif Discovery: A GPU Approach
    • そのまんま，motifはランダムグラフ上の出現頻度より多いよ考える
  • Convex Risk Minimization to Infer Networks from Probabilistic Diffusion Data At Multiple Scales
    • SEIRモデルの辺の推定
    • 頂点の状態情報だけ，不完全でもOK
  • ✔Mining Maximal Cliques from an Uncertain Graph
    • α-maximal clique数え上げ
    • それの出現確率がα以上，一つでも足すとα未満になる

ICDE 2016

  • Reverse Top-k Neighborhood Pattern Queries
  • Revenue Maximization by Viral Marketing: A Social Network Host's Perspective
  • Minfer: A Method of Inferring Motif Statistics From Sampled Edges
  • SimRank Computation on Uncertain Graphs
  • BlackHole: Robust Community Detection Inspired by Graph Drawing
  • Scalable Supergraph Search in Large Graph Databases
  • I/O Efficient Core Graph Decomposition at Web Scale
  • Reverse Nearest Neighbor Heat Maps: A Tool for Influence Exploration
  • Reachability and Time-Based Path Queries in Temporal Graphs
  • Cross-layer Betweenness Centrality in Multiplex Networks with Applications
  • Influence based cost optimization on user preference
  • Efficiently Computing Reverse k Furthest Neighbors
  • CSI_GED: An Efficient Approach for Graph Edit Similarity Computation
  • Streaming Spectral Clustering
  • Streaming Link Prediction on Graph Streams
  • Edge Classification in Networks
  • VColor: A Practical Vertex-cut Based Approach for Coloring Large Graphs
  • Compressing Graphs via Grammars
  • Distance-Aware Influence Maximization in Geo-social Network
  • TOPIC: Toward Perfect Influence Graph Summarization

ICDE 2017

  • UniWalk: Unidirectional Random Walk Based Scalable SimRank Computation over Large Graph
  • A Fast Order-Based Approach for Core Maintenance
    • k-coreを動的グラフで頑張って保持、（頂点？）順序を保持する
  • Scalable and Interactive Graph Clustering Algorithm on Multicore CPUs
  • Fast Computation of Dense Temporal Subgraphs
    • テンポラルグラフで辺の重みが変わる
    • 何か難しいので、Prize Collecting Steiner Tree辺りの関連でヒューリスティクス提案
  • ✔Network Backboning with Noisy Data
    • 辺重みが二項分布、何かしらの尺度で良さ主張
  • Streaming k-Means Clustering with Fast Queries
  • TT-Join: Efficient Set Containment Join
  • PrivSuper: a Superset-First Approach to Frequent Itemset Mining under Differential Privacy
  • Tracking matrix approximations over distributed sliding windows
  • Temporal Influence Blocking: Minimizing the Effect of Misinformation in Social Networks
  • Most Influential Community Search over Large Social Networks
  • ✔Boosting Information Spread: An Algorithmic Approach
    • ちょっと新しい問題: 影響される確率を上げることが出来る
  • Link Prediction across Aligned Networks with Sparse and Low Rank Matrix Estimation
    • 複数ソーシャルネットがある中でリンク予測
  • Spinner: Scalable Graph Partitioning in the Cloud
    • Pregelでグラフ分割

International Conference on Very Large Data Bases

VLDB 2010

  • On Graph Query Optimization in Large Networks
    • r10_

VLDB 2011

  • On Triangulation-based Dense Neighborhood Graph Discovery
    • r8
  • Mining Top-K Large Structural Patterns in a Massive Network
    • r8
  • ✔Private Analysis of Graph Structure
    • 部分グラフがもらえるので、秘匿性（差分プライバシ）を保ったまま、その個数を数える

VLDB 2012

  • Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification
    • best paper
  • Truss Decomposition in Massive Networks
    • k-truss

VLDB 2013

  • ✔Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation
    • FastPPV 逐次的に精度を改善する手法
  • Efficient SimRank-based Similarity Join Over Large Graphs

VLDB 2014

  • Toward a Distance Oracle for Billion-Node Graphs
    • 最短経路の近似
    • 微妙
  • Finding Shortest Paths on Terrains by Killing Two Birds with One Stone
    • shortest surface distance
      • 複雑な地形，山とか，の上を這って行く最短経路問題
  • Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited
    • joinの実験的性能
  • From "Think Like a Vertex" to "Think Like a Graph"
    • 分散グラフ処理システム
    • 分割の考え方
  • ✔Computing k-Regret Minimizing Sets
    • k-Regret Minimizingの難しさ，DPな手法，実験
  • GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph
    • タイトルのまんま
  • A Principled Approach to Bridging the Gap between Graph Data and their Schemas
    • RDFグラフ
  • Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs
    • コストが変わるグラフ
    • vへの最速到達時刻が，vの近傍の最速到達時刻から得られるわけではないのでムズイ
  • Path Problems in Temporal Graphs
    • temporal graph上の最短路
    • 既存のは問題がある
    • 新しいので，性質と効率的アルゴリズム
  • ✔On k-Path Covers and their Applications
  • Repairing Vertex Labels under Neighborhood Constraints
    • 近傍制約なるものが成立するように頂点のラベルを復元する
    • 貪欲な近似アルゴリズム
  • ✔Computing Personalized PageRank Quickly by Exploiting Graph Structures
  • Distributed Graph Simulation: Impossibility and Possibility
    • 並列計算のアルゴリズムの性質の話？
  • Reachability Querying: An Independent Permutation Labeling Approach
    • 乱択アルゴリズムでラベリング
    • permutationが乱択に関連するらしい
  • Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks
    • 索引サイズのbound，I/Oコスト，をスケールフリーネットワークの性質から
  • Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs
    • 一時的に関連がある行動に基づいて推薦
    • オンラインMotif検出
  • VERTEXICA: Your Relational Friend for Graph Analytics!
    • グラフ解析ツール
    • SQLとか
  • Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees
  • Auto-Approximation of Graph Computing
  • LogGP: A Log-based Dynamic Graph Partitioning Method
  • Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs
  • Large Scale Real-time Ridesharing with Service Guarantee on Road Networks

VLDB 2015

  • ✔Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret
    • 広告配置をバイラルマーケティング的に考える
  • ✔Online Topic-Aware Influence Maximization
    • MIAを利用
    • ε(1-1/e)近似
  • From Competition to Complementarity: Comparative Influence Diffusion and Maximization
    • 競合性と相補性をかね備えたICモデル
    • 辺だけの拡散ではない（らしい）
    • ２種類の問題を考えていろいろしてとく

VLDB 2017

  • Fast Hierarchy Construction for Dense Subgraphs
    • アレを爆速にしました

ACM International Conference on Information and Knowledge Management

CIKM 2003

  • ✔The Link Prediction Problem for Social Networks
    • リンク予測問題の先駆け

CIKM 2010

  • Path-hop: efficiently indexing large graphs for reachability queries
  • On wavelet decomposition of uncertain time series data sets
  • Online update of b-trees
  • Mining interesting link formation rules in social networks
  • SHRINK: a structural clustering algorithm for detecting hierarchical communities in networks
  • Expansion and search in networks
  • Mining topic-level influence in heterogeneous networks
  • Energy-efficient top-k query processing in wireless sensor networks
  • Set cover algorithms for very large datasets
  • Fast and accurate estimation of shortest paths in large graphs
  • Fast top-k simple shortest paths discovery in graphs
  • Network growth and the spectral evolution model
  • The anatomy of a click: modeling user behavior on web information systems
  • Probabilistic first pass retrieval for search advertising: from theory to practice
  • Predicting product adoption in large-scale social networks
  • SUMMA: subgraph matching in massive graphs
  • Evaluation of top-k queries in peer-to-peer networks using threshold algorithms
  • A hierarchical approach to reachability query answering in very large graph databases
  • Threshold behavior of incentives in social networks
  • Communication motifs: a tool to characterize social communications
  • A study of rumor control strategies on social networks

CIKM 2011

  • User browsing behavior-driven web crawling
    • リンク構造からページの重要性を測ったりするね
    • 重要性をユーザの興味とブラウザログから直接測るよ
    • クロールも同時？にする
  • ✔Local computation of PageRank: the ranking side
    • n頂点グラフからk頂点のPageRankを知りたい
      • CIKM 2004, 2008で出てた
    • $$ \Omega(\sqrt{kn}) $$頂点は見ないとだめぽ
  • Coupling or decoupling for KNN search on road networks?: a hybrid framework on user query patterns
    • 道路ネットワーク上の空間オブジェクトの検索
    • 今までグラフの走査とオブジェクトのルックアップを分けてやってたが重い（？）
  • Discovering top-k teams of experts with/without a leader in social networks
    • まとめると必要なスキルが揃って，通信コストが最小
    • 通信コストを色々定義
    • NP-hardだけど2近似
  • Probabilistic near-duplicate detection using simhash
    • simhash(Charikar)
    • simhashたちのHamming空間で探索する手法（の考案？）
  • Link prediction: the power of maximal entropy random walk
    • リンク予測にRandomWalkがよく使われる
    • ただ頂点の中心性のようなものは無視
    • 極大Entropyで（？）hitting timeとかcommute timeとか
    • あとグラフカーネルと類似尺度
  • Exploiting longer cycles for link prediction in signed networks
    • 符号付きなので，不均衡とかそういうのでリンク予測に使うよ
    • 教室付き機械学習で長い閉路を使う（謎）
  • Determining the diameter of small world networks
    • デカイグラフの直径が欲しいよお
    • 下界/上界，頂点選択・枝刈り手法で大事なとこだけ
    • |E|<24M
  • Distributed social graph embedding
    • 推薦
    • グラフをd次元空間に埋め込む
      • コミュニティを取りたい
  • Finding information nebula over large networks
    • nebula = 星雲
    • ユーザのクエリに関連するtop-k キーワード項
  • Efficient methods for finding influential locations with adaptive grids
    • サーバーとクライアントがもらえる
    • 新しいサーバーをどこに於けばいいか？
    • クライアントが必ず最近のサーバーに行くと思ったら大間違いだぜへっへっへ！
    • ↑を緩和した問題を提案
    • めっちゃ早い近似アルゴリズムを作った
  • Answering label-constraint reachability in large graphs
    • そのまんま
  • High efficiency and quality: large graphs matching
    • 最大共通部分グラフマッチング…NP-hard
    • 厳密は遅く，近似はしょぼいので，いい感じのを作った
  • Skynets: searching for minimum trees in graphs with incomparable edge weights
    • 辺の重みが範囲…なので半順序
    • 代わりの比較演算子を考案
  • Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs
    • landmarkベース
    • 最短路木をもって，辺の挿入・削除に対応
    • 最短路を被覆したい
  • Selecting related terms in query-logs using two-stage SimRank
    • クエリからクリックしたページが同じなら2つのクエリが似てるとかんがえる
    • SimRankとクラスタリング手法を使ってクエリ間の類似度を図るよ
    • ちゃんと何かしらの意味で精度が上がったらしい
  • Top-k most influential locations selection
    • 施設配置選択クエリ
    • 候補からtop-kで影響のある施設をとる
      • 影響（定義はあるらしい）
    • 厳密は辛いので近似する

CIKM 2012

  • Graph classification: a diversified discriminative feature selection approach
    • 特徴選択と分類
      • 分類はふつうの手法使えばいいので，特徴選択に注目
    • 以前のの欠点があるので，新しいのを提案
  • Multi-scale link prediction
    • 類似度（？）の計算が激重
    • 低ランク近似…単一だけだと心もとないので，一杯
  • Density index and proximity search in large graphs
    • 頂点にラベル…クエリに対してよさそな頂点集合が欲しい
    • クエリをカバーし直径最小のをとってくる
  • Efficient algorithms for generalized subgraph query processing
    • 辺を経路にマップするクエリ（？）
  • G-SPARQL: a hybrid engine for querying large attributed graphs
    • SPARQLっぽい言語
  • Utilizing common substructures to speedup tensor factorization for mining dynamic graphs
  • Predicting emerging social conventions in online social networks
    • 集会の予測 Twitterで
    • 採択の日と露出(exposures)の数が重要
      • 個々の特徴，友達の内の採択数はそんなに大事じゃない
  • Influence propagation in adversarial setting: how to defeat competition with least amount of investment
    • 競合者あり
      • 他のにスイッチしない
    • 既に拡散が始まっている，そこから新たに自分のを流す
  • Scalable clustering of signed networks using balance normalized cut
    • 符号付きグラフのLaplacianはすでにある
    • 欠点があるらしい
    • normalized cutっぽいのを提案
    • 実験的には良い
    • 重み付きカーネルk-meansと同じ(?)
  • Pay-as-you-go maintenance of precomputed nearest neighbors in large graphs
    • 最近傍のリストを各頂点について持つ
    • 頂点追加／辺重み減少をサポート
  • Spatial influence vs. community influence: modeling the global spread of social media
    • 情報が地球上の位置的にどう広がる？
    • 下の過程を取り入れたモデル
      1. 空間的なモデル：近い所に伝わる
      2. コミュニティ類似：離れてても（文化的に）繋がってればOK
  • Evaluating geo-social influence in location-based social networks
    • geoとsocialの意味での類似度を図る指標
      • penalized hitting time
      • 地理学的な重み関数
    • ユーザーの影響力を測るアルゴリズム
  • Influence and similarity on heterogeneous networks
  • GRAFT: an approximate graphlet counting algorithm for large graph analysis
    • graphletの頻度分布が知りたい
    • 5頂点以下なら全部数え上げるよ
    • 10~100倍で5%以下
  • Fast approximation of steiner trees in large graphs
    • landmarkベースの索引構造でSteiner tree
  • Shaping communities out of triangles
    • 新しいコミュニティの尺度(WCC)
    • 構造と結合の意味である以上の最小の集合
  • Degree relations of triangles in real-world networks and graph models
    • △と次数の関係
    • ソーシャルや共同：△の次数は似てる
    • Web（情報）：△の次数はかなり違う
    • 次数がtop 1%の頂点はかなりの△に所属してた
  • Finding the optimal path over multi-cost graphs
    • multi-costで最短路
    • 最良優先，分枝限定法
    • 索引も
  • On bundle configuration for viral marketing in social networks
    • いくつかのアイテムをまとめる設定の問題
    • Bundle Configuration for SpreAd Maximization
  • On compressing weighted time-evolving graphs
    • 動的グラフを圧縮したいよ
    • テンソル…
      • なんだかよく分からん
  • Tracing clusters in evolving graphs with node attributes
    • そのまま
  • Prediction of retweet cascade size over time
    • ある期間でTweetがどのくらい伸びるのか
    • 普通の特徴量＋色々
    • カスケードの流れ（？）とリツイートグラフでのPageRank
  • Bridging offline and online social graph dynamics
    • LinkedInのデータで，オフラインでのイベントがオンラインネットワークに及ぼす影響
    • あとリンク予測
  • Continuous top-k query for graph streams
    • そのままっぽい

CIKM 2013

  • G-tree: an efficient index for KNN search on road networks
  • UNIK: unsupervised social network spam detection
  • Diffusion of innovations revisited: from social network to innovation network
  • PATRIC: a parallel algorithm for counting triangles in massive networks
  • An efficient MapReduce algorithm for counting triangles in a very large graph
  • Parallel triangle counting in massive streaming graphs
  • Discovering latent blockmodels in sparse and noisy graphs using non-negative matrix factorisation
  • Understanding the roles of sub-graph features for graph classification: an empirical study perspective
  • Active exploration: simultaneous sampling and labeling for large graphs
  • Local clustering in provenance graphs
  • Content-centric flow mining for influence analysis in social streams
  • Labels or attributes?: rethinking the neighbors for collective classification in sparsely-labeled networks
  • Linear-time enumeration of maximal K-edge-connected subgraphs in large networks by random contraction
  • External memory K-bisimulation reduction of big graphs
  • Accurate and scalable nearest neighbors in large networks based on effective importance
  • Entity disambiguation in anonymized graphs using graph kernels
  • Random walk-based graphical sampling in unbalanced heterogeneous bipartite social graphs
  • Modeling information diffusion over social networks for temporal dynamic prediction
  • An efficient algorithm for approximate betweenness centrality computation
  • Graph similarity search with edit distance constraint in large graph databases
  • Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths
  • Graph hashing and factorization for fast graph stream classification
  • Overlapping community detection using seed set expansion
  • Incorporating the surfing behavior of web users into pagerank

CIKM 2014

  • Analysis on Community Variational Trend in Dynamic Networks
  • Learning Interactions for Social Prediction in Large-scale Networks
  • Influence Maximization over Large-Scale Social Networks: A Bounded Linear Approach
  • Learning a Linear Influence Model from Transient Opinion Dynamics
  • Modeling Paying Behavior in Game Social Networks
  • Pattern Match Query in a Large Uncertain Graph
  • Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
  • Active Exploration in Networks: Using Probabilistic Relationships for Learning and Inference
  • Graph-based Point-of-interest Recommendation with Geographical and Temporal Influences
  • Distributed Graph Summarization
  • Efficient Probabilistic Supergraph Search Over Large Uncertain Graphs
  • Supervised Nested PageRank
  • Sampling Triples from Restricted Networks using MCMC Strategy
  • Efficient Subgraph Skyline Search Over Large Graphs
  • Within-Network Classification Using Radius-Constrained Neighborhood Patterns
  • Pushing the Envelope in Graph Compression
  • Relationship Emergence Prediction in Heterogeneous Networks through Dynamic Frequent Subgraph Mining
  • Scalable Vaccine Distribution in Large Graphs given Uncertain Data
  • Component Detection in Directed Networks
  • MapReduce Triangle Enumeration With Guarantees

CIKM 2015

  • ✔Defragging Subgraph Features for Graph Classification
    • 頻出部分グラフを取ってくると自明な無意味パターンがとれちゃうので頑張る
  • Towards Scale-Out Capability on Social Graphs
  • HDRF: Stream-Based Partitioning for Power-Law Graphs
  • Identifying Top-k Structural Hole Spanners in Large Network
  • On Gapped Set Intersection Size Estimation
  • Efficient Sparse Matrix Multiplications on GPU for Large Social Network Analysis
  • Finding Probabilistic K-Skyline Sets on Uncertain Data
  • Location-Based Influence Maximization in Social Networks
  • Mining Brokers in Dynamic Social Networks
  • Exploiting Game Theoretic Analysis for Link Recommendation in Social Networks
  • Node Immunization Over Infectious Period
  • L2Knng: Fast Exact K-Nearest Neighbor Graph Construction with L2-Norm Pruning
  • gSparsify: Graph Motif-Based Sparsification for Graph Clustering
  • A Min-Max Optimization Framework for Online Graph Classification
  • What Is a Network Community? A Novel Quality Function and Detection Algorithms
  • Scalable Clustering Algorithm Via a Triangle Folding Processing for Complex Networks
  • Modeling Infection Dynamics Using Social Network Information
  • RoadRank: Traffic Diffusion and Influence Estimation in Dynamic Urban Road Networks
  • Top-k Reliable Edge Colors in Uncertain Graphs

CIKM 2016

  • ✔Multiple Infection Sources Identification with Provable Guarantees
    • 普通は単一ソース、トポロジも木とかで簡単、感染集合とカスケードの対称差を最小化する、解の大きさも設定不要

International Conference on Extending Database Technology

EDBT 2011

EDBT 2012

  • Limiting link disclosure in social network analysis through subgraph-wise perturbation
    • リンク関係の暴露はプライバシー侵害
    • 既存は適当にかき混ぜる→構造的性質が乱される
    • 有向グラフで行き先だけ変える
    • subgraph-wise perturbation（部分グラフに分割してそれ毎に変える）
  • Shortest-path queries for complex networks: exploiting low tree-width outside the core
    • 最短路クエリ
    • 小木幅部分と複雑ネットワーク部分クラス
  • Finding top-k similar graphs in graph databases
    • クエリグラフに近いtop-kのグラフを探す
    • 新しい類似指標 MCS (maximal common subgraph)
    • インデクシングもする
  • I/O cost minimization: reachability queries processing over massive graphs
    • メモリに入らないグラフでの到達可能性クエリでI/Oを小さくしたい
    • 分割手法も
  • Finding maximal k-edge-connected subgraphs from a large graph
    • 極大k枝連結部分グラフを見つける
    • 頂点縮小／辺縮小／カット枝刈り

EDBT 2013

EDBT 2014

  • Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach
    • 到達可能性クエリの索引手法
    • 2次元平面上の表現（？）
  • Distance oracles in edge-labeled graphs
    • Francesco Bonchi
    • 使える辺ラベルが指定されての最短距離の索引手法
  • Graph Analytics on Massive Collections of Small Graphs
  • ✔Fast Reliability Search in Uncertain Graphs
    • Francesco Bonchi
    • 信頼性=2頂点が連結の確率
    • クエリ頂点からある確率以上で到達可能な頂点集合が欲しい
    • GOODな索引を作るよ
    • 前の奴に似たテク？
  • CLUDE: An Efficient Algorithm for LU Decomposition Over a Sequence of Evolving Graphs
    • 動的グラフの（隣接）行列をLU分解
    • クラスタの力
  • Spatial Partitioning of Large Urban Road Networks
    • 空間的な都市道路ネットワークの分割
    • スペクトラルグラフ理論なグラフカットを使って分割，とか
  • Efficient Skyline Computation in MapReduce
    • スカイラインは大事だよ
    • でも並列してないね
    • MapReduce！！
    • でーたの空間を分割
  • L-opacity: Linkage-Aware Graph Anonymization
    • L-opacityはモデルのことらしい
  • Privacy Risk in Anonymized Heterogeneous Information Networks
  • Diversified Spatial Keyword Search On Road Networks
    • 位置に例えばレストランなら店名とか食べ物とかの内容
    • 関連があって空間的に雑多なやつをクエリとして答える
  • Distributed Spatial Keyword Querying on Road Networks
  • Cost-Based Median Query Processing in Wireless Sensor Networks
    • エネルギー消費を減らして長生きしたい
    • メディアン
    • 元からある奴を連続な奴に拡張

EDBT 2015

  • Hermes: Dynamic Partitioning for Distributed Social Network Graph Databases
    • グラフの動的分割
    • ハッシュベースの分割手法の2～3倍
  • Learning Path Queries on Graph Databases
    • ユーザが頂点を正or負にラベル付したグラフ
    • ユーザの予期したクエリを見つける（？）
  • TimeReach: Historical Reachability Queries on Evolving Graphs
    • historicalな到達可能性クエリ
    • でかいSCCを活用
  • ✔ Efficiently Computing Top-K Shortest Path Join
    • 頂点集合S,Tがある
    • SからTの最短経路のtop-k
    • 最良優先的
    • 探索空間をイイ感じに分割
    • top-kより早くなりうるのをだけ
  • SIEF: Efficiently Answering Distance Queries for Failure Prone Graphs
    • 動的なグラフ…辺が「消える」
  • A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs
    • ストリームグラフ上の部分グラフマッチング
    • 応用：cyber attackの検知（？）

EDBT 2017

  • Reverse k-Ranks Queries on Large Graphs
    • 今まではベクトル空間だけど、今回はグラフ、filter-and-refinement
  • Task-Optimized Group Search for Social Internet of Things
  • ✔Information Propagation in Interaction Networks
    • 瞬間的なやり取りを通じて情報が流れる、時間幅を区切って流れるものを計算、影響最大化とか
  • Efficient Motif Discovery in Spatial Trajectories Using Discrete Frechet Distance.
    • Frechet distanceは曲線の距離を測る、近い部分曲線対をモチーフと呼ぶ、計算を頑張って高速化
  • Exact and Approximate Algorithms for Finding k-Shortest Paths with Limited Overlap.
    • 名前通り、ワンパスアルゴリズムも提案

International Conference on Database Systems for Advanced Applications

DASFAA 2016

ウェブ

International World Wide Web Conference

WWW 2000

  • Graph Structure in the Web
    • best paper

WWW 2012

  • Community Detection in Incomplete Information Networks
  • Distributed Graph Pattern Matching
  • Vertex Collocation Profiles: Subgraph Counting for Link Analysis and Prediction

WWW 2013

  • Predicting Positive and Negative Links in Signed Social Networks by Transfer Learning
  • Mining Structural Hole Spanners in Large Networks
  • What Is the Added Value of Negative Links in Online Social Networks?
  • Distributed large-scale natural graph factorization
  • Strategyproof mechanisms for competitive influence in networks

WWW 2014

  • Random Walks based Modularity: Application to Semi-Supervised Learning by Robin Devooght, Amin Mantrach, Ilkka Kivima"ki, Hugues Bersini, Alejandro Jaimes and Marco Saerens
  • High Quality, Scalable and Parallel Community Detection for Large Real Graph by Arnau Prat-Pe'rez, David Dominguez-Sal and Josep-Lluis Larriba-Pey
  • Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling by Takuya Akiba, Yoichi Iwata and Yuichi Yoshida
  • On Estimating the Average Degree by Anirban Dasgupta, Ravi Kumar and Tamas Sarlos
  • How information diffusion shapes social network structure by Seth Myers and Jue Leskovec
  • Can cascades be predicted? by Justin Cheng, Lada Adamic, Alex Dow, Jon Kleinberg and Jure Leskovec
  • How to Influence People with Partial Incentives by Erik Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, David Malec, Anshul Sawant, Morteza Zadimoghaddam and S. Raghavan

WWW 2015

  • ✔The k-clique Densest Subgraph Problem
    • 頂点集合Sであって，平均k-cliqueの下図を最大化したい
    • 分母は超点数
    • k=2…densest subgraph
    • k=3…$$ \frac{\# \Delta(S)}{|S|} $$
    • k固定で厳密多項式時間
    • 1/k-近似…効率的
    • 実験: 3-clique densestの解はnear-clique
  • A Game Theoretic Model for the Formation of Navigable Small-World Networks
    • ゲーム理論的モデル
    • ↑のNash近郊がnavigable small-world networks
    • 距離とreciprocityとの関係
  • Discovering Meta-Paths in Large Heterogeneous Information Networks
  • HIN…頂点・辺にラベル
    • meta-path…2頂点を結ぶ経路のラベル列
      • 情報検索・意思決定・商品推薦
    • 2頂点間の最も関連のある経路を出す←貪欲算法
  • ✔Spanning edge centrality: large-scale computation and applications
    • eの全域中心性=Gの全域木がeを含む割合
    • 近似手法←理論を持ちこむ（？）
    • 消すとやばい辺の同定に使える
  • ✔Scalable Methods for Adaptively Seeding a Social Network
    • 直接指定するんじゃなくてその近傍にやってもらう
    • friendship paradoxのおかげで強そう
    • scalableな手法を作ったよ
  • Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment
    • 非対称minhashという新しい手法
  • ✔Improved Theoretical and Practical Guarantees for Chromatic Correlation Clustering
    • LPベースの手法4近似
      • 遅いけど理論的理解
    • ヒューリスティクス
  • ✔Efficient Densest Subgraph Computation in Evolving Graphs
    • 動的・大規模同時はない
    • ↑クロールの手間
    • 2(1+ε)近似　O(polylog(n+r))コスト
  • Skolemising Blank Nodes while Preserving Isomorphism
    • RDFグラフ
  • Global Diffusion via Cascading Invitations: Structure, Growth, and Homophily
    • Webサイトとか招待でメンバが増える←カスケード！
    • LinkedIn
      • カスケードの形が違う（サインアップ）
      • 長時間起こる
  • Uncovering the Small Community Structure in Large Networks: A Local Spectral Approach
  • Recommendation Subgraphs for Web Discovery
    • 二部グラフ上の最適化問題
    • 左：よく訪れる
    • 右：あんま訪れない
    • 左から出辺をいくつか選ぶ
    • 右が冗長に選ばれる沢山
    • いろんな手法
      • 局所的無作為標本
      • 貪欲法
      • 分割
  • Random-Walk TripleRush: Asynchronous Graph Querying and Sampling
    • SPARQL 3つ組
    • DBの話
  • Essential Web Pages Are Easy to Find
    • 沢山のクエリに答えられる
    • ログから索引サイズの推定
    • Max Cover 63%近似
  • ✔Density-friendly graph decomposition
    • k-coreの問題を解決する系論文、密度も考える、実はk-coreは2近似
  • Mining Missing Hyperlinks from Human Navigation Traces: A Case Study of Wikipedia
    • Leskovec, missing linkをグラフ構造から、というより、Wikipediaのナビゲーション能力を高めるために探す

WWW 2016

  • ✔Social Networks Under Stress
    • ベストペーパー
    • "外部"事象がネットワーク構造・コミュニケーションにどう紐づく？
    • 価格ショック、ネットワーク構造
    • ネットワーク構造の変化が色々と（集団態度）予測する
  • Measuring Urban Social Diversity Using Interconnected Geo-Social Networks
  • Recommendations in Signed Social Networks
    • 符号付きネットワークでの推薦がそもそも少なかったので、頑張ってモデルを作りました
  • Economic Recommendation with Surplus Maximization
  • In a World That Counts: Clustering and Detecting Fake Social Engagement at Scale
    • YouTubeのヤバげなやつを検出したい
    • 偽のエンゲージメント活動を追跡する
    • semi-supervisedで、シードと似たパターンを探す
  • Tracking the Trackers
  • ✔Visualizing Large-scale and High-dimensional Data
    • 大規模高次元データを低次元空間に可視化
    • 提案手法LargeVis: 近似k-近傍グラフを構築→低次元空間にレイアウト
    • 確率的勾配降下法で線形時間
  • ✔On Sampling Nodes in a Network
    • 事前に指定した分布に従って，頂点をサンプリングしたい，ランダムウォーク！
  • Distributed Estimation of Graph 4-Profiles
    • 4-profile（連結でなくても良い部分グラフ）
    • 拡張点が11次元空間に埋め込まれる
  • ✔Do Cascades Recur?
    • Facebookのデータを解析，デカイカスケードが再発する
    • 経過時間とか重複具合とかで測定してみる
    • 予測できたよ
  • Exploring Limits to Prediction in Complex Social Systems
    • 複雑社会系での成功の予測
  • The Effect of Recommendations on Network Structure
    • 推薦はニッチなユーザの数を増やすのか，既にポピュラーなユーザの数を増やすのか
    • rich get richer的な現象が起きた

WWW 2017

  • Cascades: A View from Audience
    • Jon Kleinberg
    • 大事そう…
  • DeepCas: an End-to-end Predictor of Information Cascades
  • Detecting Large Reshare Cascades in Social Networks
    • ネットワーク構造を無視して、カスケードが凄くなるか／早く予測できるかを答える
  • Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
    • 隣接行列のスペクトラル半径・非Backtracking行列でなくて、高次非Backtracking行列
    • しきい値の推定がより良くなった
  • ✔Large Scale Density-friendly Graph Decomposition via Convex Programming
    • [Tatti-Gionis. WWW'15]が元ネタ
    • Frank-Wolfeに基づく爆速アルゴリズム
  • nTD: Noise Adaptive Tensor Decomposition
  • AutoCyclone: Automatic Mining of Cyclic Online Activities with Robust Tensor Factorization
  • When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors
    • MapReduceでwedgeサンプリング、あと色々理論的に頑張る
  • ✔Submodular Optimization Over Sliding Windows
    • sliding windowsで良い近似解をずっとキープしたい、1/3近似アルゴリズムを提案
  • ✔Correlation Clustering with Low-Rank Matrices
    • David Gleich
    • 低ランク近似で頑張る
    • 半正定値、定数ランクなら多項式時間
    • 頭の良さそうなアルゴリズムを提案
  • Consistent Weighted Sampling Made More Practical
    • 実数値重み付き集合のMinHash Improved Consistent Weighted Sampling を更に改善
  • Who Controls the Internet? Analyzing Global Threats using Property Graph Traversals
  • What Makes a Link Successful on Wikipedia?
  • Secure Centrality Computation Over Multiple Networks
    • 情報論的意味とかで安全性を証明している中心性計算、真面目
  • ✔Interplay between Social Influence and Network Centrality: A Comparative Study on Shapley Centrality and Single-Node-Influence Centrality
  • Sampling from social networks with attributes
    • 性別属性（男女）があるようなグラフでサンプリングアルゴリズムを走らせてみる
    • 適当にやっているとやばい
  • Deanonymizing Web Browsing Data With Social Networks
    • 各個人には特有のソーシャルネットワークがあるので、閲覧履歴からバレる
  • ✔ESCAPE: Efficiently Counting All 5-Vertex Subgraphs
    • 頑張りました
  • ✔The k-peak decomposition: Mapping the global structure of graphs
    • k-coreの欠点を修正するようなk-peak分解を提案。可視化もうまく出来るよ！
  • Scalable motif-aware graph clustering
    • モチーフとして、△に注目して、良いクラスタリング
    • △conductanceを提案（何処かで見たような…）、既存のクラスタリングを上手く適応
  • Indexing Public-Private Graphs
    • あのPublic-Privateグラフで到達可能性クエリを考える
    • k-centerとか解く

WWW 2018

  • ✔Minimizing Polarization and Disagreement in Social Networks
    • Charalampos E. Tsourakakis
    • 不一致・意見の相違と対立・分裂
    • 個々の初期意見が指定され、意見ダイナミクスモデルがある時、どういうグラフ構造が不一致と論争を減らせるか？
    • 推薦システムとしては…：似た者同士を合わせて論争を避ける or 違う家者同士を合わせて全体の不一致を減らす…とか。
    • 近似アルゴリズム提案＋計算機実験。
  • TIMES: Temporal Information Maximally Extracted from Structures
    • よく分からん
  • ✔Fast and Accurate Random Walk with Restart on Dynamic Graphs with Guarantees
    • Minji Yoon, U. Kang
    • 厳密計算：できるらしい
    • 近似計算：反復回数と精度の保証
    • "Ohsaka et al. proposed TrackingPPR ... However, they fail to provide theoretical analysis of accuracy bound"←？？？- SIR-Hawkes: Linking Epidemic Models and Hawkes Processes to Model Diffusions in Finite Populations
    • ほぼタイトル通り？
  • ✔A Correlation Clustering Framework for Community Detection
    • David F. Gleich
    • WWW'17の続き感。
    • LambdaCCなる枠組みを提案。resolution param λを変えると粗さが変わる。他のクラスタ指標を統一・一般化。2近似可能。
  • Mining Tours and Paths in Activity Networks
    • activity network：頂点に何らかの活動斗その頻度が紐づけ
    • prize-collecting subgraph：色々な活動を含み、互いに近い部分グラフ
    • 問題を定式化、後はいつもの流れ
  • Spectral Algorithms for Temporal Graph Cuts
    • temporalというよりはdynamicな感じ
  • Preferential Attachment as a Unique Equilibrium
    • Q. 何故PAで実際のグラフっぽいものが出来るのか？
    • A. PA is the unique Nash equilibrium of a natural network formation game
  • Fully Dynamic k-Center Clustering
    • sliding windowとか多いけど、任意の変更したいですね。
    • 2+ε近似アルゴリズム作りました。更新費用も理論的に解析。実験したら良かったよ。
  • ✔Listing k-cliques in Sparse Real-World Graphs
    • Chiba-Nishizekiのアルゴリズムから改善を図る。並列化。疎なグラフに対しては最悪計算量（の上限）が改善。
    • k-clique core decompositionとk-clique densest subgraphに応用。
  • Fast Exact CoSimRank Search on Evolving and Static Graphs
    • いつもの感じかな？SimRankは非線形な操作が入るけどCoSimRankは無さそう・・・？
  • Measuring and Improving the Core Resilience of Networks
    • ネットワークのk-coreに関するresilience（弾性）を定式化したい。頂点のスコアを考える。
    • 辺を追加して弾性を改善する問題を考案。
  • ✔Low Rank Spectral Network Alignment
    • David F. Gleich
    • EigenAlignの改善に近い。低ランク行列で最大重み二部マッチングをする。
  • ✔Mapping the Invocation Structure of Online Political Interaction
    • Jon M. Kleinberg
    • イデオロギー的な観点の異なる相互作用を表現したいです
    • 「あるドメインのページが他のドメインのページを含む投稿に返信するために呼び出される範囲を示すWebドメイン上のinnovation graph」を作る
    • 埋込みが得られる→相互作用リンクが異なる距離に及ぶか分かる（？）
  • ✔Algorithmic Glass Ceiling in Social Networks: The effects of social recommendations on network diversity
    • glass ceiling ＝ マイノリティの地位向上を阻む見えない天井のこと
    • 友達とかの推薦システムが実はこれを悪化させてしまう。特にgenderに関してネットワーク構造を調査。

WWW 2019

  • Sensitivity Analysis of Centralities on Unweighted Networks
  • Estimating Walk-Based Similarities Using Random Walk
  • Maximizing Current Flow Closeness under Cardinality Constraints
  • Revisiting Wedge Sampling for Triangle Counting
  • Distributed Algorithms for Fully Personalized PageRank on Large Graphs
  • Link Prediction in Networks with Core-Fringe Data
  • Constrained Local Graph Clustering by Colored Random Walk

ACM International Conference on Web Search and Data Mining

WSDM 2013

  • On the Streaming Complexity of Computing Local. Clustering Coefficients
  • Cascade-based Community Detection
  • Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships
  • Overlapping community detection at scale: A Nonnegative Matrix Factorization Approach
    • Leskovec

WSDM 2014

  • FENNEL: Streaming Graph Partitioning for Massive Scale Graphs
  • Learning Social Network Embeddings for Predicting Information Diffusion
  • Active Learning for Networked Data Based on Non-progressive Diffusion Model
  • Fast Approximation of Betweenness Centrality Through Sampling
  • The Last Click: Why Users Give up Information Network Navigation
    • 例のごとくLeskovec
  • Scalable k-Means
    • タイトルがシンプルすぎる…
  • Effective Co-betweenness Centrality Computation
  • Finding HeavyPaths in Weighted Graphs and a Case-Study on Core Community Detection

WSDM 2015

WSDM 2016

  • ✔Personalized PageRank Estimation and Search: A Bidirectional Approach
    • Estimation: 普通のPPR計算を双方向な感じで高速化
    • Search: sとTが与えられるので，PPR_sがtop-kのT中の頂点を見つける
  • Improving Website Hyperlink Structure Using Server Logs
    • Leskovec, 存在しないリンクの将来の有用性をサーバログデータ使ってモデル化、最適化問題、Wikipediaで検証
  • Nonlinear Laplacian for Digraphs and its Applications to Network Analysis
  • Querying and Tracking Influencers in Social Streams
  • Scaling up Link Prediction with Ensembles
  • Personalized PageRank Estimation and Search: A Bidirectional Approach

WSDM 2017

  • ✔Counting Graphlets: Space vs Time
    • Ravi Kumar
  • D-Cube: Dense-Block Detection in Terabyte-Scale Tensors
    • Christos Faloutsos
  • Embedding of Embedding (EOE) : Embedding for Coupled Heterogeneous Networks
  • Location Influence in Location-based Social Networks
  • Link Prediction with Cardinality Constraint
  • Motifs in Temporal Networks
    • Jure Leskovec

WSDM 2018

  • Peeling Bipartite Networks for Dense Subgraph Discovery
  • Fast Coreset-Based Max-Sum Diversity under Matroid Constraints

International Conference on Weblogs and Social Media

ICWSM 2010

ICWSM 2011

人工知能

AAAI Conference on Artificial Intelligence

AAAI 2007

AAAI 2016

  • Closeness Centrality for Networks with Overlapping Community Structure
  • DRIMUX: Dynamic Rumor Influence Minimization with User Experience in Social Networks
  • Two Efficient Local Search Algorithms for Maximum Weight Clique Problem
  • Submodular Optimization with Routing Constraints
  • Approximate K-Means++ in Sublinear Time
  • Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization
  • Learning Expected Hitting Time Distance
  • General Error Bounds in Heuristic Search Algorithms for Stochastic Shorte
  • Optimizing Resilience in Large Scale Networks

International Joint Conference on Artificial Intelligence

IJCAI 2009

IJCAI 2011

IJCAI 2015

  • A Fast Local Search for Mnimum Vertex Cover in Massive Graphs
  • A Scalable Community Detection Algorithm for Large Graphs Using Stochastic Block Models
  • Scalable Graph Hashing with Feature Transformation
  • Maximizing the Coverage of Information Propagation in Social Networks
  • Analysis of Sampling Algorithms for Twitter
  • Generalized Transitive Distance with Minimum Spanning Random Forest
  • Exploiting k-Degree Locality to Improve Overlapping Community Detection
  • Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning

IJCAI 2017

  • No Time to Observe: Adaptive Influence Maximization with Partial Feedback
  • Semi-supervised Feature Selection via Rescaled Linear Regression
  • When Does Label Propagation Fail? A View from a Network Generative Model
    • Yuto Yamaguchi, Kohei Hayashi
  • A Reduction based Method for Coloring Very Large Graphs
  • Efficient Kernel Selection via Spectral Analysis
  • Diverse Weighted Bipartite b-Matching
  • Confusion Graph: Detecting Confusion Communities in Large Scale Image Classification
  • SVD-Based Screening for the Graphical Lasso
    • NTT
  • An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization
    • Hanna Sumita
  • Attachment Centrality for Weighted Graphs
  • Orthogonal and Nonnegative Graph Reconstruction for Large Scale Clustering
  • A Partitioning Algorithm for Maximum Common Subgraph Problems
  • Fast Change Point Detection on Dynamic Social Networks
  • Restart and Random Walk in Local Search for Maximum Vertex Weight Cliques
  • Directly Minimizing Normalized Cut for Large Scale Data
  • Robust Advertisement Allocation
  • Cardinality Encodings for Graph Optimization Problems
  • Manipulating Opinion Diffusion in Social Networks

IJCAI 2018

  • Improving Information Centrality of a Node in Complex Networks by Adding Edges
  • Efficient Pruning of Large Knowledge Graphs
  • An Exact Algorithm for Maximum k-Plexes in Massive Graphs
  • Axiomatization of the PageRank Centrality
  • A Property Testing Framework for the Theoretical Expressivity of Graph Kernels
  • Differentiable Submodular Maximization
    • Andreas Krause

International Conference on Artificial Intelligence and Statistics

AISTATS 2016

  • Graph Sparsification Approaches for Laplacian Smoothing

AISTATS 2018

  • ✔Combinatorial Preconditioners for Proximal Algorithms on Graphs
    • なんか特定の種類の問題を早く解きたいので、グラフを森に分割すると良いことがあるらしい？！
  • Growth-Optimal Portfolio Selection under CVaR Constraints
  • Accelerated Stochastic Power Iteration
    • PCAのためのアルゴリズムで、sample complexityと#iter.がきになる
  • Can clustering scale sublinearly with its clusters? A variational EM acceleration of GMMs and k-means
    • O(nkd)を切れるか？！
  • Optimal Submodular Extensions for Marginal Estimation
  • Matrix completability analysis via graph k-connectivity
    • completabilityをk枝連結性と関連付け
  • One-shot Coresets: The Case of k-Clustering
    • 一発でいい感じの要約データを作れますか？
  • Community Detection in Hypergraphs: Optimal Statistical Limit and Efficient Algorithms
  • ✔Robust Maximization of Non-Submodular Objectives
    • いくつか消滅するタイプのロバスト性、既存のあのパラメタを考えれば、非劣モジュラでも何とかなる
  • Statistically Efficient Estimation for Non-Smooth Probability Densities
    • Best paper
  • Factor Analysis on a Graph
  • ✔Submodularity on Hypergraphs: From Sets to Sequences
    • Krause、有向グラフになるらしい…
  • Achieving the time of 1-NN, but the accuracy of k-NN
    • 分散計算機資源
  • Reducing Crowdsourcing to Graphon Estimation, Statistically
  • Online Continuous Submodular Maximization
    • Frank-Wolfの変種を使う、regretとか考えるよねー
  • Labeled Graph Clustering via Projected Gradient Descent
    • SDPベースは遅いです

AISTATS 2018

  • Distributionally Robust Submodular Maximization
  • Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions 2: Numerical integrators
  • No-regret algorithms for online k-submodular maximization
  • Restarting Frank-Wolfe
  • Markov Properties of Discrete Determinantal Point Processes
  • Matroids, Matchings, and Fairness
  • Learning Determinantal Point Processes by Corrective Negative Sampling
  • Sampling from Non-Log-Concave Distributions via Variance-Reduced Gradient Langevin Dynamics
  • A Fast Sampling Algorithm for Maximum Inner Product Search
  • Structured Robust Submodular Maximization: Offline and Online Algorithms

IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology

Conference on Uncertainty in Artificial Intelligence

UAI 1998

  • Marginalizing in Undirected Graph and Hypergraph Models
    • marginal distribution: 周辺分布

UAI 1999

  • Random Algorithms for the Loop Cutset Problem
    • 最小閉路カットセット
    • $$O(c 6^k kn)$$ステップ
    • kは最小解のサイズ

UAI 2001

  • Efficient Approximation for Triangulation of Minimum Treewidth

UAI 2004

  • On Finding Minimal w-cutset
  • A Complete Anytime Algorithm for Treewidth

UAI 2007

  • Reachability Under Uncertainty
  • Search for Choquet-optimal paths under uncertainty

UAI 2008

  • Clique Matrices for Statistical Graph Decomposition and Parameterising Restricted Positive Definite Matrices

UAI 2010

  • Exact and Approximate Inference in Associative Hierarchical Networks using Graph Cuts

UAI 2011

  • Suboptimality Bounds for Stochastic Shortest Path Problems
  • Generalized Fast Approximate Energy Minimization via Graph Cuts: a-Expansion b-Shrink Moves
  • Graph Cuts is a Max-Product Algorithm
  • Planar Cycle Covering Graphs

UAI 2012

  • Spectral Estimation of Conditional Random Graph Models for Large-Scale Network Data
  • Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
  • Fast Graph Construction Using Auction Algorithm

UAI 2013

  • Treedy: A Heuristic for Counting and Sampling Subsets
  • Structured Convex Optimization under Submodular Constraints

UAI 2014

  • A Unified Approach to Fast Algorithms for Submodular Optimization based on Continuous Relaxations and Rounding

UAI 2015

  • Revisiting Non-Progressive Influence Models: Scalable Influence Maximization in Social Networks
    • 熱伝導を取りいれた非進歩的（選択が戻ったりする）な拡散モデル
    • 劣モジュラ，で，σが閉じた式で表せるっぽい？
  • Parameterizing the Distance Distribution of Undirected Networks
  • Revisiting Non-Progressive Influence Models: Scalable Influence Maximization in Social Networks
  • Averaging of Decomposable Graphs by Dynamic Programming and Sampling

International Conference on Antonomous Agents and Multiagent Sytems

AAMAS 2015

機械学習

Conference on Neural Information Processing Systems

NIPS 2013

NIPS 2014

  • Provable Submodular Minimization using Wolfe's Algorithm
    • 1976年の手法だけど，あんま解析されてなかった
    • 擬多項式時間保証を得られた
  • ✔Parallel Double Greedy Submodular Maximization
    • 非単調な場合の二重貪欲の並列化
    • 数十億辺規模のグラフで実験

NIPS 2016

  • A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++
    • $$\beta k$$クラスタでいいなら定数近似
  • Adaptive Maximization of Pointwise Submodular Functions With Budget Constraint
    • 貪欲はほぼ最適か？そうでもないので、どういう時か調べる
  • An Efficient Streaming Algorithm for the Submodular Cover Problem
    • ワンパス、bicriteria
  • Budgeted stream-based active learning via adaptive submodular maximization
    • Fujii-Kashima
  • Community Detection on Evolving Graphs
    • モデルの話し
  • Deep Submodular Functions: Definitions and Learning
    • Jeff A. Bilmes, すごそう(粉蜜柑)
  • Dimensionality Reduction of Massive Sparse Datasets Using Coresets
    • 主成分分析のためのコアセット計算; nとdに依存しない＋非自明な近似が得られるか（Wikipediaのdocument-term行列）
  • Estimating the Size of a Large Network and its Communities from a Random Sample
  • Fast Distributed Submodular Cover: Public-Private Data Summarization
  • Graph Clustering: Block-models and model free results
    • モデルから来ていると仮定しないで正しさの保証; データの統計に依存
  • Graphons, mergeons, and so on!
    • Graphonからグラフをサンプルしたとして、階層的クラスタリング
    • 「正しさ」、統計的一貫性などの議論
  • k*-Nearest Neighbors: From Global to Local
    • 古典的な問題=最適な近傍数と重みが分からん！←解決します！
  • Learning Influence Functions from Incomplete Observations
    • David Kempe、正当な方向っぽい
  • Leveraging Sparsity for Efficient Submodular Data Summarization
    • 施設配置問題、全点対は重めなので、最近傍だけ計算←強い仮定が必要
    • やってこと: 実は必要ない、最近傍計算を高速化
  • Maximization of Approximately Submodular Functions
  • ✔Maximizing Influence in an Ising Network: A Mean-Field Optimal Solution
    • 意見＝スピン、物理的解釈＝磁化を最大化、ICとかと全然違う（っぽい）アルゴリズムを提案
  • On Graph Reconstruction via Empirical Risk Minimization: Fast Learning Rates and Scalability
    • グラフ再構築=対全体の平均誤差の最小化、オーダーが改善
  • On Valid Optimal Assignment Kernels and Applications to Graph Classification
    • 畳込みカーネルじゃなくて、割当カーネルで頑張る
  • Robust k-means: a Theoretical Revisit
    • 外れ値つきk-means; 正則化 or トリミング
    • 頑健性・一貫性の理論解析→ちょっと改変すると改善するっぽい
  • Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
    • 疎・雑音があると固有ベクトルが局在化しちゃう→局所化固有ベクトルから正規化行列を学習する
    • コミュニティ検出、クラスタリング、行列補完とか
  • Simple and Efficient Weighted Minwise Hashing
    • すごいらしいMin-Hash
  • ✔The Multiscale Laplacian Graph Kernel
    • 既存のグラフカーネル…局所的か大域的すぎる
    • Feature Space Laplacian Graphカーネルを再帰的に適用
    • いい感じに適用するためにちょっとテクニカルにも頑張る
  • The Power of Optimization from Samples
    • Yaron Singer
    • 曲率制限時に、どのくらいサンプリングすると、どんな近似比が得られるか？
  • The Product Cut
    • 多方グラフ分割、乗法的カットベース目的、頑張って解く

NIPS 2017

  • Learning Graph Representations with Embedding Propagation
    • Embedding Propagation、教師なし、半教師あり学習手法
  • Cost efficient gradient boosting
    • 精度が高いまま少ない・安い特徴で速い評価がしたい
    • deep boosted regression treeベース
  • ✔Practical Hash Functions for Similarity Estimation and Dimensionality Reduction
    • Mikkel Thorup
    • 色々なハッシュを実験的に評価。MurmurHash3も（理論的保証は無いけど）。
  • Improved Graph Laplacian via Geometric Self-Consistency
    • kernel bandwidthをどうしよう。データのgeometryを保持するようにパラメタを設定
  • ✔The Importance of Communities for Learning to Influence
    • Yaron Singer
    • 既知：生成モデルが知らず、学習した場合、定数近似は厳しい。
    • コミュニティ構造を利用して、学習データから最適化する。実験的には上手くいくゾイ。
    • Stochastic blockモデルなら定数近似
  • Inductive Representation Learning on Large Graphs
    • Jure Leskovec
    • 普通のはグラフの全部の頂点が見られないと低次元埋め込みが出来ない→出来るようにしました！
  • ✔Gradient Methods for Submodular Maximization
    • Hamed Hassani
    • 連続劣モジュラ関数の最大化。凸性は無いけど、stochastic projected gradientが上手く行きますよ！
    • 単調連続DR-劣モジュラで不動点は1/2近似。確率的劣モジュラでもいい感じ
  • ✔Influence Maximization with ε-Almost Submodular Threshold Functions
    • Wei Chen
    • 閾値モデルで各頂点の関数がε-almost 劣モジュラの場合を考えます
    • 劣モジュラじゃなくなった途端に難しくなります
    • ε-almost 劣モジュラが$$\ell$$個の場合、$$ (1-\epsilon)^{\ell} (1-1/e) $$近似
  • Subset Selection under Noise
    • 雑音単調関数で考える（今までは雑音単調劣モジュラとか）。雑音を加味したうまいアルゴリズムPONSSを考案
    • 影響最大化とsparse regressionで実験評価
  • ✔Continuous DR-submodular Maximization: Structure and Algorithms
    • An Bian, Andreas Krause
    • 非単調DR劣モジュラ関数を凸制約で最大化
    • 2つアルゴリズムを提案したよ
  • ✔Nonbacktracking Bounds on the Influence in Independent Cascade Models
    • influenceのバウンドを（また）提案
    • 時間-精度のトレードオフを設定可能
  • From which world is your graph
    • 統計的な感じで構造（latent patterns）を見つけますよ。
  • Clustering Stable Instances of Euclidean k-means
    • ヒューリスティクスが何で上手く動くのか？additive perturbation stabilityを提案
    • 感覚的には：ちょっと点が動いても大丈夫。アルゴリズムも提案しました
  • Affinity Clustering: Hierarchical Clustering at Scale
    • 階層的なグラフクラスタリング、MSTをベース、MapReduceで速い
  • Sparse Embedded k-Means Clustering
  • K-Medoids For K-Means Seeding
    • 実験をする。k-medoidsの方法をk-meansにも適用してみると（k-means++よりも）上手く行ってしまった。
  • Inhomogeneous Hypergraph Clustering with Applications
    • 普通は、ハイパーエッジがどう切断されようが、同じ費用。
    • 今回は切断のされ方によって違う費用を考えるお。費用が劣モジュラなら近似出来る
  • Tensor Biclustering
    • 情報理論的限界、スペクトラルなアルゴリズムを提案
  • Matrix Norm Estimation from a Few Entries
    • Schatten norms、何かグラフ的な話も
  • Graph Matching via Multiplicative Update Algorithm
    • CVの世界の話。基本的には色々制約がついたQPになる。（MWUでは無い？）
  • Streaming Weak Submodularity: Interpreting Neural Networks on the Fly
  • Decomposable Submodular Function Minimization: Discrete and Continuous
  • Differentiable Learning of Submodular Models
    • Josip Djolonga, Andreas Krause
    • Neural networksの中で劣モジュラ最小化を使いたい？
  • ✔Robust Optimization for Non-Convex Objectives
    • Yaron Singer
    • objectiveの分布に対する解→最悪時保証のある解の分布
    • robust influence maximizationに活用
  • On Frank-Wolfe and Equilibrium Computation
    • FWはconvex-concave zero sum gameの均衡点だった・・・！
  • ✔A graph-theoretic approach to multitasking
    • Noga Alon
    • 良さそうだけど良く分からん。
  • Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
    • ちゃんとした理論の話っぽい
  • Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback
    • 色々な人の研究の後続っぽい
  • Interactive Submodular Bandit
    • Andreas Krause
  • Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach
    • (streaming = 普通のやつ) × (robust = m個任意に消えちゃう)を考えてみました
  • Minimizing a Submodular Function from Samples
    • Yaron Singer
    • 1/2-o(1)の近似比が境界
  • Approximate Supermodularity Bounds for Experimental Design
    • supermodularじゃないけど、出来るので、性能評価をしてみたよ

NeurIPS 2018

  • Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression
  • Data-Driven Clustering via Parameterized Lloyd's Families
  • Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
  • Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
  • Adversarially Robust Optimization with Gaussian Processes
    • Stefanie Jegelka
  • Sublinear Time Low-Rank Approximation of Distance Matrices
  • Found Graph Data and Planted Vertex Covers
    • Jon Kleinberg
  • Do Less, Get More: Streaming Submodular Maximization with Subsampling
    • Moran Feldman, Amin Karbasi, Ehsan Kazemi
  • Learning convex polytopes with margin
  • Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions
    • Jeff Bilmes
  • Approximation algorithms for stochastic clustering
  • RetGK: Graph Kernels based on Return Probabilities of Random Walks
  • HOGWILD!-Gibbs can be PanAccurate
  • (Probably) Concave Graph Matching
  • Non-monotone Submodular Maximization in Exponentially Fewer Iterations
    • Yaron Singer
  • Top-k lists: Models and Algorithms
    • Ravi Kumar
  • Robust Hypothesis Testing Using Wasserstein Uncertainty Sets
  • Practical Methods for Graph Two-Sample Testing
    • Ulrike von Luxburg
  • Multi-objective Maximization of Monotone Submodular Functions with Cardinality Constraint
  • Understanding Regularized Spectral Clustering via Graph Conductance
  • Generalizing Graph Matching beyond Quadratic Assignment Model
  • Quadratic Decomposable Submodular Function Minimization

NeurIPS 2019

  • ✔The Parameterized Complexity of Cascading Portfolio Scheduling
  • ✔Online sampling from log-concave distributions
  • ✔Flexible Modeling of Diversity with Strongly Log-Concave Distributions
  • The Randomized Midpoint Method for Log-Concave Sampling
  • Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning
  • Approximation Ratios of Graph Neural Networks for Combinatorial Problems
  • q-means: A quantum algorithm for unsupervised machine learning
  • End to end learning and optimization on graphs
  • Towards a Zero-One Law for Column Subset Selection
  • Fast and Accurate Least-Mean-Squares Solvers
  • Approximating the Permanent by Sampling from Adaptive Partitions
  • Counting the Optimal Solutions in Graphical Models
  • Exact Combinatorial Optimization with Graph Convolutional Neural Networks

NeurIPS 2020

  • ✔Online MAP Inference of Determinantal Point Processes
  • ✔Sampling from a k-DPP without looking at all items
  • ✔Testing Determinantal Point Processes
  • Submodular Maximization Through Barrier Functions
  • Fairness in Streaming Submodular Maximization: Algorithms and Hardness
  • Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time
  • Submodular Meta-Learning
  • Dynamic Submodular Maximization
  • Robust Sequence Submodular Maximization
  • Fully Dynamic Algorithm for Constrained Submodular Optimization
  • Continuous Submodular Maximization: Beyond DR-Submodularity
  • Improved Algorithms for Online Submodular Maximization via First-order Regret Bounds
  • Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
  • A Single Recipe for Online Submodular Maximization with Adversarial or Stochastic Constraints
  • Concentration Bounds for Co-occurrence Matrices of Markov Chains
  • Provable Overlapping Community Detection in Weighted Graphs
  • Scalable Approximation Algorithm for Fair k−center Clustering
  • Faster DBSCAN via subsampled similarity queries
  • Online Influence Maximization under Linear Threshold Model
  • Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions
  • Improved Guarantees for k-means++ and k-means++ Parallel
  • Correlation Robust Influence Maximization
  • Efficient Clustering Based On A Unified View Of K-means And Ratio-cut
  • Sliding Window Algorithms for k-Clustering Problems
  • Simple, Scalable Sparse k-means by Feature Ranking
  • Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization
  • Community detection using fast low-cardinality semidefinite programming

  • GCOMB: Learning Budget-constrained Combinatorial Algorithms over Billion-sized Graphs
  • Model Interpretability through the lens of Computational Complexity
  • Co-exposure Maximization in Online Social Networks
  • On the Power of Louvain for Graph Clustering
  • Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
  • Fast and Accurate k-means++ via Rejection Sampling

International Conference on Machine Learning

ICML 2014

  • Influence Function Learning in Information Diffusion Networks
    • 学習するにしても情報拡散のモデル化が物凄くシビア
    • 被覆関数っぽいので，random basis関数の凸結合で表す
    • モデルを定義しなくても良い
  • ✔Fast Multi-Stage Submodular Maximization
    • 多段階でメモリを節約，1000倍とか速くなった

ICML 2015

  • An Aligned Subtree Kernel for Weighted Graphs
    • 実験すると分類の精度で既存より良い
  • A Provable Generalized Tensor Spectral Method for Uniform Hypergraph Partitioning
    • 類似度は普通2点間
    • CVとかTextMiningではmulti-wayなのでhypergraphを分割したくなる
    • tensor trace optimization として
  • A Divide and Conquer Framework for Distributed Graph Clustering
    • 分割統治，小さいクラスタのサイズがo(√n)でOK（よくわからん）
  • ✔Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with Consistent Speedup
    • 基本は距離計算の枝刈り
    • 普通のk-meansと同じ結果を返す
  • Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions
    • 最近は凸最適化
    • random coordinate descentなるものを使う
    • 線形収束，速いらしい…
  • Inferring Graphs from Cascades: A Sparse Recovery Framework
    • 疎復元の観点から
    • IC，Voterを含む一般的なモデルを考える
    • グラフの辺（重みパラメータも）を高確率で復元
  • ✔Faster cover trees
    • cover tree data structure…厳密最近傍クエリに有効
    • もっと早くしました
    • 頂点数: O(n)→n
    • 並列で処理できるお
    • キャッシュ効率も良く
  • ✔On Greedy Maximization of Entropy
    • 何で1-1/eより良い（ほぼ最適）？
    • curvatureに基づいて

ICML 2016

  • k-variates++: more pluses in the k-means++
    • 一般的な密度でのサンプリング
    • Arthur-Vassilvitskii近似保証の一般化
    • 何か上位互換っぽい感じ？
    • differential privacyへの応用
  • ✔Correlation Clustering and Biclustering with Locally Bounded Errors
    • 各頂点における誤り数の何かしらの関数で考える
    • 丸めアルゴリズム，定数近似
  • Fast k-means with accurate bounds
    1. 高速化，3倍くらい
    2. 距離推定の奴の改善，1.8倍くらい
  • K-Means Clustering with Distributed Dimensions
    • 次元がいくつかのマシンに分割
    • 新しい近似アルゴリズム
      • 通信費用少ない，定数近似
  • Fast Constrained Submodular Maximization: Personalized Data Summarization
    • 単調とは限らない，p-systemとl knapsackの交差制約
      • 制約の例が参考になるのでは？！
    • クエリ数 vs. 近似比
  • Learning Sparse Combinatorial Representations via Two-stage Submodular Maximization
    • Krause, Singer
    • 二段階の奴，基数制約劣モジュラ最大化の一般化
    • 連続最適化と局所探索1/2近似
  • Speeding up k-means by approximating Euclidean distances via block vectors
    • Holder不等式なるもので，ユークリッド距離を近似する
    • で，k-meansに応用，Yinyangにも優る
  • ✔Algorithms for Optimizing the Ratio of Submodular Functions
    • Bilmes
    • 新しい問題，割りとタイトな結果（hardnessと手法），効率を調べる
    • 差の最小化との関連も
  • Horizontally Scalable Submodular Maximization
    • Krause
    • 分散劣モジュラ最大化，各マシンの容量に制約がある

ICML 2017

  • Fast k-Nearest Neighbour Search via Prioritized DCI
  • Distributed and Provably Good Seedings for k-Means in Constant Rounds
    • Andreas Krause
  • Robust Guarantees of Stochastic Greedy Algorithms
  • Analysis and Optimization of Graph Decompositions by Lifted Multicuts
  • Deep Spectral Clutering Learning
  • Re-revisiting Learning on Hypergraphs: Confidence Interval and Subgradient Method
  • ChoiceRank: Identifying Preferences from Node Traffic in Networks
  • Guarantees for Greedy Maximization of Non-submodular Functions with Applications
  • Bayesian inference on random simple graphs with power law degree distributions
  • Co-clustering through Optimal Transport
  • Clustering High Dimensional Dynamic Data Streams
  • Diffusion Independent Semi-Bandit Influence Maximization
  • Robust Budget Allocation via Continuous Submodular Functions
  • Adapting kernel representations online using submodular maximization
  • Robust Submodular Maximization: A Non-Uniform Partitioning Approach
  • Deletion-Robust Submodular Maximization: Data Summarization with "the Right to be Forgotten"
  • Deriving Neural Architectures from Sequence and Graph Kernels
  • Probabilistic Submodular Maximization in Sub-Linear Time
  • Efficient Optimization for Connected Subgraph Detection

ICML 2018

  • Quickshift++: Provably Good Initializations for Sample-Based Mean Shift
    • Quick Shift clustering のための初期seedingを与える。
  • Learning Diffusion using Hyperparameters
    • 辺確率がハイパーパラメータと各頂点の特徴の関数で記述できる時、sample complexityが|E|/d（ハイパーパラメータの次元）まで下がる
  • K-means clustering using random matrix sparsification
    • データ点からなる行列を適当に疎化してもk-meansはあまり変わらない！
  • ✔Learning to Optimize Combinatorial Functions
    • 劣モジュラ関数のoptimization from samplesは難しい
    • 違う基準を導入、学習・最適化できる条件
  • Representation Learning on Graphs with Jumping Knowledge Networks
  • NetGAN: Generating Graphs via Random Walks
  • Parameterized Algorithms for the Matrix Completion Problem
    • 行列補完問題を考える、最小ランク、異なる列の個数最小化。parameterized complexityだよ。
  • Katyusha X: Simple Momentum Method for Stochastic Sum-of-Nonconvex Optimization
  • signSGD: Compressed Optimisation for Non-Convex Problems
  • Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?
    • マトロイド制約で乱択貪欲すると定数近似。初めて。
  • ✔Data Summarization at Scale: A Two-Stage Submodular Approach
    • データがでかいときに、第一段でground setを縮小するよ
  • Learning Steady-States of Iterative Algorithms over Graphs
    • グラフ上の反復法に基づくアルゴリズムを問題ごとに早くするように学習したいよ。
  • Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering
  • The Well-Tempered Lasso
  • Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams
    • 各要素がランダムに来るならば、1/2近似を超えられる！そうでないと1/2が限界。
  • Safe Element Screening for Submodular Function Minimization
  • Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints
    • そのまま。
  • ✔Network Global Testing by Counting Graphlets
    • よくわからん。パスとかサイクルの数の統計量を作った。
  • Ultra Large-Scale Feature Selection using Count-Sketches
    • データを小さく表現したままSGDを実行するよ。
  • Adversarial Attack on Graph Structured Data
  • ✔Improved large-scale graph learning through ridge spectral sparsification
    • Spectral sparsificationを半教師付き学習のもろもろに組み込むよ。nlog^3n時間。
  • Parallel and Streaming Algorithms for K-Core Decomposition
    • 分散ストリーミングアルゴリズム。何故ICML通る？
  • Fast Approximate Spectral Clustering for Dynamic Networks
    • polynomial-based randomized sketchingでめっちゃ早くしたよ！
  • Greed is Still Good: Maximizing Monotone Submodular+Supermodular (BP) Functions
    • 貪欲かdiscrete semi-gradient basedで、curvature制限時には何とかなります。
  • Constrained Interacting Submodular Groupings
    • 各ブロックがいい感じ、互いに冗長にはなりにくい、みたいな。マトロイド制約。ensembles of classification/regression models
  • Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice
    • 多項式質問計算量。影響最大化への枠組み提案。
  • Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
    • グラフ構造な設定。局所的な関数の和として、大域的連続劣モジュラ関数が定義される。
  • Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices
  • Solving Partial Assignment Problems using Random Clique Complexes
    • 部分割当問題を、ランダムクリークのマッチングで表現して解きます～。
  • Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
    • 劣モジュラ重みがカットに応じて割り当てられる。なんか深淵。
  • Distributional Optimization from Samples
  • ✔Approximation Guarantees for Adaptive Sampling
  • Spectrally approximating large graphs with smaller graphs
    • coarseningするといい感じ、spectral clusteringにも使えるよ！

ICML 2019

  • Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm
  • Optimal Continuous DR-Submodular Maximization and Applications to Provable Mean Field Inference
  • Multiplicative Weights Updates as a distributed constrained optimization algorithm: Convergence to second-order stationary points almost always
  • Inference and Sampling of K33-free Ising Models
  • Fast Incremental von Neumann Graph Entropy Computation: Theory, Algorithm, and Applications
  • Robust Influence Maximization for Hyperparametric Models
  • Sum-of-Squares Polynomial Flow
  • Concentration Inequalities for Conditional Value at Risk
  • Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio
  • Submodular Observation Selection and Information Gathering for Quadratic Models
  • Submodular Cost Submodular Cover with an Approximate Oracle
  • Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
  • A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes
  • Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
  • Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity
  • Faster Algorithms for Binary Matrix Factorization
  • A Better k-means++ Algorithm via Local Search
  • A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes
  • Graph Resistance and Learning from Pairwise Comparisons

通信ネットワーク

IEEE International Conference on Computer Communications

INFOCOM 2015

  • A Better Constant Approximation for Minimum 3-connected m-dominating Set Problem in Unit Disk Graph using Tutte Decomposition
  • On the Progressive Spread over Strategic Diffusion: Asymptotic and Computation
  • Cliques in Hyperbolic Random Graphs
  • De-anonymizing scale-free social networks by percolation graph matching

INFOCOM 2106

  • To delay or not: temporal vaccination games on networks
  • Distributed Spectral Decomposition in Networks by Complex Diffusion and Quantum Random Walk
  • Cost-aware Targeted Viral Marketing in Billion-scale Networks
  • Network Utility Maximization with Path Cardinality Constraints
  • Performance-Guaranteed Strongly Connected Dominating Sets in Heterogeneous Wireless Sensor Networks
  • Performance-Guaranteed Approximation Algorithm for Fault-Tolerant Connected Dominating Set in Wireless Networks
  • Profit Maximization for Multiple Products in Online Social Networks
  • Using Crowdsourced Data in Location-based Social Networks to Explore Influence Maximization
  • Minimum Cost Seed Set for Competitive Social Influence
  • Terminal-Set-Enhanced Community Detection in Social Networks
  • Survivability in Time-varying Networks
  • High-Precision Shortest Distance Estimation for Large-Scale Social Networks

情報検索

ACM International Conference on Research and Development in Information Retrieval

SIGIR 2014

「気になった論文」をウィキ内検索
最終更新：2021年11月01日 19:34